Smoothed Analysis of Online and Differentially Private Learning

Nika Haghtalab, Tim Roughgarden, Abhishek Shetty

Introduction

In the realms of online and differentially private (DP) learning, "worst-case" scenarios often lead to discouraging impossibility results, even for simple models like linear thresholds. This paper breaks that theoretical deadlock by applying smoothed analysis. By assuming that nature adds just a small amount of noise to the data, the authors demonstrate that these models become efficiently learnable. Crucially, they provide guarantees that depend on the model's Vapnik-Chervonenkis (VC) dimension rather than the much more restrictive Littlestone dimension.

The Core Problem: Worst-Case Pessimism

Machine learning theory often distinguishes between "offline" learning (where the entire dataset is available at once) and "online" learning (where data arrives sequentially, one point at a time). In the offline setting, a model is considered learnable if it has a finite VC dimension, which measures its capacity or complexity.

However, in online learning and Differential Privacy, the standard for learnability is much higher and is characterized by the Littlestone dimension. The problem arises because many ubiquitous models—such as linear thresholds (halfspaces) and neural networks—have a finite VC dimension but an infinite Littlestone dimension. Under traditional worst-case analysis, an adversary can provide a sequence of data points that forces any online learner to make an infinite number of mistakes. Similarly, this implies that these models cannot be learned privately without an impractically massive amount of data.

The authors argue that this worst-case perspective is overly pessimistic. In real-world scenarios, data is rarely chosen by a malicious entity with infinite precision. Instead, there is usually some measurement error, inherent uncertainty, or natural "smoothness" in the environment.

Methodology: Smoothed Analysis and Bracketing

To overcome the limitations of worst-case bounds, the authors employ the framework of smoothed analysis. Instead of a worst-case adversary, they introduce a $\sigma$-smooth adversary. In this model, the adversary chooses a distribution for the next data point, but that distribution cannot be overly concentrated (or "pointy"). It must be somewhat spread out, reflecting natural environmental noise.

To prove their results, the authors transition from standard "covering numbers" to bracketing numbers:

  • Standard Cover: A set of functions that are "close" to any function in the hypothesis class on average.
  • Bracketing Cover: A set of pairs of functions (brackets) that strictly "sandwich" every function in the class pointwise.

For the online learning setting, they utilize a modified version of the Hedge algorithm that competes against a finite proxy set derived from these brackets. For Differential Privacy, they introduce two novel algorithms: Smooth MWEM and Projected Smooth MWEM. The "Projected" variant is particularly innovative, using KL-divergence projections to ensure that the synthetic data generated by the algorithm remains "smooth." This prevents the privacy mechanism from becoming too concentrated on specific, noisy data points.

Theoretical Scope

As a theoretical foundation, the paper does not rely on empirical datasets like ImageNet or MNIST. Instead, it provides rigorous mathematical proofs for broad categories of hypothesis classes, including:

  • Halfspaces (Linear Thresholds): The fundamental building blocks of classification.
  • Polytopes: Intersections of multiple halfspaces.
  • Polynomial Threshold Functions: More complex, non-linear decision boundaries.

The paper demonstrates that while these classes are deemed "unlearnable" in worst-case online and private settings, they are perfectly tractable under smoothed analysis.

Key Insights and Results

The Brittleness of Impossibility

The "infinite mistakes" result for online learning relies on an adversary's ability to pick points with infinite precision—akin to a binary search that never terminates. Smoothness effectively limits this precision, "rounding off" the adversary's ability to exploit the model's exact boundaries.

Adaptivity is the Real Enemy

The paper draws a sharp distinction between non-adaptive adversaries (who determine the noise ahead of time) and adaptive ones (who react to the learner's choices). While standard covers suffice for non-adaptive noise, the stronger "bracketing" approach is necessary to defeat an adaptive adversary.

Smoothness as a Regularizer in DP

In Differential Privacy, the "Projected Smooth MWEM" algorithm demonstrates that forcing the internal model to maintain smoothness actually accelerates its convergence to the true data distribution.

Quantitative Guarantees

  • Online Learning: The authors achieve a regret bound of $\tilde{O}(\sqrt{T \cdot \text{VCDim}(\mathcal{H}) \ln(1/\sigma)})$. Crucially, this bound depends on the VC dimension, rendering online learning possible for any class that is learnable offline.
  • Differential Privacy: They provide error bounds that are independent of the domain size. Traditional DP algorithms often suffer from errors that scale with the number of possible inputs (which is infinite for continuous data). The proposed algorithms bypass this limitation entirely by leveraging smoothness.
  • Unified Framework: The paper establishes a systematic method to bound the complexity of intricate models (like intersections or unions of shapes) by analyzing the growth of their bracketing numbers.

Limitations and Future Work

While the paper makes significant theoretical strides, the authors note a few limitations and avenues for future research:

  • Computational Complexity: The paper proves that these models are statistically learnable (achieving low regret/error), but it does not always provide a computationally efficient method to find the "brackets" for every possible hypothesis class.
  • Tightness of Bounds: Although the authors have proven robust upper bounds, it remains an open question whether these bounds are "tight" (the best possible) or if a different combinatorial measure—perhaps a "smoothed Littlestone dimension"—exists.
  • Characterizing Learnability: The authors suggest that future work could investigate "sign rank" as a potential candidate for a more fundamental characterization of what makes a problem learnable in a smoothed environment.

Summary updated

Abstract

Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary quantity that characterizes learnability in these settings is the Littlestone dimension of the class of hypotheses [Ben-David et al., 2009, Alon et al., 2019]. This characterization is often interpreted as an impossibility result because classes such as linear thresholds and neural networks have infinite Littlestone dimension. In this paper, we apply the framework of smoothed analysis [Spielman and Teng, 2004], in which adversarially chosen inputs are perturbed slightly by nature. We show that fundamentally stronger regret and error guarantees are possible with smoothed adversaries than with worst-case adversaries. In particular, we obtain regret and privacy error bounds that depend only on the VC dimension and the bracketing number of a hypothesis class, and on the magnitudes of the perturbations.
BibTeX
@inproceedings{haghtalab2020smoothed,
  author = {Nika Haghtalab and Tim Roughgarden and Abhishek Shetty},
  title = {{Smoothed Analysis of Online and Differentially Private Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=CUHo8yqdI89},
}
Figure