Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
Authors: Yuheng Zhao
Yu-Hu Yan
Kfir Yehuda Levy
Peng Zhao
Venue: NeurIPS 2025 spotlight ()
Keywords: online learning
regret
acceleration
Primary area: optimization

Abstract: Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization in online learning. 
Interestingly, these two problems are actually closely connected --- accelerated optimization can be understood through the lens of gradient-variation online learning.
In this paper, we investigate online learning with *Hölder* functions, a general class encompassing both smooth and non-smooth (Lipschitz) functions, and explore its implications for offline optimization. 
For (strongly) convex online functions, we design the corresponding gradient-variation online learning algorithm whose regret smoothly interpolates between the optimal guarantees in smooth and non-smooth regimes. 
Notably, our algorithms do not require prior knowledge of the Hölder smoothness parameter, exhibiting strong adaptivity over existing methods.
Through online-to-batch conversion, this gradient-variation online adaptivity yields an optimal universal method for stochastic convex optimization under Hölder smoothness. 
However, achieving universality in offline strongly convex optimization is more challenging. 
We address this by integrating online adaptivity with a detection-based guess-and-check procedure, which, for the first time, yields a universal offline method that achieves accelerated convergence in the smooth regime while maintaining near-optimal convergence in the non-smooth one.

Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
Yuheng Zh Yu-Hu Yan Kfir Yehuda Levy?, Peng Zhao 1.2
National Key Laboratory for Novel Software Technology, Nanjing University, China School of Artificial Intelligence, Nanjing University, China Electrical and Computer Engineering, Technion, Haifa, Israel
Abstract
Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization online learning. Interestingly, these problems actually closely connected - accelerated optimization be understood through the lens of gradient-variation online learning. In this paper, investigate online learning with Hölder smooth functions, general class compassing both smooth and non-smooth (Lipschitz) functions, and explore its implications for offline optimization. For (strongly) convex online functions, we design the corresponding gradient-variation online learning algorithm whose regret smoothly interpolates between the optimal guarantees in smooth and non-smooth regimes. Notably, our algorithms do not require prior knowledge of the Hölder smoothness parameter, exhibiting strong adaptivity over existing methods. Through online-to-batch conversion, this gradient- gradient-variation online adaptivity yields an opti- mal universal method for stochastic convex optimization under Hölder smoothness. However, achieving universality in offline strongly convex optimization is more challenging. We address this by integrating online adaptivity with detection- based guess-and-check procedure, which, for the first time, yields a universal offline method that achieves accelerated convergence in the smooth regime while maintaining near-optimal convergence in the non-smooth one.
1 Introduction
First-order optimization methods based on (stochastic) gradients are widely used in machine learning due their efficiency and simplicity [Nesterov, 2018; Duchi et al., 2011: Kingma and Ba, 2015]. It is well-known that the curvature of the objective function strongly influences the difficulty of optimization. In particular, the optimal convergence rates differ significantly between smooth and non-smooth objectives. For convex functions, the optimal rate in the non-smooth case is O(1/ ((I/VT), achievable by standard gradient descent (GD), where T denotes the total number of gradient queries. In contrast, for smooth functions, GD only attains an O(1/T) rate, which exhibits large gap with the accelerated rate (1/TT² attained by the Nesterov's 's accelerated gradient (NAG) method [Nesterov, 2018]. Similar acceleration phenomena also arise in the strongly convex setting.
The significant performance gap between smooth and non-smooth optimization has motivated the study of universality in optimization [Nesterov, 2015]: an ideal universal method should adapt to both unknown smooth and non- non-smooth cases, achieving optimal convergence both regimes. Several studies have explored adapting more challenging setting known Hölder smoothness [Devolder et al., 2014; Nesterov, 2015], which continuously interpolates between smooth and non-smooth
*Correspondence: Peng Zhao <zhaop Maahop@llnnie lamda.nju.edu.cn>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Summary and comparison of the convergence rates of existing universal methods and ours for offline (strongly) convex optimization. "Weak/strong universality" notations defined in Definition 1. Let - L/A. a denotes the variance the stochastic setting. The rate marked with i accelerele in smooth functions.
Setting
Convergence Rate
Universality
O(fa + (Tr) for L-smooth; O (T) for Lipschitz (Kavis et al., 2019]
Weak
Convex
O Trettioz + vT) for (Lu, Hööder smooth [Rodomanov et al., 2024]
Strong
Pi vT
for (Lv Hölder smooth [Theorem 2]
Strong
X-Strongly Convex
O ((exp(-2) -2 4) for L-smooth und Lipschitz; Ō (xze ) for Lipschitz [Levy, 2017]
Weak'
((exp(
T )) for Lsmooth and Lipschitz; O X7 for Lipschitz [Theorem 4]
Weak
SyR
functions, Formally, a function é Rd + R is (Lu, ) Höller smooth with respect to the forno where Ly > 0 and v E [o, 1]. if
[[V((x) - Ve(y) S - Vx,y E R.
It can be observed that Ly-smoothness corresponds to (Ie, ---ldde smoothness, while G-Lipschitz continuity is (2G, O)-Hölder smoothness. For convex and (Iv, v--Hölder smooth functions, the optimal convergence rate is (L/TT(++3/)22) and has been achieved by several recent methods [Nes- terov, 2015; Li and Lan, 2025; Rodomanov et al., 2024]. However, progress in the strongly convex setting remains limited, even adapting only between the smooth and non-smooth cases is still un- resolved. Levy [2017] attained coneecceeeddedd rate in the smooth case and a suboptimal rate in the non-smooth case. It remains open on how to achieve universality in the strongly convex setting, particularly in obtaining an accelerated rate in the smooth regime.
Online-to-Bated Conversion. An important perspective for designing optimization algorithms is et al., 2004], which reformulates an offline
the Online-to-Bi to-bachh Conversion framework optimization problem as a regret minimization task addressed by online learning algorithms. The key advantage typically lies in the simplicity of the converted algorithm. More importantly, it allows one to leverage the rich adaptivity results developed in online learning to enhance optimization performance. In online learning, the goal is to minimize the regref over a sequence of 7 online functions, denoted by (O2B) conversion implies
REGT [Hazan, 2016]. For convex functions, the standard Online-to-Batee that the convergence rate of the averaged iterate is REGT /T. Consequently, in the non-smooth case, combining this conversion with an online algorithm achieving an optimal ((VT) regret directly yields the optimal convergence rate for offline optimization of order O(1vVT)
In offline smooth optimization, achieving optimal convergence requires more refined conversion techniques and adaptive online algorithms [Levy, 2017; Cutkosky, 2019]. Specifically, attaining the optimal (1/T22 rate for smooth functions relies on an O2B conversion with stabilized gradient evaluations [Cutkosky, 2019] and an online learning algorithm equipped with gradient-variation adaptivity [Chiang et al., 2012; Zhao et al., 2020]. Notably, Kavis et al. [2019] achieved optimal rates in both smooth and non-smooth cases without requiring prior knowledge of smoothness, thereby attaining universality. concise technical discussion can be found in the lecture note [Zhao, 2025].
However, a gap persists in online-to-oflline methods under general Hölder smoothness settings. Furthermore, for strongly convex functions, achieving universality remains far from complete, even when focusing solely on smooth and non-smooth cases. These challenges motivate our study of gradient-variatuinn online learning with Hölder smoothness and the development of effective conversion techniques to offline optimization.
Our Contributions. Our contributions are mainly two-fold, summarized as follows.
(i) For convex functions, we study gradient-variation online learning with Hölder smoothness, achiev- ing an O(VVT + L ) regret that seamlessly interpolates between the optimal guarantees in smooth and non-smooth regimes. Leveraging this adaptivity through O2B conversion, we achieve universality for stochastic convex optimization with Hölder smoothness, matching the optimal result [Rodomanov et al., 2024] obtained using arguably more sophisticated techniques.
2

---

(ii) For strongly convex functions, develop an O log VT + x (log T) 14p gradient-variation regret with Hölder smoothness that recovers the optimal results in both smooth and non-smooth scenarios. Achieving universality in offline strongly convex optimization presents additional chal- lenges. We address this by integrating online adaptivity with detection-base procedure. Combined with carefully designed O2B conversion, for the first time, we provide universal method for strongly convex optimization that achieves accelerated convergence in the smooth regime while maintaining near-optimal convergence in the non-smooth one.
guess-and- and-check
The convergence rates of the existing universal methods and our newly obtained results are summa- rized in Table Our work opens new avenue for converting gradient-variation online adaptivity to offline optimization, and recent progress in gradient-variation online learning [Zhao et al., 2024; Yan al., 2024] suggests possible further opportunities. Moreover, we hope will inspire broader efforts to integrate online adaptivity into offline methods, which may not only advance the pursuit of universality and other forms of adaptivity in offline optimization but also shed light on the design and understanding of modern optimizers in deep learning [Cutkosky et al., 2023; Chen and Hazan, 2024].
Organization. The rest is organized as follows. Section 2 introduces the problem setup and prelimi- naries. Section presents our results for convex functions in both online and offline settings. Section 4 considers the strongly convex scenario, where achieving universality in offline optimization is partic- ularly challenging. Section 5 concludes the paper. All proofs are in the appendices.
2 Problem Setups and Preliminaries
This section provides preliminaries. Section 2.1 introduces the problem setup of offline (stochastic) first-order optimization. Section 2.2 covers online learning and its gradient-variation adaptivity. Section 2.3 introduces online-to-batch conversion and its advanced variants.
Notations. We use [N]] to denote the index set [I. The shorthand Σ, stands for Elery
0 whenever > b. The Bregman divergence associated with convex and we define Σ i - IR is defined as (x. y) _ (xx)) (y(y) - (Vi((y), - y). By default, ||-I| regularizer vb : X denotes the normo We use S b to indicate (b), and use O())-notation to suppress poly- logarithmic factors in the leading terms.
2.1 Offline Optimization: Acceleration and Universality
Consider the optimization problem over convex feasible domain & C Rdd.
min {(x),
(2)
xEX
where é: X TR. is a convex objective. We assume the algorithm has access to gradient oracle denoted by g(-), and consider two settings:
(i) Deterministic setting: g(-) returns the exact gradient, i.e., g(x) V((x).
(ii) Stochastic setting: g(-) provides an unbiased estimate of the gradient. (lg( | V((x), and satisfies the standard bounded-variance condition, (x]]g(x) - v(())l x
S 0² vx E X.
Suppose the algorithm is allowed T queries to the gradient oracle and outputs final solution x/. We focus on the convergence rates of the sub-optimality gap, i.e., {(x{) minxex {(x) S Ex.
It is well known that smoothness plays central role in accelerated convergence [Nesterov, 2018), Consider the deterministic setting as an example. For convex functions, the optimal convergence rate is (1/ /T) for Lipschitz objectives, which can be accelerated to (1/TT2) when the objective is smooth. For strongly convex functions, the optimal rate improves from (LL/T") in the Lipschitz case to (eexp(-T/VF) for smooth objectives, where x - Le/ / denotes the condition number.
Prior research has aimed to develop a single algorithm that can adaptively achieve (optimal) guarantees without prior knowledge of whether the objective is smooth or non-smooth. In addition, several studies have extended this adaptivity to the broader setting of Hölder smoothness. This adaptability, known as universality in optimization methods [Nesterov, 2015], has attracted considerable attention in recent years [Levy, 2017; Kavis et al., 2019; Rodomanov al., 2024; Kreisler al., 2024].
In this paper, to clearly distinguish the degrees of adaptability of optimization methods to different smoothness levels, we introduce the following definitions of weak/strong universality.
3

---

Definition 1 (Weak/Strong Universality). An optimization method is said be universal if it can automatically adapt to an unknown level of smoothness of the objective function. Specifically,
(i) Weak universality: it simultaneously adapts to smooth and non-smooth (Lipshcitz) functions;
(ii) Strong universality: it simultaneously adapts to (Lv, - smooth functions for E [0. 1|.
It is infeasible to rely on the knowledge of smoothness parameter L or Lipschitz continuity constant G when developing weakly universal methods, and likewise v Ly when devising strongly universal methods. In essence, universality demands that the optimization method can automatically adapt various scenarios, with weak universality adapting to two cases (smooth and Lipschitz) and strong universality extending to broader Hölder smoothness.
2.2 Online Optimization: Regret and Gradient- Cradient-Variation Variation Adaptivity
Online Convex Optimization (OCO) [Hazan, 2022] is versatile online learning framework, typically modeled as an iterative game between a player and the environment. At iteration E [7], the player chooses decision x, from a convex feasible domain X' C Rdd. Simultaneously, the environment reveals a convex function ft X + R. and the player incurs loss f((x). The player then receives the gradient information to update X aiming to optimize the regret defined as
T
REGT Σ fx(x)) min Σ (xx).
For Lipschitz online functions, the minimax optimal regret bounds are ((VT) for convex func- tions [Zinkevich, 2003] and O log I') for X-strongly convex functions [Hazan et al., 2007]. When the functions are smooth, we can further obtain problem-dependent regret guarantees, which enjoy better bounds in easy problem instances while maintaining the same minimax optimality in the worst case [de Rooij et al., 2014; Foster et al., 2015]. Among many problem-dependent quantities, a particular one called gradient variations draws much attention [Chiang et al., 2012; Yang et al., 2014], which is defined to capture how the gradients of online functions evolve over time,
VT Σ sup supl [x) (x)11 XEX
is established that optimal gradient-variation regret for convex and X-strongly convex functions are ((VVr) and O & log Vr) [Chiang et al., 2012], respectively. There has been significant subsequent development in more complex environments [Zhao et al., 2020, 2024; Sachs et al., 2023; Yan et al., 2023, 2024; Xie et al., 2024]. Gradient-variatie due to its impact on analyzing trajectory dynamics and its fundamental connections to various optimization problems. It has been proved essential for fast convergence in minimax games [Syrgkanis et al., 2015; Zhang et al., 2022] and bridging adversarial and stochastic convex optimization [Sachs et al., 2022; Chen et al., 2024]. Recent results also demonstrate its important role in accelerated optimization [Cutkosky, 2019; Kavis et al., 2019; Joulani et al., 2020b].
online learning has gained significant attention
2.3 Online-to-Bateh Conversion: Stabilization
Consider the optimization problem of minxex E(x) with access a (stochastic) gradient oracle g(-). This problem can be solved using online algorithms with online-to-ban bathh conversion. A basic example as follows: we define the online function fi (x) A (g(x)); x) and ensure that for any x, E X::
E
T
x X )
-(xx)
((xx))
+ E
Σ
T
x.>)
1 + E [REGT].
Hence, for convex objectives, if the online algorithm achieves a regret bound of O O(VT), the corre- sponding offline optimization method directly attains a convergence rate of (1//TT).
To achieve accelerated rates in smooth optimization, advanced conversion methods and adaptive online algorithms are required. The key insight to evaluate the gradient on weighted averaged iterates, which introduces a stabilization effect [Wang and Abernethy, 2018; Cutkosky, 2019].

---

Algorithm Stabilized Online-to-Batees Conversion
Input: Online learning algorithm AOl, weights {arli=1 with at O.
I: Initialization: X1 E X.
2: for t = 1 to T do
3: Calculate X, 1 E. ag, with a1. Ex= ae receive g(x,) and
4: Construct fi(x) _ (g(,,, x) to AoL as the t-th iteration online function
5: Obtain X from AOL
6: end for
Ei= 04x, Output: X7 01:7
Stabilized Baline-to-Bated Conversion [Cutkosky, 2019]. Algorithm summarizes the con- version. Given online learning algorithm AoL and sequence of positive weights {az (o))Tr the conversion operates as follows: At each iteration f, it computes a weighted average of past decisions X, 1 Σ Os with Ora - E.= Os-- It then queries the gradient g(x;), and constructs the online function f2(x) (g( x). This function ft(-) is passed to the online algorithm AoL to obtain the next decision X(+1- After T iterations, the conversion outputs the final decision Σi= 0xX4 The conversion ensures the following inequality holds for all x, E X::
Xy 01.7
E [
E [(((x)] [(xx)
E
Σ (g(x)))
xx.
(5)
OIT
a1.
where the expectation is taken gradient randomness, and REG A Et a (g -x,, the weighted regret of the online learning algorithm Aoi..
is
This conversion of Eq. (5) enables accelerated convergence for convex and smooth optimization. For example, by setting at = f and leveraging gradient-variate online adaptivity to obtain an O(1) weighted regret, Kavis et al. [2019] ultimately achieved convergence rate of O(1/T3).
3 Convex Optimization with Hölder Smoothness
We achieve the gradient-variation our method to obtain the universal method for stochastic convex optimization in Section 3.2.
variation regret bound with Hölder smoothness in Section 3.1, then apply
3.1 Crraiint-VVariatoon Online Learning with Hölder Smoothness
We aim to establish gradient-variation variation regret for online lcarning with convex and (Ly, Hölder smooth functions {fr)/= A commonly used bounded domain assumption is required [Hazan, 2022]. Assumption (Bounded Domain). The feasible domain X' C TR. is non-empty and closed with the diameter bounded by D, that is, ||x yyl2 & D for all x, E X'
We leverage the optimistic online gradient descent (optimistic OGD) [Chiang et al., 2012] as our algorithmic framework for vradien-vvaraaton online learning. Optimistic OGD is similar to online gradient descent [Zinkevich, 2003], e.g., X4+1 = & 17 (X,,) but key difference lies in the point where the gradient f-) is evaluated. In optimistic OGD, the gradient is computed Xr, which is updated one step ahead of &, using prediction M, E IR" for the upcoming gradient. To this end, optimistic OGD maintains decision sequences {x, (=11 1 and updates by
point
X xxx X Mc).
R Ix [ 1/ V (x:)),
where n7 0 is time-varying step size, and II [y] A arg min ||x ||2 is Euclidean projection.
We first review the derivation of the O
gradient-variation bound under the L-smoothness as- sumption on [f By setting M, = V fa-1 (x, (x,-1), optimistic OGD yields the following classical gradient-variation analysis [Chiang et al., 2012]:
T
T Σ 2
REGT S
Th
(xx)))
- V sr- I
Xx T--1
1
TTT
5

---

Given the smoothness parameter I., deriving (VVVT) from Eq. (7) straightforward by appropriately
setting the step size 7)- On the right-hand side, the second term Σ, 1/: /1lV/(((x)) - 1 1|
an adaptivity term measuring the deviation between the two gradients, and the last one is negative stability term. The adaptivity term can be bounded by || fx(,)) - V ft-1 (xx) f=- (X;-1(x;-1)1) where the first part can be converted to the desired gradient variation Eq. (4) and the second part is bounded by _ x1-1l under standard L-smoothness assumption, and thus can be canceled out by the negative term in Eq. (7) by clipping the step size to n/: I 1 Therefore, most existing gradient-variation variation techniques require the prior knowledge of the smoothness parameter L.
Let us return to gradient-variation online learning with (Iu. -öHöder smoothness. Unfortunately we cannot directly apply the definition in Eg. (1) as we did with standard smoothness, because it would yield || ft-1 (x,) V (x,-1)ll [,]]|x, x,-1l which mismatches with the negative term. To this end, we present a key lemma regarding Hölder smoothness as a kind of inexact smoothness [Devolder et al., 2014], which has a similar form standard smoothness except for an additional corruption term. The proof is in Appendix A.2.
Lemma 1. Suppose the function f is (Lu, v)- Hööder smooth. Then, for any 8 > 0, denoting by L L 8 T+0 Lit", it holds that for all x,y E RR;
[Vx
Vf(y) S 1 1 y + 4L5.
(8)
When smoothness holds, i.e., v 1, Lemma 1 recovers the standard smoothness assumption when d approaches O. When functions are G-Lipschitz, i.e., V = 0 and L, 2G. by treating the right-hand side as a function for and calculating the minimum, the lemma results in - x G2, providing an upper bound that depends only on G.
In the next step. applying Lemma 1 encounters another severe issue: the parameter L in Lemma is algorithmically unavailable, preventing us from explicitly setting the step size clipping n S L. This is because the Hölder smoothness parameters L, and v are unknown, and 6 is chosen based on theoretical considerations and thus exists only in the analysis.
To handle this problem, inspired by Kavis al. [2019), adopt the following AdaGrad-style step sizes [Duchi et al., 2011] which allows us to perform virtual clipping in the analysis:
M++1 x VA, where A a (x)( + Σ (v.) M,ll
The rationale behind is that, since 7h-11 in Eq. (9) is non-increasing, it will eventually become smaller than I/L after certain rounds, i.e., for 1 >> T, thereby achieving implicit clipping. On the other hand, for i. < т. the relation 7/-1 x 1/ /A, Z 1/L implies that VA, remains small. Hence, the uncancelled gradient-variation summation in Eq. (7), which is bounded by VA,, is at most constant.
Putting everything together, we establish the gradient- variiantva regret with the proof in Appendix A.3.
Theorem 1. Consider online learning with convex and (Lv, -HHölderr smooth functions. Under Assumption optimistic OGD in Eq. (6) with M1 0, M₁ f for all t > 2, and step sizes 2/A1-1
D with A₁ defined in Eq. (9) for all t E [T], ensures the following regret bound:
REGT S (DVVV LL + + + DIVAA(I))))
(10)
Theorem implies optimal guarantees for both smooth and Lipschitz functions even in terms of the dependence on the domain diameter D: (i) when online functions are L-smooth, i.e., (L, 1)-Hölder smooth, our result recovers the optimal bound of O(DVVF + LD²) [Chiang et al., 2012]; and (ii) when online functions are G-Lipschitz, i.e., (2G, -H-der smooth, result also recovers the worst-case minimax optimal guarantee (GGVTT [Zinkevich, 2003].
We emphasize that our algorithm is strongly universal (as defined in Definition 1), since it does not require knowledge of the Hölder smoothness parameters. In fact, even when restricted to gradient-variatio online learning with smooth functions, our results imply an algorithm achieving an optimal
Remark 1.
+ LD2) regret without requiring prior knowledge of the smoothness parameter L. unlike previous works that depend on it [Chiang et al., 2012; Yan et al., 2023; Zhao et al., 2024]. <

---

3.2 Implication to Offline Convex Optimization
In this section, we achieve acceleration for offline convex and (L,, ---lerr smooth optimization in the stochastic setting, as defined in Section 2.1. This is accomplished by leveraging the effectiveness of the condient-variation adaptivity presented in Section 3.1 and combining it with the stabilized online-to-batch conversion [Cutkosky, 2019]. The proof can be found in Appendix A.4.
Theorem 2. Consider the oplimization problem minxex f(x) in the stochastic setting, where the objective E is convex and (Iw, - smooth, under Assumption I. Using the online-to-batch conversion (Algorithm 1) with weights oN = for all E [T], and choosing the online algorithm Aot. as optimistic OGD Eq. (6) with following configurations:
setting the optimism M1 0, M, (xg)(x)) with X, setting the step size as Trt
1 1. 0g22 + 01x4-11);
D with At defined in Eq. (9).
013
AV-1
Then we obtain the following last-iterate convergence rate for any x, E.:
L. T
oD VT
DI[V((x))I)
E [(((x)) - ((x.) 5
T
Theorem 2 achieves strong universality due to its adaptivity to Hölder smoothness, matching the best-known result of Rodomanov et al. [2024]. while our analysis is arguably much simpler due to explicitly decoupling the two algorithmic components - adaptive step sizes and gradient evaluation on weighted averaged iterates. For L-smooth and G-Lipschitz functions, our result recovers the optimal rates of O(LD² T + DD/VT) and O((G + t)DD/VT respectively.
Remark 2. We have achieved strong universality in constrained stochastic optimization. However, the unconstrained setting presents additional challenges and remains less explored, especially with strong universality unconstrained stochastic optimization still an open question [Rodomanov et al., 2024]. Although there have been some partial advancements in this area. In the deterministic setting, strong universality has been achieved: Orabona [2023] attained an OL sst||ate/// /T()+)))) rate, while Li and Lan [2025] obtained an accelerated [(L]||x, ||,||xx|/////// /| /T(+++)//)) rate with the pre- specified accuracy.
the stochastic setting, progress has been limited to weak universality and sub-optimality [Ivgi et al., 2023; Kreisler et al., 2024]. To the best of our knowledge, achieving strong universality in unconstrained and stochastic optimization remains an open question. We leave the extension of our method to unconstrained optimization an interesting future direction.
4 Strongly Convex Optimization with Hölder Smoothness
This section focuses on strongly convex optimization with Hölder smoothness. Section 4.1 establishes gradient-variation regret bounds for online learning, Section 4.2 obtains a weakly universal method for offline optimization, and Section 4.3 develops optimization algorithm that does not require the smoothness parameter or strong convexity curvature.
4.1
Variiatinn Online Strongly Convex Optimization with Hölder Smoothness
In this part, we study online optimization with strongly convex and Hölder smooth functions. In Theorem 3, we demonstrate that optimistic OGD, when properly configured, achieves the gradient- variation regret guarantee. The proof is provided in Appendix B.I.
Theorem 3. Consider online learning with X-strongly convex and (Tw, v--Hölder smooth functions. Under Assumption 1, optimistic OGD in Eq. (6) with M1 O, M, V f for all t 2 2, and step size Tt xt for all E [T]. ensures the following regret bound:
(
log (
VT
D2
[ X
REGT S
1
(log T) 140
max
where G2
max maX supxex
fx())
V f. (x)
Theorem 3 recovers kest- results under both smoothness and Lipschitzness: O Lnee log(1+ +
VT /&G ) + } D2) for I-smooth functions [Chen et al., 2024] and O log T) for G-Lipschitz functions [Hazan al., 2007; Abernethy et al., 2008], respectively.
7

---

4.2 Implication to Offline Strongly Convex Optimization
In this part, we develop a weakly universal algorithm for deterministic strongly convex optimization. This is done by leveraging the gradient-variation adaptivity with online-to-batch conversion tailored for strongly convex optimization, and a carefully designed smoothness detection scheme.
We first introduce the motivation of our solution. As explained in Section 2.3, the online-to-batch con- version transforms the convergence rate into the regret divided by the total weight a1:7 = =>i=1 at. To minimize regret, we employ online algorithm with gradient-variation adaptivity, which lever- ages smoothness to convert the adaptivity term, allowing the positive term to be canceled out by the corresponding negative term. Now, let us consider the A-strongly convex and Lm-smooth case. By tai- loring an online- tiline-to-batte to-batch conversion specifically for strongly convex optimization, i..,, Lemma 5, the cancellation between the positive and negative terms hinges analyzing the following expression:
20
V((x.)
V((x 01.1- 1D
(11)
we directly use the smoothness property [|V((x) Vi(y))l2 S (y x) [Nesterov, 2018, Theorem 2.5.5] to bound the positive term, we would need og satisfy 4ko S 01:011-11, where _ Lz/A. However, as we aim to design universal algorithm that adapts to both smooth and non-smooth settings, the design of a must not rely on the smoothness parameter Le.
Then, we design novel smoothness-detection scheme. First, denoting the empirical smoothness parameter at the t-th iteration by L, [ 1)ll, where Lt S Le, we proceed to analyze
2De(x:-1.xx)
the cancellation between the following two terms:
4.8 A(1 + B.) -1 01a-
Eq. (11)
where we define 3, - 01/0n for simplicity. Ideally, the cancellation holds if 3r S VA/(A..). However, challenge remains: L,, is obtained only after 3r has been determined. This arises from the use of optimistic OGD as the online algorithm the online-to-batch conversion, requiring an additional update step that integrates 3, information before computing x, and consequently Lt.
To this end, we designed a method that first guesses a Be, and then decides whether adjust the guess based on the observed L, Specifically, if the guessed 3, fails to meet the requirements 3. S /AL(L,,, we discard the current x,, halve 3r, and recompute x,. We then repeat this guess- and-check procedure until the requirement is satisfied. As long as we can ensure a reasonable lower bound for 3, the number of wasted updates will be logarithmic, which will only add multiplicative constant factor to the final bound. The simplest design is to explicitly define a lower bound / for 3r, which acts as a safeguard to guarantee a convergence rate in non-smooth scenarios. For the Le-smooth case, our mechanism implicitly provides an adaptive lower bound 1. \VA((4L)). This arises from the fact that when & S /X/(4Le), we directly obtain 8, S (A/(41,) since I,2 2 La- In this case, 3e will no longer be decreased.
To conclude, there are three key ingredients in our solution: (i) online-to-batee conversion tailored for strongly convex optimization (i.e., Lemma 5), (ii) the guess-and-ched smoothness detection scheme, and (iii) a one-step variant of optimistic OGD as the online algorithm (i.e., Lemma 11). We provide the convergence guarantee Theorem 4 with the proof in Appendix B.3.
Theorem 4. Consider the optimization problem minxex ((x) in the deterministic setting, where the objective is X-strongly convex and G-Lipschitz. Then Algorithm with 31 = 1,3 = exp( { In ensures that
G² min exp (mmin
-T
log T })
{(x,) - ((x.) S
GVR
T
without the knowledge of G or the smoothness parameter Le, where k A Le/ denotes the condition mamber, and we define L; oc if & is non-smooth.
Theorem 4 demonstrates the weak universality of Algorithm 2, meaning that it maintains the respective near-optimal convergence rates in both smooth and non-smooth cases, without knowledge of the parameters Teg or G. However, a slight issue arises similar to that in Levy [2017]: to achieve universality, both our method and theirs depend on the Lipschitz continuity of L, even though the
8

---

Algorithm 2 Universal Accelerated Strongly Convex Optimization
Input: Strong convexity curvature X, 31 and threshold B, oracle queries budget T and X1 E A. 1, X1 M1 O, index t 1, oracle queries count 1.
1: Initialization: 01
2: while c < T do
3: Construct g: a4 V( + Xx xx,,, set Be+1 Be
4: while c < 7 do
5: Set 0+++1 04+1 1 calculate x++1 a1:t-1 (01:xx (x+11x))
Guess procedure
6:
Construct M = 01+1 V((x, + Aas+1 - x(+1)
7:
Update x = 11x (g. M, + M++1)) with 1): Aaua
8:
Calculate X(+1 =
(01:X; + a4+1x query V((X++1), count + c+1
count
9:
if B:41 3 then: 4-66 ++ 1, break
10:
Calculate Tx+11 A [((x.)) (1)11
D> Check procedure
2D, (3,
11:
if B341 S V 41.--1
then: / + 1+ 1. break
else Be+1 max Be+1 ,33 Output: X, with r = the final iteration.
specific parameter is not required. We conjecture that Lipschitz continuity might be a necessary condition for universality in strongly convex optimization. Further investigation is needed.
Additionally, our algorithm Algorithm 2 is highly flexible and can achieve better theoretical guarantees when more information about smoothness available. For further details, see Corollary 1.
Remark 3. To the best of our knowledge, Levy [2017] achieved the previously best-known uni- versal results for strongly convex optimization, in which an adaptive normalized gradient descent employed with gradient norm. In the deterministic setup, the author achieved an O(log T)/T) convergence rate for the Lipschitz function, and an ((xp((-T/o) work improves upon their result by designing a weakly universal algorithm with the first accelerated rate of O (exx((-T/(6 (K)))) for smooth and Lipschitz functions. However, our method relies on a smoothness detection scheme based on the observed gradients, which only works in the deterministic setting for now. Extending it to the stochastic setting remains challenging.
conversion weights inversely proportional to the square of the
TTxx) rate for smooth and Lipschitz objectives. Our
Remark Designing a strongly universal, i.c., adapting to Hölder smoothness, method for strongly convex optimization is still an open problem. Notably, given the Hölder smoothness parame- ters, Devolder et al. [2013] have established a sample-complexity-baae (near-)optimal rate for smooth and non-smooth cases, which may a starting point.
rate that can recover the
4.3 Grid Search for the Unknown Strong Convexity Curvature
Algorithm 2 shows strong adaptivity the unknown smoothness parameter Le, and in this part, further enhance its adaptivity by removing the strong convexity curvature À as the algorithmic input."
We consider the strongly convex optimization minxeR= {(x) in the deterministic setting, where e(x)
sm-othoth and A-strongly convex, but the algorithm does not know Le and X.
For this setting, the best-known result is achieved by Lan et al. [2023], who obtained the optimal sample complexity with a pre-specified target error e. However, their sample complexity bound, when translated into a convergence rate for the sub-optimality gap, is expressed as O(exp (8////82//// (k)) and thus not optimal (see further details in Remark 6). Whereas we design an algorithm achieving an exp(-TT((1 + 4v 4v2k) [ log2 T))) convergence rate, with only the oracle queries budget T as input.
Algorithm outlines the main procedures. Essentially, it runs multiple instances of Algorithm 2 to search for the strong convexity parameter À by selecting the output with the smallest loss. Notably, a proper choice of the search range for is critical for success. In our algorithm, this range is derived
In online learning. adapting to unknown curvature is known "universal online learning", where widely adopted technique is to multiple base algorithms for exploration and use meta algorithm for exploitation.

---

Algorithm 3 Universal Accelerated Strongly Convex Optimization, Search Method
Input: Total oracle queries budget T. =
1: Initialization: 102 log, x7 E X = Idd and Ā =
[ with any a, b E Rd.
||a
2: for 1,,..... M do
3: Run Algorithm with (Λ₃ 2 x, B1 = 0,T, to4 x1 x"). receive x'.
4: end for
Output: x² with i, arg minogieM (((x)))
through rigorous analysis by carefully exploiting properties of smoothness and strong convexity, rather than imposing assumptions about the upper or lower bounds of X. The following theorem provides the convergence rate, with the proof provided in Appendix B.4.
Theorem 5, Consider the optimization problem minxeRs E(x) in the deterministic setting, where (()) is X-strongly convex and Lm-soohth. Denoted by n. - Le/X. Then, Algorithm 3 guarantees
| A
-T
log, mT) ))
S O
+ 4v 2x) 2x))
which is achieved without the knowledge of Le and X
Remark 5. The limitation of both Theorem and Lan et al. [2023] is that neither algorithm can guarantee convergence in the non-smooth case, i.e., when L 0c. However, result has an advantage in terms of the convergence rate. The result of Lan et al. [2023], when translated into the convergence rate for the sub-optimality gap, is expressed large denominator 882 in the exponent. Consequently, despite the log ''' factor in our Theorem 5,
((exp((TT((88))) /k))), with notably
remains highly competitive and even surpasses Lan al. [2023] when T S 8.7 x 10 Further details can be found in Appendix B.4.
Remark 6. We note that when expressing exponential convergence, the of asymptotic notation differs between convergence rate and sample complexity. To understand this, let us reconsider the sample complexity T S a log(3/e) the corresponding convergence rate S 8 exp( -T/aa) = (eex((TT/a)) constants. It can be observed that the constant a in the asymptotic notation for sample complexity has an exponential impact on the convergence rate. In contrast, the constant 3 in the asymptotic bound of the convergence rate influences the sample complexity only logarithmically. Thus this case, achieving optimal sample complexity does not necessarily guarantee optimal convergence rate.
(log((3fe) required to achieve the target error e and where a, 3 are two
5 Conclusion
In this work, we explore gradient-variation online learning with Hölder smoothness and its impli- cations to offline optimization. For online learning with Hölder smoothness, establish the first gradient-variation regret bounds for (strongly) convex online functions, seamlessly interpolating between the optimal regret rates in the smooth and non-smooth regimes. For offline optimization, develop a series of universal optimization methods by leveraging gradient-variation variiaton online adaptivity, stabilized online-to-batch conversion, and carefully designed components such detection-baas based procedures and grid search tailored specifically for strongly convex cases. Our convergence rates match the existing optimal universal results for convex optimization and significantly improve upon non-accelerated rates for strongly convex optimization.
An important open problem is designing gradient- gradient-variation online adaptivity and extending its implications to offline optimization in the unconstrained setting. Another interesting direction is to further develop offline optimization algorithms by leveraging insights from adaptive online learning.
Acknowledgments
This research was supported by NSFC (62361146857)
10

---

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.
N. Cesa-Bianchi. A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transaction on Information Theory, 50(9):250- 2004.
G. Chen and M. Teboulle, Convergence analysis of a proximal-lik, minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):33--543 1993.
Chen, Y.JJ. 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.
X. Chen and E. Hazan. Open problem: Black-box reductions & adaptive gradient methods. Proceed- ings of Machine Learning Research vol, 196:1-8, 2024.
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference Learning Theory (COLT), pages 6.1-6.20, 2012.
A. Cutkosky. Anytime online-to toaeett--btch,, optimism and acceleration. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1446-1454, 2019.
A. Cutkosky, H. Mehta, and F. Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-nee to-non-convex conversion. In Proceedings of the 40th International Conference Machine Learning (ICML), pages 6643-6670, 2023.
S. de Rooij, T. van Erven, P. D. Grünwald, and W. M. Koolen. Follow the leader if you can, Hedge if you must. Journal of Machine Learning Research, 15(1):1281-1316, 2014.
O. Devolder, F. Glineur, and Y. Nesterov. First-order methods with inexact oracle: the strongly convex case. CORE Discussion Papers, 2013016:47, 2013.
O. Devolder, F. Glineur, and Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
J. C. Duchi, F. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
D. J. Foster, A. Rakhlin, and K. Sridharan. Adaptive online learning. In Advances in Neural Information Processing Systems 28 (NIPS), pages 3375-3383, 2015.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Hazan. Introduction to Online Convex Optimization. MIT Press, 2nd edition, 2022.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-1)) 2007.
M. Ivgi, O. Hinder, and Y. Carmon. DoG SGD's best friend: parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202, pages 14465-14499, 2023.
Joulani, A. György, and C. Szepesvári. A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108:100888, 2020a.
P. Joulani, A. Raj, A. Gyorgy, and C. Szepesvári. A simpler approach to accelerated optimization: iterative averaging meets optimism. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 4984-4993, 2020b.

---

A. Kavis, K. Y. Levy, F. R. Bach, and V. Cevher. UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 6257-6266, 2019.
D. Kingma and J. Ba. Adam: method for stochastic optimization. In 3rd International Conference Learning Representations' (ICIR), 2015.
I. Kreisler, M. Ivgi, O. Hinder, and Y. Carmon. Accelerated parameter-free free stochastic optimization. In Proceedings of 37th Conference on Learning Theory (COLT), pages 3257-3324, 2024.
G. Lan, Y. Ouyang, and Z. Zhang. Optimal and parameter-free gradient minimization methods for
convex and nonconvex optimization. arXiv preprint arXiv::230. 12.399 2023.
K. Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Advances in Neural Information Processing Systems 30 (NIPS), pages 1613-1622, 2017.
Li and Lan. A simple uniformly optimal method without line search for convex optimization. Mathematical Programming, pages 1-38, 2025.
H. Luo and R. E. Schapire. Achieving all with parameters: AdaNormalHedge. In Proceedings of the 28th Annual Conference Computational Learning Theory (COLT), pages 1286-1304, 2015.
H. B. McMahan and M. J. Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Conference Learning Theory (COLT), pages 244-256, 2010.
Y. Nesterov. Universal gradient methods for convex optimization problems. Mathematical Program- ming, 152(1):381 2015.
Y. Nesterov. Lectures Convex Optimization, volume 137. Springer, 2018.
Orabona. Normalized gradients for all. arXiv preprint 2rXiv:2308.05022) 2023.
A. Rodomanov, X. Jiang, and S. U. Stich. Universality of adagrad stepsizes for stochastic optimization: Inexact oracle, acceleration and variance reduction. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 16770-26813, 2024.
S. Sachs, H. Hadiji, T. van Erven, and C. A. Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 691-702, 2022.
S. Sachs, H. Hadiji, T. van Erven, and C. Guzman. Accelerated rates between stochastic and adversarial online convex optimization. ArXiv preprint, arXiv:2303.03272 2023.
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.
J. Wang and J. D. Abernethy. Acceleration through optimistic no-regret dynamics. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 3828-3838, 2018.
J. Wei and L. Chen. Accelcrated over-relaxation heavy-ball method: Achieving global accelerated convergence with broad generalization. Proceedings of the 13rd International Conference on Learning Representations (ICLR), 2025.
Y.-F Xie, P. Zhao, and Z.-H. Zhou. Gradient-variation online learning under generalized smoothness. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 37865-37899, 2024.
Y.H. Yan, P. Zhao, and 7.-H. Zhou. Universal online learning with gradient variations: multi-layer online ensemble approach. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 37682-37715, 2023.
Y.H. Yan, P. Zhao, and Z.-H. Zhou. A simple and optimal approach for universal online learning with gradient variations. Advances Neural Information Processing Systems 37 (NeurIPS), pages 11112-111661 2024.
12

---

T. Yang, M. Mahdavi, R. Jin, and S. Zhu. Regret bounded by gradual variation for online optimization. Machine Learning, 95(2):183-223, 2014.
M. Zhang, P. Zhao, H. Luo, and Z.-H. Zhou. No-regret learning in time-varying, zero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26772- 26808, 2022.
Zhao. Lecture 9. Optimism for Acceleration, 2025. URL http::///oxx.eengzaao.. com/ course/ AAtttaattetttttttteee.......// Lecture Note for Advanced Optimization.
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. 12520, 2020.
Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem- debleen-dependett dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICMI., pages 928-936, 2003.
13

---

A Omitted Details for Section 3
In this section, we first provide some useful lemmas for Hölder smoothness, then give the proofs of theorems in Section 3.
A.1 Useful Lemmas for Hölder Smoothness
This part provides several useful lemmas for Hölder smoothness.
Lemma (Lemma Nesterov [2015]). Let convex function f R over the convex set X be
--..ver smooth. 3 Then for any ā > 0, denoting by =81+0 - for all x, y E N:
L x) - y|12 -1
f(y) - fxx) (V)(x),
(12)
Lemma (Theorem of Devolder [2014]). If convex function f TK over the convex set X satisfies that, there exists positive constants L and 5 such that, for all x, y E X:
f(y) - [(x) (VS(x), - x) s L - y + 6,
(13)
2
then for all x,y E X:
1 2L
V
Vf(r) f(y) f(x) s(>)
y +
(14)
Lemma 4 (Theorem A.2. of Rodomanov et al. [2024]). If convex function f Rd - R over Rd satisfies that, there exists positive constants L. and such that, for all x, Rdd
L |x 2
f(y) - f(x) (Vf(x), - x)
y11² +
(15)
then for all x,y E Rd:
[V - S 2LD,(x,y) + +2L8.
(16)
A.2 Proof of Lemma
Proof. Since f is (Lv, Hööldr smooth, by combining Lemma 2 and Lemma 3, for any 8 > 0.
denoting by L == 5 TT L for all x. X:
(14)
(12) J. & fly) f(x) (Vf(x), x) 8 S ||x y/1 26. (17)
2L fx()) vf(y)
Multiplying both sides of the inequality by 2L completes the proof.
A.3
Proof of Theorem
Proof. Applying Lemma 10 with comparators u, = X, = arg min Et fe(x) for all e (T).
REGT
[i(x:)
(x.)) <
Σ (x,)) Xt xx)
T
Mh+ [[(xxx M D
Σ
Xx
11
1/+1
81p+11
T
<3D Ar
Σ
|x] X 112
(18)
8
where A, A [x) + E (x,(x.)
M2 and we apply Lemma in the last line.
'Toough X' is supposed be closed in Nesterov [2015]. this lemma holds for X R with the same proof.
14

---

If VAT S 2TDD, we finish the proof trivially, so in the following, we assume VAr 2LD.
Define to that, if VAi > 2LD, let to 1, otherwise let to = min : t E [T - 11, v A++1 > 2LD). Then have / Ato I (x)( ) + 2T.D, while for all to + S 1. S T it holds that VA, > 2LD. Because all online functions are (In --Hder smooth and applying Lemma 1, we show the following decomposition for av Ar with constant a > 0. For any 6 > that only exists in analysis, denoting by L 6 IT -
aVAT av A 1
Σ
[V((xx - Vf--((x,) Vx,
- (x+ 11
1
Sa Avo +a 1
2L2
Σ
||x - x 8L Σ 8
1=ta+1
to+
L
Sav Arg +a//V/ a L +
Σ
x +aV8LL
-
1=tt1
With this decomposition, we prove the regret bound in the following with a - 3D:
(" L
REGT S <3DvAn Ato + 3D 2Vr 9LD2 +
Σ
|x| x, 1
2
874+1
+1
< 2V 3DIVV/ )| + 3DVSLST.
Then by choosing ô = D1t " (that only exists in analysis), we obtain
REGT SO (DVV++ L. DI + -DIV)((s)I))
which completes the proof.
A.4
Proof of Theorem 2
Proof. With optimistic OGD as the online algorithm, by defining f+(x)= _ (oig(X)); x), we have:
(g X x.) Σ f((x;) Σ (xx))
(18) 3D AT
Σ
Xx x1
8mp+1
Now trivially assume VAr 4LD, and define to [T 1] that, if /Ai ALD, let to =
otherwise let 40 min E [T-1], /Ar+1 > 4LD).. Then we have A I (x)))++D
while for all to 1 < 1 < T it holds that VAr > 4LD. Continuing with our previous inequality:
T
(g(g(x)), x.)
1=1
1
< <3DVAto +3D
Σ
afllg(x:) g(x.)]12
Xxr
xx-
1|2
81/++1
11
2=
53D +3D
Σ V - v((x)))
1
|| xx-1l²
81/++1
1=
+ +3D
Σ 3a V - g(x:)12 3D,
Σ
3af || [((xx)) g(x:))13
(=++1
(=
15

---

where |a b + cll2 /||l| + 3||b||2 2 + 3||c|| for any a, b, Rd. Now by taking
expectation and using Jensen's inequality, i.e., Ez [v]] I [x] we have
T
E
a
(g())) X
x.)
T
T
E
3D,
30 - V((x)))
X X
871+1
1=
+3D/|V +
12 1 22
where we apply [l]l((x)
| x - -.. By Lemma I and the definitions of X,, Sx,
Lt
V
V2(22)11
2 a.'² [ - 1 2 + 4a LŌ
|x - x11 + +4
0
x 41. X x1-1 + 4
Then have
3D,
Σ
(o(l((((x)) 2 Σ
xx x1-1 1|
817+11
1=
T
< 6D
3
|xx
X 11-1|- 112
xx x1-1
12V2222
817++1
Amta+!
27LD2
L
|2]
x1
12
2
2DV
87/41
< 27LD 12V2DVL8T"
Therefore, by combining the above inequalities we obtain
a (x)) X -x.)
x.)
B [(((xr)] f(x.) s
E
01T
(D Il + 78LD
24v2D Lo + 24
72
VT
Then by setting d = D 33
we achieve the convergence rate of
oD
D[I T2
E [(((x))] ((xx) 50
T
VT
which completes the proof.
B Omitted Details for Section
In this section, we give the proofs of theorems in Section 4.
B.1 Proof of Theorem 3
Proof. We apply Lemma with u, = x, arg min
T
REGT
f((x)) E f((x)) = Σ (x)())); X1 xx) Σ (x,,
T
T
T
((xx)))), Xx - -x.)
Σ
xx X ||
Σ (x.:
2
t=1
16

---

(23)
T
A T
5
(1|x, - 81112-11xx -1x,
&2+1119) 113)
Σ xx - Xx 1|
2/7t.
TERM-A
Th VV)(() I
1
Σ Dj, Xx.,
TERM-1
TERM-C
In the second line above, we use D,. (x, We first investigate TERM-A. Since T/1
2
2 211x - yl2 by the x-strong convexity of ft.
G
X7
X,, 12112
X
T
TERM-A
|x.
11,11
X,
xel1?
2171
277
21/-11
4
1=2
1=1
T-1
1
T T-1
(1|x,
Re+1 112 X+ - xx113)
5
1x
81+1 11?
12
VA
6
(lV - (x-1 TERM-B,
where the second line we use x = XI. And the last line above we apply Lemma 7 [Chiang et al., 2012]. Then by combining TERM-A, TERM-B and TERM-C together and applying Lemma
with arbitrary 5 0 that only exists in analysis, and denoting by L 8 L obtain:
12
REGT s
(x,,)
(x-- 2 Σ Dj (x,,
Xt
12
[xxx))) - V((x.)) -V V(L-i((..)
Vi-
Σ Dj. (x., xt)
T
36
T
144L
1
T
144L8
(x,,) (x,)
2
(x,,
+
Xt
Xt
Xt
1=1
1=1
36
144L
1
144L8(1 + In
<
sup (x)x)) - (x)- +
2 -
Dj, (x,, x:)
1=1
X
xEX
At
The first two terms can be well controlled by two technical lemmas (Lemma 13, Lemma 14), hence:
36G2
VT
72G2
36| [)
REGT S X
max In
1+
max
G2
Gaxx
144
288L A
144L8(1 + In?)
In
1+
A
where we define G2 max supxex f(((x) V (x) and use the property of (Ly, Hööler smooth function fi that Dj, (x, < L, Di+ [Nesterov, 2015]. Solving the trade-
off: Ln D with L 1TT L obtain d = LI TT) and arrive at:
36 max In (
Vr
7202 max
36 / f1
REGT <
1+
22
A
max
144L3
288L, D
(In T") T
2 (1 T)
In
1+
X
A
17

---

Gh
max
Vr
D2
[ A
=0
log
1+
(log T) 140
G
max
where 1n(1 + 2, (In (7440//)4 ((D) = (1). because it only consists of the logarithm of the constant / (AD1-V), and we treat the log log factor as a constant, following previous studies [Luo and Schapire, 2015; Zhao et al., 2024].
B.2 Useful Lemmas for Theorem 4
In this subsection, we provide the proofs of some useful lemmas for Theorem 4.
Lemma 5 (Online-to-batel Conversion for Strongly Convex Functions). Let the objective E(-) X - R be X-strongly convex. By employing the online-to-batch conversion algorithm with online function fe(x) A ar (V(()))
x)
+ Xae
||x - xel. , we have, for any x, E X:
2
-1.0-1 (xxx11(((x 1 ( -
((xT) [(xx)=
(19)
01:
where Dr(x, y) A E(x) - -(yy) (Vely), - any x, y X.
x- y) is the Bregman divergence associated with é f.ror
Proof. This lemma the variant of the stabilized online-to-batch conversion [Cutkosky, 2019] for strongly convex functions, We start from the equality:
((XT) - ((x.) = 01((x1)
a1x((x))
12 f(x-)
01:7
01:7
t=2
1
(e(x() -((x))
0112111 (((xx) ((xx-1))
0::TT
01
2=
(V((x)), & -
Xx - -x1133
ar
0nT
T
01+-1 ((V((x)), X² - -x--1) - 1xx
01: t=
1
2 11, xx113
(V((x)), X - -x+)
0.:T
[=1
1
au (V(x(())), X xx)
a1:--1 (D((xx,1,x)))
OET 2
01.TT
(V((xt), - -x,) x - Xx
1
1|x - xx11²)
Σ a 11
ar
マタ
OAT
T -xx
OAT
where in the inequality we use the definition of X-strong convexity and Bregman divergence, after which we use the property of 1 x,) (x, x,) in Theorem I of Cutkosky [2019]. The second inequality is by directly adding the positive term Aay
2a ||: x,I12.
Lemma 6. For the settings in Theorem 4, is non-increasing with lower bound B. Denoting by to the minimum iteration satisfying Br, = 3, otherwise let tu = T + 1. Algorithm 2 ensures:
232
((x,) {(x.) S
V((x,)) VI(x.-)|| (20)
A AI + B.)
t= X(1 + T24
18

---

Proof. With f((x) _ or (V((((())
x)
Are ||x xxxx111 by Lemma 5 we have:
2
1 (fe(xi) f((xx)) - -1x=-D(((xx1.
((xx) {(xx)= S 01:
By Lemma 11, with the definitions 7)
Aoye''
Mr = V,Ve((x-1) + -
1
(E==1 022x2 + 01)x-11,, we arrive at
- -x(x))) Σ 01 (xx-11,;
(Vx((x)),x X - xxxx,,
xx,)
0i||x -x+11
2
t=1
1=1
nel VXx() - Mll?
Σ
|x - X(+111?
Arjs
1=1
Σ De
1
da!
||x xx+12
2171
21/-11
of
[((x,)) - v((xx-1) + A(x, - X1-1 - xx + xx)
1|
Σ
1
||x - x1-1
Aayi
41
t=2
a1 (x)-1D((( + 2
[[((xs))
(by setting me Xani
A
1=1
2ag
V((x,)
V((x-1)11 + Σ 2a7d
(1-ore)
ac
(xt x--
Aaya
a'it
Aa1=-11
||x: -x,- 11_ 11
011--1 1 (D((X._1,xx)
+ ス [[(x1)]1
al
2=
t=1
201
[((x.)) - v((xx-1)|1
01 1 x4) + a1 x |((x)))1
ttya
1=2
20fafz-1d
Aa1=-11
||x x1-1 |
ai
4
2a
<
[((x.) - vi(xx-1)11
Σ
+ [((x))1?
Xaya
t=1
where the last inequality is because 3i I and consequently
2f
A011=11
38
201
aix
(1+ 3.)3
8
Algorithm 2 ensures that for all t t2 2, 3, // 4 and either Be > 3 or Br 3. When 3r > B, it
holds that 8, S V
due to the algorithm design. then we have The
A
20 V[(x.) - V[(xx-1)]1 (xxx-1x
4LLa?
1)
D( = ( 4Lo87 x (1)+ -1) o11-1D((Xx-11..)) S O.
=
Since 3r is non-inereasing, denoting by to the minimum iteration satisfying Brg = B. otherwise let
la = - +1 1. Then for all 1. 2 l0. 3r = B. Finally, we arrive at
an [
2a
((x,) {(x.) S
[(((x)) - VI(X
Aa1a
19

---

V 2 B,)
2
V((x.) - ve(xx-1)|1=
1(1 B) 1+2
t-
which finishes the proof.
B.3 Proof of Theorem 4 and Corollary
Proof of Theorem 4. We do not know whether ((x) is smooth non-smooth, but it Lipschitz con-
tinuous with unknown constant G. We have maxiers-II [V(x)
v((xx-1)]1 < 4G2. By Lemma 6,
I[V((x))11 +
8G
((x-) - 5(x+) ((xx)
Σ
x 2 + 5.)
A
(1 + B) T
t=
8G 3
1 tto S T).
(21)
X(1 + max (1/(4/ 9))
À
By choosing = exp(( In - 1, we conduct the following case-by-case study:
Case of 1 2 B. Then since for all 2 2, Be > 1 we have to = J + by definition, then the 1y second term in (21) becomes zero. In this case, we have
[ min exp (T+4/R)
) (1 (1++))-)
(xx) - ((x.) < o
X
Moreover, the total gradient queries number T S [l0g2(4 then we arrive at
((x,) - [(x.) 0
[V((x)]1 min exp
T + 1
(1 T+logg (4
1+ AVK
[V[(x1)]1
-T
(1 1o (oR2(1113) })
0
A min
exp
1+4/8 'T
[VV((x))
6// T 1):
-T 1
0o
min
cxp
A
where in the last inequality we use (1 + x) (10g, < 3 for all x > 0.
Case of 1 TVK
B. In this case, by (21) have:
[V((x)))| (1+ G2B GGB)
-
A
Moreover, the total gradient queries number T + [log2 then we arrive at
((Tr)) - ((xx)) 0
/|V((x))1?
(1 (1+?) ())
TT -T+ (10g(1111)))
+ G2
A
||V((x))]*
G2 Golog +
0
XT
XT
where we use (1+r) < 3 for the exponential rate, that is (xp(),/=) dominated. Finally, combining these two cases, obtain
and exp( + In 1) -1 -15
77. In T. Additionally,
-T' > exp(- (5) 2 exp( - In T) 75/o = 22("ogg' T is
((x)) ((xx)) 50
( min exp
G
T 6VR
log T
}
T
which finishes the proof.
When the optimization problem is easier, i.e., with additional informations, we can use Algorithm framework obtain better convergence rates, provided in Corollary
20

---

Corollary 1. Consider the optimization problem minxex f(x) in the deterministic setting, where the objective is X-strongly convex. In the following two cases:
(i) If is known to be Le-smooth, then Algorithm with 31 3 (ALe)) ensures that
[V((x))]
-T
(xx)) - ((x.) So
exp
1+ 2/R
where 2 LE/D denotes the condition number.
(i) If E. is smooth but the smoothness parameter L. remains unknown, then Algorithm 2 with 81 1, B- ensures that
[V((xi)]I exp
T
(xx)) ((x)) S0
1+4VF
Interestingly, in the first case of Corollary 1, where Lę is known, convergence rate matches Wei and Chen [2025, Theorem 1.1]. Moreover, their "over-relaxation" update form coincides with the one-step update variant of our optimistic OGD online algorithm.
Proof. The first case. We are given the smoothness parameter L. By Lemma 6, since Br = (A/(4L)) & vA/(AL)) for all t 2 2, we have to = r + 1 by definition, and T = T, therefore
2 2
5O [|
-T
((xT) ((xx) 5
X(1 \/(LA))
exp
I+ 1+2
where we use (1 + + (1 1/(1 2))² & exp( 2)) for all æ > 0.
The second case. We know that L is smooth but do not know the exact smoothness parameter Le- With = O, we have 1
1/e 5 3r S V 47. for all 2 St S By Lemma 6 with to = T 1,
01 (3)))) I 21(V((x))]1
|1(x1)111
2[x exp
((x,) ((x.)
A(1 - 1/(4/T))
1 4VR
where use + -ーーーーーーー---ー =(1 (1-1/(1 1x(1+x)) Sexp(-7/(C (-/((1 x)) for all x O. Moreover, the total gradient queries number T +++1log) 4 (vr)): substituting into the above inequality,
2/1 21( exp
-T
(4vk)
((x+) f(x.) <
exp
1+45K -T
1 4/K
|1(x))11
exp
I + 4V
where we use exp
logg xt
1.5 for all x > 0. This case is proved.
B.4 Proof of Theorem 5 and Discussions
Proof of Theorem 5. For any x X, we have {(x) - {(x.) [V(()) | x. V[(x))]
because {xx) is X-strongly convex, and V((x.) ) = Hence when T the convergence rate of (x) exp( =I) Vx Vx(x)) becomes vacuous. Therefore, without loss of generality,
assume & < 2
a-bb Moreover, by calculating the curvature estimate Ā [V((a)-V(()) vibii] with any a, b E IRd, have A Tag. Combining with < 2 implies that T/T2,
Denoting by M [2 T7. and A; 2- Ā for E [M]. there exists i, [M that A, < < 2x,,. Then E(-) is also X; -strongly convex with condition number being 2x. Substituting
into Theorem with T; = 37 we have
T
|[VE(x))11 A
T
{ - s
exp
+ 4 4v2x) ) logz T
The proof is finished.
21

---

Comparison with Lan et al. [2023] We compare our result in Theorem 5 with the sample complex- ity hound for optimizing the gradient norm established in Theorem 5.1
Lan et Lan [2023], that is, with
C = v2(3 + 16v2ca)) CA = as they provided, T S
First, we reformulate their result as follows:
(i) After translating their result into the convergence rate of the gradient norm, turns out be -2)(2)) (4+55501)v )) Substituting the constants implies:
O( exp(
[i((x)] S 5 exp (176,
(ii) Applying ((xT) - (xx.) S [V(((T)] we obtain sub-optimality bound given by
T
((XT) ((x.) S o exp
(22)
882
Then we consider when our rate in Theorem is better than Eq. (22). Solving the following condition:
(1 + 2v))) 2 log2 27 < (1 +
T VK S 882
implies that T' s 8.7 1019.
C Supporting Lemmas
In this section, we provide supporting lemmas for this paper.
C.1 Lemmas for Optimistic OGD Algorithms
In this part, we provide useful lemmas for optimistic OGD and its one-step variant.
Lemma 7 (Proposition 7 of Chiang et al. [2012]). Consider the following two updates: (i) x arg migminxxx (gg x) + (x, c)}, and (ii) x' arg minxex {g'' + Dx c)}, where the regu- larizer v X' + IR is X-strongly convex function with respect to ||-II. we have A|xx -x'Il S llg- - g' Il..
Lemma 8 (Bregman proximal inequality, Lemma 3.2 of Chen and Teboulle [1993]). Consider the following update: x = arg minxex {(g, x) + (x c) where the regularizer 1/ X + IR is convex function, then for all u E X, we have (g, u) I De (u, - D x) Dx c).
Lemma 9 (Theorem of Zhao al. [2024]). Under Assumption 1, Optimistic OGD specialized at Eq. (6), that starts at &1 E X and updates by
X TTx R2 - Mc), 8 1Ix (x, nN [(x:)))
ensures that T
T
1
[V)(())) X (0x)x--4)5
(xx))))) - Mr - x(+1)
(I|I x,
||e
x 11
217
TERM-A
TERM-B
T
(|ix: Se+1l1 + 1|x: - -x, 12.
(23)
2TP.
TERM-C where Ui,..., UT E X are arbitrary comparators.
Lemma 10. Under Assumption 1, Optimistic OGD specialized at Eq. (6) with non-increasing step
sizes Tr, ensures that
D2 +DP
(V((x)) x: 5
Σ Mo+t Vi(()))) M,Il
||xx -x- 11 (24)
4T+1
8mp+1
where Pr $ ET u--1ll is the path length.
22

---

Lemma 11 (One-step Variant of Optimistic OGD, [Joulani al., 2020al). Under Assumption the one-step variant of optimistic OGD that starts at X1 E X and updates by
X++1 = 1xx [x (x))) - M2 + M4+1)l,
(25)
ensures that, for all u E X::
Σ
(V)((x)) - Mc x(-1)
_ ||x xx+1l1
1
21/r
+
Xx - -ull +
||x| - -11??
21T
27p:
2m
Proof of Lemma 10. By Lemma 9, we consider each term:
T
T
1
TERM-A
Th
7++1 [ M
1xx:
&et1ll
11
xx Rc+1l1
47t+1
477o
47%c
t=1
T
D2
T
S
7h
[x,( - M +
||
|x - 81+111?
4ff+1
417t
t=1
1=1
D
1
1
1
1
TERM-B <
||u 8,112
|
&rl12
+
||
-
| Rell?
21
21/r
217t
217
21p-11
2
D
1
1
[|u
|| xxl13) ) Σ
D²
2111
21/t
21/t.
21k=11
1=2
D2
T
u1
||u - 2 + u - 3z
20T
277
t=2
D2
DPT
S
21/+1
7/1+1"
T
T
TERM-C >
I|xe -x,+1l1
11+
+
(|xx-1
22112 + +11xx - 2x
41/=-1
1=2
T
||x:
x2+1
+
||x:
x1-1 +
Σ
||
41/;
81/--1
811:
81/:
t=1
t=2
1=2
2
1
T
1
||x:
x1+111
||x1
X1-1
11
|x]
x1-1
41/:
STY
8T)
87/111
87/+1
T
D
T
||x:
x2+111
l|xe
x1-111?
4nj
Avy++1
811+1
where we apply Assumption 1 and the condition that y non-increasing. Combining TERM-A, TERM-B and TERM-C finishes the proof.
Proof of Lemma 11. By Lemma 8 with (xx) = 2nj x the update Eq. (25) implies for all u E X::
1 (/u x I|u x1-1112 1|xe x2+1l??).
fx)( Mf + M441, u) S
2n
Then by rearranging and taking summation from 1 to T, we arrive
r
23

---

T
(xx)
M,, X x(+1) + (M1, x1) - (M XT+1 +
Σ
(M++1 - My, u)
T
T
+
Σ
1x: -
-ul? u112+ + - ||2c - ul1
Σ
|x| x(+111
2t
201-11
2n11
217²
1=2
t=1
(V)((x)))
- M1
x(+1)
||x: x(+111 11?
2712
1
1
1x1
ull2
||x u/l?
23te
20/t-1
2011
where we define M1 - 0 and Mr+1 O.
C.2 Useful Lemmas
This part provides some useful lemmas for mathematical analysis.
Lemma 12 (McMahan and Streeter [2010]). Suppose non-negative sequence {ai (a))_ and constant
> 0, then we have
a₂
2
8
ar.
(26)
-==1 ag
Lemma 13. Suppose non-negative sequence {arlT
Define Omax maX de and assume
Qmax 0, then we have
T
amax
In
1
at
+
2amaxx
amax
1=1
1=1
Lemma 14. Suppose A 0 and non-negative sequence (b, and denote by bmax max by >> 0. Then holds that
A (4-1)) b, bmax AAnn( A).
Σ
Proof of Lemma 13. Define 7 = [
Et= at E (T). We have
Rmex
T
0:
Σ
amax
1
<
amax
1+
dx
<
amax In
1
a:
+
amax-
amax
t=1
1=1
T < T. we also have
T
T
Σ
Q0 <
Σ
Qmax
t
at
S
Σ a1
Σ
a2
0max-
(=++1
(=7+1
1=1
Proof of Lemma 14. Define min(T, [A]} and trivially assume 2 then have
Umax Σ 7 -1 1 b. - Σ ( -1 1) s 1+ l -ss - = A+ A
s=1
whose maximum is < Aln(1 + A).
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have claimed the paper's contribution in both the abstract and the introduc- tion part.
Guidelines:
The answer NA means that the abstract and introduction do 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 to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
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 of the work performed by the authors?
Answer: [Yes]
Justification: This paper clearly outlines the assumptions that may be required for the theorems and regards some of them as limitations (such as bounded domain assumption or deterministic setting), and discusses the future areas for improvement in the corresponding sections.
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 "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution 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 fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, a worse outcome night be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The problem setups and assumptions are provided in Section 2. We provide theoretical guarantees in Section Section 4 and Section ??, and all the corresponding proofs can be found in Appendix A, Appendix B and Appendix ??.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but 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 proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions 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 verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case large language model), releasing of a model checkpoint, or other means that are 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., a large language model), then there should either be way access this model for reproducing the results way reproduce 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 authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-souree models, it may be that access to the model is limited in some way (c.g., to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
26

---

5. Open access to data and code
Question: Does the paper provide open to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ public/guides/ hoooliccguudes//deeuuuiiiiie onoosooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. ppublic/guiden (CodeSubmissi oioooiicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset experiments are reproducible, they should state which ones 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 to 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 to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate 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, confidence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing some parameter, or overall run with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call to a 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 the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not 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 are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures 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, or 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 in the paper (e.g., preliminary or failed experiments that didn't t make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /ttpp:::///uuips..../.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consider- ation due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is purely theoretical work, and we do not find specific societal impacts that should be highlighted here.
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 socictal impact.
28

---

Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, there is direct path to any negative applications, the authors should point 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 needed point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology 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 mitigation strategies (e.g., gated release of models, providing defenses in addition 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 (data or models), and thus poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
This paper does 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.
29

---

If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi saperswithcode, thcode. com/ comaaatsets has
curated licenses for some datasets. Their licensing guide can help determine the license of a 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
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations,
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material fine, but if the main contri- bution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
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]
Justification: This paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
30

---

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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https / htt///eerppppp/ee/ /ttp//rips.cc/ooffeeeeeeeeeeeeee cc//onnereencee/2225///////////e for what should should not be described.
31


Reviews:
[{"review_id": "bEofkB9ybJ", "reviewer": "Reviewer_yNEM", "summary": "This paper addresses the challenge of achieving optimal regret bounds in online convex optimization (OCO) under gradient variation measures. Specifically, while prior works in OCO typically assume Lipschitz or first-order smooth conditions, the authors considered  $\\nu$-Holder conditions which interpolates these two regimes. The authors propose a parameter-free algorithm based on Online Gradient Descent (OGD) that achieves regret bounds of the order  $O(\\sqrt{V_T}+T^{\\frac{1-\\nu}{2}})$, where $V_T$ is gradient variation defined as the maximum total squared variation of the gradients through iterations. This matches the known lower bounds at the two corner points of Lipschitz and smooth functions. The authors further demonstrate that their method extends to various settings such as offline convex optimization, strongly convex optimization, and dynamic and universal regrets.", "questions": "We recommend the authors to address the issues in the weakness section, especially the optimality claim of the proposed results stated in the abstract needs to be appropriately justified. Besides, while the submitted work covers a wide range of extended settings, the explicit formulations in this work contain limitations that were not clearly stated. For instance, in the extension of SCO the authors focused on the settings of first-order oracles, while there has been extensive works on zeroth-order optimization, which has different fundamental sample complexities. The authors also focused on Holder conditions with $\\nu\\leq 1$, while there are works that explores higher-order smoothness conditions. To name a few, see the references at the end, which are by no means exclusive. We recommend the authors to clarify these limitations, and briefly mention if the proposed results can be extended to those settings. We would be happy to raise the score if the above issues are addressed adequately. \n\nBach and Perchet. \"Highly-smooth zero-th order online optimization\" \nAkhavan et al. \"Exploiting higher order smoothness in derivative-free optimization and continuous bandits\"\nNovitskii and Gasnikov. \"Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit\"\nYu et al. \"Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity\"\nAkhavan and Tsybakov. \"Gradient-free stochastic optimization for additive models\"", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:  The main conceptual contribution, adaptivity to unknown regularity under the gradient variation metric for Holder smooth functions, seem to be novel. The proposed algorithm provides a flexible tradeoff between the required sample complexity and the level of smoothness of the objective function. Rigorous analysis was provided and the achieved sample complexities are presented in clean forms. The paper is generally clear, with good use of tables, figures, and notation to present the main results. Section 2 provides an insightful summary of related works and positions the contribution well.\n\nWeakness: \n1. While the achievability results are clearly presented, it is not clear that whether the proposed algorithm achieve optimal regrets besides the two special cases of $\\nu=0,1$ as no lower bounds were formally presented as theorems or remarks. If no lower bound is provided, the authors should not claim in the abstract that the proposed algorithm is optimal. \n2.  According to the discussion provided by the author, the extended result to SCO seems to be already known in Rodomanov et al 2024.\n3. The formulation and assumptions in this work can be better clarified. For instance, while OCO is a well known framework, it is recommended to still provide a brief and concrete description before introducing the formulations for extensions.", "was_revised": true, "final_justification": "All my earlier comments have been adequately addressed. I appreciate the authors’ careful revisions and have raised my score as previously indicated.", "rebuttal": "Thanks for the feedback of our work. We will respond to your questions below.\n\n---\n\n**Q1.** While the achievability results are clearly presented, it is not clear that whether the proposed algorithm achieve optimal regrets besides the two special cases of $\\nu=0,1$ as no lower bounds were formally presented as theorems or remarks. If no lower bound is provided, the authors should not claim in the abstract that the proposed algorithm is optimal.\n\n**A1.** Thank you for your suggestion. Although the regret bound of $O(\\sqrt{V_T}+T^{\\frac{1-\\nu}{2}})$ proposed in Theorem 1 has not been proven optimal, there are two noteworthy points: 1) this bound is optimal in the two special cases $\\nu=0$ and $\\nu=1$; and 2) the online adaptivity in Theorem 1 can be used to obtain the convergence rate in Theorem 2, which is known to be optimal [1]. We will remove the word \"optimal\" from Line 8, and focus on investigating the lower bound of the regret in future work. Thank you for your suggestion to improve the rigor of our paper.\n\n[1] Y. Nesterov. \"Universal gradient methods for convex optimization problems\"\n\n---\n\n**Q2.** According to the discussion provided by the author, the extended result to SCO seems to be already known in Rodomanov et al 2024 [2].\n\n**A2.** Thanks for the comment. Although two works share some similarities, **we differ from them both in techniques and results.**\n\n**Similarities:** In terms of the algorithm, we both use a *decreasing adaptive step size* and apply *gradient evaluation on weighted averaged iterates*. In analysis, we both adopt the approach of treating Hölder smoothness as inexact smoothness (as shown in Lemma 1), introducing a virtual $(\\delta, L)$ to facilitate the final tuning.\n\n**Differences**: \n\n- Techniques: In our analysis, we **explicitly decouple** the two algorithmic components — adaptive step size and gradient evaluation on weighted averaged iterates. We associate the former with achieving smoothness adaptivity in online learning (e.g., Theorem 1), and the latter with the online-to-batch conversion [3], which transforms online learning regret into convergence rates for offline optimization. This makes our proof highly intuitive and has inspired us to **extend this approach to strongly convex optimization**, achieving guarantees (Theorem 4) that significantly improve upon existing results [4]. In contrast, Rodomanov et al. [2] employ a potential-based analysis method without decoupling these two algorithmic components.\n\n- Results: **The bound we obtain for the final tuning $\\delta$ differs from theirs**. Specifically, they derive $O(\\frac{LD^2}{T^2}+{\\color{red}\\delta T}+\\frac{\\sigma D}{\\sqrt{T}})$, whereas we obtain $O(\\frac{LD^2}{T^2}+{\\color{red}\\frac{D\\sqrt{L\\delta}}{\\sqrt{T}}}+\\frac{\\sigma D}{\\sqrt{T}})$. This, to some extent, serves as evidence that our analyses differ.\n\n[2] Universality of adagrad stepsizes for stochastic optimization: Inexact oracle, acceleration and variance reduction, NeurIPS 2024  \n\n[3] Anytime online-to-batch, optimism and acceleration, ICML 2019  \n\n[4] Online to offline conversions, universality and adaptive minibatch sizes, NIPS 2017\n\n---\n\n**Q3.** The formulation and assumptions in this work can be better clarified. For instance, while OCO is a well known framework, it is recommended to still provide a brief and concrete description before introducing the formulations for extensions.\n\n**A3.** Thank you for your suggestion. In the next version, we will provide readers with a brief and concrete review of the OCO framework before introducing the more complex regret measures and the extension of online-to-batch conversion.\n\n---\n\n**Q4.** While the submitted work covers a wide range of extended settings, the explicit formulations in this work contain limitations that were not clearly stated. For instance, in the extension of SCO the authors focused on the settings of first-order oracles, while there has been extensive works on zeroth-order optimization, which has different fundamental sample complexities. The authors also focused on Hölder conditions with $\\nu\\le 1$, while there are works that explores higher-order smoothness conditions. To name a few, see the references at the end, which are by no means exclusive. We recommend the authors to clarify these limitations, and briefly mention if the proposed results can be extended to those settings.\n\n**A4.** Thank you for your suggestion! The direction you proposed, namely zeroth-order SCO under higher-order smoothness, is indeed a potential avenue for further development. We believe that one possible approach is to incorporate a higher-order smoothness form into the gradient variation within the step size design of Eq. (9). This not only retains the adaptivity brought by the adaptive step size decay but also leverages the information from higher-order smoothness, thereby better complementing zeroth-order SCO. In the next version, we will add the following statements:\n\n- In the Introduction section, when presenting the optimization setting (Line 44 and onward), we will emphasize that it is first-order optimization. At the end of the this section, we will add information about zeroth-order optimization and higher-order smoothness:  \n  > \"In addition to the first-order optimization studied in this paper, the zeroth-order stochastic optimization field is also considering a more general class of smooth settings, namely higher-order smoothness [5,6,7,8,9], which could serve as a potential extension of the methods proposed in this paper.\"\n- In the conclusion section, we will discuss the potential application of the method proposed in this paper to zeroth-order optimization in the future directions part:\n  > \"The adaptivity demonstrated by the method in this paper, with appropriate design, also has the potential to be applied to zeroth-order stochastic optimization under higher-order smoothness conditions.\"\n  >\n\n\n\n[5] Bach and Perchet. \"Highly-smooth zero-th order online optimization\"\n\n[6] Akhavan et al. \"Exploiting higher order smoothness in derivative-free optimization and continuous bandits\"\n\n[7] Novitskii and Gasnikov. \"Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit\"\n\n[8] Yu et al. \"Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity\"\n\n[9] Akhavan and Tsybakov. \"Gradient-free stochastic optimization for additive models\"  \n\n---\n\n**Additional explanation.** We sincerely appreciate your attention to the convex function setting in our paper (i.e., Theorems 1 and 2). We also recommend paying attention to our progress on strongly convex offline optimization, i.e., **Theorem 4**. It is very challenging to develop an algorithm that can adapt to the smoothness level to achieve accelerated convergence while simultaneously guaranteeing nearly optimal convergence in the non-smooth case. To the best of our knowledge, the most recent results date back to the 2017 paper [4], which, however, only obtained a *non-accelerated* $O(\\exp(-T/\\kappa)\\cdot T/\\kappa)$ result for the smooth case. We improved this to an *accelerated and near-optimal* $O(\\exp(-T/(\\sqrt{\\kappa}\\cdot\\log \\kappa)))$ rate. And we are happy to provide further clarifications if needed during the following author-reviewer discussions.\n\n---\n\nIf our answers have solved your concerns, we would greatly appreciate it if you could consider a reevaluation of the score for our paper. We are happy to provide further explanations during the upcoming author-reviewer discussions if needed."}, {"review_id": "EbkHKE4QFW", "reviewer": "Reviewer_KXW6", "summary": "This paper studies online convex optimization under Holder smoothness, and shows that optimistic OGD can obtain $R_T\\le O(\\sqrt{\\sum_t\\sup_x\\\\|f_t(x)-f_{t-1}(x)\\\\|^2}+T^{\\frac{1-\\nu}{2}}+\\\\|\\nabla f_1(x_1)\\\\|)$ regret without any prior knowledge of the Holder smoothness parameters, and it is shown that this yields optimal rates in the stochastic optimization setting. The result is also extended to strongly-convex losses, to time-varying comparators (dynamic regret), and to universal regret.", "questions": "- Do you expect that the non-adaptive penalties can be improved to adaptive ones such as $V_T$ or $\\sum_t\\\\|g_t\\\\|^2$, or are the non-adaptive penalties unavoidable when adapting to the Holder smoothness parameters?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nThe main contribution in Theorem 1 is very nice and the analysis is very clean. The main tool is Lemma 1, which lets allows you to connect $\\\\|\\nabla f(x)-\\nabla f(y)\\\\|^2$ to $\\\\|x-y\\\\|^2$, similar to how you would with smooth losses, but with an additional $\\delta$ factor that appears only in the analysis and can therefore be tuned *a posteriori* at the end of the analysis. It's a very nice approach overall and leads to several extensions essentially \"for free\" after Theorem 1 is established.\n\n## Weaknesses\n\n**Universality**\n\nI think the insistence on defining methods as \"strongly universal\" will serve only to complicate the literature. For one, there are already other notions of universality, for instance Nesterov's Universal Algorithm, or in OCO algorithms which achieve guarantees on universal regret (as in Section 5.2) are sometimes referred to as being \"universal\".\n\nBut it is also more generally just a short-sighted naming convention. Intuitively, an algorithm should be deemed universal if it solves any problem in a problem class without manually adjusting any problem-dependent parameters; a practitioner should be able to just hit run and know the guarantee will hold. This is not the case here because the results depend on the diameter of the decision set. I think to really be able to call an algorithm universal here you'd have to develop a comparator-adaptive version. So let's suppose that you extend the approach here to achieve comparator adaptivity, what should we call such an algorithm? \"Extra Strongly Universal\"? \n\n**Loss of Adaptivity**\n\nThe key argument seems to unavoidably lead non-adaptive penalties (factors of $T$ instead of, say, $V_T$ or $\\sum_t\\\\|g_t\\\\|^2$) showing up in the bound. Prior works avoid such penalties from showing up, though they don't adapt to the Holder smoothness parameters; is it possible to improve the results here to achieve fully adaptive bounds? Or does adapting to the Holder smoothness parameters necessitate non-adaptive penalties? For example, the dynamic regret result in the Lipschitz losses setting ends up being $O(G\\sqrt{P_T T})$ instead of the usual $O(\\sqrt{P_T\\sum_t\\\\|g_t\\\\|^2})$.\n\n**Minor Weaknesses**\n\nThe main novelty is Theorem 1, and each of the extensions are generally very straight-forward afterwards. For example, the extension to stochastic optimization via anytime online-to-batch is well-known from Cutkosky 2019, and the result is basically immediate by combining the online-to-batch argument with Theorem 1. It is also well-known that gradient variation bounds imply improved regret under strong convexity, so these too are fairly easily obtained given Theorem 1, and obtaining the $\\sqrt{P_T T}$ dynamic regret bounds is also straight-forward once one has the static regret result.", "was_revised": true, "final_justification": "The main weaknesses were that there was essentially one novel result + several \"free\" ones. The author clarified the difficulties associated with some of the freebies, and theorem 4 seems to be significant. They clarified whether gradient adaptivity *must* be lost, and provided a partial result showing that some adaptivity can be retained, but opens some new questions to be addressed. Overall, well-written paper with a nice technique.", "rebuttal": "Thanks for the insightful feedback. Below, we will address your questions and clarify our contributions, hoping to address your concerns.\n\n---\n\n**Q1. Universality.** I think the insistence on defining methods as \"strongly universal\" will serve only to complicate the literature. For one, there are already other notions of universality, for instance Nesterov's Universal Algorithm, or in OCO algorithms which achieve guarantees on universal regret (as in Section 5.2) are sometimes referred to as being \"universal\".\n\n**A1.** Thank you for the comment. We indeed only adopt the two existing universal definitions (Nesterov's Universal, and universal in OCO) in our paper. The purpose of introducing Definition 1 (strong and weak universality) in this paper is to facilitate the distinction between the strengths of our methods' adaptability to smoothness. Our Theorem 2 achieves the traditional \"Nesterov's Universal,\" that is, adaptive to Hölder smoothness, while Theorem 4 currently only achieves adaptivity to both smooth and non-smooth cases. Therefore, to help readers differentiate, we refer to Theorem 2 as \"strongly universal\" and Theorem 4 as \"weakly universal.\" This definition is proposed merely for clarity and is not intended as a contribution of our work.\n\n---\n\n**Q2. Loss of Adaptivity.** The key argument seems to unavoidably lead non-adaptive penalties (factors of $T$ instead of, say, $V_T$ or $\\sum_t\\\\|g_t\\\\|^2$) showing up in the bound. Do you expect that the non-adaptive penalties can be improved to adaptive ones such as $V_T$ or $\\sum_t\\\\|g_t\\\\|^2$, or are the non-adaptive penalties unavoidable when adapting to the Hölder smoothness parameters?\n\n**A2.** Very nice question! Let's take the convex case as an example and see if we can improve our current bound $O(\\sqrt{V_T}+T^{\\frac{1-\\nu}{2}})$ to a more adaptive $O(\\sqrt{V_T}+{V_T}^{\\frac{1-\\nu}{2}})$ or $O(\\sqrt{V_T}+(\\sum_t\\\\|g_t\\\\|^2)^{\\frac{1-\\nu}{2}})$. First, it is clear that the $O(\\sqrt{V_T}+{V_T}^{\\frac{1-\\nu}{2}})$ bound is impossible, because when $\\nu=0$, i.e., in the non-smooth case, this bound becomes $O(\\sqrt{V_T})$, which is in fact not achievable. Therefore, we focus on the $O(\\sqrt{V_T}+(\\sum_t\\\\|g_t\\\\|^2)^{\\frac{1-\\nu}{2}})$ bound. The current conclusion is that we can establish an upper bound that is partially adaptive to $\\sum_t\\\\|g_t\\\\|^2$, but there are some additional components that are difficult to bound.\n\nWe consider still using a method similar to Theorem 1, with the only difference being that at each round $t$, we *no longer use the same global parameters* $(L,\\delta)$ when applying Lemma 1. Otherwise, we would unavoidably suffer a $T$ penalty, just like in the original proof.\n$$\n\\def \\x {\\mathbf{x}}\n\\begin{align*}\nReg_T&\\lesssim D\\sqrt{A_T} - \\sum_{t=2}^T\\frac{1}{\\eta_{t+1}}\\\\|\\x_t - \\x_{t-1}\\\\|^2\\tag{Eq. (20)} \\\\\\\\\n&\\lesssim D\\sqrt{A_{t_0}}+D\\sqrt{\\sum_{t=t_0+1}^T\\\\|\\nabla f_t(\\x_t)-\\nabla f_{t-1}(\\x_t)+\\nabla f_{t-1}(\\x_t)-\\nabla f_{t-1}(\\x_{t-1})\\\\|^2}-\\sum_{t=2}^T\\frac{1}{\\eta_{t+1}}\\\\|\\x_t - \\x_{t-1}\\\\|^2 \\\\\\\\\n&\\lesssim D\\sqrt{A_{t_0}}+D\\sqrt{V_T}+D\\sqrt{\\sum_{t=t_0+1}^T\\Big(L_t^2\\\\|\\x_t-\\x_{t-1}\\\\|^2+L_t\\delta_t\\Big)}-\\sum_{t=2}^T\\frac{1}{\\eta_{t+1}}\\\\|\\x_t - \\x_{t-1}\\\\|^2\\tag{Lemma 1} \\\\\\\\\n&\\lesssim D\\sqrt{A_{t_0}}+D\\sqrt{V_T}+D^2L_{\\max}+\\sum_{t=t_0+1}^T\\left(L_{\\max}-\\frac{1}{\\eta_{t+1}}\\right)\\\\|\\x_t - \\x_{t-1}\\\\|^2+D\\sqrt{\\sum_{t=t_0+1}^TL_t\\delta_t}\\tag{$L_{\\max}\\triangleq\\max_t L_t$} \\\\\\\\\n&\\lesssim D\\sqrt{V_T}+D^2L_{\\max}+DL_\\nu^{\\frac{1}{1+\\nu}}\\sqrt{\\sum_{t=t_0+1}^T\\delta_t^{\\frac{2\\nu}{1+\\nu}}}.\\tag{By a case-by-case analysis}\n\\end{align*}\n$$\nIn the last inequality above we also apply that for any $\\delta_t>0$, $L_t=\\delta_t^{\\frac{\\nu-1}{1+\\nu}}L_\\nu^{\\frac{2}{1+\\nu}}$. To ultimately achieve the desired adaptive bound, we select $\\delta_t=\\delta\\\\|g_t\\\\|^{\\frac{1+\\nu}{\\nu}}$ (with $0<\\nu\\le 1$) and then proceed with our derivation:\n$$\n\\def \\x {\\mathbf{x}}\n\\begin{align*}\nReg_T&\\lesssim D\\sqrt{V_T}+D^2L_\\nu^{\\frac{2}{1+\\nu}}\\delta^{\\frac{\\nu-1}{1+\\nu}}G_{\\min}^{\\frac{\\nu-1}{\\nu}}+DL_\\nu^{\\frac{1}{1+\\nu}}\\delta^{\\frac{\\nu}{1+\\nu}}\\sqrt{\\sum_{t=1}^{T}\\\\|g_t\\\\|^2}\\tag{$G_{\\min}\\triangleq\\min_t\\\\|g_t\\\\|$} \\\\\\\\\n&\\lesssim D\\sqrt{V_T}+L_\\nu G_{\\min}^{\\nu-1}D^{1+\\nu}\\left(\\sum_{t=1}^{T}\\\\|g_t\\\\|^2\\right)^{\\frac{1-\\nu}{2}}.\\tag{Tuning $\\delta$}\n\\end{align*}\n$$\nObviously, this result has a drawback: there is a $(\\min_t\\\\|g_t\\\\|)^{\\nu-1}$ term that cannot be bounded. This may be because, in order to obtain an adaptive bound, we use different $(\\delta_t, L_t)$ for each round, which contradicts the requirement for a global constant $L$ in the case-by-case analysis technique [1]. We currently do not know how to resolve this issue, and it is also possible that when adapting to the Hölder smoothness parameters, these non-adaptive penalties are unavoidable. Thank you for your very valuable question! We will mention it in the next version of the paper.\n\n[1] UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization, NeurIPS 2019\n\n---\n\n**Q3. Minor Weaknesses.** The main novelty is Theorem 1, and each of the extensions are generally very straight-forward afterwards. For example, the extension to stochastic optimization via anytime online-to-batch is well-known from Cutkosky 2019, and the result is basically immediate by combining the online-to-batch argument with Theorem 1. It is also well-known that gradient variation bounds imply improved regret under strong convexity, so these too are fairly easily obtained given Theorem 1, and obtaining the $\\sqrt{P_T T}$ dynamic regret bounds is also straight-forward once one has the static regret result.\n\n**A3.** Thanks for the comment. Below, we will explain the contributions of our theorems with some noteworthy points.\n\n1. **About Theorem 2:** It matches the 2024 state-of-the-art results [2]. A key point here is that: due to the power of our Theorem 1, when combined with the anytime online-to-batch conversion, we can achieve state-of-the-art results in stochastic convex optimization. Our intention is not to claim the result of Theorem 2 as our main contribution, but to illustrate the power of Theorem 1.\n2. **About Theorem 3:** The method and the corresponding analysis for the strongly convex setting also builds upon our advancements in the convex setup, and the obtained result is new for this problem as well. It demonstrates that the step size structure $\\eta_t\\propto 1/t$ inherently possesses strong adaptivity.\n3. **About Theorem 4:** This is the **most challenging** theorem in this paper. Due to the page constraints of the main part, this theorem was not emphasized enough. In terms of results, we significantly improved upon the most recent results [3], which date back to 2017, and achieved an *accelerated and near-optimal* convergence rate. And we believe the techniques used are sufficiently innovative and worth the readers' attention. More explanations will be provided at the end of this rebuttal.\n4. **About Theorem 5:** It is quite interesting in terms of the result $O(\\sqrt{V_T P_T}+P_T^{\\frac{1+\\nu}{2}}T^{\\frac{1-\\nu}{2}})$. Although we know that the $O(\\sqrt{TP_T})$ bound is worst-case optimal [4], whether the gradient variation bound $O(\\sqrt{V_TP_T}+P_T)$ is optimal remains an open problem, especially regarding the term $P_T$ [5]. However, no one had known the interpolation of these two bounds before, and we are the first to achieve it, providing a new perspective on this problem. Technically, we avoid the previous approach of using *fixed* step sizes for the base learners and instead implement a more refined algorithm design with adaptive step sizes to achieve adaptivity to smoothness.\n5. **About Theorem 6:** It demonstrates that the work [6] actually possesses stronger adaptivity to smoothness.\n\n[2] Universality of adagrad stepsizes for stochastic optimization: Inexact oracle, acceleration and variance reduction, NeurIPS 2024\n\n[3] Online to offline conversions, universality and adaptive minibatch sizes, NIPS 2017\n\n[4] Adaptive online learning in dynamic environments, NeurIPS 2018\n\n[5] Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization, JMLR 2024\n\n[6] A simple and optimal approach for universal online learning with gradient variations, NeurIPS 2024\n\n---\n\n**Additional explanation for Theorem 4.** We introduce the challenges encountered in the algorithm and analysis, hoping to provide you with a better understanding of the contributions of this theorem.\n\n- **Algorithmically:** In the strongly convex setting, there is no equivalent adaptive step size or corresponding structure. Therefore, the originally used case-by-case analysis technique [1] can no longer be applied to handle unknown smoothness. To this end, we designed a smoothness estimation method and maintained it using the classic doubling technique in case of inaccurate estimation, as we can calculate the empirical smoothness parameter at the end of each iteration.\n\n- **Technically:** In the analysis, we encountered a significant challenge. The inaccurate estimation means cancellations cannot be performed in the analysis, which directly adds a *constant* to the convergence rate, causing the convergence rate in the earlier iterations to seem almost invalidated. Therefore, we turn to consider proving *best-iterate convergence*, and examine when each constant term appears and when it can be optimized to a sufficiently small value. We also employ some relatively novel constructive approaches.\n\n\n---\n\nIf our answers have solved your concerns, we would greatly appreciate it if you could consider a reevaluation of the score for our paper. We are happy to provide further explanations during the upcoming author-reviewer discussions if needed."}, {"review_id": "sLu3bgfjLt", "reviewer": "Reviewer_Agbt", "summary": "The paper develops algorithms for online convex optimization and offline optimization under Hölder smoothness and convexity or strong convexity. Several algorithms are proposed, versions of optimistic gradient descent without and with round weights, and a meta-level learning algorithm. The algorithm does not have to know the class, and it yields optimal bounds in terms of the gradient variation.\n\n\nLet me go into a bit more detail on how the results are achieved.\n\nTheorems 1 and 3 rely on \n(a) the optimistic OMD analysis, resulting in gradient variation appearing plus negative movement terms.\n(b) the Hölder-to-quadratic-plus-overhead inequality\n(c) decaying learning rate schedule, so that it eventually the negative terms from (a) start helping.\n\nThese are all well-known techniques. The contribution of this paper is to show that they can be chained together even in intermediate smoothness regimes i.e. nu in (0,1) and while retaining the gradient variation in the answer.\n\nThe results are then applied and extended for offline stochastic optimization, and for dynamic and universal regret.", "questions": "Can you relate to the techniques in Wang and Abernethy 2018, Acceleration through Optimistic No-Regret Dynamics?\n\nThe presentation of \"universality\" in online learning is not quite accurate. Going back to van Erven et al (2016), universality is adaptivity to the curvature parameter *without knowing it*. The paper under review instead adapts to a fixed given \\lambda or \\lambda=0. Wang et al (2019) show how to adapt to the strong convexity parameter (\\lambda in the paper under review) without knowing it up-front. Would their approach (of combining multiple learning rates) extend to your setting, and deliver adaptivity to any \\lambda without knowing it? That seems like a desirable and within-reach extension.\n\nThe universal regret result in Theorem 6 has a *better* exponent on log(T) than the \"just-strongly convex\" result in Theorem 3. This is strange. What is the catch? Why would we be satisfied with Theorem 3?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality:\nThe achieved adaptivity result is an accomplishment.\n\nClarity:\nThe paper is well written and organized clearly. The results are compared to the existing literature.\n\nSignificance:\nI think this paper will be remembered for its Theorem 6. I find it positively amazing that the Hölder smoothness constants are not required for tuning the algorithm.\n\nOriginality:\nThe paper presents a tighter analysis of an existing algorithm.", "was_revised": true, "final_justification": "I am satisfied with the answers. I hope that the comparison from the rebuttal with the Abernethy et al paper ends up in the paper. The universality claim was my confusion. I hope that the authors can prevent this with a minor adjustment of wording. Finally, I am happy with the authors explanation as to why a better possible dependence on log(T) is possible, and I'm confident they'll implement it.", "rebuttal": "Thanks for the positive feedback and appreciation of our work! Below we answer your questions and highlight some noteworthy technical contributions of our work. \n\n---\n\n**Q1.** Can you relate to the techniques in Wang and Abernethy 2018, Acceleration through Optimistic No-Regret Dynamics?\n\n**A1.** Thank you for your reminder! Below is a comparison of the techniques used in the two papers:\n\n**Similarities:** Both Paper [1] and ours utilize an important technique named gradient evaluation on weighted averaged iterates. This technique, combined with smoothness, effectively controls the gradient variation of the optimistic algorithm, and together with negative movement terms, ultimately achieves the accelerated optimization results present in both papers. We will emphasize the connection between our work and theirs [1] regarding this technique in the revised version of the paper.\n\n**Differences:**\n\n- The two papers have different starting points. Our paper starts from online-to-batch conversion [2], applying the adaptivity of online algorithms to offline accelerated optimization; whereas Paper [1] approaches the problem from a game perspective. Both are interesting applications of the optimistic method in online optimization.\n- We not only focus on achieving accelerated optimization but also pay special attention to *adaptively handling unknown smoothness levels*. Theorem 2 presents results adaptive to Hölder smoothness in the convex setting. Theorem 4 provides results adaptive to both smooth and non-smooth cases under the strongly convex setting, which is more challenging. We believe these distinctions are also highly worthy of attention and discussion.\n\n\n\n[1] Wang and Abernethy 2018, Acceleration through Optimistic No-Regret Dynamics \n\n[2] Anytime online-to-batch, optimism and acceleration, ICML 2019\n\n---\n\n**Q2.** The presentation of \"universality\" in online learning is not quite accurate. Going back to van Erven et al (2016), universality is adaptivity to the curvature parameter without knowing it. The paper under review instead adapts to a fixed given $\\lambda$ or $\\lambda=0$. Wang et al (2019) show how to adapt to the strong convexity parameter ($\\lambda$ in the paper under review) without knowing it up-front. Would their approach (of combining multiple learning rates) extend to your setting, and deliver adaptivity to any $\\lambda$ without knowing it? That seems like a desirable and within-reach extension.\n\n**A2.** Thanks for the question. The problem we are studying here is precisely what was investigated in the previous research on universal online learning. The statement \"The paper under review instead adapts to a fixed given $\\lambda$ or $\\lambda=0$.\" may stem from some misunderstandings of the paper. The notation of \"universal regret\" in this paper, i.e., $\\text{U-Reg}({\\cal F})$, means adapts to unknown function class $\\cal F$ which is either convex or strongly convex with **unknown** curvature $\\lambda$. Readers might mistakenly interpret ${\\cal F}\\in\\\\{{\\cal F} _c,{\\cal F} _{sc}^\\lambda\\\\}$ that the strong convexity curvature $\\lambda$ is known. And as presented in Algorithm 3, page 24, the algorithm only requires domain diameter $D$ and total iterations $T$, without any curvature $\\lambda$. Moreover, this algorithm exactly uses the approach of combining multiple learning rates as expected by the reader, and indeed achieves a favorable result.\n\n---\n\n**Q3.** The universal regret result in Theorem 6 has a better exponent on $\\log(T)$ than the \"just-strongly convex\" result in Theorem 3. This is strange. What is the catch? Why would we be satisfied with Theorem 3?\n\n**A3.** This is a very nice observation! **The conclusion is that we can indeed obtain an $(\\log T)^{\\frac{1-\\nu}{1+\\nu}}$ term in Theorem 3.** The reason for the difference — that is, the exponent difference between the $(\\log T)^{1-\\nu}$ term in current Theorem 3 and the $(\\log T)^{\\frac{1-\\nu}{1+\\nu}}$ term in Theorem 6 — is because different *positive and negative cancellation* techniques were used in the proofs of the two theorems, respectively.\n\n- In Theorem 3, we used **Lemma 1**, i.e., $\\\\|\\nabla f({\\bf x})-\\nabla f({\\bf y})\\\\|^2\\lesssim L^2\\\\|{\\bf x-y}\\\\|^2+L\\delta$. And we used the negative movement terms $-\\sum _t\\\\|{\\bf x} _t - {\\bf x} _{t-1}\\\\|^2$ to handle the positive terms arising from the decomposition of empirical gradient variation:\n  $$\n  \\def \\x {\\mathbf{x}}\n  \\begin{align*}\n  \\\\|\\nabla f _t(\\x _t) - \\nabla f _{t-1}(\\x _{t-1})\\\\|^2 &\\lesssim \\\\|\\nabla f _t(\\x _t) - \\nabla f _{t-1}(\\x _t)\\\\|^2 + \\\\|\\nabla f _{t-1}(\\x _t) - \\nabla f _{t-1}(\\x _{t-1})\\\\|^2 \\\\\\\\\n  &\\lesssim \\sup _{\\x} \\\\|\\nabla f _t(\\x) - \\nabla f _{t-1}(\\x)\\\\|^2 + L^2\\\\|\\x _t - \\x _{t-1}\\\\|^2 + L\\delta. \\tag*{(by Lemma 1)}\n  \\end{align*}\n  $$\n\n- In Theorem 6, we used **Lemma 4**, i.e., $\\\\|\\nabla f({\\bf x})-\\nabla f({\\bf y})\\\\|^2\\lesssim L{\\cal D} _f({\\bf y,x})+L\\delta$. And we used the Bregman negativity from linearization $-{\\cal D} _{f _t}({\\bf x} _\\star, {\\bf x} _t)$ to handle the positive terms arising from the decomposition of empirical gradient variation:\n  $$\n  \\def \\x {\\mathbf{x}}\n  \\def \\xs {\\x _\\star}\n  \\begin{align*}\n  \\\\|\\nabla f _t(\\x _t) - \\nabla f _{t-1}(\\x _{t-1})\\\\|^2 &\\lesssim \\\\|\\nabla f _t(\\xs) - \\nabla f _{t-1}(\\xs)\\\\|^2 + \\\\|\\nabla f _t(\\x _t) - \\nabla f _t(\\xs)\\\\|^2 + \\\\|\\nabla f _{t-1}(\\x _{t-1}) - \\nabla f _{t-1}(\\xs)\\\\|^2 \\\\\\\\\n  &\\lesssim \\sup _{\\x} \\\\|\\nabla f _t(\\x) - \\nabla f _{t-1}(\\x)\\\\|^2 + L{\\cal D} _{f _t}(\\xs, \\x _t) + L{\\cal D} _{f _{t-1}}(\\xs, \\x _{t-1}) + L\\delta. \\tag*{(by Lemma 4)}\n  \\end{align*}\n  $$\n\nIt can be proven that by using the cancellation from Theorem 6, we can indeed upgrade $(\\log T)^{1-\\nu}$ to $(\\log T)^{\\frac{1-\\nu}{1+\\nu}}$ in Theorem 3 without modifying the algorithm. We will update Theorem 3 to reflect better results in the revised version of the paper. This reflects an interesting insight: we know that, in the smoothness inequality, the form presented in Lemma 1 is indeed looser than that in Lemma 4, and this difference is reflected in the final results of our analysis of Hölder smoothness.\n\n---\n\n**Additional explanation.** We would also kindly ask you to pay attention to our progress on strongly convex offline optimization, i.e., **Theorem 4**. It is very challenging to develop an algorithm that can adapt to the smoothness level to achieve accelerated convergence while simultaneously guaranteeing nearly optimal convergence in the non-smooth case. To the best of our knowledge, the most recent results date back to the 2017 paper [3], which, however, only obtained *non-accelerated* $O(\\exp(-T/\\kappa)\\cdot T/\\kappa)$ result for the smooth case. We improved this to an *accelerated and near-optimal* $O(\\exp(-T/(\\sqrt{\\kappa}\\cdot\\log \\kappa)))$ rate. And we believe the techniques used are sufficiently innovative and worth the readers' attention. We are happy to provide further explanations if needed during the following author-reviewer discussions!\n\n[3] Online to offline conversions, universality and adaptive minibatch sizes, NIPS 2017"}, {"review_id": "ZfBUDIkUIs", "reviewer": "Reviewer_BMFE", "summary": "This paper studies regret bounds with gradient variation in the context of online learning.\n\nIt first extends existing regret bounds by incorporating gradient variation terms when the loss functions are Hölder smooth and Lipschitz continuous. The authors then provide an online-to-batch conversion technique that yields accelerated convergence rates of order $O(T^{-2})$ for smooth functions, thereby generalizing existing results. A key strength of the method is its universality—it does not require prior knowledge of the Lipschitz or smoothness constants.\n\nThe authors further extend their results to the strongly convex setting, deriving regret bounds and corresponding accelerated online-to-batch conversion rates. However, in this case, the method is not fully universal, as it requires prior knowledge of the strong convexity parameter. Additionally, the obtained rates are slightly suboptimal when the Lipschitz constant is unknown.\n\nFinally, the authors design a meta-algorithm that achieves dynamic regret bounds with gradient variation when the loss functions are Lipschitz and Hölder smooth. They also propose an algorithm that adapts to unknown strong convexity parameter.", "questions": "1. Could the authors elaborate on the specific challenges involved in extending the online-to-batch conversion to the stochastic setting in the strongly convex case? Are there particular obstacles that prevent a direct extension of the techniques used in the smooth or convex cases?\n\n2. Is it possible to obtain an online-to-batch conversion for Theorem 6 in the case where the curvature parameter (i.e., the strong convexity constant) is unknown? If not, could the authors comment on what makes this technically difficult or whether a universal algorithm could adapt to unknown curvature in this setting?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well written and presents a clearly motivated framework, relevant to both online learning and convex optimization. It offers a substantial analysis of regret bounds incorporating gradient variation for Hölder smooth functions, providing a range of results that either improve upon existing work (by requiring fewer parameter assumptions) or generalize it (by considering Hölder smoothness with a generic parameter $\\nu$). These contributions add breadth and flexibility to the theory of learning with smooth losses.\n\nWeaknesses:\n\nIt is not entirely clear to what extent the results go beyond incremental generalizations of existing work—primarily extending known analyses from $\\nu = 1$ (standard smoothness) to a generic Hölder smoothness parameter $\\nu$. Could the authors clarify what technical challenges were encountered and how they were addressed in order to extend the results? For example, the analysis in Theorem 1 appears to follow standard Optimistic OMD techniques, and the online-to-batch conversion arguments seem to closely mirror those in [Cutkosky, 2019].", "was_revised": true, "final_justification": "I read other reviews and rebuttal. The authors address well my concerns and no reviewer seem to raise major weakness. I lean toward acceptance and raise my score to 5.", "rebuttal": "Thank you for the valuable feedback. Below, we will respond to your questions and clarify our contributions in hopes of addressing your concerns.\n\n---\n\n**Q1.** It is not entirely clear to what extent the results go beyond incremental generalizations of existing work—primarily extending known analyses from $\\nu=1$ (standard smoothness) to a generic Hölder smoothness parameter $\\nu$. Could the authors clarify what technical challenges were encountered and how they were addressed in order to extend the results? For example, the analysis in Theorem 1 appears to follow standard Optimistic OMD techniques, and the online-to-batch conversion arguments seem to closely mirror those in [Cutkosky, 2019].\n\n**A1.** Thanks for the comment. Below, we will explain the contributions of ours. There are some noteworthy points, such as Theorem 4.\n\n**Results:**\n\n- **About Theorem 1,3,5,6:** These regret bounds interpolated through the Hölder smoothness parameters $(L_\\nu, \\nu)$ are novel and meaningful. They bridge the classic gradient variation bound and worst-case bound, and for the first time, demonstrate a connection between these two types of bounds across various settings (convex, strongly convex, dynamic regret, and universal).\n- **About Theorem 4:** It is particularly noteworthy. It is very challenging to develop an algorithm that can adapt to the smoothness level to achieve accelerated convergence while simultaneously guaranteeing nearly optimal convergence in the non-smooth case. To the best of our knowledge, the most recent results date back to the 2017 paper [1], which, however, only obtained a *non-accelerated* $O(\\exp(-T/\\kappa)\\cdot T/\\kappa)$ rate for the smooth case. We improved this to an *accelerated and near-optimal* $O(\\exp(-T/(\\sqrt{\\kappa}\\cdot\\log \\kappa)))$ rate.\n\n**Techniques:**\n\n- We applied the adaptive step size and a case-by-case analysis technique [2] to gradient variation online learning (where previous works often required the algorithm to explicitly know the smoothness parameter $L$ for clipping the step size), and further extending it to the Hölder smooth setting. We also avoid the explicit requirement for smoothness $L$ in optimizing dynamic regret that was present in previous works [3].\n\n- **Theorem 4 is, in fact, the most challenging part of this paper.** Due to the page constraints of the main part, this theorem was not emphasized enough. And we believe the techniques used are sufficiently innovative and worth the readers' attention. We briefly introduce the challenges encountered in the algorithm and analysis.\n\n  1. **Algorithmically:** In the strongly convex setting, there is no equivalent adaptive step size or corresponding structure. Therefore, the originally used case-by-case analysis technique [2] can no longer be applied to handle unknown smoothness. To this end, we designed a smoothness estimation method and maintained it using the classic doubling technique in case of inaccurate estimation, as we can calculate the empirical smoothness parameter at the end of each iteration.\n\n  2. **Technically:** In the analysis, we encountered a significant challenge. The inaccurate estimation means cancellations cannot be performed in the analysis, which directly adds a *constant* to the convergence rate, causing the convergence rate in the earlier iterations to seem almost invalidated. Therefore, we turn to consider proving *best-iterate convergence*, and examine when each constant term appears and when it can be optimized to a sufficiently small value. We also employ some relatively novel constructive approaches.\n\n\n\n\n[1] Online to offline conversions, universality and adaptive minibatch sizes, NIPS 2017\n\n[2] UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization, NeurIPS 2019\n\n[3] Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization, JMLR 2024\n\n---\n\n**Q2.** Could the authors elaborate on the specific challenges involved in extending the online-to-batch conversion to the stochastic setting in the strongly convex case? Are there particular obstacles that prevent a direct extension of the techniques used in the smooth or convex cases?\n\n**A2.** Your attention to this gap is very important! As we demonstrated in A1 regarding the challenges and solutions of Theorem 4, the techniques for achieving adaptivity to unknown smoothness in the strongly convex case are, in fact, *completely different* from those in the convex case. As presented in Section 4.2 of our paper, to achieve this result in the strongly convex case, we designed a smoothness observation $L _t$ to guide the updates of our smoothness estimator $\\hat{L} _t$. Once we find that the estimator $\\hat{L} _t$ is inaccurate, we double it so that it can adaptively approach the underlying smoothness parameter $L _\\ell$. The key to this approach is that we have the property $L _t \\leq L _\\ell$, which ensures that the number of times $\\hat{L} _t$ is doubled is limited. However, in the stochastic setting, we can currently only obtain $E[L _t] \\leq L _\\ell$, which may cause the estimator $\\hat{L} _t$ to be excessively large due to noise-induced inaccuracies, ultimately harming our convergence rate. Solving this problem is highly non-trivial and thus beyond the scope of this work and we leave it as an important work for future exploration.\n\n---\n\n**Q3.** Is it possible to obtain an online-to-batch conversion for Theorem 6 in the case where the curvature parameter (i.e., the strong convexity constant) is unknown? If not, could the authors comment on what makes this technically difficult or whether a universal algorithm could adapt to unknown curvature in this setting?\n\n**A3.** Thanks for the question. To the best of our knowledge, applying ensemble techniques like Theorem 6 to solve offline optimization problems with unknown strong convexity curvature is feasible under Lipschitz conditions. However, under smoothness, since the online-to-batch weights $\\alpha _t$ require the knowledge of curvature $\\lambda$, which cannot be addressed using universal online learning, solving this problem is challenging and we leave it as a future direction.\n\n---\n\nIf our answers have solved your concerns, we would greatly appreciate it if you could consider a reevaluation of the score for our paper. We are happy to provide further explanations during the upcoming author-reviewer discussions if needed."}]

Author rebuttal:

Meta-review: This paper investigates online learning with Holder smooth functions. Their main result, Theorem 1, shows that optimistic OGD can obtain a regret $O(D \sqrt{\sum_{x \in X} || \grad f_t(x) - \grad f_{t-1}(x) ||^2 } + L_v D^{1+\nu} T^{(1-\nu)/2} + D || \grad f_1(x_1) ||) on (L_v, v)-holder smooth functions. This result does not require knowledge of v or L_v but does require a domain bound D. This improves over previous online learning bounds for Holder smooth functions.

From this result they are able to achieve several interesting theorems establishing the optimality of optimistic OGD with holder smooth functions in (i) the stochastic setting and (ii) the strongly convex setting.  

Minor comment: there appears to be a typo in Theorem 1, in the big-O term L should be L_v
Decision: Accept (spotlight)