In Online Convex Optimization (OCO), a learner repeatedly makes decisions in the face of changing, adversarial loss functions. If the environment is completely flat—meaning the loss functions are linear and the decision space is a flat polytope—the learner faces a fundamental speed limit. In this worst-case scenario, the best achievable regret grows at a sublinear rate of $O(\sqrt{T})$.
Why is $O(\sqrt{T})$ the limit for flat functions? Consider a simple Follow-the-Leader (FTL) strategy. If the cumulative loss vector shifts even slightly across the origin, the optimal decision can instantly jump from one extreme corner of the feasible set to another. These violent oscillations force the learner to make massive, erroneous adjustments, accumulating significant regret.
To break past this $\sqrt{T}$ barrier, we need a stabilizing force. That force is curvature. When either the loss functions or the boundaries of the decision set possess curvature, the optimal decision can no longer jump erratically. Instead, it drifts smoothly. This geometric stability allows algorithms to achieve logarithmic regret ($O(\log T)$), fundamentally changing the speed at which an online system can learn.
Curvature in the Loss Landscape
The most intuitive way to introduce curvature is through the objective function itself. A function is strongly convex if it is bounded from below by a quadratic bowl.
As Shai Shalev-Shwartz et al. demonstrate in Mind the Duality Gap: Logarithmic regret algorithms for online optimization, strong convexity acts as a cumulative resource that builds up over successive rounds. Every time the learner experiences a strongly convex loss, the overall objective becomes more "bowl-like," pinning the minimum more securely in place. Because this curvature accumulates linearly with time, the optimal learning rate should not scale with $1/\sqrt{t}$ (as it does in general convex optimization), but should instead decrease aggressively as $1/t$.
This $1/t$ learning rate schedule leverages the growing curvature to rapidly shrink the step size, compressing the cumulative regret down to an optimal $O(\log T)$ bound. In their foundational framework, Elad Hazan et al. show in Logarithmic regret algorithms for online convex optimization that this acceleration extends beyond strong convexity to a broader class of functions known as exp-concave functions (such as log-loss scenarios), where the exponential of the negative loss is concave.
The transition from $O(\sqrt{T})$ to $O(\log T)$ is not just a minor mathematical detail; it represents a qualitative shift in performance. In a minimax duality framework, Jacob Abernethy et al. in A Stochastic View of Optimal Regret through Minimax Duality show that this transition is entirely dictated by how the intrinsic curvature of the loss space prevents the worst-case adversarial environment from forcing large errors.
Curvature in the Decision Space
Remarkably, curvature does not have to come from the loss functions at all. A series of insights has revealed that the geometry of the constraint set can substitute for the curvature of the loss.
Consider an online linear prediction task where the loss functions are completely flat (linear), but the decision set is a smooth, curved ball (such as an $\ell_p$-ball for $p > 2$). As Ruitong Huang in Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities demonstrates, a curved boundary in the decision space functions mathematically as a substitute for curvature in the loss function itself. When the boundary is smooth and curved, a small shift in the cumulative loss vector cannot cause the optimal decision to jump wildly across the domain; the geometry forces the optimal point to slide incrementally along the boundary. Consequently, even a simple greedy strategy like Follow-the-Leader can achieve logarithmic regret without any explicit regularization.
This phenomenon is formalized by Alexandre d'Aspremont et al. in Projection-Free Optimization on Uniformly Convex Sets, who show that the uniform convexity of the decision set acts as an implicit regularizer. The degree of curvature in the constraint set dictates a continuous spectrum of regret bounds, smoothly transitioning from logarithmic to sublinear based entirely on the set's geometric properties.
The Downstream Benefits of Stability
When an algorithm exploits curvature—whether from the loss or the constraint set—the resulting stability yields massive dividends across more complex, constrained, or resource-limited online settings.
Long-Term and Hard Constraints
In many real-world applications, a learner must minimize regret while satisfying a set of constraints over time. When the objective functions are strongly convex, this curvature can be leveraged to simultaneously tighten both regret and constraint violations. Xinlei Yi et al. in Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints show that strong convexity allows both cumulative regret and total constraint violations to drop from polynomial growth rates to logarithmic rates. For systems facing hard constraints that cannot be violated on average, Hengquan Guo et al. in Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond demonstrate that strongly convex losses enable the system to maintain a constant ($O(1)$) hard constraint violation while still securing logarithmic regret.
Switching Budgets and Lazy Learning
In scenarios where changing a decision incurs a physical or computational cost, a learner operates under a "switching budget." Curvature dramatically mitigates the penalty of staying put. Uri Sherman et al. in Lazy OCO: Online Convex Optimization on a Switching Budget establish that strongly convex loss functions yield a quadratic improvement in the regret-to-switching-budget ratio. Because the high curvature prevents the optimal decision from drifting rapidly, a "lazy" algorithm that updates its decisions infrequently suffers a much smaller performance penalty than it would in a flat landscape.
Projection-Free Optimization
For high-dimensional problems, projecting a point back onto a complex feasible set at every step is computationally prohibitive. The Frank-Wolfe algorithm avoids projections by using linear updates, but it historically suffered from slow convergence. Ben Kretzu et al. in Revisiting Projection-free Online Learning: the Strongly Convex Case proved that strong convexity stabilizes the drift of loss functions over time in the online setting, boosting the projection-free regret bound from $O(T^{3/4})$ to $O(T^{2/3})$ in both full-information and bandit environments.
Ultimately, curvature changes the fundamental nature of online learning. By transforming volatile, erratic landscapes into stable, predictable environments, curvature allows simple first-order updates to act with the precision of second-order methods, unlocking the coveted logarithmic regret bound across a vast array of applications.
Key Foundational Work
Mind the Duality Gap: Logarithmic regret algorithms for online optimization (2008) — contributed 4 concept elements to this direction.
Logarithmic regret algorithms for online convex optimization (2007) — contributed 3 concept elements to this direction.