Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum
Authors: Sarit Khirirat
Abdurakhmon Sadiev
Artem Riabinin
Eduard Gorbunov
Peter Richtárik
Venue: NeurIPS 2025 poster ()
Keywords: Generalized smoothness
error feedback
normalization
stochastic gradient descent
momentum
Primary area: optimization

Abstract: We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. 
Despite their popularity and efficiency in training deep neural networks, traditional analyses of error feedback algorithms rely on the smoothness assumption that does not capture the properties of objective functions in these  problems. 
Rather, these problems have recently been shown to satisfy generalized smoothness assumptions, and the theoretical understanding of error feedback algorithms under these assumptions remains largely unexplored. 
Moreover, to the best of our knowledge, all existing analyses under generalized smoothness either i) focus on single-node settings or ii) make unrealistically strong assumptions for distributed settings, such as requiring data heterogeneity, and almost surely bounded stochastic gradient noise variance. 
In this paper, we propose distributed error feedback algorithms that utilize normalization to achieve the $\mathcal{O}(1/\sqrt{K})$ convergence rate for nonconvex problems under generalized smoothness. Our analyses apply for distributed settings without data heterogeneity conditions, and enable stepsize tuning that is independent of problem parameters. 
Additionally, we provide strong convergence guarantees of normalized error feedback algorithms for stochastic settings. 
Finally, we show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks, including the minimization of polynomial functions, logistic regression, and ResNet-20 training.

Error Feedback under (Lo, -mmmoohhhssss:: Normalization and Momentum
Sarit Khirirat
Abdurakhmon Sadiev KAUST abdurakhmon. andievvkaust. edu. sa
KAUST
sarit www.riattkkksst....mm edu.
Artem Riabinin
Eduard Gorbunov
KAUST
MBZUAI
artem. rrtee.riabininnkauus. edu. sa
eduard. soraarddggrbuu
Peter Richtárik
KAUST
peter wwwhtarikkkausste...........eeee edu.
Abstract
We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. Despite their popularity and efficiency in training deep neural networks, traditional analyses of error feedback algorithms rely on the smoothness assumption that does not capture the properties of objective functions in these problems. Rather, these problems have recently been shown to satisfy generalized smoothness assumptions, and the theoretical un- derstanding of eттor feedback algorithms under these assumptions remains largely unexplored. Moreover, to the best of our knowledge, all existing analyses un- der generalized smoothness either focus on single-node settings or ii) make unrealistically strong assumptions for distributed settings, such requiring data heterogeneity, and almost surely bounded stochastic gradient noise variance. In this paper, we propose distributed error feedback algorithms that utilize normalization to achieve the O(1/ ((//V) convergence rate for nonconvex problems under generalized smoothness. Our analyses apply for distributed settings without data heterogencity conditions, and enable stepsize tuning that is independent of problem parameters. Additionally, we provide strong convergence guarantees of normalized error feed- back algorithms for stochastic settings. Finally, show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts various tasks, including the minimization of polynomial functions, logistic regression, and ResNet-20 training.
Introduction
Machine learning models achieve impressive prediction and classification power employing sophisticated architectures, comprising vast numbers of model parameters, and requiring training on massive datasets. Distributed training has emerged
important approach, where multiple
Sarit Khirirat, Abdurakhmon Sadiev, Artem Riabinin, and Peter Richtárik are with the Center of Excellence for Generative AI, King Abdullah University Science and Technology (KAUST), Thuwal, Saudi Arabia. 'Eduard Gorbunov is with the Department of Statistics and Data Science, Mohamed bin Zayed University of Artificial Intelligence (MBZUAD), Abu Dhabi, United Arab Emirates.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

machines with their own local training data collaborate to train model efficiently within reasonable time. Many optimization algorithms can be easily adapted for distributed training frameworks. For example, stochastic gradient descent (SGD) can be modified into distributed stochastic gradient descent within a data parallelism framework, and into federated averaging algorithms [1] in a federated learning framework. However, the communication overhead of running these distributed algorithms poses a significant barrier to scaling up to large models. For example, training the VGG-16 model [2] using distributed stochastic gradient descent involves communicating 138.34 million parameters, thus consuming over 500MB of storage and posing an unmanageable burden on the communication network between machines.
One approach mitigate the communication burden to apply compression. In this approach, the information, such as gradients or model parameters, is compressed using sparsifiers or quantizers to be transmitted with much lower communicated bits between machines. However, while this reduces communication overhead, too coarse compression often brings substantial challenges in maintaining high training performance due to information loss, and in extreme cases, may potentially lead to divergence. Therefore, error feedback mechanisms have been developed improve the convergence performance compression algorithms, while ensuring high communication efficiency. Examples of error feedback mechanisms include EF14 [3, 4, 5, 6, 7J, EF21 [8, 9], EF21-SGDM [10], EF21-P [1 I], and EControl [12]. Several studies developing error feedback algorithms often assume the smoothness of objective function, i.e., its gradient is Lipschitz continuous.
However, many modern learning problems, such as distributionally robust optimization [13] and deep neural network training, are often non-smooth. For instance, the gradient of the loss computed for deep neural networks, such as LSTM [14], ResNer20 [14], and transformer models [15], is not Lipschitz. continuous. These empirical findings highlight the need for new smoothness assumption. One such assumption is (Lo, L1 smmoothness, originally introduced by Zhang et al. [14], for twice differentiable functions, and later extended to differentiable functions by Chen et al. [16].
To solve generalized smooth problems, clipping and normalization have been widely utilized in first-order algorithms. Gradient descent with gradient clipping was initially shown by Zhang et al. [14] to achieve lower iteration complexity, i.c., fewer iterations needed attain a target solution accuracy, than classical gradient descent. Subsequent works have further refined the convergence theory of clipped gradient descent [17], and improved its convergence performance by employing momentum updates [18], variance reduction techniques [19]. and adaptive step sizes [20, 21, 22]. Similar convergence results have been obtained for gradient descent using normalization [23], and its momentum variants [24], including generalized SignSGD [15]. However, these first-order algorithms have mostly been explored in training on a single machine. To the best of our knowledge, distributed algorithms under generalized smoothness have been investigated in only few works, e.g., by Crawshaw et al. [25], Liu et al. [26]. Nonetheless, these works rely on assumptions limiting families of optimization problems, including data heterogeneity, almost sure variance bounds, and symmetric noise distributions around the mean assumptions. Furthermore, these first-order algorithms under generalized smoothness do not incorporate compression techniques to improve communication efficiency. These aspects motivate us to develop distributed communication-effiiee algorithms for solving nonconvex generalized smooth problems.
1.1 Contributions
In this paper, we develop distributed error feedback algorithms for communication-efficcenn optimiza- tion under nonconvex, generalized smooth regimes. Our contributions are summarized below.
Importance of normalization. Just as gradient clipping is crucial for gradient descent, we empirically demonstrate that normalization stabilizes the convergence of error feedback algorithms for minimizing nonconvex generalized smooth functions. In this paper, we introduce variant of EF21, a widely used error feedback algorithm by Richtárik et al. [8], which incorporates normalization guarantee convergence for nonconvex, generalized smooth problems. In single-node setting, this new method, which we call ||EF21-GD],, or more compactly as ||EF21]|, provides larger stepsize, and faster convergence rate than its non-normalized counterpart EF21 for minimizing simple nonconvex polynomial functions that satisfy generalized smoothness, as shown by Figure 1.
Convergence of normalized error feedback algorithms. We establish an ((1/VK convergence rate in the gradient norm for ||EF21| on nonconvex generalized smooth problems. ||EF21| achieves

---

Figure 1: The minimization of polynomial functions using EF21 with 7 L+LV and ||EF21||
with 7 VK+1* 7 (blue line) and 7 2cr (green line). Here, we ran both algorithms for (1)
Lo 4, L1 1, and 2, 000 (left), (2) Lo = 4, L1 = 4, and K = 5, 000 (middle), and (3)
Lo 4. L1 8, and K 16, 000 (right).
the same rate as EF21 under L-smoothness by [8]. Our results are derived under standard assumptions, Le., generalized smoothness and the existence of lower bounds the objective function, and applicable in distributed settings regardless of any data heterogeneity degree, unlike the results by Crawshaw al. [25], Liu et al. [26]. Additionally,
stepsize rules for ||EF21 ensure convergence without requiring knowledge of the generalized smoothness constants Lo or L1, in contrast to Richtárik et al. [8], where the stepsize depends the smoothness constant L (which is often inaccessible).
Extension to stochastic settings. Furthermore, propose variant of EF21-SGDM error feedback algorithm with momentum updates by Fatkhullin et al. [10], that employs normalization for solving nonconvex, stochastic optimization under generalized smoothness. Specifically, prove that ||EF21-SGDMI] with suitable stepsize choices attains the same O K2/4) convergence rate in gradient norm as EF21-SGDM.
Numerical evaluation. We implemented ||EF2|] using the stepsize rules derived from our theory, and compared its performance against EF21. Both algorithms were evaluated on three learning tasks: minimizing nonconvex polynomial functions, solving logistic regression with nonconvex regularizer, and training ResNet-20 on the CIFAR- 10 dataset. Thanks its larger stepsizes, ||EF21|] outperforms EF21, in terms of both convergence speed and solution accuracy across these tasks.
Methods
Complexity
Smoothness
Variance bound
Normalization
EF21
0(1/2)
No
No
Richtárik et al. [8]
EF21-SGDM
O(1/et)
L
expectation
No
Fatkhullin et al. [10]
||EF21]]
0(1/²)
(Lo; In)
No
Yes
NEW (Alg. 1)
IEF21-SGDMI]
0(1/e) (Lo. L1)
Expectation
Yes
NEW (Alg. 2)
Table 1: Comparisons of complexities and assumptions between known and our results for EF21 variants. The complexity is defined by the iteration count K required by the algorithms attain min [||v/(>>)|]] S (Lo, L))-mmothhness refers to generalized smoothness in Assump- k=U,1....K
tion 3. The variance bound in expectation is defined in Assumption 5.
Related Works
Error feedback. Error feedback mechanisms have been utilized in various algorithms with com- munication compression, leading to significant improvements in solution accuracy, while reducing communication. As the first version of these mechanisms, EF14 was introduced by Seide al. [3], and later analyzed for first-order algorithms in both single-node [4, 27] and distributed settings [5, 6, 28, 29, 7, 30, 31, 32]. Next, EF21 is another error feedback variant proposed by Richtárik et al. [8], which offers strong convergence guarantees for distributed gradient algorithms with any

---

contractive compressors, without requiring bounded gradient norm or bounded data heterogeneity assumptions. EF21 can also be adapted for stochastic optimization through sufficiently large mini- batches [9] or momentum updates [10]. More recently, EControl was developed by Gao et al. [12] to guarantee provably superior complexity results for distributed stochastic optimization compared to prior error feedback mechanisms. To the best of our knowledge, these existing works on error feedback have focused solely on optimization under traditional L-smoothness. In this paper, we introduce normalized variant of the EF21 methods [8] for solving nonconvex generalized smooth problems, In particular, we prove that ||EF21 || under generalized smoothness achieves the same O(1/VK) rate as EF21 under traditional smoothness, and demonstrate in experiments that ||EF21]] permits larger step sizes, and thus attains faster convergence than EF21.
Non-smoothness assumptions. Empirical findings suggest that the traditional smoothness used for analyzing optimization algorithms does not capture the properties of objective functions in many machine learning problems, especially deep neural network training problems. This motivates researchers to consider different assumptions to replace this traditional smoothness condition. First introduced by Zhang et al. [14], the (Lo, Li }-mmoothness condition on a twice differentiable function f() defined by f(x)] Lo + L1 [x)]] for z Rd. This (Lo, L1) -moothhess has been extended to differentiable functions without assuming the existence of the Hessian. For instance, the smoothness with a differentiable function {(x:) [33], and symmetric generalized smoothness [16] cover the (Lo, L1) -mmoothness when the Hessian exists, and includes many important machine learning problems, such as phase retrieval problems [16), and distributionally robust optimization [34]. Other classes of non-smoothness assumptions, which are not related to the generalized smoothness but capture other optimization problems, include Hölder's continuity of the gradient [35], the relative smoothness [36], and the polynomial growth of the gradient norm [37]. In this paper, we impose the generalized smoothness condition to establish the convergence of ||EF21|| for solving deterministic and stochastic optimization.
Gradient clipping and normalization. Clipping and normalization are commonly employed in gradient-based methods for solving generalized smooth problems. Clipped (stochastic) gradient descent has been studied for both nonconvex and convex problems under (I.g, L, )smmmoohsssss conditions by Zhang et al. [14], Koloskova et al. [17]. Extensions to clipped gradient algorithms have been proposed, including momentum updates [18], variance reduction methods [19], and adaptive step sizes [20, 21, 22, 38). Comparable complexities have been achieved for normalized gradient descent [23], and its pooentuum-assed variants [24], including SignSGD [15] and its variance-reducttio variants [39]. Convergence properties of gradient- based algorithms have also been explored under more generalized forms of non-uniform smoothness, extending beyond the (Lo, L1)-smoothness by Zhang et al. [14] to cover a wider range of optimization problems. For example, variants of (stochastic) gradient descent have been analyzed under a-symmetric generalized smoothness by Chen et al. [16], and under Ê-smoothness involving certain differentiable functions f(-) by Li et al. [33, 21]. However, the majority of these analyses focus on the single-node setting. To the best of our knowledge, only limited number of works, such those by Crawshaw et al. [25], Liu et al. [26], have examined federated averaging algorithms for nonconvex problems under generalized smoothness. These works, however, often rely on restrictive assumptions, including data heterogeneity, almost sure variance bounds, and symmetric noise distributions centered around their means. In this paper, we develop distributed error feedback algorithms, which eliminate the need for the restrictive assumptions mentioned above, and rely on standard assumptions on objective functions and compressors.
emplooye
Preliminaries
Notations. We use [n] to denote the set 21, and E [[] to represent the expectation of a random variable u. Additionally, |I=I| indicates the Euclidean norm for vectors the spectral norm for matrices, and I|-1|, is the foomr for vectors, while (I, y) denotes the inner product between x and in IRd, Lastly, for a square matrix A E Rdxd Amin(A) refers to its minimum eigenvalue, and I E Rdxd is the identity matrix.
Problem Formulation. We focus on the following distributed optimization problem:
((x) = 1 a (10)
-
min #ER
(1)

---

where n refers to the number of clients, and fz) is the loss of a model parameterized by vector I E Td over its local data D, owned by client E [n).
Assumptions. To facilitate our convergence analysis, we make standard assumptions on objective functions and compression operators.
Assumption (Lower Boundedness of f). The function f is bounded from below, i.e,,
fom inf
f(x) -00.
=ER
Assumption 2 (Lower Boundedness of Ji). For each i E [n]], the function St is bounded from below, Le.,
fin inf f1(2) > -cc.
ZERd
Assumptions and 2 are standard for analyzing optimization algorithms for unconstrained problems.
Assumption 3 (Generalized Smoothness of ft). A function f((x) is symmetrically generalized smooth
there exists Lo, L1 > O such that for ug = fr (1 8)y, and for all x. y E R
[V - S La L1 sup [V | y/l 6E|0.1]
Assumption refers to symmetric generalized smoothness by Chen et al. [16], which covers asym- metric generalized smoothness [17, 16], and the original (Lo, Li }-mmothnness by [14]. Moreover, Assumption covers the functions with unbounded classical smoothness constant, e.g., exponential function. Additionally, Assumption 3 with Lı 0 reduces to the traditional Lo-smoothness [40, 41], under which the convergence of optimization algorithms has been extensively studied.
Assumption 4 (Contractive Compressor). An operator C* IRd Rd is a-contractive compressor if there exists a e (0, 1] such for l 2 and v E Rd.
E [|| -
=12 (v)
(1 a) a) ||012
Furthermore, compressors defined by Assumption 4 cover top-k sparsifiers [5, 4], low-rank approxi- mation [42, 43], and various other compressors described by Safaryan et al. [44], Beznosikov et al. [45], Demidovich al. [46].
Assumption (Bounded Variance). A stochastic gradient Vf(x;; {i) with its sample & ~ DD is an unbiased estimator of f((x) with bounded variance, i.e., for all x E IRd,
E fx(; = f((2), and [lV - Vf((())1? 5
Assumption is standard for stochastic optimization [47, 48, 49] that is only imposed on each local stochastic gradient, and it does not imply data heterogeneity, i.e., the bounded difference between each component function fa (x) and the global function fxx
Normalized Error Feedback ([|EF21]))
For nonconvex deterministic optimization under generalized smoothness, we develop a distributed emor feedback algorithm. One challenge is that the generalized smoothness parameter scales with the gradient norm | f [a=) To resolve this issue, we apply gradient normalization to the algorithms. In particular, consider ||EF21]], the normalized version of EF21 [8] that updates the next iterates
x k+1 using the ||EF21|] update. The full description of ||EF21]] can be found in Algorithm 1.
Our new method ||EF21]], just like EF21 [8] under traditional smoothness, enjoys the ((IVK)) convergence in the gradient norm under generalized smoothness, as shown below.

---

Algorithm Normalized Error Feedback (||F21)))
Input: Stepsize 7 > 0 for &:
starting points x 91
Rd for {1. 21.2.... n and
a-contractive compressors C* [Rd R² for k = I....
2: for each iteration & = 0, 1, K do
3: for each client 1, 2, ..... n in parallel do
4: Compute local gradient ff(((
5: Transmit A = C* (V f((x*) 1
6: Update of 9i A
7: end for
8: Central server computes g" 1
n -i=1 of via o k-1
9: Central server updates #+1 x. 7k 11
end for
11: Output: x: K+1
Theorem 1 (Convergence of ||EF21]). Consider Problem (1), where Assumption 1 (lower bound on f), Assumption 2 (lower bound on fi), Assumption 3 (generalized smoothness of fi), and Assumption 4 (contractive compressor) hold. Then, the iterates {x²) generated by ||EF21]| (Algorithm 1) with
7
Th
VK +1
for K 2 0 and 7 > 0 satify
0 exp((8111 L1 exp(L17)??)
BB- exp(L11)
min E Vf(x*))
k=0.,...,KK K
VK
v +1
where V = f(x pinf + 1-VT-
2% 1 E
Vf((+t) -
- B 200 8h1es Ei - f.
and c;
1/2 2 VT-a
L; ior 0,
1-VI-o
Theorem establishes the (1IVV)) convergence in the expectation gradient norms for [|EF21]] nonconvex deterministic problems under generalized smoothness. This rate is the same as Theorem of Richtárik et al. [8] for EF21 under traditional smoothness, and does not depend on data heterogeneity conditions in contrast to Crawshaw et al. [25], Liu et al. [26]. Also, stepsize depends on any positive constant "o. and total iteration count K, without needing to know smoothness
constants Lo, Li in contrast Richtárik et al. [8]. Additionally, if we choose 7o 1/(8cL1), then our convergence bound from Theorem becomes
32cL, VO LL L1 + 2L,
min k=
S
K
VK +1
where 1/2 2
VI --V and ginf EE - f!nt).
Comparisons between ||F22|| and EF21 under traditional smoothness. For nonconvex, traditional smooth problems, ||EF21|| from Theorem 1 with L1 0 achieves the same O(1v/K) rate in the expectation of gradient norms as EF21 analyzed by Richtárik et al. [8], but with a larger convergence factor of 2. We refer to the derivation and discussion details in Appendix C.
In the following section, we demonstrate how to integrate normalization into EF21-SGDM [10], an error feedback algorithm that allows each node compute its local stochastic gradient, for solving nonconvex stochastic problems.
5 Normalized Error Feedback with Stochastic Gradients & Momentum (|EF211-GGDMI)
Having established the convergence of ||EF21| for deterministic optimization, we will next develop distributed error feedback algorithm that incorporate stochastic gradients and normalization to accom- modate generalized smoothness conditions. In particular, focus on
(Algorithm 2),

---

Algorithm 2 Normalized Error Feedback with Stochastic Gradients & Momentum (/JF221-SGDM))
Input: Stepsizes 7 0 and 7 E [0, 1] for k 0, o......; starting points x 9; R for (., n), and i/ (. (?) with independent random samples & for .L.2.....1. a-contractive compressors C R2 R for k 0, 1....
2: for each iteration & = o....... K do
3: for each client 1, ..... n parallel do
4: Compute local stochastic gradient V [ gl)
5: Update a momentum estimator uy (1 m + Vh Vitatt)
6: Transmit A C*
(v) 9h
7: Update of - 96 A
8: end for
9: Central server computes g" 1 Ei=1 of via gft = 9 d-11 A
n
Central server updates 2+1 x² 7k l1
11:
end for
12:
Output: x: K+1
the normalized version of EF21-SGDM due to Fatkhullin et al. [10]. We also note that ||EF21-SGDM] recovers many optimization algorithms of interest in the special cases. For instance, it reduces to
normalized version of EF21 [8], which call ||EF2|||, when let Vi and fi(;; <+) = fxr*),
normalized version of EF21-SGD [9), which we call ||EF21-SGDj,, when we let Tu 1, and
normalized version of SGDM [50], which call ||SGDMIJ*, when we let 7/k- Bx and (*()) is the identity compressor/mapping..
In the next theorem, we demonstrate that ||EF2--SGDDD attains the same 0(1/K1/1) convergence rate both EF21-SGDM and ||SGDMIJ-
Theorem (Convergence of ||EF21-SGDMIX, Consider Problem (1), where Assumption (lower
bound on f). Assumption 2 (lower bound on fi). Assumption 3 (generalized smoothness of fih.
Assumption (contractive compressor), and Assumption 5 (bounded variance) hold. If 9, for
i E
n) and
Y (K + 1)%/ 1
min {(K+))* 11K+))/C..13 and
7kk E
with 0 < 167,
mh =
(K + 1)4/**
where Ca : vI a, then the iterates {a²} generated by ||EF21-SGMM]] (Algorithm 2) satisfy for K 2
8 + o/ + 7Lg + L7ginl)
E
0
(K + +1)
Vl-a
+ (Tn + T.38lat)
+0
(K 1K
(K 1)%/
where 80 = f(x²) ) fintt and ginf : 1 Σ (finf- - flnf).
From Theorem 2, ||EF21-SDDM] under generalized smoothness achieves the O(1 O(1/K1/1) conver- gence rate in the expectation of gradient norms. This rate is the same as that of EF21-SGDM, previously analyzed under traditional smoothness by Fatkhullin et al. [10, Theorem 3]. The result holds regardless of the data heterogeneity degree and the mini-batch size. We also notice that the stepsize tTo for constant L1. and the compression parameter a. However, the considered choice of stepsizes is agnostic to and Lg-
unlike in the case of [|FF21]], depends the generalized smoothness
"This method is also known NSGD-M.

---

Furthermore, Theorem 2 with = 1 (i.e., C* is the identity compressor) implies the convergence
bound of the distributed version of normalized SGD with momentum (JSGDM]J) [50] using 3 n7.
min E Vf("")l - o "/) %/vT + 7 7L380mn
(5)
(K + 1)1/
For the single-node SGDM, where n and ginl O, our convergence bound in (5) with y convergence, which matches the rate obtained by Hübler et al. [24, Corollary 3]. Unlike the earlier results for single-node SGDM, our result holds for the multi-node regime. The bound in (5) for multi-node SGDM includes the 5/v7-term indicating
(2/1za) achieves the O (<(((x")) (((((=))ff")) (ar((a")-"""")+++++ +o0//ttt///
(K (K+1)4/
/n-fold reduction in the influence of stochastic variance noise o, and the -Lf -term accounting for the effect of data heterogeneity.
Novel proof techniques for ||EF21|| and ||EF21-SGDMI] under generalized smoothness. Our analysis demonstrates that ||EF21|| achieves the convergence rate under generalized smooth- ness equivalent to EF21 under traditional smoothness. However, our proof techniques differ significantly from prior work. We employ different Lyapunov functions. For ||EF21]|, we I in constrast to Richtárik et al. [8] that (f((t* - 1 For ||EF21-SGDMJ, we use V
use V = f(x*) finf + A Ei=1
VV
uses V = [(x*) - flat + B
D
[a**) fiml E
n Ei ||o
g
+
E
10 VV((=*)]| unlike Farkhullin et al. [10] that || E
V/((=>) These new Lya- punov functions necessitate the Lyapunov- based convergence analysis, distinct from standard tech- niques for error feedback methods. Our analysis leverages Lemma 2 to handle generalized smooth- ness. For ||EF21]|,
uses V = f(**) piul
+ + + ||
of + +
Il, we rely on Lemma 4. For ||EF21-SGDM] we derive a new upper-bound on E [||e* (=())))) unlike Fatkhullin al. [10] to show the /n-speedup for the term proportional to a, and utilize non-uniform weights to obtain convergence in the gradient norm.
Experiments
In this section, evaluate the performance of [|EF21]], and compare it against EF21 [8]. We test these algorithms for three nonconvex, generalized smooth problems: the problem of minimizing polynomial functions, the logistic regression problem with nonconvex regularization term over synthetic and benchmark datasets from LIBSVM [51], and the training of the ResNet-20 [52] model over the CIFARIO [53] dataset'. For all experiments, we use a top-k sparsifier, which is a d' e-contractive compressor.
6.1 Logistic Regression with a Nonconvex Regularizer
First, we consider a logistic regression problem with nonconvex regularizer, i.e., Problem (1) with
f((x) log(1 + exp(-bbaa x)) +
1 1+ ++
where E IRd is the 2th feature vector of data matrix A E xxd with its class label by E {-1,1}, and > 0 is a regularization parameter. Here, f(x) is nonconvex, and L-smooth with L
|| /44n) + 2x. Also, each f((x) is L--smooth with f. = ||a]|= / + 2X, and generalized smooth with Lo= = 2\ + max, ||a:]] and L1 max, ||a,]]. The derivations of smoothness parameters can be found in Appendix H.
In this experiment, we initialized z.0 E IRd, where each coordinate was drawn from standard normal distribution (N 1), and set À 0.1. Here, the condition À Amin (AT A) /22) ensures that f(x) is nonconvex. We ran ||F21|| and EF21 on the following datasets: (1) two from LIBSVM [51]: Breast Cancer (n 683, synthetically generated dataset (n 20, d 10), where the data matrix A Raxd had entries
10, and scaled to [-1, 1)). and a1a (n 1605, d 123): and (2)
drawn from (00, 1), and the class label b; was set to either 1 or with equal probability. For
We implemented EF21 and ||EF21]] on training the 2esNet-20 model by using Py Torch. Our source codes can be found in the link to arror-feedbcck segeralized-smoottheee paper.

---

EF21, we selected the stepsize 7 = 1/ 1/(L L/83 with L = E i=
nn, n, 0 1 vI
given by Richtárik et al. [8, Theorem 11. For ||EF21||, we chose The = >>///++ + with y 0 from Theorem I, by setting fo 1, K 100 for the generated data and Breast Cancer, and = 400 for ala. We choose "o = 1, because ||EF21|] with to E [1, 10] converges faster than that with small values of " (c.g. 0.1). when run the algorithm on single node (n = 1) for minimizing polynomial function and solving logistic regression. We determine K as the smallest number of iterations required to achieve the desired accuracy by performing grid search with a stepsize of 50.
and B (1- (1-a)/(1-v)))
Figure 2 shows that ||EF21|| outperforms the traditional EF21 on all evaluated datasets, achieving faster convergence and higher solution aceuracy. This improvement results from the fact that the theoretical stepsize for ||EF21]|, derived in Theorem I, is larger than the stepsize for EF21 outlined by Richtárik et al. [8. Theorem 1].
228
1.C
D05
20.00
4:03
3000
Figure 2: Logistic regression with nonconvex regularizer using normalized ||EF21|] and EF21. We reported [V](>>)] ||² with respect to iteration count k. We used the constant stepsize 7 I. I.t.. ;
for EF21, and 7 - = 1 for ||EF21]]. Here, K = 100 for our generated data (left), and Breast Cancer (middle), while K = 400 for ala (right).
6.2 ResNet20 Training Over CIFAR-10
Next, we trained the ResNet20 [52] model on the CIFAR-10 [53] dataset, which was demonstrated
empirically by Zhang et al. [14] satisfy the (To, L.)-smoothness condition. In these experiments, we used a top-k compressor over 50, 000 training images, with evaluation on 10, 000 test images. The dataset was evenly distributed among clients, each using a mini-batch size of 128. Both algorithms
were run for 100 epochs with a constant stepsize = 5. Here, one epoch refers to full pass through the entire dataset processed by all clients.
From Figure 3, under the same constant stepsize and the top-k sparsifier with k = 0.01d, ||EF21]] outperforms EF21, in terms of convergence speed (in gradient norms and losses) and accuracy, relative to the number of bits communicated from each client to the server. Specifically, ||EF21|] achieved accuracy gains of up to 10% over EF21.
EPP
Figure 3: ResNet20 training on CIFAR-10 10 by using EF21 and ||EF21|| under the same stepsize 7 = 5
and l: = 0.1d for top-k sparsifier.
7 Conclusion and Future Works
In this paper, we have demonstrated that normalization can be effectively combined with EF21 to develop distributed error feedback algorithms for solving nonconvex optimization problems under generalized smoothness conditions. Specifically, ||EF21] and ||EF21-SGDM]] achieve convergence

---

rates of /21/K)/2) in deterministic settings and (11////)) in stochastic settings, respectively. These convergence rates match those of the vanilla EF21 and EF21-SGDM algorithms. Unlike previous works on distributed algorithms under generalized smoothness, our analysis does not assume data heterogeneity or impose smoothness-deennden restrictions on the stepsize (in the deterministic case). Finally, our experiments confirm that ||EF21|| exhibits stronger convergence performance compared to the original EF21, due to its larger allowable stepsizes.
Our work implies many promising research directions. One interesting direction is to extend our convergence results for ||EF21]| and ||EF21-SGMM] to accommodate decreasing or adaptive stepsize schedules, as the constant stepsizes required by our current analysis can become impractically small when the total number of iterations large. Another important direction is the development of distributed and federated algorithms that leverage clipping or normalization for minimizing nonconvex generalized smooth functions.
Acknowledgements
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFS- CRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.
References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efffccient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[2] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
[3] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- parallel distributed training speech DNNs. Fifteenth annual conference of the international speech communication association, 2014.
[4] Sebastian U Stich, Jean- Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. Advances Neural Information Processing Systems, 31, 2018.
[5] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cé- dric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems. 31, 2018.
[6] Jiaxiang Wu, Weidong Huang. Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In International conference on machine learning, pages 5325-5333. PMLR, 2018
[7] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly con- verging error compensated SGD. Advances in Neural Information Processing Systems, 33: 20889-20900, 2020.
[8] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 4384 4396, 2021.
[9] Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.032944 2021.
[10] Iyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feedback! Advances in Neural Information Processing Systems, 36, 2024.
10

---

[11] Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. EF21-P and friends: Improved theo- retical communication complexity for distributed optimization with bidirectional compression. In International Conference on Machine Learning, pages 1 1161-11807. PMLR, 2023.
[12] Yuan Gao, Rustem Islamov, and Sebastian U Stich. EControl: Fast distributed optimization with compression and error control. In The Twelfth International Conference on Learning Representations, 2024.
[13] Jikai Jin, Bohang Zhang. Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances Neural Information Processing Systems, 34:2771-2782, 2021.
[14) Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
[15) Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signSGD. Advances neural information processing systems, 35:9955-99900
2022.
[16] Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooot nonconvex op- timization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pages 5396- 5427. PMLR, 2023.
[17] Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pages 17343-17363. PMLR, 2023.
[18] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511- 15521, 2020.
[19] Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5. IEEE, 2025.
[20] Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng. Ruoyu Sun, Zhi-Ming Ma, Tie- Yan Liu, Zhi-Quan Luo, and Wei Chen. Provable adaptivity of adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2960-2969, 2024.
[21] Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie, Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024.
[22] Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Parameter-fres clipped gradient descent meets polyak. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[23] Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1-13, 2021.
[24] Florian Hübler, Junchi Yang. Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. International Conference on Artificial Intelligence and Statistics, pages 4861-4869. PMLR, 2024.
[25] Michael Crawshaw, Yajie Bao, and Mingrui Liu. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. Advances Neural Information Processing Systems, 36, 2024.
[26] Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-effiiene distributed gradient clipping algorithm for training deep neural networks. Advances Neural Information Processing Systems, 35:26204-26217, 2022.

---

[27] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[28] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Liu. Doublesquezze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning, pages 0155-6165. PMLR, 2019.
[29] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-Iocal-SGD. Distributed SGD with quantization, sparsification and local computations. Advances Neural Information Processing Systems, 32, 2019.
[30] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference Machine Learning, pages 5895-5904. PMLR, 2020.
[31] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. Advances in Neural Information Processing Systems, 34:30401-30413, 2021.
[32] Hanlin Tang, Yao Li, Ji Liu, and Ming Yan. Errorcompensatedx: error compensation for variance reduced algorithms. Advances in Neural Information Processing Systems, 34:18102-1811 2021.
[33] Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non- convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024.
[34] Daniel Levy. Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33: 8847-8860, 2020.
[35] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
[36] Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematicc of Operations Research, 42(2):330-348, 2017.
[37] Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pages 7325-7335. PMLR, 2021.
[38] Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (Lo, L1 smooth optimization: Clipping, accel- eration, and udaptivity. In The Thirteenth International Conference on Learning Representations, 2025.
[39] Wei Jiang, Sifan Yang, Wenhao Yang. and Lijun Zhang. Efficient sign-based optimization: Accelerating convergence via variance reduction. Advances Neural Information Processing Systems, 37:33891-33923 2024.
[40] Yurii Nesterov et Lectures on convex optimization, volume 137. Springer, 2018
[41] Amir Beck. First-order methods in optimization. SIAM, 2017.
[42] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: practical low-rank gradient compression for distributed optimization. Advances in Neurul Information Processing Systems, 32, 2019.
[43] Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtarik. FedNL: Making newton-type methods applicable to federated learning. In International Conference on Machine Learning, pages 18959-19009 PMLR, 2022.
12

---

[44] Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 11(2):57-5800 2022.
[45] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 1402 2023.
[46] Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the zoo of biased SGD. Advances in Neural Information Processing Systems, 36:23158-23171, 2023.
[47] Arkadii S Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19(4):1574-1609 2009.
[48] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 12(4414499-1492, 2012.
[49] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4) -23688, 2013.
[50] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International conference on machine learning, pages 2260-2268. PMLR, 2020.
[51] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-77, 2011.
[52] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016. doi: 10.1109/CVPR.2216.999
[53] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
Contents
Introduction
1.1 Contributions
2 Related Works
3 Preliminaries
Normalized Error Feedback (|EF21]])
5 Normalized Error Feedback with Stochastic Gradients & Momentum (/EF21-SGGMM))
Experiments
6.1 Logistic Regression with a Nonconvex Regularizer
6.2 ResNer20 Training Over CIFAR-10
7 Conclusion and Future Works
A Lemmas
14
13

---

B Convergence Proof for ||EF21| (Theorem 1)
17
B.1 Proof of Theorem
18
C Discussion on Theorem 1
19
Convergence of ||EF21]| for a Single-node Case
20
E Convergence of
||EF21-SGDM] ||a
(Theorem 2)
21
E.1 Auxiliary Lemmas
E.2 Proof of Theorem 2
26
Extension to Strongly Convex and Convex Problems
30
G Additional Experimental Results
31
G.1 Minimization of Nonconvex Polynomial Functions
G.2 ResNer20 Training over CIFAR-10
32
H Omitted Proof for Smoothness Parameters of Logistic Regression
34
A
Lemmas
In this section, we introduce useful lemmas for our analysis. Lemmas and 2 introduce inequalities by generalized smoothness, while Lemmas 3 and 4 present the descent inequality and convergence rate, respectively, when the normalized gradient descent update is applied.
Lemma 1.
Let each fa(x) be generalized smooth with parameters Lo, L1 > 0, and lower bounded by fint and let f(z) = 1 Σ f((x). Then, for any y E Rd
[V - Vf((v))l - (Lo + L V. II) exp (La ||x- - yll) || - vll, fi()) S f((x) + (Vf((z),)) x) To La [1))]]
(6)
exp (I1 || - vll) lly x01
(7)
4(L. 4 (+) f(((z) pinf and
(8)
f()) < f(x) + (VI(z).y x) + Lo La E [V]((>]
exp (L, ||x - y/l) lly x1| (9)
2
Proof. The first and second statements are derived in Chen et al. [16, Proposition 3.2]. Next, the third inequality follows from [38, Lemma 2.2]. Finally, averaging (7) for 1,..., and taking into account that fz)) = Σ
1 f((x), we get (9).
Lemma Let f((x) be generalized smooth with parameters Lo, L1 >> and lower bounded by fint and let (xx be lower bounded by fini. Then, for any Rd
8L,
Σ [Vf((x)I 8L)(((2) fiml) T
(fiut
f!ul)) + Lo L1.
(10)
Proof. By the (Lo, L1) smoothnesss of f((x).
A(f((x) - fint) (8)
[x)]
if (VA(a)) +
2
2L
Lo + L, f(((ll
otherwise.
2L

---

This condition implies
(fx()L)(f((z) Sinl) Lo/ L1) L1)
I (L)(f(()) - si + Lo/ L1
- 8L)(fi(2) - ppint) + 881 -:aut) + Lo/Li L1.
Finally, by the fact that ((x) = E==
[V[(')] s (L)((())) - -pmn) + 811 ginf f(ml)+ + Io/I1.
n
Lemma 3. Let f(x) = 1 - li(x), where each Jı(x) is generalized smooth with parameters Lo, L1 > O. Let xk+1 x² |1021 th for 7/ > O. Then,
1(aht1) I 5(x²) yh [V |||
+ 27k Vf((=)) - =01l
2h exp (mxta) +
Lo + L Σ [[
Proof. Let each fi(x)) be generalized smooth with Lo, L1 > 0, and f(x) = 1. Ei fi(x). By of
Lemma 1, and by the fact that ++1
= x²
24 2 for "ik > 0.
f(abt)) s 1(a²)
ot + 2kk (x)()x11)
Lo L Σ V }l
| I
f(x²)
fx*²) - -tt (,,) mh ||
|
I V [
exp(1xl1))
Lo +
2
i=1
ʃ(x²) + 7h [/(xtt)
7k ||0||| - **1|
the exp((x(4)
L [
Lo
where we reach the last inequality by Cauchy- ineuuuaaantitttltttt.......
inequality. Next, since
||0|1| triangle ineq.
-|V ||Vf(*** =*11
we get
((xh11) S s(x - 7h || + 27t [ - x/1
+ 28
Lo 4 Σ ((
2 exp()nli)
Lemma 4. Let 1k20, ( [V*1k20,
Jazu be non-negative sequences satisfying vh s (1 by exp(L17)72) b ba exp(Li
for bi, by 0. Then,
0 exp((b
1)) exp(Lin)7 bz
by
min Wh < k=
+
b27(K (K 1)
15

---

Proof. Define 3x=
Dk-1 1+b exp(L1)) for k = 0, o... and B-1 = 1. Then, we can show that
Bk = (1+b) exp(L1))72)611
for = 0, 0.l...., and that
(1 + b1 exp(L17)79)& - b + by exp((11))22
= 8k-1 1V b273% Wh + by exp(L17)7 BR.
Therefore,
min W k=0,1...,KK
Σ Br W
Σ 3k k=0
Σ E (Bk V Bx 1k
by exp(Lin)) 62
b2y k== 8k
8-1Vo .xx Vk++1
bs
exp(L1n)7 b2
b2y k== Bx
By the fact that B-1 1, 3K > and ph+1
0,
V
by exp(L17) b2
min
W
O=
b2 >
k
8k
Next, since
K
K ++
Ba 2 (K +
k=0.1
min
3x =
(1 + by exp(I1n)72)K41
k=
we have
v + b exp( exp(L1n)7))K++
by + exp(L1n)) b2
min
W
Jem0,
boy(K + 1) 0 exp(( exp( ( + 1))
1+xSexp(a) S
+ by exp(I1r)77
by + 1)
b2
16

---

B Convergence Proof for ||EF21|| (Theorem 1)
In this section, derive the convergence rate results of ||EF21|]. We start with the following lemma technical lemma.
5. 5. Let Assumptions and 4 hold. Then, the iterates {a*) generated by ||EF21]| (Algorithm I) satisfy
B Vf(x=+1)) - +11]
v1 aE - gfll]
+ - a wxppp111111101 [
(11)
Proof. From the definition of the Euclidean norm, and by taking the expectation conditioned on xxt ++ .9, and by the update of of from Algorithm
E | fi (x g x**1,,+0000 g
= [ V Vf(( k+1 - g.t - - (V.i(cht))) 5. |ll x ,
E [ii(ttt11 of C(VSi(x++1) of }l( 1ott1
where we use the concavity of the square root function, and Jensen's 's inequality for the concave function, i.e., E [x))]] f(E [x]) if f(x) is concave. By the a-contractive property of compressors in (3), by the fact that triangle inequality, we have
ofll is constant conditioned on x**1 9 and then by the
V (1--)) aE [ - 1/112 sk+1
V1 V (x -o,'1
S v1- V(((=*) - rf + v VJ (z vs((
By the generalized smoothness of fi()) in (2), and by the fact that n.+11 x - 7tk g"
g
E fl 9; ++1
/ - r.¹l
+V1 aL L1 / |[ (xx(a=))))xx(((naee exp(Lrnx)
Let 7t > 0 be constants conditioned on ++1 .g.h Then, by the tower property, i.e.,
E (x**+++))
+ E E Vf(2+*t) + - -
we have
E [[
+1
aE V If
+V1 a (1 L [I
This concludes the proof.
Next, we present the following descent lemma for ||EF21|].
Lemma 6. Let Assumptions 1-4 hold. Then, the iterates {a*} generated by ||EF21]| (Algorithm 1) satisfy
E [vkt]] E [vk]
ta Σ
E
I|] E [ [f +an
where V f(xa) piul
27
Σ
[ 0111 and c 4/ 2 -ل-ي for
1-
1-v1-
V1-ai
=.
17

---

Proof. For brevity, let A&
Then, we have V
f(x²) fint
Au -i=1 [(((=)) o. and from Lemma 3, we derive
E [ 1 E [f((²) 8ud
E ff(=)))
V ||I + +ep(Lin))) 20
Lo
+ +exp(L17x)11
2m
2
+ E V |ا + Ak+1 VI
9f +
Identities vf(x²) = ビー (((***) and De - of and the triangle inequality imply
E [vkt]]] 1 E [f((x)) - fini] 7x E [1] V
1,
To E [/>\>> ||| + exp(IInk) 2
+ +exp(I1174 )
2n
+2
1
E Vf((("))) - r1 AR+1
E (ff((**1)))) k+1
9, k+ I|]
1=1
1=1
Next, we apply (1I):
The + A A or1s)
E [[
S E [ff(x*) - [ - 7
+
exp(LI
2
2k 2
+
+ AA441i1 10-ivi-aa anis
exp(LInX)
L1
11
+ (2 + AR41VI
E [[V
Ti
If Ag
2yh and y) satisfies 7 Ykk then
VT
2% A S 27 + A a As.
Therefore.
E [ I
E [V + cj exp((L
E Vf(
E [[ + c exp(L
where c, bi + 2 2TTTaly
for i 0,1.
I-VI-a
B.1 Proof of Theorem
Now, we are ready to prove Theorem 1. From Lemma 6 and 2, and by the fact that ci Lo/ 11 co.
we have
E [ < E [ + exp4 [f(*)) pint
E Vf(=**) ||| + B expp(I
8cy Li where B 200
2imi (fint ). Using the fact that f(x*) - fiul S Vk, we derive
n
E [ s (1 8c, L exp ( ))))) [v*] E [|| (= 111 + cxxp(L17k)t
Applying Lemma 4 with V |v / ||| ||]. by Sc, by = 1, and by B. we get
W v exp(bne exp(L17)) + 1)) +1))
ba exp(Lin)7 bz
min k=
+
b2r(K +
Finally, if with To > 0, then exp( (1) I exp(LLnoo) and thus by 70 exp(Li
70
VK+I
v exx((b exp L1 (L1 )n))
min
W <
k=0,I..,,KK
b2 K +
bz VK+1
18

---

C Discussion on Theorem
In this section, we compare the convergence bound between ||E221| and EF21 under traditional smoothness. For nonconvex, traditional smooth problems, ||EF21|| from Theorem I with L1 0 achieves the same ((1/VK) rate in the expectation of gradient norms as EF21 analyzed by Richtárik
al. [8]. but with larger convergence factor. We prove this by assuming Vf((=") = 9 for all i.
That is, Theorem with Lo L, L1 = 0, To V(f(=")- (2bb, and
L + VL
1-vI-o
implies that [F achieves
1
f(x)) finf
min E vf(**)]
+26%
k=
K
+
70
(1 + (1+3V1
a) + v1 -a)
[(x9) fint
21 L
a
K+1
T. [xx) fint
1v2
K+1
On the other hand, EF21 attains from Theorem of [8] with L, = L== (i.e., fi(x) has the same smoothness constant as f(x)), and & being chosen from the iterates x²", x," x uniformly at random
E (x k=0.1....KK
min
E [
|
E
[
22 + /B10) f(x0) - fint
K k+1
VB1052/a-1
2v 2/a
L f(x²) fine
W
K K+1
In conclusion, the convergence bound of ||EF21] is slower by a factor of 2 than the original EF21 for nonconvex, L-smooth problems.
19

---

D Convergence of ||EF21|| for a Single-node Case
In this section, we provide the convergence of ||EF21|] for a single-node case. In particular, the algorithm enjoys the (1) convergence up to the error of 1-c "x))) In contrast to Theorem for mudti-node ||EF21||, the next result for single-node ||EF21] applies for any 7 7 (0, (0.c)))))) with 3 2 2,
I I-vi-a' and a E (0, 1].
Theorem Lel Assumptions 1-4 hold. Then, the iterates {x*) generated by ||EF21| (Algorithm 1)
with 1, 7k (B(c) and 2 2 satisfy
E V E VKK1]
min K= [[] I|] S 7(1 o exp (17))())))(( +K)) 11 exp [1>))²'
COT
where V f(x²)) pint + i-vi-a [f(x*)) - 1 and ei
L, vI-al, for = 1.
2 I-vII-
Proof. In the single-node case, Lemma implies
E [|l - gh+
< VI- VI-abi aE ( -
+ exp L (H (Lo + L1 [[ (12)
Next, for brevity, let As I-V1-a Then, we have yk = f(z²) finl
A Ei=1
[f((t** of and from Lemma derive
E [f(at)) - pinl - (TH n1
REL1 exp(Linu) E ((]l) []]
R2LO
E [
exp(Linm)
2
2
+ ||| ||x*) - -l"ll| + + E [|| |1]
(12) s
E [f((t*) | + (2 + A [ 1
Tn
Yk
exp(LInn) ALtIVI- al1?% (p((L)))))))))))))))))))(()))( E (f
2
n Lo
exp(L17/a) + - alonee
2
If A
2%h and 7k satisfies 7++1 S nk. then 1-VI-a
27 + AK+1 v1 S 2 + A - aa= Ak-
Therefore,
E [ < E [v*] - (Th
E [f(( co exp((rmm)))
where = 11 + 2 /I-al for i = 0, 1.
Finally, taking 7% 7 1/(80)) for B > 2, we get ei exp(L17) exp(Ln/(8os))// < exp(2/8)/3 < 0.7 < 1, and
[ < -[v*]-<(1 B
+ coo
Rearranging the terms, we derive
K
min E Vf(*)|
<
Σ E ( |||
K
K K+1
k=0
E V
E KK+
COT
+1) +
(1 ci exp
1- exp((1)))
Noticing that // 2 0, we complete the proof.
20

---

E Convergence of ||EF21-SGDMI] (Theorem 2)
In this section, derive the convergence rate results of ||EF21-SGDM]] We first introduce auxiliary lemmas in Section E. and later prove the convergence theorem (Theorem 2) in Section E.2.
E.1 Auxiliary Lemmas
Now, we provide useful lemmas for analyzing ||EF21-SGDMM First, Lemma 7 shows the descent inequality of the normalized gradient descent update under Assumption 3 (generalized smoothness of fi). Second, Lemmas and provide the upper-bound bound of the Euclidean distance between off and g and of the Euclidean distance between of and V fi("", respectively.
Lemma Consider the iterates {a"} generated by Algorithm 2. If Assumption holds, then for any 7k > 7, E [0,
f(xht1)
1 f(x²) 7h
[V + n7 Vs(x*) rl1| 27k l|ut - ge1l
+ +o exp(mxLi) + 4L77% exp(>x (f(x*) - pant)
4Li7 L1) n
n print -(aat-
Proof. Applying the triangle inequality in Lemma 3, i.e. [|V - g²1l s |[v - |/ 1011. we get
f(aht1)
s
f(x²) -87-- Th
[f(a*>||
+ 27M | -011| 27x 1|00 g/1l
2 2
Lo + L1 n Σ [[
exp (mnl))
(10)
f(x²) - yh [f ||| + 27t |f((tt - + + 27x 1/ - gell
+ + exp(>x< L1) + 4L771 exp(Tx L1) (f(x*) )
4L722 (xp()x<11
Σ (pint -
which concludes the proof.
Lemma 8. Consider the iterates {a*} generated by Algorithm 2. If Assumptions 3, 4, and 5 hold, then for "Yk > O, mı E [0, 11, and k 2 O,
n E 1| o 111 + VI atk+1
9; *+1
o f.
n
1=1
+ V1
017 / exp (7/ I1) E. [f(x*) p
8L?
off V exp (1) (pial f(ull)
+
n
+2L v ont +1 1 exp (7x b1) + v1 07/ 10.
21

---

Proof. Taking conditional expectation with fixed Fb-1 - f _x++1 - }. using the concavity of the squared root of the function, and applying the definition of of in Algorithm 2, we have
E
[[[|ut+ 11tt+11
Di 0
E
luftl
1/+1 Fatt
|0 g C (o,t1 gt) 112
Fatz
(8)
(1 a)) 11o, - g F
Next, let 7/-- = > 0, and 77 = n E [o, 1]. By the fact that of k+1 9 are constants being conditioned on Fk+1, and by the triangle inequality,
[[|o 1
9 +
FR+1]
<
vI vI-a |o
9 vI al rf
= a1-a|lo² 9 + /1 - am1+1 V (f - of
Here, the equality comes from the definition of of of in Algorithm Next, by the triangle inequality,
[[|o] M++
9r g 11+1 Fx+1]
$
vI- 11
9 || + VI ame+1 /l0 V
+v 1 07//+11 V/i(a*) - [[i(o++1)]]
+v 1 017++11
[ft ( [f(aatt]]]
vI
o. + vI -1-0m141111
amm+11110 ||0 vf((2*))|
+V1 0m76+1 Lo + L1 [+((<>)]]) exp (L1 || 201)) | - x²
+ 1 07f
V { + [/(a+tt]]|-
Next, using x+1 2* -7 T
xt and taking the expectation, we obtain
E [ K-1
g, *1+
<
VI- aE [| I1 + vI a [||o v.fi+>)]ll
+V1 onn exp I1) (Lo + LE [//
+VI 1 (z , - (x
Finally, since
E V/i (1 - ||]
5
vB E
(1 [i(++t1)11
WW
6,
22

---

we derive
v1
B
k++
5
E [llop r.'1]]
1=1
+1]
E |||o
V vfi(z*))
11
1=1
+v1 007 +1 exp (7tt1)
Lo + 41 - E EIl
1 007++100
(10)
v1
E || - r.1l
n1
v1 am]
n E o|lot ff((t*))
n
+813 0T 7k exp (Y's L1) E [f(**) - piml]
817 a7]k+ / exp (7h. [1)
Σ piint f
n
+2L 00] 7a exp (r + vI 0011-10.
This concludes the proof.
Lemma Consider the iterates {-²} generated by Algorithm If Assumptions 3, and hold, then for any "A = > 0, n, and l 2 0,
Vna
2o exp
E []][a* [>(>>))]] s - ")= _1|00
vn
h-1
exp
(1 >F [s(e)) pimet
8137exp(711)
pinn - -(ul)
(13)
1772
addition, for any l: 2 O.
1 ΣE k+1 -filtttt)l
1 -
Σ
E 1| Vf((=*)]] + no + 20 exp (rL1)
+8L exp(pxp)) [ - piml]
81
Σ (fint -!int).
(14)
n
Proof. We prove the result using the arguments similar to those given in the proof of Theorem 1 from Cutkosky and Mehta [50]. From the definition of oi+1, we have the following recursion for any
k
o k+1
(1 n) + V/ [/
Vfl(attl) + (1- () vf(x²)) + (1 (1-(\))) - v.((a++1))
(. (1 - ()((t+))).
Next, from the recursion of ,+1 obtain the following recursion for k: 2
H (1 (1-7)H + (1 (1- (1- + n
(15)
23

---

where U -Vfi(ttt1 :ttt)) Vii(att)), G = Vf((z*) V.i(athl), = vr vf((z')
Uktt1 1 Eoft o o==
1 Σ c and H¹ 1 Σ H
==1
1=1
Unrolling the recursion for H,,,, we derive
-1- n) H + (1 7)
++1
G + Σ
(1 - 1) t
1=0
t=0
Averaging the above inequality, we get
H (1-n)*+1H² H
G + > (1-
f=0
1=0
Next, taking the Euclidean norm, using the triangle inequality, and then taking the expectation, we obtain
E H++
< (1 - 1))
E
1I
Σ (1 - n) - G||| ||
=
k
+n
Σ
(1
(16)
=
To bound E ||++++||]+ we need to bound the expectation of the last two terms. First, we bound term I 1
A1. Using the fact that |G*||
Em= ||] and the definition of G we obtain
a
A
++ E [f((tt) (fr
(0)
Lo exp (1) | - z'Il) ||_ -x'1
L1 [f((=')]| exp (L1 ||| - z'll) || - 2'1]
L
Σ
(1 m)
texp(rL)) +
m) 2 exp (714) E [|] V ft (z))l
=
iml 0m0
(10)
2007 exp (7L1)
Σ (1-1)) 8Li7 exp (7L1)
11- [f(xtt - p
1=0
8Liyexp (1L1)
1
&
- n) ++1 (fint s(uet)
n
1=0
<
2o7 exp (1
(1 7)² + +LL2 exp (7L1) E (1--m) B - fint]
1=0
1=
8Li7 exp (7L1)
8
pint
piuf)
- =1)
n
t=0
2 exoyexp(XLi) + 8L77 exp (7L1)
k
(1 - x [f(x') pin[]
"
1=0
m 8L exp (7
pint - pimt- pdul)
1p7
24

---

Next, we bound term A2. Jensen's 's inequality and the tower property of the conditional expectation imply
A S
E
Σ 1=
(1-
U
Σ
(1
2))
DE
[1
Moreover, due to independence of [4)]== we have
k
7)
2(k
(1)
Σ (1 2)) o²
A2 I
E
n2
t=
8
nejo.11
Σ
(1
1))
v Vnn(2 7
mm
(=0
Therefore, plugging the derived upper-bounds for A1. and for A2 into (16), we obtain
2 exp (Tl1)
E
I|]
s 11-1)
k+ E 1 []] +
7
+8177 exp (7(1)
(1 - ++ E [f(x²) - pint]
(fint finf) + Vio
+
7m
vn
which is equivalent to (13).
To derive (14), we make a step back to the recursion from (15), which implies
n
17
B
n
n
.1
(17)
Next, we derive the upper bounds for Bi and B2. For Bi, we have
1
B1
E fz(* vf((aa+)))
(6)
1
S
E (Lo- L1 || ||) exp (L1 1|0a - x(t1ll) ||ae - x+1
n
(1 - exp(\bb)
n)
E V+
n
(10)
S 2(1 17) Lo? exp(y + 8(1 - 1) ex [f( - pimd]
8(1 7) exp(7Ta)
n
Σ (fint -fnnt-
+
n
and for B2, obtain
77 n
(s (4)
B2
V t1, -
no.
n
25

---

Plugging the derived upper bounds for B1 and Bg into (17) and using 1 - S 1, we get
1
<
1 7
E
|1 + 2007 (x)
n
18 [ - pim(]
8137
(rint - 1 + nj,
n
which is equivalent to (14).
E.2 Proof of Theorem 2
Now, we are ready to prove Theorem 2. For convenience, we introduce new notation:
8* =f(a()>) fiul]
A = 1 n
E Il
B& B=:=E[llot [=
C2 =
ginf :=
1 n
Σ (fint f!lnt.
Using the new notation and noticing that E [[|u* - g01l] S Ag. we rewrite the results of Lemmas 7, 8, and 9 as
g++1
S (1+ exp(L exxp(()))) 8h + + + By EE [I[
(xp(x)( (Lo 1
Ax+1
S VI- aA + I aCk + &LL am7y exp (7L1) 8*
+2v1 - an exp (T LL + 4L300m) + vI - cmjo
v/a
27 exp (L17)
Bx S (1 - 1)* Bu +
+
(Lo + 4L230m²)
VV
"
k-1
+8L37ex exp (Lm))
Σ
(1 -
1=0
C++11 < 11 + 8L7 exp (L17) 8* + to + 27 2xexp(77)))) (7L1) (Lo + 41138"n).
Moreover, since 7 = (K (K+1)%4 with 70 S 2
76
we have exp (Im)) S exppl11n0 S 2 and the above
inequalities can be further simplified as
gk+1 < 8LT7)) 8 + AyA + BB E V
II] +2 (Lo + 4L7 (18)
AK+1 S V1 - aA + uV' aO' + 161. 0
+4V1 anyy (Lo + -L7g + v1 - amjo,
(19)
k- 1
Bo + vioo B₁ < - Bo
+ 4% (Lo + 4L78lnt) + 16 Vā
(1 1) k-8
(20)
1
1=0
Ck+1 < (1- (1-n) + 16 no + 47 (Lo + 4L38hnt).
(21)
Next, we introduce the Lyapunov function V22 defined for any h 2 as
V/= = 8 + aA + cC2,
27 where a:= I-VI-a and c:= c== a. Then, using (18), (19), (21), we get
Ve+1 5 (1+817?? 8* + 2y + By > [I] [ ||] + 27² (Lo + 4L30
+o (V1 - aA + n/1 - aC* + 16L, /1 - -1a
+a (4v1 - (To + (l)) + vT - x
+c +c1(1 1) + , + + 47 (Lo 4L23o'())
26

---

To proceed, we rearrange the terms:
(1 8T777 + +16a1]v - -any + 1161177) 8 + (2- + vI - aA
vi-
Ve+1
anvi-a + +1-1) cC + +, - b | ||
+
C
+ (27² +av11 - anyy + 407) (Lo + + +
aato-
US1
(1+81772 + +32aL2 1 1 8h ( + vI a aA + c0
a
+2yBA - BB [[(x=)
+ +2272 -8vi1 ar) (Lo + 4L30'n)) 2nay 1 a0.
Since a
27 1-vI-a'
we have 27 + VI- and
64L772VI-a a
VA-1 1 1+88777 +
8t +a + cCC +2 >F (+>>
1 - v1 a
27² + 1 1
(Lo (L0+4L388mn) + 4
1 v1
-1-a
64T,772
1 + 1 v1
Via + By - 7 [[]
167 (Lo + (
4/1111 - 00
VI
VT-a
Next, we bound B3 using (20) and 8 < Vy:
641772
k-1
VE+I S
1
Ve + 72T,
(1 1) k +
-V 2y((1 - -n)* Bo 7F [1] V
vI
1=
16
872) 17
1- v1 -1-a + 27
4 a
+
(Lo + 41Z +
vI a
Vn
Summing up the above inequality with weights Br := 1 641270²
I-VI-a + 3212g²
-(k+1)
for k
O,..., K and denoting SK := Ek 3x and B-1 == 1, we get
K
K
64L7>2
K
k-1
34 Va+1
<
Σ
1 + 1- v1
Be Vi + 32L?>2
Σ Σ (1 - m) k'1
k=
k=0
k=0
(=0
2-y Bu
11 7)** By
Σ
B&E V
fz ||]
k=0
16
822
4 27
+SK
+
(Lo + 4L78
+ Sk
1-v1- +
a.
vI
1
Vn
27

---

By definition of Bk, we have 3₁ S - and, in particular, B& S for all h 2 0. Using these inequalities, we continue the derivation as follows:
K
k
64
K k-1
V
1 1
B&VE + 32
(1 - -
1-
v1
R=
k=0
k= t=
K
2 Bu
(1 7))*
7
B& [|| vf(x*)) ||
k=
k=0
16y²
+ 8722
44m/I- 2
SK
(Lo + 4L20
+S 1- 11v +
v1
11
vn
K
64L
K
<
+
V& + 32L??²
Σ (1-n)) m)
Σ Bk
1 v1
k=0
1=0
k=0
+2y Bu
Σ (1 11)* - 7SK
min
[[[[[((>*)
O K
k=0
16
872
[4/ -
27
-SK
+
(To + AT.70imtt
+ SK
1-v1- +
v1 a
17
vn
64L 2
3217722
2yBo
1 1
3x V/
-YSK min E. [||>/>>>)]] k=D....
1
a
1
"
k=0
-P
16
sx2) (Lo + ALFOlul) + Sk
44m/11
2
+Sk
1- vI + 17
+
vn a.
1- vI 1-vI-a
Rearranging the terms and dividing both sides of the above inequality by SSk, we obtain
K
2Bo
min E (f
||]
(B
- B& Vx+11) +
km D...... K
SSK
S)
km0
16y
87
(Lo 44T,08mtt + -LTVT-a + 2V7
11-1a -
1 v1 - a
vn
Vo
+ 2Bo
167
+ 88
s
+
(Lo 4L78iuf)
S
S
v1
aa
4ny1
2
o,
(22)
VI
Vn
where in the last inequality we use VK+1 2 and 3-1 = 1. Next, we estimate Sk:
K
K +1
SK
=
Σ
3
2 (K + 1)3x =
(1
64L772 I-v1-a
+ 32L7?2
K+1
k=0
"1
K +1
M
(23)
(K+1)
32L7TP(K-1)
exp
1-vI-a
71
Since = (K+1) and =
(K+1)334 with To S 162, min ((K + 1) - -1- 0),, 1}. we (4+3)*(K+1] < 7. Plugging these inequalities into (23), we get
70
(K+)) < and
have
1-vI-a
SK 2 (K (K+1)/expt 11/xpp(/1/2) 2 (K+1) Using this lower bound for Sk and r7 (K+1) 7 (K+1)%
2 in
28

---

(22), we get
2Vo
4Bp
min E [[(**)]] k= k
70(K + 1)14
(K + 1)
16%
8%
(Lo + 4L30
+
v1 o + 1)
(K (K+1)
4vI-a
2
v1 - (K(K + 1142
VT(( 1)
For the convenience, we define Ca == 1 v1 a a. Then, by definition of Vo, we have
2Vo
28
2Ao
Co)o
70(K + 15 + (K(K+))
1o(K + 1)44
Co(K
Moreover, since 9, =0 0 and u/ = (a. 5d) for all -1, 1...., with independent {<)) /i=1 have of Vi( ) and 50 = (V ) for all i= 1,..., n and
Ao =
(.. C* (VAA(
n
(3)
vA(a'|| (4) / C.)o,
E
1
(4)
Cu =
V
Bu =
E
(x 9 v)AD))
1
(4)
E
Vfii..:
2 vn
n²
Using these incqualities, we get
280
2Ap
2(1 - Co +
4Bo
min
E
+
K
oo(K 1)
Ca(K +1)
Ca(K +1]
(K + 1)
16%
8%0
(Lo + 4L7giutt)
CC,(K + 1)9
+
(K+1)
(K
4(1 - Ca)o
20
C.(K 1)
Vū(K + 1)1/
280
4(1 - 4(1-Ca)o
40
+
7oK + 1)
C. +1)
Vn(( + 1)4/2
16%
8%0
(Lo 41238int)
+
Ca(K + +1%%
(K (K+1)
4(1 - Ca)a
2a
Ca(K 1)
vn(K + 1)
280
16%
870
) (Lu 4L33int)
+
mo( + 111/
Ca(K + 1)%
(K + 1744
8(1 - Ca)o
60
Ca(K 1)
vī(K + 1)14''
which concludes the proof since
1-Ca Co
< 2vI-a and
1 < Co
29

---

Extension to Strongly Convex and Convex Problems
Our current analysis for ||EF21]| and ||EF21-SGDMJJ, which are initially developed for minimizing non-convex functions, can be extended to strongly convex and convex functions.
Strongly convex problems. We can extend the convergence for ||EF21|] and ||EF21-SGDMI] to minimize strongly convex functions. Applying the p-strong convexity condition of the function f. i.c. | 2 2p(s(x")- - f(x))) where arg min fxx), into the convergence bounds in Theorems and yields the convergence results in min 0,1 I...... K E Vf((**) f(x)) However, these results do not imply the standard exponential convergence typically expected in strongly convex problems. This theoretical gap suggests need for new analytical techniques, which involves tighter Lyapunov functions more refined descent inequalities tailored strongly convex functions.
Convex problems. We can extend the convergence for minimizing convex functions. This can be achieved by assuming that there exists the iterates {x*] } satisfying || - x²1 S. R for some R >> 0. Hence, the convexity the function f implies that
f(x²) - f(x)) < V || - -=11| S |||\|(>>|||
Applying the above inequality to Theorems and 2 yields the convergence bounds in I..... E [f(**) f(x))].
30

---

G Additional Experimental Results
In this section, we provide additional results for minimizing nonconvex polynomial functions, and for training the ResNet-20 model over the CIFAR-10 dataset.
G.1 Minimization of Nonconvex Polynomial Functions
We ran ||F22|| ||
and EF21 in single-node setting (n 1) for solving the following problem:
min EER
f(x) : a
(24)
(g((a)
where >
0.
Let us show that f(x) is non-convex (for the specific choice of a:) and (Lo, Lm)-shooth. First, prove that ((x) is non-convex. Indeed,
f(x) = v² g(x) + ((x)
3x
- 3x (1 + x2)) 3
12 diag {a x (xaa) + 2X diag
(1 + x7)
not positive definite matrix if we choose a;
24 4z = +1 for = 1,....d.
A
Second, find Lo, 11 0 such that
V f(x) S Lo L, (v)(,)), Vo Rd.
This condition is equivalent to Assumption (generalized smoothness) with Lo L1 [16, Theorem 1]. Let us fix some L > and choose Lo
9Ad
2X. Since (2h(x) x 2XI,
213
2 f(=) g(x) vhh(2) - [ <>)(>>]
- 12 afat + +.. az +
< 12 (010) +
+ + + 2X.
Also, notice that
|Vf(z)]| = (z) + vh(=)]1
- [101o
2X
2
x + (4adx] +
2A
2
x²
(1+ x??
(1 + x2²²
1/
a7 + ... + 22
4 01 |21| 3 +.... as |zal²)
Vd
where (+) results from the fact that ||=||,
S /d
|||||| for x E Rdd Our goal is to show that
12 (aja) + +... axx3)= Lo
4L
(a) |11] + +... + aa aall")) Lo Lo 2d.
Vd
To show this, we consider two cases: if |x;|
3vd L,
and otherwise.
If |xa| < 3vd for all i = I,...,d, d, then 120;0 Li
108a,d 1,
Thus, (ajzî +... + axa)) S
1082d2
241 T..
2. If [z) >
Va a |æy1 and the sum of the remaining terms (such that |z;|| 3y4 in 12 (alD) +... axxz) can be upper bounded
3/d for some j = 1,...,d, d, then 12ay23 <
4hg
by Lo-
31

---

In conclusion, f() is (Lo, L -smoohh, where L1 is any positive constant and Lo 2dd 221
+ 2X.
Additionally, we can show that under certain additional constraints, f(z) L-smooth with AvaD² 2 If x I D for all -,.... d, then
2
f(z) - 1 + a. + +2 5 AvdD²
+ 21 = L,
In the experiments, we estimate based on the initial point x. R
In the following experiments, we used a top-k sparsifier with k = and a = k/d, setting d = 4, L1 {1,4,8) 8), and Lo = 4 (adjusting À maintain constant Lg). The initial values x were drawn from a normal distribution, 2 ~ N (20,, 1) for i I,..., d, with D estimated as 20. For EF21, we using = L-LVT
set 7/s
1 a and I-VI-a' according to Theorem of [8]. For
||EF21||, chose * 2c with e L Vl- from Theorem 3, and % 70 0, specified in Theorem with 1.
with
vK+
The impact of "lo and K on the convergence of ||F22]]. First, we investigate the impact of Yu and K on the convergence of ||EF21|]. We evaluated "/o from the set {0.1, 10), and plotted the histogram representing the number of iterations required achieve the target accuracy of || fz)]] = 10-4, using the stepsize rule = VK+I For each Yo. we determined K as the minimum number of iterations required to achieve the desired accuracy, found through grid search with step sizes of 500 for "o = 1, 10 and 5000 for to 0.1. From Figure 4, for small values of yo, such as
with
20
Number of itterations for convergence
0.1
10
No
Yo
10
10²
4,4444-1
Lg Lg-4,41-4
L,4,L,=8
Figure 4: Number of iterations required to achieve the desired accuracy, [+x))]] <E 10-4 for different values of Ly and L1. VK+I
using ||EF21]| with
0.1, significantly more iterations required to reach convergence compared to % values of 1 and 10, which show similar performance (with the exception of the Lo = 4, L1 = case, where " = 10 converges faster). Based this observation, we 7o in all subsequent experiments and adjust only to achieve convergence, identifying the minimum number of iterations needed to reach the target accuracy through grid search with step size of 500.
Comparisons between EF21 and ||E22/]]- Next, we evaluate the performance of EF21 and ||F21]] for a fixed Lo = and varying L1 values of {1, 4, 8). From Figure 1, ||EF21]], regardless of the chosen stepsize y, achieves the desired accuracy [|v < with 10 faster than EF21. Initially, however, EF21 converges more quickly, likely because ||EF21|| employs normalized gradients, which can be slower the start due to the large gradients when the initial point is far from the stationary point. Moreover, as L, increases, both methods show slower convergence.
G.2 ResNet20 Training over CIFAR-10
We included additional experimental results from running EF21 and ||EF21|| for training the ResNer20 model over the CIFAR-I0 dataset. The parameter details were set to be the same as those in Section 6.2, with the exception that we vary & 0.01d, 0.5d for top-k sparsifier. From Figures and 6, [|EF21|] attains a higher accuracy improvement than EF21, across different sparsification levels k.
32

---

Figure 5: ResNer20 training CIFAR-10 by using EF21 and ||EF21] under the same stepsize
and h 0.01d for top-k sparsifier.
Figure 6: ResNet20 training CIFAR-10 by using EF21 and ||EF21] under the same stepsize
and = 0.05d for top-k sparsifier.
33

---

H Omitted Proof for Smoothness Parameters of Logistic Regression
In this section, we prove the generalized smoothness parameters Lo, L1 for logistic regression problems with nonconvex regularizer, which are the following problems
min xE
f(x)
1 71
f((z)
Σ
log(1 +
2))
j=1
where a, Fd is the 8th feature vector of matrix A with its class label b, E {-1,1}, 0.
First, prove that f() is L-smooth with L + |||l + 2X, and that each f((z) is L--smooth with f. i||a;1| + 22.
Next, we show that each fi(z) is generalized smooth with Lo = 2X + Av max; ||s and Lı max; ||sl],, when the Hessian exists. By the fact that
exp(-b,a) r) Vi(() 1 + expp-bbaa x)
exp(-b,af x)
(1 + exp( x)) ba bias, and v²j(()==
we have
(babbbaaf - (max()
v2 f100
(1 (1+ex) exp( b.at )²)
exp( -b:a x))
||a11
(1 + exp( b, x))
||a|||
Vf((z))
+ exp( -baaaaaa
|| [+
(25)
After adding the nonconvex regularizer h(r), we can show the following inequalities:
+ +||>><<>||
< (1) || +22,
(26)
and
2Ax
2
2λxa
2
[[f(())] 2
= vF(Tt)
+...+ +
(1 + x?)²
(1 (1+23)²
vi(2z)
x2 + + X2
V
Avd.
(27)
By combining inequalities (25), (26), and (27), we obtain
||>]|( <
v2 j(x))
+ 2A
V
||د||| (x) + 22
2 | ||)
In conclusion, [+x)]| < Lo + L, [ with La < 2X + Avd|aa and L, S ||ai]]. This
condition equivalent Assumption 3 (generalized smoothness) with Lo, Li [16, Theorem 1].
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We develop error feedback algorithms that attain the first convergence guar- antees under generalized smoothness, suitable for deep neural networks. Unlike existing works, we do not assume unrealistically strong assumptions for distributed settings. These claims are stated explicitly in the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our results are limited to constant step sizes. In the conclusion, we identify these as limitations and propose promising future research directions, including extending our algorithms to incorporate decreasing or adaptive stepsizes.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
35

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions used in this work are detailed in the Preliminaries section. Complete proofs for all theorems and corollaries are provided the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details of the experimental setups were provided, encompassing the neural network models employed, the datasets utilized, the partitioning of data into training and validation sets, the specific hyperparameters chosen, and the computational infrastructure used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
36

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The data and model sources open and cited. We provide necessary details for reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cc
public/ Coleeee/soSSSSmmsiiiic..
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so Et is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nips. www.ccpwlcgggccccccoccooooooocce gwtge//ieee//e// SolodeSubmissionPooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details regarding training and testing procedures, including data splits and hyperparameter settings, are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not reported because would be too computationally expensive run all the experiments multiple times.
Guidelines:
37

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Our experiments (1) minimizing simple functions and logistic functions, and on (2) ResNet20 training can be run on machine with single GPU.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: : http///eurrrp.eeeee//eee/e cc httpppllcc/thhccchieeeeeeeee
Answer: [Yes]
Justification: The contribution of this paper is to provide the first convergence guarantee of eтror feedback algorithms for problems under generalized smoothness for deep neu- ral network training. We ensure full reproducibility and fair comparisons by providing comprehensive experimental details in the appendix.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
38

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This paper introduces distributed error feedback methods for training deep neural networks. These methods utilize normalization stabilize convergence under generalized smoothness conditions, which effectively model the challenges of neural network training. Crucially, they maintain the convergence rates of their standard smoothness counterparts without requiring unrealistic assumptions, such as bounded data heterogeneity or smoothness dependent stepsize restrictions (in the deterministic setting).
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: The data and models utilized in this work are publicly available, aligning with open-access principles.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
39

---

Answer: [Yes]
Justification: We acknowledge the sources of our datasets, the ResNet models, and the ResNet training implementation by citing the creators' respective publications. Furthermore, any modifications made to the software for our specific research investigation were done in accordance with the software's license and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does introduce entirely new datasets or models assets. Instead, we provide a detailed description of our novel algorithms, along with the specific datasets and model architectures used (which are publicly available). Our comprehensive implementation details should be sufficient for others to reproduce and modify our algorithms for implementation and testing.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
40

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy (https: http:ppps.ee/ooeeeeeenee/////220 for what should or should not be described.
41


Reviews:
[{"review_id": "F2YrE5FfYn", "reviewer": "Reviewer_Sp22", "summary": "**Contributions**:\n\n 1. Extends the results of Compressed Distributed Learning with Error Feedback (EF21)[1] to generalized smoothness, via normalization.\n2. The proposed algorithm does not require additional assumptions like bounded gradient, bounded heterogeneity.\n3. The proposed algorithm matches the convergence rate of EF21 with problem independent parameters (smoothness) which are generally unknown.\n4. They also propose a stochastic variant (||EF21SGDM||) under the bounded expected gradient variance assumption with matching rates as the previous work[2]\n\n[1] Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error\n333 feedback!\n[2] |Richtárik, Peter, Igor Sokolov, and Ilyas Fatkhullin. \"EF21: A new, simpler, theoretically better, and practically faster error feedback.\" _Advances in Neural Information Processing Systems_ 34 (2021): 4384-4396.|", "questions": "See weaknesses", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**:\n1. The paper is clearly written, with improvements with prior work clearly mentioned. \n2. Generalized smoothness is a much more relaxed condition and most FL works perform normalization/clipping and error feedback so this is an important analysis.\n3. Numerical experiments show the strength of the proposed algorithm over EF21.\n\n**Weaknesses/Questions**:\n1. The authors provide single-step Federated Learning / Distributed Learning algorithm. However, clients perform multiple local steps before pushing updates to the server. Can this analysis be extended to multiple local steps without the bounded heterogeneity assumption? \n2. This is not a weakness per se but a question, can the results be extended to strongly convex / convex losses / PL losses without a bounded gradient assumption  and achieve exponential convergence to the true minimum?", "was_revised": true, "final_justification": "All my concerns were answered by the reviewers.", "rebuttal": "We sincerely thank the reviewer for the positive and constructive feedback, and for recognizing the clarity of our presentation, the relevance of generalized smoothness in practical FL scenarios, and the empirical strength of our algorithms.\n\n\n> **Q1**: The authors provide a single-step Federated Learning / Distributed Learning algorithm. However, clients perform multiple local steps before pushing updates to the server. Can this analysis be extended to multiple local steps without the bounded heterogeneity assumption? \n\n**A1**: Thank you for this insightful question. We believe that our analysis can indeed be extended to incorporate multiple local steps **without requiring the bounded heterogeneity assumption**. \n\nTo illustrate this, consider the following modification of the normalized EF21 algorithm: \n\n1. Each client performs $T$ local gradient descent (local GD) steps using a fixed local stepsize $\\eta$ after receiving the global model $x^k$ at iteration $k$. \n\n\n2. Instead of communicating $\\mathcal{C}^k(\\nabla f_i(x^k) - g_i^{k-1})$, each client now transmits  $\\mathcal{C}^k(  \\frac{x^k - x_i^{k,T}}{\\eta} - g_i^{k-1})$, where $x_i^{k,T}$ denotes the local model after $T$ steps of local GD starting from $x^k$. \n\nThe primary change in the analysis occurs in **Lemma 5**, which bounds $\\mathbb{E}\\|\\| \\nabla f_i(x^{k+1})-g_i^{k+1} \\|\\|$. \n\nBy the definition of $g_i^{k+1}$, by the triangle inequality, and then by the tower property of the expectation, we derive: \n\n$$\n\\mathbb{E}\\|\\| \\nabla f_i(x^{k+1}) - g_i^{k+1} \\|\\| \\leq \\mathbb{E}\\|\\| \\nabla f_i(x^{k+1}) - \\nabla f_i(x^k) \\|\\| + \\mathbb{E}\\|\\| \\nabla f_i(x^k) - \\frac{x^k - x_i^{k,T}}{\\eta}  \\|\\| + \\mathbb{E}\\left[ \\sqrt{\\mathbb{E}_k \\|\\| \\frac{x^k - x_i^{k,T}}{\\eta} - g_i^k - \\mathcal{C}^k( \\frac{x^k - x_i^{k,T}}{\\eta} - g_i^k ) \\|\\|^2 }\\right], \n$$\nwhere $\\mathbb{E}_k[\\cdot] = \\mathbb{E}[\\cdot| \\mathcal{F}_k]$ and $\\mathcal{F}_k$ is the filtration up to $k$. \n\nNext, by invoking the contractive property of compression, this simplifies to:  \n$$\n\\mathbb{E}\\|\\| \\nabla f_i(x^{k+1}) - g_i^{k+1} \\|\\| \\leq \\mathbb{E}\\|\\| \\nabla f_i(x^{k+1}) - \\nabla f_i(x^k) \\|\\| + (1+\\sqrt{1-\\alpha})\\mathbb{E}\\|\\| \\nabla f_i(x^k) - \\frac{x^k - x_i^{k,T}}{\\eta}  \\|\\|. \n$$\n\nBoth terms of the right-hand side can be upper-bounded: \n\n\nThe first term can be bounded by the relaxed smoothness and the update rule for $x^{k+1}$. \nThe second term can be bounded by leveraging analyses of local GD without relying on bounded heterogeneity, as in [1] and [2].  \n\n\nFurthermore, it is a promising direction to integrate EF21 with other SOTA federated learning algorithms that accommodate multiple local steps and variance control, such as SCAFFOLD and ProxSkip. \n\n**References:** \n\n[1] Khaled, Ahmed, Konstantin Mishchenko, and Peter Richtárik. \"First analysis of local GD on heterogeneous data.\" arXiv preprint arXiv:1909.04715 (2019).\n\n[2] Demidovich, Yury, et al. \"Methods with local steps and random reshuffling for generally smooth non-convex federated optimization.\" arXiv preprint arXiv:2412.02781 (2024). \n\n\n> **Q2:** This is not a weakness per se but a question, can the results be extended to strongly convex / convex losses / PL losses without a bounded gradient assumption and achieve exponential convergence to the true minimum?\n\n**A2**: Thank you for raising this excellent point. Let us address the **convex** case and the **strongly convex / PL** cases separately. \n\n**1) Convex case:**  \n\nYes, our current analysis can be extended to convex objectives without assuming bounded gradients. Specifically, by the convexity of $f(\\cdot)$, by Cauchy-Schwarz inequality, and by assuming that there exists a sequence $\\{x^k\\}$ such that $\\|\\| x^k-x^\\star \\|\\| \\leq R$ for some $R>0$, we obtain \n\n$$\nf(x^k)-f(x^\\star) \\leq \\|\\| \\nabla f(x^k) \\|\\| \\cdot \\|\\| x^k-x^\\star\\|\\|. \n$$ \n\nThis inequality allows us to derive the convergence bound for $\\min_{k}\\mathbb{E}{f(x^k)-f(x^\\star)}$ by applying it to Theorem 1 for || EF21 || and Theorem 2 for || EF21-SGDM ||. This approach enables sublinear convergence for minimizing convex, relaxed smooth functions. \n\n**2) Strongly Convex / PL case:**\n\nExtending our results to $\\mu$-strongly convex or $\\mu$-PL objectives is more subtle. While these settings satisfy: \n$$\n\\|\\| \\nabla f(x^k) \\|\\|^2 \\geq 2\\mu (f(x^k) - f(x^\\star)),\n$$\nPlugging this inequality into the convergence bounds in Theorems 1 and 2 yields convergence in terms of $\\min_{k} \\mathbb{E}{\\sqrt{f(x^k)-f(x^\\star)}}$. This approach does not imply exponential convergence to the optimum. Addressing this gap requires new techniques, potentially involving tighter Lyapunov functions or refined descent inequalities tailored to PL-type objectives. We believe this is an interesting open question and a promising direction for future investigation."}, {"review_id": "2FXLxdDZLl", "reviewer": "Reviewer_Acin", "summary": "This paper explores the convergence properties of error feedback algorithms in distributed machine learning under generalized smoothness assumptions. Building on the existing EF21 error feedback algorithm, the authors introduce a new variant, **||EF21||**, which achieves \\$O(1/\\sqrt{K})\\$ convergence for nonconvex problems without requiring data heterogeneity. Additionally, the paper extends these results to stochastic settings by incorporating momentum-based updates (**||EF21-SGDM||**), offering stronger theoretical guarantees and improved performance in practical scenarios.", "questions": "See the Weaknesses section above .", "limitations": "The authors appropriately address the limitations of their work.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper makes a significant contribution by providing the first proof of convergence for error feedback algorithms in distributed machine learning under generalized smoothness assumptions. \n\n2. The theoretical analysis is robust, delivering strong convergence guarantees while avoiding restrictive assumptions such as data heterogeneity. \n\n3. The paper is well-organized, with a clear structure. The theoretical contributions are supported by rigorous proofs, and the experiments provide valuable insights into the practical utility of the proposed algorithms.\n\n**Weaknesses:**\n\n1. While the paper includes experiments on several tasks, such as logistic regression and ResNet-20 on CIFAR-10, expanding the benchmarking to include a wider variety of problem domains would strengthen the generalizability of the results.\n\n2. The paper touches on several important topics, including error feedback, generalized smoothness, communication compression, and normalization techniques. The authors could enrich the related work section by including more recent studies. For example, [1] uses the sign operation to compress communication and also provides guarantees under generalized smoothness assumptions, which should be discussed in the related work.\n\n[1] Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction. NeurIPS 2024.", "was_revised": true, "final_justification": "After reading the author's rebuttal and other reviewers' comments, I feel confident in recommending \"Accept\" for this paper. Accordingly, I raised my score from 4 to 5.", "rebuttal": "We sincerely thank the reviewer for the positive and encouraging feedback. We are glad that the reviewer found our work theoretically sound, well-organized, and of practical relevance.\n\n\n> **Q1**: While the paper includes experiments on several tasks, such as logistic regression and ResNet-20 on CIFAR-10, expanding the benchmarking to include a wider variety of problem domains would strengthen the generalizability of the results.\n\n**A1**: In the current manuscript, we evaluate our algorithms on three representative tasks—minimization of nonconvex polynomial functions, logistic regression with nonconvex regularization, and training ResNet-20 on CIFAR-10. These benchmarks were selected to demonstrate the effectiveness of normalization in stabilizing distributed error feedback under generalized smoothness, across both synthetic and real-world scenarios.\n\nWhile our primary focus is theoretical, we fully agree that broadening the empirical evaluation would further support the generality and practical relevance of our results. \n\n\n\n\n> **Q2**: The paper touches on several important topics, including error feedback, generalized smoothness, communication compression, and normalization techniques. The authors could enrich the related work section by including more recent studies. For example, [1] uses the sign operation to compress communication and also provides guarantees under generalized smoothness assumptions, which should be discussed in the related work.\n\n**A2**: We are happy to include additional recent studies that address generalized smoothness and normalization techniques. We will include and discuss [1] in the related work section for two main reasons. \n\n**Connection via  Normalization:** The sign operation can be viewed as coordinate-wise normalization. Potentially, our convergence results for normalized EF21 can be extended to the case where a sign operator is applied to the aggregated gradient descent update. The key difference lies in the trade-off: while the sign operator leads to a more aggressive compression scheme, it introduces a **dimension-dependent convergence rate**, which becomes a significant limitation in high-dimensional settings. \n\n**Parameter-Agnostic Guarantees:** Both [1] and our work provide parameter-agnostic convergence guarantees. That is, the algorithms do not require knowledge of the smoothness constants of the objective functions. This makes the methods more practical in distributed settings."}, {"review_id": "4RiisBmIYb", "reviewer": "Reviewer_nR5L", "summary": "In this work the authors studied the EF21 algorithm with normalisation and the L0-L1 smoothness assumption. The authors analyzed the normalised EF21 algorithm and normalised EF21-SGDM algorithm theoretically, and conducted experiments evaluating the performance of normalised EF21 against the ordinary EF21.", "questions": "1. Can the authors provide clearer explanations regarding their proof techniques? What are the choices of the parameters in the Lyapunov functions? How are these choices derived and why are they critical for the analysis of the normalised method (in contrast to the choices in the EF21 paper)? There are also some recent papers that got rid of the need of Lyapunov functions altogether, by upper bounding the sum of the error terms together [1]. Such an approach eliminated the need for guessing the parameters in the Lyapunov function. Since the authors believe that the novel technical contribution of the proof lies in the construction of the Lyapunov function, I wonder if it's possible to follow the approach in [1] and obtain an analysis of the normalised EF21 without the Lyapunov function?\n\n2. Can the authors add a discussion regarding Assumption 2? In particular, it would be interesting to understand why is this assumption necessary? Would the analysis of EF21 be improved when given this assumption? This should also be complimented by a discussion on how would $\\delta^{\\inf}$ affect the comparisons of convergence rates\n\n3. Can the authors please also compare the normalised EF21 with other popular compressed optimization methods, including the original EF, and maybe also EControl or some other variants of EF?\n\n\n\n[1] Gao et. al., Accelerated Distributed Optimization with Compression and Error Feedback, 2025", "limitations": "see weakness and questions.\n\nI think the results of the paper are interesting and I'll be happy to raise the score if my questions can be addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think from a theory perspective this is an interesting paper. No EF21-style methods, or indeed, no EF methods, has been analysed with normalised stepsizes and L0-L1 smoothness prior to this work. So the results are new and I think the techniques employed here would be of interests to other people working on the same topics as well. In particular, controlling the errors with varying stepsizes for EF, or EF21 style methods, is non-trivial (unless when the stepsizes are non-increasing, which is not the case with normalised stepsizes). However, in its current form, the paper still has many weaknesses, and I discuss these below:\n\n1. Lack of clear discussion on the technical innovations in the proofs: the authors had a brief discussion of their proof techniques at the end of Section 5, but this discussion, to put it mildly, is non-informative. The authors claimed that the key difference is a new choice of Lyapunov function. But it's unclear why is that the case given the discussion. It seems that the only difference is just with the choice of parameter A and B. The authors didn't discuss the choices of A and B, so for all we know they might as well be the same.\n\n2. Stronger assumption: The authors claimed that Assumption 2 is standard for analysing optimisation algorithms. I find that unconvincing. In particular, as far as I'm aware, most existing works on EF and EF21 only requires Assumption 1, instead of Assumption 2. Here it seems that Assumption 2 acts as some sort of relaxation of the overparametrization assumption, which would typically be considered a very strong assumption. I'm not against introducing stronger assumptions when needed, but this should be adequately discussed.\n\n3. The experiments section only compares the proposed algorithm against EF21. This seems a bit insufficient to me. There are many other state of the arts algorithms in compressed optimization methods, and I think it's hard to gauge the actual practical value of the proposed algorithm if it's only compared against EF21.", "was_revised": true, "final_justification": "The authors have addressed my questions and I have raised the score. I strongly encourage the authors to include their discussions in the rebuttal in the main text of the paper.", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and for acknowledging the novelty of our theoretical techniques and the potential impact of our work. We address each concern below:\n\n> **Q1**: Can the authors provide clearer explanations regarding their proof techniques? What are the choices of the parameters in the Lyapunov functions? How are these choices derived and why are they critical for the analysis of the normalised method (in contrast to the choices in the EF21 paper)? There are also some recent papers that got rid of the need of Lyapunov functions altogether, by upper bounding the sum of the error terms together [1]. Such an approach eliminated the need for guessing the parameters in the Lyapunov function. Since the authors believe that the novel technical contribution of the proof lies in the construction of the Lyapunov function, I wonder if it's possible to follow the approach in [1] and obtain an analysis of the normalised EF21 without the Lyapunov function?\n\n**A1**: Thank you for the thoughtful questions. We address them below in the following points: \n\n**Clarification on proof techniques and Lyapunov function parameters:** The structure of our Lyapunov function differs from EF21 primarily in the second term: we use $|| v^k_i -\\nabla f(x^k) ||$, while EF21 uses $|| v^k_i-\\nabla f(x^k) ||^2$. This change is driven by the nature of the descent lemma in our analysis. Due to normalization in our method, we need to control the quantity $|| g^k -\\nabla f(x^k) ||$, whereas EF21 deals with $|| g^k -\\nabla f(x^k) ||^2$. This distinction affects the entire structure of our Lyapunov function.\n\nAdditionally, our analysis operates under a **generalized smoothness condition**, unlike EF21, which assumes standard smoothness. The generalized smoothness makes the analysis more intricate, particularly in deriving recursive inequalities. This is most evident in Lemma 4, which forms the core of our recursive argument and requires significantly different handling compared to EF21.\n\nMoreover, the proof technique for normalized EF21-SGDM deviates even more significantly from prior works. Specifically, we introduce a novel Lyapunov function that differs from the one used by Fatkhullin et al. [10] (see our submission), derive an upper bound for $\\mathbb{E}[\\|\\| v^k - \\nabla f(x^k) \\|\\|]$ via a new route (see Lemma 9), and employ the Lyapunov function in a fundamentally different manner.\nIn particular, after establishing the descent inequality in the proof of Theorem 2 (see the inequality following Line 624), we face a key challenge: the right-hand side involves non-telescoping terms, namely $\\left(1 + \\frac{64L_1^2 \\gamma^2}{1 - \\sqrt{1-\\alpha}}\\right)V_k + 32L_1^2\\gamma^2 \\sum_{t=0}^{k-1} (1-\\eta)^{k-t} V_t$ which prevents a straightforward summation as done in the analyses of EF21 or EF21-SGDM.\n\nTo overcome this, we introduce carefully chosen weights $\\beta_k$ (defined in Line 625) and apply a weighted summation strategy. This allows us to effectively upper-bound the double-sum term on the right-hand side and complete the proof of convergence (see Lines 626–639). \n\n**On the choice of Lyapunov function parameters:** The parameters in our Lyapunov function are not guessed heuristically; instead, they are **systematically derived** to ensure the monotonic decrease of the Lyapunov function, i.e., to guarantee that $V_{k+1} \\leq V_k$. This is crucial for proving convergence. We refer you to **Lemma 6**, where this parameter selection arises naturally from the analysis. The choice ensures that error terms are properly balanced across iterations to obtain a descent inequality.\n\n**On Lyapunov-free techniques and comparison with [1]:** We agree that the Lyapunov-free approach in [1]—which upper bounds the accumulated error without relying on a crafted Lyapunov function—is an elegant and promising alternative. However, to the best of our knowledge, we believe that **preferences between Lyapunov-style and Lyapunov-free analysis can be subjective.**\n\nFurthermore, the effectiveness of the Lyapunov-free approach is tied to their use of the **Similar Triangle Method**, which serves as a foundation for their new analysis. Therefore, applying a similar technique to our normalized method would be **non-trivial and may require significant modification** of both algorithmic structure and analytical tools. Additionally, **[1] focuses on convex and standard smooth settings, whereas our framework targets nonconvex problems with relaxed smoothness**, which poses different technical challenges.\nThat said, exploring a Lyapunov-free analysis for our setting is an interesting direction for future work, and we thank you for raising this possibility.\n\n\n> **Q2**: Can the authors add a discussion regarding Assumption 2? In particular, it would be interesting to understand why is this assumption necessary? Would the analysis of EF21 be improved when given this assumption? This should also be complimented by a discussion on how would  affect the comparisons of convergence rates.\n\n\n**A2**: **Assumption 2 is necessary** to carry out our analysis under the **generalized smoothness condition**, which is more general than the standard $L$-smoothness used in EF21 and [1]. Specifically, this assumption **plays a crucial role in controlling the discrepancy between local and global function behavior**, which is essential for establishing descent bounds under our relaxed smoothness model. Notably, this assumption is made **in place of the commonly used uniformly bounded heterogeneity condition** found in existing works.\nImportantly, if we consider the special case where **$L_1 = 0$**, then our analysis simplifies considerably. In this case, the troublesome term involving the difference between $f^{\\inf}$ and $f_i^{\\inf}$ disappears, and **Assumption 2 becomes unnecessary**. This highlights that \n\n\n1. The original EF21 and || EF21 || can operate under standard smoothness assumptions and do not require Assumption 2. \n\n2. Assumption 2 is only invoked to handle the additional complexity introduced by **$(L_0,L_1)$-smoothness assumptions**.\n\nFurthermore, in terms of convergence rate in $\\varepsilon$ under **$(L_0,L_1)$-smoothness assumptions**, our method, || EF21 ||, **matches** the EF21 rate. Furthermore, our convergence results are **parameter-agnostic**, meaning they do not require tuning based on problem-specific constants.\nHowever, the detailed comparison of constants in the rates (i.e., dependence on $L_0$, $L_1$, and $\\delta^{\\inf} := \\frac{1}{n}\\sum_{i=1}^n f^{\\inf} - f_i^{\\inf}$) is more nuanced due to the difference in assumptions and settings. If we set $L_1 = 0$, then the generalized smoothness reduces to standard smoothness, and our rate constants become comparable to those in EF21. In this case, we recover a similar rate up to minor differences in step size choices (e.g., $\\gamma = \\sqrt{\\Delta / c_0}$ in our method). \nWe are happy to include these discussions in the final version of our manuscript. \n\n\n> **Q3**: Can the authors please also compare the normalised EF21 with other popular compressed optimization methods, including the original EF, and maybe also EControl or some other variants of EF?\n\n**A3**: We already provide a direct empirical comparison between normalized EF21 and EF21 in Figure 1, which demonstrates the effectiveness of normalization to improve the convergence of EF21 algorithms to minimize the convex, relaxed smooth functions. Specifically, normalized EF21 allows for larger stepsizes and faster convergence than its non-normalized counterpart, original EF21. Our additional benchmarking results on logistic regression and ResNet-20 training further confirm these findings. \n\nOur main focus in this paper is to investigate **why normalization is important under relaxed smoothness assumptions**. While a direct comparison with other error feedback variants (e.g. **EControl**) may not directly address this core question, we agree that it would be valuable to explore how normalization interacts with these methods. Extending both the theoretical and empirical analysis to other error feedback variants could help determine whether normalization plays a similarly stabilizing or accelerating role in those contexts as well."}, {"review_id": "mBDjadXqBa", "reviewer": "Reviewer_Xvhq", "summary": "This paper addresses the challenge of training deep neural networks with error feedback algorithms under generalized smoothness assumptions, specifically $(L_0,L_2)$-smoothness, which is more representative of modern machine learning problems than traditional smoothness assumptions.", "questions": "- **Anonymous GitHub Link:** As of June 29, I attempted to access the anonymous GitHub repository, but the link has expired.  \n- **Proof:** I did not follow every proof detail; however, the overall results appear reasonable and reliable.  \n- **Experimental Questions:**  \n  1. **Logistic Regression:** The proposed method substantially outperforms EF21. Could you specify the exact step sizes used for both algorithms?   \n  2. **Related Work Comparison:** You identify [25] and [26] as the most relevant works. Maybe, you can include a direct comparison of your experimental results with the findings in these references.  \n  3. **Machine number:** I think the $n$ become the number of data volume in experiment section. Please point out how many machines (nodes) are you used in the experiments.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The paper provides the proof of convergence for normalized error feedback algorithms in $(L_0,L_1)$ generated smoothness. These analyses apply to distributed settings with data heterogeneity conditions.\n\n- The primary limitation is that the current analysis relies on constant stepsizes (depends on the iterations budget $K$), hence it is not a any-time optimal algorithm.", "was_revised": true, "final_justification": "I must acknowledge that I did not grasp every detail of the manuscript; however, overall, its logic is relatively clear and its contribution is well-defined.", "rebuttal": "We thank the reviewer for their constructive feedback and for recognizing the relevance of our generalized smoothness analysis and its applicability to modern distributed training scenarios.\n\n\n> **Q1**: The primary limitation is that the current analysis relies on constant stepsizes (depends on the iterations budget ), hence it is not a any-time optimal algorithm.\n\n\n**A1**: We appreciate this important observation. As you pointed out, our current theoretical analysis assumes a constant stepsize that depends on the total number of iterations, which limits the any-time nature of the algorithm. \nWe believe that our current results can be extended to the case of decreasing stepsizes, which would remove the dependency on knowing the total number of iterations. For example, in the case of || EF21 || under generalized/relaxed smoothness assumptions, we can show that by using a decreasing stepsize on the form \n$$\n\\gamma_k = \\gamma_0/(k+1)^{1/2+\\nu} \\quad \\text{for} \\quad \\nu \\in (0,1/2),\n$$\nyields a convergence rate of  \n$$\n\\min_{k\\in[0,K]} \\mathbb{E}|| \\nabla f(x_k)||  = \\mathcal{O}\\left( \\frac{1}{(K+1)^{1/2-\\nu}} \\right).\n$$\nWe prove this result from the descent inequality we obtained for  || EF21 || under generic decreasing stepsizes (Theorem 1):\n$$\nV_{k+1} \\leq (1+A \\gamma_k^2 \\exp(L_1\\gamma_k)) V_k - \\gamma_k W_k + B \\exp(L_1\\gamma_k) \\gamma_k^2, \n$$\nwhere $V_k = \\mathbb{E}{f(x_k)-f_{\\inf}}$ and $W_k = \\mathbb{E}\\| \\nabla f(x_k)\\|^2$. \nSince $\\gamma_k \\leq \\gamma_0$, this inequality simplifies to: \n$$\nV_{k+1} \\leq (1+ \\tilde A \\gamma_k^2) V_k - \\gamma_k W_k + \\tilde B \\gamma_k^2,\n$$\nwhere $\\tilde A = A \\exp(L_1\\gamma_0)$ and $\\tilde B = B \\exp(L_1\\gamma_0)$. \n\nFinally, defining a sequence $\\alpha_k = \\alpha_{k-1}/(1+\\tilde A \\gamma_k^2)$, applying the fact that  $\\min_{k \\in [0,K]} W_k \\leq \\frac{1}{\\sum_{k=0}^K \\alpha_k\\gamma_k} \\sum_{k=0}^K \\alpha_k \\gamma_k W_k$, and using the above inequality, we obtain the final convergence result stated above. \n\nFurthermore, we believe that similar convergence results can be established for  || EF21-SGDM || under the decreasing stepsize, e.g. by choosing $\\gamma_k=\\gamma_0/(k+1)^{3/4}$ and $\\eta_k = 1/(k+1)^{1/2}$. However, this requires us to revisit key lemmas related to the decreasing stepsizes, as presented, e.g., by Hübler et al. (2024). \n\n\n> **Q2**: Logistic Regression: The proposed method substantially outperforms EF21. Could you specify the exact step sizes used for both algorithms?\n\n\n**A2**: We benchmarked normalized EF21 and original EF21 algorithms **with their own theoretical stepsizes** for solving logistic regression problems. The stepsize of normalized EF21 is $\\gamma = 1/\\sqrt{K+1}$ by Theorem 1 of our paper, while that of original EF21 is $\\gamma = 1/(L + \\tilde L \\sqrt{\\beta/\\theta})$ with $\\tilde L = \\sqrt{\\sum_i L_i^2/n}$ and $\\theta,\\beta$ given by Theorem 1 of [8]. Here, $L,\\tilde L$ is estimated from the loss function, while $\\theta,\\beta$ is tuned according to $\\alpha = k/d$ for the top-k sparsifier and for each $d$-dimensional feature vector of the data matrix. \n\n\n> **Q3**: Related Work Comparison: You identify [25] and [26] as the most relevant works. Maybe, you can include a direct comparison of your experimental results with the findings in these references.\n\n\n**A3**: We include [25], because clipping and normalization are two popular operations for stabilizing optimization algorithms to minimize relaxed smooth functions. As clipping is the generalization of normalization, we agree that it is interesting to extend our current theorems for the cases when we apply clipping rather than normalization, and to benchmark our modified algorithms empirically. \nRegarding [26], we reference it (Lines 141–146) because it also addresses convergence under relaxed smoothness assumptions. However, their approach relies on additional restrictive conditions—such as almost sure variance bounds and symmetric noise distributions—which our analysis avoids. Moreover, we do not benchmark against their algorithms, as their methods do not incorporate error feedback, a key feature of our proposed approach.\n\n\n> **Q4**: Machine number: I think the $n$  become the number of data volume in experiment section. Please point out how many machines (nodes) are you used in the experiments.\n\n\n**A4**: Thank you for pointing this out. You are correct – there is an overload of notation. In our experiments on nonconvex polynomial minimization and logistic regression, we used $n$ to denote the number of data points. In contrast, for the ResNet-20 training on CIFAR-10, $n$ refers to the number of clients (machines), which we set to $n=5$. We will revise this part of the paper to clearly distinguish between the number of data points and the number of clients, and adopt consistent, unambiguous notation throughout."}]

Author rebuttal:

Meta-review: **Summary:** 
The current sutidy of error feedback algorithms requires smoothness assumption which is not necessarily satisfied by for instance deep neural networks. Relying on a more general $(L_0, L_1)$-smoothness, the paper proposes a normalization strategy to an existing algorithm **EF21**, and studies the convergence property of the new scheme. Extension to stochastic setting is also considered. The new scheme is supported by numerical experiments. 

**Strength:**
 - The paper makes a significant contribution the analysis of error feedback algorithms under merely generalized smoothness. The proposed analysis has potential impact to other problems.
 - Solid theoretical analysis without strong assumptions.
 - Convincing numerical experiments. 

**Weakness:**
 - The presentation of the paper can be further improved.

**Discussion summary:** 
All reviews acknowledge the significance of the proposed study, and its potential broad impact. We also suggest the reviewers to revise the paper according to the author-reviewer discussion.
Decision: Accept (poster)