Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
\name Omar Montasser \email [email protected] · 2025
Read Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks by \name Omar Montasser \email [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10598.txt.
Introduction
Omar Montasser, Abhishek Shetty, and Nikita Zhivotovskiy rethink how online classifiers should be judged, in a research paper from 2025. In online classification, a model makes a call, learns the truth, and moves on. The usual test compares it with the single best exact predictor, which can set a harsh bar.
The team instead compares models with gentler targets, such as predictors that stay steady under small changes to the input. Their methods come with error bounds that depend on a simpler measure of the class of predictors. They also prove matching lower bounds, so the results cannot be improved much in general.
Catalog record
| CREATOR | \name Omar Montasser \email [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-10598
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks \name Omar Montasser \email [email protected] Abstract 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 / γ ) ) O(\log(1/\gamma)) dependence on the generalized margin γ \gamma . This stands in contrast to most existing regret bounds, which typically exhibit a polynomial dependence on 1 / γ 1/\gamma . We complement this with matching lower bounds. Our analysis connects recent ideas from adversarial robustness and smoothed online learning. Keywords: online learning, binary classification, generalized margin, regret bounds, VC dimension, Littlestone dimension, adversarial robustness, smoothed online learning 1 Introduction We revisit the problem of online learning, specifically online binary classification, which is arguably archetypical setting for sequential decision making, that much of the later theory is built upon. It is well-known that a hypothesis class \mathcal{H} is online learnable if and only if \mathcal{H} has finite Littlestone dimension ( Littlestone, 1987 ; Ben-David, Pál, and Shalev-Shwartz, 2009 ) . In particular, it is well-understood that minimizing regret relative to the smallest achievable error with a class \mathcal{H} is quantified (up to constant factors) by the Littlestone dimension of \mathcal{H} , denoted \mathsf{lit}(\mathcal{H}) , in both the realizable ( Littlestone, 1987 ) and agnostic cases ( Ben-David, Pál, and Shalev-Shwartz, 2009 ; Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev, 2021a ) . Though, we have this precise combinatorial characterization, online learning is challenging. This is exemplified by arguably the simplest hypothesis class: thresholds on the unit interval \mathcal{H}=\Big\{x\mapsto\operatorname{sign}(x-\theta)\,\Big|\,\theta\in[0,1]\Big\} which is not online learnable since it has infinite Littlestone dimension, implying that any learner can be forced to make infinitely many mistakes even when the adversarial sequence is realizable by a threshold. Needless to say, the learning of classes induced by linear functions, such as thresholds or general halfspaces, is arguably one of the most basic problems in machine learning. Given this pessimistic situation, the learning theory community has developed several techniques to bypass the above lower bound. • A classical perspective on learning linear classifiers, that perhaps even predated the modern theory of online learning, is the assumption of margin . It is well known that, when the online sequence satisfies a margin assumption, the Perceptron algorithm ( Rosenblatt, 1958 ) can learn thresholds (and more generally halfspaces) with a mistake bound of O(1/\gamma^{2}) ( Novikoff, 1962 ) , where \gamma>0 is the margin parameter. The sequential margin bound can be generalized to the agnostic case ( Cesa-Bianchi et al., 2005 ; Mohri and Rostamizadeh, 2013 ) , showing the same polynomial dependence on the inverse margin 1/\gamma . • A more recent direction is smoothed online learning . Simplifying the setup, the idea is to assume that there is some known base density \mu such that, at each round, the new observation X_{t} is generated from a density which has density ratio with respect to \mu bounded by 1/\sigma , where \sigma>0 is called the smoothness parameter. In its simplest form, this assumption allows one to prove regret bounds of the form O\bigl(\sqrt{\mathsf{vc}(\mathcal{H})T\log(T/\sigma)}\bigr) ( Haghtalab, Roughgarden, and Shetty, 2024 ) . In this work, with a similar aim of bypassing pessimistic lower bounds, we study online learning from a different perspective: relaxing the notion of optimality . That is, instead of minimizing regret relative to the smallest achievable error with a class \mathcal{H} , denoted by \mathsf{OPT} , we consider minimizing regret relative to relaxed benchmarks: \mathsf{OPT^{\gamma}_{pert}} ( 2 ), \mathsf{OPT^{\sigma,\varepsilon}_{gauss}} ( 3 ), and \mathsf{OPT^{\gamma}_{margin}} ( 6 ). These can be thought of as generalizations of the classic margin assumption for halfspaces that are defined more broadly for generic hypothesis classes. The introduction of these benchmarks is partially inspired by the seminal work of Spielman and Teng (2004) on smoothed analysis, and more recently the work of Chandrasekaran, Klivans, Kontonis, Meka, and Stavropoulos (2024) which demonstrated the computational benefits of competing with a relaxed notion of optimality in agnostic PAC learning. This work explores statistical benefits of these relaxations in the context of online learning. To better understand our motivation, we put some existing results in context. Arguably the most well-known relaxation of the binary loss in the sequential setting, closely related to the margin loss, is the hinge loss , whose normalized version for y\in\{-1,1\} and f(x) a real-valued predictor satisfies \mathds{1}[\operatorname{sign}(f(x))\neq y]\leq\frac{\max\left\{0,\gamma-yf(x)\right\}}{\gamma}. The following regret bound, relevant to our discussion, is given by the Perceptron algorithm ( Mohri and Rostamizadeh, 2013 , see e.g., Corollary 1 in) ; see also ( Cesa-Bianchi et al., 2005 ) ). For any \gamma>0 , and any (adversarially chosen) sequence (x_{t},y_{t})_{t=1}^{T} with y_{t}\in\{-1,1\} and x_{t}\in\mathbb{R}^{d},\lVert x_{t}\rVert_{2}\leq 1 , \sum\limits_{t=1}^{T}\mathds{1}[\widehat{y}_{t}\neq y_{t}]-\underbrace{\min_{w\in{\mathbb{R}}^{d},\lVert w\rVert_{2}=1}\sum\limits_{t=1}^{T}\frac{\max\left\{0,\gamma-y_{t}\left\langle w,x_{t}\right\rangle\right\}}{\gamma}}_{\mathsf{OPT^{\gamma}_{hinge}}}\leq\sqrt{\frac{T}{\gamma^{2}}}. (1) In the particular setup of the regret bound ( 1 ), we observe polynomial dependence on \tfrac{1}{\gamma} (as in Novikoff’s margin bound). However, it can be shown that requiring polynomial dependence on \tfrac{1}{\gamma} is overly pessimistic. For context, the regret bound of Gilad-Bachrach, Navot, and Tishby (2004) , in the margin setting of Novikoff, provides an O\bigl(d\log\!\bigl(\tfrac{1}{\gamma}\bigr)\bigr) bound and thus achieves dimension dependence alongside a more favorable logarithmic dependence on \tfrac{1}{\gamma} . Recently, Qian, Rakhlin, and Zhivotovskiy (2024) extended the bound ( 1 ) using a version of the exponential weights algorithm with respect to the hinge loss, again combining dependence on d with only logarithmic dependence on \tfrac{1}{\gamma} . An important remark regarding the comparison of bounds O\bigl(d\log\!\bigl(\tfrac{1}{\gamma}\bigr)\bigr) and Novikoff’s “dimension-free” bound O\bigl(\!\tfrac{1}{\gamma^{2}}\bigr) is in order. While each has regimes where it is preferable, Novikoff’s bound relies on the rescaling \max_{t}\|x_{t}\|_{2}\leq 1 , which is often unrealistic in high dimensions where norms typically grow as \sqrt{d} (e.g., for a multivariate Gaussian distribution). In the natural rescaling where \max_{t}\|x_{t}\|_{2}\sim\sqrt{d} , our parametric bounds scale as O\bigl(d\log\!\bigl(\tfrac{d}{\gamma^{2}}\bigr)\bigr) , usually outperforming Novikoff’s weaker O\bigl(\!\tfrac{d}{\gamma^{2}}\bigr) bound. This serves as additional motivation for studying O\bigl(d\log\!\bigl(\tfrac{1}{\gamma}\bigr)\bigr) -style regret bounds. A more detailed discussion is deferred to Section 3 . Since the hinge loss is merely one form of relaxing the binary loss, and noting the surprising lack of results in the literature with logarithmic dependence on the inverse generalized margin \tfrac{1}{\gamma} , we are interested in understanding when such favorable regret bounds can be achieved in broader scenarios: We aim for new regret bounds that replace the prohibitive Littlestone dimension with dependence on the VC dimension, while incurring only a logarithmic dependence on the inverse generalized margin \tfrac{1}{\gamma} , by competing against one of the smoothed comparators \mathsf{OPT}^{\gamma} given below by ( 2 ), ( 3 ), ( 6 ). Notation and Preliminaries. We consider instance spaces \mathcal{X} that are equipped with a metric \rho:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{\geq