Source-linked AI summary
Efficient Private ERM for Smooth Objectives
Jiaqi Zhang, Kai Zheng, Wenlong Mou, Liwei Wang
TL;DR
The paper asks how to make differentially private ERM both accurate and computationally efficient, especially when existing convex methods require many iterations and non-convex guarantees are lacking. It uses smoothness-aware gradient-based methods, including output-perturbed gradient descent and a private non-convex optimizer, and reports faster computation, utility guarantees, and favorable empirical comparisons.
Problem
Private convex ERM methods can require at least Ω(n^2) iterations, while existing theoretical results do not cover non-convex ERM despite its importance in deep neural networks.
Method
The paper uses smoothness-aware optimization, applying gradient descent with output perturbation to strongly convex objectives and a randomized stochastic gradient variant to non-convex objectives.
Results
The proposed algorithms improve running time and utility guarantees for strongly convex objectives, provide expectation and high-probability utility guarantees for non-convex objectives, and outperform existing approaches numerically.
Takeaways & Limitations
Smoothness enables private optimization methods that are more computationally practical for convex ERM and theoretically supported for non-convex objectives.
Takeaways & Limitations
The analysis assumes smooth objectives, and the paper notes that private algorithms can have polynomial dependence on dimension, which may hurt generalization for large d.
Abstract
from arXiv · showhide
In this paper, we consider efficient differentially private empirical risk minimization from the viewpoint of optimization algorithms. For strongly convex and smooth objectives, we prove that gradient descent with output perturbation not only achieves nearly optimal utility, but also significantly improves the running time of previous state-of-the-art private optimization algorithms, for both $ε$-DP and $(ε, δ)$-DP. For non-convex but smooth objectives, we propose an RRPSGD (Random Round Private Stochastic Gradient Descent) algorithm, which provably converges to a stationary point with privacy guarantee. Besides the expected utility bounds, we also provide guarantees in high probability form. Experiments demonstrate that our algorithm consistently outperforms existing method in both utility and running time.
1 Introduction
The paper studies efficient differentially private ERM through optimization algorithms, addressing excessive iteration costs for convex objectives and missing theoretical guarantees for non-convex objectives. It uses smoothness to design faster private methods with utility guarantees.
- Motivation: Private ERM must balance privacy with the computational cost and convergence effects of approximate optimization.Finite optimization iterations can enhance stability, while privacy noise creates new convergence challenges.
- Open problems: Existing private convex ERM methods can require at least Ω(n^2) iterations to reach ideal accuracy, limiting scalability.The paper frames reducing this iteration cost while retaining privacy and accuracy as a central question.
- Open problems: Existing theoretical results addressed convex ERM, leaving private non-convex ERM without a theoretical guarantee despite its importance in deep neural networks.The paper specifically targets efficient private optimization with guarantees for non-convex objectives.
- Approach: Smoothness permits more aggressive gradient steps and supports theoretical guarantees around stationary points in the non-convex case.The authors use smoothness as a common optimization assumption to improve convergence behavior.
- Contributions: For strongly convex objectives, gradient descent with output perturbation improves utility by a logarithmic factor while running much faster than private SGD.The utility improvement matches the lower bound cited by the authors.
- Contributions: The paper proposes a private non-convex optimization algorithm with utility guarantees in both expectation and high-probability forms.The method is motivated by stability analysis and uses a variant of randomized stochastic gradient optimization.
- Empirical results: Numerical experiments report that the proposed algorithms consistently outperform existing approaches.The introduction also reports improved running time and utility guarantees relative to prior methods for the studied settings.
2 Preliminaries
The preliminaries define the private ERM setting, smoothness and convexity assumptions, neighboring datasets, differential privacy, sensitivity, and noise mechanisms used in the analysis.
- ERM setting: The paper studies differentially private solutions to an empirical risk minimization problem over a training set S of n data points.The ERM formulation uses a loss function and an optimizer denoted by ˆw.
- Objective assumptions: When each example-wise loss is convex, the ERM formulation reduces to the convex case.The paper separately considers strongly convex, general convex, and non-convex objectives.
- Objective assumptions: β-smoothness is treated as a common assumption in the optimization setting.The paper relies on smoothness in its algorithmic analysis and convergence discussion.
- Differential privacy: Neighboring databases have equal size and differ in exactly one data point.This neighboring relation underlies the differential privacy definition used in the paper.
- Differential privacy: An algorithm is (ε, δ)-differentially private when its outputs satisfy the definition for every pair of neighboring databases; ε-DP is the δ=0 case.The preliminaries introduce differential privacy as a randomized algorithm property over neighboring databases.
- Privacy mechanisms: The Laplace mechanism releases a query plus independent noise calibrated to its L1-sensitivity and privacy parameter ε.The supplied mechanism description gives noise variables drawn from Lap(∆1(q)/ε).
3 Main Results
The paper develops efficient private optimization methods for smooth ERM: output-perturbed gradient descent for convex objectives and random-round private SGD for non-convex objectives. These methods provide privacy and utility guarantees while reducing iteration costs or establishing stationary-point convergence.
- Convex case: Output-perturbed gradient descent uses smoothness and stability analysis to obtain private optimization guarantees without requiring an exact minimizer.The algorithm is analyzed through gradient-descent sensitivity and convergence recursions.
- Strongly convex case: For strongly convex smooth objectives, the method significantly reduces running time while achieving nearly optimal utility guarantees.The paper attributes the acceleration to aggressive gradient steps enabled by smoothness and reports matching lower bounds up to logarithmic factors.
- General convex case: For general convex smooth objectives, the utility guarantee can be weaker by an O(1/n) factor, but the algorithm remains faster and preserves typical learning accuracy when d is smaller than n.Experiments also report lower empirical error and faster running time than the compared method under convex and strongly convex settings.
- Non-convex case: The non-convex method, RRPSGD, combines randomized stopping with private stochastic gradients and provides differential privacy together with utility guarantees.Its analysis uses a stopping-round distribution over at most n^2 iterations and establishes both expected and high-probability forms of utility guarantees.
- Non-convex case: For smooth non-convex objectives, the method converges in expectation to a stationary point with diminishing error, providing a theoretical privacy guarantee.The paper presents this as its first theoretical result for differentially private non-convex optimization, to the authors’ knowledge.
- Scope and limitation: The non-convex results assume smoothness and Lipschitz continuity, while the paper notes that private algorithms generally have polynomial dependence on dimension d.This dependence can hurt generalization error in high-dimensional settings.
4 Experimental Results
The experiments compare the proposed algorithm with private SGD on UCI classification and regression datasets. Across almost all settings, the proposed method achieves better utility and runtime.
- The evaluation uses regularized logistic regression on 3 UCI binary-classification datasets and regularized Huber regression on 2 UCI regression datasets.
- Experiments measure minimization error and running time across ε = {0.1, 0.5, 1, 2} and δ = 0.001.Results are averaged over 100 independent rounds.
- The baseline’s original SGD implementation was replaced by mini-batch SGD with batch size m = 50 because its n^2 iteration cost was prohibitive on real data.
- The proposed algorithm outperforms the existing method on both utility and runtime under almost all settings.
5 Conclusion
The paper studies private ERM for smooth objectives across strongly convex, convex, and non-convex settings. It reports faster optimization with comparable utility and a first theoretical bound for private non-convex optimization.
- For strongly convex and smooth objectives, output-perturbation gradient descent achieves optimal utility and runs much faster than private SGD.
- For general convex objectives, the method remains practical because of fast convergence and reasonable utility.
- Experiments show lower optimization error and runtime than private SGD in almost all cases.
- For non-convex objectives, random-round private SGD reaches a stationary point in expectation with carefully chosen parameters.
- The paper presents this as the first theoretical bound for differentially private non-convex optimization to the authors’ knowledge.
A.1 Proof of Theorem 1
The proof analyzes how gradient-descent iterates on neighboring datasets diverge. It bounds this divergence recursively using Lipschitzness and smoothness-related assumptions.
- The proof compares neighboring databases differing in one sample and defines Δ_t = ∥w_t − w′_t∥, with Δ_0 = 0.
- The remaining bound follows by induction from the assumed bound at iteration t.
- The proof of the related lemma uses the same neighboring-dataset comparison and divergence notation.
- Because both iterates remain in a bounded ball, the proof applies the L-Lipschitz property to control their difference.
A.2 Proof of Theorem 2
Theorem 2 combines a gradient-descent convergence lemma with two noise lemmas. Output perturbation then yields the final utility analysis under β-smoothness.
- Lemma 5 assumes a μ-strongly convex and β-smooth loss and analyzes gradient descent with a constant step size η ≤ 2.
- Lemmas 6 and 7 characterize the random perturbation used in the utility analysis.
- The proof combines Lemmas 5, 6, and 7 and recalls the perturbed output w_priv = w_T + z.
- β-smoothness of the objective is then used to complete the utility bound.
A.3 Proof of Theorem 3
The proof combines earlier lemmas with smoothness and output perturbation to establish Theorem 3, using a selected iteration count for the privacy utility bound.
- Gradient descent is analyzed for convex, β-smooth loss functions with a constant step size.
- The proof combines Lemmas 6, 7, and 8 after expressing the private output as w_priv = w_T + z.
- The resulting bound includes a term proportional to 9T^2L^2d(d+1).
- For (ε, δ)-DP, the theorem is completed by setting T according to the stated asymptotic choice.
A.4 Proof of Theorem 4
The proof establishes Theorem 4 through privacy-loss analysis for noisy stochastic gradients, followed by amplification and strong composition arguments.
- The proof models each noisy stochastic gradient as a random variable conditioned on the current iterate and compares neighboring datasets through privacy loss.
- Privacy is analyzed across rounds using the privacy-loss random variable for neighboring datasets.
- The proof applies the amplification lemma after establishing the per-round privacy bound.
- Random subsampling amplifies privacy: an (ε, δ)-DP algorithm run on uniformly random αn entries gives (2αε, αδ)-DP.
- Strong composition combines T adaptive private steps into overall parameters (ε′, Tδ + δ′), with ε′ determined by the composition bound.
A.5 Proof of Theorem 5
The proof of Theorem 5 treats the noisy gradient as a stochastic first-order oracle, then applies stochastic-gradient convergence results and concentration arguments for high-probability guarantees.
- The noisy gradient G(w_t) is unbiased, with expected squared error bounded by a quantity involving L, n, and δ.
- The proof applies Lemmas 11 and 12 with T = n^2 to obtain the theorem.
- The stochastic-gradient analysis assumes E[G(w_t)] = ∇F(w_t, S) and bounds its variance by σ^2.
- For convex objectives, the convergence statement includes an additional convex-case guarantee relative to the global minimum F*.
- The analysis decomposes stochastic-gradient error using δ_t = ∇f(w_t, ξ) − ∇F(w_t, S), whose norm is bounded by 2L.
- The proof controls martingale terms and Gaussian-noise terms with concentration inequalities, including a chi-square tail bound.