Sign-SGD via Parameter-Free Optimization
Authors: Daniil Medyakov
Stanko Sergey
Gleb Molodtsov
Philip Zmushko
Evseev Grigoriy
Egor Petrov
Aleksandr Beznosikov
Venue: ICLR 2026 Poster (2026)
Keywords: Parameter-free optimization
Sign descent
Convex optimization
Stochastic optimization
Primary area: optimization

Abstract: Large language models have achieved major advances across domains, yet training them remains extremely resource-intensive. We revisit Sign-SGD, which serves both as a memory-efficient optimizer for single-node training and as a gradient compression mechanism for distributed learning. This paper addresses a central limitation: the effective stepsize cannot be determined a priori because it relies on unknown, problem-specific quantities. We present a parameter-free Sign-SGD that removes manual stepsize selection. We analyze the deterministic single-node case, and extend the method to stochastic single-node training and multi-node settings. We also incorporate the momentum technique into our algorithms and propose a memory-efficient variant that stores only gradient signs instead of full gradients. We evaluate our methods on pre-training LLaMA models (130M and 350M) and fine-tuning a Swin Transformer (28M). Across considered tasks, the proposed methods match the performance of tuned Sign-SGD and AdamW (grid-searched stepsizes with a cosine schedule), while avoiding tuning overhead. Employing parameter-free training yields approximately $1.5\times$ end-to-end speedup compared to runs with grid-searched stepsizes.

Published as a conference paper at ICLR 2026
SIGN-SGD VIA PARAMETER-FRES OPTIMIZATION
Daniil Medyakov 122
Sergey Stanko 1.2
Gleb Molodtsov 1.2
Philip Zmushko 122,4,4
Grigoriy Evseev
Egor Petrov Aleksandr Beznosikoy
Basic Research of Artificial Intelligence Laboratory (BRAIn Lab)
2 Moscow Independent Research Institute of Artificial Intelligence
3 Yandex Research
Institute of Science and Technology Austria (ISTA)
5 Innopolis University
ABSTRACT
Large language models have achieved major advances across domains, yet training them remains extremely resource- intercee. We revisit SIGN-SGD, which serves both as a memory -efiirrefffi optimizer for single-node training and as gradient compression mechanism for distributed learning. This paper addresses central limitation: the effective stepsize cannot be determined a priori because it relies on unknown, mroblem-specifee quantities. We present parameter- free SIGN-SGD that removes manual stepsize selection. We analyze the deterministic single-node case, and extend the method to stochastic single-node training and multi-node settings. We also incorporate the momentum technique into our algorithms and propose a memory-efficient variant that stores only gradient signs instead of full gradients. We evaluate our methods pre-training LLaMA models (1 (130M and 350M) and fine-tuning a Swin Transformer (28M). Across considered tasks, the proposed methods match the performance of tuned SIGN-SGD and ADAMW (grid-searched stepsizes with a cosine schedule), while avoiding tuning overhead. Employing parameter-free training yields approximately 1.5x end-to-end speedup compared to runs with grid-searched stepsizes.
INTRODUCTION
Models and datasets continue to scale rapidly (Vaswani 2017 202I). This growth drives steep increases in compute requirements, memory footprint, and wall-clock training time, consequently raising hardware costs. These pressures motivate the development of methods that accelerate training and reduce resource usage without sacrificing accuracy. A significant breakthrough arose not from designing advanced learning algorithms, but primarily from the manner in which these algorithms can be applied: distributed learning (Konečný al., (016 McMahan et al.) 2017; Verbraeken et al. 2020). However, distributing training across M nodes does not yield an M-fold speedup practice, inter-device communication remains significant bottleneck.
Hoffmann et al.) 2022] Alzubaidi et al.,
The reduction of the number of transmitted packages through compression is one of the key techniques to address this issue (Seide al. [2014] Alistarh et al., 2018). Among method stands out (Bernstein et al. 2018). Solving the classic
Algorithm 1 SIGN-SGD
1: Input: Start point x0 E Rd, number of iterations T
Parameter: Stepsize y
others, the
3: for t = 0, T do
x1+1 x² - signn (Ssig(nS((")) (*)()*)
optimization problem min [xx it utilizes =ER4 an intuitive heuristic that takes the sign of each gradient coordinate (Algorithm) I.. In the distributed setup, aggregation is performed by majority vote on the transmitted signs of the gradients,
5: end for
Additionally, SIGN-SGD is rapidly gaining popularity, even for single-node training. In contrast to methods such as ADAM (Kingma 2014) and ADAMW (Loshchilov) (017). which require sub- stantial memory for storing statistics, SIGN-SGD is free from this constraint. Moreover, sign-based
Email: medyakovd366 gmail.com.
I The work was completed prior to joining ISTA.

---

Published as a conference paper at ICLR 2026
approaches offer both theoretical and practical advantages traditional SGD (Robbins & Monro 1951), demonstrating superior convergence (Balles & Hennig 2018 Balles et al. 2020 and empirical performance (Kunstner et al. 2023 Zhao et al. 2024 Zmushko et al. 2024 in training large models.
Although SIGN-SGD is effectively used both for compression in distributed learning and as a memory- -fffcieteficceent method in single-node regime, achieving its full potential requires selecting appropriate stepsize. The optimal choice depends on problem-specifie quantities that are unknown in practice, necessitating costly manual tuning. To address this issue, introduce parameter-free SIGN-SGD algorithm that employ automatic stepsize selection schemes.
2 BRIEF LITERATURE REVIEW AND CONTRIBUTIONS
To situate the problem and motivate our algorithms, this section reviews the literature and distills the open challenges that guide our contributions.
We begin by revisiting SIGN-SGD and identifying the theoretically desirable stepsize that would
enable effective training without manual tuning.
Next, we survey parameter-free optimization methods, highlighting their advantages and limitations.
We conclude by stating the contributions of this work and explaining how they address the gaps.
2.1 RELATED WORK
Sign-SGD. In the original paper on SIGN-SGD (Bernstein et al. 2018). the authors explored convergence in the paradigm of finding a near-stationary point, i.e., such x E Rd that [ < e. where represents the accuracy of the solution. Moreover, to achieve convergence with respect to the variance term, the authors utilized mini-batches. Both this convergence criterion and the use of mini-batches are essential components of the analysis. As shown in (Karimireddy al., 2019).
SIGN-SGD may fail to converge when considered the regret minimization. Moreover, to achieve convergence with respect to the variance term, the authors of (Karimireddy al. 2019) utilized mini-batches. Mcanwhile, Saaaryan & Richtárik (202T) proposed relaxation of the SIGN-SGD method and showed that least half of the coordinates in the sign of the stochastic gradient align with those of the exact gradient, thereby enabling convergence with respect to the variance term. A number of works have also emerged around SIGN- SGD, extending with momentum (Sun et al.) 2023), providing high-probabilig convergence bounds (Kornilov al. 2025), and studying it in the context of differential privacy (Jin & Dai 2025). Nevertheless. the possibility of selecting a stepsize independent problem properties while achieving optimal convergence rate has been largely overlooked.
Let us provide the basic estimate of SIGN-SGD convergence with the exact gradient oracles. This can be simply derived from Theorem (ernstein et al. 2018):
T
7ox
[VS((')|
2
where Lxs is the smoothness constant of the objective with respect to loo -orm, and A f(x") - fxx") represents the initial distance to the solution. Putting
Lo VT
we obtain optimal
convergence rate.
This stepsize poses challenges, depends on the problem's hy hyperparameters. To address this issue, we turn to various techniques that facilitate the provision of an adaptive stepsize.
Parameter-free approaches. In the non-smooth setting, considering regret minimization, classic
gradient methods (Robbins & Monro 1951; Moulines & Bach 2011 Stich 2019
Lan 2020
require
| x 122
to have O [1000 x" M
convergence rate.
(2)
M MVT
This estimate is (worst-case) optimal in its complexity class (Nemirovskij & Yudin 1983). We M
denote the Lipschitz constant (I)()) f(w) & M ||x vll for all x. y E IRo). The parameter-free
2

---

Published as a conference paper at ICLR 2026
setting aims to adapt the stepsize automatically, without prior knowledge of the initial distance |1z0 -x"112 2| or the Lipschitz constant M.
For the first time, the idea of an automatic stepsize setting was proposed to achieve adaptation to constant M. It was embodied in methods such as ADAGRAD (Duchi et al. 201T), ADAM (Kingma
2014), RMSPROP (Tieleman & Hinton, 2012), ADADELTA (Zeiler 2012), and ADAPTIVE SGD
(Gupta et al. 2017| Attia & Koren 2023). In these methods, computed gradients were utilized to adjust the stepsize based on the properties of M. Hlowever, these methods required additional memory and computations, and they lacked adaptivity to the initial distance. Attempts to modify y in equation to approaches within the general online stochastic learning setting (Orabona) 2019).
such as com betting and reward-doubligg techniques (Streeter& & McMahann] (2012) Orabona 2013
McMahan & Orabona 2014 Orabona Pál 2016; Cutkosky & Orabonal 2018 Cutkosky 2019).
which can also be classified as parameter-free algorithms. Nevertheless, these approaches assumed that the stochastic oracles have some (loose) bound.
Further studies suggested more intricate solutions in parameter-free convex stochastic optimiza- tion. These methods achieved asymptotic convergence rates comparable to classic approaches while adapting to essential hyperparameters. The starting point was the work (Carmon & Hinder) 2022) which provided adaptivity to the initial distance | - x" l|2 through estimators of the form maXteT ||=" - x²1 To find such estimators, the authors employed
additional grid search procedure which increased the required number of steps only in double -ogae--ogaaithmic time. The primary objective of this work was to derive probbbbbbbiilty convergence estimates in the stochastic convex non-smooth setup. Several studies that did not utilize the additional search procedure were built upon, including (Khaled et al. 2023), (Ivgi et al. 2023) and (Kreisler et al. 2024).
The work (Defazio & Mishchenko 2023) provided another approach for sensitivity to the initial distance. The authors iteratively constructed a sequence upper bounded by ||20 x" and approx- imated it accordingly. However, they considered only exact gradient oracles, which represents significant limitation. Later, in (Mishchenko & Defazio (023). the authors introduced damping factor in the denominator to improve convergence in the logarithmic factor's square root. Never- theless, theoretical analysis depended on the knowledge of the Lipschitz constant, which not a parameter-free approach. We note that the use of the classic ADAGRAD-NORM stepsize (Duchi et al. 2011 Streeter & McMahan 2010; Wardd et al. 2020), possibly with additional factors in the denominators, remains standard for adaptation to M.
The orthogonal approach was presented in the work (Mishkin et al. 2024 J. The authors considered a smooth setup and proposed the use of local approximations of the smoothness constant L to achieve
||x '6'))='')
adaptivity. However, the authors employed the stepsize 7 = ( Vie at the f-th
iteration, where 7² was determined by exponential search in the manner CCarmon & Hinder 2022 by Newton's 's method. Both variants are inefficient.
In light of the literature, present the main directions of this study. Our goal is to provide the parameter-free SIGN-SGD method that achieves a convergence rate comparable to the optimal stepsize tuning]
2.2 CONTRIBUTIONS
We propose novel mechanism for estimators compared existing approaches. Instead of the classic | - x=I and M hyperparameters in equation 2 we aim to gain the tolerance to f(x") f(x*) and We now outline our contributions.
Loo from equation|
Parameter-free SIGN-SGD. We introduce a parameter-free SIGN-SGD method. The core idea involves per-iteration step-size adaptation. Every iteration, we choose estimators of Loo and (2²)) fx=) using the current gradient information. This design is practical, as it requires no additional hyperparameter search or restarts. As starting point, we analyze the exact gradients setup. Stochastic and distributed settings. We study our algorithm in the distributed setting and the case of stochastic gradient oracles. A lack of stochastic analysis presents a significant drawback in parameter-free optimization. Our work addresses this limitation.
Practical extensions. We extend our approach in two important directions.
We incorporate momentum to improve practical performance.
3

---

Published as a conference paper at ICLR 2026
We provide memory-efficiem parameter-free version. It stores only the sign of the gradient from the previous step while remaining an adaptivity to the problem properties.
Theoretical analysis. We provide comprchensive theoretical analysis of the proposed methods and establish convergence guarantces. In our setup, we consider convex and smooth objective. Experimental validation. We demonstrate that methods competitive in practical tasks, including LLM and VIT training. An Adam-style momentum variant further improves performance across both language and vision benchmarks. Empirically, parameter-free training matches or is slightly below tuned SIGN-SGD and Adam W with cosine schedules, while achieving appreciably better overall training time.
ALGORITHMS AND CONVERGENCE ANALYSIS
Notation. We begin with the following notation: E[|] denotes the expected value of random variable, ||æ||| = / (z. z²) represents the Euclidean norm of the vector x E RR ||e|| = Σ | refers to the & norm of the vector and || = maXig[4] [zy]] defines the &o -nom of the vector
Assumptions. We present the assumptions regarding the objective function f A ssumptton 3.1. The function f is Toe--mooot i.e., it satisfies [VV - V ull for any 2, E IRd.
Assumption 3.2. The function f is convex, i.e. it satisfies f(x) < f(v) (Vi(z),, y) for any 2, y E Rd.
Although neural networks are inherently non-convex, theoretical analysis under convexity assump- tions remains relevant. Recent studies suggest that deep neural networks often exhibit properties similar to convexity in certain regions, making insights from convex analysis applicable (Kleinberg jet al. 2018 Zhou al. 2019 Liu et al. 2022). Moreover, convex optimization serves as a theoretical foundation for the design of optimization algorithms. For example, momentum (Nesterov et al. 2018) and AdaGrad (Duchi et al. (01TT) were initially developed and analyzed for convex problems.
Assumption 3.3. The function f has a (maybe not unique) finite minimum, i.e., f(x*)
infzer (xx -C.
Now we move to the base point of our analysis: the algorithms with exact gradient oracles.
3.1 EXACT GRADIENTS SETTING
We begin with an additional assumption regarding the gradient oracles.
Assumption 3.4. At any point Rdd, we have access the exact gradient, i.e., we can compute the full gradient value V f(x)).
We now present the main algorithm of this paper named ALIAS (Automatic Local Ite-ltera Approximation of the Stepsize, Algorithm 2). At each iteration, it utilizes the stepsize selection in a specific manner gain adaptivity to the global parameters of the problem. Below, provide an explanation of the algorithm and offer some intuition why the presented stepsize facilitates adaptivity. Considering the stepsize in equation I need to approximate the numerator and denominator. Thus, we first analyze how to estimate A and then proceed with L
We start with a positive scalar d', representing the initial approximation of A' Next, construct new approximation based on the newly calculated gradient (Line (6) at each iteration of the algorithm. To bring these approximations closer to A over iterations, and newly computed values (Line
take the maximum of the previous 7). This approach yields an non-decreasing sequence that is upper bounded by A (see Lemma F.I We adopt this iterative scheme as Option I Algorithm 2 (Line 9).
We note that estimating A does not require advanced schemes such as Option for most tasks, as adaptivity oo (a=" is typically not critical. As shown in (Boyd et al., 2003). the condition f(x²) 0 arises in problems such as finding a point in the intersection of con- vex sets, completing positive semi-definite matrices, or solving systems of convex inequalities.
4

---

Published as a conference paper at ICLR 2026
Moreover, lower bound on f(x") " is of- ten known or readily available. For instance, f 0 serves as valid estimate in the em- pirical risk minimization setting. Taking this into account, we present the second option for method, where use f(z")
Algorithm 2 ALIAS
1: Input: Starting point x. E Rd, initial Loo- approximation 7) 1 initial A' A'-approximation
d E R, lower bound f on f(x"), number of iterations T
2: for tarl=00 ...... T do
with < f(x') (Line 10 instead of the sequence )t=0
3: Compute gradient V (z())) V(we) (2
4:
n/² =-= -
V4
As for the denominator, at the 1-th iteration, we approximate the local Lipschitz constant
5:
if l / 0 then
Loo between x' and xf-1 We accumulate
6:
d'
the manner of ADAGRAD-NORM by adding it to the sum of previous approxima- tions:
7:
d' max
dd-1,,d ,d'
8:
end
9:
Option 7' X'vo'
1 - vf(2'')]|,
[V
10: Option II: 7t N' f(x0) ((x9)-] -
|x x 11 20
11: x1+1 x¹ (sign(V[(r))
In the stepsize, the corresponding to the de- nominator coefficient appears as:
12:
end for
X
1-1 ((((a)))--(((()) 2i=0
- 20
This stepsize facilitates iterative adaptation to the objective landscape. We are now prepared to present the main theoretical results of this section.
Theorem 3.5. Suppose Assumptions
3.1
3.2
3.3
3.4
hold. We denote & E. [Vf
[ Then Algorithm with d
Lo
to reach e-accuracy needs
|| 1|
δ (A (Lxz)
A (Loo)"
and δ
iterations with Options and II, respectively.
d (LQ))²
(IO))²
c²
Remark 3.6. Under conditions Theorem 3.5
Algorithm 2 with
T-11 reach e-accuracy, where > + δ
2
V (a
Il,
needs
( and
Loo c2
δ
iterations with Options I and II, respectively.
dug2
Discussion of the results. Since we provide convergence guarantees for finding near-stationary points for convex objective, first examine the relationship between convergence rates in convex and non-conves settings. For instance, we compare gradient descent rates using the gradient norm as the convergence criterion. While the behavior of gradient norm minimization is well understood in the non-convex setting (Arjevani et al. 2023), it is specific in the context of convex optimization. Notably, Allen-Zhul (2088) showed that vanilla gradient descent without acceleration additional techniques achieves the same O (2/²2) rate for finding near-stationary points in both convex and non-convex settings. However, as previously noted, SIGN-SGD does admit convergence guarantees beyond any criterion except the gradient norm, even in the convex case. Consequently, convergence analysis for sign-based methods must be framed in terms of finding the pear-stationary point. Thus, our convex rate is not superior to that of the non-convex case. Moreover, the bound in Theorem 3.5 includes an additional factor of (4~~/10)) )² compared to Remark 3.6| However, the algorithm analyzed in Remark 3.6 not parameter-free it requires prior knowledge L In Appendix A we present empirical results for varying values of Loc. which demonstrate that this additive factor has negligible impact the practical convergence of Algorithm??
So far, propose algorithm and provide the theoretical analysis behind it. However, the analysis assumes access to exact gradient oracles an unrealistic assumption in practice. We now extend the analysis to more realistic scenarios involving stochastic oracles.
5

---

Published as a conference paper at ICLR 2026
3.2 STOCHASTIC GRADIENTS SETTING
We begin with the assumption regarding the gradient oracles.
Assumption 3.7. At any point x IR we have access to the stochastic gradient, i.e., we can compute 96 (x()) = V fr,,, {) the stochastic gradient value with respect to the randomness in the choice of samples ç. Additionally, the variance of these stochastic estimators is coordinate wise bounded, ie..
E (Lge (2)], /V fxx)))) <oa Furthermore, this implies that E (x))
ff(x)) < ||ll
It is a classic assumption in stochastic optimization (Bernstein et al., 2018 Furthermore, the batch gradient de typically exhibits smoothness (Liu et al. 2023). Thus, we introduce an additional assumption.
Assumption 3.8. The stochastic function fe Lo -smooth according to the realization &. i.e., satisfies |1 (v)) < Los || 20 for any x, y E R
The stochastic formulation of the problem (Assumption 3.7 necessitates modifications of Algorithm This algorithm assumes access to the exact gradients, and the estimation of the local smoothness constant relies on computing full gradients. Thus, our goal is modify Line + Algorithm 2 Utilizing Assumption 3.8 stochastic gradients with respect to the stochastic realization ç Namely,
2
construct local approximation of Loo the t-th iteration via
X
gei
where L. is the stochastic gradient computed at the f-th iteration based on the stochastic realization ç:. We query the oracle twice per iteration, utilizing the current and subsequent stochastic realizations. Another change in Algorithm 2 involves performing a step in Line II regarding sign(gE:). In the subsequent theoretical analysis, we focus solely on Option in Algorithm 2
We provide a formal description of the stochastic method, Algorithm 7 in Appendix F22 There, we present both the practical and theoretical versions.
We now present the convergence results.
Theorem 3,9. Suppose Assumptions
3.8
3.2
3.3
3.7
hold. Then Algorithm 2 wwth Option Il to reach
o -0 ll, || l,
E-accuracy, where
T-1
E
Vf(x')]l
and L. ++1
needs
7
[Zx))
E
+ ||ااا L.o
E
iterations.
22
LO
min 0g157-1
L
Remark 3.10. Under the conditions of Theorem 3.9 Algorithm with X
Option II and mini-batch of the size t 1 at t-th iteration, to reach e-accuracy needs
Loo
||011 1
Too
))
E
iterations,
2
62
T(g-m 0
min
o
where + Σ |V
LLg
more stringent version of Assumption 3.1 we approximate the smoothness constant via stochastic gradients. The key point is to measure the gradient the current point while considering the stochastic realization from the next iteration. Since z², gt, and g++1 are independent, we can provide a theoretical analysis. Thus, we surpass works such as (Defazio & Mishchenko 2023 Mishchenko & Defaziol 2023 Mishkin al. 2024).
Discussion of the results. With Assumption 3.8

---

Published as a conference paper at ICLR 2026
which employed similar idea of the adaptation to the Lipschitz constant but lacked stochastic analysis. Notably, the result of Theorem 3.9 achieves convergence only to a neighborhood, the size of which is determined by the variance. This rate fully aligns with the original SIGN-SGD convergence (Bernstein et al., 2018). To address it in theory, we introduce increasing mini-batches analogously to (Bernstein al. 2018) in Remark(3.10 We note that mini-batching enables convergence guarantees concerning the variance term: however, the method remains parameter- even without it. In our experiments, do not employ mini-batching.
We develop an analysis not only for the stochastic setting, but also for the distributed one. A full deseription of Algorithm 2 in the distributed setup, along with theoretical statements and proofs, is presented in Appendix F.3
Above, we present an algorithm that can be casily applied practical tasks. It does not require multiple restarts or additional search procedures. However, Algorithm lacks the main advantage of the original SIGN-SGD method. Indeed, performing step on the t-th iteration requires storing the entire gradient [x(x'²) instead of just its sign. To address this limitation, we propose memory-efficient modification in the next section.
3.3 MEMORY-EFFICIEN ALIAS
In Algorithm 2 memory efficiency is sacrificed achieve a parameter- stepsize. Indeed,
d'
7 (Vf(a++)) sign (VS(x))))
3' = =VV
V
2i=0 [V/
To compute d', it is sufficient to store only sign (V (x(-1)) incurring no additional memory costs. Regarding X4, we calculate f (f(x
" I1 and xtt1 x² at each step. The last term
does not present an issue since || x' "
Il siig (vf(2* 1)) || However, to find
| (x)="))) it is necessary to store the entire gradient Vf(x"-))
We address this concern by modifying A in Algorithm
n/t = n 11--1 ||*)'²) - vf(z*-))le
followed by =
|| - xz11|
[V((++)) - 11
To approximate the smoothness constant, we interchange the Loc norm and 4 4--ormm in the ex- pression, leveraging their duality relationship. Thus, we approximate the constant L1. not Loc. as indicated in Algorithm 2 Theoretically, this approach still requires memorizing V ff(x*
For this reason, we consider a practical option by the approximation [[ - (z max(|max, [='()') miny [Vf((t"))( [vax (V min, / fxx)))))))))) It necessitates
storing only additional constants: max; [V((x'))), 1, and min, [V/(x' )), In the theoretical
analysis, we provide convergence guarantees only for the X' choice, in equation However, we additionally validate the methods empirically with the approximation the (se -norm and provide an ablation study that shows a small deviation of the approximate solution from the exact one. More precisely, this approximation provides an upper bound on the initial -nomm, while remaining close to it (see Section 4 and Appendix A
We present a theoretical analysis a memory-efficiee approach, utilizing an additional assumption on the smssohhhesss..
Assumption 3.11. The function f is L Lı-smooth, i.e., it satisfies [Vx V fv) <4 vll for any y E I
Now we present the convergence guarantees of Algorithm 2 with X as in equation 3
Theorem 3.12. Suppose Assumptions
3.11
3.3
3.4
hold.
We denote E >
7 - [V |V
Then Algorithm with d < A and d X as
7

---

Published as a conference paper at ICLR 2026
in equation reach E-accuracy needs
(A7) (Ta) de d (1.9) 82
A (L1)* d2 (1.9) 82
and δ
iterations with Options I and II, respectively.
The result of Theorem 3.12 deteriorates the rate established in Theorem 3.5 Indeed, we can derive the Lx & dL, inequality. However, the proposed approach offers significant advantages in terms of memory efficiency.
Nevertheless, the theoretical convergence rates presented in this section not optimal. In the stochastic case, we aim to achieve ① Lt [ell? rate. This issue is discussed in detail in Appendix
where we present an algorithm that attains this rate.
3.4 ALIAS WITH MOMENTUM
In previous sections, we presented methods that do not utilize the momentum parameter (Polyak 1987; Nesterov et al.) 2018). However, many modern optimizers, such as ADAM (Kingmal (014). PRODIGY MMischeenko & Defazio 2023).
Algorithm ALIAS Adam version
1: Input: Start points x x² E Rd, r m
20 = 0.
d > O, number of iterations T
2: Parameters: 7², 17,31,35 8/2 > 0
3: for = 0..... T
4: rlt = /V2r"* 2 + (1
vB2) d' sign((
MUON (Jordan et al., 2024). and MARS (Yuan et al.J 2024), employ this technique. We address this gap in the current section and present Algorithm 3] which incorporates the momentum parameter into Algorithm
5:
d' = -max 08-1,,0+1
6: m (+ = -mmm' + +(1 - B1 dddd'df Dz.
ml+1
7: rtl = -2y' + (1 - B2) (dd) (5te
8: 141 = x² y6 (d
sign(m++1) +1)
m
2 in manner similar to (Mishchenko Defazio 2023). Specifically, we include exponential moving averages of the first and second statistics, as in ADAM to aggregate past gradients and provide coordinate-wise normalization that mitigates sharp directions and gradient noise.
9: end for
4 EXPERIMENTS
In this section, we present empirical results for the LLM pre-training task. In Appendix we validate our approach on vision tasks, specifically by fine-tuning the SWIN Transformer architecture (Liu et al. 2021). Our code is open-sourced!
Language model pre-training. Following the protocol of (Lialin al. 2023). we train LLaMA-
based architecture (Touvron et af. (023) with 130M parameters on the C4 dataset (Raffel et al.] 2020). detailed description of the experimental setup provided in Appendix A We compare several optimization methods: SIGN-SGD with tuned constant learning rate (Ir), and three methods using tuned learning rate with cosine scheduler (cosine sc) - namely, and NORMALIZED SGD. All of these methods are compared against ALIAS (Algorithm ( which is used without any tuning. Additionally, we evaluate all methods with weight decay (wd). We provide final validation loss and perplexity in Table
STEEPEST DESCENT,
In Table 2 we present the results for methods incorporating momentum (3) (all methods with weight decay). ALIAS Adam version utilizes sign descent with momentum and an additional scaling factor (see Algorithm 3 for details). We consider two options for this method: with and without cosine scheduler. We provide comparison with ADAMW (Loshchilov) 2017) and PRODIGY (Mishchenko & Defazio 2023). We test PRODIGY with and without a learning rate scheduler. We present the pre-training dynamic in Figure [
These results coincides with those in Tables I
https:://github..cmm///
8

---

Published as a conference paper at ICLR 2026
Table 1: SIGN methods on LLAMA pre-training.
Table SIGN-SGD methods with added mo- mentum parameter (3), ADAMW and PRODIGY on LLAMA pre-training.
Algenihm
Vilidrin (osc(
Peppisity (
SiGk-SGD (r)
1,041
30.935
Algonimm
Volidaoem Linc
Perpleccy (4)
SGDN (k. comine
2,992
19.925
STEEFEST DESCENT (Ir, onsine
3,035
20.791
SHam-SCaD (ndd 2.30
2,900
Stux SGD ood, cosune sc)
ALJAS lours)
SIGN SGD ood.tn
NORMAALZZED IZED SGD il, oniine
3,017
3,04]
2,590
3,135
22.952
20.92
19,93
20.422
Noesa, SGiD ted,
Abssw ted, 8 couns Promiy (wi. ())
Dest: lesite
cosise so]
2.953
2.954
2.92)
3.003
18. 18.765
18,955
13.211
Stnerest Desicaso (wid, It. cosine se1
3,022
20.537
PRODIGY (wc. cosine sc)
NORMAAL iren SGD twd. cosine sc]
3,005
20.10 10.109
ALJAS (ud) (eurs)
1/005
20110
ALJAS Adam (ool
2.918
Sig--20 lnsrant Nerrol 500
16
Sigh-5oo jud di
Opt ECI pel
ALAG
Hoaes lind Iwc Aulk ladt
Stapid EesarCEeaattti coie
Validation 1000
Vadiciation
K.20 vecso CONDEc
34
Number stachastic gradient calls. 1
Number of stochastic gradient calls,
Number stochasctic gradient calls.
GGD tomaentti
Son cendentt
ge tnniio)
Syn (nd. csinal
To aad wit let
Partoxit
33
ALAS
Sumppai Descent
Discant ind)
23
2000
20010
40/00
32000
100000
2002
2306
20003
733030
20022 Number stochaschic gradient calls
80303 100000
Number stochastic gradient calls
Number stnchwatic gradient calls,
Figure 1: Comparison of SIGN-SGD methods in LLAMA pre-training. The left column shows results without weight decay, the central column presents results with weight decay (wd), and the right column displays results with weight decay (wd) and momentum parameter (3).
We highlight that our basic ALIAS achieves performance only slightly inferior that of SIGN-SGD with a tuned cosine scheduler. The Adam-based version of ALIAS outperforms all competing methods, including tuned ADAMW and the state-of-the-art parameter- optimizer PRODIGY with tuned cosine scheduler. These results are particularly competitive given that our approach eliminates the need for learning rate tuning - a significant practical advantage. This feature enhances the method's usability, making it appealing for large-scale applications.
2 We proceed with testing the memory-efficient ap- proach, presented in Section 3.3 Recall that we approximate [[V vf(a'=)) s max [V[(<(1))] - miny /V [++)))) We compare
Memory-eflicient version of Algorithm
max max([maxx; [ (x=)), min, (/ the performance of ALIAS with X' as in equation 3 considering exact and approximated -norm (me), SIGN-SGD with constant (uuned) stepsize, and SIGN-SGD with a (tuned) cosine scheduler. The results of the 130M ALAMA-basee model pre-training are presented in Table We provide an ablation comparing exact and approximated values of l -norms during training in Appendix A
The results indicate a slight performance degra- dation of the remory-efficieen version of ALIAS compared to SIGN-SGD with cosine scheduler baseline, as well as relative to the orig- inal ALIAS method. However, it is crucial to emphasize that this variant a parameter-free algorithm that retains only the sign of the gra- dient from the previous iteration. Despite these simplifications, its performance remains competitive with significantly more memory-intente intensive meth- ods. We report performance metrics, memory footprint, and runtime efficiency in Appendix A along with detailed training configurations for full reproducibility.
Table 3: SIGN-SGD methods and memory- efficient version of ALIAS LLAMA pre- training.
Algacitin
Validaton Loss (1)
Peppecity (3)
SGD (wd.li StoNe-CCD (wd, creine
3.41
209933
2,900
19
ALTAS
303399

---

Published as a conference paper at ICLR 2026
5 CONCLUSION
In this work, we present novel parameter-free SIGN-SGD that eliminates manual stepsize selection. The method is analyzed in deterministic, stochastic, and distributed settings. Additionally, introduce a memory-efficient variant that stores only gradient signs while maintaining adaptivity. We
also explore momentum-adappte version that demonstrates strong performance in practice.
ACKNOWLEDGMENTS
The work was supported by the Ministry of Economic Development of the Russian Federation (agreement No. 139-15-2025-013, dated June 20, 2025, IGK (1M0000C3132554B0O00
REFERENCES
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018.
Zeyuan Allen-Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances Neural Information Processing Systems, 31, 2018.
Laith Alzubaidi, Jinglan Zhang, Amjad Humaidi, Ayad Al-Dujaili, Ye Duan, Omran Al-Shamma, José Santamaría, Mohammed A Fadhel, Muthana Al-Amidie, and Laith Farhan. Review of deep learning: concepts, enn architectures, challenges, applications, future directions. Journal of big Data, 8:1-74, 2021.
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.
Amit Attia and Tomer Koren. Sgd with adagrad stepsizes: Full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance. In International Conference on Machine Learning, pp. 1147-1171, PMLR, 2023.
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pp. 404-413. PMLR, 2018.
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux. The geometry of sign gradient descent. arXiv preprint arXiv:2002.08056, 2020.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Stephen Boyd, Lin Xiao, and Almir Mutapcic. Subgradient methods. lecture notes of EE392o. Stanford University, Autumn Quarter, 2004(01), 2003.
Yair Carmon and Oliver Hinder. Making sgd parameter-free. In Conference on Learning Theory, pp. 2360-2389. PMLR, 2022.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Iransactions on intelligent systems and technology (TIST), 2(3):1-27, 2011
Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Conference Learning Theory, pp. 874-894. PMLR, 2019.
Ashok Cutkosky and Francesco Orabona. Black- box reductions for parameter-fiee online learning in banach spaces. In Conference On Learning Theory, pp. 1493-1529, PMLR, 2018.
George E Dahl. Frank Schneider, Zachary Nado, Naman Agarwal, Chandramouli Shama Sastry, Philipp Hennig, Sourabh Medapati, Runa Eschenhagen, Priya Kasimbeg, Daniel Suo, et al. Bench- marking neural network training algorithms. arXiv preprint arXiv:2306.07179, 2023.
10

---

Published as a conference paper at ICLR 2026
Aaron Defazio and Konstantin Mishchenko. Learning-rate learning by d-adaptation. In Interna- tional Conference on Machine Learning, pp. 7449-7479. PMLR, 2023.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition. pp. 248-244225 205. Ieee, 2009.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. I.
Vineet Gupta, Tomer Koren, and Yoram Singer. A unified approach to adaptive regularization in online and stochastic optimization. arXiv preprint arXiv: 0006 065666 2017.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. /5556, 2022.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference Machine Learning, pp. 14465-14499. PMLR, 2023.
Richeng Jin and Huaiyu Dai. Noisy signsgd is more differentially private than you (might) think. In Forly-second International Conference on Machine Learning, 2025.
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy
Bernstein. Muon: An optimizer for hidden layers neural networks, 2024. URL https
7/keller github..th.... itciii..////// wttppsssttssttoooo////ooooo
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252-3261. PMLR, 2019.
Priya Kasimbeg, Vincent Roulet, Naman Agarwal, Sourabh Medapati, Fabian Pedregosa, Atish Agarwala, and George E Dahl. How far away are truly hyperparameter-frre learning algorithms? arXiv preprint 1iXiv:2505.24005 2025.
Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-free gradient descent method. Advances in Neural Information Processing Systems, 36: 6748-6769, 2023.
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint 2014.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. alternative view: When does sgd escape local minima? In International conference machine learning. pp. (698-2707. PMLR, 2018.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 160.02661 2016.
Nikita Kornilov, Philip Zmushko, Andrei Semenov, Mark Ikonnikov, Alexander Gasnikov, and Alexander Beznosikov. Sign operator for coping with heavy-tailed noise in non-convex optimiza- tion: High probability bounds under (I (t_0,4 [0l_1) smoothhessss arXiv preprint arXiv:2502.07923, 2025.
Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-fre stochastic optimization. arXiv preprint arXiv:2404.0066 2024.
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint arXiv:2304. 39600, 2023.
Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Yann Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.

---

Published as a conference paper at ICLR 2026
Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. Relora: High- rank training through low-rank updates. In The Tweifth International Conference on Learning Representations, 2023.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterizee non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference computer vision. pp. 10012-10022, 2021.
Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal non-convex stochastic opti- mization under generalized smoothness. arXiv preprint arXiv:2302.06603 2023.
I Loshchilov. Decoupled weight decay regularization. arXiv preprint arXiv:711.05101,, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efffcceenn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
H Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory, pp. 1020-1039. PMLR, 2014.
Konstantin Mishchenko and Aaron Defazio. Prodigy: An expeditiously adaptive parameter-free learner. arXiv preprini 21Ti::2006.66000 2023.
Aaron Mishkin, Ahmed Khaled, Yuanhao Wang, Aaron Defazio, and Robert Gower Directional smoothness and gradient methods: Convergence and adaptivity. Advances in Neural Information Processing Systems, (1144481114444 2024.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Francesco Orabona. Dimension-free exponentiated gradient. Advances in Neural Information Processing Systems, 26, 2013.
Francesco Orabona. A modern introduction online learning. arXiv preprint arXiv: 1912. 2019.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016.
Boris T Polyak. Introduction to optimization. 1987.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1 11 2020.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Mher Safaryan and Peter Richtárik, Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, pp. 9224-9234, PMLR, 2021.
Fabian Schaipp. Ruben Ohana, Michael Eickenberg, Aaron Defazio, and Robert Gower. Momo: Momentum models for adaptive learning rates. arXiv preprint arXiv:2305.07583 2023.
12

---

Published as a conference paper at ICLR 2026
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pat data-parallll distributed training of speech dnns. Interppeech, volume 2014, pp. 1058-1062. Singapore, 2014.
Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:1907.04232, 2019.
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv:1002.4862, 2010.
Matthew Streeter and H Brendan McMahan. No-regret algorithms for unconstrained online convex optimization. arXiv preprini
2012.
Tao Sun, Qingsong Wang. Dongsheng Li, and Bao Wang. Momentum ensures convergence of signsgd under weaker assumptions. In International Conference on Machine Learning, pp. 33077-33099. PMLR, 2023.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop, coursera: Neural networks for machine learning. University of Toronto, Technical Report, 6, 2012.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint urXiv:2302.1997, 2023.
Vaswani. Attention all you need. Advances Neural Information Processing Systems, 2017.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey distributed machine learning. Acm computing surveys (csur), 53(2): 1-33, 2020.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1-30, 2020.
Huizhuo Yuan, Yifeng Liu, Shuang Wu, Xun Zhou, and Quanquan Gu. Mars: Unleashing the power of variance reduction for training large models. arXiv preprint arXiv:2411.10433 2024.
Matthew D Zeiler. Adadelta: adaptive learning rate method. arXiv preprint arXiv:1212.5701 2012.
Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, and Sham Kakade. Deconstructing what makes good optimizer for language models. arXiv preprint arXiv:2407.07977. 2024.
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:1901.00451, 20199 2019.
Philip Zmushko, Aleksandr Beznosikov, Martin Takáč, and Samuel Horváth. Frugal: Memory-
efficient optimization by reducing state overhead for scalable training. arXiv:2411.07837. 2024.
arXiv preprint
13

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
2
Brief Literature Review and Contributions
Related work
2.2
Contributions
3
Algorithms and Convergence Analysis
3.1
Exact gradients setting
3.2
Stochastic gradients setting
3.3
Memory-efficiet ALIAS
3.4
ALIAS with momentum
Experiments
Conclusion
10
Additional Experiments
16
A.I
LLaMA pre-training
16
A.I.I
Experimental setup,
16
A.1.2
Additional results
16
A.1.3
Comparison with parameter-free approaches
18
A.1.4
Experiments on big model
18
A.I.5
Compute resources.)
19
A.2
Tiny ImageNet classification with Swin Transformer Fine- Tuning
20
A.2.I
Experimental setup
20
A.2.2
Performance on Image Classification
20
A.2.3
Compute Resources
20
A.3
AlgoPerf benchmark
21
SIGN-SGD with Additional Stepsize Search Procedure
21
B.I
SOS SIGN-SGD experiments
23
B.1.1
Logistic regression.
23
B.1.2 Non-convex problem
24
Additional Notation and General Inequalities
24
Lemmas for SOS SIGN-SGD
25
Main Proofs and Details for SOS SIGN-SGD
28
E. Exact gradient setting
28
14

---

Published as a conference paper at ICLR 2026
E.2
Stochastic gradient setting
31
Distributed setting
36
F
Proofs for ALTAS]
39
Exact gradient setting
39
F2
Stochastic gradient setting
43
Distributed setting.
Memory-efficiet ALIAS
55
Steepest Descent
58
15

---

Published as a conference paper at ICLR 2026
A ADDITIONAL EXPERIMENTS
This section supplements our experimental validation by examining the internal mechanisms of parameter-free sign-based optimizers across LLaMA pre-training and Tiny ImageNet classification. We analyze how step-size dynamics naturally emerge without manual scheduling, investigate memory consumption and computational time compared established optimizers, and demonstrate robustness to hyperparameter choices.
A.1 LLAMA PRE-TRAINING
A.1.1 EXPERIMENTAL SETUP.
Our experiments use LLMMA-baan architecture (Touvron et al. 2023) equipped with RMSNorm and SwiGLU (Shazeer 2020) activations, trained on the C4 dataset (Raffel et al. 2020). The training consists of 100k steps. We use batch size of 512 sequences and sequence length of 256, as in Lialin ct al. (2023), and T5 tokenizer with the dictionary size of 32k since was originally trained on C4.
For all experiments, the respective optimization method is applied to the main model parameters, while the LM Head layer optimized with AdamW. This design follows prior work ZZao al. (2024) which showed that the LM Head layer requires more fine-grained learning rate adjustment.
The learning rate was selected through grid search with multiplicative step of 10 We employ cosine learning rate schedule with a warmup of 10% of the total steps and decay to 10% the peak learning rate. For ALIAS Adam version (Algorithm 3). we choose stepsize 7t 10-3
The weight decay value was selected from [0, 0.01, 0.1] through validation. We also applied gradient clipping with threshold of 1.0 for all methods except STEEPEST DESCENT and NORMALIZED SGD. All methods with momentum utilize the Nesterov acceleration scheme with momentum value of 0.9. For AdamW we use the standard hyperparameters: B1 0.9, B2 0.999, le 8.
A.1.2 ADDITIONAL RESULTS
In this section, explore key aspects of our method. We analyze the stepsize derived from approach and compare it to the effective learning rate induced by the cosine scheduler. Next, we ex- amine the memory and computational efficiency of all considered optimizers. We present ablation study on the approximation used in the stepsize of the memory-efficient variant, demonstrating its close alignment with exact computation. We provide empirical evidence for the robustness of ALIAS to an additional constant Loe term (see Remark 3.6). Finally, we discuss the question regarding the performance dependence on the choice of the initial value dd and the level of gradient noise.
Study on the stepsize. question arises regarding how 7
(d
performs compared
14
to the effective cosine scheduler when 7 remains constant. This pairing is presented in Figure
effective codine stepsize stheduler AUAS version Repsize
0.8
Stepsize
0.2
10000
Number of stochastic gradient calls,
Figure 2: Comparison of ALIAS Adam version stepsize with constant 76 with effective cosine stepsize scheduler.
16

---

Published as a conference paper at ICLR 2026
One state that the cosine nature of the stepsize is automatically obtained. This feature highlights the distinctiveness of our parameter-fie approach.
Study on the time and memory consumption. In Table we present details of memory require- ments and time consumption per-iteration.
Table 4: Comparison of memory and time consumption.
Algorithm
Memory consumption (gb)
Time consumption per-iteration (s)
SIGN-SGD
0.41
0.004
STEEPEST DESCENT
0,41
0.01
NORMALIZED SGD
0.41
0.01
ADAMW
1.5
0.007
PRODIGY
3.5
0.05
ALIAS (ours)
1.22
0.01
ALIAS Adam version (ours)
1.91
0.03
memory-efficient ALIAS (ours)
0.41
0.007
Table Ishows a higher time per-iteration for ALIAS Adam version and PRODIGY, which we adopt from the work (Mishchenko & Defazio 2023). We attribute this to the suboptimal implementation of these algorithms, in contrast to others that have been utilized for an extended period. Simultaneously, our algorithms are comparable to ADAMW in terms of required memory, while PRODIGY occupies more GPU resources because stores a vector initial model parameters. Note that the memory- efficient version of ALIAS is superior to ADAM and comparable the basic HGN-SGD.
Study on the memory-efficient ALIAS. We now analyze the memory-efficient vari- of ALIAS, focusing on the accuracy of the approximated -orm used in its up- date rule. Figure shows the dynamics of |[V Vx Ilso across iterations, along with the deviation range of its approxi- mation (see Section 3.3 for details the ap- proximation scheme). The ablation study re- veals that the approximate norm deviates from the exact value by approximately 50% on av- erage. Notably, the approximation consis- tently exceeds the true norm as expected, since it constitutes an upper bound by de- sign. This leads to smaller effective stepsizes, mance of the memory-efficient variant compared the basic ALIAS algorithm (Algorithm 2
0.022
0.000
mpxx ghx
0.002
20303
82000
103200
Number of stochastic gradient calls,
Figure Ablation study on approximated 4o0- norm deviation from the exact one in the memory-
efficient version of ALIAS.
which explains the slightly degraded perfor-
Study on the robustness to Loc. In T provide empirical evidence supporting the claim made Section 3. that the modification of ALIAS (Algorithm 2 is robust concerning the Tox parameter. Hence, although the ver- sion of the algorithm considered in Remark [3.6] requires prior knowledge of Loc. this additive factor has negligible impact on the practical con- vergence of Algorithm 2
Table Robustness Loo-
Lx value
Validation loss (L)
3.006
50
3.006
100
3.007
500
3.005
1000
3.006
Performance dependence on d' choice. In this paragraph, investigate the robustness of our ALIAS Adam version concerning the choice of the initial distance dº. To this end, we compare the performance of Algorithm 3 on LLAMA pre-training using d 1 and dd 10-3 3, In both cases, we obtain the same validation metric: validation loss = 2.918. Based on these results, we conclude that method is insensitive the choice of dº
17

---

Published as a conference paper at ICLR 2026
Performance dependence gradient noise. We investigate the dependence of the performance of our ALIAS procedure (Algorithm 2) on the level of gradient noise. To simulate different noise levels, vary the batch size. Indeed, decreasing the batch size increases the stochasticity and the variance of the gradient estimate, thereby leading to higher level of gradient noise. While in previous experiments we used batch size of 512 sequences, here we compare the validation loss on these runs. Table provides a pairwise comparison of ALIAS and SIGN-SGD across these batch sizes.
256, 128, and 64 sequences. Then
Table 6: SIGN-SGD and ALIAS with different bath sizes on LLAMA pre-training.
Batch Size (# of Sequences)
Algorithm
Validation Loss (L)
512
SIGN-SGD
2.980
512
ALIAS (ours)
3.006
256
SIGN-SGD
2.986
256
ALIAS (ours)
3.013
128
SIGN-SGD
2.992
128
ALIAS (ours)
3.021
64
SIGN-SGD
2.999
64
ALIAS (ours)
3.029
The experimental results demonstrate that, when the batch size is reduced - thereby increasing the level of gradient noise both SIGN-SGD and ALIAS exhibit comparable decline in performance. This suggests that ALIAS is not disproportionately affected by the increased stochasticity in gradient estimates, underscoring its robustness to gradient noise.
A.1.3 COMPARISON WITH PARAMETER- APPROACHES
In this section, we present an experimental comparison of our ALIAS Adam version algorithm with competing parameter-free optimization methods. For this additional evaluation, selected the following approaches: DoG (Ivgi et al., 2023), D-ADAPTATION (Defazio & Mishchenko (003)), and MoMo (Schaipp al., (2023). These methods chosen based on their performance reported in
the work (Kasimbeg et al. 2025) on the ALGOPERF benchmark (Dahl et al. 2023). Our validation
results for pre-training the ILAMA-based architecture are summarized Table
Table Parameter-free methods on LLAMA pre-training.
Algorithm
Validation Loss (L)
Perplexity (4)
DoG
2.939
18,897
D-ADAPTATION (with Adam)
2.927
18,672
MoMo (with Adam)
2.925
18.634
PRODIGY
2.930
18.727
ALIAS Adam version (wd) (ours)
2.918
18.504
These results complement our comparison against sign-based methods and ADAMW. They demon- strate that our approach achieves stronger performance than prior parameter-fiee methods.
A.1.4 EXPERIMENTS ON BIG MODEL
evaluate the methods on LLAMA with 350M parameters. The training setup remains consistent with the previous experiment. However, the number of layers in the model increases, leading to total parameter count that rises from 130M to 350M. This experiment is essential to demonstrate the sustainability of our approaches to increasing dimensionality. We conduct experiments comparing methods with and without the momentum parameter / along with weight decay. The results are presented Tables 8 9 and Figure
18

---

Published as a conference paper at ICLR 2026
Table 8: SIGN-SGD methods on LLAMA pre-training.
Algorithm
Validation Loss (4)
Perplexity (4)
SIGN-SGI (wd, Ir, cosine sc) SteepEST DESCENT (wd, Ir, cosine sc)
2.819
16.760
2.828
16.912
NORMALIZED SGD (wd, Ir, cosine sc)
3.510
33.448
ALIAS (wd) (ours)
2.821
16.793
Table 9: SIGN-SGD methods with added momentum parameter (3), ADAM (wd) and PRODIGY on LLAMA pre-training.
Algorithm
Validation Loss (J)
Perplexity (L)
SIGN-SGD (wd, 8, Ir, cosine sc) STEEPEST DESCENT (wd, 3, Ir, cosine sc) NORMALIZED SGD (wd, 3, Ir, cosine sc) ADAMW (wd, B, Ir, cosine sc)
2.717
15.135
2.711
15.044
3,460
31.817
2.719
15.165
PRODIGY (wd, 3, cosine sc)
2.715
15.105
ALIAS Adam version (wd, B, cosine sc) (ours)
2.707
14.984
Normall SCD oi
Mtreae poicent led coske oa
Acaeth let f. costrect
corrent
3x39
20000
40000
50000
30000
100000
20000
40000
50000
50000 100000
Number of stochasctic gradient calls,
Number of stochasctic gradient calls,
Sig-diooo lnd it cathess so horre land 5GD jes caina moin
Signdioo led & calhees
107
. Romeitee 5o0 lvs f.Y. cosre
Smappst Duscert led &
(erplelitty
6x11
Perplexity exiextty
ALAS Acam reabn
6-11
axcaal
20000
40000
43000
200000
stochasctic gradient calls,
Number stochasctic gradient calls,
Figure 4: Comparison SIGN-SGD methods on 350M parameters LLAMA pre-training. Left column is results for methods with weight decay and without momentum parameter 3, right column methods with momentum B.
The results are consistent with those obtained for the smaller model. Among the momentum- based methods, ALIAS Adam version demonstrates the best performance, while among the methods without momentum, ALIAS exhibits comparable performance other solutions.
A.1.5 COMPUTE RESOURCES.
We conducted all experiments described in Section A.I on the cluster equipped with 4xNVIDIA A 110 GPUs. A complete of 100,000 steps took approximately 12 hours using a full node.
19

---

input Published as a conference paper at ICLR 2026
A.2
TINY IMAGENET CLASSIFICATION WITH SWIN TRANSFORMER FINE- TUNING
A.2.1 EXPERIMENTAL SETUP
Our image classification experiments on the Tiny ImageNet dataset (Le & Yang 2015) employed the Tiny Swin Transformer architecture (Liu et al. (021). This lightweight variant of the Swin Transformer is characterized by its hierarchical design and the use of shifted windows for efficient
self-attention computation. The specific configuration utilized involved non-overlapping
patches and a 7 X window size for local self-attention
We initialized the model using pretrained weights from ImageNet- IK (Deng et al. 2009), specifi- cally the swin__ Ba_p_____tttttt_____ ch4 wwwwwwwwwwww.. 224 checkpoint provided in the official Swin Transformer repository [ The model was then fine-tuned on Tiny ImageNet.
The Tiny ImageNet dataset comprises 200 classes with images of 64 x 64 resolution. To meet the model's 's input requirements, images were upsampled to 224 224. A standard ImageNet-style data augmentation pipeline was implemented, including random resized cropping and horizontal flipping.
Training spanned 50 epochs, with batch size of 256. The learning rate determined via grid search, employing multiplicative step of 10 A cosine learning rate schedule was adopted, featuring a linear warm-up phase for the initial 10% of total training steps, followed by decay to 10% of the peak learning rate. Weight decay was selected from {0, 0.01, 0.1} based on validation performance. All optimization methods incorporated gradient clipping with threshold of 1.0. When momentum was applied, Nesterov acceleration with coefficient of 0.99 was used. For AdamW, the standard configuration of 31 = 0.9, $2 0.999, and 10 was maintained.
A.2.2 PERFORMANCE ON IMAGE CLASSIFICATION
Further results and training curves for the Tiny Swin Transformer on the Tiny ImageNet classification task are presented in Figure 5 and Table TO We provide plots for the same methods with the incorporated momentum parameter as for the LLAMA pre-training task.
Accuracy
Accuracy
-2
74
Epochs,
Epochs,
Sign-SGD terl constant
Descent (wid, cocoeel
Prodioy (wd, B. cosime))
Sign
Normaiized SGD (wd, & cosine
Prodigy (we. B. constant
ALAS Adam version tod, B. cosine)
Figure 5: SIGN-SGD methods with added momentum parameter (9), ADAMW (wd) and PRODIGY on SWIN fine-tuning. Left plot represents full process of training, right plot demonstrates accuracy on last 20 epoch.
The results demonstrate the superiority of our algorithms over both tuned methods and advanced optimizers, such as PRODIGY and ADAMW.
A.2.3 COMPUTE RESOURCES
We conducted all experiments described in Section A.2 using single NVIDIA A100 GPU. complete run of 50 epochs required approximately 3 hours.
20

---

Published as a conference paper at ICLR 2026
Table 10: Final accuracy of SIGN-SGD methods with added momentum parameter (3), ADAMW (wd) and PRODIGY on SWIN fine-tuning.
Algorithm
Final accuracy (1)
SIGN-SGD (wd, 9, Ir)
77.045
SIGN-SGD (wd, 33, Ir, cosine sc)
78.885
NORMALIZED SGD (wd, B, Ir, cosine sc)
78.375
STEEPEST DESCNET (wd, B. Ir. cosine sc)
77.547
ADAMW (wd, B, Ir, cosine sc)
77.612
PRODIGY (wd,
77.035
PRODIGY (wd, P3, cosine SC)
77.944
ALIAS Adam version (wd, (3 (ours)
77.433
ALIAS Adam version (wd, B, cosine sc) (ours)
79.161
A.3 ALGOPERF BENCHMARK
In this section, we evaluate method some tasks from the ALGOPERF benchmark (Dahl et al. 2023). To test our approach across different modalities, we chose the MRI reconstruction and molecular property prediction (MPP) tasks. We preserve the original setups from the benchmark implementation"" Specifically, for the MRI reconstruction task, we use the fastMRI dataset and a U-Net model; for molecular property prediction, utilize the OGBG dataset with GNN model. We validate only our ALIAS Adam version algorithm. The results for the other methods are taken from Table 4 in (Kasimbeg al. 2025), which reports comparisons between parameter-free optimizers and tuned ADAMW W. For our method, we fix 7 = 10-3 The results are presented in Table
Table 11: Parameter-free methods and ADAMW on MRI reconstruction and molecular property prediction tasks.
Algorithm
MRI, SSIM (f)
MPP, mAP (f)
ADAMW
0.723
0.254
DoG
0.714
0.231
D-ADAPTATION (with Adam)
0.722
0,221
MoMo (with Adam)
0.723
0.221
PRODIGY
0.723
0.212
ALIAS Adam version (wd) (ours)
0.724
0.242
The results demonstrate that approach improves upon the metrics of prior parameter-fire methods on the evaluated tasks. We also note that, for the MRI reconstruction task, the performance of our method surpasses that of the tuned ADAMW.
B SIGN-SGD WITH ADDITIONAL STEPSIZE SEARCH PROCEDURE
In this section, present algorithm that achieves near-optimal convergence rates for SIGN-SGD - - - A' in the deterministic case, and مياا + || in the stochastic case. The method
does not utilize prior knowledge about the parameters the problem and incorporates an additional automatic stepsize search procedure.
Exact gradients. design the necessary algorithm, we should provide stepsize y in Algorithm
I that yields an estimate as in equation [ Let us begin with the description of the approxima- 0ir
tion of the stepsize that we utilize. We establish that the desired value is Dyr' where
My Är f(x²) minogrer (xx') is the numerator and Dr ( -f(=")))
https://githhe thub. wwm/m/
SETTING NWTTINGG_TTOE SES__STTRTEDD...
21

---

Published as a conference paper at ICLR 2026
is the denominator. The intuition behind this choice is that due to 1 we have Dr Lox Ei=o | - 100 = 7o Ei= ||ignn (V/(z)))l Loo T: then ? has V magnitude. However, we face a more complex situation compared to the regret minimization paradigm: in our case, Ây can be non-negative (in regret minimization, the analog of Aq is the norm of the points' difference ||.00 x² Carmon & Hinder 2022) which is always positive). To address this, we add an extra step to the SIGN-SGD algorithm. Define e sign (x)(x)))) Let T be a small parameter. The update is:
yār
f(x)) min {f(x
(4)
The rationale behind selecting the step is follows. Due to the smoothness of the objective function, there exists small neighborhood around any point within which moving in any direction decreases the objective value. The exception arises when x= is the minimum itself. In this case, the sign descent algorithm would not take any steps, and we return this point as the solution. Since the neighborhood size depends on Los, we iteratively decrease until it is sufficiently small. The choice of T and the guarantee f(x") < f(x=1) are discussed in Lemma D.4 In this manner, we ensure that My = År fx==') min-1 f(x²) O. To prevent the denominator from being zero, we introduce a small constant (. which represents the minimum gradient norm encountered during learning. This leads to Dy = Σi= [)(x*+))) V (x=) + (see Lemma D.2 for details). However, determining these values necessitates completing all T iterations. address this, we employ the BISECTION procedure from (Carmon & Hinder 2022) which is outlined in Algorithm
Our goal is to have y <(>) = ]r(())
Algorithm 4 BISECTION procedure
Dr(s)' To find such 7. we take an ini- tial interval ht. Phil and, it- eratively narrowing it, ob- tain a small enough interval (766 %il that contains the w-)(>> point. To per- form this, firstly have make sure that the initial in- terval contains the desired point. For this purpose, we require Thi > ((Tai) and No < 6(%)). We desig- nate the group of these two requirements as the bisec-
1: Input: Optimal stepsize value d(7), lower stepsize bound "oo.
upper stepsize bound This x=1 E Rd number of iterations T
2: <(7) (it is always in the form ((7) Dr()))
1r(2))
if 7hi & ((hni) then return oo // Early infinite termination
4: end if
if Tho o(Tia) then return The 7ho // Early non-infinite termination
6: end if
while "hi > 2 do
8: "mid naa
9:
Mr Dr((mim)) + SIGN-SGD(2=1,77 7mia) // First
step in Sign- is made by equation $
10:
if' Timid & (((mmi)) then
11:
noo = 7/mid
12:
else
tion start condition (Lines
13:
Thi = "/mid
3 5)
Note that we can al- ways satisfy the first condi- tion, as shown in Lemma D.2 Regarding the second requirement, we can choose a sufficiently small initial No value. Even if no is still greater than @(11), we can select this no value as the desired stepsize with- out performing the BISEC- TION procedure, thereby obtaining optimal conver-
14: end if // Bisection invariants: Noo <, ((T1)), mm >> 6(7m)
15: end while // Bisection stop condition: "Ihi % 2%
16: if (T(())) < My (%1o)
@(m)) then return 7/1 = Th 1 return "he
condition
17: elsereturn 7ha 7ho // Noo return condition
18: end if
Algorithm SOS SIGN-SGD
I: Input: Initial stepsize bound 7.. initial bound step k; start point Rdd, number of iterations T
2: 70 BISECTION ((77), 72.22 7,.T)
3: xT SIGN-SGD 1,, To,
gence guarantees. This is
This enables us to avoid early infinite termination (non-compliance with the first condition) and prevents convergence from being compromised by early non-infinite termination com-lcomleancee with the second condition). Additionally, ensure that, by entering the procedure with the desired point between Yoo and Yhi it remains invariant throughout the procedure. Indeed, at each iteration we compute Timid as the geometric average of the bounds and perform T iterations of the SIGN-SGD method with this
demonstrated Step 2 the proof of Theorem B. (Theorem
22

---

Published as a conference paper at ICLR 2026
It remains for to choose such part of the segment (N Y or (Ymidd (hmlld"hul) in which (imid) lies (Lines 10 [4]. We perform this bisection, until "hi exceeds "o by more than 2 times (Line 77. In the end, by utilizing return conditions, the procedure returns 7o or Thi (Lines T6
stepsize find ((Ymii) (Lines 8
18 They satisfy the specific bounds explored in Lemma D.3
Using this procedure, we present description of the SOS (Search of the Optimal Stepsize) SIGN- SGD (Algorithm(5). Before we pass to the convergence rate, we discuss the number of iterations required by Algorithm | Since we calculate the average geometric each iteration, we need log log 2h steps, where "T and "Ti are the boundaries of the initial segment. Thus, according to
Algorithm it requires log log 2" 24 k iterations. We establish a lower bound on & by requiring
that the initial "hi is greater than < (mha). According to Lemma D.2 Thi should be at least [+="i> In this way, k = log log [[>]i> Therefore, allowing Algorithm to perform iterations, the total number of iterations (considering Algorithm performance time) T log log
A
We
V
regard this additional Nouble-logarithin factor as negligible, it aligns with the results in (Carmon & Hinder 2022). We now present the main theoretical result of this section.
Theorem B.1. Suppose Assumplions 3.7 3.2
hold. Then Algorithm after obtaining the
stepsize to the following estimate is valid:
T
V
3
Vf(291
[f(x*)l &
T
VT
T
Moreover, laking into account the complexity of Algorithm f in relation to the initial stepsize bound Yo reach E-accuracy. where > + Et IIV Algorithm 5 needs
Loc g2
iterations.
Discussion of the results. We obtain the near-optimal convergence rate [ Our method retains dependency on the initial approximation. Indeed, we should take 7 be less than T. according to Step 2 in the proof of Theorem B.I (Theorem E.2). An analogous requirement was established in the work (Carmon & Hinder 2022 and we do not consider this to be an issue. Nevertheless, despite the theoretical optimality of the proposed approach, its practical application not promising. Launching multiple training sessions on large models does not appear effective. In this context, Algorithm 2 remains our main contribution. While proposing Algorithm [5) we demonstrate how to obtain the near-optimal rate for SIGN-SGD in parameter-free optimization.
Stochastic gradients and distributed settings. The description and analysis of Algorithm 5 in stochastic and distributed setups can be found in Appendix E.2
B.1 SOS SIGN-SGD EXPERIMENTS
B. LOGISTIC REGRESSION.
We present toy experiments on logistic regression. We provide comparison of SIGN-SGD with the theoretical stepsize 1 (Algorithm) SOS SIGN-SGD (Algorithm 5), ALIAS (Algorithm 2 and
VT
STEEPEST DESCENT (Algorithms)
8 We validate the criteria [ on four datasets sourced
from the LIBSVM library (Chang Lin 201 a 99, w8a, ijenn1 and skin-nonskin. The results presented in 6
The plots show that even on the convex problems, SOS SIGN-SGD performs worse than ALIAS. This was expected, however, testing this method on real non-convex problem, such training LLMs, lacks justification. Additionally, is noteworthy that STeepEST DESCENT performs worse compared to SIGN-SGD, highlighting the limited practical applicability of this approach. Consequently, provide analysis for STEEPEST DESCENT only with incorporated Algorithm in Appendix We do not focus the analysis and development of efficient parameter-free methods based on this approach.
23

---

Published as a conference paper at ICLR 2026
DIOLE NEY
Nen
DrTE Sgt MIO
D-O
Sirgpeon Descort
ALAS Sp--0G
AT
Sumppe Descert
Staspon Coccor
ALIG Spn-500
Stouper Dopcort
ALAS Sp-SCD
(a) a9
(b) wBa
(c) ijennl
(d) skin-nonskin
Figure SIGN-SGD methods on logistic regression.
B.1.2 NON-CONVEX PROBLEM
We provide the comparison of SIGN-SGD with theoretical stepsize J SGD (Algorithm []. ALIAS (Algorithm 2 and STEEPEST DESCENT (Algorithms 8 9 We validate criteria [V(x=")] [ on four datasets, sourced from the LIBSVM library (Chang & Lin 2011): a9a, wBa, i Jinnl and skin-nonskin In the main part we presented the results for the convex problem. Now we consider the non-convex objective, namely the non-linear least squares loss:
VT (Algorithm SOS SIGN-
f(x)
yi exp (-a
(5)
There denote a; E iglxd the sample and yi E 10 as the target. The results are presented in Figure
Ditkat Sgn-50 Al AS sin Mirepont Desioved
DETaUE Sig
Delak Sg0
Detkat Sgy500 ALDS 90D Strepee Decrrve
FILAN SELD Viregend Desirntt
ALASS New 106 Siceani Destove
(a) a
(b) w8a
(c) ijcnnl
(d) skin-
Figure 7: Comparison of SIGN-SGD methods on problem equation 5
The plots demonstrate the superiority of our methods, SOS SIGN-SGD and ALIAS, over classical SIGN-SGD with the vanilla step size choice /T This highlights the importance of adapting the stepsize the problem structure and hyperparameters. However, SOS SIGN-SGD still underperforms compared to ALIAS.
C ADDITIONAL NOTATION AND GENERAL INEQUALITIES
Notation.
Here we present the full list of notation, used in our paper.
We denote d as the dimension of the problem; 7 the total number of iterations the algorithms; as the starting point in the SOS SIGN-SGD algorithm, x as the starting point in the ALIAS algorithm; zt as the point at f-th iteration the algorithms; x² as the optimal solution of the [(x';; A =(= (x*) for the SOS SIGN-SGD method,
problem; Ä = f(x-1)- -ISIET
min
f(x0) f(=²) for the ALIAS method.
We denote V fxxt) as the honest full gradient of the objective function the point at; g" (or gt as the stochastic gradient of the objective function the point æ', according to the stochastic realization gt (we add lower index only when we use different stochastic realizations in the method); of (or gf.se)
the stochastic gradient of the objective function the point z' j-th device in the distributed setup, according to the stochastic realization gt.
For vectors x, y IRd we denote sign(::) the vector of the dimension d, where the i-th coordinate
24

---

Published as a conference paper at ICLR 2026
defines
1, if >
(sign(=)], sign(2;)
0,
x; 0:
if x4
d Σ Fiys is the scalar product; ||a|| |xs is l 1-normm; ||e||
d Σ
(r,0)
x is 1o-norm;
| max an is nnomm.
iel, For a random vector ç E R.d and fixed vector Rd we denote [c] the expected value with respect to random vector & and IE (Elvb) as the expected value with the respect to random vector conditioned on the fixed vector tb.
General inequalities. Suppose y E Rdd a. b. E IR, f()) is under Assumption 3.1 and &, s R+ are random variables. Then,
[V[(2) - VS(W)ll
Lxa| - -lloo
(Lip)
1 + ell
||=|| + Illll va+bs Va vb
(CS)
(x,
||=| llyllo
(Conj)
E [gv]]
(E (EP) (B
1 where
=1
(Höl)
p 9
D LEMMAS FOR SOS SIGN-SGD
Lemma D.I (Quadratic inequality). Let x E RR+ be a variable and u, E RR,, be constants. Then x² U & 0 implies & u u Vū. Additionally, x² ur u & 0 implies Vu.
Proof. Since u, are non-negative constants, the plain algebra involves Tsp. = w a being stationary points of 2ur v & 0 inequality. Since x the positive variable, the boundary spp is the appropriate area of the solution. remains for us say that
2
1 r < 2²
22 4
u
VT,
which finishes the proof of the first statement. Proceeding analogically for the second part, we obtain x < fu + vv + du < - + ju Vo
Ve.
Lemma D.2 (Bisection entry). Let Timax (Grdd[((>)) or Timax
for dis-
(G"))
tributed setting
where A = 1(= and the gradient oracle Grad( can be specified
f.)) g(-) 9j (.), that depends the algorithm setting (exact gradient, stochastic gradient or gradient on the i-th node distributed setting). Then we can always entry the bisection procedure without infinite early terminations taking "hii "imax-
Proof. We can entry the BISECTION procedure, when Thi > d(ma). Thus, to proof the lemma statement we can show that Thi < <(m)) is impossible, when Mhi > 7max [+))] Using
Â f(x f(x-1)= -IStET
min fxx") notation, we consider
(r(m) Mm((N)) 6(mm)) > 2 7max
(6)
(r(mi)
Dr(mn)
25

---

Published as a conference paper at ICLR 2026
Let us look at the numerators of the fractions in the obtained inequality. According Assumption 3.3 f(x²) < min f(x'. ). In that way.
(7hi)) $ A"
Now we consider denominators in equation
6 Pr(hi) has the following form in any setting:
IM
(G** (fx" ((hh),, where ((y) is defined as the minimum of
gradients norm over the training: {(7)
min 06 1ET
[]r (ra))) Using equation CS we obtain
(faad((()))
[radd[ (nt) Grad(f( + (|Gra)))))))//G((((((( ([ (e (7n))
[frad (fr [[ (cai))l
[Grad( (mi)) (fa)))(
+ min [
0E
(184)
(frad(f(z
+ ((%i)
(rta))
(8)
where inequality (i) holds for any 1 & & T and in (ii) we choose 7 = arg min [] (rmn)) oEtET
One can note that omit the case when the norm of the oracle reaches its minimum iteration = 0 in ( definition, when use it in (iti). However, it is trivial case and it satisfies
[G=ad(((=)))]l & ((mi)
(] (mm) (x"())))""))))) + ((mi) = Dr(mn).
In that way, combining it with equation and equation we obtain
Ar(hi)
Dr [frad(fxx
which contradicts equation 6 Thus, we entry the Algorithm 4 without infinite early ter-
Note that for the distributed case we can obtain mination if take initial Thi least (
Grad (f(*9) Dr (Ya) in the same way as in equation &
Lemma D.3 (Bisection invariants). If The BISECTION procedure (Algorithm has no early termi- nation all, it relurns "Io such that
Mr <
Rr((())
(9)
PD
Dr(10)
where The and The values, from which "0 is chosen in the end of Algorithm
Moreover.
Mr(7o) < (rtr))
(10)
Dr(1)) < (7
(11)
Proof. Consider the case procedure returns 70 7%- Then
N7 (T
MT(x))
Mr(1))
Mr(T))) (y)
(6)
((7)))
2 Thi < %o
2Dr((/)))
20,, (m)) Dr
26

---

Published as a conference paper at ICLR 2026
(186)
My (
(
(12)
Dr((i)))
where (7) is correct due the Nt return condition, (ii) bisection stop condition, (iii) bisection invariant. Consider the case when procedure returns "Yo Thi- Then
1 2 2 (
My (1i)
( 1 2 2
(() Mr D7(
(13)
where (i) is correct due to the bisection invariant and (ii) Thi the return condition. Combining
equation 12 with equation 13] we obtain the first claim of the lemma whether Algorithm returns
To % "oo 7he It remains to notice that equation i2 is followed by Dr(1)) & (T(ii)) when
70 = Tho and, consequently, (700) < Dr(()) since Dr(*)) & (m()) is trivial. Analogically,
equation 13 is followed by Myp(hi
(r(h)) when 70 Thi and, consequently, (7
(1())) This finishes the proof.
Lemma D.4 (Extra step). Suppose Assumptions 3.1 3.2 3.3 following form:
hold. Then, considering update of the
f(x²) = min {f(x + fe), -re)),
where e is the random vector from the unit basis, and we can guarantee f(x") < f(x when
Moreover, Algorithm 4 starting with T Ta and performing T 2. needs least extra iterations to find efficient value of T.
Trou
log
Proof. We choose f(x") min
re)}. We use convexity to show
fx + TE)
<
[(x + (V
f(x ( VV Vf(x
+ / Vf(2 ))1,
\) ||e/lo
( Loo lella.
f(x tE)
- -V-
1(x (V/(x= (V - Te) - V5(x (((=)))) ))
f(x11) - <V ),)) + Vf(x rE) vf(z (|)0=))|| ||0/00
Lip
- - (V )) 7 1e/l3.
Utilizing sign 1)), we take expectation and obtain
f(x0) & f(x 2) V e) + L ||e|
d
= 11x
Σ [[ fz 111 + +
sign
& f(x
[ ||1 + T2
f(x 7 (lv (1 |1>|= -Looo
[ 1 Loe
In that way, if we have
we derive
f(x") f(z
Since in the algorithm we start with r To and divide it by 2, after I divisions, we have
V vf(x ||1
Leo
Thus, we need at least / = -log
To [IVV7( MTT
iterations.
27

---

Published as a conference paper at ICLR 2026
E MAIN PROOFS AND DETAILS FOR SOS SIGN-SGD
E. EXACT GRADIENT SETTING
Lemma E.1 (Descent lemma), For Algorithm estimate is valid:
under Assumptions
3.7
3.2
3.3
the following
T-1 Σ
f(x )(aa")
T-1
[V
Σ
-
70
Proof. Starting from the convexity the objective,
/( f(x')
< (V x't1 -x¹) --- (V](x sign (Vf(z')))
Vf(x²)) sign (Vf(z()))
(f(x*+1 vf(x') sign (Vf(x')))
Con
~VVV/( || + V/(2')/ |sgn (VS(x') ao
~>IV(> )| + + /VV/ v/(2")l
Now we express the gradient norm and sum over all iterations to obtain
T-1 - s((t)))
>((Vs(> &
( VS(x')ll
1=
-(=9) f(x2) +
Σ 7'IV -
Using Lemma D.4 to consider the extra step, get
T-1
[(x
Σ
-
Since Algorithm 5 performs all the steps with the constant to which define later, we rewrite the result in the following form:
f((=))
T-1
Σ IVf('')l
+
(f('')
70
O=
t=
which ends the proof of the lemma.
Theorem E.2 (Theorem B.I]. Suppose Assumptions 3.7
3.2
3.3
3.4
hold. Then Algorithm
after obtaining the stepsize Yo. the following estimate is valid:
T-1 Σ
V
3
|
[VS((*)| &
VT
T
Moreover, taking into account the complexity of Algorithm 4 in relation to the initial stepsize bound
Ys reach e-accuracy, where [V('')],, Algorithm Snedds
A A
log log
iterations.
V )
Proof. Let us start with the result of Lemmal E.1
T-
f(x
f(xT)
T- (1) -v/(x))
<
7o
t=
t=
28

---

Published as a conference paper at ICLR 2026
T-1
Σ t=
[V((att)) - v)(x"))l,,
(14)
where ÂT f(f
min IETT
f(²').
Now, we accurately estimate the last term in equation 14
which is additionally denoted as Pr Σ ||
Vf(x))) )h. Thus,
T
Fr
-
1|1
Lo
|| ++
x21000
10
t=
Loo
IIsign (Vf(x') 1o00
Loo
Σ
7
(15)
t=0
t=
Now let choose (77), which we push into the BISECTION procedure (Algorithm 4 <6<))
m(a) År(z)
Fr(t)+((n)) where Â. = f(= -T
min f(x") and 0S
min
fv'(x)))] In that way.
②(7)
we obtain some Yo. which can be equal to nh or Th (see Lemma D.2 Lemma D.3 and use as
constant stepsize for our method. Thus, equation 15 transforms into
Fr(1o) & T.
(16)
Mention that, according Lemma D.2 termination. that way, we have two situations: when we have no early terminations at all and we under the activity of Lemma D.3] and when have early termination with initial %% We divide the following proof into two steps, where we separately show the convergence guarantees in this two situations.
always entry to the procedure without infinite early
Step 1: no early terminations.
Since we have only two cases: "o = Ni or "Yo This let us consider them separately.
Yo equation 16 transforms into
Lemma D33 9 My (7mn)
(1)
(r( Lox.T
(r < The LooT
Looo T
Dr (
Fr((H) + ((7)))
where is correct due to the ((>) choice. Solving this quadratic inequality with respect (r(())
(Lemma D.I., we obtain
Fr(Mi) & Ar VT
(17)
where A f(x-1) - (xx) Plugging it into equation
14
we obtain
1 (r(in)
V (z())l1
+ T (Thi))
T Thi
0=0
Lemma D.3
1 22
1
Ar
Fr((hh)
T
Mr(M)))
T
2 (F(()))
+ <((hii)) Ar(Ti))
+ 3 Fr((i)
T
Ar(1))
3
2((7)))
Fr(2n))
+
T
T
2 ||(\((>))||
(18)
VT
T
In that way, equation 18 is the final estimate when BISECTION procedure returns 76-
To % equation transforms into
My (7i))
Ar(
Fr (ri) & Loo
LOOT
T
Loo
Dr (7ih)
Fr(1i) + (((
29

---

Published as a conference paper at ICLR 2026
where (7) is correct due to the (67) choice. Solving this quadratic inequality with respect (r(t)))
(Lemma D.I), we obtain
Pr(nf)) & V Ar & To..
(19)
Now we make an additional distinction and consider the estimates separately: one case when A
no LaT and another when %h L We can do this without any limitations, since combining the intervals considered for % returns all possible values.
7o
straightforwardly move the equation 14 estimation:
Σ T t=
1
1 Ar(
1
Fr(1%)
T
%o
T
Trgo
1
(r(TT))
Fr((1r))
T
T
A
V
Lox
(20)
VT
No E
in this case, we start from the estimate that followed by equation 16
T T
Fr(ai) < Too & Loo & LTT
(21)
where (i) is done due to the bisection stop condition. Now proceed with estimation of equation
14
1 (T(1))
+ T FT(())
T t=0
T
To
Lemma
9
1 22 (1hi)
(r(1H) + 1
T Fr((()
T
Lemma D 11
2
(Fr())))
+ <(T)i)) (T(1)))
+ Pr(mit) + ((m))
T
(r(1))
T
3((%))
T
T
A
3((mm)
TT
T
L
3
(22)
VT
Combining equation 20 and equation 22
we get that equation 22 is the final estimate when BISECTION
procedure returns %ie In the end, equation 18 and equation 22 give us the estimate in the case when BISECTION procedure does not have early terminations at all and outputs any value of yo:
V VT
3
T Σ IVf(())
<
+
(23)
T
Step 2: early termination with no-
Now we consider the scenario when with initial Tio there is 7o > )b())) and algorithm early returns
no- To dissect this, we should choose initial Nho 7 & A.
T. Thus, equation 16 transforms into
Fr((f) < no Too T & / AT.
(24)
In that way, equation
14 turns into
T
Ar(
<
+ T PT(()))
T
The
30

---

Published as a conference paper at ICLR 2026
1 Ar(
1
(r(()))))
T
((1i))
TT
(P(()))
+ (((io))) (nto)o
1
T
(T
T
(n
((1)))
21
L
[[
(25)
T
T
Hence, equation 25 delivers the estimate, when Algorithm makes an early termination.
Combining equation 23 with equation 25 we finally obtain the estimate for all possible cases of the BISECTION procedure return:
T-1
A
3 V
(co((( &
T
VT
T
Expressing the number of iterations and using >
[V || as criterion, we obtain that
|V
algorithm needs O L' iterations to reach e-accuracy. Note that we drop the term T
since it is asymptotically smaller than the main one.
However, we firstly need to find the step to with the bisection procedure which takes 7 log log
7.22" - 0 iterations, where
2 denotes the length of the initial interval for the stepsize. We have already discussed in the main part that, according to Lemma D.2 should be at least = log log |[][|]] Thus,
Le log log (.())))))
is the final iteration complexity.
E.2 STOCHASTIC GRADIENT SETTING
Let start with the description of the stepsize choice for stochastic version of Algorithm The main purpose of the BISECTION procedure (Algorithm 4 is to find stepsize y close enough to the <(>) desired value utilizing small number of sign descent launches. Recall establish
år(7)
( ΣT-1 Vf(x++1) f1(x)))1++((
for the exact gradient case. The numerator can remain unchanged. However, since we lack ac- cess to exact gradients, cannot use the original denominator. Instead, we employ stochastic oracles: Dr(7) = EnD [[g(x*+1)- g(x')l) [I + <(>). Other details remain the same, and we can
straightforwardly pass to the convergence results.
Lemma E.3 (Descent lemma). For Algorithm under Assumptions 3.1 estimate is valid:
3.2
3.3
3.7
the following
T-1
[V((*')]1 < -(a-))
T-1 - 9 + 38" 8
Σ
l1g 1g
70
T-1 where 8t = E [Vf((*)) 96
Proof. Starting from the convexity the objective,
f(x(+1) f(x²)
(Vf(xtt),, x' 2²) (Vf sign(()))
-0' sign(g")) - -V gt sign(g"))
11l - n (Vf(z') sign(g"))
(1) v signgg))))
C003
31

---

Published as a conference paper at ICLR 2026
+y + - 96 + +>'l)f(<=)> - I'lli|ssign (g') 1lo0
- (g') 1l
+ +// 9' + +~ - g
+
Now rearrange terms and summarize over all iterations to obtain
T-1
T-1 -
Σ
- 1(xlt1)] + Σ Al -
T-1
+3
/VV - اا'l +
V((+)(( - -
Since Algorithm Algorithmmpperfrme performs all the steps with the constant rate yo. which we define later, we can rewrite the result in the following form:
[f(x*) ((a)))((++t1))
f(x
Vf(2')ll
l1g -9'll1
70
T-1
+3
(Vf(2) -
VV - 41 111
the obtained estimate the last two terms consist from differences between the honest and stochastic gradient the t-th and (t + 1)-th moments. One of our goals is to estimate them, however,
want perform analogically to Theorem and continue the proof with the M llg g' term
[|2
estimate. In order to simplify following writing give additional notation and denote 8*
[f(x*) gf Il.. In that way, additionally considering the extra step (Lemma D.4), we derive
[VS(=')ll < 1(x - f(x")
T
llg ++
111 + 30 6
70
2=
which ends the proof of the lemma.
Theorem E.4. Suppose Assumptions 3.7
3.2
3.3 3.7
hold. Then for Algorithm 5 using at t-th
iteration mini-batcher of sizes + 1, after obtaining the stepsize No. the following estimate is valid:
T-1 Σ R[V(((")) &
A
3E
11
+ 10
VT
T
Moreover, taking into account the complexity of Algorithm 4 in relation to the initial stepsize bound Yss reach e-accuracy, where 7 [V |1, Algorithm
needs
(A7
A Lox c
||ا|3
log log
iterations.
7s 1
Proof. Let us start with the result of Lemmal We transform due to the fact that Algorithm performs all the steps with the constant rate To. which we define later:
f(x 1) f(x²)
Σ |[V
llg 1-
9011 + 35" + 8++1
A T
T- 1
1 1+
g" 1011 + 35* + 8
(26)
70
t=0
32

---

Published as a conference paper at ICLR 2026
T-1
where Är - 1 min
((*)).
Now, we focus on estimating Gr =
Σ
11g -ggli
term
-IE'ST
1=
in equation 26
Thus,
T-1
T-1 Σ [Vf - 1'1l2
Gr
11g
x+
g01l2
[ -
+
100
V vf(x9)11
8 +0 + Loc
|| x 21110
8 + 88411 + Loc
>Issign (V.f(z+)) 1l
T-1
< + ge41 + Loc
(27)
Now let us choose p(7), which we push to the BISECTION procedure (Algorithm 4 p07) = 2( =
91(0)
(r(1)+((7)* where ÄT = f(x ) min f(x') and Ç min |lg')l1- In that way, we obtain
(r())
-E
05
some "oo, which can be equal to % or The (see Lemma D.2 Lemma D.3) and use as a constant
stepsize for our method. Thus, equation (2 transforms into
Gr(10) < - T.
(28)
Mention that, according to Lemma D.2, we can always entry to the procedure without infinite early termination. In that way we have two situations: when we have no early terminations at all and we are under the activity of Lemma D.3 and when we have early termination with the initial % We divide the following proof into two steps, where we separately show the convergence guarantees in these two situations.
Step I: no early terminations.
Since have only two cases: no J/u 70 = The let us consider them separately.
7o The equation 28 transforms into
(
GT(Ti))
<
8 8-1
+ Mhi Too0 T
5 5t+1 +
Tooe
Dr (Tm))
i
8' 8
(r
LooTT < E² + 8++1
AT(
Loo T,
Gr + ((1m))
Gr(())))
where (i) is correct due to the (b7) choice. Solving this quadratic inequality with respect to Gr(( (Lemma D.I), we obtain
Gr(Ti)) < 8 + ge+1 + (o 8 + g ALLLoTT
(29)
where A = f(x - f(x)). Plugging it into equation 26 we obtain
1 AT(TH)
1
(r((hh))
T (35' + 55441)
1
T
Vii
T
t=
1 Lemma D33 9
1 2Dr
Ar + -
1 Gr((h)
+ - -300 +
T Mr((1))
2 (rr(hi)) + S(1i)) (r
1
Gr((in)) + - (36' + +(+11)
+
T
Ar(Ti)
T
2((rm)
Gr Gr(m))
+ T (36' + +5(+1)-
+ T
T
33

---

Published as a conference paper at ICLR 2026
28D
VA
(60' + 18
-
2 211g%) 48
3
(30)
T
In that way, equation 30 the final estimate when BISECTION procedure returns Yii- 70
No equation 28
transforms into
Lemma
D.30
My (
Gr(
<
8
No 100
6 +
Lox
Dr
!
8' 8-11
(r Gr(T%)) + ((7%))
Lima & 8r 8 Ar(
Loxe T
Gr(
where (f) is correct due (()) choice. Solving this quadratic inequality with respect to GT(1))
(Lemma D.I), we obtain
Gr(TG) < 8 + 8
(ār(T)LLT < 8' + + V..
(31)
Now we make an additional distinction and consider the estimates separately: one case when and another when %i < Time We can do this without any limitations, since combining the intervals considered for Th returns all possible values.
No T T
straightforwardly move the equation 26 estimation:
L
Ar (16) To
1
+ - T
fll''ll
-r(Th)
7380 + +0t+1)
T
TTx À (1%) + 7 Gr(1%) + 7330' + 80t1)
V
L
VALL + = + +0
VT
VT
Lo
7 (48' + 28+
(32)
VT
No &
I T
A in this case we start from the estimate that is followed by equation 28
Gr(YM) < 8' + gc+1 + T & 8" g-+1 + 2oo & 8' + 5++1 + T
(33)
where (i) is done due bisection stop condition. Now we proceed to the equation 26 estimatiion:
(r(T))
1 Gr(1))
1 (35' + t
T
T %o
T
Lemmn
D.3
2DD(mi)
(T(Ti)) + cT( 1 =3300 0
M)(
(Gr(hh) + ((1i))) Ar(1)))
Gr + ((16i)
+ T
T
Ar(1))
1
138" + +8tt1)
3GT(1i))
+ (38' + 3((%))
LA
+ T (60" + +40++1) + 3((1h))
VT
T
T
3 3119²
(65' +48++1)
(34)
VT
T
Combining equation 32 and equation 34 procedure returns 7
we get that equation
34 is the final estimate when BISECTION
34

---

Published as a conference paper at ICLR 2026
In the end, equation and equation 34 give the estimate in the case when BISECTION procedure does not have early terminations at all and outputs any value of yo:
1 T-1 Σ IVf(2')l < Vo-Lo VT
+ 7 +0 3 3110%1| 1
(35)
T
T
Step 2: early termination with no- Now consider the scenario when, with the initial No. there is no ((m)) and algorithm early
returns %o. To consider this, should choose the initial No - No & T transforms into
A
Thus, equation 28
GT(T & 8' + 8 + NoLOoT & 8 + 8 + v A..
(36)
In that way, equation 26 transforms into
(r(H))
T GT((b)) + + -
T Ni
1 Ar(
1 + - 7330' -
1
T Gr((1))
T
o(%%))
1 [GT(11))
+ ((Tio) Ar(TiO)
1 -
+3300 + +8t22)
1
+
T
(r(Ti)
2GT(11))
T (30' + +8+1) + ((7%)
1
T
36
V Lo
1 T (58' + 38++1) ||00|1
(37)
T
In that way, equation 37 delivers the estimate, when Algorithm makes an early termination.
Combining equation 35 with equation 37 BISECTION procedure return:
finally obtain the estimate for all possible cases of the
1 (+)(i <
T VT
+ 1 - 1) 3 $119%112
(38)
Now it is time to take expectation and give estimate 8 One can note, using the law of total expectation (E [g] = [E (E),))),
[o71 (Jen)
E(V))(>) - l'lli Σ
E
[V[(}))
E (VV(())) (g9),)
d
Σ
E [[V](<*)) -101)) 1o0
1=1
In that way, obtain important bound:
E B)(()((t)) - -//111 ||ll.
(39)
Then,
E8
B[V 1/112 x
Σ
||l|| & ||o|/TT
1=
E8++1
( - + <
| ||al)TT
Substituting it to equation 38 have
A'
3 |
&
+
10 +
T
/T
T
t=0
35

---

9: end for Published as a conference paper at ICLR 2026
T
Expressing the number of iterations and using > 7
V (x("))
as a criterion, we obtain ||
that algorithm needs O A Lo
iterations to reach e-accuracy. Note the we drop the term a ll. since it is asymptotically smaller than the main one. However we firstly need to find step
||
li
2=2 o (( ((-t/-- + lllllltt 1: iterations,
ho with bisection procedure that takes T log log
where 22t denotes the length of the initial interval for the stepsize. We have already discussed in the main part that, according to Lemma D.2 i should least log log 7. ".l Thus, is the final iteration complexity.
O A A L0 + || loglog %1119"111>
A'
Remark E.5. Under conditions of Theorem E.4 Algorithm 5 with mini-batch of the size t + 1 at t-th iteration to reach e-accuracy needs
(
A Loo + |
o
log log
iterations.
7/s 1
Proof. The proof of the remark repeats the proof of Theorem 3.9 except for the estimate on V[V g" I| term. Since we now use mini-batches, we can bound
|a]h
E V -
<
vt+1
instead of equation 39 In that way.
1 T-1
||al| ||11 t+1 VT
E8
Σ E(V 9'111
T
which ends the proof of the remark.
E.3 DISTRIBUTED SETTING
To begin with, we present the modification of the classic SIGN-SGD algorithm (Algorithm) I that aligns with the distributed learning. We consider SIGN-SGD with majority vote (Algorithm 6). similarly to (Bernstein al., 2018). We present the assumption that we utilize in distributed regime.
Assumption E.6. In the multi-node regime of learning each node 1, at any point IR has an access to the stochastic gradient, i.e., it can compute g;(x) = ff(x, Eý) ) - the stochastic gradient value with respect to the randomness in the choice fo samples Ey- Additionally, this stochastic estimators is unbiased, i... E [g) = fz),, and its variance is coordinate wise bounded, i.e.,
(1), (=))), & o7.
Algorithm SIGN- SGD with majority vote
1: Input: Start point - Rd number of iterations T
2: Parameter: Stepsize 7 > 0
do 4: for all nodes j 1,...,M M in parallel do
3: for t= 0, .,.
5: Compute stochastic gradient 9j V (a',E)
6: Send sign(g, (x*)) to the server
7: end for
8: 11+1 ysign [M sign(y((x))))
Proceeding analogically to the stochastic one-node regime, we establish Mr(r) and Dr(r)
that in Φ(7) in the BISECTION procedure: Mr(r) Ar()), Dr(1)
36

---

Published as a conference paper at ICLR 2026
Let emphasize how this affects Algorithms Firstly, we now need to call the SIGN-SGD with majority vote method (Algorithm ( instead of SIGN-SGD (Algorithm D Secondly, to obtain Dr(7) in the bisection procedure, each node counts E'zo llu, (x'-1) Jy (x') II using locally stored gradients, and sends the complete sum to the server the end. Note that this requirement has no effect on extra memory and communication complexity, since each device requires only (dd) extra memory and performs only one extra communication during the whole learning. Now we present the theoretical result for the distributed setting.
1= Σز= (و"")(
((7)). -g
Lemma E.7 (Theorem 2 (a) from (Bernstein al. 2018)). Suppose Assumption E.6 holds. Then, at any point x E RRd, the following estimate is valid:
[V]())] P
sign Σ sign (11)(=)1,)
* sign ([Vf(z)).)
< 0z
Lemma E.8 (Descent lemma), For Algorithm under Assumptions estimate is valid:
3.1
3.2
3.3
E.6
the following
Vf(29)l ((
|lg
++
28T + 8 g
70
j=1
M
where 8z
Σ Σ [f(('') 951ز2
T-1 d
M
(lo5l.)) # sign ((VI(x'))))
and 8 = =Σ E
[V T
sign
Σ
sign
Proof. Starting from the convexity of the objective,
M
1(x -(x²)
& (
x0)=--/ (s(att)), sign
Σ
sign(
M
= -
v Vi(x'), sign
sign(g))
M
sign(of) )
vf( Vf(x') sign
Σ
V 111 + 27 Σ [[ff(')]]
M sign Σ
sign (1081.) # sign ([Vf(z')])
II
M Σ sign(s8)
-76
- vs(xx), sign
Cong Coni
>>\V)(>*)| + 8
M +~ - sign Σ sign (o))
~>|V 27 + [ v((x))]1
-
37

---

Published as a conference paper at ICLR 2026
M
~>VV((>') + 24 +
Σ M
119 ++ r}لز2
==1
M
ty
,9 1|
[Vf(x')) -9512,, (40)
M j=1
(loAle) + sign (V]((*1))) Now
where in (i) denote 8'
(x: |
sign
sign
we rearrange terms and summarize over all iterations to obtain
T-1
T
M
fV('\ll''
[f(x)) f(x +
y $1103 ++1 - rاll1
M
1=
t=
M M
M
ااززو
/V  11.
t=0
J=1
j=1
Since Algorithm A all the steps with the constant rate Yo. which we define later, denoting
5T
8
we can rewrite the result in the following form:
ff(²) f(x(+1))
[V(('))>
+55
10g 1+11
%
M
/=1
T
M
[Vf('') -911
+
[V
07 112
M
M
t=
j=1
In the obtained estimate the last terms consist from differences between the honest and stochastic gradient at the 1-th and (1 + 1--th moments. One of our goals is to estimate them, however, we want
to perform analogically to Theorem and continue the proof with the M Σ
term estimate.
To simplify the subsequent notation, we introduce the following definition: let
T-1
M
5'
[Vf(** of In that way, the following inequality finishes the proof of the Σ
lemma:
((a-t)-((x))
T-1
Σ
19g j=1
051l2
288 + 8t gr+1
70
Theorem E.9. Suppose Assumptions 3.7
E.6 hold. Then for Algorithum S using at t-th iteration hini-hatches of sizes t + 1, after obtaining the stepsize Yo, the following estimate is valid:
3.2
M
3
T-1 Σ T E=
AA + 10
T
Moreover, taking into account the complexity of Algorithm 4 in relation to the initial stepsize bound Te to reach E-accuracy, where >
Vffx'') 11, Algorithm needs
A A"Lro +
A log log
||a|13
iterations.
7/4
38

---

Published as a conference paper at ICLR 2026
Proof. Let mention that the result of Lemma
E.8 almost matches the starting point of Theorem -9 the only difference is that there 1 ++1
T-1
E.4 E.4equation228 26 If we now denote GT
Σ
have additional 28T term. However, do not estimate it yet and it does not require any transformations. Thus, we can proceed in a manner completely analogous to the proof Theorem and obtain analog of the estimate in equation 38
|
& V +
(+)('())))
(20 + 48' +8
(41)
T 1=0
VT
T
where A f(x 1) [xx)).
Now take expectation and Lemma E.7 obtain
M
EB Σ [Vf(=')],
sign
Σ
sign
(06il.) * sign ([Vf(z')),)
i=1
|
(42)
For E8", under Assumption E.6 we have the estimate equation 39
داززو
||o||1-
Thus, substituting both of these estimates to equation
we obtain the final convergence result:
M
Σ
E
M
T-1
M
Σ ElVs(>) & 6
10flo
+
J=1
M
T
T
j=1
t=
|
M
10
+
T
Since we obtain the same convergence estimate as in Theorem F.4
we can analogically establish the
L' Lm + ||01
log log
A"
iteration complexity.
1102lh 3-m
Σ
Remark E. Under conditions of Theorem E.9 Algorithm 5 t-th iteration to reach E-accuracy needs
with mini-batches of the size t + at
A Lo +
| 62
A
o
log log
iterations.
M
7s M
Σ
11 l1
Proof. Proof repeats the proofs of Remark E.5
F PROOFS FOR ALIAS
F. EXACT GRADIENT SETTING
Lemma F.1 (Approximating sequence). Let the initial A -aproxximation d0 be d0 < A*, where
A f(x") - f(x*). Then for Algorithm 2 under Assumptions 3.7
3.2
3.3
3.4
the following
estimate is valid:
A d Vn [0, 1).
39

---

Published as a conference paper at ICLR 2026
Proof. Starting from the convexity of the objective,
s(x't)) s(x') < (VS(xt+),, -x') =- (VS(xtt)) sign sign (Vi(x'))).
(43)
Now we summarize both sides over the first iterations:
n-1
- f(x)) f(x))
f(x") Σ f( f(x9)
R-1 1
Y (VI(x*+)) sign (VS('))))
[=U
where (i) is correct due to Assumption
3.3
Changing the sign of the inequality,
dn
(2( sign (Vi(z))) A
Since algorithm performs d" max dd=1 d" we obtain the required statement.
and we initialize our sequence with d
Lemma F.2 (Descent lemma). For Algorithm uudeer Assumptions 3.7 estimate is valid:
3.2
3.3
3.4
the following
T-1
T-1 <
Σ
vf(x
Σ
L
where 1:
Proof.
f(z!t!)
f(x') + Vf(l"t)),, 2²) f(x²)( - (Vf(=*+)) sign (Vf(z')))
1(x)) - " 74 (V/(x'+)) V/(x'), sign (VS(x'))
Cona
f(x²) - 7' [| +7 V)(x - v |I, sign (vf(z)))
f(z') - 7' ([ )]| + Vf(x - v)(x')]]
[/ v>(x'))] || - x'1
f(x¹) - [
1 x² loc
s(x)) - >' [>>((>))|| ||, (64)2 [f(x(+1) - vf(*')
| x² 1011
where in ( assume ||,t|| - * 0. Indeed, ||a 2'1 0 follows from the equality sign (v)())) which means that we find the optimum and do need to find another point a++1 Summing over all iterations, we obtain
Now we denote L
T-1 Σ (1500111
Σ [5(x') [(xtt1)] ((at))
E.' (7:))
==
T-1
T-1
s(x0) - f(x") + Σ (2
A +
Σ
2
which ends the proof of the lemma.
Theorem E3 (Theorem
3.5 Suppose Assumptions
3.1
3.2
3.3
3.4
hold. We denote
Σ (V'"',,, &
V -- Then Algorithm with Option 1, d A
12
to reach E-accuracy needs
(Lo)) (A
iterations.
d0 (T..) ) E2
40

---

Published as a conference paper at ICLR 2026
Algorithm 2 with Option Il to reach E-accuracy needs
δ A (Loo)
iterations.
(I [=
Proof. Let start with the result of Lemma
F22
T-1 ( ==
(V A
(44)
Now we use our 7t choice.
Let firstly estimate the denominator that is exactly X and is the same for both Options I and II. Let us estimate
( -
the following term.
T-1 Σ 0=
L
Σ
P
Lio
We mention, that each Li is bounded from the definition of smoothness (see Assumption 3.1 i.e. L. & Loc. We consider the sequence { ) Since each term in this sequence is bounded,
there exists such that Σ L/ - and for each > r 1 such that Σ L'o0 > L In that way, we divide the sum into two parts:
T-1
Lt
Σ
(45)
Σ
D
D
Σ
D
==0
mention, that estimate the denominator as D Do To As for the numerator. Thus,
Considering the first in equation 45
21-11
2L
Σ
D +
[--1
<
(46)
0
00
Considering the second sum in equation 45 we have
T
T-1
L
Σ
L/
Di
Estimating any of the sums in the denominator, claim, that In that way,
Σ
Li 2 L since t -- - 1.
1=
21
Et
Σ
2
(47)
[-)
1
Σ
T/3
Σ
Li
-=0
Σ
Li
i=0
41

---

Published as a conference paper at ICLR 2026
Next we denote
Σ
2o
and have
1=0
L
(s' - s(-1)
dx
&
dz.
(48)
Σ
Li
Σ
s/-1
where (i) was done due to is non-increasing function on (0, t00).
Summing over i, we obtain
T
T 1
Σ
1/30
Thoe T
2
dr
2log(s") 2log(s") 2 2
-=1
2lg
x
L
1=1
Σ
L020
8
Combining this estimate with equation 47
Σ
2
T
L
+2
log
Lxo Le
+1)
< 4 llg
Loof
(49)
0
t=
T
Substituting equation 46
and equation 49 into equation 45
obtain
Σ P
2 + 4 log
Loc Lo
Lxo
(50)
L
We additionally note, that i T - only first term remains this estimate, consequently our bound equation 50 is correct.
In this way, utilizing Option from Algorithm
equation together with equation 50
yields
Vd <
L'
Lemma 21
(1)
t=
A
f
Σ (2
vd X
V
30
A
Icoo
A A
log
+
TT
V
I
Vat
XT
77
A L.o
Loo
log
(51)
T
LO
L
where (i) was done due to the fact that d is minimal from all fa" It=0 (Line
from Algorithm 2
2
and the definition of X Utilizing x
Σ
Li VLxTT, we obtain the final estimate:
V
7A (Loo)
L
Σ
log
T L=
VdTTLo
LB
Expressing the number of iterations and using e > $
Σ
[V((')) as criterion, we obtain that
the algorithm needs δ (A)))))))))) [FE
iterations to reach eaaccuracy.
42

---

Published as a conference paper at ICLR 2026
Considering Option II from Algorithm f(a") f A instead of Lemma F.1 In that way,
proceed absolutely analogical, however, using
TT 4(5(2)) - -V
Loo L2
log
T 1=
( -yT (f(x0) 1 FJT
2(5(x)) - (Loo)
Vis(o") - T
7V TU(00)) 3) (Ioz)
Li T I
log
VTLS.
Expressing the number of iterations, using +
[V((')|| criterion, and utilizing is
an approximation of f(=",, we obtain that the algorithm needs Ō (L 13 e-accuracy.
iterations to reach
(F.. (E2
Remark F.4 (Remark 3.6
Under conditions of Theorem 3.5 and Option II to reach e-accuracy needs
Algorithm
with X
( vo(e")ll 2
12
A' Lox 5
iterations,
E
T where E > 7 [Vf('']
Proof.
The proof of the remark repeats the proof of Theorem (2 term. Let derive it. We use definition L.
3.5 except for the estimate on
[(x
-
T-1 Eare
T-1
L
T-1
L
Σ
t=
Loo
Σ
L
(=0 Σ
L
Continuing analogically to equation 48
equation 49
we get
T-1
Loc T
EuPPL < 2log
7,0
Substituting this bound into equation 51 instead of equation 50 we ends the proof of the remark.
F.2 STOCHASTIC GRADIENT SETTING
In this section we denote g the stochastic gradient at the f-th iteration (point x²), according the stochastic realization g² at the t-th iteration.
Before proceeding to the theoretical analysis of the algorithm, present its formal description, Algorithm 7 specifying which option for the sequence d' we use in practice and which one we analyze theoretically.
43

---

Published as a conference paper at ICLR 2026
Algorithm 7 ALIAS stochastic version
1: Input: Starting point x² "RR, initial approoxxxinotoonnn v/ 0, initial aaapproximation d
EIR,, lower bound f on f=="), number of iterations T
2: for t= .,. 1 do
3:
Compute gradients ge Te=
f-1
06 get
4:
1/ = =f=
N
11
Vn
5:
if + 0 then
6:
d' Σ/= > (gets s+1 sign(g((t1)
1-1
7:
d' = max dh- .
8:
end if
9:
Option I (Practical): 7f = 21 Vd
10: Option (Theoretical): 7/ X' (xx))= -
11: x1+1 x² - sign(())))
12:
end for
In the practical version of the algorithm, the stochastic gradient the previous point with the current stochastic realization to update d². We use the same stochastic samples, similar to the update of the smoothness constant approximation, reduce noise from the stochastic gradients.
We now proceed to the convergence analysis.
Lemma F.5 (Descent lemma). For Algorithm under Assumptions estimate is valid:
3.8
3.2
3.3
3.7
the following
T-1
y2t
Vf(x')
g T
E
AE
+ 2
E
1=0
7
7
t=
Σ
7p
t=
7 V
4+1
Σ
72
2=
L
T-1
7 V D
+
7
7
26
where LLg*
1
Proof.
f(x"tl)
f(x²) + (V x11 x²)) -=0)= f(x²) /V (V sign (ok.)
f(z') - 7 ||o.-11, -10 (V)(z((1) g'c, sign (gε:)
Conz
f(x') 3 1196 /1, + 1 /V/ 26. |l, ||sign ll
cs
s(x') - / +2 (xx)) 5 l|r
sign (otz !1
Cs
f(2²) | 2-
| [f('') o6: |l, + [f(c(+1) - o
| s ||, ||sign (le
+2' V5(x'') +1 +
44

---

Published as a conference paper at ICLR 2026
12 s(xt) - - 7-
+ + [1 2 11 7/ [5 - s6
+2" (, - ا6 || + | - ofc4z
| - x 11
| - 201lo0
f(x0) - >/ 1 fx |11 + 2 -/>1|V/(<> - 26. 11 +
|f(x - 06t
1+1 g
gec11
+ Ff(x') - g 11 + (79)
| - xz/
where in (i) assume ||a - -x'll * 0. Indeed, || - xz1 2011 0 follows from the equality
sign ( = O, which means siign g6 = 0 and at the 1-th iteration this term equals zero Thus, we can omit these iterations and consider this term only when it is non-zero, without any 0/ 0/ Summing over all iterations, we obtain a
limitations. Now we denote I
s(x*) - ((xtt1 + 2
[V(('' - Iا-
| - -
Σ 7" -
T-1
= 5(2 - f(x²) +2
Σ
- 7 [
1=0
- |o|(o
-
-
(
< A Σ 7' ( + T-1
Σ 7t
//(aot)) g
- st -
+ - (
0=
We divide both sides of inequality on ΣT-10 nth
T-1 x
Vf(x*) 06
+2
T-1
Σ 7
1=0
Σ
7
1=
Vf (+1)
gett1
(+1
76
Vf(x*) - g
T-1
Σ 7
Σ 72
1=0
Σ
7'
45

---

Published as a conference paper at ICLR 2026
Taking expectation, obtain the final result of the lemma:
g6
T-1
Vf(x*) - sé.
E
Vs(x')l
<
E
+2 E
T
T-1
Σ
7
1=
Σ 7d
T
7' |f(
Of+t
T-1
Σ nd
2
7'
vf(x*) 12
T-1
( (79)2
+
+ Σ
E
1=
Σ 7d
t=
Σ gl 1=0
26 11
T-1
Vf(x')
1
A'E
+ 2
Σ
E
T-1
Σ yt
t=0
Σ np 1=
T-1
71
V fxx
get
+
100
Σ 72
t=
Y' Vf(x*) - L
Σ
(
+
Σ
E
+E
T
7
7
Theorem E6 (Theorem 3.9
Suppose Assumptions
3.8
3.2
3.3
3.7
hold. Then Algorithm 2 with
Option II to reach s-accuracy, where > EL-LB
R
V((x))
needs
5
A
3
E
+ ||011/ Loo
E
1
iterations,
E2
0.EI
min
L
0S15T--1
| - 22
where L
Proof. Let us start with the result of Lemma F5
Vf(x")
g
E
AE
+2 E
T 1
T
T-1
x
t=
Σ 7
1=0
t=
1=0
T-1
7 Vf(x++1)
+
E
1=0
Σ 72
7/ V - Seutz
Σ
E
+E
T 1
T-1 Σ 7
1=0
Σ "
1= 0
0=
46

---

Published as a conference paper at ICLR 2026
Using equation Hö
with p 9 2, we rewrite it in the following form:
7f
E
AE
T
t=
+2
E
V
- -6E-111)
E
T-1
T-1
- 113)
1
T
1
1=1
Σ 0
11²)
E
E
1 1)
+
E
Σ 1=0
E
(52)
Now we use our choice of yt. Let us firstly estimate the denominator that is exactly A
Let us estimate the following term.
Ligt+1
T-1
LLg
Lig
t=
We mention, that each Lig is bounded from the definition of smoothness (see Assumption 3.8 T-1
ie.. Lig & Loc. We consider the sequence (L25*
[igg
J== Since each term in this sequence
bounded, there exists such that Light --- and for each > r 1 such that
Σ L L 14
In that way, we divide the sum into two parts:
It. et1
I
T-1
L L
(53)
igtt
L
igt+1
L
igtt
Considering the first sum in equation 53 we mention, that we can estimate the denominator as Di Lig 2 L As for the numerator. Thus,
1
I
Lett1
11-1
21
2T
(54)
[-1
0ge1
0.e
0g5
1=0
47

---

Published as a conference paper at ICLR 2026
Considering the second sum in equation 53
have
L 11
T-1
L
L00
+
Lo
Estimating any of the sums in the denominator, we claim, that Σ Lig
L
since
1. In that way,
T
T-1
2T
T-1
I
2
(55)
iitit
L
t=
Lio0
[=0
T,30
i=0
1=0
Next denote s Σ
L
and have
5' dx
1
1
(s'
81-1)
dz.
(56)
oc
Li
igil1
Σ
L
s1-1
where was done due a non-increasing function on (0, too). Summing over t, we obtain
T Σ
T
2
00
2
1
dr 2 log((s") -2 log(s = 2 log
[=l
2 2log
L
0.g1
0.g0
t=1
80
Combining this estimate with equation 55
I
Too log
Tro
2
Σ
+2
+
<
4
(57)
0,ET
iggtt
1=0
Substituting equation 54 and equation 57 into equation 53
we obtain
Σ 2
Leett1
Loo
0.eT + 4 4
LOOT
(58)
0,ET
We additionally note, that ifr > T 1, only first term remains this estimate, consequently our bound equation 58 is correct. Next, estimate
Loo
VL
(59)
T-1 Σ
VT
X
V+4I
boo
Now we estimate the second, third and forth terms in equation 52 the same manner, as in equation 39 we can estimate
E VS(x')
- 112
|| l|
48

---

Published as a conference paper at ICLR 2026
2
E
V f
ggeti
|
(60)
E
ff(2
ge 11
|
where the last inequality correct due to the fact that that stochastic realization g is independent from the point x'. Thus, using equation 59
E -
7p
|all
E
VT
1-1
1=
Σ
1
Lox
1011
E
Σ
T-1
VT
min
L
LI
Vt
+ 1
t=
< 22/ Locloll
min
L
0
is clear that we can bound the rest terms in the same manner. Now, substituting this estimate
along with equation 58 and equation 59 into equation 52
we obtain
LLoLo ((((2)) - Fyr
+8v Loo ||111
E
min
0
- -f(#9)-FVVL FFVI
Loe
+8
Elog
V(((E)) -IT
0,5T
+4 (f(x9) - D.
Loo
(61)
((f(19) Firr
Loo
D.E
Now A
f(x²)
ff to obtain the final estimate:
((((a)) (Ioo))
T
7
E
I11
13
E
T
T
L
t=0
Σ
7'
Loo T Elog?
0.g
+8||oT11
Voo
E
min
L
0515T
49

---

Published as a conference paper at ICLR 2026
Expressing the number of iterations and using e
Σ
[V((*)]
as a criterion, we
1=
obtain that the algorithm needs θ (hool
+
|o11
Loo
E
it-
min 0G
erations reach e-accuracy.
Remark F.7 (Remark
3.10 Under conditions of Theorem 3.9
Algorithm
2 with X
Option and mini-batch of the size + at t-th iteration to reach E-accuracy
needs
A Loc
||0|| 2²
Loo
E
iterations,
Lid 1
min
0
where + Σ [Vf LL5
at 11
Proof. The proof of the remark repeats the proof of Theorem 3.9 except for the estimate
T-1
Σ (1 term and E V[((() oE
|| term. Let us derive them. We use definition
1=
1 2 l1
I
1
T-1 Σ L
T-1
Ligut
T-1
Iig
%
1=0
Loo
L
igg+t
1=0
iggi
Continuing analogically equation 56
equation 57 we get
T-1
Lioe T T
Σ
< 2log
We substitute this bound into equation 61 instead equation 58 can bound
Next, since we now use mini bini-batches,
I |
E Vf(x') - 11
v ++ - 4+1 |
| 1
E V/(x') st-+1 1
|
instead of equation 60 In that way.
E
V
112)
E
T-1
Σ
50

---

Published as a conference paper at ICLR 2026
Lox
E
T
vl
+
1=0
520 00
1
E
VT
min
L
L
t+1
UEIET-1
L:00 0||1
2
E
log(T),
VT
min 0
Lo00
which ends the proof of the remark.
F.3 DISTRIBUTED SETTING
We remind, that in distributed setting we consider Assumption E.6 with the following approximation of Loo in Algorithm 2
We present the theoretical result
X
9
EE
EØ M
[of
In this section, we denote Si.ge the stochastic gradient from the j-th device, computed at the I-th iteration, according to the stochastic realization çt.
Lemma F.8 (Descent lemma). For Algorithm under Assumptions estimate is valid:
3.8
3.2
3.3
E.6
the following
T-1 Σ EBMIV
T-1
2 8'
A'E
+ 2
t=0
7t
t=
M
7 M
|
D3 111
E
T-1
Σ n 1=0
(x*+1)
M
E
1=1
T-1 Σ 7"
Σ
2
+E
7
Σ sign [01se]]))
M
where 8z
Σ
|| (x:"(()),,
T
sign
* sign ([V (xx)))
|
and L.55"
51

---

Published as a conference paper at ICLR 2026
Proof.
f(xtt)) f(x') < (V ) 1tt1 =xa)
M
V vs(x sign Σ sign (o)vet)
Vf(z'), sign Σ sign (0),st)
M
sign (iit)) )
1 ((( (s(x'), sign
Σ
/| + 2
Σ [Vf(x']]
sign Σ sign (1oxell))
II
F sign ([Vs(z'),,)
M Σ sign (oises
( Vf(x'), sign
Con (4)
>|V
||| 1 27
M sign Σ
+>/VV/((/) (>(''))
sign (ohe:)
= ~VVf((='> + 2
+7 1
sign Σ sign (dh,et)
M
~ + 2 +,² 1 M
[V 03.
M
g ll1
M- j=
1 M M
M |1 | - 03 11 sign Σ
Σ
sign (giss)
/=1
~>(V 2 +2²- 1 M
[[v)(()) sh
M
1 M
V +l(
+1 - g l
M
M
l1g 1 g 11 x 201100
M
|
x 11000
- + 22/0"' +n² 1 M
Σ ||
- - 12.111111
M
52

---

Published as a conference paper at ICLR 2026
1 M
V 9/54411 ll1
++1
M
==1
M
03,441111 11
1
M
||
121100
j=1
where in (i) we denote 8
Σ f='((")l11I
d
(analogous to Lemma (1hiee)
sign Σ sign
1))
+ sign ([V f(x²(()))) (11))
and in (ii) we assume |
x² Il.00
*
F.5
Defining L
3.5 11 -
and summing over all iterations gives
M
1
T-
M
<
A
+ 2
[ - - ||
M
1=0
2m0
T-1
M
V +1
0 11 +
M
0=
j=1
x=0
M
Σ
Vf(('* Se
T-1
Vf(2')/1
+
j=1
T-1
y
Σ 7
M
(7 2 Lt.
T-1 7
T-1 Σ 7d t=0
Taking expectation, we derive the result of the lemma:
T-1
Σ
A'
2
Σ
E
T-1
7
0=
7d
t=0
M
M
Σ
E
1=1
T-1
Σ 7
1=0
V fx
M
ΣE
E
1=
t=
Σ 72
+E
7
53

---

Published as a conference paper at ICLR 2026
Theorem E9. Suppose Assumptions 3.8
3.2
3.3
E.6
hold. Then Algorithm 2 with Option II reach
T-1
e-accuracy, where
Σ
Vf(x'))
11
needs
A
(zx)
)
1
8²
E
D
-
||oll Loo
E
min 0EtET-1
iterations,
where 1
1
Σ
M
getz
o
M
Proof. Let start with the result of Lemma F8
T-1
3'8'
Eh
AE
+ Σ E
T-1
T-1
Σ xt
(x+) 03 11
Σ E
T-1 Σ yt
(x
Σ E
T-1
t=0
Σ 7d
(7)
(
+E
T
Note that we have already estimated all terms in Theorem except
EE
However,
using Lemma E.7
together with equation Höl we can do the same thing and obtain
T-1 1
8
T
E
E
0
2 Loo
Lo01
E
min
0
In that way, we get the same estimate as in Theorem F.6
T
E
|f(2')l
<
E
T
uugT
7
Loo T') L
1
Elog²
54

---

Published as a conference paper at ICLR 2026
+8|1a111
v
VT
E
min
Lee
05
7-1
Expressing the number of iterations and using E
Σ
E
V
vf(x**))l 1|
as a criterion, we
=
obtain that the algorithm needs θ
E
|o Loo
E
it-
L
erations to reach E-accuracy.
Remark F.10. Under
conditions
2 with X Option II and mini-batch of the size at t-th iteration
Theorem
F.9
Algorithm
Σ
reach e-acouracy needs
T
A
||0||2 Loo
E
iterations,
22
min
L
t.ge+1
OETET
where + T-1
M
1 Wictt
0j 11
Σ
[Vf
145
Σ
|
jml
Proof. Proof repeats the proof of Remark 3.10
F.4 MEMORY-EFFICIEN ALIAS
Lemma F.11 (Descent lemma). For Algorithm estimate is valid:
under Assumptions
3.17
3.2
3.3
3.4
the following
T-1 7' [[][(+))]
T-1
Σ
where Li = V 1)
1 |
Proof.
f(x!tl)
f(x') + (
(Vf(<'*))))))))))))))))))) sign (vf(z')))
f(x 7' ( (|] - (V/( V/('') sign (Vf(''))
-
Con
1(0 / + 4/(2 - v/(2-) sign (V/(+'))
f(x') 7. ( P. V +1) vf(x')
f(x¹) /1 7 V/(a*+1 V
|| -x11|
1 x²11,
f(x)) - 7' / (1))| ||, 22 [f(x*t1 fx(x)))
||x++| - x²
where (/) we assume ||,0t1 x. ||, * 0. Indeed, || x = 0 follows from the equality
sign (vf((')) = O, which means that we find the optimum and do need to find another point ++1 Now denote ! ||//(="))~- ||
Summing over all iterations, we obtain
T-1
Σ 11
Σ [f(x)) s(x
Σ (f
0
0=
55

---

Published as a conference paper at ICLR 2026
T-1 f(x)) + 1=0
(1))
<
A
Σ
(
0
which ends the proof of the lemma.
Theorem F.12 (Theorem 3.12). Suppose Assumptions
3.17
3.2 3.3
3.4 hold. We denote 2
()("")),,, = V ( )-
+ E
Then Algorithm 2 with d A and d as in
--=
equation
to reach e-accuracy needs
( (L 3 d² (I4)² E²
and ō A (L1)* d? (L4)² c²
(L)
iterations with Options I and II, respectively.
Proof. Let start with the result of Lemma F.11
Σ >lVS((
<
Σ
(62)
Now we use our T choice. - M
Let us firstly estimate the denominator that is exactly X and is the same for both Options and II. Let us estimate the
following term.
4 Σ
Σ
Σ M
We mention, that each Li is bounded from the definition of smoothness (see Assumption 3.11 i.e., Li < L1. We consider the sequence {Li} T-1 Since each term in this sequence is bounded, there
i=
exists such that Σ 4 & - and for each / 1 such that Σ 14 T1t1. In that way,
y-2
divide the sum into two parts:
4
Σ r=0
(63)
Σ
4
Σ
H
Σ
4
Considering the first sum equation 63
we mention, that we can estimate the denominator as Et-1 Li > Lq. As for the numerator. Thus,
Σ4 D
21
2L 17
<
L
Σ
L
1
<
L7
(64)
1=
Considering the second sum in equation 63 have
Σ
T
Σ
H
Σ
4
Σ
T
Σ
T
56

---

Published as a conference paper at ICLR 2026
[-1
Estimating any of the sums in the denominator, we claim, that that way,
Σ Li
>
Dj.
since 1-13 r-
In
1=
211
41
Σ
< 2
Σ
(65)
1
Σ
1=
Σ 1
1=0
1=0
Next denote s
Σ
Li
and have
0
1
L 1
(s'
1(-1)
dx
dr.
(66)
Σ
1
Σ
Li
s1-1
Σ 1=0
Li
s1-1
x
1=0
1=0
where (7) was done due to is non-increasing function on (0, +o0). Summing over I, we obtain
Σ 7i
T
Li
LIT
Σ
2
dx 2log(s") - 2 2log(s") = 2 2lo
1=1
< 2 log
4
1
t=1
Σ
Li
Combining this estimate with equation 65
T
LA
L log
L
Σ
<2
+2
+
< 4 log
(67)
1
[=1
Σ
1=0
Substituting equation 64 and equation 67
into equation 63
we obtain
LIT D
Eade < D
+ 4
loog
(68)
We additionally note, that if T - 1, only first term remains in this estimate, consequently our bound equation 68 is correct.
In this way, utilizing Option I from Algorithm 2
equation 62
together with equation 68
yields
VT
VdX'V &
Σ d')
T-1
Lomm 2
(2)224
Σ
(2
-
VO-AT-1
1=0
A
L
L
+4
log
+ 2
V
V
17
A
LIT
log
669
VT-
T.I
57

---

Published as a conference paper at ICLR 2026
where (i) was done due to the fact that d is minimal from all {a"
{r=)
T-1 1t=0 (Line
from Algorithm 2
and the definition of X Utilizing x d
Σ 1A &
T,
obtain the final estimate:
7 (L))
LIT
[
log
v di
Expressing the number of iiterations and using e 7 [Vf(2*)l as criterion, we obtain that
algorithm needs ① (A')"
iterations to reach e-acouracy.
(z)))=²²²
Considering Option II from Algorithm 2 we can proceed absolutely analogical, however, using f(x²) -f A instead of Lemma F.1 In that way,
A'VLid
4 - FVVLid
L1T
f((2')l
log
T
- ((((z)) Fyr
47
+ 2(S(x9) - (T,,)
((H(20) - FFYTL
TV (F(x") - (L1) d
LiT 4
log
VTL.
Expressing the number of iterations, using + |f((*))l as criterion, and utilizing f is
an approximation of fxx"), we obtain that the algorithm needs Ō e-accuracy.
A (14) (14)²²
iterations to reach
The proofs under stochastic and distributed settings for the memory-efficient version of ALIAS can be obtained analogously to Theorems F.6
F9 and H12
G STEEPEST DESCENT
There is one more approach for sign descent. Classically, perform the step in the direction of the gradient. However, we not take into account the length of the gradient in any way in the step. The approach, called steepest descent, is supposed to utilize this information and provide the steps in the direction V [I sign V (x*)) at the t-th iteration. We provide the formal description of this approach (Algorithm
Algorithm 8 STEEPEST DESCENT
1: Input: Initial point x0 ERC, number of iterations T
2: Parameter: Stepsize e > 0
3: for 0. .0...,77 do
4: 1.++1
cll (==) (+)(t))
5: end for
We present the analysis of SOS STEEPEST DESCENT. We start with the descent lemma.
Lemma G.1 (Descent lemma), For Algorithm 9 under Assumptions 3.7 3.2
3.4
the following
estimate is valid:
T A
V v((z))| (1 col.oo.
< Co
t=0
58

---

Published as a conference paper at ICLR 2026
Algorithm 9 SOS STEEPEST DESCENT
1: Input: Initial stepsize bound Css initial bound step k; initial point x. E Rd number iterations
T
2: co BISECTION (á(c), 20, Cs. 1/ Algoritlum 4 we utilize Algorithm instead of Algorithm
3: x² STEEPEST DESCENT(Z co)
where Loo
L' and L'c 0
max
Proof. Starting from the convexity of the objective,
((x+1)
< 1(x") + (VS(xtt)), - = f(x²) - - "V sigo(((((())))
= ((x')-1" f sign (ign(V
-7/ (Vf(xt+t) - Vf(2 sign (Ff(x)))
om
f(x²) 7' VV - V1(x=t1) vf(='))] ||sign [
f(x") - 7' [ ||, +7 (x(x+11 (11 V5(x') !|1
f(x') 3f VV((')) |l, + + V [f(**+1) -V(xf)) ||1 || 1|a
| - x² 1100
where in (i) we assume || - x²| = * 0. Indeed, ||x - x² |l.0
o follows from sign (VS(x)) = O, which means we find the optimum and do need to search the point (+1 Now denote I. |[(""")))>>>>>>
Continue estimate,
f(att1) & f(z') - + (iig(V
< f(x') - |V((''||| (
Now we choose 7' col [xxx)))l1 where we find the constant eg using BISECTION procedure (Algorithm 4). Thus,
f(x < f(x²) - coll V + f(x') - coll (< Il
- T
Summing over all iterations and utilizing T. = max 1 notation, we have
0-167-1
T-1
A = f(x) < f(x²) f(x0)( < -0 co
/f('')1 (1 (1-cute cntrx)
which ends the proof of the lemma.
Now we present the purposes of Algorithm Let us take an arbitrary point x= g Rd. We denote
/">>") (((=))>>(aa->))) and Ī--1
--1
1 11
max -111T-
L It is obvious that it implies
L < L-d < Loos Lxo < L-v
(70)
Let us put ((c) = T=1
in the BISECTION procedure. The following lemma shows guarantees of (c)
((qn) & Chi and ((o))
2 Go-
Lemma G.2 (Bisection entry). Let Cmax
1 Thus, with the initial Cbi Cmaxx Algorithm always avoids early infinite termination. Moreover, with the initial Cio 2 Cap. where
k > log log Les Algorithm 4 always avoids early non-infinite termination. T
59

---

Published as a conference paper at ICLR 2026
Proof. Let start with Chi The choice of Cmax implies
Chi =
Cmax
(cai);
Loo
(cw)
which means avoid early infinite termination. As for Qu-
1
o(cw),
=
2
Loo
L (cw)
which means we avoid early non-infinite termination.
Since we always entry to the BISECTION procedure, we are under the performing of Lemma Now we are ready to prove the final convergence guarantees for SOS STEEPEST DESCENT.
D.3
Theorem G.3. Suppose Assumptions 3.7 3.2 3.3 stepsize on the following estimate is valid:
3.4
hold. Then for Algorithm 9 after obtaining the
T-1 Σ 1=
A T
VV(22)
<
Moreover, taking into account the complexity of Algorithm f in relation to the initial stepsize bound Ca. to reach e-accuracy, where e2
[ Algorithm
needs
Lo
Loc L
O
log log
iterations.
E2
Proof. Firstly, we recall the result Lemma G.1
V \(('')> (1 (1- (1 Tioo)
t=
We have already mentioned that we can always avoid early terminations Algorithm due to cq we obtain
Lemma G.2 and thus, 27. (1g)
Co
(ro) Tuning co
1 Loo (co)
|V
11001110000 2L (co)
W0
(1-1) 2
[Vf('')If
CD
Expressing gradient norms, obtain
24 T
8A 8A
70 8A
(
<
T
T-1 Σ
Assuming +
[V
< 22 as criterion, we easily obtain the estimate on the number of
1=0
iterations required - 0 (>'4=)
Mention that the total number of iterations (together with the
Algorithm performance) - 0 A log log
Lix Time
THE USE OF LARGE LANGUAGE MODELS (LLMs)
this work, large language models (LLMs) were used exclusively for spelling edits.
60


Reviews:
[{"review_id": "rAf90X4YT0", "reviewer": "Reviewer_uXJ9", "summary": "This paper presents a variant of SignSGD which does not require manual step size selection for a given optimization task and the proposed ALIAS method provides stepsize prescription at each iteration guided by theory. Experiments on llama (upto 350M) and swin-transformer (28M) tasks show that ALIAS is competitive against tuned setups with learning rate schedules.", "questions": "See weaknesses above.\n\nAdditional question: can authors expand on LR and other hyperparameters (e.g. weight decay, schedule hyperparams) search space used for tuning the baselines? How many hyperparameter trials were performed for each baseline and the proposed approach?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper tackles an important problem of mitigating hyperparameter tuning of optimizers which is quite relevant in the current era of LLMs.\n* The proposed algorithm, guided by theory, is simple to implement and has practical benefits such as lower costs in single-node/distributed settings and no need for LR tuning. Also, kudos to authors for providing a memory-efficient version of the algorithm that is already efficient relative to SOTA optimizers such as AdamW.", "weaknesses": "* There are a bunch of hyperparameter-free methods that also eliminate the need for manually setting step sizes [1] but no such baselines are presented in this work, why?\n* Appendix A.1.1 mentions that only main model params are optimized by ALIAS and LM head params are optimized by AdamW — this detail is quite critical and must be mentioned in the main paper. How is AdamW learning rate selected for LM head params? Is it tuned through grid-search? If yes, then isn’t the point of param-free / saving tuning effort redundant since one can simply tune main model params while tuning LM head params? Moreover, how does ALIAS perform if it is also used for LM head params?\n* It looks ALIAS SignSGD performs a bit worse compared to tuned LR setup with cosine schedule (Table 1) and ALIAS Adam version also benefits from LR schedules (Figure 1). Can authors please confirm if this work eliminates the need for LR tuning but the problem of tuning schedules still remains to achieve the optimal performance?\n* There is a scope in improving the experimental setup. AdamW b2=0.999 as used in pretraining experiments isn’t standard, b2=0.95 is generally used and ideally should be tuned as per the setup. Also, it’s unclear if the method generalizes to different tasks such as those in AlgoPerf [1].\n\n[1] Kasimbeg et al. “How far away are truly hyperparameter-free learning algorithms?” TMLR 2025. https://arxiv.org/abs/2505.24005", "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": "evKUjVHhUR", "reviewer": "Reviewer_JFUp", "summary": "The authors propose a variant of the sign-GD algorithm. By estimating the Lipschitz and decaying factor during the optimization process, the authors give the algorithm with theoretical analysis on the exact case, the stochastic case, and the memory-efficient case.  The experimental results on the LLaMA 130M model show that the algorithm performance is similar or even slightly better than the tuning version.", "questions": "See Weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The authors propose a hyper-parameter-free sign-GD algorithm with its stochastic version and memory-efficient version.\n\n2. For all versions, the authors give a convergence analysis.\n\n3. The experimental results of the stochastic version and memory-efficient version work well on 130M model.", "weaknesses": "1. It is not clear what algorithm it is in the stochastic version, especially in the calculation of $d_t$.\n\n2. The expression of $\\epsilon = xxx$ is confusing. It seems that $\\epsilon$ is also related to the $T$ and gradient norm. But according to the proof, it should be $xxx \\leq \\epsilon$ when $T \\leq O(...)$.\n\n3. It is well-known that sign-sgd will not converge. It is unclear how the algorithm overcomes the issue.", "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": "ZTzkfXQrxB", "reviewer": "Reviewer_RrFQ", "summary": "This paper revisits the SIGN-SGD optimizer and proposes a novel parameter-free variant that eliminates the need to manually tune the learning rate. The core idea is an algorithm called ALIAS (Automatic Local per-Iteration Approximation of the Step size), which adaptively adjusts the step size at each iteration using the current gradient information. ALIAS estimates problem-specific constants on-the-fly, enabling SIGN-SGD to approach its theoretically optimal step size without needing prior knowledge. The method is developed first for the idealized deterministic setting and then extended to stochastic training and distributed training, addressing a known gap in prior parameter-free methods. The authors further introduce two practical enhancements: 1) a momentum-integrated version (ALIAS ADAM version) that incorporates ADAM-style 1st and 2nd moment accumulations for variance reduction, and (2) a memory-efficient modification that stores only the sign of the previous gradient to preserve the low memory footprint of SIGN-SGD.\n\nEmpirical evaluation are conducted on both LLM pre-training and vision model fine-tuning. The results show that ALIAS matches or closely approaches the performance of well-tuned optimizers (like SIGN-SGD with optimally tuned constant or cosine-scheduled LR, and even AdamW) but without any manual tuning. By removing the costly hyperparameter search, ALIAS yields about a 1.5x end-to-end speedup in training for large models. Overall, the paper’s contributions span theoretical guarantees for parameter-free SIGN-SGD and strong practical validation that this approach can simplify and accelerate large-scale training without sacrificing accuracy.", "questions": "1. Adaptivity to initial guess: ALIAS requires an initial approximation $d_0$ for $\\Delta^* = f(x_0) - f(x^)$ (or alternatively a known lower bound $f_e$ for $f(x^)$ in Option II). How sensitive is the method to this initial guess? If $d_0$ is set much smaller or larger than the true $\\Delta^*$, does ALIAS quickly correct the estimate via the $d_t = \\max(d_{t-1},\\ \\cdot)$ update, or could a poor $d_0$ slow down convergence initially? \n2. In momentum-integrated ALIAS, there are new hyperparameters: $\\beta_1,\\beta_2$ and base step size $\\gamma$ for the update. In your experiments, it appears you fixed these to standard ADAM values ($\\beta_1=0.9,\\ \\beta_2=0.999$) and chose $\\gamma_t=10^{-3}$ without further tuning. To what extent can these be considered default that work across tasks?\n3. Just for clarification: in Appendix F3,  ALIAS is extended to the distributed scenario. A question here is how the adaptive step size interacts with data-parallel distributed training: Do all ranks synchronize the value of $\\gamma_t$ each iteration, or does each node run its own version of ALIAS based on local gradient estimates?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Novel param-free algorithm for SIGN-SGD: the paper introduces a novel optimizer (ALIAS) that requires no manual step size tuning for SIGN-SGD. This is an original contribution, as prior sign-based methods either fixed a step size or relied on problem-dependent choices. ALIAS uses a clever per-iteration adaptation that accumulates an estimate of the local smoothness and the loss gap $\\Delta^*$ to adjust $\\gamma_t$ automatically. This approach is param-free in that it doesn’t need line searches or doubling tricks each round, and it doesn’t introduce additional hyperparameter to tune. The authors also propose two extensions: a momentum-incorporated version and a memory-saving version, which further increase the impact and applicability of the method.\n\n2. Theoretical guarantees: The work provides a detailed theoretical analysis in the convex setting, proving convergence rates for the proposed algorithms. The proofs build on and extend the literature (e.g., adapting techniques from adaptive online learning and recent parameter-free methods) and show that ALIAS achieves convergence within a logarithmic factor of the optimal tuned SIGN-SGD. The authors manage to handle the sign operator in analysis: they obtain convergence guarantees in terms of gradient norm, which is appropriate since sign methods inherently target stationarity. They also handle the stochastic case with theoretical guarantees (theorem 3.9 for minibatch SGD) and outline how the method works in distributed training (Appendix F). This adds comprehensiveness to the coverage and shows the method isn’t a brittle special-case solution.\n\n3. Empirical result: The authors pre-train transformer models on C4 dataset and also fine-tune a vision transformer in Appendix, demonstrating generality. ALIAS is shown to be competitive with SOTA optimizers. For instance, validation loss of ALIAS on LLaMA-130M is within 1% of SIGN-SGD with an expertly tuned LR schedule. With momentum, ALIAS even slightly outperforms AdamW. These results substantiate their claim that the new method without tuning can match the accuracy of well-tuned baselines. The results are reinforced by the training curves (Fig.1) which show that the convergence trajectory of ALIAS closely tracks that of tuned existing optimizers throughout training. The authors report metrics like end-to-end speedup (1.5x faster training when tuning is removed) which emphasizes the practical benefit of the method in real work.", "weaknesses": "1. Theoretical assumption: the theoretical guarantees are restricted to convex optimization (w/ smoothness assumption) and are expressed in terms of finding stationary points (grad norm). While this is standard for sign-based methods, it means the theory doesn’t directly guarantee improvement on the non-convex training objectives that the experiments address. The authors do discuss why a convex analysis is still informative for sign methods, but the strongest guarantees (Theorems 3.5, 3.9) hold under convexity or particular smoothness bounds. The empirical results suggest the method works for non-convex training but it would be better to close the gap between theory and expeirment.\n2. Momentum version is not fully param-free: the ADAM-style version reintroduces a LR parameter and momentum hyperparameter. The momentum version behaves more like AdamW. This is a weakness if one expected the momentum version to also automatically adjust its global scale. Similarly, the authors also had to tune weight decay via validation (0, 0.01, 0.1) for all methods including theirs.", "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": "spSXq5wBU0", "reviewer": "Reviewer_HNri", "summary": "The paper proposes a parameter-free variant of SIGN-SGD that automatically determines the learning rate using local gradient information without requiring manual tuning. The method estimates the step size via per-iteration approximations of the smoothness constant and loss gap, extending to stochastic and distributed settings. Theoretical analysis under convex assumptions supports convergence, and experiments on language and vision tasks show comparable performance to well-tuned AdamW and SIGN-SGD baselines, while removing the need for hyperparameter search.", "questions": "Can the authors clarify how the proposed step-size estimation behaves under high gradient noise or distributed training, where loss variations can be inconsistent?\n\nHow sensitive is the performance to the local smoothness and loss-gap approximations used in the parameter-free update rule?\n\nDo the authors plan to extend the theoretical analysis beyond convex assumptions to better align with the non-convex experiments presented?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles a practical and long-standing issue in optimization—manual learning rate tuning—by introducing a parameter-free variant of SIGN-SGD. The proposed formulation is conceptually simple and mathematically grounded, extending classical gradient clipping and step-size estimation ideas in a coherent way. The theoretical analysis is well-presented and the experiments, though limited, are consistent and demonstrate that the approach can achieve competitive performance without hyperparameter tuning.", "weaknesses": "Theoretical guarantees are proved under convex smooth assumptions, while the main experiments are on large non-convex models; the gap between theory and practice is not bridged.\n\nExperimental coverage is limited (few architectures/tasks and moderate scales), so generality across modalities and training regimes remains unclear.\n\nThe parameter-free step-size depends on noisy quantities (e.g., gradient-norm variation and loss gaps); there is no robustness/sensitivity analysis under high-noise or distributed settings.", "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)