142 citations · 842 across the 49 of their papers we have counts for
28 papers · 1 filter
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Gautam Kamath
We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distribut…
Not All Learnable Distribution Classes are Privately Learnable
Mark Bun, Gautam Kamath, Argyris Mouzakis +1
We give an example of a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under $(\vareps…
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid +1
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to…
New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
We prove new lower bounds for statistical estimation tasks under the constraint of -differential privacy. First, we provide tight lower bounds for private covaria…
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
We give the first polynomial-time algorithm to estimate the mean of a -variate probability distribution with bounded covariance from independent samples subject t…
Robust Estimation for Random Graphs
Jayadev Acharya, Ayush Jain, Gautam Kamath +2
We study the problem of robustly estimating the parameter of an Erdős-Rényi random graph on nodes, where a fraction of nodes may be adversarially corrupted. After showi…
The Price of Tolerance in Distribution Testing
Clément L. Canonne, Ayush Jain, Gautam Kamath +1
We revisit the problem of tolerant distribution testing. That is, given samples from an unknown distribution over , is it -close to or $\varepsi…
The Discrete Gaussian for Differential Privacy
Clément L. Canonne, Gautam Kamath, Thomas Steinke
A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Unfortunately, using a continuous dist…
Locally Private Hypothesis Selection
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni +3
We initiate the study of hypothesis selection under local differential privacy. Given samples from an unknown probability distribution and a set of probability distribution…
Private Mean Estimation of Heavy-Tailed Distributions
Gautam Kamath, Vikrant Singhal, Jonathan Ullman
We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded -th moments. Roughly speaking, in the…
Privately Learning Markov Random Fields
Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni +1
We consider the problem of learning Markov Random Fields (including the prototypical example, the Ising model) under the constraint of differential privacy. Our learning goals incl…
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Clément L. Canonne, Xi Chen, Gautam Kamath +2
We give a nearly-optimal algorithm for testing uniformity of distributions supported on , which makes queries to a subcube condition…
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians
Gautam Kamath, Or Sheffet, Vikrant Singhal +1
Learning the parameters of Gaussian mixture models is a fundamental and widely studied problem with numerous applications. In this work, we give new algorithms for learning the par…
Private Hypothesis Selection
Mark Bun, Gautam Kamath, Thomas Steinke +1
We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution and a set of probability distributions $\math…
Private Identity Testing for High-Dimensional Distributions
Clément L. Canonne, Gautam Kamath, Audra McMillan +2
In this work we present novel differentially private identity (goodness-of-fit) testers for natural and widely studied classes of multivariate product distributions: Gaussians in $…
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, Audra McMillan +2
Hypothesis testing plays a central role in statistical inference, and is used in many settings where privacy concerns are paramount. This work answers a basic question about privat…
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
Gautam Kamath, Christos Tzamos
We investigate distribution testing with access to non-adaptive conditional samples. In the conditional sampling model, the algorithm is given the following access to a distributio…
Privately Learning High-Dimensional Distributions
Gautam Kamath, Jerry Li, Vikrant Singhal +1
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and lear…
INSPECTRE: Privately Estimating the Unseen
Jayadev Acharya, Gautam Kamath, Ziteng Sun +1
We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution , some functional , and accuracy and p…
Which Distribution Distances are Sublinearly Testable?
Constantinos Daskalakis, Gautam Kamath, John Wright
Given samples from an unknown distribution and a description of a distribution , are and close or far? This question of "identity testing" has received significant a…
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an -fraction of our samples were chosen by…
Priv'IT: Private and Sample Efficient Identity Testing
Bryan Cai, Constantinos Daskalakis, Gautam Kamath
We develop differentially private hypothesis testing methods for the small sample regime. Given a sample from a categorical distribution over some domain , an expli…
Testing Ising Models
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath
Given samples from an unknown multivariate distribution , is it possible to distinguish whether is the product of its marginals versus being far from every product distr…
Robust Estimators in High Dimensions without the Computational Intractability
Ilias Diakonikolas, Gautam Kamath, Daniel Kane +3
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an -fraction of the samples. Such questions…