Logarithmic Regret through Curvature in Online Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 290 papers121 conceptsfrozen 2026-10-04

In online learning, the "speed limit" of adaptation is typically defined by regret—the difference between the cumulative loss an algorithm incurs and the loss it would have incurred had it known the best fixed decision in hindsight. For general convex functions, the standard achievable rate is $O(\sqrt{T})$, meaning the average error vanishes at a rate of $1/\sqrt{T}$.

However, a significant body of research demonstrates that we can break this speed limit, achieving "fast rates" of $O(\log T)$ regret. The secret lies in curvature. Whether it resides in the objective function being minimized or the geometric shape of the feasible decision set, curvature provides a stabilizing force that allows algorithms to commit to optimal actions much faster than they could in "flat" environments.

The Stabilizing Power of Strong Convexity

The most common source of curvature is strong convexity. While a general convex function can be flat (like a plateau), a strongly convex function is strictly bowl-shaped. This geometric property ensures that any move away from the optimum results in a penalty that grows at least quadratically.

In adaptive gradient methods, this curvature is the key to efficiency. As Guanghui Wang and Lijun Zhang demonstrate with SAdam, standard optimizers like Adam often fail to exploit this curvature, sticking to $O(\sqrt{T})$ rates. By incorporating a $1/t$ step-size decay, algorithms like FastAdaBelief can accelerate to $O(\log T)$ regret.

The intuition is that curvature reduces the "drift" of the optimal solution. In a flat landscape, a small change in the data can shift the optimum to the other side of the domain. In a curved landscape, the optimum is "trapped" at the bottom of the bowl, allowing the learner to stabilize their decisions. This stability is so potent that it even allows for logarithmic regret in asynchronous environments with delays, as shown by Lei Bao and Yuanyu Wan in Revisiting Multi-Agent Asynchronous Online Optimization with Delays.

Geometry as a Substitute for Curvature

What if the loss function is linear and has no curvature of its own? Remarkably, the learner can still achieve logarithmic regret if the feasible set—the space of allowed decisions—is curved.

In Stochastic Linear Optimization under Bandit Feedback, Varsha Dani, Sham M. Kakade, and Thomas P. Hayes characterized how the geometry of the decision set dictates performance. If the set is a polytope (flat faces and sharp corners), the learner can eventually isolate the optimal vertex and achieve logarithmic regret. If the set is smooth (like a sphere), the learner is forced into continuous exploration, leading to $O(\sqrt{T})$ regret.

However, Marco Molinaro argues in Curvature of Feasible Sets in Offline and Online Optimization that "roundness" can actually be a benefit. When the feasible set is uniformly convex, it acts as a natural regularizer. This curvature prevents radical shifts in the optimal solution as new data arrives, allowing simple greedy strategies to perform as well as complex regularized methods. Shinji Ito further unified these views in Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets, showing that algorithms designed to exploit loss curvature can automatically leverage set curvature to reach logarithmic regret.

Curvature in Control and Constraints

This "fast rate" phenomenon extends into complex systems like adaptive control and constrained optimization. In the Linear Quadratic Regulator (LQR) setting, the cost functions are quadratic—the quintessential curved function.

Naman Agarwal, Elad Hazan, and Karan Singh demonstrated in Logarithmic Regret for Online Control that this curvature allows for logarithmic regret even in noisy dynamical systems. Similarly, Sahin Lale and Anima Anandkumar showed that this holds even for partially observable systems where the internal state is hidden.

The benefits of curvature also apply to safety and constraints. When dealing with long-term or stochastic constraints, strong convexity allows for a simultaneous reduction in both regret and constraint violations. As explored by Abhishek Sinha and Rahul Vaze in Optimal Algorithms for Online Convex Optimization with Adversarial Constraints, the geometric properties of the cost landscape can be leveraged to improve performance without sacrificing the stability of the system's constraints.

Summary of the Intuition

The transition from square-root to logarithmic regret is essentially a transition from uncertainty to stability:

  1. General Convexity: The landscape is flat. A tiny change in information can move the "best" decision a long distance. The learner must move cautiously, leading to slower $O(\sqrt{T})$ convergence.
  2. Strong Curvature: The landscape (or the decision boundary) is steep. The "best" decision is anchored by the geometry. The learner can use this "gravity" to converge much faster, reaching the $O(\log T)$ limit.

Papers in this version

Showing 60 of 90 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 95 papers
  2. Version 1 · 2026-10-04 · 90 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curvature_dependent_regret_bounds_cddc5e41,
  title = {curvature-dependent regret bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curvature-dependent-regret-bounds/rdr_cddc5e4108424324bf6a1a66d27eadb9},
  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_logarithmic_regret_through_curvature_in__cddc5e41_v1,
  title = {Logarithmic Regret through Curvature in Online Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-regret-through-curvature-in-online-optimization/rdr_cddc5e4108424324bf6a1a66d27eadb9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}