Online and Distributed Robust Regressions
under Adversarial Data Corruption

arXiv:1710.00904v1 [cs.DS] 2 Oct 2017

Xuchao Zhang† , Liang Zhao‡ , Arnold P. Boedihardjo§ , Chang-Tien Lu†
† Virginia Tech, Falls Church, VA, USA
‡ George Mason University, Fairfax, VA, USA
§ U. S. Army Corps of Engineers, Alexandria, VA, USA
† {xuczhang, ctlu}@vt.edu, ‡ lzhao9@gmu.edu, § arnold.p.boedihardjo@usace.army.mil
Abstract—In today’s era of big data, robust least-squares
regression becomes a more challenging problem when considering the adversarial corruption along with explosive growth of
datasets. Traditional robust methods can handle the noise but
suffer from several challenges when applied in huge dataset
including 1) computational infeasibility of handling an entire
dataset at once, 2) existence of heterogeneously distributed
corruption, and 3) difficulty in corruption estimation when
data cannot be entirely loaded. This paper proposes online and
distributed robust regression approaches, both of which can
concurrently address all the above challenges. Specifically, the
distributed algorithm optimizes the regression coefficients of each
data block via heuristic hard thresholding and combines all the
estimates in a distributed robust consolidation. Furthermore,
an online version of the distributed algorithm is proposed to
incrementally update the existing estimates with new incoming
data. We also prove that our algorithms benefit from strong
robustness guarantees in terms of regression coefficient recovery
with a constant upper bound on the error of state-of-the-art batch
methods. Extensive experiments on synthetic and real datasets
demonstrate that our approaches are superior to those of existing
methods in effectiveness, with competitive efficiency.

I. I NTRODUCTION
In the era of data explosion, the fast-growing amount of data
makes processing entire datasets at once remarkably difficult.
For instance, urban Internet of Things (IoT) systems [1] can
produce millions of data records every second in monitoring
air quality, energy consumption, and traffic congestion. More
challenging, the presence of noise and corruption in realworld data can be inevitably caused by accidental outliers
[2], transmission loss [3], or even adversarial data attacks [4].
As the most popular statistical approach, the traditional leastsquares regression method is vulnerable to outlier observations
[5] and not scalable to large datasets [6]. By considering both
robustness and scalability in a least-squares regression model,
we study scalable robust least-squares regression (SRLR) to
handle the problem of learning a reliable set of regression
coefficients given a large dataset with several adversarial
corruptions in its response vector. A commonly adopted model
from existing robust regression methods [7][8] assumes that
the observed response is obtained from the generative model
y = X T β∗ + u, where β∗ is the true regression coefficients
that we wish to recover and u is the corruption vector with
arbitrary values. However, in the SRLR problem, our goal is to
recover the true regression coefficients under the assumption
that both the observed response y and data matrix X are
too large to be loaded into a single machine. Due to the
ubiquitousness of data corruptions and explosive data growth,
SRLR has become a critical component of several important

real-world applications in various domains such as economics
[9], signal processing [10], and image processing [11].
Existing robust learning methods typically focus on modeling the entire dataset at once; however, they may meet the
bottleneck in terms of computation and memory as more and
more datasets are becoming too large to be handled integrally.
For those seeking to address this issue, the major challenges
can be summarized as follows. 1) Computational infeasibility
of handling the entire dataset at once. Existing robust
methods typically generate the predictor by learning on the
entire training dataset. However, the explosive growth of data
makes it infeasible to handle the entire dataset up to a terabyte
or even petabyte at once. Therefore, a scalable algorithm
is required to handle the robust regression task for massive datasets. 2) Existence of heterogeneously distributed
corruption. Due to the unpredictability of corruptions, the
corrupted samples can be arbitrarily distributed in the whole
dataset. Considering the entire dataset as the combination
of multiple mini-batches, some batches may contain large
amounts of outliers. Thus, simply applying the robust method
on each batch and averaging all the estimates together is not
an ideal strategy, as some estimates will be arbitrarily poor
and break down the overall performance of robustness. 3)
Difficulty in corruption estimation when data cannot be
entirely loaded. Most robust methods assume the corruption
ratio of input data is a known parameter; however, if a small
batch of data can be loaded as inputs for robust methods,
it is infeasible to know the corruption ratio of all the minibatches. Moreover, simply using a unified corruption ratio for
all the mini-batches is clearly not an ideal solution as corrupted
samples can be regarded as uncorrupted, and vice versa. In
addition, even though some robust methods can estimate the
corruption ratio based on data observations, it is also infeasible
to estimate the ratio when corruption in one mini-batch is
greater than 50%. However, the situation can be very common
when corruption is heterogeneously distributed.
In order to simultaneously address all these technical challenges, this paper presents a novel Distributed Robust Leastsquares Regression (DRLR) method and its online version,
named Online Roubst Least-squares Regression (ORLR) to
handle the scalable robust regression problem in large datasets
with adversarial corruption. In DRLR, the regression coefficient of each mini-batch is optimized via heuristic hard thresholding, and then all the estimates are combined in distributed
robust consolidation. Based on DRLR, the ORLR algorithm
incrementally updates the existing estimates by replacing old

corrupted estimates with those of new incoming data, which
is more efficient than DRLR in handling new data and reflects
the time-varying characteristics. Also, we prove that both
DRLR and ORLR preserve the overall robustness of regression
coefficients in the entire dataset. The main contributions of this
paper are as follows:
• Formulating a framework for the SRLR problem. A
framework is proposed for scalable robust least-squares
regression problem where the entire data with adversarial
corruption is too large to store in memory all at once.
Specifically, given a large dataset with adversarial corruptions, a reliable set of regression coefficients is learned
with limited memory.
• Proposing online and distributed algorithms to handle
the adversarial corruption. By utilizing robust consolidation methods, we propose both online and distributed
algorithms to obtain overall robustness even though the
corruption is arbitrarily distributed. Moreover, the online
algorithm performs more efficiently in handling new incoming data and presents the time-varying characteristics
of regression coefficients.
• Providing a rigorous robustness guarantee for regression coefficient recovery. We prove that our online and
distributed algorithms recover the true regression coefficient with a constant upper bound on the error of state-ofthe-art batch methods under the assumption that corruption can be heterogeneously distributed. Specifically, the
upper bound of online algorithm will be infinitely close
to distributed algorithm when the number of mini-batches
is large enough.
• Conducting extensive experiments for performance
evaluations. The proposed method was evaluated on
both synthetic data and real-world datasets with various
corruption and data-size settings. The results demonstrate
that the proposed approaches consistently outperform existing methods along multiple metrics with a competitive
running time.
The rest of this paper is organized as follows. Section II reviews background and related work, and Section III introduces
the problem setup. The proposed online and distributed robust
regression algorithms are presented in Section IV. Section
V presents the proof of recovery guarantee in regression
coefficients. The experiments on both synthetic and real-world
datasets are presented in Section VI, and the paper concludes
with a summary of the research in Section VII.
II. R ELATED W ORK
The work related to this paper is summarized in two
categories below.
Robust regression model: A large body of literature on
the robust regression problem has been built over the last
few decades. Most of studies focus on handling stochastic
noise or small bounded noise [12][13][14], but these methods,
modeling the corruption on stochastic distributions, cannot
be applied to data that may exhibit malicious corruption [4].
Some studies assume the adversarial corruption in the data,
but most of them lack the strong guarantee of regression
coefficients recovery under the arbitrary corruption assumption
[4][6]. Chen et al. [4] proposed a robust algorithm based on a
trimmed inner product, but the recovery boundary is not tight

to ground truth in a massive dataset. McWilliams et al. [6]
proposed a sub-sampling algorithm for large-scale corrupted
linear regression, but their recovery result is not close to
an exact recovery [7]. To pursue exact recovery results for
robust regression problem, some studies focused on L1 penalty
based convex formulations [15][16]. However, these methods
imposed severe restrictions on the data distribution such as
row-sampling from an incoherent orthogonal matrix[16].
Currently, most research in this area requires the corruption
ratio parameter, which is difficult to determine under the
assumption that the dataset can be arbitrarily corrupted. For
instance, She and Owen [17] rely on a regularization parameter
to control the size of the uncorrupted set based on softthresholding. Instead of a regularization parameter, Chen et
al. [18] require the upper bound of the outliers number, which
is also difficult to estimate. Bhatia et al. [7] proposed a hardthesholding algorithm with a strong guarantee of coefficient
recovery under a mild assumption on input data. However,
its recovery error can be more than doubled in size if the
corruption ratio is far from the true value. Recently, Zhang
et al. [8] proposed a robust algorithm that learns the optimal
uncorrupted set via a heuristic method. However, all of these
approaches require the entire training dataset to be loaded and
learned at once, which is infeasible to apply in massive and
fast growing data.
Online and distributed learning: Most of the existing
online learning methods optimize surrogate functions such
as stochastic gradient descent [19][20] to update estimates
incrementally. For instance, Duchi et al. [19] proposed a new,
informative subgradient method that dynamically incorporates
the geometric knowledge of the data observed in earlier
iterations. Some adaptive linear regression methods such as
recursive least squares [21] and online passive aggressive algorithms [22] provide an incremental update on the regression
model for new data to capture time-varying characteristics.
However, these methods cannot handle the outlier samples
in the streaming data. For distributed learning [23][24], most
approaches such as MapReduce [25] focus on distributed
solutions for large-scale problems that are not robust to noise
and corruption in real-world data.
The existing distributed robust optimization methods can be
divided into two categories: those that use moment information
[26][27] and those that utilize directly on the probability
distributions [28][29][30]. For instance, Delage et al. [31]
proposed a model that describes uncertainty in both the distribution form and moments in a distributed robust stochastic
program. However, these methods assume either the moment
information or probability distribution as prior knowledge,
which is difficult to know in practice. In robust online learning,
few methods have been proposed in the past few years. For
instance, Sharma et al. [32] proposed an online smoothed
passive-aggressive algorithm to update estimates incrementally in a robust manner. However, the method assumes the
corruption is in stochastic distributions, which is infeasible
for data with adversarial corruption. Recently, Feng et al.
[33] proposed an online robust learning approach that gives
a provable robustness guarantee under the assumption that
data corruption is heterogeneously distributed. However, the
method requires that the corruption ratio of each data batch
be given as parameters, which is not practical for users to

estimate.

TABLE I
M ATH N OTATIONS

III. P ROBLEM F ORMULATION
In this section, the problem addressed by this research is
formulated.
In the setting of online and distributed learning, we consider
the samples to be provided in a sequence of mini batches as
{X (1) , . . . , X (m) }, where X (i) ∈ p×n represents the sample
data for the ith batch. We assume the corresponding response
vector y (i) ∈ n×1 is generated using the following model:

T
y (i) = X (i) β∗ + u(i) + ε(i)
(1)

R

R

R

where β∗ ∈ p×1 is the ground truth coefficients of the
regression model and u(i) is the adversarial corruption vector
of the ith mini-batch. ε(i) represents the additive dense noise
(i)
for the ith mini batch, where εj ∼ N (0, σ 2 ). The notations
used in this paper are summarized in Table I.
The goal of addressing our problem is to recover the
regression coefficients β̂ and determine the uncorrupted set
Ŝ for the entire dataset. The problem is formally defined as
follows:
β̂, Ŝ = arg min yS − XST β
β,S

s.t.



S∈ Ω Z

2
2
(i)

∀i ≤ m, ∀j ≤ |Z (i) | : Zj ≥ h(r (i) )

(2)
We define Z (i) as the estimated uncorrupted set for the ith
mini-batch and Z = {Z (1) , ... , Z (m) } as the collection of
uncorrupted sets for all the mini-batches. The size of set Z (i)
is represented as |Z (i) |. The function Ω(·) consolidates the
estimates of all the mini-batches in terms of the distributed or
online setting. yS restricts the row of y to indices in S, and
XS signifies that the columns of X are restricted to indices
in S. Therefore, we have yS ∈ |S|×1 and XS ∈ p×|S| ,
where p is the number of features and |S| is the size of the
(i)
uncorrupted set S ⊂ [m · n]. The notation Z∗ = supp(u(i) )
represents the true set of uncorrupted points in the ith minibatch. Also, the residual vector r (i) ∈ n of the ith mini-batch
T
is defined as r (i) = y (i) − X (i) β. Specifically, we use
(i)
the notation rZ to represent the |Z (i) |-dimensional residual
vector containing the components in Z (i) . The constraint of
Z (i) is determined by function h(·), which is designed to
estimate the size of the uncorrupted set of each mini-batch
according to the residual vector r (i) . The uncorrupted set of
each mini-batch will be consolidated by function Ω(·) in both
online and distributed approaches. The details of the heuristic
function h(·) and consolidation function Ω(·) will be explained
in Section IV.
The problem defined above is very challenging in the
following three aspects. First, the least-squares function can be
naively solved by taking the derivative to zero. However, as the
data samples of all m mini-batches are too large to be loaded
into memory simultaneously, it is impossible to calculate β
from all the batches directly by this method. Moreover, based
on the fact that the corruption ratio can be varied for each
mini-batch, we cannot simply estimate the corruption set by
using a fixed ratio for each mini-batch. In addition, since
corruption is not uniformly distributed, some mini-batches
may contain an overwhelmingly amount of corrupted samples.

R

R

R

Notations
X (i) ∈ p×n
y (i) ∈ n×1
β (i) ∈ p×1
(i)
β∗ ∈ p×1
u(i) ∈ n×1
r (i) ∈ n×1
ε(i) ∈ n×1
Z (i) ⊆ [n]
(i)
Z∗ ⊆ [n]
S ⊆ [m · n]

R
R
R
R
R
R
R

Explanations
collection of data samples of the ith mini-batch
response vector of the ith mini-batch
estimated regression coefficient of the ith batch
ground truth regression coefficient of the ith batch
corruption vector of the ith batch
residual vector of the ith batch
dense noise vector of the ith batch
estimated uncorrupted set of the ith batch
(i)
ground truth uncorrupted set, where Z∗ = supp(u(i) )
estimated uncorrupted set of entire dataset

The corresponding estimates of regression coefficients can
be arbitrarily poor and break down the overall result. In the
next section, we present both online and distributed robust
regression algorithms based on heuristic hard thresholding and
robust consolidation to address all three challenges.
IV. M ETHODOLOGY
In this section, we propose both online and distributed robust regression algorithms to handle large datasets in multiple
mini-batches. To handle each single mini-batch among these
mini-batches, a heuristic robust regression method (HRR) is
proposed in Section IV-A. Based on HRR, a new approach,
DRLR, is presented in Section IV-B to process multiple minibatches in distributed manner. Furthermore, in Section IV-C,
a novel online version of DRLR, namely ORLR, is proposed
to incrementally update the estimate of regression coefficients
with new incoming data.
A. Single-Batch Heuristic Robust Regression
In order to efficiently solve the single batch problem when
m = 1 in Equation (2), we propose a robust regression
algorithm, HRR, based on heuristic hard thresholding. The
algorithm heuristically determines the uncorrupted set Z (i)
for the ith mini-batch according to its residual vector r (i) .
Specifically, a novel heuristic function h(·) is proposed to
estimate the lower-bound size of the uncorrupted set Z (i) for
each mini batch, which is formally defined as
(i)

(i)

h(r ) := arg max τ

s.t.

τ ∈Z+ ,τ ≤n

(i)
rϕ(τ )

≤

2τ rϕ(τo )
τo

(3)

where the residual vector of ith mini-batch is denoted by

T
(i)
r (i) = y (i) − X (i) β (i) , and rϕ(k) represents the k th
elements of r (i) in ascending order of magnitude. The variable
τo in the constraint is defined as
τo = arg min
dn/2e≤τ ≤n



(i)

rϕ(τ )

2

(i)

−

2

krZτ 0 k2
τ0

(4)

where τ 0 = τ − dn/2e and Zτ 0 is the position set containing
the smallest τ 0 elements in residual r (i) .
The design of the heuristic estimator follows a natural
intuition that data points with unbounded corruption always
have a residual higher in magnitude than that of uncorrupted
data. Moreover, the constraint in Equation (3) ensures the
residual of the largest element τ in our estimation cannot be

Algorithm 1: H RR A LGORITHM

R

1
2
3
4
5
6
7
8

R

Input: Corrupted data samples X ∈ p×n and response vector
y ∈ n×1 for single mini batch, tolerance 
Output: solution β̂, Ẑ
Z0 = [n], t ← 0
repeat
β t+1 ← (XZt XZTt )−1 XZt yZt
r t+1 ← |y − X T β t+1 |
Zt+1 ← H(r t+1 ), where H(·) is defined in Equation (5).
t←t+1
t+1
t
− rZ
until krZ
k < n
t 2
t+1
t+1
return β , Zt+1

too much larger than the residual of a smaller element τo . If
the element τo is too small, some uncorrupted elements will
be excluded from our estimation, but if the element is too
large, some corrupted elements will be included. The formal
definition of τo is shown in Equation (4), in which τo is defined
(i) 2
as a value whose squared residual is closest to krZτ 0 k2 /τ 0 ,
0
where τ is less than the ground truth threshold τ∗ . This
(i)
(i)
design ensures that |Z∗ ∩ Zt | ≥ τ − n/2, which means
(i)
at least τ − n/2 elements are correctly estimated in Zt . In
addition, the precision of the estimated uncorrupted set can
be easily achieved when fewer elements are included in the
estimation, but with low recall value. To increase the recall of
our estimation, the objective function in Equation (3) chooses
the maximum uncorrupted set size.
Applying the uncorrupted set size generated by h(·), the
heuristic hard thresholding is defined as follows:
Definition 1 (Heuristic Hard Thresholding). Defining
th
ϕ−1
r (i) as the position of the i element in residual vector r’s
ascending order of magnitude, the heuristic hard thresholding
of r is defined as
H(r) = {i ∈ [n] : ϕ−1
r (i) ≤ h(r)}

(5)

The optimization of Z (i) is formulated as solving Equation
(5), where the set returned by H(r (i) ) will be used to determine regression coefficients β (i) .
The details of the HRR algorithm are shown in Algorithm
1, which follows an intuitive strategy of updating regression
coefficient β (i) to provide a better fit for the current estimated
uncorrupted set Zt in Line 3, and updating the residual vector
in Line 4. It then estimates the uncorrupted set Zt+1 via
heuristic hard thresholding in Line 5 based on residual vector
r in the current iteration. The algorithm continues until the
change in the residual vector falls within a small range.

j th mini-batches respectively, the distance between the two
estimates is defined as
di,j = kβ (i) − β (j) k2

Based on the definition of estimate distance, we define the
distance vector of the ith mini-batch as d(i) ∈ m×1 , where m
(i)
is the total number of batches and dj represents the distance
th
from the estimate of the i batch to the j th batch (1 ≤ j ≤ m).
We also define σk (d(i) ) and δk (d(i) ) as the value and index of
the k th smallest value in distance vector d(i) , respectively. For
instance, if the 3rd batch is the 5th smallest distance in d(i) with
(i)
d3 = 0.3, then we have σ5 (d(i) ) = 0.3 and δ5 (d(i) ) = 3.

R

Definition 3 (Pivot Batch). Given a set of mini-batch estimates {β (1) , . . . , β (m) } and defining d(i) as the distance
vector of the ith batch, the pth batch is defined as pivot batch
if it satisfies
p = arg min σm̃ (d(i) )

Definition 2 (Estimate Distance). Defining β (i) and β (j)
as the estimate of the regression coefficients for the ith and

(7)

i

where m̃ = bm/2c + 1 is the upper number of half
batches. By using the definition of pivot batch, we define the
dominating set as follows.
Definition 4 (Dominating Set). Given a set of mini-batch
estimates {β (1) , . . . , β (m) } and defining d(p) as the distance
vector of the pivot batch, the dominating set Ψ is defined as
follows:

Ψ = δk (d(p) )|1 ≤ k ≤ m̃
(8)
The dominating set Ψ selects the smallest m̃ batches from
the distance vector d(p) of the pivot batch, which makes a
small distance between the pivot batch and any batch j ∈ Ψ.
The property will be used later in the proof of Lemma 3.
Then we define the general robust consolidation of a set of
regression coefficients as follows.
Definition 5 (Robust Consolidation). Given a set of minibatch estimates {β (1) , . . . , β (m) } and using Ψ to denote its
dominating set, the robust consolidation of the given estimates
β̂ is defined as follows:

 X
1
(i)
kβ − βk2
(9)
β̂ = arg min
T
β
i∈Ψ

The DRLR algorithm, shown in Algorithm 2, uses m minibatches’ data as input and outputs the consolidated estimate
Algorithm 2: D RLR A LGORITHM

B. Distributed Robust Regression
Given data samples {(X (1) , y (1) ), . . . , (X (m) , y (m) )} in
a sequence of mini-batches, a distributed robust regression
algorithm, named DRLR, is proposed to optimize the robust
regression coefficients in distributed approach without loading
entire data at one time. Before we dive into the details of the
DRLR algorithm, we provide some key definitions.

(6)

Input: Corrupted data {(X (1) , y (1) ), . . . , (X (m) , y (m) )} in m
mini batches, where X (i) ∈ p×n and y (i) ∈ n×1 .
Output: solution β̂
for i = 1..m do
β (i) ← HRR(X (i) , y (i) )

R

1
2
3
4
5
6

(i)
p = arg
i σm̃ (d )
 min(p)
Ψ = δk (d )|1 ≤ k ≤ m̃
 P
β̂ = arg minβ T1 i∈Ψ kβ (i) − βk2
return β̂

R

// Optimize pivot batch p
// Find dominating set Ψ
// Robust consolidation

Algorithm 3: O RLR A LGORITHM

R

p P
β
*

̭
β

b

1
2
3
4

Uncorrupted Batch Set ψ* Domina ng Set ψ

5
6

Fig. 1. Example for Distributed Robust Least-squares Regression

of regression coefficients β̂. First, the algorithm optimizes the
coefficient estimate β (i) of each mini batch in Line 1-2, then it
combines all the estimates of mini-batches in terms of overall
robustness via distributed robust consolidation. Specifically,
the algorithm determines the pivot batch based on all the
estimates in Line 3 and generates the dominating set Ψ in
Line 4. Finally, all the batch estimates are combined via
robust consolidation in Line 5. Figure 1 shows an example
of distributed robust consolidation. The domination set Ψ
contains m̃ closest batches to pivot batch p and the green
circle node denotes the uncorrupted batch whose distance to
ground truth coefficients β∗ is less than a small error bound
ε. We call the set containing all the green circle nodes as
uncorrupted batch set Ψ∗ . The example shows a case that only
one uncorrupted batch b is contained in Ψ, which determines
the distance between β∗ and pivot batch p. The distance
between β∗ and β̂ is upper bounded by the summation of
distance dβ∗ ,p and dβ̂,p .
C. Online Robust Regression
The DRLR algorithm, proposed in Section IV-B, provides
a distributed approach when a large amount of data has
been collected. In this section, we present an online robust

C

1

ψ*
p+
β
*

R

C

b

β+

R

β
*

N

b

N
̭
β

ψ+

ψ*

2

ψ+

β+

p+
̭
β
d

Fig. 2. Examples for Online Robust Least-squares Regression

7

R

Input: New incoming corrupted data X + ∈ p×n and
y + ∈ n×1 . Previous m mini-batch estimates
Π = {β (1) , . . . , β (m) } and their corresponding Ψ.
Output: solution β̂, Π, Ψ
β + ← HRR(X + , y + )
s ← min([m] \ Ψ)
// Select removed estimate s
Π+ = Π \ {β (s) } ∪ {β + }
p+ = arg mini σm̃ (d(i) )
// Optimize new pivot batch p+

+
(p+ )
Ψ = δk (d
)|1 ≤ k ≤ m̃
// Find new dominating set Ψ+
1 P
(i)
β̂ = arg minβ m̃ i∈Ψ+ kβ − βk2 // Robust consolidation
return β̂, Π+ , Ψ+

regression algorithm, named ORLR, that incrementally updates
the robust estimate based on new incoming data. Specifically,
suppose the regression coefficients of the previous m minibatches {β (1) , . . . , β (m) } have been estimated by DRLR, the
ORLR algorithm achieves an incremental update of robust consolidation β̂ when new incoming mini-batch data X + ∈ p×n
and y + ∈ n×1 are given.
The details of algorithm ORLR are shown in Algorithm 3.
In Line 1, the regression coefficients β + of the new data is
optimized by HRR algorithm. The index of swapped estimate
s is generated in Line 2 by selecting the minimum value
from [m] \ Ψ, which represents the set of estimates that are
not included in dominating set Ψ. Since new estimates are
appended to the tail of Π, the usage of minimum index ensures
that the oldest corrupted estimate can be swapped out. In Line
3, the selected estimate β (s) is removed from Π while the new
estimate β + is appended to the tail of Π. Lines 4 through 6
re-consolidate all the estimates based on newly updated Π in
the same steps as the DRLR algorithm. It is important to note
that the distance vectors used in Lines 4 and 5 are also updated
corresponding to the new Π. Also, the ORLR algorithm can
be invoked repeatedly for the incoming mini-batches, where
the outputs Π and Ψ of the previous invocation can be used
as the input of the next one.
Figure 2 shows two cases for ORLR algorithm. The first
case shows the condition that the new estimate β + ∈ Ψ+ but
not belongs to Ψ∗ , and estimate s is removed. Although the
estimate b is excluded from Ψ+ , the distance dβ∗ ,p+ can still
be determined by the position of b. The error between β∗ and
β̂ can be increased, but still upper bounded by dβ∗ ,p+ and
dβ̂,p+ . In the second case, β + ∈ {Ψ∗ ∩ Ψ+ }. Because the
farthest node d in Ψ+ is replaced by β + , the error between
β∗ and β̂ can be decreased, but it still upper bounded by the
position of pivot batch p+ . Last but not least, the third case is
β+ ∈
/ {Ψ∗ ∪ Ψ+ }, which is not shown in Figure 2. The case
is the same as Figure 1 except a new estimate is added outside
of Ψ∗ and Ψ. However, the change will not impact the result
of β̂.

R

R

V. T HEORETICAL R ECOVERY A NALYSIS
In this section, the recovery properties of regression coefficients for the proposed distributed and online algorithms are
presented in Theorem 4 and 5, respectively. Before that, the
recovery property of HRR is presented in Theorem 1.
To prove the theoretical recovery of regression coefficients
for a single mini-batch, we require that the least-squares

function satisfies the Subset Strong Convexity (SSC) and Subset
Strong Smoothness (SSS) properties, which are defined as
follows:
Definition 6 (SSC and SSS Properties). The least squares
2
function f (β) = kyS − XST βk2 satisfies the 2ζγ -Subset
Strong Convexity property and 2κγ -Subset Strong Smoothness
property if the following holds:
1
ζγ I  O2 fS (β)  κγ I
2

for ∀S ∈ Sγ

(10)

Note that Equation (10) is equivalent to:
ζγ ≤ min λmin (XS XST ) ≤ max λmax (XS XST ) ≤ κγ (11)
S∈Sγ
S∈Sγ
where λmin and λmax denote the smallest and largest
eigenvalues of matrix X, respectively.

R

Theorem 1 (HRR Recovery Property). Let X (i) ∈ p×n
be the given data matrix of the ith mini batch and the

T
corrupted response vector y (i) = X (i) β∗ + u(i) + ε(i)
with ku(i) k0 = γn. Let Σ0 be an invertible matrix such that
−1/2
(i)
(i)
2
X̃ (i) = Σ0 X (i) ; f (β) = kyS − X̃S βk2 satisfies the
SSC and SSS properties at level α, γ with 2ζ
α,γ and 2κα,γ.
ku(i) k
ϕα,γ
1
√
If the data satisfies ζ < 2 , after t = O log η1 √n 2
α

(i)

iterations, Algorithm 1 yields an -accurate solution βt with
Ckε(i) k
(i)
kβ∗ − βt k2 ≤  + √n 2 for some C > 0.
The proof of Theorem 1 can be found in the supplementary
material1 . The theoretical analyses of regression coefficients
recovery for Algorithm 2 and 3 are shown in the following.
Lemma 2. Suppose Algorithm 1 yields an -accurate solution
β̂ with corruption ratio γ0 , and m mini-batches of data have
a corruption ratio less than γ0 /2, more than b m
2 c + 1 batches
can yield an -accurate solution by Algorithm 1.
Proof. Let Ψ∗ denote the set of mini-batches that yield accurate solutions and γi represent the corruption ratio for the
ith mini-batch. Then we have:
m
(a) X

X

γi n ≤

γi n =

i

i∈[m]\Ψ∗
(b) γ

(γ0 n + 1)(m − |Ψ∗ |) ≤

0

γ0
·m·n
2

·m·n

2m
P

P
i γi n =
i∈Ψ∗ γi n +
PInequality (a) is based on
γ
n.
And
inequality
(a)
follows
each
corrupted
i
i∈[m]\Ψ∗
mini-batch that contains at least γ0 n + 1 corrupted samples.
Applying simple algebra steps, we have
|Ψ∗ | ≥ m −

γ0
2 mn

γ0 n + 1

≥m−

γ0
2 mn

γ0 n

≥

m
2

Since |Ψ∗ | is an integer, then we have |Ψ∗ | ≥ b m
2 c + 1.

kβ (i) − β∗ k2 ≤ . According to the triangle inequality, for
∀i ∈ Ψ∗ , it satisfies:
kβ (i) − β (k) k2 − kβ (k) − β∗ k2 ≤kβ (i) − β∗ k2 ≤ 
kβ (i) − β (k) k2 ≤2

Since |Ψ∗ | ≥ m̃, we have σm̃ (d(k) ) ≤ 2. According to
the definition of pivot batch p = arg mini σm̃ (d(i) ), we have
σm̃ (d(p) ) ≤ σm̃ (d(k) ) ≤ 2.
Theorem 4 (DRLR Recovery Property). Given data samples
in m mini batches {(X (1) , y (1) ), . . . , (X (m) , y (m) )} with a
corruption ratio of γ0 /2, Algorithm 2 yields an -accurate
solution β̂ with kβ̂ − β∗ k2 ≤ 5.
Proof. Let Ψ∗ denotes the set of mini-batches that yield accurate solutions. According to Lemma 2, we have |Ψ∗ | ≥
bm
2 c + 1. Because of Lemma 3, we have ∀i ∈ [1, m̃],
σi (d(p) ) ≤ 2, where p is the index of pivot batch and
m̃ = bm/2c + 1. Using Ψ = δk (d(p) )|1 ≤ k ≤ m̃ defined
in Algorithm 2, we have ∀i, j ∈ Ψ, kβ (i) − β (j) k2 ≤ 2. As
|Ψ∗ | ≥ b m
2 c+1, we have |Ψ∗ ∩Ψ| ≥ 1. For any k ∈ {Ψ∗ ∩Ψ},
we have the following two properties of the k th mini batch:
1) ∀i ∈ Ψ, kβ (k) − β (i) k2 ≤ 2; and 2) kβ (k) − β∗ k2 ≤ .
Applying these properties, we get the error bound of kβ̂−β∗ k2
as follows.
kβ̂ − β∗ k2 =kβ̂ − β (k) + β (k) − β∗ k2
(a)

≤ kβ̂ − β (k) k2 + kβ (k) − β∗ k2
(b) 1 X
1 X (i)
≤
kβ̂ − β (i) k2 +
kβ − β (k) k2 + 
m̃
m̃
i∈Ψ

i∈Ψ

(c)

1 X (k)
≤
kβ − β (i) k2 + 3 ≤ 5
m̃
i∈Ψ

Inequality (a) is based on the triangle inequalityPof the L2
norm, and inequality (b) follows kβ̂ −β (k) k2 = T1 i∈Ψ kβ̂ −
β (i) + β (i) − β (k) k2 . Inequity (c) follows the definition of β̂,
P
P
which makes i∈Ψ kβ̂ − β (i) k ≤ i∈Ψ kβ (k) − β (i) k.
Theorem 5 (ORLR Recovery Property). Given m
mini-batch estimates of regression coefficients Π =
{β (1) , . . . , β (m) }, their corresponding dominating set Ψ, and
incoming corrupted data X + ∈ p×n and y + ∈ n×1 ,
Algorithm 3 yields an -accurate solution β̂ with kβ̂ −β∗ k2 ≤
5 + 4
m̃ .

R

R

Proof. Let e and s denote the index of added and removed
mini-batch, respectively. According to Line 2 in Algorithm 3,
the removed batch s ∈
/ Ψ. As |Ψ∩Ψ∗ | ≥ 1, there exists a minibatch k ∈ {Ψ∩Ψ∗ } that satisfies: 1) ∀i ∈ Ψ, kβ (k) −β (i) k2 ≤
2; and 2) ∀j ∈ {Ψ+ \ e}, kβ (k) − β (j) k2 ≤ 2. So we have
kβ̂ − β (k) k2 =

1 X
kβ̂ − β (i) + β (i) − β (k) k2
m̃
+
i∈Ψ

Lemma 3. Given a set of mini-batch estimates
{β (1) , . . . , β (m) } with m̃ = bm/2c + 1, defining the
pth batch as its pivot batch, then we have σm̃ (d(p) ) ≤ 2.
Proof. Suppose k th mini-batch is in the uncorrupted set Ψ∗ ,
we have kβ (k) − β∗ k2 ≤ . Similarly, for ∀i ∈ Ψ∗ , we have
1 https://goo.gl/HRwZsp

(a)

1 X
1 X (i)
≤
kβ̂ − β (i) k2 +
kβ − β (k) k2
m̃
m̃
+
+
i∈Ψ

i∈Ψ

(b)

2 X (i)
≤
kβ − β (k) k2
m̃
+
i∈Ψ

Inequality (a) is based on the triangle inequality of the L2
norm,
follows the definition of β̂, which
P and inequality (b) P
has i∈Ψ+ kβ̂ − β (i) k ≤ i∈Ψ+ kβ (k) − β (i) k.

Two conditions exist for added mini batch e. For the
condition e ∈
/ Ψ+P
, the new dominating set Ψ+ = Ψ. So
2
(k)
kβ̂ − β k2 ≤ m̃ i∈Ψ kβ (i) − β (k) k2 ≤ 4. For condition
e ∈ Ψ+ , we have
kβ̂ − β (k) k2 ≤

2 X (i)
kβ − β (k) k2
m̃
+
i∈Ψ



X
2
≤
kβ (k) − β (e) k2 +
kβ (i) − β (k) k2
m̃
i∈{Ψ+ ∩Ψ}


(d) 4
2
(k)
(p)
(p)
(e)
≤ (m̃ − 1) +
kβ − β k2 + kβ − β k2
m̃
m̃
(e) 4
8
4
≤ 4 +
≤ (m̃ − 1) +
m̃
m̃
m̃ +
(c)

Inequality (c) expands the set Ψ into the new mini
batch e and set {Ψ+ ∩ Ψ}. Inequality (d) uses the fact that
∀i ∈ Ψ, kβ (k) − β (i) k2 ≤ 2 and the triangle inequality
of β (p) , where p is the pivot batch corresponding to Π.
As max(kβ (k) − β (p) k2 , kβ (p) − β (e) k2 ) ≤ 2, inequality (e) is satisfied. Combining two conditions, we conclude
kβ̂−β (k) k2 ≤ 4+ 4
m̃ . Therefore, the error bound of kβ̂−β∗ k2
is as follows.
kβ̂ − β∗ k2 ≤kβ̂ − β (k) k2 + kβ (k) − β∗ k2
(f )

≤ 4 +

4
4
+  ≤ 5 +
m̃
m̃

Inequality (f) utilizes the fact that kβ (k) − β∗ k2 ≤ . Note
that if m̃ is large enough, kβ̂ − β∗ k2 - 5, which is the same
as the error bound in Theorem 4.
VI. E XPERIMENT
In this section, the proposed algorithms DRLR and ORLR
are evaluated on both synthetic and real-world datasets. After
the experiment setup has been introduced in Section VI-A,
we present results on the effectiveness of the methods against
several existing methods on both synthetic and real-world
datasets, along with an analysis of efficiency for all the comparison methods, in Section VI-B. All the experiments were
conducted on a 64-bit machine with an Intel(R) Core(TM)
quad-core processor (i7CPU@3.6GHz) and 32.0GB memory.
Details of both the source code and datasets used in the
experiment can be downloaded here2 .
A. Experiment Setup
1) Datasets and Labels: Our dataset is composed of synthetic and real-world data. The simulation samples were randomly generated according to the model in Equation (1) for
each mini-batch, sampling the regression coefficients β∗ ∈ p
as a random unit norm vector. The covariance data X (i)
for each mini-batch was drawn independently and identically
distributed from xi ∼ N (0, Ip ) and the uncorrupted response

T
(i)
variables were generated as y∗ = X (i) β∗ + ε(i) , where
(i)
the additive dense noise was εi ∼ N (0, σ 2 ). The corrupted
response vector for each mini-batch was generated as y (i) =
(i)
y∗ +u(i) , where the corruption vector u(i) was sampled from
(i)
(i)
the uniform distribution [−5ky∗ k∞ , 5ky∗ k∞ ]. The set of
(i)
uncorrupted points Z∗ was selected as a uniformly random
(i)
γ n-sized subset of [n], where γ (i) is the corruption ratio of

R

the ith mini-batch. We define γ as the corruption ratio of the
total m mini-batches;
γ (i) is randomly chosen in the condition
Pm (i)
of γ = i γ , where γ should be less than 1/2 to ensure
the number of uncorrupted samples is greater than the number
of corrupted ones.
The real-world datasets we use contain house rental transaction data from New York City and Los Angeles on Airbnb3
website from January 2015 to October 2016. The datasets can
be downloaded here4 . For the New York City dataset, we use
the first 321,530 data samples from January 2015 to December
2015 as training data and the remaining 329,187 samples from
January to October 2016 as testing data. For the Los Angeles
dataset, the first 106,438 samples from May 2015 to May 2016
are chosen as training data, and the remaining 103,711 samples
are used as testing data. In each dataset, there were 21 features
after data preprocessing, including the number of beds and
bathrooms, location, and average price in the area.
2) Evaluation Metrics: For the synthetic data, we measured
the performance of the regression coefficients recovery using
the averaged L2 error
e = kβ̂ − β∗ k2
where β̂ represents the recovered coefficients for each
compared method and β∗ is the ground truth regression
coefficients. To compare the scalability of each method, the
CPU running time for each of the competing methods was
also measured.
For the real-world dataset, we use the mean absolute error
(MAE) to evaluate the performance of rental price prediction.
Defining ŷ and y as the predicted price and ground truth price,
respectively, the mean absolute error between ŷ and y can be
presented as follows.
n

MAE(ŷ, y) =

1X
ŷi − yi
n i=1

3) Comparison Methods: The following methods are included in the performance comparison presented here: The
averaged ordinary least-squares (OLS-AVG) method takes the
average over the regression coefficients of each mini-batch,
which is computed by the ordinary least-squares method.
RLHH-AVG applies a recently proposed robust method, RLHH
[8], on each mini-batch and averages the regression coefficients of all the mini-batches. Different from OLS-AVG,
RLHH-AVG can estimate the corrupted samples in each minibatch by a heuristic method. The online passive aggressive
algorithm (OPAA) [22] is an online algorithm for adaptive
linear regression, which updates the model incrementally for
each new data sample. We set the threshold parameter ξ, which
controls the inaccuracy sensitively, to 22. We also compared
our method to an online robust learning approach (ORL) [33],
which addresses both the robustness and scalability issues in
the regression problem. As the method requires a parameter for
the corruption ratio, which is difficult to estimate in practice,
we chose two versions with different parameter settings:
ORL* and ORL-H. ORL* uses the true corruption ratio as
its parameter, and ORL-H sets the outlier fraction λ to 0.5,
which is a recommended setting in [33] if it is unknown. For
3 https://www.airbnb.com/

2 https://goo.gl/b5qqYK

4 http://insideairbnb.com/get-the-data.html

kβ − β ∗ k 2

2.0
1.5

1.5
1.0

kβ − β ∗ k 2

2.5

1.0

4

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

3
kβ − β ∗ k 2

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

3.0

2

0.5

0.5
0.0

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

1
0

0.0
0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

(a) p=100, n=5K, b=10, dense noise

(b) p=100, n=10K, b=10, dense noise

(c) p=400, n=10K, b=10, dense noise

3.5
3.0
2.5
2.0
1.5
1.0
0.5
0.0

kβ − β ∗ k 2

0.6
0.4
0.2
0.0

2.0
1.5

kβ − β ∗ k 2

0.8

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

kβ − β ∗ k 2

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

1.0

1.0

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

0.5
0.0

0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

(d) p=100, n=10K, b=30, dense noise

(e) p=100, n=5K, b=10, no dense noise

(f) p=200, n=10K, b=20, no dense noise

Fig. 3. Performance on regression coefficients recovery for different corruption ratios in uniform distribution.

our proposed methods, we use DRLR and ORLR to evaluate
our methods in both distributed and online settings. For ORLR,
we set the number of previous mini-batch estimates to seven
if not specified. All the results from comparison methods will
be averaged over 10 runs.
B. Performance
This section presents the recovery performance of the regression coefficients.
1) Recovery of regression coefficients: We selected seven
competing methods with which to evaluate the recovery
performance of all the mini-batches: OLS-AVG, RLHH-AVG,
OPAA, ORL-H, ORL*, DRLR, and ORLR. Figure 3 shows the
performance of coefficients recovery for different corruption
ratios in uniform distribution. Specifically, Figures 3(a) and
3(b) show the recovery performance for different data sizes
when the feature number is fixed. Looking at the results, we
can conclude: 1) The DRLR and ORLR methods outperform
TABLE II
P ERFORMANCE ON R EGRESSION C OEFFICIENTS R ECOVERY
IN D IFFERENT C ORRUPTED M INI - BATCHES

0/20

1/20

2/20

4/20

6/20

8/20

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
ORLR

0.126
0.011
1.537
0.346
0.078
0.025

0.133
0.065
1.577
0.362
0.089
0.026

0.147
0.096
1.385
0.358
0.092
0.027

0.169
0.131
1.573
0.392
0.106
0.026

0.193
0.163
1.539
0.417
0.113
0.026

0.208
0.185
1.483
0.442
0.150
0.026

DRLR

0.015

0.015

0.015

0.015

0.015

0.015

all the competing methods, including ORL*, whose corruption
ratio parameter uses the ground truth value. Also, the error
of the ORLR method has a small difference compared to
DRLR, which indicates that the online robust consolidation
performs as well as the distributed one. 2) The results of
the ORL methods are significantly affected by their corruption
ratio parameters; ORL-H performs almost three times as badly
as ORL* when the corruption ratio is less than 25%. When
the corruption ratio increases, the error of ORL-H decreases
because the actual corruption ratio is closer to 0.5, which
is the estimated corruption ratio of ORL-H. However, both
DRLR and ORLR perform consistently throughout, with no
impact of the parameter. 3) RLHH-AVG has very competitive
performance when the corruption ratio is less than 30% because almost no mini-batch contains corrupted samples larger
than 50% when the corruption samples are randomly chosen.
However, when the corruption ratio increases, some of the
batches may contain large amounts of outliers, which makes
some estimates be arbitrarily poor and break down the overall
performance. Thus, although RLHH-AVG works well on minibatches with fewer outliers, it cannot handle the case when
the corrupted samples are arbitrarily distributed. 4) OPAA
generally exhibits worse performance than the other algorithms
because the incremental update for each data sample makes
it very sensitive to outliers. Figures 3(c) and 3(d) show the
similar performance when the number of features and batches
increases. Figures 3(e) and 3(f) show that both the DRLR and
ORLR methods still outperform the other methods without
dense noise, with both achieving an exact recovery of ground
truth regression coefficients β∗ .

TABLE III
M EAN A BSOLUTE E RROR OF R ENTAL P RICE P REDICTION

New York City (Corruption Ratio)

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

Running Time(s)

4
3

3.256±0.449
2.823±0.000
91.287±51.475
6.832±0.004
6.538±0.293
2.824±0.000
2.824±0.001

3.519±0.797
2.824±0.000
100.864±72.239
6.828±0.007
6.384±0.274
2.824±0.000
2.824±0.000

5%

10%

4.641±0.664
3.994±0.002
150.668±52.344
6.819±0.045
6.257±0.497
3.995±0.005
3.997±0.008

30%

6

1

5
4

40%

Avg.

4.356±1.582
42.713±19.304
152.479±57.553
6.573±0.189
6.471±0.190
4.342±1.784
3.563±0.935

3.867±0.981
19.327±16.417
111.690±56.790
6.754±0.109
6.439±0.229
3.200±0.461
2.983±0.225

30%

40%

Avg.

6.199±1.443
28.788±47.322
121.880±55.938
6.619±0.300
6.308±0.377
4.837±1.108
4.466±1.141

6.797±2.822
30.414±35.719
146.425±104.995
6.317±0.394
6.186±0.531
6.336±2.388
5.802±1.990

5.624±1.445
14.257±16.667
148.308±76.321
6.633±0.172
6.294±0.376
4.632±0.702
4.452±0.630

3.976±0.786
4.230±1.292
13.092±25.354
35.184±37.426
121.087±64.618
92.735±38.063
6.732±0.240
6.803±0.107
6.394±0.208
6.406±0.180
2.823±0.000
3.185±0.523
2.823±0.000
2.883±0.187
Los Angeles (Corruption Ratio)
20%

7

OLS
RLHH
OPAA
ORL-H
ORL*
DRLR
ORLR

2

0

20%

4.876±0.948
5.607±1.349
3.998±0.003
4.092±0.290
209.298±124.058 113.267±44.270
6.745±0.039
6.667±0.084
6.303±0.304
6.415±0.172
3.999±0.008
3.993±0.003
3.999±0.009
3.994±0.004

Running Time(s)

5

10%

12

OLS
RLHH
OPAA
ORL-H
ORL*
DRLR
ORLR

3
2

(a) p=200, n=5K, b=10, no dense noise

0

8
6
4
2

1
0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40
Corruption Ratio

OLS
RLHH
OPAA
ORL-H
ORL*
DRLR
ORLR

10
Running Time(s)

OLS-AVG
RLHH-AVG
OPAA
ORL-H
ORL*
DRLR
ORLR

5%

2

4
6
8
Data Size Per Batch(K)

10

(b) p=100, cr=0.4, b=10, dense noise

0

10

15

20
25
Batch Number

30

(c) p=100, cr=0.4, n=5K, dense noise

Fig. 4. Running time for different corruption ratios and data sizes

2) Performance on different corrupted mini-batches: Table
II shows the performance of regression coefficient recovery
in different settings of corrupted mini-batches, ranging from
zero to eight corrupted mini-batches out of 20 mini-batches
in total. Each corrupted mini-batch used in the experiment
contains 90% corrupted samples and each uncorrupted minibatch has 10% corrupted samples. We show the result of
averaged L2 error kβ̂ − β∗ k2 in 10 different synthetic datasets
with randomly ordered mini-batches. From the result in Table
II, we conclude: 1) When some mini-batches are corrupted,
the DRLR method outperforms all the competing methods, and
ORLR achieves the best performance compared to other online
methods. 2) RLHH-AVG performs the best when no mini-batch
is corrupted, but its recovery error is dramatically increased
when the number of corrupted mini-batches increases. However, our methods perform consistently when the number of
corrupted mini-batches increases. 3) ORL* has competitive
performance in different settings of corrupted mini-batches.
However, its recovery error still increases two times when the
number of corrupted mini-batches increases from two to eight.
3) Result of Rental Price Prediction: To evaluate the robustness of our proposed methods in a real-world dataset,

we compared the performance of rental price prediction in
different corruption settings, ranging from 5% to 40%. The
additional corruption was sampled from the uniform distribution [−0.5|yi |, 0.5|yi |], where |yi | represents the absolute
price value of the ith sample data. Table III shows the mean
absolute error of rental price prediction and its corresponding
standard deviation from 10 runs in the New York City and Los
Angeles datasets. From the result, we can conclude: 1) The
DRLR and ORLR methods outperform all the other methods
in different corruption settings except when the corruption
ratio is less than 10%. 2) The RLHH-AVG method performs
the best when the corruption ratio is less than or equal to
10%. However, as the corruption ratio rises, the error increases
dramatically because some mini-batches are entirely corrupted.
3) The OLS-AVG method has a very competitive performance
in all the corruption settings because the deviation of sampled
corruption is small, which is less than 50% from the labeled
data.
4) Efficiency: To evaluate the efficiency of our proposed
method, we compared the performance of all the competing
methods for three different data settings: different corruption
ratios, data sizes per mini-batch, and batch numbers. In

general, as Figure 4 shows, we can conclude: 1) The OPAA
method outperforms the other methods in the three different
settings because it does not consider the robustness of the data.
Also, the ORL-H and ORL* methods have performed similarly
to OPAA method, as they use fixed corruption ratios without
taking additional steps to estimate the corruption ratio. 2) The
DRLR and ORLR methods have very competitive performance
even though they take additional corruption estimation and
robust consolidation steps for each mini-batch. Moreover, with
increases of the corruption ratio, data size per batch, and
batch number, the running time of both the DRLR and ORLR
methods increases linearly, which is an important characteristic
for the two methods to be extended to a large scale problem. In
addition, our methods outperform the RLHH method although
it only estimates the corruption for each mini-batch but ignores
the overall robustness, which indicates that the corruption
estimation step in our method performs more efficiently than
that in RLHH.
VII. C ONCLUSION
In this paper, distributed and online robust regression algorithms, DRLR and ORLR, are proposed to handle the scalable
least squares regression problem in the presence of adversarial
corruption. To achieve this, we proposed a heuristic hard
thresholding method to estimate the corruption set for each
mini-batch and designed both online and distributed robust
consolidation methods to ensure the overall robustness. We
demonstrate that our algorithms can yield a constant upper
bound on the coefficient recovery error of state-of-the-art
robust regression methods. Extensive experiments on both
synthetic data and real-world rental price data demonstrated
that the proposed algorithms outperform the effectiveness of
other comparable methods with competitive efficiency.
ACKNOWLEDGMENT
This material is based upon work supported in part by the
U. S. military Research Laboratory and the U. S. military
Research Office under contract number W911NF-12-1-0445.
R EFERENCES
[1] Andrea Zanella, Nicola Bui, Angelo Castellani, Lorenzo Vangelista, and
Michele Zorzi. Internet of things for smart cities. IEEE Internet of
Things journal, 1(1):22–32, 2014.
[2] Peter J Rousseeuw and Annick M Leroy. Robust regression and outlier
detection, volume 589. John wiley & sons, 2005.
[3] B Saltzberg. Performance of an efficient parallel data transmission
system. IEEE Transactions on Communication Technology, 15(6):805–
811, 1967.
[4] Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse
regression under adversarial corruption. In ICML (3), pages 774–782,
2013.
[5] RARD Maronna, R Douglas Martin, and Victor Yohai. Robust statistics.
John Wiley & Sons, Chichester. ISBN, 2006.
[6] Brian McWilliams, Gabriel Krummenacher, Mario Lucic, and
Joachim M Buhmann. Fast and robust least squares estimation in
corrupted linear models. In Advances in Neural Information Processing
Systems, pages 415–423, 2014.
[7] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression
via hard thresholding. In Advances in Neural Information Processing
Systems, pages 721–729, 2015.
[8] Xuchao Zhang, Liang Zhao, Arnold P. Boedihardjo, and Chang-Tien Lu.
Robust regression via heuristic hard thresholding. In Proceedings of the
Twenty-Sixth International Joint Conference on Artificial Intelligence,
IJCAI’17. AAAI Press, 2017.
[9] Markus Baldauf and JMC Santos Silva. On the use of robust regression
in econometrics. Economics Letters, 114(1):124–127, 2012.

[10] A. M. Zoubir, V. Koivunen, Y. Chakhchoukh, and M. Muma. Robust
estimation in signal processing: A tutorial-style treatment of fundamental
concepts. IEEE Signal Processing Magazine, 29(4):61–80, July 2012.
[11] Imran Naseem, Roberto Togneri, and Mohammed Bennamoun. Robust
regression for face recognition. Pattern Recognition, 45(1):104–118,
2012.
[12] Yudong Chen and Constantine Caramanis. Noisy and missing data
regression: Distribution-oblivious support recovery. In Sanjoy Dasgupta
and David Mcallester, editors, Proceedings of the 30th International
Conference on Machine Learning (ICML-13), volume 28, pages 383–
391. JMLR Workshop and Conference Proceedings, 2013.
[13] Po-Ling Loh and Martin J Wainwright. High-dimensional regression
with noisy and missing data: Provable guarantees with non-convexity.
In Advances in Neural Information Processing Systems, pages 2726–
2734, 2011.
[14] Mathieu Rosenbaum, Alexandre B Tsybakov, et al. Sparse recovery
under matrix uncertainty. The Annals of Statistics, 38(5):2620–2651,
2010.
[15] John Wright and Yi Ma. Dense error correction via l1-minimization.
IEEE Trans. Inf. Theor., 56(7):3540–3560, July 2010.
[16] Nam H Nguyen and Trac D Tran. Exact recoverability from dense
corrupted observations via l1-minimization. IEEE transactions on
information theory, 59(4):2017–2035, 2013.
[17] Yiyuan She and Art B. Owen. Outlier detection using nonconvex
penalized regression. Journal of the American Statistical Association,
106(494):626–639, 2011.
[18] Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse
regression under adversarial corruption. In Sanjoy Dasgupta and David
Mcallester, editors, Proceedings of the 30th International Conference
on Machine Learning (ICML-13), volume 28, pages 774–782. JMLR
Workshop and Conference Proceedings, May 2013.
[19] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient
methods for online learning and stochastic optimization. Journal of
Machine Learning Research, 12(Jul):2121–2159, 2011.
[20] Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online
learning for matrix factorization and sparse coding. Journal of Machine
Learning Research, 11(Jan):19–60, 2010.
[21] Yaakov Engel, Shie Mannor, and Ron Meir. The kernel recursive leastsquares algorithm. IEEE Transactions on signal processing, 52(8):2275–
2285, 2004.
[22] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and
Yoram Singer. Online passive-aggressive algorithms. Journal of Machine
Learning Research, 7(Mar):551–585, 2006.
[23] G. Mateos, J. A. Bazerque, and G. B. Giannakis. Distributed sparse linear regression. IEEE Transactions on Signal Processing, 58(10):5262–
5276, Oct 2010.
[24] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan
Eckstein. Distributed optimization and statistical learning via the
alternating direction method of multipliers. Foundations and Trends R
in Machine Learning, 3(1):1–122, 2011.
[25] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data
processing on large clusters. Communications of the ACM, 51(1):107–
113, 2008.
[26] Xuan Vinh Doan, Serge Kruk, and Henry Wolkowicz. A robust algorithm
for semidefinite programming. Optimization Methods and Software,
27(4-5):667–693, 2012.
[27] Seong-Cheol Kang, Theodora S Brisimi, and Ioannis Ch Paschalidis.
Distribution-dependent robust linear optimization with applications to
inventory control. Annals of operations research, 231(1):229–263, 2015.
[28] C Cromvik and M Patriksson. On the robustness of global optima and
stationary solutions to stochastic mathematical programs with equilibrium constraints, part 1: Theory. Journal of optimization theory and
applications, 144(3):461–478, 2010.
[29] Jitka Dupačová and Miloš Kopa. Robustness in stochastic programs with
risk constraints. Annals of Operations Research, 200(1):55–74, 2012.
[30] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand
Melenberg, and Gijs Rennen. Robust solutions of optimization problems
affected by uncertain probabilities. Management Science, 59(2):341–
357, 2013.
[31] Erick Delage and Yinyu Ye. Distributionally robust optimization
under moment uncertainty with application to data-driven problems.
Operations Research, 58(3):595–612, 2010.
[32] Shekhar Sharma, Swanand Khare, and Biao Huang. Robust online algorithm for adaptive linear regression parameter estimation and prediction.
Journal of Chemometrics, 30(6):308–323, 2016. cem.2792.
[33] Jiashi Feng, Huan Xu, and Shie Mannor. Outlier robust online learning.
CoRR, abs/1701.00251, 2017.

