Robust Distributed Training of Linear Classifiers
Based on Divergence Minimization Principle
Junpei Komiyama, Hidekazu Oiwa, and Hiroshi Nakagawa
The University of Tokyo,
7-3-1, Hongo, Bunkyo-ku, Tokyo, 113-0033, Japanjunpei@komiyama.info
oiwa@r.dl.itc.u-tokyo.ac.jp
nakagawa@dl.itc.u-tokyo.ac.jp

Abstract. We study a distributed training of a linear classifier in which the data isseparated into many shards and each worker only has access to its own shard. The
goal of this distributed training is to utilize the data of all shards to obtain a wellperforming linear classifier. The iterative parameter mixture (IPM) framework(Mann et al., 2009) is a state-of-the-art distributed learning framework that has astrong theoretical guarantee when the data is clean. However, contamination on
shards, which sometimes arises in real world environments, largely deteriorates
the performances of the distributed training. To remedy the negative effect of thecontamination, we propose a divergence minimization principle for the weight
determination in IPM. From this principle, we can naturally derive the Beta-IPM
scheme, which leverages the power of robust estimation based on the beta divergence. A mistake/loss bound analysis indicates the advantage of our Beta-IPM
in contaminated environments. Experiments with various datasets revealed that,even when 80% of the shards are contaminated, Beta-IPM can suppress the influence of the contamination.

1 Introduction
A linear classifier is one of the most fundamental concepts in the field of machine learning. Online learning algorithms [20, 5, 6] are able to train linear classifiers effectively.
An online algorithm sequentially processes data points, and thus, it requires all data to
be accessible from a single machine. While the training on a single machine is of its
own importance, training in distributed environments has attracted increasing interest[1, 10, 16]. In such environments, data is divided up into disjoint sets of shards and eachworker has access to only one shard.
Iterative Parameter Mixture (IPM) [16, 17] is a state-of-the-art distributed training
framework, which involves a master node and worker nodes. Advantages of IPM lies in
its communication efficiency and simplicity: in each epoch, each worker trains a modelin parallel on his own shard, and the master mixes the training results (Fig. 1).
IPM implicitly assumes that each shard is noiseless. However, it is not always thecase: there can be some adversarially or randomly labelled data in some distributed
learning scenarios. For example, web mail systems possibly involve some users who

2
1

2

workersw(1,n)

3

i

...
(i,n)
...w

M

1

2

3

i

M

...
(avg,n)w...

(avg,n)w

mastermasterFig. 1. Illustration of the communication in IPM

WKL

WKL contamination

KL-IPM

w

w
Wβ

Wβ

Beta-IPMw
No contamination

contaminationw
With contamination

Fig. 2. Illustrative example of KL-IPM and Beta-IPM. Each horizontal line represents a parameter
space, and each vertical line represents a parameter returned by a worker, the height of which is
proportional to the mixing weight. While KL-IPM equally weights all the parameter vectors,
Beta-IPM adaptively weights each parameter as described later.

adversarially labels spams and non-spams, or incorrect data formats [9] lead to corrupted classification result. Let us call such flawed data contamination. We verified
that, the performance of the trained classifier is deteriorated by contamination.
Meanwhile, IPM has freedom in how to weight the individual workers’ results. If
some shards are known to be contaminated, we can avoid the effect of these shards bysetting their weights to zero. However, it is unlikely that there will be prior knowledge
about which shards are contaminated, and thus, the strategy we should take is to weight
seemingly contaminated results less on the basis of their statistical anomalousness.
With this in mind, we propose a weight determination principle based on a divergence minimization criterion. This criterion reinterprets the most straightforward
choice, which is to weight each worker equally, as the minimization of the KullbackLeibler divergence (KL-IPM). On the other hand, the beta divergence, which is theextension of the KL divergence, provides robust inference against contamination. We
propose the weight determination formula by minimizing the beta divergence (BetaIPM). Moreover, We prove a mistake/loss bound of IPM. This theoretical result showsthat, by weighting less heavily to contaminated shards with Beta-IPM we can suppress
the upper bound of losses over training. The difference between KL-IPM and Beta-IPM
is illustrated in Fig. 2. Finally, an empirical evaluation on various datasets confirms that
Beta-IPM remedies the effect of contamination.

3

2 Related Work
2.1 Distributed training of linear models
Distributed training frameworks for linear models have been studied in the literature.
Asynchronous updates are sets of models in which all workers simultaneously operateon shared parameters. There is a long line of work related to asynchronous updates fromthe 1980s [22] onwards [24, 12]. A problem of the shared memory resource it that, it
does not scale with many shards because the communication cost is proportional to thenumber of updates.
The distributed gradient method [4] is a distributed extension of the gradient descent method, which optimizes some smooth function by taking steps proportional to
the negative gradient. In the distributed gradient method, individual workers computepartial gradients based on their shards, which are then summed to make an update.
In the IPM method, each worker operates independently and shares parameters after
each worker finishes an iteration. A master mixes the parameters of the workers withweights whose sum is normalized. IPM is used in many linear and regression models,such as logistic regression [16], structured perceptron [17], etc. McDonald et al. [17]proved that IPM with perceptron has mistake bound in a linearly separable case (i.e.,the case in which every data point is correctly classified by some classifier). Moreover,Hall et al. [14] empirically compared the asynchronous updates, the distributed gradient method and IPM using large-scale click-through data. The results show that IPM
combined with the perceptron [20] performed the best.

2.2 Robust training against flawed data
Detection of spam and malicious activities is an important problem in the highly distributed web industry [18, 7]. In addition, poorly formatted data [19, 9] causes a considerable problem in distributed training. Despite significant efforts made at removing
such flawed data, there still is a need for robust models. Robust models are used in many
fields, including multi-task learning [13, 23] and sensor networks [3].
The problem of contamination in distributed data can be broken down into twocases: the first case is when the contamination is scattered across every shard, and thesecond case is when some shards are clean while others are contaminated. Studies on therobustness of online learning algorithms [5, 6, 15] have mainly dealt with the first case,which considers a single data repository affected by noise. In this case, the clean data
are hard to distinguish from the noise. Instead, we consider the second case and showthat a significant improvement is possible by putting less importance on statisticallyextraordinary shards which are likely to be wrongly labeled or corrupted.
We also note that, Daumé III et al. [8] proposed a distributed learning algorithmwith adversarially distributed data. Their definition of adversarially distributed data isdifferent from our adversarial noise: while they considered separable data with an adversary who can generate an arbitrary imbalance among shards, we consider an adversarial
attacker that can harm the separability assumption by maliciously labelling.

4

Algorithm 1 Iterative Parameter Mixture (IPM)
1: Shards: T1 , ..., TM , w(avg,0) = 0
2: for n = 1, ..., N do(avg,n−1)3:w(i,n) = SingleIterationTrain(T)
i, wP(avg,n)(i,n)
4:w= i αi,n w
5: end for

3 Problem Setup
We consider a binary classification. Let X ∈ Rd be the input space and Y = {−1, 1}
be the output space. A data point is defined as an input-output tuple (x, y) ∈ X × Y. A
linear classifier with parameter vector w predicts an output as ŷ = sign(w·x). The goalof our distributed training framework is to find the parameter vector w which explains
the whole data most.
In distributed training, the training data is divided into M non-overlapping subsets(shards), and a shard is assigned to each worker. There also is a master who integrates
the results of workers. Training based on IPM (Algorithm 1) goes as follows. In eachepoch n = 1, 2, ..., N , each worker i independently does a single iteration of training
its own parameters w(i,n) , which are then sent to the master. The master waits until all
workers finish their training before it computes a mixed parameter w(avg,n) , which isa weighted sum of the trainers’ parameters. The weight αi,n of each worker i in eachPM
epoch n can be chosen arbitrarily as long as it is normalized (i.e. i=1 αi,n = 1).
Later in Section 4 we propose weight determination formulas that we call KL-IPM and
Beta-IPM. At the end of the epoch, the mixed parameters w(avg,n) are sent back to
the workers, who in the next epoch start the new single iteration training based on thereceived mixed parameter. After N epochs have been completed, the master outputs the
final parameter vector (a linear classifier).

3.1 IPM combined with online algorithms
We use online learning algorithms in single iteration training (“SingleIterationTrain” in
Algorithm 1). We specifically deal with the perceptron [20] and the Passive Aggressive(PA) method [5]. Section 5 describes that, IPM combined with perceptron and PA isable to extend the theoretical guarantee of these single-machine online algorithms.

4 Divergence Minimization Principle
In this section, we describe our main proposal, which is how to determine the weights
based on the divergence minimization principle. Section 4.1 describes our statisticalassumptions and the divergence minimization principle. Section 4.2 describes the KL
and beta divergences, and Section 4.3 shows KL-IPM and Beta-IPM formulas. Section
4.4 demonstrates the behavior of KL-IPM and Beta-IPM with a simple example.

5

4.1 Statistical assumption and divergence minimization principle
The statistical assumption is as follows: the parameters returned by the workers in eachepoch n should be drawn from a Gaussian distribution Qn . Our proposal is that, ineach epoch n the mixed parameter vector w(avg,n) is determined to be the mean of theGaussian Qn . However, the parameters are actually drawn from Pn , which possibly
contains contamination. Namely, w(i,n) ∼ Pn . The mean µ and covariance Σ of Qn
are determined in such a way as to minimize the divergence:arg min D(Pn ||Qn (µ, Σ)),

(1)

µ,Σ

where D is the divergence between Pn and Qn . If we use a robust divergence thatsuppresses the influence of contamination, we are able to estimate the true µ and Σ.
4.2 KL and beta divergences
The KL divergence is the most basic measure that indicates the deviation of a distribution from another distribution. The KL divergence between two probability distributions
P and Q on Rd is defined as
Z
P (w)
dw,
(2)
DKL (P ||Q) = P (w) log
Q(w)which is non-negative and equal to zero if and only if P = Q almost everywhere. While
the KL divergence is of fundamental importance in information theory, it is not robust
to the contamination of outliers.
The beta divergence, which was introduced by [2] and [11], is parameterized by areal parameter β > 0. The beta divergence between P and Q is defined asZ 
P β (w) − Qβ (w)P β+1 (w) − Qβ+1 (w)P (w)Dβ (P ||Q) =−dw. (3)ββ+1
When β → 0, the beta divergence is consistently defined as limβ→0 Dβ (P ||Q) =DKL (P ||Q). Therefore, the beta divergence can be considered as an extension of the
KL divergence. One of the main motivations of investigating the beta divergence is todevise a robust inference against contamination. That is, the beta divergence between
two distributions P and Q remains undisturbed by some fraction of the contamination in
P . β is a trade-off parameter. The bigger β is, the more robust and less computationallyeffective the divergence becomes.
4.3 KL-IPM and Beta-IPM
KL-IPM: KL-IPM is a weight determination formula in IPM that equally weights eachworker. Namely,
1αi,n =.
(4)
M
However, if flawed data contaminate some of the shards, the performance of KL-IPM
deteriorates. To remedy this problem, we derive Beta-IPM that minimizes the beta divergence.

6
2d samples on parameter space

6
4

y

2
0

w

−2

w(avg) in KL-IPM−4−6w(avg) in Beta-IPM
0

5

10

15

20

x

Fig. 3. Illustration of a two-dimensional example. Each of the 100 crosses represents the parameters w ∼ P . The 80 crosses are from the true distribution (Gaussian with µ = (0, 0)⊤ andΣ = diag(1, 1)). The other 20 crosses are contamination and generated from a false distribution(Gaussian with µ = (20, 0)⊤ and Σ = diag(2, 2)). The large red circle is the simple mean of allparameters, determined by KL-IPM (Equation (4)). The large blue square is the mixed parameter
determined by Beta-IPM with β = 0.1 (Equation (6)).

Beta-IPM: Let µc and Σc are respectively the empirical mean and covariance of theparameter vectors {w(i,n) } defined as
µc =

M
M
1 X (i,n)
1 X (i,n)w, and Σc =(w
− µc )(w(i,n) − µc )⊤ .
M i=1
M i=1

(5)

Beta-IPM is defined as a weight determination formula in IPM that in each epoch nchooses weight αi,n as follows:
exp S(w(i,n) |µc , β1 Σc )
αi,n = PM,(j,n) |µ , 1 Σ )c β c
j=1 exp S(w(6)

where S(w(i,n) |µ, Σ) = −(1/2)(w(i,n) − µ)⊤ Σ −1 (w(i,n) − µ) is the exponent partof the Gaussian. Namely, each weight of a shard is determined by the distance of theparameter vector from the mean. Beta-IPM is parameterized by β ≥ 0 and is equivalent
to KL-IPM when β → 0 because the covariance (1/β)Σc in (6) becomes infinitely
large. The KL-IPM and Beta-IPM formulas above are derived in Appendix A.1. Notethat the problem of minimizing the beta divergence is non-convex, so we have madesome approximations in order to derive (6).
4.4 Example of KL-IPM and Beta-IPM
Fig. 3 is a two-dimensional example that displays the behaviors of KL-IPM and BetaIPM. While KL-IPM equally weights each parameter vector, Beta-IPM weights thevector farther from the mean less, and in this way it suppresses the influence of contamination. As a result, the mixed parameter vector chosen by Beta-IPM is closer to thetrue center (=(0, 0)⊤ ) than that by KL-IPM.

7

5 Mistake / Loss Bound in IPM
This section provides a theoretical viewpoint for the weight determination by Beta-IPM.
We first discuss the separable mistake bound of IPM with a single iteration perceptron(IPM-perceptron) in Section 5.1, then goes to the corresponding loss bound of IPM
with a single iteration PA (IPM-PA) in Section 5.2. With these bounds, we discuss
about Beta-IPM as a suppressor of weights in contaminated shards in Section 5.3.
5.1 Mistake bound of IPM-perceptron
The following theorem, which is proven by McDonald et al. [17], is an extension of thewell-known mistake bound of the single machine perceptron to IPM,
Theorem 1. (Mistake bound of IPM-perceptron in the separable case) [Theorem 3 in[17]] Assume all the training data is separable by a margin γ. Suppose that ||x|| ≤ R
holds for any training input x, and let ki,n be the number of mistakes in shard i during
the nth epoch of training. For any number of epochs N , the number of mistakes during
the training in the IPM-perceptron is bounded as
N X
MX

n=1 i=1αi,n ki,n ≤

R2
.
γ2

(7)

Theorem 1 states that the IPM-perceptron with separable data has a finite numberof misses, which guarantees it converges to parameters that correctly classify the entiredata.
In contrast, when some fraction of the dataset is non-separable, there are no parameters that perfectly classify all the data. Yet even in this case, we can bound the mistakein terms of the loss of the possible best classifier (parameter vector) u.
Theorem 2. (Mistake bound of IPM-perceptron in the non-separable case) Let ki,n be
the number of mistakes in shard i during the nth epoch of training. Furthermore, let u
be an arbitrary normalized
parameter vector u ∈ Rn (||u|| = 1) Let ξ = max{0, γ −Py(u · x)} and Ξi = t′ ξ, where the index t′ runs over all data points in shard i. For
any number of epochs N and any γ ≥ 0, the following inequality holds:
N X
MX

n=1 i=1αi,n ki,n ≤

N M
2 XX
R2
αi,n Ξi .
+γ2
γ n=1 i=1

(8)

Theorem 2 is proven by the combination of the technique for the IPM loss bound[17] and an ordinary technique for the non-separable mistake bound of perceptron. The
proof of Theorem 2 is in a full version of this paper. Notice that, ξ is the distancefrom the margin with a data point (x, y), which indicates how the classification witha classifier u fails for this data point. Therefore, Ξi , the sum of ξ over shard i, can beconsidered as a cumulative loss if u is run on shard i. From inequality (8), the number of
mistakes of IPM-perceptron is bounded in terms of the cumulative loss of an arbitrary
vector u.

8

5.2 Loss bound of IPM-PA
Here, we describe the loss bound of IPM with the Passive Aggressive algorithm (IPMPA). As in the case of IPM-perceptron, we can obtain separable and non-separable loss
bounds. The proofs of the bounds are in Appendix A.2.
Theorem 3. (Loss bound of IPM-PA in the separable case)
Let there be a parameter vector u that suffers no loss for any data point (x, y) inthe training data set. Suppose that ||x|| ≤ R holds for any input x. Then,M
N X
X

n=1 i=1αi,n Li,n ≤ ||u||2 R2 ,(9)

where Li,n is the cumulative squared loss which worker i suffers in epoch n.
Theorem 4. (Loss bound of IPM-PA in the non-separable case)
Assume ||x|| = 1 holds for any data point. Then, for any parameter vector u,
v

2
uN M
N X
M
uX X
X
αi,n Li,n ≤ ||u|| + 2t
αi,n L∗i  ,(10)
n=1 i=1n=1 i=1

where L∗i is the cumulative squared loss of parameter vector u with data on shard i.
5.3 Superiority of Beta-IPM from a theoretical perspective

The cumulative loss in (8) is weighted by αi,n . Suppose the shards are divided into
two categories: separable shards i = 1, ..., m which can be classified by u and nonseparable shards i = m+1, ..., M with no vector to correctly classify them. The smaller
the weights of the non-separable shards αm+1 , ..., αM are, the smaller the weighted cuPM
mulative loss i=1 αi,n Ξi we can obtain, and this means that it is very important to
reduce the weights corresponding to contaminated shards. The same argument goeswith PA. In general, Beta-IPM suppresses the weights of non-separable shards as described in Section 4, and thus Beta-IPM is expected to have a smaller mistake countthan KL-IPM.

6 Empirical Evaluation
We conducted an evaluation with various datasets. The overall goal of these experiments
was to study how KL-IPM and Beta-IPM behave in contaminated environments.
6.1 Setup
Our experiments involved 16 datasets (Table 1). Zeta and ocr datasets are from the
Pascal large-scale learning challenge1, and the imdb and citeseer datasets are from Paul
Komarek’s webpage2. The other datasets are from the LIBSVM dataset repository3.
1

http://largescale.ml.tu-berlin.de/
http://komarix.org/ac/ds/
3
http://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/binary.html
29
Table 1. List of the binary classification datasets evaluated. The tasks of the datasets are CI(census income prediction), DC (document categorization), HA (human answer prediction), IP(involvement prediction of person to some contents), IR (image recognition), MD (malware /suspicious contents detection), S (synthetically created problem), TC (toxicity categorization), orTD (text decoding).
# of features # of data points task
ijcnn1.tr
mushrooms
a8a
ocr
epsilonzeta
gisettereal-sim

22
112
123
1,156
2,000
2,000
5,000
20,95849,9908,124
22,6963,500,000
400,000
500,000
6,000
72,309

TD
TC
CI
IR
S
S
IR
DC

# of features # of data points task
rcv1
47,236
citeseer
105,354
imdb
685,569
news201,355,191
url
3,231,961
webspam 16,609,143
kdda
20,216,830
kddb
29,890,095

20,242
181,395
167,773
19,9962,396,130
350,000
8,407,752
19,264,097

DC
IP
IP
DC
MD
MD
HA
HA

Data shards: For each dataset, we used 80% of the data for training and 20% for
testing. Then, the training dataset is divided into 100 shards associated with workers.
Algorithms are trained with the training data and evaluated in terms of the classification
accuracy of the test data.
To study the proposed algorithms’ robustness against contamination, we studied theclean setting (i.e. no contamination) and two following contamination settings. Notethat the contaminations are only on the training shards (the test data is always clean).
Setting 1 - adversarial labels: In this setting, 30 out of 100 shards are adversarial data:
the labels of the data are reversed. This setting models situations where the data in someshards are maliciously labeled.
Setting 2 - random labels: In this setting, 80 out of 100 shards are assigned randomlabels. Each data point in these randomly labeled shards is labeled yt ∼ Bernoulli(p),regardless of its true label. The ratio of positive labels, p, varies from 0.1 to 0.9 among
workers. This setting models situations where data in most shards are corrupted.
Algorithms: We compared four algorithms: KL-IPM with a single-iteration perceptron
or Passive Aggressive (KL-IPM-perceptron and KL-IPM-PA, respectively) and BetaIPM with a single-iteration perceptron or Passive Aggressive (Beta-IPM-perceptron andBeta-IPM-PA, respectively). All values of β were the best among {10−1 , 10−2 , ..., 10−8 }.
Since our research includes high-dimensional datasets, we assumed that the Gaussianin Beta-IPM was diagonal. The features with zero-variances were ignored in the weightcalculation. We normalized the parameter vector of each worker by using the l2-norm
when calculating the weights in Beta-IPM.
6.2 Results
The results for all datasets are shown in Table 2. The results of KL-IPM in the cleansetting can be considered to be the possible best performance of linear classifiers in our
distributed setting. As aforementioned, the performance of IPM is degraded by contamination. Note that our main interest in these experiments is the extent to which Beta-IPM
can remedy the effects of contamination. First, let us compare the results of KL-IPM in10
Table 2. Accuracy of the algorithms in the clean/adversarial/random settings at the 50th epoch.
Boldface entries in the contamination settings are the best among the individual datasets.
Clean Setting
ijcnn1.tr mushrooms a8a
ocr epsilon zeta gisette real-sim
KL-IPM-perceptron 0.913
0.999
0.845 0.763 0.899 0.628 0.947 0.968
KL-IPM-PA
0.912
0.999
0.845 0.762 0.899 0.694 0.958 0.975
rcv1
citeseer imdb news20 url webspam kdda kddb
KL-IPM-perceptron 0.960
0.976
0.981 0.953 0.986 0.990 0.881 0.886
KL-IPM-PA
0.966
0.977
0.985 0.958 0.986 0.990 0.882 0.887
Contamination Setting 1: Adversarial Labels
ijcnn1.tr mushrooms a8a
ocr epsilon zeta gisette real-sim
KL-IPM-perceptron 0.908
0.937
0.838 0.760 0.881 0.582 0.854 0.824
KL-IPM-PA
0.908
0.983
0.837 0.760 0.886 0.651 0.912 0.904
Beta-IPM-perceptron 0.908
0.998
0.846 0.763 0.898 0.665 0.935 0.961
Beta-IPM-PA
0.908
0.989
0.846 0.762 0.898 0.663 0.957 0.972
rcv1
citeseer imdb news20 url webspam kdda kddb
KL-IPM-perceptron 0.762
0.976
0.980 0.703 0.983 0.987 0.743 0.759
KL-IPM-PA
0.871
0.977
0.984 0.844 0.983 0.987 0.689 0.712
Beta-IPM-perceptron 0.955
0.976
0.981 0.945 0.986 0.991 0.876 0.882
Beta-IPM-PA
0.962
0.977
0.984 0.950 0.986 0.991 0.676 0.693
Contamination Setting 2: Random Labels
ijcnn1.tr mushrooms a8a
ocr epsilon zeta gisette real-sim
KL-IPM-perceptron 0.886
0.858
0.820 0.750 0.737 0.516 0.698 0.680
KL-IPM-PA
0.855
0.942
0.817 0.674 0.758 0.545 0.827 0.741
Beta-IPM-perceptron 0.911
0.980
0.825 0.755 0.886 0.642 0.888 0.948
Beta-IPM-PA
0.913
0.999
0.830 0.723 0.890 0.624 0.942 0.958
rcv1
citeseer imdb news20 url webspam kdda kddb
KL-IPM-perceptron 0.600
0.657
0.611 0.644 0.971 0.951 0.739 0.734
KL-IPM-PA
0.701
0.685
0.684 0.730 0.971 0.960 0.761 0.757
Beta-IPM-perceptron 0.919
0.836
0.826 0.717 0.981 0.986 0.853 0.833
Beta-IPM-PA
0.910
0.916
0.943 0.730 0.985 0.985 0.868 0.868

the adversarial/random settings with those in the clean setting. The contamination negatively affected the results on almost all datasets. On the random setting, where 80% of
the shards are contaminated, the damage to the results tended to be more severe than thaton the adversarial setting. Second, let us compare the performances of Beta-IPM and
KL-IPM in the adversarial/random settings. One can see that Beta-IPM outperformed
KL-IPM on almost all datasets. Indeed, one many datasets Beta-IPM performed almost
as well as KL-IPM under the clean setting; this confirms that Beta-IPM can remove theinfluence of contamination.
Fig. 4 shows the classification results of Beta-IPM with a single iteration perceptron
for several values of β. The optimal value with this dataset was β = 10−5 , and theaccuracy with this β value showed a steady rise in epochs. The accuracy after epoch

11
news20 (adversarial setting)

1.0

0.9

0.7

KL-IPM-Perceptron
Beta-IPM-Perceptron (beta=10−3 )0.6

Beta-IPM-Perceptron (beta=10−4)

Beta-IPM-Perceptron (beta=10−5 )0.5

Beta-IPM-Perceptron (beta=10

0

10

20
30
Epoch

40

−6

0.8
0.7
Beta-IPM-Perceptron (beta=10−5 )0.6

Beta-IPM-PA (beta=10−5Beta-IPM-PA2 (beta=10

)

0.4

)

Beta-IPM-PA1 (beta=10−6 )0.5
50

Accuracy

0.8

Accuracy

Accuracy

0.9

0.4

news20 (adversarial setting)

1.0

0

10

20
30
Epoch

−6

)

40

50

1.00
0.95
0.90
0.85
0.80
0.75
0.70
0.65
0.60

news20 (adversarial setting)Beta-IPM-Perceptron (beta=10−5 )Beta-IPM-PA (beta=10−5 )Single PA1 (C=10−2 )Single PA2 (C=10−3 )Single AROW (r=103 )

0

10

20
30
Epoch

40

50

Fig. 4. Classification accuracy Fig. 5. Classification accuracies Fig. 6. Classification accuof Beta-IPM with a single it- of Beta-IPM with various al- racy of Beta-IPM and single
eration perceptron for several gorithms. The algorithms were machine
PA-I/PA-II/AROW.
values of beta. The algorithms run with news20 in the adver- The algorithms were run with
were run with news20 in the ad- sarial setting.
news20 in the adversarial
versarial setting.
setting.

optimal beta

50 was nearly 95%. With a β value smaller than the optimal one (β = 10−6 ) andwith no beta (KL-IPM-perceptron), the algorithm failed to suppress the influence of theadversarial workers. Conversely, with β values bigger than optimal (β = 10−3 ), theregularization was so strong that even the influence of some of the correct workers was
suppressed. As a result, the learning rate with this beta value was very slow.
Fig. 5 compares several different algorithms
Dataset dimension and optimal beta with the best beta values. Given a proper value-110of β, Beta-IPM with a perceptron or PA success-2
10fully learned the parameter vectors. However,-3
10
PA-I and PA-II4 , the noise-tolerant version of PA,-410-5
did not perform well. These results indicate that10
-610
robustness in a distributed environment is essen-7
10tially different from that of single machine online-810
learning: while we assume some fraction of the
4
1
2
3
5
6
8
7
10 10 10 10 10 10 10 10data is clean and the rest is contaminated, robust# of features
learning in a single machine aims to learn in enviFig. 7. Number of features and optimal ronments where the clean and contaminated data
value of beta in the adversarial setting. are mixed. A possible hypothesis is that, the regEach point corresponds to a dataset.
ularization of the learning rate in PA-I and PA-II
obscured the difference between clean and contaminated shards, which made the accuracies of IPM with PA-I and PA-II poor.
Fig. 6 compares Beta-IPM-perceptron with a single machine PA-I or PA-II and
AROW [6]. The hyper-parameter C in PA-I and PA-II and r in AROW were optimizedin {10−4, 10−3 , ..., 104 }. The data of all 100 shards were put into a single shard in
the single machine experiments. The two Beta-IPM algorithms performed better than
the single machine algorithms. These results are empirical evidence that Beta-IPM can
reduce the weights of adversarial shards.
Fig. 7 shows the optimal value of beta as a function of the number of features.
Overall, in high-dimensional datasets, the value of beta tends to be small. The reason
4

The parameter C in PA-I and PA-II was set to be 0.001.

12

for this is that the weight in Beta-IPM (Equation (6)) is a multivariate Gaussian, which
is a product of exponentials over all dimensions and thus is small at high dimensions.

7 Conclusion
We studied robust distributed training of linear classifiers. By minimizing the divergence, we devised a criterion for determining the weights in IPM. Experiments revealed
that the performance of IPM is significantly recovered on many contaminated datasets
by determining the weights based on the beta divergence. An interesting direction of future work is to remove the statistiscal assumption of Gaussian distribution, by allowing
more wider class of distributions, or non-parametric models.

References
1. Aberdeen, D., Pacovsky, O., Slater, A.: The learning behind gmail priority inbox. In: LCCC:NIPS 2010 Workshop on Learning on Cores, Clusters and Clouds (2010)
2. Basu, A., Harris, I.R., Hjort, N.L., Jones, M.C.: Robust and efficient estimation by minimising a density power divergence. Biometrika 85(3), 549–559 (1998)
3. Chouvardas, S., Slavakis, K., Theodoridis, S.: Adaptive robust distributed learning in diffusion sensor networks. IEEE Transactions on Signal Processing 59(10), 4692–4707 (2011)
4. Chu, C.T., Kim, S.K., Lin, Y.A., Yu, Y., Bradski, G.R., Ng, A.Y., Olukotun, K.: Map-reducefor machine learning on multicore. In: NIPS. pp. 281–288 (2006)
5. Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., Singer, Y.: Online passive-aggressivealgorithms. Journal of Machine Learning Research 7, 551–585 (2006)
6. Crammer, K., Kulesza, A., Dredze, M.: Adaptive regularization of weight vectors. Machine
Learning 91(2), 155–187 (2013)
7. Curtsinger, C., Livshits, B., Zorn, B.G., Seifert, C.: Zozzle: Fast and precise in-browser
javascript malware detection. In: USENIX Security Symposium (2011)
8. Daumé III, H., Phillips, J.M., Saha, A., Venkatasubramanian, S.: Efficient protocols for distributed classification and optimization. In: ALT. pp. 154–168 (2012)
9. Dekel, O., Shamir, O., Xiao, L.: Learning to classify with missing and corrupted features.
Mach. Learn. 81(2), 149–178 (Nov 2010)
10. Djuric, N., Grbovic, M., Vucetic, S.: Distributed confidence-weighted classification onmapreduce. In: IEEE Bigdata (2013)
11. Eguchi, S., Kano, Y.: Robustifying maximum likelihood estimation. In: Technical report,
Institute of Statistical Mathematics, June 2001 (2001)
12. Gimpel, K., Das, D., Smith, N.A.: Distributed asynchronous online learning for natural language processing. pp. 213–222. CoNLL ’10 (2010)
13. Gong, P., Ye, J., Zhang, C.: Robust multi-task feature learning. In: KDD. pp. 895–903 (2012)
14. Hall, K.B., Inc, G., Gilpin, S., Mann, G.: Mapreduce/bigtable for distributed optimization.
In: LCCC: NIPS 2010 Workshop on Learning on Cores, Clusters and Clouds (2010)
15. Hoi, S.C.H., Wang, J., Zhao, P.: Exact soft confidence-weighted learning. In: ICML (2012)
16. Mann, G., McDonald, R.T., Mohri, M., Silberman, N., Walker, D.: Efficient large-scale distributed training of conditional maximum entropy models. In: NIPS. pp. 1231–1239 (2009)
17. McDonald, R., Hall, K., Mann, G.: Distributed training strategies for the structured perceptron. In: NAACL. pp. 456–464. HLT ’10 (2010)
18. Meyer, T.A., Whateley, B.: Spambayes: Effective open-source, bayesian based, email classification system. In: CEAS (2004)

13
19. Rahm, E., Do, H.H.: Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin 23, 2000 (2000)
20. Rosenblatt, F.: The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review 65(6), 386–408 (1958)
21. Runnalls, A.R.: A kullback-leibler approach to gaussian mixture reduction. IEEE Trans.
Aerosp. Electron. Syst pp. 989–999 (2007)
22. Tsitsiklis, J., Bertsekas, D., Athans, M.: Distributed asynchronous deterministic and stochastic gradient optimization algorithms. Automatic Control, IEEE Transactions on 31(9), 803–
812 (Sep 1986)
23. Xu, H., Leng, C.: Robust multi-task regression with grossly corrupted observations. Journalof Machine Learning Research - Proceedings Track 22, 1341–1349 (2012)
24. Zinkevich, M., Smola, A.J., Langford, J.: Slow learners are fast. In: NIPS. pp. 2331–2339(2009)A

Appendix

A.1 Derivation of KL-IPM and Beta-IPM
Derivation of KL-IPM We want to show that a mixed weight based on KL-IPM minimizes the KL-divergence between P and Q based on the parameter vectors {w(1,n) , ..., w(M,n) }.
The following lemma states that KL divergence minimization based on Gaussian distributions preserves the mean and covariance.
Lemma 5. [Theorem 3.2 in [21]] Let P be an arbitrary probability distribution on Rd
with a well-defined mean µ∗ and covariance matrix Σ∗ , where Σ∗ is strictly positivedefinite. Let Q be a Gaussian distribution with mean µ and covariance matrix Σ. The
unique minimum value of DKL (P ||Q) is achieved when µ = µ∗ and Σ = Σ∗ .
The inequality (4) follows by using Lemma
5 and the fact that the empirical meanPof P on the parameter vectors is (1/M ) i w(i,n) .

Derivation of Beta-IPM Let the parameters of the workers be {w(1,n) , ..., w(M,n) },which is generated from a distribution P , and Q(µ, Σ) be a Gaussian distribution. We
would like to minimize the beta divergence, namely, w(avg,n) = arg min Dβ (P ||Q(µ, Σ)).
µThen,
Dβ (P ||Q(µ, Σ))
(11)
Z
Z
1
1
= −
P (w)Qβ (w|µ, Σ)dw +Qβ+1 (w|µ, Σ)dw + Const. (12)
β
β+1
Z
1
1
β
Qβ+1 (w|µ, Σ)dw + Const.,(13)= − EP (w) [Q (w|µ, Σ)] +β
β+1

where Const. is a term independent of µ and Σ, and EP (w) is the expectation under the assumption that w follows the probability distribution P (w). Replacing the
expectation of the first term with an empirical expectation over the parameter vectors{w(1,n) , ..., w(M,n) } yields
ZM
i
1 X 1 h β (i,n)1(13) = −Q (w|µ, Σ) +Qβ+1 (w|µ, Σ)dw.
(14)
β i=1 Mβ+1

14

Algorithm 2 Single iteration Passive Aggressive
1: T = {(xt , yt )}, w
2: for t = 1, ..., |T | do3:ŷt ← sign(w · xt )4:lt ← max (0, 1 − yt (w · xt ))5:
τt ← lt /||xt ||26:w ← w + τt yt x t
7: end for

The multivariate Gaussian
Q is explicitly written as Q(w|µ, Σ) = Z(Σ) exp S(w|µ, Σ),pwhere Z(Σ) = 1/ (2π)d |Σ| and S(w|µ, Σ) = − 21 (w − µ)⊤ Σ−1 (w − µ). The second term in (14) is, from the property of multivariate Gaussian distribution,Z1
Qβ+1 (w|µ, Σ)dw = Z(Σ)β (β + 1)−1−d/2 ,(15)
β+1which is independent on µ. By using these facts, the first derivative of Dβ (P ||Q(µ, Σ))is equivalent to the one of the first term in the RHS of (14), which is transformed as,
(
)
(
)
M
M
i
1 X 1 h β (i,n)
Z(Σ)β
d X
1
d
(i,n)
−
Q (w
|µ, Σ)=−
exp S(w, µ, Σ) .
dµβ i=1 MβM
dµ i=1β(M)Z(Σ)β X1=
exp S(w(i,n) , µ, Σ)(βΣ−1 )(w(i,n) − µ)
βM
β
i=1
(
)
M
β
X
1
Z(Σ)
−1
(i,n)
(i,n)
exp S(w, µ, Σ)(wβΣ− µ) .
(16)
=
βM
β
i=1
Therefore, we obtain
(
)
M
M
i
X
d
1
1 X 1 h β (i,n)
exp S(w(i,n) , µ, Σ)(w(i,n) − µ) = 0−
Q (w|µ, Σ)=0 ⇔dµβ i=1 M
β
i=1
PM
(i,n)
, µ, β1 Σ)w(i,n)
i=1 exp S(w. (17)⇔µ=PM(j,n) , µ, 1 Σ)
j=1 exp S(wβ

RHS of (17) states that µ that minimizes Dβ (P ||Q) is a weighted mean of eachw(i,n) with weight exp S(w(i,n) , µ, β1 Σ). Unfortunately, the weight exp S(w(i,n) , µ, β1 Σ)on the RHS includes µ, and thus, an exact solution is unattainable. To get a reasonable
solution, we can approximate µ and Σ on the RHS of (17) by the mean and covarianceof the samples {w(1,n) , ..., w(M,n) }, which finally yields (6).
A.2 Proof of Theorem 3 and 4
The crux in the mistake/loss bound proofs in online classifiers is to find some valuethat can be bounded from both the upper and lower side: in the case of PA we boundthe value ∆n = ||w(avg,n−1) − u|| − ||w(avg,n) − u||. By using these lower and upperbounds we obtain Lemma 6, which leads to the proofs of Theorem 3 and 4.

15

Lemma 6. Let the index t = 1, ..., ki,n denotes the data points on shard i that theworker suffered non-zero losses, and (xi,t , yi,t ) be the data point at that round. More∗over, let li,t be the corresponding loss of the worker, and τi,t = li,t /||xi,t ||2 , and li,tbethe loss of any constant classifier u with the data point. Then,


ki,n
N X
M

X
X

∗
≤ ||u||.
(18)
τi,t (2li,t − τi,t ||xi,t ||2 − 2li,t
)
αi,n


n=1

t=1

i=1

Proof (Lemma 6). Consider shard i in epoch n. Let ∆i,n = ||w(avg,n−1) − u||2 −||w(i,n) − u||2 . Notice that the parameter vector is updated only when the loss is nonzero, and For 1 ≤ t ≤ ki,n , let w([i,n]+t) be the parameter vector on shard i in epoch nin the round just before the t-th loss occurred. Also, for t = ki,n + 1, let w([i,n]+t) =w(i,n) . Notice that w([i,n]+1) = w(avg,n−1) . The update per single loss is,||w([i,n]+t)− u||2 − ||w([i,n]+(t+1))− u||2

= ||w([i,n]+t)− u||2 − ||w([i,n]+t)− u + yi,t τi,t xi,t ||2on2= ||w([i,n]+t)) − u||2 − ||w([i,n]+t) − u||2 + 2yi,t τi,t (w([i,n]+t) − u) · xi,t + τi,t||xi,t ||22= −2yi,t τi,t (w([i,n]+t) − u) · xi,t − τi,t||xi,t ||2 .

(19)

Since we assumed li,t > 0 with this data point, yi,t (w([i,n]+t) · xi,t ) = 1 − li,t and∗li,t≥ 1 − yi,t (u · xi,t ) always holds. Thus, (19) can be bounded as,∗2∗(19) ≥ 2τi,t ((1−li,t)−(1−li,t ))−τi,t||xi,t ||2 = τi,t (2li,t −τi,t ||xi,t ||2 −2li,t). (20)

By using (20), ∆i,n is bounded as,∆i,n = ||w(avg,n−1) − u||2 − ||w(i,n) − u||2=

ki,n 
X
t=1||w([i,n]+t)− u||2 − ||w([i,n]+(t+1))− u||2

ki,n

≥

X
t=1



∗
τi,t (2li,t − τi,t ||xi,t ||2 − 2li,t
) .

(21)

We now lower-bound ∆n as follows:∆n = ||w(avg,n−1)− u||2 − ||w(avg,n)− u||2 = ||w(avg,n−1)− u||2 − ||
≥
≥

M
X
i=1

M
X
i=1

X
i

αi,n (w(i,n)− u)||2M Xαi,n ∆i,n
αi,n ||w(avg,n−1) − u||2 − ||w(i,n) − u||2 =
i=1

ki,n

αi,n

X
t=1

∗
τi,t (2li,t − τi,t ||xi,t ||2 − 2li,t
) ,

(22)

P
where we have used i αi,n = 1 in going between the first and second line, and used(21) at the last transformation.

16

On the other hand, the sum of ∆n is upper-bounded as follows:
N
X

∆n =

n=1

N 

X
||w(avg,n−1) − u||2 − ||w(avg,n) − u||2

n=1

= ||w(avg,0) − u||2 − ||w(avg,N ) − u||2 ≤ ||u||,(23)

where the last inequality follows from the fact that the initial parameter vector is thezero vector and ||w(avg,N ) − u||2 ≥ 0. Using (22) and (23) yields (18).
⊓⊔∗Proof (Theorem 3). By using the fact that li,t
= 0, li,t = τi,t ||xi,t ||2 , Lemma 6 istransformed as follows:


ki,n
N X
M
X
X
(li,t )2 αi,n
≤ ||u||2 .
(24)
||xi,t ||2 
n=1

i=1

t=1

With the fact that ||xi,t || < R, we finally obtain


ki,n
N X
M

X
X
αi,n
(li,t )2 ≤ ||u||2 R2 .


n=1

i=1

(25)

t=1

Li,n , the cumulative squared loss the worker i suffers during epoch n, corresponds toPki,n2
t=1 (li,t ) . Therefore, the inequality (25) is equivalent to (9).
⊓⊔∗Proof (Theorem 4). Next, we consider the case where li,t
is not necessarily zero. Let us
assume ||xi,t || = 1. Notice that τi,t = li,t /||xi,t ||2 = li,t . By these facts and Lemma 6,


ki,n
M
N X

X
X

∗
(li,t )2 − 2li,t li,t)
αi,n≤ ||u||2 .
(26)


n=1

t=1

i=1

Let

XN

v
u N M
uX X
=t
α
n=1 i=1

v
uN M
ki,n
ki,n
uX X
X
X
∗ )2 .
2αi,n(li,t ) , and YN = t
(li,t
i,n
t=1

(27)

t=1

n=1 i=1

2
Using the Cauchy-Schwarz inequality on the LHS of (26), we obtain X
pN − 2XN YN ≤2||u|| , which is a quadratic inequality of XN , and thus X√
YN2 + ||u||2 ≤N ≤ YN +√√||u|| + 2YN , where we used the fact that a + b ≤ a + b for a, b ≥ 0. By explicitly
writing XN and YN we obtain
v
v
u N M
u N M
ki,n
ki,n
uX X
uX X
X
X
t
(28)
(l )2 ≤ ||u|| + 2t(l∗ )2 .
α
α
i,t

i,n

n=1 i=1t=1i,nn=1 i=1

i,t

t=1

Pki,n
The cumulative squared loss the worker i suffers in epoch n is Li,n = t=1(li,t )2 .
Pki,n ∗ 2∗
Moreover, Li ≥ t=1 (li,t ) holds because the index t runs the subset of data on shard
i. Taking these into consideration, we finally obtain (10).
⊓
⊔

17

Algorithm 3 Single iteration perceptron
1: T = {(xt , yt )}, w
2: for t = 1, ..., |T | do3:ŷt ← sign(w · xt )4:
if yt 6= ŷt then5:w ← w + yt x t
6:
end if
7: end for

A.3 Proof of Theorem 2:Here, we prove the non-separable mistake bound of the IPM (Algorithm 1) combined with the single iteration perceptron (Algorithm 3). Remember that, w(i,n) is theparameter vector returned by the ith worker at the end of the nth iteration, w(avg,n)is the mixed vector at the end of epoch n, ki,n is the number of mistakes occurringin shard i during epoch n. Let index t = 1, ..., ki,n denotes the rounds on shard ithat the worker made a mistake5 , and (xi,t , yi,t ) be the data point at that round. andξi,t = max{0, γ − yi,t (u · xi,t )}. Let w[i,n]−k be the parameter vector of worker i in
the nth iteration k mistakes before w(i,n) . Notice that w[i,n]−ki,n = w(avg,n−1) . Just
like the case of the single-machine perceptron, we prove both the lower and the upperbound of a norm. By definition, for any data point (xi,t , yi,t ), we have(i,n)

yi,t (u · xi,t ) ≥ γ − ξi,t .

(29)(avg,n−1)

We now bound (w−w) · u, which expresses how the parameter vector
changes in a single iteration with worker i.
w(i,n) · u = (w[i,n]−1 + yi,t xi,t ) · u = w[i,n]−1 · u + yi,t (xi,t · u)≥w... ≥ w[i,n]−1· u + (γ − ξi,t )X·u+[i,n]−ki,nt∈mistakes on shard i(γ − ξi,t ),

(30)
(31)
(32)

Since Ξi is the sum of ξ over all data points in shard i (including, but not only t-indexed
data points that the worker misclassified),XX
Ξi =ξi,t′ ≥
ξi,t(33)
t′ ∈shard it∈mistakes on shard iholds. By using (32) and (33), we obtain the following:
w(i,n) · u ≥ w[i,n]−ki,n · u + ki,n γ − Ξi=w(avg,n−1)· u + ki,n γ − Ξi .

(34)
(35)

By using (35) and the fact that w(avg,n) is the weighted sum of the vectors returned by
all workers, we obtainw(avg,n) · u ≥ w(avg,n−1) · u +
5

M
X
i=1

αi,n (ki,n γ − Ξi ) .

Note that the mistake of the worker is different from the mistake of constant classifier u.

(36)

18

Moreover, by summing (36) over all epochs we obtain
N X
M
X

w(avg,N ) · u ≥n=1 i=1αi,n (ki,n γ − Ξi ) ,(37)

where we have used the fact that w(avg,0) = 0.
So far, we have proven the lower bound. On the other hand, the upper bound in
the separable case (inequality (IH2) in [17]) also holds in our non-separable case. The
upper bound inequality is,||w(avg,N ) ||2 ≤

N X
M
X

αi,n ki,n R2 .

(38)

n=1 i=1

By using (37) and (38), as well as the fact ||u|| = 1 we obtain the bound:M
N X
X

n=1 i=1!2αi,n (ki,n γ − Ξi )≤ (w(avg,N ) · u)2(39)≤ ||w(avg,N ) ||2 ||u||2 ≤ ||w(avg,N ) ||2(40)≤
By using XN =formed as:

PN

n=1

PM

N X
M
X

αi,n ki,n R2 .

(41)

PN

(42)

n=1 i=1i=1 αi,n ki,n and YN=

n=1(γXN − YN )2 ≤ XN R2 ,PM

i=1 αi,n Ξi , (41) is trans-

or, equally,2
γ 2 XN− (R2 + 2γYN )XN + YN2 ≤ 0,

which is a quadratic inequality of XN . The possible maximum XN isp(R2 + 2γYN ) + (R2 + 2γYN )2 − 4γ 2 YN2
XN ≤
2γ 2
2(R2 + 2γYN )R2 + 2γYN
≤
=
.
2
2γ
γ2

(43)

(44)

The explicit representation of (44) is the final inequality we obtain. That is,
N X
MX

n=1 i=1αi,n ki,n ≤

N M
2 XX
R2
αi,n Ξi .
+γ2
γ n=1 i=1(45)⊓⊔