Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
This work addresses the problem of improving worst-case regret bounds in online learning for researchers, offering a novel approach but is incremental as it builds on existing adversarial robustness and smoothed learning ideas.
The paper tackles online binary classification by competing against relaxed benchmarks like smoothed optimality, achieving regret bounds that depend only on VC dimension and instance space complexity, with an O(log(1/γ)) dependence on margin γ, contrasting with typical polynomial bounds.
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.