Efficient Private ERM for Smooth Objectives

Abstract

In this paper, we consider efficient differentially private empirical risk minimization from the viewpoint of optimization algorithms. For strongly convex and smooth objectives, we prove that gradient descent with output perturbation not only achieves nearly optimal utility, but also significantly improves the running time of previous state-of-the-art private optimization algorithms, for both $\epsilon$-DP and $(\epsilon ,\delta )$-DP. For non-convex but smooth objectives, we propose an RRPSGD (Random Round Private Stochastic Gradient Descent) algorithm, which provably converges to a stationary point with privacy guarantee. Besides the expected utility bounds, we also provide guarantees in high probability form. Experiments demonstrate that our algorithm consistently outperforms existing method in both utility and running time.

References in corpus (2)

• Train faster, generalize better: Stability of stochastic gradient descent
• Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry

Cited by in corpus (10)

• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• Differentially Private Accelerated Optimization Algorithms
• Input Perturbation: A New Paradigm between Central and Local Differential Privacy
• Weighted Distributed Differential Privacy ERM: Convex and Non-convex
• Private and Communication-Efficient Edge Learning: A Sparse Differential Gaussian-Masking Distributed SGD Approach
• Stochastic Adaptive Line Search for Differentially Private Optimization
• Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms
• DPlis: Boosting Utility of Differentially Private Deep Learning via Randomized Smoothing
• Differentially Private Consensus-Based Distributed Optimization
• Secure Metric Learning via Differential Pairwise Privacy