Exact risk curves of signSGD in High-Dimensions: quantifying preconditioning and noise-compression effects
Authors: Ke Liang Xiao
Noah Marshall
Atish Agarwala
Elliot Paquette
Venue: ICML 2025 poster (2025)
Keywords: signSGD
stochastic optimization
deep learning theory
high-dimensional probability
stochastic differential equation
Primary area: optimization->stochastic
TL;DR: We derive SDEs and ODEs for SignSGD in high-dimensions: identifying scheduling, preconditioning, noise compression effects.

Abstract: In recent years, SignSGD has garnered interest as both a practical optimizer as well as a simple model to understand adaptive optimizers like Adam. Though there is a general consensus that SignSGD acts to precondition optimization and reshapes noise, quantitatively understanding these effects in theoretically solvable settings remains difficult. We present an analysis of SignSGD in a high dimensional limit, and derive a limiting SDE and ODE to describe the risk. Using this framework we quantify four effects of SignSGD: effective learning rate, noise compression, diagonal preconditioning, and gradient noise reshaping. Our analysis is consistent with experimental observations but moves beyond that by quantifying the dependence of these effects on the data and noise distributions. We conclude with a conjecture on how these results might be extended to Adam.

Exact risk curves of signSGD in High-Dimensions: quantifying preconditioning and noise-compression effects
Ke Liang Xiao
Noah Marshall
Atish Agarwala?
Elliot Paquette'
Abstract
ing of Adam and its variants is hindered by their complexity. While the multiple exponential moving averages are easy to implement, they complicate analysis.
In recent years, SIGNSGD has garnered interest both practical optimizer well as sim- ple model to understand adaptive optimizers like ADAM. Though there is general consensus that SIGNSGD acts to precondition optimization and reshapes noise, quantitatively understanding these effects theoretically solvable settings remains difficult. We present an analysis of SIGNSGD in high-dimensional limit, and derive limiting SDE and ODE to deseribe the risk. Using this framework we quantify four effects of SIGNSGD; effective learning rate, noise compression, diago- nal preconditioning, and gradient noise reshaping. Our analysis is consistent with experimental ob- servations but moves beyond that by quantifying the dependence of these effects on the data and noise distributions. We conclude with conjec- ture on how these results might be extended to ADAM.
The practical desire for simpler, more efficient learning algo- rithms as well the theoretical desire for simpler models to analyze have led a resurgence in the study of SIGNSGD. SIGNSGD is variant of SGD where the stochastic gradient is passed through the sign function a, leading to update vector of +1s On average, SIGNSGD's 's updates at every step have positive dot product with the average SGD step, but can have dramatically different convergence properties (Bernstein et al., 201 8a; Karimireddy et al., 2019). Multiple studies point towards sign-based methods as an effective proxy given that the sign component of the gradient has been shown to play important role in ADAM (Kunstner et al., 2023; Balles & Hennig, 2018; 8; Bernstein et al., 2018b), SIGNSGD is also the basis for new practical methods; the LION algorithm (Chen et al., 2023) combines SIGNSGD with multiple exponential moving averages, and SIGNSGD momentum was used to train LLMs with performance comparable to ADAM (Zhao al., 2024).
Despite the promise of SIGNSGD, detailed quantitative understanding of its dynamics in realistic settings remain elusive-in particular the nature of the preconditioning and the effect of the a function on the noise are not well under- stood. A crucial first step is to understand these effects on quadratic optimization problems.
1. Introduction
The success of deep learning has been driven by the effec- tiveness of relatively simple stochastic optimization algo- rithms. Stochastic gradient descent (SGD) with momentum can be used to train models like ResNet50 with minimal hyperparameter tuning. The workhorse of modern machine learning is ADAM, which was designed to give an approxi- mation of preconditioning with a diagonal, online approx- imation of the Fisher information matrix (Kingma, 2014). Additional hypotheses for the success of ADAM include its ability to maintain balanced updates to parameters across layers and its potential noise-mitigating effects (Zhang et al., 2020b; 2024). Getting a quantitative, theoretical understand-
Motivated by these questions, provide the first analysis of the learning dynamics of SIGNSGD in high-dimensional stochastic setting (Section 2). We make the following con- tributions:
We derive limiting stochastic differential equation (SDE) for SIGNSGD and combine it with a concentra- tion result to derive a deterministic ordinary differential equation (ODE) that describes the dynamics of the risk our setting (Section 3).
DDepartment of Mathematics and Statistics, McGill University, Montreal, Canada 'Google Deepmind, Mountain View, United States of America. Correspondence to: Ke Liang Xiao <ke- @iang.xiao@ mail.megill.a.>.
We compare the dynamics of SIGNSGD and vanilla SGD, isolating 4 effects: effective learning rate, noise- compression, diagonal preconditioning, and gradient noise reshaping (Section 4).
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Exact risk curves of signSGD in high-dimensions
We quantitatively analyze these four effects and their contributions learning, including exact results in specific settings (remainder of Section 4).
law (see discussion in (Tao, 2023) section 2.2). Formalizing this is left to future work.
In contrast, the distribution of the label noise has a nontrivial impact on the behavior of the process. We shall require that
Our work addresses significant technical challenges in an- alyzing both the preconditioning and noise transformation effects of SIGNSGD. Our analysis is consistent with more general experimental observations about adaptive methods, but provides more quantitative understanding in our set- ting. We conclude with discussion of the implications of our results for future study of adaptive algorithms, including conjecture on the limiting form of ADAM in an equivalent setting.
the noise is well-behaved in a neighborhood around O. Assumption 2. There exists og > such that the law of the noise has an C² density on 00, ao).
Assumption 2 ensures SDE (8) is Lipschitz (c.f. Lemma 12) and applies to many distributions; it encompasses heavy- tailed distributions such as a-stable laws, and we make no assumptions on any tail properties of the noise. Due to the non-smoothness of the a function at O, extraordinary behavior of the noise near 0 will lead to degraded perfor- mance of SIGNSGD as the risk vanishes. At the cost of less-informative theorem, it is possible to drop Assumption 2; see Theorem 6 in the Appendix.
In concurrent work, Compagnoni et al. (2025) also derives SDEs for SIGNSGD in the weak-approximation setting of (Li et al., 2019). We discuss this in more detail in Appendix G.
An important characterizing feature of SIGNSGD its ef- feet on the covariance of the signed stochastic gradients. We introduce the following transformations on K:
2. Problem Setup
Our work considers linear regression using the mean- squared loss f in the one-pass scenario, where data is not reused. SIGNSGD, with mini-batching of size b, is first initialized by some 0, E Rd and then follows the update rule:
K = D K and K2 =
n Ex (xx = aresin
Kij Kii
2
(4)
b VeC x khii))
0x+1 = 0 1 Σ
(9) xh11)
(1)
where D v diag K). We remark that K is similar in the matrix- to D kD thus K has all real, positive eigenvalues. K, proportional the covariance of (x)). We assume some properties of the matrices K, K, and K,,
i=1 C(O,x, x, = =I1 =11(x, 0) /2
(2)
where denotes the sign function applied element- wise
Assumption 3. Suppose:
and VoL(O,, xk+11 = ((O,, Xk+1) - 1/++1 1 Xx++1- 1. It
is typically assumed that the mini-batch (x 1k+1) for
(1) (1)
i). The spectrum of K is bounded from above and away from O independently of d.
1 S i < b are drawn i.i.d.
ii. The sign-data matrix K, also has operator norm bounded independent of d.
We will assume that the samples ((x, Me) hxz. consisting of data X2 and targets yk. satisfy the following:
iii). The resolvent of K defined by R( K. = KK
Assumption 1. The data x are mean O and Gaussian with positive definite covariance matrix K E Rdxd, The targets y are generated by y = (x, 0.) c, where 0, is the ground- truth and e the label noise.
=I) satisfies
max max |R(:: (R(2:K), O iSd iFj
(5)
Td
for all E OB2||K|| and for some do 1/12. (Equivalently, one may instead assume the same bounds with K replaced by K).
Definition 1. Define the population risk P and the noiseless risk R:
P(0)= (xxx)) [[(x, 0) 00-00)--))) -y) /2
(3)
The upper bound on K Assumption 3 (i) is standard and can always be achieved by rescaling the risk. But the lower bound is nontrivial assumption that is necessary for analyz- ing how a affects the stochastic gradient. Assumption 3 (ii) is convenient for the proof. A full understanding of when it holds is highly nontrivial; there exists some theory establish- ing it for some random K (Fan & Montanari, 2019). A sim- ple case where (ii) is satisfied when ||D 'KD -1] <
R(00) Ex (x, 0 - 0.) /2.
Although our theory is framed in the setting of Gaussian data, as we will see, the results are still good description for world, a priori non- Gan-Gassiinn settings (Figure 1). This an instance of universality, wherein the details of the data distribution do not affect the precise digh-dimensional limit
2

---

Exact risk curves of signSGD in high-dimensions
#igHt5GD 80 0%
sinHSGD 80. CI
signSGD
signSED 80.0%
1.8
eignODE
signODE
vanilaCDE Limil Risk
1.4
1.2
0.9
0.6
1000
2000
3000 leeations (k)
4000
5000
0
1000
2000
3000
4000
5000
lterations
(a) Gaussian noise
(b) Non-centered Cauchy noise
3.0
#0
signSGD
2.5
signDDE
eign
OODE
10%
vanilaODE
2.0
Theorem 3
Risk
Risk
10a1
0.5
0.0
101
10P
169
16+
0
10 10a
161
16a
llerations (k)
Ilerations (k)
(c) CIFARIO data, assumed Gaussian noise
(d) IMDB movie reviews data, assumed GMM noise
Figure Dynamics of the risk under SIGNSGD and SIGNHSGD on synthetic and real datasets. SIGNHSGD and its deterministic equivalent ODE are good models for the risk dynamics even for d 500 (a, b) or on real datasets (c. d). The convergence of SIGNSGD for Cauchy noise (b) is remarkable given that SGD fails to converge there. The usefulness of the ODE CIFAR10 10 and IMDB movie reviews is remarkable due to the non Gaussan nature of the data, and the significant estimation of key quantities like 0, or c. For the CIFAR10 dataset, we validate the results of Theorem 3 which gives the limit risk of SIGNODE under Gaussian data. We include the deterministic equivalent for SGD (VANILLAODE) for reference. Details of these experiments may be found in Appendix I.
Assumption (iii) can be interpreted condition that the eigenvectors of K contain Now-dimensions structure: for
Oo satisfies
PP ([( - 0.) 2 s C Cexp ((z;; 1))
example, it is satisfied with high probability if the eigenvec- tors of K are taken to be uniformly random. Additionally, trivially satisfied for any diagonal K. For a further discussion, including applicability to real data, see Paquette & Paquette (2022), Figure 2.
(7)
for all Sii d with absolute, positive constants c, C.
For example, this assumption holds for any initialization and target generated by normalized Gaussian. In the case that the initialization and target are deterministic, 0g O. have entries of order O 2 then rotating the data x by a diarrdistributed orthogonal matrix U, we obtain a new data covariance matrix A = UKUT, Moreover, A R /d/ Tr(K) with high probability, See (33). It follows with high probability that R(2; A) URR (3/E:: K) UT where & v Tr(K)/d. One may then derive simi- lar probabilistic bound as in (7) on nom-syrmetric rays (-xc, -t + O and tt+ ++0(7)) oo). where the proba- bility is now taken with respect to U.
We assume the learning rates have high-dimensional limit- ing profile:
Assumption 4. The learning rates follow
n(t/d///
(6)
where yj R+ R is a continuous bounded function. We will write nu for ntt).
This scaling is critical: it ensures that as the problem size grows, both the bias and variance terms in the risk evolution balanced (see e.g. Equation (25)).
Finally, we assume the initialization remains (stochastically) bounded across d:
3. SIGNHSGD
The analysis of SIGNSGD in high-dimensional settings presents a unique set of technical challenges and requires
Assumption The difference between Q., and initialization
3

---

Exact risk curves of signSGD in high-dimensions
careful mathematical treatment. A core difficulty lies in the transformative effect of the sign operator the gra- dient. Unlike traditional SGD, where the gradient di- rection remains consistent with the magnitude of the up- date, SIGNSGD changes the gradient's direction, via a non- Lipschitz compression operation. This compression alters the optimization landscape observed by the optimizer, in ways we will explore in Section 4.
Theorem 1 (Main Theorem, part 1). Given b 1, Assump-
tions 1-5 and choosing any fixed even moment 2p E (0, d) there exists a constant C(K, e) > 8 E (1/3.1/2) and all T > 3,
0 such that for any
sup IR(O tdj) - R( 5 uSisT
Td ||
(11)
exp (C(K,() Ilull 7),
Vd
Nonetheless, show that under the assumptions above, there is continuous stochastic process Sign-Homogenized SGD (SGGN which captures the high-dimensione behaviour of SIGNSGD; see (Thygesen, 2023) or (Karatzas & Shreve, 1991) for background on SDEs.
with probability at least 1 - c(2p, K))p(1/3-6) for con- stant c(2p, K) independent to d.
In other words, the risk curves of SIGNSGD are well approx- imated by the risk curves of SIGNHSGD and this approxima- tion improves as dimension grows. Numerical simulations suggest that in practice this correspondence is strong even by d = 500 (Figure 1 (a), (b)). Other statistics like iter- ate norms or distance to optimality can also be computed using general result across quadraties (Theorem in the Appendix).
Definition 2 (SIGNHSGD). We define O2 as the solution of the stochastic differential equation:
(b)) (R(O.) -())-o.)d(+m do;- NB (2)(@.)
2
dB,, rd
(8)
with initial condition O = Op. Here, the constant No-- E] ZZ,,.... Zb)l1//B|Zz, [I for i.i.d. standard normals
The risk curves of both SIGNSGD and SIGNHSGD con- centrate around the same deterministic path. Let R; be this deterministic equivalent of SIGNSGD; we will refer to the solution as SIGNODE for reasons that will soon be made clear. In order to find the deterministic equivalent we intro- duce family of scalars {ri):- which loosely correspond to the magnitudes of the residual O O. projected onto an cigenbasis (see Appendix B). The sum of these scalars then gives the deterministic equivalent for the risk:
7,j. and
p(0) (R(O.)
2 π
Ers
exp O.)
where 6 = Ei Ows for (1 and {wi iid samples of and entries of b-dimensional uniform vectors on the sphere, respectively.
Remark 1. No may be computed explicitly to be
R4 def
rl)))
(12)
T((b+ + 1)/2) vb as b - co. N₂- ((6/2)r(1/2)
(10)
The scalars r; follow a coupled system of ODEs:
This is consistent with the square-root scaling hypothesis, as the bias increases relative to the noise by a factor of square- root of the batch (which leads to the popular square-roo learning rate scaling rule).
dr;
dt = -21 (R..))
w Ku
A (K)r: + m rd
(13a)
/2R,
1
r:(0) = 2 (0, 0. Ku,) (w; Oo 0.)
(13b)
Remark 2. In the case e 0, we take (x) 2/m. While this does not satisfy Assumption 2, we formulate Theorem 6 in the Appendix which covers this case.
where {; u, and w; are the eigenvalues and left/right eigenvectors of K respectively. A similar argument, can be used to derive coupled system of ODEs that describe the risk of vanilla SGD (Collins-Woodfin & Paquette, 2023), which we will call VANILLAODE (Appendix B).
It is worth noting that, in practice, (p(²) is often easy and inexpensive to compute numerically; we compute it analyti- cally for some common distributions (Figure 2). In general, is simple to fit a Gaussian mixture model to the noise and use that to compute (00)) (Appendix I).
We can now present a deterministic version of Theorem 1: Theorem 2 (Main Theorem, part 2). Let Re be given by (12) and (13). Then given Assumptions 1-5 and choosing any fixed even moment 2p E (0, d) there exists constant C(K,) c) > O such that for any 5 E (1/3,1/2) and all T>3 3,
For the remainder of this paper, we focus on the single batch setting, i.e., b- = 1. For notational convenience, we will write sp in place of (1) in the single batch setting. Numerical validation of our main result, Theorem 1, for larger batch sizes (b> > 1) may be seen in Figure 5.
sup (R(0(1d)) Rol $ 05:5T
(14)
We can now state the first part of our main theorem:
112 1/2 K exp (C c) |1 T),
4

---

Exact risk curves of signSGD in high-dimensions
Distribution
(0x))
0.5
(0,02) 02)
2v
0.4
+22
Rademacher
exp
1z
N(0, v*)
Unif (-1,1)
2 2 erf
2/
1
0.2
Rademacher Unii(-1,1)
LAvy(A)
exp
- 2r
A
0.1
Root-Levy
10
10
10
10
Figure 2: Examples of yp for simple noise distributions. VLevy has Cauchy type-tails and vanishing density near 0. We note that (xx) is trivially bounded above by and converges to 2 as - the rate of convergence at is related to the tail decay rate. At (xx)/ vx converges to the density of the noise at 0 scaled by 2/T.
with probability at least 1 - c(2p, K)dp(/338)) for a con- stant c(2p, K) independent to d.
do,
-ipt
SGD & (R(O.)) D K(O, -0.)dt
e-compress. D.Precodd.
2Kg
(17b)
This ODE captures the behavior of the risk even at finite d 500 (Figure (a), (b)). Moreover, it seems capture the behavior of high-dimensional linear regression real, non-Gaussian datasets as well (Figure (c), (d)).
+
dB,.
Reshape
Comparison of the minibatched version can be found in Appendix D.
4. Comparing SIGNSGD to vanilla SGD
We summarize the precise effects below:
To produce an apples-to-apples comparison, we compare the SIGNHSGD to the analogous SDE for vanilla SGD from (CollinsWWoodin & Paquette, 2023):
Effective learning rate. The effective learning rate of SIGNSGD can be considered as risk dependent, effectively matching the expected (2-norm of gradient.
do SGD
-
SGD
K(O O.)dl
2KP (OSG)
(15)
SGD :
dB.
e-compression. The distribution of the label noise (be from moodel-misspccificatio otherwise) rescales the bias term. Formally, letting o² E
To control for the adaptive-scheduling inherent in SIGNSGD, we run vanilla SGD with risk dependent learn- ing rate schedule of
SGD given by
(xxx Tx((x) V 2x 02
(18)
2v2x
SGD 1/1 π
T OS
7
V x, v
(16) which to say that scale the steps in SGD inversely proportional the norm of the gradients. We note that the P-risk requires the noise to have finite variance indeed if the variance is infinite, then SIGNSGD is overwhelmingly favored, see Remark in Zhang et al. (2020a). Training SIGNSGD with learning rate 7/ and SGD with learning rate SGD, we can use (8) to write, with va as (18)),
Diagonal preconditioner. The matrix D-1 gives the diag- onal preconditioner (D;: VK,)).
Gradient noise reshaping. Finally, passing the gradient through the a function results in different covariance struc- ture to the gradients, which is accounted for in the differing diffusion term.
4K
Although all the effects appear in concert SIGNSGD, we will now attempt to isolate and address each one separately in the following sections.
SGD
SGDD SGD 0.)dt n ad
1/t
(17a)
5

---

Exact risk curves of signSGD in high-dimensions
4.1. Effective learning rate and convergence
s can be interpreted as oc, corresponding to overwhelming SIGNSGI favor, although the quantitative meaning in (17b) breaks down.
We recall that to match the learning rate of SGD to SIGNSGD, we had to use the identification (16),
In the Gaussian case, 3 = 1. Hence, we can interpret &b as the effect that deviation from Gaussianity has on the drift term of the SDE. We note that all the influence of the label noise e on SIGNSGD is entirely through (20) which in turn only depends on e², Hence SIGNSGD symmetrizes the noise distribution.
SGD 2
Th
2 T
O SGD
In particular, the effective learning rate gets smaller when the optimizer's position is far from optimality and gets larger as it gets closer. In the convex setting this is generally undesirable at both extremes. When far from optimality, the algorithm slows far beyond what would tend to be favorable, while at small risks this behavior can impede convergence. On the other hand, it can easily be addressed by using a learning rate schedule.
A full comparison of SGD and STGNSGI requires optimiz- ing the learning rates of both algorithms independently. We will show that in the case of isotropic data, this procedure is tractable and produces a different threshold t/ = z above which SIGNSGD is favored (see Equation (28)).
2
In nonconvex setting, identifying 2P( with the ex- pected square-norm of the gradients (c.f. (16)), one possible benefit of this schedule is that it may be helpful in dynami- cally adjusting to saddle manifolds in the loss landscape.
2.
d
df -
2.0
df= 10
1.8
4f 30
x/2
1.8
4.1.1. STATIONARY POINT OF SIGNSGD
1.4
If the learning rate any constant 7) = 1). we have a unique stationary point of the ODE system (13a) which is locally attractive. The 77 dependence of this stationary point demon- strates the effect of an aggressive learning rate, which is accentuated in the presence of small noise variance v.
12
1.0
10a1
10P
10'
10
R
Theorem 3. With fixed learning rale '): = E (0, oo) and E E NO0, )²), the ODEs have a unique stationary point [s : 1 S i < d) given by Equation (244). Then, the limiting risk, Roc- = Σ St, is given by
100
(iR))
10-1
Tr Tr(D)
72 TT()3
Rox
Tr(D)
1602
N(0, v*)
32d
2d
4d
Rademacher
(19)
10
Uni((-1.11
10
10
10"
10'
Notice that the limiting risk's dependence on 1) changes depending on the relationship between 17 and v, for small n it will be proportional to 17. See Figure/ for numerical validation, and see (255) for analogous SGD limit risk.
R
Figure 3: Top: vb for Student's s-l. Here v is always greater than 1 and e-compression accelerates SIGNSGD, For suf- ficiently small df. 1b > n/2 over some range of R and SIGNSGD also converges faster than SGD in the isotropic setting. Bottom: sp for (O, o²), Rademacher, U,,
4.2. c-compression
The influence of the distribution of the noise on the opti- mization, in the case of finite variance, can be summarized by (c.f. (18) and (9))
Setups favoring SIGNSGD. In the presence of heavy tails, (R) can be large and hence SIGNSGD is very fa- vored. Indeed, among some parametric classes, such as the Student's- s-t family, this is observed numerically to always be larger than 1 (Figure 3, left) and increase to oc as the kurtosis increases. More generally, as R. tends to 0, letting fc (0) be the density of the noise at 0, one has
E|22]
(R) = E
exp
X
(20)
4R
2R
When v < 1, the descent term of (17b) is decreased, and hence SIGNSGD is slowed with respect to SGD with learn- ing rate Ty SGD Conversely, when 1b >> the descent term increased, and SIGNSGD is favored. When [](2] = co,
lim (R) = 22 R-0
(21)
6

---

Exact risk curves of signSGD in high-dimensions
which can be arbitrarily large, in particular when the noise distribution puts more mass in its tails than at O.
If we greedily optimize in 7/2 we arrive
dR, di ( where ti = =
Conversely, for all distributions, we also observe that when the risk is relatively large, SIGNSGD is always modestly favored over SGD under the xDSD learning rate as we have
(26)
So generally for large risks, the optimal stepsize compen- sates for the effective gradient rescaling (16). This com-
2
2 S (R)
E E 1+
pensation is seen for all risks in the Gaussian setting.
1 EEE
1
4R
R
R
As point of comparison, for the SGD risk ODE RS with learning rate n7², which can be derived from (15):
may repeat the same procedure
(22)
for all |
dR = 21/ R + dt
(n)))
Setups where SIGNSGD does not improve. For light- tailed noises, the factor 10 can only mildly favor SGD. A density I on R is called log-concave if it can be written as e for concave (see (Saumard & Wellner, 2014) for discus- sion). The exponential, uniform and many other canonical noise distributions are log-concave. Note these decay no slower than exponentially at infinity. Then as ((R)//VAR the density at 0 of log-concave density, Saumard & Wellner (2014), Proposition 5.2 gives us
(2R + 0²)
2
(27)
dRg
2R,
R
(optimized in on))
dt
215 + 02
Hence (26) can also be expressed as
dig di -
(
2R,
x 2R, + + R..
(28)
Thus the performance benefits of SIGNSGD using the opti- mal learning rate can again be reduced to a question of the magnitude of sb albeit with a crossover at &i = π a/2.
(R) S 2nT.
(23)
In the non-isotropic setting, locally greedy stepsizes can be very far from optimal, even with two eigenvalues (Collins- Woodfin et al., 2024). But expect the conclusion of (28) remains mostly true in well-conditioned settings.
Hence, for these distributions, while there may be limited gains from using SIGNSGD, they are bounded by an abso- lute constant factor.
Setups where SIGNSGD is catastrophic. In the situation that the noise is bounded away from 0 by some 6, it follows that we have the upper bound:
4.3. Diagonal preconditioner
Next, and strikingly, we see that SIGNSGD performs diagonal preconditioning step on the gradients. with the preconditioner given by D = VK E where x is a sample. To produce this bias term in SGD, we would need to run the algorithm
52 (R) S IR
Eie2]
1
(24)
2R
This tends 0 exponentially in 1/R (e.g. see the Rademacher case of Figure 3). For such noise distributions, SIGNSGD will effectively experience floor on the risk, which is completely induced by distributional properties of the noise (and unrelated to the underlying optimization prob- lem geometry). In this situation, SGD is heavily favored for small risks, which are seen late in training.
B = 02 - DD D- (VoL(e,x,) v))
(29)
We expect the dynamical preconditioner in ADAM also sim- plifies to in high- digh--imenssons; for details, see Appendix F.
As K appears naturally in (8), its spectrum regulates the rate of convergence of the optimization to stationarity. By utiliz- ing our d-systems of ODEs we can establish the following convergence rate:
Scheduling SIGNSGD. We have discussed adjusting the SGD learning rate to match the behaviour of SIGNSGD. However, when using SIGNSGD there is the question of how to optimize its learning rate. This is analytically tractable for isotropic data K = La, for which K = K and K, _ I, which allows us to isolate the effects of the label noise. It is easy to check that the d-system of ODEs for SIGNSGD in (12) may be reduced to the following single ODE:
Theorem 4. Assume e ~ N(0, 02) and let 8; be the sta- tionary points to (13a). Then there is an absolute constant so that if
Tr(K)
4u
" 2d
S min
and Ro S cv,
(30)
then we have, setting Roo = Di 81 to be the limit risk,
dR: dt
(R,) V2R,
T12
R2 +
2
Ro R(0o). (25)
RR Rool S 2( + Roo tnnmmi (R)((r))
(31)
7

---

Exact risk curves of signSGD in high-dimensions
The proof is given in Appendix C. In contrast to vanilla SGD, where the risk converges (in a high-dimensional set- ting) with rate . where k(K) (Kmis(K] is the average condition number (Paquette et al., 2022b). Theorem states
4.4. Gradient noise reshaping
Trrk)
Finally, there gradient noise reshaping, wherein the SGD gradient noise matrix K is replaced by the matrix K,, up to constants. This is a complicated mapping; there is no short answer about the impact of this effect. In some cases passing from K + K, might affect the magnitudes of the eigenvalues but not their structure; see Figure 4 for an example on CIFARIO.
that the risk of SIGNSGD converges at rate Tr(K) (Amii(()) after selecting the largest allowed 17. SIGNSGD is therefore favored over SGD when <(() < x(K). See Figure for experimental validation.
In the case that K itself is a sample covariance matrix, the matrix K, is strongly related matrix, for which there is a large literature. This includes properties of bulk spectra (Karoui, 2010; Cheng & Singer, 2013) 3), norms (Fan & Montanari, 2019) and more.
Settings in which the preconditioned K is preferable. Theorem 4 shows that the rate of convergence is governed entirely by K. The clearest setting when this is favourable is if K is diagonal, so that K = K. In this case, the convergence rate is, up to constants
kernel inner product
When K a diagonal matrix then K, = 2 and so this can be considered type of preconditioning of the gradient noise, albeit with more aggressive preconditioner than D.
1 (r
1 Tr d
à (r) v VAmiu (K)
(32)
d Amin KK)
Vmmin K)
We expect that for K with power-law spectra, often seen in practice in vision (e.g. in Figure 4) and language embed- dings, K,, again has powerlaw spectra of the same exponent. Beyond the spectral distribution, replacing K by K, may also serve to slightly break the alignment of large directions of gradient variance from large gradient biases (they are perfectly aligned in SGD), which should be beneficial both to stability of the algorithm and performance.
Hence on diagonal problems, SIGNSGD attains a speedup over SGD commensurate to the speedup of optimal deter- ministic convex optimization algorithms such as Conjugate gradient over gradient descent (Nocedal & Wright, 2006).
Diagonally dominant matrices should see similar benefits consistent with prior work showing that SIGNSGD is effective when the the Hessian of the risk (K in our setting) is sufficiently diagonally concentrated (Balles et al., 2020).
second situation in which one may have substantial speedups are for block-diagonal K. where the blocks are scaled by greatly differing constants; diagonal precondi- tioning by D partially corrects for this effect. It has been argued that one of the principal advantages of ADAM is that it correctly adapts learning rates across different layers of Transformers and MLPs (Zhang et al., 2024), which can have similar structures in their Jacobians.
K.
10
10
10
10"
10
10
10a
Log eigenvalues
Settings in which K does not help. Like precondition- ing generally, K does not always have smaller condition number than K. See Appendix H for counter example.
Figure 4: Log eigenvalues of K, K, K, computed for the CIFARIO dataset.
In addition, if the cigenvectors of K are randomized to make a new covariance matrix A, say by performing a uniformly random orthogonal change of basis, the entries of the diagonal of A will concentrate be
5. Minibatching
Although our main theorem is established for a batch size of 1, we can numerically validate SIGNHSGD at larger batch sizes b > (Figure 5). SIGNHSGD with b > exhibits all of the same core properties as the single-pass case, i.e. preconditioning, c-compression and gradient reshaping. The two main differences between b = and b > 1 can be seen in scaling factor N₂ (see Remark 1) and e-compression (b()) found in the drift term of SIGNHSGD. When > 1, the noise compression factor (b) becomes the expectation of function of the risk across a distribution that differs from
Tr(K) d
max A#
(loogd)dd113 (33)
and so the preconditioner diaggA) A1/ does not affect the condition number of A. Thus, the benefit of diagonal pre- conditioning is strongly tied to special properties of the basis in which the optimization is performed (Nocedal & Wright, 2006).
8

---

Exact risk curves of signSGD in high-dimensions
the original noise. This can have significant effects on the noise compared to single-pass. Indeed, when b 1, Wi as defined in (9) is not identically 1, allowing eb to gain some regularity over e Which is to say that (0(0) may have improve decay rate of no-worse than (v)R) when R approaches O. This due to the addition of a density wi. A straightforward application of the Lebesgue differentiation Theorem reveals that (R)) / can be bounded from below by (())) where C' is absolute constant and f denotes the respective density, in the small risk regime. For example, in the Radamacher case, in which yp(t) can be very badly behaved at small risk, E, simply becomes the law of an entry of a spherical vector, which is a good unimodular, bounded density. In addition, as batch grows, the yp will be pushed into the Gaussian regime due to the central limit theorem, provided that (f) has second moment.
of non-Gaussian data. We note that our analysis is in qualitatively different regime than the concurrent work of Compagnoni et al. (2025); see Appendix G for more details.
More detailed analysis of the effects of non non-diagonal co- variance is a key future direction. There is an active area of research on the benefits of non-diagonal preconditioning methods as an alternative to Adam variants, and studying the non-diagonal case in SIGNSGD may provide more insight into cases where the diagonal preconditioner is insufficient to improve optimization. Our SDEs and ODEs provide the tools to analyze such settings.
Though our work focuses on the case of MSE loss and linear regression, there a path towards extending results to more general settings using recent results in high-dimensional optimization "Collins-Woodife et al., 2023). In practical settings, models undergo dramatic changes in local geom- etry during training; nonetheless, stability analysis of the linearized problem is still useful for understanding aspects of the non-linear dynamics of these systems (Cohen et al., 2022; Agarwala & Pennington, 2024).
Rademacher noise, with batch and compensated learning rate
Risk
Batch 1
Finally, our analysis of SIGNSGD gives hints towards un- derstanding ADAM in similar setting. A heuristic anal- ysis shows that ADAM has homogenized process simi- lar to SIGNHSGD: it appears to share the preconditioner D while differing from SIGNHSGD in its noise compres- sion and gradient noise effects K,, (Appendix F). For well- behaved noises e, SIGNSGD should be nearly path-identical to ADAM: we note that LION has been recently observed to do just that (Zhao al., 2024). We leave investigation of ADAM for future work.
Batch 4
Batch 9
Batch 16
Batch 25
Batch 100
Iterations/dimensioon
Figure 5: Minibatch-SIaNSGDD versus theory. SIGNHSGD and SIGNODE adapt to this case, in (8). LR rescaled by inverse of square-root-batch (more specifically by 1/N,) to illustrate square-root scaling.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
6. Discussion
Our high-dimensional limit sheds quantitative light on the precise ways in which SIGNSGD can be compared to SGD, via change of effective learning rate, noise compression, preconditioning, and reshaping of the gradient noise.
Acknowledgments
Theorem 2, the main technical contribution of this work, required substantial technical efforts. Although similar in formulation to existing work like Woond-- et al. (2024), there are technical complexities in working with the nonsmooth a function: both terms of deriving the relevant concentration of measure estimates (the textbook versions of which require smoothness) and in terms of the additional pathology of the resulting SIGNHSGD (especially the sp). We believe that a version of Theorem 2 is true in much greater generality than we have proven it, even for the lin- ear setting: two desirable mathematical generalizations are quantifying dimension intrinsically (instead of through the ambient dimension) and generalizing the theory to settings
We would like to thank Courtney Paquette and Lechao Xiao for taking the time to proofread and provide feed- back throughout the writing of this paper. We would also like thank anonymous referees for suggesting the natural extension to minibatching.
Research by E. Paquette was supported by Google Grant and a Discovery Grant from the Natural Science and Engi- neering Research Council (NSERC) of Canada.
9

---

Exact risk curves of signSGD in high-dimensions
References
notes: An ode for sgd learning dynamies glms and multi-index models. arXiv preprint arXiv:2308.08977, 2023.
Robert J. Adler and Jonathan E. Taylor. Random Fields and Geometry. Springer New York, 2007. ISBN 9780387481 166. doi: 10.1007/978- 11199788--33888 16-6.
Elizabeth Collins- Woodfin, Inbar Seroussi, Begoña García Malaxechebarría, Andrew W Mackenzie, Elliot Paquette, and Courtney Paquette. The high line: Exact risk and learning rate curves of stochastic adaptive learning rate algorithms. arXiv preprint arXiv:2405. 19585, 2024.
Atish Agarwala and Jeffrey Pennington. High dimensional analysis reveals conservative sharpening and stochastic edge of stability, arXiv preprint arXiv:2404. 19261, 2024.
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.
Enea Monzio Compagnoni, Tianlin Liu, Rustem Islamov, Frank Norbert Proske, Antonio Orvieto, and Aurelien Lucchi. Adaptive methods through the lens of SDEs: Theoretical insights on the role of noise. In The Thirteenth International Conference Learning Representations, 2025. URL https:/ http///pwpeeeneeeeeeeeeeeeeeeeee 3d=ww3CLRhET
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux. The geometry of sign gradient descent, 2020. URL https: //openreview net/ /tt.:/runnuneeeee wttp://ormmmiidii dormmmidddDDe11pP
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzade- nesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause (eds.), Proceed- ings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pp. 560-569, PMLR, 2018a. URLhttps: http:///ooceeddeeeeeee ngs mlr. www..m...........mmmmm..m......e wwwppprwssss/eeep Mernstein18a.nce
Zhou Fan and Andrea Montanari. The spectral norm of ran- dom inner-product kernel matrices. Probability Theory and Related Fields, 173:27-85, 2019.
loannis Karatzas and Steven Shreve. Brownian motion and stochastic calculus, volume 113. Springer Science & Business Media, 1991.
Sai Pranceth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Interna- tional Conference Machine Learming, pp. 3252-3261 PMLR, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint arXiv: 2018b.
Noureddine El Karoui. The spectrum of kernel random matrices. The Annuls of Statistics, 38(1):1 50, 2010. doi: 10.1214/88-OO6688 URL 10. 11111211100-55--1
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang. Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, and Quoe V Le. Symbolic discovery of optimization algorithms. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:t///// /ttttp:::/openeie http:///ppeeeeeeeeeeeemee www/eeetuuurre Ad=ne6zeqLFCE
Diederik P Kingma. Adam: A method for stochastic opti-
mization. arXiv preprint arXiv:1412.6988 2014.
Alex Krizhevsky. Learning multiple layers of fea- tures from tiny images, 2009. URL https://api.
Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices. Random Matrices: Theory and Applicatiios, 2(04))1350010, 2013.
cemanticscholas www.laa..rroooopuoottta 182668744
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lav- ington, and Mark Schmidt. Noise is not the main fac- tor behind the gap between sgd and adam trans- formers, but sign descent might be. In The Eleventh International Conference Learning Representations, 2023. URL https:/ /openreview net forum? 1 dd 65YK0cqH8..
Jeremy M Cohen, Behrooz Ghorbani, Shankar Krishnan,
Naman Agarwal, Sourabh Medapati, Michal Badura, Daniel Suo, David Cardoze, Zachary Nado, George E Dahl, et al. Adaptive gradient methods at the edge of stability. arXiv preprint arXiv:2207. 2tti:2207..14888 14484, 2022.
Elizabeth
and Elliot Paquette. High- dimensional limit of one-pass sgd on least squares, 2023.
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. Journal of Machine Learn- ing Research, 20(40):1 1-:00) 2019.
URL attpss:/aazet org/ abs/2304. 06847.
Elizabeth Collins- Woodfin, Courtney Paquette, Elliot Pa- quette, and Inbar Seroussi. Hitting the high-dimensional
10

---

Exact risk curves of signSGD in high-dimensions
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learn- ing word vectors for sentiment analysis. In Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (eds.), Pro- ceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Tech- nologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguisties. URL https: htaas////oo/aaahloooyoo org/P11-1015,
Herbert Robbins and Sutton Monro. A stochastic approx- imation method. The annals of mathematical stafistics, pp. 400-407, 1951.
Adrien Saumard and Jon Wellner. Log-concavity and strong log-concavity: a review. Statistics surveys, 8:45, 2014.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Society, 2023.
Sadhika Malladi, Kaifeng Lyu, Abhishek Panigrahi, and Sanjeev Arora. On the sdes and scaling rules for adaptive gradient algorithms. Advances in Neural Information Processing Systems, 35:7697-7711, 2022.
Uffe Høgsbro Thygesen. Stochastic Differential Equations for Science and Engineering. Chapman and Hall/CRC, 2023.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Su- vrit Sra. Why are adaptive methods good for attention models? H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Informa- tion Processing Systems, volume 33, pp. 15383-15393. Curran Associates, Inc., 2020a.
Jorge Nocedal and Stephen J. Wright. Numerical optimiza- tion. Springer Series in Operations Research and Finan- cial Engineering. Springer, New York, second edition, 2006. ISBN 978-0387-30303-11 0-387-30303-0.
Courtney Paquette and Elliot Paquette. Dynamics of stochas- tic momentum methods on large-scale, quadratic models. Advances in Neural Information Processing Systems, 34: 9229-9240, 2021.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? arXiv preprint http:///arzivoor///////111111113 2020b.
Courtney Paquette and Elliot Paquette. dimensional optimization. News, 20:16pp, December 2022.
High- SIAM Views and
https:
//siagopttimzzziionn.go views//VeewsnndNewss 30..
io/assets/
Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhi- Luo. Why transformers need adam: A hessian perspective. arXiv preprint a7Xiv:2402.16788, 2024.
Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of sgd in nigh-dimensions: Exact dynamics and generalization properties. arXiv preprint arXiv:2205.07006 2022a.
Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, and Sham Kakade. Deconstructing what makes good optimizer for language models. arXiv preprint 20070:240..07772 2024.
Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Implicit regularization or implicit condition- ing? exact risk trajectories of sgd high dimensions. Advances in Neural Information Processing Systems, 35: 35984 35999, 2022b.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cour- napeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit- learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Jeffrey Pennington, Richard Socher, and Christopher Man- ning. GloVe: Global vectors for word representation. In Alessandro Moschitti, Bo Pang, and Walter Daelemans (eds.), Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1/114-1162. URL https:ttp///.c....t. //tss:///llaaee www.ollnnooooyyyyooooooooooooooe hwtp:/looooo.og/111100/0 http:////..aaaooooooooooo///----

---

Exact risk curves of signSGD in high-dimensions
Overview of supplementary material
The supplementary material is primarily dedicated to the proofs the main theorems, Theorem and Here we give the organization of the appendices.
In Appendix A, give the proof of these main theorems, including their extensions in Theorem 5 and 6. The key approximations to the update rules of SIGNSGD are given in Appendix A. including the key technical Lemma 3. In Appendix A.2, we show how these tools are used to give the main proof (but we defer the estimates the stochastic errors to Appendix A.4), culminating in Lemma 7, which in fact proves the main theorem statement (that of Theorem 5). In Appendix A.3, we discuss the extension Theorem as this is a modification of the proof Theorem 5, we do not go into details.
In Appendix B, give the derivation the ODEs SIGNODE and VANILLAODE from their homogenized counterparts, and discuss the proof of Theorem 2, which follows the same strategy Theorem 5 (for full details of this type of ODE comparison, (Collins-Woodle Woodfin et al., 2023)). Here also, we discuss the derivation of the VANILLAODE, which is special case of (Collins-Woodfnn et al., 2023).
In Appendix C, we proof the analysis of the SIGNODE and VANILLAODE that gives its limit level (Theorem 3) and a local convergence rate (Theorem 4).
In Appendix E, we provide additional supporting simulations, corroborating aspects of the main theorems.
In Appendix F, give heuristic derivation of the high- nigh-dimensional limit of ADAM.
In Appendix G we show the "Weak Approximation" theory of ADAM produces a different SDE predictio (see the discussion there as well).
In Appendix H, we give an example of a matrix where diagonal preconditioning hurts.
Finally in Appendix I, we give some additional information how the experiments were performed.
12

---

Exact risk curves of signSGD in high-dimensions
A. Proof of Main Theorem
A.I. Approximation of the conditional updates
For simplicity of our proofs, we will assume 7j is constant as well as batch-size is 1. The proof remains unchanged if v defined as in Assumption 4 and if For the convenience of the reader and avoid confusion, we provide the typical notions of convergence in high-dimensions.
Definition An event A C R holds with high--robbbbllty, if there exists some > independent to such that P(A) 21 Cd for some C independent to d.
Definition 4. An event A C Rd holds with hrepwheliiing-rrbbbbiig if for all 5 > O there exists Cs such that P(A) 2
1 Cad
Denote F& to be the natural filtration generated by the data {x, } and the label noise {ez Le))-=- For notational convenience, we define the "centered" SIGNSGD iterate Vv: = 0 0.. We also denote R₁ = R((x)) when is clear.
Notice now, that the k + 1th update SIGNSGD is given by
Mk+1 - V4: = d (x ex-1).
(34)
key component of our proof aims to compute the mean of this update (conditioned on .P)) and then simplify this mean by introducing errors which vanish in gigh-dimensions.
Lemma 1. Conditional on Fks the mean of the i-th element of (34) given by
7 (xx( " 2 22 (0) (K,,
v
2hg VV π
(35)
where, denoting L. as the law of the noise,
-(x + y)
(x) =
exp
(Ki, vn) )/)))) dL)
(36)
2T 2Rxx (K,, vz)
JR
2 (2R2x
and
(( ((K,.
(Kis Xi+t] )
x
)
R Rk+1= =
(37)
Proof. Following the update rule (1), we start by computing the conditional update of the i-th entry of the iterates
E [pk+i - vilFe]
- 7 E [x(x ((x
Ek+1)|
(38)
= = o (x E
Dixt+1 + Σ u1xp211 ext1
|
Fis xh+1
Fx
(39)
Given that the data Gaussian distributed, upon conditioning on Fx we see that
En(e (0, 2R, 2n (K,,)) ka(x)))).
(40)
jti
Additionally, for is any constant, we can write
ΣV
- -arixtrr) + +avixtn
(41)
171
13

---

Exact risk curves of signSGD in high-dimensions
Let = Ejz 2 x/xx+11 x Choosing G; (K.,))) makes y' uncorrelated to x and hence independent.
K
Additionally, notice y² [00,2R - (K, vz)) Moreover, since y' is independent to ck+1 their difference yi cx+1 has density given by
(x + 32²
(x)
=
exp
dC.
(42)
V 2T (2Rx (K,; un)
JR
2 2R U1)
Using (42), we compute
v xxx + Σ C2x -E4t] -(0t1)
E
o (y² co+1 + (1 + Cs 2/ x 1) FRx xk+1 E
(yi - -(1 + cs 2 x1) P F (vi -ui-ce cx+1 (0+-1 -(1 + c))(x()))
Ek+1
- -(4taieextt ()(x) de - /
- (1+00)))x
(x) dr.
(43)
Define
H(s) = [ 000 (x) dr 1T (x) (z)
H())
(44)
where upon differentiating it is easy to see that
11(s) 2h (-s).
(45)
Taylor expanding around () we obtain,
)
E σ
Σ
v x eat1)
Fri xta2
-1((1 +c)((x++1)
(Ki, Mi)
H(0)) 20)
Kis x
(K)
2
+ ds
h (0)
Kis Si6tt
+ R
(46)
where
R O ((
((K,, Xi+t] )
(47)
Plugging this back into (39) yields
(Ki
xbots ) Fit
[M - v([Fa]]
= -
" F
(x((1))
H((0) 2h)
Kis
d
" R
o (x((11)
d
(2((0)
(Ki
x/ot1)
+ Birt Fx
ds
Kis
(2)
(K,, vk)
Elxt+11
y 2B8O +1 R
Kii
2
- 222t(()
(K, V
"E[o(xi+
d
1) R
(48)
14

---

Exact risk curves of signSGD in high-dimensions
In the next two lemmas will show that for all I i S d, the risk dependent factors 2 2 hi (0) can be well-approximated
by V2R. (RR)), where
2
{ exp
y²²
((R))
d..
(49)
J
4Rx
To do this, we will show that: v1) O(d for some 0. Additionally, this would also imply the enror R vanishes as d - co. This simplifies (35) by removing the latter error term and reducing each hig into single constant factor, i.e.
vk+1 - v/ Fi = " (R&))
E
(k,,
(50)
d V2R
Our proof makes use of the resolvent R(z; K) = (K -x=1))- =1)-1 , matrix valued function essentially encoding powers of K. The following lemma will allows us to to control (K U/) by finite net of resolvents.
Lemma 2. There exists net To C of order (dd) and C(K) O such that for all is and 1 15i5 d,
(Ki S OK
max max sEI' ISiSd
[[2; [2;;
(51)
Proof. It is easy to check by the Cauchy's 's integral formula that
$ KK, 2 Jr
R(2;;)) dz.
(52)
By Assumption 3, we may bound [R(2; K): for all 2 E I by finite collection of 20 T. Indeed, I' is L/ on r then |ol Odd). It follows that for all I, there exists some 20 To such that zol 1/Vd. Then, by resolvent identities that for all S i < d and Rd,
R[; K) K)Ta
R(20; K) K)Ta+ (a
20
R
K)R
20: K) K)JTal a
R(zo: K) T
a
+ Vd
R[:: K)
R(20: K)all
< (1 + MR)
max isid
R
K)T
(53)
In particular,
max max zET 15isd
RR;;K)Ja S (1 + Mn) max max mello 1sisd
R(20; K). al
(54)
Plugging this into (52),
$ |2| (1 MR) max max
K, mb)
S 2n Jr
R(zu K)T vnl de
zoEloo Isidd max max
=4(1 + MR)
K
R K) 1/
zeloo Isisa
Ck max max zEL's ISiSd
R)
(55)
Note that terms such as and K are bounded by assumption, thus we make the convention moving forward any constants independent to d such CR may change from line to line. Therefore, to show that (K,, vx) shrinks d - co, it suffices show that maX,eT, sidd R(2; K)F vxl shrinks as d oc.
Before we do so, it will be convenient to work under the setting that the risk is bounded. As such, let L > 0 and define the following stopping time,
min {k; || > L}.
(56)
as well as the stopped process Vù = V/ATT We show in Lemma that L may be chosen so that Vy = 1y with overwhelming probability, effectively removing the bounded constraint.
15

---

Exact risk curves of signSGD in high-dimensions
Lemma 3. Given Assumptions 1 -5, there exists net To T order O(d), such that for all i 0 and 1/6+6, < 1/4,
d
max max max seTo 1sisdogks(ed)
[[(2; K) Vol <
(57)
Vd
with high-probability.
Proof. For clarity of notation, let hig 2 h (0) and h4 -
V2Rg (Rx). In addition, define A₃ be diagonal matrix
+1 By (35), for a fixed & E To and I i S d, with entries given by hig as well as the vector E = (Blo(x)++) R 1-
E R(z -v))1-
R(z; K) Vi+11 vk(FF]
" R(2; K); (A, Ex+1)
TTuR(: (T,,R(;K)TKVV KvT
/ "[; K)} (ArKva - Kv + Ex+1)
The (2R(2; V
(2; ;; K) (AnKva - Kv + Ex+1)
d ThuaR(e R(z; K:KK)vx
+ d
[Thuvi + R)= (TaKva- - AgKvE Ex+1
(58)
=2](2)
By the Doob decomposition we see that,
R( K)T ve+1 R(;; K), Vk + E [[2 K) (v++1- vA] + (M))1()
17 1u R -1-
K) Va {z) + (1)))
(59)
where AM,+1 (=) are the martingale increments of R(z: K)T (Va+1 - vz). Let
1 - -
1=0
then upon iterating (59) we obtain
& R(; F Ve+1 = L L<; vo + La
Σ (8)(z) + AM)+
(60)
3=0 Lj
It is easy to check that = I, AM; 4M)+1(2) (2) is martingale we shall denote it by M M (2). Let
d
for some 1 d and E ETD )
min
k; R(2,
(61)
Vd
It suffices to show (57) holds for the stopped process VEAR given that
d
IP max max R(2:
K)J
>
IskS[td] #EL, ISiSd
Vd
d6
=P max max | 2;
Vied
(62)
=EE 1Sidd
Vdl
16

---

Exact risk curves of signSGD in high-dimensions
For notational clarity, will write Ve VKAT Note that (60) holds all k. so it must also hold for the stopped process Va- Given that the entries of Ve move increments of 2. observe the following bound the stopped process,
d
nMRR
R(;:K);
Vd Vd
RM
(63)
Vd
Moreover, by Lemma 12 we know that h2 v Mc. This in turn implies L.K is bounded from above and below. Indeed,
77 h4
L
MM4 |z|
+
5-0
[td]
1+ 2n
K
S exp (1C
(64)
Similarly for the lower bound,
k
|L > II
Th
|=|
d
j=0
[ed]
Mr
K
21/ K
1tdd
exp
M
K
Mn
K
exp
[td]
d
exp
(-nCt,c.k)
(65)
provided that MM K
2. Therefore, up to a constant factor
R(x: Vo = M M2+1(2) + + + -1
R(: K) V S C C...e.K
(66)
3=0
We will now bound the error (x). By (51), we already know that
K, Vy) S OR max max
R(2; K), TV
(67)
zer's Isisd
Similarly,
V < C
max max
R(2; K) TV V
(68)
sEL's 18idd
17

---

Exact risk curves of signSGD in high-dimensions
We also observe for all i d.
E J+ = E
(x R1+1]
33
K V s+1
50 E
Ki
0 (K,
(K V3) 19)
=0
R(z; K), k), )
max max sELo 1sisd
(69)
In particular, for some constant CK >
Ejtl
Σ
11)+1) 2
max max R(z: k) )²
I
VdCk
(70)
aETo Isidd
For our last error term we apply the Lipschitz bound obtained by Lemma 12. That is the map
2
-1²²
- (b()) TT 8V3
exp
dpe(y);
(71)
2s
Lipschitz with constant Le Moreover, (2R, - (K (,,,,)²² ",}²)= = hi and (2R,) = hg. By (67), for all isis d.
hッ < L. (K, ),
S L. (Ok max max zelos Isidd
R(;; R(;;K), vV,))
(72)
follows that
Ty - A,KV, S Tiyla As |KvV||
Tic Oxx max max
K)] v,
|V
C, Vd
max max =Eoo Isidd
R
K
(73)
For notational clarity, let us write wi = max maxigisd factor,
R (2; K) T |
Putting all this together we have up to constant
[g(()) S ( [ + ||[[x (liTgLa- - A.
||++,++|[(+++1)))
|IE,+1l))
< d
(w, + (w)+
2Vdws)
(74)
Returning to (66), upon taking the max across z E Lo and Sis d and up to constant C C,,cckk O, we obtain for all
< td]
k-1
2vdw?))
Wk S G C...c.k
WD + max max max Mz
+
Σ wj
(75)
ZET, [st
1=
18

---

Exact risk curves of signSGD in high-dimensions
Define
Mc(z));
Be Cj,cccK Wo max max max zeto ISpSAisk((e)
(76)
as well as the stopping time As before, we note that w/ can only move at increments of at-most
min wi:w 2 35t exp (CnEER)
(77)
q.M.
Thus,
va
nM, vd
WhAT 33. expeexppC,rp (,tt,,)))
= By
(78)
for all & E N. Plugging this into (75),
(1ed)-1)Ar) Σ
[td] !
Σn (2Vd2z)
W AadjArz S 3c + 18,+C C.t.KKK
d
wy +
(11A)
S Be + C C.
(2vd(1)8²)
Σ
C
(79)
I=0
By Gronwall's incquality,
Wldd/Ars S (3. + ( exp (Cntack)
(80)
If we can show that Br can be made sufficiently small that
C C,,t,c.K [V((8)3] s 3r
(81)
then @ LidjAn Ars = [ed]- To see this, recall by Assumption 5 we know that for any constant & > 0, the former term of 3r has the following tail bound,
EdM
IP max max R K)
Vol
S Cdl expeepp(ee (-
(82)
ZEDD 15idd
Vd
To bound the martingale term, we first fix
To and
sis d, then let
min { kk: M,
Ed Vd
T3 min
(83)
Let X₁ = MMnrs (2). Notice that E
(x) = 0. so E [x]] = 0. It follows that
5d
Ed5
F
max 1sk [t]
|Ma(E)) 2
Vo
= P (1xees) 2
Vd
(84)
Notice that
(=) - (+))
1
R(2; (v++1 vk) vn) R(2; KKFK [v+++ vn [Fx]]
[&d
C CR
(85)
Vd
CiRnAn Vd almost surely for all k. However, we may improve this increment bound by d' ă for
Hence, |X - Xx-1l <
5p < 8 < Indeed, by Corollary 2 for all even moments 2p < d, there exists a constant C(2p, 17. K) such that
P (1X Xx12 () C(pp, n,, K)d((t (2-20260))
(86)
19

---

Exact risk curves of signSGD in high-dimensions
follows by Lemma 15,
5d Vdl
(2
+ [td]]C(2p K)d(1 -2222266 -20266
P
exp
(87)
C...K
Thus, taking union bounds across & E To and S d gives.
Mx(z) 2 Edd
(52
P max max max seTo Isisd 1g
Cd exp
Vdl
n,t.K
2Cd C2p, K kdd(( 224260)
(88)
easy to see that for d sufficiently large, we may choose p large so that $ > + 80 + 2p² implying the latter term converges to 0 as d co. Therefore, Br sd Vi
with high-probability. Returning to (81), up constant factor that is
independent
P (Vdos 31) P
8
1
vd
d26
1
1
22
8
+
P
33 z
d
Vd
Vd
d
d
3
(89)
provided that 8 < 1/4. Thus, (81) satisfied and Ared/Are = Wld with high-probability.. By choosing & appropriately in de
accordance to (77), we conclude Wlrd]
S
with high-probability.
va
We can now formalize our prior statement of
(R()
E
V
v
Fi
(K,
(90)
/2R
for all 1 < iis d.
Lemma 4. Conditional on Fk, the mean of (34) is
(T((RK)) /
E
Vk+1 - Vk Fi
KVv + Ex+1,
(91)
where Ex-1 is an error term such that for all E (1/6 + 50. 1/4), with high-probubility [Ei+al = O 1 isisd d.
for all
2373
Proof. By (35), the coordinate- error can be defined
(((x)) V2Rx
(Ki vo) V 22h (Ki (Ki vi)
E
E (x(x
(92)
d
Applying Lemma onto (69) and (72) yields the result.
A.2. Convergence of SIGNSGD to SIGNHSGD
In this section we will show convergence of the dynamics of SIGNSGD to that of SIGNHSGD. Recall SIGNHSGD is defined as in (8). Similarly to SIGNSGD we will impose stopping time onto SIGNHSGD,
T = min (t: ||0 0. L}.
(93)
t>0
We will also define the stopped process by V, OuT - O.. We will prove the main result for the stopped SIGNSGD process Vy and stopped SIGNHSGD process V., then in Lemma we will generalize to the non-stopped process 0 and e,
We shall use the following:
20

---

Exact risk curves of signSGD in high-dimensions
Definition 5 (Quadratic). function q Rd R is quadratic if may be written in the form
((x) = A
for some A Rdddd b E R2, and R.
Once again, for notational convenience we will denote 0h+1 σ (( ext1) when it is clear. Now if q Rd -> IR is quadratic, it is easy to see that
1p2 ((+++)) - ((va)) - V (ox(1))
(ak- (
(94)
20
Thus, taking its conditional expectation we obtain
(p((R)) Vg((E) Kvv + (V'g(v)), Ko) +0 dv2Rk
2n1²
d
B[g(v++1) - ((vx)[Fu)
(95)
By the Doob-decomposition, we have
((+++1) - g(vx) = (R()
2T²²
VV((k)
d2x "Kv; + (V'g(va),
(96)
dv dv/2Rx
d3p
+0
AM
iin k+1
AM
k+1
(97)
d2
where
AM
! Vo(va) - - B[ox+1 Fxl),
(98)
d
and
AMoudd o/2
2d (++ V'u(ve)Ou+H - B[O V Ve((vx)0x+111F)
(99)
k+1
Similarly, by Ito's lemma on Vo, we see that
(V(R(V)) Vo(V.)TKVV KV, + 2T2² (V'((K)) Ko) dt dMy,
dg(V.)
(100)
(2)(
rd
where
/2K dn
aMp = VoVV,
dB.
(101)
Comparing (97) and (100), we see that predictable part of signSGD and the total variation part of HSGD depend only on (x(x) Kx and R(x). We capture these statistics in a "closed" manifold defined by
Qg = [xxxx, x, ((x), (x 2 R( K)x, x (2: "V'(")VV((((R 2, E).
(102)
To be precise in our notion of closure, given any E Qq. the predictable part of (97) (not accounting the error) and the drift part of (100) may be expressed via contour integral around I by a linear combination of functions from Q,- Let us look at an example. Suppose g(x) = Vg(x) RR(:: K)x. It easy to see that
(R()
E
FR)
(2 + (V'Kkr))
dv/2R
d3p
0
(103)
de
(Rk)
d3
T (VVx + +0
d22R
d
(T(((Rx)
V K + R..
(104)
dd/2R.
p(va)
21

---

Exact risk curves of signSGD in high-dimensions
Notice that our error O operator norm for all & E r. thus the Il is also uniformly bounded for all E Qy. It then follows that
is independent to choice of g. This is because the resolvent R[2; K) has uniformly bounded
d=
Vg(va) V E VV(v=))l Ex+ill Il
119l|c= (1 + [[vlll) | 0
(105)
d2
In addition, by the Cauchy's integral theorem may express p(v&) by
1 f 2v R (2: R.. K dy.
p(vx)
(106)
2
as well
1 $ 472 Jr. f
V
K) dzdy.
(107)
Consequently, we see that
E Vo(vv) (v)+1-va)[FA]]
(P((R()
12
K
2
max [o(v 0 DEQ,
d8p
(108)
dv/R
d2
12
d0
K
max gEQ₂
((v)) + d2
(109)
where we applied Lemma 12 in the second inequality. Note the constant factor of 12 around this quadratic dependent constant to obtain a uniform bound on (109) for all g E Q, with the following lemma:
K
2 dependee on g. We may work
Lemma 5. Let Qn be defined as above then for all > 0 there exists Qg Qu such that (Qgl S C(K)d and for all
E Qq. there exists go E Qg satisfying ||g - -0lllll> S d
The proof of Lemma 5 may be found in Collins-Woodfin al. (2024).
Lemma 6. There exists constants C(K), M, O such that for all g E Qq N and p E (1/6+ + do. 1/4),
M.M.
d30
[Vg(v)) (Ve+1 v*)] < d
C(K)
max gEQ,
(g((v)) + 0
(110)
d²
Proof. Let g E Q2 and n > 0, then by Lemma 5 there exists go E Q2 such that ||g
gollca S 2n It follows that
(Rx) Vg(vR) T +0
d
E (Vl(v)) - vb)]Fa]]
KVv
(111)
d/2R%
dc
(Rxx
(vV - (vx)) 'Kvb + (o 'Kvx
(112)
d 1/2
d3p
0
(113)
d
nM
[1g
| ||]] + (K)
max [o(v))]
(114)
d
gEQ.
d3p
+
0
(115)
dz
nM
Ap
(d-
K
+ Cg
(K))
max (g(vx) + +
(116)
d
gEQ,
d2
where Cgo K) is the choice dependent constant as in (109). By taking the max across our finite net QTy. there exists C(K) such that for all g Qa-
7
A
( ( <
C(K) max [g((v)) +
(117)
gEQ,
22

---

Exact risk curves of signSGD in high-dimensions
We are ready to prove our main result. It would be convenient extend the indexing of va from N to R by defining the sequence l = k//d. With some slight abuse of notation, let Vt, Vv. If 4 S t < 1k. then define V, ViN-1"
Lemma 7. Given 0 <, 2p <, d and a quadratic such that ||alcc* I 1, define Q = Qq U QR. where R. is the risk. For all T > 3 and 1/3 < 5 < 1/2, there exists C(K, c) > O such that
T Vd
sup (v(v.) q(V.)l USIST
exp (C(K, (Inlls T)
(118)
with probability at least c(2p, K K)dp(1/3-6)
Proof. Let g E Q, by (97), we see that
[td]
((((v.))
g(v,) g(vo)=
7
Σ
Vol,v)"KV, 'Kv
(119)
d i=0
(2R(v))
[td]
dap
+ 11
+
V2 g(v(),, Ko) + M, + MMquad
d2
d
1=0
=9(v 11 ((((vv))
(g(vv)_Kv. ds
(120)
(2((v.)
dpp
207²
Ko) ds I'
_udjo
d2
dx
+ +M + .Mquadd
(121)
Taking the difference with SIGNHSGD, we see that
le(v.)- 9(v)) sn /,¹² ((((v.)) (2R(vs)
Vg(v.) (R((V.))
Vg(V.)
KVV
ds
(2R(V.)
30
+ sup 0545t
(IM [Mguadi + (MM +0 t.
(122)
However, Lemma 12 tells us the map
(a, p((a) 22a
(123)
on bounded domain is Lipschitz continuous with constant I. 0. Thus, using the same argument as in (110) may bound the integrand by
((R(v.)) 22R(v.)
Vg(v.) Kvv (V((V (2R(V.)
V VV(V.)
< L. V (Vg(vs) KV, KVV, )²² (R(v.))R(VV.))
< (.C max (v(v)) - v(V.)..
(124)
gEQ
Plugging into (122) we get
max (g(v.) v(V.)) ( (830
(1))
sup lo(v.)) - g(Vi)l < sup (MM!i + [Mquad] + +lM)) + 0 sEQ
05e50
d
//'
+ (L.C(K)
(125)
DEQ
By Gronwall's inequality,
(IM!.im) + MMquad + +lM))) + (=)))
1) exp (nL.C(K)t).
sup sEQ 05+5t
sup lg(ve)- - v(vo)l
(126)
23

---

Exact risk curves of signSGD in high-dimensions
Lemmas 9, 10 and 11 bounds the martingales by va for 1/3 < 8 < 1/2. Subsequently, the proof.
bounds 0
concluding
va
We have now shown that the stopped processes satisfy the conclusion of Theorem We will conclude the proof of Theorem 1 by showing that, with high-probability, the process is not stopped.
Lemma 8. For all T O, there exists C(K, K.) such that
max DSAST
| S exp (T)(K,Ko)),
(127)
with overwhelming probability.
Proof. For a E Rdd let (2)) = log(1 + ||z]|]). By Itó's lemma,
(R)((Re)
T/2 dr(1 + [[v.113)
(v.(
V.
V.K. V
dt
22, + +IV.)
2n²
2n (1+IVV
K,
dI[e+||Vell' Tr.)))
dt
VT
dB..
(128)
di
is easy to check by the Sauchy-Schward inequality that the deterministic terms of may be uniformly bounded by some constant C(K, K,) > Denote the martingale term by M - HSSDD then the quadratic variation given by,
4n2
/ V. V, ds
(yP-HSGD)
(129)
dr(11 + | 33
17² Kollt
(130)
dm
By subgaussian concentration,
IP
max 1/ (V,)) 2TC(K, Ko) OS1ST
SP
max M³ M HSGD OStST
TC(K, Ko)
(CC(K Ko \TdT
< 2exp
(131)
20² |K,
That is
max 0StS
|V I exp (TC(K,K.))
(132)
with overwhelming probability.
Therefore by choosing the upper bound in our stopping To and T/ in accordance to Lemma 8, we obtain v. = O2 - 0, and
V, = O e, for all 0 t with overwhelming probability. Combining this with Lemma 7 proves Theorem as well as the following generalization:
Theorem 5. Given Assumptions 1-5 and quadratic Rdd + R. if g(x) q(x 0.) then choosing any fixed even moment 2p E (0, d), there exists constant C(K, <) 0 such that for any E 11/3,1/2) and all T > 3,
Tat llalic
0StST sup [g(0 g(O))
exp (C(K, c) |lmlloc T).
(133)
Vd
with probability at least
c(2p, K K)dp(1/3-0) for a constant c(2p, K) independent to d.
24

---

Exact risk curves of signSGD in high-dimensions
A.3. Main theorem with badly behaved noise
In this section we formulate version of Theorem 5 without Assumption The key is that we must work on subsets the state space where the risk remains away from 0. So suppose that we let
= min {t; | 0.1 < e), 1>0
for fixed positive > 0.
We note that the map x + s0(x) is Lipschitz on [e, xi), even without Assumption 2, since
('(()) f
1 y² exp
(- 1²²
s(dyy)
J 2s
The function re uniformly bounded on x 2 0 by and hence (s((s) S 1/e on the interval [e, 00).
Thus, we can now proceed with the same proof as Theorem 5, although we do not remove the stopping time d. The end result the following:
Theorem 6. Given Assumptions 1, 3, 4, and quadratic q IRd + R. if gx)) q(x 0.) then choosing any fixed even
moment 2p E (0, d) and choosing any > there exists a constant C(K, c, 0) > such that for any E (1/3, 1/2) and all T > 3.
Td IIalic Vd
sup
1g(0 [dj) [g(0(d))
g(O.)l
exp (C(K, e, Inll T),
(134)
USiSTAB
with probability at least c(2p, K K)p((1/360) for constant c(2p, K) independent to d.
We remark that if the risk of SIGNHSGD remains bounded away from 0, which will be the case for constant stepsize and nonzero noise, one could additionally show that & does not occur with high probability. In that case, one can derive as a corollary of Theorem a statement without
A.4. Bounding martingale terms
Lemma 9, For all g E Qg as defined in Equation (102) and 1/3 < < 1/2,
! d
sup osks|Tdl
(135)
vd
with high-probabiliyy
Proof. Recall that under To. < L. Moreover, given that ||alcc & 1 and []] s Mg. we see that |[gl|ce is uniformly bounded for all E Q. Therefore,
VVg(vk = 11gllc> L)
(136)
for all k. Now by Corollary 3, for every even moment 2p < d, there exists C(2p, K) > 0 such that
1/2
d6 5 ))
C(2p. KJE
[V
dPD/3
PP
|
d26p
C(2p, K) (1 2> df
(137)
25

---

Exact risk curves of signSGD in high-dimensions
Lemma 10. For all g Q and 0 1/2.
1
M < oskg[TT]]
sup
(138)
d=
with overwhelming probability.
Proof. From Cauchy-Schwarc we see that
AMguad
S
1/2 d 11lllc>
(139)
Then, Azuma's inequality shows that
1
-d-20t1
P
max Igkk
[M
2 d'
2xx
(140)
which gives the result.
Lemma 11. For all g E Q and s < 1,
sup
MNl
(141)
0SEST
do
with overwhelming probability.
Proof. From Equation (101), we know that
M. M,=n/ =n va(V.)) V
2K
dB.
(142)
dm
Using the ||gl|c> norm can bound
V (V.ll I (1 + [[V+]))
(143)
Then, with Assumption 3 and Equation (143) we can bound the quadratic variation as,
24²
l V K, Vo(V)) ds
(M").
dm
2//
1'" ||o|| VV((V ds
s dm
2n²
dm | 11911 (1 M)
(144)
Then, using the subgaussian tail bound for continuous martingales that the stopped martingale satisfies,
+2d dm
0
sup
M
2t
<
2xxp
41 K
[19| & (1 M M
(145)
26

---

Exact risk curves of signSGD in high-dimensions
Lemma 12. If y is probability measure R with the property that there exists ag such that de g(x) on (-ag, dol
for g aol), then the map R - R defined by
f exp
-v²
du(y).
(146)
2s
bounded well Lipschitz.
Proof. Notice that it suffices show (146) is bounded and Lipschitz for 0 s < 1. Let fa(v)
~ exp
(#x))
well
2s
G(y) pu((-00,,) vl). Decomposing the integral into
J (all) du(vy)
f.(v)d((v) + 1 aRil-a
fa(v) du(y),
(147)
[aa00oo]
that the latter term may be easily bounded by
1
-ag
(a(v) du(y)
exp
(148)
2s
which decays to as - The former term we apply the integration by parts formula to get
y
y²²
|aagaaol
3/22
exp
2s
G(y) dy.
(149)
Further decomposing the latter integral into positive and negative regions get
3/2
y
exp
yy²
2s
G(y) dy
53/2
exp
-y²
2s
(G(-an) + p(((aa,,)))) ul)] dy,
(150)
and
-y²
-1²
3/2 exp
G(y) dy =
3//2 exp
[G( (G(-ao) + ul( va((-ao vl) dy
(151)
28
-ag
28
y2²
83/2
1/
exp
2s
[G(-av) + u((-ag. -y)] dy.
(152)
Thus,
1
-y²
y
V22
33/2
exp
2s
G(y) dy
=
3/2 exp
2s
u((-v. y. vl) dy
(153)
-2²
Jo
3/2 cxp
2s
dy
(154)
aa/
V8
-y²
C
Jn
y²
exp
dy.
(155)
2
Putting this all together, we conclude that (pss is uniformly bounded for all argument. We first differentiate fz() with respect to we get
0. To Lipschitz, apply similar
d ds foly) 2/ exp
y2
(y² s)-
(156)
2s
Therefore,
d
fz) du(y) + /
d
a' a'(s) = [-000a] ds
-
ds fv) du(y).
(157)
R\:-00.00)
27

---

Exact risk curves of signSGD in high-dimensions
There exists 80 such that if 80, then v3s og- It is easy check that if Likewise, if y < - v3s then ds (v) is increasing in y. It follows that
v then de (v) is decreasing in y-
-ag
aallap ds (v) du(() 5 exp
(ag 8),
(158)
2s
which decays to as + Finally, we apply integration by parts once more to get
d
fo(() (o
(159)
no) ds
ds
0
-v²
2s7/2 exp
(y² 3sy))(((B,, dy.
(160)
Since g E (2((-au, anl) we may express (=((1/,,))))) y|) as
p((- y. v)) = | ((0) + g +000)==(0z=))) dr 2g(0)) O(y").
(161)
Plugging this into (160) it is easy to check that
g(0)a x exp
1/80
g(0) s7/2
-1²²
exp
(y²
3sy)ydy
(162)
2s
g5/2
and
1/000 (00
-y²
-y²
257/2
exp
2s
(y² 3sy)
SC
257/2 exp
2s
(y²² 3sy)r" dy
(163)
/
y²
exp
(y² + 3y)y dy.
(164)
Combining this with (158), we conclude that [a'(s)] is uniformly bounded for all
Lemma 13. Let x ~ No, K) such that K is positive-defintte. Ifa E Rd, then for all even moments 2h: S d,
(()) - C(2k, || a///// 2a//s
(165)
where C(2k, K) > 0 depends only on 2k, Amin (K) and Amax
Proof. We start by fixing 8 > 0 and defining the smooth approximation of o(x) be os(x) Ps (x),, where Ps I R is the standard compactly-supported mollifier convolved entry-wise oxx), i.e. (ax(x)); Ps (x.)). It follows that
|| (a, (x)) I| < (a, (x) - (x)))) 11 + (x())) 11z2..
(166)
Note that Ps has support contained in [-6, 6). thus the entry-wise difference of (x) ox(x) may be bounded by
0
Xx > 28
(x(x;) - as(xa)) <
2
x; S 28.
Define No(x) Ed= 1 x//2263 to be the number of coordinates of x within the interval (-26, 26), we see that
E (x) 2x
< ||a|| 24 22k E [Ns
(167)
||a|| 22 22h
Σ P (xx))se E 1 26 )
(168)
SET
28

---

Exact risk curves of signSGD in high-dimensions
where I (1,..., ......,dJaa and 8 is set of distinct elements of Let K (s') E [(x, ) leer then (x,) N(0, K( Recall that there exists a permutation matrix P, such (s)) forms the top |s'| x Is' sub-matrix of PKP-1. Given that PKP- and K are similar, they share the same eigenvalues. Therefore, by the Cauchy interlacing-law.
Amin (K) S Amin (K(
(169)
In particular this implies
|s'|
det K K(,))
II (i(())))
Amin (K))
(170)
Plugging this back into (168) and choosing 8 = d= we get
(40)
E -xs(0())=((x))))
ox(x))
I ||a||20 22
(171)
(2T Ammn (K)) 8'1/2
.EI
24
2k
(48)
2k =|aa|1
11
(172)
(2 Xmmin (K))U2
1=1
2k
edd
(46)
||a||ad
2k 22
max 15152k
11
(173)
1
(2 (K)
i=1
2k
4ed -r
S ||a|| 2k 22 ((2A)
(174)
2T min Aminn (K),
=|aa| 2k C(2k, ()d(1-r)2a
(175)
where [ is Stirling's 's number of a second-kind. For clarity of notation moving forward, we note that C(2k; K) may change up to factors of constants or powers of from line to line, while always being independent to d.
To control the second term of Equation (166), we modify the proof of concentration of Lipschitz functions of Gaussian random variables. See Lemma 2.5.5 for more details (Adler Taylor, 2007). Let G(x) = (a, as (x)). and z ~ N(, K) be independent Define the Gaussian interpolation n be
()) ax + V azz,
and note that x law (0) for all [0, 1). Then by Lemma 2.1.4 in (Adler & Taylor, 2007),
B[ = (2k 1) // E (K(a0 o( 2x)= da.
(176)
where @ represents the Hadamard product. Going forward, we will use Hölder's inequality to break up the expectation and form a recursive equation. As such, consider
[[
(177)
for some Standard linear algebra gives us
2p B (x00
1 [|] [ S [|] ||a|| 2PE (x)()(1
(178)
with the last line following from Cauchy-Schwartz and equality in law of and (a)) Given that dx(x)) 0 for x; E [-25, 26]. as well as (x:) I 4e for x; E [-25, 28) and T.p universal constant depending on our mollifier,
29

---

Exact risk curves of signSGD in high-dimensions
L 3p E| [x)]|( -
mm
(179)
8t
As we have seen in Equation (175),
T [[No(x))P) S C(p. K)d(t-122p
(180)
Therefore, up to absolute constants
I.Ap < C(p, ((aal)) 22 (1-)22
84p
(181)
I C(p. )
Returning to (176) and choosing 2p- =2 1, we see by Hölder's inequality
[ < (2k 1) G(xx 2k- 2 II[(K(a o' of
(182)
< (2k (x C(k,K) lall d'tr.
(183)
Iterating the same inequalities as above for B[G2k-1] we obtain
2k-1
(2k - i)C K, k,) Ilal d(tr) #
3 2h
- II
(184)
i=1
S C2k, K)
||a 2h (1+r))
(185)
Equations (175) and (184)combined give control over Equation (166),
(a, (x)) 11... I C(2k,, K) (d't" + d'-r).
(186)
Optimizing over r yields r = 1/3 leading to
E [() 1|a < C(2k, K) |alla 24/33 24R/33
(187)
as desired.
Lemma 14. Let N(O, K) such K positive-definite. I IRd random vector independent x, then for all moments 2k < d.
1/2 2k//3
(y, (x)); S C(2k: K)E ||x||
(188)
where C(2k, K) > 0 depends only on 2k: Amin (K) and (m).
Proof. The proof is almost identical to that Lemma 13, but instead taking the sup-norm of a in (168), we take the la norm via the Cauchy Schwarz inequality. Now proceeding proceeding in similar fashion we get
[() -xx(x))
24
E
|
||
24
|[o(x)
(x(x))
(189)
1/2
E [|](()) os(x))11k) 1/2
E
||y
||
(190)
E8
||y
4k
1/2
22h (E [NN(()))))) 1/2
(191)
1/2
E
||y
4k
()d
(192)
30

---

Exact risk curves of signSGD in high-dimensions
Lastly, by the independence of and x, upon conditioning on y by Gaussian-connenntaation on (y, (x(()) that
E
(x)))
E
E (x))
24
(193)
Cv llyl
Amax KK)
s E
(194)
C(kk, K)
||y| 1|
(195)
where > 0 is absolute constant. Combining (192) and (195) then optimizing in yields the result.
Corollary 1. Ler Rd and X (0, then for all even moments 2p S d, there exists C(2p, K) 0 such that
C(2p. K)
| 0o
dtp/3
P (a, (4x+1 - E (
t) <
(196)
P2p
Proof. For notational clarity, let us denote Y (a, 0l2++ (0x4+11X4+111 )). By Jensen's 's inequality and convexity of x + 22
[ y22p F
E Y E(|]])))
- 2
(197)
2 [
(198)
However, notice that E [y2]] = E (a, (a, (x By Markov's inequality and Lemma 13,
P(Y -Y
2 = (YY Y E|Y Fx 2p 22)
(199)
2 (a, o (xx+1)))
(200)
(2p
C2p,, K) ||al d
(201)
tpp
Corollary 2. If a E TRd such that max2gigd |a$| = 0 -5²)) then for all even moments 2p d and s > there exists C(2p,K) K) > 0 such that,
P P( E(o((e+1X++)) 2 d²) C(2p. ()
(202)
provided that d' 4.
Proof. For of notation, let 0241 Corollary 1,
o (44+11 Given that |at (ax+11 E [ox+ [Fxl) S 2/a4|, it follows by
PP (a, Tktl - E(ox41 d3) d SF ( a' ookt E ootz Fi 1
d"
(203)
C(2p, K) (maxesisd (a²)) d4p/3
(204)
ppps
C(p, (2222))))
(205)
Corollary 3. xf ~ K) and y E Rd a random vector independent to x, then for all even moments 2p S d there existy C(2p, K) > 0 and independent to d such that
C(2p, K)E
lly 4p
1/2
dpp/
( (y, (f++188411 -
(206)
f2p
31

---

Exact risk curves of signSGD in high-dimensions
The proof is identical to that of Corollary 1 but using Lemma 14 instead.
Lemma 15. Let Mg a martingale such that [M N O,
MR-1 1 S C almost-surely and les Ss. S C. Then for all > 0 and
f2
P(MN 2exp
- - Mk-1 > Sk).
(207)
C + k= S
Proof. Let mk; [M Ma-1l Sk} and Y MEAT, then on the event that (A <). V2 - Yk-1l - Sk- On
the other hand, if {T & k} then \ - Yk-1l S C. Breaking the probability space into the event {r S N 1} and its complement gives.
P(MN SP SN 1).
(208)
Azuma's inequality completes the proof as
82
P P( 2 1) < 2exp
(209)
N-1 ?2(0 +
5%
k=
32

---

Exact risk curves of signSGD in high-dimensions
B. Risk Curve Dynamies
B.1. Proof Theorem
. e - 0. where e solves the SDE given by (8) then Itō's lemma applied onto
1 T KR(2;K)æ,
g(z)
(210)
2
yields
(R,) V
KR(2; + R(z; K)*K
dg(V.)
KV, de
(211)
V2R (KR(2; (KR((:K),KK K), dt + d.p.
2
(212)
ad
where we denote R. R(V,) for ease of notation. By resolvent identities, we know that
KR(2; K)K - <2R(2;; 22; K) + K
(213)
Moreover,
R K) KK (KKR(;;K)) (=KR(( 2; K) K)",
(214)
R(2; K KV (R K
2 (zg( + RR)= = V7
(215)
2
Returning to Itô's we see that
(R1) (V. R2)
dv.
Tr (K<(2:K)K.) dt + dMg.
(216)
V2R,
To recover the risk R1, we once again turn towards the Cauchy integral law as well as the Spectral Theorem. Indeed,
k=
A u, & w.
R(2; K
69 W.: (K)
(217)
t=1
where u, and w, are left and right eigenvectors respectively of We may then write
d
(Vv))
V (Ku, & V.
(218)
2
K
Denoting Fi(t) VT (Ku, @ V,, then upon integrating r,, closed curve enclosing only A Ax(K), that
di; of dg (V.)
dz
(219)
Jr.
2 (Rx)
(K):
1² rd
Tr (K(u @ w.).k) di + a.a.
(220)
V2R,
where
M -2vi
Min
dz.
(221)
Jr.
Given that the martingale terms vanish d - oo, should expect the drift term of F; to dominate. Thus, let us define the deterministic equivalent of F; as
dr: (-2mp(2R)) >. (K),
n
Tr (K(u, & w.))K)) dt, r:(0) (.
(222)
VRa
nd
33

---

Exact risk curves of signSGD in high-dimensions
where
d
R4
Tt-
(223)
i=1
Note, we integrate (218) around r, we obtain
d
R2
(224)
We will show that R, concentrates around RG using the same idea as in Lemma 7. We start by considering set of functions that maps x E R to C by
W []=))x;==TT)
(225)
where [2) E Cd defined coordinate-wise by
[x()]] = {:( -
(226)
ret) = (r:)))) F(t) = (7(0) and g(x) = [(2)=x for some & E I, then as in (122) it is easy to check that
2mp R.)
d
(R,)
(o(r(t)) - g(F(t))
A (K) (J))),
Σ (K) [2)),, F. ds
(227)
Rg
VR,
==1
sup
Mal
(228)
05
where Mr are all the martingale terms grouped together. Utilizing the same Lipschtiz map found in the proof of Lemma 7, there exists Le > such that the integrand may be bounded by
2nd Rs)
(R,) VR,
d
A [ [J))
X (K)
(229)
RR,
$ Le
RA R -
(:(K) [[(=]], (ri- Fi)
(230)
The latter term may be further bounded by
s Σ (1 2TJ -Fi)
X K [2)], (r: -r))
(231)
$ RR R. + K -
- 9(((s))
(232)
However, notice that
2mi /
RR, Ral =
dy
(233)
K
sup (9(((s)) ((((s))
(234)
gEW
Therefore,
2mp((R.)
(R d
(235)
VR,
VR, 1=1
1=1
< LKC(K) sup (o(((s)) g(f(s))) gEW
(236)
Putting all this together we see that
sup (g(r(()) - g((())) < sup [Ma +
I.CC(K) sup (g((())) ds.
(237)
sEW
05+5t
gEW
34

---

Exact risk curves of signSGD in high-dimensions
By Gronwall's inequality,
sup (g(((())))))))))))))(())))))([ =(F(t))) seW
sup MMIexp (L))(()t).. 05o5e
(238)
By (234) and Lemma 9, we that R₂ and R& concentrates. Finally, Theorem concludes the proof.
B.1.1. RISK CURVES FOR SGD
Following a similar approach but taking
1 (<; 2 1-=2xxRRR
g(x)
(239)
we may derive system of d-ODEs for SGD. We note this is not novel, and a full derivation in much greater generality is in (Collins-Woodfin et al., 2023); see also (Collins-Woodfin et al., 2024) for a shorter discussion. Using the HSGD formulation of vanilla streaming SGD (Collins- -oolinn et al., 2024), we arrive at the VANILLAODE for subgaussian noise and variance v
2m),,, + de dt
T71)2
(R)
SCD +2212), AI sisis..
(240)
d
R R
Σ
Xx(K)ot
(241)
35

---

Exact risk curves of signSGD in high-dimensions
C. Convergence and phase-properties of the ODEs
Lemma 16. ! [(0, )²), then ()))) is bounded from above and below for all
Proof. Take g(x) = x Dx then plugging this into (100) we obtain
4n R(V,)
22 Wd Ir + Mg
VV. (V((VV) + 62
(242)
By concentration inequalities we know that M2 vanishes as d + 0o, thus we will omit the martingale term. Solving for the stationary point yields the following roots,
C2 CTyy C + 6462
R_
(243)
64
where C, 1/ Tr(K, 3d Tr(D). Phase diagram analysis shows that if R(V,) < R+, then (V,)) is increasing. Conversely, if R( > R+ then q(v.) is decreasing. Since D is positive-definite, q ((v)) provided that V, + 0. The growth and decay conditions of q(V,) implies that (V.,) cannot converge to nor diverge to co. Therefore, ((V,) is bounded from above and below. Consequently, ||V,]| || is bounded from above and below and so RVV.) is well.
Theorem 7. If e N(0, 0²) and 1) (0, 00) is a fixed learning rate then there exists unique stationary points
17 Tr(K(u, & W.) s;
Tr(DK,))
2 Tr.DK,)) ) + 1602
(244)
(K)d
and the limit risk is given by
n Tr(DK,) )
R 16d
Tr(DK,)
+ 1602
(245)
d
d2
We note that in these formulas, Tr(DK,) = = Tr(D) = Tr(K) on account of K, having a constant diagonal.
Proof. Let Y₁ =
402 47
and my
Ow, nd
then our d coupled ODEs are given by
dr:
A K r
+n
r:(0) 2 V
(Ku, @ Vo)
(246)
dt
Y,
Solving for the stationary point, we see that for sisd. d.
Yi 1im Yt (
(247)
Thus, at equilibrium
R₂
Σ
d
ri x7 Y₁
m4
Y
TrDDK.).
(248)
X (
nd
1=1
1=1
However, RS can expressed in terms of Y by
2
R₂
0²
(249)
2
π
Plugging into (248) see that
1
4n/Ya
r²Yr
62
Tr(DK.).
(250)
2
nd
36

---

Exact risk curves of signSGD in high-dimensions
Solving for Y yields the following positive
Ir(DK,,)
2 Tr (DK,)
Yec
1602
(251)
16n
d²
Therefore, by (247) and (249), dr. dr
= 0 if and only if
mo,
AI sisd.
(252)
(K)
This concludes uniqueness. The limiting risk is then given by
Y²²
Rix- = xd
TD(K,,).
(253)
Similarly, fixing 7, we may derive unique stationary points to VANILLAODE (240):
Theorem 8. If is subgaussian with variance v², E o0) is a fixed learning rate and {ui as given by (240), then
there exists unique stationary points
SGD
1/0
(254)
2(2d 17 K)
with limiting risk
1702 TK(
RSGD
(255)
2(2d Tr(K)n)
Theorem 9. Assume 02) and let 8; be the stationary points to (13a). Then there is absolute constant >> that if
0
TD(K,,))
min { (
4u and Ro S co.
17
Rd
then we have, setting Rxc- = Ei= 8t to be the limit risk.
RR
Rac s 2(R + Roo) tmp (K)/(xv)
We note again that in these formulas, TrDKK,) Tr(D) = K) on account of K. having a constant diagonal.
Proof. We recall (252), in terms of which we have
dr;
A K
A
ri +
81.
dt
Y
Y
and where recall
TV 2R, + 02
4n
Then we rewrite the evolution of r; as
d
(
(A:(K)
{x(K)
(r. s,)
(r, 81) +
de
You
You
Y,
and we set Roo as Σ 8/. Now we observe that
Y,2
Y2
(R, Roo) = (Rg - Roc),
(256)
Y2
8Y
37

---

Exact risk curves of signSGD in high-dimensions
from which it follows
1
Y ---Y- Y
Y? Y
+ Erro,
YOc
Yt
(Y, (Y2)
2Y3
where Err, is bounded by
Y,,
Y
I 0 a
ErT, &
C
(Ro -Rxo
(257)
Y
y
where y is the minimum value of Yt over all time and C' is an absolute constant. Hence we can further develop
Y? Y2
Y? Y2
(Ti - s;) =
BYr.)
-5) +
+ ExI:)
A {[(K)s, st,
dt
2Y
2Y
Define
1/-
2/11 1
Y?
Y2
e(s)
Err, dt.
1oc
2Y3
Then by variation of parameters, we have
(t) (r: s;)( -xi(()) (0)(0))>1o0))__1 f -2ice(t))-10)
(Y?-
+ +Er,, {(K)s,
2Y 00
Now if we over all i, we have
R₂ Roc F((t) + (( k(t,s)
YY? - Y2
+ EIr, ds.
2Y3
where
F(I) Σ (0) -ce(t)
where
K(1, Σ -2(((())-e(e)) (r))ss
Now suppose that on some interval of time [0. 7]
Y,2 Y2
Y? Y2
Err, 1
and
<
(258)
2Y
2Y33
2Y
Then for s <t<< T. we have
e(t) - e(s) 2
(t s),
2Y
and so we have the convolution Volterra upper bound for / S T
RR - R (F0) + Yo - \,K)s
|R, Roc ds.
Now note that we have the upper bound (for < 7)
[F(I) < (Ro + Roo ) (Amin/(2Y..)
Now suppose that 0 < T i's such that for S 7M
Rs Rool S Me Me-(amil (mmin/ (4Y
38

---

Exact risk curves of signSGD in high-dimensions
have for 1 ST,
Σ
e (
Me Me (Amii (AY ds
Σ
c (-AA/1(28)))
(hl//0Ya)Aautt((1X /2Y Amin/ (4Y
A K 8;
M
(K));
Σ (2 Amin/ (4Y
M
A (K)s
Σ (2Y (4Y
M
S \/40 RAY R.M
Hence T" = provided
4a and M (Ro Rxx)
1 4a
Now we return to showing T does not occur. Recall (258), which up to are satisfied. Then suffices to have (compare (257)),
2C' Yoo y aM s 1, where
aM S and
8
which case (258) satisfied for all time. Note that we may always bound y below by
y 2 (TO) (4n))
Define HK Tr(D.,) ad
We now recall (251) and (249), from which
[H + v H 1602/7²
Yxc = x²
and Rx = Yool HK.
16n
Hence for HH I 40/x, we have
I nV
<
Y
xc
< 43,
41j
1
and hence we have
2 and
5
Rx S npllle.
Thus we conclude there is an absolute constant > 0 so that if
40
nllk < min
c, TJ
and Ro S co,
then we have
RR Rool s 2(Ro + R tndaam (K) (xo))
39

---

Exact risk curves of signSGD in high-dimensions
D. Minibatching SDEs comparison
In this section, we will present the SDE comparison between SIGNHSGD and HSGD when b > 1 for convenience of future work. Modifying (15), it is easy check that HSGD with minibatching
2
_ -/t K(O 0.)dl mh
KdB.
(259)
db
Once again running SGD with adaptive learning rate
21j 2P((O)GD)
SGD
(260)
π
we obtain the similar SDEs for HSGD and SIGNHSGD as in (17a) and (17b)
4K
dOSGD
-ttt
SGD
0.)dt. + 1/
dB.
(261)
72d
2K, TO
d0, = - SGD (8) (R(O.)
D K(@, - d. + m
dB,
(262)
c. compress.
D.Precond.
Reshape
where
2x + 0²
(x)
2 (z)
(263)
2r
vb
This shows that our analysis in Section 4 also applies to the mini-bater setting. Notably, the effective learning rate scales by a factor vb, while the e-compression term (b())) gains some additional regularity near 0 when b > 1. See Section 5.
40

---

Exact risk curves of signSGD in high-dimensions
E. Additional experiments
begin by illustrating (Figure 6) the concentration effect: as d increases, the loss curves more closely match ODEs. We also note the spread of SIGNHSGD and SIGNSGD are close across dimension.
6x10 10
Risk
Risk
40-1
3x10-1
signHSGD 80.0% Cl
signHSGD 80.0% CI
signSGD 80.0% CI signODE
signSGD 80.0% CI
2x10-1
signODE
vanillaODE
vanillaODE
10-1
10
10
102
10a
104
10-1
10
101
102
10a
104
Iterations
Iterations
(a) d 50
(b) 100
109
109
6
6 10
Risk
Risk
4x10-1
4x10
3x10-1
signHSGD 80.0% Cl
3x10-1
signHSGD 80.0% CI
signSGD 80.0% CI
signSGD 80.0% CI
2x
signODE
2x10
signODE
vanillaODE
vanillaODE
10
10
10
102
103
10
10
10
10
102
10a
10
105
Iterations
Iterations
(c) d 250
(d) 750
Figure 6: A demonstration that SIGNSGD, SIGNHSGD, and their deterministic equivalent concentrate in nigh-dimensions over long time scales. In the limit as d - oo our main theorem shows that all these objects become the same.

---

Exact risk curves of signSGD in high-dimensinn
In the figure compare the limit risk prediction in Theorem 3.
2.00
1.8
signHSGD 80.0% CI
signHSGD 80.0% CI
1.75
signSGD 80.0% CI
1.6
signSGD 80.0% CI
signODE
signODE
Theorem
1.4
Vanilla ODE
Risk
1.25
Risk
1.2
Theorem 3
1.00
1.0
0.75
0.8
0.50
0.6
0.25
0.4
10
15
20
5
10
15
20
lterations/d
Iterations/d
(a) = 0.3
(b) 0.7
2.0
signHSGD 80.0% CI
signHSGD 80.0% CI
1.9
signSGD 80.0% CI
signSGD 80.0% CI
1.8
signODE Theorem 3
1.8
signODE Theorem 3
1.6
1.7
Risk
Risk
1.4
1.6
1.2
1.5
1.0
1.4
1.3
0.8
0
10
15
20
5
10
15
20
Iterations/d
Iterations/d
(c) 1.1
(d) 1.5
Figure 7: A demonstration of Theorem 3, over varying learning rates. Here d 500, and we take Gaussian noise with
= 0.7
42

---

Exact risk curves of signSGD in high-dimensions
To demonstrate the convergence rates, consider of diagonal covariance matrices. The eigenvalues the diagonal given by uniform grid of [0.5, 1.0]. To these eigenvalues, then raise them power the range (1.0, ..... 5.0). This causes the smallest eigenvalue to approach 0, We then compare SIGNSGD SGD after Tdd steps with T = 30. The noise is set to = 0.01.
The learning rates are taken 'optimal" which is to say that they are rjd/ tr tr(K) and rdd/ (K) for SGD and SIGNSGD respectively for a fixed multiple y. The constant is given by = 0.01. The resulting risk curves look like:
0.30
vanilla SGD 80.0% CI
Vanilla ODE
10
0.25
signSGD 80.0% CI
signODE
0.20
Limit Risk
Risk
Risk
10
0.15
0.10
vanilla SGD 80.0% CI
Vanilla ODE
0.05
10
signSGD 80 10.0%
signODE
0.00
0
10
15
20
25
30
0
10
15
20
25
30
Iterations/d
Iterations/d
(a) Risk curves before removing limit risk
(b) Risk curves after removing limit risk
Figure 8: These are the risk curves from the setup described in the text (with a 5.0). After recentering using the values from Theorem and (255), (b) shows the linear convergence.
Now varying over these problems over a between 1.0 and 5.0. We have:
43

---

Exact risk curves of signSGD in high-dimensions
A=1.23
Last Iterate Risk
-2
10
A=1.56
A=2.01
10
vanillaODE
SGD CI
A=2.66
signODE
10 -4
signSGD CI
A 3=3.57
2 x 10 x 10 4 x 10
6 10
10
Averaged condition number of K
Figure 9: We plot the limiting suboptimality against the averaged condition number of the problem Tr(K)/(da) (dDamnn(K) (K)). SGD attains this convergence rate. The label A for each point is the ratio of the averaged condition number of K the averaged condition number of K. This measures the speedup of SIGNSGD over SGD, and is the rate effect captured by Theorem 4.
44

---

Exact risk curves of signSGD in high-dimensions
F. Heuristic for ADAM
this section we derive a heuristic for ADAM (Kingma, 2014). This is given, our context, by:
Given: 1 learning rate
81 E [0, 1) exponential decay rates for moment estimates
6a small constant for numerical stability
Initialize:
0o: initial parameter vector
mo <- O: 1st moment vector
Vo < 2nd moment vector
k + timestep
Repeat until convergence:
k k:
g: + VeL(O, k- 1,, 3k) (Get gradients w.r.t. stochastic objective at timestep k)
m + 81 m (1
31) (Update biased first moment estimate)
Vk -- 82 Vk-1 + (1 32) g (Update biased second raw moment estimate)
mg m3/(1 (8) (Compute bias-corrected first moment estimate)
VN + v -12)
(Compute bias-corrected second raw moment estimate)
0g < - 1a---p1 rmmu/// (vvx hinee/lVi//
60) (Update parameters)
In high-dimenn digeensiiii context, the first moment momentum 31 has been observed to be equivalent to an effective change of learning rate, without inducing other benefits on the dynamics (see (Paquette & Paquette, 2021)), and so we ignore it.
The role of the second moment, in contrast, should induce a preconditioner. If we assume that exponential decay rate of 32 chosen sufficiently close to 1, we would have
with the square applied entrywise. Using the definition of the stochastic gradient, have
V (xx)) ((x:: 0x-1 - 0.) + +ex)² (
This can be computed explicitly by Gaussian conditioning. Note that conditionally on the Gaussian (xk, θk-1 O.), X develops mean K(Oa-1 0.), which has norm O(1). Hence provided it also has small L norm, so too will all the variances of the entries of x be nearly unaffected. Hence we essentially have independence, in that
v E ((xx)²) E ((xx)) 0 -.) 0.) +c)+ (1) diag(()((2))
Hence, we arrive at the approximate update rule for ADAM
0 R++1 0:
Th
(264)
(2)(Op)
The corresponding homogenized ADAM equation is given by
d
K(O, 0.)+ D-1/2 KdB, Th
(265)
(
G. Weak-approximation and high-dimension
The idea of approximating discrete stochastic processes using differential equations is not new and can be traced back to (Robbins Monro, 1951). These approaches typically involved deriving an ODE by sending the step size of stochastic
45

---

Exact risk curves of signSGD in high-dimensions
difference equation zero and demonstrating that the noise vanishes in the asymptotic limit. In recent years, SDEs have also been integrated into the study of SGD dynamics. In particular, the work of (Li et al., 2019) establishes a weak-approximmaton framework for tracking SGD across a wide range of suitable test functions. (Malladi et al., 2022) further builds on these ideas to derive SDEs for ADAM and RMSprop. Simultancously with our work, (Compagnoni et al., 2025) applies the aeaakaappoximmttoon framework to derive SDEs for SIGNSGD. Their approach leverages the noisy gradient model, which allows them to extend their theory to a broader class of loss functions. In contrast, our approach follows the high-dimensional framework developed by (Paquette et al., 2022a) and (Collins-Woodfin & Paquette, 2023).
In the high-dimensional setting, we are interested in studying a sequence of problems of growing complexity (as dimension goes to infinity). This influences notion of convergence. As shown in Theorem I, we demonstrate that the risk curves of SIGNSGD and its SDE, SIGNHSGD, closely track each other in pointwise sense. This enables us to directly study the behavior of SIGNSGD by analyzing SIGNHSGD, as seen in Theorems 3 and 4. Additionally, the precision of this tracking improves as the dimension increases. In contrast, within the veak-approximation framework, for a fixed dimension, the notion of convergence is more akin to convergence in distribution between the SDE and the optimizer as the learning rate approaches zero. Below, we highlight some of the key differences between these two approaches.
In the following, we will show that SIGNHSGD as defined in (8) is almost recoverable from the weak-approximation framework. The weaa-approximation SDE of (Compagnoni al., 2025) for SIGNSGD with learning rate 17 and constant scheduler is described by
d WA -x(1 - 2P (VI, < 0))d + KV (O JdB,,
(266)
where (I = EVV + Z, for Z the gradient noise, and Σ the covariance matrix of o (O
V ))j. Moreover, the probability and expectation are understood to be taken conditional on @W See (Malladi et al., 2022) for more the noisy gradient model. We consider the quadratic-loss function and to match our label-noise gradient to the noisy gradient, set Z(O)WA) xx ((x, O. - 0.) Et) K(@."> 0.). for x2 (0, K) and e, independent to O.! A. Since the effective learning rate in high-dimension is n/ d. choosing 1/d and plugging this into (266), we obtain
doW 1
2K.
711 21P(x, ((xx, Q. - -O.) eea) < 0)) di + d "
-
M(O dB,
(267)
π
- - [a(x O.F -0.) 0.)- - -c)))] dt + 7 "
2K, M(O dB.,
(268)
V
π
- {+))] 00 Computing the expectation of the signed gradient is not a straight- where M()))= E [xxxx(xx, (x,, 0.² 0
forward task and to reduce to a simplified form requires high-dimensional concentration. See Lemmas 1, 3 and 4. Thus, taking the liberty of fixing the dimension d to be large, for p < 144 as specified in Lemma 4,
doW WA A
-
0.) 0.) + ((( K -0.)
2K, - M((BWA) dB, 10(0(000))) dt + 2V"
1
(269)
O
We present SIGNHSGD for case of reference,
d0, --1 o (R())) (
(((0)) K(O, 0.)dl + VV rd
2K
dB,
(270)
Most notable between SIGNHSGD and (269) is the error O (dop-2 and M() in the drift and diffusion term of (269)
respectively. It is clear that the error in the drift term diminishes as the dimension increases. However, the error in the diffusion term is less obvious. We once again turn towards high- high-dimensional concentration. Indeed, by Lemmas 3, 4 and 12, W
we see that for all 1 S i,j < d, ! )ss = O 11 with high-probabiliiyy
Another important distinction between the two SDEs is the presence of r) in both the drift and diffusion term of SIGNHSGD. Whereas with @AA, is only present in the diffusion term. This relates to the different notions of convergence within the respective frameworks. In the vprk-approo setting, @WA is an order 1 approximate of 0₂ in the sense of
sup TT4l
Big( O WA WADI] []] < C(d, ()d,
(271)
46

---

Exact risk curves of signSGD in high-dimensions
where g is any function with polynomial growth. We see that within fixed dimension setting, O. has improved performance in approximating 0% when -> O and the drift term dominates. On the contrary, SIGNHSGD vanishes if we were to send 1/ + O. Instead, we take the limit in dimension and show that SIGNHSGD improves as dimension d oo. See Theorem 1. Comparing these two regimes, it is not immediately clear whether one can send both 1) - 0 and d - oo in (271) and still retain good approximation. For instance, we fix and send d + oo in (269), we see that the diffusion term persists as K grows with dimension. On the other hand, the drift term vanishes. The consideration dimensionality as the problem scales an important aspect of our work.
47

---

Exact risk curves of signSGD in high-dimensions
H. K does not always reduce the condition number
As counter example consider the covariance matrix,
0.17
0.49
-0.19
-0.36
- 0.49
2.34
0.71
1.79
K
(272)
0.19
0.71
0.32
0.53
0.36
1.79
0.53
1.44
Up to two decimals the condition number 2is <(K) = 115.88. However, the condition number of K is (K) 129.78.
I. Experimental details
The code reproduce these results is available at https::/ts//cc....tt. htttp:://anozymuus 4open. (ogpen.scieenne////iinso---2222 We summarize the experimental setup of Figure in Table 1.
Dataset
Learning Rate (1)
Dimension
Noise Distribution
Noise Details
# Iterations
Synthetic (Gaussian noise)
0.7
500
Gaussian
E|c] 0, B[e3] =
5,000
Synthetic (Cauchy noise)
0.5
500
Cauchy
Location 2. Scale
5,000
CIFARIO
0.9
400
Gaussian (assumed)
E|c] = 1, BB(²]] = 0.76
40,000
= #191 + #292
IMDB
0.2
50
2-GMM (assumed)
m π2
25,000
Elgn] 00.76, B[y] 0.18
E 0.75, Blgå] 0.17
Table 1: A summary of experimental details of Figure 1. The full details of the experiments available below.
The experiments creating Figure 1 were carried out M1 Macbook Air. Homogenized SIGNHSGD is solved via standard Suler-Maruyanm algorithm. The procedure for solving for the risk is described in Appendix B.
Synthetic data:
The synthetic data was generated in dimension d 500. The covariance matrix K was generated by multiplying a random unitary matrix by a diagonal matrix of d log-spaced eigenvalues between 0.01 and 0.5.
was explicitly computed the Gaussian data case and was solved via numerical integration in the case of Cauchy (Student's- s-t family) noise. Note that vanilla SGD does not converge under Cauchy noise and thus we cannot provide a comparison. We plot the 80% confidence interval across 20 runs.
The CIFARIO (Krizhevsky, 2009) data was used perform binary classification by regressing to #1 labels being animals vehicles. The "frog" class was removed to retain balanced classes. The data matrix D is first passed through a random features model so that
CIFARIO:
D,f = tanh DA
(273)
where A is random features matrix of independent standard Gaussians. This choice was found better condition the data so that SIGNODE could be effectively solved via numerical integration.
In order to estimate 0, the regression problem was first solved using Sci-kit learn (Pedregosa et al., 2011) and the resulting solution was taken to be 0, The differences {y - (e.. x,)} for all x; E Drf was then assumed to be the noise. A histogram of this noise is available in Figure 10a. The noise was then fitted to a Gaussian. Finally, 17 = 0.5 and the SIGNSGD plot represents the 80% confidence interval over 50 runs.
48

---

Exact risk curves of signSGD in high-dimensions
Empirical Density Estimated PDF
Empirical Density
0.5
0.5
Estimated PDF
0.4
0.4
0.3
0.3
0.2
0.1
0.1
0.0
0.0
-3
-2
-1
2
-2
2
(a) CIFARIO noise
(b) IMDB noise
Figure 10: Histograms of the estimated noise distributions for the CIFARIO and IMDB datasets. Also shown is the estimated PDFs used to compute for each case.
The IMDB dataset (Maas al., 2011) was first embedded using GLOVE (Pennington et al., 2014) into dimension 50. Then, 2-layer random features model was applied well as some noise added regularize the problem. We add sG where G is matrix of independent standard Gaussians. We take 0.03. This additional regularization was required in the case of text data as the covariance of the original GLOVE embedded data has extremely high condition number making numerically solving our ODEs impossible. The choice of s = 0.03 was found to regularize the data while maintaining the accuracy (== 73%) of trained models. Ultimately the data used is,
IMDB:
Drj tanh(A' tanh D(A + +G)).
(274)
Note that this regularization did not destroy the information contained in the original problem. Sci-kit learn achieves accuracy of Rz 75% on the unregularized problem and the finally accuracy on the regularized problem was & 73%.
We perform the same method as in the CIFARI0 case to first estimate 0_ and then to estimate the distribution of the noise. We fit a mixture of two Gaussians model (GMM) to this noise. yo is trivial to compute exactly when noise is assumed to come from a GMM. The estimated noise is again available in Figure 10,


Reviews:
[{"review_id": "ojtF4q4BPW", "reviewer": "Reviewer_ZURo", "summary": "The authors analyze Sign-SGD for linear regression in high dimensions by deriving limiting differential equations that describe its behavior. Their analysis quantifies four main effects: learning rate adjustment, noise compression, diagonal preconditioning, and gradient noise reshaping. The paper includes theoretical proofs and experimental validation on both synthetic and real datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and address some key points below.\n\n## Minbatching:\n\nWe have added more details regarding batch sizes $b$ in our response to Reviewer ugE8. One particular consequence of minibatching is that our condition on the behaviour of the noise near $0$ relaxes significantly. Averaging multiple sources of noise effectively conditions the noise even for $b = 2$. Numerical results can be found [here](https://anonymous.4open.science/r/revision-2025-stuff-F275/rademacher_batch_comparison_dimension_500_evals_logspace_num_runs_10.pdf) for fixed learning rate, varying batch size.\n\n## Questions:\n\n**First question**\n\n(27) is comparing the risk obtained by the optimally scheduled signSGD to optimally scheduled SGD when data is isotropic. We don’t know the optimal learning rate schedule in non-isotropic settings but what we expect is that whether or not signSGD outperforms SGD depends generally on the magnitude of $\\psi$. \n\nThe argument why can be sketched like: for any signSGD learning rate $\\eta^{S}(t)$ run SGD with a learning rate of $\\eta(t)  =\\eta^{S}(t)\\phi(R_t) / \\sqrt{R_t}$. Now the descent terms are the same up to the $K$ vs $\\overline{K}$ distinction. With this learning rate we see the function $\\psi$ in the variance term on the SGD risk equation. If the various matrices involved ($K, \\overline{K}, K_\\sigma$) are similar enough (as they are when $K=Id$) then whether or not signSGD is beaten by SGD with this learning rate is again determined by the magnitude of $\\psi$. This “similar enough” statement is what we mean by well-conditioned settings.\n\n**Second question**\n\nFor SGD in the same setting, the limiting risk can be found in Equation (254) and is  \n\n$$\n\\frac{\\eta v^2 Tr(K) }{2(2d-Tr(K)\\eta)}.\n$$\n\t\nFor sufficiently small $\\eta$, the limiting SGD risk is $O(\\eta v^2 Tr(K) / d)$.  This is consistent with 'neighborhood' convergence for fixed step-size SGD when $v > 0$ (e.g. Theorem 5.5 of Garrigos-Gower '23, Handbook of Convergence Theorems) and convergence with fixed step-size in the case $v=0$.\n\nIn contrast we can use Theorem 3 to approximate the limiting signSGD risk as up to constants:\n\n$$\n\\frac{\\eta Tr(\\overline{K})}{d} \\max \\left (\\frac{\\eta Tr(\\overline{K})}{d}, v \\right) \n$$\n\nNotably, even if $v = 0$ this limiting risk is not $0$. The simple explanation is that with SGD, the average magnitude of the gradient naturally decreases with the risk and so we effectively take smaller steps; however for signSGD the magnitude of the gradient is always $\\sqrt{d}$ and does not change with the risk. To achieve similar results with signSGD the stepsize needs to be decreased. This aligns with what is seen in practice for algorithms like Adam.\n\n\n## Other: \n\n\"In a nonconvex setting, identifying ....\" paragraph.  We have attempted to improve the wording for clarity, but we’d be happy for additional guidance here.  Our intention is to say that dividing by the norm of the gradient could be reasonable in vanishing gradient situations, such as near saddles.", "claims_and_evidence": "Main Claims and Evidence:\n\nClaims:\n1. Sign-HSGD and its deterministic equivalent ODE are good models for the risk dynamics induced by Sign-SGD \n2. The risk curves of Sign-SGD are well approximated by the risk curves of Sign-HSGD and this approximation improves as dimension grows.\n3. Convergence to a neighbourhood of the solution (?) under a fixed learning rate \n4. The condition number affects whether Sign-SGD or SGD is should be favoured \n\nEvidence:\n1. Figure 1\n2. Theorem 1 / Theorem 2\n3. Theorem 3\n4. Theorem 4\n\nThe evidence to me was convincing and followed from my intuition of the algorithm, however I did not review the appendices in detail. I especially appreciated the mixture of theoretical analysis with a grounded set of experiments which verified the results derived seemed to make sense.", "methods_and_evaluation_criteria": "Benchmarks were a mixture of toy problems like linear regression under varying noise and preconditioned assumptions which more closely resembled the theoretical setting analyzed, as well as a set of more practical experiments on common ML benchmarks like CIFAR10 and IMDB.", "theoretical_claims": "I did not verify the claims in detail but based on my experience they seem reasonable. I would like to double check that the result from theorem 3 roughly align with standard results from stochastic convex optimization regarding SGD with a fixed step-size. If they do not would the authors explain in more detail the differences.", "experimental_designs_or_analyses": "The experimental designs at there face seem sound, and tailored to fit the larger narrative of the paper.", "relation_to_broader_scientific_literature": "I think that this work seems to address a unique and important problem posed by modern optimization research, and I believe a better understanding of the optimization dynamics of algorithms like sign decent would benefit the larger machine learning community.", "essential_references_not_discussed": "Possibly might want to look at \"Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models\"", "other_strengths_and_weaknesses": "Strengths:\n\n1. Comprehensive theoretical framework:\n- Proves convergence to limiting equations\n- Derives exact formulas for limiting risk\n- Quantifies specific effects (learning rate, noise compression, preconditioning, noise reshaping)\n\n2. Strong empirical validation:\n- Theory matches experiments even at moderate dimension (d=500)\n- Works on both synthetic and real datasets\n- Demonstrates convergence under different noise conditions\n\n3. Clear practical implications:\n- Shows when Sign-SGD might outperform SGD (based on condition numbers)\n- Explains behavior under different noise distributions\n\nWeaknesses:\n\n1. Limited scope:\n- Theory only covers linear regression\n- Strongest results require specific noise conditions (C² density near zero)\n- Extensions to non-smooth noise only work above risk threshold\n\n2. Some findings lack theoretical foundation:\n- Success on real (non-Gaussian) data isn't fully explained\n- Authors note this is left for future work\n\n3. Some practical aspects not addressed:\n- Doesn't analyze mini-batch settings\n- Doesn't fully connect to practical deep learning scenarios / analyze non-convex settings.", "other_comments_or_suggestions": "- The \"In a nonconvex setting, identifying ....\" paragraph is broken and needs to be revised.", "questions_for_authors": "- Can you explain: \"But we expect the conclusion of (27) remains mostly true in well-conditioned settings.\"\n- From the above:  I would like to double check that the result from theorem 3 roughly align with standard results from stochastic convex optimization regarding SGD with a fixed step-size. If they do not would the authors explain in more detail the differences.", "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": "NUmFa57H4N", "reviewer": "Reviewer_ugE8", "summary": "The paper studies the dynamics of signSGD in a linear regression setting with Gaussian covariates $x \\sim N(0,K)$ and noisy labels $y = \\langle x,\\theta_\\ast \\rangle + \\epsilon$. The authors derive a limiting SDE (signHSGD) that describes the dynamics of $\\theta$ as the dimension $d \\to \\infty$ which depends on both the covariance $K$ and the distribution of $\\epsilon$. After transforming this process onto a process on the residual $r$, they derive a deterministic equivalent (signODE) which approximates the loss of of signSGD as $d \\to \\infty$. Finally, they compare the SDE for signHSGD to the corresponding SDE for SGD to compare the behavior of the two algorithms and to predict when signSGD should outperform vanilla SGD.\n\n**Update after Rebuttal:** I am satisfied with the author's responses and have updated my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the author for their detailed review and address weaknesses and questions below.\n\n## Weaknesses\n\n\n**Noise reshaping**\n\nFor the $K \\to K_\\sigma$ mapping, there is strong dependence on the eigenbasis of $K$. For example if $K$ is diagonal then $K_\\sigma = Id$. Otherwise, if the eigenbasis is relatively random (such as what is seen in CIFAR and in Figure 4), the operation can preserve some spectral properties of $K$.  For example, in CIFAR-10, $K_\\sigma$ appears to preserve the power-law structure of $K$, albeit with a different power (plots [here](https://anonymous.4open.science/r/revision-2025-stuff-F275/cifar_eigenvalues.pdf)).\n\n\nOne major point (discussed below in response to the learning-rate) is that the the trace of $K_\\sigma$ can be much larger than the trace of $K$, which will cause sign-SGD gradient noise to be a major slow-down\nRigorously saying more is probably difficult. But, we'll rewrite this section in order to be clearer.  \n\n**Assumption 5**\n\nThank you for catching this. We like your suggestion to instead assume $v^T(\\theta_0 - \\theta_*)$ is subgaussian with constant $O(d^{-1/2})$. You're right that general deterministic initialization and targets do not fit the assumption.  For the record, the assumption is for all $z \\in B(||K||)$.   \n\n\n## Questions\n\n**Batch sizes**\n\nThis is a very good question -- thanks for bringing it up.  We have worked out some of the mathematics for batch sizes small compared to $d$, and plan to add the following results to an appendix.\n\nSo first, just to be clear, we are following usual optimization (and standard package) conventions, and we are applying the minibatch average prior to applying the sign-function.  \n\nWe will take a fixed batch size b independent of the dimension of the problem.  One could also look at other scaling regimes, and we expect (based on the fixed batch size case) that the behavior continues to hold for batch sizes that satisfy (b/d) to 0, but we’re only 100% confident for fixed $b,$ and $d \\to \\infty$.  The good news is that even in this limited setting, the story is already interesting.\n\nThe bias-term (or descent-term) is the only term affected by minibatching.  The gradient noise term (the Brownian term in homogenized sgd) is unaffected.\n\nThe homogenized-SGD equation is changed to \n\n$$ \\mathrm{d}\\Theta_t= -\\eta_t N_b \\frac{\\varphi^{(b)}(\\left(\\mathcal{R}({\\Theta}_t)\\right)}{\\sqrt{2 \\mathcal{R}(\\Theta_t)}} \n\\overline{\\mathbf{K}} \\left(\\Theta_t-\\theta^{*}\\right) \\mathrm{d}t \n$$\n\n$$ + \\eta_t \\sqrt{\\frac{2 \\mathbf{K}_\\sigma}{\\pi d}} \\mathrm{~d} \\mathbf{B}_t$$\n\nThe $N_b$ is a numerical constant (the mean of a chi-variable with $b$ degrees of freedom, to the mean of a chi variable with $1$ degree of freedom).  It is asymptotic to $\\sqrt{b}$, consistent with what is shown in Malladi et al.\n\nThe $\\varphi^{(b)}$ is the $\\varphi$ of a new convolved noise.  It is the $\\varphi$ that results from looking at $\\sum_{i=1}^b \\epsilon^{(i)} \\omega_i$ where $\\epsilon^{(i)}$ are iid copies of the label noise and where $\\omega$ is an independent random vector, drawn uniformly from the sphere of dimension $b$.  \n\nWe have run some simulations implementing this (code is available in the anonymous code repository for the paper). Simulations at fixed learning rate, varying batch size are available [here](https://anonymous.4open.science/r/revision-2025-stuff-F275/rademacher_batch_comparison_dimension_500_evals_logspace_num_runs_10.pdf) and with $\\sqrt{b}$ scaling [here](https://anonymous.4open.science/r/revision-2025-stuff-F275/rademacher_batch_comparison_dimension_500_evals_logspace_num_runs_10_rescaled_lr.pdf).\n\n\n**Learning rate scaling**\n\nIndeed, the choice of $\\eta’ = O(1/d)$ is needed to prevent (gradient) noise domination. See the Hessian term of equation 94 where the Hilbert-Schmidt inner product is $O(Tr(K_\\sigma))$. In this setting, if $\\eta’$ decays slower than $1/d$ this noise term would dominate. Had $\\eta’$ decayed faster, the noise term would vanish and we would be performing gradient flow in the high-dimensional limit. \n\nFor SGD it is possible to instead rescale by the “intrinsic dimension” of the data, defined as the trace of covariance normalized by its operator norm ( $Tr(K) / ||K|| $). We think a similar change could be made for signSGD but some care has to be taken since signSGD reshapes the gradient covariance to $K_\\sigma$. This connects to our discuss about the reshaping of gradient noise. Given a diagonal $K$ with intrinsic dimension $O(\\sqrt{d})$, signSGD still has intrinsic dimension $O(d)$ since $K_\\sigma = Id$. This leads to signSGD having learning rates $O(d^{1/2})$ smaller than vanilla SGD to guarantee convergence, leading to slow dynamics.\n\nLet us know if we can clarify anything else; if we have addressed your concerns satisfactorily, we hope that you will consider revisiting your review score.", "claims_and_evidence": "This paper is focused on theoretical understanding and the technical claims are supported by the proofs in Appendices A, B.\n\nThere is a minor claim/conjecture which is unsupported (lines 416-424). It would be good to include a few words about why the authors expect this to hold.", "methods_and_evaluation_criteria": "This paper is focused on developing theoretical understanding in a linear regression setting, and the experiments on more realistic datasets support the idea that Gaussian universality may allow the analysis to extend beyond the Gaussian setting. However, this is not a central claim of the paper.", "theoretical_claims": "I skimmed the proofs in appendices A, B but did not verify their correctness.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "This paper is attempting to understand the effectiveness of coordinate-wise adaptivity (as in Adam) in a concrete theoretical setting. The approach in this paper is most closely related to (Collins-Woodfin & Paquette 2023) which performed a similar analysis for SGD.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n- The paper is generally well written and includes an extended discussion of the different terms in eq. 8\n- The theory seem to match experiments incredibly well (in the linear regression setting)\n- The derivation of the SDE for signHSGD is highly nontrivial\n\nWeaknesses:\n- As acknowledged by the authors, this paper focuses on the simple setting of linear regression with Gaussian covariates. However, even in this setting, we have a very poor understanding of coordinate-wise adaptive optimizers like signSGD or Adam.\n- The paper focuses on online SGD with batch size 1. It would be interesting to extend these results to the more general case.\n- There is limited discussion about the effect of the noise reshaping $K \\to K_\\sigma$.", "other_comments_or_suggestions": "- The use of $\\eta_t'$ for the signSGD learning rate and $\\eta_t := \\eta(t)$ for the rescaled learning rate is a bit confusing\n- The discussion for the effects of $\\epsilon$-compression (4.2) and preconditioning (4.3) are clear but the noise reshaping (section 4.4) is a bit handwavy. In particular, the conjectures in the last paragraph are difficult to follow and could merit additional explanation in the Appendix, even if there is no rigorous theory to back them up. It could also be useful to run some ablations with and without the reshaped noise covariance to check if it's actually beneficial or just a side-effect of the preconditioning.\n- In Assumption 5, $z$ is not defined. Is the assumption that this holds for all $z$? Could this assumption simply be replaced with the assumption that $v^T (\\theta_0 - \\theta^\\ast)$ is sub-Gaussian for any $v$? Also, why does this assumption hold for a deterministic $\\theta_0,\\theta_\\ast$? If $v = R(z;\\overline{K})_i$ is aligned with $\\theta_0 - \\theta^\\ast$ then Assumption 5 forces $\\|\\theta_0 - \\theta^\\ast\\| \\lesssim d^{-1/2}$?", "questions_for_authors": "- This paper focuses on the batch-size $1$ setting. How are both signHSGD and the strength of the SDE approximation affected by the batch size? Would your analysis recover the \"square root\" scaling rule in Malladi et al. for Adam? Additionally, would the analysis extend to batch sizes that grow with $d$?\n\n- The analysis restricts to learning rates $\\eta_t' = \\Theta(1/d)$ (eq. 6). Is the issue that if $\\eta_t' \\gg 1/d$ the noise will dominate and the SDE becomes degenerate in the limit $d \\to \\infty$?", "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": "r52fjmZKZb", "reviewer": "Reviewer_Rgqs", "summary": "This paper studies SignSGD, which can be viewed as Adam without the moment accumulator, in the high-dimensional limit. The main goals of the paper are to quantitatively understand the observed preconditioning and \"noise compression\" effects of SignSGD in practice. Toward this end, a limiting SDE (SignHSGD) and ODE (SignODE) are derived for SignSGD on square-loss linear regression. Notably, this requires non-trivial analysis due to the discontinuous sign operation. The authors then compare SignSGD to SGD in various ways, demonstrating four key differences: 1. effective learning rate, 2. noise compression, 3. diagonal preconditioning, 4. gradient noise rescaling, each of induces regimes where SignSGD may be favorable over SGD or vice versa. Most notably, SignSGD is expected to provide benefits for many non-Gaussian or heavy-tailed noise classes, supporting folk knowledge.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments, we address some key questions here.\n\n**NTK Regime**\n\nIf we write consider the mean square loss for a general neural network $f(\\theta, x)$ in the NTK regime such that $f(\\theta, x) = f(\\theta_0, x) + \\nabla_{\\theta} f(\\theta_0, x) ^T (\\theta_k - \\theta_*)$ then the risk, in a student-teacher setup, is given by \n\n$$\n \\mathcal{R}(\\theta_k) = E [ (f(\\theta_k, x) - f(\\theta_*, x)^2 ] = E[( \\langle \\nabla_{\\theta} f(\\theta_0, x), \\theta_k - \\theta_*\\rangle^2] = (\\theta_k - \\theta_*)^T E[\\Theta(x,x)] (\\theta_k - \\theta_*)\n$$\nwhere $\\Theta$ is the NTK. Therefore in order to describe the NTK regime, we need to understand the expected signSGD updates where the “data” is given by $\\nabla_{\\theta} f(\\theta_0, x)$. Right now, we must assume this is Gaussian. Then, if the model is such that $\\nabla_{\\theta} f(\\theta_0, x)$ is Gaussian then our results will hold as written. In the more likely case that $\\nabla_{\\theta} f(\\theta_0, x)$ isn’t Gaussian but is sufficiently regular (such as subgaussian) then if we can formulate our results for this larger class of data distribution then we can capture the behaviour of this NTK regime.\n\nQuite possibly our equations, if not our method of proof, already hold for subgaussian data given the good agreement with the CIFAR-10 and IMDB datasets which are not themselves Gaussian.\n\n\n**Exponential blowup in T**\n\nThis $e^T$ term appears because we allow for very flexible learning rate scheduling, including schedules where the risks diverge.  With an additional restriction on the smallness of the learning rate, one could improve the exponential explosion in $T$.  It will not go away entirely, however -- optimistically one could put a $polylog(T)$.  On very long time-frames there will always be a chance for the stochastic optimizer to explode.\n\nWe don't have a full picture of how a proof like this would go, but roughly you would want to show that the projection of the errors in each eigendirection of $\\bar{K}$ are $O(1/\\sqrt(d))$ and crucially remain bounded that way in time due to the contractive nature of the dynamics in that eigendirection.  This is also the reason the small stepsize is needed -- to ensure the dynamics tends to contract in each eigendirection, and hence the approximation errors are shrunk as well.  (Our current proof uses a resolvent argument, which is an average over all eigendirections; this is technically simpler, but would not be good as the contractive-ness of the optimizer dynamics is lost).", "claims_and_evidence": "This claims in this paper are well-supported by rigorous theorem statements and proofs, and supporting results in the appendix. Numerical experiments are presented to support the theoretical trends.", "methods_and_evaluation_criteria": "The numerical experiments are helpful for contextualizing the theory, and are documented in the appendix.", "theoretical_claims": "I did not check all the proofs entirely. However, I checked the proof strategies of the main Theorems and they make sense to me. I also checked the comparisons between SGD and SignSGD; these are correct by my verification.", "experimental_designs_or_analyses": "A sufficient description of experiment set-ups is contained in the main paper, with additional details contained in Appendix D and H.", "relation_to_broader_scientific_literature": "This work belongs to the general category of literature concerned with capturing the practical behavior of optimization algorithms in deep learning settings. In particular, this paper takes the approach of deriving the corresponding continuous-time SDE/ODE of its algorithm of interest, SignSGD, and deriving some key properties therein. On the other hand, most of prior works along this line study SGD. However, it is well-understood in practice that vanilla SGD experiences a host of problems in deep learning, for which various practical adjustments have been introduced. I think this work references the important prior work leading to this point, and provides some interesting tools and insights toward closing the \"insight gap\" between SGD and more practical methods like SignSGD and Adam. In particular, the results formalizing the unique interaction of SignSGD and noise are potentially a fruitful way of studying this type of adaptive gradient methods. Furthermore, I think the \"case-by-case\" results, such as when diagonal preconditioning hurts or helps (Section 4.3) are also potentially fruitful, as they may serve as a basis for understanding the relative benefit of other families of non-diagonal preconditioning methods in deep learning, such as KFAC and Shampoo.", "essential_references_not_discussed": "None as far as I can tell.", "other_strengths_and_weaknesses": "I think this paper is quite well-written and understandable. The main insights and arguments are likely of interest to the machine learning optimization community. I have described some of the strengths that stood out to me earlier. I have a few minor things to point out / ask:\n\n- The analysis in this paper is restricted to linear regression and MSE loss (which is acknowledged in the Discussion), and already seems quite involved. It would be helpful to highlight to what degree the broader class of noise considered here can expand expressivity of the problem set-up. Additionally, can the \"linearized\" analysis here potentially extend to the NTK regime (despite the expressivity gap the NTK regime itself suffers)?\n    \n- In the main theorems (Thm 1 and 2), the gap between the discrete descent method and flow) suffers an Exp(T) factor from an application of Gronwall's inequality. This implies for fixed dimension $d$, the drift blows up exponentially in time, which doesn't seem to practically be the case. What would be required to make this bound less conservative, if possible?", "other_comments_or_suggestions": "Minor comments:\n- The authors should remember to put in the Impact Statement.\n- Line 304 first column: \"very SignSGD\" -> \"SignSGD is very\".\n\n(Possibly errant) suggestions:\n\n- As previewed earlier, some other works have considered departing from diagonal preconditioning. The most relevant algorithm in this class is Shampoo (or more recently still, Muon). The base curvature matrix between SignSGD and Shampoo I believe are the same (AdaGrad), but Shampoo does a layer-wise \"Kronecker-Factorization\" rather than the diagonal. I think it would be extremely interesting to see if this type of preconditioning has similar beneficial interaction with noise, and whether it broadens the class of covariances where preconditioning is helpful.", "questions_for_authors": "None beyond the above.", "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": "fSabgo0wEz", "reviewer": "Reviewer_XYtH", "summary": "The paper studies the precise risk curves of signSGD in high dimensional limit for quadratic loss with Gaussian data under certain assumptions on the label noise. It contrasts the risk curves with SGD and quantifies the differences in terms of four effects - effective learning rate, noise compression, preconditioning and gradient noise reshaping. The exact risk curves are numerically verified for various examples.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review, we’re glad that you appreciate our contributions. Our expectation that $K_\\sigma$ inherits a power-law spectrum from $K$ is mostly speculative. We should qualify that this claim is basis dependent. If $K$ is diagonal then $K_\\sigma$ is the identity, which collapses any power-law structure.  So this is more about `very non-diagonal' matrices.\n\nThis is probably best defined as having eigenvectors which are very spread out over the space, such as in CIFAR-10 or in an i.i.d. random matrix.  In the case of CIFAR-10, the map appears to preserve the power-law structure but change the power. We've included an additional plot to illustrate this effect:\nhttps://anonymous.4open.science/r/revision-2025-stuff-F275/cifar_eigenvalues.pdf\n\nWe don't know of an existing theorem demonstrating this effect. \n\nWe’ll revise this section to make ourselves clearer.", "claims_and_evidence": "The claims in the work are theoretical and proofs are provided in the Appendix.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I had a brief look at Appendix A.1, B and C, which seem mostly correct to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The work is well placed among the recent works related to analyzing preconditioned gradient algorithms.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The main strength of the paper is the rigorous extension of HSGD to signSGD and then using the result for the clear discussion of the differences between the risk curves of the two.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can the authors explain the reasoning behind why they expect $K_\\sigma$ to have a power-law spectra when $K$ has power-law spectra?", "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:

Meta-review: The paper studies the dynamics of signSGD in a linear regression setting with Gaussian covariates and label noise and derives a limiting SDE (SignHSGD). This paper makes solid theoretical contribution towards understanding coordinate-wise adaptivity in optimization algorithms, which is at the core of the optimization theory in the era of LLMs. Though the theory is limited to linear regression, the result and analysis is already quite complicated, yet they predict the experiments incredibly well, even for the real dataset like CIFAR10 (though it is linear regression). Reviewers unanimously recommend to accept.
Decision: Accept (poster)