Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

Regarding the Weighted Approach Experiment:

We would like to clarify that we addressed the comparison with weighting methods in Figure 2 of our paper. This figure presents a comparison between weighted and non-weighted robust aggregators, demonstrating that the weighted approach outperforms the non-weighted approach, which is equivalent to using the fraction of Byzantine workers. Also, we have conducted further experiments for various values of the fraction of Byzantine iterations with a fixed number of Byzantine workers to evaluate the impact of the fraction of Byzantine iterations. Our findings demonstrate that as the proportion of Byzantine iterations increases, there is a degradation in the training performance. You can see this in Figure 4, in the experiments that we attach in the pdf for the rebuttal.

Regarding the Weight Coefficients:

The weight coefficients in our framework are determined based on the total number of updates of each worker, a factor known in an asynchronous system (see lines 259-267 and Algorithm 2). These weight coefficients align elegantly with the asynchronous dynamics by prioritizing workers with more frequent updates.

Regarding the Limitations:

Thank you for pointing this out. We will include this discussion in the final version of the paper.

The paper does not introduce additional negative social impacts beyond the standard Byzantine synchronous settings. In fact, our work enables us to enhance the robustness of asynchronous training.

In terms of memory consumption, asynchronous systems without Byzantine workers typically require the parameter server to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where $m$ represents the workers’ number and $d$ represents the dimensionality of the model.

Regarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g., applying the coordinatewise median aggregator requires an additional $O(dm\log(m))$ complexity per round). Note that such additional computation also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent.

It is worth noting that, compared to the synchronous case, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.

The additional memory overhead and time complexity, compared to the asynchronous Byzantine-free scenario, represent a trade-off for enhanced robustness, as it enables the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and an improved performance of the training process in the presence of adversarial behavior.

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

Regarding the Empirical Evaluation:

We agree that including experiments on additional datasets would strengthen the empirical validation of our proposed approach. In response, we have conducted experiments on the CIFAR-10 dataset, complementing our existing results from the MNIST dataset. We believe these additional experiments provide a more comprehensive evaluation of our approach and highlight its practicality. Furthermore, we will ensure that important experimental details are retained in the main paper in the final version.

Regarding the Convex Setting:

The convex case is important for two main reasons: It captures classical ML problems like linear and logistic regression, and it serves as a theoretical testbed for analyzing and developing novel ideas and algorithms in various machine-learning scenarios. These new algorithms often induce novel heuristics that are very useful in the context of general ML problems, including non-convex ones and specifically in Deep Learning scenarios. Indeed, this approach is prevalent and has led to many important contributions in ML. Two prominent examples are the well-known Adagrad and Adam algorithms, which were conceived and analyzed under the convexity assumption. Other influential examples are the many works on convex synchronous/asynchronous training, and works on Byzantine-resilient algorithms for convex problems, see e.g.:

• Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018. https://arxiv.org/pdf/1803.08917
• Minghong Fang, Jia Liu, Neil Zhenqiang Gong, and Elizabeth S Bentley. Aflguard: Byzantine robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632–646, 2022. https://arxiv.org/pdf/2212.06325

For the asynchronous Byzantine problem, the convex framework enables the development of a more intuitive and naturally weighted scheme. It provides a foundational basis for extending these findings to non-convex settings, which is a challenging and ongoing research area. In fact, extending our weighted scheme to the non-convex setting requires less straightforward analysis and necessitates a careful adaptation to accommodate the stochastic error inherent in non-convex scenarios. For further details, please refer to lines 259-271 and the Future Work section of our paper.

Please note that in our work, we empirically examine the ideas developed in the non-convex setting, specifically focusing on non-convex deep learning problems. Our empirical study demonstrated the practicality and usefulness of our approach in deep learning scenarios, complementing our theoretical findings. Additionally, we conducted further experiments using the CIFAR-10 dataset to validate the effectiveness of our methods in a more complex, non-convex machine learning task.

Regarding the Attacks Adaptation to the Asynchronous Case:

The attacks of Little and Empire are designed to hide under the variance among the workers' outputs. In asynchronous settings, delays can increase this variance, providing an opportunity for Byzantine workers to blend in more effectively with honest outputs. Therefore, we believe that these attacks also may be effective in the asynchronous setting. Moreover, we have adapted these attacks to directly tackle the weighted robust aggregation rules that we utilize in our algorithmic approach, thus making them more comparable to the synchronous case. Nevertheless, the exploration of attacks specific to asynchronous settings is still underexplored. Further investigation into asynchronous-specific attacks is necessary to better understand their impact.

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

Regarding the Assumptions on Byzantine Behavior: “... it raises questions about whether alternative, potentially simpler solutions could be explored”

This is a very good question. Our goal was to develop the simplest approach for which we could draw provable guarantees for the general Byzantine asynchronous setting, and our approach indeed ensures such guarantees. It is an important open question to understand whether a simpler approach can work in this case, and we believe that this is an interesting future direction.

Monitoring update frequencies can potentially assist, for example, in an extreme case where we have a dominant worker who appears more than half times in some of the iterations, then this worker can be identified as an honest worker and might serve as an honest reference for anomaly detection. While this can lead to a simple approach for this specific case, we believe the guarantees will coincide with ours. In less extreme cases, however, relying solely on update frequencies to detect outliers becomes more challenging within the general Byzantine framework. This framework assumes only a majority of iterations are honest, without prior knowledge of additional characteristics of Byzantine updates. The generality of this framework allows us to develop an approach applicable to a wide range of scenarios. Nevertheless, this broad applicability makes it difficult to set definitive criteria for identifying anomalous behavior based on frequency alone. For example, a Byzantine worker could adapt their behavior to mimic honest patterns, making identification more difficult. Leveraging additional prior knowledge might be useful in developing simpler approaches, and this is a future work to investigate.

We will add this discussion to the final version of the paper.

Regarding the Impact on System Metrics:

Thank you for pointing this out. We will include this discussion in the final version of the paper.

Regarding memory requirement and computational complexity, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.

Compared to the asynchronous case without Byzantine workers, the parameter server only needs to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where $m$ represents the workers’ number and $d$ represents the dimensionality of the model. Regarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g. applying the coordinatewise median aggregator requires an additional $O(dm\log(m))$ complexity per round). Note that such additional computation also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent.

The additional memory overhead and time complexity is a trade-off for enhanced robustness, as it enables the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and an improved performance of the training process in the presence of adversarial behavior.

Regarding the Temporal Distribution of Byzantine Updates:

We would like to clarify that our analysis does not assume uniform updates for Byzantine workers. The generality of our framework enables us to handle scenarios where Byzantine iterations are concentrated within specific periods, as long as the majority of iterations are honest, in the sense that $t_{honest}\geq(1-\lambda)t, \forall t\in[T]$.

In our experiments, we used a uniform distribution of Byzantine updates primarily for simplicity. However, we acknowledge that concentrated Byzantine iterations can indeed cause severe degradation in performance. Such scenarios can significantly increase the honest delays, potentially degrading the overall convergence. We will include this discussion on the behavior of Byzantine updates and their implications in the final version of our paper.

Dear reviewer,

Thanks again for your positive feedback. We appreciate your suggestion to experiment with extreme scenarios, and agree that it could further support our proposed approach and findings. We will incorporate this into the final version of the paper.

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

Regarding the Complexity of Methodology:

While our approach may not be trivial to code, conceptually, it can be implemented as a combination of several quite simple modules, which simplifies the implementation. And indeed, this is how we translated our method into a rather simple Python code. To assist in implementing our methods, we will share our code with the community, which includes a detailed implementation of the proposed framework. It is worth noting that many widely-used optimization algorithms, such as the Adam optimizer, also involve intricate components (momentum, and per-feature learning rate) but are popular in practice due to their effectiveness.

References:

• Adam paper: Kingma, Diederik P., and Jimmy Ba. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014). https://arxiv.org/pdf/1412.6980
• Adam Pytorch documation: https://pytorch.org/docs/stable/generated/torch.optim.Adam.html

Regarding the Practical Examples:

We have conducted additional experiments using the CIFAR-10 dataset, in addition to our earlier experiments on MNIST. These experiments further validate the robustness and performance of our proposed methods in more complex and diverse settings.

The results from the CIFAR-10 experiments align closely with those observed on MNIST, showcasing the consistency and effectiveness of our framework across different types of data. We believe these additional experiments provide a more comprehensive evaluation of our approach and highlight its practicality.

Regarding the Dependency on Assumptions:

We would like to clarify that while our analysis assumes a bounded delay model for theoretical analysis, our algorithmic approach does not rely on this assumption. This assumption is used primarily to facilitate the mathematical analysis and to derive performance guarantees under controlled conditions. In practice, our method can handle varying levels of delay, including scenarios with significant delays. As demonstrated in Figure 1 of the paper, we tested our approach in a setting with heavy delays, and the results show that it performs robustly even under these challenging conditions.

Regarding the assumption of bounded Byzantine iterations, apart from the weighted CTMA, which relies on knowledge of the parameter $\lambda$ (the fraction of Byzantine iterations), our approach with weighted double momentum, as well as robust aggregation rules like the weighted geometric median or the weighted coordinate-wise median, do not require knowing the fraction of Byzantine iterations. These methods can perform effectively without this additional knowledge. While knowing the fraction of Byzantine iterations is beneficial for achieving theoretical optimality, our proposed methods can remain robust and practical in the absence of this information.

Additionally, it is quite standard in the synchronous literature to assume knowledge of the fraction of Byzantine workers or to have a reliable approximation of this parameter. In scenarios where such an assumption is not made, alternative solutions often rely on knowing the bound of the stochastic variance, which can be less practical and more challenging to estimate than the fraction of Byzantine workers. This adaptation to the fraction of Byzantine iterations is intended to be reasonable and practical, given that a parallel assumption is widely accepted in the literature on synchronous systems.

Regarding the Further Empirical Evaluation:

We have conducted further experiments for different values of the fraction of the Byzantine iterations and additional experiments on the CIFAR-10 dataset, complementing our existing results from the MNIST dataset. These experiments provide a more comprehensive evaluation of our approach and highlight its practicality.

Regarding the Scalability of Our Approach:

Thank you for pointing this out. We will include this discussion in the final version of the paper.

Regarding memory requirement and computational complexity, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.

Compared to the asynchronous case without Byzantine workers, the parameter server only needs to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where $m$ represents the workers’ number and $d$ represents the dimensionality of the model. Regarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g. applying the coordinatewise median aggregator requires an additional $O(dm\log(m))$ complexity per round). Note, that such additional computation, also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent.

Also, it is worth noting that the number of Byzantine workers, whether increasing or decreasing, does not affect the scalability of our approaches for a fixed number of $m$ workers.

Overall, the additional memory overhead and time complexity are a trade-off for enhanced robustness, as they enable the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and improved performance of the training process in the presence of adversarial behavior.

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

Regarding the Convex Setting:
The convex case is important for two main reasons: It captures classical ML problems like linear and logistic regression, and it serves as a theoretical testbed for analyzing and developing novel ideas and algorithms in various machine-learning scenarios. These new algorithms often induce novel heuristics that are very useful in the context of general ML problems, including non-convex ones and specifically in Deep Learning scenarios. Indeed, this approach is prevalent and has led to many important contributions in ML. Two prominent examples are the well-known Adagrad and Adam algorithms, which were conceived and analyzed under the convexity assumption. Other influential examples are the many works on convex synchronous/asynchronous training, and works on Byzantine-resilient algorithms for convex problems, see e.g.:

• Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018. https://arxiv.org/pdf/1803.08917
• Minghong Fang, Jia Liu, Neil Zhenqiang Gong, and Elizabeth S Bentley. Aflguard: Byzantine robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632–646, 2022. https://arxiv.org/pdf/2212.06325

For the asynchronous Byzantine problem, the convex framework enables the development of a more intuitive and naturally weighted scheme. It provides a foundational basis for extending these findings to non-convex settings, which is a challenging and ongoing research area. In fact, extending our weighted scheme to the non-convex setting requires less straightforward analysis and necessitates a careful adaptation to accommodate the stochastic error inherent in non-convex scenarios. For further details, please refer to lines 259-271 and the Future Work section of our paper.

Please note that in our work, we empirically examine the ideas developed in the non-convex setting, specifically focusing on non-convex deep learning problems. Our empirical study demonstrated the practicality and usefulness of our approach in deep learning scenarios, complementing our theoretical findings. Additionally, we conducted further experiments using the CIFAR-10 dataset to validate the effectiveness of our methods in a more complex, non-convex machine learning task.

Regarding the Experiments Setup:

As with other optimization algorithms like ADAGrad, which were analyzed in convex settings and employed in non-convex scenarios, we demonstrated the performance of our approach in a non-convex context. We used a 2-layer convolutional network designed for the MNIST dataset. The network includes two convolutional layers (20 filters and 50 filters, both 5x5), followed by ReLU activation and 2x2 max pooling. This is followed by a fully connected layer with 50 units, batch normalization, and a final fully connected layer with 10 units. Similarly, for the new CIFAR-10 experiments, we applied an analogous architecture.

Thank you for highlighting this. We will add further details about the setup and implementation of our experiments in the final version of the paper to enhance the clarity of the experimental configuration.

• ADAGrad Paper: Duchi, John, Elad Hazan, and Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." Journal of machine learning research 12.7 (2011). https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf