Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective
Adam Block, Abhishek Shetty · 2025
Read Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective by Adam Block, Abhishek Shetty (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-2502-10292.txt.
Introduction
Learning systems that must act as data arrive face a tension: adapt quickly to easy cases, but stay stable enough to trust. Adam Block and Abhishek Shetty explore that tension in 2025 for online learning and private learning, two fields that both demand stability. They focus on when a learner can earn so-called small-loss bounds, doing much better on friendly data than worst-case promises suggest.
Their key notion is separation between function classes, which gathers several older conditions under one roof. With separation in place, they give an efficient algorithm that reaches improved small-loss rates, and a private variant with optimal rates. A new stability result for Gaussian process minimizers supports the argument and extends earlier work.
Catalog record
| CREATOR | Adam Block, Abhishek Shetty |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10292
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective Adam Block, Abhishek Shetty Abstract In order to develop practical and efficient algorithms while circumventing overly pessimistic computational lower bounds, recent work has been interested in developing oracle-efficient algorithms in a variety of learning settings. Two such settings of particular interest are online and differentially private learning. While seemingly different, these two fields are fundamentally connected by the requirement that successful algorithms in each case satisfy stability guarantees; in particular, recent work has demonstrated that algorithms for online learning whose performance adapts to beneficial problem instances, attaining the so-called small-loss bounds , require a form of stability similar to that of differential privacy. In this work, we identify the crucial role that separation plays in allowing oracle-efficient algorithms to achieve this strong stability. Our notion, which we term ρ \rho -separation, generalizes and unifies several previous approaches to enforcing this strong stability, including the existence of small-separator sets and the recent notion of γ \gamma -approximability. We present an oracle-efficient algorithm that is capable of achieving small-loss bounds with improved rates in greater generality than previous work, as well as a variant for differentially private learning that attains optimal rates, again under our separation condition. In so doing, we prove a new stability result for minimizers of a Gaussian process that strengthens and generalizes previous work. 1 Introduction In order to satisfy modern resource constraints it is important to develop computationally efficient algorithms for learning. Unfortunately, many function classes of interest are computationally hard to learn, which prompts the search for algorithms that make efficient use of computational primitives, or oracle, that have heuristically motivated and practical implementation in settings of interest. To wit, a common such primitive in learning is the notion of an Empirical Risk Minimization (ERM) Oracle, which grants one the ability to efficiently find a function that minimizes the empirical loss of some loss function on a given data set. This oracle is motivated both by it sufficiency for classical learning ( Shalev-Shwartz and Ben-David, 2014 , Chapter 4) and its practical instantiation in a variety of settings of interest, such as deep neural networks ( LeCun et al., 2015 ) . While a single call to an ERM oracle on independent data suffices for classical learning, there are many alternative settings where the extent to which this oracle can aid learning is less well understood; two examples of such are online and differentially private learning. In online learning, a learner receives adversarially generated data points one in a series of T rounds and, at each time step t , makes a prediction; the learner attempts to minimize his regret to the best function in a given class \mathcal{F} viewed in hindsight ( Cesa-Bianchi and Lugosi, 2006 ) . In addition to being an important learning setting in its own right, online learning algorithms are an important primitive in a number of other applications including sequential decision-making ( Lattimore and Szepesvári, 2020 ) , algorithm design ( Arora et al., 2012 ) , learning in games ( Cesa-Bianchi and Lugosi, 2006 ) , and fairness ( Haghtalab et al., 2023 ) . While online learning is separated from classical learning by removing assumptions on the data, differentially private learning ( Dwork et al., 2006 ) allows independent data but forces the algorithm to satisfy strong stability constraints that ensure that release of a trained model does not leak private information about the data on which it is trained. Due to the increasing deployment of machine learning models, often trained on sensitive customer data, privacy has seen wide application in many fields ( Dwork et al., 2014 ) and has even been adopted by the US Census ( Abowd, 2018 ) . While a priori these two settings may seem quite different, in fact they are intimately related because successful algorithms in both settings require some degree of stability . Indeed, a formal example of this connection is the fact that the combinatorial notion of complexity known as the Littlestone dimension ( Littlestone, 1988 ; Ben-David et al., 2009 ) characterizes learnability in both settings ( Alon et al., 2019 ; Bun et al., 2020 ) . Another way in which online and differentially private learning are connected is in the study of small loss (or L^{\star} ) bounds in online learning ( Cesa-Bianchi and Lugosi, 2006 , Section 2.4) . Typically, one expects regret for online learning to scale like \mathcal{O}(\sqrt{T}) in the worst case. Often, however, one may expect \mathcal{F} to be chosen so that the f\in\mathcal{F} performing best in hindsight has total loss L^{\star}=o(T) ; in such cases, one may hope for algorithms whose regret scales with L^{\star} instead of with T , automatically adapting to the beneficial problem instance. Prior work ( Hutter and Poland, 2004 ; Abernethy et al., 2019 ; Wang et al., 2022 ) has identified differential privacy as an essential ingredient to proving L^{\star} bounds for online learning for a family of algorithms conducive to the application of an ERM oracle, but the generality in which one can efficiently achieve such guarantees are unknown. In this work, we identify a new condition on function classes, \rho -separation ( Definition 5 ), that suffices to ensure oracle-efficient online and differentially private learning. Our condition unifies and generalizes several earlier approaches including small separator sets Dudík et al. (2020) ; Syrgkanis et al. (2016) and \gamma -approximability ( Wang et al., 2022 ) . The notion of \rho -separation requires that functions in \mathcal{F} are sufficiently distinguishable in the sense that distinct functions are not too close to each other in L^{2}(\mu) for some measure \mu ; intuitively, this separation helps ‘boost’ stability in an L^{2} sense to differential privacy. Using \rho -separation, we demonstrate the following: • We present an oracle-efficient algorithm for online learning ( Theorem 1 ) that attains a small-loss ( L^{\star} ) bounds whenever the function class is \rho -separated. We compare our regret to that of alternative oracle-efficient algorithms and find that our approach generalizes and, in many settings, improves upon existing methods. • We show that a variant of the algorithm used for online learning is capable of differentially private PAC-learning with optimal rates whenever \mathcal{F} is \rho -separated, improving on existing results in many cases. In the course of our analysis, we prove a new stability bound for minimizers of Gaussian Processes ( Lemma 1 ) that stengthens prior such bounds both in the precise notion of stability controlled and the generality of the result itself. In Section 2 we state a number of prerequisite notions from learning theory as well as provide a formal definition of \rho -separation. In Section 3 , we provide rigorous statements of our main results as well as the oracle-efficient algorithms achieving the stated bounds; we conclude in Section 4 by providing the main ideas behind our proofs. We defer an extended discussion of related work to Appendix A . 2 Prequisite Notions and \rho -Separation We now recall prerequisite notions, define the main problems of study, and introduce the fundamental assumption underlying our work: \rho -separation. 2.1 Notions from Learning Theory Recall that