Parameter-Free Locally Differentially Private Stochastic Subgradient Descent

We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing null -locally differentially private ( null -LDP). While it has been shown that stochastic optimization is possible with null -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 null -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. 1 Introduction In this paper, we consider the problem of minimizing the convex risk of a machine learning predictor, guaranteeing local differential privacy. Instead of going through the empirical risk minimization route, we directly optimize the stochastic objective of the risk via stochastic subgradients appropriately sanitized to guarantee the local differential privacy.