Parameter-Free Locally Differentially Private Stochastic Subgradient Descent

Kwang-Sung Jun, Francesco OrabonaarXiv 2019 · OpenReview

Abstract

We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing $\epsilon$-locally differentially private ($\epsilon$-LDP). While it has been shown that stochastic optimization is possible with $\epsilon$-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 $\epsilon$-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.

Introduction

In the landscape of privacy-preserving machine learning, Local Differential Privacy (LDP) represents a gold standard for user protection. Unlike centralized differential privacy, which relies on a trusted server, LDP assumes the server is untrusted. Data is sanitized—typically by adding noise—directly on the user's device before it is transmitted.

While Stochastic Subgradient Descent (SGD) is the workhorse for optimizing models under these constraints, it suffers from a significant drawback: extreme sensitivity to the learning rate ($\eta$). In non-private settings, finding the optimal $\eta$ is a matter of computational expense. In the private setting, however, this becomes a security cost. Every additional run required to tune hyperparameters consumes more of the finite "privacy budget," increasing the risk of data leakage. This creates a "Privacy-Tuning Paradox" where achieving high performance through tuning directly undermines the privacy guarantees the system was designed to provide.

The BANCO Algorithm

To resolve this paradox, we introduce BANCO (Betting Algorithm for Noisy COins). BANCO is the first $\epsilon$-LDP SGD algorithm that achieves optimal convergence rates without requiring any learning rate tuning. The core innovation lies in a "divide and conquer" strategy that decomposes the weight vector $w$ into two distinct components:

  1. Direction ($q_t$): A unit vector representing the direction of the weights, updated via a variant of projected SGD with adaptive learning rates.
  2. Magnitude ($m_t$): A scalar representing the scale of the weights, managed by a parameter-free 1D optimization framework based on coin-betting.

The Coin-Betting Framework

Coin-betting treats optimization as a game where the algorithm "bets" a fraction of its current "wealth" on the outcome of a gradient. If the gradient aligns with the bet, wealth increases. This approach is inherently scale-free; it does not require a pre-defined learning rate because it dynamically adapts its bets based on accumulated performance.

Overcoming Unbounded Noise

A primary technical hurdle in applying coin-betting to LDP is that standard parameter-free algorithms require bounded gradients. However, the noise added to satisfy LDP requirements is theoretically unbounded. BANCO overcomes this by demonstrating that as long as the noise follows a specific "tail condition" (conditionally sub-exponential), the betting strategy remains stable and converges effectively.

Theoretical Results

BANCO is a theoretical contribution that provides rigorous convergence guarantees. The algorithm achieves a convergence rate of:

$$\tilde{O}\left(\frac{d \|w^*\|}{\epsilon \sqrt{T}}\right)$$

Where:

  • $d$ is the dimensionality of the problem.
  • $\|w^*\|$ is the norm of the optimal solution.
  • $\epsilon$ is the privacy parameter.
  • $T$ is the number of samples.

This rate is significant because it essentially matches the performance of an "Oracle SGD"—an idealized version of SGD that is pre-configured with the perfect learning rate. BANCO reaches this level of efficiency in a single pass over the data without any prior knowledge of the optimal weight scale, effectively preserving the privacy budget that would otherwise be spent on hyperparameter searches.

Insights and Implications

  • Eliminating the Tuning Overhead: By removing the need for learning rate selection, BANCO transforms hyperparameter tuning from a privacy risk into a non-issue.
  • Scale-Free Decomposition: The separation of direction and magnitude allows the algorithm to use a simple unit-ball learner for direction while delegating the complex task of finding the correct scale to the robust coin-betting mechanism.
  • Robustness to Sub-exponential Noise: The research proves that strictly bounded gradients are not a prerequisite for parameter-free optimization, provided the noise distribution is well-behaved.

Limitations and Future Directions

While BANCO represents a major step forward, some challenges remain. The algorithm currently requires knowledge of noise parameters (variance $\sigma^2$ and tail parameter $b$). Future research could focus on a "fully" parameter-free version that functions without knowing the noise level. Additionally, while the current bounds are "worst-case," future iterations might incorporate data-dependent bounds to capitalize on "easy" datasets. Finally, extending these results from "in expectation" performance to high-probability guarantees will be a necessary step for practical deployment.

Summary updated

Abstract

We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing $\epsilon$-locally differentially private ($\epsilon$-LDP). While it has been shown that stochastic optimization is possible with $\epsilon$-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 $\epsilon$-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.
BibTeX
@misc{jun2019parameter,
  author = {Kwang-Sung Jun and Francesco Orabona},
  title = {{Parameter-Free Locally Differentially Private Stochastic Subgradient Descent}},
  year = {2019},
  eprint = {1911.09564},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.09564},
}
Figure