Research map / Learning theory and algorithms / Sample complexity
Smoothed Online Classification can be Harder than Batch Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that smoothed online classification with an oblivious adversary can be strictly harder than PAC batch learning when the label space is unbounded, and gives a sufficient condition (UBEME) for smoothed online learnability.
Problem
Whether smoothed online classification is as easy as iid batch (PAC) classification for arbitrary label spaces under an oblivious smoothed adversary, and what characterizes smoothed online learnability.
Approach
Constructs a hypothesis class with a size-1 compression scheme (hence PAC learnable) whose smoothed online regret is linear in T when the label space is unbounded, and proves a sufficient condition based on uniformly bounded expected empirical metric entropy (UBEME) with respect to the base measure, via covering numbers and randomized exponential weights.
Key results
- Constructs a hypothesis class with a size-1 compression scheme whose smoothed online regret is at least T/2 for mu=Uniform and sigma=1, separating agnostic PAC from smoothed online learnability when the label space is unbounded.
- For finite label space K, regret lower bound log K / (24 log log K), linear in T when K >= 2^{T log T}.
- Sufficiency: regret at most 6 inf_eps {eps T/sigma + sqrt(T log C)}, giving O(sqrt(T G(H) log(T|Y|/sigma^2))) for finite Y.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an unbounded-label hypothesis class with a size-1 compression scheme | Smoothed online classification under Uniform([0,1]), σ=1 · Uniform([0,1]), σ=1 | regret: regret lower bound \frac{T}{2} | Hurt |
| Restrict the label space to finite size K | Constructed class with a size-1 compression scheme · Uniform(𝒳), σ=1 | regret: regret lower bound \frac{\log{K}}{24\log{\log{K}}} | Mixed |
| Assume uniformly bounded expected empirical metric entropy | Smoothed online classification · Smoothed online classification | regret: 6 \inf_{\varepsilon > 0} \Biggl\{ \frac{\varepsilon T}{\sigma} + \sqrt{T \log (C_{\varepsilon^2, \sigma}(\mathcal{H}, \m | Helped |
| Assume finite graph dimension and finite label space | Smoothed online classification · Finite |𝒴| | regret: 12 \sqrt{T \, \operatorname{G}(\mathcal{H}) \, \log \Bigl(\frac{41 \, T \, |\mathcal{Y}|}{\sigma^2}\Bigl)} | Helped |
| Use finite-set indicators whose functions agree μ-almost everywhere | Smoothed online classification under Uniform([0,1]) · Uniform([0,1]), σ>0 | regret: \frac{T}{2} | Hurt |
| Use constant functions over an infinite label space | Smoothed online classification under Uniform([0,1]) · Uniform([0,1]), σ>0 | regret: O(\sqrt{T \log(T)}) | Helped |
Surprising findings
- PAC learnability is not sufficient for smoothed online learnability when the label space is unbounded.
- Finiteness of the covering number N(eps, H, d_mu) is neither necessary nor sufficient for smoothed online learnability.
Limitations
- Sufficiency condition is not necessary (e.g., constant functions over N are learnable but violate UBEME).
- Results proven for oblivious adversary choosing labels after the full sample; adaptive case not covered.
- No characterization of smoothed online learnability as a joint property of (H, mu) is given.
Experimental setup
Metrics: expected regret
Baselines: Haghtalab et al. 2020 Block et al. 2022
Builds on: Haghtalab et al. smoothed online learning Block et al. smoothed online learning compression implies learning Randomized Exponential Weights Algorithm
Closest papers by meaning
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.85)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.85)
- Information-theoretic Limits of Online Classification with Noisy Labels (NeurIPS 2024 · similarity 0.85)
- Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · similarity 0.85)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.84)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.