Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction

Thank you very much for your constructive comments!

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.

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.

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.

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.

Q3: There are some typos in the paper.

A3: Thank you for catching typos. We will correct them in the revised version.

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.

A4: According to the analysis from Lines 379 to 380, we can bound the gradient estimation error as follows:

$

    \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] 

$

Note 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:

$

 \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] 
\leq  \mathbb{E}\left[||\nabla f\_{i\_{t+1}}(\mathbf{x}\_{t+1}) - \nabla f\_{i\_{t+1}}(\mathbf{x}\_{\tau})||^2 \right] 
 \leq L^2 \mathbb{E}\left[|| \mathbf{x}\_{t+1} - \mathbf{x}\_{\tau}||^2 \right].

$

As long as the learning rate is small enough and $\tau$ is updated periodically, we can easily bound the above term.

Thank you very much for your constructive comments and suggestions!

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?

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.

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.

A2: Sorry for the misleading notation. We will clarify this by replacing the $\tau$ in step 10 with $\varphi$ in the revised version.

Q3: Some typos.

A3: Thank you for pointing out the typos. We will correct them in the revised paper.

Q4: Does previous work also require similar bounded gradient assumptions for the majority vote in heterogeneous settings?

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.

Q5: Is the performance of the proposed method sensitive to variations in batch size?

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.

References:

Jin et al. Stochastic-Sign SGD for federated learning with theoretical guarantees. 2023.

Sun et al. Momentum ensures convergence of SIGNSGD under weaker assumptions. ICML, 2023.

Thanks for your constructive comments! We will revise accordingly.

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.

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.

Regarding 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.

Q2: I am not confident in the robustness of the proposed algorithms to hyper-parameters.

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.

Q3: Why is the term of $md/T$ required in Theorem 4?

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.

Q4: Why is the term of $dn^{-1/2}$ required in Theorem 5?

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:

$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}}.$

Q5: In theorem 6, why cannot you improve the convergence rate to $\mathcal{O}(T^{-1/3})$?

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.

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$?

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:

$\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,$

which indicates the proof holds with averaged smoothness.

Many thanks for the constructive feedback! We will revise our paper accordingly.

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.

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)$.

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?

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.

References:

Qin et al. Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization. 2023.