Dynamic Regret Reduces to Kernelized Static Regret

Andrew Jacobsen, Alessandro Rudi, Francesco Orabona, Nicolò Cesa-Bianchi · 2025

Read Dynamic Regret Reduces to Kernelized Static Regret by Andrew Jacobsen, Alessandro Rudi, Francesco Orabona, Nicolò Cesa-Bianchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05478.txt.

Introduction

Andrew Jacobsen, Alessandro Rudi, Francesco Orabona, and Nicolò Cesa-Bianchi recast a learning problem in a 2025 paper. In online learning, dynamic regret scores a learner against a moving target path. Static regret scores it against one fixed rival, which is simpler to handle.

The team show a moving path can be seen as one fixed function of time. Placed in a rich function space, the dynamic task turns into a static one. That swap restores a known best rate for straight losses and adds fresh scale-free bounds. It also works for loss types past methods barred. Though the space is endless, the math stays workable in practice.

Catalog record

CREATORAndrew Jacobsen, Alessandro Rudi, Francesco Orabona, Nicolò Cesa-Bianchi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05478

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Regret Reduces to Kernelized Static Regret Andrew Jacobsen, Alessandro Rudi, Francesco Orabona, Nicolò Cesa-Bianchi Abstract We study dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence. By observing that competing with an arbitrary sequence of comparators u 1 , … , u T u_{1},\ldots,u_{T} in 𝒲 ⊆ ℝ d \mathcal{W}\subseteq\mathbb{R}^{d} is equivalent to competing with a fixed comparator function u : [ 1 , T ] → 𝒲 u:[1,T]\to\mathcal{W} , we frame dynamic regret minimization as a static regret problem in a function space . By carefully constructing a suitable function space in the form of a Reproducing Kernel Hilbert Space (RKHS), our reduction enables us to recover the optimal R T ​ ( u 1 , … , u T ) = 𝒪 ⁡ ( ∑ t ‖ u t − u t − 1 ‖ ​ T ) R_{T}(u_{1},\ldots,u_{T})=\mathcal{O}(\sqrt{\sum_{t}\|u_{t}-u_{t-1}\|T}) dynamic regret guarantee in the setting of linear losses, and yields new scale-free and directionally-adaptive dynamic regret guarantees. Moreover, unlike prior dynamic-to-static reductions—which are valid only for linear losses—our reduction holds for any sequence of losses, allowing us to recover 𝒪 ⁡ ( ‖ u ‖ 2 + d eff ​ ( λ ) ​ ln ⁡ T ) \mathcal{O}\big(\|u\|^{2}+d_{\mathrm{eff}}(\lambda)\ln T\big) bounds in exp-concave and improper linear regression settings, where d eff ​ ( λ ) d_{\mathrm{eff}}(\lambda) is a measure of complexity of the RKHS. Despite working in an infinite-dimensional space, the resulting reduction leads to algorithms that are computable in practice, due to the reproducing property of RKHSs. 1 Introduction This paper introduces new techniques for Online Convex Optimization (OCO), a framework for designing and analyzing algorithms which learn on-the-fly from a stream of data ( Gordon 1999 ; Zinkevich 2003 ; Cesa-Bianchi and Lugosi 2006 ; Orabona 2019 ; Cesa-Bianchi and Orabona 2021 ) . Formally, consider T rounds of interaction between the learner and the environment. In each round, the learner chooses w_{t}\in\mathcal{W} from a convex set \mathcal{W}\subseteq\mathbb{R}^{d} , the environment reveals a convex loss function \ell_{t}:\mathcal{W}\to\mathbb{R} , and the learner incurs a loss of \ell_{t}(w_{t}) . The classic objective in this setting is to minimize the learner’s regret relative to any fixed benchmark u\in\mathcal{W} : \Regret(u):=\textstyle\sum_{t=1}^{T}(\ell_{t}(w_{t})-\ell_{t}(u))~. In this paper, we study the more general problem of minimizing the learner’s regret relative to any sequence of benchmarks u_{1},\dots,u_{T}\in\mathcal{W} ( Herbster and Warmuth 1998 ; Herbster and Warmuth 2001 ; Zinkevich 2003 ) : \DRegret(u_{1},\dots,u_{T}):=\textstyle\sum_{t=1}^{T}(\ell_{t}(w_{t})-\ell_{t}(u_{t}))~. This objective is typically referred to as dynamic regret, to distinguish it from the special case where the comparator sequence is fixed u_{1}=\dots=u_{T} (referred to as static regret). Intuitively, dynamic regret captures a notion of non-stationarity in learning problems. Problem instances where u_{1}=\cdots=u_{T} model classic problem settings, wherein there is a fixed “solution” whose performance we want to emulate, while a time-varying comparator sequence models problem settings where the learner needs to continuously adapt to a changing environment in which the best solution is time-varying and must be tracked over time. The complexity of a given comparator sequence is typically characterized by its path-length : \displaystyle P_{T}=\textstyle\sum_{t=2}^{T}\left\|u_{t}-u_{t-1}\right\|~. Clearly, if the path-length is large there is no hope to obtain low dynamic regret. The goal is thus to obtain performance guarantees that gracefully adapt to the level of non-stationarity. For instance, in the setting of G -Lipschitz losses the minimax optimal dynamic regret guarantee is of the order of \mathcal{O}(\sqrt{(1+P_{T})T}) , which scales naturally with the complexity of the benchmark sequence and recovers the optimal \mathcal{O}(\sqrt{T}) static regret guarantee when the comparator is fixed. t u_{t} 1 2 3 4 5 6 Transform t u(t) 1 2 3 4 5 6 Figure 1: Transformation from a sequence of comparators to a function. Many functions may implement the transformation. In Proposition 1 we will see that under mild assumptions on the chosen function space \mathcal{H} we can always find a function u\in\mathcal{H} such that u(t)=u_{t} for all t and \left\|u\right\|_{\mathcal{H}^{d}}^{2}=O\big(\sum_{t=2}^{T}\left\|u_{t}-u_{t-1}\right\|\big) . Contributions. In this work we introduce a new framework for reducing dynamic regret minimization to static regret minimization. Our key insight is that competing with a sequence u_{1},\ldots,u_{T} in \mathcal{W} can be equivalently framed as competing with some fixed function u(\cdot) such that u(t)=u_{t} for all t . In this view, we effectively transform dynamic regret minimization over a domain \mathcal{W}\subseteq\mathbb{R}^{d} into a static regret minimization problem over a domain of functions , depicted graphically in Figure 1 . The choice of the function space is crucial, as it controls the trade-offs of the resulting algorithm. To complete the construction, we carefully design a rich family of function spaces which embed the comparator sequence in a way that (1) optimizes the inherent trade-offs of the function class to achieve optimal dynamic regret guarantees and (2) ensures that the resulting algorithm is computable in practice, despite being stated as an infinite-dimensional optimization problem. Indeed, the family we design is an instance of a Reproducing Kernel Hilbert Space (RKHS), a well-studied class of functions endowed with the familiar structure of a Hilbert space. The reduction to learning in an RKHS is particularly natural in the context of online learning—the vast majority of modern online learning theory is developed for static regret minimization in Hilbert spaces , so our reduction enables the use of the familiar online learning toolkit while also allowing us to draw upon deep connections between dynamic regret minimization, kernel methods, and signal processing theory. In the linear losses setting, our construction enables us to achieve the optimal dynamic regret guarantees of \mathcal{O}(\sqrt{P_{T}T}) up to poly-logarithmic terms. Notably, the resulting algorithm is naturally horizon independent , and is easily extended to a scale-free version. These are the first algorithms that obtain the optimal \sqrt{P_{T}} dependence without prior knowledge of the horizon T natively, without resorting to the doubling trick. Our reduction also enables us to derive new directionally-adaptive guarantees, which scale as \widetilde{\mathcal{O}}\Big(\sqrt{d_{\mathrm{eff}}(\lambda)\big(\left\|u\right\|^{2}_{\mathcal{H}^{d}}+\sum_{t=1}^{T}\left\langle g_{t},u_{t}\right\rangle^{2}\big)}\Big) , where \left\|u\right\|^{2}_{\mathcal{H}} and d_{\mathrm{eff}}(\lambda) are measures of the complexity of the comparator function and complexity of the function class \mathcal{H} respectively. Interestingly, because our reduction only involves viewing the comparator sequence through a different lens, it holds for any sequence of loss functions, contrasting prior works which are valid only for linear losses ( Zhang et al. 2024 ; Jacobsen and Orabona 2024 ) . We show that this allows us to account for loss curvature and obtain \mathcal{O}(\lambda\left\|u\right\|_{\mathcal{H}}^{2}+d_{\mathrm{eff}}(\lambda)\log T) dynamic regret in the context of exp-concave losses and improper linear regression settings. Related Works. Our work is most directly related to a recent thread of research in the linear loss setting initiated by Zhang et al. 2024 . Their strategy approaches dynamic regret from a signal processing perspective, wherein the comparator sequence is stacked into a high-dimensional “signal” \widetilde{u}=\mathrm{vec}\left(u_{1},\ldots,u_{T}\right)\in\mathbb{R}^{dT} , and 1 -dimensional static regret algorithms are employed to learn the coefficients of a basis of features which decompose that signal, leading to \mathcal{O}(\sqrt{P_{T}T}) dynamic regret via a carefully chosen dictionary of features. Jacobsen and Orabona 2024 generalize this perspective by designing static regret algorithms that are applied directly in this high-dimensional space, and derive the \mathcal{O}(\sqrt{P_{T}T}) bound by choosing a suitable dual-norm pair in this space, such that \left\|\widetilde{u}\right\|=\mathcal{O}(\sqrt{P_{T}}) . Our work further

Read the complete text