Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism
Authors: Francisco Patitucci
Ruichen Jiang
Aryan Mokhtari
Venue: ICLR 2026 Poster (2026)
Keywords: Online-to-nonconvex conversion
Optimistic Gradient Descent
Smooth Nonconvex Optimization
Primary area: optimization

Abstract: A recent breakthrough in nonconvex optimization is the online-to-nonconvex conversion framework of Cutkosky et al. (2023), which reformulates the task of finding an $\varepsilon$-first-order stationary point as an online learning problem. 
When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves
a complexity of $ \mathcal{O}(\varepsilon^{-1.75}\log(1/\varepsilon)) $ in the deterministic case and a complexity of $ \mathcal{O}(\varepsilon^{-3.5}) $ in the stochastic case.
However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves a fixed-point equation to construct hint vectors for an optimistic online learner, introducing an extra logarithmic factor; (ii) the stochastic method assumes a bounded second-order moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used in the two settings.
In this paper, we address these issues by introducing an online optimistic gradient method based on a novel **doubly optimistic hint function**. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assumptions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due to smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by $\sigma^2$, we obtain a unified algorithm with complexity $\mathcal{O}(\varepsilon^{-1.75} + \sigma^2 \varepsilon^{-3.5})$, smoothly interpolating between the best-known deterministic rate and the optimal stochastic rate.

Published as a conference paper at ICLR 2026
IMPROVING ONLINE-TO-NONCONNE CONVERSION FOR SMOOTH OPTIMIZATION VIA DOUBLE OPTIMISM
Francisco Patitucci' Ruichen Jiang' Aryan Mokhtari
'Tee University of Texas at Austin Google Research (Epatitucci, )
@utexas. edu, mokhtari@austing wtwpsustttiiuexese.o...eu..
ABSTRACT
A recent breakthrough in nonconvex optimization is the online-to-nonconvvr conversion framework of Cutkosky al. (2023), which reformulates the task of finding an e-first-order stationary point as an online learning problem. When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves complexity of O log(1/e)) in the deterministic case and a complexity of O 3.5) in the stochastic case. However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves fixed-point equation to construct hint vectors for an optimistic online learner, introducing extra logarithmic factor; (ii) the stochastic method assumes a bounded second-ordes moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used the two settings.
In this paper, we address these issues by introducing online optimistic gradient method based on novel doubly optimistic hint function. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assump- tions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by o², we obtain unified algorithm with complexity (( -175 1.75 + g2g-3.5) -35),, smoothly interpolating
between the best-known deterministic rate and the optimal stochastic rate.
INTRODUCTION
In this paper, we consider an unconstrained minimization problem
min Fxx). xER
where F Rd + IR is smooth but possibly non-convex function bounded from below. With access to a deterministic gradient oracle, it is well known that gradient descent (GD) can find an e-stationary point within ((s-2) iterations when the gradient of F' is Lipschitz continuous, which is worst-case optimal among all first-order methods (Carmon et al.] 2020). In the stochastic setting, where the oracle returns an unbiased noisy gradient with variance bounded by o², stochastic gradient descent (SGD) achieves a complexity of O( o²g-4) Ghaadimi & Lan 2013). which is likewise worst-case optimal (Arjevani al. 2023).
Interestingly, when both the gradient and the Hessian of F are Lipschitz continuous, it becomes possible to outperform standard GD or SGD. In the deterministic setting, Carmon et al. (2017) 7) pro- posed an accelerated gradient-based method that exploits directions of negative curvature, achieving a complexity of O( -1.75 log(1 (1/ 1/E)). Concurrently, Agarwal et (2017) introduced an approximate variant of the cubic regularization method (Nesterov & Polyak 2006). which uses only first-order gradients and access to Hesstinn-vector vector products, and achieves a complexity of O(E -1.55 log(d/=)),
"Equal contribution

---

Published as a conference paper at ICLR 2026
More recently, Li & Lin (2022 2023) eliminated the logarithmic factor from these bounds by in-
corporating restarting techniques into accelerated gradient and heavy-ball methods, achieving the state-of-the-art complexity of O( 1.75). However, the methods proposed in (Carmon et al. 2017 Agarwal et al. 2017) are complex and rely on multiple subroutines to exploit negative curvature, while the restarting techniques in (Li & Lin 2022 2023) involve lengthy derivations, and their extension to the stochastic setting remains unclear. In the stochastic setting, similar improvements over SGD have been achieved using different algorithmic techniques (Allen-Zhu 2018a by Tripuraneni al. 2018
Fang et al. 2019). To our knowledge, the best known result is due to Cutkosky & Mehta (2020), who proposed normalized SGD with momentum and extrapolation, achieving O  3.5) While this method attains the optimal rate of 0 for the stochastic setting (Arjevani et al. (020), it fails to achieve the accelerated rate of D(e-1177 for the deterministic setting. Notably, to the best of our knowledge, no single unified algorithm simultaneously attains the best-known guarantees in both settings.
To address this gap, promising step toward unification is the online-to- (O2NC) conversion proposed in (Cutkosky et al. 2023), which offers a general and powerful framework for nonconvex optimization across various settings. The core idea is to reduce the problem of finding stationary point of a nonconvex function to an online learning problem over the update directions. This reduction enables converting an online learning algorithm into a nonconvex optimization method, which greatly simplifies convergence analysis. In the smooth setting considered in this paper, by instantiating two different online learning algorithms, Cutkosky al. (2023) establish a complexity of O(s 1.75 (1g)) in the deterministic case and O 5.) in the stochastic case, where G2 an upper bound on the second-order moment of the stochastic gradient. Despite its conceptual elegance, the O2NC framework has several limitations. First, in the deterministic setting, the algorithm relies on a fixed-point iteration as a subroutine, introducing an extra logarithmic factor in the convergence rate and adding complexity to the algorithmic design. Second, in the stochastic setting, it requires a stronger assumption that the second-order moment of the stochastic gradient is uniformly bounded, which can be restrictive in practice. Third, the framework requires different online learning algorithms for the stochastic and deterministic settings, limiting its modularity and complicating potential extensions.
Our contribution. Building on the O2NC framework, we propose a simple yet effective algorithm that replaces the fixed-point iteration subroutine in (Cutkosky et al. 2023) with single stochastic gradient call at an extrapolated point, achieving a complexity of ( 1.75 - This eliminates the additional logarithmic factor and smoothly interpolates between the best-known deterministic and stochastic rates. Our core idea is a novel doubly optimistic online gradient method, which aims to predict the gradient using a carefully crafted hint function. Inspired by standard optimistic methods (Chiang et al. 2012: Rakhlin & Sridharan, 20013: Joulani et al. 2020). our first optimistic assumption that the discrepancy between the gradient and the hint evolves slowly over time. Crucially, we introduce a second optimism that the update direction itself also evolves slowly, which we exploit using the function's s smoothness to guide the design of the hint. To the best of our knowledge, this is the first algorithm to seamlessly attain the best-known guarantees in both deterministic and stochastic settings, resolving a key limitation of the original O2NC framework.
1.1 ADDITIONAL RELATED WORK
Deterministic setting Beyond the works reviewed in the introduction, Marumo & Takeda (2024a b) built on the restarting technique from (Li & Lin 2022 2023) to develop parameter-free algorithms using line search, thereby removing the need for prior knowledge of -ppeeii- constants. Complementing these upper bounds, Carmon et al. (021) established a lower bound of Q(E # for functions with Lipschitz gradient and Hessian. This leaves a gap of (( + between the best-known upper and lower bounds in this setting. Several works also aimed to find second-orde stationary points (Agarwal et al. 2017: Carmon et al. [2188) JJnn et al. 2018) Allen-Zhu & Li 2018 Xu et al.)
2017 Royer& & Wright 20188] Royer et al. 20200) using gradient Hessian-vector product oracles, but their complexity remains no better than ( -175).
Stochastic setting Several works have shown improved guarantees by either strengthening the oracle or imposing additional restrictions on the noise. Specifically, with a stronger oracle that has access to Hessian-vector products, Arjevani et al. (2020) proposed veriance-reduccion algorithm
2

---

Published as a conference paper at ICLR 2026
that combines stochastic gradients with Hessian-vector products, attaining the optimal complexity of O(a2E 9) Moreover, another line work relies on the mean-squared smoothness assumption on stochastic gradients, i.c., ||| f (x: {) V fly: E) I [ - yl 2 for all x and y with some constant L.; under this condition, variance-reduction based methods such as SPIDER (Fang et al. 2018) and SNVRG (Zhou et al. 2020) achieved complexity of (( Under slightly stricter assumption that (x(x;E) is Lipschitz continuous with probability one, one, Cutkosky & Orabona (2019) established the complexity O(
3) It is also worth mentioning that the above methods require multi- multi-point stochastic oracle, which computes the stochastic gradients at two different points with the same random seed Ç. Finally, the lower bounds in (Arjevani al. 2023 these complexity results are worst-case optimal.
established that
Online-to-nonconvex conversion Apart from the smooth nonconvex optimization considered in this paper, the original O2NC conversion by Cuttkosky et al. (2023) also addressed the complexity of nonsmooth nonconvex optimization first considered in Zhang et al. (2020), yielding an optimal stochastic algorithm. The framework has been extended and refined in several follow-up works (Zhang) Cutkosky 2024 AAhn et al.) 2024a), and has been shown that various practical algorithms, such SGD with momentum and Adam, can be interpreted within the O2NC framework (Zhang &
Cutkosky 2024
Ahn et al. 2024b Ahn & Cutkosky 2024
Ahn et al. 2024a).
Comparison with Jiang et al. 2025) A recent work by Diang et al. (2025) also built upon the online-
to-non-convex conversion framework introduced by Cutkosky et al. (2023), leveraging optimistic online gradient descent to tackle the resulting online learning problem. However, their focus is on quasi-Newton methods in the deterministic setting, whereas our work focuses on first-order methods in both stochastic and deterministic settings. While that approach shares similar high-level structure and relies on common core lemmas as ours, they differ fundamentally in their hint constructions. Specifically, in our paper, our hint is based on the stochastic gradient at an extrapolated point, whereas Jiang et al. (2025) employed second-order approximation, where the approximate Hessian matrix updated via an online learning algorithm the space of matrices. Due to the different hint constructions, our analysis exploits negative terms in the regret of optimistic online gradient descent to obtain tighter regret hounds-term that are neglected in (Jiang et al.) 2025).
PRELIMINARIES AND BACKGROUND
Throughout the paper, assume that F satisfies key assumptions described below. Unless otherwise specified, we use || to denote the fz-norm for vectors and the operator norm of matrices. Assumption 2.1. We have
FV VF(y)] < L ||x yll any x, y E Rd
Assumption 2.2. We have F(x) 4 Fyy)l S L2||x for any x, y E Rdd
In the stochastic setting, we assume access to an unbiased gradient oracle with bounded variance. Assumption 2.3. We assume that we have access a stochastic gradient oracle satisfying
EEND [x) VF(x) and ( <o0, Vx Rd where D is a data distribution.
(2)
2.1
ONLINE-TO-NONCONVER CONVERSION
As discussed, the online-to cecine-to-nonommee nonconvex conversion (O2NC) framework proposed in Cutkosky et al. (2023) provides unified approach that reformulates the task of finding stationary point of nonconvex function F as an online convex optimization (OCO) problem. By instantiating this framework with different online learning algorithms to solve the resulting OCO problem, one can derive various algorithms for nonconvex optimization. In this section, we first recap the core ideas behind the O2NC framework.
Consider the general update rule X, = Xx-1 + A., where we assume that the update direction A has bounded norm, i.c.. |||, < D for constant > The starting point of Cutkosky al. (2023) is to apply the fundamental theorem of calculus to characterize the function decrease between two consecutive points as
F(x.) F(x.-1) (V n: Xx xn-1) (
3

---

Published as a conference paper at ICLR 2026
where in the above expression V VF(x,-1+s(xx; x)- ds is the average gradient along the line segment between X and Xn. Given the equality in (3) and upper bound on the norm of An. the ideal choice of A, to maximize the function value decrease to set it as An = - - -II.. - |
which leads to function decrease of V Il. However, the implementation of this update poses several challenges, which we outline below along with potential solutions.
First, computing V, n involves evaluating an integral over segment, which is computationally expensive. One remedy is to approximate the average gradient over the segment by evaluating the gradient at randomly selected point along the line segment connecting X and x, in expectation, this yields the same value as Vn. An alternative, deterministic approach is to use the gradient at the midpoint 2/2 (x,,- + x,) an approximation to V Under the assumption of Lipschitz continuity of the Hessian, it can be shown that the resulting error is (T.D2). In this work, adopt the second approach and define the midpoint as w, 1 (x,-1 X,).
However, two key challenges remain. First, in the stochastic setting, we do not have access to the gradient V (ww,,. but only to a stochastic gradient oracle (see Assumption 2.3 To resolve this, we use an unbiased stochastic estimate of the gradient the midpoint, denoted by ga = f where S, ~ D. In the rest of the paper, we assume access to stochastic gradient oracle with variance a². By setting 2² our analysis and algorithm naturally recover the deterministic setting.
The second and perhaps most critical challenge, which arises in both deterministic and stochastic settings, is that computing the (stochastic) gradient the midpoint w,, requires knowledge of the next iterate X,. which itself depends on the update direction A.. Since x,, is not available when choosing A.. this creates a circular dependency. To overcome this, we cast the selection of A as online learning problem, where A, is the action taken at round and the loss is defined as (gn A,) This loss reflects how well the chosen direction aligns with the negative of the (stochastic) gradient evaluated the midpoint, thus guiding the updates even in the absence of x,, decision time. Concretely, the online-to-nonconve conversion framework proceeds as follows
Update x,, = X + An and wn = Xn-1 - A
Construct a stochastic estimate ga = V fw En) with En ~ D:
Feed the loss (gn. A) to an online learning algorithm to obtain A with | D.
key result from Cutkosky et al. (203) establishes that convergence to stationarity in Problem ①I can be related to specific notion of regret in the online learning problem above. Specifically, suppose
the process runs for M = KT iterations, divided into K episodes of length T each. We then define the K K-shifting regret
K
RT
Regr(u'
K)
gm:
u²),
n= (B-T4))
where {u*} k== is sequence of comparator vectors to be specified. In the next proposition, we bound the gradient norm at the average iterates in terms of Regr (u'....,u" ) Due to space constraints, we defer the detailed discussions and the proof to the Appendix.
Proposition 2.1. Suppose that Assumptions
2.2 and 2.3 hold. For k 1,..., K, de- D
fine w = T Em=(k (m=(k-1)T+ Wn and u
11
8- Recall the definition of
Reg (u' ..... u in (4. Then have
K IVF |||
F(xx) - F DKT
E Regr (u'.... w²)
.....
La D2 + 12
o /T
E
<
DKT
48
2
In Proposition 2.1 the returned points (
]k=1 represent the average iterates within each episode, and the comparators {u*) ) are defined based on the sum of stochastic gradients in each episode. Moreover, the proposition shows that the average gradient norm at {w*) ]k=1 can be bounded in terms of the K KK-hhifing regret with respect to these comparators. Hence, to obtain a gradient complexity bound for finding stationary point of the function F, it suffices to use online learning algorithm
4

---

Published as a conference paper at ICLR 2026
to minimize the regret. This approach yields explicit update for A., and consequently for the iterates. Specifically, the online learning problem we need to solve is presented in the box below.
introduce online doubly optimistic gradient method along with function, designed to efficiently solve the above online learning problem in both deterministic and stochastic settings. Before that, briefly review the online learning algorithms proposed in CCtkkokky let al. (2023), originally developed for these settings, and highlight their limitations. Notably, the approaches differ between the deterministic and stochastic cases to achieve the best possible regret bounds and corresponding gradient complexity.
In Section 3
hint
Online Learning Problem
For ..... KT:
The learner chooses A, E IRd such that || | S D;
Sample &n ~ and compute gn = V + +x En), where x,, = Xn-1 Ani
The learner observes the loss E,, (An) = (gn: An).
Goal: Minimize the regret Regr (u' ..... u*) Σ ~ (n. An u²).
Deterministic setting. In the deterministic setting, Cutkosky et (2023) employs an optimistic gradient method, which relies on hint vector h, to approximate the true gradient
closely as possible. The regret of these methods is governed by the approximation error hetween h, and gn. as shown later in Lemma 3.1 Hence, natural choice for h, is to leverage the smoothness of F and set
that is suboptimal compared the state-of- ofae--ofttheart as discussed in Section 3.2 To achieve a better rate, CCukkosky et al. (2023) build on a variant of optimistic gradient descent from Chen et al. (202I) and propose more sophisticated hint construction. Specifically, starting from À they follow the update rule A., [I (Á,,
h, gn-1- However, this only leads to complexity of ((
yy,,), An+1 = [IIAI
78.) where (.)) denotes projection onto the Euclidean ball of radius D. As shown by the update rule, the algorithm maintains
sequences: Á, and A..
The auxiliary sequence Ån designed closely approximate A,, and plays key role in constructing the hint vector h,, Specifically, h, is computed through an inner loop that solves the following nyhl):
fixed-point equation for h, which depends on Á,, = FF [xn-1 + /
While successfully achieving the complexity of (s log(E) )), this hint construction introduces two drawbacks: the inner loop adds extra logarithmic factor the final complexity bound, and the fixed-point formulation complicates its extension to the stochastic setting.
Stochastic setting. In the stochastic setting, Cutkosky et al. (2023) proposes using standard pro- jected online gradient descent (OGD) solve the online learning problems. The update rule follows An+1- = Dy An
7g.). ). Under the assumption that the stochastic gradient has a bounded second moment, i.e., E V fx: 1 < G2 for all x, they prove that the regret of OGD can be bounded by Reg,, (u² the hyperparameters, this leads to an improved complexity of O( 3.5 However, note that this rate does not improve in the deterministic setting, where = 0. Moreover, the bounded second moment condition required to guarantee regret bounds using OGD can be a restrictive assumption to impose, which is not necessary in other existing methods Cutkosky & Mehta 2020).
u*) ) O(GGDVT). Under Assumption 2.2 and with proper tuning of
To address the limitations identified above in both the stochastic and deterministic settings, we develop our "Online Doubly Optimistic Gradient" method. In the following section, we explain how the algorithm leverages two layers of optimism to overcome these challenges and provide a comprehensive analysis of its complexity.
PROPOSED ALGORITHM
This section introduces our proposed algorithm and the key ideas behind its design. Building on the O2NC framework Cutkosky et al. (2023), reformulate the problem of finding stationary point of
5

---

Published as a conference paper at ICLR 2026
F as an online learning task. To solve the resulting OCO problem, present modified variant of the Online Optimistic Gradient method, distinct from the one discussed in the previous section. In addition, our main algorithmic contribution, propose novel hint function derived from two-level optimism scheme, detailed below. Hence, we refer to our approach as the "Online Doubly Optimistic Gradient" method.
3.1 ONLINE OPTIMISTIC GRADIENT METHOD
As mentioned earlier, we also aim to solve the online learning problem described in Section 2.1 Unlike the optimistic template used Cu et al. (2023), which requires two projections per iteration, we adopt simpler variant of the optimistic gradient method that requires only a single projection. Specifically, for n > 1, we update the direction A using the following rule
An+1 I (An Th nggn hn)),, Vn 1,
(5)
and for n 1, we initialize with A = arg min (
To motivate the update rule introduced above, observe that natural approach would be to base the update of p on the current gradient g.+11 but this is not feasible because g++11 revealed only after An+1 has already been selected. To address this challenge,
leverage online optimistic learning techniques from Rakhlin & Sridharan (2013); Joulani et al. (2020), introducing the first layer of optimism in doubly optimistic algorithm. These methods rely that approximates ga as accurately as possible. The intuition of this approach assumes that the deviation between the true gradient and the hint remains relatively stable across iterations, i.e., ga+1 ha+11 2 gn. hn. Accordingly, one can estimate gn-1 s h + gg ha and the update combines an optimistic prediction using h,+1 with correction based on the observed error go. h
hint vector h,
Next, we present the K K-shifting regret bound for the optimistic gradient method described in (5) This result holds for any hint function and, accordingly, depends on the approximation error between gn and hn as shown in the following lemma.
Lemma 3.1. Consider executing the update described in with a constant step size Then the K K-shifting regret can be bounded by
Regy (u' 1 4KD2
+
57
KT
h2
11
1
Σ
KT
A,
A 1
2
4nj
Lemma 3.1 highlights the crucial role of the hint vector h,; the more accurately it approximates the true gradient g.. the more favorable the convergence behavior of the algorithm becomes. Precise hints tighten the regret bound, while inaccurate approximations
substantially degrade performance. Lemma 3.1 also establishes the foundation for the second layer of optimism in our algorithm. In particular, it features negative term, A A I|? which was previously neglected in Cutkosky et al. 2023)) Under the smoothness assumption, we can reasonably expect that A, Re An Our second layer of optimism capitalizes this assumption and incorporates the previously neglected term, establishing connection between this term and lg. h, ll under the Lipschitz continuity of the gradient. This connection allows us to use telescoping techniques, thereby improving upon previous convergence rates within this framework. We now address the critical question of how to construct the hint sequence h, to minimize the regret bound established in Lemma 3.1
3.2 HINT CONSTRUCTION
For of exposition, we first assume access deterministic gradient oracle; will return the stochastic setting at the end this section. As explained in Section 3.1 our primary objective in hint construction is to estimate gn V F(w,,) with maximum accuracy using only information available up to x,-1. as illustrated in Figure I Leveraging the function's 's smoothness properties, an intuitive first approximation to reuse the previous gradient estimate, assuming gn. ~ -n-
positing that the gradient at w, approximates the gradient at wn-1- This leads to the following update rule, which corresponds the standard optimistic online gradient descent
A n+
II A <D A 1)(2gn. 8a-1))-

---

Published as a conference paper at ICLR 2026
2
wp-1
2n
3m-1
An-1
Figure 1: Illustration for the extrapolated point in our algorithm.
However, this straightforward approximation fails to exploit the negative term || -1 Lemma 3.1. With this approach, llg, h < T.IWw, w becomes proportional to A n +
preventing the application of telescoping arguments. Consequently, this method yields an overall gradient complexity of (s--1//6 in the deterministic setting (Cutkosky al. 2023 which is worse than the best-known bound of O(e-7/4)
Cutkosky et al. (023)) improved this rate under the O2NC framework by constructing the hint h, through a fixed-point iteration scheme. Their approach develops an approximation A, A via multiple iteration steps, estimating gn R Fx + (.))) While this method achieves an improved convergence rate of O(= log(1/E)) O(s=7/log(1/EE) in the deterministic setting, it introduces an additional logarithmic factor. Moreover, this construction complex and presents challenges when extended to stochastic environments. These limitations motivate our search for alternative that maintains theoretical guarantees while offering greater simplicity and broader applicability.
Our method not only removes the logarithmic factor in the deterministic case but also matches the known lower bound in the stochastic case, achieving complexity of O -1.5 + - We leverage second layer of optimism to improve upon previous results. Referring Figure I our goal is to estimate the gradient at w, using only information available up to x,-1- Since W,,
1.75
Xn-1 2 A,, and can reasonably approximate A, An-1 in the smooth setting, we propose estimate the gradient at w, using the gradient an extrapolated point Zn-1 1 Xn-1
This leads to the following elegant construction for the hint
h VF(2n-1) (x + A n-1.
(6)
We use the convention Ao which implies that h1 Vx(x)). This approximation has clear mathematical justification from the regret analysis. Recalling from Lemma 3.1 the negative term ||A, A, 1| that was previously neglected in Cutkosky et al. (002)). we can now see that under this hint construction and using Assumption 2.1 we have l|g., h,ll x ||w, 2n-1 ll. and by construction |w,, Zn
Zn-ill ||= 2 A, A IT. With appropriate stepsize selection, this allows us to leverage telescoping between these two terms and obtain tighter convergence rates.
The novelty of our hint construction lies its simplicity: requires only one gradient call compared to the multi-step procedure in Cutkosky et al. (2023), and it significantly simplifies the analysis. In particular, this makes especially well-suited for the stochastic setting, where the only modification needed is replacing the deterministic gradient with its stochastic counterpart, i.e., h (. E.). where En the random sample drawn at iteration n. In this setting, we continue to leverage the telescoping argument, with only an additional term accounting for the stochastic gradient variance. The regret incurred by our hint is formalized in the following lemma.
Lemma 3.2. Consider executing the update described in (5) with the hint construction defined in (6) (or its stochastic counterpart in the stochastic setting), using step size nj V3L," Then bound one episode of the K K-shifting regret, as
4D
9L3nD2 +
E
Σ
gn. A
)
+ 2
"
2
The stochastic variant of our proposed method is summarized Algorithm [ The deterministic version can be obtained by simply replacing the stochastic gradients with their deterministic coun-
7

---

Published as a conference paper at ICLR 2026
Algorithm 1 Online Doubly Optimistic Gradient Algorithm
Require: Initial point Xo. K,T's N. radius D)
Initialize: A = D V f((ooio))
h1 Vx(xx;
1: for v = 1 to KT do
2: Set
1 A 3: Set n AIID (An 7/ V (zni En) 1/ (V(V/(WaiEa) (i(
Xn-1 + A.. =
24n
end for
5: Set w. Wik-1)T++ for k 1...., , K and I....,
6: Set w = De=1 wi for l = ,,
7: return Deterministic Oracle: arg e (Kk..... [VF(W)]l Stochastic Oracle: Uniformly sample {w w w*)
terparts. In the following section, we present a comprehensive complexity analysis to establish the convergence rate of the algorithm.
3.3 COMPLEXITY ANALYSIS
Thus far, we have presented our proposed "Online Doubly Optimistic Gradient" method in Algo- rithm D and discussed the construction of the hint vector h, Next, leveraging Lemma 3.2 and Proposition 2.1, we establish the convergence rate of our proposed method.
Theorem
3.3. If Assumptions
2.3 hold and we (min max{ [ (T2D)
set
D
O (min (MLiot) (ML LB) +1) T
(
}. 1)
K-
M T
and 1 O VI9+o"T/Da) in Algorithm then
K
o |VF( ||| = -0((F(8))- -
(F(xo) -
E
+ L L2
(7)
K
M
M
Proof Sketch. Based on Proposition 2.1
achieving the final convergence rate requires bounding
the K K-shifting regret. As corollary of Lemma 3.2 we get E (Ree.
..... u <
4KD²
7
91 D²
6TKTo2 Combining this regret bound with Proposition
2.1
we obtain
F(xo) P DKT Tn
4D
9T2nD 2T
6n
L D2 +
T 2
E
<
D2
K
D
48
2
VT
Finally, by selecting the parameters 7), D, and T according the theorem's prescription, we arrive at the stated convergence rate. The definitions of D and T involve a max and min, respectively, to interpolate between the deterministic and stochastic regimes. This allows the final bound to adapt to the variance a of the stochastic oracle, interpolating between both settings.
We show that after iterations, the gradient norm at the best iterate satisfies 4/T M MAT): which yields total gradient complexity of O 1.75. This matches the lower bound 2(02g-3.5) in the stochastic regime Arjevani ct al. (023) and recovers the best known rate (1.555 in the deterministic setting, smoothly interpolating between these two regimes.
minigAsK E. [[VF[(*>]]] O
Remark 3.1. While our paper focuses on the smooth setting, Algorithm [ also recovers the optimal convergence rate in the nonsmooth setting with properly chosen parameters. In this case, we assume that [xx; [P]]] S G2 for all x E IRd and follow the stationary notation of Cutkosky al. 2002)). Under this assumption, Algorithm Jachiveess a complexity of O(e -38-1) for finding (6, e)- stationary points. This guarantee is obtained by adapting our analysis to the nonsmooth regime. Specifically, we replace Proposition 2.1 with Theorem Cutkosky et al. (002)), which serves as its nonsmooth analogue, and in the regret bound of Lemma [3.1 discard the negative term and bound lgg. h | directly using the bounded recond-momedd assumption. The remaining steps follow the same structure the analysis in Cutkosky et al. (2023).
8

---

Published as a conference paper at ICLR 2026
4 ADAPTIVE STEP SIZE SCHEME
In the previous section, we analyzed Algorithm with a constant step size 7) and established its convergence rate. However, as shown in Theorem 3.3 the choice of 1) depends on the global gradient Lipschitz constant and the episode length 7', which can be overly conservative and leads to slow convergence. To address this, is often desirable to select the step size adaptively to exploit the local Lipschitz continuity of the objective function. In this section, we extend Algorithm to incorporate an adaptive step size scheme that automatically adjusts the step size based on past gradient information.
Inspired by the adaptive step size analyses developed in Kavis et al. (019); Antonakopoulos et al. (2022): Levy et al. (2018), we define the learning rate as
7D
7/n
(8)
Di=1
mod T Igs
111
where 7 > 0 controls the initial step size and a >> O is a small constant added for numerical stability. Here, g B(k-1)2++ and h = 1y with k indicating the episode and the iteration index within that episode. The sum Σ
mod T lg - b 2 is reset at the beginning of each episode, which
facilitates the theoretical analysis of regret in the Online Learning Problem [
The key challenge in analyzing the adaptive step size scheme in (8) is that the step size Thn does not admit direct upper bound, making it difficult leverage the negative term in the regret analysis. Specifically, similar to Lemma 3.1 we can bound the regret for the first episode as (the subsequent
episodes follow by similar arguments) Em=r An n²) 3D + +
ggn h, ||
11)) In the constant step size setting, as shown in the proof of Lemma 3.2 the key to A n
47p
applying the telescoping argument is the ability to choose r S _1, ensuring that the negative term ||
V3L."
- balances the deterministic approximation error 2n I[FF((,,)
However, in the adaptive setting, we have no guarantee that 17, is bounded by 1 making the telescoping argument not directly applicable.
V3L,"
To overcome this difficulty, we adopt a thresholding strategy inspired by prior work in Kavis et al. (2019): AAtonakooooulss et al. (2022); Levy al. (2018). At high level, we partition the iterations within each episode into two categories. For iterations where Yh is below a certain threshold, we show that the negative term dominates the positive one. Conversely, when 7h large, the definition of ( implies that the denominator Σ mod T l|g. - 1/ small, which allows us to control the cumulative contribution of the positive terms. We refer the reader to the appendix for further details.
Under the adaptive step size Th. we establish the following lemma, which bounds the regret incurred during single episode of the K- K-shifting regret. Without loss of generality, we present the result for the first episode; the analysis extends straightforwardly to any subsequent episode.
Lemma 4.1. Consider executing the update described (5), using h, as defined in (or its
stochastic counterpart in the stochastic selting), and the aulattive step size defined in 8 Then we can bound the first episode of the K -shiffing regret as
T E [(
3 +7) (2+ 7
3 ( (7) Lny'D?
An n²)l )
88
DVTO + +16 DVTo+166
n=
where in = --maaaggnn
Ig. 1gn-ball || - all'
Lemma 4.1 plays the same role Lemma 3.2 in the constant step size setting. Notably, instead of relying on the global gradient Lipschitz constant, the bound depends f.,, which can be interpreted as local Lipschitz constant and may be significantly smaller in practice. We are now ready to present the final convergence guarantee for this adaptive variant of the "Online Doubly Optimistic Gradient" method.
Theorem 4.2, Suppose Assumptions 2.3 2.1 and 2.2 hold. If we run Algorithm 7 with hn as described in (6) (or its stochastic counterpart in the stochastic setting), the values for D. T, and K are selected as the ones in Theorem 3.3 and nn as described in ( replacing Tn with iz where

---

Published as a conference paper at ICLR 2026
ī maxignsM
||.. T hn || w. kn, ill
then the following holds
K
VF((W) = -
(F(xo) - PT)}
M + (L:) L
(9)
M
Theorem 4.2 shows that our adaptive step size scheme maintains the same complexity of -1.75
-²g-3.5) 3.5) without requiring manual tuning of the learning rate, while offering improved dependence on the gradient Lipschitz constant compared the constant step size scheme. Moreover, Cutkosky & Mehta (2020) posed an open problem of designing an algorithm that achieves this complexity without knowledge of the variance o². Our result represents a first step towards this goal by introducing an adaptive step size. A promising future direction is to further adapt the choices of D and T, ultimately aiming to make the algorithm fully parameter-fre
CONCLUSION
In this paper, we build on the online-to online-to-noncomeee no--oonconvxx conversion framework of Cutkosky et al. (2023) and propose a simple algorithm for solving smooth nonconvex optimization problems, which only requires two (stochastic) gradient queries per iteration. Our key contribution is a doubly optimistic hint function for the online optimistic gradient method, thus eliminating the fixed point iteration subroutine from (Cutkosky et al., 2023). ). Assuming that both the gradient and the Hessian of the objective are Lipschitz continuous and that the stochastic gradient has bounded variance o², our algorithm achieves a complexity of (6-11.7 1.75 + -2e-3.5 This result smoothly interpolates between the best-known deterministic rate and the worst-case optimal stochastic rate. In addition, we develop an adaptive step size strategy for our algorithm, marking first step toward a potential future direction: the design of fully adaptive, parameter-free algorithms that match this performance without relying on prior knowledge of cooblem-specinne parameters.
ACKNOWLEDGMENTS
This work was supported in part by the NSF CAREER Award CCF-2338846, the NSF AI Institute for Foundations of Machine Learning (IFML), and the NSF AI Institute for Future Edge Networks and Distributed Intelligence (AI-EDGE).
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199, 2017.
Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024.
Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky. General framework for online-to-nonconve conversion: Schedule-fir sgd is also effective for nonconvex optimization. arXiv preprint arXiv:2411.07061. 2024a.
Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding adam optimizer via online learning of updates: Adam ftrl disguise. In Proceedings of the 41st International Conference on Machine Learning, pp. 619-640, 2024b.
Zeyuan Allen-Zhu. How to make the gradients small stochastically; Even faster convex and nonconvex sgd. Advances Neural Information Processing Systems, 31, 2018a.
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd, Advances in neural information processing systems, 31, 2018b.
Zeyuan Allen Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances in Neural Information Processing Systems, 31, 2018.
10

---

Published as a conference paper at ICLR 2026
Kimon Antonakopoulos, Ali Kavis, and Volkan Cevher. Extra-newton A first approach to noise- adaptive accelerated second-order methods. Advances in Neural Information Processing Systems, 35:29859-29888 2022.
Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242-299. PMLR, 2020.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1): 165-214, 2023.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. "convex until proven guilty": Dimension-free acceleration of gradient descent on non-convex functions. In International confer- ence on machine learning, pp. 654-663. PMLR, 2017.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex 2018.
optimization. SIAM Journal Optimization,
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315-355, 2021.
Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pp. 1216-1259. PMLR, 2021.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, pp. 6-1. JMLR Workshop and Conference Proceedings, 2012.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD, In International conference on machine learning, pp. 2260-2268. PMLR, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex SGD. Advances in neural information processing systems, 32, 2019.
Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-nnn toni------nn--onnve conversion. International Conference on Machine Learning, pp. 6643-6670. PMLR, 2023.
Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path- inth-integrated differential estimator. Advances in neural information processing systems, 31, 2018
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points. In Conference on Learning Theory, pp. 1192-1234. PMLR, 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-2363 2013.
Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci. Improved complexity for smooth nonconvex optimization: a two-level online learning approach with quasi-newton methods. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pp. 2225-2236, 2025.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.
Pooria Joulani, András György, and Csaba Szepesvári. A modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108-188, 2020.

---

Published as a conference paper at ICLR 2026
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019.
Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. Advances in neural information processing systems, 31, 2018.
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polyloga- rithmic factor in the ((+-//) complexity. In International Conference on Machine Learning, pp. 12901-12916. PMLR, 2022.
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polyloga- rithmic factor in the in the O/4-T/4) complexity. Journal of Machine Learning Research, 24(157): 1-37, 2023.
Naoki Marumo and Akiko Takeda. frree accelerated gradient descent for nonconvex minimization. SIAM Journal on Optimization, 34(2):2093-2120, 2024a.
Naoki Marumo and Akiko Takeda. Universal heavy-ball method for nonconvex optimization under hölder continuous hessians. Mathematical Programming, pp. 1 1-29, 2024b.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical programminng 108(1):177-205, 2006.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pp. 993-1019. PMIR, 2013.
Clément W Royer and Stephen J Wright. Complexity analysis of second-order search algorithms for smooth nonconvex optimization. SIAM Journal on Optimization, 28(2):1448 (22:1444-1177,, 2018.
Clément W Royer, Michael O'Neill, and Stephen Wright. A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 180:451-488, 2020.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. Advances in neural information processing systems, 31, 2018
Yi Xu, Rong Jin, and Tianbao Yang. Neon+: Accelerated gradient methods for extracting negative curvature for non-convex optimization. arXiv preprint arXiv: 2017.
Jingzhao Zhang. Hongzhou Lin, Stefanic Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pp. 11173-11182, PMLR, 2020.
Qinzi Zhang and Ashok Cutkosky. Random scaling and momentum for non-smooth non-convex optimization. In Proceedings of the 41st International Conference Machine Learning, pp. 58780-58799, 2024.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of machine learning research, 21(103): 2020.
12

---

Published as a conference paper at ICLR 2026
APPENDIX
A MORE DETAILS ON WOLINE-TO-NONCONVE CONVERSION AND RELATED PROOFS
In this section, we elaborate the details of the online-to-nonconvee conversion under the assumption that we have access to deterministic oracle. with the goal of building intuition. In the next subsection, these results will be extended the case where only stochastic oracle is available.
As introduced in Section 2.1 to eliminate the randomness from the analysis, we define the gradient estimate gn V (w.) where Wn 1 (xn-1 x,). This modification introduces an error in approximating Fxx,) F(x,-1) by gn An. However, as established in the next lemma, under Assumption 2.2 and for sufficiently small D, this error becomes negligible. The proof is available in (Jiang et al. 2025| Appendix A.1).
Lemma A.I. Consider X,, = Xn-1 + where | S D. Further, define 8n - VV((w,) where Wn 2 (xn-1 + Xn). If Assumption 2.2 holds, then F f((x=11 Fxxx)) gn An
48
Lemma A.I provides formal connection between gn. An and the function value decrease. While the choice gn. yields the steepest local descent, as discussed in Section 2. the key challenge is that g, cannot be computed prior to selecting An. since it depends on x,. which itself requires A,. This observation motivates alternative interpretation: the process of choosing A, can be cast as an instance of online learning, where each An serves as a decision variable, and the loss incurred at step is given by the linear form g. A..
To rigorously relate the online learning perspective of choosing A, to the objective of identifying a stationary point, appeal to Lemma A.I This result establishes that for any fixed comparator u. after 7 iterations satisfies the following bound:
TL2D3
F(XT) F(xo)= S
8n (A
U)
+
gn
48
Setting the arbitrary vector as -D Bat/11 ΣT
Bnll, it can be shown:
T
F(xo)= - F(XT)
T
L2D²
ga
5
T (A, 1)
(10)
T
DT
DT
48
n=1
n=1
While the connection between the average gradient and the cumulative regret over T iterations has been established, our primary objective remains the identification of an e-first-order stationary point. To bridge this gap, we now present formal relationship linking the average of the gradients to the gradient evaluated at the mean iterate. The following lemma serves a similar purpose to (Cutkosky 2023 Proposition 15).
et al.
Lemma A.2. If ga = ((w,)) and Assumption 2.2 holds, then [VF(W]] S |1 E gm 2 2 D2, where
E Wn-
The proof of this lemma provided in (Jiang et al. with the expression in (1O), we obtain a connection between the norm of the gradient at the averaged iterate and the regret bound appearing on the right- hand side. It is important to note that the error incurred when approximating the average of the gradients over ł iterations by the gradient evaluated at the average iterate grows quadratically with the window length To control this approximation error, we reset the averaging process every T iterations. At the same time, we must account for the fact that certain terms in the upper bound scale inversely with T, requiring a careful choice of T to achieve the tightest possible convergence guarantees.
2025 Appendix A.2). By combining this result
A.1 PROOF OF PROPOSITION 2.1
Note that when we have access to a stochastic oracle, the gradient becomes gn VS(W En). Consequently, Lemma A.I takes the following form:
L₂D3
F(x,-1) F(xx) 2 -F((W)) A,
48
13

---

Published as a conference paper at ICLR 2026
This expression can be further related to Bn follows:
L D>
F(xa-1) F(x.) (VE(ww))) - gn: An)
gn A
48
Taking expectations and using the fact that gn. an unbiased estimator of V FWw)). we get:
L₂D²
[[ - ((,() 2 -E
48
By telescoping over T iterations and adding and subtracting
T
gn.
U:
Th2
E F - F(xo) E
gn. An
u}
+
8n
+
48
Choosing the comparator vector as DIE
8n1/11
Bulls we obtain the following bound
T
F(xo)
[[F((x]]
LzD²
E
gm
(A, 1)
(11)
DT
DT
48
n=1
n=1
Now consider the k-th episode (k: 1,2..... K) from n (k: the inequality in (II.
1)T
1 ton
KT. By applying
we obtain
E
E[F(X
1
E
Σ
gn
E
Σ
gn (A u
DT
DT
n=
n=(k-1)T++
D2D2
(12)
48
Morcover, recall that wh = 4 Σ KT
(k=(k=1)T+ Wn and it follows from Lemma A.2 that [VF
KT L VF(wn)
2 D2. Recall that Lemma A.2 was derived under the determin- V (W,), but now g. = -ff(w.. {). However, we can state:
istic setting where gn
KT
+ Le T2
VF( I1 S
Σ
VF(wn))
T
2
n=(k-1)T+
KT
L2 D2 2
Σ
(VF(wn)) - + +gn)
+
(K-ITT+
Σ
KT
(VF(wa) - -Bw)
Σ
KT
+ L 2 D2
T
2
n=(k-1)T+1
The final inequality follows from the triangle inequality. In expectation, we can state
KT
E
Σ
ga
12
(13)
n=(k-1yT+1
This
bound follows from applying
Assumption
2.3 which allows us to establish
+
KT m 11 VF(w,) gn
VT
Using 12 together with 13 leads to
E
V [)]]
F(x 1)7)]
E. [[(XXT)]
1 DT
E
Σ
g T (A,
R2 )
DT
(1-+1)++1
D2
Lg 1 D2
48
2
/T'
14

---

Published as a conference paper at ICLR 2026
Summing over A 1 to K and dividing by K, we obtain
k
F(xo) - -E(F(XM)
K
RT
E [|] <
E
Σ
Σ
8
(
u²)
KDT
KDT
k=
(k-
1)7+1
D2D²
La 2 D2
+
48
Finally, noting that E [F(xM)) 2 F* completes the proof.
B PROOFS FOR ONLINE DOUBLY OPTIMISTIC GRADIENT WITH CONSTANT STEP SIZE
In this section, we provide the detailed proofs corresponding to Section where the Online Doubly Optimistic Gradient method with constant step size was introduced, along with its complexity analysis. While some of the proof' closely follow arguments from Jiang et al. (2025), we include them here for completeness.
B.1 PROOF LEMMA 3
To prepare for the proof of Lemma 3.1
first prove auxiliary result.
Lemma B.1. Consider the update rule in
Then for any u such that |||| S D, it holds that
A 1
An+1
-ul2
[g++1 Ant1 - u)
+ (gn+1
hn+1, Ant1 u
2m
2n
Bg hn: A. u) n/1gan
h
_ 1 n+ Ax
1
4n
Proof. By using the optimality condition, for any u E {A Rd ||||| S D}.
we have
A+1 An + 1/h411 + n(g. hn), u Aat1) 2 0.
Rearranging terms, obtain
(g.+1, A n+t u) (gn+1 hn+1, Ant1 u) (g. hn, A n+1 u)
1
A
u||2
| A, 2n7
A - -u/13
2m
211
where we have used the three-point equality (An+1 A n. 11 An+1) 11 A - -ul2 - A
An 1 n+1 u/l2. Moreover, we have:
- (g. h, An+1 u) (g. h A. U) + (gn h A Anti).
We can further bound the second term as follows:
(g. - h,, An Ant1) < lgg. h, II - Antil 1 wllgn h,
An+t
A,
4n
where the final inequality follows from the weighted Young's inequality. Putting all of the above inequalities together yields the desired bound.
Using Lemma B.I we can bound the regret for each episode in the following lemma.
Lemma B.2. Consider the optimistic update in (5). Then for and any u such that ||u || $ D, have
T
gny A. u²) - 2D2
T hall
T
Σ
Σ
n nllg.
Σ n=2
-
_ 4n
A.
A 11.
(14)
D=1
15

---

Published as a conference paper at ICLR 2026
For k 2 2 and any u such that ||u*
I
D, we have
Σ
gg, An
u*) S
4D2
!
[(k-
1(k-1)T 12
Σ
KT
n/|go,
h
"
2
1y7+1
(k-1)7
Σ
1
A A 1-1
(15)
41
n=
1)T+1
Proof. To prove 14 we set ut and sum the inequality in Lemma B.1 from to -
1
1
Σ gn, A u²) S
A u' 112
AT u 112 + (gT hT, AT -u)
21
211
2
(g) h1,
A
nl h
| n+1 An.l3)
4nj
Moreover, recall that A arg min A A (h1, A). Thus, this implies that (h1,
A1 u') 50
gr hr. AT u gr hr AT
u'll ||
" gg hr
1
A 121
2
2n
Combining all the inequalities, we obtain that
T
T-1
Σ
1 gn. u - A - 112 7
hr
nlign gn - -h
17
--1 -11 Ant1 Am1
27
4n
1=1
n=1
Using " gr 1r s 1/lgr 1r and ET-1 dnj
Ant1 Anl ΣT
|A,, 1n1111
bn
lead to:
T Σ
Σ gn. A,
u²) S
1 || A1 1²112 Σ nlgg. h 2n
|A
1-11
4n
Finally, since we have || D and ||'||| S D, this leads to (14
Now we move 15 To simplify the notation, we let A
(k- 1y * 8(k-1)7++
and h 1 Then by setting u = x and summing the inequality in Lemma B.1 from
n (k- to AT 1, we obtain:
I u*
Σ gr A k u
(g)
h
A w
27
2n
KT
(g) k-1
h
R-1
h- n
Σ
nllg. - -h 2- 4n
Ant1 -Anl1
An112)
a=(k-1)T
Following a similar argument in the proof of 14). we have the following inequalities:
Bg
h A
-
||
h
A
2n
[g) k-
h
|
1|
2/ A k-1
n k1
A n-
An
A 11-11
1yT
16

---

Published as a conference paper at ICLR 2026
Thus, combining all the inequalities above, obtain:
T
n -
A
1²112
+
g
11
+
!
||87
k-1
h
1-1
11
1 k
u
1
21
2
2
2n
r
1=1
kT-1 Σ
KT
h
Σ
A n
A
-11
4n
1)T
(k-1)7++
A
u
||2
17
8T
k-1
h
K-
k-1
k 1
Σ
n/
h
21
21
n= 1)T
1
n
41)
n=
1y-144+1
Finally, since have |
||||
D, and -
S D, get
||
A 21
1
24
4D This completes the proof of (15
Now we are ready to prove Lemma
Proof of Lemma 3.1 Summing the inequality in 14 and the incquality in 155 for 2, 2,3, ..,...... K
in Lemma B.2 we have:
Regr (u
n
4K D2
K
7
88
11
2
+
Σ n=1
KT
n g. h, 12
Σ 4n n=
KT
A
An-112
2
k=1
K
nllT k-
h 112
k=1
4K D2
31
KT
Br
k-1
h
k-1
+
nlg..
h
|| A
2n
4m
4KD2
5n
Σ
KT
|gx
h
KT
A A 11
2
4n
n=1
n=2
Where the last inequality we use the fact that Ek= This completes the proof.
3q
2
gr
h
21
kT
KT
m=
37
2
g. h,
B.2 PROOF OF LEMMA 32
To prepare for the proof of Lemma 3.2 we first prove an auxiliary result.
Lemma B.3. Let h be defined as in 6 Then the following bound holds
3I.2 A.
gn h 19 S
60 +
4
17

---

Published as a conference paper at ICLR 2026
Proof. To bound E lgg h 11. we begin by recalling the definitions of the respective vectors: gn Vf(wni (n) and h, Vi(zn-riEn-1 Thus,
E [[lgn h, E V (w) - 1in
E V Ex) - V ((
(Zn vf((z=1)
+VF(wn)) VF(w,))l"
where the last equality comes from adding and subtracting its deterministic counterparts. Applying Young's inequality
||g.
hnll?)
hn
11
S 3E
V (Zn-1i V V2
+3
[Vf(wni VF(ww..) )11
+ 3
[IVF(w.)
VF(an- )
3L3
$ 6 +
1
4
The last inequality follows from Assumption 2.3 that allows us to bound the vari- ance of the first two terms, and the last term comes from leveraging Assumption 2.1 1
- A | An-1
To prove Lemma 3.2 we first analyze the case k 2 2 and subsequently show that the bound also holds
for 1: 1. Our analysis focuses on the stochastic setting. However, by Lemma B.2 inequality (15) is valid in both the deterministic and stochastic cases. Therefore, we have:
RT
4D2 "
RT Σ
Σ
gg, A n n² <
g(k-1)T - haa-1)712
n/1g.
h, 1
"1
2
n=(R-1)TH
KT
1
Σ
-
A An
A 1n
4n
(k-1))+++
Taking expectations on both sides yields
NT
4D2
RT Σ
Σ
Bgg A. w²)
E
B(k
1)7 - b
E
gn
h
D1+1
1)T
RT
1
Σ
E. A, A An-1112
(16)
4nj
1)7+1
Leveraging Lemma B.3
4D
3L
Σ
Bgg. A. ut)
+
60
E E| (k-1)7
A(--1T--113
71
(A +1
3L-
E A. A1-
1)
6o
1yT
Σ
E3
An-111
4n
1)
18

---

Published as a conference paper at ICLR 2026
Rearranging the terms leads
KT
4D
Bgg.: An uty S
+
30 n +
E
(k-ITT - A (1-1))-111
7
8
n= 1)7+1
KT Σ
KT
3LS1
1
Go nj +
Σ
E
A A.-1
4
41)
(k-11 1yT
n=
1)T+1
Note that as long 17 5 /3L,
it holds that Σ -
(n=(k-1)2+1
(3L
in
E
B
1
Finally, since |
D for all we have:
KT
4D2
9T,722m
Σ
Eg A. - ut) x +
T 2
60²2
2
(1-1)4+
4D
18.
(17)
where the last incquality follows from the fact that T 2 1, completing the proof.
For completeness, analyze the case k = 1. As will be shown, the upper bound also holds in
this case. From Lemma B.2 inequality (14) gives
gz. u²) <
2D
Σ nll., h
Σ
E
A
A
111...
7
4n
nm
Taking expectations on both sides yields
T
2D
T
Σ
u S
+
Σ
nB
|gn
1 Σ
E A. - 111 (18)
4n
n=1
n=
Leveraging Lemma
B.3
Σ
T u
E gg
<
2D2
T Σ
7
60² +
3L? E An - Am-11
-A...
T EL -A-11.
4n
n=1
R=1
m=
Rearranging terms (with the convention Ao = 0) leads to
2D2
3L3n E
3L31
1
Eggn: An u²)
60 n
E An
"
4n
Note that as long as S V32," it holds that Σ on=
(3L
1
E
A
4n
Finally, since || A s D for all n, we have:
KT
2D2
31,
B(g.. A. u²
+
+ 6TTO2
17
4
11
2D
DL3D21
+
+ -188"Tn
"
2
where the last inequality simply enlarges constants. This confirms that also holds when k 1.
B.3 PROOF THEOREM 3.3
According Proposition 2.1 attaining the final convergence rate necessitates bounding the K- K-shifting
regret. We obtain the following result as a direct consequence of Lemma 3.2
4K
9LInKD²
E [eeg (u) ..... u*]] <
+
+ KT
17
2
19

---

Published as a conference paper at ICLR 2026
Integrating the aforementioned regret bound with Proposition 2.1
arrive at
F(xo) - F
4D
9LinD
18n
L2
+ La D2
IVF(W*)] k=1
DKT +
+
+
o² + D2
K
Tn
2T
D
48
2
VT
Rearranging terms
F(xo) F
4D
(9
18
+
+
0² D
n L2T
(19)
K
DKT
Tn
2T
VT
From the upper bound in 19.. must select the hyperparameterrs 77, D, K,T. T, subject to the constraint KT < M. where M denotes the total iteration budget and K, T' E N. To obtain the tightest possible bound, we will first choose n,, then determine I and K, and finally set D.
To proceed, we balance the two n-dependent terms to determine the optimal and scale appro- priately that the condition 7) I V3L, required by Lemma 3.2 is satisfied. This yields the choice
Substituting this expression into the bound gives
V var.+ D2 02
K
[VF((*)]
<
F(xo) -
F
+
11D
3L7 +
12T
r² + L2T
K k=1
DKT
2T
D2
VT.
Applying the inequality Va +b+ Va + vb a b> 2 0. and simplifying yields
E
K
[VF(W>)|| |||
<
F(xo) - Fr
10L
20g
DZT
(20)
K
DKT
T
VT
Note that the bound involves four terms dependent on
If
we
set T
min max ([(
20 L2D2
10L L
and = [ we can bound the first three terms
of the inequality (20) as follows:
KT 1)T M T M/2 which implies F(xo)-F' DKT
S F(x F(xo)-F
DM
10 < max (103 Li L 1 D3, 201,
20g < max (20 レ Diot,
20 VM
The max terms arise from the fact that the second and third terms in (20) are inversely proportional to T. Since T is clipped by M/2, these terms become inversely proportional min (D- A and
min (
respectively.
We upper bound D2 as follows:
(1(200))
20
$
10L,
$1)
$7
2
2²I² < Le max
D2
Lel
$72 2
472
200
10L1
< Le
D2
La
D2
LzDD²
LzD
Using the fact that [x]]
< (xr 1)2 < 2x. 2 for any & 2 obtain
20

---

Published as a conference paper at ICLR 2026
20
10L1
12 < L2
2
+2 D2 + la
2
+2 D32
D2
L2D
20
10L1
2L
D2
222
D2 4L2D2
D2
L2
S 22L 0 D
+ 10L L
D
+ 42
Substituting the above inequalities into the bound in 20 yields
E
Σ
K
IVF(W*)]
2 F(xo) F
DM +
max
[10 L DJ,
20L
K
M
20 L3 D& D
20
+ 22L ioLi 4L
max
VM
Using max(a, b) S a + b. and after rounding constants, we get:
K
[VF(W*)]|
< F(xo) F* +
20L,
20v2o 20
+33 0 D
I.
K
DM
M
VM
If we set D min upper bounds are as follows:
((F((x))-M)))
5/7 (((( F*)
Given this selection of D, the resulting
332, 6400
15ML, Lg
3312 Diot < 33 (F(x))- F
L S 15(F(x)) F
L 13
M
M
7
15L L L
15724 (F(xg) FT)+
5(F(xo) x=
L
Lig
M7
M
2 F(xa)-F"
< 2 7.5 ((F)))xFFF))
+ 2
16.5 (F(x0)-
F
L
o
5(F(xo)- -F")
L L
DM
M
M
M
15(F(x))- F
L at:
M
D < 201 (F(xo) ( -F
I. (F(xo) -
7.5 1117 M 4
1.77 M 4 L. (F(x))-F*)
ALzD²
41 (F(x))
7 M E
1 M
Substituting these inequalities into the bound yields
1
K
V VVF(W I|
10(F(x)) F*)+
Lİ +
30(F(x)) -F*)
L
K
M
M?
(F(x)) FF) +
L (F(x)) F
20
L
VM
This final bound confirms the convergence rate stated in the main theorem, the last three terms are of higher order and thus do not influence the rate.
C PROOFS FOR ONLINE DOUBLY OPTIMISTIC GRADIENT METHOD WITH ADAPTIVE STEP SIZE
In this section, we provide detailed proofs corresponding to Section 4 where the Online Doubly Optimistic Gradient method with adaptive step size introduced, along with its complexity analysis. The section is organized into several subsections, presenting useful inequalities and lemmas that build up to the proofs of the two main results from Section namely Le and Theorem 4.2
21

---

Published as a conference paper at ICLR 2026
C.I HELPFUL INEQUALITIES
Lemma C.I. Let 04 2 O Vi, and that there exists at least one index j E [1, with aj > 0. Then the following inequality holds
T
T
T
a
<
2
Σ
at.
0j
i=1
Lemma C.I appears in Kavis et al. 2011); Antonakopoulos et al. sake of completeness, we additionally provide its proof here.
(2022):
Levy et al. 2018); for the
Proof. We prove the lower and upper bounds separately. Lower bound: We observe that
T
V VE
T V - as و== aj
Σ i=1
04
0g
a
f=1
where the second inequality follows from the fact that a; 2 0 Vi. Dividing both sides by v E/= oj gives the desired bound.
Upper bound: Define S Ei= 0g with the convention that So = 0. For each i, it holds that
- VS, VS..I,
04
2/S. 2 VS. + VS VS. + /S
where the first inequality uses S;-1 S S₁, the first equality uses a; - 1, and the last equality follows from the difference of squares. Summing both sides of the inequality from I to T. yields:
T
Σ
/S. VS,-1 VSr. Σ
where the first equality follows from telescoping the series, and note that by definition So Multiplying both sides by 2 gives the desired inequality.
Lemma C.2. Let a, b E R, and define M = min {(a + b)2, d²}. Then the following inequality holds:
(a+ 6)2 2M +62.
Proof. We have both (a + 6)2 < 2a + 28 and (a + b)² < 2( b)2 + 26 Combining these two gives the desired inequality.
C.2 PROOF OF LEMMA
Prior to proving Lemma 4.1 of Lemma|
we state the following proposition, which is an immediate consequence
Proposition C.3. Consider the update in 5 with adaptive step size qn Then for any such that ||u|] < D, it holds that
1 AA,
1 | u/l? + (g.+1
(g.+1. A n+1
4
<
u/|2
hn+1, Ant1
u)
217
27m
(gn h An u) + 7m 8n
h
| Anti Anl
41pn
Remark C. To simplify the notation in the remainder of the proof, we define g. = VF(w,,) and
hn := FZ(zn-)).
We prepared present the proof of Lemma 4.1
22

---

Published as a conference paper at ICLR 2026
Proof of Lemma 4.1 The first step in proving Lemma 4.1 is to bound the regret within the episode.
Analogously to Lemma B.2 we can formulate the following lemma for the first episode using an adaptive step size.
Lemma C.4. Consider the optimistic update in and any ut such that || S D, have
( with an adaptive step size The Then for = 1
T Σ
3D
1 A A An-11?)
ga, A
u
BalBB. hn.l1
1T
41pr
The proof of this lemma is provided in Appendix C.3
Furthermore, the following lemma allows us to
upper bound the sum Σx= 1hn ll. h,, 2 in terms of Σ lgg. h ll effectively decoupling
the product of random variables. The proof can be found in Apendix C.3
Lemma C.5. Using the definition of the from (
derive the following bound
3D WT
3D
Σ Th gn
hn 2
2v2
7D))
a Σ
ga
hnll²
12
27
In addition, define Mn min (llg. - h
we obtain the inequality l/g.. h < 2n + 4/|g. 8n 2 + 4 h, h 11 This allows us upper bound the right-hand side of the expression as follows
Br 1 2) Applying Lemma
C.2
T
T
a
g.
1 S 2,
Σ n=1
(lg. -2 + b h + v2 a Σ
Pn.
n=1
n=1
This effectively decouples the noise in llg. hr into separate, more manageable com- ponents. We now focus on bounding the expectation of the first term in the preced- ing inequality. By applying Jensen's inequality and invoking Assumption 2.3 we ob-
tain: E 2 ET (lgg, 8. + ll,, h,,l)) & V Ellgg, g.ll2 h 1 < 2 2/20VT. Therefore, it only remains to upper bound
( 27
(3D
3D -10
a
Un
(21)
477p
n=1
Note that by the definition of Tn in
8 have 17n
DD Also, by the definition
Va+ in
i = maxisnsM M
w. -n-1ll Ill we have I
Ilg. l8.-hh,ll
2 >
gn h (Lyya Un. Hence,
(1p)2
we obtain that D 4m
A,
2 E T
-==
Vo+
pn Hence, the term in (1 can be
TD(11))
upper bounded by 4
3D 2-y
+ DD a E
/+ pi
D Mn. which in turn is bounded
in the following lemma. Its proof can be found in Appendix
C.5
Lemma C.6. Given the previously defined quantities pn, and i we have the following
3D + tDD)
a
Σ Pn
Va Ei 14
pn 16
( 3
+7)
$ Li D2
24
7D(Li)²
27
Combining all the pieces together yields
a +7)
3 (+))) DVTo+16 3
E (g., A. - u ) 58
D
27
#=1
and this completes the proof.
23

---

Published as a conference paper at ICLR 2026
C.3 PROOF OF LEMMA C,4
Setting u², we sum the inequality from Proposition C.3 overn = - -1
Σ gr
gn: A n
u
hT, AT
u')
(g1
h1.
A u
7n mnllgn hh
T
|
|
12112
+ -
-111i1 u u²12
Ar 1'11
21/x+1
21/n
2m
21T
==1
T
1 Anll?
47mm
n=1
First, note that by the definitions of h and A, we have A migmin
A A).
This implies
that (h1, A - u') < 0. Therefore
T-1
Σ gn: An u²) S (gT hT, AT u²)
In ggn
h
1
|
u²112
2nn+1
2n
T-1
1
+ 21/1
A
1²112
Ar
112
112
21T
4mm
==1
Additionally, applying the Cauchy-Schwarz and Young's incqualities, we can bound
(gr hT,
A
n²) 1 gr
hr
u²
gT
hrll
+
- 11 AT u u²12
1
2
21T
Combining all the inequalities, we obtain
T-1 +
gn,
n²)) v TT 2
gr
hr
2
malggn
-h,l12
1
-1 A Anl1?
47mm
n=1
1
Ant
12/12
+
||
A 121
2mm+1
21m
2m/1
As Th decreasing sequence, by definition
8 we have
1
2
Additionally,
2nn+1
27pm
A < D and ||u||
< D. Therefore, we have
|| n
u
+ 2m
|
2mm41
Imm
u 1| < 4D
-T= T- n=
+
1D
2D
Hence
20
2mp
2m
Σ
T
gg: A
1 -
TT
ggr hr
1
Σ
Thi nml..
h
11 Antt
Aml13)
2D
4nn
2D2
+
'/7
Igr
hr 1|2 +
T-1
nal nmllgn
hn
|| A 1n-
2
4nn-1
n=
1
Ar
Ar- 11 + m l[g:
h1ll
41
24

---

Published as a conference paper at ICLR 2026
Note that 22 gr
hr
I mr
hrll? Therefore, we can state the following upper bound
2D
nn A u
1n ll. hnll
| An-=11²) + 7h Villg: h1ll?
1/T
41/n11
2D
T
A Am-111) + +milg: - -hill
?h lllgnn
bnll
4//m
n=
T
1
11
A, 1112
T/n
7/-1
n=
2D
Am- +mllg: -hil h1ll2
7n mallggn
hnll
4/T
41m
n=
D
D
4T 7
1 1|,, An-1l while Here, the first equality follows by adding and subtracting the term Σ 4nj the final inequality uses the facts that we observe that
0 0nd
112 I 4D², Moreover, || An-1l1
11a
Un
D2
S
A
Dol 1|2 Therefore
4011
T
3D2
1 I An An-11?)
ga. A
u
+
Σ
No BallBn hn.l
1/
4rjo.
This completes the proof.
C.4 PROOF OF LEMMA C.5
Using 7n, as defined in 8 and noting that we are analyzing the first episode (so n mod T simplifies to ni,, we have
3D
T
3D
DD1g
-h,,1
nal n....
1 7
a g:
h +
Tfr
V
a
+
Σ
1g
h
n=1
Applying the inequality va b Va + vb for b 2 0, we obtain
3D
T
3D
3D γ
DDgg h 12
Σ
nn lg.
Va +
Σ
g: h
Σ
7/
Σ 1=1 Ig. -h
n=1
Applying the upper bound corresponding to the lower bound from Lemma C.I
we get
3D
3D
3D 7
Σ I....
2 7
Vo +
Σ lg: h1
2yD
Σ
g: h
Utilizing the fact that (Va + vb)² < 2(a + b) leads to
3D
3D
nn gn
h 2
27
+ 7D)
/
Σ
ga h 12.1
n=1
25

---

Published as a conference paper at ICLR 2026
C.5
PROOF OF LEMMA C.6
Proof. Applying Lemma obtain
3D 27
T
Va 2i bi
+7D)
a
Un
Un
? ((,g))
3D Va + Va+4
3D
> Un
Va 2i-1 Mi
<
27 DD)
+7D)
Un-
27
V 2i=1 M4
(Ig)2nD
Reorganizing the terms, we further have
3DD
Nn Σ Va Va+ E 14
4
+ +7D)
a
2y
DD(Li)
S 4
3D +nD)
Va +
4 ( + +nD)
(3D
a Ei= (Li)?n
Pn
(22)
2y
Ea+EEa K4
Observe that the quantity (4 (4(2) 2y
+ +DD)
a -E defines a decreasing sequence with respect 2(1:)9D
n. Define T as the smallest integer such that for all T the following holds
3DD
a + M 0
4
+ +1D)
2y
(L
Remark C.2. For sufficiently small a, ensure that the following two inequalities hold, where T is an integer between 1 and T':
Then, the following two scenarios hold, depending on the value of n
4
3D
+2D)
(Li) sa Σ #4
T
27
4
3DD
+ >D)
Σ Hi TT
(23)
27
1=1
Returning to equation
22
with this definition of T* we have
4
[3D
+ 1D)
T
Pn
T
Ei Ui
pn 54
(3D 3D
+1D) Va
27
DD(Li)²
27
1=1
T
3D
+ 7D)
a
-+E
Hn
2
(11))T1
Va >im Pi
n=1
By discarding the negative terms, we obtain
4
(3D
+ +nD)
a+
pn
a Σe
pn <4
3DD
+7D Va
2
?D(ig)²
27
==1
n=1
T
4
3D
+7D
Pn V
27
Σ 14
#=1
26

---

Published as a conference paper at ICLR 2026
Observing that
and applying Lemma C.1 to this sequence, obtain
V E.
2i-1
D. 22-1
3D 27
a +
"
33D
4
+ +7D)
a
pn
Un S
+7D)
va
27
33D
tnD)
T Σ Un.
+ 8
27
Combining terms
4
3D 7D)
+
a
VI a
Li=1 14
Un 58
(3D
+ +
T Σ
Mn-
27
D(L))
27
Invoking the upper bound for T from 23
(3D a
+ +DD)
Σ Pn
a + Li=1 Mi
Un 58
3D
3DD + 7D) /
+20) (19)27D
27
27
27
3
3
Di
16
+7
27
This concludes the proof.
C.6 PROOF OF THEOREM 4.2
Note that the algorithm restarts after every T iterations. Therefore, the bounds proven for the first episode apply to each subsequent episode, and as a corollary of Lemma 4.1 we obtain
+7) 3 & 27
[Regr(u'...... u }] S 8 27 + +7) DKVTo+16
3
KD? Together with Propo-
sition 2.1
we can show that:
K
[FF("))]l S F(xo) F+
DM + 801 o
+ 160 isnt D
La
D2 +
La 22 a VT
+
K
VT
T
48
2
3 + also define C2 = (1 +1 18++++11
where C1 =
27
Equivalently
1 K
[VF(W*)]
F(xo) F+ DKT
+ VT + 100
D T L2T
(24)
Based on the upper bound in 24). the hyperparameters D, K, T must be chosen under the constraint KT < M, where M denotese the total iteration budget and K, T N. To obtain the sharpest bound, we will first determine T and K, and then specify D.
If we set T min max
([
Caa L,
(10c
Lin # L.
and K we can
bound the first three terms of the inequality (24)
follows:
KT N 2f 1)T M - M/2 which implies
F(x))-F'
<2 F F(x)-FF DM
DKT
16c Liy T
3,C i D
max
max (LL 3 320 Lix
( o C2 (141
C2 < max
27

---

Published as a conference paper at ICLR 2026
We upper bound D² as follows:
22T² D2 S L2 max ([(220)
C20
#. 7. .
Ligz
$1
2
D2
L2
S L2 {
372
D² + Lz ( (1807 Liy'
372
C2a
D³a
D2D2
L
Using the fact that [x]] < (x + 1)2 S 2x + 2 for any x 2 0, we obtain
C2ar
2 (16c Lij's
LTTD² & L
+2 +2) D² + L2
+2 D²
D2D2
L2D
t D2D² )
C2Ø
D² + 2L2 11o 1:17²²
= =2h
D² + 4L2D2
L2D
< 22c 12 D + 130, (i,) 3 D3 + 4L2D2
Substituting these values into 24p yields
VF w ||| < F(xo) F"
+ max ( M
D
K 1=1
DM
1 ) + +2C 130 (Li) &
max
VM
Using max(a, b) < a + b, and after rounding constants, we get:
K
VF(w*)ll < F(xo) - F + 32 D M C2V2
K
DM
VM
+ 3C L LI DZ 20C (Li) DLzD2.
(2
F(xo)- -
Setting D =
leads to the following upper
1
bounds:
L D (
C CIL+ot
s 3 (F(
M² C L
M²
20L3 C
20 (i7) レ3 [F(x))
Vn
107M7
by (i:)² L
(F()
M7
2 F(x < 2
LJ (F(x)) F
+ 2 1.5 (F(xo) F
C2
L3o 5
DN
M7
c (1:) レ FF
+ 3 (F(x)) F
C L :
M²
N
32 2 R < 10
0 (1 v A (F(x)) F(xx)-F')} 7
12 (t7) 4, ft (F(x)) F
M 4 L
19
28

---

Published as a conference paper at ICLR 2026
AL2D² & (F(x)))
- (F(0))))))
107 M (
Mr (
Finally, substituting this value into the bound yields
VF S 12 (ii)* L (F(x)) - F=)
(F(x)) - F
C L3
M7
M²
C
(ij) 3 y La (F (xn) F*)*
(Fxx))) F*)
+ 12
+ C2v2
M M L
M (
VM
This final bound confirms the convergence rate stated in the main theorem, as the last three terms are of higher order and thus do not influence the rate.
D USE LARGE LANGUAGE MODELS
Large Language models used lightly refine wording and correct grammatical errors in parts of the paper.
29


Reviews:
[{"review_id": "dF7Fy7D2r8", "reviewer": "Reviewer_4KMs", "summary": "This paper revisits the online-to-batch conversion paradigm for nonconvex optimization, focusing on the gap between online regret and stationarity guarantees. Classical online-to-batch techniques translate sublinear regret bounds into expected stationarity, but typically require either (i) bounded gradients or (ii) smoothness and convexity assumptions that limit applicability.\n\nThe authors propose a refined conversion framework -- generalized online-to-nonconvex conversion (Go2N) -- that directly bounds the gradient norm of the average iterate without relying on convexity or heavy smoothness assumptions. The contributions can be summarized as follows: (i) A new regret decomposition that connects weighted dynamic regret to expected stationarity through gradient averaging lemmas. (ii) Applications to stochastic and adversarial nonconvex optimization, yielding improved dependence on learning rates and gradient variance. (iii) An extension to adaptive algorithms (e.g., AdaGrad, Online Newton Step), providing the first theoretical bridge between regret and stationarity for such adaptive schemes. (iv) Experiments on nonconvex online learning tasks (e.g., nonconvex matrix factorization, deep linear regression) showing faster convergence to stationary points than standard online-to-batch baselines.", "questions": "1. Can the conversion framework be extended to constrained or manifold-based nonconvex settings?\n2. How does Go2N perform under stochastic non-i.i.d. gradient noise?\n3. Are there concrete examples where Go2N achieves provably better asymptotic rates than the Cutkosky (2022) reduction?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The work revises the fundamental link between online regret and nonconvex stationarity, providing a general and unified theoretical treatment. The new conversion inequality—based on a telescoping analysis of projected gradients—sharpens previous results such as those by Hazan et al. (2017) and Cutkosky (2022)\n\n2. The proposed conversion yields a tighter upper bound, improving constants and eliminating dependence on boundedness assumptions. \n\n3. The framework is compatible with a broad class of online learning algorithms—including mirror descent, AdaGrad, and optimistic variants—demonstrating wide relevance to both optimization and learning theory.\n\n4. The paper is well-organized, mathematically clean, and pedagogically presented. The proofs are compact yet general enough to apply to diverse online schemes.\n\n5. Experiments, while modest, confirm theoretical predictions: algorithms derived via Go2N achieve faster decrease in gradient norms and improved training stability compared to standard regret-based methods", "weaknesses": "1. The main insight—a refined conversion between regret and stationarity—extends existing frameworks rather than introducing a fundamentally new algorithmic principle. The contribution is primarily theoretical sharpening rather than conceptual breakthrough.\n\n2. Empirical results are confined to small-scale nonconvex problems (e.g., 2-layer linear networks, low-rank factorization). It would be more convincing to include modern deep learning benchmarks to demonstrate practical impact.\n\n3. The analysis still relies on Lipschitz continuity of gradients and smoothness constants. It remains unclear how tight the improved bounds are in practice, especially under adversarial noise or stochastic gradients.\n\n4. The paper could better position itself against recent advances in nonconvex online learning (e.g., Jin et al., 2023; Duchi et al., 2024) and adaptive nonconvex regret analysis, which also aim to establish gradient-based guarantees.\n\n5. The work provides only upper bounds; without matching lower bounds or counterexamples, the “improvement” claim remains qualitative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rVUtAABijw", "reviewer": "Reviewer_Nne7", "summary": "The paper proposes a new algorithm for smooth nonconvex optimization based on an online-to-nonconvex (O2NC) framework. Building on prior work, it introduces a doubly optimistic hint function in the online learning subroutine to simplify the algorithm and improve theoretical guarantees. The theoretical results show convergence to an $\\epsilon$-first-order stationary point with improved rates in both deterministic and stochastic regimes.", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is generally well-written, with a logical presentation of prior work, motivation, and main contributions.\n\n* The complexity analysis is rigorous and improves on existing bounds by removing logarithmic factors.\n\n* The algorithm handles both deterministic and stochastic settings without requiring separate analyses or algorithms. This universal applicability is a notable advantage.", "weaknesses": "* It would be helpful to understand whether the algorithm and proofs can be extended to constrained or nonsmooth functions. While it is understandable that such generalization may be challenging, could the authors discuss potential difficulties in these settings and how the algorithm might be adapted?\n  \n* For the optimistic step, a natural estimation is $g_{n+1} = 2 g_n - g_{n-1}$. Could the authors clarify why this choice was not adopted and what motivated the current design?\n\n* The paper focuses on general nonconvex objectives. It would be interesting to see how the convergence rate could improve if the function is convex or strongly convex. Could the authors provide insights or analysis for these special cases?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HhmZB87jZh", "reviewer": "Reviewer_sQGF", "summary": "The paper builds on O2NC (Cutkosky et al., 2023) to propose a simple first-order method for smooth non-convex optimization. For problems with Lipschitz-continuous gradients and Hessians, the algorithm achieves an $O(\\epsilon^{-1.75} + \\sigma^2 \\epsilon^{-3.5})$ convergence rate, thereby interpolating between the best-known deterministic and the worst-case optimal stochastic rates.", "questions": "- Do you think 2 gradient evaluations per step is essential for getting a simple algorithm?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The technical strengths are \n\n- Improving upon Cutkosky et al 2023 with a simpler algorithm. \n- Getting a rate that interpolates between deterministic and stochastic settings. \n- Providing adaptive step size scheduling and making progress towards fully parameter-free algorithms.  \n\nThe paper is well-written and nicely presented.", "weaknesses": "I do not see any noticeable weaknesses to this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F98pPl4JZC", "reviewer": "Reviewer_miQo", "summary": "This paper proposes a novel method to improve the recently proposed online-to-nonconvex conversion framework (Cutkosky et al., 2023) under gradient and Hessian smoothness assumptions. Two levels of optimism are used when solving the online learning problem in (Cutkosky et al., 2023). The algorithm achieves the complexity of $\\mathcal{O}(\\epsilon^{-1.75} + \\sigma^2 \\epsilon^{-3.5})$, which recovers the best-known rates under both deterministic and stochastic settings. An adaptive variant of the method is also proposed.", "questions": "1. In lines 289-290, “base the update of $\\Delta_n$ on the current gradient $g_n$, but this is not feasible because  $g_n$ is revealed only after $\\Delta_n$,” perhaps $\\Delta_n$ and $g_n$ should be changed to $\\Delta_{n+1}$ and $g_{n+1}$ to maintain consistency with the context?\n\n2. It seems that Lemma C.1 is the same as the ones used in (Levy et al., 2018; Kavis et al., 2019; Antonakopoulos et al., 2022), which I think should be explicitly mentioned.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The article is well-written, with the authors clearly articulating their ideas. The derivations presented in the paper lead naturally to the proposed algorithm, making it easy for readers to follow the authors' thought process. Furthermore, the final algorithm can be implemented with a single loop, and each iteration only requires a single batch, suggesting that it could be effective in practical applications.  The theoretical improvements over (Cutkosky et al., 2023) are also sound: improving a logarithmic factor in the deterministic case,  removing a stronger assumption in the stochastic case, achieved with a unified algorithm that can be extended to adaptive optimization.", "weaknesses": "1. The main results of this paper become relatively straightforward given the inspiring recent work (Jiang et al., 2025), and the idea of double optimism has also appeared in that work, and that work also remarked explicitly that a $\\mathcal{O}(\\epsilon^{-1.75})$ complexity is achievable.  Although the results in stochastic problems and adaptive optimization were not mentioned in \n(Jiang et al., 2025), they appear to be expected from prior analysis (Levy et al., 2018; Kavis et al., 2019; Cutkosky et al., 2023). \n\n2. Although the article improves upon the results under the second-order smooth setting in O2NC, the main contribution of O2NC lies in its results under the non-convex non-smooth setting, rather than the non-convex smooth setting. It is reasonable that the original O2NC can be improved under the smooth setting.\n \n3. Moreover, no experiments are given in this paper, though I think the algorithm is simple to implement and believe it can work well in some scenarios.\n\nThese reasons led me not to assign a higher score.\n\nAnother minor weakness in the article is the limited references to past literature; for example: the prior $\\tilde{\\mathcal{O}}(\\epsilon^{-3.5})$ results before he works by (Cutkosky and Mehta 2022; Cutkosky et al., 2023) were presented in reference [1-4] which I believe should also be cited. Additionally, O2NC was primarily proposed to address the non-convex non-smooth problems discussed in reference [5], but this citation is also missing.\n\n[1] Fang, Cong, Zhouchen Lin, and Tong Zhang. \"Sharp analysis for nonconvex SGD escaping from saddle points.\" In COLT, 2019.\n\n[2] Tripuraneni, N., Stern, M., Jin, C., Regier, J., & Jordan, M. I. \"Stochastic cubic regularization for fast nonconvex optimization.\" In NeurIPS, 2018.\n\n[3] Allen-Zhu, Z.  “Natasha 2: Faster non-convex optimization than SGD\". In NeurIPS, 2018.\n\n[4] Allen-Zhu, Z. \"How to make the gradients small stochastically: Even faster convex and nonconvex SGD\" In NeurIPS, 2018.\n\n[5] Zhang, Jingzhao, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. \"Complexity of finding stationary points of nonconvex nonsmooth functions.\" In ICML, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)