8 papers · 1 filter
The Fast Mixing Mechanism for Differential Privacy
Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2
Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, s…
Efficient privacy loss accounting for subsampling and random allocation
Vitaly Feldman, Moshe Shenfeld
We consider the privacy amplification properties of a sampling scheme in which a user's data isused in steps chosen randomly and uniformly from a sequence (or set) of steps…
Near-Optimal Private Linear Regression via Iterative Hessian Mixing
Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2
We study differentially private ordinary least squares (DP-OLS) with bounded data via sketching-based mechanisms. While Gaussian sketching approaches have been explored for…
The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches
Omri Lev, Vishwak Srinivasan, Moshe Shenfeld +3
Gaussian sketching, which consists of pre-multiplying the data with a random Gaussian matrix, is a widely used technique for multiple problems in data science and machine learning,…
How Well Can Differential Privacy Be Audited in One Run?
Amit Keinan, Moshe Shenfeld, Katrina Ligett
Recent methods for auditing the privacy of machine learning algorithms have improved computational efficiency by simultaneously intervening on multiple training examples in a singl…
Privacy amplification by random allocation
Vitaly Feldman, Moshe Shenfeld
We consider the privacy amplification properties of a sampling scheme in which a user's data is used in k steps chosen randomly and uniformly from a sequence (or set) of t steps. T…
Generalization in the Face of Adaptivity: A Bayesian Perspective
Moshe Shenfeld, Katrina Ligett
Repeated use of a data sample via adaptively chosen queries can rapidly lead to overfitting, wherein the empirical evaluation of queries on the sample significantly deviates from t…
A New Analysis of Differential Privacy's Generalization Guarantees
Christopher Jung, Katrina Ligett, Seth Neel +3
We give a new proof of the "transfer theorem" underlying adaptive data analysis: that any mechanism for answering adaptively chosen statistical queries that is differentially priva…