Efficient Private ERM for Smooth Objectives
This work addresses the problem of balancing privacy and efficiency in machine learning optimization for researchers and practitioners, offering incremental improvements over existing methods.
The paper tackles efficient differentially private empirical risk minimization for smooth objectives, showing that gradient descent with output perturbation achieves nearly optimal utility and significantly improves running time for convex cases, while a proposed RRPSGD algorithm converges to stationary points for non-convex cases, with experiments demonstrating consistent outperformance in utility and speed.
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 $ε$-DP and $(ε, δ)$-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.