Unconstrained Dynamic Regret via Sparse Coding
Authors: Zhiyu Zhang
Ashok Cutkosky
Ioannis Paschalidis
Venue: NeurIPS 2023 poster (2023)
Keywords: Dynamic online learning
parameter-free online learning
time series forecasting
wavelet
TL;DR: We propose a general framework achieving a new type of dynamic regret bounds on unconstrained domains.

Abstract: Motivated by the challenge of nonstationarity in sequential decision making, we study Online Convex Optimization (OCO) under the coupling of two problem structures: the domain is unbounded, and the comparator sequence $u_1,\ldots,u_T$ is arbitrarily time-varying. As no algorithm can guarantee low regret simultaneously against all comparator sequences, handling this setting requires moving from minimax optimality to comparator adaptivity. That is, sensible regret bounds should depend on certain complexity measures of the comparator relative to one's prior knowledge. This paper achieves a new type of such adaptive regret bounds leveraging a sparse coding framework. The complexity of the comparator is measured by its energy and its sparsity on a user-specified dictionary, which offers considerable versatility. For example, equipped with a wavelet dictionary, our framework improves the state-of-the-art bound (Jacobsen & Cutkosky, 2022) by adapting to both ($i$) the magnitude of the comparator average $||\bar u||=||\sum_{t=1}^Tu_t/T||$, rather than the maximum $\max_t||u_t||$; and ($ii$) the comparator variability $\sum_{t=1}^T||u_t-\bar u||$, rather than the uncentered sum $\sum_{t=1}^T||u_t||$. Furthermore, our proof is simpler due to decoupling function approximation from regret minimization.

Unconstrained Dynamic Regret via Sparse Coding
Zhiyu Zhang" Harvard University zhiyuz@seas. harvard.edu
Ashok Cutkosky Boston University ashok@cutkossky.com
Ioannis Ch. Paschalidis Boston University yannisp@bu.c eed edu
Abstract
Motivated by the challenge of nonstationarity in sequential decision making, we study Online Convex Optimization (OCO) under the coupling two problem structures: the domain is unbounded, and the comparator sequence u1..... Wy is arbitrarily time-varying. As no algorithm can guarantee low regret simultaneously against all comparator sequences, handling this setting requires moving from minimax optimality to comparator adaptivity. That is, sensible regret bounds should depend on certain complexity measures of the comparator relative to one's prior knowledge. This paper achieves a new type of such adaptive regret bounds leveraging sparse coding framework. The complexity of the comparator is measured by its energy and its sparsity on a user-specified dictionary, which offers considerable versatility. For example, equipped with wavelet dictionary, our framework improves the state-of-the-at bound [JC22] by adapting to both (i) the magnitude of the comparator average || = | "t/T|l. rather than the maximum max, ||ue]l: and (ii) the comparator variability Σ ||u, - ūll. rather than the uncentered sum E/= ||ull Furthermore, our analysis is simpler due to decoupling function approximation from regret minimization.
Introduction
Nonstationarity is prevalent in sequential decision making, which poses critical challenge to the vast majority of existing approaches developed offline. Consider weather forecasting for example [SBG+211 A meteorologist typically starts from the governing physical equations and simulates them online using high performance computing; the imperfection of this physical model can lead to time-varying patterns in its forecasting error. Alternatively, machine learning scientist may build data-driven model from historical weather datasets, but its online deployment is subject to distribution shifts. If the structure of such nonstationarity can be exploited in our algorithm, then we may expect better forecasting performance. This paper investigates the problem from a theoretical angle we aim improve nonstationary online decision making by incorporating temporal representations.
Concretely, we study Online Convex Optimization (OCO), which is a repeated game between us (the player) and an adversarial environment E. In each (the t-th) round, with mutually known Lipschitz constant G:
1. We make prediction E d based on the observations before the f-th round. The environment & reveals a convex loss function 4 : Rd R dependent on our prediction history æı,..., Zz; I is G-Lipschitz with respect to ||-
3. We suffer the loss 1,(x)))
The game ends after T rounds, and then, our total loss is compared that of alternative sequence of predictions U , ur E Rdd Without knowing the time horizon T,, the environment & and the
Work done at Boston University. Future versions available at https::
13349.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

comparator sequence fui our goal is to achieve low unconstrained dynamic regret
T
Regrety (Un:)) = sup Σ ((x))
44(u)
(I)
Fixing any comparator (4) hez: if such an expression can be upper-bounded by a sublinear function of T, then asymplotically, in any environment, we perform at least as well as the {ur hez sequence.
The above setting deviates from the most standard setting of OCO [Haz16, Ora19] two ways.
Structure 1.
The domain Id unbounded.
Structure 2. The comparator is allowed to be time-varying.
While the latter has been studied extensively in the literature (since [Zin03]) to account for nonstation- arity, most existing approaches require time-invarian bounded domain to set the hyperparameters properly, which, to some extent, limits the amount of nonstationarity they can handle. One might argue that most practical problems have finite range, which could be heuristically estimated from offline datasets. However, such heuristic is not robust in nature, as underestimates will invalidate the theoretical analysis, and overestimates will make the regret bound excessively conservative. It thus important study the more challenging unconstrained dynamic setting" combining the two problem structures, where algorithms cannot rely on pre-selected range estimates at all.
Taking closer look at their analysis, it is perhaps a little surprising that these problem structures share a common theme, despite being studied mostly separately. In either the unconstrained static setting [MO14, OP16, CO18] or the bounded dynamic setting [Zin03, HW 15 ZLZ18], the standard form of minimax optimality [ABRTO8, AABRO9, RS14b] becomes vacuous, as it is impossible to guarantee that sup Regrety (u1:T) is sublinear in T. Cireumventing this issue relies on comparator adaptivity" instead of only depending on T, any appropriate regret upper bound, denoted by Boundy measure. Intuitively, despite the intractability of hard comparators, nonvacuous bounds can be established against "easy ones", A total loss bound then follows from the oracle inequality
should also depend on the comparator V1.7 through a certain complexity
T E4(u)) Boundy (u::))
Σ inf WErT
(2)
A crucial observation is that the complexity of 41.T is not uniquely defined: one could imagine bounding Regretr(ui:r) by many different non-comparable functions of u1.T. Essentially, this complexity measure serves Bayesian prior:* choosing it amounts assigning different priorities to different comparators W1.7 E Rdxx", The associated algorithm guarantees lower Boundr (uirr) against comparators with higher priority, and due (2), the total loss of our algorithm is low some of these high priority comparators actually achieve low loss ΣT= (u,)) Such a Bayesian reasoning highlights the importance of versatility in this workflow: in order to place arbitrary
application-dependerr prior, we need a versatile algorithmic framework that adapts to a wide range of complexity measures. This leads to the limitations of existing results, discussed next.
To our knowledge, [JC22] the only existing work that considers our setting. Two unconstrained dynamic regret bounds are presented based on three statistics of the comparator sequence. the
maximum range M := max; ||ue||2. the norm sum S : >T ||ull|2 and the path length P := Ef || wellg- First, using 1D unconstrained static algorithm as simple range scaler, the paper achieves [JC22, Lemma 10]
Regrety(un:r) Ô 6
PIt is known that unconstrained OCO algorithms can also handle time-varying (but not necessarily bounded) domains in black-bor, manner [Cut20, Section 4).
In general, adaptivity means achieving near minimax optimality simultaneously for many restricted sub- classes of the problem, where minimax optimality is well-defined [Joh19, Chapter 6).
'The prior can be selected on the fly, depending on the observation history. This brings key practical benefits: Appendix E discusses how an empirical forecaster based on domain knowledge or deep learning could be "robustified" using framework.

---

Table 1: Comparison almost static environments. Each row improves the previous row (omitting logarithmic factors), c.f., Appendix A.
Algorithm
P-dependent bound
K-switching regret
Example
Example
ADER (ZLZ18] (metu-expert OGD)
(VIDD P)DT)
Ö (DV(1 K)T)
N/ O(T) Ö(TR/4)
Ó Ófii/1y ÖcTa//4)
[JC22, Algorithm (range scaling)
Ó ((MM 1MM-PMM
MM KY
[IC22, Algorithm 2] (centered MD)
Ô (VM PIS
V(I+ K)MS)
Ours (Haar OLR)
δ [|lll2 vT VPS
δ [|all2 vT + VKE
O(VT)
Ö(VT)
Then, by developing a customized mirror descent approach, most of the effort is devoted to improving MT to S [JC22, Theorem 4], i.e., adapting to the magnitude of individual u4-
( S Ô (V(M+ (MM+P%) P))).
Despite the strengths of these results and their nontrivial analysis, a shared limitation is that both bounds depend explicitly on the path length P. Intuitively, it means that good performance is only guaranteed in almost static environments: in the typical situation of = @ these bounds are only sublinear when P o(T), which rules out important persistent dynamics such as periodicity. Moreover, even the second bound still depends on MS instead of finer characterization of each individual u 's magnitude. That is, the mission of removing M is not fully accomplished yet.²
The goal of this paper is to extend comparator adaptivity a wider range of complexity measures. For almost static environments in particular, quantitative benefits will be obtained from specific instances of this general approach.
1.1 Contribution
The contributions of this paper are twofold.
1. First, we present an algorithmic framework achieving new type of unconstrained dynamic regret bounds. It is based on a conversion to vector-output Online Linear Regression (OLR): given dictionary H of orthogonal feature vectors spanning the sequence space pdT we use an unconstrained static OCO algorithm to linearly aggregate these feature vectors, which are themselves time-varying prediction sequences. Such procedure guarantees
Regrety (ui.T) S Ô (VE Sparsity
(5)
where E ET= 1 is the energy of the comparator W1.7, and Sparsity measures the sparsity of u1:T on the dictionary H. Both E and Sparsity n are unknown beforehand. Compared to [JC22], the main advantage of this framework is its versatility. Prior knowledge on the transform domain can be incorporated by picking H. and favorable algorithmic properties can be conveniently inherited from static online learning.
2.
Our second contribution is quantitative: although [JC22] is specifically crafted to handle almost static environments, we show that equipped with a Haar waveler dictionary, our framework actually guarantees better bounds (Table 1) in this setting, which is a surprising finding us.
With the comparator average ū := Σin ue/T and the first order variability Š == ΣL [ - جوااة our Haar wavelet algorithm guarantees
Regret,(u1:r) S Ö (lllll VT VPS)
'The significance of this issue could be seen through an analogy to (static D-bounded domain) gradient adaptive OCO: although there are algorithms achicving the already adaptive (DVGE llaellz static
regret bound, the hallmark of gradient adaptivity is the so-called "second-orde" bound" O EV Ei ||s.1
popularized by ADAGRAD [DHS11]. In a rough but related sense, we aim to achieve "second order comparator adaptivity", which is only manifested in the less studied dynamic regret setting.
'For conciseness, we omit uir in the notation. Throughout this paper, the regularity parameters on the RHS of the regret bound generally depend on ur.. A list of these parameters is presented in Appendix A, including their relations.
3

---

It improves (4) by (i) a better dependence on the comparator magnitude (VMS + | vT); and (ii) decoupling the bias ū from the characterization of variability ( (vPS
VPS).
With the number of switches = Ei lutt1 # us] and the second order variability E == Et | u1/22 the same Haar wavelet algorithm guarantees unconstrained switching
regret bound
VT (egrety((11)) - Ô (1lll V VT VVE).
which improves the existing Ô ( bound resulting from Eq.(4) and P O(KM).
Due to the local property of wavelets, our algorithm runs in Old time per round, matching that of the baselines. As for the regret, our bounds are never worse than the baselines, and in two examples corresponding to ||ūl| < . and < S. they reduce to clearly improved rates in T. Furthermore, our analysis follows from the generic regret bound (5) and the wavelet appreximation theory, providing an intriguing connection between disparate fields.
The paper concludes with an application in fine-tuning time series forecasters, where unconstrained dynamic OCO is naturally motivated. Due to limited space, this is deferred to Appendix E, with experiments that support our theoretical results.
1.2 Related work
Our paper addresses the connection between unconstrained OCO and dynamic OCO. Although they both embody the idea of comparator adaptivity, unified studies have been scarce.
Unconstrained OCO To obtain static regret bounds in OCO, Online Gradient Descent (OGD) [Zin03] is often the default approach. With learning rate 7). guarantees O || + v/T') regret with respect any unconstrained static comparator u E IRd, and the optimal choice in hindsight 77 = O[]ull /vT). Without the oracle knowledge of ||u||2. is impossible tune 7) optimally, To address this issue, a series of works (also called parameter-free online learning) [SM12, MA13 13, GY14, MO14, OP16, FKMS17, CO18, FRS18, MK20, CLW21, ZCP22] developed vastly different strategies to achieve the oracle optimal rate O(I vT) up to logarithmic factors. That is, the algorithm performs as if the complexity measure ||u|] is known beforehand.
There is certain flexibility in the choice of the norm ||-||: L, and L2 norm bounds were presented in [SM12], while Banach norm bounds were developed by [FRS18, CO18]. Historically, the connection between the L, norm and sparsity has powered breakthroughs in batch data science, including LASSO [Tib96] and compressed sensing [CRT06). However, the parallel path in online learning remains less studied: while the sparsity implication of the T, norm adaptive bounds has been discussed in the literature [SM12, G, vdH19), there is in general a lack of downstream investigations with conerete benefits. In this paper, we show that the sparsity of the comparator can be naturally associated to the structural simplicity of nonstationary environment.
Dynamic OCO Comparing against dynamic sequences is a classical research topic. It is clear that one cannot go beyond linear regret in the worst case, therefore various notions of complexity should be introduced.
The closest topic to ours is the universal dynamic regret, where the regret bound adapts to the complexity of an arbitrary W1.r on bounded domain with T.g-diameter D. In the most common framework, the complexity measure is an T.p_ norm of the difference sequence (wtạ1 wr), such as the Lp,1 norm, i.e., the path length P = ET= ||u44 uu [HW01].? Omitting the depen- dence on the dimension d (thus also the choice of p), the optimal bound under convex Lipschitz losses is Ô [V(++ + P)DT) [Zin03, HW JRSS15, GS16, ZLZ18], while the accelerated rate* 0(p2/3T11331) v1) can be achieved with strong convexity [BW21, BW22]. Improvements have been
ET- [uee 1 (uelg) 1/4 with g > is associated to more homogeneous measures of comparator smoothness [BW19, BW21]. Further omitting the dependence the diameter D.
7 "Motivated by nonparametric statistics, the Lp.g norm

---

studied under the additional smoothness assumption |ZZZZ20, ZZZZ21]. These bounds subsume results in switching (a.k.a,, shifting) regret, where the complexity of u1 measured by number of switches K, as P is dominated by DK.
A notable exception is the dynamic model framework from [HW15, ZLZI8]. Still considering a bounded domain, it takes a collection of dynamic models as input, which are mappings from the domain itself. Then, the complexity of comparator u1.r is measured by how well it can be reconstructed by the best dynamic model in hindsight. Essentially, the use of temporal representations is somewhat similar to the dictionary in framework. The important difference is that instead of using the best feature (or the best convex combination of the features) to measure the comparator, use linear combinations of the features this allows handling unconstrained domains through subspace modeling.
Besides the universal dynamic regret, there are other notions of dynamic regret that do not induce oracle inequalities like (2),2), including (i) the restricted dynamic regret [Y7JY16, ZYY+17, BW19, BW20 B7W21], which depends on the complexity of certain offline optimal comparators," and (ii) regret bounds that depend on the functional variation Σi= max (x)) - 4++1 (z) [BGZ15, CWW19). They are not as relevant to our purpose, due to being vacuous on unbounded domains under the linear losses this is important setting in our investigation.
Unconstrained (universal) dynamic regret To our knowledge, [JC22] is the only work studying the universal dynamic regret without bounded domain, whose contributions have been summarized in our Introduction. Here we survey some negative results in the literature.
The restricted dynamic regret is a special case of the universal dynamic regret, therefore lower bounds for the former apply to the latter as well. For convex Lipschitz losses [YZJY16] and strongly convex losses [B [9], any algorithm should suffer the dynamic regret of S?(P) and S2(P2). respectively.
For dynamic OCO on bounded domains, recurring analysis goes through the notion of strong adaptivity [DGSS15]: one first achieves low static regret bounds every subinterval of the time horizon [: T). and then assembles these local bounds appropriately to bound the global dynamic regret [ZYZ+ 18, Cur20, BW21, BW22]. Following this route in the unconstrained setting appears to be challenging, as [JC22, Section 4] showed that (a natural form of) strong adaptivity cannot be achieved there.
Additional discussions of related works are deferred to Appendix B, including the more general problem of online nonparametric regression, the more specific problem of parametric time series forecasting, and other orthogonal uses of sparsity in online learning.
1.3 Notation
For two integers a S b, [a 6] is the set of all integers such that S c b. The brackets removed when on the subscript, denoting a tuple with indices in [a b]. Treating all vectors as column vectors, gpan(A) represents the column space of matrix A. log is natural logarithm when the base omitted, and log, (.) ;= 0 V log(.). polylog denotes a poly-logarithme function of its input. represents a zero vector whose dimension depends on the context.
2 The general sparse coding framework
This section presents our sparse coding framework. achieving the generic sparsity adaptive regret bound E5). The key idea is to view online learning on the sequence space Ref rather than the default domain Rdd Despite central role in signal processing (e.g., the Fourier transform), such a view is (in our opinion) under-explored by the online learning community." 10
Notably, [BW19, BW20J creatively employed wavelet techniques detect change-pone -pintts of the environment, which, to the best of our knowledge. is the only existing use of wavelets the online learning literature. Possibly due to the emphasis on the static regret: the sequence uir collapses into time invariant which contained in ddd
5

---

2.1 Setting
To begin with, we follow the conventions in online learning [Haz16, Ora19] linearize convex losses. Consider that instead of the full loss function 4, we only observe its subgradient 9r E 34, (24) at our prediction 24. By using the linear loss (g..) -) as a surrogate, we can still upper bound the regret (1. due to 4 (x+) (m) S (gt, - u). The linear loss problem is also called Online Linear Optimization (OLO), where each observation St is d dimensional vector satisfying |19: S G.
Now, consider the length 7' sequences of predictions T1:T, gradients 91.7 and comparators 11:7- Let us flatten everything and treat them as d'I' dimensional vectors, concatenating per-round quantities in Rd These are called signals. The comparator statistics could be more succinctly represented using vector notations, e.g., the energy F- = Σi= ||u. l12 = =1111=112
Our framework requires a dictionary matrix H E _RT'',, possibly revealed online, whose columns are N nonzero feature vectors. We write H in an equivalent block form as (: N, where each block Ne,, Rdx1 The accompanied linear transform coefficient vector û E TR-N (if it exists). Adopting the convention in signal processing, we will call RdT the time domain, and R the transform domain. In general, symbols without hat refer to time domain quantities, while their transform domain counterparts are denoted with hat.
Hú relates signal E IRd2 to
Summarizing the above, we consider the following concise interaction protocol." Despite its parametric appearance, our main focus is the nonparametric regime, where the dictionary size N scales with the amount of data T.
Vector-output OLR with linear losses In the t-th round, our algorithm observes a d-by-N feature matrix He := [he.n] IiggN linearly combines its columns into a prediction He E RRd receives a loss gradient 9r Rd, and then suffers the linear loss (gt, 21). We assume that || S
E/= | 1| 2 1 and llæel2 I G. The performance metric is the unconstrained dynamic regret defined in (1)
2.2 Main result
In a nutshell, our strategy is to apply an unconstrained static OLO algorithm on the transform domain, and in a coordinate-we wise fashion. This is remarkably simple, but also contains few twists. To make it concrete, let us start with a single feature vector.
Size 1 dictionary Consider index E [L N]. which is associated to the feature HITT [ lt] E RdT We suppress the index n and write it as hIT = /hi,...,,r7) For any comparator u1.7 E span(hirr), there exists E IR such that un.7 = hTTū. The cumulative loss of U1.T can be rewritten as
(gHT, u.r)) (g1.T, (u.T) â Σ (ge he) ú,
which is the loss of the coefficient Essentially, to compete with ID comparator subspace span(hi:)), it suffices run 1D static regret algorithm A that competes with e R. Such a procedure is presented as Algorithm 1.
ID OLO problem with surrogate loss gradients (gt, ht).
It still remains to choose the static algorithm A. Technically, all known static comparator adaptive algorithms can be applied. As an illustrative example, we adopt the FREEGRAD algorithm [MK20], which simultaneously achieves static comparator adaptivity and second order gradient adaptivity [DHS11]." Its pseudocode and static regret bound are presented Appendix C.1 for completeness.
In summary, our single feature learner (Algorithm 1) has the following simplified guarantee, with the full gradient adaptive version deferred to Appendix C.
"Despite also using features, the considered setting slightly differs from the standard notion of regression, the loss function here does not necessarily have a minimizer. use term OLR for cleaner exposition.
12he assumptions on the features are mild: an important special case is max; || 1, as in the Haar wavelet dictionary. We impose these assumptions apply unconstrained static algorithms verbatim.
13 gradient adaptive regret bound refines our definition (q. by depending on the actually encountered environment E as well. FREEGRAD enjoys another favorable property called scale-freenes, the predictions are invariant any positive scaling of the loss gradients and the Lipschitz constant G.

---

Algorithm Sparse coding with size I dictionary.
Require: An algorithm A for static ID unconstrained OLO with G-Lipschitz losses; and nonzero feature vector h1rr Rdd
1: for t 1,2..... do
2: Receive h, E Rd.
3: If h4 is nonzero, query A for its oulput, and assign it to 2g E R; otherwise, 2, is arbitrary.
4: Predict 2; 8yh, E RRd and receive the loss gradient 9r IR..
5: If h4 is nonzero, compute Ōt (gt, hy) and send it to A as its surrogate loss gradient.
6: end for
Lemma 2.1. Let > 0 be an arbitrary hyperparameter for FREEGRAD (Algorithm 3 in Ap-
pendix C.I). Applying its ID version as the static subroutine, for all T E 14 and u1.1 span(hr:r). Algorithm I guaranteey
(U)T) S eG + ||u1rll12 G polylog (max ||rll2 T,, TT.-
Note that the hyperparameter be arbitrarily small. Further neglecting poly-logarithmic factors, the bound is essentially Ö (G' ||urr l12)-
General dictionary Given the above single feature learner, us turn to the general setting with N features. We run N copies of Algorithm 1 in parallel, aggregate their predictions, and the regret bound sums Lemma 2.1, similar to [Cut19] in static setting. The pseudocode is presented as Algorithm 2, and the regret bound is Theorem 1.
Algorithm 2 Sparse coding with general dictionary.
Require: A dictionary H [.,, where h4,,, E R4; and hyperparameter & > O. For all n E [1 NJ. initialize copy of Algorithm as An It runs the ID version of Algorithm as a subroutine, with hyperparameter s/N.
2: for | ... do
3: Receive H4 = [henllguSN- For all n, send h to An, and query its prediction Wt.n-
4: Predict
>n Wk.n-
5: Receive loss gradient gr, and send it to A AN as loss gradients.
6: end for
Theorem Consider any collection of signals 2 E span(hi:Tm)) Vn. We define its reconstruction
error (for the comparator u1:T) as (0) u1.T - En 2(0) E R&T Then, for all T E NN and
W1.T E RRT Algorithm 2 guarantees
N
T
(uir) S SGG+C +G
Σ
-polylo
max k,m
T, T,,,
+ +G Σ
(0)
2
t=1
where (n) E TRd is the 1-th round component of the sequence (n) E RT
To interpret this very general result, let us consider a few concrete settings.
Static regret. If the size N d and the dictionary H4 Ia. then for any static comparator (u, E Rd), we can let 2(x)) be the projection of the sequence u1.r onto span(hi.r,.)) This leaves zero reconstruction error, i.e., U1.T EN ((a), Theorem reduces to
(Mgr)) S cG + ||w]] GVT polylog (I|u)l . T,d,e-1)
which recovers standard Ö([]w|], VT) bound coordinate unconstrained static OLO [Ora19, Section 9.3]. The gradient adaptive version yields a better Ö([[=]]z vT) bound, c.f., Appendix C.2. Orthogonal dictionary. Entering the dynamic realm, we now consider the situation where feature vectors are orthogonal (standard in signal processing), and the comparator unrr E span(H). Same the static setting, free define z(n) as the projection
hi.m
= (hi:T,n U1-T)
|
7

---

Due to orthogonality, the projection preserves the energy of the time domain signal, i.e, E ||ا = Σ || By further defining Sparsity == (Σ |=(")|| 112)
/E n= (n)
(arbitrary when the denominator is zero), Theorem 1 reduces to
(egrety(41.r) Ô (VF.
(VE.Sparsinn Sparsity
Note that as the squared L,/L2 ratio, Sparsity N is classical spansity measure [HR09] of the decomposed signals {=(*) Jingg:: if there are only No I N nonzero vectors within this collection, then Sparsity x S No due to the Cauchy-Schward inequality. Therefore, the generic sparsity adaptive bound (7) depends on (i) the energy of the comparator u1.T; and (ii) the sparsity of its representation, without knowing either condition beforehand. The easier the comparator (low energy, and sparse on H), the lower the bound becomes.
Overparameterization So far we have only considered N S d7, where feature vectors can be orthogonal. However, key idea in signal processing is to use redundant features (N >> d'T) to obtain sparser representations. Theorem implies a feature selection property in this context: since it applies to any decomposition of U1:7, as long as 11T can be represented by subset H of orthogonal features within H. the regret bound adapts to Sparsity ft. the sparsity of u1.7 measured on H. That is, we are theoretically justified to assemble smaller dictionaries into a larger one the regret bound adapts to the quality of the optimal (comparator-depedenn) sub-dictionary H.
How to choose the dictionary H? In practice, we may use prior knowledge on the dynamics of the environment. For example, if the environment is periodic, such the weather or the traffic, then a good choice could be the Fourier dictionary. Similarly, wavelet dictionaries are useful for piecewise regular environments. Another possibility is to learn the dictionary from offline datasets, which is also called representation learning- Overall, such prior knowledge is not required to be correct our algorithm can take any dictionary as input, and the regret bound naturally adapts its quality. The established connection between adaptivity and signal structures is key benefit of our framework.
Eats
Pedeer cantoree (mn 1at
Fite6, 0-5.66
10
Figure The power law.
Power law For a more specific discussion, let us consider an empirically justified setup. In signal processing, the study of sparsity has been partially motivated by the power law [Pri21]: under the standard Fourier or wavelet transforms, the n-th largest transform domain coefficient of many real signals can have magnitude roughly proportional to n- where (0.5, 1). We also observe this phenomenon from a weather dataset, with details presented in Appendix E. Figure plots the sorted Fourier coefficients of an actual temperature sequence, on a log-log scale. A fitted dashed line is shown in orange, with (negative) slope a = 0.68.
When the power law holds, our bound (7) has more interpretable form. Assuming d = 1 and N T
E -T
Sparsity F
Di',n n n-2a
In a typical setting of F (T), we obtain sublinear Ö(T1.5-0) dynamic regret bound.
3
The Haar OLR algorithm
This section presents the quantitative contributions of this paper: despite its generality, our sparse coding framework can improve existing results [JC22]. Our workhorse is the ability of wavelet bases to sparsely represent smooth signals.
3.1 Haar wavelet
Wavelet is fundamental topic in signal processing, with long lasting impact throughout modern data science. Roughly, the motivation that a signal can simultaneously exhibit nonstationarity at different time scales, such slow drifts and fast jumps, therefore to faithfully represent it, we should apply feature vectors with different resolutions. We will only use the simplest Haar wavelets, which already sufficient. Readers are referred to [Ma108, 19] for a thorough introduction to this topic.
8

---

Specifically, we start from the ID setting (d = 1) with a dyadic horizon (I 2nh for some m E N+). The Haar wavelet dictionary consists Tf (unnormalized) orthogonal feature vectors, indexed by scale parameter j E [1 logg 7 and a location parameter E [1 : 2- Given (j.1) pair, define
(1. feature h(il) [h] [h]) RT
Rd entry-wise as
1,
E [2 - (1- +1 (1 - - 2
1
Le (2 + 20-1 :21];
0, else.
means that ((.) is only nonzero on a length-2? interval, while changing its sign once in the middle of this interval. Collecting all the (i.1) pairs yield T features; then, we incorporate extra all-one feature h* = [I,...: , 1] to complete this size T dictionary.
The defined features can be assembled into the columns of a matrix Haarm To help with the intuition, Haar, with T = is presented in (8), The columns from the left to the right are h", ((2.1), (O.1) and (2.2), Observe that they are orthogonal, and the norm assumption from Section 2.1 is satisfied. Therefore, our sparsity adaptive regret bound Eq.(7) is applicable.
1
1
0
1
1
-1
0
Haarz
1
-1
0
1 -1
Given this ID Haar wavelet dictionary, we apply a minor variant of Algorithm 2 to prevent the dimension from appearing in the regret bound. When d 1, the algorithm exactly Algorithm where intuitions are most clearly demonstrated. Then, the doubling trick [SS11, Section 2.3.1] is adopted relax the knowledge of T. The pseudocode is presented Algorithm
Appendix
Computation An appealing property is that most Haar wavelet features are supported on short local intervals. Despite N T, there are only log2 T active features in each round. Therefore, the runtime of our algorithm (d log 7) per round, matching that all the baselines we compare to. This local property holds for compactly supported wavelets, most notably the Daubechies family [Dau88, CDV93J. The latter can represent more general, piecewise polynomial signals.
3.2
Main result
For almost static environments, our Haar OLR algorithm guarantees the following bounds, by relating comparator smoothness to the sparsity of its Haar wavelet representation. Different from [JC22] which only contains P-dependent bounds, avoid using P O(KM)." Interestingly, the proofs of the following two bounds are quite different: the first uses exact sparsity, while the second uses approximate sparsity.
also provide K-switching regret bound, in order to
Theorem 2 (Switching regret). For all T N+ and U1.r RdT, Algorithm 5 guarantees
Regretr(u::)) < 20 VT VT+VVE
(9)
Theorem (Path length bound). For all T N4 and unrr RaT Algorithm 5 guarantees
(ugret,((i:T) < Ô [|ū||2 VT VVS)
(10)
can be verified (Appendix A) that for all comparators U1.7, our bounds are at least as good as prior works (Table 1). The optimality is a more subtle issue, one should compare upper bound functions (of WI:T) to lower bound functions in a global manner, rather than comparing the exponents of T in minimax online learning.
Nonetheless, we present two examples of WI.T, where the improvement can be clearly seen through better exponents of T'. To give it a concrete background, suppose we want to sequentially predict ID time series ..,..., 2T R. This could be formulated OCO problem where the decision Ie there is our prediction of and the loss function is the absolute loss (xx) = Ix zel- A natural
Recall that one of our motivations is remove M from the existing bounds.

---

choice of the comparator is the ground truth sequence 21:7. and due to E2,(2), any upper bound on Regrety also upper-bounds the total forecasting loss our algorithm. Below we present specific ID comparator sequences u1T to demonstrate the strength of our results, which could be intuitively thought as the true time series 21.T in this more restricted discussion.
Example (Tracking outliers). Consider the situation where u1:T has a locally outlyigg scale: we set all the instantaneous comparators ue to 1, except k S VT consecutive members which are set to VT. Crucially, |ū| = O(1) and S = O(k-T), while M = vT and 5 @(T). With details deferred to Appendix D.7, both our bounds, i.e., Eq-(9) and (10), are Ö(VKT), while the fine baseline (4) is O(TS/A), and the coarse baseline (3.(3) is ÔTT). The largest gain is observed when k is constant, i.e., the comparator is subject a short but large perturbation.
Example (Persistent oscillation). Consider the situation where ü and all the instantaneous comparators oscillate around ú: Uh + ot/ VT.V.. a₁ or 11, and only switches sign for l times. Notice that S = .T,, while S (T)). All the baselines are Ô (VT + k2/221/4). while both our bounds are Ö(VT). The largest gain is observed when k T 1, i.e., the comparator switches in every round.
In summary, we show that existing bounds are suboptimal, while the optimality of our results remains to be studied. It highlights the importance of comparator energy and variability in the pursuit of better algorithms, which have not received enough attention in the literature. Next, we briefly sketch the proofs of these bounds.
Proof sketch The switching regret bound mostly follows from a very simple observation: if a sequence is constant throughout the support of Haar wavelet feature, then its transform domain coefficient for this feature zero. As features on the same scale j do not overlap, a K K-switching comparator can only induce K nonzero coefficients on the j-th scale. There are at most K log, T nonzero coefficients total, therefore Sparsity = Ö(K). The bound (9) is obtained by applying this argument after taking out the average of u1:7-
As for the path length bound, the idea is to consider the reconstructed sequences, using transform domain coefficients on a single scale j. These are usually called detail sequences in the wavelet literature [Ma108]. Each detail sequence has relatively simple structure, whose path length and variability can be associated to the magnitude of its transform domain coefficients. Moreover, as these detail sequences are certain "locally averaged" and "globally centered" versions of the actual comparator uir,, their regularities are dominated by the regularity of u1.7 itself. In combination, this yields relation between PS and the coefficients' I, norm, i.e., Σn (000 ||2 in Theorem 1, from which the bound established.
Compared to the analysis of [JC22], the key advantage of our analysis is the decoupling of function approximation from the generic sparsity-based regret bound. The former algorithm-indepeneen while the latter can be conveniently combined with advances in static online learning. With the help of approximation theory (c.g., Fourier features, wavelets, and possibly deep learning further down the line), intuitions are arguably clearer in this way, and solutions could be more precise (compared to analyses that "mix" " function approximation with regret minimization).
Additional discussion Finally, due to limited space, we defer additional discussion of our technical results to Appendix F, including
The related use of Mulri-Resollttion Analysis (MRA) in the existing online learning literature.
The comparison between Lipschitz and strongly convex losses in unconstrained dynamic OCO.
Conclusion
This paper presents a unified study of unconstrained and dynamic online learning, where the two problem structures are naturally connected via comparator adaptivity. Building on the synergy between static parameter-free algorithms and temporal representations, we develop an algorithmic framework achieving a generic sparsity-adaptive regret bound. Equipped with the wavelet dictionary, our framework improves the quantitative results from [JC22], by adapting to finer characterizations of the comparator sequence.
10

---

Acknowledgments and Disclosure of Funding
We thank Vivek Goyal for helpful pointers the signal processing literature, and the NeurIPS reviewers for their constructive feedback. This research was partially supported by the NSF under grants CCF-2200052, DMS-1664644, and I1S-1914792, by the ONR under grant N00014-19-1-255 by the DOE under grant ME-AC02-05CHI1233 by the NIH under grant UL54 TR004130, and by Boston University.
References
[AABR09] Jacob Abernethy, Alekh Agarwal, Peter L Bartlett, and Alexander Rakhlin. stochastic view of optimal regret through minimax duality. In Conference on Learning Theory, 2009.
[ABRTO8] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies minimax lower bounds for online convex games. Conference on Learning Theory, pages 415-423, 2008,
[AHMS13] Oren Anava, Elad Hazan, Shie Mannor, and Ohad Shamir. Online learning for time series prediction. In Conference on learning theory, pages 172-184. PMLR, 2013.
[AHZ1S] Oren Anava, Elad Hazan, and Assal Zeevi. Online time series prediction with missing data. In International conference on machine learning, pages 2191-2199. PMLR, 2015.
[AM16] Oren Anava and Shie Mannor. Heteroscedastic sequences: beyond gaussianity. In International Conference on Machine Learning, pages 755-763. PMLR, 2016.
[AW01] Katy Azoury and Manfred K Warmuth. Relative loss bounds for on- on-line density estimation with the exponential family of distributions. Machine Learning, 43(3):211 1464 2001.
[BGZI5] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operutions research, 6377) 1244, 2015.
[BW19] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of anal-variation-hounnee sequences. Advances in Neural Information Processing Systems, 32, 2019.
[BW20] Dheeraj Baby and Yu-Xiang Wang. Adaptive online estimation of piecewise polynomial trends. Advances in Neural Information Processing Systems, 33:20462-20047,, 2020.
[BW21] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theory, pages 359-409. PMIR, 2021.
[BW22] Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference Artificial Intelligence and Statistics, pages 1805-1845. PMLR, 2022.
[BZW21] Dheeraj Baby. Xuandong Zhao, and Yu-Xiang Wang. An optimal reduction of -deeoiisg adaptive online learning. In International Conference on Artificial Intelligence and Statisties, pages PMLR, 2021.
[CDV93] Albert Cohen, Ingrid Daubechies, Pierre Vial. Wavelets on the interval and fast wavelet transforms. Applied and computational harmonic analysis, 1993.
[CLW21] Liyu Chen, Haipeng Luo, and Chen- Wei. Impossible tuning made possible: new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-1259, PMLR, 2021.
[CO18] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493-1529. PMLR, 2018.
[CRT06] Emmanuel J Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 5292)4889-509 2006.
[Cut19] Ashok Cutkosky. Combining online learning guarantees. In Conference on Learning Theory, pages 895-913. 913. PMLR, 2019.
[Cut20] Ashok Cutkosky. Parameter-free dynamic, and crongly-adapptoe online learning. In International Conference Machine Learning, pages 2259. PMLR. 2020.

---

[CWW19] Xi Chen, Yining Wang, and Yu-Xiang Wang. Nonstationary stochastic optimization under Lp.a" variation measures. Operations Rexearch, 67(6):1552-165, 2019.
[Dau88] Ingrid Daubechies. Orthonormal bases of compactly supported wavelets. Communications on pure and applied mathematics, (1(7):909-999) 1988.
[DGSS15] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pages 1405-1411, PMLR, 2015.
[DHS11] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7). 2011. 20
[DSSSTIO] John C Duchi, Shai Shalev-Sha Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In COLT, volume 10, pages 14-26. Citeseer, 2010.
[FKK16] Dean Foster, Satyen Kale, and Howard Karloff. Online sparse lincar regression. In Conference on Learning Theory, pages 960-970, PMLR, 2016.
[FKMS17] Dylan Foster, Satyen Kalc, Mehryar Mohri, and Karthik Sridharan, Parameter- free online learning via model selection. Advances in Neural Information Processing Systems, 30, 2017.
[FRS18] Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the Burkholder method. In Conference On Learning Theory, pages 0028-3064. PMLR, 2018.
[Ger13] Sébastien Gerchinovitz. Sparsity regret bounds for individual sequences online linear regression. The Journal of Machine Learning Research, 14(1):729-P3) 769, 2013.
[GG15] Pierre Gaillard and Sébastien Gerchinovitz. A chaining algorithm for online nonparametric regression. In Conference on Learning Theory, pages 764-796. PMLR, 2015.
[GS16] Andras Gyorgy and Csaba Szepesvári. Shifting regret, mirror descent, and matrices. International Conference on Machine Learning, pages 2943-2951. PMLR, 2016.
[GW18] Pierre Gaillard and Olivier Wintenberger. Efficient online algorithms for fast-rate regret bounds under sparsity. Advances in Neural Information Processing Systems, 31, 2018
[GY14] Sébastien Gerchinovitz and Jia Yuan Yu. Adaptive and optimal online linear regression L1 -alls. Theoretical Computer Science, 519:4-28, 2014.
[6az16] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
[HLS+ 18] Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang, Spectral filtering for general linear dynamical systems, Advances Neural Information Processing Systems, 31, 2018
[HR09] Niall Hurley and Scott Rickard. Comparing measures of sparsity. IEEE Transuctions on Information Theory, 55(10))4423-4744 2009.
[HW01] Mark Herbster and Manfred K Warmuth. Tracking the best linear predictor. The Journal of Machine Learning Research, 1:281-309, 2001.
[HW15] Eric C Hall and Rebecca M Willett. Online convex optimization in dynamic environments. IEEE Journal of Selected Topics in Signal Processing, 94))64776662, 2015.
[JC22] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Conference on Learning Theory, pages 1160--221. PMLR, 2022.
PMLR,
[Joh19] lain M Johnstone, Gaussian estimation: Sequence and wavelet models. Unpublished lecture notes. 2019. ht attpps///mg chnstone su. domains/mBBt. SectainssGE_o_.... _9_16_19_91111111101__00_____11_ 19f.....f............
JOOW17] Kwang-Sun Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Arrificial Intelligence and Statistics, pages 943-951. PMLR, 2017.
[JRSS15] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimiza- tion: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406. PMLR, 2015.
[Kal14] Satyen Kale. Open problem: Efficient online sparse regression. In Conference on Learning Theory. pages 1299-1301 1301. PMLR, 2014.
12

---

[KKLP17] Satyen Kale, Zohar Karnin, Tengyuan Liang, and Dávid Pál. Adaptive feature selection: Computa- tionally efficient online sparse linear regression under rip. In International Conference Machine Learning, pages 1780-1788. PMLR, 2017.
[KM16] Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning. In Conference on Learning Theory, pages 12100 PMLR, 2016.
[LLZ09] John Langford, Lihong Li, and Tong Zhang. Sparse online learning via truncated gradient. Journal of Machine Learning Research, 10(3), 2009.
[I.S15] Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory, pages 1204-1304 PMLR, 2015.
[MA13] Brendan McMahan and Jacob Abernethy. Minimax optimal algorithms for unconstrained linear optimization. Advances in Neural Information Processing Systems, 26:2724 2732, 2013.
[Ma108] Stephane Mallat. A Wavelet Tour of Signal Prucessing: The Spurse Way. Academic Press, 2008
[MK20] Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory, pages 2858-2887, PMLR, 2020.
[MO14] Brendan McMahan and Francesco Orabona. Unconstrained online linear learning hilbert spaces: Minimax algorithms and normal approximations. Conference on Learning Theory, pages 1020-1039. PMLR, 2014.
[OP16] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016.
[Ora19] Francesco Orabona. A modern introduction to online learning. arXiv preprint 13X113191..13211.
2019.
[Pri21] Eric Price. Sparse recovery. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms,, page 140-164. Cambridge University Press, 2021.
[RS14a] Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Conference on Learning Theory, pages 2232-1664 PMLR, 2014.
[RS14b] Alexander Rakhlin and Karthik Sridharan. Statistical learning and sequential prediction. Unpub- lished lecture notes, 2014. http://wwe http:///wwwtttttt/t/////ett/tttt www.:miiiittmmaaeeeeeee notea. notea.pdf. pdf.
[SBG+21] Martin G Schultz, Clara Betancourt, Bing Gong, Felix Kleinert, Michael Langguth, Lukas Hubert Leufen, Amirpasha Mozaffari, and Scarlet Stadtler. Can deep learning beat numerical weather prediction? Philosophical Trunsactions of the Royal Suciety A, 379(2194):2020099)) 2021.
[SM12] Matthew Streeter Brendan Mcmahan. No-regret algorithms unconstrained online convex
optimization. Advances in Neural Information Processing Systems, 25, 2012.
[SS11] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and trends Machine Learning, 4(2):107-194 2011.
[SSTI1] Shai Shalev-Shwartz and Ambuj Tewari. Stochastic methods Legrelulaize loss minimization. Journal of Machine Learning Research, 12:1865-18 1892, 2011.
[Tib96] Robert Tibshirani. Regression shrinkage and selection via lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-28) 1996.
[vdH19] Dirk van der Hoeven. User-specified local differential privacy in unconstrained adaptive online learning. Advances in Neural Information Processing Systems, 32, 2019.
[Vov01] Volodya Vovk. Competitive on-line statistics. International Statistical Review, 69(2):213-24 2001.
[Xia09] Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. Advances in Neural Information Processing Systems, 22, 2009.
[YZJY16] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning, pages 449 457. PMLR, 2016.
13

---

[ZCP22] Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. PDE-based optimal strategy for uncon- strained online learning. In International Conference Machine Learning, pages 26085-26115. PMLR, 2022.
[Zin03] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-9988-999 228-936.11 2003.
[ZLZ18]
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning dynamic environments. Advances neural information processing systems, 31, 2018.
[ZYY+17 17]
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. Advances Neurul Information Processing Systems. 30, 2017.
[ZYZ* 18]
Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, al. Dynamic regret of strongly adaptive methods. In International conference on machine learning, pages 5882 5891. PMLR, 2018.
[ZZZZ20] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-HHu Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, 13:12510-12520, 2020.
[777721] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adantivity and stationarity: wobblem-dependen dynamic regret for online convex optimization. arXiv preprint a1Xiv:2112.14368, 2021.
14

---

Appendix
Organization Appendix A summarizes list of comparator statistics involved in our theoretical analysis. Appendix B surveys additional related works. Appendix C, D and E respectively present details of our general sparse coding framework, its special version with wavelet dictionaries, and applications in time series forecasting. Finally, Appendix F presents additional discussion of our technical results.
A List of comparator statisties
A major task in comparator adaptive online learning is finding suitable statistics to quantify the regularity of a comparator sequence. Several such statistics are defined throughout this paper, which are summarized in Table 2. Note that for the definition of sparsity on the last line, we assume the dictionary H is orthogonal, and the sequence M1.r is contained in its span. Then, (()) is defined as the projection u1:7 onto feature vector h1:T, i.e.,
h1.T.
g(n) (hi:T,m u1:3)
||01:2;1012
This is well defined due to our assumption | la 2 from Section 2.1.
Name
Notation
Definition
Maximum range
M
max;
Comparator average
T
Up
Path length
P
Uc l12
Norm sum
S
Σ t=1
||
First order variability
5
Σ
||u
t=
Energy
E
Σ
||u
12
Second order variability
E
Σ1=1
|
T|
Number of switches
K
Σ 1=1
1(u+11
u4
N
Sparsity on a dictionary H.
Sparsity
(2(m)
Table 2: A list of comparator statistics.
Next, let us discuss their relations, in order to interpret our quantitative contribution more clearly (Table 1). It is clear that MT, therefore the fine baseline (4. from [JC22] improves the coarse one (3); comparing their associated switching regret bounds follows the same reasoning.
To compare results to the baselines, observe that
T
| VT
Juell2 S V S VMS,
t=1
tm
T
5
144 ū||2 S
luell + T | Σ
|uellz + Σ U1
28,
2
E
Σ
| U|ا2 5 2MS < 4MS.
t=1
Therefore,
| VT VP
0 (JM))
|00|2 VT + + KE VMS (V(1+ K)MS).
15

---

That is, both our www--lennthddeeeeeee bound and the switching regret bound are at least as good as the results from [JC22]. Concrete benefits are demonstrated in Example and 2.
Finally, as a sanity check, our path-length-ddeeeddet bound does not violate the lower bound 52 PP): even when u = 0,
P
Σ
114p1
Hell2
Σ
11++1
u112 +
Σ 1 u112 S 22,,
therefore our bound is never better than ((P).
B More on related work
Online regression Our sparse coding framework converts unconstrained dynamic OCO special form of online regression. The standard setting of the latter [RS14a] considers a repeated game as well: in each round, we observe covariate 22 Rd make prediction yr R (which depends Ty), and then observe a label y: E R. The performance metric is the minimax regret under the square loss
T Σ (1: y0) 1=1
T inf ((f())) JET
Regrety(F)) =
y0)²
- y.)
t=1
Roughly, the problem is of nonparametric type if the complexity of the function class F is not fixed a priori, but grows with (i.e., the amount of data).
Overall, such an online regression problem is highly general, as static OCO is recovered if oz is time-invariant. The setting we utilize is variant with (i) vector output; (+i) general convex losses; (Hii) 24 specified by the dictionary, possibly being sparse itself (e.g., wavelets); and (iv) the function class F being linear, but unbounded. As discussed in Footnote 11, our setting deviates from the conventional definition of regression, as a general convex loss function does not necessarily have minimizers. We adopt the terminology of "regression" for streamlined exposition.
Existing works on online nonparametric regression [RS144 RRS14a, GG15] have established the relation of this problem to certain path length characterizations of dynamic regret. However, the generality of this setting makes the analysis challenging, and especially, algorithms can be computationally expensive. With a bounded domain assumption (on predictions ÿr). recent breakthrough [BW21] simultaneously achieved several notions of optimality for path-lengtt-deeeeddent bounds, with efficient computation. Readers referred [BW21, Appendix A] for thorough discussion of this line of works.
For the special case of Online Linear Regression (OLR) with square losses, the celebrated VAW forecaster [AW0I, Vov0l] guarantees O log I) regret against any unbounded coefficient vector E IRN, where N is the dimension of the feature space. Such a fast rate becomes vacuous in the nonparametric regime (when N > T) [GY14), therefore [Ger13] proposed sparsity regret bound ((11)ll)) and accompanying inefficient algorithm its high dimensional generalization. Efficient computation was addressed by [GW18] but the obtained result only applics to bounded û. In a rough sense, such sparsity regret bounds are the square loss and reature-based analogue of the L1 -oomm parameter-free bounds in OLO [Ora19, Chapter 9]. They are also closely related to sparsity oracle inequalities in statisties, reviewed by [Ger13].
Parametric time series models For time series forecasting, most prior works are devoted to parametric strategies with strong inductive bias, such as the ARMA model, state space models, and more recent deep learning models. Online learning has been applied to such models as well [AHMS13, AHZ15, AM16, KM16, HLS 18], leading forecasting guarantees under mild statistical assumptions. When convexity is present, some of these problems could be reframed as special cases of our OLR problem, with a constant-size dictionary that does not grow with T;; for example, learning the autoregressive model corresponds to defining the features as the fixed-length observation history. Also, Appendix E shows that given parametric time series forecaster (possibly without performance guarantees), our algorithm can be applied on top of it, in order to provably correct its nonstationary bias.
Other sparsity topies in OL Finally, we review other sparsity-related topics in online learning, which do not fit into the scope of this paper. [LLZ09, Xia09, DSSSTIO, SSTI1] considered using
16

---

online learning to solve batch L1 regularized problems. The goal is to achieve sparse predictions instead of sparsity adaptive regret bounds. [Kall4, FKK16, KKLP17] studied online sparse regres- sion, where only subset of features are available in each round. The challenge is to handle bandit. feedback in OLR.
C Detail on the general framework
This section presents details on our general sparse coding framework. Appendix C.1 introduces the static subroutine we adopt from [MK20]. Appendix C.2 proves our main results, but with additional gradient adaptivity compared to the main paper.
C.1 Unconstrained static subroutine
The following static OCO algorithm and its guarantee are due to [MK20, Section 3.1]. We assume that | < G, and >> 0.
Algorithm 3 FREEGRAD [MK20, Definition 4]: scale-free and gradient adaptive unconstrained static OLO.
Require: A hyperparameter ε > 0; dimension d; Lipschitz constant G.
Initialize a gradient sum counter 0 E Rdd and variance counter v G
2: for = 1, 1,2..... do
3: Predict
(2c & [1
|| 2
4. CS
exp
2(v G ||s ) /0
2v + 2G |
4: Observe the loss gradient 9c-
5: Update s <- + 9t, and +- + o8.
6: end for
Lemma C.1 (Theorem 20 of [MK20]). With any hyperparameter 0, for all T E N_. and á E TR
Algorithm 3 guarantees
T
2 21| VT
(4 (411/il2 vVT )
Σ
(e Rt - a) s S
2 |ááll V
Vr log
4 ||ūl| Glog
EG2
zG
where
T V/ = 6
11be112
C.2 Proof of the main result
We present the analysis of our general sparse coding framework. The following lemma is slightly more general version of Lemma 2.1 in the main paper, which characterizes the performance of our single direction learner (Algorithm 1). Recall that ge (1.():) from the OCO-OLO reduction.
Lemma C.2 (Lemma 2.1, full). Let > 0 be an arbitrary hyperparameter for Algorithm 3. Applying its ID version as the static subroutine, for all T E N and wi. E span(hurr). against any adversary E, Algorithm guarantees
T
G C [1rlll
Σ ((x))) E4(m)) S t=1
sGG+
+
Σ (gt, uz)²
polylog (iaxx |lwel|2 2 , T)
The simplified form (Lemma 2.1) is recovered by using || 2 1 and 119el12 - G.
17

---

Proof of Lemma 2.1. Subsuming poly-logarithmic factors, the static regret bound of our static sub- routine (Algorithm 3) can be written
T
T Σ g2 1=1
9e (a, 2) S GG |ál Σ
G+
polylog [o],T.==]]
where ú is any ID static comparator that the subroutine handles.
Now, for any single-directional comparator V1:7 span(()ar) considered in this lemma, there exists R such that U1TT ihT. The dynamic regret can be rewritten as
T Σ ((4)) $
T
T
T (g hylt hT Σ ( - -t)
Σ ((x))
Σ
(o,, Iz u1)
Σ
and the RHS can be bounded using the static regret bound above. Note that lãel Kgn, /4> S G. therefore the surrogate Lipschitz. constant & from the static regret bound can be assigned to G. In summary,
T
Σ ((x))
Σ (dew)) S EG + |
G+
Σ
lo hi??
polylog ([ul,T,=-))
|urrll
| l2 T
= 5G +
G
+
(gt. up)
poollog
h
|lurrll
S &G
+
Σ (gt, u1)²
polylog (max |luell2 T,,-1) ||
where the last line is due our assumption that ||/1: 1l2 2
Next, we prove the unconstrained dynamic regret bound with general dictionaries (Theorem 1). Theorem 4 (Theorem 1, full). Consider any collection of signals (n)) E span(hirr,.), Vn. We
define its reconstruction error (for the comparator uI:T) 2 U1. - E (x) RdT Then, for all T N. and unr E pee against any adversary E, Algorithm 2 guarantees
T Σ ((v))=
Σ (((x))=
S S
Σ
gts 2t (0)
t=1
G
|
2
N
(m) (n))2 yr Re /
polylog
(max [ni 2t ||2 T, N,e))
n=1
where =(
Rdd is the 1-th round component of the sequence ((n) RTT
Proof of Theorem 4. The idea of this theorem is dynamic analogue of [Cut19] to aggregate the regret bound of single direction learners. For all decomposition Wi.T > z(n) such that 2(n) span(hi:r,..) for all n [1: T), we have
T
T
N
(xx)))
Σ le(we) S (gi.T, uIT)) = -1.T
gir WTTT, - 2(n)
18

---

For the first term on the RHS, (-917, Lemma C.2, with hyperparameter e/N.
-EE= (01)(")) As for the rest, we plug in
91:T: WI-T,n - -2(m)
N
||
T
ge, 24 )
max 2 12 I, I.N.
NN +
G
polylog
n=1
|2 1l2
< &G
gts 2t )
polylog
max
[n) TTN, =t 2
N,,N
PITTT ll
f,n
Next, we show how this dynamic regret bound recovers the static regret bound in Rd. As discussed in Section 2.2, the static setting amounts to picking N = d and H4 la. and the decomposed signals 2(n) are determined by orthogonal projection of the static comparator sequence U1.7 = [u..... u].
Specifically, =²") is d-dimensional vector which is zero except the n-th entry; its n-th entry equals the n-th entry of the static comparator u. If we index the gradient as 9t 19t, It,al E IR and the static comparator as u = [u1...., ual E Rd, then (9.- 21 = Br Applying Theorem 4, against static UI.T.
Σ h(x))
l(())
N
|0000
N
T
ge, of )
G
polylog
max 2
T, NT,NNe-1
2
n=1
Uel VT
SeG+
mal
Σ g
pollloo (11u1l T, N,N,
VT
T
EG
G||ull + ||ull2
G
11
122
polylog (1ul1 ,T,N,
In the asymptotic regime with large T, (wrr) = 0(1uu12 vT).
D Detail on the wavelet algorithm
This section presents details of our wavelet algorithm. The pseudocode is presented in Appendix D. Appendix D.2 introduces the wavelet-specific notations for our analysis. Appendix D.3 presents a generic sparsity based bound for our algorithm. Appendix D.4 and D.5 prove our main results. Auxiliary lemmas are contained in Appendix D.6. Finally, Appendix D.7 works the details of the two examples from the main paper.
D.1 Pseudocode
For all E N4. let T 2 and let Haar, be the T' x T Haar dictionary matrix defined in Section 3.1, for d 1. We apply the following variant (Algorithm 4) of our sparse coding framework, in order remove all d dependence from the final regret bound. It adopts the d dimensional version of the static subroutine (FREEGRAD), instead of the 1D version in Section The pseudocode mirrors the combination of Algorithm and 2.
is equivalent to view Algorithm as operating on dT x dT "master" dictionary matrix H. defined block-wisc as the following: for all (i.j) [1 272, the (i,j)-th block of H. is the product of the
19

---

Algorithm 4 Haar OLR with known time horizon.
Require: A time horizon T = = the T Haar dictionary matrix Haarm; and a hyperparameter >> (default is 1).
1: Let = T. For all n E [1: .). initialize a copy of the d dimensional version of Algorithm (FREEGRAD) as An, with hyperparameter E/N.
2: for = 1,2 ...... do
3: Receive the t-th row of Haarm. and index it as 1..., N note that he, E R.
4: for n = 1,2,... NN do
5: h4.n * 0, query An for its output, and assign it.. E IR otherwise, Ze,n is arbitrary.
6: Define Wt.n ft, R
7: end for
8: Predict F2 >n Whnn E IRd receive loss gradient Jt E Rdd.
9: for nL = 1,2, 1,, do
he * O, compute St.n htngt and send it to A, as its surrogate loss gradient.
11: end for
12: end for
Algorithm 5 Anytime Haar OLR (Algorithm 4 with doubling trick).
1:
for m = 2......, do
2: Run Algorithm 4 for 2n rounds, which uses the matrix Haarm- The hyperparameter set to 1.
3: end for
(i, entry of Haarm (which is a scalar) and the d-dimensional identity matrix la- That is, H is a block matrix; each block is a diagonal matrix with equal diagonal entries determined by Haarm- Roughly, the algorithm measures distances in R by the Le norm, while measuring IR by the L1 norm.
Algorithm 4 alone is not sufficient for our purpose: it must take integer and for fixed = 2n rounds. We apply meta algorithm (Algorithm 5), which simply restarts the known T algorithm using the classical doubling trick, e.f., [SS11, Section 2.3.1].
D.2 More background
Although the analysis of our framework is simpler than [JC22], challenge is carefully indexing all the quantities to account for the vectorized setting. It is thus important to introduce few notations to streamline the presentation. Haar, is the T T Haar dictionary matrix defined in Section 3.1, with T 2nh Recall the statistics of the comparator sequence, summarized Appendix A.
Local interval Given any scale-location pair (j, (), let the support [(,.) be the time interval where the feature h(.) nonzero. That is,
7 = 22 (1- - 11:
Moreover, let (( denote the first half of this interval, and ((: for the second half. h(11) is on f(ad) and -1 on (idd)
Let Haar, be the orthonormal matrix obtained by scaling the columns of Haar The normalized feature vectors also denoted by tilde, i.e., instead of h" and h(A), the normalized features are A and h..) They are vectors in IRT,, with the f-th component denoted by hg and h, (i.)) in R.
Normalization
Coordinate sequence Consider any comparator sequence u1.7 E RT For all coordinate i E [1 d]. we define its i-th coordinate sequence as (i)) RT, the t-th entry of this coordinate sequence (6)
(6) is the i-th coordinate of uy. "17 denoted by
20

---

Transform domain coefficient We will also use the transform domain coefficients of 11:r. under the Haar wavelet transform. Recall that the single-feature, generic setting (Section 2.2). we denoted single transform domain coefficient by ú E R. With wavelets, the transform domain encodes d' -i-einnnsional vectors. According to our convention so far, we will denote them by scale-location pairs (j. (): given a ( pair, the "coefficient" gli-)) is d-dimensional vector. There T 1 pairs of (j.1) in total; complementing the representation, "coefficient" for the all-one feature.
another ü' Rd represent the
Given any scale parameter j E [1 log2 7] and location parameter 1 E [1 [1:27/)). let
a { (1,00 u1
(1)
(d) u1
and for the all-one feature,
[ hi U1:T
i' -
That is, each entry is the inner product between the normalized feature and a coordinate sequence from U1:T-
Due to the orthonormality the applied transform (specified by the normalized features h and h(0,), the energy is preserved between the time domain and the transform domain, i.e.,
E
U1. 2 = | 1| +
Σ ju
and also the second order variability (the energy of the centered dynamic component within (1:T),
F 1u ū =
Σ a(i.))
(11)
Moreover, since h equals 1/vT times the all-one vector,
2
|| 1/
= =1 (12)
1:T
LT
IT
Detail reconstruction Given the transform domain coefficients, we can reconstruct details of the comparator uIr on the time domain. Similar to notation in the generic framework (Section 2.2), we keep the letter z, but replace the index n by (j. l). which is more suitable for indexing wavelets.
Let 20:0 E pdT be the detail of W1.T along the (j. ()-th feature. It is the concatenation of T vectors in Rd, and for all t, the t-th of these vectors is defined by
(j.) == a(:0) (1:0 Rdd.
Similarly, we can define the detail along the feature ht. Its t-th component is
2 == -
and clearly, the RHS does not depend on t since h" is the normalization of the all-one feature h*. Let us also sum the details across different locations. Given scale j. let
200 == (10 E RT
Note that the summands are sequences that do not overlap: at each entry, only one of the summand sequence is nonzero. The full reconstruction obtained by summing all the details,
lon T
W1.T
2"
+
j=1
21

---

Statistics of the detail sequence We can define statistics of the detail sequences just like the statistics the comparator u1.7. Specifically, define the first order variability of the (j. 1)-th detail as
T
24
(1:0) Note that since the ot sequence is centered (with average being equal to 0), its first order variability equals its norm sum, c.f., Appendix A. Summing over the locations, the first order variability at the j-th scale is
SCi = Σ
which equals E, SU.D.
Similarly, we can define the path length of the detail sequences. caveat that we only count the path length within the support (6.) of the feature h(i))
211-1
p
GD
(1.1)
[+1
2x
t= (1-11)+
The comparator's movement when the support changes does not count. Summing over the locations,
pl)) = Σ p(..).
D.3
Generic sparsity adaptive bound
With the notation from the previous subsection, now present generic sparsity adaptive regret bound for Algorithm (fixed Haar OLR). Since the latter a variant of our main sparse coding framework (Section 2). the result can be analogously derived, although the notations need to be treated carefully.
Lemma D.I. For any m, T 2m and u1r E RR with any hyperparameter > 0, Algorithm 4 guarantees
log, T2 2-r
(UIr)) S =G GG +G ||
Σ
20.0
pollyog (M,
1=1
The proof sums the regret bound of the d-dimensional version of the static subroutine (Lemma C.1), across 7 different copies. It is very similar to Theorem 1, therefore omitted.
might be more convenient to use the transform domain coefficients ( in the bound, rather than the reconstructed details 2(1.), In this case, we have
1
Σ
(1,) 26
Σ
R
FG.0
27
20000
12
Σ
|000000 ?
Similarly,
||
|| ||a"|1²-
Therefore,
log, 2' 2'2 -/
(G..)) 11,
Regret,((1.r)) S cG
||00|l2 +
pollloo (M,T.E
(13)
D.4 Unconstrained switching regret
In the K-switching regret, the complexity of the comparator is characterized by its amount of switches. The idea is that, the comparator W1.7 is static on a support (G.1 for some (j. l), then the corresponding transform domain coefficient . E IRd. We have the following bound for the fixed T' algorithm (Algorithm 4).
22

---

Lemma D.2. For any m, T = 2 and u1.T E RTT,, Algorithm 4 with the hyperparameter 1 guarantees
(u))) = ( VT V KE
Proof of Lemma D.2. Consider any scale j. Since the supports (76:0); do not overlap, if u1.7 shifts K times, then there are at most K choices of location I such that the transform domain coefficient a(i)) is nonzero. Furthermore, since there are log, scales in total, there are most K log, T pairs of (i such that ((i-)) is nonzero. Therefore, using Gauchy-Schwarr and Eq.(11).
Σ j.t
ll I / log, T
Σ 3u
||0 V KK T.
Plugging this into Eq3(13), and further using (q.( for | complete the proof.
The anytime bound in general follows from the classical doubling trick. A twist is that the analysis is slightly more involved than the standard one, e.g.. [SS11, Section 2.3.1], as we also need to relate the comparator statistics each block to those for the entire signal M1:1-
Theorem 2 (Switching regret). For all T E N+ and u1.T
RdT Algorithm 5 guarantees
(uI:7) S 6 VT+
Proof of Theorem 2. First, assume T can be exactly decomposed into m segments with dyadic lengths 2 ......................... 2m We use Um. Km and Em to represent the statistics the comparator sequence on the length 2n block, and let 1 denote the time interval that this block operates u, K and $ denote the statistics of the entire signal U1:7T c.f., Appendix A. From Lemma D.2,
(ugre))((1:r))
Σ m
(lūmmllz 22m + V Km
m
m
Ō
|
2m
1um
u112
2
v Km Em
(14)
The first term follows from the standard doubling trick analysis [SS11, Section 2.3.1].
m
V2
0 (VT)
2
2
(15)
V2 -
As for the second term in (14), using Cauchy- Scheha,
m
m
üm
ū/12 V2m S
m
Σ
2m
m = O(log and also observe that the sum (in the parenthesis) the RHS equals the second order variability of the following signal: for any time in the m-th block, the signal's component is ün Rdd This signal is locally averaged version of the original comparator uI.r, and the key idea that local averaging decreases the variability. Formally, due to Lemma D.7, we have
7m x|l2 V2m S 2 <V(VE)
(16)
For the third term in (14,) using Cauchy-Sehward again,
Km Em <
Σ Km
Σ Fm $ V
K.
m=1
mmml 1
23

---

The sum of Km is straightforward. The inequality for the sum of Em follows from the observation that on the m-th block, um minimizes Erero I| - ==12 with respect to E R24
Also, notice that the second term in Eq.(14) is dominated by the third term. If = 0, then both F and v KE equal O. 2 1, then VE & VKE. Therefore, Eq.(14) can be written as
(ugretr(uur) S SO (lāl|2 VT KE
As for the general setting where 7' cannot be exactly decomposed into dyadic blocks: consider the smallest 7 > T such that 7 can be decomposed. Due to doubling intervals, T < 2T. Let us consider hypothetical length T game with the rounds t T constructed gradient 9t = E R., and u, = ū. this case, with and still representing the statistics of the length 7 sequence W1.7, the number of switches on the entire time interval [1 7 is most K and the second order variability on [1 : TM] is E; furthermore, is clear that (K + 1) S 2K E. The regret of any algorithm this hypothetical length 7 game is the same the length T game, therefore bounding the latter follows from bounding the former.
follows: the loss
D.5 Path-length-band based bound
Next, we turn to bounds that depend on the path length P of the comparator 41.7. Similar to the switching regret analysis, will first consider the setting with fixed dyadic T (Algorithm 4), and then extend its guarantee through a doubling trick.
D.5.1 Fixed dyadic horizon
In the following, we consider Algorithm 4; assume T = 2 for some m. The static component (i.e., =²) and the dynamic component (i.e., u1.7 2²) of v1:7 are analyzed separately; the former is fairly standard, while the latter is more challenging. We will first consider the dynamic component, and proceed three steps.
Step Considering any scale j. aim to show Σ, || SP)) which relates the transform domain coefficients to the regularity of the reconstructed signals.
Lemma D.3. For all (j, 1) pair,
2-1 S(A.)
2
and
Σ
22-1/2 PP))
2
Proof of Lemma D.3. Let us start from the first part this lemma, and express the detail sequence 2(id), and equivalently 2(5), more explicitly on its support 10:4)
2 2-1020001
LE r(1).
2
- 2 2-112(6111
Le 1.49)
Rewriting p(.)) and S011)
2/111
p(i.)
Σ
-00
21--//2
[2(:00)
2++1
21 1)+1
50.0
Σ
(3)
2-1/2
2 = 22/2
=
2
1E(G.)
which yields the equality in the lemma. The second part follows from Cauchy-Schwarz.
24

---

Step 2
Showing that pú) < P and SC) < S. That is, the reconstructed signals are easier than the original comparator UL. Here, P and 5 should be considered separately.
Lemma D.A. For any uvr and any scale parameter jr, p(") S
Proof of Lemma D.4. From the definition of P and the reconstruction of UTT from detail sequences,
200
P= Σ
|441 Hell2 Σ
(= -
Σ t=
Σ
G) 2+1
241
[=1
t=1
where the last equality is due to being constant sequence.
Consider removing "shorter" scales with 1 S j < j", which is equivalent to local averaging, c.f., Appendix D.6. Due to Lemma D.7, the path length does not increase, i.e,
Σ
2 - 10)
2
Then, we can further remove the rounds where the path length is not counted p("), i.c. when time E 70",0) but t + 1 I0",441)
1-1
RHS Σ
Σ
Σ
200)
2441
2=
1)+1
Now, consider any location 1, which determines the time interval 10 ,) = 120 - 1): Any detail sequence 200) with scale > j is constant on this time interval, thus removing it does not change the path length all. Therefore,
2 1-1
P2
Σ
Σ
241 - 24 2 = p())
(=2)"((-1)+)
t=2j
As for the first order variability, Lemma D.5. For any u1T and any scale parameter jr, 30") < S.
Proof of Lemma D.5. From the definition, noticing that is entirely captured by the all-one feature,
loga T
$
1u ū =
Σ
Due to Lemma D.7, removing short scales amounts to local averaging, which decreases the variability.
3 M
Σ P2J
= = Σ
SEIG
プ>ン
2
For any 1, consider the support of the ())th feature, I0'.0) Observe that Σz>}" ( is time invariant throughout IO',,) let us denote it as E Rd, Meanwhile, for some Rd. (7") equals w on 1 4). the first half of this interval, while being -w on the second half 1 (1) of this interval. Therefore,
Σ (Er0"))
Σ j>1"
( 2t
= 2 -1 (Ilv + w|l2 + || wll2) 2 25 ||ll22
Σ
Combining the above.
5 Σ Σ
- = 500)
tEIG".
25

---

Step 3 Summarizing the above relations, and using the property that there are only log2 I scales. Lemma D.6. For any m, T = 2 and WIT E pdt, Algorithm 4 with the hyperparameter = 1
guarantees
(ugre = (lā12 VT VP))
Proof of Lemma D.6. Starting from the generic regret bound, Eq.(13) for Algorithm
Segrety(uL.T)S S
|| +
Σ Ju
|2b00111 polylog (M,
Due to (12), 11"112 - |2 VT. Then, combining Lemma D.3, D.4 and D.5,
Σ aale)) so (V T).
Plugging it into the generic bound completes the proof.
D.5.2 Anytime bound
Now we are ready to prove an anytime unconstrained dynamic regret bound that depends on the path length.
Theorem (Path length bound). For all E N4 and u1.r RdTT, Algorithm guarantees
Regrety (ui:T) S Ô (1u| VT + VPS).
(10)
Proof of Theorem 3. Similar to the analysis the switching regret (Theorem 2), we first consider the situation where the time horizon T can be exactly decomposed into m segments with dyadic lengths 2,....,2" In this situation, have
2
m
n
Regrety (UI:T)
SÓ
Um ll
2
Pm35m
-m=1
m=1
| vT
E
Pn
S m
mmm
where the second line follows from the proof of Theorem 2, specifically (q,(1 and (1.) Now let us consider the remaining sum on the RHS. Using Cauchy-Schwarz,
m
m
2m
PmSS
S
Σ
Pm
Σ Sm
S
P
Σ
Σ
l - um Smull2
mml
Li
where
m
2m+
m²
20+
m
Σ
Σ
Um 1l2
Σ
Σ
(1lu
2/|2 + ||ūn ru|12) S +
Σ
2m
u/|2
77
The last sum on the RHS is the first order variability of a locally averaged version of uI.T. Due to Lemma D.7,
m
Σ
2
[mm -ul12 S.
Combining everything above,
Regret (UIT) 5. <0 VT VV++VE+
26

---

It remains to show that VE < VPS, thus the former can be absorbed into the latter. Plugging in the definitions, this is equivalent showing
T
P uc u|12.
and it suffices to prove ||u ūl| & P for all t E [1 T7. This completed in Lemma D.8. Till this point, have shown the desirable result in the situation of "exact dyadic partitioning".
To complete the proof, we turn to the general situation where 7 cannot be partitioned into dyadic blocks. This follows from a similar "padding" construction from the proof of Theorem 2. Let T = 2 21, and by definition, 7 < 27' Let us consider a hypothetical length 7 game with the constructed as follows: the loss gradient Jr E F. and u,
Then, the regret of any algorithm on the length 7 hypothetical game equals its regret on the actual length T game, and the regret bound for the former applies the latter as well: if we write ps and S as the statisties of the extended length 7 comparator, then
rounds
Regrety((11)) ( +VP
Clearly, 5 S and T < 2T. As for the path length, P = P |ur ū u1|l- and due to Lemma D.8.
|uu - 2||2 < P. Plugging it back completes the proof.
D.6
Useful lemma
Our analysis uses two auxiliary lemmas. First, we show that local averaging makes a signal "more regular". Consider any signal u1.7 RdT, with the 1-th round component E Rd. Local averaging refers to replacing any & consecutive components of un. by their average, i.e., setting
M7+1, Mr+h k
U 4
for some E :0: k)..
Lemma D.7. Let a signal wirr RdT be the result of uir after local averaging, and t T-1 Σ w. E Rdd Then, the path length, the norm sum and the energy of WYT, including their centered versions, are all dominated by those of u.r. That
1. E
T-1 |1 well2 ΣT-1
|1u41
uzllz
Σ
||0e - -w112 5 Σ |/1e ū||ات
ΣT 1=1 |ww, - -w1 s ΣT= 1|2e T||2
4. ΣT
|well2 5 Et | lly and En 11wel1 < Er 114
Proof of Lemma D.7. Starting from the first part of the lemma, we prove for the general case of 0 < k. The boundary cases (T and T k) analogous.
Local averaging only affects the path length caused by the averaged entries u7+1,-.., Mr+*s and the two entries Uy and ur+k+1 right besides averaging boundary; this original path length quantity in
27

---

u1.7 is Ei=o 1/4-+++1 2r+eel22 2
After averaging, the path length among these entries becomes
"
k
Ur+i
+
k
Urti ur+k+1
1=1
k-
U7 u
+ k
(ur+s u++++1)
b
(1|u, - ur+ille 12l222222 + |lura ur+k+11222 (12)
i=1
b
S
|,++++ ur+oll2
1=1
|ur+i+1 Ur+ill2-
Now consider the second part of the lemma. After local averaging, t i. The affected part of the signal contributes to the following first order variability
|w 1112
k:
7
U
ki
ur++ u112
As for the third part of the lemma,
2
|ir+i - 2112 = k k
4r
< k-
Ur ú|12
5
Ur4i
-
where the last incquality is due to AM-QM inequality.
The final part of the proof is the uncentered version of Part and 3, which follows the same steps. In fact, any fixed reference point (for the variability) works, i.., for all e Rdd
We
2112
21122
t=1
T
T
1w - u11
|
u1
1=1
We also another simple lemma.
Lemma D.8. Consider any comparator sequence W.r. For all we have I|ue
rll2 P.
Proof of Lemma D.8. Starting from the definition,
T <T
|lue ūi|l
We u4 ll
and for all i, e [1: 2), 1/ue us < P due to triangle inequality.
D.7 Quantitative example
This subsection presents details of our two quantitative examples, Example and 2.
28

---

Tracking outliers We first calculate the relevant statistics of the comparator u1:r. Note that we assume k I VT, and in this way, there is only small amount of Me with large magnitude, which can then be called outliers.
1
T [
- -T | = ( M 1 - ((VT), - S,
k- (kT)). As for S and
8 == + - +T
$ = - ū) +)+ (T- 1)
2KT (T 11)
- O(KVT).
Intuitively, we have | = (1) while == = while S = (TT). This explains the improvements detailed next. For each algorithm considered Table we evaluate both its switching regret bound and its wath-length-dependee bound.
The minimax algorithm ADER [ZLZ18] is not applicable, as M grows with T and can be larger than any fixed diameter D.
The P-dependent bound of the coarse baseline [JC22, Algorithm 6], c.f. Eq.(3), is
Ô (V
Ö(T).
With P = O(KM), the resulting K K-dependent bound is
ò (MV K)T) = Ö(T).
The P-dependent bound of the fine baseline [JC22, Algorithm 2], c.f., (4), is
δ (V(M + PT5) Ō (T9/1)
With P = O(KM), the resulting K K-dependent bound is
δ (1
O
Our path length bound is
δ ( [ TT + VPS) = Ō (VVK)
Same for our switching regret bound,
δ (10) V V KE = δ (VIT)
Persistent oscillation Again, we calculate the statistics of the comparator 11.7 à = 1, M < 2, K = k. P (k/kV))) Crucially, S = VT and E @(1), while S = O(T) and E = O Here the K K-dependent bounds of the baselines are loose compared to their corresponding Pedependent bounds, due to using the relation P = O K M). Therefore we will only evaluate their P-dependent bounds.
Suppose one knows that M < 2 beforehand, then ADER can be applied with D = 2. The regret bound is
δ ( Ô (VT+ +2/271/44
One could check that the P P-dependent bounds of the coarse and the fine baselines are also
δ ( + P)MT) Ô (VT + 12/21//44
Ô (V(M
(M + PPS) Ô (VT + /2/27///44
For our algorithm, the P-dependent bound is
Ô Vi P$ = δ (VTT)
The K --dependent bound is
ò Ö VT
=
29

---

E Application: Time series forecasting
This section presents an application of our framework in time series forecasting. 15 Roughly speaking, we aim to address the following question:
Given a black box forecaster, can make it provably robust against (structured) nonstationarity?
Along the way, our objective is show that
Simultancously handling unconstrained domains and dynamic comparators in online learning brings downstream benefits in time series forecasting.
Our sparse coding framework can enhance empirically developed forecasting strategies.
Setting Let us consider the following forecasting problem. which resembles the online learning game introduced the beginning of this paper. The difference is that, here, we further assume access to black box forecaster A. each (the t-th) round,
1. The black box forecaster A produces prediction E Rd based on the observed history (#1:1-1 and 11:--)).
After observing a,, we make a prediction Zt E Rd.
3. The environment reveals a true value 2t E IRd and a convex loss function 1 RR - R. le is G-Lipschitz with respect 11- and is one of its minimizer satisfying 4(2)) = 0.
Our goal is to achieve low total loss Eim 4x,)) Since trivially picking x; = a, already achieves
a total loss of Σ/=1 (at), our goal is to improve it in certain situations, by designing a more sophisticated prediction rule based on ag.
Intuition In the above setting, A can be any algorithm that predicts 21.r in a reasonable, but non-robust manner. Taking the weather forecasting for example, there are few notable cases.
a simulator of the governing meteorological equations, which uses the online observations
-1:t-1 as boundary conditions.
A is an autoregressive model, which predicts linear combination of the past observations. The coefficients are determined by statistical modeling.
AA is a large deep learning model trained on offline datasets (e.g., the weather history at geographi- cally similar locations).
Even though such forecasters typically lack performance guarantees, their predictions can be used to construct time-varying Bayesian priors (see our discussion in the Introduction): given ae, will apply a fine- fine-tunin adjustment ò, to predict I, = a, + 8g. Intuitively, the total loss low if ag is close to the true value 2t, i.e., when the prior is good.
Reduction to unconstrained dynamic regret Concretely, if x; - a, + d., then due to convexity, for all subgradients E 04 (xx) we have le(xz) 4 (x,) < (gt, 6,) - (gt, az). The RHS is the instantaneous regret of & an OLO problem with loss gradient 9t and comparator 2N dg Applying unconstrained dynamic OLO algorithm, the total loss in forecasting be bounded
Σ 4(x)) Regret, - (1.T).
That is, the total loss bound adapts to the complexity of the error sequence 21,7 - a1.r (of the given black box forecaster). This contains 01.T 0 as special case, where side information is assumed.
Let compare this bound to the baseline Σ (a.)), which corresponds to trivially picking It az
If 21:7 01.T. i.c. the black box A perfect, then the baseline loss Ers (e(a)) 0. In this case, due to Theorem 4, our general sparse coding framework guarantees -t=1 le(xxe) < eG. where is an arbitrary hyperparameter. That is, our algorithm worse than the baseline by most a constant.
Code available atttps://gtt http:://ggghhub..c////e//ugeeeee
Sparse-Coding
30

---

If 21:T * 41:7, then in general, the baseline loss Σi= (e())) is linear in T. In contrast, our algorithm could guarantee a sublinear Regrety(21:1 d1:T), thus also a sublinear total loss, when the error sequence 21.7 a1.r is structurally simple (e.g., sparse under transform, or low path length) with respect to our prior knowledge.
In summary, the idea is that by sacrificing at most a constant loss when A is perfect (21.T = 01:T), we could robustify A against certain structured unseen environments, improving the linear total loss to sublinear rate.
Importance of unconstrained domain The above application critically relies on the ability of algorithm to handle unconstrained domains. To demonstrate this, suppose we instead use the bounded domain algorithm from [ZLZ18] to pick the fine-tuning adjustment óG. Then, the above analysis only holds if an upper bound D of the maximum error max, || as llly is known priori this is a stringent requirement in practice. Furthermore, when 21:7' = 01.7, such an alternative approach only guarantees Σ 1x(z)) < O(DVT), which is considerably worse than the baseline O. In other words, the alternative fine-tuning strategy could ruin the black box forecaster A, when the latter performs well.
In the rest of this section, present experiments for this time series application. Appendix E.1 demonstrates the power law phenomenon, which shows that both the time series 21:7 and the error sequence 21:7 d1.7 could exhibit exploitable structures. This implies good performance guarantees using our theoretical framework. Appendix E.2 goes one step further by actually testing the fine-tuning performance of our algorithm.
E.1 Power law phenomenon
This subsection further verifies the power law phenomenon discussed in Section 2.2, with both wavelet and Fourier dictionaries. The goal to present concrete examples where signal structures can be exploited by our framework, generating more interpretable, sublinear regret bounds.
Wavelet dictionary We first verify the power law on the Haar wavelet dictionary. Intuitively is suitable when the dynamics of the environment exhibits switching behavior. To this end, consider the following stochastic time series model
4 2₁ 11 + Cr,
(17)
where { and { are iid random variables satisfying Se ~ Uniform(-qe q) and
w.p. P.
3.
w.p. 1 1-p. 1,
Picking T 25 32768.77222 p 0.0005 and g 0.005. generate four sample paths of 21-7 using four arbitrary random seeds (2020, 2021, 2022 and 2023), and the obtained time domain signals are plotted in the first row of Figure 2. As the switching probability p is chosen to be low enough, all the sample paths exhibit a small amount of sharp switches, corrupted by the noise term G. According to our intuition from signal processing, the Haar wavelet transform of these signals is sparse.
Now let us verify this intuition. We take the Haar wavelet transform of these signals, sort the transform domain coefficients and plot the results on log-log scales these are shown the solid blue lines in the second row of Figure 2. Using the largest 100 transform domain coefficients on each plot, we fit a liner model using least square, which is shown the dashed orange line. The slope of each line is -a, where a is displayed in the legend. It can be seen that for all four sample paths, the fitted a is within (0.5, 1), thus justifying the power law phenomenon [Pri21]. Given a, the regret of our Haar wavelet algorithm is Ö(Ti.5-a) as shown in Section 2.2.
As for the implication in time series forecasting, let us consider forecasting E1t with 01.7 = 0, i.e. without the external forecaster A. Given the power law, the total forecasting loss of our fine-tuning approach is Eln (xx))) S O(T...)))
We also remark that although only four sample paths are demonstrated, we observe the power law phenomenon all random seeds we tried in the experiment.
31

---

529
1022 1000
E0HA
(a) Sced= 2020.
(b) Sced= 2021.
(c) Seed= 2022.
(d) Seed= 2023.
Figure 2: Verifying the power law on the Haar Wavelet dictionary. First row: time domain signals. Second row: sorted transform domain coefficients on log-log plot. The dashed orange line is the best linear fit on the log-log plot, using the largest 100 transform domain coefficients. From left to right: four arbitrary random seeds.
Fourier dictionary Next, we verify the power law on the Fourier dictionary. Here we use Jena weather forecasting dataset, 16 which records the weather data at a German city, Jena, every 10 minutes. We take the data from Jan 1st, 2010 till July Ist, 2022, consisting of T 656956 time steps. Two different modalities, namely the temperature and the humidity, considered. The actual temperature and humidity sequences are plotted in Figure
100
Temperabure (*C)
humidity
40
-10
-20
2010
2014
2018
2020
2022
2018
Time
Time
Figure 3: Time domain behavior the weather data.
For the sequence of temperature 21:T, perform its Discrete Fourier Transform (DFT), which returns T complex number as the frequency domain coefficients. We discard the second half of the coefficients due symmetry, since the input of the transform is real. For the remaining coefficients, we take their absolute values, sort them and plot the result on a log-log plot. Similar to the wavelet experiment, also fit linear model using the largest 100 transform domain coefficients. These shown as Figure 4 (Left), which exhibit the power law phenomenon.
Furthermore, we perform the same procedure on the temperature difference sequence { z where the f-th entry the change of temperature from the t-th time step to the + 1-th time step. The result is shown Figure 4 (Right). Although the tail is heavier, can still observe similar power-law phenomenon for large transform domain coefficients.
Now, let discuss again the implication of the observed power law in time series forecasting, First, consider forecasting 21.r without A. Given the power law of 21:T itself, the Fourier version of our forecaster guarantees sublinear total loss. Next, consider forecasting zeroth-order hold forecaster, i.c, a; = žt-1- The power law of the difference sequence { - 2.} implies good forecasting performance of our framework in this context.
with A being the
Available https: //wp///ww//////// http///www...aaoeee/eee///e bgc-jenna jaaneejnna...p..... de/vette/
32

---

Data
Data
Fourier coeficiens (abs, log)
Fittdd, 2-0.68
Fiteed d-
Fourler coefticlens diff
204
102
10?
10
10a
10a
10a
10a
10a
10
102
10a
10a
10
10a
10
102
Indi (log)
(log)
Figure 4: Verifying the power law the Fourier dictionary. Left: the DFT of the temperature sequence. Right: the DFT of the temperature difference sequence.
Parallel results on the humidity sequence are reported in Figure 5, with a similar qualitative behavior. illustrates the prevalence of the power law across different types of the data.
Data
coefricents diff looi
10
Data Fitted,
Fourler coefriclens (abs, log)
Fitted,
104
103
10a
10a
104
10a
10a
10a
10
10
10"
10
10"
10
cedices (log)
Indices (log)
Figure 5: Verifying the power law on the Fourier dictionary. Left: the DFT of the humidity sequence. Right: the DFT of the humidity difference sequence.
E.2 Fine-tuning forecaster
Finally, we test the performance of our forecasting framework on the synthetic switching data and the actual temperature sequence. For the first case, framework is equipped with the Haar wavelet dictionary. The Fourier dictionary is adopted the second case. In both cases, we compare our algorithm against the baseline from [JC22]. More specifically,
take online learning algorithm (Algorithm 2) and the algorithm from [JC22], plug them both into the time series forecasting workflow introduced at the beginning of this section, and then compare their total forecasting loss.
Concretely, us start from the wavelet dictionary.
Wavelet dictionary this case, consider the setting without the external forecaster A. We run both online learning algorithms (our Algorithm and the bascline [JC22, Algorithm 2)), and use their outputs directly as the time series predictions. Our Algorithm is equipped with the Haar wavelet dictionary defined in Section 3.1. The configurations of the time series model are the same as the previous subsection, with T = 215 = 32768, = 0.0005 and g = 0.005. The loss functions I are the absolute loss.
Both algorithms require confidence hyperparameter e, and we set 1. Since the time series data (17) is random, we run both algorithms on 10 random seeds, and calculate their total loss. Our algorithm achieves total loss of 44048, which is considerably lower than the baseline's 's total loss 62465. This is consistent with the thcoretical results developed so far.
33

---

Fourier dictionary Next, we turn to the task of temperature forecasting. The data is reported in the previous subsection. We take its first 50000 entries, and assign the true time series &1.7i the loss functions 4 are the absolute loss. The black box forecaster A is assigned to the zeroth-order hold forecaster, i.e., 02 2t-1-
For our framework, we need to specify the dictionary. Although using the entire DFT matrix could lead low regret guarantees (as demonstrated by the power law), this computationally challenging. Instead, we exploit the fact that the weather is naturally periodic, with the period of one day. Picking the base frequency w accordingly, we define features indexed by & (the harmonic order) as
1 = cos(kut).
14,24 sin(kwt).
By specifying the maximum order K, we obtain 2K features (h+,2x-1, 24.24 1 [keliK]] from this construction. An all-one feature is further added, making the dictionary size N 2K +1
Again, we the confidence hyperparameter ε 1 for algorithm. The total loss as function of the dictionary size N is plotted in Figure 6. Notably, the case of N = 0 is equivalent to trivially following the advice the given forecaster A: 2, a₂ zt-1. can be seen that our fine-tuning framework (N > 0) actually results in better performance, due to exploiting the structures in the error sequence 21:T 01:T-
1e3
8.2
8.0
7.8
Total
7.6
7.4
7.2
3
Number of features
Figure 6: Testing our algorithm for temperature forecasting.
We also test the fine-tuning performance of the algorithm from [JC22]. Same as the above, we set The total loss achieved by this alternative algorithm 8238, which is around the same A itself, and significantly higher than the total loss our algorithm with moderate amount of features (N 5). This fits the intuition from this paper: the environment contains persistent dynamics, which the algorithm from [JC22] cannot handle.
Additional discussion
MRA in online learning On a broader scope, wavelets embody the idea of Multi-Resolation Analysis (MRA), which reminiscent of the classical geometric covering (GC) construction in adaptive online learning [DGSS15]. Such a construction starts from a class of GC time intervals, which are equivalent the support of Haar wavelet features. On each GC interval, a static online learning algorithm is defined (corresponding to using an all-one feature, c.f., Section 2.2); and then, the outputs of these "local" algorithms are aggregated by a sleeping expert algorithm on top [LS15, JOWW17J. Algorithmically. our innovation is introducing sign changes in the features, accompanied by a different, additive way to aggregate base algorithms. For tackling nonstationarity, both approaches have their own strengths: the GC construction can produce strongly adaptive guarantees on subintervals of the time horizon, while our algorithm does not need bounded domain. Their possible connections are intriguing.
34

---

Lipschitz vs strongly convex losses We also comment on the choice of loss functions in uncon- strained dynamic OCO. Besides the Lipschitz assumption we impose, fruitful line of works by Baby and Wang [BW19, 19, BW20, BW21, BZW21, BW22] considered an alternative setting with strong convexity, motivated by the prevalence of the square loss statistics. Their focus is primarily on bounded domains, as [BW19] showed that evaluated under the square loss, lower bound for the unconstrained dynamic regret is ). A sublinear regret bound here requires P = ol ((VT), rather than P = o(T) with Lipschitz losses that is, the environment is required to be "more static" than the typical requirement in the Lipschitz setting.
Essentially, such behavior due to the large penalty that the square loss imposes on outliers. An adversary in online learning can deliberately pick the loss functions such that some of the player's s predictions are large outliers with "huge" (square) losses, while the offline optimal comparator sequence suffers zero losses. Using the Lipschitz losses instead may offer an advantage on unbounded domains, due to being more tolerant these outliers. Furthermore, Lipschitz losses not necessarily have minimizers this is useful for decision problems (as opposed to estimation), where ground truth may not exist." 17
Future work For future works, several interesting questions could stem from this paper. For example,
Our regret bound is stated against individual comparator sequences. One could investigate the implication of this result in stochastic environments, where the comparator statisties may take more concrete forms.
Besides the sparsity and the energy studied in this paper, interesting open problem is investigating alternative complexity measures of the comparator, possibly drawing connections to statistical learning theory.
Our framework builds pre-defined dictionary inputs. The quantitative benefit of using data- dependent dictionary is unclear.
Beyond wavelets, one may investigate the combination of the sparse coding framework with other function approximators, such as neural networks.
17 An example is financial investment without budget constraints: doubling the invested amount also doubles
the return.
35


Reviews:
[{"review_id": "FwGO1MANug", "reviewer": "Reviewer_qkG5", "summary": "This paper studies the universal dynamic regret minimization problem with the unconstraint decision domain. The authors proposed the sparsing coding framework, which converts the dynamic regret minimization problem in the time domain into a static regret minimization problem in the transfer domain. The comparator-adaptive static regret bound in the transfer domain implies a dynamic regret bound in the time domain. Specifically, by choosing the dictionary as the Haar wavelet base, this paper achieves improved dynamic regret bound with better dependence on the range of the comparator sequence. Several concrete examples are provided to illustrate the superiority of the proposed bound.", "questions": "- could you provide more concrete examples to illustrate the superiority of the proposed bound? (please refer to the second point of the weakness for more details)\n- is it possible to achieve the $\\tilde{O}\\left(\\Vert \\bar{u}\\Vert\\sqrt{T}+\\sqrt{P\\bar{S}}\\right)$ bound without the knowledge of $T$. Could you highlight what is the main difference to obtain such a bound?", "limitations": "One of the main limitations of the paper is that the tightness of the proposed bound is still unclear. The authors discuss this issue at the end of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper provides a novel framework to obtain universal dynamic regret bound via sparsing coding. The conversion from comparator-adaptive static regret bound to dynamic regret bound in the time domain is interesting to me.\n+ This paper achieves improved universal dynamic regret bound with the new framework, which is strictly better than the existing results. Several examples are provided to illustrate the advantages of the proposed bound.\n+ This paper is well-written and provides a sufficient discussion of the related literature.", "weaknesses": "I do not find a major weakness in the paper, but there are still some minor comments:\n\n- about the general formulation (Eq. (5)): it would be nice to mention that the dynamic regret bound (Eq.(5)) is not universal dynamic regret bound in general as it only holds for the comparator $u_{1:T}\\in\\mbox{span}(h_{1:T})$. The universal dynamic regret bound can only be achieved with an appropriate choice of the dictionary.\n\n- about the examples: this paper has listed several examples with the specific choice of the comparator sequence to show the superiority of the proposed bound. However, since the main focus of this paper is the universal dynamic regret, it is unclear in which situation the listed comparator sequence is an appropriate benchmark that can minimize the right-hand side of Eq (2). I suggest the authors provide more concrete examples to illustrate the advantage of the proposed bound with certain specific loss functions.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and your support of our paper! \n\n- Clarification on Eq.(5).\n\nThanks for the suggestion, we will add the remark that the bound holds for $u_{1:T}$ in the span of the feature vectors. \n\n- Example of the loss functions.  \n\nThe question is on whether there exist loss functions $l_{1:T}$ such that the comparators $u_{1:T}$ from Example 1 and 2 are actually good comparators with low cumulative loss. This is a great point, and let us use time series forecasting as an example (Appendix E). \n \nConsider the true time series $z_{1:T}$ being the sequences from our Example 1 and 2, and the loss functions in OCO are the absolute loss, $l_t(x)=|x-z_t|$. As the comparator sequence, the true time series $z_{1:T}$ suffers zero loss, therefore the total loss of our OCO algorithm is upper bounded by its regret bound with respect to $z_{1:T}$. In this case, our improved regret bound over [JC22] translates to a smaller total loss bound. \n\nEssentially, this example shows that the *restricted dynamic regret bound* obtained from our universal bound improves the one obtained from [JC22]. Such an argument is a relaxation of the oracle inequality Eq.(2), and a natural next step is to directly characterize the infimum on the RHS there. To our knowledge, this is a less studied topic within comparator adaptive online learning, which could be a good direction for future works.\n\n- Anytime $\\tilde O\\left(||\\bar u||_2\\sqrt{T}+\\sqrt{P\\bar S}\\right)$ bound\n\nThis can indeed be achieved from our core fixed-$T$ result, which we realized after the submission. Details are the following. We will add this small improvement to the camera ready version. \n\nIn our current proof, we have (line 801 and 802),\n\n$\n\\mathrm{Regret}(u_{1:T})\\leq \\tilde O\\left(\\sum_{m=1}^{m^*}||\\bar u_m||_2\\sqrt{2^m}\\right)+\\tilde O\\left(\\sqrt{P \\bar S}\\right).\n$\n\nFor the first sum on the RHS, same as our proof of Theorem 2 (line 722 to 727),\n\n$\n\\sum_{m=1}^{m^*}||\\bar u_m||_2\\sqrt{2^m}\\leq \\tilde O\\left(||\\bar u||_2\\sqrt{T}+\\sqrt{\\bar E}\\right).\n$\n\nThe remaining task is to show that $\\sqrt{\\bar E}$ is dominated by $\\sqrt{P\\bar S}$, thus can be combined into the later. Plugging in their definitions, it suffices to show that for all $t$, $||u_t-\\bar u||_2\\leq P$. This follows from\n\n$\n||u_t-\\bar u||_2 \\leq T^{-1} \\sum_i ||u_t-u_i||_2\\leq \\max_i ||u_t-u_i||_2,\n$\n\nand for all $i,t\\in[1:T]$, $||u_t-u_i||_2\\leq P$. "}, {"review_id": "B6KOsAaZdP", "reviewer": "Reviewer_45WG", "summary": "In this paper, the authors examine the dynamic regret of Online Convex Optimization (OCO) within the context of unbounded comparator sequences. To address this issue, they introduce a novel framework of sparse dictionary coding for online optimization. Following this, the authors provide theoretical proof for the regret bounds applicable to different types of dictionary matrices - the general dictionary matrix, orthogonal dictionary matrix, and the Haar wavelet dictionary matrix. Of notable mention is the result pertaining to the Haar wavelet dictionary matrix, where the authors establish a regret bound that surpasses the current state-of-the-art.", "questions": "See above discussions.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Originality & Significance: The introduction of the sparse coding framework for Online Convex Optimization (OCO), complemented with the corresponding proof, is highly innovative. Furthermore, considering the dynamic regret of OCO in the unbounded domain is very crucial. The result that the authors obtained is related to the comparator average, first-order variability, and second-order variability, rather than the path length. This indicates that the authors have achieved smaller dynamic regret under more adaptive conditions, thereby enriching optimization theory within the community.  \n- Quality & Clarity: The work is clear, well written, and technically sound.", "weaknesses": "- Comparing the proposed method with the meta-expert optimistic online gradient descent method as described in [1] could be beneficial. Particularly in Examples 1 and 2, it appears that the meta-expert optimistic online gradient descent method can also achieve a regret of $\\mathcal O(\\sqrt T)$, considering the path-length is actually $\\mathcal O(\\sqrt T)$. This comparison might offer a broader perspective.\n\n- I'm concerned about the computational complexity of $\\mathcal O(d\\log T)$ for high-dimensional problems, especially when compared to the $\\mathcal O(\\log T)$ complexity of both the meta-expert OGD and the meta-expert optimistic OGD methods. If possible, an in-depth discussion on this issue would be helpful for readers.\n\n- Additionally, the main text seems to miss Algorithms 3-5. This omission may cause a minor confusion for readers during their first read. Rectifying this could help in enhancing the flow and clarity of the paper.\n\nRef: [1] P Zhao et.al., Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and your support of our paper! \n\n- Related work [1]\n\nThanks for bringing it to our attention. Both [1] and our paper study how to achieve more adaptivity in dynamic online learning, but they take different directions. For example, [1] has an additional smoothness assumption, therefore the quantitative results are not directly comparable to ours. We'll discuss this related work in the camera ready version.  \n\n- Computational complexity of meta-expert OGD\n\nIt's possible that we missed its latest improvement: to our knowledge, the meta-expert OGD baseline [Ader, ZLZ18] also runs in $O(d\\log T)$ time per round right? There are $O(\\log T)$ base algorithms running in parallel, and each of them is OGD in $\\mathbb{R}^d$ which runs in $O(d)$ time per round. \n\n- Finally, thanks for the suggestions on the organization of this paper. "}, {"review_id": "vVLI5416aK", "reviewer": "Reviewer_pdGo", "summary": "The problem that this paper tries to tackle is the unconstrained online convex optimization with dynamic regret. Previous works usually assume that the comparator sequence is arbitrary and maybe time-varying with some fixed form of comparator measurement in the final dynamic regret bound. For this paper, it proposes a new way of the comparator measurement by first using a pre-defined subspace (by the users) to characterize the comparator sequence and then upper bound the dynamic regret in terms of the pre-defined subspace complexity as well as the reconstruction error between the subspace and the comparator sequence. It shows that for the almost static environment, the proposed algorithm + wavelet constructed subspace could have better regret than the existing works' in (maybe) the constant part. ", "questions": "1) The proposed algorithm requires the user to provide the subspace, which is very critical for the final dynamic regret result. If the user provided subspace is not good enough, does that mean the resulted algorithm will have bad performance? If so, how to guarantee the performance?\n2) Since the proposed algorithm depends on the Algorithm 3 a lot, do you think it may make more sense to move Algorithm 3 from the Appendix to the main paper?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) It provides the researchers a new perspective of measuring the comparator sequence when upper bounding the dynamic regret, which is interesting and useful in real applications.\n2) The specific wavelet based subspace version could result in a regret better than the existing works' with (maybe) smaller constant part.", "weaknesses": "1) The proposed algorithm framework only moves the dynamic regret from previous works in the constant value part. And in order to compare the actual improvement in terms of the constant part, the author/s need to provide the complete regret result comparison instead of an order O() based one.\n2) The paper result depends heavily on the existing work [MK20], and the subspace based comparator sequence measurement is the only part that makes it interesting, although previous works like [HW15, ZLZ18] has already shown such an idea as pointed out by the author/s.\n3) The author/s explained the motivation of tackling unconstrained dynamic setting rather than the constrained one. But for the finite range argument in the paper, more often than not, the finite range usually comes from the requirement of the model output and not just some heuristic estimation. I think it's better to also provide some examples to demonstrate the motivation of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! \n\n- Improvement over [JC22].\n\nWe would like to respectfully clarify that compared to [JC22], our bound depends on a tighter complexity measure of the comparator sequence $u_{1:T}$. Such an improvement is considerably more substantial than improving the multiplicative constant of the conventional minimax regret bounds. In fact, multiplicative constants and logarithmic factors are omitted in our analysis. Example 1 and 2 demonstrate improvements on the *exponent* of $T$, rather than multiplying factors. \n\n- Dependence on [MK20]\n\nOur framework is actually very general: any static comparator adaptive OCO algorithm can be applied to replace [MK20], such as [MO14, OP16, CO18]. We only adopt [MK20] as an illustrative example. \n\n- Difference with [HW15, ZLZ18]\n\nAs discussed in the paper, our framework is fundamentally different from [HW15, ZLZ18], as we use *linear combinations* of the side information, rather than *convex combinations*, to approximate the comparator sequence. This is the key reason behind its success, as it leads to natural connections to linear transforms, one of the most fundamental ideas of signal processing. \n\nBesides, we would like to argue that despite bearing a natural idea, the analysis in this paper is a nontrivial one, and the strength of the wavelet result is quite surprising in our opinion. \n\n- Bounded domain setting\n\nIf we are given a bounded domain, then there is a useful projection technique [Section 4, Cut20] that converts an unconstrained algorithm to a constrained one, without changing its regret bound. Therefore, our unconstrained dynamic regret bound also improves the standard bounded domain dynamic regret bound from [ZLZ18], modulo logarithmic factors. \n\nMoreover, Appendix E discusses an application in fine-tuning time-series forecasters, which quite naturally motivates our unconstrained setting (due to its enhanced adaptivity). The relevant discussion is line 903 to 915. \n\n- Dependence on the quality of the dictionary\n\nIndeed, the performance of our generic framework depends on the quality of the dictionary. The rationale is a classical and natural one: without a good inductive bias from the dictionary, we cannot compete with a benchmark that \"knows the future''. In a consistent manner, all the existing dynamic regret bounds are trivially $O(T)$ in their worst case. \n\nWith this, the main strength of our framework is its versatility: it is strictly more general than existing approaches without dictionaries. One could always pick the Haar wavelet dictionary, which leads to better quantitative bounds than the baselines, in almost static environments. "}, {"review_id": "xpfAT3d1Yu", "reviewer": "Reviewer_4s3X", "summary": "This paper studies adaptive online convex optimization, with focus on adapting to unbounded domain and arbitrary time-varying comparator sequence. Different from previous studies which mostly consider the path-length as the prior which appears in the dynamic regret bound, this paper aims to enlarge the range of priors. For a given dictionary of orthogonal feature vectors, it is shown that an $\\tilde{O}(\\sqrt{E\\cdot \\text{Sparsity}_H})$ regret bound can be achieved, which not only recovers previous results on path-length, but also allows more flexibility. This paper also strictly improves the result of JC22 by replacing comparator-dependent terms in the regret bound by strictly smaller ones.", "questions": "Can you provide more technical details to address my questions discussed above? In particular, can you provide 1: an example of dictionary that recovers the traditional path-length case, and 2: an example of dictionary that corresponds to some other prior different from path-length?\n\nCan you provide details on using the Fourier dictionary to tackle periodic environments? It looks interesting to me because the naive idea of setting $H_t=(-1)^t I_d$ won't work.", "limitations": "The presentation of technical results is not very clear.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper makes solid contributions to adaptive online convex optimization. It extends the scope of comparator adaptivity from the traditional path-length, to other priors on the comparator via a novel sparse coding framework. The achieved bounds involve more refined dependence on the comparator, and are never worse than previous results. In particular, the special case of the wavelet dictionary improves the SotA result in JC22.", "weaknesses": "The main weakness is the unclear presentation of technical results, which are hard to fully understand and interpret. Though the claimed results seem promising, I have to vote for rejection for now because I can't verify the correctness without a better understanding of the results. Here are some confusions I met.\n\nFor the size 1 dictionary case, isn't the assumption too strong which seems to trivialize Lemma 2.1? In line 211, the comparator is assumed to lie in the span of a single vector $h_{1:T}$, which is just a scaling of the vector $h_{1:T}$. Since the dictionary is fixed and revealed to the player, the range of potential comparators seems very restricted (the degree of freedom is just one through $\\hat{u}$).\n\nThe same issue carries over to the main result Theorem 1, which assumes the signal $z^{(n)}$ lies in the span of a single vector. Even if the reconstruction error creates certain flexibility, to achieve vanishing regret one still needs to guarantee the comparator is very close to $\\sum_{n=1}^N z^{(n)}$, which seems under-expressive: for a given dictionary, the overall degree of freedom is just $n$, while for arbitrary time-varying comparators the degree of freedom is $dT$.\n\nTwo examples are presented right after the main theorem. The case of static regret is well understood. However, I feel the case of orthogonal dictionary requires more technical details, at least to readers unfamiliar with signal processing. For example, what exactly does the \"orthogonal\" means here? (which vector is orthogonal to which?) It would be great if you can provide an intuitive example here to show the power of your method over previous results.\n\nI'm also concerned with how to choose the dictionary. It seems a good choice of dictionary requires prior knowledge. It's not clear to me if one can adapt to a class of dictionaries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments! We hope the following clarifications can answer your questions. \n\n- Interpretation of the generic framework\n\nOur generic framework aggregates a collection of single-feature learners. Roughly speaking, each of these single-feature learner is in charge of a fixed direction in the sequence space $\\mathbb{R}^{dT}$. Aggregating them means assembling these fixed directions into a subspace in $\\mathbb{R}^{dT}$, which the comparator sequence $u_{1:T}$ belongs to. \n\nTo recover static online learning, we need $N=d$ feature vectors. The dynamic setting is more challenging: in Theorem 1, if we want to completely eliminate the reconstruction error term $z^{0}$, then we have to use $dT$ feature vectors. As mentioned in your comment, this means setting $N=dT$. \n\nYou may wonder if this procedure is computationally efficient, since there are now $dT$ simple learners to aggregate. This is the reason why we focus on the wavelet dictionary in the second part of the paper: among the $O(T)$ simple learners, only $O(\\log T)$ of them are active in any given round, therefore computationally their aggregation is not so expensive. \n\n- Meaning of \"orthogonal\" and example\n\n\"Orthogonal dictionary\" in this paper means that we consider a dictionary matrix $\\mathcal{H}\\in\\mathbb{R}^{dT\\times N}$ whose columns are orthogonal. An example is the Haar wavelet dictionary, e.g., Eq.(8).\n\nTo recover (and improve) traditional path-length bounds, we can use the Haar wavelet dictionary. \n\nFor a different inductive bias, the Discrete Fourier Transform (DFT) matrix is useful for periodic environments. Besides, the Daubechies wavelet family is a generalization of the Haar wavelet suitable for piecewise smooth environments. \n\n- How to choose the dictionary, and adaptivity\n\nThe choice of the dictionary relies on (Bayesian) prior knowledge of the environment, which is a key idea of adaptive online learning, and machine learning in general. For *any* dynamic OCO algorithm, if the environment behaves very differently from the inductive bias of the algorithm (e.g., the environment is periodic, but the algorithm guarantees a path-length-based bound), then its performance cannot be good. Our framework is not an exception. \n\nMeanwhile, it is indeed possible to \"adapt\" to the best dictionary in a certain category: given a collection of dictionaries, we can perform almost as if we know beforehand which dictionary is the best one. This is explained in our line 251 to 257. The idea is to simply combine all the dictionaries into a mega-dictionary, and run our framework verbatim. The dictionary-selection property follows from some nice behaviors of static comparator-adaptive online learning. Achieving this task without using the mega-dictionary is an interesting open question. \n\n- Fourier dictionary\n\nFor periodic environments, the most natural idea is to use the Discrete Fourier Transform (DFT) matrix as the dictionary. The limitation is that the DFT matrix is dense itself, therefore computationally, this approach needs to aggregate $dT$ simple learners per round, which is computationally challenging. \n\nIn practice, a more appealing approach is to use a smaller dictionary defined from a base frequency and its low order harmonics. Specifically in the one-dimensional setting, given a base frequency $\\omega$ and a maximum order $K$, we define two features for all $k\\leq K$: the first has per-round component $h_t=\\cos(k\\omega t)\\in\\mathbb{R}$, and similarly, the second is $h_t=\\sin(k\\omega t)$. The base frequency $\\omega$ is often determined by the natural periodicity of the environment, e.g., the weather and the traffic flow are roughly daily periodic. Details and supporting experiments are presented on the last page of the appendix. In the weather forecasting experiment, using a moderate amount of features ($K>3$) suffices, which quite significantly outperforms the baseline from [JC22]."}]

Author rebuttal:

Meta-review: This paper proposes an algorithmic framework for minimizing unconstrained dynamic regret. Unlike existing methods that depend on the path length, the dynamic regret of the proposed method depends on both the energy of the comparator sequence, and its sparsity with respect to a dictionary. In the special case where the dictionary is a Haar wavelet dictionary, this framework gives better dynamic regret bounds than previous state-of-the-art. During the discussion, the novelty of the framework and the use of the sparse coding perspective in online convex optimization is appreciated. Even though there is some concern around the practicality of the framework in the general case, the improvements in special cases is interesting and show the promise of this new approach. I recommend acceptance.
Decision: Accept (poster)