# Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

arXiv: https://arxiv.org/abs/2504.10598 · HTML: https://mlsanity.com/paper/2504.10598/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 14 Apr 2025.

## Builds on (most cited first, 22 of 22)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin](https://mlsanity.com/paper/1908.11335/) (2019)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Perceptron Mistake Bounds](https://mlsanity.com/paper/1305.0208/) (2013)
- [Refined Risk Bounds for Unbounded Losses via Transductive Priors](https://mlsanity.com/paper/2410.21621/) (2024)
- [Agnostic Smoothed Online Learning without Knowledge of the Base Measure](https://mlsanity.com/paper/2410.05124/) (2024)

## Built on by (most cited first, 2 of 2)

- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Minimizing Human Intervention in Online Classification](https://mlsanity.com/paper/2510.23557/) (2025)

## Abstract (arXiv)

We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notions of optimality. Instead of measuring regret relative to the exact minimal binary error -- a standard approach that leads to worst-case bounds tied to the Littlestone dimension -- we consider comparing with predictors that are robust to small input perturbations, perform well under Gaussian smoothing, or maintain a prescribed output margin. Previous examples of this were primarily limited to the hinge loss. Our algorithms achieve regret guarantees that depend only on the VC dimension and the complexity of the instance space (e.g., metric entropy), and notably, they incur only an O(log(1/γ)) dependence on the generalized margin γ. This stands in contrast to most existing regret bounds, which typically exhibit a polynomial dependence on 1/γ. We complement this with matching lower bounds. Our analysis connects recent ideas from adversarial robustness and smoothed online learning.