6 papers
Instance-Optimality for Private KL Distribution Estimation
Jiayuan Ye, Vitaly Feldman, Kunal Talwar
We study the fundamental problem of estimating an unknown discrete distribution over symbols, given i.i.d. samples from the distribution. We are interested in minimizin…
Faster Rates for Private Adversarial Bandits
Hilal Asi, Vinod Raman, Kunal Talwar
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conv…
On Privately Estimating a Single Parameter
Hilal Asi, John C. Duchi, Kunal Talwar
We investigate differentially private estimators for individual parameters within larger parametric models. While generic private estimators exist, the estimators we provide repose…
Local Pan-Privacy for Federated Analytics
Vitaly Feldman, Audra McMillan, Guy N. Rothblum +1
Pan-privacy was proposed by Dwork et al. as an approach to designing a private analytics system that retains its privacy properties in the face of intrusions that expose the system…
PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
Hilal Asi, Vitaly Feldman, Hannah Keller +2
We revisit the problem of secure aggregation of high-dimensional vectors in a two-server system such as Prio. These systems are typically used to aggregate vectors such as gradient…
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu, Kunal Talwar
Fingerprinting codes are a crucial tool for proving lower bounds in differential privacy. They have been used to prove tight lower bounds for several fundamental questions, especia…