More Like this

1. On Differentially Private U Statistics

   Chaudhuri, Kamalika; Loh, Po-Ling; Pandey, Shourya; Sarkar, Purnamrita (July 2024, https://doi.org/10.48550/arXiv.2407.04945)

   We consider the problem of privately estimating a parameter 𝔼[h(X1,…,Xk)], where X1, X2, …, Xk are i.i.d. data from some distribution and h is a permutation-invariant function. Without privacy constraints, standard estimators are U-statistics, which commonly arise in a wide range of problems, including nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and can be shown to be minimum variance unbiased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied to obtain confidence intervals, we show that they can lead to suboptimal private error, e.g., constant-factor inflation in the leading term, or even Θ(1/n) rather than O(1/n²) in degenerate settings. To remedy this, we propose a new thresholding-based approach using local Hájek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics. 

   more » « less
2. Minimax Kernel Machine Learning for a Class of Doubly Robust Functionals with Application to Proximal Causal Inference

   Amiremad Ghassami, Andrew Ying (April 2022, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics)

   Gustau Camps-Valls; Francisco J. R. Ruiz; Isabel Valera (Ed.)

   Robins et al. (2008) introduced a class of influence functions (IFs) which could be used to obtain doubly robust moment functions for the corresponding parameters. However, that class does not include the IF of parameters for which the nuisance functions are solutions to integral equations. Such parameters are particularly important in the field of causal inference, specifically in the recently proposed proximal causal inference framework of Tchetgen Tchetgen et al. (2020), which allows for estimating the causal effect in the presence of latent confounders. In this paper, we first extend the class of Robins et al. to include doubly robust IFs in which the nuisance functions are solutions to integral equations. Then we demonstrate that the double robustness property of these IFs can be leveraged to construct estimating equations for the nuisance functions, which enables us to solve the integral equations without resorting to parametric models. We frame the estimation of the nuisance functions as a minimax optimization problem. We provide convergence rates for the nuisance functions and conditions required for asymptotic linearity of the estimator of the parameter of interest. The experiment results demonstrate that our proposed methodology leads to robust and high-performance estimators for average causal effect in the proximal causal inference framework. 

   more » « less
3. Differentially private estimation of U statistics

   Kamalika Chaudhuri, Po-Ling Loh (January 2024, Proceedings of Machine Learning Research)

   Under Review for COLT 2024 (Ed.)

   In this paper, we consider the problem of private estimation of U statistics. U statistics are widely used estimators that naturally arise in a broad class of problems, from nonparametric signed rank tests to subgraph counts in random networks. They are simply averages of an appropriate kernel applied to all subsets of a given size (also known as the degree) of sample size n. However, despite the recent outpouring of interest in private mean estimation, private algorithms for more general U statistics have received little attention. We propose a framework where, for a broad class of U statistics, one can use existing tools in private mean estimation to obtain confidence intervals where the private error does not overwhelm the irreducible error resulting from the variance of the U statistics. However, in specific cases that arise when the U statistics degenerate or have vanishing moments, the private error may be of a larger order than the non-private error. To remedy this, we propose a new thresholding-based approach that uses Hajek projections to re-weight different subsets. As we show, this leads to more accurate inference in certain settings. 

   more » « less
4. Priv'IT: Private and Sample Efficient Identity Testing.

   Cai, Bryan; Daskalakis, Constantinos; Kamath, Gautam (January 2017, 34th International Conference on Machine Learning)

   We develop differentially private hypothesis testing methods for the small sample regime. Given a sample  from a categorical distribution p over some domain Σ, an explicitly described distribution q over Σ, some privacy parameter ε, accuracy parameter α, and requirements βI and βII for the type I and type II errors of our test, the goal is to distinguish between p=q and dTV(p,q)≥α. We provide theoretical bounds for the sample size || so that our method both satisfies (ε,0)-differential privacy, and guarantees βI and βII type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the χ2-test with noisy counts, or standard approaches such as repetition for endowing non-private χ2-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing. 

   more » « less
5. The Fundamental Limits of Structure-Agnostic Functional Estimation

   Balakrishnan, Sivaraman; Kennedy, Edward; Wasserman, Larry (January 2023, arXivorg)

   Many recent developments in causal inference, and functional estimation problems more generally, have been motivated by the fact that classical one-step (first-order) debiasing methods, or their more recent sample-split double machine-learning avatars, can outperform plugin estimators under surprisingly weak conditions. These first-order corrections improve on plugin estimators in a black-box fashion, and consequently are often used in conjunction with powerful off-the-shelf estimation methods. These first-order methods are however provably suboptimal in a minimax sense for functional estimation when the nuisance functions live in Holder-type function spaces. This suboptimality of first-order debiasing has motivated the development of "higher-order" debiasing methods. The resulting estimators are, in some cases, provably optimal over Holder-type spaces, but both the estimators which are minimax-optimal and their analyses are crucially tied to properties of the underlying function space. In this paper we investigate the fundamental limits of structure-agnostic functional estimation, where relatively weak conditions are placed on the underlying nuisance functions. We show that there is a strong sense in which existing first-order methods are optimal. We achieve this goal by providing a formalization of the problem of functional estimation with black-box nuisance function estimates, and deriving minimax lower bounds for this problem. Our results highlight some clear tradeoffs in functional estimation -- if we wish to remain agnostic to the underlying nuisance function spaces, impose only high-level rate conditions, and maintain compatibility with black-box nuisance estimators then first-order methods are optimal. When we have an understanding of the structure of the underlying nuisance functions then carefully constructed higher-order estimators can outperform first-order estimators. 

   more » « less