Private Stochastic Convex Optimization with Optimal Rates

Abstract

We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d. samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of $1/\sqrt{n}$ as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of $1/n^{1/4}$. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.

References in corpus (3)

• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back

Cited by in corpus (27)

• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Remember What You Want to Forget: Algorithms for Machine Unlearning
• Federated Reconstruction: Partially Local Federated Learning
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Efficient Privacy-Preserving Stochastic Nonconvex Optimization
• Differentially Private Federated Learning with Laplacian Smoothing
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Deep Learning with Label Differential Privacy
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
• Shuffle Private Stochastic Convex Optimization
• Dealer: End-to-End Data Marketplace with Model-based Pricing
• Differentially Private SGD with Non-Smooth Losses
• Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
• Improved Learning Rates for Stochastic Optimization
• Public Data-Assisted Mirror Descent for Private Model Training
• Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General
• Private Optimization Without Constraint Violations
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives
• Learning with User-Level Privacy
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
• The Relative Gaussian Mechanism and its Application to Private Gradient Descent
• Algorithmic Instabilities of Accelerated Gradient Descent