Adapting to Function Difficulty and Growth Conditions in Private Optimization

Abstract

We develop algorithms for private stochastic convex optimization that adapt to the hardness of the specific function we wish to optimize. While previous work provide worst-case bounds for arbitrary convex functions, it is often the case that the function at hand belongs to a smaller class that enjoys faster rates. Concretely, we show that for functions exhibiting $\kappa$-growth around the optimum, i.e., $f(x)\ge f(x^{\ast })+\lambda {\kappa }^{-1}\Vert x-x^{\ast }{\Vert }_2^{\kappa }$ for $\kappa >1$, our algorithms improve upon the standard $\sqrt{d}/n\epsilon$ privacy rate to the faster $(\sqrt{d}/n\epsilon {)}^{\frac{\kappa }{\kappa -1}}$. Crucially, they achieve these rates without knowledge of the growth constant $\kappa$ of the function. Our algorithms build upon the inverse sensitivity mechanism, which adapts to instance difficulty (Asi & Duchi, 2020), and recent localization techniques in private optimization (Feldman et al., 2020). We complement our algorithms with matching lower bounds for these function classes and demonstrate that our adaptive algorithm is \emph{simultaneously} (minimax) optimal over all $\kappa \ge 1+c$ whenever $c=\Theta (1)$.

arXiv comment28 pages

References in corpus (11)

• Deep Learning with Differential Privacy
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Primal-dual subgradient methods for minimizing uniformly convex functions
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• An optimal algorithm for stochastic strongly-convex optimization
• Private Adaptive Gradient Methods for Convex Optimization
• Private Stochastic Convex Optimization: Optimal Rates in ${\ell }_1$ Geometry
• Near Instance-Optimality in Differential Privacy
• Learning with User-Level Privacy