Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction
Authors: Wei Jiang
Sifan Yang
Wenhao Yang
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: SignSGD
majority vote
sign-based method
variance reduction
Primary area: optimization

Abstract: Sign stochastic gradient descent (signSGD) is a communication-efficient method that transmits only the sign of stochastic gradients for parameter updating. Existing literature has demonstrated that signSGD can achieve a convergence rate of $\mathcal{O}(d^{1/2}T^{-1/4})$, where $d$ represents the dimension and $T$ is the iteration number. In this paper, we improve this convergence rate to $\mathcal{O}(d^{1/2}T^{-1/3})$ by introducing the Sign-based Stochastic Variance Reduction (SSVR) method, which employs variance reduction estimators to track gradients and leverages their signs to update. For finite-sum problems, our method can be further enhanced to achieve a convergence rate of $\mathcal{O}(m^{1/4}d^{1/2}T^{-1/2})$, where $m$ denotes the number of component functions. Furthermore, we investigate the heterogeneous majority vote in distributed settings and introduce two novel algorithms that attain improved convergence rates of $\mathcal{O}(d^{1/2}T^{-1/2} + dn^{-1/2})$ and $\mathcal{O}(d^{1/4}T^{-1/4})$ respectively, outperforming the previous results of $\mathcal{O}(dT^{-1/4} + dn^{-1/2})$ and $\mathcal{O}(d^{3/8}T^{-1/8})$, where $n$ represents the number of nodes. Numerical experiments across different tasks validate the effectiveness of our proposed methods.

Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction
Wei Jiang', Sifan Yangl, Wenhao Yang Lijun Zhang 1.2.+
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Schooo of Artificial Intelligence, Nanjing University, Nanjing, China Pazhou Laboratory (Huangpu), Guangzhou, China [jiangu, yangsf, yangwh, changlj]@@lan .nw.. edu.
Abstract
Sign stochastic gradient descent (signSGD) is communication-efficient method that transmits only the sign stochastic gradients for parameter updating. Exist- ing literature has demonstrated that signSGD can achieve convergence rate of (1d/2TT1/4) where d represents the dimension and T is the iteration number. In this paper, we improve this convergence rate to /22 by introducing the Sign-based Stochastic Variance Reduction (SSVR) method, which employs vari- ance reduction estimators to track gradients and leverages their signs to update. For finite-sum problems, our method can be further enhanced achieve convergence rate of (m /1/22-111)) where denotes the number of component functions. Furthermore, we investigate the heterogeneous majority vote in distributed set- tings and introduce two novel algorithms that attain improved convergence rates of ((d-/2T-1/2 + dd/-1/2) and (d//1T-1/2)) respectively, outperforming the previous results of 11/ dn. dn2-1/2) and (d8/88T-1/8) where represents the number of nodes. Numerical experiments across different tasks validate the effectiveness of our proposed methods.
Introduction
This paper investigates the stochastic optimization problem
min f(x), x
(1)
where R + the gradient fx(x) can be accessed, represented f E), where & is random sample drawn from a stochastic oracle such that [[V = fxx).
a smooth and non-convex function. We assume that only noisy estimations of
The most well-known method for problem is stochastic gradient descent (SGD), which performs X4+1 = X₁ v f (x(x;) E,) for each iteration, where & is the sample used in the t-th iteration, and 17 is the learning rate. It has been proved that the SGD method OT741/4) Ghadimi and Lan 2013 where 7 is the iteration number. Recently, sign stochastic gradient descent (signSGD) method [Seide et al. 2014 Bernstein et al., [2018) has become popular in the machine learning community, which uses the sign of the stochastic gradient to update, i.c..
obtain convergence rate of
X = X, 77 Sign V (xx; E.)
This method largely reduce the communication overhead in distributed environments, and prior research [Bersstein et al. 2018 2019 has established that signSGD can achieve a convergence rate
Lijunn Zhang the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of ((21/21-1/4) measured in terms of the 11 no-m. Since the O(T 1/4) rate is already optimal for SGD methods when measured in the 12-norm [Arjevani et al. [023] we can not further improve the dependence on 7 for signSGD method, considering that |x||| S x ll for any x However, it is also known that variance reduction techniques can further enhance the convergence rate to OTT-1/3) 1/3).
under a slightly stronger assumption of average smoothness [Fang et al., 2018 Wang et al. 2019 Cutkosky and Orabona 20191. This leads to natural question: Can the convergence of sign-based methods be further improved by employing variance reduction techniques along with the average smoothness assumption? ? We respond affirmatively by introducing the Sign-based Stochastic Variance Reduction (SSVR) method. By integrating variance reduction technique [Cutkosky and Orabona 2019] with sign operations, we achieve an improved convergence rate of Od 1/5) measured in the 1 -norm, matching the optimal rates in terms of ' for stochastic variance reduction methods (Fang et al. 2018 Li et al., 2021 Arjevani et al., 2023]
Furthermore, we investigate a special case of problem I in which the objective function exhibits a finite-sum structure:
min fxx XER
f((x).
where each fi(-) smooth and non-convex. This problem has been extensively studied in stochastic optimization (Zhang et al.] 2013 Defazio et al. 2014 Fang et al., 2018). J, but is less explored with sign-based methods. Previous literature proposes signS VRRSVRRGPP [Chzhen and Schechtman 2023) method
to deal with the finite-sune sum problem, which achieves a convergence rate of O(m /2d 1/2).
However, its dependence on m sub-optimal, failing to match the O Om (4/-411//2) lower bound [Fnng et al. 2018 [i ct al., [02T] for problem (2) To address this gap, we propose the SSVR-FS algorithm. which periodically computes the exact gradient [Zhang et al. 2013 Johnson and Zhang, 2013)
and incorporates it into the variance reduction estimator. In this way, we can achieve an improved convergence rate of (m=2/442/27-11/3 for finite-sum problems.
Finally, sign- based methods are especially favorable in distributed settings. where the parameter server aggregates gradient signs from each worker through majority vote [Bernstein et al.) 20188. allowing 1-bit compression of communication in both directions. Existing literature [Bernstein et al.) 2018 2019) has proved that signSGD can obtain a convergence rate of O(d2/27-174) for majority vote in homogeneous settings, where the data across nodes is uniformly distributed or identical. For the more challenging heterogeneous setting, in which data distribution can vary significantly across nodes, existing methods can only achieve convergence rates of O(dT-1/1 + dn dn2) (Sun et al. 2023) and O(d9/8T-1/8) rate indicates that the gradient does not converge to zero as T approaches infinity, and the second one suffers from a high sample complexity. To address these limitations, we first introduce our basic SSVR-MV method, which employs variance reduction estimators to track gradients and replaces the sign operation in each worker as a stochastic unbiased sign operation. This practice ensures 1-bit compression and unbiased estimation at the same time, and the newly proposed method can obtain an improved convergence rate of (d + dn-1//2 1/2). By further substituting the sign operation in the parameter server with another stochastic unbiased sign operation, our method can further achieve a convergence rate of (d1/4T-1/4) which converges to zero as T increases.
1/8 Jii et al. 2023). where n denotes the number of nodes. Note that the first
In summary, compared with existing methods, this paper makes the following contributions:
For stochastic non-convex functions, we develop sign-based variance reduction algorithm to achieve improved convergence rate of O(d-/2T-1/3) surpassing the O//1/27-1/1) rate for signSGD methods.
For non-convex finite-sum optimization, we further improve the our proposed method to obtain an enhanced convergence rate of 0/22//4//2T-11// which is better than the Om /2
convergence rate for SignSVRG method.
Note that most lower bounds are measured in the lu-norm, and there are no existing lower bounds for the I (n-orrm to the best of our knowledge. However, since ||x||| 2 ||||>||| for dense vector x, the additional O d)) term is acceptable when considering the norm.. This is also the case for methods (measured in the l1 (i-norm) and the lower bounds for variance reduction methods (for no-morm).
'The original convergence rate is measured under the squared nz-norm, and we convert it to the rate under the lo-norm criterion for fair comparison.

---

Table 1: Summary of results for sign-based algorithms. Here, stochastic indicates problem U
finite-sum represents problem (2) N is the number of stochastic gradient calls, and m is the number of component functions. Note that some rates measured under squared 1 2y -n-nomm, and convert them to 11- or 22-mrmm for fair comparison.
Method
Setting
Measure
Convergence rate
signSGD Bemstein et al.
2018
stochastic
4--nr
N174
EF-signSGD
Karimireddy et al.
2019
stochastic
12-norm
signSGD-SIM
Sun al.
2023
stochastic
4-norm
N1y4
SignSVRG Chzhen and Schechtman
2023
finite-uum
4--norm
d/
SignRVR/SignRVM
Qin et al.
2023
finite-sum
1 4ormm
d4/2 m 1/2 N1/2
dl//2
Theorem
stochastic
4--nrm
NT73
m//2
Theorem
finite-sum
I-norm
.172
Table 2: Summary of results for sign-based algorithms under the majority vote setting, where n the number of workers. Some rates are measured under squared 4 or 12-norm, and we convert them to 11- or 22-mo for fair comparison.
Method
Heterogeneous
Measure
Convergence rate
signSGD
Bernstein al.
2018
I-normm
41/2
T174
Signum
Bernstein et al.
2019
x
Ii-nrmm
g²/2
T'744
4///
SSDM Safaryan and Richtarik
2021
/
12-norm
7174
Sto-signSGD [Jin et al.
2023
/
12-norm
1 d2/
MV-sto-signSGD-SIM
Sun et al.
2023
/
41-norm
T1/4 + n!/a
Theorem
/
12-norm
T1/2 + m!/2
21/2
2//4
Theorem
/ 12-norm
T174
We also investigate sign-based variance reduction methods with heterogeneous majority vote in distributed settings. The proposed algorithms obtain the convergence rates of Odd'/2T-1/2 + dn -1/2) and O1d4/47-1/4) which outperform the previous results of O dn 1 and ((10/8T-1/8) respectively.
We compare our results with existing methods in Table and Table 2 and validate the effectiveness of our method via numerical experiments Section 5
2
Related work
This section provides an overview the existing literature on signSGD methods and stochastic variance reduction techniques.
2.1 SignSGD and its variants
The idea of only transmitting the sign information of the stochastic gradient traces back to the 1-bit SGD algorithm, introduced by [Seide et al. [2014). Despite the biased nature of sign operation, Bernstein al. (018 demonstrated that signSGD achieves a convergence rate of ( 114)) by using large batch sizes in each iteration. Despite the theoretical assurance, Karimireddy et al. 2019 highlighted that signSGD may not converge to the optimal solutions for convex functions and could suffer from poor generalization without large batches. To address these issues, they proposed the

---

EF-sigDSGD method, which integrates eπror feedback into signSGD to correct errors introduced by the sign operation. Instead of requiring unbiased stochastic gradients in previous literature, [Safaryan and Richtarik [02T] assumed that the signs of the stochastic gradient are the same as those of true gradient with a probability greater than 1/2. Under this assumption, they demonstrated that signSGI) can obtain a similar convergence rate but does not require large batches anymore. Recently. [Sun et al.) [2023] proposed the signSGD-SIM method, which incorporates the momentum into the signSGD, achieving convergence rate of O (dT= with constant batch sizes and an improved convergence of (dd/2TT-2// 2/7) with second-order smoothness.
To deal with the finite-sum problems, Chzhen and Schechtman 2023 developed SignSVRG algo- rithm, which combines SVRG (Johnson and Zhang [013] method with signSGD and achieves where m is the number of component functions. More recently, Qin et al. [203]] further investigate signSGD with random reshuffling, achieving a con- vergence rate of O (m mmm-1/271//2 log(m'T) + || where the variance bound of stochastic gradients. By leveraging variance-reduced gradients and momentum updates, they further propose the SignRVR and SignRVM methods, both achieving the convergence rate of O (d! 1/2
convergence rate of
In distributed settings, sign-based methods with majority vote also widely investigated. |eensttinn ct al. 2018, 2019] first indicated that signSGD and its momentum variant Signum can enable 1-bit compression of worker-server communication, obtaining the ((d/2T=-144) convergence rates in the homogeneous environment, For the more challenging heterogeneous settings, SSDM method (Sa) faryan and Richtarik 2021] attains the same O(d convergence rate, but the information sent back to the server is not a sign information anymore. To remedy this issue, Sto-signSGD algorithm (Jin et al. 2023) proposed, equipped with a convergence rate of Odd measured in squared l2 norm. More recently, Sun et al. (2023) introduced the MV-signSGD-SNN algorithm and demonstrated a convergence rate of (dT + dn d112), which could be further enhanced to Odd (d9/2T222/7 + dn 112) under second-order smoothness conditions, where n denotes the number of nodes in the distributed system.
2.2 Stochastic variance reduction methods
Stochastic variance reduction methods have gained significant attention in the optimization com- munity in recent years. Among the pioneering approaches, the stochastic average gradient (SAG) method [Roux et al. 2012) and Stochastic Dual Coordinate Ascent (SDCA) algorithm (Shalev] Shwartz and Zhang 2013] utilize a memory of previous gradients to ensure variance reduction, achieving linear convergence for strongly convex functions. To circumvent the need for storing gradients, the stochastic variance reduced gradient (SVRG) [Zhang et al. 2013 Johnson and Zhang 2013] recalculates the full gradient periodically to enhance the accuracy of gradient estimators, maintaining linear convergence for strongly convex functions, Inspired by SAG and SVRG, Defazio ct al. [2014] introduced the SAGA algorithm, which not only provides superior convergence rates but also supports proximal regularization. Subsequently, the stochastic recursive gradient algorithm (SARAH) [Nguyen al. 2017] employs a simple recursive approach to update gradient estimators, ensuring better convergence for smooth convex functions.
For non-convex optimization, inspired by the SVRG algorithm, many methods [Reddi et al. 2016 Lei et al. 2017 Zhou et al., [000] employ variance reduction to design their algorithms and provide the corresponding convergence guarantees. More recent well-known advancements include the SPI- DER Fang et al. 2018) and SpiderBoost [Wang et al. 2019) methods, which improved the O(T 1/4) convergence rate of traditional SGD to O(3-173) under the average smoothness assumption. The convergence rate can be further improved to Om 1//m//11//// for problems with a finite-sum structure, where m represents the number of component functions. However, these methods typically require a huge batch size to ensure convergence. To avoid this limitation, the stochastic recursive momentum (STORM) method [Cutkosky and Orabona 2019] introduces a momentum- based updating and an adaptive learning rate based on the stochastic gradients, achieving convergence rate of 1133 without necessitating large batches. More recently. variance reduction techniques are widely em- ployed in more complex problems to improve the existing convergence rates, such as compositional
optimization |Wang et al. 2017a b. Yuan et al. 2019 Jiang et al. 2022a 2023 multi-level optimiza- tion [Chen et al. [202] //hang and Xiao| 2021 Jiang et al. 2022h 2024b), adaptive algorithms (Kavis)
et al. 2022 Jiang ct al. 2024a], and distributionally robust optimization
YYu ct al. 2024).

---

Algorithm SSVR
1: Input: time step T, initial point
2: for time step t to do
5211 .5. 4: Compute V. B, Σ Vx(x; ( + (1- (vo-1- 1 E vf(x(-i(())
3: Draw a batch samples (El,
B,
5: Update the decision variable: X Xt - 11) Sign (v,)
6: end for
7: Select uniformly at random from (I,...,
8: Return X,
The proposed methods
In this section, we present the proposed methods for the expectation case, i.e., problem I and the finite-sum structure, i.e., problem (2), respectively, along with corresponding theoretical guarantees.
3.1 Sign-based stochastic variance reduction
In this subsection, we introduce our Sign-based Stochastic Variance Reduction (SSVR) method for problem (T). One crucial step in stochastic optimization is to track the gradient of the objective function. Here, we use a variance reduction gradient estimator V, to evaluate the overall gradient fx(x). In the first iteration (t = 1), the estimator is defined as 1 Σ Bo k=1 ff(xi: Ef). where
Bo
Bo is the batch size used in the first iteration. For subsequent iterations (f 2 2), Ve is updated in the style of STORM [Cutkosky and Orabona 2019 i.e.,
1 B, V. B1
Σ
Vf(x: (1 (1-3) Vi-1 ((((x=1
B1
where 3 represents the momentum parameter and Bj the batch size. This method ensures that the expectation of the estimation error Billv, (xx))) would be reduced gradually. After obtaining the gradient estimator Vt, we update the decision variable using the sign of Vy:
X x Sign (v:).
The whole algorithm is outlined in Algorithm Next, introduce the following assumptions for our SSVR method, which are standard and commonly adopted in the analysis variance reduction
methods and stochastic non-convex optimization (Fang al. 2018 Wang al. 2019 Cutkosky and
Orabona 2019 et al. 2021].
Assumption (Average smoothness)
Eg [V]((;)) - -s(x;()]1 < I
yl1?.
Assumption (Bounded variance)
Eg [V]({;)) - vS(x) S 0²
With the above assumptions, can obtain the theoretical guarantee for method as stated below.
Theorem Under Assumptions 7 2 by setting 8 = O ((TT)))) O (171)17))) Bo O(T2/3), and B = (1), our SSVR method ensures:
1/22
E [[x+))] 50
T1/3
This convergence rate surpasses the (14/22-114) rate achieved by previous sign-based methods [Bernstein al. 2018 2019]. and it also outperforms the ((d3/27-2/7) convergence rate under the second-order smoothness condition (Sun et al.) 2023 Specifically, to ensure that E|||V f (x+))l < c, our method requires sample complexity of ( which is much better than the e and 1//11/1--773 complexities of previous approaches.
Remark:
5

---

Algorithm 2 SSVR for Finite-Sum (SSVR-FS)
1: Input: time step T, initial point
2: for time step 1
do
3: if mod I = 0 then
4: Set r = f and compute ff((,) E Vf((x,,
5: end if
6: Sample i, randomly from {1, (1,2,...,m)
7: Compute gradient estimator V, according equation
8: Update the decision variable: X,+1 = X sySign (v,)
9: end for
10: Select uniformly at random from {I...., 7}
Return x
3.2 Sign-based stochastic variance reduction for finite-sum structure
We now extend our SSVR method to deal with the finite-sum structure in problem In this context, we introduce the following assumption for each component function, which is standard and widely
adopted in existing literature (Fang al. 2018 Wang et al. 2019 Li et al. 2021].
Assumption (Smoothness) For each i (1.2, .m), the gradient functionn satisfy:
[V)(x) (/i()) < L||x yll.
To handle the finite-sum problems, we retain the core structure of our SSVR method while incorporat- ing elements from the SVRG [Zhang et al. 2013) Johhsson and Zhang 2013 approach. Specifically, we compute full batch gradient at the first step and every / iteeation, i.e.,
v (x(x)) =
V(((x))
For other iterations, we randomly select an index i, from the set .mm and construct variance reduction gradient estimator V, as follows:
V:- ft. (x,)
(v (1 Vf,
(V Vf(x)))
(3)
STORM estimator
error correctio
The first two terms of v; align with the STORM estimator, and the last term measures the difference of past gradients between the selected component function fi, (x,) and the overall objective ff(x,), Note that the STORM estimator employs the component gradient Vfa (x;) to track the overall gradient fx{e). which leads to estimation error due the gap between the component function and the overall objective. This gap can be effectively mitigated by the error correction term we introduced in equation (3). With such design,
obtain better gradient estimation of the overall gradient, and ensure that the estimation error B fx;) - vzll can be reduced gradually. After computing v,, we utilize its sign information to update the decision variable. The detailed procedure is outlined Algorithm Next, we present the theoretical convergence for this method.
Theorem Under Assumption by setting 3 = ( ) = m, and = Ol ( ) our algorithu ensures:
m////2/2
(Ix)F((
T1/2
Remark: ensure VF
|l1 S c, the sample complexity is O(m + 2 which improves
over the O dm 22
complexity the previous SignSVRG method (Chzhen and Schechtman 2023
Sign-based stochastic variance reduction with majority vote
Sign-based methods are advantageous in distributed settings for their low communication overhead, as they can only transmit sign information between nodes via majority vote. This section explores sign- based stochastic methods with majority vote. typical example of distributed learning extensively

---

Algorithm 3 SSVR-MV
1: Input: time step T, initial point
2: for time step t
I do 3: On node j {1, .1.,,
Draw sample e and compute v/ (xy(x ( + (1- (v/-1= Vxf
4:
5:
Option 1: Send Sx(v;) to the parameter server, where 4G
6:
Option 2: Send So(V:) to the parameter server, where v/ = [ca[v!]
7:
On parameter server:
8:
Option 1: Send V. Sign [ 12 2 SR
(v))
to all nodes
9:
Option 2: Send V, = S1
-ド= SG (v)
all nodes
On node j 11, nn:
11: Update the decision variable X = 7/Vr
end for Select uniformly at random from (I...., T}
13:
Return x
studied in previous sign-based based algorithms [ernsttii et al. 2018 2019 Safaryan and Richtarik] 2021
Sun al. 2023 To begin with, we investigate the following distributed learning task:
min f(x = Σ (x), fz(x) = EEIDD [x)) XER
where Dj represents the data distribution for node j. and [x( is the corresponding loss function.
Some previous studies [Bernstein et al.) 2018 2019] investigate the homogeneous setting, which
assumes the data across each node uniformly distributed identical, ensuring that [[ ((x).
In contrast, this paper considers the more challenging heterogencous setting [Jin et al. 2023 Sun
al. 2023). where data distributions can vary significantly across nodes.
For sign-based methods in distributed settings, each node computes gradient estimator v and transmits its sign, i.e., (vg), the parameter server. Note that the server can not directly send aggregate information Σn= Sign(v?) back to each node, since loses binary characteristic after summation. natural solution to apply another sign operation update the decision variable as:
X 17 Sign
Σ n
Sign
This process is called majority vote [Bernstein et al. 2018 each worker votes on the sign of the gradient, with the server tallying these voles and broadcasting the decision back the nodes. However, the sign operation introduces bias in the estimation, and employing it twice can significantly amplify this bias, particularly in a heterogeneous environment. Previous analysis (Chen et al. 2020) indicates that signSGD fails to converge in the heterogeneous setting. To deal with this problem, we introduce an unbiased sign operation SR(-), which is defined below.
Definition For any vector with ||v| S R, define the function mapping Sx(v) as:
+1, with probability } + 2R
[v]
[Sx(V))a
(5)
1. with probability 1 [v]. 28
Remark:
This operation provides an unbiased estimation of /R, such that
It
worth noting that the function mapping valid when || S R, since the probability should
always fall within [0, 1]. For this purpose, we need to further assume that the gradient is bounded.
7

---

Utilizing this unbiased sign operation, we can update the decision variable as:
n Sk( Sa(v?)
Xt-1 x, - Sign
7
After applying Sx(-), the output is sign information, which can be transported between nodes efficiently. The complete algorithm, named SSVR with majority vote (SSVR-MV), is described in Algorithm (with Option 1). Note that in Step 4, we set vi [x((x;;; when I = 1. Next, we present the convergence guarantee for the proposed algorithm with the following assumption.
Assumption For each node j. the stochastic gradient is bounded by G in the infinity norm, such that [V (x: =0 G.
Theorem Under Assumptions and by setting B = and n O ( our SSVR-MV method (with Option 1) ensures:
d=/22 d
E [[+
71/2
n²/22
Remark: Our rate is better than the previous result of (dT 1/4 + dn dn-1/22, and also outperforms the rate of ((d8/2T-211 dn 1/2) under the second-order smoothness [Sun al. 2023
Although the above convergence rate is superior to previous results, we have to note that the gradient even T
does not converge operation with the Si)+) mapping, as defined in equation (5) with R = 1. Additionally, in our prior analysis, we ensured that each v is bounded by assuming the stochastic gradient is bounded and using a constant 3. Here, we instead suppose that the true gradient is bounded, as detailed below.
To address this issue, propose replacing another sign
Assumption 4' For each node j. the gradient bounded such that [x)] S G.
Remark: This assumption is weaker than the one used by Sun et al. 2023 which assumes all stochastic gradients are bounded, i.e., (x; E)ll S G.
To ensure each gradient estimator is bounded, we employ a projection operation v Hl [v]]. where IIg denotes the projection onto ball of radius G. This allows us utilize an unbiased sign mapping (V(V)) before transmission to the parameter server. The revised algorithm is presented in Algorithm 3 (with Option 2), and the modifications lie in Steps and 9. We now present the convergence guarantee for this modified approach below.
Theorem Under Assumptions I 2 and 4
by setting 5 0 (ptba))) and rj O ( our
SSVR-MV method (with Option 2) ensures:
d//4
E
II|
O
T1/4
Remark:
This rate converges previous results of (1///8T-1/8) [Jin et al. 2023]. Our result is also better than the (1///2111/1) convergence rate obtained by Safaryan and Richtarik [202T], whose algorithm requires transmitting Σj= sign(v)) v/) back to all nodes, which is actually not sign information anymore.
T 00, and offers significant improvement the
5 Experiments
In this section, we assess the performance of the proposed methods through numerical experiments. We first evaluate the SSVR and SSVR-FS algorithms within the centralized setting, and then assess the performance of SSVR-MV method the distributed learning environment. All experiments are conducted on NVIDIA 3090 GPUs.

---

1.00
Taining loss
0.75
Graßeen norm
Testing accuracy
0.50
0.25
860
Epoch
Epoch
Epoch
signSGD
SignSGD-SIM
SignSVRG
SSVR
SSVR-FS
Figure 1: Results for CIFAR-10 dataset in the centralized environment.
Testag socueazy
Toul aucusracy
Triinin
Epoch
Epoch
Epoch
Ipoch
(a) Majority vote with 4 nodes
(b) Majority vote with 8 nodes
Sign
Signum
SSDM
Sto signSDD
MVnnig SIM
SSVR-MV
Figure 2: Results for CIFAR- 100 dataset in the distributed environment.
5.1 Evaluation of SSVR and SSVR-FS methods in the centralized environment
To begin with, we conduct numerical experiments multi-class image classification tasks validate the effectiveness of our proposed methods. Concretely, we train a ResNet18 model [He et al. 2016) the CIFAR-10 dataset [Krizhevsky] 2009]. We compare the performance of our SSV V and SSVR-FS methods against signSGD [Bernstein et al.] (2018). signSGD -IM [Sun et al.) 2023). and SignSVRG [Chzhen and Schechtman 2023]. For syyper-paraeed recommendations from the original papers or employ grid search to determine the best settings. Specifically, the momentum parameter is searched from the set (0.1, 0.5, 0.9, 0.99), and the learning rate fine-tuned within the range of (1e-5, 1e-4, le 1e-3, le-2, 1e-1).
tuming, either follow the
The training loss, gradient norm, and testing accuracy presented in Figure with curves averaged over five runs. We observe that methods exhibit a rapid decrease in training losses, with methods showing more pronounced reduction in the gradient norm. In terms of testing accuracy, our SSVR algorithm outperforms other sign-basee methods, and our SSVR-FS method achieves superior accuracy in the final epochs.
Results.
5.2 Evaluation of SSVR-MV method in the distributed learning
Subsequently, we conduct experiments to evaluate the effectiveness of the SSVR-MV method in the distributed environment. Specifically, we train a ResNet50 model [He et al., 2016 on the CIFAR- 100 dataset [Krizhevsky] 2009] with 4 and 8 nodes respectively. We compare the performance of our method against signSGD (with majority vote) [Bernstein et al. 2018), Signum (with majority vote) [Bernstein et al. 2019), SSDM [Sataryan and Richtarik] 202 Sto-signSGD (Jin et al. 2023 and MV-signSGDDSSIM [Sun et al. 2023]. The syper-parameter tuning follows the same methodology in the centralized environment experiment.
Results. We plot the training loss and testing accuracy Figure 2 with all curves averaged over five runs. The results indicate that the training loss of our SSVR-MV algorithm decreases rapidly, and our method obtains higher testing accuracy compared to other methods, both in experiments with nodes and 8 nodes.

---

6 Conclusion
In this paper, we explore sign-based stochastic variance reduction (SSVR) methods, which use only the sign information of puriance-reduced estimators to update decision variables. The proposed method achieves an improved convergence rate of (( surpassing the O(d4/2T-1/1) convergence of signSGD methods. When applied to finite-sum problems, this rate can be further enhanced to O(m
convergence rate of SignSVRG. Finally, we investigate the SSVR method in distributed settings and devise novel algorithms to attain convergence rates of (dd + dn- 11/2) and (d'//ap-1/4) which improve upon the previous results of OdT dn - 1/2) and (d8/87--13) 1/8) respectively.
which is also better than the
Acknowledgements
This work was partially supported by NSFC (62122037), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. 0231).
References
Y. Arjevani, Y. Carmon, J. C. Duchi, J. Foster, N. Srebro. and B. E. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):165-2141 2023.
J. Bernstein, Y.-.. Wang, K. Azizzadenesheli, and A. Anandkumar. signSGD: Compressed optimisa- tion for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning, pages 560-569, 2018.
J. Bernstein, J. Zhao, K. Azizzadenesheli, and A. Anandkumar. signSGD with majority vote is com- munication efficient and fault tolerant. In International Conference on Learning Representations, 2019.
T. Chen, Y. Sun, and W. Yin. Solving stochastic compositional optimization is nearly easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021.
X. Chen, T. Chen, H. Sun, S. Z. Wu, and M. Hong. Distributed training with heterogeneous data: Bridging median- and mean-baset algorithms. In Advances in Neural Information Processing Systems 33, pages 21616-211 21666, 2020.
Z. Chen, Y. Zhou, Y. Liang, and Z. Lu, Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In Proceedings the 40th International Conference on Machine Learning, pages 5396-5427, 2023.
E. Chzhen and S. Schechtman. SignSVRG: fixing SignSGD via variance reduction. ArXiv e-prints, 1.Xiv:2305.13188 2023.
A. Cutkosky and Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15210-15219, 2019.
A. Defazio, F. R. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems 27, pages 1646-1654, 2014.
C. Fang, C. Li, Z. Lin, and T. Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems 31, pages 689-699, 2018.
M. Faw, Tziotis, C. Caramanis, A. Mokhtari, Shakkottai, and R. Ward. The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pages 313-355, 2022.
Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, (614))2341-2366 2013.
10

---

K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
W. Jiang, G. Li, Y. Wang. L. Zhang, and T. Yang. Multi-bloc--sngle-roote variance reduced estimator for coupled compositional optimization. In Advances in Neural Information Processing Systems 35, pages 32499-32511, 2022a.
W. Jiang, B. Wang. Y. Wang, L. Zhang, and T. Yang. Optimal algorithms for stochastic multi-level compositional optimization. In Proceedings of the 39th International Conference on Machine Learning, pages 10195-10216, 2022b.
W. Jiang, J. Qin, L. Wu, C. Chen, Yang, and L. Zhang. Learning unnormalized statistical models via compositional optimization. In Proceedings of the 40th International Conference on Machine Learning, pages 15105-15124, 2023.
W. Jiang, S. Yang, Y. Wang, and L. Zhang. Adaptive variance reduction for stochastic optimization under weaker assumptions. In Advances Neural Information Processing Systems 37, 2024a.
W. Jiang, S. Yang, W. Yang, Y. Wang, Y. Wan, and L. Zhang. Projection-free variance reduction methods for stochastic constrained multi-level compositional optimization. In Proceedings of the 41st International Conference on Machine Learning, pages 21 21962-21987, 2024b.
R. Jin, Y. Huang, X. He, H. Dai, and T. Wu. Stochastic-Sige SGD for federated learning with theoretical guarantees. ArXiv e-prints, arXiv:2002.10944) 2023.
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances Neural Information Processing Systems 26, pages 315- 1133,22, 2013.
S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning, pages 3252-3261, 2019.
A. Kavis, S. Skoulakis, K. Antonakopoulos, L. T. Dadi, and V. Cevher. Adaptive stochastic variance reduction for non-convex finite-sum minimization. Advances in Neural Information Processing Systems 35, pages 23524-23538. 2022.
A. Krizhevsky. Learning multiple layers of features from tiny images. Masters Thesis, Deptartment of Computer Science, University of Toronto, 2009.
L. Lei, Ju, J. Chen, and M. I. Jordan. Non-convex finite-sum optimization via sesg methods. In Advances in Neural Information Processing Systems, volume 30, pages 2345-2355, 2017.
7. Li, H. Bao, X. Zhang, and P. Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, pages 6286-6292 2021.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takac. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning, pages 2613-2621, 2017.
7. Qin, 7. Liu, and P. Xu. Convergence of sign-based random reshuffling algorithms for nonconvex optimization. ArXiv e-prints, arXiv:2310.1553 15976, 2023.
J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In Proceedings of The 33rd International Conference on Machine Learning, pages 314-323, 2016.
N. L. Roux, M. Schmidt, and F. R. Bach. A stochastic gradient method with exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems 25, pages 2672-2680, 2012.
M. Safaryan and Richtarik. Stochastic sign descent methods: New algorithms and better theory. In Proceedings of the 38th International Conference Machine Learning, pages 0224-9234, 2021.
11

---

F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training speech DNNs. In Conference of the International Speech Communication Association, pages 1058-1062, 2014.
S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(16)5567-55) 2013.
T. Sun, Q. Wang, D. Li, and B. Wang. Momentum ensures convergence of SIGNSGD under weaker assumptions. In Proceedings of the 40th International Conference Machine Learning, pages 33077-33099, 2023.
M. Wang. E. X. Fang, and H. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2): 419, 2017a.
M. Wang, J. Liu, and E. X. Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 1s:105:1-10:::: 2017b.
Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. SpiderBoost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems 32, pages 2406-2416, 2019.
D. Yu, Y. Cai, W. Jiang, and L. Zhang. Efficient algorithms for empirical group distributionally robust optimization and beyond. In Proceedings of the 41st International Conference on Machine Learning, pages 37384-57411 2024.
H. Yuan, X. Lian, C. Li, J. Liu, and W. Hu. Efficient smooth non-convex stochastic composi- tional optimization via stochastic recursive gradient descent. In Advances in Neural Information Processing Systems 32, pages 14905-14916, 2019.
J. Zhang and L. Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 131-111 2021.
L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full gradients. In Advances in Neural Information Processing Systems 26, pages 980-988 2013.
D. Zhou, P. Xu, and Q. Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of Machine Learning Research, 21(103):1-63, 2020.
12

---

A Proof of Theorem 1
Firstly, note that Assumption indicates that the objective function f(x) also T-smooth Li et 2021 Given this property, we have that
f(x++1)
L $ f((x) + (VI( Xx+1 X1) ||(+1 xel1
sx(()) + (x)) Sign(v))) 1 [Sign(v))l
f(() + 7 (V (iggn(/((x))) Sign(v, vv))) [V Sign [(x))))))))))))))))))))))))))[ + r (6)
= f(x)) + (V Sign(v Sign(v:)) - - [xx )|1
2
S f(x)) 2n V v.l - /x)[(x))) + T
where the last inequality is due to the fact that
(ignxx), -Signvvv)))
- Sign((v))))
[ Sign((v)):))
2l[V/(x))] [ (()(()() * Sign((v.].)
f(x(f(x))l [
-2 (xxx)) velli
<2vd]V]((x) vell-
Summing up and rearranging the equation 6 derive:
T
E
V
fxx:)ll
T
f(x1)
f(xT+1)
nLd
+ +2dd E
f vell
(8)
T/T
A T
T [V((x))
nLd +
+ 2vd.
E
v.
2
where we define A, (xx) f., and the second inequality is due to Jensen's 's Incquality.
13

---

Next, we can bound the term
1 - [Vf - -ell²] follows.
E
V fxx++1)
Ve+1ll
B
B1
1
vxxx-1i (1- - 1
E
(1 3)ve+
B
B1
B1
E
(1 - (v. (x(xx)) + 39-
( - vf(xi))
B
B1
B
+ [f(x)) - (x(++)) +
V f
Σ
((x
B1
B1
km
B
S (1 3)²B ||v, [ (/xx))))+++ +2
1
Vf(x;:
cl
(x(xx)
B
k=1
2E
V
V.((xr
ch
B1
233²0²
22221
Xx+1
-Xel Xx|
<1 -) [llve fx(()))
+
B1
B1
233²0²
22221/dd
$ (1 B)F [lvv [
B1
B1
[(3,, E (V](xi: - -V/(xx) + (x(x))
where the first inequality is due to the fact EE
- (xx+x) +
1 B. E. (( - Vx (fxx;:+++)) {(+1)) 0, and (a + 6)2 - 2a + 26
Summing up and noticing that we use batch size of Bg in the first iteration, we can ensure
E
T Σ lv.
1
V
E
|| - [x(111?
20
+
2T,2
BT
B1
(9)
20 2T.2
BO
Bi
3Bi
Incorporating the above into equation (8) and setting that = 0 (T-2/3),
- 0d 2/3).
Bo = 0 (T1/3), Bi = O (1), we observe:
T
AS n/T
+ nLd
E
v (x,))1
<
+2Vd
E
|V
-vel3
T
T
t=1
AS n/T
o²
2023
2L21Rd
nd
<
+ +2vd
BOST
B1
3B,
2
(A, +
a + L)12
= 0
T1/3
1/2
T1/3
which finishes the proof of Theorem 1
B Proof of Theorem 2
To improve the convergence rate for finite-sum structures, we can reuse the results of equation (8. but
bound the term + E' [[V[(x)) - v. differently. Since V, = (1 - --) + Bh, + (1
14

---

(x), (x4-)),, where h, (x)( (x,,(x, + Vf(x)), we have:
E [V ve+21l
E [I(1 - B)v, + 3h++1 + (1 (Vi,,, V. (/)00++)(
E [](1 -V(v:VV[(x)))+) (
+(1 8)
+
(iitti [1a]
1 (1 - 3)²8 | V[ + 2 |||b4+1 - vf(xx+1)]1
+ 2(1 ( + (i Viiej [x)]1
< (1 - 8)²B - V/<x) [llb++1 - VS((x+1)11)
+ 2(1
- Viinn (x.)111
< (1 || [||v: V 2,2 [[h44] fx((++1)) 1|1] )[(] + 2 [[xx++1 x3|1a]
$ (1 - 3) [lvv- - v + 2/ L [||x++1- - x, [|2] + +2L [||x+1 - xel1
where the last inequality is due to the fact that:
E h.+1 1((x++1)11 =E [|| fi,_ (x++1) - Viitti (x+) ) + [f(x,) - Vf(x++1)11)
<B ||| ( - V Viitti (x,)
< ||xx+1 x, 112)
By rearranging and summing up, we establish:
T
E
[V
v.ll
T
[|v1
vx(11)11
2L E
2
X
x+11
xx+1
x,l1
3T
T
B
T
T T
21
12,T2TT2
Xx+1 - xt|12
+
TF
xt+1
xel1
B
T
1
221,
(112 +
r22d.
3
where we use full batch in the first iteration, and the second inequality due to the fact that
T
T
T
X
x =
Xi+1 - xi)
X - x
T
T
1=T
Xr+1 - x=112.
Incorporate the above into equation and setting I = m, B O (1), and 17 = O (mira refine the bound as:
[V((x))]1
A +Vd.
[V(xx) vell? nLd
E
E T
T
nTT
A5 nT
(BR+ + 1 8) 1
nld
+2vd.
v2ra
2
(A, + L) L)m-/4a412
=0
71/2
m
1/2
T1/2
15

---

C Proof of Theorem 3
By setting 3 = 2. we can ensure that vi I R = 4G, since
= =1(1 -1-1)v/ + vf(x( - (1 -115)
5(1 - 5) 1/-1 + -2- B)G
5(1 - -)- |
+ +2 - B)G > -1-
8=1
<G 12 - B)G
< 4 R.
Since the overall objective function f(x) is L-smooth, we have the following:
L
f(x++1) sf(x), + (V fxx,) x,41
xx)
|
-x,l12
2
17² Ld
<f(x.) 11 Vx((x)), Sign
SR(vi)
11
11 fxx)(())))) Sign((f(xx))) + T2
1
1 n
)
1f
=f(x) + 11 v/((x)), Sign (x(()))) Sign
Σ
Sn(v\)
n i=1
2
vf(x))
1 n
1d²Ld
sf(x)) + 2nRV
Sa(v\)
V f
-
17
n j=1
(10)
where the last inequality is because of
V (ign)))))) Sign
1
Σ Sa(vi)
n2
1))
Sign Sign
Σ SR((Z)
n
( Sk(vI)
2R [ (x))) R I (ign((V[(xx)))) # Sign
1))
Vf(x)):
12
n
2R
SR(v!)
1 [iggn(VV((())) Sign
Σ
SR(V?)
j=1
fx(())
n
2R
Sk(v!)
n
fxx,)
n
vx(x))
1 n
=2R
SR(v!)
< 2RVd
Σ
Sn(vi)
R
n
n j=1
j=1
(LI)
16

---

Rearranging and taking the expectation over equation (00 we have:
E [[f(x++1)
-((x)]
(x(x))
1
If
<2nRVdE
Sk(v))
mB V
(xx))111+
+
R
71
2
j=1
(xx)))
n nR
1
v/
S2nIRVdB
+
2n
SR(v?)
R
R
j=1
+ Ld
- [xx])V((x))ll]1+
2
1 Σ
1
7 Sn(v²)
<2la dR
V((xx)
v
+ Ry d
E
Sn
R
/=1
- -n [1] f 1111 + Ld
(12)
2
/2n dE
(x(x)
1
v
+ 2nRV d
1
Σ
E
Se(vv)
- v2
n j=1
n² 5=1
R
+ Id
-> ff
2
- Σ
1
(savvee 2
<2 dB
[xxx))
v
+ +2nRVd, d
Σ
E
n2
"1 1=1
Ldddd
-nE
[IV
<DnVEE
[((xx))
1
Σ
v
2nd
mB
((x)()
n j=1
Vn
where the third inequality is due to the fact that (E) < E [x and the forth inequality is because of E
S v?
x as well as the S operation in each node is independent.
Rearranging the terms and summing up, we have:
E B[IVS[(x)II]]
AS
2V
V((xi)
1
2dR
nLd
T
T
7
Vn
2
27
< n
+
2vd
E
1 T
v/(x,)
v
+
2dR
+
LL
11
Vn
2
1=1
where the last inequality is due to Jensen's 's inequality.
For each worker j. we have the following according to the definition of v/:
v 41 (x,(x)+1) = (1- (v(-vv()x)) + 3 (Vit(x (xf((x+1))
-31-3) (VIg(x++1iSLL) ((z(x(:((41) Vx)(x.) -VI((x+1))
17

---

Summing over {n} and noting that vf(x) n/ E (x)()), we can obtain:
n
V (x(++11)
1
V v(z(((+)))
L+1
71
71 j=1
j=1
n
n
=(1 (3) n j=1
Σ
v2 -Vz(xi)) + 3 Σ
j=1
+ (1 3)
1
Σ
n2
(x(+i -ff vfz(x)) - (f((()))))
i=1
Then we have
V (x((++1)
V+1
π
<(1 ")
1 Σ
v! vfz(xi))
+
+232
1
E
V (x0t1:4(1)) -
n²
j=1
+ 2(1 - B)2 8))
Σ
5 (xx+1:
(Xx((x
1=1
28202
2L
<(1 B)L
Σ (v) (x)()))
||xc+1 - xel1
2,82 02
2T.2
Σ v! - vf(x,)
5(1
B)LE
+
+
By summing up and rearranging, we observe
vs(xi) 2
1 f=== v
2023
212n12
E
vs(x))
T
BT
n3
(13)
0²
2023
ndd
n,TT
n
n1
Finally, by setting and 1) O (T-1/2
we ensure that
1 T
AS
2dR
Ll
[x(x))l
<
+
2vd
E
V
T
TT
Vn
2
T
i=
A
2dR
Ldd
o²
2023
2Ld
<
+ 2V
+
nT
Vn
2
n&T
n3
d1/2
0
71/2
1/2
18

---

D Proof of Theorem 4
Due to the fact that the overall objective function f(x) is I-smooth, we have the following:
T. 2
f(x+11) (x(x)) + (Vf(x,), X
xx)
||x++1
-x,l1
Lddd
5f(x;) - 17 S1
Σ
So(v))
11 j=1
Σ sc((1)) )) )) - IPLd
=f(x)) +1 V)(x)) - S1
n
Taking expectations leads to:
(xx+1)) [xx)]
||
V [(xx), 1
7 v/((x)) Si
1 Σ
so((t))
ق [IV
+ 11²Ld
2
1=1
1)
In
V f((x); V[((x))
Σ
Sc((:))
" E [ ||] +
1²Idd
G
2
j=1
SnB
V f((x), T f(x))
1
Σ
7 E
| [2]
+ LLLd
(14)
nG
G
2
==l
InB
1
[
+
Vf(xi)
Σ m/
n
E
[1T
+
TT
2G
2G
G
2
j=1
1 n
.PLd
Σ 1)
E
[x(x))
Σ
11 2G
E
[[V |1²]
2G
n
Rearranging the terms and summing up:
1
Σ
E
24,G
+E
1
[x(x))
1 Σ 8!
+ ILdG
T
nT
T
12 ,=1
2
V (x)(x,) .!1?
+E T/
+nLG
T
j=1
24yG TT
[zz(x)) - 1o [v]]]] + LJG
+E
T
2 T/
Ví5(x,) -v v3!
+ E
Σ j=1
+TI.G.
T
where the last inequality is due to the non-expansive property of the projection operation.
For each worker j. according to the definition of v/, we have:
v 41 (fz(((+1) = =(1 (1- B) (v/-vvvvvx vzz(x)) + 3 (Vf)(xH11:4441 - -1f(((+11)
(1 (3) (VI5(x++1:SLL) V5z(x(:((41) + V))(x)) - -VI((x+1))
19

---

Then we have
E r+1 (x)((x+)) 19
s(1 - B) 11 - (x))
+ +209F [1( ([(F)(( - v((((((11)) 1
+ +111 B) Viff (x 1241) (()(x((((+1) |
<(1 - 3)B
v/ (x) /
+2320² + +2L2 | - x1 1
5(1-9)B 9)B
V (x, /
+23202 + 2L2
As result, we know that
T v
+ 20²2 3+ 21'npd
E
S BT
Finally, combining the above and setting that 0 bound:
T1/ ) 11 O
(2:75177)) ) obtain the final
T
T
E
[xx()l
E
T
T
1=1
2
a²
+
nLdG
+ 20 +
T/I
3T
B
(Varz (A, L) + σ2 + L
T1/2
d!/4
0
T1/4
E Results under weaker assumptions
In this section, we demonstrate that our proposed methods can maintain similar convergence rates under less stringent assumptions expected a-symmetric smmrrlized-ssmothheee [Chen al. 2023] and affine variance [Faw et al. 2002]. We first detail these relaxed assumptions below.
Assumption 1' (Expected a-symmetric generalizeddsmoottees))
Eg [IV)((;)) V < ||x -y (To
)
27
Tn max [V]((x)))]1 0.10
where = Ax + (1 -)y, and 0 < < 1. Assumption 2' (Affine variance)
Ex [[V [f()) < [[) +
Remark:
Assumption can be reduced to standard average smoothness (Assumption when L1 = O. Note that a-symmetric generalized-smooe functions not only include asymmetric and Hessian deaseann-based generalized-smood smooth functions, but also contain high-order polynomials and exponential functions [Chen et al. 2023]. Moreover, affine variance also weaker than Assumption 2 and can be reduced to it when I
We then demonstrate that these relaxed conditions are sufficient for our algorithms to achieve the same convergence rate.
20

---

Theorem Under Assumptions I' and 2' by setting that 3 O
T273 n
d'/3
Ol
((ाجアアي75 ) Bo
(()) B1 Odd), and denoting N the samples used, our SSVR method guarantees:
d2/2
E [[]]((x))l))
A1/3
Furthermore, we introduce the following relaxed assumption for the sinite-sum problem.
Assumption 3' (Generalized smoothness) For each i E f1,2, .., ,,,, we have
- - - x x-yl Lo Lo + L1 max [f(xx)]1))
8E
where == 0x + (1 - f)y, and 0 - 1
This assumption is weaker than the standard Assumption 3 can still achieve similar convergence under this relaxed condition.
We validate that our SSVR-FS algorithm
Theorem Under Assumption 3' by setting nj O(minf m 1//2///7 mid) 1), B O 1 ), and
m
= m, our SSVR-FS algorithm ensures:
221/22/22
md T
E [|[x((x))]
T1/2
When the iteration number T' large, the dominant term becomes (22222222/77-//3// which aligns with the results in Theorem
Remark:
E.1 Proof of Theorem 5
We first present some useful tools for analysis. According to Proposition in Chen et al. 20233 Assumption I' leads to the following lemmas.
Lemma For (0,1), we have:
f(x++1) (x(x)) + (VI(()), X1+1 Xx)
1
+ 2
xt-1
x1|1² (Ko K1 [xxlVf((x)]1 + - xx(
where Kg = Lo (2 + 1), Ki = L1 2 3a, K₂ 1 2 3a(1 -
2
For 1, we also have:
f(x++1) 55(x)) +
xi)
+ Xx+1 - x (Lu + L1 (xx))l exp (L1|x441 - xell),
Similarly, according the Proposition in Chen al. 2023 have the following guarantees.
Lemma For (0, we have:
[x v Vf(y < ||x (l + K, V/(::)) + K2Ixx + yyl
where Ko - Lo. K 2 L1. K (5L))
For 1, we also have:
[f(x vf(y:e)]1 < -
1 22 (xxp2])))) -
21

---

Then, we can begin our proof. For a E (0, according to Lemma
by setting 17 S d
we have:
f(x(+1)
$ f(xi) + (Vf(x), -xx)
+ 2 1=
11:11-x/) x:|1² (Ko + (= + 2K Xx+1 xx x=
s f(x)) + (V 1 Sign (v:))
+ 2
[x++1 xx|1 (Ko Ki (1 + [V]+[[ +
$ (xx) + (x)( (VggnV/((S (x+))) Sign(v:))
+ 2 Xi+1 x:I1² (Ko + K [1 [Vf( 2K₂)
= f(xx) + 11 (x() WV..ni//iiiiiii. (xx)))) Sin)(v:)) 7/ (xx)ll
1
+ |x[+1 x111 (Koo K1 + 2K2) + K | (x:))l
r ((K + K1 + 2K2) + K1 [V(x)))
$ fxx) / / + 2
where the second inequality is due to the fact that a < 1 and || - x.I1 rnd $ 1.
Rearranging and summing up, we then have
1
E
f(xiil
2vd- E
[V((x)
vzll
T
T
1=1
<oo
K1 2K2)
gdK1 2T
V fxx)ll
By setting 7) S minf
-/2
val ā.. }. get
T
20 nT
E
4vd- E
T ff(x))
vell
nn((Ko + Ki 2Kg).
(15)
For a = 1, according to Lemma and setting 1 I
we have
Liva'
1(x++1)
<((x)) + (V X - x.) +
2 [ - x1112 (Lu -.IVV exp (L1l|x++1 - -x(l)
<s(x)) + V X++1 x.) exp (1) 112d (Lo + (xx)\((x)II)
(x.) v.ll - (xx)ll 3rdd
+ +
(Lo + Li [(x))(()))),
2
where the second inequality is due to Ta ||x+1 xx1l E 1, and others follow the previous proof.
Rearranging and summing up, we then have
E
[xxx))
A 2dd
1
3ndLo
3rddh
T
E
[V((x)) - vell
+
V (xx))l
n
T
2
2T
By setting 1) S
3dl.1
we can get
24, nT
T
E
[xx,)))
+
4vd. E
V fx(,)) - -vall
+ 3ndLo-
(16)
T
T
22

---

Then we begin to bound the term E2 } - [Vf()) -vil].
According to the definition of Va-
we have:
B1
Vz - - -(1 (vc-1 - vf(xx-1)) +
(xxx vf(xi)
B
k=
+ (1-
Vs((; vf(xx-1((f) + -
B1 k=1
Denote that G. 1 Σ Bi
[xxx {t
V (x(xx= (X(x--))- and A.
k=1
Σ (Vf(x ) - V f(x))) By summing up, we have
Vf(x;) = (v - V
+ BA, + + (1--
=(1 - 8)- (v1 - Vf(xi)) + Σ (1 3) ". + (1 B) 1 (1 *G.
Thus, we can know that
B[[v: - vs(x))l 5(1 - [[]] - (x())]]
+ 3E
Σ (1-
+
B)E
-1- - 3)
Then give the following two important lemmas, and their proofs can be found in Appendix E.I.1 and Appendix 1.1.2 respectively.
Lemma
E
Σ (1
B)
A.
S
E1- 3)
1
11- g)2e-2A2
B
r
Σ
(1 -1-
VB
1=t+1-
Lemma
t
I (1 - 9)- Σ
E
Σ
-)-
<
1
Σ
2(1 3)2- 2,
B
V2d2L1
Σ
VBi
s=t+--r
23

---

Using these lemmas and setting = t, we then have
A
E
Σ
8)
3)2c-
Σ vB
B) [x))
B1
A
(1 - - E [x,,)l |||
BB
BB
aml
t
21 L
B)20-2 + V2dNLa
E
Σ
(1
G
Σ
-1 (x,)) |||
B₁
BBi
V2
Σ
(1- - [1x((x))
vBi
Combining above inequalities and setting 3 = nnv
we derive
T
E
fx(1)))
vell
T
T
T
(1
E || v((x))1
+ 3
E
Σ 8=1
(1
3)- A. s.
T 1=1
T
[=1
T
Σ E
Σ (1
GG
[=1
AVB
BT
VddnTa
T
13)-11
+
+
(1 -E [V)((,))
BB
VBI
VBB
VBI
BBi
AVB
2dn
3L
+
2dnnL
Σ (1 -B)²
T
T
E
(x)
3T
VB
VBB
VBI
VBi
T
AVB
22nLL3
r
2dmL4
+
E
f(x:))
BT
VB
BBB
VBI
VB,3
T
(A + 2Tgg)d/A4
r
2T
E
[(
TfT' /Bod
VBi
VBr
v B
T
For E (0, 1). by setting that
B. = 1,
B1 2 max
3 d//3
T2/3
") d1/6T2/3
and suppose that iteration number
T2 0(8),
24

---

then we can guarantee
E
(x(()l1
t=1
2
40
4(A + /2
+ nd((Ko + K1 + 2K²)
+
+
r/T
1/T BB
VBi
4var
4v22L
E
VBI
VBi
//6
00
E
V
fx+))l ||
T1/3
T
t=1
d
1
50
E
[vf((
T1/3
T
which indicates that
d'/6
E
Vf(x))]l
50
T
71/3
Note that the batch size for each iteration is B₁ (dd,, by assuming that N = B₁ * T, we know that the convergence concerning N
d=/6 T1/3
dL/2
d2/2
= =0
=0
(BiT)1/3
N1/3
Similar results can easily obtained for = 1, i.e. we can also guarantce the following for a
T
d'/6
E
fx(x))l
00
T
N1/3
E.1.1 Proof Lemma
We prove this lemma by mathematical induction.
When 0, we have the following:
E
Σ
3)-
A.
E
1
- B)
which satisfies the above lemma.
25

---

2) Then, suppose the lemma holds for = k. For r = k + 1, we have
E
Σ 11
E
Σ 11 =A
+ E
8)20-2 2A
(1 - 8)
(x,,))] [1.)
B ==1
s=t- 1-k VBI
1-k-1
E
Σ (1 11- + (1 8)
+
B)20-2A2
B1
Σ
(1 [1--))-
VB
#=++1-k
k-1
2
S S
RE
Σ
+ (1-
+ B
(1 3)
3) 2
Σ
(1 -
||]
B
#= 1-
k-1
<
Σ (1- (1-B))-a)
+ EE, (1 3)2k [+1
Σ (1
2)20-2
B
Σ
(1 - [1V](x)))]]]
VB
#=++1-A
E
k-
Σ (1 B)~ A
+ (1- 3)2k
12
+
1
11-
Bi
B
Σ
(1
11
VB
k-k-1
k+1
(1- 3T
E
Σ (1-
+ B -1- B1-333-221
+
E [1
v f
(x x) |I]
VB.
Σ
(1
|I |I
BB
s=t+-
--1
k+1
E
(1-)))
+
Σ (1 - (1-8))2-221
2)2
s=t-k VB (1 [I
Σ
B
where the second inequality is due to the Jensen Inequality.
E.1.2 Proof of Lemma 4
We prove this lemma by mathematical induction.
/ - B) (1-)
1) When r = 0, we can easily prove E' (1-
-1)
=E
26

---

2) Suppose the inequality holds for r = k. Then, for r = k + 1, we derive
E
Σ (1 B)
G
L-
<B
Σ (1 3)
+ Bi
2(1 - 2/
V2d1L1
Σ 3) E [[
+
VBi
s=++1-k
k (1- (L1-3)--GG Gs Σ(1
1
E
Be..
+
2(1 (111-)22 B)2+ 8)20-2122 21
B
V2dnLa
Σ (1- ([xx
+
/Bi
-
t-
2
E
E B
Σ
+
1
Σ
2(1 -
2
B
5=1
Ld
Σ
[1-
/BI
s
t-
2
1
<B
Σ
(1-
+
2(1
21
B1
a=1
Td
Σ (1- | (l.
+ VBi
s=t+1-k
E
Σ (1 - GG,
+11 - 3)20 [IGL_APP]
+
1
Σ
2(1 223
B1
2d
Σ (1 (1-8) (1-8)- - V (xx))l
VBi
s=t+1-k
--1
<E
Σ (1 3)-
+
2
(1 2 +
Σ
2(1 - -,
B
B1 ==1
V 2dn L4 (1 8)*
2dg
+
VBi E
[|| (x x|l +
Σ
(1 - 3) [
BBi
s=
k-1
2
k+1
E
Σ (1 - 1-
+
Σ
2(1 - 2,, 133
B #=1
V2d
Σ - |1 "| (x.))l
+
/B,
s=
27

---

where the third inequality is due to the following, for simplity we denote _ = G
1 B1
2
Bec-x
= -REIn
B
B1
V v((x--ii((+) V[ +
1 -
B
B j=1
Bi
1 B1
((xx)))) -V((x))11)
-2EE,- x
B 1=1
v -1
1 -
B
B1
BBe.
Bi
For a E (0, 1). denoting L3 = (Ko + Ki + K2)² 2 + K, and L3 = K2 + 13), we have:
B
Be, &
ki G x
V -
B
By
X x1- Roo Ki | [ + 12|1xx1 xI-k-1| 2
B
d
Bi
V |11
Ko + K1 + K2 + Ri
j=1
2d
(Ro R + R2)² + 277²d d
Σ
B1
2
B
[[
B1
B
j=1
dd
+ 2
(uu + kK, K2) K₂)²
+
K
(11+12)
+
B,
B1
2n/2
dL3
[x)x++)
B1
B,
where the second inequality holds by setting 7) S d-1/2 such that ||x x1- S nvdd S1.
For = 1, denoting I.3 = 3 (T8 + 2T7 and I = 6T, + T2), we have:
B
v - 2 -
Be_
(x
k
B
2
Bi
[| xi exp (1213 Ix- X, xx- 112)
<
X X1 X1-
+
B
6
Bi
Σ
12 +
BR j=1
6n'd dl
(L. + 2L + 22) V + +A2)
B,
dr2 2n dT
[
B1
B1
where the second inequality holds by setting 1) S /12zz
such that ||xx x1- 1227
28

---

E.2
Proof of Theorem 6
Similar to Lemma and we can have the following lemma for generalized individual smoothness.
Lemma For a E (0,1) generalized individual smoothness (Assumption 3' leads 10
+ (V)((x))xx(11 xx)
|x++1 11 (Ko + (l]lV(())]l + 2Kg X++1 x=)l===),
as well as where Ko = Lo (2 - + 1), =1:=1 2 3 K₂ == , 2 30(1 a) -
[VV[((x+1) - (xi(()))l - ||x-1 xxl1(Ko + K1 [xx)|]( K2||x4+ x1| x=)
Lemma For 1, generalized individual smoothness (Assumption 3' leads
f((x++1) (xx:)) + (V.f( X++1 -xx) xx)
+ 2 | - x (Lo + La L1ll VV f(x,))) exp (71 |x++1 xxll)
as well as
[V Vx((x))] ||++1- - x1 L1 [f(x) exp (L1 -xill.
Then, we can begin our proof. For a E (0, 1), according to Lemma
by setting 1) S <d= we have:
((x++1) - f(x))
m
M(x++1) 1 m
fi(x))
m
m7
(X;, Xx+1 -x,) | x,1 (K( + [(x))( -
(Vf(x)), 77 Sign(v:)) + |x++1 x:11 (Ko + K2 (1 + [V + +
< (x): Sign V f(x))) - -Sign(v:)) -
Sigg(((())))
2 ||x++] - -1 (Ko + Ki (1 ||V[((x)]l) + 2K2)
n (ign(())) SSinnvv)) // (xx))l
マタ ||x+ x ((Ko + Ki + 2K2) + Ki [|+/()))))
rdd
v.ll 2n -vll /V/l=)
2 ((Ko + Ki + +(2) + K1 [x))),,))),
where the second inequality is due to the fact that a < 1 and [|x141 x112 s r $1
Rearranging and summing up, we then have
E
1
[x)))
2vd
E
1
[V/(x,)
- -
T
T
(=1
nd(Ko
Ki
+ 2K2)
ndK1
V fxx))l
2T
By setting 7) S minf
1
}. we can get
' dk.
T
24, TT
1
E
Σ
[+f(()))
4vd.
E
V fx.)) - vell
nd(Ko + Ki + 2K2).
T
T
(17)
29

---

For = 1, by setting
1 3dL1
we can apply the very similar analysis and obtain
T
201 r/
T
[f(())) - -vell + 3ndLo-
+ 4Vd.E
(18)
T
+ - Vf(xx) - vell According to the definition of Vt. we have:
Then we bound the term E
-1--V//x-----111---</--=---) v/(x, + (h- VS(xx)
V, -
+ - 8) (V V/((x-1: + (1((x-1)- - - and A. h. - -VS(x)).
Denote that G. (VI(xx;))) - Vs((
V
By summing up, we have
Vi vx(x))
=(1 - (v - vf((x-1)) + _A, + (1 -1- B)
t
=(1 - 0)- (vi vf(xi)) + Σ (1 3) A. + (1 - -8 1 (1 - 83 "..
s=1
Thus, we can know that
E vl [xx))ll]
<(1 11-38)--BB [[]v - [xxii]1| BE
Σ 3)¹ 3)--" "A,
+ + B)E
Σ (1 3) GG
G.
B) A. || (1 B)E
|.
<BE
Σ (1 (1-
Σ (1 -1- ()-
where the first term vanishes since we use full batch in the first iteration.
Then give the following two important lemmas, and their proofs can be found in Appendix E.2. and Appendix E.2.2 respectively.
Lemma
E
Σ
1
A
<E
Σ
8) B)
Σ
2(1
3)20 1
8=1
+ Le
Σ
(1- (1-
s=t+1-r
Lemma
2 G)
E
Σ
(1 3) *G,
S
Σ 1)-B)
+ Σ 2(1 - 21
+ 22d
Σ
(1 (1- [|
s=++1-r
30

---

Using these lemmas and setting = t, we then have
Σ (1 3) A.
22 L3d
(1 B)2s 2 + L6 Σ (1- -IVxx
Ld
+ 2dn Σ 8) -f]]
V3
8=1
as well
E
Σ - (1--3) G
1=1
L2d
(1 3)20-2 2 + 22
3)
[xx)]l
2dn + v 2d (1 [ [IV]xx)
Combining above inequalities and setting 1/m and I m. derive
E
vell fxxx))
t
$
=
Σ
(1
~G
T
T
22d
<v /VddBnITs +
+ (V2dnBITS + V2d1Ls
vB
T
t=1
<v 2Ts + To7) + 2dn(To LB)
E B)$
E
[(IV)(())II]
T
<v 2dmmn + L7) + v 2ddmmnoLo + L8)
E
[II]s(x))]]
For (0, 1), by setting y min m///a/erva 8VZmd(Lot S. we can guarantee
T V (x
1=1
2
1 + qid( Ko + K1 + 2K2) + Add/2mn(1e 1.s + LT) + 4d/22mm(a Ls)
Σ E [[/\/(x;)
TT
1///2222
md
<0
E
T1/2
T
which indicates that E obtained for = 1.
[V
s 0
m 1//// md 7//2
+
Similar results can easily
T
T
31

---

E.2.1 Proof of Lemmal 7
We prove this lemma by mathematical induction.
1) When O, we have the following:
Σ (1 -))-)))--1
E
E
which satisfies the above lemma.
2) Then, suppose the lemma holds for k. For k + 1, we have
E
Σ 11 (1-
<
Σ (1 A,
Σ 2(1 211-317 2)
+ Le
Σ (1- BB 1IV
s-++--
k-
Eig k
Σ (1-))-
+
> 2(1 - 201-)22-1-11-12
+ v 22n
Σ (\-)"=1/
-- Σ
2
k + Σ
SE
Bi
+1-
2(1 2/
8=1
s=1
+ v I
Σ (1 B V[
#=
Σ - -
+ B.. [IA_-l]] + 2(1 2,
+ 2dn L1
Σ (1- B |1
1=1+1-
1
<E
Σ (1- 3) |
22 221133 +
Σ 2 9)22 21
+ /2dn - / V2dn
(1- -)
#=1+1-k
1-k-1
k+1
Σ (1 9)
+ Σ 2(1 - 2
1=1
+ <22dn Lo
Σ (1- BI
k
32

---

where the third inequality is due to the following:
-
||
- || fie ( Vi... + Vf((x)) [
- IE, [IV ( (x(-x)
Vla, . (x+))]
For (0,1), denoting that
L (Ko + Ki + K2)²
L KP
we have:
B || Vii (Xi-k) - V xx,,
< X - X, 21 (Ko + Ki [V + K2
-
(Ko Ki K₂ K1 [x/(xx+))))*
$ d + Ki + K2)² + 2//² 12 [V]
2n + 12 [Vx(()+)))++
where the second inequality holds by setting
n $ 1-121112
such that
X1- - 1
For 1, denoting that
L 9L3
1 9T
we have:
Bi_ ||| V (XL- V Vi (x.))
$ 1| - x 11 (B + L3 | f [x)
(exp L 1| x,
- xx,)
I 18 (I3 + L3 [
2 aL? + 2n aL [(xx-=))1
where the second inequality holds by setting
1
such that we have
- x =
TTdd
I
E.2.2 Proof of Lemma
g
We prove this lemma by mathematical induction.
1) When r r= 0, we can easily prove that
E
11-33--00
=
Σ (1
B)
33

---

2) Suppose the inequality holds for r = k. Then, for r = k + 1, we derive
E
Σ 1
GG
k
<E
Σ 11 B)- G,
+
2(1 B8 2) L3d
1=1
+ 22
Σ
(1 =) || )ll
-=++1- k
t-k
<E
E B
Σ G.
B)
> 2(1 -320--21213.
+ v 2d
Σ (1- --- f
--
k-1
=E
Ei, k
Σ (1-
+
> 2(1 - 2/20-211211
+ v Id
Σ (1 By [[)(()
s=t+1-k
k-
2
k
SE
E
Σ
(1- G)
+ Σ 2(1 - 2))
a=1
8=1
+ v Ld
Σ (1-8)) - fx
1=
k-1
=E
Σ (1 - 3)
+ - 3) |IGL_sP + + 2(1 - 2,20
|
#=1
+ v 2dn Lig
Σ (1 - 3)¹ / [xx))l
8=++1-
1-k-1
SE
Σ (1- B)
+ + 2
Σ
2(1 (01-33)
+ 22d -
V2dn
Σ (1- 3) /V (xx))1
8=1+1-k
1-k-
2 k+1
Σ (1 9) 10-
+ Σ
2(1 - L7d
s=1
+ 2d
Σ
k
34

---

where the third inequality is due to the following:
B
G
- (X - +
Vi (x(- - V Si, -/0--)----------
+
--) v/(xx->>)
2B,,-
(V (x)+k) - V (x
V
f() vf(xx
Ei, V (x)=x) Vii, (x k
(x- VV
S - Vi V (x -
For (0, 1), denoting L (Ko + K1 + K2) and L K3, we have:
Bin. || Vii (x 1) - V fi. (x (x))11
< X X 2| (Ko + Ki V (x+- + - -x-
r/d (Ko + Ki K₂ Ki V (x)
& 21 (Ko + Ki + K2) )² + 21 i [x(++=))]|
s 212 + dL +x(++
where the second inequality holds by setting 1) S 1/2 1/2 such that ||x X1-k-11 S - midds.
For
1, denoting L UL6 and L 9L1, have:
Ei. V fi (x1=x) V ( (x)=
< 2 2|1x - X Xt-k 2| [1 + L3 [[ (exp ( [x - xx-))
18 d [ 21 V (x++))))
dn? 2n d f
where the second inequality holds by setting 1) S VTça
such that we have ||xc X s
ndd S
F
Additional experiments
In this section, we present additional experiments on the CIFAR-10 dataset to validate whether the proposed SSVR method sensitive to hyper-parameters such as learning rate 77, momentum parameter (3, and batch size. Specifically, we fix the value of 3 as 0.5 and try different learning rates from the set (5e 3, le 3, 5c 4, 4, 5). Then, we fix the learning rate as Ie 3 and enumerate 3 from the set {0.3, 0.5, 0.7, 0.9, 0.99]. The results are reported in Figure and Figure 4 respectively, which indicate that our method insensitive to the choice hyper-parameterrs within certain range. Finally, we also try different batch sizes from the set (64, 128, 256, 512), and the results are shown Figure 5 It can seen that our algorithm does not necessitate large batches for convergence and is not sensitive to variations in batch sizes.
35

---

1.0
Testing accuracy
90
Training loss
85
0.5
80
75
0.0
70
50
100 Epoch
150
200
50
100 Epoch
150
200
0.005
0.001
f) 0.0005
7) 0.0001
0.00005
Figure 3: Results for CIFAR-10 dataset with different learning rates.
1.00
Testing accuracy
-00
Training loss
0.75
85
0.50
80
0.25
75
0.00
70
0
50
100 Epoch
150
200
50
100 Epoch
150
200
8
0.5
0.7
0
0.99
Figure 4: Results for CIFAR-10 dataset with different B.
1.00
Testing accuracy
90
Training loss
0.75
85
0.50
80
0.25
75
0.00
70
0
50
100 Epoch
150
200
50
100 Epoch
150
200
BS-64
BS=128
RS=255
RS=512
Figure Results for CIFAR-10 dataset with different batch sizes.
36

---

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: The claims presented in the abstract and introduction accurately represent the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to 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: The theoretical results demonstrated in the paper rely specific assumptions, which have been clearly stated in the main text.
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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 to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification:
The paper provides assumptions and proofs for each theoretical result.
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 or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The paper discloses the information necessary to reproduce the main experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy 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 possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
Due to privacy concerns and ongoing research, do not include the code.
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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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
/ ccipps.c/ppulli//guu /tte:///uuddde/oooSuuubbmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper describes the training and testing details.
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 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: [Yes]
Justification: The paper reports error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
39

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the relevant information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Ethics.
The research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is primarily theoretical paper with potential negative social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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.
40

---

The conference expects that many papers will be foundational research and not 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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 is 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?
Answer: [Yes]
Justification: The creators or original owners of assets used in the paper are properly credited and the license and terms of use explicitly are properly respected.
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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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 batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
41

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's 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: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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.
According the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to adhere to the NeurlPS 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.
42


Reviews:
[{"review_id": "R8TnPSJ66F", "reviewer": "Reviewer_hYmq", "summary": "This paper investigates the stochastic optimization problem and a special case of finite sum optimization problem. They propose the\nSign-based Stochastic Variance Reduction (SSVR) method, leveraging variance reduction techiniques, which improves the convergence rate of Sign stochastic gradient descent (signSGD) algorithm.\nFurther, they also study the heterogeneous majority vote in distributed settings and introduce two novel algorithms, whose convergence rates improve the state-of-the-art.\nNumerical experiments prove the efficiency of their algorithms and support their theoretical guarantees.", "questions": "1. How did you get the convergence rate of $O(m^{1/2}d^{1/2}T^{−1/2})$ for the SignSVRG of y? It seems that in their paper they claim $O(T^{-1/2}) convergence rate without $m$ and $n$ in the numerator. Did you calculate this result by yourself? Please provide discussions.\n\n2. There is another paper studying sign-based optimization (Qin et al. (2023)), the setting studied in this paper is the same as your problem (2).  Can you also discuss this paper and compare the results?\n\n\nReferences:\n1. E. Chzhen and S. Schechtman. SignSVRG: fixing SignSGD via variance reduction. ArXiv e-prints, 317 arXiv:2305.13187, 2023.\n2. Qin, Z., Liu, Z., & Xu, P. (2023). Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization. arXiv preprint arXiv:2310.15976.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written, with detailed discussion and comparision.", "weaknesses": "Some places of the paper need further clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive feedback! We will revise our paper accordingly.\n\n---\n\n**Q1:** How did you get the convergence rate of $\\mathcal{O}(m^{1/2}d^{1/2}T^{-1/2})$ for the SignSVRG? It seems that in their paper they claim $\\mathcal{O}(T^{-1/2})$ convergence rate without $m$ and $d$ in the numerator. Did you calculate this result by yourself? Please provide discussions.\n\n**A1:** Yes, the original paper does not explicitly state the dependence on $m$ and $d$, so we derived these dependencies ourselves. In Remark 2 of their paper, they indicate that $\\mathbb{E}\\left[||\\nabla f(\\bar{x}\\_{T^{\\prime}})||_{1}\\right]  \\lesssim  \\sqrt{\\frac{d}{T^{\\prime}}}  \\max \\left( ( f\\left(x_1\\right)-f\\left(x\\_{*}\\right)+1 ) / d, \\mathrm{P} \\right)$, where $T^{\\prime}$ is the iteration number. Consequently, to ensure $\\mathbb{E} \\left[ || \\nabla f(\\bar{x}\\_{T^{\\prime}})||\\_{1} \\right] \\leq \\epsilon$, we require at least $T^{\\prime}=\\mathcal{O}\\left( dP^2 \\epsilon^{-2}\\right)$. As mentioned in Lemma 4 of their paper, the algorithm may need to recompute the full gradient ($m$ samples) every $P$ round, resulting in a sample complexity on the order of $\\mathcal{O}\\left( d m \\epsilon^{-2}\\right)$. This leads to the overall convergence rate of $\\mathcal{O}\\left( d^{1/2} m^{1/2} T^{-1/2}\\right)$.\n\n---\n\n**Q2:** There is another paper studying sign-based optimization [Qin et al, 2023], the setting studied in this paper is the same as your problem (2). Can you also discuss this paper and compare the results?\n\n**A2:** Thank you for bringing this related work to our attention. We will cite this paper and provide a detailed discussion in the revised version of our paper. Specifically, the mentioned paper [Qin et al., 2023] focuses on the finite-sum optimization problem and investigates signSGD **with random reshuffling**, achieving a convergence rate of $\\mathcal{O}\\left({\\log (mT)}/{\\sqrt{mT}}+||\\sigma ||_1\\right)$, where $m$ is the number of component functions, $T$ is the number of epochs of data passes, and $\\sigma$ is the variance bound of stochastic gradients. By leveraging variance-reduced gradients and momentum updates, they further propose the SignRVR and SignRVM methods, both achieving the convergence rate of $\\mathcal{O}\\left({\\log (mT)\\sqrt{m}}/{\\sqrt{T}}\\right)$. In contrast, our method obtains a convergence rate of $\\mathcal{O}\\left({m^{1/4}}/{\\sqrt{T}}\\right)$, which enjoys a better dependence on $m$ than their methods.\n\n---\n\n**References:**\n\nQin et al.  Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization. 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JYxik8vHdX", "reviewer": "Reviewer_2Gd9", "summary": "This paper considers application of variance reduction to sign-based optimization, i.e., a setting where the algorithm can only access to $\\mathrm{sign}(\\nabla f(x^t; \\xi^t))$ at step $t$, in the smooth and nonconvex setting.\nBecause $\\\\{\\pm 1\\\\}$-valued vectors can be transmitted more efficiently than real-valued vectors, the sign-based optimization is considered to be useful especially in distributed optimization.\nWhile a naive SGD-type algorithm previously achieved the convergence rate of $O(d^\\frac12 T^{-\\frac14})$, the proposed variance-reduced algorithm yields the rate of $O(d^\\frac12 T^{-\\frac13})$ (measured by the $L_1$-norm of the gradient.)\nNext, they applied the algorithm to finite-sum optimization (with $m$ components) and obtained the convergence rate of $O(m^\\frac14 d^\\frac12 T^{-\\frac14})$. \nFinally, they applied these results to distributed optimization (the server received $\\\\{\\pm 1\\\\}$-valued gradient estimators from clients), with an additional technique called \\textit{majority vote} to obtain unbiased gradient estimators, and obtained improved communication complexities.", "questions": "### **On additional terms**\n\n- Why is the term of $md/T$ required in Theorem 4?\n\n- Why is the term of $d n^{-\\frac12}$ required in Theorem 5?\n\n### **On the difficulties to further improve the convergence rates**\n\n- In theorem 6, why cannot you improve the convergence rate into $\\mathrm{poly}(d) T^{-\\frac13}$?\n\n### **Assumptions**\n\n- Is it possible to weaken Assumption 3 to averaged smoothness, i.e., $\\frac1m \\sum_{i=1}^m \\\\|\\nabla f_i(x)-\\nabla f_i(y)\\\\|^2 \\leq L^2 \\\\|x-y\\\\|^2$", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### **The problem is well-motivated**\n\nSign-based optimization is an important technique to reduce computational / communication complexities in large-scale optimization. I think it is a natural attempt to apply variance reduction, which is a common technique to accelerate optimization, to achieve more efficient sign-based optimization.\n\n### **Improved convergence rate**\n\nOverall, the proposed approach improved the convergence rates of sign-based optimization, which I think solid contributions to the theory of optimization.\n\n- For stochastic non-convex optimization, the proposed algorithm achieves $\\min{1\\leq t \\leq T}\\mathbb{E}[\\\\|\\nabla f(x^t)\\\\|]\\lesssim d^\\frac12 T^{-\\frac13}$, which is an improvement from the $d^\\frac12 T^{-\\frac14}$ rate of SignSGD ([Bernstein et al., 2018](https://arxiv.org/abs/1802.04434)).\n\n- For finite-sum optimization, the proposed algorithm achieves $\\min{1\\leq t \\leq T}\\mathbb{E}\\[\\|\\nabla f(x^t)\\\\|]\\lesssim m^\\frac14 d^\\frac12 T^{-\\frac12}$, whereas the previous SignSVRG algorithm achieves the rate of $O(m^\\frac12 d^\\frac12 T^{-\\frac12})$ ([Chzhen and Schechtman, 2023](https://arxiv.org/abs/2305.13187). (I am a bit confused because Ii looks like there is no benefit of variance reduction for SignSVRG in terms of the dependency on $m$.)\n\n- For distributed optimization, the proposed algorithm achieves $\\min{1\\leq t \\leq T}\\mathbb{E}[\\\\|\\nabla f(x^t)\\\\|]\\lesssim d^\\frac12 T^{-\\frac12} + d n^{-\\frac12}$ or $\\lesssim d^\\frac14 T^{-\\frac14}$. The previous bound was $d T^{-\\frac14} + d n^{-\\frac12}$ ([Sun et al., 2023](https://proceedings.mlr.press/v202/sun23l.html)) or $d^\\frac38 T^{-\\frac18}$ ([Jin et al., 2023](https://arxiv.org/abs/2002.10940), in $L^2$-norm). This is achieved by a trick called majority vote, which stochastically maps the real-valued gradient vector (or $\\nabla f_i(x)$) into $\\\\{\\pm 1\\\\}$-valued vectors transmitted to the server.\n\n### **Experimental results**\n\nThe authors showed sufficient amount of experiments to verify the validity of the proposed methods (as a theory paper).", "weaknesses": "### **Technical novelty**\n\nVariance reduction itself is quite common in the optimization field so I am afraid that this paper might be a bit incremental. Section 3.3 (Results under weaker assumptions) looks redundant given Theorem 2, as there are no technical difficulty about weakening the assumption described. \n\n### **Hyperparameter choice**\n\nAlthough this is a common criticism, most variance reduction algorithm require a very careful hyperparameter tuning. It looks like the theoretical guarantees of the proposed algorithms also require a specific set of hyperparameters, and I am not confident in the robustness of the proposed algorithms to the hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments! We will revise accordingly.\n\n---\n**Q1:** Variance reduction is quite common in the optimization field so I am afraid this paper might be a bit incremental. Section 3.3 looks redundant given Theorem 2, as there are no technical difficulty about weakening the assumption described.\n\n**A1:** First, we want to emphasize that our Algorithm 1 is the first sign-based variance reduction method to improve the convergence rate from $\\mathcal{O}(T^{-1/4})$ to $\\mathcal{O}(T^{-1/3})$ (Theorem 1). Second, to deal with the finite-sum problem, we introduce a novel error correction term into our gradient estimator in Algorithm 2, making our approach distinct from existing methods. Furthermore, the corresponding guarantee (Theorem 2) surpasses the existing variance reduction method signSVRG. Finally, the proposed SSVR-MV algorithm and its corresponding analysis (Theorem 3 & 4) are also new, where we utilize unbiased sign operations and the projection operation in the SSVR-MV method. As a result, we believe our paper provides significant contributions beyond being merely incremental in the existing literature. \n\nRegarding Section 3.3, we agree it is not the main contribution of our paper and our intention is to broaden the applicability of our methods to a wider range of functions by relaxing assumptions. Moreover, there actually exists technique challenges in the analysis. For instance, in the previous analysis, we can bound $\\mathbb{E}[||\\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1})-\\nabla f(\\mathbf{x}_t;\\xi\\_{t+1})||^2]\\le L^2||\\mathbf{x}\\_{t+1}-\\mathbf{x}_t||^2\\le L^2 \\eta^2d$ with small $\\eta$. Under weaker assumptions, we can only ensure $\\mathbb{E}[||\\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1})-\\nabla f(\\mathbf{x}_t;\\xi\\_{t+1})||^2]\\le ||\\mathbf{x}\\_{t+1}-\\mathbf{x}_t ||^2(K_0+K_1\\mathbb{E}\\_{\\xi\\_{t+1}}||\\nabla f(\\mathbf{x}_t;\\xi\\_{t+1})||)$, which can not be bounded since $||\\nabla f(\\mathbf{x}_t;\\xi\\_{t+1})||$ is unbounded. To address this, we employed a different analysis, using mathematical induction techniques (see the proofs of Lemmas 3 and 4). Therefore, the analyses for Section 3.3 are more challenging. However, following your suggestion, we will consider moving Section 3.3 to the appendix.\n\n---\n**Q2:** I am not confident in the robustness of the proposed algorithms to hyper-parameters.\n\n**A2:** Following your suggestion, we have examined the behavior of our algorithm with different values of the learning rate and parameter $\\beta$. Initially, we fix $\\beta=0.5$ and vary the learning rate within the set {$5e-3,1e-3,5e-4,1e-4,5e-5$}. Then, we fix the learning rate at $1e-3$ and varied $\\beta$ within {$0.3,0.5,0.7,0.9,0.99$}. The results, which are reported in the **Global Response**, indicate that our method is not sensitive to the choice of hyper-parameters.\n\n---\n**Q3:** Why is the term of $md/T$ required in Theorem 4?\n\n**A3:** Compared to Assumption 3 used in Theorem 2, we use the weaker Assumption 3$^\\prime$ in Theorem 4, which includes an additional $||\\nabla f(\\mathbf{x}_t)||$ term. Consequently, this extra term appears in the analysis. In the final step, we have $\\mathbb{E}[\\frac{1}{T}\\sum\\_{t=1}^T||f(\\mathbf{x}_t)||_1]\\le\\mathcal{O}(\\frac{1}{\\eta T}+\\eta d+d\\sqrt{m}\\eta)+\\mathcal{O}(d{\\eta m})\\mathbb{E}[\\frac{1}{T}\\sum\\_{t=1}^T||\\nabla f(\\mathbf{x}_t)||_1]$. To cancel the last term, we set $\\eta\\leq\\mathcal{O}(\\frac{1}{md})$. As a result, we have $\\mathcal{O}(\\frac{1}{\\eta T})=\\mathcal{O}(\\frac{md}{T})$ in the convergence rate. \n\n---\n**Q4:** Why is the term of $dn^{-1/2}$ required in Theorem 5?\n\n**A4:** According to equation (15) on Page 29, we need to bound $R\\sqrt{d}||\\frac{\\nabla f(\\mathbf{x}_t)}{R}-\\frac1n\\sum\\_{j=1}^n S(\\mathbf{v}_t^j)||$. To this end, we separate it into two terms: $R\\sqrt{d}||\\frac{\\nabla f(\\mathbf{x}_t)}{R}-\\frac{1}{nR}\\sum\\_{j=1}^n\\mathbf{v}_t^j||$ and $ R\\sqrt{d}||\\frac{1}{n}\\sum\\_{j=1}^n(S(\\mathbf{v}_t^j)-\\frac{\\mathbf{v}_t^j}{R})||$. The first term represents the estimation error of estimator $\\mathbf{v}_t^j$ and can be bounded using a similar technique in Theorem 1. The second term leads to the $\\mathcal{O}(dn^{-1/2})$ term, since we bound it as:\n\\begin{align} R\\sqrt{d}\\mathbb{E}[||\\frac1n\\sum\\_{j=1}^n (S(\\mathbf{v}_t^j)-\\frac{\\mathbf{v}_t^j}{R})||]\\le R\\sqrt{d}\\sqrt{\\mathbb{E}[||\\frac{1}{n}\\sum\\_{j=1}^n(S(\\mathbf{v}_t^j)-\\frac{\\mathbf{v}_t^j}{R})||^2]}\\le R\\sqrt{d}\\sqrt{\\frac{1}{n^2}\\sum\\_{j=1}^n\\mathbb{E}||S(\\mathbf{v}_t^j)-\\frac{\\mathbf{v}_t^j}{R}||^2}\\le R\\sqrt{d}\\sqrt{\\frac{1}{n^2}\\sum\\_{j=1}^n\\mathbb{E}[||S(\\mathbf{v}_t^j)||^2]}\\le \\frac{dR}{\\sqrt{n}}.\\end{align}\n\n---\n**Q5:** In theorem 6, why cannot you improve the convergence rate to $\\mathcal{O}(T^{-1/3})$?\n\n**A5:** For Theorem 1, we obtain the convergence rate of $\\mathcal{O}(T^{-1/3})$ with the help of Assumptions 1 and 2. In theorem 6, although the proposed unbiased sign operation provides an unbiased gradient estimation, the obtained gradient cannot satisfy the average smoothness (Assumption 1), which is crucial for achieving the $\\mathcal{O}(T^{-1/3})$ converge rate. This is the main reason why we cannot further improve the convergence rate.\n\n---\n**Q6:** Is it possible to weaken Assumption 3 to averaged smoothness, i.e., $\\frac1m \\sum_{i=1}^m||\\nabla f_i(x)-\\nabla f_i(y)||^2\\le L^2||x-y||^2$?\n\n**A6:** Yes, it is possible. In the analysis, Assumption 3 is used to ensure $\\mathbb{E}\\_{i\\_{t+1}}[||\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{t+1})-\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_t)||^2]\\le L^2||\\mathbf{x}\\_{t+1}-\\mathbf{x}\\_t||^2$. With the averaged smoothness, we can achieve a similar guarantee. Since $i_{t+1}$ is randomly sampled from {$1,\\cdots,m$}, we have:\n\\begin{align}\\mathbb{E}\\_{i\\_{t+1}}[||\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{t+1})-\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_t)||^2]=\\frac1m\\sum_{i=1}^{m}||\\nabla f_i(\\mathbf{x}\\_{t+1})-\\nabla f_{i}(\\mathbf{x}\\_t)||^2\\le L^2 ||\\mathbf{x}\\_{t+1}-\\mathbf{x}\\_t||^2,\\end{align}\nwhich indicates the proof holds with averaged smoothness.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8jgG2wfaUQ", "reviewer": "Reviewer_Huhp", "summary": "The paper introduces an enhanced sign-based method called SSVR, designed to improve the convergence rate of signSGD with variance reduction techniques. SSVR achieves an improved convergence rate of $O(d^{1/2}T^{-1/3})$ for stochastic non-convex functions. For non-convex finite-sum optimization problems, the SSVR-FS method demonstrates an improved convergence rate of $ O(m^{1/4}d^{1/2}T^{-1/2}) $. To address heterogeneous data in distributed settings, the authors present novel algorithms that outperform existing methods in terms of convergence rates. The effectiveness of these proposed methods is validated through numerical experiments.", "questions": "1. Does previous work also require similar bounded gradient assumptions for the majority vote in heterogeneous settings? \n2. Is the performance of the proposed method sensitive to variations in batch size?", "limitations": "This paper does not present negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The proposed methods improves upon existing algorithms in complexities. The sign-based algorithms have broad applications in the ML community and may be of great interest in the field. \n2. The proposed sign-based variance-reduced estimator and stochastic unbiased sign operation are novel and efficient. They effectively reduce the gradient estimation error and are communication efficient, particularly for heterogeneous data in distributed settings.\n3. The experimental results on various datasets validate the effectiveness of the proposed methods.\n4. The paper is well-written, with clear problem settings and contributions. The proofs are also easy to follow.", "weaknesses": "1. The authors introduce the bounded gradient assumption (Assumption 4) for distributed settings. Why is this assumption necessary? Is it commonly used in previous literature for this setting?\n2. The description of Algorithm 2 is not very rigorous. The variable $\\tau$ in step 4 and $\\tau$ in step 10 seems different but used the same notation.\n3. Some typos:\n    - Line 98: \"signed-based\" --> \"sign-based.\"\n    - Line 247: \"Assumption 5′\" --> \"Assumption 5\" or \"Assumption 4′.\"\n    - Line 487: \"$S(v_t^j)$\" --> \"$S_{R}(v_t^j)$.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments and suggestions! \n\n---\n\n**Q1:** The authors introduce the bounded gradient assumption (Assumption 4) for distributed settings. Why is this assumption necessary? Is it commonly used in previous literature for this setting?\n\n**A1:** This assumption is necessary because the unbiased sign operation $\\operatorname{S_R}(\\cdot)$ defined in Definition 1 requires its input to be bounded such that $ ||\\mathbf{v}||_{\\infty} \\leq R $. To meet this requirement, we assume the gradient is bounded so that the norm of our gradient estimator $\\mathbf{v}_t^j$ is also bounded. Similar bounded (stochastic) gradient assumptions are also used in previous literature [Jin et al., 2023, Sun et al., 2023] for this heterogeneous distributed setting. \n\n---\n\n**Q2:** The description of Algorithm 2 is not very rigorous. The variable $\\tau$ in step 4 and $\\tau$ in step 10 seems different but used the same notation.\n\n**A2:** Sorry for the misleading notation. We will clarify this by replacing the $\\tau$ in step 10 with $\\varphi$ in the revised version. \n\n---\n\n**Q3:** Some typos.\n\n**A3:** Thank you for pointing out the typos. We will correct them in the revised paper.\n\n---\n\n\n**Q4:** Does previous work also require similar bounded gradient assumptions for the majority vote in heterogeneous settings?\n\n**A4:** Yes, as mentioned in A1, previous literature [Jin et al., 2023, Sun et al., 2023] also requires similar bounded gradient assumptions for this setting.\n\n---\n\n**Q5:** Is the performance of the proposed method sensitive to variations in batch size?\n\n**A5:** To answer this question, we conduct experiments with different batch sizes {$64, 128, 256, 512$}, and the results can be found in **Global Response**. As can be seen, the proposed algorithm is not sensitive to variations in batch size. \n\n---\n\n**References:**\n\nJin et al.  Stochastic-Sign SGD for federated learning with theoretical guarantees. 2023.\n\nSun et al.  Momentum ensures convergence of SIGNSGD under weaker assumptions. ICML, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l33prIPY3o", "reviewer": "Reviewer_XovB", "summary": "This paper introduces the Sign-based Stochastic Variance Reduction (SSVR) algorithm, which enhances the convergence rate of the traditional signSGD method. By incorporating variance reduction techniques with sign-based updates, the authors achieve a convergence rate of $O(d^{1/2}T^{-1/3})$ for general stochastic optimization and $O(m^{1/4}d^{1/2}T^{-1/2})$ for finite-sum problems. Additionally, the paper proposes novel algorithms for distributed environments by introducing the unbiased sign operation, resulting in superior convergence rates for heterogeneous data. Numerical experiments further validate the effectiveness of the proposed methods.", "questions": "1. Can you provide a more detailed discussion about the design of equation (3), especially the error correction term? The authors claim that \"This gap can be effectively mitigated by the error correction term we introduced in equation (3),\" but it remains unclear how it works based solely on the content in the main body.\n2. Could you provide additional experimental results to demonstrate the performance of the proposed SSVR method with different batch sizes?", "limitations": "The paper is theoretical and does not present potential negative societal impacts.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed methods improve the convergence rates over traditional signSGD methods and their variants, achieving faster convergence rates for general non-convex optimization and finite-sum optimization.\n2. The SSVR-MV algorithm developed in the paper is communication-efficient and well-suited for distributed settings. The obtained convergence rates significantly enhance previous results in heterogeneous settings.\n3. Numerical experiments validate the effectiveness of the proposed methods, demonstrating superior performance compared to existing sign-based optimization methods in terms of convergence speed and accuracy.", "weaknesses": "1. Given that signSGD methods typically require large batch sizes to ensure convergence, the authors should include more experimental results to demonstrate the dependency on batch size for the proposed methods. This would clarify whether the proposed method also necessitates large batches for convergence in practice.\n2. The authors introduce the stochastic unbiased sign operation in Definition 1, which differs from the traditional sign operation. It would be beneficial to provide a more detailed explanation of their differences and specify when the sign operation is preferred.\n3. There are some typos in the paper, as listed below:\n   - Page 2, Lines 44 and 45: $T^{1/2}$ should be $T^{-1/2}$.\n   - Page 3, Line 98: \"signed-based\" should be \"sign-based\".\n   - Page 5, Algorithm 2, Step 4: \"set $t=\\tau$\" should be \"set $\\tau=t$\".\n   - Page 9, Figure 2: \"SSVR\" should be \"SSVR-MV\".\n   - Page 28, Line 482: $f(x_t;\\xi_t^j)$ should be $\\nabla f(x_t;\\xi_t^j)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments!\n\n---\n**Q1:** The authors should include more experimental results to demonstrate the dependency on batch size for the proposed methods. This would clarify whether the proposed method also necessitates large batches for convergence in practice.\n\n**A1:** According to your request, we have included additional experimental results for different batch sizes {$64,128,256,512$}, and the results can be found in the **Global Response**. As can be seen, the proposed method does not necessitate large batches for convergence in practice. \n\n---\n\n**Q2:** The authors introduce the stochastic unbiased sign operation in Definition 1, which differs from the traditional sign operation. It would be beneficial to provide a more detailed explanation of their differences and specify when the sign operation is preferred.\n\n**A2:** The main difference is that the traditional sign operation produces a biased estimation of the original input, whereas the stochastic sign operation in Definition 1 provides an unbiased estimation. The disadvantage of the unbiased sign operation is that it requires the bounded gradient assumption to ensure the input of this operation is bounded. In the centralized setting, where the traditional sign operation already achieves improved convergence rates, we simply use it to avoid introducing additional assumptions. In heterogeneous distributed settings, where we need to use the sign operation twice, the traditional sign operation  can lead to large bias and worse convergence rates. Therefore, we use the stochastic sign operation to obtain better convergence rates in this setting. \n\n---\n\n**Q3:** There are some typos in the paper.\n\n**A3:** Thank you for catching typos. We will correct them in the revised version.\n\n---\n\n**Q4:** Can you provide a more detailed discussion about the design of equation (3), especially the error correction term? The authors claim that \"This gap can be effectively mitigated by the error correction term we introduced in equation (3),\" but it remains unclear how it works based solely on the content in the main body.\n\n**A4:** According to the analysis from Lines 379 to 380, we can bound the gradient estimation error as follows:\n\\begin{align}\n        \\mathbb{E}  \\left[ || \\nabla f(\\mathbf{x}_{t+1}) - \\mathbf{v}\\_{t+1} ||^2\\right] \\leq  (1-\\beta) \\mathbb{E}\\left[ ||\\mathbf{v}_t - \\nabla f(\\mathbf{x}_t) ||^2\\right]   + 2L^2 \\mathbb{E}\\left[||\\mathbf{x}\\_{t+1} - \\mathbf{x}_t ||^2\\right]  + 2\\beta^2 \\mathbb{E} \\left[||\\nabla f\\_{i\\_{t+1}}  ( \\mathbf{x}\\_{t+1} )  - \\nabla f ( \\mathbf{x}\\_\\{t+1} ) + \\nabla f( \\mathbf{x}\\_{\\tau} ) - \\nabla f\\_{i\\_{t+1}} ( \\mathbf{x}\\_{\\tau} ) ||^2\\right] \n\\end{align}\nNote that in the last term, $ \\nabla f(\\mathbf{x}\\_{\\tau})- \\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{\\tau})$ is the error correction term. Without this term, we would need to bound $ \\mathbb{E} \\left[||\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t+1})||^2\\right]$, which is hard to deal with without assuming $ \\mathbb{E} \\left[||\\nabla f\\_{i}(\\mathbf{x}) - \\nabla f(\\mathbf{x})||^2\\right] \\leq \\sigma^2$ for each function $f_i$. However, with the error correction term, we can effectively bound it as: \n\\begin{align}\n     \\mathbb{E} \\left[||\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{t+1}) - \\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{\\tau})  - \\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{\\tau})||^2\\right] \n    \\leq  \\mathbb{E}\\left[||\\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{t+1}) - \\nabla f\\_{i\\_{t+1}}(\\mathbf{x}\\_{\\tau})||^2 \\right] \n     \\leq L^2 \\mathbb{E}\\left[|| \\mathbf{x}\\_{t+1} - \\mathbf{x}\\_{\\tau}||^2 \\right].\n\\end{align}\nAs long as the learning rate is small enough and $\\tau$ is updated periodically, we can easily bound the above term.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## **Global Response** ##

---
In response to the request of reviewers, we provide additional experimental results in this part.

**Figure 1 \& Figure 2:** According to the suggestion of Reviewer 2Gd9, we provide the performance of our SSVR method with different hyper-parameters. First, we fix the value of $\beta$ as 0.5 and try different learning rates from the set {$5e-3, 1e-3, 5e-4, 1e-4, 5e-5$}. Then, we fix the learning rate as $1e-3$ and enumerate $\beta$ from the set {$0.3, 0.5,0.7,0.9,0.99$}. The results show that our method is insensitive to the choice of the hyper-parameters within a certain range.

**Figure 3:** As requested by Reviewer Huhp and Reviewer Xovb, we include experiments on the SSVR method with different batch sizes {$64, 128, 256, 512$}. The results indicate that our algorithm does not necessitate large batches for convergence and is not sensitive to variations in batch sizes.

Meta-review: This paper investigates the convergence of sign-SGD algorithms, with a focus on enhancing their performance through variance reduction techniques. The authors successfully improve the convergence rate of sign-SGD for stochastic optimization from \(O(d^{1/2}T^{-1/4})\) to \(O(d^{1/2}T^{-1/3})\). For finite-sum problems, the proposed approach further accelerates convergence by a factor of \(m^{1/4}\), where \(m\) represents the number of individual functions. Additionally, the paper demonstrates that this technique can be effectively applied to distributed settings, improving upon existing results in the literature.

The paper is generally well-written, presenting a solid contribution in the form of improved convergence rates over established methods. Following an in-depth discussion between the authors and reviewers, consensus has been reached that the paper is suitable for publication. I am also recommending acceptance of this paper. However, I have some additional comments that I believe could enhance the paper’s clarity and presentation, which I encourage the authors to consider in their final version:

1. **Clarification of Convergence Rate Definitions:**  
   The paper would benefit from a more detailed description of the convergence rate definitions used. Specifically, it would be helpful if the authors could clearly delineate the differences between this work and others in terms of convergence rate definitions—whether in terms of the norm of the gradient or the squared norm, and whether considering \(l_1\) or \(l_2\) norms. This clarification will aid readers in making direct comparisons between the results in this paper and those in related works.

2. **Discussion on Upper vs. Lower Bounds:**  
   In the introduction, the authors discuss lower bounds for stochastic gradient methods and finite-sum optimization. However, the upper bounds provided in the theoretical section are primarily for the \(l_1\) norm, while the literature often discusses upper bounds in terms of the \(l_2\) norm. The authors should add a discussion that addresses this discrepancy, clarifying that it is acceptable that there is no exact lower bound for the sign-based optimization setting.

3. **Comprehensive Discussion of Variance Reduction Techniques:**  
   Since SVRG plays a pivotal role in achieving the improved convergence results in this paper, the related work section would benefit from a more thorough discussion of key variance reduction algorithms such as SCSG [1], SDCA [2, 4], nonconvex SVRG [3], SNVRG [5], etc. 

[1] Lei, Lihua, and Michael Jordan. "Less than a single pass: Stochastically controlled stochastic gradient." Artificial Intelligence and Statistics. PMLR, 2017.

[2] Shalev-Shwartz, Shai, and Tong Zhang. "Stochastic dual coordinate ascent methods for regularized loss minimization." Journal of Machine Learning Research 14.1 (2013).

[3] Reddi, Sashank J., et al. "Stochastic variance reduction for nonconvex optimization." International conference on machine learning. PMLR, 2016.

[4] Richtárik, Peter, and Martin Takáč. "Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function." Mathematical Programming 144.1 (2014): 1-38.

[5] Zhou, Dongruo, et al. "Stochastic nested variance reduction for nonconvex optimization." Journal of machine learning research 21.103 (2020): 1-63.
Decision: Accept (poster)