Gradient-Variation Online Learning under Generalized Smoothness
Authors: Yan-Feng Xie
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
generalized smoothness
gradient-variation regret bound
Lipschitz-adaptive algorithm
Primary area: online_learning
TL;DR: This paper systematically studies the gradient-variation online learning under generalized smoothness.

Abstract: Gradient-variation online learning aims to achieve regret guarantees that scale with variations in the gradients of online functions, which is crucial for attaining fast convergence in games and robustness in stochastic optimization, hence receiving increased attention. Existing results often require the smoothness condition by imposing a fixed bound on gradient Lipschitzness, which may be unrealistic in practice. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. In this paper, we systematically study gradient-variation online learning under generalized smoothness. We extend the classic optimistic mirror descent algorithm to derive gradient-variation regret by analyzing stability over the optimization trajectory and exploiting smoothness locally. Then, we explore universal online learning, designing a single algorithm with the optimal gradient-variation regrets for convex and strongly convex functions simultaneously, without requiring prior knowledge of curvature. This algorithm adopts a two-layer structure with a meta-algorithm running over a group of base-learners. To ensure favorable guarantees, we design a new Lipschitz-adaptive meta-algorithm, capable of handling potentially unbounded gradients while ensuring a second-order bound to effectively ensemble the base-learners. Finally, we provide the applications for fast-rate convergence in games and stochastic extended adversarial optimization.

Gradient- Variittnn Online Learning under Generalized Smoothness
Yan-Feng Xie, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology. Nanjing University, China School Artificial Intelligence, Nanjing University, China {xieyf, zhaop, zhouzh)@11 almama..... nju. edu
Abstract
Gradient-variation online learning aims to achieve regret guarantees that scale with variations in the gradients of online functions, which is crucial for attain- ing fast convergence in games and robustness in stochastic optimization, hence receiving increased attention. Existing results often require the smoothness con- dition by imposing fixed bound on gradient Lipschitzness, which may be unre- alistic in practice. Recent efforts in neural network optimization suggest a gen- eralized smoothness condition, allowing smoothness correlate with gradient norms. In this paper, we systematically study gradient-variation online learning under generalized smoothness. We extend the classic optimistic mirror descent algorithm to derive mization trajectory and exploiting smoothness locally. Then, we explore universal online learning, designing a single algorithm with the optimal cordiient-vaiatioon regrets for convex and strongly convex functions simultaneously, without requir- ing prior knowledge of curvature. This algorithm adopts a two-layer structure with meta-algorithm running over a group of base-learners. To ensure favor- able guarantees, we design new Lipschitz-adaptive meta-algorithm, capable of handling potentially unbounded gradients while ensuring second-order bound effectively ensemble the base-learners. Finally, provide the applications for fast-rate convergence games and stochastic extended adversarial optimization.
variation regret by analyzing stability over the opti-
Introduction
We consider online convex optimization (OCO) [Hazan, 2016; Orabona, 2019], flexible framework that models the decision pocision-making problem in an online fashion. At each round E [T], an online learner is required submit decision x, from convex compact set X' C Rd and the environments reveal convex function fe X' + R. Then the learner suffers a loss fx()) and updates her decision. The standard performance measure is the regrer IZinkevich, 2003] that benchmarks the cumulative loss of the learner against the best decision in hindsight, formally defined as
T
REGT Σ f((x))
min XEX
f((x).
Regret bounds of O(VT) and O L log T) are established for convex and A-strongly convex func- tions respectively [Zinkevich, 2003; Hazan et al., 2007]. While these results are known to be min- imax optimal [Abernethy et al., 2008], in this paper we are more interested obtaining gradient- variation regret guarantees, which replace the dependence of T' in the regret bounds by variations in
Correspondence: Peng Zhao <zzhop @ lawdda.juum.uuu......
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the gradients of online functions [Chiang et al., 2012] defined as
VT Σ sup xEX
(x) - (x)-1
(2)
This quantity can be as small as constant in stable environments where online functions remain fixed, and is most (T) in the worst case under standard OCO assumptions, safeguarding min- imax results. Besides this favorable adaptivity, recent studies have shown close relationships of gradient-variation online learning
various fields, including fast convergence in games [Rakhlin and Sridharan, 2013b; Syrgkanis et al., 2015; Zhang et al., 2022b] and robust stochastic optimiza- tion [Sachs et al., 2022; Chen al., 2024], hence receiving increased attention [Zhao al., 2020; Yan et al., 2023: Tsai et al., 2023; Atace Tarzanagh et al., 2024; Zhao et al., 2024].
In online learning. it is proved that the smoothness assumption is necessary for first-order algo- rithms to achieve gradient-variation regret bounds as discussed in Remark 1 of Yang et al. [2014], which is also restated in Proposition 2 in Appendix B. Previous works typically rely on the global L-smoothness condition, imposing a fixed upper bound on the gradient Lipschitzness, i.e., requiring f())l S L for all E [T] and X. However, this global assumption restricts the applica- bility of theories to loss functions that are quadratically bounded from above. Furthermore, recent studies in neural network optimization have observed phenomena where the global smoothness con- dition fails to model optimization dynamics effectively, especially for important types of neural net- works like LSTM [Zhang al., 2020b] and Transformer [Crawshaw et al., 2022]. Therefore, modern optimization has devoted efforts to generalizing the smoothness condition. For example, Zhang et al. [2020b] introduce (Lo, L1) -mmotthesss, which assumes || V/V² (x))l2 I Lo + L fx) for an offline objective function f (.). A notable generalization is the recent proposal of the f-smoothness condition [Li et al., 2023], which assumes fx) I|2 I f()) l12) with a link function E(-). significantly broadening previous assumptions through the flexibility of f(.). Given this, it is natu- ral to ask how to design online algorithms to exploit generalized smoothness and obtain favorable gradient-variee
regrel guarantees.
In this paper, we provide a systematic study of gradient-variation online learning under generalized smoothness. We extend the classic optimistic online mirror descent (optimistic OMD) algorithm [Chiang et al.. 2012; Rakhlin and Sridharan, 2013a] to derive gradient-varias variation regret bounds, achieving ((VVT) regret and (log VT) regret for convex and strongly convex functions under generalized smoothness, respectively. We emphasize the importance of stability analysis across the optimization trajectory, which allows generalized smoothness to be effectively exploited locally. Specifically, optimistic OMD maintains two sequences with submitted decisions {x:]Tm and inter- mediate decisions {&, YT- We need to control algorithmic stability by appropriate step size tuning and optimism design, ensuring that x, is sufficiently close to X, to exploit local smoothness at &,-
Based on this development, we investigate universal online learning [van Erven and Koolen, 2016; Wang et al., 2019: Mhammedi al., 2019; Zhang et al., 2022a; Yan et al., 2023; Yang et al., 2024], where the learner aims to design a single algorithm that simultancously attains the optimal regret for both convex and strongly functions without the prior knowledge of curvature information. For this scenario, a common wisdom is to adopt an online ensemble consisting of a meta-base two-layer structure to handle the environmental uncertainty [Zhao et al., 2024], i.e., the unknown curvature of is running over a set of base-learners with different configura-
loss functions, where a meta-algorithe tions. The base-learners are basically the instantiations of the developed variants of optimistic OMD, as mentioned earlier. However, designing the meta-algorithn is non-trivial with new challenges. The first challenge from the potentially unbounded smoothness, which might lead to unbounded Lipschitz constants as well. This challenge requires the meta-algorithm to be Lipxchüzz-uluptive, adapting to Lipschitzness on the fly. Furthermore, we also expect it to provide a recond-order regret, technically required when analyzing the ensemble errors, and to enable predictions with optimism, thereby producing the gradient variation. The second challenge is the complexity introduced by the combination procedure inherent in the ensemble method, which further complicates the smoothness estimation, making it difficult to properly tune the alta-algorithm and exploit smoothness.
To this end, we address both challenges with the sion and a newly-designed Lipschitz-adaptive meta-algorithm. The conversion technique, drawing inspiration from Bai et al. [2022], decouples the design between the meta and base levels and de- rives the gradient variation directly from function values, allowing us to avoid the cancellation-based analysis [Yan et al., 2023] for utilizing smoothness at the meta level. Nevertheless, this conversion
tootooo--ttoooooe towttt--gnnt-vuueee graiitnt-variation conver-

---

requires the meta- aelto-aggoi to handle heterogeneous inputs due to certain technical considerations, and we are not aware of available algorithms satisfying all the requirements, motivating us de- sign a new algorithm. Based on optimistic Adapt-MI.-Prod [Wei et al., 2016] and the clipping technique [Cutkosky, 2019], we present a new Lipschitz-adaptive meta-algorithm with a simpler algorithmic design, which can be of independent interest. With this algorithm, we can apply the variiaiion-o-grraiieee
conversion to achieve the optimal results for both convex and strongly convex functions, up to doubly logarithmic factors of T, without knowing curvature.
Our findings for gradient-variation online learning are useful for several important applications, in- cluding fast-convereenc online games [Rakhlin and Sridharan, 2013a; Syrgkanis et al., 2015] and stochastic extended adversarial online learning [Sachs al.. 2022], where we establish new results under the generalized smoothness condition.
The rest of paper is organized follows. ing the generalized smoothness throughout the trajectory. In Section 3 we study universal online learning and present our key meta-algorithm. Section 4 discusses our applications. Related work is provided in Appendix A. All proof' can be found in the remaining appendices (Appendix B - B).
Section 2 provides preliminaries and key ideas for exploit-
2 Gradient-Variation Online Learning under Generalized Smoothness
In this section, first introduce the problem setup, including the formal definition of generalized smoothness and other assumptions used in the paper. We then extend the optimistic online mirror descent framework to achieve gradient-variatinn regret bounds under generalized smoothness.
2.1 Problem Setup: Generalized Smoothness and Assumptions
Recent studies [Zhang et al., 2020b; Chen al., 2023b] extend the global smoothness condition by allowing the smoothness to positively correlate with the gradient norm, where a particular func- tion is required to model this relationship. Zhang et al. [2020b] introduce the (Lo, Is)-smoothness condition, where the smoothness is upper bounded by a linear function of the gradient norm, i.e., [[v*[()]|a S Lo + (x)l22 Li et al. [2023] further generalize this by imposing weaker assumption on the link function and propose the generalized smoothness defined as follows.
Definition 1 (é-smoothness). A for some non-decreasing continuous link function [0, +00) + (0, +oo) it satisfies that fx)]2 s f(I[f(()) for any E X.
function X R is called é-smooth
The mild requirement the link function {(.) allows for considerable generality. By selecting linear link function, ε-smoothness immediately recovers (Lu, -m)soootssssss [Zhang et al., 2020b]. Furthermore, has been shown that ê-smoothness can imply wide class of functions including rational, logarithmic, and self-concordant functions [Li et al., 2023]. Based on this generalized smoothness notion, we now provide the formal assumption on the smoothness of online functions.
Assumption (generalized smoothness). The online function ft : X + R is 4 smoohh in an open set containing X' C Rdd for t [T], and the learner query fx(x) provided any point X.
We also require a standard bounded domain assumption in the OCO literature [Hazan, 2016].
Assumption (bounded domain). The feasible domain X' C IRd, which contains the origin 0, is non-empty and closed with the diameter bounded by D, i.e. || yll2 < D for any x, X.
We do not assume the prior knowledge of the Lipschitz constant of online functions. In fact, the unboundedness of smoothness may result in unbounded Lipschitz constants. If a Lipschitz upper bound were known, the generalized smoothness condition would be trivialized, as it would allow us to directly compute the upper hound of the smoothness constant. Furthermore, following the discussion in Jacobsen and Cutkosky [2023, Page 2, second paragraph on the right], assume that there exist finite but unknown upper bounds G and L for Lipschitzness and smoothness to ensure the theoretical results are valid. Note that these quantities will only appear in the final regret bounds, and our algorithms does not use them as the inputs. Throughout the paper, we use the (-))nootaion to hide the constants and use the O -notttnn to omit the poly-logarithmic factors in T.
3

---

2.2 Algorithmic Framework
We choose optimistic online mirror descent (optimistic OMD) [Rakhlin and Sridharan, 2013a] as the algorithmic framework, which provides unified view to design and analyze many online algorithms. Compared to classic OMD [Nemirovskij and Yudin, 1985: Beck and Teboulle, 2003], optimistic OMD predicts with side information, an optimistic vector M, E Rd. This optimistic vector, also known as optimism, serves as a prediction of the incoming function ft+1(), leading to tighter regret bounds when accurate. Optimistic OMD updates the decisions in two steps:
X = arg min {M,, x) + D (x, 8,)3 XEN
Xe+1 = arg min ((Vf(())) + + &1)) XEX
where De, (x, y) = 1. (x( b,(y) (Ve) y) is the Bregman divergence associated with the regularizer 2/ X' - R. Optimistic OMD maintains sequences: the sequence of submitted decisions {x and the one intermediate decisions {& |T_ Although a simplified optimistic OMD with one-step update per round exists [Joulani al., 2020], we will demonstrate later that tun- ing the step size based on intermediate decisions is crucial for adapting to generalized smoothness.
2.3
Variiatin Regret for Convex and Strongly Convex Functions
When minimizing the convex strongly convex functions, we set the regularizer (x) | and optimistic OMD updates with the following steps:
2xp
x = xx & Mc). & = Ix [ n (x,)),
where IIx Iy = arg min / - ylll denotes the Euclidean projection operator. Next, we briefly review approaches for obtaining the gradient- variation bound under global smoothness. This bound typically follows from the regret analysis for optimistic OMD:
T
REGT $ 1
S1 Σ (l)))( - M Σ
(1x+ 77
x2 + ||c x12)
(5)
1/T'
On the right-hand side, the second term is known as the stability term, while the third one is the negative terms that can further bounded by O-- --= ||x,
x, 12)). Previous studies [Chi-
ang et al., 2012: Zhao et al., 2024] for gradient-variation regret under global smoothness often set optimism as M, V ft-1(x(-1) such that, the positive stability term can be upper bounded by fxx)) - V ft-11 (xx))1 + 37. ft-
( where the first part can be directly
converted to the desired gradient variation and the second part will be at most L [[x, x,-1 | under global smoothness. Given the smoothness constant L. tuning the step size as S 1/(4L)
ensures (, x, x,-1
| x,- 1l2) S thus obtaining the ceddient-variation bound.
However, under generalized smoothness, we do not have global parameter L for setting the step sizes, and the smoothness constants are related to the decisions. To follow the previous approach, optimistic OMD would require the smoothness constant before generating x, to tune the step size, Nev-
ensuring that the negative terms are large enough to cancel 17 (x,) - ( ertheless, the smoothness constant between x; and x,-1 can only be evaluated after updating to xx, resulting in contradiction. Unlike offline optimization, where the function is fixed and smoothness constants be shown to decrease along the trajectory [Li al., 2023], in online optimization, the online functions change at each round, preventing the reuse of previous smoothness estimations.
To address this challenge, our key idea is to perform a trajectory-wist analysis and configure the algorithm using estimated smoothness so far. The key technical lemma is the local smoothness property of f--smooth functions [Li et al., 2023], which allows the smoothness constant between two points to be estimated in advance, provided that the two points are close enough.
Lemma 1 (local smoothness [Li al., 2023, Lemma 3.3]). Suppose f X + IR is E-smooth. For Vf(y)lla & (2 ||x mak-yll yll2- Vx, y E X such that ||x - yll S [( VV
[V
Recall that in the update procedures (3) of optimistic OMD, the submitted decision x, is updated based on the intermediate decision X, Therefore, it is convenient to control their distance and then exploit the local smoothness at point &t. Specifically, we set optimism M, = f(,((())) and the step size π) 1/(4Lr-1), where L,1 l-1 (2 fx)) denotes the locally estimated

---

smoothness and is used to tune the step size. This configuration leads to 17: [V - for the second term in Eq. (5), which can be further upper bounded as
fx,,) V (x2 - 2 fx,,) (x, + + 2
(6)
The first part is basically the favorable gradient variation, so it suffices to handle the second part. Performing the stability analysis for OMD and noticing the step size setting, it can be verified that
This satisfies the criteria for applying Lemma to the 4-moohh function f--1 allowing us to upper bound the second term (6) by O ||x - 22 We have clipped nu by 1/(4L,-1), thereby ensuring the negative term is sufficient to cancel out positive term. Below, we summarize the result for convex functions.
||x, & ||22 S 7) (&))(l - fi- ( (228))/ll////-1
Theorem 1. Under Assumptions 1 2 and assuming online functions are convex, we set the optimism as M,- (&,) and fo(-) = 0, with step sizes Th D and, for 2 2,
D2
min
W I+
(x,=1(
min sE(t] 4l, 1 (x,)
(7)
optimistic OMD in (4) ensures the following regret bound,
REGY O (DVV Emaax D²).
measures the gradient variations and Lmax m L. is the maximum smoothness constant over the optimization trajectory.
where Vi = Ei= V - 1x))
This result implies tighter bound in scenarios where the environments change slowly, i.e., Vr (1). Meanwhile, safeguards the worst-case optimal result since V/ S O(T) holds in all cases. When assuming fe(-) L for E [T], the fe-smoothness condition degenerates to the classic global L-smoothness condition, and our result implies O(VVT LDD)) bound, which matches the best-known gradient-varian variation regret bounds with the first-order oracle [Chiang et al., 2012; Yan et al., 2023; Zhao et al., 2024] even in terms of the dependence D and L. Compared to offline optimization, result depends on Lmaxx the maximum smoothness constant along the trajectory. This dependence arises from the adversarial nature of online learning, where the loss functions chosen in consecutive rounds may differ significantly, making it hopeless leverage the previous estimates of smoothness to improve the dependence.
We further provide an improved gradient- variation regret bound for strongly convex functions, with step size tuning based on recent result under global smoothness [Chen et al., 2024, $ 3.4].
Theorem 2. Under Assumptions 1 --2 2 and assuming online functions are X-strongly convex, we set the optimism as M, V ft- (8)), fo(-) O, and step sizes as πi 2/ and, for 2/(At + 16 max l--1 (2 fa (2))) optimistic OMD in (4) ensures the regret bound REGT S ( log Vr + T.max D2). where T = max(e(T] L.-
The above theorem requires the knowledge of curvature information A. In Section 3, we design universal method to remove this requirement and achieve the optimal guarantees for convex and strongly convex functions simultaneously without knowing X. In Appendix B.2, we discuss the challenge to obtain veddieentvvriation bound for exp-concave functions under Assumption 1.
3 Universal Online Learning under Generalized Smoothness
Classic online learning algorithms require the curvature information of online functions as algo- rithmic parameters to achieve favorable regret guarantees. However, obtaining these curvature pa- rameters can be difficult in practice. This challenge motivates the recent study of universal online learning [van Erven and Koolen, 2016; Cutkosky and Boahen, 2017: Wang et al., 2019; Mhammedi et al., 2019; Zhang et al., 2022a; Yan et al., 2023; Yang et al., 2024], which aims to design single al- gorithm that can achieve optimal regrets without knowing the curvature information. In this section, study universal online learning with gradient- variiatin regret under generalized smoothness.
5

---

3.1 Reviewing Related Work and Techniques
We review related work on pradient-variatio universal online learning under global smoothness [Zhang et al., 2022a; Yan et al., 2023]. To handle the unknown curvature, universal online learning algorithms utilize a two-layer structure, consisting of a meta-algorithm that ensembles group of base-learners. Each base-learner optimizes functions with a specific convex curvature, while the meta-algorithm designed to ensure that ensemble errors do not ruin base-learners' guarantees. Denoted by N the number of base-learners, the decision X, = EiE[N] Pr, submitted by two- layer structure algorithm comprises two key components: Pt AN. the weights provided by the meta-algorithm, and Xt,i, the decision of the i-th base-learner. The analysis of a universal algorithm begins by decomposing the regret into two parts against any base-learner. In particular, choose the base-learner with the best performance (the index i, is unknown) as the benchmark:
REGT Σ fx()))
Σ (x(.)))
Σ f((x)..))
min XEX
Σ f((),,
(8)
META-REG
BASE-REG
where the first part is the meta-regret, evaluating the meta-algorithm's 's performance against the best base-learner, and the second part, known as the base-regret, measures the best learner's performance.
Zhang et al. [2022a] advocate for simple approach by employing the meta-algorithms with second- order regret guarantees, which facilitates the analysis at the meta level. In specific, they use Adapt-ML-Prod [Gaillard et al., 2014] as the meta-algorithm, showing that the meta-regret for strongly convex and exp-concave functions are constants by exploiting the negative terms from convexity. Consider X-strongly convex functions an example and assume the i.-th base-learner ensures the optimal O(3 log Vr-) base-regret. At the meta level, Zhang et al. [2022a] pass the lin- earized regret rı,i = (V.,, x,,i) to the meta-algorithm for each base-learner. By strong convexity and the guarantees of Adapt-ML- the meta-regret can be bounded by constant:
A
A
META-RES REETA-REG- I
TL.
X X 113 <
x X 11 0(1),
2
2
where the last inequality follows from v (
Xt.i. 2max E Xt,i, and is then canceled by the negative terms via the AM-GM inequality. By leveraging the negative terms from strong convexity, the meta-regret can be dominated by the base-regret, which is then controlled by selecting appropriate base-alge mase-algorithms.
allowing the overall regret to be
However, this method is unsuitable for producing the gradient-variatin bound for convex functions. To address it, Yan et al. [2023] propose to use meta-algorithm which ensures an optimistic and second-order regret bound while provides additional negative terms E, lp: Pt- Besides showing that the meta-regret is a constant for strongly convex and exp-concave functions following the previous approach, with newly designed optimism, Yan et al. [2023] prove that the meta-regret for convex functions can be roughly bounded by:
o (VVT VT (
Σ XL. X; 2 Σ - P PI-
L Σ Σ
Pr. pr,il
Xx- 1,11
The first term is the gradient variation, matching the optimal order of convex functions. Yan et al. [2023] demonstrate that the remaining stability terms can be canceled through the collaboration between the base and meta levels [Zhao et al., 2024] with the prior knowledge of the global smooth- ness constant L. thus obtaining the near-optimal gradient-variation bounds for convex functions as well. Nevertheless, the employed meta-algorithe already has a two-layer structure, resulting in a three-layer structure for the overall algorithm, which is relatively complicated.
3.2 Key Challenges and Main Ideas
We aim to design a universal algorithm with the optimal gradient-variation bounds under general- ized smoothness, which exhibits two challenges. First, the Lipschitz condition of online functions unknown to the aega-algorithm, which requires the meta-algorithm to be Lipschitz-adaptive, pro- vide second-order regret, and enable predictions with optimism. Second, the combination of the

---

ensemble method further complicates the estimation of smoothness constants, making it challenging to tune algorithms properly and to cancel stability terms as Yan et al. [2023] did.
We tackle the second challenge by utilizing a fiuctiin-variaaion---o watp--rrraaattt----rrdeeeee-e-ee gradiiett-vvariitonn conversion to derive the gradient- gradient-variation bounds at the meta level, drawing inspiration from the development of dynamic regret minimization [Bai et al., 2022]. This conversion technique decouples the meta and base levels, allowing us avoid cancellation-based analysis. To illustrate, suppose a meta-algorithm ensuring O E, (C1,5, mr,,,) 12) provided optimism m, (me,,, ..... "1,,,N), ). By setting l,,i, fe(xx,;,) (xre) and ma,i = ft-1 (Xr.i.
where Xref is a fixed reference point, the meta regret bound becomes O E (x)(),,) (x..)) (fr(X)et) - ft-1(Xxel) (Xret) )){²) By the mean value theorem, (x,.( f-- (xx,,)) -ffr(x,or)) fi-1 - equals the first term below,
which can be further upper bounded by the gradient variation:
x,,t)]² -xx,)) D supxex
[f( | - -
This technique brings hope for minimizing the convex functions. To develop a universal method, our first attempt is to utilize
[Chen et al., 2021] as the meta-algorithm, which satisfies all the three requirements imposed by the first challenge. Nevertheless, the heterogeneous inputs at the meta level present another challenge to this approach. The heterogeneity arises as we pass re. = [x,x,) - (x(x,,) to the meta-algorithm for base-learner responsible for convex functions, leveraging the conversion technique, while r2, (V)(( x xx,,) for base-learners minimizing strongly convex functions. It remains unclear how to adapt MsMwC-Master [Chen et al., 2021] to our heterogeneous inputs, as MsMwC-Master requires an &, as inputs, and the guarantee is for the regret in the form of r = (pr. l L.- However, such an l cannot be retrieved from our above design. Fortunately, we observe that the Prod algorithms [Cesa- Bianchi et al., 2007; Gaillard et al., 2014; Wei et al., 2016] are friendly to heterogeneous inputs. Technically, the Prod algorithms provide the same guarantees long as E
I O, thanks to the potential basedd analysis. Therefore, aside from the requirements of the first challenge, we expect that the meta-algorithm can be analyzed similarly to the Prod algorithms, motivating us to design a new meta-algorithm. As a byproduct, we present universal algorithm with a two-layer structure under global smoothness with the developed techniques. It is more efficient than that by Yan et al. [2023] and attains the optimal gradient-variation guarantees for convex, strongly convex, and exp-concave functions, at cost of additional function value queries. We defer algorithms and regret bounds to Appendix C.5.
3.3 A New Lipschitz-Adaptive Aeta-Algorithm
In Algorithm 1, we present our algorrthm, which builds on optimistic Adapt-ML-Prod [Wei et al., 2016] and incorporates the clipping technique introduced by Cutkosky [2019] and further refined by Chen et al. [2021]. This algorithm, described in the language of Prediction with Experts' Advice (PEA), may be of independent interest beyond adapting to the generalized smoothness. Apart for satisfying all expected requirements, this algorithm offers simpler design, which does not require a forced restart as opposed to MsMwC-Master [Chen et al., 2021].
This efficiency improvement is achieved through simple self-confident learning rate in Line 6 of Algorithm 1, unlike that uses fixed learning rates and thus require restarts. In essence, our ap- proach incorporates the clipping mechanism by adding B the denominator and removing the threshold on learning rates commonly applied in prior Prod algorithms [Gaillard et al., 2014; Wei al., 2016]. This term B² acts as threshold, ensuring that 77., me,e| < 1/2, critical condition in the analysis (typically satisfied when the Lipschitz constant is provided for prior Prod algorithms). Lipschitz-adaptive algorithms may be sensitive the choice of By, while in our case, Bu O ((11(log 7)) is sufficient and does not ruin the guarantees as the factor Ollog log) is often treated as a constant [Gaillard et al., 2014; Luo and Schapire, 2015]. Theorem 3 summarizes the guarantee of Algorithm 1 and the proof is provided in Appendix C.3.
le-1, i.s in Algorithm I ensures that, for any i, E [N]. Σx (pr, li) - Ei=1 le,i, is bounded as follows, where BT = max{ Bo, maxtejr ):
Theorem 3. Setting My,i (pt,
T Σ
(ris. mes.) )2 +Brr
)r) (Iog(N)) + Bo + 1og77)
{
<0(1]
D 1=1
T
ec e--1
7

---

Algorithm Lipschitz Adaptive Optimistic Adapt-ML-Prod
Input: prior information of the scale Bu, the number of experts N.
1: Initialization:
w1,i 1, m,, 0 and M = 1/v1 + 4B for all [N].
2: for (= 1 to 7 do
3: Update the weight for E [N] Wii Wa, exp(n), Vt.
4: Calculate decision p: E AN with Pt,i EJE(N) We, and submit it;
5: Receive ry, update B. max BB 1|r, 10:mmm;,, lla) and build Fe,i ma, B, B.-
(re,--M,,))
6: Update the learning rate for i E [N]: 7,+1,1 I+ -m.)
76-11
7: Update the weight for i E [M] W1-1, = (we, exp (n..ee, - (F,, - m,,))) mid
8: end for
Algorithm 2 Universal Gradient- Variation Online I Learning under Generalized Smoothness
Input: curvature coefficient pool H. number base-leamers N, prior information of the scale Bg- 1: Initialization: Send N and Bo to the meta-algorithm, for X H. initialize an algorithm in Theorem 2 with it; initialize an algorithm in Theorem
2: for t= 1 to T do
3: Obtain p: from meta-algorithm, Xt,; from each base-learner E [N];
4: Submit X2 = EiE[N] Pr,iXt,i;
5: Receive fe(-) and send it to each base-learner for update:
6: For strongly convex functions learners: set rt, = (x,),, Xt,i);
7: For convex functions learner: set Vz,1 fx(x,) Le (xx,,));
8: Send m1+1, fx(x)) - fx(x,,)) to the meta-algorithm for [N].
9: end for
Our algorithm improves efficiency at the cost of an additional factor O O(vlog N). This factor is ignorable for universal online learning since we set N (log T). and the factor Olog log T') is negligible. Considering other related Lipschitz-adaptive algorithms, Mhammedi et al. [2019] obtain a regret bound of O (V,,,,r,,)
(log(N) + log log( (r(')) + Br (N), which offers better dependence the dominant term ( )² but it is unclear how include optimism. Chen al. [2021] achieve a bound of (( E, (C,, my.;) ) log(NT) + By (Ng() with a two- layer algorithm; however, the OVVlog 7' term would ruin the desired O(log Vr) bound for strongly convex functions. We remark that the compared methods enjoy other strengths not discussed here, such as the ability to compete with an arbitrary competitor æ E AN and the versatility to handle various learning scenarios, while our method is sufficient for purpose and the only option to tackle all the challenges as we mention in Section 3.2. Lastly, notice that the optimism m, involves the decision Pt. which might be improper since p: depends m, as well. We refer readers to Appendix C.1 for efficiently setting m, through a univariate binary search.
We emphasize that optimism m: in our algorithm is not chosen arbitrarily. In Line 5, we clip the regret with optimism to keep them on the same scale. The performance then evaluated based on the clipped regret Fi, For the analytical purpose, it is essential that (P,, F.) S O, and a sufficient condition for this is ensuring (pr, m.) S O, which imposes an additional requirement on m. In Appendix C.2, we discuss how this requirement introduces challenges for exp-concave functions minimization universal online learning.
3.4 Overall Algorithm and Regret Guarantees
The
to-gradient-vaeee variation vratiint-vvaraatoon technique decouples the design of universal methods into the base and meta levels, and we are ready to combine the proposed components together. We employ algorithms Section 2.3 as the base-learners and use Algorithm as the meta-learner, concluding in Algorithm 2. Theorem 4 presents its guarantee with the proof in Appendix C.4.
Theorem 4. Under Assumptions I 2 and assuming globul lower bound such that [ < fx(x) for any x X,t [T], setting N [log2 1" + 1. defining the curvature coefficient pool H.
8

---

12-1/T::EN -]],, and specifying By, Algorithm 2 simultaneously ensures:
O OVVV log Br):
(convex),
REGT S
log VT + G log logg((r))))) (Br)/A+ Br log Br) (A-strongly convex),
where X [1/T,11, Br (mmax Bo, D max supx Vx(()) V(e-1(x)123) and Gmax the Lipschitz constant on the optimization trajectory.
Without loss of generality, we assume X [L/T, 1] for strongly convex functions. If X 1/T. the optimal (log VA) bound would imply linear regret. in which case we would treat them as general convex functions. If 1, our result is slightly worse than the optimal one by a negligible constant factor. This simplification is also employed by Zhang et al. [2022a]: Yan et al. [2023].
This theorem additionally requires the lower bound loss functions, which is used to perform the binary search when setting the optimism. We defer the details of the binary search to Appendix C.1. This assumption is also employed recently in parameter-free optimizations [Hazan and Kakade, 2019; Attia and Koren, 2024; Khaled and Jin, 2024], and in empirical risk minimization settings [Hazan and Kakade, 2019].
Remark 1.
simply choose 0
Applications
In this section, we demonstrate the importance of our results by providing applications (SEA model and online games), where new results can be directly implied from our findings.
4.1 Stochastically Extended Adversarial (SEA) Model
The stochastically extended adversarial (SEA) model [Sachs et al., 2022] interpolates adversarial and stochastic online optimization. It assumes that the environments select the loss function fe(-) from a distribution D, The adversarial nature is characterized by shifts in distribution De, and when D, re- mains constant, the model captures the environments' stochastic behavior. The following quantities introduced to measure the levels of adversarial and stochastic behaviors in environments:
T
T
E = E
Σ sup [ - - F o. 1=2 XEX
Σ
sup ft (x)()) (9) XEX
where we denote by Fx(x) = EASD [x)] In above, Dirr represents the adversarial shift of the distribution, and oir denotes the stochastic variance.
Sachs et al. [2022] prove an O(vo io + E regret for convex functions, and refined regret for strongly convex functions obtained by Chen et al. [2023a]; Sachs et al. [2023], where o max maxte[2] supxe B[[] fx( V (x) and > max suPxe. [x(x)) (F)-1(x)11 Yan et al. [2023] present universal method which can obtain O(V o.. / Di and ((o max + E 7 E² bounds for convex and strongly convex functions. However, these results require the global smoothness assumption.
(irr))) bound of ( max + Σ x log(a +Eg,r) ))
Our result Section 3 implies a new finding for the SEA model, relaxing the assumption from the global smoothness to the generalized smoothness, while adapting to unknown curvature, summa- rized in Corollary The proof can be found in Appendix D.
Corollary 1. Under Assumptions
2 and assuming global lower bound for the loss functions such that f < [x(x) for any x E X, 1. E [T), setting N = [log, T + 1, defining the curvature [N - 1]}, and specifying Bo with specific value, then, under
coefficient pool H = (2 the SEA model, Algorithm simultaneously ensures:
O(V + V log log(G (ggGmmD)))
(convex).
E[REGT] s
O (G 2 + Enan)) log + 2i.r))
(strongly convex).
where Grax is the maximum empirical Lipschitz constant, 0 Σ E(sup ff(xx) v F, Fx(x) (x) and 22 -[/maxeeTT] Supxs fx((x) FF [1)

---

Note that, in real-world streaming learning applications, this corollary can offer more generalized depiction of data throughput with limited computing resources [Zhou, 2024; Wang et al., 2024], given the connection between these scenarios and the SEA model [Chen et al., 2024, $ 5.6]. Our result depends on - a larger quantity than o. but still can track the stochastic variance. This because our algorithm utilizes the information afterward x;- to generate X,. We refer the interested readers for this subtle issue to the discussion by Chen et al. [2024]. This dependence currently is unknown how to improve even under the global smoothness condition since we need to leverage the function variation to produce gradient variation, inevitably involving the afterward information.
4.2 Fast Rates in Games
Our second application explores the min-max game, aiming to achieve an e-approximate solution to the problem minxex maxyey fx. y) within an (1//T) fast convergence rate. Here, we assume that y) is convex for any y E ), and correspondingly. f(x.-) is concave given any E X. Additionally, we assume that both X' C IK" and y c I Th are bounded convex sets. Pioneering research ISyrgkanis et al., 2015] demonstrates that optimistic algorithms can reach convergence rate of O(/TT) by leveraging gradient variation. However, these results are limited to the global smoothness condition. In this part, we demonstrate that findings in Section 2 directly imply new algorithm that can exploit generalized smoothness.
Following the notations of Nemirovski [2004], we define 2 = xx, (x,y) E Z and introduce an operator F 2 -> IR" Th. with F(z) = (Vx -V,,)) We extend the concept of f-smoothness to the min-max optimization setting as follows.
Definition (f-smoothness for min-max game). A differentiable convex-concave function f & x
y + R is called f-smooth with a non-decreasing link function é [O, +20) + (0, +20) if satisfies: for any Z1, Z2 E Z, if Z1. Zg E IB (z,
|[ [2)]ll F()][VF())]l)) then [z) - F(22) 12 S ((2))F())II) ||z]
22 22 where B (z. r) denotes the Euclidean ball centered point with radius
This definition is a counterpart to Definition in the min-max game, but weaker as it does not require the twice-differentiabiliyy requirement. The s-approximate solution (x) to the min-max game is formally defined by y)) - S. y.) S f(x. y. ) e for any x E X. E y. To achieve the fast convergence rate to the solution, indeed our result Section 2 can be directly applied the min-max game and obtains the following tailored algorithm for min-max optimization:
2 = Ilz [2, 77, F(2,), 2 = Il ž - Fz:)).
(10)
In above we set the optimism at the point 2, order exploit the smoothness locally. We conclude our result in Corollary 2, with the proof available in Appendix D.2.
Corollary 2. Assume that the convex-concad function yx) is E-smooth, and the domain 2 is bounded with diameter D. By applying the tuning strategy described in Theorem I, and defining the final approximated solution as 2τ + Σt= Zt where z, is generated by Eq. (10), we achieve an E-approximate solution with convergence rate of O(1/T).
5 Conclusion
In this paper, we provide a systematic study of gradient-variation online learning under the gener- alized smoothness condition. We exploit trajectory-wise smoothness to achieve the optimal regret bounds: (VVVr) for convex functions and Olog Vr) for strongly convex functions, respectively. We further consider more complicated online learning scenarios, motivating to design new Lipschitz-adaptive meta-algorithm, which can be of independent interest. Hinging on this algorithm technique, we design universal algorithm which
with the function-varte variation-to- wwwpattiontt-grdneett-----e-- guarantees the optimal results for convex functions and strongly convex functions simultaneously without knowing the curvature. In addition, our findings directly imply new results in stochastic extended adversarial online learning and fast-rate games under generalized smoothness.
An important future direction for future research is to explore whether our method can be further extended to accommodate the one-gradient feedback model, where the Icarner receives only the gradient information of the decision submitted in each round. Another interesting problem is to exploit the exp-concavity in gradicnt-variin variation online learning under generalized smoothness.
10

---

Acknowledgements
This research supported by National Key R&D Program of China (2022/D01 14800)) NSFC (U23A20382), and JiangsuSF (BK20220776). Peng Zhao was supported in part by the Xiaomi Foundation.
References
J. D. Abernethy, P. L.. Bartlett, A. Rakhlin, and A. Tewari. Optimal stragies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 415-424, 2008.
D. Ataee Tarzanagh, P. Nazari, B. Hou, Shen, and L.. Balzano. Online bilevel optimization: Regret analysis of online alternating gradient methods. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2854-2862, 2024.
A. Attia and T. Koren. How free is parameter-free free stochastic optimization? In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 2009-2034, 2024.
Auer, N. Cesa-Bianchi and C. Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48- (1--744777, 2002.
Y. Bai, Y.-J. Zhang, P. Zhao, M. Sugiyama, and Z.-H. Zhou. Adapting to online label shift with provable guarantees. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 299604299744 2022.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operation Research Letter, 31(5):667-775, 2003.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Bianchi, Mansour, and Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2-3):321-356 2007. 2007.
L. Chen, H. Luo, and C. Wei. Impossible tuning made possible: new expert algorithm and its applications. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 1216- 1259, 2021.
S. Chen, W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 5002-5035, 2023a.
S. Chen, Y.-J. Zhang, W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25 (178):1 62, 2024.
Z. Chen, Zhou, Y. Liang, and Z. Lu. Generalized-smooll nonconvex optimization as efficient as smooth nonconvex optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 5396-5427, 2023b.
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference On Learning Theory (COLT),
pages 6.16..20 2012.
M. Crawshaw, M. Liu, F. Orabona, W. Zhang, and Z. Zhuang. Robustness to unbounded smoothness of generalized signsgd. In Advances in Neural Information Processing Systems 34 (NeurIPS), volume 35, pages 9955-9968, 2022.
A. Cutkosky. Artificial constraints and hints for unbounded online learning. In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), pages 874-894, 2019.
A. Cutkosky and K. Boahen. Stochastic and adversarial online learning without hyperparameters. In Advances in Neural Information Processing Systems 30 (NIPS), pages 5059-5067, 2017.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7). 2011.
M. Faw, L. Rout, C. Caramanis, and S. Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive SGD. Proceedings of the 36th Conference on Learning Theory (COLTT), pages 89- 160, 2023.
11

---

P. Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In Proceedings of the 27th Annual Conference on Learning Theory (COLT), pages 176-196, 2014.
E. Hazan, Introduction to Online Convex Optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
E. Hazan and S. Kakade. Revisiting the polyak step size. ArXiv preprint, arXiv:1905.000 2019.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-192. 2007.
A. Jacobsen and Cutkosky. Parameter-free mirror descent. In Proceedings of the 35th Annual Conference on Learning Theory (COLT), pages 4160-4211, 2022.
A. Jacobsen and A. Cutkosky. Unconstrained online learning with unbounded losses. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 14590-14630, 2023. Joulani, A. György, and Szepesvári. modular analysis of adaptive (non-jconvex optimiza- tion: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108-138, 2020.
A. Khaled and C. Jin. Tuning-free stochastic optimization. In Proceedings of 41st International Conference on Machine Learning (ICML), pages 23622-2533 2-621, 2024.
B. Kulis and P. L. Bartlet. Implicit online learning. In Proceedings of the 27th International Conference on Machine Learning (ICML), pages 575-582, 2010.
H. Li, J. Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2023.
H. Lu, R. M. Freund, and Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1):333-354, 2018.
H. Luo and R. E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Proceedings of the 28th Annual Conference on Computational Learning Theory (COLT), pages 1286-1304, 2015.
7. Mhammedi, W. M. Koolen, and T. van Erven. Lipschitz. adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), pages 2490-2511, 2019.
A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with lips- chitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
A. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. SIAM Review, 27(2):264-265, 1985.
Y. Nesterov. Lectures on Conver Optimization, volume 137. Springer, 2018.
C. Nicolò and O. Francesco. Temporal variability in implicit online learning. In Advances Neural Information Processing Systems 33 (NeurIPS), pages 12377-12387, 2020.
F. Orabona. A Modern Introduction to Online Learning, ArXiv preprint, arXiv:1912.13213,, 2019.
F. Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 7 716:30-69, 2018.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference On Leurning Theory (COLT), pages 993-1019, 2013a.
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neurul Information Processing Systems 26 (NIPS), pages 3066-3074, 2013b.
A. Reisizadeh, H. Li, S. Das, and A. Jadbabaie. Variance-reduced clipping for non-convex optimiza- tion. ArXiv preprint, arXiv:2303.00883 2023.
Sachs, H. Hadiji, T. van Erven, and C. Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 691-702, 2022.
Sachs, H. Hadiji, T. van Erven, and C. Guzmán. Accelerated rates between stochastic and adver- sarial online convex optimization. ArXiv preprint, arXiv:2303.03272. 2023.
12

---

V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pages 2989-2997, 2015.
M. Telgarsky. Stochastic linear optimization never overfits with quadratically-bondded losses on general data. In Proceedings of the 35th Annual Conference on Learning Theory (COLTT) pages 5453-5488, 2022.
C. Tsai, Y. Lin, and Y. Li. Data-dependent bounds for online portfolio selection without lipschitzness and smoothness. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages
62764-62791, 2023.
van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3666-3674, 2016.
B. Wang, H. Zhang. Z. Ma, and W. Chen. Convergence of adagrad for non-convex objectives: Sim- ple proof's and relaxed assumptions. In Proceedings of the 36th Annual Conference on Learning Theory (COLT), pages 161-190, 2023.
G. Wang. S. Lu, and I.. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference Uncertainty in Artificial Intelligence (UAI), pages 659-668, 2019.
J. Wang, M. Yu, P. Zhao, and Z.-H. Zhou. Learning with adaptive resource allocation. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 52099-52116, 2024.
C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Tracking the best expert in non-stationary stochastic envi- ronments. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3972-3980, 2016.
Y.H.. Yan, P. Zhao, and Z.-H. Zhou. Universal online learning with gradient variations: A multi- layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 37682-37715, 2023.
T. Yang, M. Mahdavi, R. Jin, and S. Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95(2):183 2211883-233,222 2014.
W. Yang, Y. Wang, P. Zhao, and L. Zhang. Universal online convex optimization with projection per round. ArXiv preprint, arXiv:2405.19705, 2024.
B. Zhang, J. Jin, C. Fang, and L. Wang. Improved analysis of clipping algorithms for non-convex optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 15511- 1- 15521, 2020a.
J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoreti- cal justification for adaptivity. In Proceedings of the Sth International Conference on Learning Representations (ICLR), 2020b.
L. Zhang, G. Wang. J. Yi, and T. Yang. A simple yet universal strategy for online convex optimiza- tion. Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26605-26623, 2022a.
M. Zhang, P. Zhao, H. Luo, and Z.-H. Zhou. No-regret learning in time-varying sero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26772- 26808, 2022b.
P. Zhao, Y.J. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12510-12520, 2020.
P. Zhao, Y.J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 - 52, 2024.
H. Zhou. Learnability with time-sharing computational resource concerns. National Science Review, 11(10))waee044, 2024.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Pre- ceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936. 2003.
13

---

A
Related Work
In this section, we review the related work in gradient-variation online learning, the generalized smoothness conditions, and the Lipschitz-adaptive algorithms.
A.1 Praddent-VVariatee Online Learning
The gradient-variation quantity defined in Eq. (2) is firstly introduced by Chiang et al. [2012] for global smooth functions. Chiang et al. [2012] obtain Q(VVT) and O á log Vr) regret bounds respectively for general convex and n-exp-coneave functions. Zhang et al. [2022a] later achieve O log V/) result for X-strongly convex functions. Considering the non-stationary environ- ments, Zhao et al. [2020] study gradient variation under the dynamic regret, a strengthened mea- sure that requires the learner to compete with a sequence time-varying comparators. Their work revives the study of gradient-variation online learning, especially revealing the importance of the stability analysis in the two-layer online ensemble. Their results are further improved in Zhao et al. [2024], where they only require one gradient per round with the same optimal guarantees through the collaboration between the meta and the base. For universal online learning [van Erven and Koolen, 2016], there are several recent researches trying to derive the variittovv bounds in this context [Zhang et al., 2022a; Sachs et al., 2023; Yan et al., 2023].
Gradient variation demonstrates its importance due to its close connection with many online learning problems. Pioneering works [Rakhlin and Sridharan, 2013a; Syrgkanis et al., 2015; Zhang et al., 2022b] demonstrate the importance of gradient variation via useful property (Regret bounded by Variation in Utilities, RVU) to achieve fast-rate convergences in multi-player games. Recently, Sachs et al. [2022] and Chen et al. [2024] reveal that the gradient variation is also essential in bridging stochastic and adversarial convex optimization.
However, all the mentioned works require the global smoothness assumption. As highlighted in Proposition 2 in Appendix B, the smoothness condition necessary to obtain the gradient-variation bounds for algorithms with first-order oracle assumption [Nesterov, 2018]. Exceptions are that Jacobsen and Cutkosky [2022]; Bai et al. [2022] obtain the gradient-variation bounds without the smoothness assumption, but they require implicit updates [Kulis and Bartlett, 2010; Nicolò and Francesco, 2020] per round, which may be inefficient under online settings. Our work considers generalized smoothness, and we develop first-order methods to achieve gradient-variation bounds.
A.2 Generalized Smoothness
Generalized smoothness has received increasing attention in recent years since the analysis under the standard global smoothness is insufficient to depict the dynamics of neural network optimization. Based on the empirical observation for the relationship between the smoothness and the gradients of LSTMs, Zhang et al. [2020b] relax the global smoothness assumption by (Lo, L1 Ls)-smoothness con- dition, which assumes fx)) la S Lo + f for offline objective function f X' + IR. With this new smoothness assumption, Zhang et al. [2020b] explain the importance of gradient clip- ping in neural network training. There are variety of subsequent works developed for different methods and settings IZhang et al., 2020a; Crawshaw et al., 2022; Reisizadeh et al., 2023; Faw et al., 2023: Wang et al., 2023]. There are studies further generalizing the (Lo, L -smoothnness condi- tion. Chen et al. [2023b] introduce the a-symmetric smoothness condition, which symmetrizes the (Lo, L )smoothhssss condition and allows the smoothness to depend polynomially on the gradient. Notably, Li et al. [2023] propose the /-smoothness, defined as ||V2[(x) [(x)]l2 S <(]V ll2) This condition does not specify a particular form for the function R + R, other than some mild assumptions about its properties, thereby allowing great generality of this notion.
Telgarsky [2022] introduces the concept of (G, -uqudrraati bounded functions, which aims to generalize the Lipschitz condition as f[x < G L|x - Xoll2 with reference point Xy E X. Though this notion covers the standard global smoothness condition, it lacks detailed depiction of the relationship between the smoothness and the gradients, hindering further research into understanding the optimization dynamics such as the role of gradient clipping [Zhang et al., 2020b]. Jacobsen and Cutkosky [2023] investigate online convex optimization under this constraint such that the online functions may be unbounded. However, is unclear how to obtain the gradient- variation regret in their context and using their methods.
14

---

We also mention another generalization of the standard smoothness called the relative smooth- ness [Lu et al., 2018]. A function f X R L-smooth relative function if f(x) < f(y) + (V.(y): y) (x, for any x,y in, where h X + IR is reference function with DA (x, y) denoting the Bregman divergence. However, the global constant still required to tune the algorithm, and studying this notion is beyond the scope of our paper.
A.3 Lipschitz-Adaptii Algorithms
The upper bound of gradients G and the diameter of the bounded feasible domain D are often re- quired to build up online algorithms. An algorithm that requires the diameter D of the bounded feasible domain D but not the upper bound of gradients is known to be Lipschitz-adaptive [Duchi et al., 2011; Orabona and Pál, 2018; Cutkosky, 2019; Mhammedi et al., 2019]. For the general OCO setting, to the best of our knowledge, there no Lipschitz-adaptive algorithm that ensures a cendient-variation bound. When specialized to the Prediction with Experts' Advice (PEA) set- ting [Cesa-Bianchi and Lugosi, 2006], Chen et al. [2021] design two-layer algorithm with restart- ing mechanism that can obtain gradient-variation bound in PEA setting. In this paper, we develop a new I Lipschitz-adaptiv algorithm with lightweight design, which guarantees the wradient-variation bound as well and is the only option for our purposes, to the best of our knowledge.
B Omitted Details for Section 2
In this section, first provide judgement of the necessity of smoothness for first-order online algorithms Appendix B.I. Next, we will provide proofs for the theorems in Section 2.3. In Appendix B.2, present the omitted discussion for the challenge in designing the algorithm for exp-concave functions. We introduce a key lemma in Appendix B.3, which abstracts the key idea of exploiting the generalized smoothness. Later, the proofs for Theorem and Theorem 2 provided in Appendix B.4 and Appendix B.5, respectively.
B.1 Necessity of Smoothness
We first provide a lower bound on the convergence rate for first-order methods with convex functions. Proposition 1 (Theorem 3.2. of Nesterov [2018]). There exists a G-Lipschitz and convex function f: IRd R with |x] x. D where x, E arg min f(x) such that
GD
f(x)) - min f(x) 2
xeRd
2(2 + Vt)
for any optimization scheme that generates sequence {xt} satisfying that
X; E X1 + Lin [Vf(x)....... [x(x--1)}
where Lin(a } denotes the linear span of vectors a
Yang et al. [2014] prove the necessity of the smoothness to obtain the gradient-varitte variation bounds with convex functions using the first-order online algorithms. We formally present this idea in below.
Proposition 2 (Remark 1 of Yang al. [2014]). The smoothness assumption for G-Lipschitz and convex online functions Jt X + TR is necessary for any online algorithms, whose decisions are linear combinations of the queried gradients when no projections made, and ensure:
T (xxx)
T min Σ ((())s(( + constant, XEX 1=1
with only e T times gradient queries, with N being constant independent of T and environ- mental parameters, such as the Lipschitz constant and the smoothness constant.
Proof. We prove this proposition by contradiction. Assume that fi non-smooth. Then consider special case where the algorithm projects the decisions onto X' Ed i.c., projections are made,
15

---

and all the online functions are equal fi = =... = fr f. Notice that, under such case, the gradient variation zero and therefore,
T Σ
T f(x) 5
fxx)
min XEX
which implies Xy = Ei=1 X approaches an O()/T) convergence rate. Now it remains to check whether this convergence rate contradicts with Proposition Denoted by xi...., ,x. the points that the algorithm queries gradients on, because the decisions are linear combinations of the gradients when no projections are made, then,
&y E X1 + Lin (VS(x), V
which indicates that, there exists a method which promises Occ/T) = ( convergence rate under the protocol considered in Proposition 1, contradicting the lower bound.
B.2 Challenge for Exp-Concave Functions in Regret Minimization
In Section 2, we design algorithms for convex and strongly convex functions respectively. How- ever, the gradient-variation regret for exp-coneave functions [Hazan et al., 2007] under generalized smoothness has not yet been addressed. For online learning with global smooth functions, it has been demonstrated that an (d V/r) regret is attainable for exp-concave functions [Chiang et al., 2012], which is realized by optimistic variant of the online Newton step algorithm [Hazan et al., 2007] using the last-round gradient as optimism, i.e., Mr = Vt-i (x:-1). However, it remains unclear how to obtain a general optimistic bound of order log Dr) with Dr = E V ( M, 1 for arbitrary optimism { [M, M Our technique for achieving gradient-variation regret under gener- alized smoothness relies flexible setting for optimism (which may be the last-round gradient) and step size tuning (which requires a trajectory-wiss stability analysis), making it challenging for extension to exp-concave functions. We leave this as an open question for future research.
B.3 Lemma for Regret Minimization
Below, present lemma that leverages the local smoothness of the optimization trajectory to derive gradient variation within the OMD framework. This lemma can be applied in the analysis of both convex and strongly convex functions.
Lemma 2. Under Assumptions I and 2, by selecting regularizer v/((x) 2m. | 12. setting step
sizes satisfying that M S 1) and ny S 1/(4L,-1), where L, l--1 (2 (2x) l12). and by
choosing optimism as M, V f- (x4), the OMD in Eq. (4) ensures the regret bound:
1
Vx((x)) xx.)
(||x,
-
-2,12
|x. 8(+1113)
2TT
1=1
T
+
1/
Vf((x))) V
||x
xel12
417,
D2
T
T
< + 2
nel V - (
|x - 22
(11)
21Fr
47pt
where x, E arg min Et fe(x) denotes the best decision in hindsight.
Proof. Following the standard analysis of OMD (Lemma 3), OMD with the optimism chosen as M₁ = f(-,((x,) ensures the following regret bound:
(xxi))), - xx,) 2n
(I|x,
111
1|x.
xe+1
ne
-f
TERM-A
TERM-B
16

---

1
(1
X
12
|x:
&cllB)
2ftt
TERM-C
The analysis for TERM-AD is straightforward under Assumption 2:
1
D
T
D2
D2
D
TERM-A &
|x.
x
|xx
x
2711
2Tp
2T)
2771
27
21)-1
2TT
f=2
Next, we analyze the TERMMB under the generalized smoothness condition. By the basic calculation, can decompose the TERM-B into following two terms:
TERM-B S Σ ne V V + Σ nr V (
(12)
where the first term is the desirable gradient variation and the second term should be further ana- lyzed under the generalized smoothness. Given the optimism setting and the step size tuning, we demonstrate that x2 and & are sufficiently close apply local smoothness:
(
xx - 8,112 S ml V (8.) S
4h,-1
In above, the first inequality is by the the Pythagorean theorem and the second inequality is by the step size tuning. Therefore, we can apply Lemma to bound the gradient deviation in Eq. (12) by
T
n T
|x: 22
Finally, combining TERM-A, TERM-B and TERM-C together, we obtain:
V f((x:),xx X1- - x.)
D2
+2
Σ
T
Tol V f((x))
T
1
||x:
xel12
20T
47
(=1
T
- >||xx 32ol2
+
(21]
12
A1h1
t=1
D
T
1 32.1..
+ fc((x)) - v
||x:
2/TT
4n
where the second inequality is by setting T) S 1/(4Lt-1). Hence, we finish the proof.
B.4 Proof of Theorem
Proof. The step size tuning in Eq. (7) in Theorem satisfies the criterions for applying Lemma specifically that M4+1 Tt and vi S 1/(4Lt - 1), where L,-1 (2) Therefore, by Lemma 2 and the convexity of loss functions, we obtain:
T Σ J((x.) (.(x)))
T ((VS(xx));. - x.) S +
D2
Σ [V]lV)((.)))
Se-1
1=1
where x, E arg minxxx
Et fe(x).
The first term can be bounded as follows,
D2 2tpr < 2L D2 D
D. 2
1+
f((i))) - vx-1(x)11+
(x))ll
= =m D2 + DV
17

---

where we denote by Lmax= e (T] L. For the second term, we apply the self-confident tuning lemma (Lemma 5) by choosing f(x) = 1/v2 in the lemma statement:
( V
Th Vfx())) V
1=1
(x,)),)
(x.))
T
2D
1+
Σ (Vss(x,) VX
(1+ D max (x( (x-((x))11 EE(T)
-D
where we use Gimax to denote the empirically maximum Lipschitz constant. The additional term O max results from the lack of knowledge about Gmax- However, we can improve this term to ( D) by incorporating the clipping technique [Cutkosky, 2019; Chen et al., 2021] into OMD framework. In the main text, avoid introducing this method to prevent complicating the approach further. Our goal in the OMD introduction is to illustrate how to adapt to generalized smoothness at the base level. The details of this refined approach are provided in Appendix B.6.
B.5 Proof of Theorem 2
Proof. For X-strongly convex functions, we tune the step size as 7/: = 2/ + 16 max,e Le). where we denote by T. = ( 1l)+) the locally estimated smoothness constant. By the property of strongly convex functions and Eq. (11) in Lemma 2, we have:
T Σ fx,,,) - > fx.)))
T
T
= (x,,,,,,
X - xx,) 2 ||x,
- -x, 1|
1=1
1=1
t=1
1
(11x+ -xell3 - ||x, R+11 12))
1|x
xx112 +2 Σ
fx(x))
(x))(x))
217
2
TERM-A
TERM-B
T
|xx - 22112
4mp
1=1
TERM-C
Unlike in the case of convex functions, TERM-A A involves negative terms derived from the strong convexity of the loss functions, which require slightly different analysis:
1
1
A ||x,
TERM-A- <
X.
x112
+
||x,
xx 12
2111
2m
21
2
XD2
T
maxx
L. -
max L.) [>x] - xel12
マ/2 ||x, xx
4
xc({)
=E(t-1]
1=2
XD2
+ 4D2
max L. + +E[T]
Σ
T
xx. 11
1 _|x -0-xx x
(bounded domain assumption)
2
4
t=2
XD2
+ 4DD Lmax +
||x:
(||x, kell3 = 2||xx. xx
+ X xx11
4
2=
XD2
X 1T
+ 24D22mma Lmax +
(x,, (x)
(Lemma 4)
2
XD2
+ 2D222
2
Lmax
+
Ne Vel[V[i(x.)) - V (
4
18

---

XD2 S 4 + 2D Lmax +
T 27 Vf(())) - V 11 +
Σ
27 V (x-1(x)) - V
where the last term can be cancelled by TERM-C, and the third term in the same order TERM-B B. Therefore, we only need focus TERM-B. For TERM-B, we follow the analysis of Chen et al. [2024], who applies a simpler analysis for the self-confident tuning. First, we define:
T Σ
(x.)
(x,)
Then by dividing the time horizon into [1, a] and la+ + 1, T) we can upper bound TERM-B as:
T
TERM-B <
Vx(x)) V (x +2
Σ
mll[)(((x.) - V (x+)1(
1=a+1
Vie-
Σ
-
N
XI
1
< 4(max xE[T]
(xx()))
VS--I
Σ
[Vs((x)) (xx1(xx)113 (13)
Xt.
Tt
1=1
1=++1
I
16G max
1
4
Σ
[x((xx))
Vz-
Al.
A(a + 1)
(=1
(=a+1
16G max
(1 + Ina)= +
16G
T
16G2 + max
max In
f +1 +
X
A
where we use Gmax to denote the maximum Lipschitz constant estimated empirically. Therefore:
E f((x) 5o (Oxer log V1 + Limax D2 AD2 >DD)
which finishes the proof.
B.6 OMD Incorporating Clipping Technique
In Appendix B.4, an additional term O ( max D) shows in the final regret bound, which results from the lack of knowledge about &max- In this subsection, we improve the term O D) to O(Gmax by incorporating the clipping technique [Cutkosky, 2019; Chen al., 2021] into the OMD framework. This modified OMD algorithm is defined as follows,
X = IIx X
1
R = 1Ix [ mgg:),
(14)
where f B (v)(xx)) (x,) is clipped gradient with the maintained threshold B, max Bu, max (x, (x, Notice that, x, still updates from &, in the same manner as illustrated in Theorem 1, therefore, we can apply the similar analysis to it when exploiting the smoothness locally. Correspondingly, provided the following step size tuning:
B
D2
= min (V B + E g.
(15)
V
1 (x))
4L,-1
where the key modification that we add BE_, in the denominator to facilitate the tuning analysis and we denote by L. (()x+)) The following theorem presents the guarantec.
19

---

Theorem 5. Under Assumptions 2, assuming online functions are convex, OMD presented in Eq. (14) with the step sizes in Eq. (15) ensures that:
5D
REGT - 2
22V + 4. D2 + 5,Gmax
the gradient variations, Im = max Tu is the maximum smoothness constant over the optimization trajectory, and Gmax is the maximum empirically estimated Lipschitz constant.
where VI V===ie =i= SuPxEX -V
Proof. First, prove that the clipping technique incurs constant in the regret bound:
T
T
B B--B--1 (Vf((xx) Vf--1(8),,x -x,)
Vf((x)). xx)) (, xx)
Σ
B.
1=1
D
B, B(-1)= D(Br Bu) (G D).
In the following analysis, will focus the regret associated with the clipped gradient g.. Fol- lowing the standard analysis of OMD (Lemma 3), and with simple calculations, we arrive at:
D
T
Xt
xx)
Th gt
Vie
x
(16)
2TT
2T
TERM-A
TERM-B B
TERM-C
By the step size tuiing, TERM-A A can be bounded as:
D
T
TERM-A < 2 D
B
+
(8.-1
2
s=1
T
D
< 2m D2 + Gmax D +
g. Vf. (8,)11
2
sm2
T
B2
2m D2 + Gmax D +
s-1
V - V
2
B²
a=2
T
< 2 D + Gmax D +
Σ (v.((x)) (8,)1
(17)
2
TERM-A-
For TERM-B (16), by the self-confident tuning lemma (Lemma 6) we obtain,
g
(x:)
gr so- (R,)
TERM-B
D
B2 Σ
VSs (x,)
g.
ffa-((Xx))
< 2D,
g ( 2D
Σ
-
+2Gmax D.
(18)
TERM-B
Combine TERM-A-VAR in (17), TERM-B-VAR in (18), and negative term TERM-C in (16):
TERM-A- VAR TERM-B- VAR
TERM-C
5D
T
2
(x(( (x) +2
V (xx)
V
(x
2
21
1=2
[=
20

---

5D
T
5D
T
2
Vx((
2
- -f-
2
2
1=2
1=2
T
||x: - 2
21/
[=1
5D
5D
T
2V
2
>
D
Xt
Σ
2(
max L.) 1x+ 8:11 sE(t-1]
2
2
1=2
5D
25
2V
L
D2
16
where in the forth line we apply Lemma 1, and ub the final line, we apply the AM-GM inequality, 2/ab - a < b. Combing each component together, we conclude the proof as:
f((()
E1(xx)
Σ
-x
(xxe))))
x.) gr X x.) + 2GmaxD
t=1
5D
22V mmx 1>2 55mmax] D.
2
C Omitted Details for Section 3
In this section, we present the omitted details for Section 3. Appendix C.1 discusses how set the optimism m, efficiently via binary search. Appendix C.2 provides the omitted discussion for the challenge in universal online learning with exp-concave functions. Proofs for the theorems in Section 3 are included Appendix C.3 and Appendix C.4. Appendix C.5 gives simple universal algorithm under the global smoothness condition, which improves the optimality and efficiency of the method by Yan al. [2023], at cost of additional function value queries.
C.1 Discussion on Optimism
In this part, we discuss how to set the optimism m, that involves the decision Pt- We present the steps for incorporating the optimism and generating the decision in Algorithm for reference:
Wt w ex.(n,, Pt. ESE(N) Weg
(19)
For more general consideration, set optimism the My,1 [(EiE|N) Pt, f X + R is convex and continuous function and x, X is a decision available before setting the optimism. Notice that i; requires Pt to update while is produced based on Wy,, resulting in a circular argument. Following Wei al. [2016], the P: can be solved via the binary search technique. We define a = f(Eie(N) Xt), then the weight We,i is a function of as Wt,((a) = we, exp(h,saa (x),)))) Furthermore, with the update formulation in (19), the decision Pt, is function of a as well, with the formulation (a)) = g(a:) = ((EiEN)) (t, solving the decision Pt is equal to solving g(a: a.
h(x;,s) where
Ex((y) Ve. (o)) By introducing a function
T/. (a)
Below, we prove the existence of a solution to g(a) = a. Provided the lower bound f of function
f(.), and by the convexity of the function /(.), the searching range of a is restricted to [ S S maxie(N] (x))) and thus a is bounded. The continuity of the function f(-) implies the continuity of the function g(a:) as well. The choice of a = f results in g(a) - a = f(E (a)xx)
f O, and the choice of a = max {f(x)) implies g(a) - a < EiEiN] (a) maxie(N] (f(x))) 0, indicating that solution to g(a) exists. By using a binary search within [f, maxie(N] (x))))), we can approach within an error O(1/T) in Ollog T) iterations.
21

---

The above argument requires the lower bound of the function f(-) to determine the searching range over a. When considering a simpler case where f(x;) = & and f(ENE Pt,(,;) EIEIN] Pt,ihi we can omit the requirement for the lower bound because a falls within [minge(y] { max (L,)), because of the simpler structure of linear functions.
C.2 Challenge for Exp-Concave Functions in Universal Online Learning
In Section 3.4, we present Algorithm 2 that achieves gradient-variation bounds for convex and strongly convex functions simultancously. However, it does not guarantee such bounds for exp-concave functions. Besides the challenges discussed Section B.2, a new obstacle arises in designing the meta-algorithm. We require optimism to satisfy (Pt, mi) pass the meta-algorithm with heterogeneous inputs, and therefore we set Ma = fx,1(x,)
0, since
(xt,) for all the base-learners. This optimism design is suitable for strongly convex func- introduced by optimism can be bounded by tions, the term (f--(i(x))) fx=1(xx:)))
Gmaxy E X 1.. cancelled by the negative term - E, A/|x; - x1,ill3 from strong convexity. However, for exp-concave functions, the negative term - -(VSe(x)) X x,,)² from exp-concavity may not be sufficient to cancel (fx( -ft- fx-1(x,,))² for future exploration.
We leave this as an open problem
C.3 Proof of Theorem
In this subsection, prove slightly generalized version of Theorem 3, which does not specify optimism and instead imposes conditions only on Py. One can verify that the setting of optimism in Theorem satisfies the requirement of Theorem 6.
Theorem 6. By setting řt,s such that Σ Pt, I 0, Algorithm 1 ensures that, for any i, E [N].
the regret Etz (pt, li) Et= le,i, can be bounded by:
T
(res. m4..) Br) (log(N) log Br + log T?) )
where By = max Bo, maxee()] ||r ml
Proof. First, we demonstrate that the clipping technique [Chen et al., 2021; Cutkosky, 2019] incurs constant in the regret bound:
T B, B
Th. - Fe,
Σ 1=1
TE. - Mini
BI-1
(ri.. - m,,.))
Σ
(re,s. - -me,i.
B.
B.
t=1
T
T
B
B
B B
me, m4.ll
ri 1arm-mllee milloo I Br Bo.
(20)
Bi
B
1=1
(=1
In below, we focus on the analysis associated with clipped regret Fr, Following previous work [Wei et al., 2016), define W, = Wt. represent the summation of weights time I. The quantity W, can be realized as the potential to be analyzed. Next, we consider to upper bound In Wr+1-
By the inequality x S xa + (a 1)/e for x > 0, 2 0, for any i E [N], we have:
77.4 WT+1, & (WT+1,) MT+L.
Tr -1-11
+
(21)
Based on the updates in Line 7 of Algorithm 1, we bound the first term on the right-hand side as:
RTa PIILS
(WT+1a)
WT, exp
(Tr The (FT.: mT,)²)
- exp
(TT (Fr,s mr,,) - w (Fr,s - m²r,)²)
22

---

S Wr, (1 + n1 (Fr, m.r,))
(22)
The last inequality is by exp(x - =²) S 1 + for x: 2 -1/2. This is crucial condition needed to be verified for Lipschitz-adaptive meta-algorithm. By the tuning of learning rates, and the clipping technique, control the range of frr mT,)) well:
BT-1 FT, BT
BT-1 1 2Br-1 2
TT mT TT,
mT,a S BT S
which meets the criterion for applying the mentioned inequality. By plugging inequality (22)
into (21), we can further analyze the weights for all experts at time T:
N
N
WT+1.
Wr, (1 + 7I.4 (Fr, mT,)))
+
i=1
Wrs (1 mmr +
TTi
aT+11
im
N
Σ
WT, exp( (T.)
+
MT, " TT
TTT
-1
1=1
i=1
N
N
N
N
Σ
Wr,
+
PT.
Pr.
+
TT,
7T+1,
)=1
1=1
1=1
N
N
TT,
-1).
$
WTy
+
e
71+11,
1=1
1=1
where we apply - r < exp(-x) for any x E R, and the last inequality is by the assumption in the theorem statement that Ei=1 Pr, S 0 for any t E [T].
Now we are ready to upper bound WT+1 in an inductive style:
N
N
MT'ss
1) = Wr+ +
Mr's
WT+1
WT+1
WT&
11
11
T
N
T N
11,1
-1
)
nh. 11-11 1):
W
N +
(23)
7/-1,
71+1
im1
where the last inequality is by the induction. It remains to analyze the last term, the deviations of the learning rates. We present the following analysis tailored for the new learning rate setting, Vi E [N]:
1+ Σ7 1= (Fr. - m2, 3 + 4B2
T
+ ΣT
(Tr, - m,,))
(7,;) 2 + 4B2
4B2. 4B2 (FT ))T
1 E[-1
(Fr.s mp,)) 2 + 4 4B2
1
4B7 4B2_ + (FT, 1)
<
(VI+ x 5 1 (x)
2 1+ >
(Fr, m²,)²² 2 + AB2_
ΦT, JJ-1 Øt.i
(01, 4B, ABB, + (Fr, - mn 2 0)
2 1 4B3
By Lemma 5 with the choices of f(xx = 1/x, 0g = + 4B3 a, = &r.. in the lemma statement, summing up the preceding inequality from 1 to T results in:
T
Nt.i -1) <
2Bz
T
+
1 4B2
(Fr. me,)) - In(1 + +4B))
11+1,
1 4B3
23

---

2B4
1+ (T+ 4)
(24)
1 4B0
+
4B4
Now combining (23) and (24), we can upper bound In Wr+1 as follows:
B3
1 1+TTB
1 4 ) + IIN
In WT+1 In In another direction, we lower bound In WT+1 In WT41, with an inductive argument:
1 (1+ + 4Bg
In
(25)
2e
1 In 41.
(In t.S.fT. Ti... (FT,.. m))
41,
1
In WT,
UT, -TT,., )a fT.
T
1
WI
Σ 1=1
Bes (Frie - m,,..
11,i,
T
T
= Σ
Mes, (Fr.. -me,.. )
Per
(Wi,s, 1)
Rearranging the above equality with notice of Eq. (20), we have:
Σ Tta
Pri + Br
T
B2
)) +InN) + Br. 1 412
Σ
Mri (Fr,i,
m²
In (1+
In
4/1+
1 4Bg
2e
1=1
where the second term is in the order of
of ( B2 + Σ (rc. m,,,)) )2. (log Br log(T + log.
t=1
As for the first term, by applying Lemma 6, it can be bounded as follows:
(Fe.. )²
Me. (Fr.i. me,..)
+ ABB + | (Fe.d. -m,t.. )2
(Fr.s. m4,i.)
2
1
(Fr. me,i. )2
Ei=r(F (Fait. -a.i.) )2
B
2, 1+
(re,i. m2,.,)² 22
1+ Σ
(rr, - -m,,e.
B
t=1
Thus, the proof is complete.
C.4 Proof of Theorem
Proof. We first decompose the static regret based on the performance of base-learner i, into two parts as presented in Eq. (8).
The base-regret is guaranteed by the corresponding base-learner via Theorem and Theorem 2. And we mainly focus on the analysis of the meta-regret by leveraging Theorem 6. First we are required to verify the condition that Eie(n Fr, < O. Without loss of generality, we assume the 1-st base- leamner is for convex functions. Recall that we set rt, = (V)((x,) xx,) for strongly convex
24

---

functions learners i E [2, N M2,1 = f((x)) 1 for the convex function learner, and optimism my,i fi-1(x;) (x,) fi- (Xt,,) for each base-learner E [NV] therefore we have:
Σ Pe, (1 BL-1) NE[N]
(fi-((x)1))-
Σ
Pt.ffi P
Br
[E|N]
+ (fax( - f((xx,))
Σ Pe. iE|2,N]
(xxxVi - -x(,i)
$ (1 BB-1)
Σ
Σ
B₁
KEIN]
MEIM
+ (pr. x
+
Σ Pt. Px - xx,s)) O. <E[2.N]
Therefore, Theorem 6 is applicable in analyzing the meta-regret for universal online learning- In follows, we prove the regret bounds for convex functions and strongly convex functions respectively.
Convex functions. By Theorem I, the base-regret is bounded by O(VVT), as for the meta-regret, by the setting of inputs and optimism, by Theorem 6, is bounded by
META-REE 0o
- - f((xx,)) (fe-1(x)) ft- - (x Cr + Br log By
=0
Σ - f(-1(x))) - 1x-1(x)1)) (- Cr + By log Br
0
Σ (VI((E)))) - Vf-- -x,1i Cr + Br log BT
T
T
=
5o
D
Σ
sup (x)) - V Cr + log BrggBr) Br XEX
where we denote by === = Olog BT + log( BrT))) and in the third line we apply the mean value theorem. Combining the base-regret and meta-regret together, concludes that the static regret bound for convex functions is bounded by Vogg (lg++ where Br O(Gmax D)
with Gmax denoting the maximum Lipschitz, constant.
Strongly convex functions. For -strong convex functions with A, E [1/ by the construc- tion of the curvature coefficient pool H. there exists i, [2, N] such that
Xi. X, I 2Xi,
With this specific i, base-learner, the base-regret can be upper bounded by O(log Vrr/\,) by Theorem 2, up to a multiplicative constant of 2. The meta-regret can be bounded as follows:
META-REG S
(Vx()))), - -x,,))
xxx - Xt,i,
2
T
X
((VI)(x))) -x.x) (x.1 Sa- (x., .C
|xt
1 1xx-xx,;,1
BTCT
2
[=1
T
Σ -xx,))) (VS- - ). N2.C-
Σ
|xx xt,,,
+BTCC
2
t=1
T
T
0 Gmax
Σ
Xr
11.
CT
Σ
\
xx
x1. -
BTCT
2
[=]
t=1
25

---

Algorithm 3 Universal Gradient- Variaatio Online Learning under Global Smoothness
Input: curvature coefficient pools Hy, Hesp. number of base-learners N, optimistic Adapt-MI. Prod [Wei et al., 2016] as the meta-algorithm, base-algorithms Aeva. Assp
1: Initialization: Pass N the meta-algorithm, initialize base-learner with Asvxi for X E Hye initialize a base-learner with As; for a E Hexp. initialize a base-learner with Aexp.
2: for I. 1 to 7 do
3: Obtain p: from meta-algorithm, Xt,; from each base-learner [N];
4: Submit x EiE[N] 1,,i
5:
Receive V [x(e) and send it to each base-learner for update;
6: For strongly convex and exp-concave functions learners: set Tr,i (x,)), xt,)):
7: For convex functions learner: set Tt,1 ft (xx) - fx(x))));
8: Send to the meta-algorithm:
9: Send M1+1,1 = f((x)) f and m4+1, = 0, E [2 to the meta-algorithm.
10: end for
so Cmass X
C
-o log" Br + Br log BT
Br log Br
X
where we use Gmxx to denote the maximum Lipschitz constant on the optimization trajectory, treat log log as constants, and Br = ( D). In the fourth line, we again utilize the mean value theorem. The fifth line follows from Lemma 7, which ensures that:
(V.,)( - xt...)l | max (xx,))xxx,..;;,, xt. (V
thus, our result depends on the Lipschitz constant on the optimization trajectory. In the last step, apply the AM-GM inequality. The above statements show that the meta-regret is bounded by constants. With the base-regret guarantee, the proof for strongly convex functions is complete. O
C.5 Simple Universal Algorithm under Global Smoothness
As byproduct, our techniques can be used to design a simpler two-layer universal algorithm that achieves the optimal gradient-variation variation regret bounds for convex, strongly convex, and exp-concave functions simultancously, thereby improving upon the results of Yan al. [2023]. The crux involves leveraging the siriiion-vviiaiiiotooorrrre varriitttaaiitionn technique for convex functions, and follow- ing the strategy of Zhang et al. [2022a] to demonstrate that the meta-regret is bounded by constants for strongly convex and exp-concave functions, at a cost of (log 7)) times function value queries per round. Given the global smoothness constant and the Lipschitz constant, algorithm does not need to be prsschizz-adaptiie thus suitable for more general optimism settings.
In Algorithm 3, we present this idea. In contrast to Algorithm 2, which is designed under the generalized smoothness, this algorithm in addition can guarantee gradient- gradient-variation bound for exp- concave functions. In below, we present the theoretical guarantees for Algorithm 3.
Corollary 3. Under Assumption 2, and assuming the loss functions are L-smooth and G-Lipschitz, set N 2 logg T + The curvature coefficient pools defined as Hye Hep {2--1 1-2-1/TT
i E [[N - 1)/2]}. By selecting suitable base-algorithmg for X, a E [1/T, 11. Algorithm 3 ensures the following results simultaneously:
O
Vr (log log T)),
(convex),
log Vi + G log log )
REGT
(A-strongly convex),
log Vr + log log
(a-exp-concave))
Proof. When assuming the Lipschitz constant G, optimistic Adapt-ML-Prod (Wei et al., 2016] can ensure the meta-regret bounded by Ø(vy Ei m2,)) log log 7), thus the dependence of logarithmic terms is improved compared to Theorem 4. The proofs for convex functions and strongly convex functions are nearly identical to the proofs for Theorem 4 in Appendix C.4; thus, we omit to-gradient-variiiii variation technique,
them here. We highlight the importance of the uunctionvvaiittioo bounding the meta-regret of order O( VT log T') without the cancellation- based analysis.
26

---

Next, we show that the meta-regret for a, exp-cca functions is bounded by constant. By the construction of the curvature pool Hesp- there exists base-learner with the input curvature at, satisfying that Ok,, I a4 I 20z,- Decompose the regret against this specific base-learner and by the definition of exp-concave functions, have:
META-REEH
Σ
(xt))))) -x,,,)
(Vi((x)), -x...)
(ris. me,s.) log (.o..)).ooooo
(Vf((x)) -x,,.)
2
= =o(1 (V)((x)) - x2,,,))2 log log T xx, 50
log log T
where the second-to-last line follows from the settings that Tr, (V)t(x;), Xx x Xe,..) O, and we apply the AM-GM inequality in the final step. Therefore, by choosing the base-algorithm that ensures the regret bound of O d log V7), we complete the proof for this theorem.
and m,,i,
D Omitted Details for Section 4
This section provides the omitted proofs for our two applications.
D.1 Proof of Corollary
Proof. We prove this theorem in black-box box manner, thanks to the graiient-variation bound we derive. By Theorem 4, for convex functions, Algorithm ensures:
REGT S <o
(1(
Σ
T
sup [ - (x)()) + Σ sup Hupp|VFF((() - -VF--(()11 xEX
XEX
where we decompose
f(()) f 113 follows:
- O (VF(x()))VV(((11 [|V |
- (z)
(26)
Finally, by taking expectation both sides and leveraging the concavity of the square root, have:
T
E[REGT] S 50(
Σ
E
sup V{(x)) (x(())
Σ
sup x
V
-
xEX
which is in order of 0 OVVE Vo+).
For strongly convex functions, shown in Eq. (13) in the proof of Theorem 2, the multiplicative factor Gmax can be replaced by more refined factor max | fxx,) fi- (x:)l22.. Then
Algorithm can ensure the following bound for strongly convex functions:
REGT s 50 max VVx())) - V (x log Σ xEX
( )
(E(T]
By applying a similar argument as in Eq. (26) to decompose the gradient variation, taking the expec- tation on both sides, and leveraging the concavity of the logarithm, we conclude the proof. Li
D.2 Proof of Corollary 2
Proof. The step sizes for optimistic OMD in (10) is π). min(D, min,e(() 4F, (2, )1l)
By the convexity and the concavity for the objective function f(- :), for any = (x,y) E Z, we can
linearize the gap for e-approximate solution as f(xr,y) f(x Fr) - 4 (F Zi z).
27

---

Following the proof of Lemma 2, we can demonstrate that optimistic OMD in (10) ensures:
E (F(z)), z) - o |
2|z 2
1 7/
Σ To [lll F(
Σ t=1
1ze 2cl12
1/
The first term on the right-hand side is in the order of O( by the step size configura- tion, where Lmax denotes the maximum smoothness constant the optimization trajectory. By the t-smoothness in Definition 2, the second term can be bounded as Flz,) 1211 which can be further cancelled by the negative terms. There- fore, Σ (F(2:), 2z - z} bounded by a constant, thus, the convergence rate to an E-approximate solution is (1/TT), implying a fast convergence rate.
F(2,) I
E Supporting Lemmas
E.1 Lemmas for Optimistic OMD
We first present the generic lemma for optimistic OMD with dynamic regret [Zhao et al., 2024], which encompasses the standard regret by setting i ur x, arg min Σ ft (x). Lemma 3 (Theorem of Zhao et al. [2024]). Optimistic OMD specialized at Eq. (3) satisfies
V V((x)) X u,) Vf((x)) Mr, - -84+1) Σ (De, (u:; (x) Dw, (u,, 8(+11)
T Σ (Re,,, + Dos (x1, x1))
where UI....;uT UT X are arbitrary comparators in the feasible domain.
The next lemma, known as the stability lemma, establishes an upper bound on the proximity between successive decisions in terms of the gradient utilized for updates.
Lemma 4 (Proposition 7 of Chiang et al. [2012]). Consider the following two updates: (i) x = arg minxex (gg, x) + De (x.c)) c)}, and (ii) x' = arg minxex ((g' x) + (x, When
the regularizer 1o + R X-strongly convex function with respect norm |1-I], we have
x|Ix - x < g - g'll..
E.2 Self- Confionnne Tuning Lemmas
In this part, provide some useful lemmas when analyzing the self-confident tuning strategy. Lemma 5 (Extension of Lemma 14 Gaillard et al. [2014]). Lef on 0 and at E [0, B] be real numbers for all t [T] and let f +00) + [0, +00) be nonincreasing function. Then
Et aef (E--) as) S ((a) + Liizo f(u)du.
Lemma 6 (Lemma 3.5 of Auer et al. [2002]). Let a1...., ar and 8 be non-negative real numbers.
Then El= Vo+E.
61
2 6 ΣT 4: - V8).
E.3 Technical Lemma
Lemma 7. Let f: + R be a convex, twice differentiable function. Then for any x,y E in
and X E [0, 1J. we have that:
[V (1 A)y), - 8)1 max X///:///////////////////////>>//
Proof. Define a function that d(t) = f(tx + (1 t)y). For this univariate convex function.
have dt) (V + (1 t)y). y). By the convexity of o(t), there is (0((t) <
max o (1)), /0' (0))), concluding the proof.
28

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract, we present the contributions sequentially through ordinal words and we discuss the contributions further in the introduction part.
Guidelines:
The answer NA means that the abstract and introduction not include the claims made in 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. No or NA answer 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.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: One limitation of our work is the requirement for multiple gradient queries. Another limitation is that we cannot obtain the gradient-variation results exp-concave functions due the technical reasons.
Guidelines:
The answer NA means that the paper has no 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 a separate "LLimitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity 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?
29

---

Answer: [Yes]
Justification: The assumptions are provided in Section The main theoretical results are provided from Section 2 to Section 4. All proofs can be found in the Appendix and, specifically from Appendix B to Appendix D, which contain the proofs for the main results.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
While NeurIPS 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 new algorithm, the paper should make it clear how to 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 is a new model (e.g., large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (c.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 thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access the model is limited in some way (e.g., to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
30

---

Question: 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?
Answer: [NA]
Justification: This paper does not include experiments, and no data or code will be pro- vided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please
the NeurIPS code and data submission guidelines for more details.
(https://nips
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nips
SeniidesCoodeSublii ssioollicyy) for more details. The authors should provide instructions 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: 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 to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
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
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer:
[NA]
Justification: This paper does not include experiments.
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, at 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 run with given experimental conditions).
31

---

The method for calculating the error bars should be explained (closed form formula, call library function, bootstrap. etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error the mean.
It is OK to report 1-sigma error bars, but one should state The authors should prefer- ably report 2-sigma enror 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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: [NA]
Justification:
This paper does not include experiments.
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 well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn'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 attps://neurife htte///plc//ttcccuuttieieeeoeeee ines?
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances 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 in 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 paper only focuses on online learning theory, and we are not aware of any potential societal impacts.
Guidelines:
The answer NA means that there is 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.
32

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there 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 tech- nology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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 paper does not include experiments, and there risks for misuse of data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to 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 deseribe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
This paper does not include experiments, and we do not use existing assets.
Guidelines:
The answer NA means that the paper does not use 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 of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi trriihhooeee com datasets 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.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Question:
Answer: [NA]
Justification:
This paper does not include experiments, and we do not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, lim- itations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper focuses on online learning theory and does not involve crowd- sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
This paper focuses on online learning theory and does not involve crowd- sourcing nor research with human subjects.
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. 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 NeurIPS 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.
35


Reviews:
[{"review_id": "JcLwk8tx7W", "reviewer": "Reviewer_VaQR", "summary": "This paper studies adaptive online learning under the generalized smoothness assumption. The authors proposed optimistic OMD based algorithms that achieves the first gradient variation bounds under this general setting. Under this assumption, they also provide uninveral algorithms which can adapt to different function types, and also algorithms with dynamic regret.", "questions": "Please see weakness", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is the first to study adaptive online learning under generalized smoothness, which is a much milder condition compared to the standard global smoothness that considered by previous work. \n\n\n2. In section 2, the authors provide optimistic OMD based algorithms with adaptive step size, and prove that it enjoys O(sqrt{V_T}) and O(log V_T/\\lambda) regret bounds for convex and strongly convex functions. To my knowledge, these are the first adaptive bounds under the generalized smoothness condition, which is a novel and interesting contribution. \n\n3. The authors also provide a universal algorithm for achieving gradient variation bounds under the generalized smoothness setting, which can adapt to convex and strongly convex functions, without knowing the type of loss functions in advance. Existing universal methods cannot be directly applied due to the unknown Lipschitzness parameters, and the authors address it by using novel techniques such as function-variation-to-gradient-variation conversion.\n\n4. The authors also showed that the proposed methods can be applied to get adaptive bounds in stochastic extended adversarial online learning and the fast-rate games under more general assumptions.", "weaknesses": "1. The base learner proposed in Section 2 needs to know the Smooth constant of the previous observed loss functions (at round t-1), which might be difficult to compute if the loss functions are complicated.\n\n2. The proposed universal algorithm requires to query the gradient O(\\log T) times per iterations, while most of the existing universal methods only need to query the gradient once.\n\n3. Previous universal algorithms with gradient variation bound can deal with exp-concave functions, while the proposed algorithm can only deal with convex and strongly convex functions.\n\n4. Previous work can also achieve small-loss bound in this setting. It would be great to understand if small-loss bound is achievable under this more general assumption. \n\n\nMinor comments:\n\nLine 56: sqrt{V}_T: T should be inside the square root;\n\nLine 140: “a finte bound but unknown L” is not assumed in this paper\n\nLine 197: it is more common to use equality for the big-O notation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and appreciation of our work! We will respond to your comments below.\n\n---\n\n**Q1**. \"The base learner proposed in Section 2 needs to know the Smooth constant of the previous observed loss functions (at round $t-1$), which might be difficult to compute if the loss functions are complicated.\" \"The proposed universal algorithm requires to query the gradient $O(\\log T)$ times per iterations, while most of the existing universal methods only need to query the gradient once.\"\n\n**A1**. Thanks for the comments. We will respond to these two comments together since the query for gradients and smoothness are coupled.\n\n- **Computation for smoothness**: The computation of smooth constants can be difficult for generalized smoothness. Given that we work on a weaker notion of smoothness in the online setting, it is essential to query the smoothness at each time step to adapt to the optimization trajectory. When specifying $(L_0, L_1)$-smoothness, a representative instance of generalized smoothness often observed in neural network optimization [1, 2], the smoothness constants can be efficiently estimated by the definition $L_t = L_0+L_1*\\\\| \\nabla f_t(x_t)\\\\|$.\n- **Multiple queries for gradients**: Existing universal methods are developed under global smoothness, where the gradients and smoothness of the combined decision $x_t = \\sum_{i=1}^N p_{t,i}x_{t,i}$ can be shared to tune the base-learners. Under the generalized smoothness condition, the smoothness is highly correlated to the optimization trajectory, and its estimation is guaranteed only within a local region. The smoothness at point $x_t$ might be improper to tune the base-learners, which in turn affects the submitted decision $x_{t+1}$, complicating the tuning process. Therefore, at this stage, we have to decouple the analysis from the meta and base levels and query the gradients, which are related to smoothness by function $\\ell_t$, multiple times to analyze the base learners separately. Reducing the number of gradient queries is definitely an important future direction. Thanks for pointing this out!\n\n---\n\n**Q2**. \"Previous universal algorithms with gradient variation bound can deal with exp-concave functions, while the proposed algorithm can only deal with convex and strongly convex functions.\"\n\n**A2**. Thanks for the question. As discussed in Remark 1 and Remark 2 of the paper, dealing with exp-concave functions is particularly challenging for gradient-variation online learning under generalized smoothness. Specifically, at the base level, the challenge arises because the online Newton step (ONS) algorithm seems unable to benefit from arbitrary optimism. This limitation hinders our ability to tune ONS locally by setting the optimism as $M_t = \\nabla f_{t-1}(\\hat{x}_t)$. Learning with arbitrary optimism for exp-concave functions remains open. At the meta level, the challenge arises when accommodating heterogeneous inputs, which necessitates a specific optimism design in the meta-algorithm. This optimism design cannot leverage the negative terms introduced by the \"exp-concave curvature\".\n\n---\n\n**Q3**. \"Previous work can also achieve small-loss bound in this setting. It would be great to understand if small-loss bound is achievable under this more general assumption.\"\n\n**A3**. Thank you for the comment! Yes, the small-loss bound can be achieved in this setting. Specifically, taking convex functions as an example, we can employ SOAL [3] as the base-algorithm and Algorithm 1 in the paper with $m_{t,i} = \\langle \\nabla f_t(x_t), x_t - x_{t,i}\\rangle$  as the meta-algorithm. These combinations can guarantee a regret bound of $O(\\sqrt{\\sum_{t=1}^T \\\\|\\nabla f_t(x_t)\\\\|^2})$ for convex functions. The generalized smooth functions also enjoy the self-bounding property that $\\\\|\\nabla f_t(x_t)\\\\|^2 \\lesssim f_t(x_t) - \\min_{x} f_t(x)$ [4, Lemma 3.5], which can further convert the obtained regret bound to the small-loss bound with standard arguments. It remains an interesting question whether it is possible to obtain both the small-loss and gradient-variation results simultaneously with one algorithm. In the future, we will investigate this problem.\n\n---\n\n**Q4**. minor comments regarding typos and formatting issues \n\n**A4**. Thanks for your careful review and helpful suggestions. We will revise and improve our paper presentation accordingly.\n\n---\n\n**References:**\n\n[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity, ICLR'20.\n\n[2] Robustness to unbounded smoothness of generalized signSGD, NeurIPS'22.\n\n[3] Scale-free online learning, TCS'18.\n\n[4] Convex and non-convex optimization under generalized smoothness, NeurIPS'23.", "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": "svI0BesZqO", "reviewer": "Reviewer_ian3", "summary": "The paper aims to provide gradient-variation regret bound when only a generalized smoothness condition holds. It considers the optimistic mirror descent algorithm. It further designed a meta-algorithm, which can be Lipscthiz adaptive. Lastly, it considers adaptive regret and dynamic regret.", "questions": "1. The paper addresses the generalized smoothness condition and frequently mentions the potential for unbounded gradients and smoothness. However, Assumption 2 posits a bounded domain. Does this imply that the gradients and smoothness are also bounded? In reference [7], such boundedness does not appear to be a requirement. \n\n2. On page 5, line 203, the paper asserts that the complexity \\(O(D\\sqrt{V_T} + LD^2)\\) aligns with the optimal constant dependency. It would be helpful if the authors could specify where exactly in reference [7] this lower bound is discussed.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) Compared with existing literature, the work relaxed the smoothness assumption.\n\n(2) The meta-algorithm to achieve universality seems novel to me.", "weaknesses": "The clarity and effectiveness of the paper could be improved by condensing the extensive paragraphs that discuss \"challenges.\" Instead, it would be beneficial to expand the remarks on how the findings compare with existing results following the theorems. This would provide readers with a clearer understanding of the paper's contributions to the current body of knowledge.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments.  We will revise our paper to highlight the contributions according to your suggestions. Below, we will address your questions.\n\n---\n\n**Q1**. \"However, Assumption 2 posits a bounded domain. Does this imply that the gradients and smoothness are also bounded? In reference [7], such boundedness does not appear to be a requirement.\"\n\n**A1**. Thanks for the question. We make the following explanations.\n\n- **Bounded domain assumption**: The bounded domain assumption does *not* imply the boundedness of gradients and smoothness. For example, considering the online portfolio selection (OPS) problem [1], where the decision $x_t \\in \\Delta_d$ and the loss function is $f_t(x) = -\\ln \\langle x , r_t\\rangle$ with $r_t \\in (0, 1]^d$. In this case, the feasible domain is bounded while the Lipschitzness and smoothness could be arbitrarily large. In fact, in the online learning community, research under the assumption of bounded domain and unbounded Lipschitzness [2], as well as research under the assumption of unbounded domain and bounded Lipschitzness [3], are both studied and usually conducted parallelly.\n- **Requirement on the boundedness**: We clarify that the proposed algorithms in our paper are Lipschitz-adaptive, meaning they do *not* require the upper bounds of Lipschitzness as an algorithmic input, and they can handle unbounded (but finite) Lipschitzness. Regarding reference [7], we believe their method is not Lipschitz-adaptive. In fact, in Section 6 of [7], when introducing the regularizer $\\mathcal{R}_t(x)$, an upper bound of Lipschitzness is required to tune the algorithm.\n\n---\n\n**Q2**. \"On page 5, line 203, the paper asserts that the complexity $(O(D\\sqrt{V_T} + LD^2))$ aligns with the optimal constant dependency. It would be helpful if the authors could specify where exactly in reference [7] this lower bound is discussed.\"\n\n**A2**. Sorry for this misleading expression.  We wish to clarify that our result matches the existing upper bound designed for global smoothness [4, 5] of order $O(D\\sqrt{V_T} + LD^2)$, in which our result matches the dependence on all terms including $V_T$ and the constants $D$ and $L$. From a lower bound side, it's known that the gradient-variation lower bound for convex functions is $\\Omega(\\sqrt{V_T})$ [see discussion above Lemma 9 of [7]), but there remains a lack of lower bounds for $D$ and $L$. We will revise the paper to provide more precise expressions. Thank you!\n\n---\n\n**Q3**. \"The clarity and effectiveness of the paper could be improved by condensing the extensive paragraphs that discuss ‘challenges’ ...This would provide readers with a clearer understanding of the paper's contributions to the current body of knowledge.\"\n\n**A3**. We appreciate your suggestion! In the revised version, we will condense the content and highlight the paper’s contributions. Thank you for highlighting this point for improvement.\n\n---\n\n**References:**\n\n[1] Universal portfolios, Mathematical Finance 1991. \n\n[2] Lipschitz adaptivity with multiple learning rates in online learning, COLT 2019.\n\n[3] Black-box reductions for parameter-free online learning in Banach spaces, COLT 2018.\n\n[4] Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization, ICML 2023.\n\n[5] Universal online Learning with gradient variations: A multi-layer online ensemble approach, NeurIPS 2023.\n\n[Paper ref 7] (referred to in the paper) Online optimization with gradual variations, COLT 2012.", "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": "tZz0bJ5lhT", "reviewer": "Reviewer_NEvk", "summary": "Problem: The paper studies the OCO problem under the generalized smoothness assumption, i.e. at each time $t$, $f_{t}$ satisfies $\\|| \\nabla ^ {2} f_{t} (x) \\|| \\le \\ell_{t}(\\|| \\nabla f_{t}(x) \\||)$ for all $x \\in \\mathcal{X}$, where $\\ell_{t}$ is a positive non-decreasing function. In addition to the information model in OCO, the algorithm can query $\\ell_{t}$ at any local point $x \\in \\mathcal{X}$. This condition subsumes global smoothness, i.e. $\\ell \\le L$ is upper bounded globally, and $(L_{0},L_{1})$ smoothness, i.e. $\\ell(x) = L_0 + L_1 x$; which have been studied in the prior works. The authors obtain gradient-based variation bounds for several settings of interest (see contributions below).\n\nContributions: \n1) First, the authors extend the classic optimistic OMD algorithm to handle generalized smoothness and obtain an optimal $\\mathcal{O}(\\log V_{T})$ rate for strongly convex and $\\mathcal{O}(\\sqrt{V_{T}})$ static regret for convex functions (ref. Theorem 1, 2). However, these rates are first derived assuming that the algorithm knows the curvature of the $f_{t}$'s, i.e. whether all the $f_{t}$'s are convex or strongly convex.\n\n2) To circumvent the curvature information, the authors devise an algorithm that is adaptive to the curvature of the functions $f_{t}$'s (referred to as universal online learning -- the goal is to obtain an algorithm with simultaneous guarantees for convex and strongly convex functions). The proposed algorithm obtains the optimal $\\mathcal{O}(\\sqrt{V_T}), \\mathcal{O}(\\log V_T)$ static regret bounds for convex, strongly convex functions respectively (ref. Theorem 4).\n\n3) Finally, the authors consider stronger regret measures, i.e. interval regret and dynamic regret (referred to as non-stationary online learning), and propose an algorithm with the optimal gradient variation-based regret guarantees (ref. Theorem 5, 6).", "questions": "1) The discussion towards the end of page 3 is confusing to me. The authors mention that assuming the Lipschitzness of $f_{t}$ is not reasonable since the bound on $\\|| \\nabla ^ {2} f(x) \\||$ can be obtained from knowing $\\ell$ directly, and the function is globally smooth. However, the bounds presented in the Theorems are a function of the Lipschitzness parameters. I would appreciate clarification from the authors.\n\n2) In the Equation after Line 384, $\\xi_{t, i}$ is not necessarily same for $f_t$ and $f_{t - 1}$ since the Mean Value Theorem only guarantees the existence of a $\\xi$. With $\\xi_t$ and $\\xi_{t-1}$ being possibly different, I don't think the next inequality follows immediately. Is that a typo or am I missing something?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is solid and shows that gradient variation-based bounds can be derived under a more general smoothness assumption. Prior works focused on global smoothness, or $(L_{0}, L_{1})$ smoothness, and did not consider some or the other regret metrics as considered in the paper, e.g. the authors mention that an adaptive regret guarantee was not obtained even in the context of global smoothness.  \n\nWhile this might seem doable, the authors very well mention the key challenges in obtaining the desired algorithms, e.g. for contribution (2) above, section 3.2 does a great job of highlighting the key challenges. I liked this section and the authors spent considerable effort explaining why existing meta algorithms, e.g. McMwC-Master algorithm (Chen et al.) do not directly work since they cannot handle heterogeneous inputs. \n\nThe function-to-gradient variation technique is simple and seems pretty useful since it allows us to decouple the meta-algorithm and the base learners and explicitly aim toward obtaining a meta-algorithm with the desired guarantee. It helps avoid the seemingly messier cancellation-based tricks as done by Yan et al.", "weaknesses": "1) Section 4 is presented in a rush. Like section 3.1, it would be quite beneficial to have some more discussion on the algorithm and potential challenges in deriving non-stationary regret guarantees. The authors claim that their proposed algorithm is the first to obtain gradient variation-based non-stationary regret guarantees under the generalized smoothness assumption, whereas prior works did not obtain similar guarantees under the global smoothness assumption. The authors should have at least backed this with the potential difficulties faced by existing approaches. I recommend that the authors cut down some earlier discussions, such as the discussion about exp-concave functions, which in my opinion is not very relevant, given that the entire paper is about convex and strongly convex functions.\n\n2) While the paper shows interesting results, I feel the key ideas are borrowed from existing works. While this is fine, in some places the authors failed to mention the potential technical challenges in the analysis. This is the most applicable to section 3. The authors mention that the proposed algorithm can be analyzed similarly to the prod-style algorithms. Are there technical difficulties in directly incorporating the analysis of prod-style algorithms into Algorithm 1? \n\nSome minor typos that I found:\n\n1) Line 38: \"stochatsic -> stochastic\"\n2) Lemma 1: Remove the $\\ell_t$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and very constructive comments. We will revise the paper according to your suggestions. In the following, we address each of your technical questions.\n\n---\n\n**Q1**. \"The discussion towards the end of page 3 is confusing to me....the bounds presented in the Theorems are a function of the Lipschitzness parameters.\" \n\n**A1.** Thanks for the question. We make the following clarifications.\n\n- First, we do *not* assume the prior knowledge of the Lipschitz constant as an algorithmic input. Otherwise, with such foreknowledge, we could directly compute a global smoothness constant, reducing the problem to OCO with global smoothness.\n- Second, we do assume *finite* Lipschitz constants during the learning process, even though this finite upper bound is *unknown* to the algorithm. Without this assumption, the regret bounds would become vacuous. The Lipschitz constants presented in our theorems are evaluated on the fly, which demonstrates the Lipschitz-adaptivity of our algorithms when exploiting generalized smoothness. \n- We emphasize that the above assumption is fundamental and shared in OCO relating to the unbounded quantities; also refer to prior discussions [1] (Page 2, right column) \"Importantly, note that in all of these prior works there is an implicit assumption that there exists a uniform bound such that $ G ≥ \\\\|\\nabla \\ell_t(w)\\\\|$ for any $w\\in \\mathcal{W}$ — even if it is not known in advance. Otherwise, the terms $G_T = \\max_t \\\\|g_t\\\\|$ can easily make any of the aforementioned regret guarantees vacuous\". \n\nWe will improve the presentation to avoid any confusion on this point in the revised version.\n\n---\n\n**Q2**. \"With $\\xi_t$ and $\\xi_{t-1}$ being possibly different, I don't think the next inequality follows immediately. Is that a typo or am I missing something?\"\n\n**A2**. Sorry for this confusion. The inequality is indeed correct, and we provide derivations for clarity. One can introduce a function $F_t(x) = f_t(x) - f_{t-1}(x)$, then the \"function-variation quantity\" is essentially $F_t(x_{t,i}) - F_t(x_{\\text{ref}})$. Applying the Mean Value Theorem to $F_t$ yields\n\n$$F_t(x_{t,i}) - F_t(x_{\\text{ref}}) = \\langle \\nabla F_t(\\xi_{t,i}), x_{t,i} - x_{\\text{ref}} \\rangle = \\langle \\nabla f_t(\\xi_{t,i}) - \\nabla f_{t-1}(\\xi_{t,i}), x_{t,i} - x_{\\text{ref}} \\rangle,$$\n\nwhere $\\xi_{t,i}$ is a point guaranteed to lie between $x_t$ and $x_{\\text{ref}}$. \n\nWe will make it clear in the next version. Thanks!\n\n----\n\n**Q3**.  \"Section 4 is presented in a rush......prior works did not obtain similar guarantees (gradient variation-based non-stationary regret) under the global smoothness assumption.....The authors should have at least backed this with the potential difficulties faced by existing approaches....I recommend that the authors cut down some earlier discussions....\"\n\n**A3**. Thanks for the suggestions! We will reserve space to incorporate additional details for Section 4 (especially given that one additional page is allowed in the final version). \n\nWe briefly highlight difficulties faced by existing approaches in achieving gradient-variation adaptive regret. To the best of our understanding, previous efforts mainly focus on \"cancellation-based analysis\" to attain gradient variations. However, minimizing adaptive regret requires the meta-algorithm to accommodate the sleeping-expert mechanism, which significantly complicated the cancellation-based arguments due to the impact of varying numbers of active base-learners on negative terms. In contrast, our approach leverages the function-variation-to-gradient-variation conversion and thus can avoid this issue.\n\n----\n\n**Q4**. \"Are there technical difficulties in directly incorporating the analysis of prod-style algorithms into Algorithm 1?\"\n\n**A4**. There are two key algorithmic modifications in Algorithm 1 compared to standard Prod-style algorithms, which have introduced technical difficulties.\n\n- **Clipping operation**: Due to the Lipschitz-adaptive requirement of meta-algorithm, we introduce a clipping operation [2] into the prod-style algorithm with optimism. This incorporation requires to *carefully design the optimism*. We demonstrate that the condition $\\langle p_t, m_t \\rangle \\leq 0$ is essential for achieving regret bounds scaling with  $\\sum_{t=1}^T (r_{t,i} - m_{t,i})^2$, which further leads to a new optimism design in the universal method.\n- **Learning rate setting**: We introduce a novel non-increasing learning rate setting, as opposed to prior Lipschitz-adaptive algorithms that use a fixed learning rate with restarts. This simplified and more practical learning rate setting requires sophisticated analysis. Specifically, the addition of $B_t^2$ in the denominator of learning rates is *novel* to prod-style algorithms. It not only *ensures* the key condition of $\\eta_{t,i} |\\bar{r}_{t,i} - m_{t,i}| \\leq 1/2$, but also *removes* the threshold on learning rates commonly used in previous prod-style algorithms [3, 4], which guarantees that $\\eta_{t,i}/\\eta_{t+1,i}$ can still be well controlled (as analyzed at Line 899 in Appendix D.5).\n\nTo summarize, extending prod-style algorithms with optimism to be Lipschitz-adaptive requires novel ingredients. We will add discussions to highlight those potential technical challenges.\n\n---\n\nWe will revise the paper to enhance our presentation's clarity and avoid confusion. Please consider updating the score if our clarifications have properly addressed your concern. Thank you!\n\n---\n\n**References:**\n\n[1] Unconstrained online learning with unbounded losses, ICML'23.\n\n[2] Artificial constraints and hints for unbounded online learning, COLT'19.\n\n[3] A second-order bound with excess losses, COLT'14.\n\n[4] Tracking the best expert in non-stationary stochastic environments, NIPS'16.", "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": "XDpLDc6ToZ", "reviewer": "Reviewer_YPdL", "summary": "This paper contributes gradient-variation extensions of several online learning guarantees to\na generalized smoothness setting. Under a more general smoothness assumption,\nthe paper first provides an algorithm which achieves a $O(\\sqrt{V_T})$\ngurantee, where $V_T=\\sum_{t} \\sup_{x}\\\\|\\nabla f_t(x)-\\nabla f_{t-1}(x)\\\\|^2$, as well as a $O(\\log{V_T})$ guarantee for\nstrongly-convex functions.\nThe result is then extended to a universal guarantee, which holds\nwithout knowledge of whether the losses are strongly convex or just convex.\nThe approach is also extended to provide an analogous strongly-adaptive guarantee and a $O(\\sqrt{V_TP_T})$ dynamic regret guarantee.", "questions": "- \"However, to ensure the theoretical results are valid, we assume that there exist finite but unknown upper bounds G and L for the Lipschitzness and smoothness following the discussion in Jacobsen and Cutkosky [35].\"\n  - What discussion is being referred to here specifically?", "limitations": "- The limitation in terms of a potential exp-concave result is stated explicitly in Section 2.3\n- The assumption that $\\min_x f_t(x)$ is required is pointed out explicitly. Although it it's significance\n  is a bit downplayed.\n- Multiple-query gradient access is also pointed out in the conclusion", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The generalized smoothness assumption is nice. The paper reads well and the technical development easy to follow. Results seem novel.", "weaknesses": "The assumption that the learner has prior knowledge of and can query the smoothness function arbitrarily seems very strong\n\nThe method requires multiple-query gradient access\n\nThe approach requires prior knowledge of $\\min_x f_t(x)$, which makes the problem quite a bit easier. One of the difficult things\nthat arises in these non-globally-bounded settings is that the learner doesn't have a proper frame-of-reference for how large\nlosses and gradients really are; giving the learner access to $\\min_x f_t(x)$ provides a very strong version of such a frame-of-reference", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! In the following, we will answer your question and respond to your concerns regarding the assumptions.\n\n---\n\n**Q1**. \"However, to ensure the theoretical results are valid, we assume that there exist finite but unknown upper bounds G and L for the Lipschitzness and smoothness following the discussion in Jacobsen and Cutkosky [35].\" What discussion is being referred to here specifically?\"\n\n**A1**. Thanks for the question. We refer to the discussion on the finiteness of the Lipschitz constant and the smoothness constant in the right column of page 2 in Jacobsen and Cutkosky [35], as restated below: \"Importantly, note that in all of these prior works there is an implicit assumption that there exists a uniform bound such that $ G \\geq \\\\|\\nabla \\ell_t(w)\\\\|$ for any $w\\in \\mathcal{W}$ — even if it is not known in advance. Otherwise, the terms $G_T = \\max_t \\\\|g_t\\\\|$ can easily make any of the aforementioned regret guarantees vacuous.\"\n\n---\n\n**Q2**. \"The assumption that the learner has prior knowledge of and can query the smoothness function arbitrarily seems very strong.\" \"The method requires multiple-query gradient access.\"\n\n**A2**. Thanks for the comments. We will respond to these two comments together since, for generalized smoothness, querying gradients is directly related to estimating smoothness.\n\n- **Prior knowledge of the smoothness function**: For the general form of generalized smoothness, this query requirement is arguably strong. Technically, given the weaker notion of smoothness we are working with, obtaining certain *local* information is essential to properly adapt to the optimization trajectory. On the other hand, in the case of the commonly studied $(L_0, L_1)$-smoothness, which is one representative instance of generalized smoothness often observed in neural network optimization, this query becomes inexpensive. This is because we can directly calculate the local smoothness $L_t = L_0+L_1*\\\\| \\nabla f_t(x_t)\\\\|$ by definition provided that $L_0$ and $L_1$ are known (they are usually empirically estimated on the fly for NN optimization).\n- **Multiple-query gradient access**: When assuming the global smoothness, the information (gradients, smoothness) of the combined decision $x_t = \\sum_{i=1}^N p_{t,i}x_{t,i}$ can be shared to tune base-learners. Consequently, previous works have developed algorithms by thoroughly utilizing this shared information.  However, when considering the generalized smoothness, *the estimation of the smoothness is highly correlated to the optimization trajectory and is valid only within a local region*. Utilizing the gradient and smoothness at point $x_t$ leads to improper tuning of the base learners, which in turn affects the generation of the subsequent decision $x_{t+1}$, complicating the tuning process. Therefore, we have to decouple the design of meta and base levels, and require multiple-query gradient access to estimate the smoothness for each base-learner. Reducing the number of gradient queries is definitely an important future work. Thanks for pointing it out! \n---\n**Q3**. \"The approach requires prior knowledge of $\\min_x f_t(x)$, which makes the problem quite a bit easier.\"\n\n**A3**. Thanks for the comment. We need to clarify that we only require knowledge of $\\min_x f_t(x)$ when developing the universal method; it is not required for non-stationary online algorithms. Removing this assumption is important for future work, but currently, we have to work with it. Below, we provide explanations for the technical necessity and justifications. \n\n- **Technical reason for requiring this assumption**: The assumption for the $\\min_x f_t(x)$ arises from the heterogeneous inputs and the binary search operation in the meta-algorithm. To accommodate the heterogeneous inputs, we need to search $p_t$ such that $f_t(\\sum_{i=1}^N p_{t,i}x_{t,i})$ satisfies some properties. Here, we require the lower bound of $f_t(x)$ to facilitate the binary search operation. In contrast, when developing the adaptive regret minimization method, it is acceptable to search $p_t$ such that $\\sum_{i=1}^N p_{t,i} f_t(x_{t,i})$ satisfies the same properties. Notice that, in this case, the range of $\\sum_{i=1}^N p_{t,i} f_t(x_{t,i})$ is $[\\min_{i} f_t(x_{t,i}), \\max_{i} f_t(x_{t,i})]$ as $p_t$ is from simplex. \n- **Justification and support for this assumption**: As mentioned in the paper, in the typical Empirical Risk Minimization (ERM) setting, this lower bound certification is mild, as recent works in optimization suggest that $0$ can naturally serve as a lower bound for $f_t(x)$ [3, discussion below Theorem 1]. Other recent works in parameter-free stochastic optimization also necessitate a lower bound on function values, concretely, the learning rate tuning in Theorem 1 of [4] and the inputs in Algorithm 1 of [5].\n\nWe will consider how to remove this assumption, which is definitely an important yet challenging future work to address.\n\n---\n\n**References:**\n\n[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity, ICLR'20.\n\n[2] Robustness to unbounded smoothness of generalized signSGD, NeurIPS'22.\n\n[3] Revisiting the Polyak step size, arXiv'19.\n\n[4] How free is parameter-free stochastic optimization?, ICML'24.\n\n[5] Tuning-free stochastic optimization, ICML'24.\n\n[Paper ref 35] Unconstrained online learning with unbounded losses, ICML'23.", "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:

Meta-review: Typically, regret bounds  in terms of "gradient variation" $\|\nabla f_t(x) -\nabla f_{t-1}(x)\|$  require a smoothness condition. This work  extends this notion to a weaker smoothness condition that has recently been used for analysis of non-convex objectives in deep learning. 

Overall the reviewers have a positive opinion  of the  novelty and technical significance of this work, so it is recommended for acceptance.
Decision: Accept (poster)