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

Abstract

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 $(\epsilon ,0)$- and $(\epsilon ,\delta )$-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.

References in corpus (2)

• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Characterizing the Sample Complexity of Private Learners

Cited by in corpus (36)

• Privacy Amplification by Iteration
• Private Stochastic Convex Optimization with Optimal Rates
• Large Language Models Can Be Strong Differentially Private Learners
• AdaCliP: Adaptive Clipping for Private SGD
• Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms
• Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning
• Jointly Private Convex Programming
• Federated Reconstruction: Partially Local Federated Learning
• Local Differential Privacy for Evolving Data
• The Large Margin Mechanism for Differentially Private Maximization
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Large Scale Private Learning via Low-rank Reparametrization
• Data-dependent PAC-Bayes priors via differential privacy
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• Differentially Private Deep Learning with Smooth Sensitivity
• Gradient Perturbation is Underrated for Differentially Private Convex Optimization
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
• Differentially Private Bayesian Inference for Generalized Linear Models
• Differentially Private Variational Dropout
• Parameter-Free Locally Differentially Private Stochastic Subgradient Descent
• Towards Understanding the Impact of Model Size on Differential Private Classification
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General
• Private Optimization Without Constraint Violations
• Privacy Preserving Off-Policy Evaluation
• On Connecting Stochastic Gradient MCMC and Differential Privacy
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
• Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors
• Quantifying Membership Privacy via Information Leakage
• Do I Get the Privacy I Need? Benchmarking Utility in Differential Privacy Libraries
• Differentially Private Distributed Online Learning
• Private Deep Learning with Teacher Ensembles
• Utility Preserving Secure Private Data Release
• A Knowledge Transfer Framework for Differentially Private Sparse Learning
• Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
• Pufferfish Privacy Mechanisms for Correlated Data