Differentially Private Empirical Risk Minimization Revisited: Faster and More General

By Di Wang, Minwei Ye, Jinhui Xu. Neural Information Processing Systems, 2018

297 citations recorded by the source corpus.

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}.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0f859fac5908995037d7ee22b287114dfac9b780

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

MemGuard: Defending against Black-Box Membership Inference Attacks via Adversarial Examples (2019, background): “Another line of defenses [1, 6, 12, 24, 30, 60, 66, 70] leverage differential privacy [13] when training the target classifier.”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, background): “Problem setting [19, 24, 23] Given a convex, closed and bounded constraint set C ⊆ R, a data universe D, and a loss function ` : C × D 7→ R.”
P3SGD: Patient Privacy Preserving SGD for Regularizing Deep CNNs in Pathological Image Classification (2019, background): “However, such kind of simple solutions cause considerable performance decreasing [4, 43], the situation may become worse in the context of deep learning.”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, background): “These algorithms directly satisfy ( , δ)-differential privacy, and many algorithms were built based on them, such as [24], [25].”
Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget (2018, methodology): “risk is optimal, ignoring multiplicative log factor for both lipschitz convex and strongly convex functions. Later, Talwar et al. [20] improved those lower bounds on the utility for LASSO problem. In [21], gradient perturbation method has been combined with the stochastic variance reduced gradient (”
Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, methodology): “Firstly, diﬀerent from the approach of using Gradient Descent methods to solve DP-ERM ( e.g., (Wang et al., 2017)), our algorithm is parameter-free.”
TAN without a burn: Scaling Laws of DP-SGD (2022, background): “…than large batches when training DNNs. Theoretical Analysis of TAN in the Convex Setting Convergence theory has been thoroughly studied for DP-SGD in convex, strongly convex, and nonconvex (stationary point convergence) settings (Bassily et al., 2014; Wang et al., 2017; Feldman et al., 2018).”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “…has also been a considerable progress in generalizing privacy-preserving machine learning to more complex scenarios such as learning in high dimensional settings [34,35,65], learning without strong convexity assumptions [66], or relaxing the assumptions on data and objective functions [63, 70, 79].”
Differentially Private Federated Learning: An Information-Theoretic Perspective (2021, methodology): “We adopt differential privacy (DP) as our privacy metric of choice, since DP has become the standard for large-scale model ﬁtting (e.g., [4–14]).”
Distributed Learning without Distress: Privacy-Preserving Empirical Risk Minimization (2018, methodology): “[51] used the moments accountant to propose iterative learning with gradient perturbation for the centralized setting.”
Private stochastic convex optimization: optimal rates in linear time (2020, background): “In this case, the optimal statistical rate is O ( L 2 λn ) [HK14], and the private ERM can be optimized with an error of (cid:101) O ( dL 2 ε 2 λn 2 ).”
DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy (2018, methodology): “[29] focus on a more general problem: non-convex problem, and propose a faster algorithm based on a proximal stochastic gradient method.”