Derandomized Online-to-Non-convex Conversion for Stochastic Weakly Convex Optimization
Authors: Fanfan Ji
Xiaotong Yuan
Venue: ICLR 2026 Poster (2026)
Keywords: Non-smooth optimization
Non-convex optimization
Stochastic gradient descent with momentum
Online learning
Neural networks
Primary area: optimization
TL;DR: A derandomized O2NC method for stochastic weakly convex optimization with optimal complexity and competitive numerical performances

Abstract: Online-to-non-convex conversion (O2NC) is an online updates learning framework for producing Goldstein $(\delta,\epsilon)$-stationary points of non-smooth non-convex functions with optimal oracle complexity $\mathcal{O}(\delta^{-1} \epsilon^{-3})$. Subject to auxiliary \emph{random interpolation or scaling}, O2NC recapitulates the stochastic gradient descent with momentum (SGDM) algorithm popularly used for training neural networks. Randomization, however, introduces deviations from practical SGDM. So a natural question arises: Can we derandomize O2NC to achieve the same optimal guarantees while resembling SGDM? On the negative side, the general answer is \emph{no} due to the impossibility results of~\citet{jordan23deterministic}, showing that no dimension-free rate can be achieved by deterministic algorithms. On the positive side, as the primary contribution of the present work, we show that O2NC can be naturally derandomized for \emph{weakly convex} functions. Remarkably, our deterministic algorithm converges at an optimal rate as long as the weak convexity parameter is no larger than $\mathcal{O}(\delta^{-1}\epsilon^{-1})$. In other words, the stronger stationarity is expected, the higher non-convexity can be tolerated by our optimizer. Additionally, we develop a periodically restarted variant of our method to enable more progressive updates when the iterates are far from stationarity. The resulting algorithm, which can be viewed as a momentum-restarted variant of SGDM, has been empirically demonstrated to be effective and efficient for training ResNet and ViT models.

Published as a conference paper at ICLR 2026
DERANDOMIZED ONLINE-TO-NON-CONVEEX CON- VERSION FOR STOCHASTIC WEAKLY CONVEX OPTI- MIZATION
Fanfan Ji Xiao-Tong Yuan"
School of Intelligence Science and Technology Nanjing University
Suzhou, 215163, China
State Key Laboratory for Novel Software Technology
Nanjing University
Nanjing, 210023, China
{jiff1995 xtyuan) ju x edu. en
ABSTRACT
Online-to to--oo--onnoeee conversion (O2NC) is online updates learning frame- work for producing Goldstein (6, --sttationyyy points of non-smooth non-convex functions with optimal oracle complexity 06--1-3)). Subject auxiliary ran- dom interpolation or scaling, O2NC recapitulates the stochastic gradient descent with momentum (SGDM) algorithm popularly used for training neural networks. Randomization, however, introduces deviations from practical SGDM. So natu- question arises: Can we derandomize O2NC to achieve the same optimal guar- antees while resembling SGDM? On the negative side, the general answer is no due to the impossibility results Jordan al. (2023), showing that no dimension- free rate can be achieved by deterministic algorithms. On the positive side, as the primary contribution the present work, we show that O2NC can be naturally derandomized for weakly conver functions. Remarkably, rithm converges at an optimal rate as long as the weak convexity parameter no larger than O05-'c (1). ).. In other words, the stronger stationarity is expected, the higher convexixy can be tolerated by our optimizer. Additionally, we develop periodically restarted variant of our method enable more progressive updates when the iterates are far from stationarity. The resulting algorithm, which can be variant SGDM, has been empirically demon-
deterministic algo-
viewed momentum-restate strated to be effective and efficient for training ResNet and ViT models.
INTRODUCTION
Classic machine learning optimization methods often rely crucially on convexity and/or smooth- ness assumptions to guarantee the convergence to optima (Nesterov) 2018, Bubeeck] 2015) Snyman 2005). However, many modern large-scale machine learning models, such as residual neural net- works (He al. (016) and transformers (Vaswani al.) (017)), involve non-smooth and non-convex objective functions. These models achieve state-of-the-arr performance precisely thanks to their ca- pability to learn highly complex, nonlinear hidden representations data. Given such widespread use, efficient non-smooth and non-convex optimization algorithms are of central theoretical and practical interest.
Specifically, this paper is concerned with stochastic gradient algorithms for solving the following expected risk minimization problem ubiquitous statistical learning:
min R(w) = Ez~pl [f(w; 2)]. A
(1)
where E: 2dd Z - R is nen-neee loss function whose value f(w; 2) measures the loss evaluated at = E Z with parameter w E R and D represents distribution over the measurable
"Corresponding author.

---

Published as a conference paper at ICLR 2026
set Z. We consider the setting where the loss l is Lipschitz continuous with respect to its first gument, yet potentially neither convex nor smooth. In contrast to the smooth counterpart, finding an e-stationary point (or even neighborhood around it) of non-smooth objective in [ gener- ally intractable (Zhang et al. 2020, Kornowski & Shamir 2022). This intractability motivates the notion of approximate conver- gence for non-smooth non-convex functions (Zhang et al. 2020). The study of efficient algorithms with finite-time complexity guarantees for finding (6, -stationary points has since received ever emerging interests in non-smooth, non-convex optimization (hang et al. 2020 Davis et al. 2022
employment of Goldstein (o, -sstationartty (see Dehnition
Cutkosky al., 2023] Jordan et 2023 Tian & So 2024. Kong & Lewis 2025).
Developed by Cutkosky et al. (2023), , the online-to-non-convee conversion (O2NC) method finds (ő, - points of problem ] with ( stochastic gradient oracle calls, attaining the optimal first-order complexity. As outlined in Algorithm | O2NC essentially converts an online leamner (highlighted in light red to stochastic gradient optimizer (highlighted in light blue ). It recursively updates the increments An := Wn Wn-1 between consecutive iterates via invoking an online convex optimization (OCO) algorithm A to minimize the regret Σx=1 (0n, An - A), where the stochastic subgradient 9n is evaluated at random intermediate state En Wn-1 + S, with 8n ~ Uniform( [0, 1]). The optimal oracle complexity can be achieved by any instantiation of A with optimal regret bound, such online gradient descent (OGD) (Zinkevich 2003).
Beyond theoretical optimality, another appealing feature of the O2NC framework is its potential to recover the stochastic nomentum-basee optimizers widely used in neural network training. Indeed, under the random interpolation scheme over iterates, O2NC equipped with projected OGD becomes clipped variant of SGD with momentum (SGDM) Cutkosky et al. 2023). Alternatively, Zhang & Cutkosky (2024) introduced the Exponentiated O2NC (E-O2NC) framework with exponential random scaling on the updates, which nearly recovers the standard SGDM when combined with
unconstrained online mirror descent (OMD) (Beck & Teboulle 2003). Within the O2NC framework, Ahn et al. 2024) showed that the widely used Adam optimizer (Kingma Ba 2013) corresponds to a discounted variant of the Beello-thheRegulanne analyzed the merits of its key algorithmic components: momentum and discounting factors.
Leader (FTRL) algorithm (Gordon) 1999). and
Algorithm 1: Onnline-to-non-coovee Conversion (O2NC) (Cutkosky et al.
2023
Input : OCO algorithm A, K,T E N, initial point wi and increment A Set N K T.
for n = 1,..., N do
Stochastic gradient optimizer +/ Update w/ = wn-1 + Axi
Compute random interpolation v, Wn-1 8n An. where 8n Uniform([O. 1]); Randomly sample 2n ~ D and obtain 9n E Øl(Uni
/+
Online learning of increment */
Send the linear loss (gm, A) to and receive the next increment Ant1 from A.
end
Set Wi - Ak E [K],4 4 E [T], and (k)) 1
(k) T ET= Wi
Output: WT ~ Uniform( (k) A [K])).
Despite the appeal of O2NC in explaining the effectiveness and efficiency of SGDM-style optimiz- ers, the resulting algorithmic correspondence inherently relies on several auxiliary randomization procedures, such as uniform interpolation iterates exponential scaling on increments. However, such randomization components are rarely, if ever, used in practical implementations of SGDM. This fundamental gap motivates to investigate the following question:
Can the O2NC technique be derandomized to still achieve optimal dimension-free guarantees while maintaining a close resemblance to SGDM in the non-smooth, non-convex setting?
Unfortunately, the general answer to the above question is negative: it has been shown by Jordan et al. (2023 Theorem 1) that no dimension-fin free rate be achieved by deterministic algorithms in the worst case. Fortumately, in this paper, we show that for weakly convex functions, one can indeed develop deterministic variants of O2NC that find Goldstein-stationary solutions with optimal rates.
2

---

Published as a conference paper at ICLR 2026
1.1 OVERVIEW OF OUR RESULTS
Our main contribution is derandomized O2NC framework (Algorithm 2 for solving the stochastic optimization problem with a p-weakly convex risk function, mcaning that R(-) + 211.11 Inspired by the original O2NC, our key development leverages weak convexity to naturally reformu- late the optimization of iterates W,, as the online learning of increments A, with respect to quadratic losses (0n: > + ž || 2| for some Y 2 p. In contrast to evaluating gradients random intermediate point Up between consecutive iterates Wn and Wn-1, our method evaluates gradients exactly at each iterate W,, Wn-1 + An. yielding fully deterministic algorithm (up to stochastic gradient estima- tion). Concretely, we propose two optional online learners for updating the increments An. which are summarized as follows:
-12 is convex.
Derandomized O2NC with clipped OGD (Section 3.2). The first option is a simple projected OGD algorithm under an appropriate ball constraint. The resulting algorithm can be interpreted as a clipped variant of SGDM, without requiring extra random interpolations. Our convergence analysis (Corollary
D shows that the proposed deterministic method identifies a (6, --statiionary point with O (8- + + + stochastic gradient oracle calls, which dominated by the optimal rate 8-1c-3 Strikingly, the weak convexity parameter p does not appear in this dominant term, and it can scale as large as 0 in its associated term before matching the optimal rate. This observation implies that the smaller the required (ò, e), the higher the non-convexity our optimizer can tolerate while still achieving optimal oracle complexity.
As the original O2NC, our first approach based OGD under an explicit ball constraint tends to be overly conservative for increment updates and is also impractical from the viewpoint of standard SGDM implementa- tion. To overcome this limitation, our second scheme, we further introduce novel periodically restarted OGD procedure, which resets the increments to zero after a fixed number of iterations. The resulting method is nearly identical to the standard SGDM, differing only in that the momentum update is periodically restarted from scratch. Under a novel notion of (f4, e--eeuularized stationar- ity (see Definition 2). which is equivalent the Goldstein stationarity, we establish in Corollary that the proposed deterministic, unconstrained O2NC algorithm converges with the composite rate 2/3 + +,1/2), where p = 0(n2/2 is admissible without dominating O (12/22-7/2 + p/ --2/3
Derandomized O2NC with periodically restarted OGD (Section 3.3)
the optimal term /22/2
Coupled with our theoretical results, we conduct extensive numerical experiments on standard benchmark tasks to validate that the proposed momentum-restaree SGDM variant achieves performance comparable to, or even better than, the standard SGDM when training deep residual networks and vision transformers (Section
1.2 RELATED WORK
Our work is situated within the broad landscape of non-smooth and non-convex optimization. Below provide brief overview of closely relevant prior work.
Non-smooth optimization. The foundations of non-smooth optimization trace back to the sem- inal work of Clarke (1775); Goldstein (1977). While asymptotic analysis of non-smooth opti- mization problems has been extensively studied (Benaïm et al.] 2005) Davis et al.] 2020) [Bolte] & Pauwels 2021), non-asymptotic guarantees for generic non-smooth settings remained elusive for a long time. A pivotal advance was made by Zhang et al. (2020). who established finite-time com- plexity bounds for subgradient algorithms targeting Goldstein stationary points-thi this breakthrough spurred a surge of follow-up research (Davis et al., 2022 Kornowski & Shamir 2022 Cutkosky al. 2023 Jordan et al., 2023 Kornowski & Shamir (024). Notably, building on the online-to- batch conversion paradigm (Cesa-Bianchi et al. 22004), Curkosky et al. (2023) introduced the O2NC framework, which for the first time derived optimal convergence rates for stochastic non-smooth, non-convex optimization. By instantiating different online learners within O2NC, one recover several widely used optimizers: SGDM corresponds to online mirror descent (Zhang & Cutkosky. 2024], Adam aligns with a variant of fellow-the-Regulatee Leader (Ahn & Cutkosky (0224), and most recently, Ahn et al. (2025) showed that a generalized O2NC framework also encompasses schedule-free SGD (Defazio et 2024).
Stochastic weakly convex optimization. The class of weakly convex functions, first introduced in English by Nurminskii (1973), is broad and easily identifiable, as it encompasses all composition
3

---

Published as a conference paper at ICLR 2026
forms h of convex functions and smooth maps. For weakly convex optimization problems, vast literature of asymptotic convergence results has been established for stochastic optimization algorithms (Ermol ev & Norkin 1998 Duchi & Ruan 2018). However, finite-time non-asymptotic convergence rates remained largely unresolved until a series of breakthroughs by Davis & Grim- mer (2019); Davis & Drusvyatskiy (2019); Mai & Johansson (2020), who showed that various SGD/SGDM algorithms achieve the optimal O(E=*) rate for producing an e-stationary point of the Moreau envelope of the objective function. From variational analysis perspective, several dis- tinct notions of approximate subdifferentials have been analyzed and compared for weakly convex functions (van Ackooij et al., (024). In practice, weakly convex optimization has found widespread applications in deep learning, signal processing and control theory (see, e.g., Duchi & Ruan 2018 Davis & Drusvyatskiy 2019 Drusvyatskiy & Paquette 2019 Pougkakiotis & Kalogerias 2023
PRELIMINARIES
Let us begin by formally introducing some notation, key assumptions, and preliminary results on non-smooth and non-convex optimization.
2.1 NOTATION AND ASSUMPTIONS
Notation. Throughout this paper, we denote || as the Euclidean norm, and (..)) as the Euclidean
inner product. For a vector set V S Rdd we denote dist(0, V) := infoev ||||| and conv(V} the
convex hull of V. For any positive integer N, abbreviate [N] = {1, ".......... N). The symbol Bs(w) denotes the closed ball of radius 8 centered on w, and clipp(w) := w min {
Tw denotes
D
the Euclidean projection operator associated with the constraint of (0). For a pair of functions f O, we use - O(f") to denote cf' for some universal constant >>
We say that a function / Rd - IR is G-Lipschitz continuous if [[(w) f(w")l < Gllw - w'll for all w, w' e Fd The Clarke subdifferential (Clarke [990) of a non- non-smooth function f at w Rd is denoted by (w)). Recall that f is said to be p-weakly convex for some p > if the quadratically regularized function f(.) + 2ll 1|2 convex, or equivalently
f(w) 2 f(w') (g', w w') _ I w- w' 1|2, Vw, w' E ,R E =f((w').
A key class of weakly convex functions takes the composite form f(x) = h(((x))) where h is con- vex and G-Lipschitz continuous function, and e is a smooth mapping with L-Lipschitz Jacobian. These composite functions are neither smooth nor convex, but rather GL--waklly convex (Davis & Drusvyatskiy 2019). A concrete example, considered in our experimental study, is neural networks equipped with smooth activation functions (e.g., softplus and GeI.U): their loss functions follow the composite form h o c, where /t denotes a convex top-layer predictor (c.g.. cross-entropy loss) and e represents a smooth hierarchical feature mapping. For additional examples of weakly convex functions, we refer interested readers to Davis & Drusvyatskiy (019);; Asi & Duchi 2019))
The Moreau envelope (Rockafellar 1997) a weekkly convex function f with parameter À E p0,p=') is defined by fx(w) == inf uERe {f(u) 1
2X Iu w|l?). J. and the associated proximal map- ping is given by p == arg min {f(u) 2x ||u w|]2]. J. The following result (Böhm) & &Wiggt 202T) characterizes the continuous differentiability of Moreau envelope functions.
Lemma 1. Let I be p-weakly convex function and X (0,p-1) be scalar. Then the
Moreau envelope fx is continuously differentiable with gradient ff((w) = {w (u--po --rroxxx(u) e
0 (proox,y(w) which is L-Lipschitz continuous with parameter L max X -
Assumptions. We next impose some key assumptions on the loss and risk functions in problem for stochastic gradient-based based optimization.
Assumption 1. For any z E Z, the loss function E(:;2) is G-Lipschitz with respect to its first argument. Moreover, the expected risk function R is p weakly-convex.
Assumption 2 (Stochastic oracle). For each w IRd, it holds that ((w)) = EEzzDee(ws Z)] aR( w). where El (w; 2) E al(w; 2), for any 2 E Z.
Also, we assume that R win R(w)= > -oo and abbreviate ARo R(wn)) R²
4

---

Published as a conference paper at ICLR 2026
2.2 REGULARIZED GOLDSTEIN STATIONARITY CRITERION
For general non-smooth, non-convex functions, Goldstein (ó. e)-stationarity (Goldstein serves standard criterion for convergence analysis, and is defined formally below. Definition ((6, (ddtci-Staionaaittt). The Goldstein ó Ó-subdifferential of a Lipschitz, E Rd the convex hull of all Clarke subgradients at points in a ô-ball around w, i.e.,
1977
f at a point
O&f (w) conv' (w) Of(v)}
A point w is called (6, --statioony point if dist (0, (w)(())()))))) Se.
While finite-time guarantees on the (6, -statioonnay have been thoroughly studied in the original O2NC framework (Cutkosky et al. 2023). the corresponding analysis inherently requires online increment updates to be explicitly constrained within a ball of radius de² which can be overly con- servative. Inspired by Zhang & Cutkosky (2024), we next introduce novel regularized variant of (ò, staationnay which obviates the need for such explicit constraints, thereby enabling potentially more aggressive increment updates. Given a subset V S Rd, we define the set-valued mapping f == conv (U)evê((v)). We further define the j-regularized subdifferential norm as
[[0f(w)l++t == inf ddist(0, fv sup ||v VCRd
w
Definition ((,,e) Reguulaaid Stationarity). point w is said to be (p. e) -eguulrrie stationary point of a Lipschitr.uuntion f [[af(w))l++ S.
Remark 1. Intuitively, rregulareee stationarity jointly controls the magnitude of the convex hull of subgradients evaluated at points in an underlying subset V, as well as the proximiry of V to w. In contrast to the relaxed Goldstein stationarity introduced by Zhang Cutkosky (2024), our formulation employs supremum norm penalty instead of its average counterpart, which yields an exact equivalence to the original (ô, -sttttatiionaattt as summarized in the following lemma (see Appendix A. for its proof).
Lemma 2. Let 8, C,C,H. be arbitrary positive values. Consider function f.
(a) If w is a (6. --statiooryy point, then it is also a (5,,2) 2e))rrgglarizer stationary point.
(b) w a (n, rregulrrre stationary point, then also a (Vioe) -stationary point.
We further state the following lemma, which establishes the monotonicity of [[0((w +p with re- spect to the regularization strength parameter μ. A proof is provided in Appendix A.2 Lemma 3. Let f be a Lipschitz function. Then for any E Rdd and O P S p2, holds that [10(w)))+ [10((w)))+
3 DERANDOMIZED O2NC FOR WEAKLY CONVEX OPTIMIZATION
Building on the O2NC framework, we develop in this section a derandomized stochastic subgradient method for computing Goldstein-style stationary points of weakly convex functions. An overview of our algorithm is presented in Section 3.1 Notably, the online learning module of our algorithm incorporates alternative subroutines for updating the increments: clipped OGD and periodically respectively.
restarted OGD, which are described and analyzed in detail in Sections 3.2 and 3.3
3.1 ALGORITHM
The pseudocode for our Derandomized Online-to-non-convex Conversion (D-O2NC) algorithm is presented in Algorithm 2 In contrast to the original O2NC (Algorithm D]. the stochastic gradient optimizer module (highlighted in light blue of our algorithm removes the random interpolation step U, 1 + 8,, An and instead directly evaluates the subgradient 9. at the current iterate wn, w A.- For the online learning module (highlighted in light red ), we propose two alternative OGD variants for updating the next increment A,+1. 1. both are designed to minimize regret sequence of quadratic losses of the form (gn, + 3 1|2, elaborated below:
5

---

Published as a conference paper at ICLR 2026
Algorithm 2: Derandomized O2NC
Input : 77 0, D (optional), K, e N, initial wy and A 0. Set K x for n = I,..,,N do
/+ Stochastic gradient optimizer
Update Wn, Wn-1 + Ani
Randomly sample 2n D and compute In E =d((wniz))
/+ Online Learning of increments +/
(Option-I) Update A++1 = clipp [[1 77) ngnli/* clipped OGD +/ (Option-II) /+ Per periodica cally restarted OGD +/
if mod(n + I, # then
Update A = (1 m)) 79ni
end else
Set An+1 = 0:
end
end
Set Wi -((=-))++ Ak [K],t E [7], and (7(h) E w/(
Output: WT Uniform( (1o(k) [K])).
Option-I (clipped OGD): The online learner A is instantiated as a projected OGD iteration
Ant1 clipp (1 7y)A, ngn] with learning rate r) over D-ball constraint.
Option-1l (periodically restarted OGD): We adopt an unconstrained OGD iteration A.+ (1 (1- n9n, with the modification that An+ is reset to 0 whenever mod (n+1]
1.
In other words, the OGD update for A, is restarted from scratch after every T steps of iteration.
Inspired by the original O2NC, our algorithm minimizes a sequence of quadratic losses in the online setting with the following motivation: for a p-weakly convex risk function R and any y 2 p. we have R( R(w,,) R(w,-1) I E [(ô.. A..) + |, This implies that the increments An can be selected sequentially to minimize the regret term Σa (gn, A.. + 3 I142,] thereby ensuring that the function value gap R(wx) R(ww)) admits tight upper bound. Further details the regret guarantees of OGD for online quadratic loss minimization are provided in Appendix
3.2 RESULTS FOR D-O2NC UNDER CLIPPED OGD
ngå,] which is projected OGD iteration over the quadratic loss function (@n. A) + || subject to a D-ball constraint. Notably, this update step can be connected the SGDM method popularly used for training deep learning models (Sutskever et al.) 2013 Cutkosky & Orabona (019).
Recall that in Option-I, the increments are updated via An+1 clipp [[1 17)
Recovering SGDM. By setting m. = -, and B = 177, we can rephrase the Option-I update as
Wn Wn-1 1 7 -m Ma+1 clipp [[1- [(1-3)m [.m]-
This procedure corresponds clipped variant of SGDM, where m, denotes the search direction (constrained to lie within a D-ball), 9n is the stochastic subgradient, is the learning rate, and the momentum parameter. Compared the clipped SGDM formula implied by the original O2NC (Cutkosky et al., (203), our variant eliminates random perturbations on the iterates entirely.
Complexity guarantees. The following theorem establishes the convergence rate of Algorithm for finding (6. )-tttttionn points of weakly convex functions. See Appendix B.2 for its proof.
Theorem 1. Suppose that Assumption and Assumption 2 hold. Let p be an arbitrary scalar, 7 S ... K,T be positive integers, and D be an arbitrary positive number. Then for any ó 2 TD,
the sequence (
1R=1 generated by Algorithm
2 with Option-I satisfies
K
1/622
2
D
G
AR
dist(O, 0g (g
<
+
7T
+
K
D
T T
VT
DKT

---

Published as a conference paper at ICLR 2026
As direct consequence of Theorem the following corollary establishes the complexity of Algo- rithm 2 (Option-)) for finding Goldstein (ó, e)-staiionary points. A proof of this corollary is provided
in Appendix B33
Corollary 1. Suppose that Assumption 7 and Assumption hold. Let ó, > 0 denote the target Goldstein stationarity parameters, and N the total iteration budget. We set
T T=[(8N)213)
N T
N2/3
1
81/3
K
7=
82/3
11
8N
D
N2/3
Suppose further that
G + G ARo
17)3
1
N
+
de
Then the output UT by Algorithm
2 with Option-I satisfies
E [dist (0, (g,((R))]] E.
Remark 2. We comment that the 068-1e rate, which dominates the composite complexity bound of Corollary [ is indeed tight for weakly convex functions. The key insight that the O88-1e rate is known to be optimal for all S ((8) (Cutkosky et al. 2203) result that holds even for smooth functions, let alone their superclass of weakly convex functions.
Remark 3. Notably, the weak convexity parameter p does not appear in the dominant rate term, but instead in suboptimal term p² 62 which allows it to scale up to O(5-1(-1) without dominating the optimal rate. In other words, as higher convergence precision required, our algorithm can tolerate a larger weak convexity parameter while preserving the optimal complexity rate.
Remark 4. The hyperparameter choices specified in Corollary [ are uniquely determined by the iteration budget N and and the target stationarity precisions d, which typically be user- specified in practical applications. For example, setting 5 = c ONN-1/4) Corollary _ yields = O(N1/2) K = 7 O = 1)
and D = (N-3)
3.3 RESULTS FOR D-O2NC UNDER PERIODICALLY RESTARTED OGD
While Algorithm 2 with Option-I achieves optimal dimension-fres iteration complexity, the clipped OGD iteration restricts the increments An to lie within sufficiently small ball constraint that may be overly conservative. To address this limitation, we further propose a novel periodically restarted OGD procedure (Option-II) for the OCO module of our algorithm. Specifically, for each time step n 2 1, we update A,+1 (1 777),, - 7/n; and reset A,+1 = whenever mod (n + 1,7) = 1. This unconstrained OGD procedure allows for more progressive updates, particularly when iterates are far from stationarity.
Remark 5. Regarding the design of the OCO module, Algorithm 2 with Option-II aligns with E- O2NC Zhang & Cutkosky 2024) in spirit, as the latter instantiates its OCO module with an un- constrained OMD procedure. Despite this similarity, our algorithm differs from E-O2NC in two key respects: (1) ours is deterministic and eliminates the need for random scaling of increments; (2) our algorithm avoids both exponential weighting of subgradients in loss construction and exponen- tial moving average (EMA) of iterates for oulput generation-mute makinng it more amenable to practical implementation.
Remark 6. is worth highlighting that the proposed periodically restarted OGD procedure can be readily extended to the original O2NC framework for general non-smooth, non-convex optimization under the bell-behavedness assumption (Cutkosky et al. 2023). This holds because, under this assumption, quadratic loss functions of the form (9n. ) -11 (with arbitrary y > 0) can similarly be constructed for O2NC (or F-O2NC).
Recovering SGDM. A notable consequence of adopting the periodically restarted OGD procedure is that we can explicitly rewrite the update rule for Algorithm (PtiionII) as
Wn Wn-1 - 7 1 mn;
mn+1 ((1 B)mm (3.)) 1 mod (x+1,T))
where m, := An 3 := ny,, and 1(.) denotes the indicator function. The above update rule is nearly identical to standard SGDM, with the only distinction being that the update of the search

---

Published as a conference paper at ICLR 2026
direction m, is reset zero after every T rounds of iteration. A similar connection to SGDM was also established for the E-O2NC method (Zhang & Cutkosky 2024), albeit under more sophisticated algorithmic designs (see Remark 5 for further discussion).
Complexity guarantees. The following is our main result on the convergence rate of Algorithm with periodically restarted OGD (Option-II). A proof of this result is provided in Appendix B.4
Theorem 2. Suppose that Assumption and Assumption hold. Let 2 be an arbitrary scalar, " S Byy K,T be positive integers, and D be an arbitrary positive number. Then any μ S 8DT2 R==1 generated by Algorithm
the sequence {wok))
2 with Option-Il satisfies
E
( |
K
K
S
G D
D
D 7
G VT
ARo DKT
Remark Unlike in Theorem 7 where serves as a hyperparameter in Option-I, the scalar D in Theorem does not appear in Option-II: it is introduced solely for analytical purposes.
Building on Theorem 2 we further establish the following result regarding the complexity of Algo- rithm 2 (Option II) for finding (μ, reggularie stationary points. See Appendix B.5 for its proof.
Corollary 2. Suppose that Assumption 7 and Assumption hold. Let μ.c. > denote the target regularized stationarity parameters and N be the total iteration budget. We set
T= N4/T p 2/7 -2/7
==
N
7= NN/T
7 8N
T
Suppose further that
(4G2 32 + 1)7/2
7/3
N
12/3 + 4 122
e//2
Then the output wh of Algorithm 2 with Option-II satisfies
E
[[@R((@))l++)) S.
Remark 8. By virtue of Lemmal
2 setting = 8-2e yields that the bound in Corollary 2 iimlles 2/3 6 + ( ) for producing (8, -tsttttionnrry points, which
complexity O (8-1c- + 1²13 ///
is dominated by the optimal term 8-1,-3 Consistent with the discussion in Remark 3 the weak convexity parameter p can scale up to (22222-331 without dominating the optimal component.
3.4 COMPARISON WITH PRIOR RESULTT
we summarize the complexity bounds and key properties of D-O2NC, and compare them to those of several other subgradient- based methods for weakly convex optimization, including SGD (Davis& & Drusvyatskiy 2019) SGDM (Mai & Johansson, 2020) and Interpolated Normalized Gradient Descent (INGD) (Davis et al.) 2022). ) We make the following key observations:
In Table I
Comparison with INGD. Our D-O2NC is deterministic (up to the use of stochastic oracles) and achieves dimension- free, optimal complexity with respect to (8, e In contrast, INGD is randomized by design and difficult to extend to the stochastic setting; additionally, its corresponding complexity bound is dimension-den -eeeeddnn,,,eddeen,, though it exhibits sharper depen- dence on and (ő, e)
Comparison with SGD and SGDM. The reported optimal complexity of O(c-t) for SGD and SGDM corresponds to the e-stationarity of Moreau envelope, i.e., R S e with p = (p). While our optimal bounds are not directly comparable to this complexity due the distinct criteria employed, we highlight the following key observations: 1) Leemma[establiises establisses that an e-stationary point of the Moreau envelope implies a (t/((p),.)-ssatiionn)) point of the original objective (see Remark [ in Appendix D for details); accordingly, the bounds for SGD and SGDM imply an O 'e complexity for finding (6, e)-staiionary points, albeit under the relatively restrictive choice = =<((pp); 2) As shown in Theorem (Appendix D). (8, e)-
stationary point implies (e vō) V8)-stationary point of the Moreau envelope, which however
8

---

Published as a conference paper at ICLR 2026
yields suboptimal complexity of 0(e-5) ) for achieving e-stationarity (Corollary 3: 3) For second-order smooth functions, building on the result of Cutkkosyy et al. 2002) Proposition 15) it can be readily shown that D-O2NC recovers the optimal O(e 5.0) complexity for finding e-stationary point, which however cannot be automatically implied by the tabulated results for SGD/SGDM. Finally, the weak convexity parameter can scale up 0 in our bounds without dominating the optimal rate, a feature not shared by those of SGD and SGDM.
c-stationarity (Moreau envelope)
Method
(6, -stationnay
DET SO
SGD
Davis & Drusvyatskiy 2019)
SGDM
O
/
/
MMai & Johansson 2020
INGD
O
d log(p)) de
x
x
Davis et al.
2022
D-O2NC with Option-I (ours)
O
p²88 8
51)
/
/
1//384/3
D-O2NC with Option-II (ours)
4e3
+
Table 1: Comparison of subgradient- based methods for weakly convex optimization with respect to complexity bounds, determinism (DET), and applicability to stochastic oracle (SO). The notation used include convergence precisions (6, e), weak convexity parameter p, and model dimension d.
4 EXPERIMENTS
In this section, we present a preliminary experimental study on the effectiveness of D-O2NC (con- figured with the periodically restarted OGI) optimizer, Option-II) for training deep neural networks. Given that our algorithm corresponds to a momentun-restarted variant SGDM, we adopt standard SGDM as the baseline for comparison. Additional experimental results are provided in Appendix
4.1 EXPERIMENT SETUP
Dataset and backbone networks. Our experiments are conducted on the CIFAR-10 10 image classifi- cation benchmark Krizhevsky & Hinton (2009) popularly used for evaluating deep learning models and algorithms. This dataset comprises 60,000 color images across 10 classes, with 50,000 images designated for training and 10,000 for testing. We adopt ResNet-101 (He et al. 2016) and Vision Transformer (VTT) (Dosovitskiy al. 2021) backbone networks for representation learning, with GeLU (Hendrycks & Gimpel| 2016) used as the activation function for both architectures. Notably, neural networks with smooth activation functions (e.g.. GeLU, softplus) typically match or outperform their ReLU-based non-smooth counterparts (Clevert et al. 2016 Xu et al., 2015).
Implementation details and performance metries. For all considered algorithms, model parame- ters are optimized for 400 epochs with a mini-batch size of 256 for ResNet- and for 600 epochs (same mini-batch size) for WiT-where a patch size of 4 is used for the latter. The total number of bani-batches per epoch is 196. The initial learning rate is set to 0.01 and decayed via cosine an- nealing to enable smoother convergence. The optimizer employs a momentum of 0.99 and a weight decay of 5 x 14 Our periodically restarted O2NC method is implemented and evaluated under two distinct restart frequencies: T {20, 50). For each experiment, we carried out three inde- pendent runs with distinct random seeds, recording the empirical loss and training accuracy during training, as well as the test set prediction accuracy.
4.2 RESULTS
Figure shows the convergence curves of the considered algorithms. Results for the optimal iterate of each trial are reported in Table These results show that D-O2NC converges significantly faster than SGDM both models: average, D-O2NC outperforms SGDM in test accuracy by 0.9

---

Published as a conference paper at ICLR 2026
(a) Train Loss (RssNet-101)
(b) Train Accuracy (ResNet-101
(c) Test Accuracy (ResNet-101)
DOGI
Dopll:
Do00:
(d) Train Loss (VIT)
(e) Train Accuracy (ViT)
(f) Test Accuracy (ViT)
Figure 1: Experimental results on CIFAR-10 with ResNet-101 (top) and VIT (bottom) networks.
percentage points for ResNet-101 and 1.96 percentage points for VIT. These findings confirm that the momentum restart mechanism in our method not only accelerates convergence but also yields superior generalization performance.
Table 2: Numerical results of the optimal iterate per trial on CIFAR-10.
D-O2NC
D-O2NC
Backbone
Metric
SGDM
= 20)
50)
Train Loss (x10-3)
2.55 + 0.08
0.55 + 0.02
1.38 + 0.01
ResNet-101
Train Accuracy (%)
99.98 + 0.0
100 0.0
100 0.0
Test Accuracy (%)
93.91 + 0.55
94.64 + 0.07
94.81 + 0.34
Train Loss (x 1
2.78 # 0.10
2.12
2.44 0.10
VIT
Train Accuracy (%)
90.16 0.51
92.38 + 0.28
91.36 0.22
Test Accuracy (%)
84.26 + 0.41
84.92 + 0.17
86.22 + 0.29
To validate the hyperparameter sensitivity of our method, we conduct additional experiments across diverse configurations of restart frequency, learning rate, and momentum coefficient (see Ap- pendix for detailed results). These results demonstrate that D-O2NC consistently outperforms SGDM under identical hyperparameter configurations.
5 CONCLUSION
In this paper, we make progress towards resolving critical issue regarding the link between O2NC (omline-to-non--oovver conversion) and SGDM: under auxiliary random interpolation or scaling. O2NC mirrors SGDM, but such randomization induces deviations from standard SGDM. To this end, for broad class of weakly convex functions, we introduce D-O2NC as derandomized ver- sion of O2NC that maintains the optimal oracle complexity a deterministic manner. Our method allows the weak convexity parameter to scale up (6-11-11) without dominating the optimal rate, meaning that stronger stationarity enables tolerating higher non-convexity. Furthermore, we develop a periodically restarted variant of D-O2NC, which facili- tates more progressive updates when far from stationarity. Corresponding to momentum-restant SGDM method, this variant has been empirically shown to be effective for training ResNet and ViT models benchmark datasets. An interesting direction for future work is to extend our periodi- cally restarted O2NC technique to the analysis and improvement of other popular machine learning optimizers, including Adam and schedule-free SGD.
"E-3 while recovering SGDM in
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the Natural Science Foundation of China (NSFC) under Grant No. U21B2049, the Special Fund for Key Program of Science and Technology of Jiangsu Province under Grant No. BG2024042, the Gusu Leading Talents Program for Innovation and Entrepreneurship under Grant No. ZXL2025323, and the CCF-Ant Research Fund (Ant Group) under Grant No. 20240512. We would like to thank the ICLR reviewers for their valuable feedback and suggestions.
DECLARATION OF LARGE LANGUAGE MODELS (LLMs) USAGE
We acknowledge the use of Doubao 1.6 (ByteDance, 2025) as an auxiliary LLM tool solely for polishing this manuscript, including refining English grammar and improving the readability of non-core descriptive content. All outputs from Doubao were thoroughly reviewed, revised, and val- idated by the authors ensure accuracy, consistency with the research context, and alignment with academic standard. Doubao did not participate in idea formalization, theoretical derivation, result analysis, or drafting of core sections (Abstract, Introduction, Method, Experiment). All authors bear full responsibility for the manuscript's content integrity and scientific validity.
REFERENCES
Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp- 94909-94999 94933, 2024.
Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding Adam optimizer via online learning updates: Adam is FTRL in disguise. International Conference on Machine Learning (ICML), pp. 619-640, 2024.
Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky. General framework for online-to- nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization. In Inter- national Conference on Machine Learning (ICML), pp. 772-795, 2025.
Hilal Asi and John C Duchi. Stochastic (approximate) proximal point methods: Convergence, opti- mality, and adaptivity. SIAM Journal on Optimization, 29(3):257 2019.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-775, 2003.
Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1))322-344) 2005.
Axel Böhm and Stephen J Wright. Variable smoothing for weakly convex composite functions. Journal of Ooptimization Theory and Applications, 188:628-666 649, 2021.
Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation,
stochastic gradient methods and deep learning. Mathematical Programming, (88(1):19-51, 2021.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357 2015.
Nicolo
Alessandro Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions Information Theory, 5009):000--2055 2004.
Frank H Clarke, Generalized gradients and applications. Trunsactions of the American Mathemati- cal Society, 205:247-262. 1975.
Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
Djórk-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (clus). In International Conference on Learning Representa- fions (ICL.), 2016.
11

---

Published as a conference paper at ICLR 2026
Ashok Cutkosky and Francesco Orabona. Momentum- variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems (NeurIPS), pp. 12236-1524,, 2019.
Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-conver conversion. In International Conference Machine Learning (ICML), pp. 6643-6670, 2023.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233) 2019.
Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nons- mooth, nonconvex problems. SIAM Journal on Optimization, 19(3):1908-199 2019.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges tame functions. Foundations of Computational Mathematics, 20(1):119- 154, 2020.
Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye, A gra- dient sampling method with complexity guarantees for lipschitz functions in high and low di- mensions. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6692-6703, 2022.
Aaron Defazio, Xingyu Yang, Ahmed Khaled, Konstantin Mishchenko, Harsh Mehta, and Ashok Cutkosky. The road less scheduled. In Advances in Neural Information Processing Systems (NeurIPS), pp. 9974-10007, 2024.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition scale. In International Confer- ence on Learning Representations (ICLR), 2021.
D Drusvyatskiy and C Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming. 178(1-2):503-555)) 2019.
John C Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, 28(4):3229-3259, 2018.
Yu M Ermol'e ev and VI Norkin. Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization. Cybernetics and Systems Analysis, 34(2):196-215, 1998.
Allen Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13 (1):14-22, 1977.
Geoffrey J Gordon. Regret bounds for prediction problems. In Annual Conference on Computational Learning Theory (COLT), pp. 29-40. 1999.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). arXiv preprint 1606:06606.08411 2016.
Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. Deterministic nonsmooth nonconvex optimization. In Annual Conference on Learning Theory (COLT), pp- 4570-4597, 2023.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Siyu Kong and Adrian Lewis. Lipschitz minimization and the goldstein modulus. Mathematical Programming, pp. 1-30, 2025.
Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Jour- nal of Machine Learning Research, 23:1-43, 2022.
12

---

Published as a conference paper at ICLR 2026
Guy Kornowki and Ohad Shamir. An algorithm with optimal dimension-deeendemne for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122): 1-14, 2024.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Vien Mai and Mikael Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. In International Conference on Machine Learning (ICML), pp. 6630-6639, 2020.
Yurii Nesterov. Lectures on convex optimization, Springer, 2018.
Evgeni Alekseevich Nurminskii. The quasigradient method for the solving of the nonlinear pro- gramming problems. Cybernetics, 9()):145-150, 1973.
Spyridon Pougkakiotis and Dionysios S Kalogerias. A zeroth-order proximal stochastic gradient method for weakly convex stochastic optimization. SIAM Journal on Scientific Computing, 45 (5):2679-2702, 2023.
Tyrrell Rockafellar. Convex analysis. Princeton university press, 1997.
Jan A Snyman. Practical mathematical optimizaaion: an introduction to basic optimization theory and classical and gradient-based algorithms. Springer, 2005.
Ilya Sutskever, James Martens, George E Dahl, and Geoffrey E Hinton. On the importance of
initialization and momentum in deep learning. In International Conference on Machine Learning (ICML). pp. 1139-1147, 2013.
Lai Tian and Anthony Man-Cho So. No dimension-free free deterministic algorithm computes approxi- mate stationarities of lipschitzians. Mathematical Programming, 208(1):51-74, 2024.
Wim van Ackooij, Felipe Atenas, and Claudia Sagastizábal. Weak convexity and approximate sub- differentials. Journal of Optimization Theory and Applications, 203(2):1686-100) 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Infor- mation Processing Systems (NeurIPS), 2017.
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv:1505.00853 2015.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference Machine Learning (ICML), pp. 11173-11182, 2020.
Qinzi Zhang and Ashok Cutkosky. Random scaling and momentum for non-smooth non-convex optimization. International Conference on Machine Learning (ICMI), pp. 58780 58799, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
International Conference on Machine Learning (ICML), pp. 928-936, 2003.
13

---

Published as a conference paper at ICLR 2026
A PROOFS IN SECTION 2
A.1 PROOF OF LEMMA 2
We prove the following restated lemma, which establishes the equivalence between (p, E)- regularized stationarity and Goldstein (6, -)-stationnaity.
Lemma 2. Let ó, 0, > 0 be arbitrary positive values. Consider Lipschitz function f.
(a) w is a (ô, --stttiionryy point, then also (e). stationary point.
(b) If w is a (n, rregularize stationary point, then it is also a (V // -Stationary point.
Proof. Part(a): Let be Goldstein (6, -ttttiionnryy point of and set μt jz- By the definition of the p-regularized subdifferential norm given in equation 2 we have
[[0[()]ll++ Sdist(O, OB((w)s) + μ sup
||U - w|l
oEB,(w)
_dist(0, fzf(w)) + sup VER
||0 w|
26 = 2e,
where the second inequality uses the definition of Goldstein (6, e)-stationarity. It then follows from Definition 2 that is a (g= reggllaulrd stationary point of f.
Part(b): We now consider the case where w is (H, rrregulariie stationary point of f. Let 6 = E
and let > 0 be arbitrary. Since [af(w)ll+ I c, Definition ensures that there exists set V (c)
such that
z [|0S(w)]l+ 2 dist(0,@vv-e) 0v- +
sup (E)
-| w|l2 -
which immediately yields
sup 1 wil S EEE -eV
- V
C
E =
dist(0, (c) S
S
V P
V
The second inequality above implies that (=) C BB+ / ( therefore obtain
(w) and hence ()-( S Og Po-v=St We
dist (0.0o+ dist (0, dv-(())) sete.
Since > 0 can be chosen arbitrarily small and 8 = Vh. it follows that w is Goldstein (Vi.e).
stationary point. The proof is completed.
A.2 PROOF OF LEMMA 3
Here we prove the following restated lemma on the monotonicity [la II+p with respect to p. function.
Lemma 3. Let be a Lipschitefunntion. Then for any E Rdd and 0 P4 I p2 holds that [0f(w))l+m & (10
Proof. Fix a vector w and let e > 0 be arbitrary. By definition, there exists a subset (e)(s) C Rd such that [[0f(w)) 2 dist(0, (e) f)+ #2 suprevz(e) w -s. Using the definition again together with the condition μl $ μ2, we obtain
[[0(ww)]+ <dist(0, Ovz(e)))) pn sup ||u w| w||2 (EV
<dist(0, Ov + p22 (EV
sup
||u- w||
<110f(w)]l +E.
Since E > 0 can be chosen arbitrarily small, it follows that [0f( tp $ (10f(w))l+ps The proof completed.
14

---

Published as a conference paper at ICLR 2026
B PROOFS IN SECTION
B.1 SOME KEY LEMMAS
The following lemma is crucial for analyzing Algorithm
Lemma 4, Suppose that Assumptions 7 and Assumption 2 hold. Let y 2 p and D > 0 be arbitrary
(k) (K)TT numbers, and let S .q. Then for any k E [K], the sequence {w; Ji=1 generated by Algorithm satisfies
E R(w4)) R(mb)) (+))
Σ 1 12
+nG DGVT (1T+ 1 D
(4) ||
s E E DT g
17
7
Proof. Let consider the filtration Fi of Ag.... A441). where of denotes the generated
o-field. For any n 2 1, it follows from Assumption that 9n == E(g. Fn-1l E @R(w,). For any y p. the weak convexity condition in Assumption T iimplies that for all n 2
R(w,) R(wn-1) & (gm, An) + 3 111..112 = E (0ns A.) + 2 | Fa-1
By the law of total expectation,
E [R(ww)- - R(wn-11) < (bn, An) + 311 ||.1
Fix an arbitrary is E [K]. Recall that w 1) [T] and we use analogous notation for (A) (K) (k)
A 91 9t
Then the preceding inequality yields that for any ( [T]:
E
[(w (K) R(w((1)
E
A
(8)) + - (3) [P]
Summing the above bound over I,..., T yields
E A(w (1) R(ux(t))
(3)
R(w(()) H(u(1i) =E Σ
<
Σ
Lot
(k)
(0) + 2 (0/0011p]) (p))
214
We next upper-bound the right-hand side (RHS) the above inequality using the OGD regret bound provided in Lemma 6 To this end, observe that the sequence {A (k) TT generated by Algorithm corresponds the iterates produced by OGD initialized at A 1 with step-size r,, applied to the
(8)
sequence of quadratic losses {.f! (R) hE([)] over the constraint B p (0) (for Option-I) or over the full space Rd (for Option-II), where
1
(0( 31 112
+))+
For any D> > 0, we define the following comparator:
T (k)
A (k)
D
9t
1 D1
15

---

Published as a conference paper at ICLR 2026
Denote g(h)
+ Et= Dt
(k)
and (((h) + Ei= g6 Since 17 S 87.
apply Lemma
6 and
obtain
) + 2 [p]
E
(K)
T
r
((o ( A + 2 (1 +
?114
<E
2
1
(I4 (K) 112 + 13(0113)
17
T
T
-E
(k) (1)) ).(()) (b) )
+
Σ 9r
A (8)
1=1
(nlibe (0) 1|2 + > 11 - 2 |4 (1)
+ _ (14(")++13<(0))))) 113)
S
DT
g(k)
gihi|
-DT DT |
Σ
T
\nll! ( 112 DD² -114
+
D
|| (K) ||2
17
T + Σ [=1
+ GGG + DGVT + (1T= D² +
1 17
| (0)
|?
1 E
DT
g(k)
| (1)
1|2
where in step "(1" " we used Cauchy-Schwarz inequality together with the fact that | (k) || S
D holds for both Option-I and Option-ll, and in step "G2" we used the bound 19]
(k) || S G
from Assumption as well as the inequality E [|| - g(*il| I
v B - =
T Σ R Elggt (2)
o. 12 <
S G Substituting the above inequality
VT
into equation 3 and rearranging terms yields the desired bound, which completes the proof.
The following simple lemma is also useful our analysis. We provide its proof for the sake of completeness.
Lemma 5. Let W1, W2, ... Wn be set of vectors, and let w
E Wi. Then for all i E [n],
|00
w2ll
wy
S In
||
n
1=1
where Dj: = Wi - w and wo can be chosen arbitrarily.
Proof. Fix any i [n]. We have
1
1
Iw,- 2 2
Wy
<
[w
w. 1|
12
71
#=1
(w,-1- - w3y)
x
2
2
AVv'
|لره|
x
Σ ||
In Σ | 11
This completes the proof.
16

---

Published as a conference paper at ICLR 2026
B.2 PROOF OF THEOREM L
Theorem 1. Suppose that Assumption 7 and Assumption 2 hold. Let 7 2 be an arbitrary scalar, " ... K,T be positive integers, and D be an arbitrary positive number. Then for any ô 2 T,, generated by Algorithm the sequence { 1k=1
2 with Option-I satisfies
E
1
Σ
dist(O, a5 Rs
I
n
7T
2
D
G
ARo DKT
K
D
17
T
VT
Proof. Under the given conditions, for any k [K], invoke Lemma 4 Option-I) to get
on Algorithm 2 (with
r'
E R(wf")
R(ug)) ( +
Σ | 10 12
(TT+ D2 | 11
s DT
9 g/51
+ +n + DGVT+
S DT
g (8)
+ + DGVT+
7T D?
where the last step uses the fact that (1) < D, which follows from the explicit constraint im- posed in Option-I. Note that by definition, WT = wo term on the LHS of the above inequality, we get
(k+1)
Omitting the non-negative summation
E ( (w)))) f E DT
[
+ DGVT (NT+ 2) 2) D 19
Rearranging the terms on both sides of the above inequality yields
|| G DGVT + (TT+ + ?> D2 [(w(())) R(wn(+t))))
E DT
7)
By summing the above inequality over k E [K] we get
K
K KD2 + Σ R(w!")) Rlww ((((t))))
DT
|
S DGKVT
+ 2
KT + DGKVT+
(TT+ 2
KD2 + [R(wo] (2) R(wo (
KT + DGKVT
(T KD2 + R(wo) R²
Dividing both sides of the above inequality by DKT yields
||
G
2
D T
G AR
E
<
(T
(4)
K
D
DKT
Since | < D almost surely for all / [T], applying Lemma 5
giiees
(k)
(T()
<
(k)
STD VE V [2),
which implies
dist (o. (1(())
1
Σ
(K)
T
9
Combining the above with equation
we obtain
Σ dist (0, 0g R(ml))))))
K
s 112
2 7
D
G
ARo
E
7T
+
K
T
VT
DKT
This completes the proof.
17

---

Published as a conference paper at ICLR 2026
B.3 PROOF OF COROLLARY 1
Corollary 1. Suppose that Assumption 7 and Assumplion 2 hold. Let 6. >> 0 denote the targtt Goldstein stationarity parameters, and N be the total tteration budget. We set
T T= T=[[8N)R/3]
N
N2/3
51/3
K
T
7=
82/3
1J
SN
D
N2/3
Suppose further that
G
G Aoo
17)3
1
888
5c3
Then the output WT by Algorithm
2 with Option-I satisfies
[dist (0, 0 (( )) 6.
Proof. The given choice of the hyperparameters ensures that TD S 6. Under the condition N we can verify that
72P. Y1 8(5N)2/3 8
All conditions of Theorem T are thus satisfied our setting, and applying the theorem yields
(0, (0,0s R(m
dist
K
G22
G ARO
+ (TT+ + // T +
D
VT DKT
G
+1+ +6+ ARd
8
(8N)1/3
< (G G 174 A (6N)1/3 Se,
where the last inequality follows from the condition on N. The desired bound is obtained by noting that Wh ~ Uniform( (t) k [K]]). This completes the proof.
B.4 PROOF OF THEOREM 2
Theorem 2. Suppose that Assumption 7 and Assumption 2 hold. Let 2 p be an arbitrary sealar,
S K,T be positive integers, and D be an arbitrary positive number. Then any μ S 8DT2. 1==1 generated by Algorithm
the sequence {
2 with Option-ll satisfies
E
Σ
K
aR( (6)00) (2)
G22
(TT+
1
D
G
ARo DKT
K
+H
D
T
VT
Proof. Under the given conditions, for any E [K], we can invoke Lemma 4 on Algorithm 2 (with Option-II) to get
E ((wf)) R(w! (k) +
1 10
1=1
|1 12)
< - E DT
+ + DGVT+
7T+-
D2
E DT
, + DGVT+
(TT+ 1
D2
18

---

Published as a conference paper at ICLR 2026
where the last inequality uses the fact that || step in Option-ll of Algorithm Recall that by definition, wi wb (k+1) This implies that
0, which follows from the periodic restarting
E
R(w++t))
R(wb (1))
7
1 1
8 t=1
+ G + DGVT + (1T + D2.
$
E
DT
By applying Lemma] inequality as
we can lower-bound the term Ak)) on the left-hand side (LHS) of the above
A 2
max [T
W
8T
follows that
E R(wn
(
R(w (k)
+ ?
max
(u( =
(k)
8T
EE[T]
-- E
DT
(k)
||
+ n + DGVT+ (IT
2 +
D2.
Rearranging the terms both sides of the above inequality yields
( ||]
E
DT
(k)
+
max LE[T]
ST
STGT + DGVT
TT
1
D + E R(wb R(ub+t1))
2
By summing the above inequality over k E [K]. we get
E
g
(8)
+
max E
w
(k) - w//0/1
87
K
KTGKT + DGKVT +
(T !
KD2 +E
R((u))) (k)) Ri(w ((
k=
=n + DGKVT+
(I + 1
KD2 +E [((w)") R(w! (
(xT+1) 1
KTG DGKVT+ +
KD2 + R(wo) R
Finally, dividing both sides of the above inequality by DKT yields
K
x (')
G
D (1T
1
D
G
ARo
max [E(T]
<
K
8DT
T
VT
DKT
k=1
Since j S n SDT2. by Lemma
we have
(R)
|| +w <
(k) w.
(
<
max :
8DT
Combining the preceding inequalities leads to the desired result. This completes the proof.
B.5 PROOF OF COROLLARY 2
Corollary 2. Suppose that Assumption 7 and Assumption 2 hold. Let μ.c > 0 denote the target
regularized stationarity parameters and N be the total iteration budget. We set
N
T= N4/7 2/7
K
r = N3/7 2//7 " 8N
T
19

---

Published as a conference paper at ICLR 2026
Suppose further that
(4G + 322R Ro + 11)7/2
13/3
N
2
12/3 + 12//2
2/2
Then the output Ty of Algorithm 2 with Option- II satisfies
IR
[10R(
Se.
Proof. Under the condition on N, we can verify that
2 7 72 P. 1n 8/4/7
S
8
We now consider the value
32 1
1/7 N 3-/7 Again the condition on N implies that
T' = N 1 2/7 21. 1.
With the given choices of 7,y, D, it can be readily shown that
8DI772 SD(T++I) 32DT = μ.
8DT
In view of the above arguments, all conditions of Theorem are satisfied in our setting, and we can thus apply the theorem to obtain
E
K
@R( (K)
G2
+ +(1T++
7)
D T
G
ARo
K
4/
D
VT
DKT
1// N2/7
4G2
+ --32 Ro
32
111
S(4G +1+ 32
N2/7 S.
where the last inequality follows from the condition N. The desired bound is obtained by noting that ÖT Uniform( (x)) k E [K]]). This completes the proof.
C ANALYSIS OF ONLINE GRADIENT DESCENT FOR QUADRATIC LOSSES
Consider the quadratic loss functions of the form fx(x) = (u,, + 311 2 1. defined over convex constraint C. We analyze the following standard online gradient descent (OGD) method, which starts from an initial iterate 21 with step-size > O:
E++1 = He [x. fx.))) He [(1 - m7)2z -uu)),
(5)
where 1le denotes the Euclidian projection operator associated with C. Let Regrety (σ) denote the regret of the algorithm with respect to some comparator C after T iterations, defined as follows:
T
Regret, (i) == Σ f((z)) Σ f((z).
1=1
t=1
Based on standard analysis, we can establish the following result regarding the regret bound of the OGD algorithm described above.
Lemma 6. Suppose that 17 S L. Then the OGD procedure 5 applied to (fe) over the corvex constraint set guarantees that for all T 2 and all x C:
Regrety (x)
T
2 ++? [|
2 8
||
+ 7
1 (| + [|=])))
20

---

Published as a conference paper at ICLR 2026
Proof. First, it can be verified that
|0441
=||² |[e (2,, fz))) =1
s || - (. - ø||
=I| =||are - म|| + (++ -177--2nVV 2 fe(1t), xt - x));
which implies
1 I 21+1 - ~11
7 (x)))l
fi()), σ) S
2n
2
Using the strong convexity of Jt, we can then show that
Regrety (z)
f((1))
Σ fx)
T
(eee())). 34 - x) - 1100 - =|
2
100 x1|² - || - =x12
T
17 // f2(x:)11
2112 I1l
+
217
2
2
1
1
T
17 11 + yare?
2 |102 -0112 +
||21 =11²-
|
=1
2n
27
2
1=1
T
x||2
(1|0)
12+ + |
+
n([uelll + 7 112)
||a,/13
T
||
+ (1|2a 112 + || +
7 nlluell + >1
2
1/ 1 +
2
11111
( 1
1/4 - -m) | + (1|a) 11 + ||=))²)
2
(Mllua 2
? 111311
7 31
(11=a 112 + |=
8
where step "Si" uses the fact |la b1l2 ||ا||2 ||b||3 and the last step follows from the condition ry S g.4 This completes the proof.
Remark 9. The main message conveyed by Lemma o is that it is beneficial to control the scales of the competitor I. and the initial iterate 2n to keep the regret small, even when the domain of interest is allowed be unbounded. This result inspires to explicitly control the scale of the initial iterate.
D FROM GOLDSTEIN TO CLARKE STATIONARITY
As a side contribution of our work, we establish in the following theorem a set of results regard- ing the connection between the Goldstein stationarity of weakly convex function and the Clarke stationarity of its Moreau envelope, which we believe are of independent interest. Theorem 3. Let J be a G-Lipschitz and p-weukly convex function.
(a) w is a (8, -sttttiionayyy point of f, then it holds that
/ V (w)l < 3 2
122
+ 4Gpo + 2p282.
(b) w is a (n, rregularrze stationary point of f. then it holds that
22
- + 2p² 4GG
2 (w)) s /3/
+
1
21

---

Published as a conference paper at ICLR 2026
Proof. Part (a): Let w be a (6, -tttationayy point of f. By definition, there exists a subset V S (w) and a set of weights faelvev such that a, 2 0, Evev ar and
Σ
Ougy s
REV
where Io E (v) For any w', consider a subgradient o' E @f((w'.. Since I is p-weakly convex, we can show that
f(w') = Σ a.f("")
EV
2 Σ
(f(u) + (9v. w² -0) P 2'lw' - 2113)
2
NEV
=f(w)+ +
Σ
Ore w' -w
+ Σ av (F(e) - f(w) + (9v. -0) -
Ilu'' --1lu' w + w e1(2)
DEV
NEV
2f(w)+ +
avlos w w pllwo
w|
Σ ae (f(v) f(w) + (gv, w o) -pllu 0113)
WEV
VEV
S((w)
1
2pllwd
w|l2 Σ av (2Gl|u w|ll p||w - w)13)
4p
E)(w) 2pllwo - w/l2
2
2GB
po²
4p
6²
2f(w') + "g',0 w - -w') w| w 212
2pllw' - wll2
2GB
p82
4p
=f(w') + (g', w - w²) 5p u w1
2 4p
2G8 po²
where step "(1" " uses the Cauchy-Schwarre Schwarz inequality, step "C2" " uses the Cauchy-Schwarz Schwarz inequality and the G-Lipschitz continuity of J, step "C3" uses the fact that V C BB(w) and equation [ and the last inequality uses the p- p-weak convexity of f. We now consider úē = prox f/o(w) for some p > 5g which by Lemma satisfies satisfiss
2
Viya(w)) = p(w w) E @f
Subsisting w' ② into the preceding inequality and rearranging the terms yields
3p)
5p
2
|| + < p
2G5 po²
4p
It follows from the above inequality that
5p
11/
(22
1/2
[ = |1 - اللl S p
+ +G8 + pD²)
4p
Finally, setting ` 3p in the above expression and performing some minor algebraic manipula- tions yields the desired bound in Part (a). The bound in Part (b) follows directly from Part (a) and Lemma 2 This completes the proof.
Remark 10. Theorem essentially shows that the (6, c)stttiionayy of weakly convex function implies the (e+ -ttttiooorn of its Moreau envelope, and correspondingly the (H, regglarizzd stationary implies the (c+ / -stationarity.
Remark 11. Conversely, for p-weakly convex function f, the translation from the Clarke sta- tionarity of its Moreau envelope to the Goldstein stationarity of the original objective is relatively straightforward. Indeed, suppose that w is an e-stationary point the Moreau envelope fi/(20) such that V f1/em) S Consider v : p (w). Then according Lemma 7 we have
| [1 5 2p'
Viie E Of(w), ||w wll S
2p
22

---

Published as a conference paper at ICLR 2026
which implies dist (0,0gf(w) & [V I e, and thus w is a (6, -tationaayy poins of f with 2p However, limitation of translating rates via the setting = (2p)) is that it excludes the range of relatively large (e.g. = Ve. choice critical for sharper rates in second-order smooth finctions), as p is rypically lower bounded by constant.
The following corollary is direct consequence of Theorem when applied to Algorithm 2 with Option-I.
Corollary 3. Suppose that Assumption ! and Assumption 2 hold. Let c 0 be the desired station- arity precision, and let N be the total budget of ileration. Set
N
N1/3
2/3 N2/3*
T T=
=
T
?
4/3
1= 8N
Suppose further that
N + Aoo + 17)3
+ tpp 2
Then the oulput WT of Algorithm 2 with Option-I satisfies
V (wr(s) 50 + =
E
Proof. Let = 2 and E(,, Wr) == dist (0, 0g R(WT)). Under the given conditions, it follows from
Corollary that
[=( wr]] = [dist (0, (gR((uT)) ))1 S E.
Conditioned Wr, it is straightforward to that ür is (6, ( wT)) (tr))stttionnary point of R. Therefore, from Part (a) of Theorem we have
3v2 <0 WT) 4Gp8 + 2p228
V (3p)) [T)||| s 3v
268, WT) 6v Gpõ + 3v2
2
2
Taking expectation on both sides of the above inequality yields
3v2 (6, ΦT) + G 3v 2pó
E / (WT)) ||| SE
3 <
E + Gp + 3V2pe²
2
where the last step uses equation 7 and 5 =². This completes the proof.
Remark 12. The ( complexity established in Corollary is suboptimal compared to the
optimal O)e=A) complexity SGD (Davis & Grimmer 2019 and SGDM (Mai & JJhansson 2020 for achieving the c-stationarity of the Moreau envelope. Such a slower rate is mainly attributed to the V8 component appearing in the bound of Theorem for improvement in future work.
Part (a)). which remains an open problem
Similarly, by applying Theorem 3 to Algorithm 2 with Option-II, we obtain the following corollary.
Corollary 4. Suppose that Assumption 7 and Assumption 2 hold. Let e >> 0 be the desired station- arity precision, and let N be the total budget of ieeration. Set
T N4/7.0/7
6/7
K
N
T
N3/7
6/7
17
8N
1
Suppose further that
N
(4G² +1+32AR))77
+pT 713
1
3/2
Then the output wr of Algorithm with Option III satisfies
E
[i/(30) (wT) < >Io=>>//><<<ee
(vGpe pe?)
23

---

Published as a conference paper at ICLR 2026
and is included here for completeness. Let J = 3 and E(p, wr) = [[a((w)) )l++) Under the stated assumptions, follows from Corollary
Proof. The proof follows similarly to that of Corollary and
that
E ( wr)] = E [[@R((T)]]++)) S.
Conditioned on ar, it straightforward to see that Dr is a (6, =(6, (rr) point of R. Accordingly, by Part (b) of Theorem 3
we obtain
E² (2 ΦT)
3v2 + 4GGP + +2p² < E(, WT) wT)+ GPV 1
v VR (1/p (WT) & 3/
+33
P 2
Taking expectation on both sides of the above inequality yields
3 E E(4, uT) 6 GPV
c
E
(TT) <
3v
3v2
2 c G Gpe + 3322pt
where the last inequality uses equation 8 and the choice μ -3. This establishes the desired bound.
E ADDITIONAL EXPERIMENTAL RESULTS
In this appendix, we present additional experimental results on neural networks (Appendix E.I] and robust phase retrieval (Appendix E.2 further validate the effectiveness and efficiency of our D-O2NC method equipped with periodically restarted OGD.
E.1 EXPERIMENTS ON NEURAL NETWORKS
Additional descriptions of backbone networks. We employ the ResNet- and VIT models evaluate our method. ResNet-101 is a representative deep architecture in the ResNet family, consisting of 101 layers constructed by stacking residual blocks, each formed by Ix1, 3x3, and Ix] convolutional layers. is widely used backbone in various downstream computer vision tasks, such as object detection and image segmentation. In our experiments, the employed VIT contains Transformer encoder layers, each with multi-head self-attention heads and a 512-dimensional multilayer perceptron (MLP). The dropout rate is set to 0.1, and the input is divided into 4 patches. Both networks are trained from scratch.
Results under various restarting frequency. In our experiments on the CIFAR-10 dataset, we set the restarting frequency T to the range (2, 20, 50, 196), and the total number of minibatches one epoch is 196. Consistent with the parameter settings in the main paper, use learning rate of 0.01 and momentum of 0.99. As shown in Figure 2 the results demonstrate that, in most cases, the model performance first improves gradually with increasing T and then degrades. Notably, extreme values of T (c.g.. T = 2) lead to degraded performance. Thus, choosing an appropriate restarting interval 7' is crucial for achieving optimal model performance.
24

---

Published as a conference paper at ICLR 2026
12
(a) Train Loss (ResNet-100 101)
(b) Train Accuracy (ResNet-101
(c) Test Accuracy (ResNet-101)
DC20012
(d) Train Loss (VIT)
(e) Train Accuracy (ViT)
(f) Test Accuracy (VIT)
Figure 2:
Experimental results on CIFAR-10 with ResNet-101 (top) and VIT (bottom) networks
under various restarting frequencies T.
Teda Acanane
The Accaan
1200012
(a) Train Loss (ResNet-100) 101)
(b) Train Accuracy (ResNct-101)
(c) Test Accuracy (ResNct-101)
Insta Aeomace
Dope: 2
(d) Train Loss (ResNet-101)
(e) Train Accuracy (ResNet-101) (f) Test Accuracy (ResNet-101))
Experimental results on CIFAR-10 with ResNet-101 under relaxed momentum and learn- ing rate settings. The top corresponds to momentum coefficient of 0.95 and learning rate of 0.05, while the bottom row corresponds to a momentum coefficient of 0.9 and learning rate of 0.1.
Figure 3:
Results under various momentum and learning rate configurations. For the experiments re- ported in the main paper, we used momentum coefficient of 0.99 and a learning rate of 0.01. In this section, we further present results under two additional parameter settings: (0.95, 0.05) and (0.9, 0.1). As shown in Figure 3 our method consistently achieves substantial advantages in both convergence speed and prediction accuracy. Moreover, it can be observed that the performance gain of our method gradually diminishes as T increases under these hyperparameter settings.
Results on CIFAR-100. Finally, in addition to CIFAR-10, we also evaluate our algorithm on the CIFAR-100 dataset. CIFAR-100 is an advanced counterpart of CIFAR- 10, comprising 60,000 32x32 color images. In contrast to the 10 coarse classes in CIFAR-10. CIFAR-100 contains 100 fine-grained categories. For this fine- tnn-grained recognition task, we use ResNet- 152 as the backbone network, which possesses deeper network structure compared to ResNet-101. The optimizer is set
25

---

Published as a conference paper at ICLR 2026
with learning rate of 0.01, momentum of 0.99, and weight decay of 5 10-4. The experimen- tal results are shown in Figure from which we observe that: 1) Our D-O2NC method converges faster than standard SGDM in terms of both training loss and accuracy; and 2) Our D-O2NC method achieves higher test accuracy than SGDM, further verifying the effectiveness and superior general- ization ability of our algorithm.
This Acceracy
1op-1 Acceruo
SCOM
SCON D-0GND
D-002C 3T
Epech
Spech
Spech
(a) Train Loss
(b) Train Accuracy
(c) Test Accuracy
Figure 4: Experimental results on CIFAR-100 with ResNet- 152 network.
SCDM
D-02NG 0.7348
Objective Value
Suboptimality
18
Iertiion
Iteration
(b) 10
Figure 5: Experimental results on robust phase retrieval for two different condition numbers s.
E.2 EXPERIMENTS ON ROBUST PHASE RETRIEVAL
To further validate the effectiveness our D-O2NC method for weakly convex problems, we con-
duct an additional set of experiments on the robust phase retrieval task (Duchi & Ruan 2018). Given a set of m measurement -mmplittt-- pairs {æ,, y 1= robust phase retrieval is typically formulated as the following composite minimization problem:
L(w) Σ 1=1
where denotes the unknown signal to be recovered, are the measurement vectors, and yı are the observed squared amplitude values. This loss function measures the discrepancy between the
predicted squared inner-product magnitudes and the observed measurements. Clearly, it is of composition form c, where h(u) |u] Lipschitz continuous and c(w) (w 2x)² ys is smooth. Thus, the loss function is weakly convex.
Following the related experimental setup of Mai Johansson 2020), we generate measurement matrix of size 300 x 100 as X QP, where P is diagonal matrix with condition number x E {1, 103, and Q consists of i.i.d. entries. The observation noise follows (0, 25) and corrupts 20% of the data points. Both SGDM and D-O2NC use momentum coefficient of 0.92 and learning rate of 2 x 10 10-4, with a total of 10,000 iterations. Figure 5 plots the sub-optimality gap against the number of iterations for both values of k. From these results, observe that for both condition numbers, our method achieves performance comparable to SGDM under the same learning rate and momentum.
26


Reviews:
[{"review_id": "Z0K40Uop3w", "reviewer": "Reviewer_11DY", "summary": "This paper proposes a derandomized version of the Online-to-Non-Convex Conversion (O2NC) framework for stochastic weakly convex optimization. Two options are given, one is clipped SGDM, and the other is restarted SGDM. The derandomization part is novel but the the weakly convexity condition seems to be strong for this problem class.", "questions": "1. Is weak convexity necessary for achieving optimal rates with deterministic algorithms? \n2. Can you elaborate the hyperparameter tuning of the experiment section? Is it possible that SGDM converges slower due to suboptimal hyper-parameters?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a deterministic framework that achieves the optimal complexity, showing that this is doable for weakly convex functions even not doable for general non-convex non-smooth functions.\n2. Weaker convexity is allowable when the desired error is small.", "weaknesses": "1.  It's not clear under the weakly convex condition, what's the technical challenges addressed in this work. \n2. Lack of examples of weakly convex functions and related numerical experiments. It would be very helpful if there are some simple function constructions to understand these bounds.", "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": "LSKS3CSSch", "reviewer": "Reviewer_FDFs", "summary": "This paper provides an algorithm for finding Goldstein stationary points of weakly convex functions using the \"online-to-non-convex\" framework.\nThe resulting algorithm does not require randomization, which is required for previous analyses that do not require weak convexity.\n\nA few experimental results are provided using cifar10.", "questions": "For the experiments, what is meant by learning rate and momentum parameters? How are they translated to the new algorithms? Is the learning rate the learning rate of the inner online learner or something else?\n\nThe resulting algorithms look rather similar to SGD with momentum. Indeed, without the clipping value, option 1 appears to literally be SGD with momentum. It looks like the algorithm of Cutkosky & Zhang does not require clipping through use of an extra regularization - would that be applicable here? In such a case, the analysis of Mai & Johanansson would also apply to this algorithm and so both kinds of convergence would be achievable.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Removing the randomization is intuitively a desirable behavior, and the present result provides a more general way to obtaining convergence rates without randomization. In particular, it strictly generalizes prior results finding stationary points of smooth or second-order smooth objectives.", "weaknesses": "The most obvious weakness is that the results for finding stationary points of the Moreau envelope are suboptimal.", "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": "2AK0a0FLe7", "reviewer": "Reviewer_xFGb", "summary": "This paper studies the Online-to-nonconvex conversion (O2NC) under weakly convex scenario. While the original O2NC has general update form $w_n = w_{n-1} + s_n\\Delta_n$, where $\\Delta_n$ denotes the update vector and $s_n$ is a random scaling or interpolation, this paper proposes derandomized O2NC (D-O2NC) with deterministic update form $w_n = w_{n-1} + \\Delta_n$. The core difference is that O2NC relies on the identity $\\mathbb{E}\\_{s_n } [R(w_n) - R(w\\_{n-1})] = \\mathbb{E}[ \\langle \\nabla R(w_n), \\Delta_n\\rangle]$ from random scaling, while D-O2NC relies on the weak convexity identity $R(w_n) - R(w_{n-1}) \\le \\langle \\nabla R(w\\_n), \\Delta\\_n\\rangle + \\frac{\\rho}{2}\\\\|\\Delta_n\\\\|^2$, where $\\rho$ denotes the weak convexity constant. Consequently, upon substituting online learners with proper regret bound on the quadratic loss $f_n(\\Delta) = \\langle g\\_n, \\Delta\\rangle + \\frac{\\rho}{2}\\\\|\\Delta\\\\|^2$, the resulting D-O2NC optimizer achieves good convergence guarantee. In particular, this paper considers two such online learners, clipped OGD and unclipped OGD with periodic restarting, both achieving sub-linear regret on the aforementioned quadratic losses and recovering variants of the popular SGDM optimizer upon substituting into D-O2NC. Finally, this paper also provides empirical experiments on cifar10 with resnets and ViT models and shows that D-O2NC outperforms standard SGDM.", "questions": "- Regarding the definition of regulated Goldstein stationary, my understanding is that this definition makes it more convenient for the convergence analysis, but does not include more optimizer algorithms (unlike the relaxed Goldstein stationary definition which relaxes the deterministic radius $\\delta$ to a stochastic variance bound). This is further convinced by the equivalence relation between standard Goldstein stationary and regulated version (Lemma 1). Am I understanding correctly?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The weakly convex scenario is rarely studied in the line of O2NC research, and this paper provides new results along this line. These results are novel, and they help to better understand the performance of O2NC under different settings.\n- In the convergence rate, I find it interesting that the weak convexity constant $\\rho$ is only in the non-dominant terms. In other words, the convergence rate of derandomized O2NC matches that of O2NC as long as weak convexity is bounded by $O(\\delta^{-1}\\epsilon^{-1})$, even though there is no random scaling.\n- Compared to original O2NC, derandomized O2NC better aligns with the practical implementation of popular optimizers such as SGDM, in which the random scaling is typically absent. \n- Empirical results on cifar-10 with resnets and ViT demonstrates better practical performance of D-O2NC compared to vanilla SGDM.\n- Overall, I find this paper well-written. The presentation of the main results and corresponding discussions are clear and easy to follow.", "weaknesses": "The discussion of the lower bound on the convergence rate of Goldstein stationary point of a weakly convex loss is missing. Although $O(\\delta^{-1}\\epsilon^{-3})$ is the minimax optimal rate for the general non-convex losses, it's unclear whether it remains tight for weakly convex functions. In fact, in the discussion section about the connection to Moreau envelope (e.g. Appendix D), it seems to me that the previously achieved rates on Moreau envelope translates to better rates on Goldstein stationary point. Could the authors confirm if I understand correctly, and provide some insights on the lower bound?", "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": "V4SFFWVf6X", "reviewer": "Reviewer_fXmg", "summary": "The paper extends the Online-to-Non-Convex Conversion (O2NC) framework by introducing an online learning method that efficiently finds approximate stationary points for non-smooth, non-convex functions with optimal oracle complexity. It shows that when random interpolation or scaling is applied, O2NC becomes equivalent to the stochastic gradient descent with momentum algorithm commonly used in deep learning, providing a theoretical explanation for its effectiveness. Although it is generally impossible to remove randomness without losing optimality, the paper proves that for weakly convex functions, a deterministic version of O2NC can still achieve the same optimal rate when the weak convexity parameter is not too large. The authors also propose a momentum-restarted variant that improves progress when the algorithm is far from stationarity and demonstrate through experiments on ResNet and Vision Transformer networks that this version is both efficient and effective in practice.", "questions": "I feel like there is some lack between the theory and practice. How would you for example use the theory to run the algorithm, e.g., hyper parameters. \n\nIs it possible to determine or approximate in practice the step-size and other hyperparameter choices required by the theoretical analysis, and if so, how sensitive is the algorithm’s performance to deviations from these theoretically prescribed values?”", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper establishes that O2NC achieves an oracle complexity of O(deltaˆ(-1) epsilonˆ(-3)) for finding Goldstein (delta-stationary points) of non-smooth, non-convex functions. This result improves the state-of-the art complexity of this problem (e.g., compared to Cutkosky, 2019).\n\nAnother clear contribution is that theoretical analysis clearly characterizes the boundary between when randomness is necessary and when it is not. Using the impossibility results of Jordan et al. (2023), the paper explains why fully deterministic algorithms cannot achieve dimension-free rates in general non-convex settings. However, it provides a positive theoretical result showing that when the weak convexity parameter is smaller than O(deltaˆ(-1) epsilonˆ(-3)), randomness can be eliminated without losing optimality. \n\nThe experiments show that the proposed D-O2NC method improves upon the baseline SGDM algorithm. When applied to training deep neural networks on CIFAR-10 using ResNet-101 and ViT models, D-O2NC achieves faster convergence and slightly higher test accuracy, demonstrating the practical benefit of its periodic momentum restart mechanism.", "weaknesses": "The results are only for weakly convex functions, which is theoretically fine. But, are there many functions that are non-convex but weakly convex? In particular, if I understand correctly, the problem considered in experiments does not have this property, or at least the paper does not weakly convex, so I dont know, but my feeling is that all the interesting problems are convex. Thus it would be useful if there was better comparison with the state of the art for convex setup as well.\n\nTo my understanding, although the analysis is novel, the algorithm itself closely resembles existing momentum-based methods such as SGDM or restarted gradient methods. The contribution lies mainly in the theoretical interpretation rather than in a new optimization technique.\n\nThe experimental results are relatively weak and provide only limited empirical support for the proposed method. The evaluation relies on single runs without statistical analysis, making it difficult to assess the consistency or significance of the reported improvements. Moreover, there is little exploration of hyperparameters, such as restart frequency or learning rate, and no ablation study to clarify how these choices affect performance. The experiments also lack comparisons with other widely used optimizers beyond SGDM, which limits the context for evaluating the method’s advantages. \n\nMoreover, the experimental section feels somewhat disconnected from the theoretical contributions of the paper, as it does not explicitly demonstrate or test the theoretical claims, such as optimal complexity or the benefits of weak convexity, in practice.", "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)