Parameter-Free Locally Differentially Private Stochastic Subgradient Descent
This work addresses privacy-preserving optimization for machine learning practitioners by reducing privacy budget consumption in differentially private settings, though it is incremental as it builds on existing SGD methods.
The paper tackles the problem of tuning learning rates in locally differentially private stochastic gradient descent, which increases privacy loss, by proposing BANCO, a parameter-free algorithm that matches the convergence rate of tuned SGD without requiring learning rate adjustments.
We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing $ε$-locally differentially private ($ε$-LDP). While it has been shown that stochastic optimization is possible with $ε$-LDP via the standard SGD (Song et al., 2013), its convergence rate largely depends on the learning rate, which must be tuned via repeated runs. Further, tuning is detrimental to privacy loss since it significantly increases the number of gradient requests. In this work, we propose BANCO (Betting Algorithm for Noisy COins), the first $ε$-LDP SGD algorithm that essentially matches the convergence rate of the tuned SGD without any learning rate parameter, reducing privacy loss and saving privacy budget.