Adapting to Function Difficulty and Growth Conditions in Private Optimization
This work addresses the problem of enhancing privacy-preserving optimization for machine learning practitioners by adapting to specific function classes, representing an incremental advance over prior worst-case methods.
The paper tackles private stochastic convex optimization by developing algorithms that adapt to the function's growth condition, improving the privacy rate from sqrt(d)/(nε) to (sqrt(d)/(nε))^(κ/(κ-1)) for functions with κ-growth, without prior knowledge of κ, and provides matching lower bounds to show optimality.
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 $κ$-growth around the optimum, i.e., $f(x) \ge f(x^*) + λκ^{-1} \|x-x^*\|_2^κ$ for $κ> 1$, our algorithms improve upon the standard ${\sqrt{d}}/{n\varepsilon}$ privacy rate to the faster $({\sqrt{d}}/{n\varepsilon})^{\tfracκ{κ- 1}}$. Crucially, they achieve these rates without knowledge of the growth constant $κ$ 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 $κ\ge 1+c$ whenever $c = Θ(1)$.