34 citations · 80 across the 12 of their papers we have counts for
14 papers
Why Forget-Only Unlearning Needs Memorization
Luka Radić, Vikrant Singhal, Amartya Sanyal
Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearnin…
Uniformity Testing under User-Level Local Privacy
Clément L. Canonne, Abigail Gentle, Vikrant Singhal
We initiate the study of distribution testing under \emph{user-level} local differential privacy, where each of users contributes samples from the unknown underlying distri…
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…
Private Distribution Learning with Public Data: The View from Sample Compression
Shai Ben-David, Alex Bie, Clément L. Canonne +2
We study the problem of private distribution learning with access to public data. In this setup, which we refer to as public-private learning, the learner is given public and priva…
A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
Vikrant Singhal
We present the first -differentially private, computationally efficient algorithm that estimates the means of product distributions over accurately in tota…
A Bias-Accuracy-Privacy Trilemma for Statistical Estimation
Gautam Kamath, Argyris Mouzakis, Matthew Regehr +3
Differential privacy (DP) is a rigorous notion of data privacy, used for private statistics. The canonical algorithm for differentially private mean estimation is to first clip the…
Private Estimation with Public Data
Alex Bie, Gautam Kamath, Vikrant Singhal
We initiate the study of differentially private (DP) estimation with access to a small amount of public data. For private estimation of d-dimensional Gaussians, we assume that the…
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…
A Private and Computationally-Efficient Estimator for Unbounded Gaussians
Gautam Kamath, Argyris Mouzakis, Vikrant Singhal +2
We give the first polynomial-time, polynomial-sample, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution in $\mat…
Privately Learning Subspaces
Vikrant Singhal, Thomas Steinke
Private data analysis suffers a costly curse of dimensionality. However, the data often has an underlying low-dimensional structure. For example, when optimizing via gradient desce…
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…
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…
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…
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal
We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm's task is to identify the…