Smoothed Analysis of Online and Differentially Private Learning

Nika Haghtalab, Tim Roughgarden, Abhishek Shetty

Abstract

Worst-case analysis suggests that online and differentially private (DP) learning are impossible for many fundamental models, such as linear thresholds, due to their infinite Littlestone dimensions. This paper demonstrates that by assuming a small degree of realistic, nature-induced noise—a framework known as "smoothed analysis"—we can bypass these pessimistic bounds. We show that under $\sigma$-smooth distributions, the learnability of a hypothesis class is governed by its VC dimension rather than its Littlestone dimension. We provide new algorithms for online learning against adaptive adversaries and for DP query release, achieving strong performance guarantees that depend only on the model's VC dimension and the smoothness parameter.

Introduction

In machine learning theory, the feasibility of learning in online or differentially private settings is traditionally characterized by the Littlestone dimension. This metric measures the complexity of a hypothesis class by its ability to withstand a sequence of adversarial queries. Unfortunately, the Littlestone dimension is notoriously unforgiving; even simple, practical classes like one-dimensional thresholds, halfspaces, or basic neural networks have an infinite Littlestone dimension.

In a worst-case scenario, an omnipotent adversary with infinite precision can force a learner to make mistakes indefinitely, leading to theoretical impossibility results. However, real-world data is rarely generated by a perfectly precise, worst-case adversary. There is almost always inherent measurement error or natural uncertainty. This paper addresses the gap between pessimistic theory and practical success by asking: if we restrict the adversary to generating data distributions that are slightly "smoothed," can we recover learnability for these models?

The Smoothed Analysis Framework

The authors apply smoothed analysis to both online and DP learning. In this framework, the adversary does not pick exact, worst-case data points. Instead, they choose a $\sigma$-smooth distribution—meaning the probability density of the data is bounded by $1/\sigma$ times the uniform distribution. The actual data point is then sampled from this distribution. This restriction prevents the adversary from concentrating all probability mass on a single, difficult point, effectively limiting their precision.

Online Learning with Adaptive Adversaries

The primary challenge in online learning is the presence of adaptive adversaries, where future data points can depend on the learner's past actions. This dependency breaks the standard independent and identically distributed (i.i.d.) assumptions required for traditional VC theory.

To solve this, the authors introduce an algorithm that utilizes a finite proxy set (a "cover") of the infinite hypothesis class and employs a no-regret algorithm like Hedge. To handle the time-correlation introduced by adaptive adversaries, the authors utilize bracketing numbers. This statistical concept creates pointwise upper and lower bounds for functions, allowing the authors to bound stochastic processes over infinite hypothesis classes without relying on i.i.d. data. This technical breakthrough allows the learner to achieve regret bounds that scale with the VC dimension.

Differentially Private Learning and Data Release

In the context of Differential Privacy (DP), the authors modify the Multiplicative Weights Exponential Mechanism (MWEM). Standard MWEM error typically scales with the size of the data domain and the hypothesis class. By leveraging $\sigma$-smoothness, the authors construct a data-independent cover of queries based on the uniform distribution.

Because this cover is constructed without looking at the actual sensitive dataset, it preserves privacy perfectly while significantly reducing the problem space. The authors also introduce "Projected Smooth MWEM," which maintains accuracy by projecting intermediate distributions back onto the space of smooth distributions during the data release process.

Key Results

The paper provides several significant theoretical improvements over worst-case models:

  • Online Learning: The authors prove a regret bound of $\tilde{O}(\sqrt{T \cdot \text{VCDim}(\mathcal{H}) \ln(1/\sigma)})$ for classes such as halfspaces and polynomial thresholds. In a worst-case model, these same classes would suffer linear regret, $O(T)$, rendering them unlearnable.
  • Differentially Private Learning: For query answering and data release, the authors achieve an error bound of $\tilde{O}(\ln^{3/8}(1/\sigma) \sqrt{\text{VCDim}(\mathcal{H})/n})$. Crucially, this bound is independent of the data domain size $|\mathcal{X}|$ and the hypothesis class size $|\mathcal{H}|$, a massive improvement over standard DP algorithms.

Discussion and Future Work

This work demonstrates that the impossibility results tied to the Littlestone dimension are brittle. A tiny amount of nature's noise ($\sigma$-smoothness) makes robust learning possible again. The realization that smoothness enables "free" privacy—by allowing the construction of proxy sets without consuming the privacy budget—is a particularly potent insight for the design of future DP algorithms.

While the paper provides strong upper bounds, the authors note the absence of matching lower bounds. A major future direction is to fully characterize the fundamental limits of learnability in the smoothed setting. They suggest that a combinatorial metric known as "sign rank" might be the key to this characterization. Additionally, the question remains whether any hypothesis class with a finite VC dimension remains unlearnable even when the adversary is smoothed.

Summary updated

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