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)$.

28 pages

References in corpus (7)

• A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• 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