Characterization of the equivalence of robustification and regularization in
linear and matrix regression
Dimitris Bertsimas
Sloan School of Management and Operations Research Center, MIT

arXiv:1411.6160v2 [] 25 Feb 2017

Martin S. Copenhaver
Operations Research Center, MIT

Abstract
The notion of developing statistical methods in machine learning which are robust to adversarial
perturbations in the underlying data has been the subject of increasing interest in recent years.
A common feature of this work is that the adversarial robustification often corresponds exactly to
regularization methods which appear as a loss function plus a penalty. In this paper we deepen and
extend the understanding of the connection between robustification and regularization (as achieved
by penalization) in regression problems. Specifically,
(a) In the context of linear regression, we characterize precisely under which conditions on the
model of uncertainty used and on the loss function penalties robustification and regularization
are equivalent.
(b) We extend the characterization of robustification and regularization to matrix regression problems (matrix completion and Principal Component Analysis).
Keywords: Convex programming, Robust optimization, Statistical regression, Regularization,
Penalty methods, Adversarial learning
1. Introduction
The development of predictive methods that perform well in the face of uncertainty is at the core
of modern machine learning and statistical practice. Indeed, the notion of regularization—loosely
speaking, a means of controlling the ability of a statistical model to generalize to new settings by
trading off with the model’s complexity—is at the very heart of such work [23]. Corresponding
regularized statistical methods, such as the Lasso for linear regression [43] and nuclear-norm-based
approaches to matrix completion [37, 9], are now ubiquitous and have seen widespread success in
practice.
Copenhaver is partially supported by the Department of Defense, Office of Naval Research, through the National
Defense Science and Engineering Graduate Fellowship.
Email addresses: dbertsim@mit.edu (Dimitris Bertsimas), mcopen@mit.edu (Martin S. Copenhaver)
✩

In parallel to the development of such regularization methods, it has been shown in the field of
robust optimization that under certain conditions these regularized problems result from the need to
immunize the statistical problem against adversarial perturbations in the data [18, 45, 2, 11]. Such
a robustification offers a different perspective on regularization methods by identifying which adversarial perturbations the model is protected against. Conversely, this can help to inform statistical
modeling decisions by identifying potential choices of regularizers. Further, this connection between
regularization and robustification offers the potential to use sophisticated data-driven methods in
robust optimization [5, 44] to design regularizers in a principled fashion.
With the continuing growth of the adversarial viewpoint in machine learning (e.g. the advent
of new deep learning methodologies such as generative adversarial networks [20, 21, 41]), it is
becoming increasingly important to better understand the connection between robustification and
regularization. Our goal in this paper is to shed new light on this relationship by focusing in
particular on linear and matrix regression problems. Specifically, our contributions include:
1. In the context of linear regression we demonstrate that in general such a robustification
procedure is not equivalent to regularization (via penalization). We characterize precisely
under which conditions on the model of uncertainty used and on the loss function penalties
one has that robustification is equivalent to regularization.
2. We break new ground by considering problems in the matrix setting, such as matrix completion and Principal Component Analysis (PCA). We show that the nuclear norm, a popular
penalty function used throughout this setting, arises directly through robustification. As
with the case of vector regression, we characterize under which conditions on the model of
uncertainty there is equivalence of robustification and regularization in the matrix setting.
The structure of the paper is as follows. In Section 2, we review background on norms and
consider robustification and regularization in the context of linear regression, focusing both on
their equivalence and non-equivalence. In Section 3, we turn our attention to regression with
underlying matrix variables, considering in depth both matrix completion and PCA. In Section 4,
we include some concluding remarks.
2. A robust perspective of linear regression
2.1. Norms and their duals
In this section, we introduce the necessary background on norms which we will use to address
the equivalence of robustification and regularization in the context of linear regression. Given a
vector space V ⊆ Rn we say that k · k : V → R is a norm if for all v, w ∈ V and α ∈ R
1. If kvk = 0, then v = 0,
2. kαvk = |α|kvk (absolute homogeneity), and
2

3. kv + wk ≤ kvk + kwk (triangle inequality).
If k · k satisfies conditions 2 and 3, but not 1, we call it a seminorm. For a norm k · k on Rn we
define its dual, denoted k · k∗ , to be

kβk∗ := maxn
x∈R

x′ β
,
kxk

where x′ denotes the transpose of x (and therefore x′ β is the usual inner product). For example,
P
the ℓp norms kβkp := ( i |βi |p )1/p for p ∈ [1, ∞) and kβk∞ := maxi |βi | satisfy a well-known

duality relation: ℓp∗ is dual to ℓp , where p∗ ∈ [1, ∞] with 1/p + 1/p∗ = 1. We call p∗ the conjugate

of p. More generally for matrix norms1 k · k on Rm×n the dual is defined analogously:
k∆k∗ :=

max

A∈Rm×n

hA, ∆i
,
kAk

where ∆ ∈ Rm×n and h·, ·i denotes the trace inner product: hA, ∆i = Tr(A′ ∆), where A′ denotes

the transpose of A. We note that the dual of the dual norm is the original norm [7].

Three widely used choices for matrix norms (see [25]) are Frobenius, spectral, and induced
norms. The definitions for these norms are given below for ∆ ∈ Rm×n and summarized in Table 1
for convenient reference.

1. The p-Frobenius norm, denoted k · kFp , is the entrywise ℓp norm on the entries of ∆:


k∆kFp := 

X
ij

1/p

|∆ij |p 

.

Analogous to before, Fp∗ is dual to Fp , where 1/p + 1/p∗ = 1.
2. The p-spectral (Schatten) norm, denoted k · kσp , is the ℓp norm on the singular values of the
matrix ∆:

k∆kσp := kµ(∆)kp ,
where µ(∆) denotes the vector containing the singular values of ∆. Again, σp∗ is dual to σp .
3. Finally we consider the class of induced norms. If g : Rm → R and h : Rn → R are norms,
then we define the induced norm k · k(h,g) as

k∆k(h,g) := maxn
β∈R

1

g(∆β)
.
h(β)

We treat a matrix norm as any norm on Rm×n which satisfies the three conditions of a usual vector norm,
although some authors reserve the term “matrix norm” for a norm on Rm×n which also satisfies a submultiplicativity
condition (see [25, pg. 341]).

3

An important special case occurs when g = ℓp and h = ℓq . When such norms are used, (q, p)
is used as shorthand to denote (ℓq , ℓp ). Induced norms are sometimes referred to as operator
norms. We reserve the term operator norm for the induced norm (ℓ2 , ℓ2 ) = (2, 2) = σ∞ , which
measures the largest singular value.
Name

Notation

p-Frobenius

Fp

Definition

1/p
X

|∆ij |p 

Description
entrywise ℓp norm

ij

p-spectral (Schatten)

σp

Induced

(h, g)

kµ(∆)kp
g(∆β)
max
β
h(β)

ℓp norm on the singular values
induced by norms g, h

Table 1: Matrix norms on ∆ ∈ Rm×n .

2.2. Uncertain regression
We now turn our attention to uncertain linear regression problems and regularization. The
starting point for our discussion is the standard problem
min g(y − Xβ),

β∈Rn

where y ∈ Rm and X ∈ Rm×n are data and g is some convex function, typically a norm. For

example, g = ℓ2 is least squares, while g = ℓ1 is known as least absolute deviation (LAD). In favor
of models which mitigate the effects of overfitting these are often replaced by the regularization
problem
min g(y − Xβ) + h(β),
β

where h :

Rn

→ R is some penalty function, typically taken to be convex. This approach often

aims to address overfitting by penalizing the complexity of the model, measured as h(β). (For a
more formal treatment using Hilbert space theory, see [6, 1].) For example, taking g = ℓ22 and
h = ℓ22 , we recover the so-called regularized least squares (RLS), also known as ridge regression
[23]. The choice of g = ℓ22 and h = ℓ1 leads to Lasso, or least absolute shrinkage and selection
operator, introduced in [43]. Lasso is often employed in scenarios where the solution β is desired
to be sparse, i.e., β has very few nonzero entries. Broadly speaking, regularization can take much
more general forms; for our purposes, we restrict our attention to regularization that appears in
the penalized form above.
In contrast to this approach, one may alternatively wish to re-examine the nominal regression
problem minβ g(y − Xβ) and instead attempt to solve this taking into account adversarial noise in

the data matrix X. As in [18, 31, 32, 2, 45], this approach may take the form
min max g(y − (X + ∆)β),
β

∆∈U

4

(1)

where the set U ⊆ Rm×n characterizes the user’s belief about uncertainty on the data matrix X.

This set U is known in the language of robust optimization [2, 4] as an uncertainty set and the
inner maximization problem max∆∈U g(y − (X + ∆)β) takes into account the worst-case error

(measured via g) over U . We call such a procedure robustification because it attempts to immunize
or robustify the regression problem from structural uncertainty in the data. Such an adversarial or
“worst-case” procedure is one of the key tenets of the area of robust optimization [2, 4].
As noted in the introduction, the adversarial perspective offers several attractive features. Let us
first focus on settings when robustification coincides with a regularization problem. In such a case,
the robustification identifies the adversarial perturbations the model is protected against, which
can in turn provide additional insight into the behavior of different regularizers. Further, technical
machinery developed for the construction of data-driven uncertainty sets in robust optimization
[5, 44] enables the potential for a principled framework for the design of regularization schemes, in
turn addressing a complex modeling decision encountered in practice.
Moreover, the adversarial approach is of interest in its own right, even if robustification does
not correspond directly to a regularization problem. This is evidenced in part by the burgeoning
success of generative adversarial networks and other methodologies in deep learning [20, 21, 41].
Further, the worst-case approach often leads to a more straightforward analysis of properties of
estimators [45] as well as algorithms for finding estimators [3].
Let us now return to the robustification problem. A natural choice of an uncertainty set which
gives rise to interpretability is the set U = {∆ ∈ Rm×n : k∆k ≤ λ}, where k · k is some matrix
norm and λ > 0. One can then write max∆∈U g(y − (X + ∆)β) as
e
max g(y − Xβ)
e
X

s. t.

e ≤ λ,
kX − Xk

e sufficiently close to the data matrix X. In what follows, if
or the worst case error taken over all X
k · k is a norm or seminorm, then we let Uk·k denote the ball of radius λ in k · k:
Uk·k = {∆ : k∆k ≤ λ}.
For example, UFp , Uσp , and U(h,g) denote uncertainty sets under the norms Fp , σp , and (h, g),

respectively. We assume λ > 0 fixed for the remainder of the paper.

We briefly mention addressing uncertainty in y. Suppose that we have a set V ⊆ Rm which

captures some belief about the uncertainty in y. If again we have an uncertainty set U ⊆ Rm×n ,

we may attempt to solve a problem of the form

min max g(y + δ − (X + ∆)β).
β

δ∈V
∆∈U

5

We can instead work with a new loss function ḡ defined as
ḡ(v) := max g(v + δ).
δ∈V

If g is convex, then so is ḡ. In this way, we can work with the problem in the form
min max ḡ(y − (X + ∆)β),
β

∆∈U

where there is only uncertainty in X. Throughout the remainder of this paper we will only consider
such uncertainty.
Relation to robust statistics
There has been extensive work in the robust statistics community on statistical methods which
perform well in noisy, real-world environments. As noted in [2], the connection between robust
optimization and robust statistics is not clear. We do not put forth any connection here, but briefly
describe the development of robust statistics to appropriately contextualize our work. Instead of
modeling noise via a distributional perspective, as is often the case in robust statistics, in this
paper we choose to model it in a deterministic way using uncertainty sets. For a comprehensive
description of the theoretical developments in robust statistics in the last half century, see the texts
[27, 38] and the surveys [35, 28].
A central aspect of work in robust statistics is the development and use of a more general set of
loss functions. (This is in contrast to the robust optimization approach, which generally results in
the same nominal loss function with a new penalty; see Section 2.3 below.) For example, while least
squares (the ℓ2 loss) is known to perform well under Gaussian noise, it does not perform well under
other types of noise, such as contaminated Gaussian noise. (Indeed, the Gaussian distribution was
defined so that least squares is the optimal method under Gaussian noise [38].) In contrast, a
method like LAD regression (the ℓ1 loss) generally performs better than least squares with errors
in y, but not necessarily errors in the data matrix X.
A more general class of such methods is M -estimators as proposed in [26] and since studied
extensively [27, 39]. However, M -estimators lack desirable finite sample breakdown properties; in
short, M -estimators perform very poorly in recovering the loadings β ∗ under gross errors in the data
(X, y). To address some of these shortcomings, GM -estimators were introduced [33, 24, 22]. Since
these, many other estimators have been proposed. One such method is least quantile of squares
regression [38] which has highly desirable robustness properties. There has been significant interest
in new robust statistical methods in recent years with the increasing availability of large quantities
of high-dimensional data, which often make reliable outlier detection difficult. For commentary on
modern approaches to robust statistics, see [28, 8, 16] and references therein.

6

Relation to error-in-variable models
Another class of statistical models which are particularly relevant for the work contained herein
are error-in-variable models [12]. One approach to such a problem takes the form
min

β∈Rn , ∆∈Rm×n

g(y − (X + ∆)β) + P (∆),

where P is a penalty function which takes into account the complexity of possible perturbations ∆
to the data matrix X. A canonical example of such a method is total least squares [19, 34], which
can be written for fixed τ > 0 as
min ky − (X + ∆)βk2 + τ k∆kF .
β,∆

An equivalent way of writing such problems is, instead of penalized form, as constrained optimization problems. In particular, the constrained version generically takes the form
min min g(y − (X + ∆)β),
β

∆:
P (∆)≤η

(2)

where η > 0 is fixed. Under the representation in (2), the comparison with the robust optimization
approach in (1) becomes immediate. While the classical error-in-variables approach takes an optimistic view on uncertainty in the data matrix X, and finds loadings β on the new “corrected” data
matrix X+ ∆, the minimax approach of (1) considers protections against adversarial perturbations
in the data which maximally increase the loss.
One of the advantages of the adversarial approach to error-in-variables is that it enables a direct
analysis of certain statistical properties, such as asymptotic consistency of estimators (c.f. [45, 11]).
In contrast, analyzing the consistency of estimators attained by a model such as total least squares
is a complex issue [30].
2.3. Equivalence of robustification and regularization
A natural question is when do the procedures of regularization and robustification coincide.
This problem was first studied in [18] in the context of uncertain least squares problems and
has been extended to more general settings in [45, 11] and most comprehensively in [2]. In this
subsection, we present settings in which robustification is equivalent to regularization. When such
an equivalence holds, tools from robust optimization can be used to analyze properties of the
regularization problem (c.f. [45, 11]).
We begin with a general result on robustification under induced seminorm uncertainty sets.
Theorem 1. If g : Rm → R is a seminorm which is not identically zero and h : Rn → R is a norm,
then for any z ∈ Rm and β ∈ Rn

max g(z + ∆β) = g(z) + λh(β),

∆∈U(h,g)

7

where U(h,g) = {∆ : k∆k(h,g) ≤ λ}.
Proof. From the triangle inequality g(z + ∆β) ≤ g(z) + g(∆β) ≤ g(z) + λh(β) for any ∆ ∈ U :=

U(h,g) . We next show that there exists some ∆ ∈ U so that g(z + ∆β) = g(z) + λh(β). Let v ∈ Rn

so that v ∈ argmaxh∗ (v)=1 v′ β, where h∗ is the dual norm of h. Note in particular that v′ β = h(β)
by the definition of the dual norm h∗ . For now suppose that g(z) 6= 0. Define the rank one matrix
b = λ zv′ . Observe that
∆
g(z)



λh(β)
g(z) + λh(β)
b
g(z + ∆β) = g z +
z =
g(z) = g(z) + λh(β).
g(z)
g(z)

b ∈ U . Observe that for any x ∈ Rn that
We next show that ∆
b =g
g(∆x)




λv′ x
z = λ|v′ x| ≤ λh(x)h∗ (v) = λh(x),
g(z)

b ∈ U , as desired.
where the final inequality follows by definition of the dual norm. Hence ∆

We now consider the case when g(z) = 0. Let u ∈ Rm so that g(u) = 1 (because g is not

identically zero there exists some u so that g(u) > 0, and so by homogeneity of g we can take u so
b = λuv′ . We observe that
that g(u) = 1). Let v be as before. Now define ∆
b
g(z + ∆β)
= g(z + λuv′ β) ≤ g(z) + λ|v′ β|g(u) = λh(β).

Now, by the reverse triangle inequality,

b
b
b
g(z + ∆β)
≥ g(∆β)
− g(z) = g(∆β)
= λh(β),

b
b ∈ U is identical to the case
and therefore g(z + ∆β)
= λh(β) = g(z) + λh(β). The proof that ∆
when g(z) 6= 0. This completes the proof.

This result implies as a corollary known results on the connection between robustification and
regularization as found in [45, 2, 11] and references therein.
Corollary 1 ([45, 2, 11]). If p, q ∈ [1, ∞] then
min max ky − (X + ∆)βkp = min ky − Xβkp + λkβkq .
β

β

∆∈U(q,p)

In particular, for p = q = 2 we recover regularized least squares as a robustification; likewise, for
p = 2 and q = 1 we recover the Lasso.2
2
Strictly speaking, we recover equivalent problems to regularized least squares and Lasso, respectively. We take
the usual convention and overlook this technicality (see [2] for a discussion). For completeness, we note that one can
work directly with the true ℓ22 loss function, although at the cost of requiring more complicated uncertainty sets to
recover equivalence results.

8

Theorem 2 ([45, 2, 11]). One has the following for any p, q ∈ [1, ∞]:
min max ky − (X + ∆)βkp = min ky − Xβkp + λkβkp∗ ,
β

β

∆∈UFp

where p∗ is the conjugate of p. Similarly,
min max ky − (X + ∆)βk2 = min ky − Xβk2 + λkβk2 .
β

β

∆∈Uσq

Observe that regularized least squares arises again under all uncertainty sets defined by the
spectral norms σq when the loss function is g = ℓ2 . Now we continue with a remark on how Lasso
arises through regularization. See [45] for comprehensive work on the robustness and sparsity
implications of Lasso as interpreted through such a robustification considered in this paper.
Remark 1. As per Corollary 1 it is known that Lasso arises as uncertain ℓ2 regression with
uncertainty set U := U(1,2) [45]. As with Theorem 1, one might argue that the ℓ1 penalizer arises

as an artifact of the model of uncertainty. We remark that one can derive the set U as an induced
uncertainty set defined using the “true” non-convex penalty ℓ0 , where kβk0 := |{i : βi 6= 0}|. To be
precise, for any p ∈ [1, ∞] and for Γ = {β ∈ Rn : kβkp ≤ 1} we claim that
U ′ :=



k∆βk2
∆ : max
≤λ
β∈Γ kβk0

satisfies U = U ′ . This is summarized, with an additional representation U ′′ as used in [45], in the

following proposition.

Proposition 1. If U = U(1,2) , U ′ = {∆ : k∆βk2 ≤ λkβk0 ∀kβkp ≤ 1} for an arbitrary p ∈ [1, ∞],

and U ′′ = {∆ : k∆i k2 ≤ λ ∀i}, where ∆i is the ith column of ∆, then U = U ′ = U ′′ .

Proof. We first show that U = U ′ . Because kβk1 ≤ kβk0 for all β ∈ Rn with kβkp ≤ 1, we have

that U ⊆ U ′ . Now suppose that ∆ ∈ U ′ . Then for any β ∈ Rn , we have that
k∆βk2 =

X

βi ∆ei

i

2

≤

X
i

|βi | k∆ei k2 ≤

X
i

|βi |λ = λkβk1 ,

where {ei }ni=1 is the standard orthonormal basis for Rn . Hence, ∆ ∈ U and therefore U ′ ⊆ U .

Combining with the previous direction gives U = U ′ .
We now prove that U = U ′′ . That U ′′ ⊆ U is essentially obvious; U ⊆ U ′′ follows by considering

β ∈ {ei }ni=1 . This completes the proof.

This proposition implies that ℓ1 arises from the robustification setting without directly appealing to
standard convexity arguments for why ℓ1 should be used to replace ℓ0 (which use the fact that ℓ1 is
the so-called convex envelope of ℓ0 on [−1, 1]n , see e.g. [7]).

9

In light of the above discussion, it is not difficult to show that other Lasso-like methods can also
be expressed as an adversarial robustification, supporting the flexibility and versatility of such an
approach. One such example is the elastic net [46, 14, 36], a hybridized version of ridge regression
and the Lasso. An equivalent representation of the elastic net is as follows:
min ky − Xβk2 + λkβk1 + µkβk2 .
β

As per Theorem 2, this can be written exactly as
min
β

max

∆,∆′ :
k∆kF∞ ≤λ
k∆′ kF2 ≤µ

ky − (X + ∆ + ∆′ )βk2 .

Under this interpretation, we see that λ and µ directly control the tradeoff between two different
types of perturbations: “feature-wise” perturbations ∆ (controlled via λ and the F∞ norm) and
“global” perturbations ∆′ (controlled via µ and the F2 norm).
We conclude this subsection with another example of when robustification is equivalent to
regularization for the case of LAD (ℓ1 ) and maximum absolute deviation (ℓ∞ ) regression under
row-wise uncertainty.
Theorem 3 ([45]). Fix q ∈ [1, ∞] and let U = {∆ : kδ i kq ≤ λ ∀i}, where δ i is the ith row of

∆ ∈ Rm×n . Then

min max ky − (X + ∆)βk1 = min ky − Xβk1 + mλkβkq∗
β

β

∆∈U

and
min max ky − (X + ∆)βk∞ = min ky − Xβk∞ + λkβkq∗ .
β

β

∆∈U

For completeness, we note that the uncertainty set U = {∆ : kδ i kq ≤ λ ∀i} considered in Theorem

3 is actually an induced uncertainty set, namely, U = U(q∗ ,∞) .
2.4. Non-equivalence of robustification and regularization

In contrast to previous work studying robustification for regression, which primarily addresses
tractability of solving the new uncertain problem [2] or the implications for Lasso [45], we instead focus our attention on characterization of the equivalence between robustification and regularization.
We begin with a regularization upper bound on robustification problems.
Proposition 2. Let U ⊆ Rm×n be any non-empty, compact set and g : Rm → R a seminorm.

Then there exists some seminorm h : Rn → R so that for any z ∈ Rm , β ∈ Rn ,
max g(z + ∆β) ≤ g(z) + h(β),
∆∈U

with equality when z = 0.
10

Proof. Let h : Rn → R be defined as
h(β) := max g(∆β).
∆∈U

To show that h is a seminorm we must show it satisfies absolute homogeneity and the triangle
inequality. For any β ∈ Rn and α ∈ R,


h(αβ) = max g(∆(αβ)) = max |α|g(∆β) = |α| max g(∆β) = |α|h(β),
∆∈U



∆∈U

∆∈U

so absolute homogeneity is satisfied. Similarly, if β, γ ∈ Rn ,
h(β + γ) = max g(∆(β + γ)) ≤ max [g(∆β) + g(∆γ)]
∆∈U
∆∈U

 

≤ max g(∆β) + max g(∆γ) ,
∆∈U

∆∈U

and hence the triangle inequality is satisfied. Therefore, h is a seminorm which satisfies the desired
properties, completing the proof.
When equality is attained for all pairs (z, β) ∈ Rm × Rn , we are in the regime of the previous

subsection, and we say that robustification under U is equivalent to regularization under h. We now

discuss a variety of explicit settings in which regularization only provides upper and lower bounds
to the true robustified problem.
Fix p, q ∈ [1, ∞]. Consider the robust ℓp regression problem
min max ky − (X + ∆)βkp ,
β

∆∈UFq

where UFq = {∆ ∈ Rm×n : k∆kFq ≤ λ}. In the case when p = q we saw earlier (Theorem 2) that

one exactly recovers ℓp regression with an ℓp∗ penalty:

min max ky − (X + ∆)βkp = min ky − Xβkp + λkβkp∗ .
β

β

∆∈UFp

Let us now consider the case when p 6= q. We claim that regularization (with h) is no longer
equivalent to robustification (with UFq ) unless p ∈ {1, ∞}. Applying Proposition 2, one has for any
z ∈ Rm that

max kz + ∆βkp ≤ kzkp + h(β),

∆∈UFq

where h = max∆∈UFq k∆βkp is a norm (when p = q, this is precisely the ℓp∗ norm, multiplied by

λ). Here we can compute h. To do this we first define a discrepancy function as follows:
Definition 1. For a, b ∈ [1, ∞] define the discrepancy function δm (a, b) as
δm (a, b) := max{kuka : u ∈ Rm , kukb = 1}.
11

This discrepancy function is computable and well-known (see e.g. [25]):
δm (a, b) =

(

m1/a−1/b ,
1,

if a ≤ b

if a > b.

It satisfies 1 ≤ δm (a, b) ≤ m and δm (a, b) is continuous in a and b. One has that δm (a, b) =

δm (b, a) = 1 if and only if a = b (so long as m ≥ 2). Using this, we now proceed with the theorem.

The proof applies basic tools from real analysis and is contained in Appendix A.
Theorem 4. (a) For any z ∈ Rm and β ∈ Rn ,
max kz + ∆βkp ≤ kzkp + λδm (p, q)kβkq∗ .

(3)

∆∈UFq

(b) When p ∈ {1, ∞}, there is equality in (3) for all (z, β).
(c) When p ∈ (1, ∞) and p 6= q, for any β 6= 0 the set of z ∈ Rm for which the inequality (3) holds

at equality is a finite union of one-dimensional subspaces (so long as m ≥ 2). Hence, for any
β 6= 0 the inequality in (3) is strict for almost all z.

(d) For p ∈ (1, ∞), one has for all z ∈ Rm and β ∈ Rn that
kzkp +

λ
kβkq∗ ≤ max kz + ∆βkp .
∆∈UFq
δm (q, p)

(4)

(e) For p ∈ (1, ∞), the lower bound in (4) is best possible in the sense that the gap can be arbitrarily
small, i.e., for any β ∈ Rn ,
inf
z

λ
max kz + ∆βkp − kzkp −
kβkq∗
∆∈UFq
δm (q, p)

!

= 0.

Theorem 4 characterizes precisely when robustification under UFq is equivalent to regularization

for the case of ℓp regression. In particular, when p 6= q and p ∈ (1, ∞), the two are not equivalent,

and one only has that

min ky − Xβkp +
β

λ
kβkq∗ ≤ min max ky − (X + ∆)βkp
β ∆∈UFq
δm (q, p)
≤ min ky − Xβkp + λδm (p, q)kβkq∗ .
β

Further, we have shown that these upper and lower bounds are the best possible (Theorem 4,
parts (c) and (e)). While ℓp regression with uncertainty set UFq for p 6= q and p ∈ (1, ∞) still
has both upper and lower bounds which correspond to regularization (with different regularization

parameters λ ∈ [λ/δm (q, p), λδm (p, q)]), we emphasize that in this case there is no longer the direct

connection between the parameter garnering the magnitude of uncertainty (λ) and the parameter
for regularization (λ).
12

Example 1. As a concrete example, consider the implications of Theorem 4 when p = 2 and
q = ∞. We have that
min ky − Xβk2 + λkβk1 ≤ min max ky − (X + ∆)βkp
β

β

∆∈UF∞

≤ min ky − Xβk2 +
β

√

mλkβk1 .

In this case, robustification is not equivalent to regularization. In particular, in the regime where
there are many data points (i.e. m is large), the gap appearing between the different problems can
be quite large.
Let us remark that in general, lower bounds on max∆∈U g(z + ∆β) will depend on the structure
of U and may not exist (except for the trivial lower bound of g(z)) in some scenarios. However, it is

easy to show that if U is compact and zero is in the interior of U , then there exists some λ ∈ (0, 1]

so that

max g(z + ∆β) ≥ g(z) + λh(β).
∆∈U

Before proceeding with other choices of uncertainty sets, it is important to make a further
distinction about the general non-equivalence of robustification and regularization as presented in
Theorem 4. In particular, it is simple to construct examples (see Appendix B) which imply the
following strong existential result:
Theorem 5. In a setting when robustification and regularization are not equivalent, it is possible
for the two problems to have no common optimal solution. In particular,
β ∗ ∈ argmin max g(y − (X + ∆)β)
β

∆∈U

is not necessarily a solution of
e
min g(y − Xβ) + λh(β)
β

e > 0, and vice versa.
for any λ

e ∈ (0, ∞) varies) and the robustification path (as
In other words, the regularization path (as λ

the radius λ ∈ (0, ∞) of U varies) do not necessarily have any point in common. As a result, when

robustification and regularization do not coincide, they can induce structurally distinct solutions.

We now proceed to analyze another setting in which robustification is not equivalent to regularization. The setting, in line with Theorem 2, is ℓp regression under spectral uncertainty sets Uσq .
As per Theorem 2, one has that

min max ky − (X + ∆)βk2 = min ky − Xβk2 + λkβk2
β

β

∆∈Uσq

for any q ∈ [1, ∞]. This result on the “universality” of RLS under a variety of uncertainty sets

relies on the fact that the ℓ2 norm underlies spectral decompositions; namely, one can write any
13

matrix X as

P

′
i µi ui vi ,

where {µi }i are the singular values of X, {ui }i and {vi }i are the left and

right singular vectors of X, respectively, and kui k2 = kvi k2 = 1 for all i.

A natural question is what happens when the loss function ℓ2 , a modeling choice, is replaced

by ℓp , where p ∈ [1, ∞]. We claim that for p ∈
/ {1, 2, ∞}, robustification under Uσq is no longer

equivalent to regularization. In light of Theorem 4 this is not difficult to prove. We find that the
choice of q ∈ [1, ∞], as before, is inconsequential. We summarize this in the following proposition:
Proposition 3. For any z ∈ Rm and β ∈ Rn ,
max kz + ∆βkp ≤ kzkp + λδm (p, 2)kβk2 .

∆∈Uσq

(5)

In particular, if p ∈ {1, 2, ∞}, there is equality in (5) for all (z, β). If p ∈
/ {1, 2, ∞}, then for any

β 6= 0 the inequality in (5) is strict for almost all z (when m ≥ 2). Further, for p ∈
/ {1, 2, ∞} one

has the lower bound

kzkp +

λ
kβk2 ≤ max kz + ∆βkp ,
∆∈Uσq
δm (2, p)

whose gap is arbitrarily small for all β.
Proof. This result is Theorem 4 in disguise. This follows by noting that
max kz + ∆βkp = max kz + ∆βkp

∆∈Uσq

∆∈UF2

and directly applying the preceding results.
We now consider a third setting for ℓp regression, this time subject to uncertainty U(q,r) ; this is

a generalized version of the problems considered in Theorems 1 and 3. From Theorem 1 we know
that if p = r, then
min max ky − (X + ∆)βkp = min ky − Xβkp + λkβkq .
β

β

∆∈U(q,p)

Similarly, as per Theorem 3, when r = ∞ and p ∈ {1, ∞},
min max
β

∆∈U(q,∞)

ky − (X + ∆)βkp = min ky − Xβkp + λδm (p, ∞)kβkq .
β

Given these results, it is natural to inquire what happens for more general choices of induced
uncertainty set U(q,r) . As before with Theorem 4, we have a complete characterization of the
equivalence of robustification and regularization for ℓp regression with uncertainty set U(q,r) :

Proposition 4. For any z ∈ Rm and β ∈ Rn ,
max kz + ∆βkp ≤ kzkp + λδm (p, r)kβkq .

∆∈U(q,r)

14

(6)

In particular, if p ∈ {1, r, ∞}, there is equality in (5) for all (z, β). If p ∈ (1, ∞) and p 6= r, then

for any β 6= 0 the inequality in (6) is strict for almost all z (when m ≥ 2). Further, for p ∈ (1, ∞)

with p 6= r one has the lower bound
kzkp +

λ
kβkq ≤ max kz + ∆βkp ,
∆∈U(q,r)
δm (r, p)

whose gap is arbitrarily small for all β.
Proof. The proof follows the argument given in the proof of Theorem 4. Here we simply note that
now one uses the fact that
max kz + ∆βkp =

∆∈U(q,r)

max

kukr ≤λkβkq

kz + ukp .

We summarize all of the results on linear regression in Table 2.
Loss function
seminorm g
ℓp
ℓp
ℓp
ℓp

Uncertainty set U
U(h,g) (h norm)
Uσq
UF q
U(q,r)
{∆ : kδ i kq ≤ λ ∀i}

h(β)
λh(β)
λδm (p, 2)kβk2
λδm (p, q)kβkq∗
λδm (p, r)kβkq
λm1/p kβkq∗

Equivalence if and only if
always
p ∈ {1, 2, ∞}
p ∈ {1, q, ∞}
p ∈ {1, r, ∞}
p ∈ {1, ∞}

Table 2: Summary of equivalencies for robustification with uncertainty set U and regularization with penalty h, where
h is as given in Proposition 2. Here by equivalence we mean that for all z ∈ Rm and β ∈ Rn , max∆∈U g(z + β) =
g(z) + h(β), where g is the loss function, i.e., the upper bound h is also a lower bound. Here δm is as in Theorem 4.
Throughout p, q ∈ [1, ∞] and m ≥ 2. Here δ i denotes the ith row of ∆.

3. On the equivalence of robustification and regularization in matrix estimation problems
A substantial body of problems at the core of modern developments in statistical estimation
involves underlying matrix variables. Two prominent examples which we consider here are matrix
completion and Principal Component Analysis (PCA). In both cases we show that a common
choice of the regularization problem corresponds exactly to a robustification of the nominal problem
subject to uncertainty. In doing so we expand the existing knowledge of robustification for vector
regression to a novel and substantial domain. We begin by reviewing these two problem classes
before introducing a simple model of uncertainty analogous to the vector model of uncertainty.

15

3.1. Problem classes
In matrix completion problems one is given data Yij ∈ R for (i, j) ∈ E ⊆ {1, . . . , m}×{1, . . . , n}.

One problem of interest is rank-constrained matrix completion
min kY − XkP(F2 )

(7)

X

s. t.

rank(X) ≤ k,

where k · kP(F2 ) denotes the projected 2−Frobenius seminorm, namely,


kZkP(F2 ) = 

X

(i,j)∈E

1/2

2
Zij

.

Matrix completion problems appear in a wide variety of areas. One well-known application is
in the Netflix challenge [42], where one wishes to predict user movie preferences based on a very
limited subset of given user ratings. Here rank-constrained models are important in order to obtain
parsimonious descriptions of user preferences in terms of a limited number of significant latent
factors. The rank-constrained problem (7) is typically converted to a regularized form with rank
replaced by the nuclear norm σ1 (the sum of singular values) to obtain the convex problem
min kY − XkP(F2 ) + λkXkσ1 .
X

In what follows we show that this regularized problem can be written as an uncertain version of a
nominal problem minX kY − XkP(F2 ) .

Similarly to matrix completion, PCA typically takes the form
min kY − Xk
X

s. t.

rank(X) ≤ k,

(8)

where k · k is either the usual Frobenius norm F2 = σ2 or the operator norm σ∞ , and Y ∈ Rm×n .
PCA arises naturally by assuming that Y is observed as some low-rank matrix X plus noise:
Y = X + E. The solution to (8) is well-known to be a truncated singular value decomposition
which retains the k largest singular values [15]. PCA is popular for a variety of applications where
dimension reduction is desired.
A variant of PCA known as robust PCA [10] operates under the assumption that some entries
of Y may be grossly corrupted. Robust PCA assumes that Y = X + E, where X is low rank and
E is sparse (few nonzero entries). Under this model robust PCA takes the form
min kY − XkF1 + λkXkσ1 .
X

(9)

Here again we can interpret kXkσ1 as a surrogate penalty for rank. In the spirit of results from
compressed sensing on exact ℓ1 recovery, it is shown in [10] that (9) can exactly recover the true X0
16

and E0 assuming that the rank of X0 is small, E0 is sufficiently sparse, and the eigenvectors of X0
are well-behaved (see technical conditions contained therein). Below we derive explicit expressions
for PCA subject to certain types of uncertainty; in doing so we show that robust PCA does not
correspond to an adversarially robust version of minX kY − Xkσ∞ or minX kY − XkF2 for any
model of additive linear uncertainty.

Finally let us note that the results we consider here on robust PCA are distinct from considerations in the robust statistics community on robust approaches to PCA. For results and commentary
on such methods, see [13, 29, 40, 28].
3.2. Models of uncertainty
For these two problem classes we now detail a model of uncertainty. Our underlying problem is
of the form minX kY − Xk, where Y is given data (possibly with some unknown entries). As with

the vector case, we do not concern ourselves with uncertainty in the observed Y because modeling
uncertainty in Y simply leads to a different choice of loss function. To be precise, if V ⊆ Rm×n and
g is convex loss function then

ḡ(Y − X) := max g((Y + ∆) − X)
∆∈V

is a new convex loss function ḡ of Y − X.

As in the vector case we assume a linear model of uncertainty in the measurement of X:
Yij = Xij +

X

(ij)
∆ℓk Xℓk

ℓk

!

+ ǫij ,

where ∆(ij) ∈ Rm×n ; alternatively, in inner product notation, Yij = Xij + h∆(ij) , Xi + ǫij . This
linear model is in direct analogy with the model for vector regression taken earlier; now β is replaced
by X, and again we consider linear perturbations of the unknown regression variable.
This linear model of uncertainty captures a variety of possible forms of uncertainty and accounts
for possible interactions among different entries of the matrix X. Note that in matrix notation, the
nominal problem becomes, subject to linear uncertainty in X,
min max kY − X − ∆(X)k,
X ∆∈U

where here U is some collection of linear maps and ∆ ∈ U is defined as [∆(X)]ij = h∆(ij) , Xi,

where again ∆(ij) ∈ Rm×n (all linear maps can be written in such a form). Note here the direct

analogy to the vector case, with the notation ∆(X) chosen for simplicity. (For clarity, note that ∆

is not itself a matrix, although one could interpret it as a matrix in ∆mn×mn , albeit at a notational
cost; we avoid this here.)
We now outline some particular choices for uncertainty sets. As with the vector case, one
natural set is an induced uncertainty set. Precisely, if g, h : Rm×n → R are functions, then we
17

define an induced uncertainty set

U(h,g) := ∆ : Rm×n → Rm×n | ∆ linear, g(∆(X)) ≤ λh(X) ∀X ∈ Rm×n .

As before, when g and h are both norms, U(h,g) is precisely a ball of radius λ in the induced norm
k∆k(h,g) = max
X

g(∆(X))
.
h(X)

There are also many other possible choices of uncertainty sets. These include the spectral uncertainty sets
Uσp = {∆ : Rm×n → Rm×n |∆ linear, k∆kσp ≤ λ},
where we interpret k∆kσp as the σp norm of ∆ in any, and hence all, of its matrix representations.

Other uncertainty sets are those such as U = {∆ : ∆(ij) ∈ U (ij) }, where U (ij) ⊆ Rm×n are

themselves uncertainty sets. These last two models we will not examine in depth here because they
are often subsumed by the vector results (note that these two uncertainty sets do not truly involve
the matrix structure of X, and can therefore be “vectorized”, reducing directly to vector results).
3.3. Basic results on equivalence

We now continue with some underlying theorems for our models of uncertainty. As a first step,
we provide a proposition on the spectral uncertainty sets. As noted above, this result is exactly
Theorem 2, and therefore we will not consider such uncertainty sets for the remainder of the paper.
Proposition 5. For any q ∈ [1, ∞] and any Y ∈ Rm×n ,
min max kY − X − ∆(X)kF2 = min kY − XkF2 + λkXkF2 .
X ∆∈Uσq

X

For what follows, we restrict our attention to induced uncertainty sets. We begin with an
analogous result to Theorem 1. The proof is similar and therefore kept concise. Throughout we
always assume without loss of generality that if Yij is not known then Yij = 0 (i.e., we set it to
some arbitrary value).
Theorem 6. If g : Rm×n → R is a seminorm which is not indentically zero and h : Rm×n → R is

a norm, then

min max g (Y − X − ∆(X)) = min g (Y − X) + λh (X) .
X ∆∈U(h,g)

X

This theorem leads to an immediate corollary:
Corollary 2. For any norm k · k : Rm×n → R and any p ∈ [1, ∞]
min

max

X ∆∈U(σp ,k·k)

kY − X − ∆(X)k = min kY − Xk + λkXkσp .
X

In the two subsections which follow we study the implications of Theorem 6 for matrix completion and PCA.
18

3.4. Robust matrix completion
We now proceed to apply Theorem 6 for the case of matrix completion. Note that the projected
Frobenius “norm” P(F2 ) is a seminorm. Therefore, we arrive at the following corollary:
Corollary 3. For any p ∈ [1, ∞] one has that
min

max

X ∆∈U(σp ,P(F2 ))

kY − X − ∆(X)kP(F2 ) = min kY − XkP(F2 ) + λkXkσp .
X

In particular, for p = 1 one exactly recovers so-called nuclear norm penalized matrix completion:
min kY − XkP(F2 ) + λkXkσ1 .
X

It is not difficult to show by modifying the proof of Theorem 6 that even though U(σp ,F2) (
U(σp ,P(F2 )) , the following holds:
Proposition 6. For any p ∈ [1, ∞] one has that
min

max

X ∆∈U(σp ,F2 )

kY − X − ∆(X)kP(F2 ) = min kY − XkP(F2 ) + λkXkσp .
X

In particular, for p = 1 one exactly recovers nuclear norm penalized matrix completion.
Let us briefly comment on the appearance of the nuclear norm in Corollary 3 and Proposition
6. In light of Remark 1, it is not surprising that such a penalty can be derived by working directly
with the rank function (nuclear norm is the convex envelope of the rank function on the ball
{X : kXkσ∞ ≤ 1}, which is why the nuclear norm is typically used to replace rank [17, 37]). We

detail this argument as before. For any p ∈ [1, ∞] and Γ = {X ∈ Rm×n : kXkσp ≤ 1}, one can

show that

U(σ1 ,P(F2 )) =




k∆(X)kP(F2 )
∆ linear : max
≤λ .
X∈Γ
rank(X)

(10)

Therefore, similar to the vector case with an underlying ℓ0 penalty which becomes a Lasso ℓ1
penalty, rank leads to the nuclear norm from the robustification setting without directly invoking
convexity.
3.5. Robust PCA
We now turn our attention to the implications of Theorem 6 for PCA. We begin by noting robust
analogues of minX kY − Xk under the F2 and σ∞ norms. This is distinct from the considerations
in [11] on robustness of PCA with respect to training and testing sets.
Corollary 4. For any p ∈ [1, ∞] one has that
min

max

X ∆∈U(σp ,F2 )

kY − X − ∆(X)kF2 = min kY − XkF2 + λkXkσp
X

19

and
min

max

X ∆∈U(σp ,σ∞ )

kY − X − ∆(X)kσ∞ = min kY − Xkσ∞ + λkXkσp .
X

We continue by considering robust PCA as presented in [10]. Suppose that U is some collection

of linear maps ∆ : Rm×n → Rm×n and k · k is some norm so that for any Y, X ∈ Rm×n
max kY − X − ∆(X)k = kY − XkF1 + λkXkσ1 .
∆∈U

It is easy to see that this implies k · k = k · kF1 . These observations, combined with Theorem 6,
imply the following:

Proposition 7. The problem (9) can be written as an uncertain version of minX kY − Xk subject

to additive, linear uncertainty in X if and only if k · k is the 1-Frobenius norm F1 . In particular, (9)

does not arise as uncertain versions of PCA (using F2 or σ∞ ) under such a model of uncertainty.

This result is not entirely surprising. This is because robust PCA attempts to solve, based on
its model of Y = X + E where X is low-rank and E is sparse, a problem of the form
min kY − XkF0 + λ rank(X),
X

where kAkF0 is the number of nonzero entries of A. In the usual way, F0 and rank are replaced

with surrogates F1 and σ1 , respectively. Hence, (9) appears as a convex, regularized form of the
problem
min kY − XkF1
X

s. t.

rank(X) ≤ k.

Again, as with matrix completion, it is possible to show that (9) and uncertain forms of PCA
with a nuclear norm penalty (as appearing in Corollary 4) can be derived using the true choice
of penalizer, rank, instead of imposing an a priori assumption of a nuclear norm penalty. We
summarize this, without proof, as follows:
Proposition 8. For any p ∈ [1, ∞] and any norm k · k,
min

max

X∈Γ ∆∈UΓ(rank,k·k)

kY − X − ∆(X)k = min kY − Xk + λkXkσ1 ,
X∈Γ

where Γ = {X ∈ Rm×n : kXkσp ≤ 1} and
UΓ(rank,k·k)



k∆(X)k
= ∆ linear : max
≤λ .
X∈Γ rank(X)

3.6. Non-equivalence of robustification and regularization
As with vector regression it is not always the case that robustification is equivalent to regularization in matrix estimation problems. For completeness we provide analogues here of the linear
20

regression results. We begin by stating results which follow over with essentially identical proofs
from the vector case; proofs are not included here. Then we characterize precisely when another
plausible model of uncertainty leads to equivalence.
We begin with the analogue of Proposition 2.
Proposition 9. Let U ⊆ {linear maps ∆ : Rm×n → Rm×n } be any non-empty, compact set and
g : Rm×n → R a seminorm. Then there exists some seminorm h : Rm×n → R so that for any

Z, X ∈ Rm×n ,

max g(Z + ∆(X)) ≤ g(Z) + h(X),
∆∈U

with equality when Z = 0.
As before with Theorem 4 and Propositions 3 and 4, one can now compute h for a variety of
problems.
Proposition 10. For any Z, X ∈ Rm×n ,
kZkFp +

λ
kXkFq∗ ≤ max kZ + ∆(X)kFp
∆∈UFq
δmn (q, p)
≤ kZkFp + λδmn (p, q)kXkFq∗

(11)
(12)

where k∆kFq is interpreted as the Fq norm on the matrix representation of ∆ in the standard basis.

In particular, if p 6= q and p ∈ (1, ∞), then for any X 6= 0 the upper bound in (12) is strict for

almost all Z (so long as mn ≥ 2). Further, when p 6= q and p ∈ (1, ∞), the gap in the lower bound
in (11) is arbitrarily small for all X.

Proposition 11. For any Z, X ∈ Rm×n ,
kZkp +

λ
kXkF2 ≤ max kZ + ∆(X)kFp
∆∈Uσq
δmn (2, p)
≤ kZkFp + λδmn (p, 2)kXkF2 .

(13)
(14)

In particular, if p ∈
/ {1, 2, ∞}, then for all X 6= 0 the upper bound in (14) is strict for almost all

Z (so long as mn ≥ 2). Further, if p ∈
/ {1, 2, ∞}, the gap in the lower bound in (13) is arbitrarily
small for all X.

We now turn our attention to non-equivalencies which may arise under different models of
uncertainty instead of the general matrix model of linear uncertainty which we have included here,
where
[∆(X)]ij =

X
ℓk

(ij)

∆ℓk Xℓk = h∆(ij) , Xi,

with ∆(ij) ∈ Rm×n . Another plausible model of uncertainty is one for which the jth column of

∆(X) only depends on Xj , the jth column of X (or, for example, with columns replaced by rows).

We now examine such a model. In this setup, we now have n matrices ∆(j) ∈ Rm×m and we define
21

the linear map ∆ so that the jth column of ∆(X) ∈ Rm×n , denoted [∆(X)]j , is [∆(X)]j := ∆(j) Xj ,

which is simply matrix vector multiplication. Therefore,
h
∆(X) = ∆(1) X1 · · ·

i
∆(n) Xn .

(15)

For an example of where such a model of uncertainty may arise, we consider matrix completion
in the context of the Netflix problem. If one treats Xj as user j’s true ratings, then such a model
addresses uncertainty within a given user’s ratings, while not allowing uncertainty to have crossuser effects. This model of uncertainty does not rely on true matrix structure and therefore reduces
to earlier results on non-equivalence in vector regression. As an example of such a reduction, we
state the following proposition characterizing equivalence. Again, this is a direct modification of
Theorem 4 and the proof we do not include here.
Proposition 12. For the model of uncertainty in (15) with ∆(j) ∈ UFqj for j = 1, . . . , n, where
qj ∈ [1, ∞], one has for the problem min max kY − X − ∆(X)kFp that h is defined as
X ∆∈U


1/p
X
p
h(X) = λ 
δm
(p, qj )kXj kp∗  .
qj

j

(16)

Further, under such a model of uncertainty, robustification is equivalent to regularization with h if
and only if p ∈ {1, ∞} or p = qj for all j = 1, . . . , n.
While the case of matrix regression offers a large variety of possible models of uncertainty, we see
again as with vector regression that this variety inevitably leads to scenarios in which robustification
is no longer directly equivalent to regularization. We summarize the conclusions of this section in
Table 3.
Loss function
seminorm g
Fp
Fp
Fp

Uncertainty set
U(h,g) (h norm)
Uσq
UF q
U in (15)
with ∆(j) ∈ UFqj

h(X)
λh(X)
λδmn (p, 2)kXkF2
λδmn (p, q)kXkFq∗
(16)

Equivalence if and only if
always
p ∈ {1, 2, ∞}
p ∈ {1, q, ∞}
(p = qj ∀j) or
p ∈ {1, ∞}

Table 3: Summary of equivalencies for robustification with uncertainty set U and regularization with penalty h, where
h is as given in Proposition 9. Here by equivalence we mean that for all Z, X ∈ Rm×n , max∆∈U g(Z+X) = g(Z)+h(X),
where g is the loss function, i.e., the upper bound h is also a lower bound. Here δmn is as in Theorem 4. Throughout
p, q ∈ [1, ∞] and mn ≥ 2.

4. Conclusion
In this work we have considered the robustification of a variety of problems from classical and
modern statistical regression as subject to data uncertainty. We have taken care to emphasize that
22

there is a fine line between this process of robustification and the usual process of regularization,
and that the two are not always directly equivalent. While deepening this understanding we have
also extended this connection to new domains, such as in matrix completion and PCA. In doing
so, we have shown that the usual regularization approaches to modern statistical regression do not
always coincide with an adversarial approach motivated by robust optimization.
References
[1] H.H. Bauschke and P.L. Combettes, Convex analysis and monotone operator theory in Hilbert
spaces, Springer, 2011.
[2] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust optimization, Princeton University Press,
2009.
[3] A. Ben-Tal, E. Hazan, T. Koren, and S. Mannor, Oracle-based robust optimization via online
learning, Operations Research 63 (2015), no. 3, 628–638.
[4] D. Bertsimas, D.B. Brown, and C. Caramanis, Theory and applications of robust optimization,
SIAM Review 53 (2011), no. 3, 464–501.
[5] D. Bertsimas, V. Gupta, and N. Kallus, Data-driven robust optimization, arXiv preprint
arXiv:1401.0212 (2013).
[6] O. Bousquet, S. Boucheron, and G. Lugosi, Advanced lectures on machine learning, ch. Introduction to statistical learning theory, Springer, 2004.
[7] S. Boyd and L. Vandenberghe, Convex optimization, Cambridge University Press, 2004.
[8] J. Bradic, J. Fan, and W. Wang, Penalized composite quasi-likelihood for ultrahigh dimensional
variable selection, Journal of the Royal Statistical Society, Series B 73 (2011), 325–349.
[9] E. Candès and B. Recht, Exact matrix completion via convex optimization, Communications
of the ACM 55 (2012), no. 6, 111–119.
[10] E.J. Candès, X. Li, Y. Ma, and J. Wright, Robust Principal Component Analysis?, Journal of
the ACM 58 (2011), no. 3, 11:1–37.
[11] C. Caramanis, S. Mannor, and H. Xu, Optimization for machine learning, ch. Robust optimization in machine learning, MIT Press, 2011.
[12] R.J. Carroll, D. Ruppert, L.A. Stefanski, and C.M. Crainiceanu, Measurement error in nonlinear models: A modern perspective, 2nd ed., CRC Press, 2006.
[13] C. Croux and A. Ruiz-Gazen, High breakdown estimators for principal components: the
projection-pursuit approach revisited, Journal of Multivariate Analysis 95 (2005), 206–226.

23

[14] C. De Mol, E. De Vito, and L. Rosasco, Elastic-net regularization in learning theory, Journal
of Complexity 25 (2009), no. 2, 201–230.
[15] C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika 1 (1936), 211–8.
[16] J. Fan, Y. Fan, and E. Barut, Adaptive robust variable selection, The Annals of Statistics 42
(2014), no. 1, 324–351.
[17] M. Fazel, Matrix rank minimization with applications, Ph.D. thesis, Stanford University, 2002.
[18] L. El Ghaoui and H. Lebret, Robust solutions to least-squares problems with uncertain data,
SIAM Journal of Matrix Analysis and Applications 18 (1997), no. 4, 1035–64.
[19] G.H. Golub and C.F. Van Loan, An analysis of the total least squares problem, SIAM Journal
of Numerical Analysis 17 (1980), no. 6, 883–893.
[20] I.J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, Sh. Ozair, A. Courville,
and Y. Bengio, Generative adversarial nets, Advances in Neural Information Processing Systems 27, 2014, pp. 2672–2680.
[21] I.J. Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples,
arXiv preprint arXiv:1412.6572 (2014).
[22] F.R. Hampel, The influence curve and its role in robust estimation, Journal of the American
Statistical Association 69 (1974), 383–393.
[23] T. Hastie, R. Tibshirani, and J. Friedman, The elements of statistical learning: data mining,
inference, and prediction, Springer, 2009.
[24] R.W. Hill, Robust regression when there are outlires in the carriers, Ph.D. thesis, Harvard
University, 1977.
[25] R.A. Horn and C.R. Johnson, Matrix analysis, second ed., Cambridge University Press, 2013.
[26] P.J. Huber, Robust regression: asymptotics, conjectures and Monte Carlo, The Annals of
Statistics 1 (1973), 799–821.
[27] P.J. Huber and E.M. Ronchetti, Robust statistics, second ed., Wiley, 2009.
[28] M. Hubert, P.J. Rousseeuw, and S. Van Aelst, High-breakdown robust multivariate methods,
Statistical Science 23 (2008), no. 1, 92–119.
[29] M. Hubert, P.J. Rousseeuw, and K. Van den Branden, ROBPCA: a new approach to robust
principal components analysis, Technometrics 47 (2005), 64–79.

24

[30] A. Kukush, I. Markovsky, and S. Van Huffel, Consistency of the structured total least squares
estimator in a multivariate errors-in-variables model, Journal of Statistical Planning and Inference 133 (2005), 315–358.
[31] A.S. Lewis, Robust regularization, Tech. report, School of ORIE, Cornell University, 2002.
[32] A.S. Lewis and C.H.J. Pang, Lipschitz behavior of the robust regularization, SIAM Journal on
Control and Optimization 48 (2009), no. 5, 3080–3104.
[33] C.L. Mallows, On some topics in robustness, Tech. report, Bell Laboratories, 1975.
[34] I. Markovsky and S. Van Huffel, Overview of total least-squares methods, Signal Processing 87
(2007), 2283–2302.
[35] S. Morgenthaler, A survey of robust statistics, Statistical Methods and Applications 15 (2007),
271–293.
[36] S. Mosci, L. Rosasco, M. Santoro, A. Verri, and S. Villa, Solving structured sparsity regularization with proximal methods, Joint European Conference on Machine Learning and Knowledge
Discovery in Databases, Springer, 2010, pp. 418–433.
[37] B. Recht, M. Fazel, and P.A. Parrilo, Guaranteed minimum-rank solutions of linear matrix
equations via nuclear norm minimization, SIAM Review 52 (2010), no. 3, 471–501.
[38] P.J. Rousseeuw, Least median of squares regression, Journal of the American Statistical Association 79 (1984), 871–80.
[39] P.J. Rousseeuw and A.M. Leroy, Robust regression and outlier detection, Wiley, 1987.
[40] M. Salibian-Barrera, S. Van Aelst, and G. Willems, PCA based on multivariate MM-estimators
with fast and robust bootstrap, Journal of the American Statistical Association 101 (2005),
no. 475, 1198–1211.
[41] U. Shaham, Y. Yamada, and S. Negahban, Understanding adversarial training: Increasing local
stability of neural nets through robust optimization, arXiv preprint arXiv:1511.05432 (2015).
[42] SIGKDD and Netflix, Soft modelling by latent variables: the nonlinear iterative partial least
squares (NIPALS) approach, Proceedings of the KDD Cup and Workshop (2007).
[43] R. Tibshirani, Regression shrinkage and selection via the Lasso, Journal of the Royal Statistical
Society, Series B 58 (1996), 267–288.
[44] T. Tulabandhula and C. Rudin, Robust optimization using machine learning for uncertainty
sets, arXiv preprint arXiv:1407.1097 (2014).
[45] H. Xu, C. Caramanis, and S. Mannor, Robust regression and Lasso, IEEE Transactions in
Information Theory 56 (2010), no. 7, 3561–74.
25

[46] H. Zou and T. Hastie, Regularization and variable selection via the elastic net, Journal of the
Royal Statistical Society: Series B 67 (2005), no. 2, 301–320.

26

Appendix A
This appendix contains proofs and additional technical results for the vector regression setting.
We prove our results in the vector setting, from which the primary results on matrices follow as a
direct corollary.
Proof of Theorem 4. (a) We begin by proving the upper bound. Here we proceed by showing that
h above is precisely h(β) = λδm (p, q)kβkq∗ . Now observe that for any ∆ ∈ UFq ,
k∆βkp ≤ δm (p, q)k∆βkq ≤ δm (p, q)k∆kFq kβkq∗ ≤ δm (p, q)λkβkq∗ .

(17)

The first inequality follows by the definition of the discrepancy function δm . The second
inequality follows from a well-known matrix inequality: k∆βkq ≤ k∆kFq kβkq∗ (this follows

from a simple application of Hölder’s inequality). Now observe that in the chain of inequalities
b := λuv′ ∈
in (17), if one takes any u ∈ argmax δm (p, q) and any v ∈ argmaxkvk =1 v′ β, then ∆
q

UF q

b p = δm (p, q)λkβkq∗ . Hence, h(β) = δm (p, q)λkβkq∗ . This proves the upper
and k∆βk

bound.

(b) We now prove that for p ∈ {1, ∞} that one has equality for all (z, β) ∈ Rm × Rn . This follows
an argument similar to that needed for Theorem 6. First consider the case when p = 1. Fix
z ∈ Rm . Again let u ∈ argmax δm (1, q) and v ∈ argmaxkvkq =1 v′ β. Without loss of generality

we may assume that sign(zi ) = sign(ui ) for i = 1, . . . , m (one may change the sign of entries of
b := λuv′ ∈ UFq and
u and it is still in argmax δm (1, q)). Then again we have ∆
b 1 = kz + λuv′ βk1 = kz + λkβkq∗ uk1
kz + ∆βk

= kzk1 + λkβkq∗ kuk1 = kzk1 + λkβkq∗ δm (1, q).

Hence, one has equality in the upper bound for p = 1, as claimed.
We now turn our attention to the case p = ∞. Note that δm (∞, q) = 1 because kzk∞ ≤ kzkq

for all z ∈ Rm . Fix z ∈ Rm , and again let v ∈ argmaxkvkq =1 v′ β. Let ℓ ∈ {1, . . . , m} so that

|zℓ | = kzk∞ . Define u = sign(zℓ )eℓ ∈ Rm , where eℓ is the vector whose only nonzero entry is a
b := λuv′ ∈ UFq and
1 in the ℓth position. Now observe that ∆
b ∞ = kz + sign(zℓ )λkβkq∗ eℓ k∞
kz + ∆βk

= kzk∞ + λkβkq∗ keℓ k∞ = kzk∞ + λkβkq∗ ,

which proves equality in (3), as was to be shown.
(c) To proceed, we examine the case where p ∈ (1, ∞) and consider for which (z, β) the inequality

in (3) is strict. Fix β 6= 0. For p ∈ (1, ∞) and y, z ∈ Rm , one has by Minkowski’s inequality

that ky + zkp = kykp + kzkp if and only if one of y or z is a non-negative scalar multiple of the
other. To have equality in (3), it must be that there exists some ∆ ∈ argmax∆∈UFq k∆βkp for
27

which kz + ∆βkp = kzkp + k∆βkp . For any z 6= 0 this observation, combined with Minkowski’s

inequality, implies that

k∆kFq = λ, ∆β = µz for some µ ≥ 0, and k∆βkp = λδm (p, q)kβkq∗ .
The first and last equalities imply that ∆β ∈ λkβkq∗ argmax δm (p, q). Note that argmax δm (p, q)
is finite whenever p 6= q and m ≥ 2, a geometric property of ℓp balls. Hence, taking any z
which is not a scalar multiple of a point in argmax δm (p, q) implies by Minkowski’s inequality
that
max kz + ∆βkp < kzkp + λδm (p, q)kβkq∗ .

∆∈UFq

Hence, for any β 6= 0, the inequality in (3) is strict for all z not in a finite union of onedimensional subspaces, so long as p ∈ (1, ∞), p 6= q, and m ≥ 2.

(d) We now prove the lower bound in (4). If z = 0 then there is nothing to show, and therefore we
assume z 6= 0. Let v ∈ Rn so that
v ∈ argmaxkvkq =1 v′ β.
b = λ zv′ . Observe that
Hence v′ β = kβkq∗ by the definition of the dual norm. Define ∆
kzkq
b
∆ ∈ UFq . Further, note that kzkq ≤ δm (q, p)kzkp by definition of δm and therefore 1/δm (q, p) ≤
kzkp /kzkq . Putting things together,
kzkp +

λkβkq∗
λkzkp kβkq∗
≤ kzkp +
δm (q, p)
kzkq


λkβkq∗
= kzkp 1 +
kzkq
b p
= kz + ∆βk
≤ max kz + ∆βkp .
∆∈UFq

This completes the proof of the lower bound.
(e) To conclude we prove that the gap in (4) can be made arbitrarily small for p ∈ (1, ∞). We
proceed in several steps. We first prove that for any z 6= 0 that
lim

α→∞

max kαz + ∆βkp − kαzkp

∆∈UFq

!

=

λkβkq∗ kzp−1 kq∗
kzkp−1
p

,

(18)

where we use the shorthand zp−1 to denote the vector in Rm whose ith entry is |zi |p−1 . Observe
that

max kαz + ∆βkp =

∆∈UFq

28

max

kukq ≤λkβkq∗

kαz + ukp .

It is easy to argue that we may assume without any loss of generality that u ∈ argmaxkukq ≤λkβkq∗ kαz+
ukp has sign(ui ) = sign(αzi ), where

sign(a) =

(

1,

a≥0

−1, a < 0.

Therefore, we restrict our attention to z ≥ 0, z 6= 0, and u ≥ 0. For any u such that
kukq ≤ λkβkq∗ and u ≥ 0, note that

kz + u/αkp − kzkp
1/α
kz + ᾱukp − kzkp
= lim
ᾱ
ᾱ→0+
d
=
kz + ᾱukp
dᾱ ᾱ=0

lim kαz + ukp − kαzkp = lim

α→∞

α→∞

=

u′ zp−1
kzkp−1
p

.

We can now proceed to finish the claim in (18) (still restricting attention to z ≥ 0 without

loss of generality). By the above arguments, for any u ≥ 0 and any ǫ > 0 there exists some

α̂ = α̂(u) > 0 sufficiently large so that for all α > α̂,
kαz + ukp − kαzkp −

u′ zp−1
kzkp−1
p

≤ ǫ.

It remains to be shown that for any ǫ > 0 there exists some α̂ so that for all α > α̂,


max

kukq ≤λkβkq∗

kαz + ukp − kαzkp



−

max

kukq ≤λkβkq∗

u′ zp−1
kzkp−1
p

!

≤ ǫ.

We prove this as follows. Let ǫ > 0. Choose points {u1 , . . . , uM } ⊆ Rm with kuj kq = λkβkq∗ ∀j

so that for any u ∈ Rm with kukq = λkβkq∗ , there exists some j so that ku − uj kp ≤ ǫ/3 (note

that our choice of ℓp here is intentional). Now observe that for any α,
max kαz + uj kp ≤
j

max
kαz + ukp


≤ max
max
kαz + ukp
j
ku−uj kp ≤ǫ/3


= max
max kαz + uj + ūkp
j
kūkp ≤ǫ/3


≤ max
max kαz + uj kp + kūkp
kukq ≤λkβkq∗

j

kūkp ≤ǫ/3

= ǫ/3 + max kαz + uj kp .
j

29

Similarly, one has for z̄ = zp−1 /kzkp−1
that maxj u′j z̄ − maxkukq ≤λkβkq∗ u′ z̄ ≤ ǫ/3. (This uses
p
the fact that kz̄kp∗ = 1.) Now for each j choose α̂j so that for all α > α̂j ,
kαz + uj kp − kαzkp − u′j z̄ ≤ ǫ/3.
Define α̂ = maxj α̂j . Now observe that by combining the above two observations, one has for
any α > α̂ that


max

kukq ≤λkβkq∗


max
u z̄ ≤
kαz + ukp − kαzkp −
kukq ≤λkβkq∗


 
′
≤ 2ǫ/3 + max kαz + uj kp − kαzkp − max uℓ z̄




′

j

ℓ

≤ 2ǫ/3 + max kαz + uj kp − kαzkp −
j

u′j z̄

≤ 2ǫ/3 + ǫ/3 = ǫ.
Noting that maxkukq ≤λkβkq∗ u′ z̄ = λkβkq∗ kz̄kq∗ concludes the proof of (18). We now claim that
min
z

First note that
min
z

kzp−1 kq∗
kzkp−1
p

kzp−1 kq∗
kzkp−1
p

=

1
.
δm (q, p)

= min
z̃

(19)

kz̃kq∗
.
kz̃kp∗

(20)

We prove this as follows: given z, let z̃ = zp−1 . Then one can show that kz̃kp∗ /kzkp−1
= 1, and
p
p−1
p−1
so kz̃kp∗ /kz̃kq∗ = kzkp /kz kq∗ . The converse is similar, proving (20). Finally, note that
min
z̃

kz̃kq∗
1
=
kz̃kp∗
δm (p∗ , q ∗ )

which follows from an elementary analysis using the definition of δm . Combined with the
observation that δm (p∗ , q ∗ ) = δm (q, p), which follows by a simply duality argument (or by
inspecting the formula), we have that (19) is proven. To finish the argument, pick any z ∈

p−1 k ∗ /kzkp−1 = 1/δ (q, p). Hence, now applying (18),
argminz kzp−1 kq∗ /kzkp−1
p
q
m
p . Per (19), kz

given any ǫ > 0, there exists some α > 0 large enough so that
max kαz + ∆βkp

∆∈UFq

!


− kαzkp +

λ
kβkq∗
δm (q, p)



≤ ǫ.

Therefore, the gap in the lower bound in (4) can be made arbitrarily small for any β ∈ Rn .
This concludes the proof.

30

Appendix B
This appendix includes an example of choice of loss function and uncertainty set under which (a)
regularization is not equivalent to robustification in general and (b) there exist problem instances
for which the regularization path and robustification path have no intersection. The example we
give is in the vector setting for simplicity, although the generalization to matrices is obvious.  
1
 
In particular, let m = m and n = 1, and consider U = U(1,2) and loss function ℓ2 , with y = 1
1

 
2
 
and X = 1. In symbols, the problem of interest is
0

min max ky − (X + ∆)βk2 ,
β

∆∈U(1,1)

where we simply use β because β is 1-dimensional. This can be rewritten exactly as

min
β

max

u:
kuk1 ≤λ|β|

   
2
1
   
1 − 1 β + u
0
1

.
2

One can argue in an elementary way that the (unique) solution to this problem, regardless of
λ ∈ (0, ∞), is β ∗ = 3/5.

We now turn our attention to the corresponding regularization problem, which as per Corollary

4, is
min ky − Xβk2 + ρ|β|.
β

By using a calculus argument, it is possible to show that as ρ ∈ (0, ∞) varies, the set of all solutions

β ∗ is the open interval (0, 3/5). In other words, the solution to the regularization problem is never
a solution to the robustification, and vice versa. This completes the counterexample.

31

