Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
Authors: Yu-Hu Yan
Peng Zhao
Zhi-Hua Zhou
Venue: NeurIPS 2025 poster ()
Keywords: offline optimization
convex optimization
online-to-batch conversion
acceleration
Primary area: optimization
TL;DR: We propose new optimistic online-to-batch conversions for acceleration and universality.

Abstract: In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (**NAG**) method achieves the optimal accelerated convergence. Extensive research has aimed to understand **NAG** from various perspectives, and a recent line of work approaches this from the viewpoint of online learning and online-to-batch conversion, emphasizing the role of *optimistic online algorithms* for acceleration. In this work, we contribute to this perspective by proposing novel *optimistic online-to-batch conversions* that incorporate optimism theoretically into the analysis, thereby significantly simplifying the online algorithm design while preserving the optimal convergence rates. Specifically, we demonstrate the effectiveness of our conversions through the following results: *(i)* when combined with simple online gradient descent, our optimistic conversion achieves the optimal accelerated convergence; *(ii)* our conversion also applies to strongly convex objectives, and by leveraging both optimistic online-to-batch conversion and optimistic online algorithms, we achieve the optimal accelerated convergence rate for strongly convex and smooth objectives, for the first time through the lens of online-to-batch conversion; *(iii)* our optimistic conversion can achieve universality to smoothness~---~applicable to both smooth and non-smooth objectives without requiring knowledge of the smoothness coefficient~---~and remains efficient as non-universal methods by using only one gradient query in each iteration. Finally, we highlight the effectiveness of our optimistic online-to-batch conversions by a precise correspondence with **NAG**.

Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology, Nanjing University, China School Artificial Intelligence, Nanjing University, China (yanyh, zhaop, zhouzh)@lamda @lamda.
Abstract
In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (NAG) method achieves the opti- mal accelerated convergence. Extensive research has aimed to understand NAG from various perspectives, and recent line of work approaches this from the viewpoint of online learning and online-to-bated conversion, emphasizing the role of optimistic online algorithms for acceleration. In this work, we contribute to this perspective by proposing novel optimistic online-to-batch conversions that incorporate optimism theoretically into the analysis, thereby significantly sim- plifying the online algorithm design while preserving the optimal convergence rates. Specifically, we demonstrate the effectiveness of our conversions through the following results: (i) when combined with simple online gradient descent, our optimistic conversion achieves the optimal accelerated convergence; (ii) our conversion also applies to strongly convex objectives, and by leveraging both opti- mistic online-to-bated conversion and optimistic online algorithms, we achieve the optimal accelerated convergence rate for strongly convex and smooth objectives, for the first time through the lens of online-to-batte conversion; (iii) our optimistic conversion can achieve universality smoothness applicable to both smooth and non-smooth objectives without requiring knowledge the smoothness coeffi- cient and remains efficient non-universal methods by using only one gradient query each iteration. Finally, we highlight the effectiveness of our optimistic online-to-batch conversions by precise correspondence with NAG.
Introduction
Convex optimization [Boyd and Vandenberghe, 2004, Nesterov, 2018] is a core problem in optimiza- tion theory. Its simple theoretical foundations and algorithms have made it essential for solving wide range of real-world problems. Specifically, we focus on the simplest and most standard form:
min f(x), XEX
where f(-) is convex objective function and I2d is the feasible domain. In this paper, focus on the function-value convergence. Specifically, we aim to minimize the suboptimality gap f(Xr)- minxex (x), where Xx denotes the final output of algorithm after T iterations.
1.1 Accelerated Convergence
When the objective function f(-) is Lipschit--oottiuuuus the simple Gradient Descent (GD) is sufficient to achieve the optimal convergence rates, specifically, (1/21 for convex functions and
"Correspondence: Peng Zhao <zhaop@@amdanjuuuduu.o
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

O(T"1) for strongly convex functions [Nemirovski and Yudin, 1983]. However, GD is still not fully capable of handling convex smooth optimization.
In convex smooth optimization, the pioneering Nesterov's Accelerated Gradient method (NAG) [Nes-
terov, 1983, 2018] achieves accelerated and optimal convergence rate of ( NAG consists of two steps - gradient descent step and an extrapolation step, formalized below:
xxx 2--1 02 V (2)-1)) 2, y: + (y yz-1),
where [xx[:] represents the Euclidean projection onto X, is the extrapolation parameter and O, denotes the step size. NAG with carefully chosen parameters is able to achieve the optimal conver- gence rate of ()T-2) for convex functions and O(exp(-T/vvi) for strongly convex functions. respectively, where x. represents the condition number [Nesterov, 1983].
1.2 Online-to-Batcl Conversion for Acceleration
Due to the significant success of NAG and acceleration methods, numerous studies have sought to understand them from various perspectives, including ordinary differential equations [Su et al., 2016], game theory [ [Wang and Abernethy, 2018], and online learning [Cutkosky, 2019], among others. In this work, we focus on understanding NAG and acceleration from the perspective of online learning.
From the online learning perspective, a classic approach is through the well-known online-to-batch conversion (O2B conversion) (Cesa-Bianchi al., 2004, Shalev-Shwarke 2012], which leverages online learning algorithms [Hazan, 2016, Orabona, 2019] to address offline optimization tasks. Formally, online learning is a versatile framework that models the interaction between learner and the environment over time. In the t-th round, the learner selects decision w, from convex compact set W C TR. Simultaneously, the environment adversarially chooses a convex loss function 4: :-WW- - RR. Subsequently, the learner incurs a loss (w:)), receives feedback of the function & (-). and updates her decision Wt+1- online learning, the learner aims to minimize the game-theoretic performance measure known as regret [Cesa-Bianch) Bianchi and Lugosi, 2006], which is formally defined as
T Σ (e(w)) min WEW
REGT A
Σ ((w).
It represents the learner's 's excess cumulative loss compared with the best fixed comparator in hindsight.
The vanilla O2B conversion is able to achieve the optimal convergence rate for convex Lipschitz-- continuous objectives via black-box use of online learning algorithms. For example, the simple online gradient descent IZinkevich, 2003] along with the 02B conversion is sufficient to achieve the optimal rate of O(T [Nemirovski and Yudin, 1983].
While the vanilla conversion proves effective for Lipschitz objectives, it encounters limitations in convex smooth optimization. To address this challenge, Cutkosky [2019] introduced a key algo- rithmic modification trajectory rather than at the current decision in each iteration, as the averaged trajectory exhibits greater stability. Therefore, throughout this paper. To utilize the stability of the averaged trajectory, Cutkosky [2019] incorporated optimistic online algorithms [Chiang al., 2012, Rakhlin and Sridharan, 2013], a powerful tech- nique in modern online learning [Orabona, 2019]. This integration has inspired a growing body of research that leverages the adaptivity of optimistic online learning algorithms achieve accelerated convergence [Cutkosky, 2019, Kavis et al., 2019, Joulani et al., 2020b, Zhao et al., 2025]. We provide a comprehensive overview of these recent developments in Section 2.2.
evaluating the gradient at the averaged decision along the optimization
refer to this enhanced approach the stabilized O2B conversion
1.3 Our Contributions
With stabilized O2B conversion, Cutkosky [2019], Kavis et al. [2019], Joulani et [2020b] have demonstrated that optimistic algorithms INemirovski, 2004] are essential for acceleration [Nesterov, 1983] in convex smooth optimization. Interestingly, game theory, recent studies reveal stark separation of the ability of optimism: optimistic methods are necessary for convergence, while non-optimistic methods invariably diverge [Mertikopoulos et al., 2018]. This fundamental difference prompts important question regarding the role of optimism across broader optimization contexts.

---

Table 1: Comparison of the stabilized O2B conversion [Cutkosky, 2019] with our optimistic O2B conversion regarding the ability for acceleration. Our optimistic O2B conversion incorporates optimism directly, enabling look-ahead online learning regret, where a non-optimistic algorithm achieves the optimal accelerated rate.
Property
Stabilized
Ours (Optimistic)
Online Learning Regret
Standard
Look-ahead
Optimism in Conversion
x
Optimism in Algorithm
/
x
Convergence Rate
OTT 3)
O(T ?)
Motivated by this question, we further investigate the role of optimism in convex smooth optimization. We find that while optimism is essential for acceleration, it does not need to be exclusively achieved via online learning algorithms, but can also be realized through the O2B conversion mechanism. Specifically, we propose an optimistic 02B conversion, which can implicitly incorporate optimistic capabilities in theoretical analysis. Interestingly, this shows that optimism not only plays a crucial role in online learning and game theory, but also in the offline optimization, making it a fundamental principle across different optimization contexts. Our work is inspired by Wang and Abernethy [201 8] but takes a fundamentally different approach: we abandon the game-theoretic interpretation and instead develop a novel optimistic O2B conversion framework that directly incorporates optimism into the conversion mechanism. While we arrive the same intermediate result (in Theorem 1), our framework provides a more direct and unified understanding of how optimism enables accelcration. As first application, our framework re-derives the algorithm from Wang and Abernethy [2018) (our Al Algorithm 2), offering new insights on its effectiveness.
Our optimistic conversion can also be extended to strongly convex and smooth objectives, achieving the optimal convergence rate for the first time through O2B conversion. Notably, while optimism remains essential in this challenging setup, it is now distributed between the O2B conversion and the online learning algorithm, and their cooperation makes the optimal convergence attainable.
Furthermore, consider making our method universal [Nesterov, 2015]. An optimization algorithm is called universal if it can automatically achieve the best possible convergence guarantces under smoothness and non-smoothness, without requiring the smoothness parameter. To this end, a natural idea is to leverage the AdaGrad-type step sizes [Duchi et al., 201 1] following Kavis et al. [2019]. However, this generally requires querying the gradient oracle twice in each iteration, which is not as efficient as non-universal methods such as NAG (2) and is also not efficient enough when the gradient evaluation is costly. The same concern also appears in the work of Kavis al. [2019]. To this end, building on our first optimistic conversion, we propose a further enhanced optimistic O2B conversion, which is able to achieve the optimal and universal convergence rates, while maintaining only one gradient query per iteration, making it as efficient as non univeniierall methods in terms of the gradient query complexity. Our results can also be extended the stochastic optimization setting with high- hioh-prrbabblity guarantees, which we defer to Appendix C due to space constraints.
Table presents the comparison between the stabilized O2B conversion of Cutkosky [2019] and our optimistic conversion regarding the ability for acceleration. The core message is - both 02B conversion and online learning algorithms are essential in achieving acceleration. Our optimistic 02B conversion incorporates the optimistic ability theoretically in the analysis and thus enables look-ahead online learning regret, which liberate the algorithm design. Therefore, even the simple online gradient descent algorithm can achieve the accelerated convergence.
Finally, we highlight the equivalence of the algorithm update trajectory between the optimistic-O2B induced algorithm and the classical NAG (2) in unconstrained settings under specific parameter configurations, offering an interpretation of NAG through the lens of optimistic online learning. Conversely, this observation also offers an intuitive explanation for the effectiveness of our optimistic conversion because of its profound connection with NAG. Furthermore, works implementing optimistic algorithms [Cutkosky, 2019, Kavis et al., 2019, Joulani et al., 2020b] can be viewed as variants of Polyak's 's Heavy-Ball method [Polyak, 1964], enhanced with carefully designed corrected gradients.
demonstrate that previous
To conclude, our contributions mainly threefold, summarized as follows:
3

---

We propose an optimistic O2B conversion framework, which implicitly incorporates optimism in theoretical analysis. Our optimistic conversion re-derives the algorithm from Wang and Abernethy [2018], while from the perspective of online-to-batel conversion, offering new insights on the relationship between the game-theoretic and the O2B-theoretic interpretations.
Our optimistic conversion extends to strongly convex and smooth objectives. This marks the first time that the optimal convergence rate for strongly convex and smooth objectives has been achieved through O2B conversion.
We further enhance our optimistic conversion to achieve the optimal and universal convergence with only one gradient query per iteration, making it as efficient non-universal methods in terms of the gradient query complexity, which is validated by the numerical evaluation Section 5.
Organization. The rest of the paper organized as follows. Section introduces the preliminaries and reviews related work. Section 3 presents our optimistic O2B conversions with accelerated and universal convergence. Section 4 compares O2B methods with classical approaches. Section provides the numerical experiments to evaluate the performance of the proposed methods. Finally, Section 6 concludes the paper. All proofs are provided in appendices.
2
Preliminary
In this section, we introduce some preliminary knowledge, including notations, assumptions, and recent advancements in convex smooth optimization via the stabilized O2B conversion.
2.1 Notations and Assumptions
In the following, we introduce the notations and assumptions used in this work.
Notations. For simplicity, we use || for || |l2 by default and write a S b (b)) if there exists a constant C' < do such that a/b < C. When there is no ambiguity, we abbreviate Σ, and {-he for Ee= and {- respectively. We adopt [xx arg min ||z x|| to denote the Euclidean projection onto X. Given sequences of O2B conversion weights {at}: and decisions of the online algorithm {x+)r, we use A, - ΣS= Ot to represent the weights' summation and define
Σ a,x, + -axi-11 and &₁
Σ a,x; ; + oxxi
A,
A,
to be two kinds of weighted decisions. The two expressions differ only in the decision associated with an, while all other terms remain the same.
Assumption 1 (Domain Boundedness). For any x.y E X C Rd, the domain satisfies ||x yll S D. Assumption (Smoothness). The objective function f(.) is L-smooth, i.e., |/ [x V S L|[x -yl y| holds for any x,y E Rdd
Both assumptions are standard in the optimization literature. Specifically, Assumption is common in constrained optimization [Cutkosky. 2019, Kavis et al., 2019, Joulani et al., 2020b]. Note that the boundedness assumption only required when designing a universal method in Section 3.3. Additionally, Assumption 2 is necessary for the accelerated convergence [Nesterov, 1983, 2018].
2.2 (Stabilized) Online-to-Bane Batch Conversion
In this part, we introduce the vanilla online-to- to-batch conversion (Cesa-Biandee et al., 2004, Shalev- Shwartz, 2012] and the enhanced stabilized conversion [Cutkosky, 2019].
First, we formalize the vanilla 02B conversion in Algorithm 1, where in each iteration, the learner queries the gradient feedback of (x,), and feeds o, V fxx)) into the black-bon box online learning algorithm to generate the next decision X By doing this, the suboptimality gap of the final decision Xy, defined in Eq. (4), satisfies f(xr) - f(xt)= < , (xx(())
-x)). The above property sufficient to attain the optimal convergence rates for Lipschitz-continnous objectives, ie.. 1122) for convex and O(T-1) for strongly convex functions [Lacoste-Julee Julien al., 2012),

---

Algorithm 1 Vanilla/Stabillzee Online-to-Band Batch Conversion
Input: Online learning algorithm AOL. weights {ar)=1 with as > O.
I: Initialize: X1 Xx E X
2: for = 1 to T do
3: Query the gradient feedback ge, where
V fxx); (vanilla O2B conversion) V fxx);
g+
(stabilized O2B conversion)
4: Define (x(x)= A (e x) as the t-th round online function for Aou
5: Get X from Aoi (x1, (6.()))==1
6: end for
1 El= 0 7: Output: XT AT
matching the known lower bounds [Nemirovski and Yudin, 1983]. Despite its simplicity, vanilla conversion has not yet been shown to yield accelerated rates in smooth convex optimization problems.
To this end, Cutkosky [2019] introduced the more powerful stabilized O2B conversion. The key idea is to query the gradient of the averaged decision x, rather than x; in each iteration. The suboptimality gap of the final decision Xy satisfies f(xx) f(x') - 1 [a fx,)) X - x*). Although the only algorithmic difference between vanilla and stabilized conversion is where the gradient is taken, this is the key reason why stabilized conversion outperforms the vanilla one in terms of acceleration. To exploit the power of the stabilized O2B conversion, Cutkosky [2019] leveraged the optimistic online learning techniques, which follows the two-step update rule below:
Ar
(5) where di > a time-varying step size and W, an intermediate variable. In each iteration, before
W; Iw [w: Mc], We+1 Tw [w: 1y Vl:w)))
receiving the gradient feedback, the learner first updates using an optimistic estimate Mj (called
an optimism) the future gradient ((,(w.) and then updates using the true gradient V& (w.). By doing this, optimistic methods can achieve the following regret bound with adaptivity for any E W:
T
T
E ((l(m)) S o
Σ
[l) -
We w 12
(6)
which can result in favorable regret guarantees when the optimistic term [V. Mell is small. In the context of offline convex optimization, (w,) equals a, (X,.. Subsequently, Cutkosky [2019] chooses M,-- a, ( as the optimism (also known as gradient-variation regret in online learning [Chiang et al., 2012)) such that the optimistic term depends on ||x - under smoothness, because the combined decisions {xe) is stable. To illustrate this, we focus on a key equation proposed therein: A,- 1 - x,) = ax xx). When the domain is bounded by Assumption 1, the variation of ||x x || as/A, 1/1 using a = 1. Cutkosky [2019] employed this key stability property to achieve an Olog 7 2-2) for unconstrained optimization.
rate in the constrained setup and
Consequently, Kavis et al. [2019] leveraged optimistic online learning (5) with optimism M, a, (xx)) where x; is another form of weighted combination, as defined in Eq, (4). By doing so, the optimistic quantity || (we))
1 is of the same order as L x(-1| when o₂ t, which therefore can be canceled by the intrinsic negative stability terms in the analysis of optimistic algo- rithms, as shown in Eq. (6), resulting in the optimal rate of O(T Joulani et al. [2020b] obtained the same optimal convergence rate but with a different optimism configuration of M, = a V (x; and extended the results to composite and variance-reduced optimization. For a comprehensive understanding of the connection between optimistic online learning and acceleration in smooth optimization, one may refer to Zhao [2025].
3 Optimistic Online-to-Batch Conversions for Acceleration and Universality
In this section, we introduce our optimistic online-to-batch conversions. Specifically, Section 3.1 proposes the first optimistic conversion for acceleration. Subsequently, Section 3.2 extends our
5

---

51-1
Stabilized Conversion: X
X X
Optimistic Conversion:
or X 11+1
X
Figure Comparison of the update between the optimistic and stabilized conversions, where gi az (Xxe)) and g a, (xx)) represent the losses faced by the optimistic and stabilized conversions, and x 5 y denotes updating from x to y using the information g. Compared with the stabilized conversion, ours can update with the information of the upcoming losses.
conversion strongly convex objectives. Finally, Section 3.3 proposes a further enhanced optimistic O2B conversion to achieve universality while maintaining efficiency.
3.1 Acceleration for Smooth and Convex Functions
In this part, propose our first optimistic O2B conversion below, which is general it only requires the convexity of the objective function. The proof is presented in Appendix B.I.
Theorem 1. If the objective function f() is convex, then we have
T
AT ((xx))-((xx)))
(a (S()), x*) + a (VS(x)) VI(x;),, -x--1), (7)
where X, A T. (E 2= O2,x, 1xxt-1) and X,
A Ae (E a,x, + axxi).
Comparison to Stablized 02B Conversion [Cutkosky, 2019]. Compared with the stabilized O2B conversion, which exhibits the property Ar [f f(x')] S V. x, x*), our
optimistic O2B conversion in Theorem differs in two aspects:
(i) The first term in the right-hand side Eq. (7) is an algorithm-relater look-ahead online learning regret that allows clairvoyant-rype update because the algorithm first observe the loss of the t-th iteration, i.e., 0g V (xx), and then updates from X to X₃. Intuitively, this look-ahead online learning problem is easier to handle than the standard online learning problem. For stabilized conversion, clairvoyant- updates are forbidden because X, contains the information of the current decision x,. Figure illustrates the aforementioned difference.
(ii)
The second term in Eq. (7) serves as optimistic quantity in the analysis, which can therefore preserve the potential for acceleration. The difference from the stabilized conversion of Cutkosky [2019] is that our conversion introduces the optimistic term directly in the analysis, whereas the stabilized conversion requires an optimistic algorithm (5) explicitly to achieve the same effect.
Our technical approach differs from the stabilized- www.-oo-eoooo---bbbbbooa
methods [Cutkosky, 2019, Kavis et al., 2019, Joulani et al., 2020b] from two aspects: (i) Previous works analyze (x+)) f(x*)]
intermediate quantity, while focus 0z. (X.) f(xt)]; )]: (ii) Previous works rely on the key equation A, (X--1 x,) a, (X, Xt), while we employ a novel equation A (xt-1- xx) (xx x;-1), which proves crucial for our final guarantee. Interested readers can refer to Appendix A for more useful equations in the 02B conversion.
theoreti Interpretation [Wang and Abernethy, 2018]. The authors pro- vided an alternative ghee-the perspective to understand acceleration in convex optimization. Specifically, they reformulated the convex optimization problem (1) two-player Fenchel game: y(x,y) = (y,x) x) fy) [Abernethy et al., 2018], where f*(-) is the Fenchel conjugate of f()). The performance measure f (xx) f(x*) is then expressed the gap towards the Nash equilibrium: supy 9xx, y) inf, supy g(x,y) Crucially, their analysis incorporated the idea of optimism from framework. In contrast, our work reformulates these tech- niques by removing the game- theeoretc interpretation and instead provides a direct O2B conversion perspective. Notably, the technical core of our Theorem closely parallels Theorem in their work, and our framework can also re-derive their Algorithm 2 (our Algorithm 2). We believe that 02B conversion provides a more general and accessible lens for understanding offline optimization compared to game theory. Importantly, our analysis reveals that optimism is essential for acceleration.
Connection
online learning into the game-ttheree

---

Algorithm 2 Optimistic Online-to-Batch Conversion with Online Gradient Descent
Input: Online-tur saiinetto-bachh weights {ar)T=1 and step size T)
1: Initialize: Xy A
2: for t = 0 to T 1 do
3: Query (x(+++1) where X++1 Aet1 (E agx, ax+1xx))
4: Update X++1 = II [x - 0/+11 fx(+++))
5: end for
6: Output: Xy (in Corollaries 2) or Xy (in Theorem 5)
Interestingly, optimism also plays critical role in the game-theoretic approach [Syrgkanis et al., 2015, Zhang et al., 2022], suggesting that optimism may be a fundamental principle across online learning, game theory, and offline optimization.
Convergence Guarantee. Consequently, we present a simple yet optimal algorithm for convex smooth optimization. Our algorithm template is summarized in Algorithm 2. In Line 3, unlike the stabilized O2B conversion, we query the gradient V f rather than V fx, from the oracle. In Line 4, the learner first observes the loss vector of the next round, 04++11 V[(x++1), and then updates its decision from X2 to X(+1- This approach differs from classical online learning, where the learner makes her decision first and then observes the loss. This represents the key algorithmic difference between our optimistic O2B conversion and the stabilized conversion. We intentionally leave the step size ne. online-to-batch weights {a=)ē=1, and final output unspecified in Algorithm 2 for flexibility.
In the following, we offer the convergence rate of Algorithm 2 and defer the proof to Appendix B.2. Corollary 1. Under Assumption 2, if f(-) is convex and X = Rd, Algorithm 2 with weights ar = t and step size 'n- 1 for any i [T] ensures: f(x)) f(x*) O(L||x x 1 TT).
Note that the convergence rate scales with the initial distance the minimizer ||xo x" ||. and we do not require the feasible domain to be bounded here, i.c., without Assumption 1. Observe that Algorithm coincides with Algorithm in Wang and Abernethy [2018]; both analyses isolate the same underlying online learning subproblem (Theorem 1). Our contribution is not to introduce a new algorithm, but to showease how the online-to-batel framework furnishes fresh route this effective method and, more importantly, unlocks the new results in Section 3.3.
3.2 Acceleration for Smooth and Strongly Convex Functions
In this part, we extend our optimistic O2B conversion Section 3.1 to strongly convex objectives, where strongly convex function is formally defined follows.
Definition 1 (Strong Convexity). A function f(:) is X-strongly convex over X if f(x) f(y) S (Vf(x),x x
||x y| for any x,y E X.
Since strong convexity a specialization of convexity, we apply our general stabilized O2B conver- sion analysis to the convex surrogate f(x) å fxx) - a/2 |x| and then reconcile the gap between f(-) and the original objective f(-). We present the resulting optimistic O2B conversion for strongly convex objectives in Theorem 2, with the proof deferred to Appendix B.3.
Theorem 2. If the objective function f(-) is X-strongly convex (in Definition 1), then we have
T
Ar --(((r))((x()) Σ an (xi( hx(x)) + Σ au (V((x)) vf(x)),,, x(-1), (8)
where f()) 2 f(-) - 211 and hx()) & (V(())).)) + 1| is a X-strongly convex surrogate.
Building on Theorem 2, we leverage the one-step variant of optimistic online gradient descent [Joulani al., 2020a] as the online learning algorithm with carefully designed optimisms to achieve the optimal accelerated convergence. We present the update rule and its guarantee in Theorem 3, with the proof deferred to Appendix B.4.
7

---

Theorem 3. Under Assumption 2, suppose the objective f(-) is X-strongly convex and X' = RR. If the algorithm updates as
a1 vf(x,) + 01 t=1
1 XA
X++1 =x
(Vhy(x,, M4 M411), M,
a4 Vf(xx) + a
22
with 01 = -1amm and az
1 1 2, then it holds that
1VK"
f(XT) - f(x*) so (AIlxxx exp
T T-1 exp 1 2/F (-1+2/=)
xx11
where K. A T represents the condition number.
Theorem achieves the optimal convergence rate for strongly convex and smooth objectives, scaling optimally with both the iteration number I and condition number k. Notably, this is the first time that the optimal convergence rate for strongly convex and smooth objectives has been achieved through online-to-batch conversion.
We note that while optimism remains essential for achieving optimality in strongly convex opti- mization, the key insight is that the optimistic mechanisms are now distributed between the O2B conversion and the online learning algorithm, making the optimal convergence attainable through their cooperative interaction.
3.3 Universality to Smooth and Non-smooth Functions
In this part, we focus on making our optimistic O2B conversion universal to smoothness to enhance its robustness while maintaining computational efficiency comparable to non-universal methods. Universality means the method can adapt to both smooth and non-smooth objectives without requiring prior knowledge of the smoothness parameter. This problem has received considerable attention in the literature [Nesterov, 2015, Kavis et al., 2019, Kreisler al., 2024, Rodomanov et al., 2024, Li and Lan, 2025] as the smoothness parameter is often unknown and challenging to estimate in practice.
To begin with, demonstrate that Algorithm 2 can be made universal by simply using an AdaGrad- type step size [Duchi et al., 20 also known as self-confident tuning in the online learning literature [Auer al., 2002]. The proof is deferred to Appendix B.5.
Corollary 2. Under Assumption I, if the objective f()) is corvex, Algorithm 2 with weights az = t and step sizes
71
(9)
EL (2V VS(X.)I
guarantees f(x))-f(x') s OLD (T2) under Assumption 2, and f(xr)- < O(GD/VT) when the objective is smoohh with |Vf()) <
Although Algorithm 2 with an AdaGrad-type step size is theoretically optimal and universal, its efficiency limited by requiring two gradient evaluations, (x().) and (x.)). This is less efficient than non-universal methods such as Theorem I and NAG (2), which require only one gradient query per iteration. Furthermore, this inefficiency becomes problematic when gradient evaluation is costly, such in nuclear norn optimization [Ji and Ye, 2009] and mini-batch optimization [Li et al., 2014]. The same limitation appears in the work of Kavis et al. [2019].
In the following, we demonstrate that it is possible to achieve the same optimal convergence rate using only one gradient query per iteration through further improved optimistic 02B conversion. The proof is deferred to Appendix B.6.
Theorem 4. If the objective f(+) is convex, when on = 1 and or = 0, the final term of Ar (f(rr f(x*)] can be bounded by
T-1
for xx
Σ
a (V 1=1
x1-1) Σ A (10)
where D) & f(x) f(y) - (Vf(y),x y) is the Bregman divergence associated with f())
8

---

Remark 1 (Technical Comparison). The main technical difference from previous conversions is that Theorem leverages novel equation: A, 1 (x; xx-1)== a (x,-1 x + a (x,-1 - -x
This analytical approach completely eliminates (x(x) from our derivation, ensuring that the algorithm requires only Vx(x)) evaluation at each iteration. Readers can refer to Appendix A for the
proof of this equation.
In Theorem below, we present that the above conversion along with online gradient descent can achieve universal optimal rates using only one gradient query per iteration. The corresponding proof deferred to Appendix B.7.
Theorem 5. Under Assumption the objective f(.) is convex, using weights on 1.for E [7'
oT = O, and the step size of
D
1/1
(11)
V V s-1 a² 1 [( (xx,))11
Algorithm 2 enjoys f(xT) - - [(x)) S O(LD2/T²) under Assumption 2, and f(xT) - f(x*) S
O(GD/ VT) when the objective is non-smooth with |Vf(-)) <
Theorem leverages the simple online gradient descent to achieve the universal optimal convergence rates, while requiring only one gradient query per iteration, making it as efficient as non-universal methods such as NAG (2) and the method in Corollary 1. Furthermore, we note that our results can be straightforwardly extended to the stochastic optimization setting with high-probability rates, which we defer to Appendix C due to page limits. Below we remark two limitations of Theorem 5.
Remark 2 (Boundedness Assumption). Theorem 5 requires bounded feasible domains, i.e., only suitable for constrained optimization. We focus on the constrained setup because online learning is naturally suited for handling constraints. Designing universal methods with accelerated convergence in the unconstrained case is highly challenging. Recent work of Kreisler et al. [2024] has made some progress in this direction in the context of "parameter- free"" optimization" 2 by combining the methods of Kavis et al. [2019] for acceleration and Ivgi et al. [2023] for errrmeter-freenesse Extending our method to the unconstrained case is highly non-trivial and thus left an important future direction.
Another limitation of our method is that the weight of the final round oT must be chosen as aT 0, which means that the algorithm requires the iteration number T' at the beginning.
Finally, we note that achieving the optimal universal rates with strongly convex objectives is still open and cannot be directly solved via the universal method proposed in this part. To this, in Theorem 3, the online-to-batch conversion weight or depends on the smoothness L. Therefore, in the universal setup where L. is unknown, it is more challenging than the convex case because the method needs to estimate the smoothness parameter on the fly, making this problem highly non-trivial.
4 Discussions of Conversion-based Methods
In this section, we illuminate the effectiveness of recent O2B conversion methods [Kavis al., 2019. Joulani et al., 2020b], including ours, by comparing them with classic approaches in convex optimization. Specifically, we first highlight that our algorithm trajectory coincides with NAG in Section 4.1. Then we find that stabilized-O22 wer----vvesionbaaaeeeeeeeeeeeeee based methods can be interpreted as variants of Polyak's Heavy-Ball Section 4.2.
4.1 Comparing Algorithm 2 with Nesterov's Accelerated Gradient
Our method is algorithmically equivalent to Nesterov's 's accelerated gradient (NAG) in Eq, (2), under certain parameter configurations. To show this, we leverage result from Wang and Abernethy [2018], with a self-contained proof in Appendix D.
Proposition 1 (Theorem 4 of Wang and Abernethy [2018]) xf = RRd our Algorithum 2 with step size 1h
[+1 - SL is equivalent to NAG (2) with 0, TI and Br 142
i-1 such that y. 3x; and
'The main parameter in our method is the domain diameter D. as shown in Eq. (11) in Theorem 5. Therefore. extending method to unconstrained setup is equivalent achieving parameter freeness with acceleration.

---

X(+1. Our method can be rewritten as the following equivalent form:
X, Xx-1 + Bt-1 ( - x(-2) 4T. V ( B x{-2));
which is exactly Nesterov's 's accelerated grudient method in a one-step update formulation.
4.2 Comparing Previous Methods with Polyak's Heavy-Ball
Kavis et al. [2019], Joulani et al. [2020b] in this thread both adopted the optimistic online learning framework, as shown in Eq. (5), but with slightly different configurations. Specifically, (w,(w,) equals ag V f(x) ) in offline convex optimization. Differently, Kavis et al. [2019] chose the optimism Mj ag V fxx) whereas Joulani et al. [2020b] used Mr a ( For clarity, their optimistic updates can be rewritten in a one
one-step step formulation [Joulani et al., 2020a]:
[Kavis et al., 2019], de f fxx + a (xx) + V
X = X2 Te.
gr
- 04 ((x + a V (x.) ar+ Vx()) [Joulani et al., 2020b].
where g, is multi-step gradient. Furthermore, due to simple derivations, the above one-step update is equivalent to the following rule in terms of }2
x = x + 5 (x x 7h-1 1.
Ae- () where 3
(12)
A,ar-1'
On the other hand, a classic method in convex optimization named Polyak's Heavy-Ball (HB) [Polyak, 1964] equips gradient descent with momentum and updates as
2 = - - - - žt-2) - V(-1V((Z-1),
(13)
where By denotes the momentum parameter and r/. is the step size. Comparing Eq. (12) with HB (13), we can find that the trajectories of (Kt), and {ze], J+ are similar except that HB uses the gradient of (z(=)1) while Eq. (12) adopts a corrected gradient of df gt-1. Note that although HB itself cannot achieve acceleration for general convex smooth objectives, its variants with corrected gradients can do this for (strongly) convex and smooth objectives [Wei and Chen, 2025]. Therefore, previous stabilized-conversion
methods can be treated as variants of HB with corrected gradients, which might explain their success in achieving acceleration.
5 Experiments
In this section, conduct numerical experiments to validate the effectiveness of our proposed methods. We evaluate our methods in the squared loss minimization and logistic regression tasks across multiple LIBSVM datasets under both non-universal and universal settings, comparing against classic methods including NAG, gradient descent, UniXGrad [Kavis et al., 2019], and the method in Joulani et al. [2020b]. The results demonstrate that our method achieves comparable or superior convergence performance while maintaining competitive computational efficiency. Detailed setup descriptions and experimental results can be found in Appendix E.
6 Conclusion
In this paper, we focus on convex smooth optimization and study the role of optimism for achieving acceleration. Previous tftte-ofthhe-eee methods rely on the stabilized O2B conversion and achieve the ability of acceleration via optimistic online learning algorithms. In this work, we propose optimistic online-to-bated conversions that introduce optimism implicitly in the analysis, allowing acceleration using the simple online gradient descent. Our optimistic online-to-batch conversion can also be extended to the strongly convex case with the optimal convergence therein. Furthermore, we consider making our method universal to smoothness and introduce an improved optimistic online-to-bae conversion method that only requires gradient query per iteration, making it as efficient as non- universal methods, while maintaining the optimal convergence rates. We also conduct the numerical experiments to evaluate the performance of the proposed methods.
Two directions are worth future exploration. The first to extend our method to unconstrained domains, which is highly non-trivial and challenging. Recent advances in parameter-free stochastic optimization [Ivgi et al., 2023] or using ensemble ideas for a hounded-to-unbounde al., 2022] might prove useful. The second direction is investigate the power of our optimistic online- to-batch conversions in more practical tasks, such as real-world deep learning training, following the recent advance of Defazio et al. [2024].
reduction [Luo
10

---

Acknowledgements
This research was supported by NSFC (62361 146852, 62176117). Peng Zhao would like to thank Jun-Kun Wang for the helpful discussions. The authors also thank the reviewers for their valuable suggestions, which helped improve this paper.
References
D. Abernethy, Lai, K. Y. Levy, and J. Wang. Faster rates for convex-concave games. In Proceedings of the s1 Annual Conference on Learning Theory (COLT), pages 1595-1625, 2018.
P. Auer, N. Cesa- Bianchi, and C. Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48 2002.
S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge university press, 2004.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-2057 2004.
C. Chiang. T. Yang, Lee, M. Mahdavi, Lu, R. Jin, and Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory (COLT), pages 6.1-6.20, 2012.
A. Cutkosky. Anytime auline-to-batchl optimism and acceleration. In Proceedings of the 36th International Conference Machine Learning (ICML), pages 4454, 2019.
A. Defazio, X. Yang, A. Khaled, K. Mishchenko, H. Mehta, and Cutkosky. The road scheduled. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 9974-10007, 2024.
J. C. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
M. Ivgi, O. Hinder, and Y. Carmon. Dog is SGD's best friend: parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 14465-1444 2023.
S. Ji and J. Ye. An accelerated gradient method for trace norm minimization. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 457-464 2009.
Joulani, A. György, and C. Szepesvári. A modular analysis of adaptive (non-)conved optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108-138, 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.
I. Kreisler, M. Ivgi, O. Hinder, and Y. Carmon. Accelerated parameter-free stochastic optimization. In Proceedings of the 37th Annual Conference on Learning Theory (COLT), pages 3257-3324, 2024.
Lacoste-Julien, Schmidt, Bach. A simpler approach to obtaining an O(1/1 convergence rate for the projected stochastic subgradient method. arXiv preprint, utXiv:1212.2000 2012.

---

M. Li, T. Zhang, Y. Chen, and A. J. Smola. Efficient mini- training for stochastic optimization. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 661-670, 2014.
T. Li and G. Lan. A simple uniformly optimal method without line search for convex optimization. Mathematical Programming, pages 1-38, 2025.
H. Luo, M. Zhang, P. Zhao, and Z.-H. Zhou. Corralling a larger band of bandits: A case study on switching regret for linear bandits. In Proceedings of the 35th Conference on Learning Theory (COLT), pages 3635-3684, 2022.
P. Mertikopoulos, C. H. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Proceedings of the 29th Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2703-2717, 2018
A. Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15())2229-251 2004.
A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983.
Y. Nesterov. A method of solving a convex programming problem with convergence rate (11/k²). Proceedings of the USSR Academy of Sciences, 269:543, 1983.
Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
Y. E. Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, (52(1-2):381 2015.
Orabona. A modern introduction to online learning. arXiv preprint, arXiv:1912.13213, 2019.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. Proceedings of the 26th Annual Conference Learning Theory (COLT), pages 993-1019, 2013.
A. Rodomanov, A. Kavis, Y. Wu, K. Antonakopoulos, and V. Cevher. Universal gradient methods for stochastic convex optimization. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.
Shalev-Shwartz. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
W. Su, P. Boyd, and E. J. Candès. differential equation for modeling nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17: 17:153:1-153:45. 2016.
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 I.. Chen. Accelerated over-relaxation heavy-ball method: Achieving global accelerated convergence with broad generalization. In Proceedings of the 13rd International Conference on Learning Representattonss (ICLR), 2025.
M. Zhang, P. Zhao, H. Luo, and 7.-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 Notes for Advanced Optimization, 2025. URL htap::::///.....gghaammm.ll/ com/ course//AptLLectureetttts Lecture 9, Optimism for Acceleration.
12

---

P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non -ottsttttonnrty: problem-dependee dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Y. Zhao, Y.-H. Yan, K. Y. Levy, and P. Zhao. Gradient-variation online adaptivity for accelerated optimization with Hölder smoothness. In Advances in Neural Information Processing Systems 38 (NeurIPS), page to appear, 2025.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936, 2003.
13

---

A Useful Equations in Online-to-Batch Conversion
In this section, we provide some useful equations in the online-to-batee conversion. We define
Ao 0 for completeness and assume 01 = (thus X1 Xo and X X1) for simplicity.
A (X - x1) ai (x+ x,):
(14)
A,(x; x1) (x1-1 x():
(15)
A, (8:-1 - x1) ax - X(-1);
(16)
A-1 (x: xx-1) ar (xx-1 - -xx) + a1-1 (x:-1 -(-2))
(17)
Eq. (14) is the key equation in the analysis of Cutkosky [2019], Eq. (15) is essential for the analysis of Kavis et al. [2019], and the last two equations are the key equations in our analysis. For boundary cases, Eq. (14)-Eq. (16) holds from = 1 and Eq. (17) holds from / =
In the following, we provide the corresponding proofs of Eq. (14)-Eq. (17).
Proof of Eq. (16). For = 1, holds trivially as Ao(Xo - -x1) = a (xi - xo) = 0. For l 2 2,
[-]
A--1 (Xt-1 - x,) Ar1
1
Σ
axXx
1
Σ
a,x; + acx--1)
A,-1
A
m=1
A!-1
+-1
a,X,
a₂X, + +
A
[5ml
Σ
14-1
Σ 0,83 + 01x1-1 -0181-1
a₂X, 01X11-1
A
1==1
Σ
02X₁ + a1x--1
0 = =0 x(-1);
A
which finishes the proof.
Proof of Eq. (17). Fort it holds trivially (1 = - -x2) 01 -x). For
t > 2, this can be proved by directly using the definitions of X4 and &, in (4):
a,x, + 1x-1X1-2 ))
1
1
Ac-1 (x, - x(-1) = Ar-1
0,X, + +a(xe-1)
Σ
A
Ar-1
s==1
A--1
2-2
Σ Cixx + 101x1-1
Σ
UgX. -4--181-
A,
AAt-
Σ agx + 0484-1
+ -0 0(x
A
0 + (04-1X1-1 01-18 (1x1-1)
or (x:-1 x.) + 0tt- (Xt-1 - X1-2).
Besides, it can also be proved by combining Eq. (16) and Eq. (15);
A (xe. x,-1) Ar-1 (X: x;-1) Ar (8t-1 x2-1)
= =0; (Xr-1 xx) + a: (xt-1 Xx-2),
which finishes the proof.
B Proof for Section 3
In this section, we provide the omitted proofs for Section 3, including Theorem 1, Corollary 1, Proposition 1, and Theorem 2.
14

---

B.1 Proof' of Theorem
Proof. We start with the analysis with the following quantity:
an [f(x) - f(xx)( S (a.V)((;), x x") + (a.V) -x,1),,
using the convexity of f()). Later, we analyze the second term above. Specifically, using the definition
of X, and & defined in Eq. (4), we have A,- (K,-1 x,) = ax - -x,-).. A detailed derivation of this equation is given in Appendix A. Therefore, using the convexity of f(:): f(x)) f(x-11) -
(x)( X x1-1), it holds that
[Jx,,) - [(x")) )] S (o.V x - xx)) + Ar-1 (5(xt-1) - [(x+))
Summing over 1. E (7), we have
Arf(x*) - V((e) x--1- -xx) + Σ 1f (Af((]]]
T
T
T
a1 ff(f((x)) X1 x1-1 xx) +
Σ [ A
Σ [Arf(R)) (xf(
Am1
T
(a. X1-1 - x*) - (x((T)
Σ -
Using the convexity f(x)) - f(xx)) (VI((z),, xx) again, it is equivalent to
T
Ar [x()) f(xx)] 5 Σ
(as Vx(x) x,, xx) + Σ (AVF())) X - xx)
1=1
T
T
(o: (ovff(x; x
a0 (x))
t=1
Σ
(a.V Xx -x") Σ (or V((x)) VS(x,);; x(-1),
where the second step is due to Ar - x.) -x(xx-11 x,) from the definitions x, and Xx. The proof is completed.
B.2 Proof of Corollary 1
Before providing the proof, we list useful lemma for online mirror descent.
Lemma (Lemma 4 of Zhao et al. [2024]). Let X be a convex set in a Banach space, and f X + IR be closed proper convex function on X. Given a convex regularizer si X R. with its corresponding Bregman divergence denoted by Do(-.-). Then any update of the form
arg min {x(x) + Dx x)-1)}
XEX
satisfies the following inequality for any u E X, l((x)) huu) < D (u, x:- D's (u, (u, xx) De (Xe,
Proof of Corollary We start from the intermediate result of Theorem 1:
Ar [f(x)) f(x*)] S (())
a ( - Vf(x)), x(-1).
TERM (A)
TERM (B)
For TERM (A), using the update rule of x xx [x, 7+0++1 (xx+11) with step size 7/c 17
TI as shown in Algorithm 2, via Lemma I, we obtain
I
T 1
TERM (A) <
21p--1 (1|x--1 - x2 1|xe - -x113)
Σ
[x: - x1-1
27p-
t=1
(=1
15

---

1 T
1 - x*113 1|xr - x
x*1²)
xx
x 1|
211
21)
X
x"
||
1
T
X
x1-1
2mj
27
For TERM (B), using the smoothness assumption and the observation of Ae - -xx) ax(xx-1--x x,) as shown in Eq. (15), we have
T
T
TERM (B) S L
a
& - x =
Σ
0
Xx - x1-111?
A
==1
1=1
Combining the two terms, we have
Arlf(xt) - f(x")]
No
11
La
||: - x1-111 22[|xx) x²1
2n
A:
21/
Finally, using Ar ) completes the proof.
B.3 Proof of Theorem 2
Proof. We first define f(x) - f(x) 2 1xx Since f(-) is X-strongly convex, f(.) is convex. As result, we directly reuse Theorem for convex objectives:
T
T
AT f(xr) f(x*)) s > ((vVf(()))
- xx)
+
au (v(x)) - -x--1)
1=1
The left-hand side of the above inequality can be expanded
À AT [(xx) j(x))] AT [f(*)) f(x - Ar || +
Ar||x*11
Moving the last two terms into the right-hand side, we have
T
Ar (f(xT) - f(x')) <
las ((xf( x: x*) + 2 Ar | 1|
Ar ||x
2
RECT
- x
a
ADAPTIVTTY
In the following, we focus on the REGT term. Specifically, because
T
T Youl xell
2 T
AT|
04
S
Σ
|xxll
Σ
Vor Var
5
o x ?|
AT
Ar
AT
where the last step uses the Cauchy- -Shhaar inequality, this term be rewritten as
T
T
REGT S
an
(Vf(x,),
xz) + l|xel]
Σ
a0
((Ff(x)
x") + [1xx113))
t=1
1=1
Σ an [hr
where the last step defines the surrogate loss function of
(x()) A (Vf(x))
x) + 2 |xx|1
finishing the proof.
16

---

B.4 Proof of Theorem 3
For strongly convex objective, we use the one-step variant of optimistic online gradient descent as the optimization algorithm, whose guarantee is presented below.
Lemma 2. The one-step optimistic online gradient descent algorithm updating as
Xt+1 = X Tht (V - M1 + Mc+1),
(18)
ensures that
T
E xx
(VS((x)) M, -x++1)
1 11x, x(+11??
21//
t=1
1
1|x: x"112
||x|
-x x²1
21lt
21/=
2011
Proof of Theorem 3. For the regret part of ΣT= convexity, we have
-1=1 a4 [ho(xe) hx(x*)] in Theorem 2, using A-strong
T
X T 2
as [ba(x.) hx(x)) S (or (hx(),), - -x')
or||x - xx112
1=1
Due to Lemma 2, the linearized term above can be controlled as
C1
aa Vh,(x)),x - xx) <
(ar (xx( - M,, - x(+1)
||x x(+11??
21
1=1
(A)
1 Ci
1x: x" x11
||
1
Xx:
x 11
2ntt
2n
2771
21tt
TERM (B)
TERM (c)
where Ci E (0, 1) is an arbitrary constant in the analysis that will be specified later. By choosing the
optimism as Mj- at V + a for 2 2 and M1 = a1 (((,) + a1x1, 3 we have
TERM (A) <
Σ
Tt
1/ar (hr(x)) - M + Σ
2C,
C1
|
X
20
21
t=1
1=1
2Cp Ci
-x-1121111
Σ
Xx X1+1 12
2Cu
21
T
X
2Co -C1
x
1|x, - x1-1
2Cp
21/-11
2=
Combining all terms, we obtain
T
am
2C. 20p-Ch
Oe [xx)x:) - -o(x")
<
Σ
||x: 111-122
2Co
20/111
1=2
T
T
1
Aoi
1
1-C1
||x:
- x21
||x| -x=112-
||x
x1+1l1
2T/.
21)-1
2171
2m
[=1
1=1
Σ
XA,11
(2Co-C1))
C1)) ||xe- - x
x 1|
Xan
||x]
x+1
Ci)AA:
||xe - x(+1
A
2
We note that the choice of M1 relies xi because is the initial point of the algorithm, which is known.
17

---

As for the other term of 01=1 vf(x)), - -x--1) in Theorem 2, we have T
(Vf(x.) V](x), -
x(-1) s Σ oz
(((x,) 1a--v/ca V((.)] ||x, x--
r=1
(x( - V)(2)) - A + A -
af (x)) v/(x,))| ([(x,)+++X[])) -
x1-1l
T
< 2L
0f || - x ||: - x1- = 21
Σ [=]
at
|x
-x--11 x11
A
where the second step is because of the definition of f(:): Vf(x) [x((x)
Ax for any E Rd. the fourth step is due to smoothness ( (Assumption 2) and the fact of X S I,, and the last step leverages the useful equation of Eq. (15). Combining all terms, obtain
2La
(1 (1-G))
da1
( - [(x))
Σ
1|x, 1x--Xx-- -x
||
x"1
A₂
2
2
t=1
T
Aag
AAp-1(20o
Gi) -Gi)
||x; 10x-xxx1 xx-111
AC
To cancel the positive terms in terms of ||x - -x4-111, their coefficients should satisfy the condition:
2La
(1 (1)AA) 00,
Aa +
AA:-1(2Co C1)
2 00,
A
Ac
which is equivalent to
02 < min
C-C1 (Ci (CI -Co)Coo
(19)
A,A,-1
4x
By setting Co d
Ci and C -I+ /T2 and because
x
C1
(CI -Co) } = (-1+ 1 2x)
min
4k
8k²
by setting
= CAA,A the following inequality is sufficient condition for (19):
07
C (-1 vi v 2x)²
= 8x2 = 0, where X = (-1+ [-1+v1+ 2k)
A-1
C+1
8x²
Solving the quadratic equation, have
C= X + +
16x²
Thus we have A₁ = A--1 + a = (C 1)A,11 = (C + 1) an, ie., a1/AT = (C (C+1)-(T-)) More specifically, for any t E [T). we have
16x²
C+1
1
X+
16A + X + VX + 32
16
x 2 + 32
-
exp
16x² + + /X² +32N2X
1+
16k²
X+VX*+32
t
t
< exp
exp
16 v 32
4x v2x
t
exp
<exp
S exp
(T1+2 2VR
1
4ec
1 +
4x
221+22
which completes the proof.
18

---

B.5 Proof of Corollary 2
Before providing the proof, list two useful lemmas for the AdaGrad-type step size.
Lemma 3 (Lemma 3.5 of Auer al. [2002]). Let d1 02,...: or and ó be non non-negative real numbers.
Then, it holds that
Σ
at
Σ at: where 0/vD = 0.
S
+
8+ 1 ax
Lemma 4 (Lemma 27 of Kreisler et al. [2024]). For any positive number e₁ and cz, for any 1 2 0, and for any sequence of of non-negante non-negative numbers Bu, B1, B2...., we have
B
8
CI
Σ
B
B S
3/2 1/2 261
62
Proof of Corollary 2. For completeness, we restate the main results of Theorem I as follows:
Ar ( f(x') S
V.(.) x x1
(VS(.) - Vf(x)), x1)
TERM (A)
TERM (B)
For TERM (B), we decompose it into two parts:
T
TERM (B)
S Ma -
- V/(x012
Xx
Xt-
41l
t=1
using AM-GM inequality: Vay S z
2a
+
ay for any x. y, >
2
O. For TERM (A), using the Bregman
proximal inequality Lemma have
TERM (A)
S
(11x;-1
x-1
|x
x
112)
Xx
Xx-1 11
211--1
21/t-1
T
1
1x,
1=1
||x
X1-
11
Σ
1
||
x,-
277t.
277--1
21/²
277r
2mp
t=1
D2
T
X
-x
-
1
W/
27p
1=1
where the last step uses the boundedness of the domain (Assumption 1). Combining both terms,
D2
T
lf(f(xt) f(x))]
Σ n Vxx (x()))
|x, x, x1 (20)
TT
4n
In the following, consider smooth and non-smooth cases separately.
Smoothness Case.
Using smoothness (Assumption 2) and the setup of at = t, we have
L²a
4L-42
[VV 2
1.21,x
xxl12
x Xt 11
Pt + 1)2 X;
x,-1
A3
41,2
41,
|x
x
2|
<
|| - x
2
aj
where the second step uses the useful equation Eq. (15). Consequently, we obtain
2
T
AT (x(()))](xx))
- [xx)) 5
Tht
a ((IIV)((.)) vs(x:)11
161
19

---

T
T
-V
3DD
Σ
V - v
a (Z(x) Vx
16L2D
where the second step uses Lemma 3 and the last step uses Lemma 4 with c 3D and 02 16L2D, resulting in the final bound of O (LD2 )T
Non-Smoothness Case.
Starting from (20), we have
D
T [V)()))
- [(x))
V/(X:)||
3DD,
Σ
7/r
1=1
T
of = o (GDT3/2).
S 3D,
2G
where the second step uses Lemma 3, the third step the assumption of bounded gradients: |V)()) & G, and the last step is due to the fact of Et= of = - 2 = O(T3). Diving both sides by Ar OTT)), we obtain the final bound of (GGD/VT), completing the proof.
-T
B.6 Proof of Theorem 4
Proof. To start with, we analyze the intermediate term of:
T x') + Σ (a.))(()) x,-1), (21)
Σ at - f(x')] S
far
1=1
where we omit the index of because X1 Xg. Via the useful equation of A,-1 (3t x1- at (x:-1 x,) + 0 (X,-1
x₁-2) (a detailed derivation is deferred to Appendix A due to page
limits), the second term above can be bounded
T
las V)(x) - x(-1)=
(v x x,)
+
(a (f X(-2)
1=2
T
$
Σ A-1 (5(x-11) ((x,) + Σ
(0 X1-1 x1-2)
Σ
t=2
1=2
1=2
where the last step uses the definition of Bregman divergence, Plugging the above back into (21),
A1f( Arf(x') S
Σ aa (& x xx)) Σ [A-11 - Axf(xx))
Σ
(a--1V/ V((()), X1-1 - -x--)
Σ
1=2
1=2
As result, we can upper-bound Ar (f(xx) - f(x')] by
Σ (1 x") +
Σ
(a-i X x
E (Z-1)
Compared with the final result in Theorem 4, we need to handle the differential terms of
T
T
(ar V/(x),)) x xx) +
Σ ([(x))
X - =
t=1
oo ( -
Σ (V/(x+41) - vf(x)) -
t=1
where the second step shifts the time index, and the last step is because of ar 0.
20

---

B.7 Proof of Theorem 5
Before providing the proof, we present a useful property of smoothness.
Proposition 2 (Theorem 2.1.5 of Nesterov [2018]. f(-) is L-smooth over R if and only if
f[V ff()]l
2L Py(y,x), for any x, Rd.
(22)
Proof of Theorem 5. For completeness, we restate the main results of Theorem 4 as follows:
Ar [[(T) - [(x))
a4 (( -
TERM (A)
T
Oo an V - Vf(x) XX-1 -
Σ
A
1=2
TERM (8)
For TERM (B), it holds that
T-1
TERM (B) S
a - -
+
|x, X1-1
21t
1=1
T-1
S SD
Σ
0 [ -
+
Σ
1
x
27
where the first step uses AM-GM incquality and the second step holds due to the step sizes (11) and the self-confident tuning lemma (Lemmaa 3). As for TERM (A), following the same analysis as in Appendix B.5, using Lemma holds that
D2
TERM (A) S
Σ t=1
Xx
11.
7T-1
21
Combining the above results, it holds that
Ar [x*))
s 2D,
Σ
(2 (23)
t=2
In the following, consider smooth and non-smooth cases separately.
Smoothness Case. Starting from (23), we obtain
T-1 Σ (2,,
Ar (s(x)) [(x')) < 2D, 2L
(2,,
< 24
Σ
a D
A, A1) D) S SOLLD))
?
t=1
where the first step uses the property of smoothness in Proposition 2, the second step uses AM- GM inequality /zy I 27 + for any x, V. > 0, and the last step holds by simply choosing 7 2D (this constant only appears in the analysis and thus can be choosen arbitrarily). Finally, since T(T-1) (T22) achieve the optimal accelerated rate of O(DD²/T4) Ar 2
Non-Smoothness Case.
Starting from (23), we have
Ar lr f(x)) 2D
< 4D,
G 2 at (GDISIE).
the second step uses the assumption of bounded gradients: |V]()) < G, and the step due to the fact of E of = Σnn 2 = O Diving both sides by Ar @(T²), we obtain the final bound of OGD) /VV)), completing the proof.
21

---

C Extension to Stochastic Optimization
In this section, extend our proposed methods to the stochastic optimization setting. In the following, we first provide a f description the stochastic gradient oracle. Assumption 3 (Stochastic Gradient Oracle). For the objective function f X - R, assume access to stochastic gradient oracle g(-) that satisfies:
(i) Unbiasedness: xx)
x
V fx) for all x E A;
(ii) Bounded noise: [
f x v a almost surely, where a > 0 is the noise parameter.
Note that Assumption leverages an almost-sure boundedness because we aim to achieve high- probability rates, which stronger than the expectation rates obtained by previous works [Cutkosky, 2019, Kavis et al., 2019, Joulani et al., 2020b], where
assumption suffices.
Below present our result for the stochastic optimization setting.
Corollary 3. Under Assumptions and 3, our Algorithm with weights 0z = for E [T 1}. OT 0, and with step size
11
(24)
1 a2]ls((*+1) - g(xx)
with probability at least guarantees
0
LD
aD
aDBr.815
if f(-) satisfies Assumption 2,
7
vT
T
f(xT)) f(xx)
0
D(G+o)
oD VT
DDe
IV G.
VT
where 01,8/3 log
180 log((t) for any E [T] and 8 >> O.
Before presenting the proof of Corollary we import useful lemma from Ivgi al. [2023].
Lemma 5 (Lemma D.2 of Ivgi et al. [2023]). Let c >> O, {X+) } be martingale difference sequence
adapted filtration F. with E. X,
and XX,| S c, and (yt be a non- negntvee and non-decreasing
sequence. Then, for any 5 E (0, 1). with probability at least 8, we have
T Σ
T
Nc
I 8yT
OT,5 Σ 1=1
x² + c207
t=1
where 0,,s - log
60 (6g(
Proof of Corollary 3. We start from the beginning of Theorem 5 and aim analyze two main terms:
T
TERM (A)
Σ
aa Vf(x)) x; -xx),
T-1
and TERM (B)
Σ a
(V/((+1)))) - VS(x)), Xt-1).
For TERM (A), we further decompose it into two parts because we can only access the stochastic gradient g(x:):
T
TERM (A) = Σ (org((t))
+ On (VS(() - x(
(A-1) where TERM (A-II) only counts from l = 1 to / = T because we manually set aT = 0. For TERM (A-1), we can use the Bregman proximal inequality (Lemma obtain
(A-II)
2
T-1
TERM (A-1) S
|x:
x1-1
21
22

---

And for TERM (A-1I), using the martingale concentration inequality (Lemma 5) with
- X y/+ - a,, c=
X;
D
where (Fe)e20 denotes the filtration generated by the history up to round t, i.e., Fi = o(xo. fx.. X.. g(xx))==1) and {X is martingale difference sequence adapted to (Fi)120; with probability at least 8/3.
TERM (A-11) S 8(T 1)D 0 0T,6 1) o2 T,6/3
where 01,8/3 log
180 log(6e) For TERM (B), we can decompose it into two parts of
TERM (B-1) - -B- (r((((e++)) g(Xx), Xx x(-1);
T-1
and TERM (B-11) =
Σ at (V((++)) - g(x++1), - xx-1) Σ
(g(x)) VX(()),, xx-1)..
t=1
For TERM (B-1), following the same analysis as Theorem 5, we have
T-1
T-1 Σ
TERM (B-1) =
Σ
() g(x))2+++++
X - x11
-x--x11111
2T
And for TERM (B-11), we can use the martingale concentration inequality (Lemma 5) again, where we note that X, = (Vx())1) - g(x++1), x xt-1)/ is also a martingale difference sequence adapted to the filtration (Fi) because X only contains the information up to the t-th iteration. Thus, with probability at least 26/3, we have
TERM (B-1) S 16(T 1)D OTP10 1) + 0209
In the following, consider smooth and non-smooth cases separately.
Smoothness Case.
Combining TERM (A-1), TERM (B-1), and the negative Bregman divergence as shown in Theorem 4, have
2D
Σ -((
(Z,,
T-1 Σ
T-1
2D,
-
Σ
a20² 22 Σ A,D Xx+1)
LD + 3/
because of [|V g(x)l I a for any X' and the fact of Σ a =
Finally, we can combine all the terms together to obtain the final bound of
LD T2
oD DD.0r.85
D00,513
((xT) - f(x))
VT
which matches the optimal rate of O(LD2 + D/ VT) with only a logarithmic factor overhead. And note that the extra logarithmic factor always appears in high-probability bounds in the literature.
Non-Smoothness Case.
Combining TERM (A-T) and TERM (B-1), we have
T- [/(
2D
Σ
- 2DD, 2D, 1=1
3
Σ
az
t=1
23

---

T-1
T-1
$ 2D,,
6G
2 +
2
Σ an s t=1
so
<o
1=1
because of [xV](x) g(x)ll a for any X' and the fact of Σ oi Finally, we can combine all the terms together to obtain the final bound of
Ei=1 O(T9).
f(xr) - f(x)) D(G + + o ODVOr DD0 VT
VT
T
which matches the optimal rate of ( + o)/vT) with only a logarithmic factor overhead. And note that the extra logarithmic factor always appears in high- high-probability bounds in the literature. A
D Proof of Proposition 1
Proof. We prove this by induction. To begin with, we aim to show yı = X1. To see this, we provide a fundamental analysis for Algorithm 2:
&
(A-1 + axxi)
1A + a (xI-1 70-10- 10 Vfxx))
A
A.
1
AA--1x1-1-
A A1-280-2 17-1a, -m-1a
1 +ar
At
0t-1
(Ar-1
ar(a A1-2)
0
11 11-10 fx()))
x
+
X1-2
A
Arac11
A
A
a,Ai-2
11-10 (f(x))
= xx-1 +
(x:-1 - xx-22
Ara5-1
A:
1
2-2 -x(-))
=x--1
fx(x))
+ 1+1
(25)
4L
where the second step uses the update rule, and the last step holds due to ar = 4, 1h-
x
For / = A, = 0, we have x = Xo IL V ( = Xo IL V)((x) due to the initialization
of x; Xg. Furthermore, for NAG (2), y1 Zo OV fzo) xa 41. fx(x)) due to the
initialization of yo Zu = Xg. To conclude, we have y1 X1-
Consequently, we assume y,-1 xt-1 for some 1> 1 and aim to prove 2.-1 x.. In NAG (2), (_
since 24-1 Y + 7+1 (yt-1 yr-2), we have 2;-1 = Xt-1 + 1-2 (x,-1 x due to 141
the induction hypothesis. To prove z = X,, since both of them are linear combinations of the sequence {x,) we only need to prove that the coefficients of x, for all E [ 1] are the same. 2(2:-1) and its coefficient in X, is F+1 = x(++1)
Specifically, for X;-1, its coefficient in 2--1 is A +
t-2
A + 0x)
(0) = 2(21-1)
1(++1) which are the same. For x, with [t 2]. its coefficient in 2;-1 is
f-2 a, = 2a, and its coefficient x, is a2 2a. which are the same. As A (1+ + (1 A k(+1)
A m[t+))
result, we have proven Z X2.
Finally, we aim to prove yt X finish the proof of induction. To see this, we combine the update of NAG (2) into one step and use y x and Z X,:
t- 2
yr 2 0V OVf(z-1)-
yc-1
(+1 (y:-1 10-1-y14 -1-2)) - 00 (Vf((-))
t-2 2
1 4T.
81-1 +
[+1 1 (X,-1 - -8
V((())
which is equivalent to (25), showing that y = 8,.
Finally, since we have proved x; x
1-2 E+1
(X|-1 x(- denoting by 8 2 the update
rule of our algorithm can be rewritten as
x = X + 3 (X - x(2
B2- + -x--)))
v
4L
which is exactly Nesterov's accelerated gradient method in one-step update formulation.
24

---

E Experiments
In this section, we present the numerical experiments to evaluate the performance of the proposed methods. We compare our methods with baseline algorithms across different problem settings (non-universal and universal) on various datasets.
Contenders. In the non-universal setting, we compare our method (Algorithm with step size
" = +) with: (i) the classic non-universal methods of NAG, as stated in Eq. (2); (ii) the standard gradient descent GD; and (iii) the non-universal variant of UniXGrad [Kavis et al., 2019] (whose step size is also
v + ) And in the universal setting, we compare methods the two-gradient version with adaptive step size Eq. (9) and the ane-graieent improvement with adaptive step size Eq. (11) - with the classic universal methods: (i) UniXGrad [Kavis al., 2019] and (ii) the method in Joulani et al. [2020b] (abbreviated as JRGS'20).
Setup. Our experiment setup is mainly inspired by Kavis et al. [2019]. We investigate two kinds of convex smooth optimization problems: the squared loss task and the logistic regression task. For the squared loss task, take the least squares problem with L2-norm ball constraint for this setting, ie.. f(x) _ 인े Ax bll2, where ||x|| R. A E R follows normal distribution of (V, and b Ax' such that is random vector (O, 10-3.. We pick N 500 and d = 100. The smoothness parameter L of the squared objective is 7 (A)2, where Tmax (A) is the largest singular value of A.
For the logistic regression task, the performance is measured by the f2-regularized logistic loss f(x) - & اin log(1 + exp( bb, a. x)) jul [|2 where E R2 and b, E +1, are chosen from a dataset (ar, b, b μ = 0.005 is the parameter of the regularization term to prevent overfitting. The smoothness parameter L of the logistic objective is 1 Amxx (E/= a,a,") where Amax(-) is the largest eigenvalue of the matrix. Here we use five LIBSVM datasets to initialize the logistic loss.
AN
In the non-universal setting, all the methods can use the knowledge of the smoothness parameter L. which is prohibited in the universal setting.
Results. We report average results of the suboptimality gap. i.e., f(-) minxeX fx), in the logarithuiic scale, and time complexity with standard deviations of independent runs. Only the randomness of the initial point is preserved. All hyper-parameters are set to be theoretically optimal.
Figure 2 plots the suboptimality gap and time complexity of all methods, in the non-universal setting. Our method (Algorithm 2) achieves a similar convergence behavior as NAG and UniXGrad while being faster than GD. As for the time complexity, GD is the fastest one, UniXGrad is the slowest because there are two gradient evaluations and projections per iteration, while our method and NAG comparable.
Figure 3 plots the suboptimality gap and time complexity of all methods, in the universal setting. Our method (Algorithm 2) achieves comparable and sometimes better convergence behavior compared with the other state-of-the-an methods. In terms of time complexity. our one- muc-gradient improvement has similar performance as JJRS'22 20, and is faster than UniXGrad and our two-gradient version. Note that the standard deviation of the convergence curves become large as the suboptimality gap becomes small because the logarithm scale is used, making it sensitive to the small variations.
The results in Figure 2 and Figure show the effectiveness of our simple method (Algorithm 2) when compared with the classic non-universal methods (NAG and GD) and the classic universal methods (UniXGrad and the method in Joulani et al. [2020b]), supporting our theoretical findings.
25

---

MMM
(a) Squared
(b) aia
(c) mushrooms
(d) splice
(e) splice-scale
(I) svmguide3
Figure 2: Comparison in the non-universal setting of the convergence curves and time complexity. Our method (Ours) compared with classic non-universal methods NAG (2), GD, and UniXGrad on one squared loss task (Squared) and five fz-regularized logistic regression tasks (ala, mushrooms, splice, splice-scale and svmguide3). Ours achieves similar convergence NAG and UniXGrad while being faster than GD.
WwM
(a) Squared
(b) ala
(c) mushrooms
(d) splice
(c) splice- selicc--calee
(1) svmguide3
Figure 3: Comparison in the universal setting of the convergence curves and time complexity, Our methods Ours (IGrad) and Ours (2Grad) one squared loss task (Squared) and five Ezrregularized logistic regression tasks (ala, mushr ooms, splice. splice-scale and svmguide3). Our methods achieve comparable convergence behavior compared with the other contenders. Ours (1Grad) is more efficient than Ours (2Grad) and UniXGrad.
compared with classic universal methods UniXGrad and JRGS'20
26

---

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:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The statements after Theorem have pointed the limitations of our work.
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 out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification: Each of our theoretical results is accompanied by complete set of assumptions and a complete proof.
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 proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
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 to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [NA]
Justification:
Our paper does not include experiments requiring code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Seapi///ggiide//oeeeuaeeeee
connoooliyy. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. wttp:ccccpppppccccccceoooooc hotooiiicgiiieesoeeeuubbiiiiiiii wwtsSSubimsiiooooooooooooooooooe
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: Our 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 be 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: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror 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 or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 failed experiments that http://urrrpss.cpppiiee/eeeeee/e cc.ppublccctthiicccsieeelellelee
didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: btttps:/nneuue
Answer: [Yes]
Justification: The research conducted in the paper conforms, every respect, with the NeurlPS Code of Ethics https: http:/pp.....bbiiiicaaceccdeeeee
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 to preserve anonymity (e.g.. if there is special consid- cration 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:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

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

---

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: Our 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/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not 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. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
32

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: httpp:://neuuip.... http://eeaarpps..ecoeeeeeeeeeeee Cc///omffeeeeccc//22///1111 for what should or should be described.
33


Reviews:
[{"review_id": "WeILdpf7fj", "reviewer": "Reviewer_SPDa", "summary": "This paper proposes a new method called optimistic conversion to leverage online learning analysis for offline convex optimization. While several conversion techniques have been developed in the past, achieving an $O(1/T^2)$ convergence rate for offline smooth convex optimization typically required analysis of optimistic online methods. In contrast, the proposed optimistic conversion enables the derivation of an offline algorithm equivalent to Nesterov's accelerated gradient method using only a simple, non-optimistic online gradient descent, while still attaining the $O(1/T^2)$ convergence. In the strongly convex case, linear convergence can also be achieved. Moreover, this conversion facilitates the development of universal methods that do not rely on smoothness, as well as stochastic variants.", "questions": "Do the universal algorithms presented in Section 3.3 achieve linear convergence, similar to Theorem 3, when applied to strongly convex and smooth functions?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**  \n- The paper addresses online-to-batch conversion, a timely and actively studied topic in the field.  \n- The idea of optimistic conversion is intriguing and has the potential to aid the design of algorithms with improved theoretical guarantees.  \n- The paper provides a thorough review of prior work, making it a valuable introduction to online-to-batch conversion. It also clearly positions the current work within the context of existing literature and describes their relationships well.  \n- The paper is overall well-written and easy to follow.  \n\n**Weakness**  \n- While the paper presents a new framework for algorithm design and analysis, it does not appear to lead to new algorithms that improve upon existing theoretical results at this stage.", "was_revised": true, "final_justification": "- The proposed optimistic conversion appears promising and helps simplify algorithm design.\n- The authors responded clearly and adequately addressed the concern regarding universality for strongly convex objectives.", "rebuttal": "We sincerely thank you for your positive feedback and for recognizing the value of our paper. We appreciate the opportunity to clarify the theoretical contribution of our work and to address your question regarding the universal algorithm.\n\n---\n\n**W.** While the paper presents a new framework for algorithm design and analysis, it does not appear to lead to new algorithms that improve upon existing theoretical results at this stage.\n\n**A1.** Thank you for the comment. We agree with the reviewer's observation that our work does not improve upon the *known optimal convergence rates*. However, it does not mean that further exploration on this problem is unnecessary. \n\nThe main contribution of our paper lies on a different, yet equally important, axis: **we propose powerful optimistic online-to-batch (O2B) conversions for designing and understanding optimal algorithms in convex optimization.** Our contribution is analogous to the long thread of research that continues to provide new perspectives on Nesterov's Accelerated Gradient (NAG) method, decades after its discovery.\n\nSpecifically, our more powerful optimistic O2B conversions can **reduce the burden of algorithm design**. For example, in the convex smooth optimization, a simple OGD suffices to achieve the optimal rate. Besides, in the universal setup, our optimistic O2B conversion allows **a single-step OGD with one gradient query** in each iteration to achieve the optimal universal convergence, which **cannot** be done by previous works. Finally, as explained in Sec 4, the progress in this thread might also provide **new understandings of the classical NAG from the perspective of online learning**. To make this point clearer, we have revised the paper to better clarify our contributions in this regard.\n\n---\n\n**Q.** Do the universal algorithms presented in Sec 3.3 achieve linear convergence, similar to Theorem 3, when applied to strongly convex and smooth functions?\n\n**A2.** Thank you for the insightful question! Formally, for $\\lambda$-strongly convex objectives, a universal method is expected to achieve $O(\\exp (-T / \\sqrt{\\kappa}))$ for smooth functions and $O(1/ [\\lambda T])$ in the Lipschitz case, where $\\kappa = L/\\lambda$ represents the condition number. **How to achieve the optimal rates is still an open problem and cannot be easily solved via direct extensions of the universal method in Sec 3.3.** Specifically, in our method, the O2B conversion weight $\\alpha_t$ is chosen as $\\alpha_t = C A_{t-1}$, where $C$ is a constant depending on the condition number $\\kappa$. Therefore, in the universal setup where the smoothness parameter $L$ is unknown, achieving universality is more challenging than the convex case because the method needs to estimate the smoothness parameter on the fly. There are some preliminary and sub-optimal results, e.g., the pioneering work of Levy (2017), where the author obtained a *non-accelerated* rate of $O(\\exp (-T / \\kappa) \\cdot T / \\kappa)$ for strongly convex smooth objectives and $O((\\log T) / T)$ for strongly convex Lipschitz objectives. We have a separate paper under review that handles this problem, justifying its separate treatment due to its complexity. And we will add a remark in Sec 3.3 to clarify this issue in the revised version.\n\n---\n\nWe believe that our work offers valuable contributions to the community in the field of online-to-batch-conversion-based methods. We hope our responses have addressed your concerns and would appreciate a reevaluation of our paper's score. And we are happy to provide further clarifications if needed during the following author-reviewer discussions."}, {"review_id": "HXkAa41d9q", "reviewer": "Reviewer_zkAz", "summary": "This paper proposes a new online-to-batch conversion method and analysis technique to achieve acceleration from online gradient descent with gradients weighted differently. In contrast, previous online-to-batch conversion achieved accelerated rates when using some *optimistic* online learning algorithms. The idea of the analysis is to, in some sense, incorporate optimism only in the analysis, not as a requirement on the OL method itself. With that they show accelerated rates in the smooth and smooth strongly convex cases. Moreover, using their online-to-batch techniques they also show how to get acceleration without knowing the smoothness constant beforehand when the domain is bounded, what is known as an *universal algorithm*.", "questions": "My main question is whether Algorithm 2 (and Theorem 5) depend on the use of online gradient descent, of whether we could use (and if it makes sense) to use other online learning algorithms.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I believe this is a very strong submission: clearly written, with an elegant main idea and with very nice results. Of course, I may be missing some of the context from the recent work on online-to-batch conversion that happened more recently, but this feels like a simple method with a clean analysis and very strong results. I really appreciated the thorough discussion that the authors do with respect to related work. I was familiar with the use of the Fenchel game from Abernethy et al., so the connection to this work was quite interesting to me. Beyond acceleration in both smooth and smooth + stongly convex case, the authors also show how to get acceleration in bounded domains without know the smoothness constants, which was a very neat addition. I did not have the time to check the proofs for correctness properly, but the ideas in this paper are quite interesting.\n\nThe one main thing I was a bit confused was whether this optimistic online-to-batch conversion is restricted to online gradient descent. Algorithm 1 is describe with a general OL method and I know some of the results end up using O-t-B conversion with other algorithms, but in the paper the optimistic O-t-B conversion is described explicitly using OGD. I did not have the time to check whether Theorem 5 actually depends on the algorithm being OGD and I feel it was a bit confusing how dependent on it this method is.", "was_revised": true, "final_justification": "I might still edit this if the discussion with the authors develops further. Currently it seems like the main contribution of this paper is a new perspective (optimistic O2B) to obtain known results and algorithms. Some of the convergence proofs at some points are very close to those of WA18, but it seems, to me at this point, quite non-obvious how this work gets to the same \"absract bounds on $\\alpha$-regret\" as WA18 starting from their framework. Since O2B reductions are quite important in OL, I think that this new perspective on known results is going to be of interest to the community.", "rebuttal": "Thank you for your strong support for our paper! In the following, we answer your question about whether online gradient descent is coupled with our optimistic online-to-batch conversion.\n\n---\n\n**Q.** My main question is whether Algo 2 (and Thm 5) depend on the use of online gradient descent, of whether we could use (and if it makes sense) to use other online learning algorithms. \n\n**A.** Thank you for the insightful question. The choice of online learning algorithms is **flexible**. We chose to present our main results with Online Gradient Descent (OGD) primarily to highlight the power of our optimistic conversion framework: **it simplifies the underlying task to a degree where even a standard algorithm like OGD is sufficient to achieve optimal rates**.\n\nIn the future, when handling more challenging tasks, such as *parameter-free accelerated optimization*, as discussed in Line 298, traditional conversion requires the online algorithm to achieve both parameter-freeness and optimism. On the other hand, since our conversion incorporates optimism intrinsically, we only require the online algorithm to enjoy parameter-freeness. This could reduce the burden of online algorithm design, which might make such advancements possible. We leave this as a promising future direction.\n\n---\n\nOnce again, we are very grateful for your positive feedback and valuable encouragement. We would be happy to provide any further clarifications needed."}, {"review_id": "Ls1u8aQBBr", "reviewer": "Reviewer_Wpuw", "summary": "This paper studies an online to batch conversion approach to convex optimization. The primary contribution of this work is demonstrating that online algorithms with optimistic hints are not necessary to obtain accelerated rates. The key change to the algorithm is evaluating the update gradient at a point which approximates the average of the iterates, without requiring access to (yet to be determined) next iterate. Due to the clever choice of evaluation point, a simple online to batch analysis results in an optimal rate with no requirement for direct hinting. The method can be extended to utilize adaptive step sizes in a manner robust to smoothness assumptions.", "questions": "- My reading is that Theorem 4 implicitly requires unconstrained problem to ensure $ x_t $ is feasible and $ \\nabla f( x^* ) = 0 $ for the final inequality in proof. Is this the case? If so you should make this explicit in the statement of the the theorem. Also the proof could be tightened by using the fact that $|| \\nabla f(\\tilde{x}_1) || = || \\nabla f(\\tilde{x}_1)- \\nabla f( x^* )|| \\leq L|| \\tilde{x}_1 - x^* ||$. \n- Could you discuss why the change in the algorithm is necessary in Theorem 4?  \n- You should make the $t$ values (e.g., $t\\geq0$?) that (16)-(17) are applicable explicit and prove the edge cases hold (particularly for (17) which includes the $x_{t-2}$ term). Similarly, you should define the edge cases for $\\tilde{x}_0$, $\\bar{x}_0$, and $A_0$ etc.\n- Could you elaborate on how (12) is obtained? What should $\\beta_{t-1}$ be?\n- line 566 why is the expectation conditioned on $x$?\n- I think that Section 1.3 could benefit from being cut down into a few dot points which highlight the main contributions.\n- Could you explain the working after line 594?\n\nTypos:\n- line 162: $\\ell_t$ is a scalar, so this statement doesn't make sense.\n- line 346: worth should be worthy?\n- In the working after line 476 I think the final equality should be an inequality. \n- line 527: \"the second step uses Lemma 3\" should this be Lemma 2?\n- line 557: should $2G^2$ be $4G^2$ after the last inequality?\n- line 585: filtration should be adapted to $\\tilde{x}_i$s instead of $x_i$s?", "limitations": "See strengths/weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "### Strengths\n- The explanation of the mechanism of the update mechanism, in comparison to previous anytime online to batch conversion is insightful and intuitive. Generally I think the discussion of previous anytime online to batch algorithms is good. \n- Most of the mathematical exposition is clear and correct (minus a few technicalities; see questions). Most of thee proofs are relatively easy to follow.\n\n### Weaknesses \n\n**Insufficient Differentiation/Discussion of Previous work**\nMy primary concern is that I am unsure whether this paper is a sufficiently novel/interesting contribution to the community. In particular, I don't think that you sufficiently highlight the connection to Wang and Abernethy (2018) on the following fronts:\n- Algorithm 2 in their paper looks to be essentially identical to your update. This fact should be highlighted in your remark/previous work\n- The analysis leading to your Theorem 2 is very similar to their Theorem 2 and Corollary 1.\n- Theorem 4 in your paper also appears to borrow heavily from their paper.\n- Since your step is the same as Algorithm 2 in their paper and Proposition 1 is lifted directly, the results from Section 4 don't feel that interesting. They are more like previous work. Furthermore, I don't think you can claim that you have established the equivalence between your method and NAG as you do in line 100.\n\nOverall I don't believe that the connection to Wang and Abernethy (2018) is sufficiently explained by the paper (in particular Remark 1 is certainly insufficient) which leaves me doubtful of exactly where the boundary between this contribution of this work and previous work is. Note that I don't have an issue building off of previous work per se, but I don't think this paper accurately summarises the relationship to previous work. Could you outline specifically how your method can be differentiated from this previous work/what your specific contribution is? So far as I can tell the adaptive step size is new but I am unsure how strong this result is.\n\n**Stochastic Case**\nOther works analyze the stochastic case in conjunction with the deterministic case, e.g, Cutosky (2019), Kavis (2019) and Joulani et al. (2022b). In particular, expectation bounds (under unbiased and bounded variance gradients assumptions) with some dependence on $\\sigma$ usually arise naturally from the online to batch framework. What were the barriers to taking this approach for, say, theorem 1-4? The stochastic analysis in this paper is focussed on one specific case and an almost sure boundedness (which is stronger than a bounded variance assumption).\n\n**Numerical Evaluation**\nA numerical comparison could significantly elevate the contribution of this paper. In particular, I would be interested to see if there is an advantage to integrating the optimism into the evaluation point, rather than though a hinting mechanism (even if there is a negative result).\n\n**Conclusion**\nOverall I am leaning towards a borderline reject pending your response to the weaknesses/technical questions. I could move to accept/reject depending on your responses. I am particularly interested if you can clearly explain 1. Your contribution over and above the results from Wang and Abernethy (2018) and 2. How you will adjust your introduction/summary of previous work to highlight how connected your method is with Wang and Abernethy (2018).", "was_revised": true, "final_justification": "As noted in my original review, my primary concern with this paper is the insufficiently acknowledged similarity to [WA18], including an identical algorithm and closely related analysis in Theorems 1–4. Over the course of the rebuttal, the authors acknowledged the need to revise their manuscript to more clearly reflect this connection and to reframe their contribution as an O2B-based analysis of an existing algorithm. That said, the paper does offer a nontrivial extension—specifically, the development of an adaptive step size scheme that avoids additional gradient evaluations, as presented in Theorems 5 and 6. With the substantial revisions outlined in the rebuttal, I would lean towards accepting the paper. However, since reviewers will not have the opportunity to evaluate the revised manuscript (including the promised numerical results), I believe the paper remains at best borderline at this stage. Ultimately, the decision hinges on whether the AC and reviewers trust the authors to carry out the proposed changes effectively.", "rebuttal": "Thanks for the valuable feedback and very careful check of our paper! Below, we restate the contributions of our paper and the major differences from Wang and Abernethy (2018) [WA'18], hoping to resolve your concerns.\n\n---\n\n**W1 & W2. About the connection/difference to [WA'18] and our own contributions.**\n\n* Algo 2 in their paper looks to be essentially identical to your update. The analysis leading to your Thm 2 is very similar to their Thm 2 and Cor 1.\n* Thm 4 in your paper also appears to borrow heavily from their paper.\n* The results from Sec 4 are more like previous work. Furthermore, I don't think you can claim that you have established the equivalence between your method and NAG as you do.\n\n**A1.** Thank you for your comments and suggestions. Below, we clarify the connections/differences with [WA'18] and explain our contributions beyond their work.\n\n* **Clarifications of the connection to [WA'18]:** First, we clarify that the convex optimization can be solved via an *online-to-batch (O2B) conversion* and an *online algorithm*. The design and analysis of online algorithms *heavily* depend on the O2B conversions. In our paper, **Thms 1,3,5 are our proposed optimistic O2B conversions** and **Thms 2,4,6 are the corresponding algorithmical analyses**. In this sense, **Thms 2,4,6 are actually corollaries of Thms 1,3,5**, and **the reviewer might mistake Thms 2,4,6 as our main contributions**. We will use \"corollary\" to state the current Thms 2, 4, 6 to clarify our own contributions to the reader. Below, we provide one-by-one clarifications.\n    * **Thm 2 is a corollary of Thm 1**. In Thm 1, our work and [WA'18] obtain the same intermediate result of $A_T [f(\\bar{x}\\_T) - f(x^\\*)] \\le \\sum_{t=1}^T \\langle \\alpha_t \\nabla f(\\tilde{x}\\_t), x_t - x^* \\rangle + \\sum_{t=1}^T \\alpha_t \\langle \\nabla f(\\bar{x}\\_t) - \\nabla f(\\tilde{x}\\_t), x_t - x_{t-1} \\rangle$.  As explained in Line 179, the first term of the RHS is a look-ahead online problem, and solving it only requires the *standard* OGD with *common* analyses, making our Thm 2 and the proof similar to theirs. **We will add a remark to explicitly state that our Thm 1 obtains the same intermediate result as [WA'18], but from a completely different perspective, in the next version.**\n    * **Thm 4 is a corollary of Thm 3**. Both our work and [WA'18] aim to handle an online learning problem with regret: $\\sum_{t=1}^T \\alpha_t[h_t(x_t)-h_t(x^*)]$, where $h_t(\\cdot)$ is a strongly convex surrogate loss. Therefore, solving this *standard* online problem leads to similar analyses. **We will add a remark to state the analytical similarity of Thm 4 to [WA'18].**\n    * Thanks for your advice. The statement of \"we establish the equivalence between our method and the classical NAG\" in Line 100 is imprecise, and **we will revise it to give correct credits to [WA'18] in the next version.** Note that in Prop 1, we have given the proper credits by citing their Thm 4. Our intention was not to claim this connection as our contribution, but to highlight this interesting connection between recent O2B-based methods and classical ones such as NAG and HB for readers.\n\n* **Differences from [WA'18]:** \n    * **Techniques behind our Thm 1 and Thm 3 are entirely new and different from [WA'18]**, as explained in Remark 1. They modeled the convex optimization problem as a two-player Fenchel game using the definition of Fenchel conjugate, while we start from the line of stabilized O2B conversion initiated by Cutkosky (2019).\n    * Furthermore, we aim to design a **universal-to-smoothness** method that does not know whether the objective is smooth or Lipschitz and can adapt to both cases automatically. This is **not** studied by [WA'18]. For this problem, we propose **a novel optimistic O2B conversion (in Thm 5)**, which allows **a single-step OGD with one gradient query** per iteration with the optimal universal convergence, which **previous works cannot do**.\n\nIn general, we **make a step forward in the field of O2B conversions by proposing the more powerful optimistic O2B conversions (in Thm 1,3,5)**, which help achieve the optimal rates in (strongly) convex optimization and the universal setup with simple online algorithms.\n\n---\n\n**W3.** About the stochastic cases. \n\n- Other works analyze the stochastic case in conjunction with the deterministic case, e.g, Cutkosky (2019), Kavis et al. (2019), and Joulani et al. (2022b). The stochastic analysis in this paper is focused on one specific case and an almost sure boundedness (stronger than a bounded variance assumption).\n- What were the barriers to taking this approach for Thms 1-4? \n\n**A3.** Thanks for the comments. \n\n- For a **bounded** domain, a common assumption required by previous works (e.g, Cutkosky, Kavis et al., and Joulani et al.), extending to the stochastic case is **straightforward**. Therefore, we defer it to the appendices due to page limits. Besides, we assume an almost sure boundedness because we aim to achieve **high-probability** rates (please kindly refer to our Thm 7), which is **stronger** than the *expectation* rates obtained by previous works, where a bounded variance assumption suffices.\n- On the other hand, handling stochastic noises in *unbounded* domains is challenging. Because our Theorem 1-4 holds even in *unbounded* domains, extending them to the stochastic setup is beyond the scope of this work, and we leave them as an interesting future direction. Thanks for the question.\n\n**W4.** Numerical Evaluation. In particular, I would be interested to see if there is an advantage to integrating the optimism into the evaluation point, rather than through a hinting mechanism (even if there is a negative result).\n\n**A4.** Thank you for the question. We agree that a numerical comparison would further strengthen the paper. As PDF attachments and external links are not permitted in this year's rebuttal, **we commit to adding experiments** comparing our algorithm with hinting-based methods (e.g., Cutkosky, 2019; Kavis et al., 2019) in the camera-ready version.\n\n---\n\n**Q1.** Thm 4 implicitly requires an unconstrained problem to ensure $x_t$ is feasible and $\\nabla f(x^*)=0$ for the final inequality in the proof.\n\n**A5.** Thank you for the sharp observation. You are right that Thm 4 indeed requires an unbounded domain. As explained in Line 128, the boundedness is only required for our universal method in Sec 3.3. And in Thm 4, we only require a smoothness assumption and do **not** import the boundedness assumption. **We will emphasize this independence in the revised version.**\n\n**Q2.** Could you discuss why the change in the algorithm is necessary in Thm 4?\n\n**A6.** Thanks for the question. This is a **necessary** adaptation to handle the geometry of strongly convex problems. The change allows the algorithm to leverage strong convexity to achieve a faster, linear convergence rate, which is analogous to how online learning algorithms are modified when moving from convex to strongly convex settings.\n\n**Q3.** You should make the $t$ values (e.g., $t \\ge 0$?) that (16)-(17) are applicable explicit and prove the edge cases hold (particularly for (17), which includes $x_{t-2}$). Similarly, you should define the edge cases for $\\tilde{x}_0$, $\\bar{x}_0$, and $A_0$ etc.\n\n**A7.** Thank you for the advice to make our analysis more rigorous. We will add the edge definitions of $A_0 = 0$ and $\\tilde{x}_1 = x_0$ such that: (14), (15), (16) hold when $t=1$; and (17) holds from $t=2$ which we indeed use from $t=2$, as in Eq. (21). **We will add the proof of the edge cases in the next version**.\n\n**Q4.** Could you elaborate on how (12) is obtained? What should $\\beta_{t-1}$ be?\n\n**A8.** Thank you for the question. The proof of (12) follows a similar argument to Eq. (25) in the proof of Prop 1 by replacing $x_t = x_{t-1} - \\eta_{t-1} g_{t-1}$ into (25). Therefore, $\\beta_{t-1} = \\frac{\\alpha_t A_{t-2}}{A_t \\alpha_{t-1}}$ in (12), which is the same as that in (25). We **will add a corresponding proof in the appendix in the next version.** \t\n\n**Q5.** Line 566 why is the expectation conditioned on $x$?\n\n**A9.** Thank you for the question. This is a standard assumption in stochastic optimization and shows that the unbiasedness does *not* depend on what the current decision $x$ is, which is reasonable and is a fundamental learnable assumption in stochastic optimization.\n\n**Q6.** Sec 1.3 could benefit from being cut down into a few dot points that highlight the main contributions.\n\n**A10.** Thanks for the suggestion. **We will restructure Sec 1.3 into a list** to highlight our main contributions more clearly.\n\n**Q7.** Could you explain the working after line 594?\n\n**A11.** We are not sure if we understand your question concretely. As we aim to prove our algorithm is *universal to smoothness*, we discuss two cases separately after Line 594. In the smoothness case, the main proof technique is the self-confident tuning, a clever idea from online learning. In the non-smoothness case, we directly bound the term using the assumption of $\\\\|g(x)-\\nabla f(x)\\\\| \\le \\sigma$. If our answer does not solve your question, we welcome further discussions in the upcoming discussion period.\n\n**Q8.** About Typos and Format. \n\n**A12.** Thank you for your careful reading. We will correct all the noted typos and formatting issues in the revised version. For brevity, we are not listing them one by one here due to the character limit.\n\n---\n\nWe believe that our work offers valuable contributions to the community and will carefully revise the paper according to your suggestions and questions. If our responses have adequately addressed your concerns about the contributions of our work, we kindly request a reevaluation of our paper's score. And we are happy to provide further clarifications if needed during the following author-reviewer discussions."}, {"review_id": "kBoAWsyHhj", "reviewer": "Reviewer_LDsK", "summary": "This paper provides an overview and some new theory for online-to-batch conversions with a focus on universal and accelerated approaches.", "questions": "See Above", "limitations": "See Above", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Online-to-batch conversions are not yet well understood in the optimization community and I think this paper does a good job of introducing existing approaches and expanding on them.\n\n- The proof techniques for the theory are a different and interesting take compared to the other approaches in the existing literature. Much of the overview content will be already familiar to researchers in the area, while for others it will be a good introduction and it's very useful to bring all these results together and provide a clarifying view.\n\n- The exact correspondence between certain instantiations of optimism methods and Nesterov's acceleration is generally known to researchers in the area but is not clearly indicated in the literature, so the discussion here is welcome. \n\n- The use of the average iterate as the location of gradient evaluation was also separately discovered in the stochastic optimization literature separately from the online learning community, under the name “Primal Averaging” by Tao et al. [2020], and was further explored in “The Power of Factorial Powers” (Defazio and Gower, 2020). Some discussion of this related work would be welcome. A variant of these  online-to-batch conversions were also very recently shown to actually be usable for real-world deep learning training in \"The Road Less Scheduled\".\n\n- The UniXGrad paper (cited briefly already) also uses a similar difference-of-gradient's to define a universal method. Is there any relation between the methods? the UniXGrad paper uses general divergences which makes it not immediately clear to me.", "was_revised": true, "final_justification": "I'm generally in agreement with the other positive scoring reviewers, the relation to existing work is ok since this work generalizes the existing work.", "rebuttal": "Thank you for the positive feedback and appreciation of our work! We answer your questions in the following.\n\n---\n\n**Q1.** The use of the average iterate as the location of gradient evaluation was also separately discovered in the stochastic optimization literature separately from the online learning community, under the name \"Primal Averaging\" by Tao et al. [2020], and was further explored in \"The Power of Factorial Powers\" (Defazio and Gower, 2020). Some discussion of this related work would be welcome. A variant of these online-to-batch conversions were also very recently shown to actually be usable for real-world deep learning training in \"The Road Less Scheduled\".\n\n**A1.** Thank you for the suggestion. We will discuss the works about the use of the average iterate as the location of gradient evaluation in the revised version to provide readers a more comprehensive review of the literature. We will also discuss the paper of \"The Road Less Scheduled\" about its important application to real-world deep learning training.\n\n---\n\n**Q2.** The UniXGrad paper (cited briefly already) also uses a similar difference-of-gradient's to define a universal method. Is there any relation between the methods? the UniXGrad paper uses general divergences which makes it not immediately clear to me.\n\n**A2.** Thank you for the question. Both UniXGrad and our Sec 3.3 aim to design a universal method in convex smooth optimization. The difference is that UniXGrad uses $\\alpha_t \\nabla f(\\bar{x}_t)$ as the gradient and $\\alpha_t \\nabla f(\\tilde{x}_t)$ as the optimism (their mirror-prox method can be seen as a variant of optimistic online learning algorithm), while our algorithm requires **only one gradient** of $\\alpha_t \\nabla f(\\tilde{x}_t)$ and **no optimism**, because **our optimistic online-to-batch conversion has already incorporated optimism directly in the analysis**. We will revise the paper to explain the difference between our method and UniXGrad more clearly.\n\n---\n\nWe will carefully revise the paper and add the related works according to your suggestions. Thank you!"}, {"review_id": "435EjhWkN4", "reviewer": "Reviewer_h8Yk", "summary": "This paper proposes optimistic online-to-batch conversions, which incorporate the optimistic approach into the online-to-batch stage, enabling the use of non-optimistic methods for achieving the same rate as optimistic methods with stabilized online-to-batch conversions (Cutkosky 2019). This enables the authors to achieve acceleration, both in convex and strongly convex settings, and universality, with a single query per iteration, in contrast to previous work. Additional relations between online approaches, NAG, and the heavy-ball method are discussed.", "questions": "1. Can the authors elaborate on what results, if any, were not established by previous work (and cannot be easily established from previous results)?\n2. Beyond elegance (and potentially practical use), is the single query per iteration of particular importance beyond saving a constant factor in the convergence rate? I do appreciate the simpler algorithm but missed if there is something beyond simplicity and constant factors.\n3. Does the approach enable guarantees in the strongly convex case with stochastic noise? I am aware that the $\\sigma / \\sqrt{T}$ term cannot be improved. (This is a question out of interest, it is ok if the authors simply do not know the answer.)\n\nOverall, this paper is interesting to read and provides some insights into acceleration and universality, with a somewhat simpler universal algorithm. That being said, articulating new guarantees or benefits achieved from this new perspective would be much appreciated.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The presentation is well structured, helping the reader understand the difference between existing online-to-batch conversions and the new proposed conversions.\n2. The results cover several cases of interest, including convex Lipschitz and convex smooth, with and without stochastic noise, and strongly convex smooth case.\n\n**Weaknesses**\n\n3. My main concern is the novelty of the results. This work mainly offers a new perspective, while each of the results can be obtained from previous work, either directly or with a minor extension (e.g., universal algorithms, Nesterov 2015, Kavis et al. 2019, Rodomanov et al. 2024a,b, or using restarts to support the strongly convex case).", "was_revised": true, "final_justification": "As pointed out in the discussion with another reviewer (thanks for the through review!), this paper draws somewhat heavily from,  [WA'18] limiting the significant of this work. That said, the universality result still can be of value to the community, leading me to my limited yet positive support of this paper.", "rebuttal": "We sincerely appreciate your feedback. Below we hope to resolve your concerns about the contributions of our paper.\n\n---\n\n**W & Q1.** About comparison with previous works and new results.\n\n* This work mainly offers a new perspective, while each of the results can be obtained from previous work, either directly or with a minor extension (e.g., universal algorithms, Nesterov 2015, Kavis et al. 2019, Rodomanov et al. 2024a,b, or using restarts to support the strongly convex case).\n* Can the authors elaborate on what results, if any, were not established by previous work (and cannot be easily established from previous results)? \n\n**A1.** Thank you for the comments and question. Below we first explain the differences with previous works and then reclarify the main contributions of our work.\n\n* Compared with Nesterov (2015), our universal method holds in the stochastic setup (in Thm 7 in the appendix) while theirs does not. And their line-search based methods cannot be directly extended to the stochastic setup.\n* Compared with Kavis et al. (2019) and Rodomanov et al. (2024a,b), although all the mentioned works can achieve the optimal universal rates, **the involved techniques are completely different**. Besides, our **improved optimistic O2B conversion** allows **the simple OGD with one gradient query** per iteration to achieve the optimal universal rates. This **cannot** be done by the  mentioned works and previous ones.\n* Finally, we would like to note that our algorithm does not need the restarting scheme because we do not consider stochastic gradients for strongly convex objectives.\n\nThe contribution of this work is not obtaining new or better convergence rates, as all convergence rates in this work are *classical and optimal*, and thus cannot be improved further. Our main contribution lies in making **a step forward in the line of online-to-batch (O2B) conversion**, where **we propose several powerful optimistic O2B conversions (in Thm 1,3,5) such that using simple OGD can achieve the optimal convergence**, which **cannot** be done via previous O2B-based works. We illustrate the effectiveness of our optimistic O2B conversions in the convex smooth optimization, strongly convex smooth optimization, and the universal setup. Besides, our findings also provide an interesting understanding of the classical NAG from the perspective of online learning, as shown in Sec 4.\n\n---\n\n**Q2.** Beyond elegance (and potentially practical use), is the single query per iteration of particular importance beyond saving a constant factor in the convergence rate? I do appreciate the simpler algorithm but missed if there is something beyond simplicity and constant factors.\n\n**A2.** Thank you for the question. If we fix the total budget of gradient queries to $T$, reducing the queries per iteration from $2$ to $1$ improves the final rate by a constant factor of $4$ for our results. However, the key messages we aim to convey here are: \n\n1. **Simplicity is a primary pursuit in the algorithm design**. For example, previous studies (e.g., Kavis et al. (2019), Joulani et al. (2020)) need optimistic algorithms for this purpose while this paper only requires the simple OGD.\n2. We view this improvement not just as a constant-factor gain, but as a **concrete demonstration of the power of our new optimistic O2B conversion**. It highlights that our framework is more efficient at extracting information to achieve acceleration. \n3. We achieve the universality to smooth via a simple OGD with one gradient query per iteration, which cannot be done by previous O2B-conversion-based methods.\n\nWe will add a clarifying statement to the paper to make our key messages clearer to readers.\n\n---\n\n**Q3.** Does the approach enable guarantees in the strongly convex case with stochastic noise? I am aware that the $\\sigma / \\sqrt{T}$ term cannot be improved. (This is a question out of interest, it is ok if the authors simply do not know the answer.)\n\n**A3.** Thanks for the insightful question! We have also been studying this problem recently. Formally, for **$\\lambda$-strongly convex** and $L$-smooth objectives with **stochastic** gradients, the optimal convergence rate is $O(\\exp(-T/\\sqrt{\\kappa}) + \\sigma/[\\lambda T])$, where $\\kappa = L/\\lambda $ denotes the condition number. Note that the dependence of $T$ in the noise term is $\\sigma/T$ but not $\\sigma/\\sqrt{T}$. Classical methods, e.g., [1,2,3], all require a restarting scheme (as the reviewer mentioned in the 'Weakness' part) to achieve this optimal rate. \n\nIn the **O2B-conversion-based** line of research, achieving the optimal convergence is still an **open problem** and highly non-trivial. Therefore, extending our method directly to this setup is challenging and beyond the scope of this work. Actually, we have recently solved this problem, which is not published yet. The solution relies on a substantially different online algorithm design (without the restarting scheme) and novel analyses. It is welcome that you can follow our subsequent works for the progress in this problem :)\n\n---\n\nWe have taken your feedback seriously and will revise the paper to make these points about our contribution clearer. If our responses have properly addressed your concerns, we kindly request a reevaluation of our paper's score. Thank you!\n\n**References:**\n\n[1] Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization II Shrinking Procedures and Optimal Algorithms, 2013\n\n[2] Optimal Regularized Dual Averaging Methods for Stochastic Optimization, 2012\n\n[3] A Universally Optimal Multistage Accelerated Stochastic Gradient Method, 2019"}]

Author rebuttal:

Meta-review: This paper introduces optimistic online-to-batch conversions that incorporate optimism into the conversion step, allowing simple online gradient descent to achieve accelerated convergence. The framework also leads to a universal method that achieves optimal rates with only one gradient query per iteration, improving over prior work.

Reviewers appreciated the paper's clarity, clean analysis, and strong positioning within the literature. They highlighted the elegance of the optimistic conversion idea and the novel universality result, which goes beyond earlier work. While some overlap with Wang & Abernethy (2018) was noted, the authors clarified that these are corollaries of their framework, which provides a new perspective and enables the new contributions.

Overall, the paper is technically solid, well written, and offers both conceptual clarity and new results.
Decision: Accept (poster)