Sharper Utility Bounds for Differentially Private Models
Not on the map. Why?
Abstract (arXiv)
In this paper, by introducing Generalized Bernstein condition, we propose the first Obig(frac√pnεbig) high probability excess population risk bound for differentially private algorithms under the assumptions G-Lipschitz, L-smooth, and Polyak-Lojasiewicz condition, based on gradient perturbation method. If we replace the properties G-Lipschitz and L-smooth by α-H"older smoothness (which can be used in non-smooth setting), the high probability bound comes to Obig(n^-fracα1+2αbig) w.r.t n, which cannot achieve Oleft(1/nright) when α∈(0,1]. To solve this problem, we propose a variant of gradient perturbation method, textbfmax1,g-Normalized Gradient Perturbation (m-NGP). We further show that by normalization, the high probability excess population risk bound under assumptions α-H"older smooth and Polyak-Lojasiewicz condition can achieve Obig(frac√pnεbig), which is the first Oleft(1/nright) high probability excess population risk bound w.r.t n for differentially private algorithms under non-smooth conditions. Moreover, we evaluate the performance of the new proposed algorithm m-NGP, the experimental results show that m-NGP improves the performance of the differentially private model over real datasets. It demonstrates that m-NGP improves the utility bound and the accuracy of the DP model on real datasets simultaneously.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 35 of its 74 references that are in the map. First posted on arXiv 22 Apr 2022.
Builds on
35 of 74 references.
References · 35
- 2016Deep Learning with Differential Privacycited by 2,682
- 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
- 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
- 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
- 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
- 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
- 2017Collecting Telemetry Data Privatelycited by 147
- 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
23 more
- 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
- 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
- 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
- 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
- 2016Identity Matters in Deep Learningcited by 107
- 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
- 2016A Geometric Analysis of Phase Retrievalcited by 92
- 2019Sharper bounds for uniformly stable algorithmscited by 91
- 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
- 2017Efficient Private ERM for Smooth Objectivescited by 61
- 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
- 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
- 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
- 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
- 2019Differentially Private Bayesian Linear Regressioncited by 24
- 2021Differentially Private SGD with Non-Smooth Lossescited by 22
- 2019Differentially Private Markov Chain Monte Carlocited by 18
- 2020Differentially Private Bayesian Inference for Generalized Linear Modelscited by 16
- 2019Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacycited by 13
- 2021Differentially Private Correlation Clusteringcited by 13
- 2015Unregularized Online Learning Algorithms with General Loss Functionscited by 11
- 2021Differentially Private Densest Subgraph Detectioncited by 7
- 2015Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methodscited by 3
Built on by
Citing papers per year: 2022: 1; 2023: 0; 2024: 2.
3 papers.