Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This work resolves the long-standing theoretical relationship between interval regret and dynamic regret in non-stationary online convex optimization. Disproving the common conjecture that local optimality naturally guarantees global tracking, the authors construct counterexamples showing that optimal interval regret does not imply optimal dynamic regret for convex, strongly convex, or exp-concave functions. To reconcile this divergence, they design a surrogate-loss reduction over an enlarged Euclidean domain that successfully converts interval regret minimizers into optimal dynamic regret algorithms, yielding the first proper, computationally efficient optimal dynamic regret method for exp-concave functions.
Locally optimal online algorithms can completely fail to track changing environments, disproving a foundational conjecture in non-stationary learning while uncovering a geometric surrogate reduction that recovers optimal dynamic regret.
Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.