Online Non-convex Learning in Dynamic Environments
Authors: Zhipan Xu
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Non-convexity
Dynamic Environments
Primary area: online_learning

Abstract: This paper considers the problem of online learning with non-convex loss functions in dynamic environments. Recently, Suggala and Netrapalli [2020] demonstrated that follow the perturbed leader (FTPL) can achieve optimal regret for non-convex losses, but their results are limited to static environments. In this research, we examine dynamic environments and choose \emph{dynamic regret} and \emph{adaptive regret} to measure the performance. First, we propose an algorithm named FTPL-D by restarting FTPL periodically and establish $O(T^\frac{2}{3}(V_T+1)^\frac{1}{3})$ dynamic regret with the prior knowledge of $V_T$, which is the variation of loss functions. In the case that $V_T$ is unknown, we run multiple FTPL-D with different restarting parameters as experts and use a meta-algorithm to track the best one on the fly. To address the challenge of non-convexity, we utilize randomized sampling in the process of tracking experts. Next, we present a novel algorithm called FTPL-A that dynamically maintains a group of FTPL experts and combines them with an advanced meta-algorithm to obtain $O(\sqrt{\tau\log{T}})$ adaptive regret for any interval of length $\tau$. Moreover, we demonstrate that FTPL-A also attains an $\tilde{O}(T^\frac{2}{3}(V_T+1)^\frac{1}{3})$ dynamic regret bound. Finally, we discuss the application to online constrained meta-learning and conduct experiments to verify the effectiveness of our methods.

Online Non-convex Learning in Dynamic Environments
Zhipan Xu', Lijun Zhang
National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing, China Schooo of Artificial Intelligence, Nanjing University, Nanjing, China xuzhipan@smail nju. edu.cn, zhangl
zhang]j@lamda... j@lamda. anj.a eju.edu.ccm
Abstract
This paper considers the problem of online learning with non-convex loss functions in dynamic environments. Recently, Suggala and Netrapalli [2020] demonstrated that follow the perturbed leader (FTPL) can achieve optimal regret for non-convex losses, but their results are limited to static environments. In this research, we examine dynamic environments and choose dynamic regret and adaptive regret to measure the performance. First, we propose an algorithm named FTPL-D by restarting FTPL periodically and establish O (Vr + 1)$) dynamic regret with the prior knowledge of Vr, which is the variation of loss functions. In multiple FTPL-D with different restarting
the case that Vr is unknown, parameters as experts and use a meta-algorithm to track the best one on the fly. To address the challenge of non-convexity, process of tracking experts. Next, we present a novel algorithm called FTPL-A that dynamically maintains group of FTPL experts and combines them with an advanced meta-algorithm to obtain O T log T)) adaptive regret for any interval length т. Moreover, we demonstrate that FTPL-A also attains an Ö (Vr + 1)3) dynamic regret bound. Finally, we discuss the application online constrained meta-learning and conduct experiments to verify the effectiveness of our methods.
utilize randomized sampling in the
1 Introduction
Online learning is a powerful model for sequential decision-making tasks, supported by well- established theoretical guarantees [Cesa-Bianchi and Lugosi, 2006, Orabona, 2019]. It can be regarded as a repeated game between a learner and an adversary. In each round I, the learner first selects decision x, E K. where K. is candidate set. Then loss function f+(-): K. IR is revealed and the learner suffers a loss fx(x).. The goal of the learner to minimize the cumulative loss T fx(xx) over all rounds. Traditionally, the performance measure is static regret or simply regret
T
R(T) = Σ f((x)) min Σ f((x).
XEK
defined as the difference between the cumulative loss of the online learner and that of the optimal decision chosen in hindsight. During the past decades, numerous algorithms and theories have been developed to minimize static regret. An extensively researched setting is online convex optimization (OCO) [Shaley-Shwartz et al., 2012], in which the losses assumed to be convex and Lipschitz- continuous. For OCO, many efficient methods such online gradient descent (OGD) attain O(vT) regret [Zinkevich, 2003], which is known to be minimax optimal [Abernethy et al., 2008].
"Lijun Zhang is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

On the other hand, when the losses are non-eo,,ex, minimizing regret becomes computationally challenging. This is because minimizing regret implies optimization, and general non-convex optimization is known to be NP-hard. In light of this computational barrier, some recent works examine the notion of local regret instead [Hazan et al., 2017, Aydore et al., 2019, Hallak al., 2021, Guan et al., 2023]. However, these researches focus finding local optima and hence do not guarantee vanishing regret that grows sublinear in T' To ensure vanishing regret, another class of studies assumes access to a sampling oracle [Krichene et al., 2015, Yang et al., 2018, Héliou et al., 2020] or an offline optimization oracle [Agarwal et al., 2019, Suggala and Netrapalli, 2020]. Particularly, Suggala and Netrapalli [2020] have demonstrated that for general non-convex and Lipschitz-continuuus losses, FTPL can achieve O(VT) regret, which matches the optimal result in the convex setting. However, their study solely focuses on static environments, as uses regret the only metric to measure the performance. In dynamic environments, the distribution of loss functions may change over time, causing a shift in the optimal decision. this scenario, the static regret in (1) is not suitable measure since the comparator is fixed [Zhang, 2020, Cesa-Bias Bianchi and Orabona, 2021]. To overcome this limitation, studies in OCO have introduced new performance metrics: dynamic regret [Zinkevich, 2003, Zhang et al., 2018a] and adaptive regret [Hazan and Seshadhri, 2007, Daniely et al., 2015].
In dynamic regret [Zinkevich, 2003], the learner is compared against sequence of local minimizers:
T Σ
T Σd((x)) t=1
RD = (x
f((x))
(2)
where x E arg minxex (x) is a minimizer of fx( over domain A. It is recognized that in the worst-case scenario, achieving sublinear dynamic regret is impossible unless we introduce certain constraints on the comparator sequence or the function sequence [Jadbabaie et al., 2015]. One such example is the functional variation defined below
T Σ
VT
max f((x) ft-1(x)]- xek
If the value of Vi is known in advance, Besbes al. [2015] showed that a restarted OGD achieves O (Vr + 1)3) dynamic regret for convex functions.
Strongly adaptive regret [Daniely et al., 2015] is another widely used performance metric in dynamic environments. It is defined as the maximum static regret over any interval of length r:
8+7-1 5(x) Σ
(A(T, =
max (.
Σ f((x)) min x
(4)
Given the dynamic nature of environments, where the optimal decisions can vary across intervals, minimizing static regret over any interval of length is essentially competing against changing comparator. For convex functions, the best known result for strongly adaptive regret is O(vTlog] [Jun et al., 2017].
In this paper, we consider minimizing dynamic regret and adaptive regret in the non-convex setting, For dynamic regret minimization, we first propose an algorithm named FTPL-D by restarting FTPL periodically and establish an O (Vr + 1) dynamic regret bound, which requires the prior knowledge of Vrr to set the optimal restarting frequency. To get rid of this limitation, we then propose the second algorithm named FTPL-D++ by running multiple instances of FTPL-D with different restarting frequencies and combining them with a meta-algorithm to track the best one. Given that the loss functions are non-convex, deterministic algorithms cannot achieve vanishing regret [Suggala and Netrapalli, 2020]. Hence, we choose Hedge [Cesa-Bianchi and Lugosi, 2006] with randomized sampling as our meta-algorithm. Correspondingly, in each round, we sample one expert based on their weights instead of computing the weighted average of all experts. We prove that FTPL-D+ enjoys the same order of dynamic regret bound as that of FTPL-D without the prior knowledge of Vz.
For adaptive regret minimization, we propose an algorithm named FTPL-A, where we construct a set of intervals dynamically and instantiate an expert of FTPL to minimize the static regret for every interval. To combine these experts whose numbers vary at different time steps, we use AdaMormalHedge [Luo and Schapire, 2015] that can deal with sleeping experts as our meta-algorithm

---

Table 1: Summary of dynamic regret and strongly adaptive regret bounds. The symbol 'indicates that the algorithm requires prior knowledge of Vr. The O-))nootation omits logarithmic factors on T. Abbreviations: dynamic regret- + D-R, strongly adaptive regret SA-R.
Method
Loss
Metric
Regret Bounds
Restarted OGD [Besbes et al., 2015]
convex
D-R
O (Vr + 1)$)
*FTPL-D (ours)
non-convex
D-R
(VT (VT
FTPL-D+ (ours)
non-convex
D-R
FTPL-A (ours)
non-convex
D-R
(VT + 1)3)
CBCE [Jun et al., 2017]
convex non-convex
SA-R
O(v T) OlyTlog
FTPL-A (ours)
SA-R
and again employ randomized sampling in it select experts. We prove that FTPL-A achieves an O( V log ?')) adaptive regret bound for any interval of length r. Besides, we demonstrate that our FTPL-A also obtains an Ô (Vr + 1)$) dynamic regret bound, indicating its effectiveness in minimizing dynamic regret and adaptive regret simultaneously. In brief, our dynamic regret and strongly adaptive regret for non non-convex loss functions are on the same order as those for convex functions. We compare our results and previous ones in Table 1.
Moreover, we discuss the application of our methods to online constrained meta-learning [Xu and Zhu, 2023] and conduct experiments. The empirical results demonstrate the effectiveness of our methods in dynamic regret and adaptive regret minimization. We highlight the main contributions of this paper below.
For dynamic regret minimization, we first propose a novel algorithm named FTPL-D and es- tablish ( (Vr + 1)$) dynamic regret. To eliminate the dependence on prior knowledge of Vr, we then propose FTPL-D+ and provide dynamic regret bound of the same order. For adaptive regret minimization, we develop a novel algorithm named FTPL-A and establish an O(VT log T strongly adaptive regret bound. Moreover, we prove that FTPL-A also ensures an Ö(T (Vr + 1)+) dynamic regret bound.
We discuss the application to online constrained meta-learning and conduct experiments to verify the effectiveness of our methods.
2
Related Work
In this section, give brief introduction to previous works in OCO and online non-convex learning. More related works are reviewed in Appendix B.
Online Convex Optimization The existing works in OCO mostly focus on static regret. For instance, OGD [Zinkevich. 2003] and follow the regularized leader [Hazan al., 2016] both achieve an O(VT) regret bound. The O(v regret bound for Lipschitz-conver functions is known to be minimax optimal [Abernethy et al., 2008]. To cope with dynamic environments, Zinkevich [2003] introduced the dynamic regret in (2), and there are numerous studies dedicated to the worst-case scenario because of its mathematical tractability [Besbes et al., 2015, Jadbabaie et al., 2015, Mokhtari al., 2016, Yang et al., 2016, Zhang et al., 2017, Baby and Wang. 2019, Zhao and Zhang, 2021, Wan et al., 2023]. As mentioned earlier, dynamic regret is often bounded in terms of certain regularities of the comparator sequence or the function sequence. In particular, Besbes et al. [2015] proposed the functional variation in (3) to evaluate the movement of loss functions. They equipped restarted OGD with Ó (Vrr + 1)$) dynamic regret bound, but require to know Vy beforehand.
Besides dynamic regret, another metric in dynamic environments is adaptive regret. Adaptive regret has been examined under the setting of prediction with expert advice (PEA) [Littlestone and Warmuth, 1994, Freund et al., 1997, Gyorgy et al., 2012, Adamskiy et al., 2012, Luo and Schapire, 2015] and OCO [Hazan and Seshadhri, 2007, Daniely et al., 2015, Jun et al., 2017, Zhang et al., 2019, 2021, Yang et al., 2024]. In the following, we focus on the latter one. To minimize (4), Daniely al. [2015] developed a meta-algorithm called strongly adaptive online learner and used it to design
3

---

two-layer structured online algorithms, which enjoy an O(v 7') strongly adaptive regret bound for convex functions. Later, Jun et [2017] proposed novel meta-algorithm and improved the strongly adaptive regret bound to O(vT log 7
Online Non-convex Learning To avoid the NP-hardness of non-convex optimization, Hazan et al. [2017] proposed a computational tractable notion of local regret and developed algorithms that attain the optimal local regret bound efficiently. Hallak al. [2021] extended the local regret minimization framework to non-smooth settings. Guan et al. [2023] further examined the cases where limited number of gradient oracles or value oracles are available. Although these techniques can efficiently minimize local regret, they do not guarantee to find the global optima and achieve vanishing regret.
Another line of work still focuses on the notion of static regret, but assumes access to sampling oracle or an offline optimization oracle. Assuming access to a sampling oracle, Krichene et al. [2015] proved that the Hedge algorithm is capable of achieving O( P(VTlog T) regret over specific feasible set. Yang et al. [2018] later improved the regret bound to O(vT) by partitioning the feasible with a layered structure and using a novel weighting method. Besides, Héliou et al. [2020] examined the dual averaging (DA) algorithm with an imperfect value-feedback model the loss function, which also attained ((VT) regret bound. However, these algorithms rely on a sampling oracle on continuum that is computationally intractable.
Under the hypothesis that the algorithm has access offline optimization oracle, Agarwal et al. [2019] showed that FTPL achieves O(T regret for general non-convex loss functions with Lipschitz continuousity. In the same setting, Suggala and Netrapalli [2020] improved the regret bound to O(VT). It should be noted that assuming access to an offline optimization oracle is reasonable since some simple algorithms such stochastic gradient descent, are able find approximate global optima quickly, even for non-convex objective functions.
By contrast, the studies on dynamic environments are limited. Aydore et al. [2019] introduced variant of local regret for dynamic environments and proposed novel algorithm to minimize Héliou et al. [2020] obtained O (Vr + 1)$) dynamic regret with their imperfect feedback method. However, it needs the prior knowledge of Vr to choose the optimal stepsize in DA and still relies on a computationally intractable sampling oracle.
Preliminaries
In this section, we introduce the problem setting and FTPL [Suggall and Netrapalli, 2020]. Assumption 1. The feasible set K. is bounded and has -ic-deieeter at most D, i.e., for all x,y K.
||x x | < DD
Assumption 2. The sequence of loss functions fi(-) are L-Lipschitz with respect to f--ormm, i.e., for x,l E K. [f((x) - f(()) $ L ||x 1 y-l1-
We proceed to introduce FTPL Algorithm 1, which is the subroutine of our algorithms. FTPL relies the offline optimization oracle below [Suggala and Netrapalli, 2020].
Definition 1. An offline optimization oracle takes input as a function f()) : K. + and d-
dimensional vector and returns an approximate minimizer of x + f(x) (a, x). An optimization
oracle is called "(a, apaprroxiee optimization oracle" if it returns x" E K. such that
f(x") (a. x*) < inf [f(x) - (a, x)] + (a 3 [1 xEX
We denote such an optimization oracle with O.,8 (J: o)..
Given the access an (a, apprrxiieee optimization oracle, the main idea of FTPL is add small perturbation to the cumulative loss and follow the "perturbed" leader:
X = Oa.8
(5)
i
where o, E IRd is a random perturbation such that Tz.j, the j-th coordinate of a,, is sampled from the exponential distribution with parameter 7), that is
for 19-1 i.dd
Exp(r).
(6)

---

Algorithm Follow the Perturbed Leader (FTPL)
1: Input: feasible set K. approximation optimization oracle O,,s, parameter of exponential distri-
bution !
2: for to 7 do
3: Generate random vector d; by (6)
4: Predict according to (5)
5: Observe loss function fr(-)
6: end for
Algorithm 2 FTPL-D
1: Input: feasible set K. length of interval approximation optimization oracle Oa,g, parameter of exponential distribution !)
2: for t 1 to I" do
3: Compute 8y = [[t 1)/rl +
4: Generate random vector by (6)
5: Predict x according (7)
6: Observe loss function ft(.)
7:
end for
Remark. We choose FTPL as our subroutine due to its simplicity and reasonable assumption of the optimization oracle. However, it is worth noting that methods not limited to FTPL alone. We can choose any algorithm that has a static regret guarantee in online non-convex learning and extend it dynamic environments.
4 Online Non-convex Learning with Dynamic Regret
In this section, we propose our first algorithm named FTPL-D based on FTPL and establish a dynamic regret bound with the prior knowledge of Vr. After that, propose the second algorithm named FTPL-D+ which is equipped with the same bound without the prior knowledge Vr.
4.1 Follow the Perturbed Leader with Dynamic Regret
Let dynamic regret defined in (2) be the performance measure. Our goal is to bound the dynamic regret by the functional variation Vr.
Following the work of Besbes et al. [2015], we apply the restarting strategy to FTPL. The key idea is to partition the time horizon T' into consecutive intervals, where the length of cach interval is controlled by a parameter y,, and then restart FTPL at the beginning of each interval. Our algorithm, which we call follow the perturbed leader with dynamic regret (FTPL-D), is described in Algorithm At each time step f, we mark the beginning of the current interval as 8, in Step 3. Then FTPL-D follows the perturbed leader within the current interval, which spans from Sy f. Specifically,
Da,
E
Σ ft fi
The following theorem presents the dynamic regret of Algorithm for general non-convex functions. Theorem 1. Under Assumptions and 2, and setting 1 = 1/ /dy, Algorithm 2 ensures
20(a, B, T) + 2vVr,
E R <
where
c(a, B,7) 125DI 125.112 (21 D)d
21a + 2dL.3
(8)
20
20
the value of VT is known, by choosing 7 = min
T . we have
E E So (11 ST)T (Vr - +1)
5

---

Algorithm 3 FTPL-D+
1: Input: feasible set K, R/ = {,,... YN step size
2: Activate a set experts [E 7/4 E H by invoking Algorithm for each "/s E H
3: For each expert Fi,, set w = 1/N for i [N]
4: for to T do
5: Receive x from each expert Eg
6: Draw according to P (x4 x w
7: Output x and observe loss function (+(.)
8: Update the weight of experts according to (9)
9: Send loss function fe(-) to each expert E;
end for
Remark. Theorem demonstrates that for general non-convex functions, when a O(1/vI and 3 O(/TT), which mirrors the settings used by Suggala and Netrapalli [2020, Page 4], our FTPL-D achieves an O(T3 (Vr + 1) dynamic regret bound that matches the existing bound for convex functions [Besbes al., 2015].
4.2 FTPL-D+
The dynamic regret in Theorem requires the prior knowledge of Vr to choose the optimal parame- ter y. However, in practice. Vr is usually unknown, posing a challenge in selecting the best y. Studies on OCO also encounter the problem of searching for the optimal parameter for their algorithms [van Erven and Koolen, 2016, Zhang et al., 201 8a, Wan et al., 2021, 2024]. The main idea in their solutions is activating multiple instances of their algorithms as experts, and tracking the best one with a meta-algorithm such as Hedge [Cesa-Bian Bianchi and Lugosi, 2006], which assigns a weight to each expert and computes the weighted average of their advice.
Inspired by the above idea, choose FTPL-D the expert algorithm and propose our second algorithm called improved FTPL-D (FTPL-D+). Note that both the loss functions and the feasible are non-convex, so we cannot combine different experts' predictions by the weighted average. According to the discussion of Besa-Bianchi and Lugosi [2006, Chapter 4.1], we can tackle this issue by randomized sampling, where we sample one expert according the weights, and then output the prediction of that expert.
The details of FTPL-D+ first define a set H = (TI,..., 7N of N values for parameter 7. Then we activate a set of experts {E, 7 E H} by invoking Algorithm 2 as E, FTPL-D(K,, 7i, .a 11). For each expert E,, denote its weight round wi, which is initiated w/ 1 1//N. At each round f, receive a prediction x; from the expert Fz. To utilize these predictions xx; E [N]], we select x with the probability wi and submit as the output x,, i.e., P (x: = x)) = wf. After the loss function revealed, we update the weights according to the following rule -iesa-Biancch and Lugosi, 2006):
shown in Algorithm 3, and deseribe the main steps below. We
wie Pfe(())
wi +1
E wfe-
where p > is the step size. We present the dynamic regret of Algorithm 3 in the following theorem.
Theorem 2. Let H = (7 = 2 = 1,...N) where N = [loga T),, and IDI
8ln N
Under
T
Assumptions/ I and Algorithm 3 ensures
E RR s O aa+
Remark. Theorem shows that our FTPL-D+ achieves the same order of dynamic regret bound as Algorithm 2 without the prior knowledge of Vr.

---

4 1[ 1[
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
T1
1
I2
Ia
I4
Figure 2: Graphic illustration of Geometric Covering intervals [Daniely et al., 2015] from Figure of Zhang et al. [2019). In the figure, each interval is denoted by
Algorithm 4 FTPL-A
1:
for 1 1 to 7 do
2:
for / C, do
3:
Create an expert E, which runs FTPL with 1/ /
4:
For the expert F,, set - Cr-111 = Add expert E to the set of active experts AA.
5:
6:
end for
7:
Remove all experts who end at the round / from Ar
8:
Receive the predictions Xr, of each expert E, E A, and calculate its weight w1, r by (10)
9:
Draw according to P (x, xt.1) = W1,I
Output x; and observe loss function fi(-)
11: Compute the instantaneous expected loss defined in (11)
For each expert F, E Ar, update Re, and Ct z by (12) 13: Send loss function fe(.) to each expert EJ E A
end for
5
Online Non-convex Learning with Adaptive Regret
In this section, we further consider strongly adaptive regret defined (4) as the performance metric in dynamic environments. We develop our third algorithm, named follow the perturbed leader with adaptive regret (FTPL-A), and establish its adaptive and dynamic regret bounds.
Previous research on adaptive regret [Hazan and Seshadhri, 2007, Daniely et al., 2015, Wang et al., 2024] has adopted two-layered framework design adaptive online algorithms. The basic idea is to dynamically construct a set of intervals and run expert algorithm to minimize the static regret within each interval. These experts are then combined by a algorithg. Building upon this idea, our FTPL-A includes three components: an expert algorithm, set of intervals, and a meta-algorithm. In the following, we illustrate them separately.
First, we FTPL as the expert algorithm, which enjoys O O(ViT) static regret for given interval (Suggala and Netrapalli, 2020]. Then, following the work of Daniely et al. [2015], we build geometric covering (GC) intervals shown in Fig. 2:
-=
I
U In. AEN
Is f (f 11+1)-22 1]:1EN).
That is, each I₃ a partition [N(,,.... 2k - 1} into consecutive intervals length 2* For each interval / E I, we activate an instance of FTPL. as the expert E2 to minimize the regret over T.
Next, we choose AdaNormalHedge [Luo and Schapire, 2015] track the best expert. Similar the Hedge forecaster we used in FTPL-D+, we maintain a weight for each expert, but in a specific form of potential function:
[
+ ((R,C) exp
3C
where [z]+ = max(0, x) and (0, 0) is defined to be 1, and the weight function is determined by
w RR C) (
Due to the non-convexity of the loss functions, as explained in Section 4.2, we use randomized sampling to generate the output.
7

---

The procedure of FTPL-A is summarized in Algorithm 4. We describe the main steps below. For brevity, we denote the of intervals starting from round as C, and the set of active experts at round i as A.. In Step 3, for each interval E Ct. we run an instance of FTPL as Fy with the optimal parameters. Step 4, the two variables R,-1./ and Ct-1./ / are initialized as for Er, where R, denotes the expected regret of F, up to round & - 1, and Ct-1,1 denotes the expected absolute regret. In Steps and 7, the active expert set A, is maintained by adding new experts and removing expired ones. In Step 8, the expert's weight is calculated by [Luo and Schapire, 2015]:
((R4-1,1,C--1.)
W4.1 = Σ EEEA, ((Rt-1,1,C(-1.))
(10)
Similarly, we sample one expert (prediction) according to the weights in Step 9, and submit it as the output in Step 10. In Step 11, the instantaneous expected loss is computed as the weighted average of different experts" losses:
[xxx))
Σ (xx,))
(11)
ErEA,
where Xx, denotes the prediction of expert E, at round In Step 12, we update Re, and Ct,7 by - -
C.-1, + [F((x)) fx((x)))
R = R
(12)
dDI.
dDL
The following theorem demonstrates the strongly adaptive regret bound Algorithm for general non-convex loss functions.
Theorem 3. Under Assumptions and 2, Algorithm 4 ensures
E [T) < (, ( VF= VV=ooVrlogT aor at + (r8))
where g(T) 51+ +n In (1 (1+ log T' In 54310 (1+T) and c(a, B, is given in (8).
Remark. Theorem demonstrates that when a = O(1/T)) and 3 O(1/T), FTPL-A A is strongly adaptive with the same order of O(vr log 7') regret as that for convex functions [Jun et al., 2017].
Furthermore, we notice that Zhang et al. [2018b] investigated the relationship between adaptive regret and dynamic regret. They showed that dynamic regret can be bounded by the strongly adaptive regret and the functional variation. According their findings, have the following theorem that presents the dynamic regret bound of Algorithm 4.
Theorem 4. Under Assumptions and 2, Algorithm ensures
E [ S ( (L++vV++ +
Remark. Theorem shows that FTPL-A achieves nearly the same dynamic regret as FTPL-D++ indicating its ability minimize adaptive and dynamic regret simultaneously. However, compared to FTPL-A, FTPL-D+ does not require the construction of GC intervals and uses a simpler meta- algorithm, making it easier implement.
6 Application to Online Constrained Meta-Learning
Online non-convex learning offers wide range of applications [Neel et al., 2020, Vietri et al., 2020, Ghai al., 2021, Castiglioni et al., 2022]. By applying our methods, we can extend these applications to dynamic environments. In this section, we discuss the application to online constrained meta-learning [Xu and Zhu, 2023] and conduct experiments to support our theoretical results.
Online constrained meta-learning. Meta-learning, also known as Marning-to-leany focuses on acquiring prior meta- partappr that enables fast adaptation new tasks. Recently, Xu and Zhu [2023] proposed the setting of online constrained meta neta-learning, which aims to learn the meta- parameter from sequence of constrained learning tasks (Ti,.... Tr). Each task T, characterized by its data distributions D, and constraint limits At each round I, training dataset Dir,, which contains data sampled i.i.d. from D,, is available to the learner. Then the learner adapts the meta- parameter o; to the task-specific parameter 0, by a within-task algorithm Alg with D and et. After
8

---

x12
X12
FTPL
FTPL
FTPL
Indartanesus
100-
Camuletten loss
FIPLA
Camuletiee
ITPL-Be
50
100
150
200
50
1,00
150
200
50
100
250
200
50
300
150
200
(a) Envl: instantaneous loss (b) Envl: cumulative loss (c) Env2: instantaneous loss (d) Env2: cumulative loss
Figure 3: Results of meta-imitation learning in two types of dynamic environments. The first two figures are for abruptly changing environments (Env1), while the latter ones for gradually evolving environments (Env2).
the learner deploys Oz, it obtains validation dataset Dral by sampling data from Dr and defines the meta-ohjective function at current round as
chaa C(Alg(ó, D.",, .c),, (,))))"))
where L(0, Dioa)) denotes the loss of 0 Drat Xu and Zhu [2023] updated the meta-parameter by using FTPL to the non-convex meta-objective function on all revealed tasks. With this approach, they effectively controlled the static regret of the meta-objective function between di and the fixed optimal meta-parameter 6* However, when the distribution of tasks is shifting, the fixed ø* may not be adapted to each task well. In such scenario, it is better use dynamic regret or adaptive regret as the performance metric. since they measures the learner's s performance against the changing optimal meta-pe pertme.rrmmete.. By applying Algorithms 3 and 4, we can minimize the two metries efficiently, To evaluate our methods, we conduct experiments on a sequence of tasks in imitation learning and another in few-shot learning, respectively.
6.1 Experiments on meta-imitation learning
Setup. We use the demonstration data given by Huang et al. [2019] and set the total number of tasks = 200. At each round / [T]. a human expert writes different letter in free space without obstacle. The learner can observe demonstration of the letter and is asked to write the same letter in cluttered environment. We provide the details of problem formulation and implement setting in Appendix C.I. By controlling the letter to be imitated for each task, we simulate two types of dynamic environments: (i) abruptly changing environments; (ii) gradually evolving environments. In (i), we split the time horizon evenly into 4 stages, and set the imitation target as capital letters "M", "E", "T" and "A" for the stages. this way, the optimal meta-parameter d* drifts notably every 50 round. In (ii), we choose the capital letter "A" as the imitation target. Additionally, we rotate the letter "A" at a small random angle 5, E (0, 0.05] in each round. This ensures the optimal meta- peta-parameter ø² undergoes slow and smooth shifts. We compare our FTPL-D+ and FTPL-A with FTPL [Suggala and Netrapalli, 2020] the above two scenarios.
We repeat the experiments five times with different random seeds and plot the loss (mean and standard deviation) in Fig. More results are provided in Appendix C. For abruptly changing environments, Fig. 3(a) shows that, in comparison to FTPL, our methods adapt more quickly to the new task distribution after the demonstration shifts, which occurs at T 50, 100, and 150. Fig. 3(b) demonstrates that our methods perform significantly better than FTPL in terms of cumulative loss. For gradually evolving environments, it can be observed from Fig. 3(c) that as the angle of rotation increases, both our methods maintain low loss, while FTPL exhibits significant increase in instantancous loss after = 100. Fig. 3(d) also shows a notable advantage in cumulative loss. Moreover, FTPL-D+ and FTPL-A achieve comparable performance in the two types of dynamic environments.
Results.
6.2 Experiments on few-shot image classification with robustness
Setup. We conduct the experiments on CUB-200-2011 (referred to as CUB) dataset [Wah et al., 2011], which includes 200 fine-grained categories of birds. There are T 150 robust 5-way 5-shot image classification tasks, each task containing images from 5 classes with only training samples per class. At each round [T), the model is updated using a few data samples and required to have high accuracy on both clean and perturbed test data. We provide the details of problem

---

0.55
FIPL
FIPL ETP Lo
ITPL-A
FTRL-A
0.55
Clean accurscy
0.55
PGD acuracy
0.50
FTRL-D+
0.50
FTP1
0.45
0.50
0:40
0.40
0.35
0.40
0.30
0.35
0.30
100
150
50
150
50
150
Round (task index)
Round ftask indded
Round (task indext
(a) Clean accuracy
(b) PGD accuracy
(c) B-score
Figure 4: Results of robust few-shot learning on the CUB dataset (5-way 5-shot) in dynamic envir environments.
formulation and implement setting in Appendix C.2. We resize the input images to 84 x 84, and apply the same data augmentation in Ye et al. [2021] and Xu and Zhu [2023]. A four-layer convolutional neural network (Conv-4) is employed as the backbone, comprising four blocks. Each block consists of convolutional layer with 64 kernels of size 3 x 3, stride 1, and zero padding. followed by a batch normalization layer, ReLU activation function, and lastly a 2 x 2 max-pooling layer. Following the convolutional layers, the network uses fully connected linear layer with neurons classifier to output the prediction for the input image. To simulate real-world dynamic environments, we select three groups of bird categories from the CUB dataset based their habitats: water birds, forest birds, and grassland birds. We then split the time horizon T evenly into 3 stages, within each stage the tasks are sampled from one group of bird categories. This simulates abruptly changing environments where the optimal meta- veta-parameter o* drifts every 50 round. We compare our FTPL-D+ and FTPL-A with FTPL [Suggala and Netrapalli, 2020].
Metries and results. The performance of the task-specific model is evaluated by: (i) clean accuracy; (ii) PGD accuracy; (iii) B-score. The clean accuracy the accuracy on the clean test dataset, and PGD accuracy is the accuracy on the corrupted test dataset, which is obtained by adding perturbation on the clean test dataset by the Projected Gradient Descent (PGD) method [Krrkiin et al., 2018]. Balance Score (B-score) Ye et al., 2021] measures both clean accuracy and PGD accuracy. It is defined as B-score x (CA x PA)/(CA + PA), where CA and PA denote clean accuracy and PGD accuracy respectively. We report the three metrics against the number of tasks in Fig. 3. As evidenced by the results, FTPL-D+ and FTPL-A attain comparable performance, and both significantly outperform FTPL in terms of all three metrics after the environmental changes at T = 50 and 100. This suggests that our methods are effective in rapidly adapting to the new task distribution.
Conclusion and Future Work
This paper investigates online non-convex learning in dynamic environments, using dynamic regret and adaptive regret as performance metrics. For dynamic regret minimization, we propose FTPL-D with an 3 (Vr + 1)4) regret bound. To eliminate the dependence on prior knowledge of Vr, we propose FTPL-D+, which runs multiple instances of FTPL-D and uses meta-algorithm to track the best one. For adaptive regret minimization, we propose FTPL-A with regret bound of OVVTlog T). Finally, we discuss the application to online constrained meta-learning, and the conducted experiments verify the effectiveness of our methods.
Currently, we bound the dynamic regret by the functional variation. A natural problem is whether can derive regret bounds based on other regularities, such as the path length of comparators that is widely used in prior works for non-stationary online convex optimization [Zhang et al., 2018a, Zhao et al., 2020, 2024, Baby and Wang, 2021, Cutkosky, 2020]. This is left as future work to explore.
Acknowledgements
This work was partially supported by NSFC (62361146855 62122037), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
10

---

References
Jacob Abernethy, Peter Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings the 21st Annual Conference Learning Theory, pages 414-424, 2008.
Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov and Vladimir Vovk. A closer look at adaptive regret. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, pages 290-304, 2012.
Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Proceedings of the 32nd Annual Conference on Learning Theory, pages 18-29, 2019.
Sergul Aydore, Tianhao Zhu, and Dean P Foster. Dynamic local regret for non-convex online forecasting. In Advances in Neural Information Processing Systems 32, pages 7982-7991, 2019,
Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation--oundee sequences. In
Advances in Neural Information Processing Systems 32, page 11071-11081, 2019.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Annual Conference on Learning Theory, pages 359-409, 2021.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 1805-1845, 2022.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research,
2015.
Aude Billard, Yann Epars, Sylvain Calinon, Stefan Schaal, and Gordon Cheng. Discovering optimal imitation strategies. Robotics and autonomous systems, 47(2-3):69-77, 2004.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. unifying framework for online optimization with long-term constraints. In Advances in Neural Information Processing Systems 35, pages 33589-33602, 2022.
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press. 2006.
Nicolò Resa-Bianchi and Francesco Orabona. Online learning algorithms. Annual review of statistics and its application, 8:165-190, 2021.
Luiz Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning. In Advances in Neural Information Processing Systems 33, pages 16722-16735, 2020.
Ashok Cutkosky, Parameter-free, dynamic, and strongly-adaptive online learning. In Proceedings of the 37th International Conference on Machine Learning, pages 2250-2259, 2020.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwarzz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pages 1405-1411, 2015.
Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth. Using and combining predictors that specialize. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 334-343, 1997.
Xiand Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, pages 235-243, 2018.
Udaya Ghai, David Snyder, Anirudha Majumdar, and Elad Hazan. Generating adversarial disturbances for controller verification. In Proceedings of the 3rd Learning for Dynamics and Control, pages 1192 1204, 2021.
Ziwei Guan, Yi Zhou, and Yingbin Liang. Online nonconvex optimization with limited instantaneous oracle feedback. In Proceedings of the 36th Annual Conference on Learning Theory, pages 3328-3355, 2023,
11

---

András Gyorgy, Tamás Linder, and Gábor Lugosi. Efficient tracking of large classes of experts. IEEE Transactions on Information Theory, (1((1))7709-62555 2012.
Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via proximal-gradiene approach. In Proceedings of the 38th International Conference on Machine Learning, pages 4008 4017, 2021.
Elad Hazan and Edgar Minasyan. Faster projection-free online learning, In Proceedings of 33rd Annual Conference on Learning Theory, pages 1877-1893, 2020.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium Computational Complexity, 14(88), 2007.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games. In Proceedings of the 34th International Conference on Machine Learning, pages 1433-1441, 2017.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-325, 2016.
Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non-convex optimization with imperfect feedback. In Advances in Neural Information Processing Systems 33, pages 11222-172355 2020.
Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Zeroth-order non-convex learning via hierarchical dual averaging. In Proceedings of the 38th International Conference on Machine Learning, pages
2021.
Yanlong Huang, Leonel Rozo, Joao Silvério, and Darwin G Caldwell. Kernelized movement primitives. The International Journal of Robotics Research, 38(7):833-852, 2019.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference Artificial Intelligence and Statistics, pages 398 406, 2015.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 943-951, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ArXiv preprint, arXiv:1412.69800 2014.
Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The hedge algorithm on continuum. In Proceedings of the 32nd International Conference on Machine Learning, pages 824-832, 2015.
Alexey Kurakin, Ian J Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In Artificial intelligence safety and security, pages 99-112. Chapman and Hall/CRC, 2018.
Antoine Lesage-Landry, Joshua Taylor, and Iman Shames. Second-order online nonconvex optimization. IEEE Transactions on Automatic Control, 66(10)4866-4872, 2020.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-2611 1994.
Haipeng Luo and Robert E Schapire. Achieving all with parameters: Adanormalhedge. In Proceedings of the 28th Annual Conference on Learning Theory, pages 1286-1304, 2015.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control, pages 7195-7201, 2016.
Seth Neel, Aaron Roth, Giuseppe Vietri, and Steven Wu. Oracle efficient private non-convex optimization. Proceedings of the 37th International Conference on Machine Learning, pages 7243-7252, 2020.
12

---

Francesco Orabona. A modern introduction to online learning. ArXiv preprint, arXiv:1912.13213 2019.
Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra. Multi- point bandit algorithms for nonstationary online nonconvex optimization. ArXiv preprint, arXiv:1907.13616, 2019.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pages 845-861, 2020.
Tim van Erven and Wouter M Koolen. Metagrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29, page 1666-3674, 2016.
Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. New algorithms for private synthetic data release. In Proceedings of the 37th International Conference on Machine Learning, pages 9765-9774, 2020.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-ucsd birds-200-2011 dataset. Technical Report CNS-TR-201 1020001100111 1-001, California Institute of Technology. 2011.
Yuanyu Wan, Bo Xue, and Lijun Zhang. Projection free online learning in dynamic environments. In Proceedings of the 35th AAAI Conference on Arlificial Intelligence, pages 10067-10075, 2021.
Yuanyu Wan, Lijun Zhang, and Mingli Song. Improved dynamic regret for online folfe- In Proceedings of the 36th Annual Conference on Learning Theory, pages 3304-3327,,2 2023.
Yuanyu Wan, Chang Yao, Mingli Song, and Lijun Zhang. Non-stationary online convex optimization with arbitrary delays. In Proceedings of the 41st International Conference Machine Learning. pages 49991-50011, 2024.
Yibo Wang, Yuanyu Wan, Shimao Zhang, and Lijun Zhang, Distributed projection-free online learning for smooth and convex losses. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 10226-10234, 2023.
Yibo Wang, Wenhao Yang, Wei Jiang. Shiyin Lu, Bin Wang, Haihong Tang, Yuanyu Wan, and Lijun Zhang. Non-stationary projection-free free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pages 1567 15671-15679, 2024.
Siyuan Xu and Minghui Zhu. Online constrained meta-learning: Provable guarantees for generaliza- tion. In Advance in Neural Information Processing Systems 37, pages 15531-15544, 2023.
Lin Yang, Lei Deng, Mohammad H Hajiesmaili, Cheng Tan, and Wing Shing Wong. An optimal algorithm for online non-convex learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(2):1 22, 2018.
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 Proceedings of the 33rd International Conference Machine Learning, pages 449-457, 2016.
Wenhao Yang, Wei Jiang, Yibo Wang, Ping Yang, Yao Hu, and Lijun Zhang. Small-loss adaptive regret for online convex optimization. In Proceedings of the 41st International Conference on Machine Learning, pages 56156-56199 2024.
Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi-objective meta learning. In Advances in Neural Information Processing Systems 34, pages 21338-213511 2021.
Lijun Zhang. Online learning in changing environments. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 5178-5182, 2020.
13

---

Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advance Neural Information Processing Systems 30, pages 732-741,2011
Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou. Adaptive online learning in dynamic environments, In Advances in Neural Information Processing Systems 31, pages 1323-1333, 2018a.
Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference Machine Learning, pages 5882-5891, 2018b.
Lijun Zhang, Tin-Yan Liu, and Zhi-Hua Zhou. Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning, pages 7414-7423, 2019.
Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simul- taneously. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pages 309-319, 2020.
Lijun Zhang. Guanghui Wang, Wei Wei Tu, Wei Jiang, and Zhi-Hua Zhou. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. In Advances in Neural Information Processing Systems 34, pages 24968 24980, 2021.
Lijun Zhang, Wei Jiang, Jinfeng Yi, and Tianbao Yang. Smoothed online convex optimization based wwwpoouttedd-oma---eeeeeeieeeeee 4928-9942, 2022.
In Advances in Neural Information Processing Systems 35, pages
Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Conference Learning for Dynamics and Control, pages 48-59, 2021.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances Neural Information Processing Systems 33, pages 12510-12520, 2020.
Peng Zhao, Yan-Feng Xie, Lijun Zhang, and Zhi-Hua Zhou. Efficient methods for non-stationary online learning. In Advances in Neural Information Processing Systems 35, pages 11573-1158. 2022.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936 2003.
14

---

A Theoretical Analysis
A.1 Proof of Theorem
Let 7. = (i - 1 for = 1,...,r, and gr+1 = +1 First, we decompose the dynamic
regret as
T
T
RD =
fx(x))
- Σ
min fi(x) xE
t=1
t=1
91+1
91-1-1 Σ
f((
min fx(x) xER
Q-41-1
9:t1-1
9--1-1
4:41-
f((x))
min
Σ fx(x)
min
Σ
f((x)
Σ
min
f((x))
(13)
XEK
t=
t=
Taking expectation with respect to X on both sides of (13), we have
E
[16p]]
9-+1-1
g++1
g++1-1
90+1-1
E
f((x))
min XEK t=
Σ
f((x)
min xER
Σ
f((x)
Σ
min f((x)
xek
1=
t=
t=
0c+11 1
0441-1
4i+1
9
Σ l=q:
f((x))
min
Σ fx(x) t=
+ min
f((x)
min xEk
fe(x)
(14)
XER
xEK
t=
0,
To bound 0;, we introduce the following lemma, which presents the static regret of Algorithm 1. Lemma 1. (Theorem I in Suggala and Netrapalli (2020]) Suppose Algorithm is using an (ax, B)- approximate optimization oracle. Under Assumptions I and 2, for any fixed Algorithm ensures
fx(x) < DLL d(213T +D) + 21aT
E
Σ (x(x))
min xEK
23dLT.
20n
20
By applying Lemma to each interval E [r], we get
4+41 1
9++1-1
d(213; + D)
+ 21a7
Σ
f((x))
min XER
Σ f((x)
< 125 DI²
+ 28dLy.
20n
20
t=
Let Vdyy
then we have
4b41
9641-1
a; = E
f((x)) - min
Σ f((x)
$ &cla.B,1VV.
(15)
xEX
t=
where c(a, 3, = 125DL (D1a+
21av 20
+ 2dL,3
20
To bound b; we follow the proof of Theorem 3 in Zhang et al. [2018b]:
9-41-1
T
b, min
Σ
f((x)
Σ
min
f((x)) xek
XEK
t=
9:+1-1
9--11
Σ
f((x;)
Σ f((x²)
1=q.
l=
< |git1
qil
max
(fe(xtg) -f((x)))
(16)
telg.9941111
15

---

where x E arg min (x)... xEA
Define the local functional variation of the i-th interval as
9++1
Vi(i) =
max xe
[f((x) - 1x)1(x))
and it is obvious that E1=1 Vir I VT.
For any E [gts q++1 - 1], we have
f((x))) f((x;) ff((x (x
- fe (x + (x), f((x))
(x() -fa (x,, + (x,) (xx)
(1V.
(17)
Combining (16) and (17), obtain
b, 2 qel (i) S 2yV%(()
(18)
Substituting (15) and (18) into (14), we have
R 1
T <o B,7)
V7+ Σ (1)
cla B.)
2/
(19)
where the last inequality uses Ei Vi( S VT and r
[ < I -1 27.
We proceed to prove the second part of Theorem For brevity, let = c(a, T). By the definition
in (8), we have c(a, () S for any 7 S T. VT 2 - Algorithm 2 with > $
achieves
E [ < (2 r v
If Vr J Algorithm 2 with 7 T ensures
E [Rtb]] S (20+ 2) VT.
Combining the results above, with the prior knowledge of Vr, we have
E [RDb S max { (2v2c + z.vă (22 2) 2) = -LL 1))
A.2 Proof of Theorem 2
The dynamic regret of the Algorithm can be devided into two parts: expert regret and meta-regret, as shown below
T
E
Σ f(
min fo
fx)
xek
T
T
T min
E
(xx)
f((x))
+E
Σ
(x
- Σ
fx(x)
(20)
xeR
[=1
regrel
regret
where x denotes the prediction of the i-th expert.
16

---

To bound the meta-regret we follow the proof of Theorem 2.2 in Cesa-Bianchi and Lugosi [2006] and introduce novel quantity In Wr. Wo"
We define
W. Σ W = N,
pLi
121
where Li -i=Et= (x{) of experts. Besides, weight of expert at round can be writen as
denotes the cumulative loss of the i-th expert and N denotes the number
6 -LiL1
(21)
Σn= -PLL
First, give lower bound of In Wr.
Wo
WT
In
In
Σ plis
IINN
Wo
2 In
max
-plit
-In
i=l....
=-
min
f((x)) In
(22)
To upper bound In Wr.
Wo we introduce the following lemma of Hoeffding's inequality.
Lemma 2. (Lemma A.I I in Cesa-Bianchi and Lugosi [2006]) Let X be random variable with a S X S Then for any 8 E IR
IE [e S &EX + (b a)²
(23)
8
Note that at each round sample expert (prediction) by P (x; =x) wi. and incur the loss of that expert. Hence, the loss incurred by the meta- meta-algorithm is random variable fx()) with probability P [f((x,) = [x(x)] = w/. and the expected loss
E [fx( = Σ (x))
(24)
Under Assumptions and the difference between the maximum and minimum of the loss function at each round can be bounded as
sup [((() - fely)) dDL. xye
(25)
Observe that for each = 1, I,
In W = In
W.
N
2i=1 e ppLi -p(((()))
(21)
In
N
w
(x()
Σn -LL_1
Now using Lemma 2, we have
In
W
In Σ
wie- (x(
W
(23,25)
wxf((x))) + (dDD2)
8
(24)
+ (dDL)
(xE(f((x))
(26)
17

---

Summing over t ,,.... T. we have
W
+ (dDL2)
In
I -pB
Σ f((xi)
(27)
Wo
By combining (22) and (27), we get the meta-regret-boond as follows:
I
pd(DLL)
IN
E
f((x))
min
f((x))
S dDLy
(28)
P
8
where p dDL
8ln
We proceed to present the dynamic regret of the best expert. Let H = { = 2 = 1......N ] where N = [log2 TJ. Assuming the optimal restarting parameter in Theorem is y", tthn there exists some & such that 7 5 S 7k++1 Moreover, have
T 2 Th S S74t1 2
(29)
According to Theorem 1, for any expert we have
RRD E
Σ fx(x))
Σ
min fi(x) xeR
2²T
2%;
(30)
Vi
where é c(a,, 8, T) given in (8).
Then, for expert ls and k + 1,
E
(30) 22T
+ 2nx VT S
22T
+ 2y
(29)
v2
22T
+ 2x 22 Vrr)
(31)
Tk
V 1/-"
and
(30)
2ET
20T VT
(29)
( 20T
E
[
+ 27 VT <
+ VT
I 2
+ 27 2T²VT
(32)
(TT
7x+1
From Theorem 1, can be inferred that
E
P
2²T
+ 2 S max (2V26+ (20 2)
(33)
Hence, the dynamic regret of the best expert can be bounded as
min
E
[
min
E
E
[
(31,32)
22T
2
+ 2/
(33)
max
(42+ 2/2)233222/2 (3.2//33/.002222+++. 2VV22+2/22TT//
(34)
Substituting (28) and (34) into (20), we get the dynamic regret of Algorithm 3:
[R5] < max {
2 (2 + + dDL In NT
= -I
A.3 Proof of Theorem 3
The analysis consists of two parts. We first upper bound the strongly adaptive regret over any interval j.j] I. Then, extend the regret bound to any interval [s, + - S [T].
18

---

For any interval J = [i,j] E I. we can decompose the regret as
fx(x))
min
(x(x))
XEX
E
(xx))) Σ (((x).)) + Σ f((x,)))
-min XER
Σ
f((x)
E
(x())) Σ f((())))
+
f((x).))
min
fi(x)
(35)
meta-regree
expert regret
According to Lemma and (15), we have the following expert regret
E
f((x).))
min E f((x)) s cla, scla,111JlV/11
(36)
Next, we analyze the meta-regret. Let Ne denote the total number of experts that have been seen up round f. Recall the definition of GC intervals:
I U- Ik. KEN
Is {[i 2 (1+ -
For every k that satisfies 2* < t, we have that single interval in I₁ contains t. Since we activate an expert for each interval, the number of active experts at round + [log2 t.. Taking each round into account, it is easy to verify that
N₂ S t(1 + loga t).
(37)
For interval J, we denote the regret at round L. as Ti.J. By (25), we scale Tt, to ensure
Tt,J dDL ( f((x),)) [-1,1]]
(38)
Then, according Theorems 1 and in Luo and Schapire [2015], we have the following lemma. Lemma 3. Under Assumptions I and 2, for any interval J [i. I, Algorithm 4 ensures
j
Σ
T& S V3g(T)
(39)
where
5+3 5)) (37)
5 5+3ln (1 + +
o( $1) + in 2
1 1+ Inj + In (1 + logg.) + In
2
Combining (38) and (39), we obtain that
i(x.)) Σ ((x.)))) = dDL Σ TCJ < dDL
(40)
Note that each round f, sample x, by P(x xx,,) = We,J. Thus, the expected loss incurred by the meta-algorithm is
E [f(())]]
Σ (e,,)(
(41)
E,E.A,
Also note that (xxx is defined as the weighted average loss of all experts, which is of the same form as (41), i.e.
f((x))= Σ (ix,)((
(42)
ELEAL
19

---

Replacing the weighted average loss in (40) by expected loss, we have
E ((x.))) s dDLv33(5MM
E
fx():)
(43)
Combining the expert regret in (36) and the meta-regret in (43), we obtain that
E
Σ
f((x))
min xeR
S + dDL,
(44)
where g(i) - 1 Inj+jjj In + log2 + In 5+31n(1+j)
In the following, extend the regret bound over J to any interval / [s, 15.8+75 introduce a property of GC intervals as below.
[T]. We first
Lemma 4. (Lemma 1.2 Daniely et al. [2015]) For any interval = 18,8 1 1] S [T. can be
partitioned into two sequences of disjoint and consecutive intervals, denoted by T -p- ... To E DD and
T1,..., Ig E 'D, such that
| S 1/22,122 and [
According to Lemma 4, we have that
r+--1
Σ F1(x)) 1
fx(x))
min xER
Σ fx(x)
Σ
Σ
f((x))
min
xEK
LEE
EEZ.
(c(o. / 1)]
(d -1)1=l)
( 1)2-iT)
20DL VT Σ
V2-i
i=0
(Sc(a, B,7) 8dDL 3g(s + -) VT.
(45)
Hence, the strongly adaptive regret of Algorithm 4 is
+++-1
E (T,)
max 10+7--1/C11
E
fx(x)) - min
Σ t=
f1(x))
XEK
<
B,T) (8)(
SdDL 3g(T))
VT= O1 / log T + + Br²),
(46)
where g(T) S 1 + In + In (1 + log, T) + In 5+33n (1+7)
A.4 Proof of Theorem
The analysis is similar to Corollary 5 in Zhang et al. [2018b], which exploits the following lemma to bound the dynamic regret by the strongly adaptive regret and the functional variation.
Lemma 5. (Theorem 3 in Zhang et al. [2018b]) Let it e arg min fe(u). For all integer is E [T].
we have
Ro(ui 17) < min
Σ (RA(T, + 2 Vi(()),
II.... Ix
where the minimization is taken over any sequence of intervals.
20

---

For our randomized algorithm, we take the expectation over both sides
E R E [ u S min Σ (R (RA((((, + 2 Vi(()).
Next, we restric to intervals of length r, and in this case K I. Then we get
E
[Rb]]
min ISTST
Σ (
E. [RAA(T,T]]
& + Vi((i)
min 15TST
==1
E [[]
min 15rST
+ +2VV/
(47)
Combining (46) and (47), we have
T
[R < min
+ 2TVT
15rS7
VF
By the fact that
5 31n +T)
+ 1og, T) +
3 + 3 log T,
2
obtain
(4d log
E R <
min ISSST
+ 2TV/
(48)
VT
In the following, we consider two cases. If VT 2
T T
we choose
T Vog T
2/3
T
ST,
VT
and have
(8c 24d log T)
T V
+ 27 v logs T
E [Rb]] <
logè
(8é + 2AdDL)
log+ + (2 (4-2D)))) T3 log T
(49)
where é = c(ax, 3, T).
Otherwise, we choose T T, and have
E R < (8c 24dDL/1++0g log
log T)
VT + 2TV
log T
<
88 2AdDL log
VT 2T
T
(8é+ (24dDL+ +og T) VT.
(50)
Combining (49) and (50), we have
(S0+2NDD)ITVV +2 (2+24dDL) log log (88 + (24dDL + / log T) VT
[Rb]] < max
(51)
= 0 (max { (1 + aa 3T) TogT (1 + a -T)T lo
log T)).
(52)
21

---

B More Related Works
In OCO, the computational effective variants of FTPL are investigated in centralized [Hazan and Minasyan, 2020] and decentrailized [Wang et al., 2023] setting. In addition to the worst-case dynamic regret defined in (2), Zinkevich [2003] also introduce the general dynamic regret, which compares the learner against any sequence of comparators
T Σ (xx.)
Rp(un UT
E Sc(u))
(53)
where U1,.... Uy E K. In this pioneer work, Zinkevich [2003] proposed a regularity of comparator sequence called path-length
Pu up) Σ U1 u.11
and showed that OGD attains O(vT(1 + Pr)) general dynamic regret bound. Zhang et al. [2018a] strengthened the general dynamic regret bound to O(vT(1 Pr)), which has been shown to be optimal. Improved results can be obtained when the online functions are smooth [Zhao et al., 2020, 2024], strongly convex [Baby and Wang, 2022] or exp-coneave [Baby and Wang, 2021]. Moreover, the computational efficiency of general dynamic regret optimization is recently considered [Zhao et al., 2022, Wang et al., 2024].
Notice that by assigning u, E arg minxek: fx(x) as the local minimizer, we get the worst-case dynamic regret in (2), and there exist numerous studies on the worst-case scenario. When the loss functions are strong convex and smooth [Mokhtari et al., 2016], or when they are smooth and the minimizers lie in the interior of I. [Yang et al., 2016], OGD can attain O + 1) dynamic regret bound, where Pj == Pr(xi..... xF) and x E arg minxeX f((x). Another regularity of comparator sequence the squared
[Zhang et al., 2017]:
T
ST = Sx
Σ 1=2
x1
- 11
which could be much smaller than the path-length P when local minimizers move slowly. Zhang et al. [2017] demonstrated that the dynamic regret bound can be reduced to (minn S + 1) for (semi-)strongly convex and smooth functions. Moreover, Besbes et al. [2015] demonstrated that
if the value of VT is known, restarted OGD achieve O (Vr + 1)å) ) and O /T(Tr 1)) dynamic regret for convex and strongly convex functions, respectively. Later, Baby and Wang [2019] + 11 for 1-dim square loss. More recently, to exploit
improved the dynamic regret to OT both comparator sequence and function sequence, Zhao and Zhang [2021] refined the analysis for online multiple gradient descent and attained an O(min Pr. ST. Vr} + 1) dynamic regret bound under the same assumption Zhang et al. [2017].
Besides dynamic regret, another metric in dynamic environments is adaptive regret. Adaptive regret is introduced by Hazan and Seshadhri [2007] to OCO, but in a weak form:
RA(T)) max [Ar]S
Σ f((x)) min XEA
Σ fe(x)
(54)
which defined as the maximum static regret over any contiguous interval. To minimize (54), Hazan and Seshadhri [2007] proposed follow the leading history (FLH) with O(VTlog" T) weakly adaptive regret for convex functions. However, this metric does not respect short intervals well since the O log T') bound meaningless for those intervals of length O(VT). To eliminate the dominance of long intervals, Daniely et al. [2015] introduced strongly adaptive regret that takes the interval length т as a parameter, as we indicate in (4). They also developed two-layer algorithms and attain O O T log T) strongly adaptive regret for general convex functions. Later, Jun al. [2017] proposed a novel meta-algorithm named sleeping coin betting (SCB) and improved the strongly adaptive regret bound O( log T))
Although both dynamic regret and adaptive regret are designed for dynamic environments, our understanding of their relationship remains limited. Zhang et al. [2018b] first demonstrated that
22

---

dynamic regret can be bounded by the strongly adaptive regret and the functional variation. Recent studies shows that it is possible to minimize dynamic regret and adaptive regret simultaneously [Zhang et al., 2020, Cutkosky, 2020, Zhang et al., 2022, Wang et al., 2024].
The metric of dynamic regret has also been investigated in online non-convex learning- Lesage- Landry et al. [2020] proposed online newton method (ONM), second-order method, achieving an O + 1) dynamic regret bound under the conditions that the starting point is located near the global optimal solution and the loss function is strongly convex around the optimal solution. Gao et al. [2018] examined class of non-conved functions that satisfy weak pseudo-come convex conditions and developed online algorithms that attain O( VT(VT + 1)) dynamic regret. They also extended their result to the bandit feedback setting. Roy et al. [2019] studied functions with weck--uusi-convexity and obtained similar results as Gao et al. [2018]. Furthermore, Héliou et al. [2020] applied their estimator. In subsequent work, Héliou et al. [2021] proposed hierarchical dual averaging (HDA) and improved the dynamic regret bounds under the same setting.
methods to bandit setting using a
C Omitted Details for Experiments
All experiments are executed on computer with a 2.50 GHz Intel Xeon Platinum 8255C CPU and an RTX 2080Ti GPU. We follow the experiment settings of Xu and Zhu [2023] and implement our methods based on their code.
C.1 Experiments on meta-imitation learning.
Problem formulation. Imitation learning [Billard al., 2004] has gained significant attention means of transferring human skills to robots. Huang et al. [2019] presents a novel formulation of imitation learning using kernelized movement primitives, which considers nonlinear hard constraints and obstacle avoidance. In their study, the states of the robot are modeled as a linear combination of basis functions, and the demonstrations provided by humans are modeled by a Gaussian mixture model (GMM). where the parameters follow a Gaussian distribution. The objective of their approach is minimize the divergence between the distributions of the robot state model and the demonstrations, while ensuring that the hard constraints are satisfied. Building upon this idea, Xu and Zhu [2023] further model the states of the robot by a neural network instead of the linear combination of basis functions.
Following the work of Xu and Zhu [2023], in this experiment, we utilize neural network model the states of the robot and GMM to model the demonstrations. Specifically, the robot's state <(w, I), which includes the joint position g(w, 1) Ro and velocity q(w, L), is parameterized by and is modeled as
q(w, g( (1 t)
E(w, ()
where g(w, t) is neural network and takes as the input and the location g(w,t) t) the output. The dataset of demonstrations consists of H trajectories, where each trajectory contains N time-state pairs. These pairs, denoted as ((/,, Em.,) > are modeled using a GMM. Each demonstration state É. associated with t, is described by conditional probability distribution with mean A. and covariance Σn, i.e., En | tn ~ (pnn, Σn,, where inn and Σn can be computed by the GMM. As formulated in previous works [Huang et al., 2019, Xu and Zhu, 2023], the imitation learning task can be cast the following constrained optimization problem:
[ (5(w,)) - (.) TE, (E(W,t) fim)
min w
E BE(l..e]] 2 g,(E(, 1)) S 44, AL No.Lwh, i i= 1,...,,,
(55)
s.t.
where 9i is the i-th state constraint, m is the total constraint number, f4, and E., are the mean and variance of the demonstration state É(t), i.e., ? {In, Ar, Exm J is provided by the GMM. It is notable that the demonstrations are collected in no-collision environment. Thus, it is possible that these demonstrations may not be able to avoid collisions effectively.
N E.). Here, the training dataset
23

---

FTPL
100
FTPLA
FTPLA
Cumulative constraint vidaation
6-
Constramt velatoon
60
1-
150
200
50
100
150
200
index)
index)
(a) Constrained violation metric
(b) Cumulative constrained violation metric
Figure 5: Supplementary results for abruptly changing environments.
In our scenario, we have a series of imitation learning tasks that are revealed sequentially. In each round a new task of Problem (55) is revealed, and its data D = (f.. Pn. En, J.y and the collision area denoted by {9: )= and {c; )e are given. Then we apply the framework of online constrained meta-learning [Xu and Zhu, 2023] and construct the meta objective at round i
L(Alg(A, o, D Di
(56)
with
Alg(A,C o, D(r) arg min L(w, DD + 2 ||
(57)
Σ (((E(w,t))) S C₁ 1, ,,.
s.t.
R=
where Lww, D(r) is the loss function of the model parameter w on a dataset Der (tas Ani En 1N and
n=1
C(w, D(w,
Σ (E(w, (n) (mx) T En (E(w, pm))
(58)
N
#=1
Next, we update de by our algorithms and compute wi = Alg(A, Φr. D(") as the task-specific model.
General setup. We use the demonstration data given by Huang et al. [2019]. In each round, the robot needs to imitate the given demonstration and write capital letter. The demonstration dataset, denoted as D'r {la, fb, E,, N n=1 consists of the sizes, angles, and locations of the letter. These sizes, angles, and locations are randomly sampled from a Gaussian distribution. The robot also needs avoid circle collision area, which defines m, 91, and C₁ in (55) as m 1, C 0.5 and 91 (z) a (-v((x) function and, r is the radius of the collision area and r = 2. The center of the collision area, denoted by (d1, d2), is sampled from the Gaussian distribution. (0 for each task. Furthermore, each task, the robot can access the full shot demonstrations including 400 data points.
d, + (I2 d2) + r), where (xx)
log(1 + cxp(3z)) is barrier
We model the position of the robot by four-layer neural network with 128 which consists of an input layer of size 8, followed by hidden layers of size 128 with the ReLU nonlincarities and an output layer of size 2. The neural network takes {t, 12 13, ,t, sin(t), cos(2t), sin(2t). cos(2t)) as the inputs and qwu, t) as the outputs. We use the Adam optimizer [Kingma and Ba, 2014] with a learning rate of 0.001 for the optimization.
We simulate two types of dynamic environments: abruptly changing environments and gradually evolving environments. For abruptly changing environments, we use the demonstration data of capital letters "M", "E", "T" and "A" for the stages. For gradually evolving environments, we rotate the letter "A" at small random angle & 0.05 in each round. Specifically, at round f, compute

---

4.0
FTAL
3.5
FTPLA
Cumuletive constreiiiiii contstrrint..oo vidaation
FTRLA
Constraint volation
3.0-
75
1.5
1.0
0.5
0
0.0
150
50
100
150
200
index)
index)
(a) Constrained violation metric
(b) Cumulative constrained violation metric
Figure 6: Supplementary results for gradually evolving environments.
the rotation angle Σ. 8,, define rotation matrix
cos 0 sin 0
sin cos 0
Rs
and then transform in and En of the dataset by
P/2 Pn E = R3 En
Supplementary results. Apart from the loss shown in Fig 3, the constrained violation is another metric considered in Xu and Zhu [2023]. We plot the constrained violation Fig and Fig 6. The results show that our methods sustain the same and even less constrained violation than FTPL. This is reasonable and can explained by Proposition 5 Xu and 7hu [2023] that the constrained violation bound holds for any meta-parameter sequence Φ1.T {ő1. dT).
C.2 Experiments on few-shot image classification with robustness
Problem formulation. Following the problem formulation in Chamon and Ribeiro [2020] and Xu and Zhu [2023], the problem of robust learning for a single image classification task Tr can be written
0r argmin EZ-D, [e(0, =)]
lee
(59)
s.l. Ez-D,,rr [e(0, =)] (1 ai) [e(0, =)] 00
where 0 < a 1 is the robustness tolerance parameter, l is the loss function, D; is the distribution of the original data, and Dr,(11 is the distribution of the perturbed data, which is generated by the PGD method D,,
In our setting, a series of robust 5-way 5-shot image classification tasks are revealed sequentially. In each round t, new task of Problem (59) is revealed, which consists of 5-shot meta- training dataset Dfr (the support dataset), and a meta-validation dataset D (the query dataset). Additionally, the dataset [(j(P) is also 5-shot and generated by the PGD method [Kurakin et al., 2018] DJr Then the meta objective at round can be written
meta-training
L(Alg(A, o, D("), D!a1)
(60)
with
X ~ ø1|2
6. arg min C(0,D))
(61)
s.t. L(0, D Pirry) (1 C(,, D(T) 0,
where L(w, Der) is the loss function of the model parameter on dataset DIr Next, we update oi by our algorithms and compute 0, Alg(A, Φb, D(r) as the task-specific model. the experiment, select 0.3 and À = 1.0.
25

---

Baack Footed Albatross
Brand: Cormerant
Cardinal
Gray Casbird
Eastern Towhee
Scissor Tailed Flycatcher
Laysan Albatross
Seaty Abatross
Yellow Billed Curkeo
Spalled Callerd
Horned Lark
Butelink
(a) Water birds
(b) Forest hirds
(c) Grassland birds
Figure 7: Example images of birds from different habitats.
General setup. We conduct the experiments on CUB-200-2011 (referred to as CUB) dataset [Wah al., 20 The input image processing and network architecture fully provided in Section 6.2. To simulate real-world dynamic environments, we select three groups of bird categories from the CUB dataset based on their habitats: water birds, forest birds, and grassland birds. We show example images in Fig. 7 and provide full list of classes for each group in Table 2. For each group, we randomly allocate 50% of the classes for training data, 25% for validation data, and 25% for test data. The time horizon 7 is then evenly divided into three stages, with tasks sampled from one group of bird categories each stage. Specifically, in each round, we sample a 5-way 5-shot task from the training data classes, involving the selection of 5 classes with images per class. During the meta-testing phase, we sampled 600 5-way 5-shot tasks from the test data classes.
We use the Adam optimizer [Kingma and Ba, 2014] with a learning rate of 0.001 for the optimization and use cross-entropy as the loss function. The adversarial attack on the query set performed using the PGD method with a perturbation size of e = 2/255. This process involves 7 iterative steps, each with step size of 2.5e.
26

---

Table 2: Bird species by habitat type in the CUB datasct.
Habitat Type
CUB Label Names
Water
001.Black footed Albatross, 002.Laysan Albatross, 003.Sooty Albatross,
023. Brandra Cormorant, 024.Red faced Cormorant, 025. 115.Pelagic_ooo Cormorant,
050.Eared Gared_Grebbe
051 _ecneHoooGeeee
billed_Grebe, 0S2.Pied_billed. Grebe,
MewtWWestteeeeee Grebe,
058. Pigeon Gasllemm,,llmot,,
059.C Cel.CaafforniaCC0 Gull, 0e2rin Gull, 066. Western Western_Gull,
460.Glaucous Ltt.ucouuu_inneee Gulll 061.Heermann Gull,
@64.Ring_billed Gull,
_aacke_
071.Long cailed_Jaegee 072.Pomarine__aa 084.Red Red__egged Kittiwake, 086. Pacific_Looni Hoodeddodd__a. MMeraanse,,,,,, 090.Red _tt___tte___eerrreeeee Merganser, WwW-Wehtteeecannn [06.Horned__uue
Forest
017. 017.Cardinal, 018. Spotted__attbllt
019. 119.Gray_Catbineg
033. Yel-
038. Grreat_Crested, Flycatcher, 357_Rose_breasted Grosbeak, 054.Blue_ 057.Rose breasted
www_billed_og [illed_CCckoo, 035. PerpPuurleeiiii
Ro8.Ruby_throated throateee Hummingbird, 070.Green Violetear 073.Bluc Jay, 075.Green 095. Baltimlie Oriole, 096.Hooded Hroceed__driilc,, 103.Sayornis, 111.Loggerhead_SStgg Sherek, 152.Blue headed Virco. 154.Red _eee__ee___________eeeee_ eyee_Vireo,, 160. 1.0.Black_throatlee throated Blue Warbler, Go6ddnn Golden_winged Warbler, 175.Palm Warbler, 185. /85.Bohemian, Waxwing, [rleeate__Woodpeckeer 193. W03.Carllina_Woe Wren, 195. 195.House_WWnn 200.Com- mon_Yellowthroot
BeaBBaabbbeateedd Warbler,
(62.Canada_Warte
183.Northern Waterthrush,
233NNothem__Waterrruusst
Grassland
(099Breewer_Baackieee 010.Red BeReedddinedd_laaeeee Blackbrrd, 113.Bobolink, 02s.
ern en_Toowhee, 041 wwcsssccosttileeeeee fllyeacterillleeelltttheeeerr 085. Howned 104.Ameri-
can can_Pipit, 110.Geococcyx, 113. B.B.Barrd_SSt Srirrdd__prrow,,,, 114. Blacklack... throated Sarrated_SSSroww...aa
115.Brewer Sparrosw_proww.. 116. 1.6.Chipping _Sarrrsw 121. Grasshhopppprrr Sparroww_
www.SSaiidd_pSrrrreeeee Sparrow, 129. SSoSSonnnnnnnnS 131. Ves- 127. 127.Savannah Saitnnah_Spprrow.. 128.Seaside
per per_Spaane jer_Sparoww, S0r.Sccrret__aaaaaeeee 14..Forsters_Tett Tern, 19.Broonn_Trrahee 15ge Thhrashrr
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section proposes algorithms for dynamic regret minimization. Section provides the algorithm for adaptive regret minimization. Section 6 reports the application and the experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the future work in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: Section presents the assumptions, Appendix A provides the proofs of the theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We describe our algorithms in Sections and 5.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code and data are included in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. httppsscccpppccccceeeeeeeeecsece htt.g/ddedeeedeeeeiiieeeeeee /Cc////oddmmssseeeeeeea wwsssonoolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: See Section and Appendix C.I for experimental details. Full details are available in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
See the results in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the enror bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See Appendix C.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /nwuriprrsp.. oc Spppblic//thicsuuiiiit
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics and conform to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This work does not present any foresceable societal consequence.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite Xu and Zhu [2023] properly.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "ygBuWMB7nr", "reviewer": "Reviewer_fFaA", "summary": "This paper considers the problem of non-convex online learning in dynamic environments. The authors go on to provide some algorıthmic variants and their respective regret bounds depending on the functional variation. They show that the non-convex dynamic regrets matches the convex ones in the literature.", "questions": "Major Question: \n\nMy biggest issue is with the missing feasibility discussion. The existence of an $(\\alpha,\\beta)$-approximate oracle is assumed, which is not a problem by itself. However, in the derivations, $(\\alpha,\\beta)$ can be set freely depending on $\\gamma$, which is an input. This seems like a big issue to me. For static regret, the effect of $\\gamma$ is non-existing and regret results may naturally depend on given $\\alpha, \\beta$, which is not the case for your analyses. Given that all of the results depend on this, I would like for authors to properly address it. Am I missing something here?\n\n\\\nMinor Questions:\n\n- Line 152: what is $x^*$?\n\n- Line 179: how do you set $\\gamma$?", "limitations": "Most limitations are adequately addressed except for the existence of a parameter-dependent offline optimization oracle.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1) Regret analysis for non-convex online learning is highly significant.\n\nS2) Deriving dynamic regret bounds for non-convex optimization with existing tools for convex optimization is nice.\n\nS3) Achieving dynamic regret and adaptive regret simultanously is powerful.", "weaknesses": "W1) While the derivations are nice, algorithmic contribution is limited.\n\nW2) Existance of an approximate optimization oracle with selectable parameters seems dubious.\n\nW3) Since the $(\\alpha,\\beta)$-approximate oracle is an integral part of the algorithm, providing regret bounds independent of $(\\alpha,\\beta)$ seems counter-intuitive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! Detailed responses have been provided for all the questions raised. In particular, we believe that the major question can be fully addressed by restating our theorems. We hope the reviewer could examine them, and re-evaluate our paper. We are looking forward to addressing any further questions in the author-reviewer discussion period.\n\n\n---\n**Q1**: My biggest issue is with the missing feasibility discussion ...\n\n**A1**: We are sorry for the confusion, and clarify this issue below.\n1. Recall that $\\alpha$ and $\\beta$ are parameters controlling the precision of the optimization oracle, with their values adjustable to achieve specific regret bounds (of course, smaller values typically lead to higher computational costs). In our submitted manuscript, we preset the values of $\\alpha$ and $\\beta$ solely to streamline the presentations. Actually, when analyzing static regret, Suggala and Netrapalli [2020, Page 4] also simplify their bound by setting $\\alpha = O(1/\\sqrt{T})$ and $\\beta = O(1/T)$.\n\n2. Following the suggestion of reviewers, we will revise our theorems to explicitly incorporate $\\alpha$ and $\\beta$, as detailed in our **global response** to all reviewers. For example, **Theorem 1** can be rewritten as: under Assumptions 1 and 2, and setting $\\eta = 1/\\sqrt{d\\gamma}$, Algorithm 2 ensures\n$$\n\\begin{equation}\n    \\mathbb{E}\\left [  R_D^* \\right ] \n    \\le O\\left (\\frac{(1+\\alpha \\sqrt \\gamma+ \\beta \\gamma)T}{\\sqrt{\\gamma }}  + \\gamma V_T \\right) . \n\\end{equation}\n$$ If the value of $V_T$ is known, we set $\\gamma = \\min \\left \\\\{\\left\\lfloor (\\frac{T}{V_T})^\\frac{2}{3}\\right\\rfloor, T \\right \\\\}$, then we have\n$$\n\\begin{align}\n    \\mathbb{E}\\left [ R_D^* \\right ] &\\le O((1+ \\alpha \\sqrt T+\\beta T )T^\\frac{2}{3}(V_T+1)^\\frac{1}{3} ).\\nonumber\n\\end{align}\n$$\nIt can be inferred that when $\\alpha = O(1/\\sqrt{T})$ and $\\beta = O(1/T)$, Algorithm 2 achieves an $O(T^\\frac{2}{3}(V_T+1)^\\frac{1}{3})$ dynamic regret bound.\n\n---\n\n**Q2**: Line 152: what is $x^*$?\n\n**A2**: We apologize for the typo in Line 152, where we mistakenly wrote $x \\in \\mathcal{K}$ instead of $x^* \\in \\mathcal{K}$. Here $x^*$ denotes the decision returned by the $(\\alpha,\\beta)$-approximate optimization oracle.\n\n---\n\n**Q3**: Line 179: how do you set $\\gamma$?\n\n**A3**: We set $\\gamma$ according to the value of $V_T$, as shown in Appendix A.1. Specifically, if $V_T \\ge \\frac{1}{\\sqrt{T}}$, we choose $\\gamma = \\left\\lfloor (\\frac{T}{V_T})^\\frac{2}{3}\\right\\rfloor $; otherwise we choose $\\gamma = T$.\n\n---\n\n**Q4**: Existance of an approximate optimization oracle with selectable parameters seems dubious.\n\n**A4**: First, as explained in **A1**, we can reformulate our theorems to explicitly incorporate $\\alpha$ and $\\beta$. In this way, we obtain the regret bounds shown in the **global response**, treating $\\alpha$ and $\\beta$ as constants. Second, it is important to note that our algorithms are not restricted to using only the approximate optimization oracle. We have the flexibility to select any algorithm with a proven static regret guarantee in online non-convex learning as our subroutine, which may not depend on the approximate optimization oracle.\n\n---\n\n**Q5**: While the derivations are nice, algorithmic contribution is limited.\n\n**A5**: We acknowledge that the techniques employed in this paper may not be entirely novel. However, the integration of these methods and the necessary adaptations we have made represent significant tasks. Importantly, this work is pioneering in showing that it is feasible to achieve optimal dynamic and adaptive regret in the context of online non-convex optimization when an approximate optimization oracle is available.", "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": "", "extra_scores": {}}, {"review_id": "AtEgmxYgeK", "reviewer": "Reviewer_PVQP", "summary": "The paper proposes two variant algorithms of the FTPL (follow-the-perturbed-leader) algorithm for online learning with non-convex losses in time-changing environments. The authors analyze these algorithms under the settings where the variability of the environment ($V_T$) is both known and unknown. FTPL-D is their proposed algorithm to minimize dynamic regret, and FTPL-A is their proposed algorithm to minimize adaptive regret, where their regret bounds match the best known bounds in the convex equivalent cases. The authors also provide an imitation-learning-based example to test the validity of their algorithms.", "questions": "Please address the questions from the above section.", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper introduces (to the best of my knowledge) novel _variants_ of the FTPL algorithm. The paper is well-organized and easy to follow, with clear explanations of the theoretical concepts and practical implementation details. The authors provide detailed proofs of their theoretical results in the appendices, as well as a numerical experiment to empirically document the performance of the algorithm in a concrete example setting to show that their regret bounds are competitive. The chief technical contribution (perhaps, surprisingly, to me) is that the non-convex adaptive-regret/dynamic-regret bounds match their convex equivalents, where the distinction follows mainly from the oracle requirements.", "weaknesses": "1) Going through the proofs: in equation 17 (to bound $b_i$, it seems that the last inequality is very loose. You are bounding two differences by two summations of differences. I wonder if this can be strengthened?\n2) The analysis for these algorithms seem to be quite straightforward - most of the proofs follow very standard analytic methods in the literature. I wonder why this result has not been discovered earlier?\n3) Is it realistic to have an $O(1/\\sqrt{\\gamma}, 1/\\gamma)$-approximate oracle? In particular, I was under the impression that the oracle defined in equation 5 was for a constant value of the parameter $\\gamma$, but it seems that the choice of $\\gamma$ might depend on $L, d, D$, and $T$ (which can be asymptotically large). Doesn't this also make the offline optimization oracle intractable? \n4) If the dynamic environment changes very quickly, how well can the system practically handle this? i.e. if the variational intensity $V_T$ is very high, the experiments do not seem to model this situation at all...\n5) Further, the computational complexity of this algorithm does not seem well-analyzed. What is the memory requirement of each algorithm? How does it scale with T and with the number of experts?\n6) One minor suggestion is that the authors should compare these proposed algorithms with SOTA algorithms (like online gradient descent (OGD) and its oracle). Further, there appears to be a line of related recent works from the control theory + online optimization literature such as [a,b,c,d] which has also made progress in this problem. For instance, [c] appears to have a more tractable oracle, in particular, than OGD. I wonder if you can also compare the analytic methods and results to these works as well, if they are in fact related?\n\nReferences:\n\n[a] Online Policy Optimization in Unknown Nonlinear Systems [Lin et. al. 2024]\n\n[b] Adaptive Regret for Control of Time-Varying Dynamics [Gradu et. al. 2020]\n\n[c] Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations [Lin et. al. 2024]\n\n[d] Online Control of Unknown Time-Varying Dynamical Systems [Minasyan et. al. 2022]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\n**Q1**: Going through the proofs: in equation 17 ... if this can be strengthened?\n\n**A1**: In our opinion, it seems impossible to strengthen this proof. The reason is that our analysis of $b_i$ aligns with that used in the convex case, and the derived $O(T^\\frac{2}{3}(V_T+1)^\\frac{1}{3})$ dynamic regret bound is minimax optimal [Besbes et al., 2015], and thus unimprovable.\n\n---\n\n**Q2**: The analysis for these algorithms seem … why this result has not been discovered earlier?\n\n**A2**: The reason may be that previous work on dynamic regret and adaptive regret has primarily focused on convex functions, often considering non-convex optimization too challenging to yield meaningful results. Recently, we were inspired by Suggala and Netrapalli [2020], who demonstrated that online non-convex optimization could also achieve optimal regret, prompting us to undertake this work.\n\n---\n\n**Q3**: Is it realistic to have an $\\mathcal{O}(1/\\sqrt\\gamma,1/\\gamma)$-approximate oracle? ...\n\n**A3**: We are sorry for the confusion, and clarify this issue below.\n1. Recall that $\\alpha$ and $\\beta$ are parameters controlling the precision of the optimization oracle, with their values adjustable to achieve specific regret bounds (of course, smaller values typically lead to higher computational costs). In our submitted manuscript, we preset the values of $\\alpha$ and $\\beta$ solely to streamline the presentations. Actually, when analyzing static regret, Suggala and Netrapalli [2020, Page 4] also simplify their bound by setting $\\alpha = O(1/\\sqrt{T})$ and $\\beta = O(1/T)$.\n\n2. Following the suggestion of reviewers, we will revise our theorems to explicitly incorporate $\\alpha$ and $\\beta$, as detailed in our **global response** to all reviewers. For example, **Theorem 1** can be rewritten as: under Assumptions 1 and 2, and setting $\\eta = 1/\\sqrt{d\\gamma}$, Algorithm 2 ensures\n$$\n\\begin{equation}\n    \\mathbb{E}\\left [  R_D^* \\right ] \n    \\le O\\left (\\frac{(1+\\alpha \\sqrt \\gamma+ \\beta \\gamma)T}{\\sqrt{\\gamma }}  + \\gamma V_T \\right) . \n\\end{equation}\n$$ If the value of $V_T$ is known, we set $\\gamma = \\min \\left \\\\{\\left\\lfloor (\\frac{T}{V_T})^\\frac{2}{3}\\right\\rfloor, T \\right \\\\}$, then we have\n$$\n\\begin{align}\n    \\mathbb{E}\\left [ R_D^* \\right ] &\\le O((1+ \\alpha \\sqrt T+\\beta T )T^\\frac{2}{3}(V_T+1)^\\frac{1}{3} ).\\nonumber\n\\end{align}\n$$\nIt can be inferred that when $\\alpha = O(1/\\sqrt{T})$ and $\\beta = O(1/T)$, which mirrors the settings used by Suggala and Netrapalli [2020, Page 4], Algorithm 2 achieves an $O(T^\\frac{2}{3}(V_T+1)^\\frac{1}{3})$ dynamic regret bound.\n---\n\n**Q4**: If the dynamic environment changes very quickly, how well ...\n\n**A4**: If the environment changes quickly and $V_T$ is very high, the system's performance will decline. That is because our dynamic regret bound of $O(T^\\frac{2}{3}(V_T+1)^\\frac{1}{3})$ is minimax optimal  [Besbes et al., 2015]. An increase in $V_T$ will lead to a larger lower bound for dynamic regret, which implies that the system's loss will increase.\n\n---\n\n**Q5**: Further, the computational complexity of this algorithm does not seem well-analyzed ...\n\n**A5**: Below we will discuss the computational complexity and the memory requirement of our algorithms.\n\n* ***Computational Complexity***: It is important to note that the computational bottleneck of our algorithms lies in the offline optimization oracle. Therefore, we can simply define the computational complexity of the algorithms in terms of the number of oracle calls. For Algorithm 2, only one oracle call is needed per round. For Algorithm 3, there are $ N = \\left \\lfloor \\log T \\right \\rfloor$ experts in each round, with each expert requiring one oracle call, so the number of oracle calls per round is $O(\\log T)$. Similarly, for Algorithm 4, in the $t$-th round, there are $N_t = 1+\\left \\lfloor \\log t \\right \\rfloor $ experts, thus requiring $O(\\log T)$ oracle calls per round.\n* ***Memory requirement***: First, in order to run the optimization oracle, we need to store all the functions in memory, which takes $O(t)$ space in the $t$-th round. Thus, Algorithm 2 has $O(t)$ space complexity, which is the same as Suggala and Netrapalli [2020]. Second, each active expert consumes a constant memory. According to the discussion above, Algorithms 3 and 4 require $O(t + \\log T)$ space, since they need to maintain $O(\\log T)$ experts. \n---\n\n**Q6**: the authors should compare these proposed algorithms with SOTA algorithms ...\n\n**A6**: Thanks for the suggestion. We compare our algorithms with OGD and the methods in [a, b, c, d] from the following aspects:\n\n* ***Oracle***: Our algorithm relies on an offline optimization oracle, whereas OGD uses a gradient oracle, which returns the gradient information of the loss function at the decision point. Additionally, we note that [c] introduced a more tractable oracle, which approximates the true gradient by computing the gradient on the actual trajectory, thereby reducing the computational complexity. Generally, a gradient oracle is easier to obtain and has lower computational complexity compared to an offline optimization oracle. \n\n* ***Metrics and results***: In dynamic environments, OGD achieves: (i) minimax optimal dynamic regret of $\\sqrt{T(P_T+1)}$ for general convex functions [Zhang et al., 2018a], using path-length $P_T$ (defined in Appendix B) to measure environmental variation; (ii) local regret of $\\sqrt{T(V_T+1)}$ for non-convex functions [c], also using $V_T$ to measure environmental variation.  In [a, c], the performance of the algorithms is measured by _local regret_ [Hazan et al., 2017], which focuses on tracking changing stationary points. In contrast, we use _regret_ (including dynamic regret and strongly adaptive regret), which is a stronger metric. [b] focuses on adaptive regret, and [d] on strongly adaptive regret, but both assume general convex cost functions, whereas our paper supports non-convex functions.", "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": "", "extra_scores": {}}, {"review_id": "4TOU9Gw73l", "reviewer": "Reviewer_njVm", "summary": "This paper presents novel algorithms to tackle the challenges of online learning with non-convex loss functions in dynamic settings. The authors extend the Follow the Perturbed Leader (FTPL) algorithm to dynamic environments by proposing two new algorithms: FTPL-D and FTPL-D+. They demonstrate the effectiveness of their methods through theoretical regret analysis.", "questions": "Could the authors include some more challenging experimental tasks? The current tasks are relatively simple.", "limitations": "The authors did not discuss the limitations in sufficient detail. The last paragraph of the paper only contains some discussion on future directions.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper introduces innovative extensions to the FTPL algorithm, specifically designed for non-convex and dynamic environments. The paper is well-written and structured, making it easy to follow the theoretical developments and experimental setups. The algorithms are clearly described, and the results are presented in a manner that highlights their significance.", "weaknesses": "I think the problem addressed in this paper is not sufficiently central. The main contribution is extending the loss function to a non-convex case under this specific setup, and the proof methods are quite similar to previous works. Additionally, the experimental setup is relatively simple and lacks more practical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\nWe will add more experiments in the final version. Here, we want to highlight that although each imitation task in our experimental setup is relatively simple, the framework of online constrained meta-learning introduces considerable complexity, especially in dynamic environments. We elaborate on this in two aspects.\n\n1. It is important to note that the demonstration trajectories to be imitated are collected in free space, without any knowledge of obstacle avoidance, whereas the task is performed in a new cluttered environment. Before the task is revealed, the obstacles in the new environment are unknown to the learner. Therefore, the learner has to quickly adapt to the presence of obstacles.\n\n2. Additionally, in the two types of dynamic environments we simulated, the changes in task trajectories are also unknown. This implies that the learner needs to adapt to these changes in trajectories to better imitate the current task's demonstration.", "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": "", "extra_scores": {}}, {"review_id": "SXjBcprBYN", "reviewer": "Reviewer_wXns", "summary": "This paper provides $O(V_T^{1/3}T^{2/3})$ dynamic regret\nand $O(\\sqrt{\\tau\\log(T)})$ strongly-adaptive regret guarantees for\nonline learning with Lipschitz losses in bounded domains.", "questions": "- what are some examples of interesting losses which are non-convex, but bounded and lipschitz?\n- Can a similar strategy be developed for FTRL? Or is randomization an essential ingredient for the base algorithm?\n- Most online learning guarantees are anytime and wp1, while the results here are only in expectation.\n  Would it be difficult to get a stronger high-probability result, at least?", "limitations": "The weakness in terms of adapting to temporal variability instead of path-length is pointed out in the conclusion", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper fills a gap in the literature by providing the\ndynamic and strongly-adaptive extensions of the FTPL\nalgorithm. The paper reads well and is easy to follow.", "weaknesses": "The results are straight-forward applications of existing results. Prior analyses provide the\nregret bound of FTPL, and by assuming Lipschitz+bounded domain one immediately has access\nto an experts algorithm which will combine instances of the base algorithm (multiplicative weights update).\nSimilarly, the strongly adaptive result seems to follow easily from the standard\ngeometric covering intervals + AdaNormalHedge.\n\nThe results are adaptive to the temporal variability, $\\sum_{t=2}^{T}\\sup_x|f_t(x)-f_{t-1}(x)|$, which is more\nof a variance measurement than it is a measure of comparator variability. For instance, even\nthe temporal variability can be high even if the comparator is fixed.\nYet studying dynamic\nregret in the first place implies we are concerned with the variability of the comparator sequence; the ideal measure\nis something like path-length, where the \"difficulty\" of the comparator sequence is directly\nreflected in the bound. Here, the bound reflects only seems to\nreflect the difficulty of the loss sequence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\n\n**Q1**: What are some examples of interesting losses which are non-convex, but bounded and lipschitz?\n\n**A1**: An illustrative example is the loss function of Generative Adversarial Networks (GANs), which has been extensively discussed by Agarwal et al. [2019, Section 4.1].\n\n---\n\n**Q2**: Can a similar strategy be developed for FTRL? Or is randomization an essential ingredient for the base algorithm?\n\n**A2**: We believe that FTRL cannot achieve similar results, as Proposition 3 of Suggala and Netrapalli [2020] demonstrates that deterministic algorithms cannot attain sublinear regret in the context of online non-convex learning. Therefore, it is essential to employ randomization in base algorithms.\n\n---\n\n**Q3**: Most online learning guarantees are anytime and wp1, while the results here are only in expectation. Would it be difficult to get a stronger high-probability result, at least?\n\n**A3**: Thank you for the valuable feedback. It is indeed feasible to establish high-probability regret bounds. We can adapt the approach used in the proof of Lemma 4.1 by Cesa-Bianchi and Lugosi [2006], particularly their technique for deriving high-probability bounds. Given our assumptions, the discrepancy between the actual loss and the expected loss in each round is bounded. Consequently, we can apply the Hoeffding-Azuma inequality for martingale differences, and extend the expected regret bound to a high-probability one.", "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": "", "extra_scores": {}}]

Author rebuttal:
According to the suggestions of **Reviewers fFaA** and **PVQP**, we will reformulate our theorems to explicitly incorporate $\alpha$ and $\beta$. In this way, we obtain the regret bounds below, treating $\alpha$ and $\beta$ as constants.

---

***Theorem 1***. Under Assumptions 1 and 2, and setting $\eta = 1/\sqrt{d\gamma}$, Algorithm  2 ensures
$$
\begin{equation}
    \mathbb{E}\left [  R_D^* \right ] 
    \le O \left (\frac{(1+\alpha \sqrt \gamma+ \beta \gamma)T}{\sqrt{\gamma }}  + \gamma V_T \right) . \nonumber
\end{equation}
$$
If the value of $V_T$ is known, we set $\gamma = \min \left \\{\left\lfloor (\frac{T}{V_T})^\frac{2}{3}\right\rfloor, T \right \\}$, then we have
$$
\begin{align}
    \mathbb{E}\left [ R_D^* \right ] &\le O((1+ \alpha \sqrt T+\beta T )T^\frac{2}{3}(V_T+1)^\frac{1}{3} ).\nonumber
\end{align}
$$
***Theorem 2.*** Let $\mathcal{H}=\left\\{\gamma_i = 2^i \mid  i=1,\cdots N\right\\} $ where $ N = \left\lfloor \log_{2}{T}\right\rfloor $, and $\rho=\frac{1}{dDL}\sqrt{\frac{8\ln{N}}{T}}$. Under Assumptions 1 and 2, Algorithm 3 ensures
$$
\begin{align}
\mathbb{E}\left [ R_D^*\right ] 
\le O((1+ \alpha \sqrt T+\beta T )T^\frac{2}{3}(V_T+1)^\frac{1}{3} ).\nonumber
\end{align}
$$

***Theorem 3.*** Under Assumptions 1 and 2, Algorithm 4 ensures
$$
\begin{align}
    \mathbb{E}\left [ R_A(T,\tau )\right ]\le  O(\sqrt{\tau \log{T}} +\alpha \tau+ \beta \tau^{\frac{3}{2}} ).\nonumber
\end{align}
$$


***Theorem 4.*** Under Assumptions 1 and 2, Algorithm 4 ensures
$$
\begin{align}
    \mathbb{E}\left [ R_D^*\right ]
    \le \tilde{O}((1+ \alpha \sqrt T+\beta T )T^\frac{2}{3}(V_T+1)^\frac{1}{3}).\nonumber
\end{align}
$$

---

To simplify these theorems, we follow the seminal work of Suggala and Netrapalli [2020, Page 4] and also consider the case where $\alpha = O(1/\sqrt{T})$ and $\beta = O(1/T)$, thereby obtaining the same regret bounds as presented in our submitted manuscript.

Meta-review: This paper provides an algorithm that, given an offline optimization oracle, can achieve optimal dynamic regret guarantees for non-convex losses.

In review, it appears that this paper's key contribution is to combine the recent results for obtaining static regret in this setting with a number of existing techniques for converting static regret into dynamic regret. This paper has borderline reviews, mostly because there is some concern about the level of contribution of this process. However, overall the reviews are more on the positive side. The authors are encouraged to address the reviewer comments and clarify their technical contributions in the revision.
Decision: Accept (poster)