Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

Raef Bassily; Adam Smith; Abhradeep Thakurta

Source-linked AI summary

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

Raef Bassily, Adam Smith, Abhradeep Thakurta

arXiv:1405.7085v2May 27, 2014cs.LGcs.CRstat.ML

TL;DR

The paper studies how to perform convex empirical risk minimization privately when losses are only Lipschitz and the optimization domain is bounded. It develops efficient algorithms and matching lower bounds, using different techniques for pure and approximate differential privacy. The results improve nonsmooth-loss excess-risk bounds by √n asymptotically, while identifying limits of smoothing-based methods and remaining generalization gaps.

Problem
Prior optimal private ERM algorithms were not known under only Lipschitz loss contributions and bounded domains, especially for nonsmooth problems such as support vector machines and high-dimensional medians.
Method
The paper designs separate polynomial-time algorithms and lower bounds for (ε,0)- and (ε,δ)-differential privacy, covering general and strongly convex losses.
Results
Algorithms improve excess-risk bounds for nonsmooth loss optimization by a factor of √n asymptotically, with matching lower bounds in the principal settings.
Takeaways & Limitations
Optimal private ERM can be achieved for important nonsmooth losses without assuming smooth data-point contributions, while simple Huberization may be highly inaccurate.
Takeaways & Limitations
For general Lipschitz convex functions, generalization bounds have a polynomial-in-p gap for smaller p, and closing it remains open.

Abstract

from arXiv · show

In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the loss function is Lipschitz bounded and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for $(ε,0)$- and $(ε,δ)$-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.

1 Introduction

The paper develops efficient differentially private algorithms and matching lower bounds for convex ERM with Lipschitz losses, including strongly convex settings. It separates the optimal techniques for (ε,0)- and (ε,δ)-privacy and addresses nonsmooth problems such as medians and SVMs.

Contributions: The paper provides new polynomial-time algorithms and matching lower bounds for private convex ERM under Lipschitz losses and bounded optimization domains.The framework also treats strongly convex losses and supports separate analyses for the two privacy regimes.
Motivation: Convex ERM can leak sensitive records, as Euclidean medians may equal data points and SVM dual coefficients may expose exact data points.These risks motivate privacy-preserving optimization for common statistical and machine-learning models.
Contributions: The algorithms improve excess-risk bounds for nonsmooth loss optimization by a factor of √n asymptotically in both general and strongly convex cases.The paper uses gradient descent, exponential sampling, and localization, with different principles for (ε,0)- and (ε,δ)-privacy.
Contributions: For (ε,δ)-privacy, noisy gradient descent achieves excess risk ˜O(√p/ε), matching the lower bound Ω(min(n, √p/ε)) up to logarithmic factors.For strongly convex functions, a variant achieves risk ˜O(p/(∆nε^2)), matching the corresponding lower bound when ∆ is bounded below.
Contributions: For (ε,0)-privacy, efficient exponential sampling achieves optimal excess risk O(p/ε) without logarithmic factors.The method samples from a continuous log-concave distribution and uses a convex-specific peeling argument.
Limitations: The paper shows that Huberizing nonsmooth losses can yield error Ω(n), while generalization bounds remain non-tight for smaller p.The latter gap is polynomial in p for general Lipschitz convex functions and is identified as an open problem.

2 Gradient Descent and Optimal (ϵ, δ)-differentially private Optimization

This section develops noisy stochastic gradient descent for (ϵ,δ)-differentially private convex ERM, covering both Lipschitz and strongly convex losses. The algorithm is private, supports nondifferentiable losses via sub-gradients, and has essentially tight excess-risk bounds.

Algorithm: ANoise−GD uses noisy stochastic gradient updates, sampling one data point with replacement at each step.The algorithm assumes gradient computation time O(p) and runs for n^2 iterations.
Utility: The method does not require differentiability: sub-gradients can replace gradients without changing the guarantees.Using complete rather than stochastic gradients preserves utility but increases running time by a factor of n.
Privacy: The algorithm is (ϵ,δ)-differentially private.Privacy follows from sampling amplification, Gaussian-noise arguments, and strong composition.
Utility: The utility analysis covers both Lipschitz convex and Lipschitz strongly convex losses, with bounds parameterized by L and, when applicable, ∆.The stated guarantees are expectations over the algorithm’s randomness.
Guarantees and cost: The excess-risk bounds are essentially tight, while the algorithm has running time O(pn^2).The paper contrasts this with prior variants that cannot guarantee excess risk o(√n) under their disjoint-batch design.

3 Exponential Sampling and Optimal (ϵ, 0)-private Optimization

This section constructs optimal pure-ϵ private algorithms for Lipschitz convex ERM using exponential sampling. A peeling analysis removes logarithmic factors, and an efficient sampler provides polynomial-time implementation under geometric oracle assumptions.

Exponential mechanism: A variant of the exponential mechanism achieves optimal excess risk for arbitrary convex bounded sets and Lipschitz losses.The mechanism samples points with probability proportional to exp(−ϵL(θ;D)).
Privacy: The algorithm is ϵ-differentially private.Its privacy analysis uses the sensitivity bound for the loss difference relative to a fixed reference point.
Utility analysis: A convexity-based peeling argument removes the extra logarithmic factor from standard exponential-mechanism analysis.The proof partitions a differential cone into marked regions and uses convexity to control their radii and volumes.
Efficient implementation: An efficient version runs in polynomial time and outputs a sample whose distribution is arbitrarily close multiplicatively to the ideal exponential-sampling distribution.The construction uses sampling over a cube containing C and grid-walk methods; isotropic-position assumptions simplify the stated running-time guarantee.
Efficient implementation: The pure-ϵ setting requires a multiplicative sampling guarantee, unlike (ϵ,δ) privacy, where total-variation sampling would suffice.This distinction motivates the specialized efficient sampler developed here.

4 Localization and Optimal Private Algorithms for Strongly Convex Loss

This section uses localization to obtain optimal pure-ϵ private algorithms for Lipschitz strongly convex ERM. Output perturbation first shrinks the feasible region, after which a generic private convex optimizer is applied.

Motivation: Directly applying the exponential mechanism over C is too loose because C is too large for tight strongly convex guarantees.The localization step addresses this geometric obstacle before the second private optimization stage.
Localization method: Localization combines output perturbation with a generic ϵ-private algorithm for Lipschitz convex losses.The first stage produces a smaller convex set, and the second stage optimizes over that set.
Localization method: The localized convex set has diameter ˜O(p/n), enabling the second-stage optimizer to exploit strong convexity.The paper instantiates the generic procedure with exponential sampling to obtain an optimal algorithm.
Scope: The localization technique extends naturally to (ϵ,δ) privacy, although the paper does not use it there because gradient descent already achieves the optimal bound.Details for that case are deferred to Appendix B.
Guarantees: Algorithm 4 is ϵ-differentially private by composition of its two private stages.The utility analysis expresses its excess risk in terms of the second-stage algorithm’s expected excess risk.

5 Lower Bounds on Excess Risk

This section establishes lower bounds on excess risk for private convex ERM, covering both Lipschitz convex and strongly convex losses under pure and approximate differential privacy.

Scope: The lower-bound analysis treats convex Lipschitz losses and strongly convex Lipschitz losses separately.The constructions use decomposable losses over a bounded convex set.
Proof strategy: 1-way marginal estimation lower bounds provide the key privacy-based ingredient for the ERM lower bounds.The lemma supplies separate statements for ε-DP and (ε,δ)-DP algorithms.
Lipschitz convex functions: For convex Lipschitz losses, every ε-DP algorithm incurs excess risk Ω(min(n, p/ε)) with probability at least 1/2 on some dataset.The hard instance uses a linear loss over the Euclidean unit ball, whose minimizer is determined by the empirical vector.
Lipschitz convex functions: The convex-loss lower bound follows by converting a private optimization output into an estimator of the dataset's empirical vector.A constant optimization error implies constant Euclidean error, which yields the stated excess-risk lower bound.
Lipschitz convex functions: The convex-loss lower bounds extend to arbitrary L and ∥C∥2 by an additional multiplicative factor L∥C∥2, making them tight against the upper bounds.The scaling changes both the parameter set and the linear loss.
Strongly convex functions: For strongly convex losses, the analogous lower bounds use squared Euclidean distance and scale with L^2/∆ when ∆∥C∥2/L = Ω(1).Under this condition, the paper states that the upper and lower bounds are tight.
Strongly convex functions: When ∆∥C∥2/L is not Ω(1), the strongly convex lower bounds are tight only up to a factor of ∆∥C∥2/L.This is the stated scope boundary for the tightness claim.

6 Efficient Sampling from Logconcave Distributions over Convex Sets and The Proof of Theorem 3.4

This section constructs efficient samplers for logconcave distributions on bounded convex sets and uses them to implement the efficient pure-DP exponential-sampling algorithm.

Efficient logconcave sampling: The generic sampler targets a logconcave distribution over an arbitrary bounded convex set with a multiplicative-distance guarantee.Its output distribution is within a constant-factor distance close to 1 from the target distribution.
Efficient logconcave sampling: The hypercube sampler discretizes the domain into a grid, runs a lazy reversible grid-walk, and samples uniformly within the resulting grid cell.The grid spacing is chosen from the Lipschitz constant and target multiplicative error.
Efficient logconcave sampling: Sampling over a general convex set proceeds by enclosing it in a hypercube, extending the potential function, and penalizing points outside the set.A Minkowski-norm-based gauge is zero inside C and increases outside C.
Efficient logconcave sampling: With probability at least 1/2, Ainit−samp outputs a point in C whose conditional distribution is within multiplicative distance ˜ε of the desired distribution.The construction controls the mass assigned outside C through the gauge function.
Efficient logconcave sampling: Aeff−samp achieves Dist∞(ˆµC, µC) ≤ ˜ε, and its running time is bounded by the cost of repeated calls to Ainit−samp.The paper gives the running-time relation O(m · TAinit−samp).
Proof of Theorem 3.4: Aeff−exp−samp instantiates the efficient sampler with a scaled empirical loss and parameters determined by ε, L, ∥C∥2, and n.Its output distribution is close to that of the ideal exponential-sampling algorithm, preserving the utility analysis.
Proof of Theorem 3.4: The instantiated algorithm is ε-differentially private and has the stated running time under the standard assumption n = ω(p).The privacy conclusion follows from the distribution-approximation lemma and the ideal algorithm's privacy.

A Straightforward Smoothing Does Not Yield Optimal Algorithms

The paper argues that smoothing non-smooth losses, such as hinge loss, incurs an inherent cost that prevents optimal excess-risk bounds. For every smoothing parameter h, objective perturbation can have provably worse excess risk on some datasets.

Smoothing hinge loss by Huberization makes it twice-continuously differentiable but introduces an inherent excess-risk cost.The smoothed loss equals the original outside [-h,h] and is quadratic within that interval.
The limitation applies to both (ε, δ)-differential privacy and pure ε-differential privacy.The text states that the presented conclusions for (ε, δ)-privacy also hold for pure ε-privacy.
For every h > 0, there exists a dataset where objective perturbation has a lower-bounded excess risk.Theorem A.1 establishes this worst-case statement for every Huberization parameter.
On D1, the excess risk is Ω(n · min{1, h}) with probability at least 2/3.This lower bound is obtained for the objective perturbation algorithm on the first constructed dataset.
The proof analyzes datasets D1 and D2 separately and combines their lower bounds to complete Theorem A.1.D1 and D2 use different configurations to expose the cost of smoothing for a given h.

B Localization and (ϵ, δ)-Differentially Private Algorithms for Lipschitz, Strongly Convex Loss

The localization construction uses a generic private algorithm on a localized convex subset and combines it with privacy composition. Its generic utility guarantee is stated for the algorithm’s output relative to the minimizer over that subset.

For (ε, δ)-privacy, the noise vector b is sampled from a Gaussian distribution.The proof contrasts this Gaussian-noise construction with the corresponding pure-privacy analysis.
Localization outputs a restricted set C′ centered at θ0 with radius ζσ0√p.The construction defines C′ using the privacy-dependent scale σ0 and the dimension p.
The generic algorithm A_(ε,δ),gen-Lip optimizes decomposable convex Lipschitz losses over an arbitrary convex subset C̃ ⊆ C.Algorithm 1 is given as an example of such a generic private algorithm.
The privacy guarantee follows from the composition theorem and the assumed privacy of the component algorithms.The proof explicitly invokes composition and the privacy of the underlying calls.
Theorem B.2 states a generic utility guarantee for the output θ̂ of A_(ε,δ),gen-Lip relative to the minimizer over C̃.The supplied theorem passage introduces the guarantee for an arbitrary convex set C̃ ⊆ C.

C.1 Proof of Part 1

The proof of Part 1 establishes a lower bound for every ε-differentially private algorithm by constructing many separated datasets and reducing the large-n case to a smaller hard instance.

M = Ω(min(n, p/ε)) quantifies the hard-instance scale for ε-differentially private algorithms.The lemma asserts that this scale applies for every n and p.
A packing of K = 2^(p/2) points in {−1/√p, 1/√p}^p supplies the separated dataset constructions.The points are chosen so every distinct pair has the required separation.
When n ≤ n* = p/(20ε), each dataset consists of n copies of one packed point.This construction yields datasets whose sums encode the packed points.
For sufficiently large p, some dataset forces L2-error at least 1/16 with probability at least 1/2.The contradiction argument uses differential privacy across the constructed datasets.
For n > n*, balanced padding with copies of c and −c extends the construction while preserving the hard signal scale.The resulting datasets differ in n* entries and have sum norms between n*−1 and n*+1.

C.2 Proof of Part 2

The proof of Part 2 extends the hard-instance argument to (ε, δ)-differential privacy when δ = o(1/n), using a smaller hard sample and balanced padding.

For δ = o(1/n), every (ε, δ)-differentially private algorithm faces a dataset with a nontrivial L2-error lower bound.Lemma 5.1 Part 2 states this existence result with probability at least 1/3.
The proof first uses a hard dataset of size n* = Ω(p/ε) when n ≤ n*.This base case is obtained through a cited result and translated into an L2-error statement.
For n > n*, the construction pads the first n* hard entries with balanced copies of c and −c.The padding keeps the additional entries from changing the relevant sum substantially.
The reduction yields an (ε, δ)-private algorithm on the smaller instance if every padded dataset were too accurate.That implication contradicts the lower bound for the first half of the proof.
The constructed padded dataset has sum norm in [M−1, M+1], with M = Ω(n*) = Ω(p/ε).This preserves the hard signal magnitude after padding.

D Converting Excess Risk Bounds in Expectation to High-probability Bounds

The paper converts expected excess-risk guarantees into high-probability guarantees by repeating the private algorithm with divided privacy parameters and selecting the best output. The resulting bound is within a polylogarithmic factor of the expectation bound.

Privacy-preserving repetition: Running the private algorithm k times with privacy parameters ϵ/k and δ/k preserves overall (ϵ, δ)-differential privacy.The repeated outputs are later evaluated and one is selected using the exponential mechanism.
High-probability conversion: Markov’s inequality ensures that at least one run has excess risk at most 2F(ϵ/k, δ/k) with probability at least 1 − 1/2k.Here F denotes the underlying expected excess-risk function.
High-probability conversion: The exponential mechanism selects an output whose excess risk is controlled with probability at least 1 − ρ/2.This selection is applied to the list of private outputs.
Final guarantee: Setting k = log(2/ρ) yields excess risk O(F(ϵ log(1/ρ), δ log(1/ρ))) with probability at least 1 − ρ.Thus, the high-probability guarantee is only a polylog(1/ρ) factor away from the expectation guarantee.

E Excess Risk Bounds for Smooth Functions

This section considers losses that are both L-Lipschitz and β-smooth, giving privacy-dependent error guarantees for pure and approximate differential privacy. Under sufficient strong convexity, tight guarantees can be recovered without an additional regularizer.

Smooth losses: The smooth-function setting assumes every loss ℓ(θ; d) is β-smooth and L-Lipschitz over the optimization domain.The results cover both ϵ-differential privacy and (ϵ, δ)-differential privacy.
Perturbation mechanisms: Objective perturbation uses Gamma noise for ϵ-differential privacy and Normal noise for (ϵ, δ)-differential privacy.The noise vector b is sampled from one of these distributions in the objective perturbation algorithm.
Smooth losses: Theorem E.1 states excess-risk bounds for losses that are Lipschitz and smooth.These bounds summarize the guarantees obtained from the objective perturbation approach in this setting.
Strong convexity: When the losses are additionally Δ-strongly convex and Δ ≥ β^2/ϵ, tight pure- and approximate-privacy error guarantees can be recovered.The privacy guarantee no longer requires adding the additional regularizer.

F From Excess Empirical Risk to Generalization Error

The paper extends private empirical-risk guarantees to true risk by combining learning-theoretic generalization bounds with private ERM utility results and regularization. It also gives specialized generalized-linear-model bounds and identifies an unresolved dimension dependence.

Generalization framework: The section relates true excess risk to excess empirical risk for datasets sampled independently from a distribution.This provides the learning-theoretic bridge from empirical optimization guarantees to generalization guarantees.
Strongly convex losses: For Lipschitz, strongly convex losses, Theorem F.1 supplies a high-probability relation between true and empirical excess risk.The paper plugs private utility guarantees into this relation and uses an expectation-to-high-probability conversion when needed.
Regularization: The regularization trick converts general convex Lipschitz losses into strongly convex losses by adding a quadratic regularizer.The regularized loss is used to obtain excess-risk guarantees for the original general convex problem.
Limitation: The private algorithms’ dependence on n matches corresponding non-private bounds, but their excess risk has an explicit dependence on p whose optimal form remains open.This is identified as an open problem for private algorithms.
Generalized linear models: For generalized linear models, the resulting true excess-risk bounds are tight and can attain the non-private upper bound O(L∥C∥2 √n).The setting writes ℓ(θ; d) as g(⟨θ, d⟩; d), with g Lipschitz in its first input and bounded data norm.