User-Specified Local Differential Privacy in Unconstrained Adaptive Online Learning

Dirk van der HoevenNeurIPS 2019 · OpenReview

Overview

This paper introduces a framework for "User-Specified" Local Differential Privacy (LDP) in online learning. It allows data providers to choose their own noise levels without revealing these parameters to the central learner. The author develops the first algorithms for unconstrained online convex optimization that adapt to unknown noise, unknown competitor norms, and sparse data, matching the theoretical performance of state-of-the-art noiseless algorithms.

The Problem: Rigid Privacy and Bounded Domains

In privacy-preserving machine learning, Local Differential Privacy (LDP) is a gold standard. It requires the data provider (the user) to add random noise to their data before sending it to a central learner. However, standard LDP has two major limitations:

  1. One Size Fits All: Traditional models assume every user wants the same level of privacy (a uniform $\epsilon$). In reality, privacy needs vary drastically depending on the user and the sensitivity of specific data points.
  2. The "Privacy of Privacy": If a user reveals the exact amount of noise they are adding, that information itself could be a privacy leak. Ideally, a learner should be able to learn effectively without ever knowing the specific noise parameters chosen by each user.

Furthermore, the paper addresses these issues in the unconstrained setting. Most algorithms assume the optimal solution lies within a known, bounded area. If that assumption is wrong, standard algorithms often fail or require manual tuning of hyperparameters—a task made impossible without knowing the noise levels in advance.

Methodology: Wealth-Regret Duality and Adaptive Learning

To solve these challenges, the author utilizes Wealth-Regret Duality. This approach treats online learning like a betting game: instead of trying to minimize "regret" (the difference between performance and the best possible fixed strategy), the algorithm tries to maximize "wealth" by betting on the direction of future gradients.

Key technical innovations include:

  • Symmetric Noise Assumption: The paper proves that as long as the noise added by users is symmetric (like Laplace or Gaussian mechanisms) and zero-mean, the learner does not need to know the noise's variance or distribution.
  • Adaptive Potential Function: The author derives a new mathematical "potential function" that includes a specific squared-gradient term. This allows the algorithm to automatically "sense" the noise level from the data it receives and adjust its step size accordingly.

Black-Box Reduction

The paper provides a method to take a standard, constrained learning algorithm and wrap it in the new adaptive potential function to make it work in unconstrained, noisy environments.

Algorithm 2: Black-Box Reduction

Coordinate-wise Adaptation

For high-dimensional data where only a few features might be noisy or relevant, the author introduces an algorithm that treats every dimension of the data independently.

Algorithm 3: Private Unconstrained Adaptive Sparse Gradient Descent

Key Insights and Theoretical Results

This theoretical research focuses on mathematical proofs and algorithmic guarantees. The core insights include:

  • Privacy Autonomy: Users can add varying amounts of noise to different parts of their data, and the algorithm will still converge to the best possible answer at the optimal rate.
  • Symmetry is a Superpower: Because the noise is equally likely to be positive or negative, its effect cancels out over time in the wealth-regret framework, even if the learner is blind to the noise's magnitude.
  • Parameter-Free Learning: The algorithms do not require the user to guess the norm of the best solution ($\lVert u \rVert$) or the total amount of noise. They adapt to the difficulty of the problem on the fly.

The paper provides a rigorous proof that the expected regret of the new algorithms is bounded by: $$O\left(\|u\| \sqrt{\sum_{t=1}^T E[\|\tilde{g}_t\|^2] \ln(1 + \|u\|T)}\right)$$

This demonstrates optimal scaling: the error grows only with the square root of the total noise and gradient energy. The algorithm performs as well as if it were in a noiseless environment, simply scaling its error based on the actual noise encountered. Furthermore, in high-dimensional settings, if the noise or the data is sparse, the coordinate-wise algorithm achieves significantly lower regret than standard methods like AdaGrad.

Limitations and Future Work

  • Symmetry Requirement: The noise must be symmetric. While this covers popular privacy mechanisms, it precludes asymmetric noise distributions.
  • Bounded Expected Gradients: The proofs assume that while the noisy data can be arbitrarily large, the underlying true data (the expected gradient) has a bounded norm ($G$).
  • Empirical Validation: As a purely theoretical paper, it lacks experimental results on real-world datasets (e.g., training a private neural network), which remains a natural next step for practitioners.

Summary updated

Abstract

Local differential privacy is a strong notion of privacy in which the provider of the data guarantees privacy by perturbing the data with random noise. In the standard application of local differential differential privacy the distribution of the noise is constant and known by the learner. In this paper we generalize this approach by allowing the provider of the data to choose the distribution of the noise without disclosing any parameters of the distribution to the learner, under the constraint that the distribution is symmetrical. We consider this problem in the unconstrained Online Convex Optimization setting with noisy feedback. In this setting the learner receives the subgradient of a loss function, perturbed by noise, and aims to achieve sublinear regret with respect to some competitor, without constraints on the norm of the competitor. We derive the first algorithms that have adaptive regret bounds in this setting, i.e. our algorithms adapt to the unknown competitor norm, unknown noise, and unknown sum of the norms of the subgradients, matching state of the art bounds in all cases.
BibTeX
@inproceedings{hoeven2019user,
  author = {Dirk van der Hoeven},
  title = {{User-Specified Local Differential Privacy in Unconstrained Adaptive Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=aoWbRpFbhj},
}
Figure