aiqbench analysis
This research introduces the first online learning algorithm that achieves interval regret bounds scaling with gradient variation, offering a robust solution for non-stationary environments where function landscapes shift over time. By employing a two-layer ensemble structure and a novel Lipschitz-adaptive meta algorithm, the method simultaneously adapts to problem-specific dynamics while maintaining minimax-optimal performance in worst-case scenarios. The approach also provides independent theoretical value through its automatic adaptation to unknown Lipschitz and smoothness constants, bridging gaps between stochastic optimization and adversarial settings.
Online Learning with Gradient-Variation Interval Regret
arXiv:2606.03831v1 Announce Type: new Abstract: This paper investigates non-stationary online learning using the metric of interval regret, which requires an online algorithm to perform well over every time interval. We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation, a fundamental measure of the cumulative change in online function gradients, which relates to various problem-dependent quantities and is closely connected to stochastic optimization and other problems. Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees. Specifically, it enjoys a regret bound that simultaneously adapts to various problem-dependent quantities while also preserving the minimax-optimal rate in the worst case. Moreover, recognizing the challenge of hyperparameter tuning, we introduce a Lipschitz- and smoothness-agnostic variant that automatically adapts to these potentially unknown constants. This is primarily enabled by a novel Lipschitz-adaptive meta algorithm, which may be of independent interest. Beyond interval regret, our method also yields broader implications: it provides versatile bounds for interval dynamic regret, a stronger measure that competes with changing comparators over any interval, and yields the first piecewise characterization for stochastic extended adversarial optimization. Theoretical findings are validated by experiments.
Abstract:This paper investigates non-stationary online learning using the metric of interval regret, which requires an online algorithm to perform well over every time interval. We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation, a fundamental measure of the cumulative change in online function gradients, which relates to various problem-dependent quantities and is closely connected to stochastic optimization and other problems. Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees. Specifically, it enjoys a regret bound that simultaneously adapts to various problem-dependent quantities while also preserving the minimax-optimal rate in the worst case. Moreover, recognizing the challenge of hyperparameter tuning, we introduce a Lipschitz- and smoothness-agnostic variant that automatically adapts to these potentially unknown constants. This is primarily enabled by a novel Lipschitz-adaptive meta algorithm, which may be of independent interest. Beyond interval regret, our method also yields broader implications: it provides versatile bounds for interval dynamic regret, a stronger measure that competes with changing comparators over any interval, and yields the first piecewise characterization for stochastic extended adversarial optimization. Theoretical findings are validated by experiments.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2606.03831 [cs.LG]
(or arXiv:2606.03831v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.03831 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 287 words
Related coverage
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
arXiv · Sep 9, 2026
Gradient-Variation Regret Bounds for Unconstrained Online Learning
arXiv · Jul 28, 2026
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
arXiv · Jun 15, 2026
Online Learning of Scale Parameters in Score-Driven Filters
arXiv · Aug 20, 2026