Small-Loss Regret Bounds in Online Learning

50 concepts38 papers1 proposal

In online learning, we evaluate algorithms by their regret: the difference between the cumulative loss the algorithm incurs and the cumulative loss of the best fixed strategy in hindsight. Standard worst-case regret bounds typically scale with the total time horizon $T$, often taking the form $O(\sqrt{T})$. While optimal in a worst-case adversarial environment, this bound is deeply pessimistic when the environment is benign. If you are choosing among a set of experts, and one of them makes perfect predictions every single time, a standard algorithm will still incur $O(\sqrt{T})$ mistakes before locking onto the truth.

To bridge this gap, researchers developed first-order or small-loss regret bounds. Instead of scaling with the time horizon $T$, these bounds scale with $L^*$, the cumulative loss of the best strategy. If a perfect strategy exists ($L^* = 0$), a first-order algorithm can achieve constant regret, meaning it stops making mistakes entirely after a finite number of rounds. Early foundations by Mark Herbster et al. in Tracking the Best Expert showed that tracking algorithms could achieve performance independent of the sequence length, depending instead on the loss of the best expert sequence.

The Mathematical Engine: Smoothness and Self-Bounding Gradients

To understand why we can replace $T$ with $L^*$, we have to look at how online optimization algorithms update their parameters. In standard Online Convex Optimization (OCO), the regret bound is driven by the magnitudes of the gradients of the loss functions. If gradients are large, the algorithm makes large, potentially erroneous adjustments.

The breakthrough insight—leveraged by Francesco Orabona et al. in Beyond Logarithmic Bounds in Online Learning and Andrew Jacobsen et al. in Unconstrained Online Learning with Unbounded Losses—comes from the property of smoothness. For a non-negative, smooth function, the norm of the gradient squared is fundamentally bounded by the value of the function itself:

$$\|\nabla f(x)\|^2 \le 2H f(x)$$

where $H$ is the smoothness parameter.

This "self-bounding" property creates a powerful feedback loop. When the best strategy incurs very little loss, the losses around the optimum are small, which forces the gradients to shrink. As the gradients shrink, the variance of the algorithm's updates drops dramatically. By designing adaptive learning rates that scale inversely with these accumulated gradients (or via adaptive relaxations as shown by Alexander Rakhlin et al. in ZigZag: A New Approach to Adaptive Online Learning), the regret bound naturally transforms from a function of the time horizon into a function of the cumulative loss $L^*$. As Guanghui Wang et al. demonstrate in Adapting to Smoothness: A More Universal Algorithm for Online Convex Optimization, this adaptivity can be achieved universally without sacrificing worst-case guarantees if the environment turns out to be truly adversarial.

Overcoming the Feedback Gap in Bandit Settings

In the full-information setting, the learner observes the loss of every action at each step. But what happens in bandit settings, where you only observe the loss of the action you actually chose?

In bandits, achieving small-loss bounds is notoriously difficult because the learner must actively explore suboptimal actions to discover if they are good. If the learner explores too aggressively, it incurs regret proportional to $T$, destroying the first-order guarantee.

The solution lies in adaptive exploration. Algorithms must couple their exploration rate directly to the estimated magnitudes of the losses. As analyzed by Akshay Krishnamurthy et al. in Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination and Thodoris Lykouris et al. in Small-loss bounds for online learning with partial information, if the predicted losses for the top actions are small, the algorithm can safely reduce its exploration. By utilizing specialized information-theoretic tools like triangular discrimination or dual-threshold freezing mechanisms, the learner can ensure that the cost of exploration scales with $L^*$ rather than $T$. This principle has been successfully extended to complex structured settings, such as combinatorial semi-bandits by Gergely Neu in First-order regret bounds for combinatorial semi-bandits.

Expanding Across Complex Paradigms

The intuition of small-loss adaptivity has recently rippled across more complex paradigms in machine learning:

Key Foundational Work

Minimizing Wide Range Regret with Time Selection Functions (2008) — contributed 3 concept elements to this direction.
Tracking the Best Expert (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_first_order_regret_bounds_1c087536,
  title = {first-order regret bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-regret-bounds/rdr_1c087536ebfd4895bff3fac56a01d793},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_first_order_regret_bounds_1c087536_v1,
  title = {first-order regret bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-regret-bounds/rdr_1c087536ebfd4895bff3fac56a01d793/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake