Source-linked AI summary
Differentially Private Empirical Risk Minimization Revisited: Faster and More General
Di Wang, Minwei Ye, Jinhui Xu
TL;DR
Differentially private ERM must balance learning utility with privacy across convex, high-dimensional, and non-convex settings. The paper develops faster algorithms and extends utility analysis, reporting optimal or near-optimal bounds with reduced gradient complexity and a tighter Polyak-Lojasiewicz-case bound.
Problem
Differentially private ERM needs improved utility and computational efficiency across convex, high-dimensional, and non-convex settings.
Method
The paper develops gradient-based differentially private ERM algorithms for smooth convex settings, high-dimensional problems, and Polyak-Lojasiewicz losses.
Results
The algorithms achieve optimal or near-optimal utility bounds with less gradient complexity, including O(n2) to O(n log n) and O(n3) to O(n1.5) reductions.
Takeaways & Limitations
Gradient perturbation combined with faster first-order methods can improve privacy-preserving ERM utility or runtime across several supported settings.
Takeaways & Limitations
The paper leaves open whether optimal bounds are achievable with less time complexity for general non-smooth convex losses and other non-convex settings.
Abstract
from arXiv · showhide
In this paper we study the differentially private Empirical Risk Minimization (ERM) problem in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithms that achieve either optimal or near optimal utility bounds with less gradient complexity compared with previous work. For ERM with smooth convex loss function in high-dimensional ($p\gg n$) setting, we give an algorithm which achieves the upper bound with less gradient complexity than previous ones. At last, we generalize the expected excess empirical risk from convex loss functions to non-convex ones satisfying the Polyak-Lojasiewicz condition and give a tighter upper bound on the utility than the one in \cite{ijcai2017-548}.
1 Introduction
The paper revisits differentially private ERM, targeting privacy and utility together while improving utility bounds and gradient complexity across convex settings.
- Motivation: Differentially private ERM must learn effectively from sensitive data while providing formal privacy guarantees.Differential privacy is presented as a rigorous definition whose guarantees hold regardless of an adversary’s prior knowledge.
- Problem setting: Expected excess empirical risk measures utility as E[F_r(x_private, D)] − F_r(x*, D).The expectation is over the algorithm’s random coins.
- Prior approaches: Existing approaches perturb outputs, objectives, or gradients, with gradient perturbation preferred because it avoids several practical issues.The paper notes that prior gradient-perturbation results rely on GD or SGD, which are generally slow for large datasets.
- Contributions: The paper presents algorithms with tighter utility upper bounds and less running time for convex losses, including settings with non-smooth regularizers.Output perturbation cannot generalize to non-smooth regularization, while objective perturbation may require an intractable exact optimum.
- Contributions: The paper also extends expected excess empirical risk analysis from convex losses to non-convex losses satisfying the Polyak-Lojasiewicz condition.This extension gives a tighter utility upper bound than the cited prior work.
2 Related Work
Related work spans multiple formulations and privacy mechanisms; the paper emphasizes improved utility and gradient complexity, especially for non-strongly convex and high-dimensional ERM.
- Related formulations: Prior differentially private ERM studies address online regret, incremental regression, learnability, and stability.The paper compares most closely related work using utility and gradient complexity.
- Strongly convex case: For strongly convex, 1-smooth losses, the paper reports near-optimal utility with less gradient complexity than previous algorithms.The method is also described as robust to non-smooth regularizers.
- Broader settings: For non-strongly convex and high-dimensional cases, the paper reports that its algorithms outperform peer methods.The comparisons are given in Tables 2 and 3.
- Broader settings: O(n2) to O(n log n) reduces gradient complexity while preserving the optimal bound for the non-strongly convex case.The paper separately reports a high-dimensional reduction from O(n3) to O(n1.5).
- Non-convex case: For non-convex smooth ERM, prior work used expected gradient norm and achieved a qualified utility in O(n2) gradient complexity via DP-SGD.This paper instead uses DP-GD and claims a tighter utility upper bound.
3 Preliminaries
The preliminaries define the loss, regularization, smoothness, neighboring datasets, and differential privacy, then specify Gaussian noise and privacy accounting tools.
- Function properties: A loss function is G-Lipschitz over θ when loss differences are bounded by G times the ℓ2 distance between parameters.The definition applies for every data point z and parameter pair in C.
- Function properties: An L-smooth loss has gradients whose dual-norm differences are bounded by L times the parameter distance.The supplied passage states the general norm-based gradient condition.
- Privacy model: Neighboring datasets differ in exactly one entry, and (ϵ, δ)-differential privacy bounds output-event probabilities across every neighboring pair.The privacy definition is introduced for randomized algorithms and all events in the output space.
- Privacy tools: The analysis uses the Gaussian Mechanism and moments accountant to guarantee (ϵ, δ)-differential privacy.The moments accountant provides tighter privacy accumulation bounds for ϵ and δ than advanced composition in the stated setting.
- Privacy tools: For sampled stochastic gradient algorithms, privacy depends on sampling probability, step count, noise scale, and the condition ϵ < c1q2T.The theorem states privacy for Gaussian noise added to gradients under specified constants and δ > 0.
4 Differentially Private ERM with Convex Loss Function
This section develops differentially private variance-reduced methods for convex ERM with regularization, covering both strongly and non-strongly convex objectives. The proposed methods target near-optimal or optimal utility with reduced gradient complexity.
- Strongly convex case: DP-SVRG applies Prox-SVRG with gradient noise to strongly convex ERM with potentially non-smooth regularization.The method is designed to improve on DP-SGD and DP-GD in time to reach near-optimal excess empirical risk.
- Strongly convex case: The strongly convex analysis provides differential privacy and a utility guarantee under convex, G-Lipschitz, L-smooth loss assumptions and suitable step-size and inner-loop conditions.The privacy constraint can alternatively be removed by increasing the noise, at the cost of additional logarithmic factors in utility.
- Complexity: The stated utility results are accompanied by gradient-complexity bounds, and the paper notes that further acceleration methods can reduce this complexity.The complexity expressions are given in the theorem results and subsequent remarks.
- Non-strongly convex case: DP-SVRG++ extends the variance-reduced approach to objectives that are not strongly convex and achieves the optimal utility bound.Its construction follows the role of SVRG++ in reducing gradient complexity relative to accelerated gradient methods.
- Non-strongly convex case: DP-SVRG++ uses a growing inner-loop schedule, with m_s = 2^s m, to support the non-strongly convex analysis.The algorithm adds noisy variance-reduced gradient updates across outer iterations.
5 Differentially Private ERM for Convex Loss Function in High Dimensions
This section addresses smooth convex ERM when the dimension greatly exceeds the sample size by reformulating optimization over a centrally symmetric convex set. DP-AccMD uses accelerated mirror descent to obtain privacy and utility guarantees with geometry-sensitive complexity.
- High-dimensional formulation: When p ≫ n, dimension-dependent utility and gradient-complexity bounds are undesirable, motivating optimization over a closed centrally symmetric convex set C.An l1-norm ball is given as an example of such a set.
- Geometry-sensitive complexity: The Gaussian width of C can replace a √p term, is no larger than O(√p), and may be significantly smaller in practice.The section presents DP-AccMD as a faster algorithm for achieving the upper utility bound.
- DP-AccMD: DP-AccMD is based on accelerated mirror descent and operates with a function w that is 1-strongly convex relative to the Minkowski norm induced by C.Its updates combine noisy gradients with Bregman-divergence-based mirror steps.
- Privacy and utility: Theorem 5.4 provides a utility guarantee and total gradient-complexity bound for convex, G-Lipschitz, L-smooth losses over C.The guarantee uses the noise choice from equation (9) and the strong-convexity condition on w.
6 ERM for General Functions
The paper extends differentially private ERM analysis to general functions, including non-convex objectives satisfying the Polyak-Lojasiewicz condition. DP-GD provides privacy and near-optimal utility guarantees under these settings.
- General-function framework: DP-GD is analyzed for non-convex objectives under the paper's general-function framework.The algorithm uses noisy gradient updates and returns either the final iterate or a uniformly sampled iterate, depending on the section.
- Privacy guarantee: DP-GD is (ϵ, δ)-differentially private under the conditions specified in Theorem 6.1.The theorem assumes a G-Lipschitz, L-smooth loss and specifies the required noise calibration.
- Polyak-Lojasiewicz objectives: The Polyak-Lojasiewicz condition is used to study excess empirical risk beyond convex loss functions.The condition implies that every critical point is a global minimum and includes strongly convex functions as a special case.
- Utility guarantee: DP-GD achieves a near-optimal utility bound for objectives satisfying the Polyak-Lojasiewicz condition.The bound hides additional logarithmic, L, and µ terms.
- Comparison with prior work: The paper notes that prior non-convex smooth ERM work used O(n^2) gradient complexity, while its DP-GD analysis gives a tighter utility upper bound.The comparison uses expected gradient norm as the utility measure.
- Open questions: An open issue is whether the optimal bound can be achieved with less gradient complexity for broader function classes and general non-smooth convex losses.The discussion also identifies interpretable utility measures for non-convex losses as future work.
7 Discussions
The discussion identifies broader conditions, non-smooth convex losses, and more interpretable non-convex utility measures as unresolved directions.
- Discussion: Gradient perturbation combined with linearly convergent first-order methods achieves near-optimal bounds with less gradient complexity.Whether this combination can attain the optimal bound remains unresolved.
- Discussion: The optimal bound remains unknown for other function conditions, including general gradient-dominated, quasi-convex, and locally-Lipschitz settings.The paper specifically proposes these classes as directions for future analysis under differential privacy.
- Discussion: For general non-smooth convex losses such as SVM, it is unknown whether the optimal bound is achievable with less time complexity.
- Discussion: A further direction is to develop an easier-to-interpret utility measure for non-convex loss functions.
A Experiments
Experiments on logistic regression with the Covertype dataset compare DP-SVRG and DP-SVRG++ against DP-GD across privacy levels and regularization settings. The reported figures show the proposed methods outperforming previous results in both comparisons.
- Experimental setup: The experiments use 200000 training samples from the 581012-sample, 54-feature Covertype dataset.The task is logistic regression with L2-norm regularization for the DP-SVRG comparison.
- DP-SVRG++ comparison: The experiments also compare DP-SVRG++ with DP-GD for logistic regression across different ϵ values.
- Experimental setup: The evaluation measures expected optimality gap and running time for ϵ = {0.2, 0.5, 1} and δ = 0.001.
- DP-SVRG comparison: Figure 1 compares DP-SVRG with DP-GD for logistic regression under different ϵ values and L2 regularization.DP-SVRG uses T = 15 and m = 5000 with SVRG-BB step-size updates, whereas DP-GD uses T = 1500.
- Results: The proposed method outperforms previous results in both experimental cases.
B.1 Using Advance Composition Theorem to Guarantee (ϵ, δ)-differential private
This appendix explains how advanced composition and privacy amplification via sampling provide differential privacy for repeated sampled queries. The analysis tracks query composition, sensitivity, and Gaussian noise calibration across iterations.
- Composition-based privacy: For general ϵ, the noise can be amplified by O(ln(T/δ)), while the utility analysis incurs O(log(Tm/δ)) factors.The privacy guarantee uses advanced composition and privacy amplification via sampling.
- Illustrative comparison: Figure 2 compares DP-SVRG++ and DP-GD for logistic regression under different ϵ values.The displayed settings are T = 15, m = 10, η = 0.01 for DP-SVRG++ and T = 1000, η = 0.1 for DP-GD.
- Composition analysis: Advanced composition assigns each of T composed queries a privacy budget proportional to ϵ divided by √(T log(1/δ)).The per-query failure probability is set using δ and T.
- Privacy amplification: Uniform subsampling amplifies privacy from an algorithm run on the full dataset to execution on a random γn-entry subset.Lemma B.1 gives a 2γϵ′-differential privacy guarantee when the base algorithm is ϵ′-differentially private.
- Final guarantee: After T iterations, the composed mechanism remains (ϵ, δ)-differentially private under the selected noise scale and query counts.
- Moment accounting: Each sampled query is decomposed into two Gaussian-perturbed components, whose Rényi moments are bounded separately and then combined.The proof uses the additive relationship between moments and the Gaussian representation of the two distributions.
B.3 Proof of Theorem 5.3 and Theorem 6.1
The proof invokes prior results and concludes an iterative bound after T iterations for some constant c.
- The proof is described as similar to an earlier proof.
- After T iterations, the argument establishes a bound for some constant c.
B.4 Proof of Theorem 4.2
The proof derives iterative expected-risk bounds by combining smoothness, convexity, independence, Bregman-divergence arguments, and Gaussian-width estimates, then selects parameters to obtain a final asymptotic bound.
- The analysis uses independence between the sampled quantities and iterates, together with prior lemmas and a quadratic norm inequality.
- The final big-O expression omits an additional logarithmic term.
- The proof repeatedly bounds expected regularized-risk differences across inner iterations and sums these inequalities over iterations.
- Choosing η = 1/13L yields an averaged bound after summing over the inner iterations and taking expectation.
- Bregman-divergence optimality conditions, strong convexity, and Cauchy–Schwarz control the noisy mirror-type update.
- Gaussian-width concentration provides a bound used in the subsequent summation over iterations.