Efficient Methods for Non-stationary Online Learning
Authors: Peng Zhao
Yan-Feng Xie
Lijun Zhang
Zhi-Hua Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: non-stationary online learning
dynamic regret
adaptive regret
online ensemble
projection complexity

Abstract: Non-stationary online learning has drawn much attention in recent years. In particular, \emph{dynamic regret} and \emph{adaptive regret} are proposed as two principled performance measures for online convex optimization in non-stationary environments. To optimize them, a two-layer online ensemble is usually deployed due to the inherent uncertainty of the non-stationarity, in which a group of base-learners are maintained and a meta-algorithm is employed to track the best one on the fly. However, the two-layer structure raises the concern about the computational complexity--those methods typically maintain $O(\log T)$ base-learners simultaneously for a $T$-round online game and thus perform multiple projections onto the feasible domain per round, which becomes the computational bottleneck when the domain is complicated. In this paper, we present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $O(\log T)$ to $1$.  Moreover, our obtained algorithms require only one gradient query and one function evaluation at each round. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods. Empirical studies verify our theoretical findings.


Efficient Methods for Non-stationary Online Learning
Peng Zhao, Yan-Feng Xie, Lijun Zhang, Zhi-Hua Zhou National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing, China {zhaop, xieyf, zhanglj, zhouzh}&l alandaaaammm..mmmmmmmmmm jju. edu. cn
Abstract
Non-stationary online learning has drawn much attention in recent years. In particu- lar, dynamic regret and adaptive regret proposed two principled performance measures for online convex optimization in non-stationary environments. To opti- mize them, two-layer online ensemble is usually deployed due to the inherent uncertainty of the non-stationarity. in which a group of base-learners are maintained and meta-algorithm is employed to track the best one the fly. However, the two-layer structure raises the concern about the computational complexity - those methods typically maintain Olog 7') base-learners simultaneously for 7-runnd online game and thus perform multiple projections onto the feasible domain per round, which becomes the computational bottleneck when the domain is compli- cated. In this paper, we present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from Olog T) to 1. Moreover, our obtained algorithms require only one gradient query and one function evaluation at each round. Our technique hinges on the reduction mecha- nism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods. Empirical studies verify our theoretical findings.
Introduction
Classic online learning minimizes the static regret, which benchmarks the online learner's perfor- mance against the best fixed decision in hindsight. In many real-world online applications, however, the environments are non-stationary [Zhou, 2022] and static regret becomes less attractive since would be unrealistic to assume the existence of single decision behaved satisfactorily over time.
To address the limitation, in recent years, researchers have studied more strengthened performance measures to facilitate online algorithms with the capability of handling non-stationarity. In particular, dynamic regret [Zinkevich, 2003; Zhang et al., 2018al 8a] and adaptive regret [Hazan and Seshadhri, 2009; Daniely et al., 2015) are proposed as two principled metrics to guide the algorithm design. We focus on the online convex optimization (OCO) setting [Hazan, 2016]. OCO can be deemed as a game between the learner and the environments. At each round t E [2]] the learner submits her decision X, E X' from a convex feasible domain X' C Rd and simultaneously environments choose a convex function fi X IR, and subsequently the learner suffers instantancous loss fx;).
1.1 Dynamic Regret and Adaptive Regret
Dynamic regret is proposed by Zinkevich [2003] to compare the online learner's performance against a sequence of any feasible comparators ui.... ur X. Formally, it is defined as
T
T
D-REGT(U,,... ur) = Σ fx())) Σ fe(we)
(I)
1=1
t=1
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Dynamic regret minimization enables the learner to track changing comparators. A favorable dynamic regret bound should scale with a certain non-stationarity measure dependent on the comparators such as the path length Pr = Σ Un - l12. Notably, the classic static regret can be treated as special case of dynamic regret by specifying the comparators as the best fixed decision in hindsight.
Adaptive regret is proposed by Hazan and Seshadhri [2009] and further strengthened by Daniely et al. [2015], which measures the regret over any interval [r, S [T] with a length of = i... i.e.
r+r-1
14--1 f
max A- A-REGT(14)) [M----- -
Σ f((x) min DEX
Σ
(2)
Since the minimizers of different intervals can be different, adaptive regret minimization also ensures the capability of competing with changing comparators. A desired adaptive regret bound should be as close as the minimax static regret of this interval. Algorithms with adaptive regret matching static regret of this interval up to logarithmic terms in T are referred to strongly adaptive [Daniely et al., 2015]. Moreover, adaptive regret includes static regret when choosing 1 [2].
It is worth noting that the relationship between dynamic regret and adaptive regret for OCO is generally unclear [Zhang, 2020, Section 5], even though a black-box reduction from dynamic regret to adaptive regret has been proven for the simper expert setting (i.e., online linear optimization over simplex) [Luo and Schapire, 2015, Theorem 4]. Hence, the two measures are separately developed and many algorithms have been proposed, including algorithms for dynamic regret [Zinkevich, 2003; Hall and Willett, 2013; Zhang et al., 201 8a; Zhao et al., 2020, 2021b,a; Baby and Wang, 2021; Zhao et al., 2022a] and the ones for adaptive regret [Hazan and Seshadhri, 2009; Daniely et al., 2015; Jun et al., 2017: Zhang et al., 201 8b, 2019]. Note that there are also studies [Zhang et al., 2020; Cutkosky, 2020] optimizing both measures simultaneously by an even strengthened metric E fx(xx) - Di., fi())) over any interval [r, s] S [T], hence called "interval dynamic regret".
1.2 Two-layer Structure and Projection Complexity Issue
The fundamental challenge of optimizing these two non-stationary regret measures is the uncertainty of the environmental non-stationarity. Concretely, to ensure the robustness to the unknown envi- ronments, dynamic regret aims to compete with any feasible comparator sequence, while adaptive regret examines the local performance over any intervals. The unknown comparators or unknown intervals bring considerable uncertainty to online optimization. To address the issue, a two-layer structure is usually deployed to optimize the measures, where a set of base-learners are main- tained handle the different possibilities of online environments and a meta-algorithm is employed to combine them all and track the unknown best one. Such a framework successfully achieves many state-of art results, including the O(VT(1+ + Pr)) dynamic regret [Zhang et al., 201 8a] and the (( + P1) + Pr)) small-loss dynamic regret for smooth functions [Zhao al., 2020], where Pr = Σ |1 - u,-1112 is the path length and Fr = -E fe(u,) is the cumu- lative loss of comparators;
adaptive regret [Jun et al., 2017] and the O(VF, log F, log FT)) small-loss adaptive regret for smooth functions [Zhang et al., 2019] for any in- terval / = [r. s] C [T]. where F, minxxx Ei=r fr( [x() and Fr minxex Σ fx(x). Besides, an (V (log T + Pr)) interval dynamic regret is also achieved by a two-layer (or even three-layer) structure [Zhang et al., 2020], where P1 = Di Iu u llz is the path length over the interval.
well as the O D(V17
The two-layer methods have demonstrated great effectiveness in tackling non-stationary online envi- ronments, whereas the gain is the price of heavier computations than the methods for minimizing static regret. While it is believed that additional computations are necessary for more robustness, we are wondering whether is possible to pay for a "minimal" computation overhead for adapting to the non-stationarity. To this end, we focus on the popular first-order online methods and aim to streamline unnecessary computations while retaining the same regret guarantees. Arguably, the most computationally expensive step of each round is the projection onto the convex feasible domain, namely, the projection operation Ix] arg min minxexxlxx yll for convex set X C Rd. Typical two-layer non-stationary online algorithms require maintaining N = O(log T' base-learners simulta- neously to cover the possibility of unknown environments. Define the projection complexity of online methods as the number of projections onto the feasible domain per round. Then, those non-stationary methods suffer an Olog 7' projection complexity, whereas standard online methods for statie regret minimization require only one projection per round such online gradient descent [Zinkevich, 2003].

---

1.3 Our Contributions and Techniques
In this paper, we design a generie mechanism to reduce the projection complexity of many existing non-stationary methods from (log to 1 without sacrificing the regret optimality, hence matching the projection complexity of stationary methods. Our reduction is inspired by the recent advance in parameter-free online learning [Cutkosky and Orabona, 2018; Mhammedi et al., 2019]. The idea is simple: we reduce the original problem learned in the feasible domain X' to an alternative one learned in surrogate domain Y' 2 X' such that the projection onto it is much cheaper, e-g., simply choosing Y' as a properly scaled Euclidean ball; and moreover, a carefully designed surrogate loss is necessary for the alternative problem retain the regret optimality. We reveal that necessary condition for our reduction mechanism to deploy and reduce the projection complexity is that the non-stationary online algorithm shall query the function gradient once and evaluate the function value once per round. Several algorithms for the worst-case dynamic regret or adaptive regret already satisfy the requirements, so we can immediately deploy the reduction and obtain their efficient counterparts with the same regret guarantees and 1 projection complexity. However, many -on-ttationary algorithms, partieularly those designed for small-loss bounds, not satisfy the requirement. Hence, we require non-trivial efforts to make them compatible. Due to this, we have developed a series of algorithms that achieve corst-case/smallloos dynamic regret and adaptive regret with one projection per round (actually, with one gradient query and one function evaluation per round well).
Despite that the reduction mechanism of this paper has been studied in parameter- online learning, applying it to non-stationary online learning requires new ideas and non-trivial modifications. Here we highlight the technical innovation. The main challenge comes from the reduction condition mentioned earlier- - as the surrogate loss involves the projection operation, our reduction requires the algorithm query one gradient and evaluate one function value at each round. However, many non- stationary algorithms do not satisfy the requirement, which is to be contrasted to the parameter-free free algorithms such as MetaGrad [van Erven and Koolen, 2016; Mhammedi et al., 2019] that naturally satisfy the condition. For example, the SACS algorithm [Zhang et al., 2019] enjoys the best known small-loss adaptive regret, yet the method requires N gradient queries and N + function evaluations at each round, where N = Olog 7') is the number of base-learners. Thus, we have to dig into the algorithm and modify it to fit our reduction. First, we replace their meta-algorithm with Adapt-ML.- Prod [Gaillard et al., 2014], an sxpert-tracking algorithm with second-order regret with excess losses to accommodate the lincarized loss that is used to ensure one gradient query per round. Second, we introduce sequence of time-varying thresholds to adaptively determine the problem-dependent geometric covers in contrast to a fixed threshold used in their method. In particular, we register the cumulative loss of the final decisions rather than the base-learner's one to compare it with the changing thresholds, which renders the design of one function value evaluation per round and also turns out to be crucial for achieving an improved small-loss bound that can recover the best known worst-case adaptive adaptive regret (by contrast, SACS cannot obtain optimal worst-case adaptive regret). To summarize, our final algorithm only requires one projection//radient query/function evaluation at each round, substantially improving the efficiency of SACS algorithm that requires N projections/gradient queries/function evaluations per round.
1.4 Assumptions
We list several standard assumptions used in OCO [Shalev-Shward 2012; Hazan, 2016]. Notably, not all assumptions are always required. We will explicitly state the requirements in the theorem.
Assumption 1 (bounded gradient). The norm of the gradients of online functions over the domain X is bounded by G. i..., (x))ll) S G, for all x E X' and & E [T].
Assumption 2 (bounded domain). The domain X C Rd contains the origin 0, and the diameter of the domain X' is at most i.i..., ||x - x'112 < D for any x, EX
Assumption 3 (non-negativity and smoothness). All the online functions are non-negative and L-smooth, i.c., for any x, x' X' and t [T'. fi (x'))la < L L||x x -
Organization. The rest is structured as follows. Section 2 presents the reduction mechanism and illustrates its application to dynamic regret minimization. Section 3 provides efficient methods for optimizing adaptive regret. Section reports the experiments. Section 5 concludes the paper and makes discussions. All the proofs and omitted details for algorithms are deferred to the appendices.
3

---

2 The Reduction Mechanism and Dynamic Regret Minimization
We start from the dynamic regret minimization. First, we briefly review existing methods in Sec- tion 2.1, and then present our reduction mechanism and illustrate how to apply it to reducing the projection complexity of dynamic regret methods in Section 2.2.
2.1 A Brief Review of Dynamic Regret Minimization
Zhang et al. [2018a] propose a two-layer online algorithm called Ader with an ((vT(L+ Pr)) dynamic regret, which is proven to be minimax optimal for convex functions. Ader maintains group of base-learners, each performing online gradient descent (OGD) [Zinkevich, 2003] with a customized step size specified by the pool H (9/1....,77N and then uses a meta-algorithm to combine them all. Denoted by B1. BI...., By the N base-learners. For each i E [N], B, updates by
11x [xr, - 7/1 (x,)),
where 7ソ. E H is the associated step size and [1x|:] denotes the projection onto the feasible domain X' with 1xx [y] arg minxe lly - 21122. Notably, all the base-learners share the same gradient fe((x)) rather than using their individual one V Vf( This is because Ader optimizes the linearized loss (x(x) = (V+( x), which enjoys the benign property of (x1.s) = (xxx) for all i [N].
Furthermore, the meta-algorithm evaluates each base-learner by (x(x,,)) = (v,( xt,)) and updates the weight vector 1 E AN by the Hedge algorithm [Freund and Schapire, 1997], namely,
Pt.i c xx.) Vi E
PI+1I
Pt. exp( Pt (
where e > the learning rate of the meta-algorithm. The final prediction obtained by X++1
Σn Pr+1,,Xt++1.. The learner submits the prediction X and then receives the loss I (x++1) and the gradient fe++ (x++1) as the feedback of this round. Under a suitable configuration of the step size pool H with N Oloo T) and learning rate & = @(v (In N)/T), Ader enjoys an (V1((1+ + Pr)) dynamic regret [Zhang et al., 2018a, 8a, Theorem 4).
For convex and smooth functions, Zhao et al. [2021b] demonstrate that a similar two-layer structure can attain O ((V(TT P1) PT)) small-loss dynamic regret under suitable setting of the step size pool H and time-varying learning rates of meta-algorithm {e+) where Fr = Σ'= Je (u,) the cumulative loss of the comparators. This bound safeguards the minimax rate in the worst case, while can be much smaller than O(vT(1 PT)) bound in benign environments.
2.2 The Reduction Mechanism for Reducing Projection Complexity
As demonstrated in the update (3), all the base-learners require projecting the intermediate solution onto the domain X' ensure the feasibility, As result, Olog 7') projections are required each round, which is generally time-consuming particularly when the domain X' is complicated.
We present generic reduction mechanism for reducing the projection complexity and apply it to dynamic regret methods. Our reduction builds upon the seminal work [Cutkosky and Orabona, 2018) 88] and further refined result [Cutkosky, 2020], who propose a black-box reduction from constrained online learning to the unconstrained setting (or another constrained problem with a larger domain).
Reduction mechanism. Given an algorithm for non-stationary online learning Algo whose projection complexity is O(log T)), our reduction mechanism builds on it to yield an algorithm Efficient-Algo with projection onto X per round and retaining the same order of regret. The central idea is to replace expensive projections onto the original domain X' with other much cheaper projections. To this end, we introduce surrogate domain ) defined as the minimum Euclidean ball containing the feasible domain X', i.e., ) = {x ||x||2 < D} 2 X. Then, the reduced algorithm Algo works on y whose projection can realized by a simple rescaling. More importantly, to avoid regret degeneration, it is necessary to carefully construct the surrogate loss gr y + RR as
(x()) = (V)((x))))) 1(V (V vz)
Sx
(5)

---

Algorithm Efficient Algorithm for Minimizing Dynamic Regret
Input: step size pool H 171.....7N1 learning rate of meta-algorithm e, simply fixed e).
1: Initialization: let x1 and (y1,s be any point in X: vi E PM.. 1/N..
2: for 1 to T do
3: Receive the gradient information V (x.)..
4: Construct the surrogate loss 9t 3 IR according Eq. (5).
5: Compute the gradient V (yx) according to Lemma 1.
6: For each E
[ the base-learner B, produces the local decision by
D
8141,1 Ye, - M/ Vg))),) Y4+1,1 = F (1118444.
1 (100))11))))))
1e+11,122
7: Meta-algorithm updates weight by P1+1, & exp(-E<+1 E.s
(y.( [N].
8: Compute Y++1 = Pt+
9: Submit X++1 = [++1)
The only step projects onto feasible domain X' per round.
10:
end for
where Sx(y) infxxx 2 is the distance function to X' and (y+ xx--xx// -xela is the vector indicating the projection direction.
The main protocol of our reduction is presented as follows. The input includes original functions (f:)T= the feasible domain X, and the reduced algorithm Algo.
1: for w 1,...,, do
2: receive the gradient information V Vf((x)))
3: construct the surrogate loss gr : y + R according to Eq. (5);
4: obtain the intermediate prediction Y++1 ( v.,)))
5: submit the final prediction x [ [y=+
6: end for
Our reduction enjoys the regret safeness due to the following benign properties of surrogate loss.
Theorem 1 (Theorem 2 of Cutkosky [2020]). The surrogate loss y + IR defined in (5) is convex. Moreover, we have V $ (xx) ll and for any u, X
f(x)), u,) g (yr)) (u (Vgcyr)) u.).
(6)
The theorem shows the convexity of the surrogate loss ge (y) and we thus have fx(x,) fu,) s (Vgr(ye), Uz), which implies that it suffices to optimize the linearized upper bound, i.e., to
optimize function (x(y) = (Vge(y:).>) y). The following lemma specifies the gradient calculation.
Lemma 1. For any y E Y, Vg. (y) (x., when (V (x(x)); ve) 2 and (g: (x(x)) (V]((x)), (y)- In particular, (y. fx()) (x,,, Vi) Ve when (x,.. v.)
1ilyyIll =Ixx
---xxxyyl)) (y])\\]] 11x [y]] when (V f((e), Ve) < O. Here V. = (y, (y--x,) x,) ly y X X
Reduction requirements. An important necessary condition for the reduction is to require the reduced algorithm satisfying one gradient query and one function evaluation at each round. Indeed, the reduction essentially updates according to the surrogate loss {9:) Note that the definition of surrogate loss involves the distance function (x ). see Eq. (5). Thus, each evaluation of gi (y) leads to one projection onto X' due to the calculation of (y)y). Similarly, each gradient query of V also contributes one projection, see Lemma for details. To summarize, we can use the reduction to ensure a 1 projection complexity, only when the reduced algorithm satisfies the requirements of one gradient query and one function evaluation per round. Below, we demonstrate the usage of our reduction mechanism for two methods of dynamic regret minimization that satisfy the conditions, including the worst-case method [Zhang al., 2018a] and the small-loss method [Zhao et al., 2021b].
Application to dynamic regret minimization. Algorithm summarizes the main procedures of our efficient methods for optimizing dynamic regret, which an instance the reduction mechanism by picking Algo as Ader [Zhang et al., 201 8a]. More specifically, Lines 6 6 8 are essentially performing Ader algorithm using the surrogate loss {9: )r_ over the surrogate domain V. Note that the base update in Line 6 is essentially performing OGD with projection onto ), scaled Euclidean ball, and
5

---

thus the projection admits a simple closed form. The overall algorithm requires projecting onto X only once per round, see Line 9. Our method provably retains the same dynamic regret.
Theorem 2. Set the step size pool as H. = {n = 2 (D/G))
li E [N]] with N 2- (o + 2T 2T/5)] +1 and the learning rate as V(N (In N)/O G2D2T.. Under Assumptions and 2, our algorithm requires one projection onto X per round and enjoys
Σ fx(x))
For smooth and non-negative functions, the Sword+++ algorithm [Zhao et al., 2021b] achieves an ((v (r) (011-/1) Pr)) small-loss dynamic regret, which requires one gradient and one function value per iteration.' However, notice that the surrogate loss 9+(-) in Eq. (5) is neither smooth nor non-negative, which hinders the application of reduction their method. Fortunately, owing to the benign property of || Ve (ye) lll S f 2 (see Theorem 1), we can still deploy the reduction via an improved analysis and obtain a projection projection-efficient efficient algorithm with the same small-loss bound.
Theorem 3. Set the step size pool as H = {n: = 2 /5D2/(1 + 8LGDT) I E [N]] with N = 1og2 ((5D2 + 21 + SLGDT)/ + and the learning rate of the meta-
algorithum El / (In D2 E. g. ( Under Assumptions 1, 2. and 3, our algorithm requires one projection onto per round and enjoys the following dynamic regret:
T
I - = P
E(
(V((F
(8)
1=1
where Fr Et= Se(ue) is the cumulative loss of the comparators.
3 Adaptive Regret Minimization
In this section, we present our efficient methods minimize adaptive regret. First, we briefly review existing methods in Section 1. and then present our efficent methods to reducing the projection complexity of adaptive regret methods in Section 3.2.
3.1 A Brief Review of Adaptive Regret Minimization
Adaptive regret minimization ensures the online learner to be competitive with fixed decision over every contiguous interval. For the worst-case bound, the best known result is the O vlz log T)) adaptive regret bound achieved by the CBCE algorithm [Jun et al., 2017]. CBCE algorithm requires multiple gradients at each round. Wang al. [2018] improve CBCE by using the linearized loss to make it requiring one gradient per iteration and retaining the same adaptive regret. Moreover, the improved CBCE algorithm only evaluates the function value once per iteration. Therefore, we directly apply our reduction and obtain a projection-efficee efficienn variation with the same adaptive regret. More detailed elaborations can be found in Appendix C.I.
Now, we focus on the more challenging case of small-loss adaptive regret. The best known re- sult is the (( log F1 log FT) bound for any interval I = [r, 8] C [T] obtained by the SACS algorithm [Zhang al., 2019], where F, minxex Ei fx(x) and Fr = minxex Σ fx(x). However, SACS does not satisfy our reduction requirements, because it requires N gradient queries (i.e.. fx(,)) for e [N] and N + function evaluations (i.e., f((x..)) for e [N]. and fx(x)) at round e [T'. where N denotes the number of active base-leamers and Xt, denotes local decision returned by the i-th base-learner. To address so, we have to modify the algorithm fit our purpose.
In the following, we first sketch the SACS algorithm and then present our modifications. In fact, to optimize the adaptive regret, online algorithm usually consists of the three components:
sword++ algorithm is mainly proposed for gradient-variation variation dynamic regret, so there are advanced components (such as correction term and optimism) in algorithu design. It can be verified that their algorithm be simplified by dropping the correction term and optimism when only small-loss bound desired.

---

base-algorithm: an online algorithm that can attain low (static) regret in a given interval;
scheduling: a set of intervals and each one is associated with a base-learner who aims to minimize the static regret over the interval (from starting time to ending time);
(iii) meta-algorithm: a combining algorithm that can track the best base-learner on the fly.
The specific configurations of the SACS algorithm is as follows. First, SACS uses scale-free online gradient descent (SOGD) [Orabona and Pál, 2018] as the base-algorithm, which ensures a small-loss regret in a given interval. Second. SACS employs AdaNormalHedge [Luo and Schapire, 2015] as the meta-algorithm, which supports the sieeping expert setup and also enjoys small-loss regret. Finally, SACS designs a clever strategy of problen-dependent geometric covers determine the set of intervals such that the number of active base-learners also depends on the small-loss quantity. As result, SACS can achieve a fully problem- dependentt adaptive regret of order (VFF log Fj log Fr)) scaling with the cumulative loss of comparators. However, SACS also suffers from an O T) projection complexity in the worst case due to a two-layer structure; and moreover, can be observed that SACS only attains an O ( [ log T) bound in the worst case, which exhibits an /log//] gap compared with the best known result of ((V log T) [Jun et al., 2017]. Below, we present an efficient algorithm for small-loss adaptive regret, which resolves the above two issues simultaneously.
3.2 Efficient Algorithms for Adaptive Regret
As multiple gradient queries and function evaluations are involved in all the three components of SACS, we have to make plenty of modifications to achieve algorithm with small-loss adaptive regret yet requiring only one gradient query and function evaluation per round. With such an algorithm on hand, we can then deploy our reduction achieve an efficient method with 1 projection complexity. Below we present the details. By the reduction mechanism, it is noticeable that we only need to consider the input online functions as surrogate loss {9 ) where It is defined in Eq. (5).
We use SOGD with a linearized surrogate loss (Vgr(y:), y) over the surrogate domain y. Denote by A, the set of active base-learners' indices, then the base-learner B, updates by
Base-algorithm.
yeti. Iylly,, T/. (e
with Th. = D/ (y (12)), where T; denotes the starting time of the base-learner i E A,. The projection onto y can be easily calculated by a simple rescaling if needed. Notably, owing to the convexity of the surrogate loss gt. we can use the same gradient (y)( for all the base-learners at each round, ensuring one gradient query of V fx(:) at each round.
Geometric Covers. The covers consist of set of intervals that specify the alive time of base- learners. To achieve a small-loss adaptive regret, SACS [Zhang et al., 2019] employs a clever covering construction called gubblm--ependder geometric covers (PGC) - instead of initiating base-learner at each round t like earlier algorithms [Daniely et al., 2015; Jun et al., 2017], SACS adds new base-learner only when the cumulative loss exceeds a pre-defined threshold. As a result, the number of active base-learners relates to the small-loss quantity such that the overall algorithm achieves a adaptive regret. Notably, to determine the threshold, SACS monitors the cumulative loss of the latest base-learner (x with i being the latest base-learner's ss index, but clearly this will introduction an additional function evaluation beyond fx;, at each round.
fully problem-dependee
To avoid the limitation, instead of using a fixed threshold to decide the initiations of base-learners, we design a sequence of time-varying thresholds to adaptively start new base-learner according to amount of cumulative loss of final decisions (e.g.. J (xx)). bypassing the requirement of additional function evaluation. This realizes the condition of one function evaluation per round. Also. the new design of thresholds mechanism is important to ensure that the overall small-loss bound can simultancously recover the best known worst-case guarantee, which SACS fails to achieve [Zhang et al., 2019]. Let C1, C22 Cs.... denote the sequence of thresholds, and they will be determined by a threshold generating function g(-) + 1R, that will be specified later. Our poolem-dependde geometric covers are set as follows. We initialize the setting by $1 1. We set 8 as the round when the cumulative loss of the overall algorithm (namely, Σ fa(x.)) exceeds the threshold Ci and then initialize a new instance of SOGD starting at this round. The process is repeated until the end of online game, We thus generate sequence of points $1, s referred to as the markers. See
7

---

Algorithm 2 Efficient Algorithm for Problem-dependent Adaptive Regret
Input: threshold generating function g(+) + Rt,
1: Initialize total intervals m 1, marker $1 = 1, threshold C1 = g[];; let x1 be any point in A.
2: for 1 to T do
3: Receive the gradient information V (x.)).
4: Construct the surrogate loss 9t : 3 + IR according Eq. (5).
5: Compute the (sub-)gradient g. (y+) according to Lemma 1.
6: Compute T,2 1 1 + fx(x)
% constructing
Geometric Covers (PGC)
7:
if L, Cm then
8:
Set L, = 0, remove base-learners By whose ending point e₁ = + 1.
9:
Set m f 1, Sm t t, Cm = ((m).
10:
Initialize new base-learner with ending point = j satisfying [m. - 1] E C, where
C= = ULEN Cs and C = { 2* (i + 1) 2 - 1] i is odd} for all & E N u (0}.
11:
Set Ym = In(1 + 2m), Wt,m m. min (1/2, )m for the meta-algorithm.
12:
end if
13:
Send (y, all learners and obtain local predictions Y1+1, for i E Ac.
14:
Meta-algorithm updates weight pi+1 E AJActa according to Eq. (11), Eq. (12), and Eq. (13)
15:
Compute Y1+1 = EiEAm Pt,1,
16:
Submit X++1 = 11x11
>> The only projection onto feasible domain X' per round.
end for
the condition in Line 7, registration of markers in Line 9, and the overall updates in Lines 7 - 11 of Algorithm Those markers specify the starting time (and the ending time) of base-learners and thus construct the PGC as
U UkEEuuo C22 where C2 -{ {[s ((41))22* 1] is oddo for all k E N (0).
(10)
is noteworthy to emphasize that PGC is constructed by the language of "marker", whose exact time stamp is unknown ahead of time but is only determined according to the learner's 's performance on the fly. Moreover, the notation C in Lines 10 Algorithm 2 defined based on the registered indexes of markers, and there a one-one correspondence from the interval in to that in PGC Č. More concretely, interval 2 (1+ 2 1] E C will be mapped into the interval [st.2,, 8(i+1)-22* -1] in PGC, managing the alive time base-learners in a geometric manner with respect to the subscripts.
Meta-algorithm. SACS uses the AdaNormalHedge [Luo and Schapire, 2015] as the meta-algorithm, however, this not suitable for our propose. To ensure one projection per iteration, we cannot use multiple function values, i.c. {9. (yr,,) for meta-algorithm to evaluate the loss. Instead, can only use the linearized loss value, namely, ((V9. yr, J.V in the weight update of meta- algorithm. The small-loss regret bound in the meta-algorithm of SACS crucially relies on the original function values, which is unfortunately inaccessible in case. Technically, when fed with linearized loss, it is hard to establish a squared gradient-norm bound and then convert the small loss due to the first-order regret bound of AdaNormalHedge. Based on this crucial technical observation, propose to use the Adapt-ML-Pros algorithm |Gaillard et al., 2014] as the meta- alga-atgo in our method. The key advantage is that it enjoys second-order regret and also supports the sleeping expert setup. Adapt-MI.-Proo maintains multiple learning rates v7++1 and an intermediate weight vector Wx+1, which updated by the following rule. For any active base-leamer A
1 min
7
W1+1,1
(wr,((1 (1 + Th, -l,)))),)))))))))))))))))))))(
(11)
2' V 1 E1 (Cx lx,)2
where 7i = In(1
21) is a certain scaling factor and the feedback loss is constructed for i A, P, (V)
and le;: (Vor(v)).
(12)
The final weight vector P A|4cia is obtained by
W1+1.1 M7t1,
Ptt1a EjEAm W1i1 7141
(13)
8

---

Notably, the meta update only uses one gradient at round t. namely, (gi(y.)
Finally, we compute y++1 Pi as the overall prediction in the surrogate domain Y and calculate x = [xx to ensure the feasibility. This is the only projection onto at each round. Algorithm 2 summarizes the main procedures of our efficient methods for small-loss adaptive regret. Albeit with a similar two-layer structure as SACS, our algorithm exhibits salient differences in base-algorithng meta-al meta-algorithm, and geometric covers. As benefit, reduction mechanism and make the overall algorithm project onto the feasible domain X' once per round, see Line 16. Our method retains the same small-loss adaptive regret as [Zhang et al., 2019].
successfully deploy our
Theorem 4. Under Assumptions 1-3, setting the threshold generating function (m) = (log m) whose explicit form is in Eq. (46) of Appendix C, Algorithm 2 requires only one projection onto X per round and enjoys the small-loss adaptive regret:
Σd(x) Σ f((u) S 50 min {v Fi log Fi log Fr, v log
(14)
for any interval 1 = [r, S [T], where F₁ = minxex Eisr fx(x and Fr = minxex Ei= fx(x).
Remark 1. Note that the O D(VFilog log FT) small-loss bound of Zhang al. [2019] becomes O(V log / logg) in the worst case, looser than the [[v bound [Jun et al., 2017] by a factor of log /J. We show that this limitation can be actually avoided by the new design of thresholds mechanism and a refined analysis. More discussions can be found in Appendix C.3. Indeed, our result in (14) can strictly match the best known problem gobblem-indepeneere result in the worst case.
4 Experiment
In this section, we provide empirical studies to evaluate our proposed methods.
General Setup. We conduct experiments on the synthetic data. We consider the following online regression problem. Let I' denote the number of total rounds. At each round E [T] the learner outputs the model parameter W, W C IRd and simultaneously receives data sample (22,, ye) with I; E X C R being the feature and y/: E IR being the corresponding label.? The learner can then evaluate her model by the online loss f<(w.) = 1.2 (xr] w, - y² which uses a square loss to evaluate the difference between the predictive value x. w, and the ground-truth label yt. and then use the feedback information to update the model. In the simulations, we set = 20000, the domain diameter as D = 6, and the dimension of the domain as d = 8. The feasible domain W is set as an ellipsoid W = w E Rd w Ew Amin (E) (D/2)²), where E is a certain diagonal matrix and Amin (E) denotes its minimum eigenvalue. Then, a projection onto W requires solving a convex programming that is generally expensive. In the experiment, we use scipy. . optimize. Non1 inarronssttnnn to solve it to perform the projection onto the feasible domain.
To simulate the non-stationary online environments, {(I,, yt Y= Specifically, for & E [T], the feature I; is randomly sampled in an Euclidean ball with diameter D same the feasible domain of model parameters; and the corresponding label is set as 3r = x w + Et. where & is the random noise drawn from [0, 0.1] and w; is the underlying ground-truth model from the feasible domain W generated according to a certain strategy specified below. For dynamic regret minimization, we simulate precewise-stational
control the way to generate the date samples
model drifts, as dynamic regret will be linear in T and thus vacuous when the model drift happens every round due to linear path length measure. Concretely, we split the time horizon evenly into 25 stages and restrict the underlying model parameter w to be stationary within a stage. For adaptive regret minimization, we simulate gradually evolving model drifts, where the underlying model parameter w is generated based on the last-round model parameter w/ with an additional random walk in the feasible domain W. The step size of random walk is set to be proportional to D/T to ensure a smooth model change.
Contenders. For both dynamic regret and adaptive regret minimization, we directly work on the small-loss online methods. We choose the Sword algorithm [Zhao et al., 2021b] as the contender of
*With slight abuse of notations, we here use w to denote the model parameter and W to denote the feasible domain, while reserve the notations of z and X to denote the feature and feature space following the conventional notations of machine learning terminologies.

---

(a) dynamic regret (loss) (b) dynamic regret (time) (c) adaptive regret (loss) (d) adaptive regret (time)
Figure 1:
Performance comparisons of existing methods and our methods (indicated by "efficient" prefix) in terms of cumulative loss and running time (in seconds). The first two figures plot the results
of methods for dynamic regret minimization, while the latter ones are for adaptive regret.
our efficient method for dynamic regret (Algorithm 1) and choose the SACS algorithm [Zhang et al., 2019] as the contender of our efficient method for adaptive regret (Algorithm 2).
Results. We repeat the experiments for five times with different random seeds and report the results (mean and standard deviation) in Figure We use machine with single CPU (Intel(R) Core(TM) i9-10900K CPU @ 3. 3.70GHz) and 32GB main memory to conduct the experiments. We plot both cumulative loss and running time (in seconds) for all the methods. We first examine the performance of dynamic regret minimization, see Figure ((a) for cumulative loss and see Figure 1(b) for running time. The empirical results show that our method has a comparable performance to Sword without much sacrifice of cumulative loss, while method can achieve about 10 times speedup due to the improved projection complexity. Second, as shown in Figure ((c) and Figure ((d), a similar performance enhancement also appears in adaptive regret minimization, though the speedup is slightly smaller due to the fact that fewer learners are required to maintain for adaptive regret. To summarize, the empirical results show the effectiveness of our methods in retaining the regret performance and also the efficiency in terms of the running time due to the reduced projection complexity.
Conclusion
In this paper, design a generic reduction mechanism that can reduce the projection complexity of two-layer methods for non-stationary online learning, hence approaching a clearer resolution of necessary computational overhead for robustness non-stationarity. Building on the reduction mechanism, we develop series of online algorithms for optimizing dynamic regret and adaptive regret. All the algorithms retain the best known regret guarantees, and more importantly, require one projection onto the feasible domain per iteration. It is further worth mentioning that, due to the requirement of our reduction, all our algorithms only need one gradient query and one function evaluation at each round as well, which can be appealing in situations with limited feedback.
Our reduction also be applied to other settings achieve light project complexity, for example, dynamic regret of OCO with memory [Zhao et al., 2022b), OCO with switching cost [Zhang et al., 2021], and related applications such online non-stochastic control [Hazan al., 2020]. Moreover, is possible to derive similar efficient algorithms for minimizing the interval dynamic regret, an even stringent measure for non-stationary online convex optimization. There is one important open question left on another type of problem-dependent bound that scales with gradient variation [Chiang et al., 2012], which plays an important role establishing fast convergence in zero-sum games [Syrgkanis et al., 2015; Zhang et al., 2022]. Although Zhao et al. [2021b] have devised two-layer method that enjoys gradient-variatio variation dynamic regret and requires one gradient per iteration, it is quite challenging to incorporate the optimistic online learning into our reduction mechanism due to the constrained feasible domain and the complicated two-layer structure. Finally, would be greatly important to further understand the minimal computational overhead in response to the robustness to non-stationarity, particular, some intermatioo-thhoreen arguments would be highly interesting.
Acknowledgements
This research was supported by NSFC (61921006, 62206125). JiangsuSF (BK2022077)), National Postdoctoral Program for Innovative Talent, and Collaborative Innovation Center of Novel Software Technology and Industrialization.
10

---

References
Auer, N. Cesa-Bianchi and C. Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48- 75, 2002.
D. Baby and Y.-X. Wang- Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 359-409, 2021.
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference On Learning Theory (COLT), pages 6.1-6.20, 2012.
A. Cutkosky. Garameter-free, dynamic, and strongly- online learning. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 2250-2255 2020.
A. Cutkosky and F. Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 1493-1529, 2018.
A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1405-1411, 2015.
Y. Freund and R. E. Schapire. application to boosting. Journal of Computer and System Sciences, 55(1): (111)::19-111 19-199, 1997.
decision-theoretic generalization of on-line learning and an
P. Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In 1 Proceedings of the 27th Conference on Learning Theory (COLTT), pages 176-196, 2014.
E. Hall and R. Willett. Dynamical models and tracking regret online convex programming. In Proceedings of the 30th International Conference on Machine Learning (ICML.) pages 579-587, 2013.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends Optimization, 13-4):1573325, 2016.
E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 393-400, 2009.
E. Hazan, S. M. Kakade, and K. Singh. The nonstochastic control problem. In Proceedings of the 31st International Conference Algorithmic Learning Theory (ALT), pages 408 088,411,55 2020.
K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved strongly adaptive online learning using coin betting. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 943-951, 2017.
H. Luo and R. E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Proceedings of the 28th Annual Conference Computational Learning Theory (COLT), pages 1286-1304, 2015.
Z. Mhammedi, W. M. Koolen, and T. van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Annual Conference Computational Learning Theory (COLT), pages 2490-251 11 2019.
Orabona. A Modern Introduction Online Learning. ArXiv preprint, 1912.13213, 2019.
Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 7 716:50-69, 2018.
R. Pogodin and T. Lattimore. On first-order bounds, variance and gap-dependent bounds for adversar- ial bandits. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 894-904, 2019.
S. Shalev-Shwartz. Online Learning: Theory, Algorithms and Applications. PhD Thesis, 2007.
S. Shwarz-Swwartz. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems 23 (NIPS), pages 2199 2199-2207, 2010.
V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pages 2989-2997, 2015. van Erven and W. M. Koolen. Metagrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3666-3674, 2016.

---

G. Wang, D. Zhao, and L. Zhang. Minimizing adaptive regret with one gradient per iteration. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 2762-2768, 2018.
L. Zhang. Online learning in changing environments. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 5178-5182, 2020. Early Career.
L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330-1340, 2018a.
Zhang, T. Yang, R. Jin, and Z. Zhou, Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 5877-5886, 2018b.
L. Zhang. T.-Y. Liu, and Z.-H. Zhou, Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7414-7423, 2019.
L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultancously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 309-319, 2020.
Zhang, W. Jiang, Lu, and Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems 34 (NeurlPS), pages 13599-13612, 2021.
M. Zhang. P. Zhao, H. Luo, and Z.-H. Zhou, No-regret learning in time-varying zero-sum games, In Proceedings of the 39th International Conference on Machine Learning (ICML)), pages 26772- 26808, 2022.
Zhao, Y.J. Zhang, L.. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurlPS), pages 12510-12520, 2020.
P. Zhao, G. Wang, L. Zhang, and Z.-H. Zhou. Bandit convex optimization in non-stationary environ- ments. Journal of Machine Learning Research, 22(125):1-45, 202
Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. ArXiv preprint, 12. 2021b.
P. Zhao, L.-F. Li, and Z. Zhou. Dynamic regret of online markov decision processes. In Proceedings of the 39th International Conference Machine Learning (ICML), pages 26865- 26894, 2022a.
P. Zhao, Y.-X. Wang, and Z.-H. Zhou, Non-stationary online learning with memory and non-stochastic control. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2101-2133, 2022b.
Z. Zhou. Open-environment machine learning. National Science Review, 98): 22,, 2022.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML) pages 928-936, 2003.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description.
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? (Yes]
(b) Did you describe the limitations of your work? [Yes] See discussions in Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
12

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 'e using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "aYrP4ThSKSD", "reviewer": "Reviewer_zt1M", "summary": "The paper presents a generic reduction-based method for obtaining online learning algorithms with adaptive and/or dynamic regret guarantees that have low “projection complexity”, i.e., use the projection operation as few times per round as possible. In fact, subject to the condition that the reduced algorithm queries the gradient and evaluates the loss function at most once per round, it is demonstrated that this reduction results in the algorithm doing at most one projection per round. The relevance of this result is that the dynamic/adaptive regret literature has recently increasingly adopted a two-level hyper-expert setup where decisions of a substantial number of hyper-experts are aggregated every round, and such methods naively would do a projection per expert per round --- such projections being a computationally costly operation. In the paper, the approach is illustrated by applying it to several algorithms (Ader, SACS, AOA) with state-of-the-art dynamic/adaptive/interval dynamic regret bounds --- thus reducing these algorithms’ projection complexity while keeping their performance guarantees.", "questions": "I am overall happy with the paper’s presentation. As one suggestion, I would recommend --- for the purposes of further driving home the main message (that low projection complexity, as achieved through the proposed reduction, does substantial good for the runtime not just in theory, but also in practice) --- that the authors try to find a way to move some improved runtime plots from the appendix into the main part of the paper.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I consider this paper to be a high-quality submission: On the one hand, it thoroughly develops and applies, on state-of-the-art terrain, a framework for reducing the computational complexity of OCO algorithms. On the other hand, it exhibits high-quality writing/presentation --- providing a good, largely self-contained, overview of important related literature and results, and giving insight into the developed reduction methods and how to apply them in “practice”. \n\nIn terms of originality, the backbone of the proposed reduction method (“replace the original domain by a Euclidean ball with an appropriately defined surrogate loss, and project back onto original domain”) to a substantial degree originates in a line of work by Cutkosky and Orabona on black-box reductions for parameter-free online learning. The main contribution of the current paper is in recognizing the generic potential of this type of reduction to generate low-projection-complexity state-of-the-art dynamic/adaptive regret algorithms, and showing how to get through the weeds of some complex recent algorithms like SACS in order to bring them into the appropriate shape for this reduction to result in one-per-round projection complexity (which essentially amounts to modifying these algorithms so that they have one gradient/function evaluation per round). I believe, on balance, that this is a high-quality and sufficiently original contribution to the online learning literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WzSPTdHaoEA", "reviewer": "Reviewer_2iQY", "summary": "This paper studies methods making online learning with non-stationary comparators more efficient in terms of the number of projections onto the feasible set in the OCO setting. The authors begin with a typical meta-algorithm for the dynamic/adaptive regret setting, where the meta-algorithm averages predictions over many base algorithms, but each base algorithm (of which there are typically O(log(T)) requires a projection step. The main idea is to replace the feasible set with the smallest Euclidean ball containing it (making the projection trivial) and the loss function with a surrogate loss that allows for the same regret guarantee, run the base algorithms with this easy projection, then do the projection onto the action set afterwards. Since  single projection can be shared by all the base algorithms, resulting in a log(T) reduction in the number of projections (assuming projections to Euclidean balls are free).\n\n\nThis reduction is applied to different algorithms to build projection-efficient algorithms for dynamic regret and small-loss dynamic regret. Finally, the authors also present a new algorithm for interval dynamic regret, which is nice; the SOTA algorithm for this setting, SACS, needs to be heavily modified to obtain the small-loss bound.\n", "questions": "The authors make a compelling case for the applicability of their reduction technique and derive several algorithms with great computational properties. Three are presented in the paper. Even without the goal of reducing the number of projections, the surrogate function reduction seems to be a powerful technique and the authors give good reason to know about it. The range of results obtained are impressive.\n\nThere are some small presentation issues. It becomes difficult to keep track of all the meta or base algorithm substitutions, some some assistance (e.g. in the form of a table) would be appreciated.\n\nI would also appreciate more discussion about the proof techniques, especially regarding what is novel. One of the main takeaways of this work is the utility of the surrogate loss, and some proof outlines would help.\n\nA few other small presentation issues:\nUse \"twists\" a bit too much, especially in the intro.\nSmall grammatical mistakes, i.e.\n166: the feasibility -> feasibility\n174 (and other places): 1 projection -> one projection\nSince empirical experiments aren't in the main body, I would not reference them in the abstract.\n", "limitations": "I think a more thorough discussion of the algorithmic trade-offs needed to ensure single projections is necessary; see my earlier comments. No societal impact discussion is presented or expected.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors make a compelling case for the applicability of their reduction technique and derive several algorithms with great computational properties. Three are presented in the paper. Even without the goal of reducing the number of projections, the surrogate function reduction seems to be a powerful technique and the authors give good reason to know about it. The range of results obtained are impressive.\n\nThere are some small presentation issues. It becomes difficult to keep track of all the meta or base algorithm substitutions, some some assistance (e.g. in the form of a table) would be appreciated.\n\nI would also appreciate more discussion about the proof techniques, especially regarding what is novel. One of the main takeaways of this work is the utility of the surrogate loss, and some proof outlines would help.\n\nA few other small presentation issues:\nUse \"twists\" a bit too much, especially in the intro.\nSmall grammatical mistakes, i.e.\n166: the feasibility -> feasibility\n174 (and other places): 1 projection -> one projection\nSince empirical experiments aren't in the main body, I would not reference them in the abstract.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HKeR58nf-h7", "reviewer": "Reviewer_JRs5", "summary": "This work tackles the topic of time complexity in modern online algorithms. Indeed, to deal with dynamic environments, modern algorithms use a 2-layers structure to obtain strong predictions and it implies at each time step $O(\\log(T)$ projections over a possibly complex convex set. Those projections may be time-expensive in practice, and not suitable for many real-life situations.\nThat is why authors propose a generic mechanism which only involves $O(1)$ projections at each time step. They apply their mechanism onto three distinct algorithms dedicated to minimise different types of regrets: dynamic regret, adaptive regret and interval dynamic regret.\nAuthors also propose in Appendix A a toy experiment illustrating the efficiency of their procedures.", "questions": "- I am wondering about the lifetime of the base learners in Alg.2. In lines 8-10, how do we choose the ending points of a new base learner? Is it arbitrary?\n- I am not sure to understand what have been the motivation to design $\\Tilde{\\mathcal{C}}$ in Eq. 10)? Is it possible to have more explanations?\n- It is said that the code is available but I did not find any python file in the supplementary nor a link to an anonymous Github, did I miss something?\n- An open question: authors state in their conclusion that it would be challenging to incorporate optimistic online learning within this work. But could not we incorporate, at each time, the optimistic information directly within the base algorithm and see where it goes?", "limitations": "None", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- A pedagogical work, clear and well-written.\n- The goals of the paper are well stated. The theoretical results are, for me, impacting and come with a convincing toy experiment.\n- Any new result or algorithm comes with welcomed explanations and discussions.\n \n\nWeaknesses:\n- It would have been good to mention more the existence of experiments within the main document. I believe they constitute an important point of this work but they seems to be quite hidden.\n- I think it would have been good to mention a few learning problems which involves concrete complicated convex sets on which the projection step is costful.\n\nConclusion: \n\nI congratulate the authors for their work. To me,  they performed a significant step in online learning as they reduced time complexity of modern algorithms with the use of insightful surrogates without sacrificing any performance guarantee. The proposed experiment numerically attest this fact. Furthermore, the proposed work is not only impacting but also clear and well-written, it has been a pleasure to read this document. \nFinally I precise that I am not that familiar with the literature around the adaptive regret, thus I may overestimate the strength of some proposed results but I am confident in the fact that Alg.1, which is a twisted improved Ader is impacting in the dynamic regret field.\nHowever, for all those positive reasons, I give this paper a 8. \n\n\n\n\nRemark: \n- As I am not familiar with Adaptive Regret literature, I only checked the proofs for Dynamic Regret which are for me, correct.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9pAX8pBE7KB", "reviewer": "Reviewer_9mtH", "summary": "The paper presents a reduction that achieves 1 projection complexity for algorithms with low dynamic regret and adaptive regret, which typically have $O(\\log T)$ projection complexity, without degrading their regret guarantees. Since the projection operation can be a major bottleneck when the decision set is complicated, the reduction has significant computational advantages over the original algorithm. In cases where the reduction cannot be straightforwardly applied, the work specifies modifications under which 1 projection complexity can be achieved. \n", "questions": "To make the impact clear, it would be helpful to explicitly state some settings/problems where the projection step is expensive in the main paper.  \n", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper proposes a method to address the computational efficiency problem in dynamic regret/adaptive regret minimization, which has applications in many domains. The proposed method achieves significant computational savings when projecting onto the convex decision set is expensive.\n- The reduction is novel as far as I know, and serves as the backbone of a series of algorithms that achieve 1 projection complexity without worsening regret guarantees. When the original algorithm doesn’t satisfy the conditions of the reduction, nontrivial changes are presented to accommodate the requirements, along with their theoretical justifications.\n- The paper is very clearly written and concisely presented. \n\nWeaknesses\n- See questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept