# Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2025.

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

- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

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 ρ-separation, generalizes and unifies several previous approaches to enforcing this strong stability, including the existence of small-separator sets and the recent notion of γ-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.