Simple Minimax Optimal Byzantine Robust Algorithm for Nonconvex Objectives with Uniform Gradient Heterogeneity

Thank you for your important comments.

About Weakness 1.

As you pointed out, the expression $\delta \leq (\zeta_\mathrm{max}/\zeta_\mathrm{mean})^2$ should be fixed as $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$ (please check the revision paper). We thank you for your pointing out these typos and apologize for them, but, they are simple systematic typos and do not affect the proofs given in Sections A and B.

About Weakness 2 and Question 1

We believe that $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$ is reasonable because $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ is not too small in practice. In fact, after reading your review, we conducted additional experiments to address the concern that $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ is very small in practice. Specifically, we examined the empirical values of $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ on the settings of Section 6 and additionally on Fed-EMNIST, which is a real FL dataset. The experimental results can be found in Section E of the revised paper (p.36). From Figure 14 in Section E, we can see that $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ was in $0.5 \sim 0.93$ on MNIST and CIFAR10, and was in $0.34 \sim 0.70$ on Fed-EMNIST. From these observations, we conclude that the condition $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$ is practical enough and the benefits of MS are not so limited.

Moreover, since $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$ and $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$ are different hypothesis classes, directly comparing rates seems to be improper. An analysis of MS in $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$ is also needed.

We disagree with the first point. In general, it is very common in the machine learning and optimization literature to show that an algorithm achieves a better rate (generalization error, optimization error, etc.) for a smaller hypothesis class than the rate of another algorithm targeting a larger hypothesis class. For example, it is well known that a typical theory of LASSO shows that LASSO achieves a better generalization error than OLS when the true parameter is sparse, where LASSO assumes a smaller hypothesis class than OLS does.

Regarding the second point, we agree that an analysis of MS in $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$ may be necessary to judge which algorithm is better in $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$. However, our main focus is to construct a minimax optimal algorithm for the hypothesis class $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$, and as shown in Figure 14 in Section E of the revised paper, it is empirically justified to assume that the local objectives are in $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$ for a reasonable $\zeta_\mathrm{max}$ because $\zeta_\mathrm{max} \not \gg \zeta_\mathrm{mean}$ empirically. Thus, this point does not detract from the importance of this study.

About Weakness 3.

In our experiments, as described in Section D.2, we used a heuristic strategy to stabilize the performance that $\tau_t$ was increased by $1.5$ times from the original $\tau_t$ as long as $|\hat {\mathcal G}| < n/2$, although $\tau_\infty$, which is the limit of $\tau_t$ ($t \to \infty$) , had to be roughly tuned. As you said, it is practically desirable that the algorithm be adaptive not only to Byzantine fraction $\delta$ but also to heterogeneity $\zeta_\mathrm{max}$ (or $\zeta_\mathrm{mean}$). This direction is definitely an important future work.

About Weakness 4.

Thanks for your suggestion. Actually, we give a brief overview of the analysis in the first part of Section 4 to clarify our proof strategy. If that is not enough, we would like to add a more detailed sketch of the proof.

We would be very happy if your concerns were addressed and the score would be raised.

Thank you for your insightful comments and questions.

The convergence rate in terms of the number of steps might not be optimal. In particular, the algorithm is a momentum-based method, however, the convergence rate exhibits the form of a non-momentum based method, and it is unclear to me why the momentum is needed here.

Will the convergence rate of the algorithm remain unchanged if the momentum is removed? Or, is there a better momentum-based algorithm that has better convergence rate?

Our algorithm relies on a heavy-ball method rather than the famous Nesterov's acceleration method. Thus, it is natural that the convergence rate matches that of non-momentum based methods when $\delta \to 0$, since a heavy-ball method does not improve the convergence rate of non-momentum methods at least in the standard nonconvex optimization theory (see, for example, Mai and Johansson, 2020 [1]). Although the main focus of this paper is on the asymptotic optimization error, obtaining the optimal convergence rate in terms of the number of steps $T$ based on Nesterov's acceleration is an interesting future direction.

The reason why we introduce the momentum in our algorithm is that the momentum mitigates the effect of the stochastic noise by canceling out the noise thanks to the accumulation of the previous stochastic gradients. This is very important when $\delta > 0$ because the screening algorithm judges the workers to be non-Byzantine or Byzantine based on comparing the distance between the workers' outputs. If the momentum is removed, the screening algorithm must aggregate the stochastic gradients only at the current iteration, which will degrade the performance of the distance-based detection of the Byzantine workers due to the large stochastic noise. As a result, the convergence rate will be degraded when the momentum is removed.

[1] Mai and Johansson, 2020: Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization.

Thank you for your helpful feedback.

About Weaknesses 1 and 2.

First of all, we want to emphasize that the most critical difference of our study from CCLIP paper [1] is the improvement of the optimization error; our obtained error is $\delta$ times smaller than that of CCLIP in the best case (i.e., $\zeta_\mathrm{max} \approx \zeta_\mathrm{mean}$). Since $\delta$ is often a small value in distributed learning systems, this improvement is quite important from both a theoretical and a practical point of view. The condition $\delta \leq \zeta_\mathrm{mean} / \zeta_\mathrm{max}$ holds empirically in our experiments (please see the comments to ``About Weakness 3'').

Below, we summarize the main differences between our Momentum Screening (MS) and CCLIP [1] that are mentioned in our paper.

• Algorithmically, as shown in Section 3, our algorithm relies on the screening technique rather than clipping, which is critical for our theoretical analysis.
• Theoretically, as described in Section 1 (Main contribution and Related work) and Section 4 (Remark 2), the optimization error can be $\delta$ times better than that of CCLIP.
• Empirically, as provided in Section 7, we demonstrated the consistent superiority of our method over CCLIP in various numerical experiments.

Also, the derivation and the results of the aggregation error bound (Proposition 2) and the momentum diameter bound (Proposition 3) under the uniform gradient heterogeneity condition is the key technical part of our analysis, and is clearly different from the analysis of CCLIP, where only the mean gradient heterogeneity condition is assumed and the aggregation error bound is $\delta$ times worse than ours due to the clipping bias.

About Weakness 3.

First, the expression $\delta \leq (\zeta_\mathrm{max}/\zeta_\mathrm{mean})^2$ was fixed in the revised paper as $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$. The typos do not affect the proofs given in Sections A and B. We thank you for pointing this out and apologize for these typos.

Second, regarding your concern, we recognize that empirical validation of the condition $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$ is critical in our study. After reading your review, we examined the empirical values of $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ on the settings of Section 6 and additionally on Fed-EMNIST, which is known as a FL dataset for a realistic situation. From Figure 14 in Section E of the revision paper (p.36), we can see that $\zeta_\mathrm{mean}/\zeta_\mathrm{max}$ was in $0.5 \sim 0.93$ on MNIST and CIFAR10, and was in $0.34 \sim 0.70$ on Fed-EMNIST. Thus, we conclude that the condition $\delta \leq (\zeta_\mathrm{mean}/\zeta_\mathrm{max})^2$ is practical enough and the benefits of MS are not so limited.

We would be very happy if your concerns were addressed and the score would be raised.

Thank you for your careful reading and important questions.

About Question (1):

Assumption 3: As you said, Assumption 3 is actually stronger than the standard Stochastic Gradient Variance Boundedness (SGVB) assumption, which requires $\mathbb{E}\\|g_i - \nabla f_i(x)\\|^2 \leq \sigma^2$ for minibatch stochastic gradient $g_i$ at $x$ of worker $i$. However, this stronger requirement comes from the fact that our theory derives a high-probability bound instead of an expectation bound, which is a much stronger result. Assumption 3 is a standard assumption for deriving a high-probability bound in the stochastic optimization literature not only in the context of the Byzantine robust optimization; in general, deriving an expectation bound requires SGVB, and deriving a high-probability bound requires Assumption 3 (see, for example, Section 2.3 of [1]).

[1] Jin et al., 2019: On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points.

Assumption 4: Assumption 4 has very little effect on our theoretical results even if $G$ can be much larger than $\sigma$ in Assumption 3. In fact, in Theorem 1, $G$ depends only log log order on the non-dominant terms of the convergence rate (and $G$ never depends on the final optimization error $O(\delta^2\zeta_\mathrm{max}^2)$), as described immediately after Assumption 4 in Section 2. Thus, Assumption 4 is not restrictive at all.

About Question (2):

This is not true. Generally, $\sigma^2$ in Assumption 3 can be much smaller than $G^2$ in Assumption 4, since $\sigma^2$ approaches to zero as the minibatch size goes to $\infty$. In Theorem 1, $\sigma^2$ in Assumption 3 arises explicitely in the convergence rate. In contrast, as mentioned in the answer to Question (1), $G$ in Assumption 4 depends only log log order on the non-dominant terms of the convergence rate. Thus, Assumption 3 is not redundant, since replacing $\sigma^2$ with $G^2$ gives a much worse bound.

About Question (3):

First, we would like to clarify your concern. We think your concern is why the upper bound $O(\delta \zeta_\mathrm{mean}^2)$ of CClip seems to be better than our lower bound $\Omega(\delta^2 \zeta_\mathrm{max}^2)$ for some $\delta \in (0, 0.5)$ when $\zeta_\mathrm{mean} < \zeta_\mathrm{max}$. Is our understanding correct? If so, we would like to address this important point.

In fact, the lower bound derived in Theorem 2 holds for any $\delta \in [0, 0.5)$ for function class $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$ and does not contradict the upper bound of CClip for any $\delta \in [0, 0.5)$. This point is explained as follows. First, please note that the theory of CClip essentially gives an upper bound $O(\delta \zeta_\mathrm{mean}^2)$ for $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$. Using this fact, a trivial upper bound $O(\delta \zeta_\mathrm{max}^2)$ by applying CClip theory to $\\{f_i\\}\_{i \in \mathcal G} \in \mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$ ($\subset \mathcal C_\mathrm{MH}(\zeta_\mathrm{max})$) is larger than our lower bound $\Omega(\delta^2 \zeta_\mathrm{max}^2)$ in Theorem 2, for any $\delta \in [0, 0.5)$. Please note that $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max}) \not \subset \mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$ for any $\zeta_\mathrm{mean} < \zeta_\mathrm{max}$ in general, and thus the theory of CClip never guarantees the upper bound $O(\delta \zeta_\mathrm{mean}^2)$ for $\mathcal C_\mathrm{UH}(\zeta_\mathrm{max})$ for any $\zeta_\mathrm{mean} < \zeta_\mathrm{max}$. Thus, the upper bound $O(\delta \zeta_\mathrm{mean}^2)$ of CClip for $\mathcal C_\mathrm{MH}(\zeta_\mathrm{mean})$ does not contradict the lower bound in Theorem 2 for any $\delta \in [0, 0.5)$.

We would be happy to clarify any further concerns and questions.