# Outlier-robust sparse/low-rank least-squares regression and robust matrix
completion

Philip Thompson

###### Abstract

We study high-dimensional least-squares regression within a subgaussian
statistical learning framework with heterogeneous noise. It includes
$s$-sparse and $r$-low-rank least-squares regression when a fraction
$\epsilon$ of the labels are adversarially contaminated. We also present a
novel theory of _trace-regression with matrix decomposition_ based on a new
application of the product process. For these problems, we show novel near-
optimal “subgaussian” estimation rates of the form
$r(n,d_{\mbox{\tiny{eff}}})+\sqrt{\log(1/\delta)/n}+\epsilon\log(1/\epsilon)$,
valid with probability at least $1-\delta$. Here, $r(n,d_{\mbox{\tiny{eff}}})$
is the optimal uncontaminated rate as a function of the effective dimension
$d_{\mbox{\tiny{eff}}}$ but independent of the failure probability $\delta$.
These rates are valid _uniformly_ on $\delta$, i.e., the estimators’ tuning do
not depend on $\delta$. Lastly, we consider noisy robust matrix completion
with non-uniform sampling. If only the low-rank matrix is of interest, we
present a novel near-optimal rate that is independent of the _corruption
level_ $a$. Our estimators are tractable and based on a new “sorted” Huber-
type loss. No information on $(s,r,\epsilon,a,\delta)$ are needed to tune
these estimators. Our analysis makes use of novel $\delta$-optimal
concentration inequalities for the multiplier and product processes which
could be useful elsewhere. For instance, they imply novel sharp oracle
inequalities for Lasso and Slope with optimal dependence on $\delta$.
Numerical simulations confirm our theoretical predictions. In particular,
“sorted” Huber regression can outperform classical Huber regression.

P. Thompson, Krannert School of Management, Purdue University, West Lafayette,
Indiana

<EMAIL_ADDRESS>
##  1 Introduction

Outlier-robust estimation has been a topic studied for many decades since the
seminal work by [49]. One of the objectives of the field is to device
estimators which are less sensitive to outlier sample contamination. The
formalization of outlyingness and the construction of robust estimators
matured in several directions. One common assumption is that the adversary can
only change a fraction $\epsilon$ of the original sample. For an extensive
overview we refer, e.g., to [47], [63], [50] and references therein.

Within a very general framework, the minimax optimality of several robust
estimation problems have been recently obtained in a series of elegant works
by [17, 18] and [45]. The construction, however, is based on Tukey’s depth, a
hard computational problem in higher dimensions. A recent trend of research,
initiated by [33] and [56], has focused in obtaining optimality of robust
estimators within the class of computationally tractable algorithms. The
_oblivious_ model assumes the contamination is independent of the original
sample. The above mentioned works also establish optimality for the
_adversary_ model where the outliers may depend arbitrarily on the sample. As
an example, near optimal mean estimators for the adversarial model can now be
computed in nearly-linear time [23, 37, 31, 28]. We refer to the recent survey
[34] for an extensive survey.

In the realm of robust linear regression, two broad lines of investigations
exist: (1) one in which only the response (label) is contaminated and (2) the
more general setting in which the covariate (feature) is also corrupted [32];
[35]. Model (1), albeit less general, has been considered in many applications
and studied in numerous past and recent works [13, 59, 80, 46, 74]. It has
also some connection with the problems of robust matrix completion [14, 22,
21, 59, 54] and matrix decomposition [16, 14, 88, 48, 2]. Both models (1) and
(2) have been considered assuming adversarial or oblivious contamination. For
instance, an interesting property of model (1) with oblivious contamination is
the existence of consistent estimators, a property not shared by the adversary
model. See for instance the recent papers [83, 8, 80, 46, 74]. We refer to
Section 3 for further references and discussion.

In this work, we revisit the problem of outlier-robust least-squares
regression with adversarial label contamination. We are particularly
interested on the high-dimensional scaling. In this setting, not only the
sample is corrupted by $o$ outliers but its sample size $n$ is prohibitively
smaller than the extrinsic dimension $p$. We will focus in the setting where
the label-feature distribution is subgaussian. We pay particularly attention
to the following points:

  * (a)

_High dimensions._ We consider the general framework of _trace-regression_
with parameters in $\mathds{R}^{p}:=\mathbb{R}^{d_{1}\times d_{2}}$ assuming
$n\ll p:=d_{1}d_{2}$. It includes in particular $s$-sparse linear regression
[82], noisy compressed sensing with a low-rank parameter [68] and noisy robust
matrix completion [54]. One practical appeal of the established theory of
high-dimensional estimation is the existence of efficient estimators
_adaptive_ to $(s,r)$. We wish to avoid knowledge of $(s,r,o)$, at least in
the label contamination model.

  * (b)

_Noise heterogeneity._ A large portion of the literature in outlier-robust
sparse linear regression assumes the noise is independent of the feature. This
model is relevant in its own right. However, we wish to assume no particular
assumptions between noise and features and consider the statistical learning
framework with the linear hypothesis class.

  * (c)

_Subgaussian rates and uniform confidence level._ Significant effort has been
paid recently in obtaining minimax rates also with respect to the failure
probability $\delta$. Just to illustrate what this means, consider the
challenging problem of estimating the mean of a heavy-tailed $p$-dimensional
random vector with identity covariance. Minsker’s original bound [66] in this
case is $\sqrt{p\log(1/\delta)/n}$. The “subgaussian” rate
$\sqrt{p/n}+\sqrt{\log(1/\delta)/n}$ was obtained recently after a series of
works and include efficient estimators. For lack of space, we refer to the
recent survey [62]. The relevant point of the subgaussian rate is that
$\log(1/\delta)$ does not multiply the “effective dimension” $p$. A second
point is to what extent the estimator _tuning_ depends on $\delta$. Is it
possible to attain the optimal _subgaussian_ rate _uniformly_ on $\delta$,
that is, with a $\delta$-independent tuned estimator? In this work, we wish to
obtain $\delta$-uniform optimal subgaussian rates for the particular model of
least-squares regression with adversarial label contamination, subgaussian
data and validity of (a)-(b).

  * (d)

_Matrix decomposition._ With identity designs, this challenging problem was
first considered by [86], [16], [14], [88], [48] and [64]. A common assumption
in most of these works is the “incoherence” condition. Alternatively, [2]
studied this problem within a general framework for identity or random designs
assuming the “low-spikeness” condition. For instance, their framework includes
multivariate regression with random designs and low-rank plus sparse
components. For this problem, one fact used is that the design operator is
positive definite (one has $n\geq d_{1}$ albeit $n\ll d_{1}d_{2}$).
Unfortunately, the same property does not hold for the trace-regression
problem. Motivated by the problem of noisy compressed sensing with a matrix
parameter [68], we wonder if a correspondent theory exists for the problem of
trace-regression with low-rank plus sparse components.

The rest of the paper is organized as follows. We state our framework in
Section 2. Contributions and related work are discussed in Section 3. The main
results are stated formally in Section 4. Numerical simulations confirming the
theoretical predictions are presented in Section 5. We finalize with a
discussion in Section 6. The proofs are presented in the Supplemental
Material.

##  2 Framework

Throughout the paper, we use standard notations for norms in
$\mathds{R}^{p}=\mathbb{R}^{d_{1}\times d_{2}}$. The $\ell_{k}$-norm ($1\leq
k\leq\infty$) is denoted by $\|\cdot\|_{k}$, the Frobenius norm by
$\|\cdot\|_{F}$, the nuclear norm by $\|\cdot\|_{N}$ and the operator norm by
$\|\cdot\|_{\operatorname*{op}}$. The inner product in $\mathbb{R}^{k}$ will
be denoted by
$\langle\boldsymbol{v},\boldsymbol{w}\rangle=\boldsymbol{v}^{\top}\boldsymbol{w}$
while the inner product in $\mathds{R}^{p}$ will be denoted by
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\mathsf{tr}(\mathbf{V}^{\top}\mathbf{W})$.

###  2.1 Sparse and trace regression

Let $(\mathbf{X},y)\in\mathds{R}^{p}\times\mathbb{R}$ be a zero mean feature-
label pair. Within a statistical learning framework, we wish to explain $y$
trough $\mathbf{X}$ via the linear class
$\mathscr{F}=\\{\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\cdot,\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle:\mathbf{B}\in\mathds{R}^{p}\\}.$
Precisely, giving a sample of $(\mathbf{X},y)$, we wish to estimate

(1)
$\displaystyle\mathbf{B}^{*}\in\operatorname*{argmin}_{\mathbf{B}\in\mathds{R}^{p}}\mathbb{E}\left[y-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\right]^{2}.$

In particular, one has
$y=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{B}^{*}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle+\xi$
with $\xi\in\mathbb{R}$ satisfying $\mathbb{E}[\xi\mathbf{X}]=0$. We consider
the following assumption on the available sample.

######  Assumption 1 (Adversarial label contamination).

Let $\\{(y_{i}^{\circ},\mathbf{X}_{i}^{\circ})\\}_{i\in[n]}$ be an iid sample
from the distribution of $(\mathbf{X},y)$. We assume available a sample
$\\{(y_{i},\mathbf{X}_{i})\\}_{i\in[n]}$ such that
$\mathbf{X}_{i}=\mathbf{X}_{i}^{\circ}$ for all $i\in[n]$ and $o$ arbitrary
outliers replace the label sample $\\{y_{i}^{\circ}\\}_{i\in[n]}$. We denote
the fraction of contamination by $\epsilon:=\frac{o}{n}$.

It will be useful to define the _design operator_ with components
$\mathfrak{X}_{i}(\mathbf{B}):=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i},\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle$.
Under Assumption 1, one may write

(2)
$\displaystyle\boldsymbol{y}=\mathfrak{X}(\mathbf{B}^{*})+\sqrt{n}\boldsymbol{\theta}^{*}+\boldsymbol{\xi},$

where $\boldsymbol{y}=(y_{i})_{i\in[n]}$,
$\boldsymbol{\xi}=(\xi_{i})_{i\in[n]}$ is an iid copy of $\xi$ and
$\boldsymbol{\theta}^{*}\in\mathbb{R}^{n}$ is an arbitrary and unknown
corruption vector having at most $o$ nonzero components.

######  Example (Sparse linear regression).

In sparse _linear regression_ [84, 10], we have
$\boldsymbol{x}:=\mathbf{X}\in\mathbb{R}^{p}$ and
$\boldsymbol{b}^{*}:=\mathbf{B}^{*}\in\mathbb{R}^{p}$ with at most $s\ll p$
nonzero coordinates ($d_{1}=p$, $d_{2}=1$). One may write the design as
$\mathfrak{X}(\boldsymbol{b}):=\mathbb{X}\boldsymbol{b}$ where $\mathbb{X}$ is
the _design matrix_ whose $i$th row is $\boldsymbol{x}_{i}^{\top}$.

######  Example (Low-rank trace-regression).

In low-rank _trace-regression_ [76, 68], the parameter
$\mathbf{B}^{*}\in\mathds{R}^{p}$ is assumed to have rank $r\ll d_{1}\wedge
d_{2}$.

Given nonincreasing positive sequence $\\{\omega_{i}\\}_{i\in[n]}$, the Slope
norm [11] at a point $\boldsymbol{u}\in\mathbb{R}^{n}$ is defined by

$\|\boldsymbol{u}\|_{\sharp}:=\sum_{i\in[n]}\omega_{i}\boldsymbol{u}_{i}^{\sharp},$

where $\boldsymbol{u}_{1}^{\sharp}\geq\ldots\geq\boldsymbol{u}_{n}^{\sharp}$
denotes the nonincreasing rearrangement of the absolute coordinates of
$\boldsymbol{u}$. Throughout this paper, we fix the sequence
$\boldsymbol{\omega}:=(\omega_{i})_{i\in[n]}$ to be $\omega_{i}:=\log(An/i)$
for some $A\geq 2$.

######  Definition 2.1 (Sorted Huber’s loss).

Given $\tau>0$, let
$\rho_{\tau\boldsymbol{\omega}}:\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$ be
the optimal value of the proximal map associated to the Slope norm
$\tau\|\cdot\|_{\sharp}$. Precisely,
$\rho_{\tau\boldsymbol{\omega}}(\boldsymbol{u}):=\min_{\boldsymbol{z}\in\mathbb{R}^{n}}\frac{1}{2}\|\boldsymbol{z}-\boldsymbol{u}\|_{2}^{2}+\tau\|\boldsymbol{z}\|_{\sharp}.$
Given $\tau>0$, we define the loss (3)
$\displaystyle\mathcal{L}_{\tau\boldsymbol{\omega}}(\mathbf{B}):=\rho_{\tau\boldsymbol{\omega}}\left(\frac{\boldsymbol{y}-\mathfrak{X}(\mathbf{B})}{\sqrt{n}}\right).$

Albeit being convex, the loss in Definition 2.1 does not possess an explicit
expression in general. One exception is when $\omega_{1}=\ldots=\omega_{n}$.
In this case, if $\omega_{1}=1$,

(4)
$\displaystyle\mathcal{L}_{\tau\boldsymbol{\omega}}(\mathbf{B})=\tau^{2}\sum_{i=1}^{n}\Phi\left(\frac{y_{i}-\mathfrak{X}_{i}(\mathbf{B})}{\tau\sqrt{n}}\right),$

where $\Phi:\mathbb{R}\rightarrow\mathbb{R}$ is the Huber’s function defined
by $\Phi(t)=\min\\{(\nicefrac{{1}}{{2}})t^{2},|t|-\nicefrac{{1}}{{2}}\\}$.
Thus, Huber regression corresponds to $M$-estimation with the loss
$\mathcal{L}_{\tau\boldsymbol{\omega}}$ with _constant_ weighting sequence
$\boldsymbol{\omega}$.

In this work, we instead advocate the use of the loss
$\mathcal{L}_{\tau\boldsymbol{\omega}}$ with weighting sequence
$\boldsymbol{\omega}=(\omega_{i})_{i\in[n]}$ given by $\omega_{i}=\log(An/i)$.
This corresponds to $M$-estimation with a “sorted” modification of Huber
regression. In high-dimensions, we additionally use a regularization norm.
Given a convex norm $\mathcal{R}$ over $\mathds{R}^{p}$, we consider the
estimator

(5) $\displaystyle\hat{\mathbf{B}}\in$
$\displaystyle\operatorname*{argmin}_{\mathbf{B}\in\mathds{R}^{p}}\rho_{\tau\boldsymbol{\omega}}\left(\frac{\boldsymbol{y}-\mathfrak{X}(\mathbf{B})}{\sqrt{n}}\right)+\lambda\mathcal{R}(\mathbf{B}).$

A well known fact in the literature is that linear regression with Huber’s
loss corresponds to a Lasso-type estimator in the augmented variable
$[\mathbf{B};\boldsymbol{\theta}]\in\mathds{R}^{p}\times\mathbb{R}^{n}$ [78,
38]. Similarly, estimator (5) is equivalent to the following augmented least-
squares estimator:

(6) $\displaystyle[\hat{\mathbf{B}},\hat{\boldsymbol{\theta}}]\in$
$\displaystyle\operatorname*{argmin}_{[\mathbf{B};\boldsymbol{\theta}]\in\mathds{R}^{p}\times\mathbb{R}^{n}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i},\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\sqrt{n}\boldsymbol{\theta}_{i}\right)^{2}+\lambda\mathcal{R}(\mathbf{B})+\tau\|\boldsymbol{\theta}\|_{\sharp}.$

If $\mathcal{R}$ is either the $\ell_{1}$-norm, the Slope norm in
$\mathbb{R}^{p}$ or the nuclear norm in $\mathbb{R}^{d_{1}\times d_{2}}$, one
practical appeal of problem (6) is that it may be computed by alternated
convex optimization using Lasso and Slope solvers [11].

###  2.2 Trace-regression with matrix decomposition

[2] considered a general framework for the _matrix decomposition problem_ : to
estimate a pair
$[\mathbf{B}^{*};\boldsymbol{\Gamma}^{*}]\in(\mathds{R}^{p})^{2}$ given a
noisy linear observation of its sum. In the case of random design and noise,
their model is

(7)
$\displaystyle\mathbf{Y}=\mathfrak{X}(\mathbf{B}^{*}+\boldsymbol{\Gamma}^{*})+\boldsymbol{\Xi},$

where the design $\mathfrak{X}:\mathds{R}^{p}\rightarrow\mathbb{R}^{n\times
m}$ take values on matrices with $n$ iid rows and
$\boldsymbol{\Xi}\in\mathbb{R}^{n\times m}$ is a noise matrix independent of
$\mathfrak{X}$ with $n$ centered iid rows. Among several results in [2], one
application with random design is _multi-task learning_ with $d_{1}$
“features” and $d_{2}$ “tasks”, assuming normal covariates
$\boldsymbol{x}\in\mathbb{R}^{d_{1}}$. In this setting, model (7) corresponds
to having an iid sample
$\\{(\boldsymbol{x}_{i},\boldsymbol{y}_{i})\\}_{i=1}^{n}$ satisfying the model
$\boldsymbol{y}_{i}=(\mathbf{B}^{*}+\boldsymbol{\Gamma}^{*})^{\top}\boldsymbol{x}_{i}+\boldsymbol{\xi}_{i}$
with $\boldsymbol{\xi}_{i}$ independent of $\boldsymbol{x}_{i}$ and design
operator $\mathfrak{X}_{i}(\mathbf{B}):=\boldsymbol{x}_{i}^{\top}\mathbf{B}$.

Motivated by the correspondent problem in matrix “compressed sensing” [68], we
investigate matrix decomposition in the trace regression problem within a
statistical learning framework: to estimate the pair

(8)
$\displaystyle[\mathbf{B}^{*};\boldsymbol{\Gamma}^{*}]\in\operatorname*{argmin}_{[\mathbf{B};\boldsymbol{\Gamma}]\in(\mathds{R}^{p})^{2}}\mathbb{E}\left[y-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{B}+\boldsymbol{\Gamma}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\right]^{2},$

given sample of $(\mathbf{X},y)\in\mathds{R}^{p}\times\mathbb{R}$. In
particular, one has
$y=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{B}^{*}+\boldsymbol{\Gamma}^{*}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle+\xi$
with $\xi\in\mathbb{R}$ satisfying $\mathbb{E}[\xi\mathbf{X}]=0$. In high-
dimensions, one assumes that $\mathbf{B}^{*}$ has low-rank and
$\boldsymbol{\Gamma}^{*}$ is sparse. If
$\\{(y_{i},\mathbf{X}_{i})\\}_{i\in[n]}$ is an iid sample of $(y,\mathbf{X})$
and $\\{\xi_{i}\\}_{i\in[n]}$ an iid copy of $\xi$, one may write

(9)
$\displaystyle\boldsymbol{y}=\mathfrak{X}(\mathbf{B}^{*}+\boldsymbol{\Gamma}^{*})+\boldsymbol{\xi},$

where $\mathfrak{X}:\mathds{R}^{p}\rightarrow\mathbb{R}^{n}$ is as in Section
2.1, $\boldsymbol{y}=(y_{i})_{i\in[n]}$ and
$\boldsymbol{\xi}=(\xi_{i})_{i\in[n]}$.

Following [2], we consider the assumption:

######  Assumption 2 (Low-spikeness).

Assume $\mathbf{X}$ is isotropic, there is,
$\mathbb{E}[\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle^{2}]=\|\mathbf{V}\|_{F}^{2}$
for all $\mathbf{V}\in\mathds{R}^{p}$. Moreover, assume there exists
$\mathsf{a}^{*}>0$ such that

(10)
$\displaystyle\|\mathbf{B}^{*}\|_{\infty}\leq\frac{\mathsf{a}^{*}}{\sqrt{n}}.$

######  Remark 1.

The low-spikeness condition in [2] is
$\|\mathbf{B}^{*}\|_{\infty}\leq\mathsf{a}^{*}/\sqrt{d_{1}d_{2}}$ for some
$\mathsf{a}^{*}>0$. In high-dimensions ($n\leq d_{1}d_{2}$) and assuming
isotropy, it implies Assumption 2.

We consider the constrained estimator

(13)
$\displaystyle\begin{array}[]{ccl}[\hat{\mathbf{B}},\hat{\boldsymbol{\Gamma}}]&\in&\operatorname*{argmin}_{[\mathbf{B};\boldsymbol{\Gamma}]\in(\mathds{R}^{p})^{2}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i},\mathbf{B}+\boldsymbol{\Gamma}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\right)^{2}+\lambda\|\mathbf{B}\|_{N}+\tau\|\boldsymbol{\Gamma}\|_{1}\\\
&&\mbox{s.t.}\quad\|\mathbf{B}\|_{\infty}\leq\frac{\mathsf{a}^{*}}{\sqrt{n}}.\end{array}$

###  2.3 Robust matrix completion

The matrix completion problem consists in estimating a low-rank matrix
$\mathbf{B}^{*}\in\mathds{R}^{p}$ having sampled an incomplete subset of its
entries. Several works have obtained statistical bounds for this problem using
nuclear norm relaxation [41, 79], either with the “incoherence” condition
[15], the “low-spikeness” condition [69] or assuming an upper bound on the
sup-norm of $\mathbf{B}^{*}\in\mathds{R}^{p}$ [55, 53]. Note that matrix
completion may be equivalently seen as the trace-regression problem with
$\mathbf{X}$ having a discrete distribution $\Pi$ supported on the canonical
basis

(14)
$\mathcal{X}:=\\{\boldsymbol{e}_{j}\bar{\boldsymbol{e}}_{k}^{\top}:j\in[d_{1}],k\in[d_{2}]\\},$

where $\boldsymbol{e}_{j}$ is the $j$th canonical vector in
$\mathbb{R}^{d_{1}}$ and $\bar{\boldsymbol{e}}_{k}$ is the $k$th canonical
vector in $\mathbb{R}^{d_{2}}$. The $i$th observed entry
$\mathbf{B}_{j(i),k(i)}$ of $\mathbf{B}$ corresponds to
$\mathbf{X}_{i}=\boldsymbol{e}_{j(i)}\bar{\boldsymbol{e}}_{k(i)}^{\top}$.

In robust matrix completion, a fraction of the sampled entries are corrupted
by outliers. [54] consider this problem in the noisy setting through the lens
of the matrix decomposition model (9) where the corruption matrix
$\boldsymbol{\Gamma}^{*}\in\mathds{R}^{p}$ have at most $o$ nonzero entries.
Optimal minimax bounds are derived on the class of parameters
$[\mathbf{B}^{*},\boldsymbol{\Gamma}^{*}]$ with bounded sup-norm, where
$\mathbf{B}^{*}$ is low-rank and $\boldsymbol{\Gamma}^{*}$ is a sparse
corruption matrix.

It some applications, only the sampled low-rank matrix $\mathbf{B}^{*}$ is of
interest. In that case, one may equivalently see the same problem as a
response adversarial trace regression problem (2) under Assumption 1. In this
work we use this point of view on the class of parameters $\mathbf{B}^{*}$
with low-rank and bounded sup norm. Recall the loss
$\rho_{\tau\boldsymbol{\omega}}$ in Definition 2.1. For tuning parameters
$\lambda,\tau>0$ and $\mathsf{a}>0$, we consider the constrained estimator

(17)
$\displaystyle\begin{array}[]{ccl}\hat{\mathbf{B}}&\in&\operatorname*{argmin}_{\mathbf{B}\in\mathds{R}^{p}}\rho_{\tau\boldsymbol{\omega}}\left(\frac{\boldsymbol{y}-\mathfrak{X}(\mathbf{B})}{\sqrt{n}}\right)+\lambda\frac{\|\mathbf{B}\|_{N}}{\sqrt{p}}\\\
&&\mbox{s.t.}\quad\|\mathbf{B}\|_{\infty}\leq\mathsf{a}.\end{array}$

Equivalently, $\hat{\mathbf{B}}$ can be computed via the augmented estimator

(20)
$\displaystyle\begin{array}[]{ccl}[\hat{\mathbf{B}},\hat{\boldsymbol{\theta}}]&\in&\operatorname*{argmin}_{[\mathbf{B};\boldsymbol{\theta}]\in\mathds{R}^{p}\times\mathbb{R}^{n}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i},\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\sqrt{n}\boldsymbol{\theta}_{i}\right)^{2}+\lambda\frac{\|\mathbf{B}\|_{N}}{\sqrt{p}}+\tau\|\boldsymbol{\theta}\|_{\sharp}\\\
&&\mbox{s.t.}\quad\|\mathbf{B}\|_{\infty}\leq\mathsf{a}.\end{array}$

##  3 Contributions and related work

###  3.1 Robust sparse least-squares regression

For sparse least-squares regression with adversarial response contamination
and subgaussian $(\boldsymbol{x},\xi)$, we show that estimator (5) achieves
the subgaussian rate

(21) $\displaystyle r_{n}+\sqrt{\log(1/\delta)/n}+\epsilon\log(1/\epsilon),$

with probability at least $1-\delta$, for any given $\delta\in(0,1)$. Here,
$r_{n}=\sqrt{s\log p/n}$ taking $\mathcal{R}$ to be the $\ell_{1}$-norm and
$r_{n}=\sqrt{s\log(ep/s)/n}$ taking $\mathcal{R}$ to be the Slope norm on
$\mathbb{R}^{p}$ (see Theorem 4.1). Note that we show such property with
tuning parameters $(\tau,\lambda)$ _independent of the failure probability
$\delta$_. The above bound is valid for a breakdown point $\epsilon\leq c$,
where $c$ is a constant. The above rate is optimal up to a log factor in
$1/\epsilon$ [17, 18, 45, 24]. These bounds are attained with no information
on $(s,o)$ and within the statistical learning framework with the linear
class. To the best of our knowledge, previous works on corrupted sparse linear
regression have assumed the noise independent of the features.

Sparse linear regression with response contamination has been the subject of
numerous works. From a methodological point of view, the $\ell_{1}$-penalized
Huber’s estimator has been considered in [77, 78, 58]. Empirical evaluation
for the choice of tuning parameters is comprehensively studied in these
papers. As already observed in past work [78, 38], Huber’s estimator with
$\ell_{1}$-penalization is equivalent to the augmented estimator

(22) $\displaystyle[\hat{\boldsymbol{b}},\hat{\boldsymbol{\theta}}]\in$
$\displaystyle\operatorname*{argmin}_{[\boldsymbol{b};\boldsymbol{\theta}]\in\mathbb{R}^{p}\times\mathbb{R}^{n}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\langle\boldsymbol{x}_{i},\boldsymbol{b}\rangle-\sqrt{n}\boldsymbol{\theta}_{i}\right)^{2}+\lambda\|\boldsymbol{b}\|_{1}+\tau\|\boldsymbol{\theta}\|_{1}.$

In the response adversarial model with Gaussian data, fast rates for such
estimator have been obtained in [13, 57, 27, 26, 72]. The minimax optimality
of estimator (22), up to log factors, was achieved only recently in [29],
showing it satisfies the rate

$\sqrt{s\log(p/\delta)/n}+\epsilon\log(n/\delta),$

with a breakdown point $\epsilon\leq c/\log n$ for a constant $c>0$. In
addition to $\log n$ factors, the above rate is not subgaussian in $\delta$.
The $\ell_{1}$-penalized Huber’s estimator was later shown to attain the
subgaussian rate by [25] assuming the features are Gaussian, knowledge of
$(s,o)$ and independence between features and noise. We highlight that the
approximately linear growth in $\epsilon$ in the error estimate (21) using the
Sorted Huber loss is confirmed in our numerical experiments. See Section 5,
Figure 1(a). Besides the mentioned theoretical improvements in the rate, we
observed in simulations that robust least-squares estimation with the Sorted
Huber loss can outperform classical Huber regression (see Figure 1(b)).

We remark that label contamination in regression has been considered in
different contamination models with dense bounded noise in [87, 59, 71, 42,
1]. This setting is also studied in [51] with the LAD-estimator [85].
Alternatively, a refined analysis of iterative thresholding methods were
considered in [9], [8], [80], [67]. They obtain sharp breakdown points and
consistency bounds for the oblivious model. Works on sparse linear regression
with covariate contamination were considered early on by [19] and, more
recently, in [3], albeit with worst rates and breakdown points compared to the
response contamination model. Works by [60, 61] have also studied the
optimality of sparse linear regression in models with error-in-variables and
missing-data covariates.

Although out of scope, we mention for completeness that tractable algorithms
for linear regression with covariate contamination have been intensively
investigated in the low-dimensional scaling ($n\geq p$), with initial works by
[32]; [35, 75] and more recent ones in [30, 24, 73].

###  3.2 Robust trace-regression and matrix completion

_Robust trace-regression._ In [68, 70] it is proposed a general framework of
$M$-estimators with decomposable regularizers. Among several different
results, they obtain optimal rates for trace-regression with Gaussian designs
for the first time. Precisely, they attain the minimax rate
$\sqrt{rd_{1}/n}+\sqrt{rd_{2}/n}$ with failure probability
$e^{-c(d_{1}+d_{2})}$, for some constant $c>0$, and noise independent of
$\mathbf{X}$. Of course, their bounds can be translated to a optimal bound in
average. With respect to the failure probability, however, their bounds are
not subgaussian optimal. Inspired by their results and with the objectives
(a)-(c) of Section 1 in mind, we consider trace-regression with response
adversarial contamination and subgaussian data. Within the statistical
learning framework, we show that estimator (5) with nuclear norm
regularization achieves the subgaussian rate

(23)
$\displaystyle\sqrt{rd_{1}/n}+\sqrt{rd_{2}/n}+\sqrt{\log(1/\delta)/n}+\epsilon\log(1/\epsilon),$

with failure probability $\delta$ and breakdown point $\epsilon\leq c$ for a
positive constant $c$ (see Theorem 4.2). The tuning of estimator (5) is
independent of $\delta$ and the above rate is optimal up to a log factor in
$1/\epsilon$ [17, 18, 45]. We are not aware of previous work showing that
efficient estimators attain the above rate under our set of assumptions. We
confirm in our simulations the approximately linear growth in $\epsilon$ in
the rate (23). See Figure 2(a) in Section 5.

_Trace-regression with matrix decomposition._ Several works studied the
problem of matrix decomposition with identity designs and the “incoherence”
condition [14, 16, 48, 21]. Alternatively, [2] viewed such problem in a
general framework assuming “low-spikeness”. Among several applications, multi-
task learning is one of them. We consider the different problem of matrix
compressed sensing [68] with $r$-low-rank plus $s$-sparse components
satisfying the “low-spikeness” condition and an isotropic design (see Section
2.2). Unlike multi-task learning, the design is not positive definite in high-
dimensions, so an alternative argument is required. Under Assumption 2 and
subgaussian design, we show that estimator (13), with tuning independent of
$\delta$, attains the near-optimal subgaussian rate

(24) $\displaystyle\sqrt{rd_{1}/n}+\sqrt{rd_{2}/n}+\sqrt{s\log
p/n}+\mathsf{a}^{*}\sqrt{s/n}+\sqrt{\log(1/\delta)/n},$

with failure probability $\delta$ (see Theorem 4.3). This is valid within the
statistical learning framework and with no information on $(r,s)$. We are not
aware of previous work establishing any estimation theory for this problem. In
our simulations, we were able to confirm the linear growth in $r$ (for fixed
$s$) and $s$ (for fixed $r$) predicted by the rate (24). See Section 5, Figure
3.

_Robust matrix completion._ The literature on matrix completion using nuclear
norm relaxation [41, 79] is extensive. For instance, bounds for exact recovery
were first obtained by [15] where the notion of “incoherence” was introduced.
[69] considers noisy matrix completion with the different notion of “low-
spikeness”. Several works on exact and noisy set-up exist. As we are mainly
interested in the corrupted model, a complete overview is out of scope. We
refer to further references in [53, 54] and the recent work [20] for a
comprehensive review on matrix completion under the “incoherence” assumption.

Related to our work are [44, 52, 43, 55, 53, 54, 12]. In these papers the main
assumption is that an upper bound on the parameter sup-norm
$\|\cdot\|_{\infty}$ is known. Robust matrix completion is considered in [40,
39] and [54]. [40] and [39] are mainly concerned with the heavy-tailed model.
Like this work, [54] considers the outlier contamination model with noise.
Assuming known $\mathsf{a}>0$ such that
$\mathsf{a}\geq\|\mathbf{B}^{*}\|_{\infty}\vee\|\boldsymbol{\Gamma}^{*}\|_{\infty}$,
[54] establish optimal minimax bounds for model (9) over the class

(25)
$\displaystyle\mathcal{A}(r,o,\mathsf{a})=\\{\mathbf{B}+\boldsymbol{\Gamma}\in\mathds{R}^{p}:\operatorname*{rank}(\mathbf{B})\leq
r,\|\boldsymbol{\Gamma}\|_{0}\leq
o,\|\mathbf{B}\|_{\infty}\vee\|\boldsymbol{\Gamma}\|_{\infty}\leq\mathsf{a}\\}.$

As usual, $\|\mathbf{A}\|_{0}$ denotes the number of nonzero entries of matrix
$\mathbf{A}$. Assuming known $\mathsf{a}>0$ such that
$\mathsf{a}\geq\|\mathbf{B}\|_{\infty}$, we instead consider noisy robust
matrix completion for model (2) on the class

(26)
$\displaystyle\bar{\mathcal{A}}(r,o,\mathsf{a})=\\{[\mathbf{B};\boldsymbol{\theta}]\in\mathds{R}^{p}\times\mathbb{R}^{n}:\operatorname*{rank}(\mathbf{B})\leq
r,\|\boldsymbol{\theta}\|_{0}\leq o,\|\mathbf{B}\|_{\infty}\leq\mathsf{a}\\}.$

For simplicity, let us assume $d_{1}=d_{2}=d$. Under similar distributional
assumptions of [54], we show that estimator (20) attains, up to logs, the rate

(27)
$\displaystyle\mathsf{a}\sqrt{(dr/n)\log(1/\delta)}+\mathsf{a}\sqrt{\log(1/\delta)/n}+\mathsf{a}\sqrt{\epsilon\log(1/\epsilon)}.$

We refer to Theorem 4.4 for details. This rate is optimal on the class
$\bar{\mathcal{A}}(r,o,\mathsf{a})$ up to log factors. In Figure 2(b) in
Section 5, we confirm the dependence on $\epsilon$ predicted in rate (27).
Finally, we note that our bounds are not fully comparable to [54] whose aim is
to estimate the pair $[\mathbf{B}^{*};\boldsymbol{\Gamma}^{*}]$. On the other
hand, there are many applications for which only the low-rank parameter
$\mathbf{B}^{*}$ is of interest. In this setting, our bound (27) show a
significant improvement as it depends only on an upper bound on the sup norm
of the _low-rank parameter_ $\mathbf{B}^{*}$. The _corruption level_
$\|\boldsymbol{\theta}^{*}\|_{\infty}$ is irrelevant, either in the rate or in
tuning the estimator. We have verified this phenomenon in our simulations. See
Section 5.

###  3.3 Comments on the proofs

We finish with some technical remarks. Related to our work is [29]. They
obtain rates for sparse linear regression with adversarial label contamination
for the Gaussian model and noise independent of features. The rates in [29]
are near-optimal and valid for $\epsilon\lesssim 1/\log n$. These rates,
however, are not optimal with respect to the failure probability $\delta$. In
order to establish subgaussian optimal rates (in the sense of item (c) in
Section 1) with $(p,n,s,\delta)$-independent breakdown point $\epsilon\lesssim
1/2$ and within the statistical learning framework, our theory relies on new
concentration inequalities for the _multiplier process_ (MP) and _product
process_ (PP). Impressive bounds for these processes were obtained by [65]
which hold for general classes having only a few bounded moments. In
establishing subgaussian rates, our arguments need concentration inequalities
for the MP and PP with improvements concerning the confidence level. Tailored
specifically to subgaussian classes, these are proven in Theorems 11.6 and
11.8 in the supplemental material. We believe these bounds may be useful
elsewhere, in particular, Compressive Sensing theory. Their proof makes use of
the “generic chaining” method, originally proposed by [81]. More precisely,
our proof is inspired by improved generic chaining methods by [36] and [5] for
the _quadratic process_. We also highlight that our theory of robust
regression makes crucial use of a high-probability version of _Chevet’s
inequality_ for subgaussian processes.

We are also inspired by the findings of [7] regarding Slope regularization in
sparse linear regression. This paper goes beyond the _exact_ sparse setting
presenting sharp _oracle inequalities_ for the Lasso and Slope estimators. It
is shown for the first time in [7] that, in the Gaussian setting, Lasso indeed
satisfies an oracle inequality with the _subgaussian_ rate (see item (c) in
Section 1). It is also shown that Lasso and Slope can be tuned _independently_
of $\delta$ assuming subgaussian data with noise independent of features. In
that setting, however, we argue that the rate is not exactly subgaussian.
Although not the main objective of this paper, our new concentration
inequality for the Multiplier Process (see Theorem 11.6 in the Supplemental
Material) imply oracle inequalities for the Lasso and Slope with
$\delta$-independent tuning and with the optimal subgaussian rate. This is
valid even when the noise may depend on the features. These oracle
inequalities are presented in detail in Section 11.4 of the Supplemental
Material.

The proof of Theorem 4.4 for noisy robust matrix completion has connections
with [69, 54]. These papers, however, invoke a _two-sided_ concentration
inequality for bounded processes. One noticeable difference in our proof is
that we use a _one-sided_ tail inequality by Bousquet in order to derive a
sufficient lower bound. This lower bound readily suggests a cone in the
augmented space $\mathds{R}^{p}\times\mathbb{R}^{n}$ at which a restricted
eigenvalue condition (RE) is satisfied for the augmented design
$\mathfrak{M}(\mathbf{B};\boldsymbol{\theta}):=\mathfrak{X}(\mathbf{B})+\sqrt{n}\boldsymbol{\theta}.$
In the setting with no corruption ($\boldsymbol{\theta}\equiv 0$), our
argument requires a RE condition in a strictly _smaller_ cone than in [69].

##  4 Formal results

We first present some notation. We say that $a\lesssim b$ if $a\leq Cb$ for
some absolute constant $C>0$ and $a\asymp b$ if $a\lesssim b$ and $b\lesssim
a$. Given $\ell\in\mathbb{N}$, $[\ell]:=\\{1,\ldots,\ell\\}$. The
$\psi_{2}$-Orlicz norm will be denoted by $|\cdot|_{\psi_{2}}$. Finally, if
$\Pi$ is the distribution of $\mathbf{X}$, we define, for any
$\mathbf{V}\in\mathds{R}^{p}$, the pseudo-norm

$\|\mathbf{V}\|_{\Pi}:=\sqrt{\mathbb{E}[\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle^{2}]}.$

###  4.1 Robust sparse/low-rank least-squares regression

For the problems of robust sparse linear regression and trace-regression, the
following standard subgaussian condition will be assumed (see Theorems 4.1,
4.2 and 4.3).

######  Assumption 3.

Assume the random pair $(\mathbf{X},\xi)$, possibly non-independent, is such
that

  * (i)

There exists $L\geq 1$ such that
$|\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle|_{\psi_{2}}\leq
L\|\mathbf{V}\|_{\Pi}$ for all $\mathbf{V}\in\mathds{R}^{p}$.

  * (ii)

$1\leq|\xi|_{\psi_{2}}<\infty$.

We define $\sigma_{\xi}^{2}:=\mathbb{E}[\xi^{2}]$ and
$\sigma^{2}:=|\xi|^{2}_{\psi_{2}}$.

We start stating our results for robust sparse linear regression.

######  Theorem 4.1 (Robust sparse linear regression).

In the framework of Section 2.1, suppose $\boldsymbol{b}^{*}$ in Example
Example is a $s$-sparse vector. Denote by $\boldsymbol{\Sigma}$ the covariance
matrix of $\boldsymbol{x}$ and let

$\rho_{1}(\boldsymbol{\Sigma}):=\max_{j\in[p]}\sqrt{\boldsymbol{\Sigma}_{jj}}.$

Grant Assumptions 1 and 3 such that
$\sigma^{2}L^{2}\epsilon\log(1/\epsilon)\leq\mathsf{c}$ for some universal
constant $\mathsf{c}\in(0,1)$. Define $r_{n}:=\sqrt{s\log p/n}$ and $S=s\log
p$.

In estimator (5) with sequence $\omega_{i}=\log(An/i)$ for some $A\geq 2$,
take $\mathcal{R}$ to be the $\ell_{1}$-norm and tuning parameters
$\tau\asymp\sigma/\sqrt{n}$ and

(28) $\displaystyle\lambda\asymp
L\sigma\rho_{1}(\boldsymbol{\Sigma})\sqrt{\frac{\log p}{n}}.$

Then there are absolute positive constants $C$, $c_{1}$ and $c_{2}$ and
constant $\mu(\boldsymbol{b}^{*})\geq 0$ for which the following property
holds. For any $\delta\in(0,1)$, if one has

(29) $\displaystyle n$ $\displaystyle\geq
C\sigma^{2}L^{2}\rho^{2}_{1}(\boldsymbol{\Sigma})\mu^{2}(\boldsymbol{b}^{*})S,$
(30) $\displaystyle\delta$
$\displaystyle\geq\exp\left(-c_{1}\frac{n}{L^{4}}\right)\bigvee\exp\left(-c_{2}\frac{n}{\sigma^{2}L^{2}}\right),$

then, with probability at least $1-\delta$,

(31)
$\displaystyle\big{\|}\hat{\boldsymbol{b}}-\boldsymbol{b}^{*}\big{\|}_{\Pi}$
$\displaystyle\lesssim
L^{3}\sigma^{2}\rho^{2}_{1}(\boldsymbol{\Sigma})\mu^{2}(\boldsymbol{b}^{*})\cdot
r_{n}^{2}+L\sigma\rho_{1}(\boldsymbol{\Sigma})\mu(\boldsymbol{b}^{*})\cdot
r_{n}$ (32)
$\displaystyle\quad+(L^{3}\sigma^{2}+L^{2}\sigma)\frac{1+\log(1/\delta)}{n}+L\sigma\frac{1+\sqrt{\log(1/\delta)}}{\sqrt{n}}$
(33) $\displaystyle\quad+L\sigma^{2}\cdot\epsilon\log(1/\epsilon).$

If, instead of Lasso penalization, one takes $\mathcal{R}$ to be the Slope
norm in $\mathbb{R}^{p}$ with the sequence $\bar{w}_{j}=\log(\bar{A}p/j)$ for
some $\bar{A}\geq 2$ and tuning

(34)
$\displaystyle\lambda\asymp\frac{L\sigma\rho_{1}(\boldsymbol{\Sigma})}{\sqrt{n}},$

a similar bound holds but with $S=s\log(ep/s)$ and
$r_{n}=\sqrt{s\log(ep/s)/n}$.

Our bound for the robust low-rank trace-regression is stated next.

######  Theorem 4.2 (Robust trace-regression).

In Example Example in Section 2.1, suppose $\mathbf{B}^{*}$ has rank $r$.
Denote by $\boldsymbol{\Sigma}$ the covariance matrix of $\mathbf{X}$ seen as
a vector in $\mathbb{R}^{p}$ and let

$\rho_{N}(\boldsymbol{\Sigma}):=\sup_{\|[\boldsymbol{z};\boldsymbol{v}]\|_{2}=1}\sqrt{\mathbb{E}[(\boldsymbol{z}^{\top}\mathbf{X}\boldsymbol{v})^{2}]}.$

Grant Assumptions 1 and 3 such that
$\sigma^{2}L^{2}\epsilon\log(1/\epsilon)\leq\mathsf{c}$ for some universal
constant $\mathsf{c}\in(0,1)$. In estimator (5) with sequence
$\omega_{i}=\log(An/i)$ for some $A\geq 2$, take $\mathcal{R}$ to be the
nuclear norm and tuning parameters $\tau\asymp\sigma/\sqrt{n}$ and

(35) $\displaystyle\lambda\asymp
L\sigma\rho_{N}(\boldsymbol{\Sigma})\left(\sqrt{\frac{d_{1}}{n}}+\sqrt{\frac{d_{2}}{n}}\right).$

Then there are absolute positive constants $C$, $c_{1}$ and $c_{2}$ and
constant $\mu(\mathbf{B}^{*})\geq 0$ for which the following property holds.
For any $\delta\in(0,1)$, if one has

(36) $\displaystyle n$ $\displaystyle\geq
C\sigma^{2}L^{2}\rho^{2}_{N}(\boldsymbol{\Sigma})\mu^{2}(\mathbf{B}^{*})\cdot
r(d_{1}+d_{2}),$ (37) $\displaystyle\delta$
$\displaystyle\geq\exp\left(-c_{1}\frac{n}{L^{4}}\right)\bigvee\exp\left(-c_{2}\frac{n}{\sigma^{2}L^{2}}\right),$

then, with probability at least $1-\delta$,

(38) $\displaystyle\big{\|}\hat{\mathbf{B}}-\mathbf{B}^{*}\big{\|}_{\Pi}$
$\displaystyle\lesssim
L^{3}\sigma^{2}\rho^{2}_{N}(\boldsymbol{\Sigma})\mu^{2}(\mathbf{B}^{*})\frac{r(d_{1}+d_{2})}{n}+L\sigma\rho_{N}(\boldsymbol{\Sigma})\mu(\mathbf{B}^{*})\left(\sqrt{\frac{rd_{1}}{n}}+\sqrt{\frac{rd_{2}}{n}}\right)$
(39)
$\displaystyle\quad+(L^{3}\sigma^{2}+L^{2}\sigma)\frac{1+\log(1/\delta)}{n}+L\sigma\frac{1+\sqrt{\log(1/\delta)}}{\sqrt{n}}$
(40) $\displaystyle\quad+L\sigma^{2}\cdot\epsilon\log(1/\epsilon).$

The rates in Theorems 4.1 and 4.2 are optimal up to a log factor in
$1/\epsilon$ [17, 18, 45]. We make a remark concerning the constant
$\rho_{1}(\boldsymbol{\Sigma})$ used in the tuning parameters
$(\lambda,\tau)$. In Theorem 4.1, we may assume without loss on generality
that $\rho_{1}(\boldsymbol{\Sigma})$ is _unknown_ replacing them by the
estimates $\hat{\rho}_{1}:=\max_{j\in[p]}\|\mathbb{X}_{\bullet,j}\|_{2}$.
Indeed, concentration upper bounds111See Proposition 3 in the supplemental
material. for subgaussian $\boldsymbol{x}$ implies that
$|\hat{\rho}_{1}-\rho_{1}(\boldsymbol{\Sigma})|\leq
c_{n}\rho_{1}(\boldsymbol{\Sigma})$, where $c_{n}$ converges to zero with the
sample size scaling of Theorem 4.1. The same observation holds for Theorem
4.2, replacing $\rho_{N}(\boldsymbol{\Sigma})$ by the estimate

$\hat{\rho}_{N}:=\sup_{\|[\boldsymbol{z};\boldsymbol{v}]\|_{2}=1}\sqrt{\frac{1}{n}\sum_{i\in[n]}(\boldsymbol{z}^{\top}\mathbf{X}_{i}\boldsymbol{v})^{2}]}.$

######  Remark 2 (Restricted eigenvalue constants).

In Theorem 4.1,
$\mu(\boldsymbol{b}^{*})=\sup_{\boldsymbol{v}\in\mathscr{C}}\nicefrac{{\|\boldsymbol{v}\|_{2}}}{{\|\boldsymbol{v}\|_{\Pi}}}$
is the usual restricted eigenvalue constant, where $\mathscr{C}$ is a
dimension reduction cone associated to the $\ell_{1}$-norm and “sparsity
support” of $\boldsymbol{b}^{*}$ (see Section 8.1 in the Supplemental
Material). Analogous observations hold for Theorem 4.2. In that case,
$\mu(\mathbf{B}^{*})=\sup_{\mathbf{V}\in\mathscr{C}^{\prime}}\nicefrac{{\|\mathbf{V}\|_{F}}}{{\|\mathbf{V}\|_{\Pi}}}$
where $\mathscr{C}^{\prime}$ is a dimension reduction cone associated to the
nuclear norm and the “low-rank support” of $\mathbf{B}^{*}$. The constant
$\mu(\mathbf{B}^{*})$ is the condition number measuring how far $\Pi$ is from
the isotropic distribution.

Finally, we present the following upper bound on the estimation of the trace-
regression problem with matrix decomposition.

######  Theorem 4.3 (Trace-regression with matrix decomposition).

In the problem of trace-regression with matrix decomposition of Section 2.2,
suppose $\mathbf{B}^{*}$ has rank $r$ and $\boldsymbol{\Gamma}^{*}$ has at
most $s$ nonzero entries. Grant Assumptions 2 and 3. In estimator (13), take
tuning parameters

(41) $\displaystyle\lambda\asymp\sigma
L\left(\sqrt{\frac{d_{1}}{n}}+\sqrt{\frac{d_{2}}{n}}\right),\quad\tau\asymp\sigma
L\sqrt{\frac{\log p}{n}}+\frac{\mathsf{a}^{*}}{\sqrt{n}}.$

Then there are absolute positive constants $C$, $c_{1}$ and $c_{2}$ for which
the following property holds. For any $\delta\in(0,1)$, if one has

(42) $\displaystyle n$ $\displaystyle\geq C\left[\sigma^{2}L^{2}\cdot
r(d_{1}+d_{2})\right]\bigvee\left[\left(\sigma^{2}L^{2}\log
p+(\mathsf{a}^{*})^{2}\right)\cdot s\right],$ (43) $\displaystyle\delta$
$\displaystyle\geq\exp\left(-c_{1}\frac{n}{L^{4}}\right)\bigvee\exp\left(-c_{2}\frac{n}{\sigma^{2}L^{2}}\right).$

then, with probability at least $1-\delta$,

(44)
$\displaystyle\sqrt{\big{\|}\hat{\mathbf{B}}-\mathbf{B}^{*}\big{\|}_{F}^{2}+\big{\|}\hat{\boldsymbol{\Gamma}}-\boldsymbol{\Gamma}^{*}\big{\|}_{F}^{2}}$
$\displaystyle\lesssim\sigma
L\left(\sqrt{\frac{rd_{1}}{n}}+\sqrt{\frac{rd_{2}}{n}}\right)+\sigma
L\sqrt{\frac{s\log p}{n}}+\mathsf{a}^{*}\sqrt{\frac{s}{n}}$ (45)
$\displaystyle\quad+\sigma
L\frac{1+\sqrt{\log(1/\delta)}}{\sqrt{n}}+\sigma^{2}L^{2}\frac{1+\log(1/\delta)}{n}.$

The next proposition assures that the previous rate is optimal up to a log
factor and constants. Its proof follows from similar arguments in [2] for the
noisy matrix decomposition problem with identity design. Define the class

(46)
$\displaystyle\mathcal{A}(r,s,\mathsf{a}^{*})=\left\\{\boldsymbol{\Theta}^{*}:=[\mathbf{B}^{*};\boldsymbol{\Gamma}^{*}]\in(\mathds{R}^{p})^{2}:\operatorname*{rank}(\mathbf{B}^{*})\leq
r,\|\boldsymbol{\Gamma}^{*}\|_{0}\leq
s,\|\mathbf{B}^{*}\|_{\infty}\leq\frac{\mathsf{a}^{*}}{\sqrt{n}}\right\\}.$

For any
$\boldsymbol{\Theta}^{*}:=[\mathbf{B}^{*},\boldsymbol{\Gamma}^{*}]\in(\mathds{R}^{p})^{2}$,
let $\mathbb{P}_{\boldsymbol{\Theta}^{*}}$ denote the distribution of the data
$\\{y_{i},\mathbf{X}_{i}\\}_{i\in[n]}$ satisfying (9) with parameters
$[\mathbf{B}^{*},\boldsymbol{\Gamma}^{*}]$. Finally, for some $\sigma>0$, let

(47)
$\displaystyle\Psi_{n}(r,s,\mathsf{a}^{*}):=\sigma^{2}\left\\{\frac{r(d_{1}+d_{2})}{n}+\frac{s}{n}\log\left(\frac{p-s}{s/2}\right)\right\\}+(\mathsf{a}^{*})^{2}\frac{s}{n}.$

######  Proposition 1.

In the model (9) assume that $\\{\xi_{i}\\}_{i\in[n]}$ are iid
$\mathcal{N}(0,\sigma^{2})$ independent of $\\{\mathbf{X}_{i}\\}_{i\in[n]}$
and Assumption 2 holds. Assume $d_{1},d_{2}\geq 10$, $\mathsf{a}^{*}\geq
32\sqrt{\log p}$ and $s<p$.

Then there exists universal constants $c>0$ and $\beta\in(0,1)$ such that

(48)
$\displaystyle\inf_{\hat{\boldsymbol{\Theta}}}\sup_{\boldsymbol{\Theta}^{*}\in\mathcal{A}(r,s,\mathsf{a}^{*})}\mathbb{P}_{\boldsymbol{\Theta}^{*}}\left\\{\|\hat{\mathbf{B}}-\mathbf{B}^{*}\|_{F}^{2}+\|\hat{\boldsymbol{\Gamma}}-\boldsymbol{\Gamma}^{*}\|_{F}^{2}\geq
c\Psi_{n}(r,s,\mathsf{a}^{*})\right\\}\geq\beta,$

where the infimum is taken over all estimators
$\hat{\boldsymbol{\Theta}}=[\hat{\mathbf{B}},\hat{\boldsymbol{\Gamma}}]$
constructed from the data $\\{y_{i},\mathbf{X}_{i}\\}_{i\in[n]}$.

###  4.2 Robust matrix completion

We follow the same distribution assumption of [53, 54] for the robust matrix
completion problem. For simplicity we only consider subgaussian noise. It is
stated as follows.

######  Assumption 4.

Assume the random pair $(\mathbf{X},\xi)\in\mathds{R}^{p}\times\mathbb{R}$ is
such that

  * (i)

$\mathbf{X}$ has a discrete distribution
$\Pi=\\{\pi_{k,\ell}\\}_{(k,\ell)\in[d_{1}]\times[d_{2}]}$ with support on
$\mathcal{X}$ defined in (14). Let $d:=d_{1}+d_{2}$ and $m=d_{1}\wedge d_{2}$.
We also define

(49) $\displaystyle R_{k}:=\sum_{\ell=1}^{d_{2}}\pi_{k,\ell},\quad\quad
C_{\ell}:=\sum_{k=1}^{d_{1}}\pi_{k,\ell},\quad\quad
L:=m\cdot\max_{k\in[d_{1}],\ell\in[d_{2}]}\\{R_{k},C_{\ell}\\}.$

  * (ii)

$\sigma:=|\xi|_{\psi_{2}}\in(1,\infty)$ and
$\sigma_{\xi}^{2}:=\mathbb{E}[\xi^{2}]\geq 1$.

######  Theorem 4.4.

In the robust matrix completion problem of Section 2.3, suppose
$\mathbf{B}^{*}$ has rank $r$. Grant Assumptions 1 and 4 such that
$\epsilon<0.5$. Let $\delta\in(0,1)$. In estimator (20) with sequence
$\omega_{i}=\log(An/i)$ for some $A\geq 2$, take $\mathcal{R}$ to be the
nuclear norm, $\mathsf{a}>0$ such that
$\|\mathbf{B}^{*}\|_{\infty}\leq\mathsf{a}$ and tuning parameters
$\tau\asymp\frac{\sigma\vee\mathsf{a}}{\sqrt{n}}$ and

(50)
$\displaystyle\lambda\asymp\left[(\sigma_{\xi}\vee\mathsf{a})\sqrt{\frac{Lp}{mn}}\sqrt{(\log(4/\delta)+\log
d)}\right]\bigvee\left[(\sigma\vee\mathsf{a})\log^{1/2}\left(\frac{\sigma
m}{\sigma_{\xi}}\right)\frac{\sqrt{p}}{n}\cdot(\log(4/\delta)+\log d)\right].$

Then there are absolute constants $C,c>0$ and constant $\mu(\mathbf{B}^{*})>0$
such that the following property holds. Given any $\delta\in(0,1)$, if one has

(51) $\displaystyle n$ $\displaystyle\geq C\left[(Lp/m)\log
d\right]\bigvee\left[\sqrt{p}(\log m)^{1/2}(\log d)\right],$ (52)
$\displaystyle\delta$ $\displaystyle\geq\exp\left(-cn\right),$

then with probability at least $1-\delta$,

(53)
$\displaystyle\sqrt{\|\hat{\mathbf{B}}-\mathbf{B}^{*}\|_{\Pi}^{2}+\|\hat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}\|_{2}^{2}}$
$\displaystyle\lesssim(\mathsf{a}\vee\sigma_{\xi})\mu(\mathbf{B}^{*})\sqrt{\frac{Lpr}{mn}}\sqrt{(\log(4/\delta)+\log
d)}$ (54) $\displaystyle+(\mathsf{a}\vee\sigma)\log^{1/2}\left(\frac{\sigma
m}{\sigma_{\xi}}\right)\mu(\mathbf{B}^{*})\frac{\sqrt{pr}}{n}\cdot(\log(4/\delta)+\log
d)$ (55)
$\displaystyle+(\mathsf{a}\vee\sigma)\frac{1+\sqrt{\log(2/\delta)}}{\sqrt{n}}$
(56) $\displaystyle+(\mathsf{a}\vee\sigma)\sqrt{\epsilon\log(1/\epsilon)}.$

Let us make a few comments about Theorem 4.4. A similar argument by [54] shows
that the rate of Theorem 4.4 is optimal up to log factors over the class
$\bar{\mathcal{A}}(r,o,\mathsf{a})$ defined in (26). If $\Pi$ is the uniform
distribution then $L=1$ and $\mu(\mathbf{B}^{*})=1$. The above rate is also
meaningful over a large class of non-uniform sampling distributions $\Pi$
having $L$ and $\mu(\mathbf{B}^{*})$ of reasonable magnitudes (see Remark 3 in
the following). In practice, one may just know an upper bound on $L$ rather
than its exact value.222As usual, the corresponding rate may scale with a
larger constant. Finally, the estimator and correspondent rate in [54] depend
on an upper bound on the corruption sup-norm
$\|\boldsymbol{\Gamma}^{*}\|_{\infty}$. In many applications, it is reasonable
to expect that only the low-rank matrix $\mathbf{B}^{*}$ is of interest. In
that specific setting, Theorem 4.4 reveals that only an upper bound on
$\|\mathbf{B}^{*}\|_{\infty}$ is of relevance. In particular, the corruption
level is irrelevant: it does not affect the rate nor it is necessary for
tuning the estimator. We confirm this theoretical finding in our numerical
experiments.

######  Remark 3 (Restricted eigenvalue constants).

In Theorem 4.4,
$\mu(\mathbf{B}^{*})=\sup_{\mathbf{V}\in\mathscr{C}^{\prime}}\nicefrac{{\|\mathbf{V}\|_{F}}}{{\sqrt{p}\|\mathbf{V}\|_{\Pi}}}$
for a specific cone $\mathscr{C}^{\prime}$. If $\Pi$ is the uniform
distribution then $\mu(\mathbf{B}^{*})=1$. In general, $\mu(\mathbf{B}^{*})$
is the condition number measuring how far $\Pi$ is from the uniform
distribution.

##  5 Simulation results

We report simulation results in R with synthetic data demonstrating excellent
agreement between our theoretical predictions (Theorems 4.1-4.4) and the
behavior in practice. The code can be accessed in
https://github.com/philipthomp/Outlier-robust-regression. For robust sparse
linear regression and trace-regression problems, we simulate a design with
i.i.d. $\mathcal{N}(0,1)$ entries and $\mathcal{N}(0,1)$ noise. For noisy
robust matrix completion, the sampling design is uniformly distributed over
$[d_{1}]\times[d_{2}]$ and the noise is $\mathcal{N}(0,1)$. For numerical
reasons, we solve (20) with the scaled design $\sqrt{p}\mathbf{X}_{i}$. We
solve (6), (20) and (13) implementing a batch version of a proximal gradient
method on the separable variables $[\mathbf{B};\boldsymbol{\theta}]$ using a
stepsize equal to $0.25$. The proximal map of the Slope or $\ell_{1}$ norms
are computed with the function prox_sorted_L1() of the glmSLOPE package [11].
The ($\ell_{\infty}$-constrained) proximal map of the nuclear norm is computed
via ($\ell_{\infty}$-constrained) soft-thresholding of the singular value
decomposition.

_Robust sparse linear regression_. We simulate model (2) with $p=100$ and
$n=1000$. This model is simulated for 3 different sparsity indexes
$s=15,25,35$ over a grid of corruption fraction $\epsilon=\frac{o}{n}$.
Respectively, $\boldsymbol{b}^{*}$ and $\boldsymbol{\theta}^{*}$ are set with
the first $s$ and $o$ entries equal to $10$ and zero otherwise. For each $s$
and $\epsilon$, we solve (6) taking $A=10$ and $\mathcal{R}$ to be the Slope
norm with $\bar{A}=10$. For each $s$, the plot of the square root
$\sqrt{\texttt{MSE}}$ of the mean squared error (MSE) as a function of
$\epsilon$ (averaged over 100 repetitions) is shown in Figure 1(a). As
predicted by Theorem 4.1, the plot fits fairly well a linear growth with
$\epsilon$. Taking $\mathcal{R}$ to be the Slope norm, we also compare Huber’s
regression (H) with the “Sorted Huber’s loss” (S) in Definition 2.1 for
$s=25$. Fixing all model parameters, we increase the nonzero entries of
$\boldsymbol{b}^{*}$ and $\boldsymbol{\theta}^{*}$ to $50$. In Figure 1(b), we
show the correspondent plots of the square root of the MSE as a function of
$\epsilon$ (averaged over 100 repetitions). We see that “S” clearly
outperforms “H”. The first 25 entries estimated by “H” and “S” fluctuated
around $40$ and $48$ respectively.

(a) Different sparsity. (b) Different losses.

Figure 1: Robust sparse linear regression: $\sqrt{\texttt{MSE}}$ versus
$\epsilon$.

_Robust low-rank trace-regression_. We simulate model (2) with
$d_{1}=d_{2}=10$ and $n=1000$. This model is simulated for 3 different rank
values $r=1,2,3$ over a grid of corruption fraction $\epsilon=\frac{o}{n}$.
The low-rank parameter is generated by randomly choosing the spaces of left
and right singular vectors with all nonzero singular values equal to $10$. The
corruption vector $\boldsymbol{\theta}^{*}$ is set to have the first $o$
entries equal to $10$ and zero otherwise. We solve (6) taking $\mathcal{R}$ to
be the nuclear norm and $A=10$. For each $r$, the plot of
$\sqrt{\texttt{MSE}}$ as a function of $\epsilon$ (averaged over 50
repetitions) is given in Figure 2(a). The plot fits fairly well a linear
growth with $\epsilon$ as predicted by Theorem 4.2.

(a) Robust trace regression. (b) Robust matrix completion.

Figure 2: Robust trace regression & matrix completion: error versus
$\epsilon$.

_Robust matrix completion_. We simulate model (2) with $d_{1}=d_{2}=10$ and
$n=80$. This model is simulated for 3 different rank values $r=1,5,10$ over a
grid of corruption fraction $\epsilon=\frac{o}{n}$. The low-rank parameter is
generated by randomly choosing the spaces of left and right singular vectors
such that $\|\mathbf{B}^{*}\|_{\infty}\leq 1$. The corruption vector
$\boldsymbol{\theta}^{*}$ is set to have the first $o$ entries equal to $10$
and zero otherwise. We solve (20) taking $\mathcal{R}$ to be the nuclear norm
and $A=10$. For each $r$, the plot of MSE as a function of $\epsilon$
(averaged over 100 repetitions) is given in Figure 2(b). The plot fits fairly
well a linear growth with $\epsilon$ as predicted by Theorem 4.4.333We have
noted, however, that the log factor $\log(C/\epsilon)$ in the MSE rate of the
form $\epsilon\mapsto\epsilon\log(C/\epsilon)$, as predicted in Theorem 4.4,
is more present around $\epsilon=0$. We also study the variability of the
corruption level $\|\boldsymbol{\theta}^{*}\|_{\infty}$. Fixing the previous
model parameters and taking $r=3$, we show in the highlighted table
$\sqrt{\texttt{MSE}}$ versus $\epsilon\in[0.05,0.35]$ (averaged over 100
repetitions) for $\|\boldsymbol{\theta}^{*}\|_{\infty}=10,100,1000$. For a
precise comparison, the same data set is used for the three values of
$\|\boldsymbol{\theta}^{*}\|_{\infty}$ in each repetition. As predicted by
Theorem 4.4, the resulted error is fairly adaptive and robust with respect to
the corruption level $\|\boldsymbol{\theta}^{*}\|_{\infty}$.

| 0.05 | 0.1 | 0.15 | 0.2 | 0.25 | 0.3 | 0.35
---|---|---|---|---|---|---|---
10 | 1.895272 | 1.967005 | 2.000942 | 2.032264 | 2.056413 | 2.074631 | 2.075563
100 | 1.895273 | 1.966962 | 2.000966 | 2.032263 | 2.056416 | 2.074635 | 2.075567
1000 | 1.895276 | 1.967034 | 2.000997 | 2.032263 | 2.056426 | 2.074644 | 2.075579

_Trace-regression with matrix decomposition_. We simulate model (7) with
$d_{1}=d_{2}=10$ and $n=1000$. The low-rank parameter is generated by randomly
choosing the spaces of left and right singular vectors such that
$\|\mathbf{B}^{*}\|_{\infty}\leq\frac{\mathsf{a}^{*}}{\sqrt{n}}$ with
$\mathsf{a}^{*}=1$. The sparse parameter is simulated with the non-zero
entries of value 10 chosen uniformly at random. We solve (20) in two settings.
First, this model is simulated for 2 different sparsity values $s=5,80$ over a
grid of ranks $r$. For each $s$, the plot of MSE versus $r$ (averaged over 20
repetitions) is given in Figure 3(a). Secondly, we simulate for rank $r=5$
over a grid of sparsity levels $s$. The plot of the MSE versus $s$ (averaged
over 20 repetitions) is given in Figure 3(b). Both plots fit fairly well a
linear growth as predicted by Theorem 4.3.

(a) Fixed sparsity. (b) Fixed rank.

Figure 3: Trace regression with matrix decomposition: plot of MSE.

##  6 Discussion

We finalize with some additional discussions complementing our contributions
already highlighted in Section 3. The $\ell_{1}$ norm treats each variable in
the same manner. Alternatively, the Slope norm adjusts the weight according to
the variable’s magnitude. The papers [11, 7] propose and study the Slope norm
as a finer _regularization_ norm for sparse linear regression. Indeed, [7]
shows that sparse linear regression with Slope regularization achieves the
_exact_ optimal rate $\sqrt{s\log(ep/s)/n}$ adaptively to $s$, a property not
satisfied by the $\ell_{1}$-norm. In this work, we exploit the Slope norm for
a related but considerably different purpose: to construct a finer _robust
loss_ against label contamination (see Definition 2.1). Differently than
classical Huber regression, the “Sorted Huber’s loss” in Definition 2.1
assign, for each $i$th data point, higher penalization to higher outlier
levels. One message of the present work is that $M$-estimation with the Sorted
Huber’s loss seem to have theoretical improvements compared to Huber
regression: it achieves the _subgaussian_ optimal rate in response adversarial
robust regression (up to a log factor in $1/\epsilon$) with a breakdown point
$\epsilon\leq c$ for a constant $c\in(0,1)$, adaptively to
$(\epsilon,d_{\mbox{\tiny eff}},\delta)$, where $d_{\mbox{\tiny eff}}$ denotes
the “effective” dimension and $\delta$ is the failure probability. This
property holds despite the parsimony structure of the parameter (sparsity or
low-rankness). We also show that these rates are valid _uniformly_ on the
failure probability $\delta$, i.e., the tuning of our estimators do not depend
on $\delta$. Although the details are not presented explicitly, it is clear
that, in _low-dimensions_ ($n\geq d_{1}d_{2}$), subgaussian optimality is also
achieved in least-squares regression with the Sorted Huber’s loss. Our
simulations also shown in practice that Sorted Huber regression can outperform
classical Huber regression (Section 5, Figure 1(b)).

The Huber loss is a seminal and fundamental robust loss which has been
considered in numerous works under various different perspectives [72, 78, 4,
38, 6]. One fundamental open question would be to further compare Huber
regression with Sorted Huber regression proposed in Definition 2.1 with
respect to other statistical metrics considered in the literature. This would
be interesting on the theoretical level and with further numerical study. One
example would be to give a tight comparison between the breakdown points of
both losses, at least in the Gaussian set-up.

To the best of our knowledge, there seems to be no prior estimation theory for
the trace-regression problem with matrix decomposition (Theorem 4.3). It is
interesting to remark that our analysis of this problem crucially makes use of
a concentration inequality for the Product Process. This seems to be a new
application in the context of matrix decomposition theory [14, 2]. In this
paper we are mainly concerned with the noisy setting. In parallel with the
established theory of signal recovery in Compressed Sensing, it would be
interesting to investigate further when _exact_ recovery is possible in this
context. This probably would require different set of assumptions such as the
_incoherence_ condition [15]. Other analytic tools from nonconvex optimization
[20] and the corresponding corrupted model are also worthy of investigation.

## References

  * Adcock et al. [2018] Adcock, B., A. Bao, J. Jakeman, and A. Narayan (2018).  Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations.  SIAM/ASA Journal on Uncertainty Quantification 6(4), 1424–1453.
  * Agarwal et al. [2012] Agarwal, A., S. Negahban, and M. Wainwright (2012).  Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions.  Ann. Statist. 40(2), 1171–1197.
  * Balakrishnan et al. [2017] Balakrishnan, S., S. S. Du, J. Li, and A. Singh (2017, 07–10 Jul).  Computationally efficient robust sparse estimation in high dimensions.  In S. Kale and O. Shamir (Eds.), Proceedings of the 2017 Conference on Learning Theory, Volume 65 of Proceedings of Machine Learning Research, Amsterdam, Netherlands, pp. 169–212. PMLR.
  * Bean et al. [2013] Bean, D., P. J. Bickel, N. E. Karoui, and B. Yu (2013).  Optimal m-estimation in high-dimensional regression.  PNAS 110(36), 14563–14568.
  * Bednorz [2014] Bednorz, W. (2014).  Concentration via chaining method and its applications.  arxiv 1405.0676.
  * Bellec [2020] Bellec, P. (2020).  Out-of-sample error estimate for robust m-estimators with convex penalty.  arxiv.org/abs/2008.11840.
  * Bellec et al. [2018] Bellec, P. C., G. Lecué, and A. B. Tsybakov (2018, 12).  Slope meets lasso: Improved oracle bounds and optimality.  Ann. Statist. 46(6B), 3603–3642.
  * Bhatia et al. [2017] Bhatia, K., P. Jain, P. Kamalaruban, and P. Kar (2017).  Consistent robust regression.  In Advances in Neural Information Processing Systems, Volume 30, pp. 2110–2119. Curran Associates, Inc.
  * Bhatia et al. [2015] Bhatia, K., P. Jain, and P. Kar (2015).  Robust regression via hard thresholding.  In Advances in Neural Information Processing Systems, Volume 28, pp. 721–729. Curran Associates, Inc.
  * Bickel et al. [2009] Bickel, P. J., Y. Ritov, and A. B. Tsybakov (2009).  Simultaneous analysis of Lasso and Dantzig selector.  Ann. Statist. 37(4), 1705–1732.
  * Bogdan et al. [2015] Bogdan, M., E. van den Berg, C. Sabatti, W. Su, and E. J. Candès (2015, 09).  Slope—adaptive variable selection via convex optimization.  Ann. Appl. Stat. 9(3), 1103–1140.
  * Cai and Zhou [2016] Cai, T. T. and W.-X. Zhou (2016).  Matrix completion via max-norm constrained optimization.  Electron. J. Statist. 10(1), 1493–1525.
  * Candès and Randall [2008] Candès, E. and P. A. Randall (2008).  Highly robust error correction by convex programming.  IEEE Trans. Inform. Theory 54(7), 2829–2840.
  * Candès et al. [2011] Candès, E. J., X. Li, Y. Ma, and J. Wright (2011, June).  Robust principal component analysis?  J. ACM 58(3).
  * Candès and Recht [2009] Candès, E. and B. Recht (2009).  Exact matrix completion via convex optimization.  Found. Comput. Math. 9(717).
  * Chandrasekaran et al. [2011] Chandrasekaran, V., S. Sanghavi, P. A. Parrilo, and A. S. Willsky (2011).  Rank-sparsity incoherence for matrix decomposition.  SIAM J. Optim. 21(2), 572–596.
  * Chen et al. [2016] Chen, M., C. Gao, and Z. Ren (2016).  A general decision theory for huber’s $\epsilon$-contamination model.  Electron. J. Statist. 10(2), 3752–3774.
  * Chen et al. [2018] Chen, M., C. Gao, and Z. Ren (2018, 10).  Robust covariance and scatter matrix estimation under huber’s contamination model.  Ann. Statist. 46(5), 1932–1960.
  * Chen et al. [2013] Chen, Y., C. Caramanis, and S. Mannor (2013, 17–19 Jun).  Robust sparse regression under adversarial corruption.  In S. Dasgupta and D. McAllester (Eds.), Proceedings of the 30th International Conference on Machine Learning, Volume 28 of Proceedings of Machine Learning Research, Atlanta, Georgia, USA, pp. 774–782. PMLR.
  * Chen et al. [2020] Chen, Y., J. Fan, C. Ma, and Y. Yan (2020).  Bridging convex and nonconvex optimization in robust pca: Noise, outliers, and missing data.  arxiv 2001.05484.
  * Chen et al. [2013] Chen, Y., A. Jalali, S. Sanghavi, and C. Caramanis (2013).  Low-rank matrix recovery from errors and erasures.  IEEE Transactions on Information Theory 59(7), 4324–4337.
  * Chen et al. [2011] Chen, Y., H. Xu, C. Caramanis, and S. Sanghavi (2011, June).  Robust matrix completion and corrupted columns.  In L. Getoor and T. Scheffer (Eds.), Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML ’11, New York, NY, USA, pp. 873–880. ACM.
  * Cheng et al. [2019] Cheng, Y., I. Diakonikolas, and R. Ge (2019).  High-dimensional robust mean estimation in nearly-linear time.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, USA, pp. 2755–2771. Society for Industrial and Applied Mathematics.
  * Cherapanamjeri et al. [2020] Cherapanamjeri, Y., E. Aras, N. Tripuraneni, M. Jordan, N. Flammarion, and P. Bartlett (2020).  Optimal robust linear regression in nearly linear time.  arxiv 2007.08137.
  * Chinot [2020] Chinot, G. (2020).  Erm and rerm are optimal estimators for regression problems when malicious outliers corrupt the labels.  Electron. J. Statist. 14(2), 3563–3605.
  * Dalalyan and Chen [2012] Dalalyan, A. and Y. Chen (2012).  Fused sparsity and robust estimation for linear models with unknown variance.  In Advances in Neural Information Processing Systems, Volume 25, pp. 1259–1267. Curran Associates, Inc.
  * Dalalyan and Keriven [2009] Dalalyan, A. and R. Keriven (2009).  L_1-penalized robust estimation for a class of inverse problems arising in multiview geometry.  In Advances in Neural Information Processing Systems, Volume 22, pp. 441–449. Curran Associates, Inc.
  * Dalalyan and Minasyan [2020] Dalalyan, A. and A. Minasyan (2020).  All-in-one robust estimator of the gaussian mean.  arxiv 2002.01432.
  * Dalalyan and Thompson [2019] Dalalyan, A. and P. Thompson (2019).  Outlier-robust estimation of a sparse linear model using \$\ell_{1}$-penalized huber’s m-estimator.  In Advances in Neural Information Processing Systems, Volume 32, pp. 13188–13198. Curran Associates, Inc.
  * Depersin [2020] Depersin, J. (2020).  A spectral algorithm for robust regression with subgaussian rates.  arxiv 2007.06072.
  * Depersin and Lecué [2019] Depersin, J. and G. Lecué (2019).  Robust subgaussian estimation of a mean vector in nearly linear time.  arxiv 1906.03058.
  * Diakonikolas et al. [2019] Diakonikolas, I., G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart (2019).  Sever: A robust meta-algorithm for stochastic optimization.  In K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of the 36th International Conference on Machine Learning, Volume 97 of Proceedings of Machine Learning Research, Long Beach, California, USA, pp. 1596–1606. PMLR.
  * Diakonikolas et al. [2016] Diakonikolas, I., G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart (2016).  Robust estimators in high dimensions without the computational intractability.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 655–664.
  * Diakonikolas and Kane [2019] Diakonikolas, I. and D. Kane (2019).  Recent advances in algorithmic high-dimensional robust statistics.  arxiv 1911.05911.
  * Diakonikolas et al. [2019] Diakonikolas, I., W. Kong, and A. Stewart (2019).  Efficient algorithms and lower bounds for robust linear regression.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, USA, pp. 2745–2754. Society for Industrial and Applied Mathematics.
  * Dirksen [2015] Dirksen, S. (2015).  Tail bounds via generic chaining.  Electron. J. Probab. 20, 1–29.
  * Dong et al. [2019] Dong, Y., S. Hopkins, and J. Li (2019).  Quantum entropy scoring for fast robust mean estimation and improved outlier detection.  In Advances in Neural Information Processing Systems, Volume 32, pp. 6067–6077. Curran Associates, Inc.
  * Donoho and Montanari [2016] Donoho, D. and A. Montanari (2016).  High dimensional robust m-estimation: asymptotic variance via approximate message passing.  Probab. Theory Relat. Fields 166, 935––969.
  * Elsener and van de Geer [2018] Elsener, A. and S. van de Geer (2018).  Robust low-rank matrix estimation.  Annals of Statistics 46(6B), 3481–3509.
  * Fan et al. [2016] Fan, J., W. Wang, and Z. Zhu (2016).  A shrinkage principle for heavy-tailed data: High-dimensional robust low-rank matrix recovery.  arxiv 1603.08315.
  * Fazel [2002] Fazel, M. (2002).  Matrix rank minimization with applications.  PhD thesis, Stanford University.
  * Foygel and Mackey [2014] Foygel, R. and L. Mackey (2014).  Corrupted sensing: Novel guarantees for separating structured signals.  IEEE Transactions on Information Theory 60(2), 1223–1247.
  * Gaïffas and Klopp [2017] Gaïffas, S. and O. Klopp (2017).  High dimensional matrix estimation with unknown variance of the noise.  Statistica Sinica 27(1), 115–145.
  * Gaïffas and Lecué [2011] Gaïffas, S. and G. Lecué (2011).  Sharp oracle inequalities for high-dimensional matrix prediction.  IEEE Transactions on Information Theory 57(10), 6942–6957.
  * Gao [2020] Gao, C. (2020, 05).  Robust regression via mutivariate regression depth.  Bernoulli 26(2), 1139–1170.
  * Gao and Lafferty [2020] Gao, C. and J. Lafferty (2020).  Model repair: Robust recovery of over-parameterized statistical models.  arxiv 2005.09912.
  * Hampel et al. [2011] Hampel, F., E. Ronchetti, P. Rousseeuw, and W. Stahel (2011).  Robust statistics: the approach based on influence functions.  Wiley Series in Probability and Statistics. Wiley.
  * Hsu et al. [2011] Hsu, D., S. M. Kakade, and T. Zhang (2011).  Robust matrix decomposition with sparse corruptions.  IEEE Transactions on Information Theory 57, 7221–7234.
  * Huber [1964] Huber, P. J. (1964).  Robust estimation of a location parameter.  Ann. Math. Statist. 35(1), 73–101.
  * Huber and Ronchetti [2011] Huber, P. J. and E. M. Ronchetti (2011).  Robust statistics.  Wiley Series in Probability and Statistics. Wiley.
  * Karmalkar and Price [2018] Karmalkar, S. and E. Price (2018).  Compressed sensing with adversarial sparse noise via l1 regression.  arxiv 1809.08055.
  * Klopp [2011] Klopp, O. (2011).  Rank penalized estimators for high-dimensional matrices.  Electron. J. Statist. 5, 1161–1183.
  * Klopp [2014] Klopp, O. (2014, 02).  Noisy low-rank matrix completion with general sampling distribution.  Bernoulli 20(1), 282–303.
  * Klopp et al. [2017] Klopp, O., K. Lounici, and A. Tsybakov (2017).  Robust matrix completion.  Probab. Theory Relat. Fields 169(523–564).
  * Koltchinskii et al. [2011] Koltchinskii, V., K. Lounici, and A. B. Tsybakov (2011, 10).  Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion.  Ann. Statist. 39(5), 2302–2329.
  * Lai et al. [2016] Lai, K. A., A. B. Rao, and S. Vempala (2016).  Agnostic estimation of mean and covariance.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 665–674.
  * Laska et al. [2009] Laska, J. N., M. A. Davenport, and R. G. Baraniuk (2009).  Exact signal recovery from sparsely corrupted measurements through the pursuit of justice.  In 2009 Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, pp. 1556–1560.
  * Lee et al. [2012] Lee, Y., S. N. MacEachern, and Y. Jung (2012, 08).  Regularization of case-specific parameters for robustness and efficiency.  Statist. Sci. 27(3), 350–372.
  * Li [2013] Li, X. (2013).  Compressed sensing and matrix completion with constant proportion of corruptions.  Constr. Approx. 37, 73–99.
  * Loh and Wainwright [2012] Loh, P. and M. J. Wainwright (2012).  Corrupted and missing predictors: Minimax bounds for high-dimensional linear regression.  In 2012 IEEE International Symposium on Information Theory Proceedings, pp. 2601–2605.
  * Loh and Wainwright [2012] Loh, P.-L. and M. J. Wainwright (2012, 06).  High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity.  Ann. Statist. 40(3), 1637–1664.
  * Lugosi and Mendelson [2019] Lugosi, G. and S. Mendelson (2019).  Mean estimation and regression under heavy-tailed distributions - a survey.  Found. Comput. Math. 19, 1145–1190.
  * Maronna et al. [2006] Maronna, R. A., D. R. Martin, and V. J. Yohai (2006).  Robust Statistics: Theory and Methods.  Wiley Series in Probability and Statistics. Wiley.
  * McCoy and Tropp [2011] McCoy, M. and J. Tropp (2011).  Two proposals for robust pca using semidefinite programming.  Electronical Journal of Statistics 5(11), 1123 – 1160\.
  * Mendelson [2016] Mendelson, S. (2016).  Upper bounds on product and multiplier empirical processes.  Stochastic Processes and their Applications 126(12), 3652 – 3680.  In Memoriam: Evarist Giné.
  * Minsker [2015] Minsker, S. (2015, 11).  Geometric median and robust estimation in banach spaces.  Bernoulli 21(4), 2308–2335.
  * Mukhoty et al. [2019] Mukhoty, B., G. Gopakumar, P. Jain, and P. Kar (2019, 16–18 Apr).  Globally-convergent iteratively reweighted least squares for robust regression problems.  In K. Chaudhuri and M. Sugiyama (Eds.), Proceedings of Machine Learning Research, Volume 89 of Proceedings of Machine Learning Research, pp. 313–322. PMLR.
  * Negahban and Wainwright [2011] Negahban, S. and M. J. Wainwright (2011, 04).  Estimation of (near) low-rank matrices with noise and high-dimensional scaling.  Ann. Statist. 39(2), 1069–1097.
  * Negahban and Wainwright [2012] Negahban, S. and M. J. Wainwright (2012).  Restricted strong convexity and weighted matrix completion: Optimal bounds with noise.  Journal of Machine Learning Research 13(53), 1665–1697.
  * Negahban et al. [2012] Negahban, S. N., P. Ravikumar, M. J. Wainwright, and B. Yu (2012, 11).  A unified framework for high-dimensional analysis of $m$-estimators with decomposable regularizers.  Statist. Sci. 27(4), 538–557.
  * Nguyen and Tran [2013] Nguyen, N. H. and T. D. Tran (2013).  Exact recoverability from dense corrupted observations via $\ell_{1}$-minimization.  IEEE Transactions on Information Theory 59(4), 2017–2035.
  * Nguyen and Tran [2013] Nguyen, N. H. and T. D. Tran (2013).  Robust lasso with missing and grossly corrupted observations.  IEEE Trans. Inform. Theory 59(4), 2036–2058.
  * Pensia et al. [2020] Pensia, A., V. Jog, and P.-L. Loh (2020).  Robust regression with covariate filtering: Heavy tails and adversarial contamination.  arxiv 2009.12976.
  * Pesme and Flammarion [2020] Pesme, S. and N. Flammarion (2020).  Online robust regression via sgd on the l1 loss.  In Advances in Neural Information Processing Systems, Volume 33, pp. 2540–2552. Curran Associates, Inc.
  * Prasad et al. [2020] Prasad, A., A. S. Suggala, S. Balakrishnan, and P. Ravikumar (2020).  Robust estimation via robust gradient estimation.  Journal of the Royal Statistical Society: Series B (Statistical Methodology) 82(3), 601–627.
  * Rohde and Tsybakov [2011] Rohde, A. and A. B. Tsybakov (2011, 04).  Estimation of high-dimensional low-rank matrices.  Ann. Statist. 39(2), 887–930.
  * Sardy et al. [2001] Sardy, S., P. Tseng, and A. Bruce (2001, Jun).  Robust wavelet denoising.  IEEE Transactions on Signal Processing 49(6), 1146–1152.
  * She and Owen [2011] She, Y. and A. B. Owen (2011).  Outlier detection using nonconvex penalized regression.  Journal of the American Statistical Association 106(494), 626–639.
  * Srebro [2004] Srebro, N. (2004).  Learning with matrix factorizations.  PhD Thesis, MIT.
  * Suggala et al. [2019] Suggala, A. S., K. Bhatia, P. Ravikumar, and P. Jain (2019, 25–28 Jun).  Adaptive hard thresholding for near-optimal consistent robust regression.  In A. Beygelzimer and D. Hsu (Eds.), Proceedings of the Thirty-Second Conference on Learning Theory, Volume 99 of Proceedings of Machine Learning Research, Phoenix, USA, pp. 2892–2897. PMLR.
  * Talagrand [2014] Talagrand, M. (2014).  Upper and Lower Bounds for Stochastic Processes.  A series of modern surveys in mathematics. Springer, Berlin, Heidelberg.
  * Tibshirani [1996] Tibshirani, R. (1996).  Regression shrinkage and selection via the Lasso.  Journal of the Royal Statistical Society. Series B 58(1), 267–288.
  * Tsakonas et al. [2014] Tsakonas, E., J. Jaldén, N. D. Sidiropoulos, and B. Ottersten (2014).  Convergence of the huber regression m-estimate in the presence of dense outliers.  IEEE Signal Processing Letters 21(10), 1211–1214.
  * van de Geer and Bühlmann [2009] van de Geer, S. A. and P. Bühlmann (2009).  On the conditions used to prove oracle results for the lasso.  Electron. J. Statist. 3, 1360–1392.
  * Wang et al. [2007] Wang, H., G. Li, and G. Jiang (2007).  Robust regression shrinkage and consistent variable selection through the lad-lasso.  Journal of Business & Economic Statistics 25(3), 347–355.
  * Wright et al. [2009] Wright, J., A. Ganesh, S. Rao, Y. Peng, and Y. Ma (2009).  Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization.  In Advances in Neural Information Processing Systems, Volume 22. Curran Associates, Inc.
  * Wright and Ma [2009] Wright, J. and Y. Ma (2009).  Dense error correction via l1-minimization.  In 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3033–3036.
  * Xu et al. [2010] Xu, H., C. Caramanis, and S. Sanghavi (2010).  Robust pca via outlier pursuit.  In Advances in Neural Information Processing Systems, Volume 23, pp. 2496–2504. Curran Associates, Inc.

Web-based supporting materials for “Outlier-robust sparse/low-rank least-
squares regression and robust matrix completion”

by Philip Thompson

##  7 Basic notation

Throughout the paper, given $\ell\in\mathbb{N}$, $A^{(\ell)}:=A/\sqrt{\ell}$
whenever $A$ is a number, vector or function. Regarding the tuning parameters
$(\lambda,\tau)$, we will sometimes use the definition $\gamma:=\lambda/\tau$.
With respect to the Slope norm in $\mathbb{R}^{n}$ with sequence
$\boldsymbol{\omega}=(\omega_{i})_{i\in[n]}$ given by $\omega_{i}=\log(An/i)$
for some $A\geq 2$, we set $\Omega:=\\{\sum_{i=1}^{o}\omega_{i}^{2}\\}^{1/2}$.
Note that from the Stirling formula, $\Omega\asymp o\log(n/o)$ [7]. Throughout
the paper,
$\boldsymbol{\Delta}^{\hat{\mathbf{B}}}:=\hat{\mathbf{B}}-\mathbf{B}^{*}$,
$\boldsymbol{\Delta}^{\hat{\boldsymbol{\Gamma}}}:=\hat{\boldsymbol{\Gamma}}-\boldsymbol{\Gamma}^{*}$
and
$\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}:=\hat{\boldsymbol{\theta}}-\boldsymbol{\theta}^{*}$.
It will be useful to define the map
$\mathfrak{M}(\mathbf{B};\boldsymbol{\theta}):=\mathfrak{X}(\mathbf{B})+\sqrt{n}\boldsymbol{\theta}.$

Letting $\Pi$ be the distribution of $\mathbf{X}$, we define the bilinear form

$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle_{\Pi}:=\mathbb{E}[\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X},\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle],$

and, as before, the $L^{2}(\Pi)$-pseudo-distance

$\|\mathbf{V}\|_{\Pi}:=\\{\mathbb{E}[\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{X}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle_{\Pi}^{2}]\\}^{1/2}.$

We denote by $\mathfrak{S}$ the covariance operator of $\mathbf{X}$, that is,
the self-adjoint linear operator on $\mathds{R}^{p}$ satisfying
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathfrak{S}(\mathbf{V}),\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle_{\Pi}$
for all $\mathbf{V},\mathbf{W}$. It will be useful to define the pseudo-norms
$\|[\mathbf{V};\boldsymbol{u}]\|_{\Pi}:=\\{\|\mathbf{V}\|_{\Pi}^{2}+\|\boldsymbol{u}\|_{2}^{2}\\}^{1/2}$
on $\mathds{R}^{p}\times\mathbb{R}^{n}$ and
$\|[\mathbf{V};\mathbf{W}]\|_{\Pi}:=\\{\|\mathbf{V}\|_{\Pi}^{2}+\|\mathbf{W}\|_{\Pi}^{2}\\}^{1/2}$
on $(\mathds{R}^{p})^{2}$.

We define the unit balls
$\mathbb{B}_{\Pi}:=\\{\mathbf{V}\in\mathds{R}^{p}:\|\mathbf{V}\|_{\Pi}\leq
1\\},$ $\mathbb{B}_{F}:=\\{\mathbf{V}\in\mathds{R}^{p}:\|\mathbf{V}\|_{F}\leq
1\\},$ and
$\mathbb{B}_{\ell}^{k}:=\\{\boldsymbol{v}\in\mathbb{R}^{k}:\|\boldsymbol{v}\|_{\ell}\leq
1\\}.$ With a slight abuse of notation, we denote by
$\mathbb{B}_{\mathcal{R}}:=\\{\mathbf{V}\in\mathds{R}^{p}:\mathcal{R}(\mathbf{V})\leq
1\\}$ and
$\mathbb{B}_{\mathcal{Q}}:=\\{\boldsymbol{u}\in\mathbb{R}^{n}:\mathcal{Q}(\boldsymbol{u})\leq
1\\}$ the correspondent unit balls for norms $\mathcal{R}$ on $\mathds{R}^{p}$
and $\mathcal{Q}$ on $\mathbb{R}^{n}$. All the corresponding unit spheres will
take the symbol $\mathbb{S}$.

Finally, the _Gaussian width_ of a compact set
$\mathcal{B}\subset\mathbb{R}^{k\times\ell}$ is the quantity
$\mathscr{G}(\mathcal{B}):=\mathbb{E}[\sup_{\mathbf{V}\in\mathcal{B}}\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\boldsymbol{\Xi}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle],$
where $\boldsymbol{\Xi}\in\mathbb{R}^{k\times\ell}$ is random matrix with iid
$\mathcal{N}(0,1)$ entries.

##  8 Proofs of Theorems 4.1 and 4.2

Recall estimator (6).

Throughout Sections 8.1 and 8.2, $\|\cdot\|_{\Pi}$ can be regarded as a
generic pseudo-norm. Moreover, $\\{(\mathbf{X}_{i},\xi_{i})\\}_{i\in[n]}$
satisfying (2) can be regarded as deterministic with
$\boldsymbol{\xi}=(\xi_{i})_{i\in[n]}$. As before, $\mathfrak{X}$ and
$\mathfrak{M}$ are the design and augmented design operators associated to the
sequence $\\{\mathbf{X}_{i}\\}_{i\in[n]}$. Probabilistic assumptions are used
only in Sections 8.3, 8.4 and 8.5.

###  8.1 Design properties, cones and restricted eigenvalues

Next we present some structural properties for the design operator
$\mathfrak{X}:\mathds{R}^{p}\rightarrow\mathbb{R}^{n}$.

######  Definition 8.1 (Transfer principles).

Let $\mathcal{R}$ be a norm over $\mathds{R}^{p}$, $\mathcal{Q}$ be a norm
over $\mathbb{R}^{n}$ and subsets $\mathbb{C}\subset\mathds{R}^{p}$ and
$\mathbb{C}^{\prime}\subset\mathds{R}^{p}\times\mathbb{R}^{n}$. (i) Given
positive numbers $\mathsf{a}_{1}$ and $\mathsf{a}_{2}$, we say that
$\mathfrak{X}$ satisfies
$\operatorname*{TP}_{\mathcal{R}}(\mathsf{a}_{1};\mathsf{a}_{2})$ on
$\mathbb{C}$ if (57)
$\displaystyle\forall\mathbf{V}\in\mathbb{C},\quad\big{\|}\mathfrak{X}^{(n)}(\mathbf{V})\big{\|}_{2}\geq\mathsf{a}_{1}\|\mathbf{V}\|_{\Pi}-\mathsf{a}_{2}\mathcal{R}(\mathbf{V}).$
(ii) Given positive numbers $\mathsf{b}_{1}$, $\mathsf{b}_{2}$ and
$\mathsf{b}_{3}$, we say that $\mathfrak{X}$ satisfies
$\operatorname*{IP}_{\mathcal{R},\mathcal{Q}}(\mathsf{b}_{1};\mathsf{b}_{2};\mathsf{b}_{3})$
if (58)
$\displaystyle\forall[\mathbf{V};\boldsymbol{u}]\in\mathds{R}^{p},\quad|\langle\boldsymbol{u},\mathfrak{X}^{(n)}(\mathbf{V})\rangle|\leq\mathsf{b}_{1}\left\|\mathbf{V}\right\|_{\Pi}\|\boldsymbol{u}\|_{2}+\mathsf{b}_{2}\mathcal{R}(\mathbf{V})\|\boldsymbol{u}\|_{2}+\mathsf{b}_{3}\left\|\mathbf{V}\right\|_{\Pi}\mathcal{Q}(\boldsymbol{u}).$
(iii) Given positive numbers $\mathsf{c}_{1}$, $\mathsf{c}_{2}$ and
$\mathsf{c}_{3}$, we say that $\mathfrak{X}$ satisfies
$\operatorname*{ATP}_{\mathcal{R},\mathcal{Q}}(\mathsf{c}_{1};\mathsf{c}_{2};\mathsf{c}_{3})$
on $\mathbb{C}^{\prime}$ if (59)
$\displaystyle\forall[\mathbf{V};\boldsymbol{u}]\in\mathbb{C}^{\prime},\quad\|\mathfrak{X}^{(n)}(\mathbf{V})+\boldsymbol{u}\|_{2}\geq\mathsf{c}_{1}\|[\mathbf{V};\boldsymbol{u}]\|_{\Pi}-\mathsf{c}_{2}\mathcal{R}(\mathbf{V})-\mathsf{c}_{3}\mathcal{Q}(\boldsymbol{u}).$
(iv) Given positive numbers $\mathsf{f}_{1}$, $\mathsf{f}_{2}$ and
$\mathsf{f}_{3}$, we will say that $(\mathfrak{X},\boldsymbol{\xi})$ satisfies
$\operatorname*{MP}_{\mathcal{R},\mathcal{Q}}(\mathsf{f}_{1};\mathsf{f}_{2};\mathsf{f}_{3})$
if (60)
$\displaystyle\forall[\mathbf{V};\boldsymbol{u}]\in\mathds{R}^{p},\quad|\langle\boldsymbol{\xi}^{(n)},\mathfrak{X}^{(n)}(\mathbf{V})+\boldsymbol{u}\rangle|\leq\mathsf{f}_{1}\|[\mathbf{V};\boldsymbol{u}]\|_{\Pi}+\mathsf{f}_{2}\mathcal{R}(\mathbf{V})+\mathsf{f}_{3}\mathcal{Q}(\boldsymbol{u}).$
If either $\mathbb{C}=\mathds{R}^{p}$ or
$\mathbb{C}^{\prime}=\mathds{R}^{p}\times\mathbb{R}^{n}$, we omit the
reference to the set where the above properties hold.

$\operatorname*{TP}$ is essentially “restricted strong convexity” [61], a well
known fundamental property in high-dimensional estimation. Indeed,
$\operatorname*{TP}_{\mathcal{R}}(\mathsf{a}_{1};0)$ on $\mathbb{C}$ is strong
convexity of $\mathfrak{X}^{(n)}$ on $\mathbb{C}$ with respect to the pseudo-
norm $\|\cdot\|_{\Pi}$.444To be precise, $\mathsf{a}_{1}$ is an absolute
constant for general classes of designs. The usual notion of restricted
eigenvalue, as e.g. in [10, 7], is with respect to the Frobenius norm. In that
case, the eigenvalue constant represents a “condition number”. In this sense,
it is more precise to say that $\operatorname*{TP}$ is a relaxation of
Bernstein’s condition. $\operatorname*{MP}(\mathsf{f}_{1};\mathsf{f}_{2};0)$
implies a bound on the “multiplier process”
$\mathbf{V}\mapsto\frac{1}{n}\sum_{i\in[n]}\boldsymbol{\xi}_{i}\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle$,
also an essential property used in high-dimensional estimation. In this work,
we give improved bounds on the MP property regarding the confidence level.

######  Remark 4.

We make use of the term “transfer principle” or “reduction principle” making
homage to the terms coined in [8, 6, 7].

The “augmented” notions of $\operatorname*{IP}$, $\operatorname*{ATP}$ and
$\operatorname*{MP}$ will be useful for robust linear regression. From the
next deterministic lemma, $\operatorname*{ATP}$ is a consequence of
$\operatorname*{TP}$ and $\operatorname*{IP}$. We will show in Section 8.3
that $\operatorname*{TP}$, $\operatorname*{IP}$ and $\operatorname*{MP}$ are
satisfied by subgaussian designs with high probability.

######  Lemma 8.2
($\operatorname*{TP}+\operatorname*{IP}\Rightarrow\operatorname*{ATP}$, Lemma
7 in [29]).

Let $\mathcal{R}$ be a norm over $\mathds{R}^{p}$ and $\mathcal{Q}$ a norm
over $\mathbb{R}^{n}$ with unit ball $\mathbb{B}_{\mathcal{Q}}^{n}$. Suppose
$\mathfrak{X}:\mathds{R}^{p}\rightarrow\mathbb{R}^{n}$ satisfies
$\operatorname*{TP}_{\mathcal{R}}(\mathsf{a}_{1};\mathsf{a}_{2})$ and
$\operatorname*{IP}_{\mathcal{R},\mathcal{Q}}(\mathsf{b}_{1};\mathsf{b}_{2};\mathsf{b}_{3})$
for some positive numbers $\mathsf{a}_{1}$, $\mathsf{a}_{2}$,
$\mathsf{b}_{1}$, $\mathsf{b}_{2}$ and $\mathsf{b}_{3}$. Then, for any
$\alpha>0$, $\mathfrak{X}$ satisfies the
$\operatorname*{ATP}_{\mathcal{R},\mathcal{Q}}(\mathsf{c}_{1};\mathsf{c}_{2};\mathsf{c}_{3})$
with constants
$\mathsf{c}_{1}=\\{\mathsf{a}_{1}^{2}-\mathsf{b}_{1}-\alpha^{2}\\}^{1/2}$,
$\mathsf{c}_{2}=\mathsf{a}_{2}+\mathsf{b}_{2}/\alpha$ and
$\mathsf{c}_{3}=\mathsf{b}_{3}/\alpha$. Taking $\alpha=\mathsf{a}_{1}/2$, we
obtain that
$\operatorname*{ATP}_{\mathcal{R},\mathcal{Q}}(\mathsf{c}_{1};\mathsf{c}_{2};\mathsf{c}_{3})$
holds with constants
$\mathsf{c}_{1}=\\{(3/4)\mathsf{a}_{1}^{2}-\mathsf{b}_{1}\\}^{1/2}$,
$\mathsf{c}_{2}=\mathsf{a}_{2}+2\mathsf{b}_{2}/\mathsf{a}_{1}$ and
$\mathsf{c}_{3}=2\mathsf{b}_{3}/\mathsf{a}_{1}$.

We now recall the definition of decomposable norms [70, 55].

######  Definition 8.3 (Decomposable norm).

A norm $\mathcal{R}$ over $\mathds{R}^{p}$ is said to be decomposable if for
all $\mathbf{B}\in\mathds{R}^{p}$, there exist linear map
$\mathbf{V}\mapsto\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{V})$ such that, for
all $\mathbf{V}\in\mathds{R}^{p}$, defining
$\mathcal{P}_{\mathbf{B}}(\mathbf{V}):=\mathbf{V}-\mathcal{P}^{\perp}_{\mathbf{B}}(\mathbf{V})$,

  * •

$\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{B})=0$,

  * •

$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathcal{P}_{\mathbf{B}}(\mathbf{V}),\mathcal{P}^{\perp}_{\mathbf{B}}(\mathbf{V})\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=0$,

  * •

$\mathcal{R}(\mathbf{V})=\mathcal{R}(\mathcal{P}_{\mathbf{B}}(\mathbf{V}))+\mathcal{R}(\mathcal{P}^{\perp}_{\mathbf{B}}(\mathbf{V}))$.

In particular,
$\|\mathbf{V}\|_{F}^{2}=\|\mathcal{P}_{\mathbf{B}}(\mathbf{V})\|_{F}^{2}+\|\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{V})\|_{F}^{2}$.
For $\mathbf{V}\in\mathds{R}^{p}\setminus\\{0\\}$, we define

$\Psi_{\mathcal{R}}(\mathbf{V}):=\frac{\mathcal{R}(\mathbf{V})}{\|\mathbf{V}\|_{F}}.$

We omit the subscript $\mathcal{R}$ when it is clear in the context.

Two well known examples of decomposable norms are the $\ell_{1}$ and nuclear
norms.

######  Example ($\ell_{1}$-norm).

Given $\mathbf{B}\in\mathds{R}^{p}$ with _sparsity support_
$\mathscr{S}(\mathbf{B}):=\\{[j,k]:\mathbf{B}_{j,k}\neq 0\\}$, the
$\ell_{1}$-norm in $\mathds{R}^{p}$ satisfies the above decomposability
condition with the map
$\mathbf{V}\mapsto\mathcal{P}^{\perp}_{\mathbf{B}}(\mathbf{V}):=\mathbf{V}_{\mathcal{S}(\mathbf{B})^{c}}$
where $\mathbf{V}_{\mathcal{S}(\mathbf{B})^{c}}$ denotes the $d_{1}\times
d_{2}$ matrix whose entries are zero at indexes in $\mathscr{S}(\mathbf{B})$.

######  Example (Nuclear norm).

Let $\mathbf{B}\in\mathds{R}^{p}$ with rank
$r:=\operatorname*{rank}(\mathbf{B})$, singular values
$\\{\sigma_{j}\\}_{j\in[r]}$ and singular vector decomposition
$\mathbf{B}=\sum_{j\in[r]}\sigma_{j}\boldsymbol{u}_{j}\boldsymbol{v}_{j}^{\top}$.
Here $\\{\boldsymbol{u}_{j}\\}_{j\in[r]}$ are the left singular vectors
spanning the subspace $\mathcal{U}$ and $\\{\boldsymbol{v}_{j}\\}_{j\in[r]}$
are the right singular vectors spanning the subspace $\mathcal{V}$. The pair
$(\mathcal{U},\mathcal{V})$ is sometimes referred as the _low-rank support_ of
$\mathbf{B}$. Given subspace $S\subset\mathbb{R}^{\ell}$ let
$\mathbf{P}_{S^{\perp}}$ denote the matrix defining the orthogonal projection
onto $S^{\perp}$. Then, the map
$\mathbf{V}\mapsto\mathcal{P}^{\perp}_{\mathbf{B}}(\mathbf{V}):=\mathbf{P}_{\mathcal{U}^{\perp}}\mathbf{V}\mathbf{P}_{\mathcal{V}^{\perp}}^{\top}$
satisfy the decomposability condition for the nuclear norm $\|\cdot\|_{N}$.

Decomposability is particularly useful because of the following well known
lemmas [70, 7].

######  Lemma 8.4.

Let $\mathcal{R}$ be a decomposable norm over $\mathds{R}^{p}$. Let
$\mathbf{B},\hat{\mathbf{B}}\in\mathds{R}^{p}$ and
$\mathbf{V}:=\hat{\mathbf{B}}-\mathbf{B}$. Then, for any $\nu\in[0,1]$,

(61)
$\displaystyle\nu\mathcal{R}(\mathbf{V})+\mathcal{R}(\mathbf{B})-\mathcal{R}(\hat{\mathbf{B}})\leq(1+\nu)\mathcal{R}(\mathcal{P}_{\mathbf{B}}(\mathbf{V}))-(1-\nu)\mathcal{R}(\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{V})).$

######  Lemma 8.5.

Let $o\in[n]$,
$\boldsymbol{\theta},\hat{\boldsymbol{\theta}}\in\mathbb{R}^{n}$ such that
$\|\boldsymbol{\theta}\|_{0}\leq o$. Set
$\boldsymbol{u}:=\hat{\boldsymbol{\theta}}-\boldsymbol{\theta}$. Then
$\|\boldsymbol{\theta}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}\leq\sum_{i=1}^{o}\omega_{i}\boldsymbol{u}_{i}^{\sharp}-\sum_{i=o+1}^{n}\omega_{i}\boldsymbol{u}_{i}^{\sharp}.$
In particular, for any $\nu\in[0,1]$,

(62)
$\displaystyle\nu\|\boldsymbol{u}\|_{\sharp}+\|\boldsymbol{\theta}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}\leq(1+\nu)\sum_{i=1}^{o}\omega_{i}\boldsymbol{u}_{i}^{\sharp}-(1-\nu)\sum_{i=o+1}^{n}\omega_{i}\boldsymbol{u}_{i}^{\sharp}.$

Finally, we state some cone definitions and recall the definition of
restricted eigenvalue constant.

######  Definition 8.6.

Let $\mathcal{R}$ be a decomposable norm over $\mathds{R}^{p}$. Given
$\mathbf{B}\in\mathds{R}^{p}$ and $c_{0},\gamma,\eta>0$, we define the
following cones (63)
$\displaystyle\mathcal{C}_{\mathbf{B},\mathcal{R}}(c_{0})$
$\displaystyle:=\left\\{\mathbf{V}:\mathcal{R}(\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{V}))\leq
c_{0}\mathcal{R}(\mathcal{P}_{\mathbf{B}}(\mathbf{V}))\right\\},$ (64)
$\displaystyle\mathcal{C}_{\mathbf{B},\mathcal{R}}(c_{0},\gamma,\eta)$
$\displaystyle:=\left\\{[\mathbf{V};\boldsymbol{u}]:\gamma\mathcal{R}(\mathcal{P}_{\mathbf{B}}^{\perp}(\mathbf{V}))+\sum_{i=o+1}^{n}\omega_{i}\boldsymbol{u}_{i}^{\sharp}\leq
c_{0}\left[\gamma\mathcal{R}(\mathcal{P}_{\mathbf{B}}(\mathbf{V}))+\eta\|\boldsymbol{u}\|_{2}\right]\right\\}.$
We will omit the subscript $\mathcal{R}$ when the norm is clear in the
context.

######  Definition 8.7 (Restricted eigenvalue).

Given a convex cone $\mathbb{C}$ on $\mathds{R}^{p}$, we define

$\mu(\mathbb{C}):=\sup_{\mathbf{V}\in\mathbb{C}}\frac{\|\mathbf{V}\|_{F}}{\|\mathbf{V}\|_{\Pi}}.$

###  8.2 Deterministic bounds

Throughout this section $\mathcal{R}$ is a general decomposable norm on
$\mathds{R}^{p}$ (see Definition 8.3).

######  Lemma 8.8 (Dimension reduction).

Suppose

  * (i)

$(\mathfrak{X},\boldsymbol{\xi})$ satisfies the
$\operatorname*{MP}_{\mathcal{R},\|\cdot\|_{\sharp}}(\mathsf{f}_{1};\mathsf{f}_{2};\mathsf{f}_{3})$
for some positive numbers $\mathsf{f}_{1}$, $\mathsf{f}_{2}$ and
$\mathsf{f}_{3}$.

  * (ii)

$\mathfrak{X}$ satisfies the
$\operatorname*{ATP}_{\mathcal{R},\|\cdot\|_{\sharp}}(\mathsf{c}_{1};\mathsf{c}_{2};\mathsf{c}_{3})$
for some positive numbers $\mathsf{c}_{1},\mathsf{c}_{2},\mathsf{c}_{3}$.

  * (iii)

$\lambda=\gamma\tau\geq
2[\mathsf{f}_{2}+(\nicefrac{{\mathsf{f}_{1}\mathsf{c}_{2}}}{{\mathsf{c}_{1}}})],\quad\text{and}\quad\tau\geq
2[\mathsf{f}_{3}+(\nicefrac{{\mathsf{f}_{1}\mathsf{c}_{3}}}{{\mathsf{c}_{1}}})].$

Then either
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$
or

(65)
$\displaystyle\|[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\|_{\Pi}$
$\displaystyle\leq
2\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}^{2}}+\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\frac{28\mathsf{f}_{1}^{2}}{3\mathsf{c}_{1}^{3}},$
(66)
$\displaystyle\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
$\displaystyle\leq\frac{28\mathsf{f}_{1}^{2}}{3\mathsf{c}_{1}^{2}}.$

###### Proof.

The first order condition of (6) at
$[\hat{\mathbf{B}},\hat{\boldsymbol{\theta}}]$ is equivalent to the statement:
there exist $\mathbf{V}\in\partial\mathcal{R}(\hat{\mathbf{B}})$ and
$\boldsymbol{u}\in\partial\|\hat{\boldsymbol{\theta}}\|_{\sharp}$ such that
for all $[\mathbf{B};\boldsymbol{\theta}]$,

(67)
$\displaystyle\sum_{i\in[n]}\left[y_{i}^{(n)}-\mathfrak{X}^{(n)}_{i}(\widehat{\mathbf{B}})-\hat{\boldsymbol{\theta}}_{i}\right]\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}^{(n)}_{i},\hat{\mathbf{B}}-\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle$
$\displaystyle\geq\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\hat{\mathbf{B}}-\mathbf{B}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle,$
(68)
$\displaystyle\langle\boldsymbol{y}^{(n)}-\mathfrak{X}^{(n)}(\hat{\mathbf{B}})-\hat{\boldsymbol{\theta}},\hat{\boldsymbol{\theta}}-\boldsymbol{\theta}\rangle$
$\displaystyle\geq\tau\langle\boldsymbol{u},\hat{\boldsymbol{\theta}}-\boldsymbol{\theta}\rangle.$

Evaluating at $[\mathbf{B}^{*};\boldsymbol{\theta}^{*}]$ and using that
$\boldsymbol{y}^{(n)}=\mathfrak{X}^{(n)}(\mathbf{B}^{*})+\boldsymbol{\theta}^{*}+\boldsymbol{\xi}^{(n)}$
we obtain

(69)
$\displaystyle\sum_{i\in[n]}\left[\mathfrak{X}^{(n)}_{i}\left(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\right)+\boldsymbol{\Delta}_{i}^{\hat{\boldsymbol{\theta}}}\right]\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}^{(n)}_{i},\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle$
$\displaystyle\leq\sum_{i\in[n]}\xi_{i}^{(n)}\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}_{i}^{(n)},\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle,$
(70)
$\displaystyle\left\langle\mathfrak{X}^{(n)}\left(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\right)+\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\right\rangle$
$\displaystyle\leq\left\langle\boldsymbol{\xi}^{(n)}-\tau\boldsymbol{u},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\right\rangle,$

so summing both equations we get

(71)
$\displaystyle\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}^{2}\leq\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\boldsymbol{\xi}^{(n)},\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\tau\langle\boldsymbol{u},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\rangle.$

There is $\mathbf{U}$ such that $\mathcal{R}^{*}(\mathbf{U})\leq 1$ and
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{U},\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\mathcal{R}(\hat{\mathbf{B}})$.555Recall
the subdifferential of a norm $\mathcal{R}$ at a point $\mathbf{W}$ is
$\partial\mathcal{R}(\mathbf{W})=\\{\mathbf{U}:\mathcal{R}^{*}(\mathbf{U})\leq
1,\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{U},\mathbf{W}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\mathcal{R}(\mathbf{W})\\}$.
Hence, we get

$-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{B}^{*}-\hat{\mathbf{B}},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{B}^{*},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle-\mathcal{R}(\hat{\mathbf{B}})\leq\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}}).$

Similarly,
$-\langle\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}},\boldsymbol{u}\rangle\leq\|\boldsymbol{\theta}^{*}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}$.
From these bounds we obtain

(72)
$\displaystyle\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}\mathsf{f}_{1}\|[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\|_{\Pi}+\mathsf{f}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\mathsf{f}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
(73)
$\displaystyle+\lambda\big{(}\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}})\big{)}+\tau\big{(}\|\boldsymbol{\theta}^{*}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}\big{)}$
(74)
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}+\left(\mathsf{f}_{2}+\frac{\mathsf{f}_{1}\mathsf{c}_{2}}{\mathsf{c}_{1}}\right)\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\left(\mathsf{f}_{3}+\frac{\mathsf{f}_{1}\mathsf{c}_{3}}{\mathsf{c}_{1}}\right)\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
(75)
$\displaystyle+\lambda\big{(}\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}})\big{)}+\tau\big{(}\|\boldsymbol{\theta}^{*}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}\big{)}$
(76)
$\displaystyle\stackrel{{\scriptstyle\rm(iii)}}{{\leq}}\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}+(\nicefrac{{\lambda}}{{2}})\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+(\nicefrac{{\tau}}{{2}})\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
(77)
$\displaystyle+\lambda\big{(}\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}})\big{)}+\tau\big{(}\|\boldsymbol{\theta}^{*}\|_{\sharp}-\|\hat{\boldsymbol{\theta}}\|_{\sharp}\big{)}$
(78)
$\displaystyle\leq\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}+\triangle,$

where in last inequality we used the decomposability of $\mathcal{R}$ and
Lemmas 8.4-8.5 with $\nu:=1/2$ and have defined

(79)
$\displaystyle\triangle:=(\nicefrac{{3\lambda}}{{2}})(\mathcal{R}\circ\mathcal{P}_{\mathbf{B}^{*}})(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})-(\nicefrac{{\lambda}}{{2}})(\mathcal{R}\circ\mathcal{P}_{\mathbf{B}^{*}}^{\perp})(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+(\nicefrac{{3\tau\Omega}}{{2}})\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}-(\nicefrac{{\tau}}{{2}})\sum_{i=o+1}^{n}\omega_{i}(\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})_{i}^{\sharp}.$

Define also
$G:=\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}$
and
$H:=(\nicefrac{{3\lambda}}{{2}})(\mathcal{R}\circ\mathcal{P}_{\mathbf{B}^{*}})(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+(\nicefrac{{3\tau\Omega}}{{2}})\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}$.
We split the argument in two cases.

Case 1:

$\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}G\leq H$. In that case, from (78) we
obtain
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$.

Case 2:

$\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}G\geq H$. In that case we obtain
$G^{2}\leq\frac{2\mathsf{f}_{1}}{\mathsf{c}_{1}}G\Rightarrow
G\leq\frac{2\mathsf{f}_{1}}{\mathsf{c}_{1}}$. Therefore $H\leq
2\frac{\mathsf{f}_{1}^{2}}{\mathsf{c}_{1}^{2}}$. We first establish a bound on
$\gamma\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$.
Again from (78), we obtain that

(80)
$\displaystyle\lambda(\mathcal{R}\circ\mathcal{P}_{\mathbf{B}^{*}}^{\perp})(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\sum_{i=o+1}^{n}\omega_{i}(\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})_{i}^{\sharp}\leq
4\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}G\leq
8\frac{\mathsf{f}_{1}^{2}}{\mathsf{c}_{1}^{2}}.$

This fact and decomposability imply

(81)
$\displaystyle\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}\leq\frac{2}{3}H+8\frac{\mathsf{f}_{1}^{2}}{\mathsf{c}_{1}^{2}}\leq\frac{28\mathsf{f}_{1}^{2}}{3\mathsf{c}_{1}^{2}}.$

From the $\operatorname*{ATP}$ in $\rm{(ii)}$ and the above bound,

(82)
$\displaystyle\mathsf{c}_{1}\|[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\|_{\Pi}\leq\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}+\mathsf{c}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\mathsf{c}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}\leq
2\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}}+\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\frac{28\mathsf{f}_{1}^{2}}{3\mathsf{c}_{1}^{2}}.$

This finishes the proof. ∎

######  Proposition 2.

Suppose that, in addition to (i)-(iii) in Lemma 8.8, the following condition
holds:

  * (iv)

For
$R:=\Psi(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))\mu(\mathcal{C}_{\mathbf{B}^{*}}(12))$,
assume

$14\big{(}{\mathsf{c}_{2}}\vee\gamma\mathsf{c}_{3}\big{)}\left(R^{2}+\frac{4\Omega^{2}}{\gamma^{2}}\right)^{1/2}\leq\mathsf{c}_{1}.$

Then either (65)-(66) hold or

(83)
$\displaystyle\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}$
$\displaystyle\leq\frac{4}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}+\frac{6}{\mathsf{c}_{1}^{2}}\sqrt{\lambda^{2}R^{2}+4\tau^{2}\Omega^{2}},$
(84)
$\displaystyle\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\big{\|}_{\sharp}$
$\displaystyle\leq\frac{56}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}^{2}+\frac{56}{\mathsf{c}_{1}^{2}}\lambda^{2}R^{2}+\frac{196}{\mathsf{c}_{1}^{2}}\tau^{2}\Omega^{2}.$

###### Proof.

From Lemma 8.8, we only need to consider the case when
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$.
A slight variation of the argument to establish (78) leads to

(85)
$\displaystyle\|\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})\|_{2}^{2}\leq\mathsf{f}_{1}\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}+\triangle,$

where $\triangle$ was already defined in the proof of Lemma 8.8.
$\operatorname*{ATP}$ as stated in item $\rm{(ii)}$ of Lemma 8.8 further leads
to

(86)
$\displaystyle\left\\{\mathsf{c}_{1}\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}-\mathsf{c}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})-\mathsf{c}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}\right\\}_{+}\leq\sqrt{\mathsf{f}_{1}\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}+\triangle}.$

We now split our arguments in two cases.

Case 1:

$12\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))\geq\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}^{\perp}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))$.
Hence
$\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\in\mathcal{C}_{\mathbf{B}^{*}}(12)$.
Decomposability of $\mathcal{R}$ and
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$
further imply

(87)
$\displaystyle\mathsf{c}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\mathsf{c}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
$\displaystyle\leq\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\big{(}\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp})$
(88) $\displaystyle\leq
7\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\big{(}\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2})$
(89) $\displaystyle\leq
7\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\bigg{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\bigg{)}^{1/2}\|[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\|_{\Pi}.$

Similarly,

(90) $\displaystyle\triangle$
$\displaystyle\leq(\nicefrac{{3\lambda}}{{2}})\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+(\nicefrac{{3\tau\Omega}}{{2}})\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}$
(91)
$\displaystyle\leq(\nicefrac{{3}}{{2}})\bigg{(}\lambda^{2}\Psi^{2}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))\mu^{2}(\mathcal{C}_{\mathbf{B}^{*}}(12))+\tau^{2}\Omega^{2}\bigg{)}^{1/2}\|[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\|_{\Pi}.$

To ease notation, define
$x=\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}$,

(92) $\displaystyle A$
$\displaystyle=7\big{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\big{)}\big{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\big{)}^{1/2},$
(93) $\displaystyle B$
$\displaystyle=\mathsf{f}_{1}+(\nicefrac{{3}}{{2}})\big{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\big{)}^{1/2}.$

From (86), (89) and (91) we get

(94) $\displaystyle\mathsf{c}_{1}x\leq Ax+\sqrt{Bx}\quad\Longrightarrow\quad
x\leq\frac{B}{(\mathsf{c}_{1}-A)^{2}}$

provided that ${A\leq\mathsf{c}_{1}}$. Assuming ${2A\leq\mathsf{c}_{1}}$, we
get

(95)
$\displaystyle\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}\leq\frac{4B}{\mathsf{c}_{1}^{2}}=\frac{4}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}+\frac{6}{\mathsf{c}_{1}^{2}}(\lambda^{2}R^{2}+\tau^{2}\Omega^{2})^{1/2}.$

For deriving the bound on
$\gamma\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$,
we again use the decomposability of $\mathcal{R}$ and
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$,
obtaining

(96)
$\displaystyle\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
$\displaystyle\leq(7\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+6\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2})$
(97) $\displaystyle\leq
7\bigg{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\bigg{)}^{1/2}\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}$
(98)
$\displaystyle\leq\frac{28}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}\bigg{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\bigg{)}^{1/2}+\frac{42}{\mathsf{c}_{1}^{2}}\bigg{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\bigg{)}$
(99)
$\displaystyle\leq\frac{56}{\mathsf{c}_{1}^{2}}\mathsf{f}^{2}_{1}+\frac{56}{\mathsf{c}_{1}^{2}}\bigg{(}\lambda^{2}R^{2}+\tau^{2}\Omega^{2}\bigg{)}.$

Case 2:

$12\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))<\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}^{\perp}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))$.
As
$[\boldsymbol{\Delta}^{\hat{\mathbf{B}}};\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\in\mathcal{C}_{\mathbf{B}^{*}}(6,\gamma,\Omega)$,
we get

(100) $\displaystyle
6\gamma\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+\sum_{i=o+1}^{n}\omega_{i}(\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}})^{\sharp}_{i}\leq
6\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}.$

This and decomposability of $\mathcal{R}$ imply

(101)
$\displaystyle\mathsf{c}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\mathsf{c}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}$
$\displaystyle\leq\Big{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\Big{)}\big{(}\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp})$
(102) $\displaystyle\leq
7\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\big{(}\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2})$
(103) $\displaystyle\leq
14\bigg{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\bigg{)}\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}.$

Similarly,

(104)
$\displaystyle\triangle\leq(\nicefrac{{3}}{{2}})\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+(\nicefrac{{3}}{{2}})\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}\leq
3\tau\Omega\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}.$

Again it is convenient to define
$x=\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\,;\,\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}$,
$A^{\prime}=14\big{(}\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}\big{)}\tau\Omega$
and $B^{\prime}=\mathsf{f}_{1}+3\tau\Omega$. From (86), (103) and (104),

(105) $\displaystyle\mathsf{c}_{1}x\leq
A^{\prime}x+\sqrt{B^{\prime}x}\quad\Longrightarrow\quad
x\leq\frac{B^{\prime}}{(\mathsf{c}_{1}-A^{\prime})^{2}}\leq\frac{4B^{\prime}}{\mathsf{c}_{1}^{2}}$

provided that $2A^{\prime}\leq\mathsf{c}_{1}$. In conclusion,

(106)
$\displaystyle\big{\|}[\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\,;\,\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}]\big{\|}_{\Pi}\leq\frac{4\mathsf{f}_{1}}{\mathsf{c}_{1}^{2}}+\frac{12\tau\Omega}{\mathsf{c}_{1}^{2}},$

implying

(107)
$\displaystyle\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\big{\|}\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\big{\|}_{\sharp}$
$\displaystyle\leq
7\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))+7\tau\Omega\big{\|}\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\big{\|}_{2}$
(108) $\displaystyle\leq
14\tau\Omega\,\big{\|}\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\big{\|}_{2}$
(109)
$\displaystyle\leq\frac{56}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}\tau\Omega+\frac{168}{\mathsf{c}_{1}^{2}}\tau^{2}\Omega^{2}$
(110)
$\displaystyle\leq\frac{28}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}^{2}+\frac{196}{\mathsf{c}_{1}^{2}}\tau^{2}\Omega^{2}.$

The proof is complete by noting that the bounds in the statement of the
proposition are larger than the bounds we have just established in the above
cases. ∎

######  Lemma 8.9.

(111)
$\displaystyle\left\langle\mathfrak{M}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}),\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right\rangle\leq\langle\boldsymbol{\xi}^{(n)},\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\rangle+\lambda\left(2\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right).$

###### Proof.

As $[\hat{\mathbf{B}};\hat{\boldsymbol{\theta}}]$ is the minimizer of (6), in
particular

(112) $\displaystyle\hat{\mathbf{B}}\in$
$\displaystyle\operatorname*{argmin}_{\mathbf{B}}\left\\{\frac{1}{2}\|\boldsymbol{y}^{(n)}-\mathfrak{X}^{(n)}(\mathbf{B})-\hat{\boldsymbol{\theta}}\|_{2}^{2}+\lambda\mathcal{R}(\mathbf{B})\right\\}.$

The KKT conditions of the above minimization problem and the expression of the
subdifferential of any norm imply that there exists
$\mathbf{V}\in\mathbb{R}^{m_{1}\times m_{2}}$ with
$\mathcal{R}^{*}(\mathbf{V})\leq 1$ and
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\mathcal{R}(\hat{\mathbf{B}})$
such that, for all $\mathbf{B}\in\mathbb{R}^{m_{1}\times m_{2}}$,

(113) $\displaystyle 0$
$\displaystyle\leq\sum_{i\in[n]}\left[\mathfrak{X}^{(n)}_{i}(\widehat{\mathbf{B}})+\widehat{\boldsymbol{\theta}}_{i}-y_{i}^{(n)}\right]\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}^{(n)}_{i},\mathbf{B}-\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle+\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{B}-\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle$
(114)
$\displaystyle=\sum_{i\in[n]}\left[\mathfrak{X}^{(n)}_{i}(\boldsymbol{\Delta}^{\widehat{\mathbf{B}}})+\boldsymbol{\Delta}^{\widehat{\boldsymbol{\theta}}}_{i}-\xi_{i}^{(n)}\right]\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{X}^{(n)}_{i},\mathbf{B}-\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle+\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{B}-\hat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle.$

We can take $\mathbf{B}:=\mathbf{B}^{*}$ above and obtain

(115) $\displaystyle 0$
$\displaystyle\leq-\left\langle\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}},\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right\rangle+\langle\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}),\boldsymbol{\xi}^{(n)}\rangle-\lambda\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle.$

Using that
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\widehat{\mathbf{B}}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle=\mathcal{R}(\hat{\mathbf{B}})$
and
$\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\mathbf{V},\mathbf{B}^{*}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\leq\mathcal{R}(\mathbf{B}^{*})$
(since $\mathcal{R}^{*}(\mathbf{V})\leq 1$), we obtain that
$-\langle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\langle\boldsymbol{\Delta}^{\hat{\mathbf{B}}},\mathbf{V}\rangle\mathchoice{{}\mkern-4.5mu}{{}\mkern-4.5mu}{{}\mkern-2.5mu}{}\rangle\leq\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}}).$
Moreover, from the triangle inequality and the decomposability property for
the norm $\mathcal{R}$, one checks that

(116)
$\displaystyle\mathcal{R}(\mathbf{B}^{*})-\mathcal{R}(\hat{\mathbf{B}})\leq\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}^{\perp}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))=2\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}).$

Combining the two previous displays finishes the proof. ∎

######  Theorem 8.10 (Trace regression).

Suppose the following condition holds:

  * (i)

$(\mathfrak{X},\boldsymbol{\xi})$ satisfies the
$\operatorname*{MP}_{\mathcal{R},\|\cdot\|_{\sharp}}(\mathsf{f}_{1};\mathsf{f}_{2};\mathsf{f}_{3})$
for some positive numbers $\mathsf{f}_{1}$, $\mathsf{f}_{2}$ and
$\mathsf{f}_{3}$.

  * (ii)

$\mathfrak{X}$ satisfies the
$\operatorname*{ATP}_{\mathcal{R},\|\cdot\|_{\sharp}}(\mathsf{c}_{1};\mathsf{c}_{2};\mathsf{c}_{3})$
for some positive numbers $\mathsf{c}_{1},\mathsf{c}_{2},\mathsf{c}_{3}$.

  * (iii)

$\lambda=\gamma\tau\geq
2[\mathsf{f}_{2}+(\nicefrac{{\mathsf{f}_{1}\mathsf{c}_{2}}}{{\mathsf{c}_{1}}})],\quad\text{and}\quad\tau\geq
2[\mathsf{f}_{3}+(\nicefrac{{\mathsf{f}_{1}\mathsf{c}_{3}}}{{\mathsf{c}_{1}}})].$

  * (iv)

$\mathfrak{X}$ satisfies the
$\operatorname*{IP}_{\mathcal{R},\|\cdot\|_{\sharp}}\left(\mathsf{b}_{1};\mathsf{b}_{2};\mathsf{b}_{3}\right)$.

  * (v)

$\mathfrak{X}$ satisfies the
$\operatorname*{TP}_{\mathcal{R}}\left(\mathsf{a}_{1};\mathsf{a}_{2}\right)$.

Suppose that $\mu(\mathcal{C}_{\mathbf{B}^{*}}(12))<\infty$. Let
$R:=\Psi(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))\mu(\mathcal{C}_{\mathbf{B}^{*}}(12))$
and suppose further that

(117) $\displaystyle
14\big{(}{\mathsf{c}_{2}}\vee\gamma\mathsf{c}_{3}\big{)}\left[R^{2}+\frac{4\Omega^{2}}{\gamma^{2}}\right]^{1/2}$
$\displaystyle\leq\mathsf{c}_{1},$ (118)
$\displaystyle\frac{4}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}+\frac{6}{\mathsf{c}_{1}^{2}}\sqrt{\lambda^{2}R^{2}+4\tau^{2}\Omega^{2}}\leq\frac{\lambda}{6\mathsf{b}_{2}}.$

Define the quantities
$\square:=\frac{1.5\mathsf{a}_{2}}{\lambda\mathsf{a}_{1}}\bigvee\frac{1.5\mathsf{b}_{3}}{\tau\mathsf{a}_{1}^{2}},$
$\triangle:=\frac{\mathsf{c}_{2}}{\lambda}\bigvee\frac{\mathsf{c}_{3}}{\tau}$
and

(119) $\displaystyle\Phi_{\square,\lambda R}$
$\displaystyle:=\left(\frac{56\square}{\mathsf{c}_{1}^{2}}+\frac{4.5}{\mathsf{c}_{1}^{2}}\right)(\lambda
R)^{2}+\frac{1.5}{\mathsf{a}_{1}^{2}}(\lambda R),$ (120)
$\displaystyle\Phi_{\square,\mathsf{b}_{1},\mathsf{f}_{1}}$
$\displaystyle:=\frac{56\square}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}^{2}+\frac{6}{\mathsf{c}_{1}^{2}}\mathsf{b}_{1}\mathsf{f}_{1}+\frac{4.5\mathsf{b}_{1}^{2}}{\mathsf{c}_{1}^{2}}+\frac{1.5\mathsf{f}_{1}}{\mathsf{a}_{1}^{2}}$
(121) $\displaystyle\omega_{\square,\tau\Omega}$
$\displaystyle:=\left(\frac{196\square}{\mathsf{c}_{1}^{2}}+\frac{18}{\mathsf{c}_{1}^{2}}\right)(\tau\Omega)^{2}.$

Then

(122)
$\displaystyle\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}$
$\displaystyle\leq\left\\{\Phi_{\square,\lambda
R}+\Phi_{\square,\mathsf{b}_{1},\mathsf{f}_{1}}+\omega_{\square,\tau\Omega}\right\\}\bigvee\left\\{2\frac{\mathsf{f}_{1}}{\mathsf{c}_{1}^{2}}+\triangle\frac{28\mathsf{f}_{1}^{2}}{3\mathsf{c}_{1}^{3}}\right\\}.$

###### Proof.

Condition (117) and items $\rm{(i)}$-$\rm{(iii)}$ imply that the claims of
Proposition 2 hold. If (65)-(66) hold we have nothing to prove. Otherwise,
(83)-(84) hold. In particular,

(123)
$\displaystyle\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}\leq\frac{4}{\mathsf{c}_{1}^{2}}\mathsf{f}_{1}+\frac{6}{\mathsf{c}_{1}^{2}}\sqrt{\lambda^{2}R^{2}+4\tau^{2}\Omega^{2}}\stackrel{{\scriptstyle\eqref{cond2:general:norm}}}{{\leq}}\frac{\lambda}{6\mathsf{b}_{2}}.$

By Lemma 8.9 and $\operatorname*{MP}$ as stated in item $\rm{(i)}$,

(124)
$\displaystyle\|\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\|_{2}^{2}$
$\displaystyle\leq-\langle\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}),\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\rangle+\mathsf{f}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}+\mathsf{f}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\lambda\left(2\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right)$
(125) $\displaystyle\stackrel{{\scriptstyle(\rm
iii)}}{{\leq}}-\langle\mathfrak{X}^{(n)}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}),\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\rangle+\mathsf{f}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}+\frac{\lambda}{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\lambda\left(2\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right)$
(126) $\displaystyle\stackrel{{\scriptstyle(\rm
iv)}}{{\leq}}\mathsf{b}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}+\mathsf{b}_{3}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}+\mathsf{f}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}+2\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\frac{\lambda}{3}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})$
(127)
$\displaystyle\quad+\mathsf{b}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}-\frac{\lambda}{6}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})$
(128)
$\displaystyle\stackrel{{\scriptstyle\eqref{cond3:general:norm}}}{{\leq}}\mathsf{b}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}+\mathsf{b}_{3}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}+\mathsf{f}_{1}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}+2\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\frac{\lambda}{3}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}).$

We now define the local variables
$x:=\|\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\|_{\Pi}$ and

(129) $\displaystyle A$
$\displaystyle:=\mathsf{b}_{1}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}+\mathsf{b}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}+\mathsf{f}_{1},$
(130) $\displaystyle B$
$\displaystyle:=\left\\{2\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))-\frac{\lambda}{3}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\right\\}_{+}.$

On the one hand, combining the last inequality and the $\operatorname*{TP}$,
as stated in item (v), we arrive at

(131)
$\displaystyle(\mathsf{a}_{1}x-\mathsf{a}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))_{+}^{2}\leq
Ax+B.$

This implies that either
$x\leq(\mathsf{a}_{2}/\mathsf{a}_{1})\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})$
or

(132)
$\displaystyle\Big{(}\mathsf{a}_{1}x-\mathsf{a}_{2}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})-\frac{A}{2\mathsf{a}_{1}}\Big{)}^{2}\leq
B+\frac{A^{2}}{4\mathsf{a}_{1}^{2}}+\frac{A\mathsf{a}_{2}}{\mathsf{a}_{1}}\,\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}).$

In both cases,

(133) $\displaystyle x$
$\displaystyle\leq\frac{\mathsf{a}_{2}}{\mathsf{a}_{1}}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\frac{A}{2\mathsf{a}_{1}^{2}}+\frac{1}{\mathsf{a}_{1}}\Big{\\{}B+\frac{A^{2}}{4\mathsf{a}_{1}^{2}}+\frac{A\mathsf{a}_{2}}{\mathsf{a}_{1}}\,\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})\Big{\\}}^{1/2}$
(134) $\displaystyle\leq
1.5\frac{\mathsf{a}_{2}}{\mathsf{a}_{1}}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+1.5\frac{A}{\mathsf{a}_{1}^{2}}+\frac{B^{1/2}}{\mathsf{a}_{1}}.$

On the other hand,

(135) $\displaystyle B\leq
2\lambda\mathcal{R}(\mathcal{P}_{\mathbf{B}^{*}}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}}))\leq
2\lambda Rx\leq\bigg{(}\frac{\mathsf{a}_{1}x}{2}+\frac{2\lambda
R}{\mathsf{a}_{1}}\bigg{)}^{2}.$

Combining (134) and (135), we get

(136)
$\displaystyle\frac{x}{2}\leq\frac{1.5\mathsf{a}_{2}}{\mathsf{a}_{1}}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\frac{1.5A}{\mathsf{a}_{1}^{2}}+\frac{2\lambda
R}{\mathsf{a}_{1}^{2}}.$

Replacing $A$ and $x$ by their expressions, we arrive at

(137)
$\displaystyle\frac{1}{2}\big{\|}\boldsymbol{\Delta}^{\hat{\mathbf{B}}}\big{\|}_{\Pi}$
$\displaystyle\leq\frac{1.5\mathsf{a}_{2}}{\mathsf{a}_{1}}\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\frac{1.5\mathsf{b}_{1}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}+1.5\mathsf{b}_{3}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}+1.5\mathsf{f}_{1}}{\mathsf{a}_{1}^{2}}+\frac{1.5\lambda
R}{\mathsf{a}_{1}^{2}}$ (138)
$\displaystyle\leq\bigg{(}\frac{1.5\mathsf{a}_{2}}{\lambda\mathsf{a}_{1}}\bigvee\frac{1.5\mathsf{b}_{3}}{\tau\mathsf{a}_{1}^{2}}\bigg{)}\big{(}\lambda\mathcal{R}(\boldsymbol{\Delta}^{\hat{\mathbf{B}}})+\tau\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{\sharp}\big{)}+1.5\mathsf{b}_{1}\|\boldsymbol{\Delta}^{\hat{\boldsymbol{\theta}}}\|_{2}+\frac{1.5\lambda
R}{\mathsf{a}_{1}^{2}}+\frac{1.5\mathsf{f}_{1}}{\mathsf{a}_{1}^{2}}.$

By (123),