Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent
We study the resilience to Byzantine failures of distributed implementations of Stochastic Gradient Descent (SGD). So far, distributed machine learning frameworks have largely ignored the possibility of failures, especially arbitrary (i.e., Byzantine) ones. Causes of failures include software bugs, network asynchrony, biases in local datasets, as well as attackers trying to compromise the entire system. Assuming a set of n workers, up to f being Byzantine, we ask how resilient can SGD be, without limiting the dimension, nor the size of the parameter space. We first show that no gradient aggregation rule based on a linear combination of the vectors proposed by the workers (i.e, current approaches) tolerates a single Byzantine failure. We then formulate a resilience property of the aggregation rule capturing the basic requirements to guarantee convergence despite f Byzantine workers. We propose Krum, an aggregation rule that satisfies our resilience property, which we argue is the first provably Byzantine-resilient algorithm for distributed SGD. We also report on experimental evaluations of Krum.
Intro:
The paper introduces a novel algorithm, called Krum, that combines partially calculated gradients in a Byzantine failure tolerant way. Such an algorithm is meant to be useful in distributed training of machine learning models on very large data sets.
I am a machine learner, but not a distributed computing expert. Hence, I review the manuscript from a customer perspective.
---
Strengths:
 * The research question is very interesting. Distributed techniques start to play a more important role in machine learning as the scales of the data sets grow exponentially.
 * The paper is written in a sophisticated academic language. It is also nicely structured.
 * The proposed algorithm is supported with rigorous theoretical argumentations.
---
Weaknesses:
 * Results in Figure 4 are not charming. When there are no Byzantine failures, the proposed algorithm lags far behind simple averaging. It starts to show its power only after one third of the workers are Byzantine. This looks like an extremely high failure rate. Apparently, averaging will remain to be extremely competitive when the failure rates are realistically low, making the motivation of the proposed approach questionable.
 * While the paper introduces an idea that starts to become useful when the data set is dramatically large, the reported experiments are on extremely small data sets. MNIST has 60000 instances, spambase has 4601. The real effect of the divergence between the true and the stochastic gradient starts to become visible when the data set is large enough. With today's hardware technology, a modest workstation with a few-thousand-dollar GPU can be easily trained on MILLIONS of data points without any need for such protocols as Krum. Furthermore, whether more data points than a few million are needed depends totally on applications. In many, the performance difference between 10 Million and 100 Million is ignorably small. For a machine learner to be convinced to slow down her model for the sake of safe distributedness, the authors should pinpoint applications where there is a real need for this and report results on those very applications.
 * The proposed algorithm is for updating global parameters from stochastic gradients calculated on minibatches. Although this approach is fundamental to many machine learning models, the central challenge of the contemporary techniques is different. Deep neural nets require distributed computing to distribute operations across "neurons" rather than minibatches. The fact that the proposed algorithm cannot be generalized to this scenario reduces the impact potential of this work significantly.
Minor point: The paper would also be stronger if it cited earlier pioneer work on distributed machine learning. One example is:
 
C.T. Chu et al., Map-Reduce for Machine Learning on Multicore, NIPS, 2007
---
Preliminary Evaluation:
While I appreciate the nice theoretical work behind this paper and that distributed machine learning is an issue of key importance, the reported results shed doubt on the usefulness of the proposed approach.
---
Final Evaluation:
 
I do acknowledge that 33% Byzantine failure rate is a standard test case for general distributed computing tasks, but here our concern is training a machine learning model. The dynamics are a lot different from "somehow" processing as large data bunches as possible. The top-priority issue is accuracy, not data size. According to Figure 4, Krum severely undermines the model accuracy if there is no attack. This literally means a machine learner will accept to use Krum only when she is ABSOLUTELY sure that i) a 10-20 million data point subset will not be sufficient for satisfactory accuracy (hence distributed computing is required), and ii) at least 33% of the nodes will act Byzantine (hence Krum is required). As a machine learner, I am trying hard but not managing to find out such a case. Essentially, it is not the readership's but the authors' duty to bring those cases to attention. This is missing in both the paper and the rebuttal. I keep my initial negative vote.