# A note on sharp oracle bounds for Slope and Lasso

Zhiyong Zhou<EMAIL_ADDRESS>Department of Statistics, Zhejiang
University City College, Hangzhou, 310015, China

###### Abstract

In this paper, we study the sharp oracle bounds for Slope and Lasso and
generalize the results in [1] to allow the case that the parameter vector is
not exactly sparse and obtain the optimal bounds for $\ell_{q}$ estimation
errors with $1\leq q\leq\infty$ by using some extended Restricted Eigenvalue
type conditions.

###### keywords:

Slope; Lasso; Restricted Eigenvalue condition; High-dimensional linear
regression.

[table]capposition=top

##  1 Introduction

In high-dimensional linear regression [5], we aim to estimate the $s$-sparse
parameter vector $\beta^{*}\in\mathbb{R}^{p}$ (i.e.,
$\lVert\beta^{*}\rVert_{0}\leq s$) from few noisy observations
$y=X\beta^{*}+\xi$, where $y\in\mathbb{R}^{n}(n\ll p)$,
$X\in\mathbb{R}^{n\times p}$ is the design matrix and
$\xi\in\mathbb{R}^{n}\sim N(0,\sigma^{2}I_{n\times n})$ is the Gaussian noise.
The best prediction and $\ell_{2}$ estimation rate achieved by the well-known
polynomial time algorithms such as the Lasso [12] and the Dantzig selector [2]
is $(s/n)\log(p)$, while the minimax rate for the problem is $(s/n)\log(p/s)$
[9]. Until recently, [10] has shown that for i.i.d. standard normal regressor
this optimal rate can be asymptotically achieved by a computable in polynomial
time method called Sorted L-One Penalized Estimator (Slope) [3]. For the high-
dimensional linear regression problem, Slope is defined as a solution of the
minimization problem:

$\displaystyle\mathop{\arg\min}\limits_{\beta\in\mathbb{R}^{p}}\frac{1}{n}\lVert
y-X\beta\rVert_{2}^{2}+2\lVert\beta\rVert_{*},$ (1)

where the norm
$\lVert\beta\rVert_{*}=\sum\limits_{j=1}^{p}\lambda_{j}\beta_{j}^{\sharp}$,
the tuning parameters satisfy
$\lambda_{1}\geq\lambda_{2}\geq\cdots\lambda_{p}\geq 0$,
$(\beta_{1}^{\sharp},\beta_{2}^{\sharp},\cdots,\beta_{p}^{\sharp})$ is a non-
increasing rearrangement of $(|\beta_{1}|,|\beta_{2}|,\cdots,|\beta_{p}|)$.
[8] extends the results in [10] to the subgaussian designs and obtains a non-
asymptotic bound with this optimal rate by using the small ball method.
Nevertheless, the strong assumption that the covariance matrix of the design
is proportional to the identity matrix (namely the design is isotropic) is
required in both of these works. In order to relax this restriction, [1] shows
that under the Restricted Eigenvalue (RE) type conditions a Lasso estimator
with adaptively chosen tuning parameters and a Slope estimator can achieve the
non-asymptotic minimax prediction and $\ell_{2}$ estimation rate
$(s/n)\log(p/s)$ both in probability and in expectation. The RE type
conditions imposed on the design are satisfied for a large class of random
matrices with independent and possibly anisotropically distributed rows with
high probability. The Slope method has attracted more and more research
interest. Among them, [6] discussed the Squared-Root Slope method. [4]
extended to the Group Slope for handling the group sparse regression problem,
while [7] proposed the Sorted Concave Penalized method through combining the
Slope and Concave Penalized method.

However, we notice that all the existing literature on the Slope only
discussed the case that the parameter vector to be estimated is exactly sparse
and the bounds are merely obtained for the $\ell_{q}$ estimation errors with
$1\leq q\leq 2$. In this paper, we aim to generalize the results in [1] to
allow the case that the parameter vector is not exactly sparse and derive the
optimal bounds for $\ell_{q}$ estimation errors with $1\leq q\leq\infty$ via
the extended RE type conditions.

The paper is organized as follows. In Section 2, we study the estimation
performance of the Lasso estimator. In Section 3, we present the results for
the Slope estimator. In Section 4, we discuss the optimality of the derived
upper bounds. In Section 5, we investigate the proposed RE conditions. In
Section 6, we give the conclusion.

##  2 Lasso estimator

In this section, we denote the Lasso estimator by
$\hat{\beta}\in\mathop{\arg\min}\limits_{\beta\in\mathbb{R}^{p}}\frac{1}{n}\lVert
y-X\beta\rVert_{2}^{2}+2\lambda\lVert\beta\rVert_{1}$, where $\lambda>0$ is a
tuning parameter. We use some notations in [1] in order to facilitate the
presentation of the results. For a given $\delta_{0}\in(0,1)$ and for any
$u=(u_{1},u_{2},\cdots,u_{p})\in\mathbb{R}^{p}$, we set

$\displaystyle
H(u):=(4+\sqrt{2})\sum\limits_{j=1}^{p}u_{j}^{\sharp}\sigma\sqrt{\frac{\log(2p/j)}{n}},\,\,G(u):=(4+\sqrt{2})\sigma\sqrt{\frac{\log(1/\delta_{0})}{n}}\lVert
Xu\rVert_{2}/\sqrt{n},$ (2)

where $(u_{1}^{\sharp},u_{2}^{\sharp},\cdots,u_{p}^{\sharp})$ is a non-
increasing rearrangement of $(|u_{1}|,|u_{2}|,\cdots,|u_{p}|)$. For a vector
$\beta\in\mathbb{R}^{p}$ and a set $S\subset\\{1,2,\cdots,p\\}$, we denote by
$\beta_{S}$ the vector which coincides with $\beta$ on the indices in $S$ and
is extended to zero outside $S$.

First, as an extension of LEMMA A.1 in [1], we have the following key lemma
that allows the parameter vector to be not exactly sparse.

###### Lemma 1

Let $s\in\\{1,\cdots,p\\}$, $\tau\in[0,1]$,
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{p}\geq 0$ and the error of
the best $s$-term approximation of $\beta$ with respect to
$\lVert\cdot\rVert_{*}$ is defined by
$\sigma_{s}(\beta)_{*}=\min\limits_{\lVert z\rVert_{0}\leq
s}\lVert\beta-z\rVert_{*}$. For any two $\beta,\hat{\beta}\in\mathbb{R}^{p}$
and $1<q\leq\infty$, we have

$\displaystyle\tau\lVert
u\rVert_{*}+\lVert\beta\rVert_{*}-\lVert\hat{\beta}\rVert_{*}$
$\displaystyle\leq(1+\tau)\sum\limits_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}-(1-\tau)\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{*}$
$\displaystyle\leq(1+\tau)\left(\sum\limits_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}\lVert
u\rVert_{q}-(1-\tau)\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{*},$
(3)

where $u=\hat{\beta}-\beta=(u_{1},u_{2},\cdots,u_{p})^{T}$ and
$(u_{1}^{\sharp},u_{2}^{\sharp},\cdots,u_{p}^{\sharp})$ is a non-increasing
rearrangement of $(|u_{1}|,|u_{2}|,\cdots,|u_{p}|)$. In particular, if
$\lambda_{1}=\lambda_{2}=\cdots=\lambda_{p}=\lambda$ for some $\lambda>0$,
then $\lVert\cdot\rVert_{*}=\lambda\lVert\cdot\rVert_{1}$ and we have

$\displaystyle\tau\lambda\lVert
u\rVert_{1}+\lambda\lVert\beta\rVert_{1}-\lambda\lVert\hat{\beta}\rVert_{1}$
$\displaystyle\leq(1+\tau)\lambda\sum\limits_{j=1}^{s}u_{j}^{\sharp}-(1-\tau)\lambda\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}+2\lambda\sigma_{s}(\beta)_{1}$
$\displaystyle\leq(1+\tau)\lambda s^{1-1/q}\lVert
u\rVert_{q}-(1-\tau)\lambda\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}+2\lambda\sigma_{s}(\beta)_{1}.$
(4)

Proof. Let $S$ be the index set of $s$ largest absolute entries of $\beta$ so
that $\sigma_{s}(\beta)_{*}=\lVert\beta_{S^{c}}\rVert_{*}$. Assume $\phi$ is
any permutation of $\\{1,\cdots,p\\}$ such that

$\displaystyle\lVert\beta_{S}\rVert_{*}=\sum\limits_{j=1}^{s}\lambda_{j}|\beta_{\phi(j)}|\,\,\text{and
$|u_{\phi(s+1)}|\geq|u_{\phi(s+2)}|\geq\cdots\geq|u_{\phi(p)}|$.}$

Then by using the definition of $\lVert\cdot\rVert_{*}$ and the Triangle
inequality, we have

$\displaystyle\lVert\beta\rVert_{*}-\lVert\hat{\beta}\rVert_{*}$
$\displaystyle\leq\lVert\beta_{S}\rVert_{*}+\lVert\beta_{S^{c}}\rVert_{*}-\lVert\hat{\beta}\rVert_{*}$
$\displaystyle\leq\sum\limits_{j=1}^{s}\lambda_{j}\left(|\beta_{\phi(j)}|-|\hat{\beta}_{\phi(j)}|\right)-\sum\limits_{j=s+1}^{p}\lambda_{j}|\hat{\beta}_{\phi(j)}|+\lVert\beta_{S^{c}}\rVert_{*}$
$\displaystyle\leq\sum\limits_{j=1}^{s}\lambda_{j}|u_{\phi(j)}|-\sum\limits_{j=s+1}^{p}\lambda_{j}|\hat{\beta}_{\phi(j)}|+\lVert\beta_{S^{c}}\rVert_{*}$
$\displaystyle\leq\sum\limits_{j=1}^{s}\lambda_{j}|u_{\phi(j)}|-\sum\limits_{j=s+1}^{p}\lambda_{j}|u_{\phi(j)}|+\sum\limits_{j=s+1}^{p}\lambda_{j}|\beta_{\phi(j)}|+\lVert\beta_{S^{c}}\rVert_{*}$
$\displaystyle\leq\sum\limits_{j=1}^{s}\lambda_{j}|u_{\phi(j)}|-\sum\limits_{j=s+1}^{p}\lambda_{j}|u_{\phi(j)}|+2\lVert\beta_{S^{c}}\rVert_{*}$
$\displaystyle\leq\sum\limits_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}-\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{*},$

since
$\sum\limits_{j=s+1}^{p}\lambda_{j}|\beta_{\phi(j)}|\leq\lVert\beta_{S^{c}}\rVert_{*}$,
$\sum\limits_{j=1}^{s}\lambda_{j}|u_{\phi(j)}|\leq\sum\limits_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}$
and
$\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}\leq\sum\limits_{j=s+1}^{p}\lambda_{j}|u_{\phi(j)}|$.
Finally, (3) follows from
$\sum\limits_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}\leq\left(\sum\limits_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}\lVert
u\rVert_{q}$ by the Hölder's inequality.

To be self-contained, here we list two technical lemmas given in [1], which
will be used for establishing the main results in what follows.

###### Lemma 2

(Lemma A.2 in [1]) Let $h:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a convex
function, let $f,\xi\in\mathbb{R}^{n}$, $y=f+\xi$ and let $X$ be any $n\times
p$ matrix. If $\hat{\beta}$ is a solution of the minimization problem
$\min_{\beta\in\mathbb{R}^{p}}\\{\frac{1}{n}\lVert
X\beta-y\rVert_{2}^{2}+h(\beta)\\}$, then $\hat{\beta}$ satisfies for all
$\beta\in\mathbb{R}^{p}$

$\displaystyle\frac{1}{n}\lVert X\hat{\beta}-f\rVert_{2}^{2}-\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}\leq\frac{2}{n}\xi^{T}X(\hat{\beta}-\beta)+h(\beta)-h(\hat{\beta})-\frac{1}{n}\lVert
X(\hat{\beta}-\beta)\rVert_{2}^{2}.$ (5)

###### Lemma 3

(Theorem 4.1 in [1]) Let $\delta_{0}\in(0,1)$ and let $X\in\mathbb{R}^{n\times
p}$ be a matrix such that $\max_{j=1,\cdots,p}\lVert
Xe_{j}\rVert_{2}/\sqrt{n}\leq 1$ where $(e_{1},e_{2},\cdots,e_{p})$ is the
canonical basis in $\mathbb{R}^{p}$. Let $H(\cdot)$ and $G(\cdot)$ be defined
in (2). If $\xi\sim N(0,\sigma^{2}I_{n\times n})$, then the random event

$\displaystyle\left\\{\frac{1}{n}\xi^{T}Xu\leq\max(H(u),G(u)),\forall\,u\in\mathbb{R}^{p}\right\\}$
(6)

is of probability of at least $1-\delta_{0}/2$.

In order to obtain the bounds for $\ell_{q}$ estimation errors with any
$q\in[1,\infty]$, we generalize the Strong Restricted Eigenvalue (SRE)
condition in [1] to involve the variable $q$ lying in $[2,\infty]$. When
$q=2$, the following $SRE(q,s,c_{0})$ condition reduces to the $SRE(s,c_{0})$
condition used in [1]. In fact, we notice that the SRE condition is exactly
equivalent to the constrained minimal singular values (CMSV) condition
proposed in [11]. Thus, it's natural to propose the following general
$SRE(q,s,c_{0})$ condition, which is essentially the same as the $q$-ratio
CMSV condition studied in [13, 14] for the sparse signal recovery. For any
$s\in[1,p]$ and $q\in(1,\infty]$, the $q$-ratio CMSV of a design matrix
$X\in\mathbb{R}^{n\times p}$ is defined as $\rho_{q,s}(X)=\min_{\\{\delta\neq
0,s_{q}(\delta)\leq s\\}}\frac{\lVert
X\delta\rVert_{2}}{\lVert\delta\rVert_{q}}$ where
$s_{q}(\delta)=(\frac{\lVert\delta\rVert_{1}}{\lVert\delta\rVert_{q}})^{\frac{q}{q-1}}$
is the $q$-ratio sparsity level of non-zero $\delta\in\mathbb{R}^{p}$.

###### Definition 1

($SRE(q,s,c_{0})$ condition) Let $c_{0}>0$ and $s\in\\{1,2,\cdots,p\\}$. For
any $2\leq q\leq\infty$, the design matrix $X$ satisfies $\lVert
Xe_{j}\rVert_{2}/\sqrt{n}\leq 1$ for all $j=1,\cdots,p$ and

$\displaystyle\theta_{q}(s,c_{0}):=\min\limits_{\delta\neq
0,\delta\in\mathcal{C}_{SRE(q,s,c_{0})}}\frac{\lVert
X\delta\rVert_{2}}{\sqrt{n}\lVert\delta\rVert_{q}}>0,$ (7)

where
$\mathcal{C}_{SRE(q,s,c_{0})}:=\\{\delta\in\mathbb{R}^{p}:\lVert\delta\rVert_{1}\leq(1+c_{0})s^{1-1/q}\lVert\delta\rVert_{q}\\}$
is a cone in $\mathbb{R}^{p}$.

Under the new proposed SRE condition, we now present our main result for the
Lasso estimator. Let $\gamma\in(0,1)$ be a constant. For any tuning parameter
$\lambda>0$, we set

$\displaystyle\delta(\lambda):=\exp\left(-\left(\frac{\gamma\lambda\sqrt{n}}{(4+\sqrt{2})\sigma}\right)^{2}\right)\,\,\text{so
that
$\lambda=\frac{(4+\sqrt{2})\sigma}{\gamma}\sqrt{\frac{\log(1/\delta(\lambda))}{n}}$.}$
(8)

For a given $s\in\\{1,\cdots,p\\}$, the following theorem holds under the
condition

$\displaystyle\lambda\geq\frac{(4+\sqrt{2})\sigma}{\gamma}\sqrt{\frac{\log(2ep/s)}{n}}\,\,\text{or
equivalently $\delta(\lambda)\leq s/(2ep)$}.$ (9)

###### Theorem 1

Let $s\in\\{1,\cdots,p\\}$, $\gamma\in(0,1)$ and $\tau\in[0,1-\gamma)$. For
any $2\leq q\leq\infty$, assume that the $SRE(q,s,c_{0})$ condition holds with
$c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau}$. Let $\lambda$
be a tuning parameter such that (9) holds. Let $\delta_{0}\in(0,1)$. Then, on
the event (6), the Lasso estimator $\hat{\beta}$ with tuning parameter
$\lambda$ satisfies

$\displaystyle 2\tau\lambda\lVert\hat{\beta}-\beta\rVert_{1}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}+C_{\gamma,\tau}(q,s,\lambda,\delta_{0})\lambda^{2}s+4\lambda\sigma_{s}(\beta)_{1},$
(10)

for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$, where

$\displaystyle
C_{\gamma,\tau}(q,s,\lambda,\delta_{0}):=(1+\gamma+\tau)^{2}\left(\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}\vee\frac{s^{1-2/q}}{\theta_{q}^{2}(s,c_{0}(\gamma,\tau))}\right).$

Furthermore, if $f=X\beta^{*}$ for some $\beta^{*}$, then on the event (6), we
have

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{1}$
$\displaystyle\leq\frac{C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}{2\tau}\lambda
s+\frac{2}{\tau}\sigma_{s}(\beta^{*})_{1},$ (11)
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{C_{\gamma,0}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q},\quad(\text{when $\beta^{*}$ is $s$-sparse})$ (12)
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\left(\frac{2}{1+\gamma}\vee\frac{1-\gamma-\tau}{4\tau}\right)C_{\gamma,\tau}(q,s,\lambda,\delta_{0})\lambda
s^{1/q}+\left(\frac{1}{1+\gamma}\vee\frac{1-\gamma-\tau}{\tau}\right)s^{1/q-1}\sigma_{s}(\beta^{*})_{1}.$
(13)

Proof. By using (5) with $h(\cdot)=2\lambda\lVert\cdot\rVert_{1}$, we get that
for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$

$\displaystyle 2\tau\lambda\lVert\hat{\beta}-\beta\rVert_{1}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}-\frac{1}{n}\lVert
X(\hat{\beta}-\beta)\rVert_{2}^{2}+\triangle^{*},$ (14)

where

$\displaystyle\triangle^{*}:=2\tau\lambda\lVert\hat{\beta}-\beta\rVert_{1}+\frac{2}{n}\xi^{T}X(\hat{\beta}-\beta)+2\lambda\lVert\beta\rVert_{1}-2\lambda\lVert\hat{\beta}\rVert_{1}.$

We let $u=\hat{\beta}-\beta$ and define

$\displaystyle\tilde{H}(u):=\frac{(4+\sqrt{2})\sigma}{\sqrt{n}}\left(\lVert
u\rVert_{q}\left[\sum\limits_{j=1}^{s}\left(\sqrt{\log(2p/j)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}+\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}\sqrt{\log(2p/j)}\right).$
(15)

For any $2\leq q\leq\infty$, using the Hölder's inequality and the fact that
$\sum\limits_{j=1}^{s}\log(2p/j)\leq s\log(2ep/s)$, it's easy to verify that

$\displaystyle
H(u)=\frac{(4+\sqrt{2})\sigma}{\sqrt{n}}\sum\limits_{j=1}^{p}u_{j}^{\sharp}\sqrt{\log(2p/j)}\leq\tilde{H}(u)\leq\lambda\gamma\left(s^{1-1/q}\lVert
u\rVert_{q}+\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}\right)=:F(u),\forall\,u\in\mathbb{R}^{p}.$
(16)

On the event (6), by using Lemma 1 we have

$\displaystyle\triangle^{*}$ $\displaystyle\leq
2\lambda(\tau\lVert\hat{\beta}-\beta\rVert_{1}+\lVert\beta\rVert_{1}-\lVert\hat{\beta}\rVert_{1})+2\max(H(u),G(u))$
$\displaystyle\leq 2\lambda\left((1+\tau)s^{1-1/q}\lVert
u\rVert_{q}-(1-\tau)\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{1}\right)+2\max(F(u),G(u)).$

By the definition of $\delta(\lambda)$, i.e.,
$\lambda=\frac{(4+\sqrt{2})\sigma}{\gamma}\sqrt{\frac{\log(1/\delta(\lambda))}{n}}$,
we have

$G(u)=\lambda\sqrt{s}\gamma\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\lVert
Xu\rVert_{2}/\sqrt{n}.$

As the arguments in Proof of Theorem 4.2 in [1], we consider the following two
cases:

(i) Case $G(u)>F(u)$: Then it holds that

$\displaystyle\lVert u\rVert_{q}\leq
s^{1/q-1/2}\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\lVert
Xu\rVert_{2}/\sqrt{n}.$ (17)

Thus,

$\displaystyle\triangle^{*}$ $\displaystyle\leq
2\lambda(1+\tau)s^{1-1/q}\lVert
u\rVert_{q}+2G(u)+4\lambda\sigma_{s}(\beta)_{1}$ $\displaystyle\leq
2\lambda(1+\tau)\sqrt{s}\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\lVert
Xu\rVert_{2}/\sqrt{n}+2\lambda\sqrt{s}\gamma\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\lVert
Xu\rVert_{2}/\sqrt{n}+4\lambda\sigma_{s}(\beta)_{1}$ $\displaystyle\leq
2\lambda\sqrt{s}(1+\tau+\gamma)\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\lVert
Xu\rVert_{2}/\sqrt{n}+4\lambda\sigma_{s}(\beta)_{1}$
$\displaystyle\leq\lambda^{2}s(1+\tau+\gamma)^{2}\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}+\frac{1}{n}\lVert
Xu\rVert_{2}^{2}+4\lambda\sigma_{s}(\beta)_{1}.$ (18)

(ii) Case $G(u)\leq F(u)$: In this case it follows that

$\displaystyle\triangle^{*}\leq\underbrace{2\lambda\left((1+\gamma+\tau)s^{1-1/q}\lVert
u\rVert_{q}-(1-\gamma-\tau)\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}\right)}_{\triangle}+4\lambda\sigma_{s}(\beta)_{1}.$

If $\triangle>0$, then $\lVert
u\rVert_{1}=\sum\limits_{j=1}^{s}u_{j}^{\sharp}+\sum\limits_{j=s+1}^{p}u_{j}^{\sharp}\leq(1+c_{0}(\gamma,\tau))s^{1-1/q}\lVert
u\rVert_{q}$, i.e., $u$ belongs to the cone $\mathcal{C}_{SRE}(q,s,c_{0})$.
The $SRE(q,s,c_{0})$ condition yields $\lVert u\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}}{\theta_{q}(s,c_{0})\sqrt{n}}$. Therefore,

$\displaystyle\triangle^{*}$
$\displaystyle\leq\triangle+4\lambda\sigma_{s}(\beta)_{1}\leq\frac{2\lambda(1+\gamma+\tau)s^{1-1/q}\lVert
Xu\rVert_{2}/\sqrt{n}}{\theta_{q}(s,c_{0})}+4\lambda\sigma_{s}(\beta)_{1}$
$\displaystyle\leq\left(\frac{\lambda(1+\gamma+\tau)s^{1-1/q}}{\theta_{q}(s,c_{0})}\right)^{2}+\frac{1}{n}\lVert
Xu\rVert_{2}^{2}+4\lambda\sigma_{s}(\beta)_{1}.$ (19)

If $\triangle\leq 0$, then (19) holds trivially.

The proof of (10) is completed by combining (18) and (19) with (14).

Now let $f=X\beta^{*}$ and $\beta=\beta^{*}$ in (10), then

$\displaystyle 2\tau\lambda\lVert\hat{\beta}-\beta^{*}\rVert_{1}\leq
2\tau\lambda\lVert\hat{\beta}-\beta^{*}\rVert_{1}+\frac{1}{n}\lVert
X(\hat{\beta}-\beta^{*})\rVert_{2}^{2}\leq
C_{\gamma,\tau}(q,s,\lambda,\delta_{0})\lambda^{2}s+4\lambda\sigma_{s}(\beta^{*})_{1},$

which immediately implies (11).

Next, to prove (12), when the true parameter vector $\beta^{*}$ is exactly
$s$-sparse (i.e., $\sigma_{s}(\beta^{*})_{1}=0$), we take $\tau=0$ and
consider the Cases (i) and (ii) as above with $u=\hat{\beta}-\beta^{*}$.

  * 1.

If $G(u)>F(u)$, then (14) and (18) implies that

$\frac{1}{n}\lVert
X(\hat{\beta}-\beta^{*})\rVert_{2}^{2}\leq\lambda^{2}(1+\gamma)^{2}\frac{\log(1/\delta_{0})}{\log(1/\delta(\lambda))}.$

By this and (17), we get

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$ $\displaystyle\leq
s^{1/q-1/2}\sqrt{\frac{\log(1/\delta_{0})}{s\log(1/\delta(\lambda))}}\cdot\sqrt{\lambda^{2}(1+\gamma)^{2}\frac{\log(1/\delta_{0})}{\log(1/\delta(\lambda))}}$
$\displaystyle\leq
s^{1/q-1/2}\sqrt{\frac{C_{\gamma,0}(q,s,\lambda,\delta_{0})}{(1+\gamma)^{2}}}\cdot\sqrt{\lambda^{2}(1+\gamma)^{2}\frac{sC_{\gamma,0}(q,s,\lambda,\delta_{0})}{(1+\gamma)^{2}}}$
$\displaystyle\leq\frac{C_{\gamma,0}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q}.$ (20)

  * 2.

If $G(u)\leq F(u)$, we have $\triangle\geq\triangle^{*}\geq 0$, i.e.,
$u=\hat{\beta}-\beta^{*}\in\mathcal{C}_{SRE(q,s,\frac{1+\gamma}{1-\gamma})}$
such that

$\displaystyle\frac{1}{n}\lVert
Xu\rVert_{2}^{2}\leq\left(\frac{(1+\gamma)\lambda
s^{1-1/q}}{\theta_{q}(s,\frac{1+\gamma}{1-\gamma})}\right)^{2}.$

Thus we can apply the $SRE(q,s,\frac{1+\gamma}{1-\gamma})$ condition, which
yields that

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}/\sqrt{n}}{\theta_{q}(s,\frac{1+\gamma}{1-\gamma})}$
$\displaystyle\leq\frac{1}{\theta_{q}(s,\frac{1+\gamma}{1-\gamma})}\sqrt{\left(\frac{(1+\gamma)\lambda
s^{1-1/q}}{\theta_{q}(s,\frac{1+\gamma}{1-\gamma})}\right)^{2}}$
$\displaystyle\leq\frac{\sqrt{C_{\gamma,0}(q,s,\lambda,\delta_{0})}}{1+\gamma}s^{1/q-1/2}\sqrt{\lambda^{2}sC_{\gamma,0}(q,s,\lambda,\delta_{0})}$
$\displaystyle\leq\frac{C_{\gamma,0}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q}.$ (21)

Putting together (20) and (21) yields
$\lVert\hat{\beta}-\beta^{*}\rVert_{q}\leq\frac{C_{\gamma,0}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q}$, which completes the proof of (12).

As for the result (13) that allows the true parameter vector $\beta^{*}$ to be
not exactly sparse, we let $f=X\beta^{*}$, $\beta=\beta^{*}$ and
$u=\hat{\beta}-\beta^{*}$ in (10), then

$\displaystyle 2\tau\lambda\lVert u\rVert_{1}+\frac{1}{n}\lVert
Xu\rVert_{2}^{2}\leq\lambda^{2}sC_{\gamma,\tau}(q,s,\lambda,\delta_{0})+4\lambda\sigma_{s}(\beta^{*})_{1}.$
(22)

If
$u\in\mathcal{C}_{SRE}(q,s,c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau})$,
then the $SRE(q,s,c_{0})$ condition implies that

$\displaystyle\lVert u\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}/\sqrt{n}}{\theta_{q}(s,c_{0}(\gamma,\tau))}$
$\displaystyle\leq\frac{1}{\theta_{q}(s,c_{0}(\gamma,\tau))}\sqrt{\lambda^{2}sC_{\gamma,\tau}(q,s,\lambda,\delta_{0})+4\lambda\sigma_{s}(\beta^{*})_{1}}$
$\displaystyle\leq\frac{\sqrt{C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}}{1+\gamma}s^{1/q-1/2}\sqrt{\lambda^{2}sC_{\gamma,\tau}(q,s,\lambda,\delta_{0})+4\lambda\sigma_{s}(\beta^{*})_{1}}$
$\displaystyle\leq\frac{C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q}+\frac{1}{1+\gamma}\left(2\sqrt{\lambda
C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}s^{\frac{1}{2q}}\cdot
s^{\frac{1}{2}(\frac{1}{q}-1)}\sqrt{\sigma_{s}(\beta^{*})_{1}}\right)$
$\displaystyle\leq\frac{C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}{1+\gamma}\lambda
s^{1/q}+\frac{1}{1+\gamma}\left(\lambda
C_{\gamma,\tau}(q,s,\lambda,\delta_{0})s^{1/q}+s^{1/q-1}\sigma_{s}(\beta^{*})_{1}\right)$
$\displaystyle\leq\frac{2}{1+\gamma}\lambda
C_{\gamma,\tau}(q,s,\lambda,\delta_{0})s^{1/q}+\frac{1}{1+\gamma}s^{1/q-1}\sigma_{s}(\beta^{*})_{1}.$
(23)

Otherwise, namely
$u\notin\mathcal{C}_{SRE}(q,s,c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau})$,
by using (11) we have

$\displaystyle\lVert u\rVert_{q}<\frac{1}{1+c_{0}}s^{1/q-1}\lVert u\rVert_{1}$
$\displaystyle<\frac{1-\gamma-\tau}{2}s^{1/q-1}\left(\frac{C_{\gamma,\tau}(q,s,\lambda,\delta_{0})}{2\tau}\lambda
s+\frac{2}{\tau}\sigma_{s}(\beta^{*})_{1}\right)$
$\displaystyle<\frac{1-\gamma-\tau}{4\tau}\lambda
C_{\gamma,\tau}(q,s,\lambda,\delta_{0})s^{1/q}+\frac{1-\gamma-\tau}{\tau}s^{1/q-1}\sigma_{s}(\beta^{*})_{1}.$
(24)

Then, (13) follows immediately from (23) and (24).

By letting $q=2$ in Theorem 1, and adopting the norm interpolation inequality
$\lVert\hat{\beta}-\beta^{*}\rVert_{q}\leq\lVert\hat{\beta}-\beta^{*}\rVert_{1}^{2/q-1}\lVert\hat{\beta}-\beta^{*}\rVert_{2}^{2-2/q}$
for any $1\leq q\leq 2$, we can obtain the following corollary immediately,
which is exactly the Theorem 4.2 in [1].

###### Corollary 1

Under the same conditions of Theorem 1 and for any $1\leq q\leq 2$, then on
the event (6), if $\beta^{*}$ is $s$-sparse, we have

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}\leq\left(\frac{C_{\gamma,\tau}(2,s,\lambda,\delta_{0})}{2\tau}\right)^{2/q-1}\left(\frac{C_{\gamma,0}(2,s,\lambda,\delta_{0})}{1+\gamma}\right)^{2-2/q}\lambda
s^{1/q}.$ (25)

In addition, if we use the particular choice of constants with
$\gamma=\frac{1}{2}$, $\tau=\frac{1}{4}$,
$\delta_{0}=\delta_{0}^{*}=(\delta(\lambda))^{\frac{s}{\theta_{2}^{2}(s,7)}}$
for Corollary 1 while
$\delta_{0}=\delta_{0}^{*}=(\delta(\lambda))^{\frac{s^{2-2/q}}{\theta_{q}^{2}(s,7)}}\leq\left(\frac{s}{2ep}\right)^{\frac{s^{2-2/q}}{\theta_{q}^{2}(s,7)}}$
for Theorem 2, then we are able to derive the Corollary 4.3 in [1] and the
corollary as follows.

###### Corollary 2

Let $s\in\\{1,\cdots,p\\}$. For any $2\leq q\leq\infty$, assume that the
$SRE(q,s,7)$ condition holds. Let $\lambda$ be a tuning parameter such that
(9) holds with $\gamma=1/2$. Then, with probability at least
$1-\frac{1}{2}\left(\frac{s}{2ep}\right)^{\frac{s^{2-2/q}}{\theta_{q}^{2}(s,7)}}$,
the Lasso estimator $\hat{\beta}$ with tuning parameter $\lambda$ satisfies

$\displaystyle\frac{\lambda}{2}\lVert\hat{\beta}-\beta\rVert_{1}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}+\frac{49\lambda^{2}s^{2-2/q}}{16\theta_{q}^{2}(s,7)}+4\lambda\sigma_{s}(\beta)_{1},$

for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$. Furthermore, if
$f=X\beta^{*}$ for some $\beta^{*}$, then with probability at least
$1-\frac{1}{2}\left(\frac{s}{2ep}\right)^{\frac{s^{2-2/q}}{\theta_{q}^{2}(s,7)}}$,
we have

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{1}$
$\displaystyle\leq\frac{49\lambda
s^{2-2/q}}{8\theta_{q}^{2}(s,7)}+8\sigma_{s}(\beta^{*})_{1},$
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{49\lambda
s^{1-1/q}}{24\theta_{q}^{2}(s,7)},\quad(\text{when $\beta^{*}$ is
$s$-sparse})$ $\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{49\lambda
s^{1-1/q}}{12\theta_{q}^{2}(s,7)}+s^{1/q-1}\sigma_{s}(\beta^{*})_{1}.$

##  3 Slope estimator

In this section, we study the Slope estimator $\hat{\beta}$ given as a
solution of the minimization problem (1) with weights

$\displaystyle\lambda_{j}=A\sigma\sqrt{\frac{\log(2p/j)}{n}}$ (26)

for any constant $A>4+\sqrt{2}$. Hereafter, we let
$\Lambda_{q}(s)=\left(\sum_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}$.
We use the following condition on the design matrix $X$ called
$WRE(q,s,c_{0})$ condition with $2\leq q\leq\infty$, which acts as an
extension of the Weighted Restricted Eigenvalue (WRE) condition used in [1].

###### Definition 2

($WRE(q,s,c_{0})$ condition) Let $c_{0}>0$ and $s\in\\{1,2,\cdots,p\\}$. For
any $2\leq q\leq\infty$, the design matrix $X$ satisfies $\lVert
Xe_{j}\rVert_{2}/\sqrt{n}\leq 1$ for all $j=1,\cdots,p$ and

$\displaystyle\nu_{q}(s,c_{0}):=\min\limits_{\delta\neq
0,\delta\in\mathcal{C}_{WRE(q,s,c_{0})}}\frac{\lVert
X\delta\rVert_{2}}{\sqrt{n}\lVert\delta\rVert_{q}}>0,$ (27)

where
$\mathcal{C}_{WRE(q,s,c_{0})}:=\\{\delta\in\mathbb{R}^{p}:\lVert\delta\rVert_{*}\leq(1+c_{0})\lVert\delta\rVert_{q}\Lambda_{q}(s)\\}$
is a cone in $\mathbb{R}^{p}$.

This $WRE(q,s,c_{0})$ condition is defined for any weights
$\lambda_{1}\geq\cdots\geq\lambda_{p}\geq 0$, while we only focus on the
weights given in (26) here. In this case, the cone is equivalently defined as

$\mathcal{C}_{WRE(q,s,c_{0})}:=\left\\{\delta\in\mathbb{R}^{p}:\sum\limits_{j=1}^{p}\delta_{j}^{\sharp}\sqrt{\log(2p/j)}\leq(1+c_{0})\lVert\delta\rVert_{q}\left[\sum\limits_{j=1}^{s}(\sqrt{\log(2p/j)})^{\frac{q}{q-1}}\right]^{1-1/q}\right\\}.$

Thus, if $\delta\in\mathcal{C}_{SRE(q,s,c_{0})}$ (i.e.,
$\lVert\delta\rVert_{1}\leq(1+c_{0})s^{1-1/q}\lVert\delta\rVert_{q}$), we have
$\sum\limits_{j=s+1}^{p}\delta_{j}^{\sharp}\leq(1+c_{0})s^{1-1/q}\lVert\delta\rVert_{q}$
and hence

$\displaystyle\sum\limits_{j=s+1}^{p}\delta_{j}^{\sharp}\sqrt{\log(2p/j)}\leq\sqrt{\log(2p/s)}\sum\limits_{j=s+1}^{p}\delta_{j}^{\sharp}$
$\displaystyle\leq(1+c_{0})\lVert\delta\rVert_{q}s^{1-1/q}\sqrt{\log(2p/s)}$
$\displaystyle\leq(1+c_{0})\lVert\delta\rVert_{q}\left[s\left(\sqrt{\log(2p/s)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}$
$\displaystyle\leq(1+c_{0})\lVert\delta\rVert_{q}\left[\sum\limits_{j=1}^{s}\left(\sqrt{\log(2p/j)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}.$

In addition, the Hölder's inequality implies that

$\sum\limits_{j=1}^{s}\delta_{j}^{\sharp}\sqrt{\log(2p/j)}\leq\lVert\delta\rVert_{q}\left[\sum\limits_{j=1}^{s}\left(\sqrt{\log(2p/j)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}.$

Combining these two statements, we obtain that
$\delta\in\mathcal{C}_{WRE(q,s,1+c_{0})}$, which leads to
$\mathcal{C}_{SRE(q,s,c_{0})}\subseteq\mathcal{C}_{WRE(q,s,1+c_{0})}$.
Therefore, the $WRE(q,s,1+c_{0})$ condition implies the $SRE(q,s,c_{0})$
condition. But the converse is not true, which means that there is no
equivalence between these two conditions. A simple sufficient condition for
$WRE(q,s,c_{0})$ is given in Proposition 3 in Section 4.

Now we are ready to state the main result for the Slope estimator, which acts
as an extension of Theorem 6.1 in [1].

###### Theorem 2

Let $s\in\\{1,\cdots,p\\}$, $\gamma\in(0,1)$ and $\tau\in[0,1-\gamma)$. For
any $2\leq q\leq\infty$, assume that the $WRE(q,s,c_{0})$ condition holds with
$c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau}$. Let the tuning
parameters $\\{\lambda_{j}\\}$ be defined by (26) with constant
$A>(4+\sqrt{2})/\gamma$. Let $\delta_{0}\in(0,1)$. Then, on the event (6), the
Slope estimator $\hat{\beta}$ with tuning parameters $\\{\lambda_{j}\\}$
satisfies

$\displaystyle 2\tau\lVert\hat{\beta}-\beta\rVert_{*}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}+C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta)_{*},$
(28)

for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$, where

$\displaystyle
C^{\prime}_{\gamma,\tau}(q,s,\delta_{0}):=(1+\gamma+\tau)^{2}\left(\frac{\log(1/\delta_{0})}{s\log(2p/s)}\vee\frac{1}{\nu_{q}^{2}(s,c_{0}(\gamma,\tau))}\right).$

Furthermore, if $f=X\beta^{*}$ for some $\beta^{*}$, then on the event (6), we
have

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{*}$
$\displaystyle\leq\frac{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})}{2\tau}\Lambda_{q}^{2}(s)+\frac{2}{\tau}\sigma_{s}(\beta^{*})_{*},$
(29) $\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}{1+\gamma}\Lambda_{q}(s),\quad(\text{when
$\beta^{*}$ is $s$-sparse})$ (30)
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\left(\frac{2}{1+\gamma}\vee\frac{1-\gamma-\tau}{4\tau}\right)C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}(s)+\left(\frac{1}{1+\gamma}\vee\frac{1-\gamma-\tau}{\tau}\right)\Lambda_{q}(s)^{-1}\sigma_{s}(\beta^{*})_{*}.$
(31)

Here, note that since the tuning parameters $\\{\lambda_{j}\\}$ satisfy (26),
so we have

$\displaystyle\Lambda_{q}(s)=\left(\sum_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}\leq
s^{1/2-1/q}\left(\sum\limits_{j=1}^{s}\lambda_{j}^{2}\right)^{1/2}\leq
s^{1/2-1/q}\sqrt{\frac{A^{2}\sigma^{2}s\log(2ep/s)}{n}}=A\sigma
s^{1-1/q}\sqrt{\frac{\log(2ep/s)}{n}}.$ (32)

Proof. The proof follows the same route as the Proof of Theorem 1 with some
careful modifications. Adopting (5) with $h=2\lVert\cdot\rVert_{*}$, we have
for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$,

$\displaystyle 2\tau\lVert\hat{\beta}-\beta\rVert_{*}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}-\frac{1}{n}\lVert
X(\hat{\beta}-\beta)\rVert_{2}^{2}+\Delta^{*},$ (33)

where
$\Delta^{*}=2\tau\lVert\hat{\beta}-\beta\rVert_{*}+\frac{2}{n}\xi^{T}X(\hat{\beta}-\beta)+2\lVert\beta\rVert_{*}-2\lVert\hat{\beta}\rVert_{*}$.
Let $u=\hat{\beta}-\beta$, then on the event (6), Lemma 1 implies that

$\displaystyle\Delta^{*}$ $\displaystyle\leq
2(\tau\lVert\hat{\beta}-\beta\rVert_{*}+\lVert\beta\rVert_{*}-\lVert\hat{\beta}\rVert_{*})+2\max(\tilde{H}(u),G(u))$
$\displaystyle\leq 2\left((1+\tau)\lVert
u\rVert_{q}\Lambda_{q}(s)-(1-\tau)\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{*}\right)+2\max(\tilde{H}(u),G(u)).$

(i) If $\tilde{H}(u)\leq G(u)$, then the definitions of $\tilde{H}(u)$ and
$G(u)$ yield

$\displaystyle\lVert
u\rVert_{q}\leq\frac{G(u)}{\frac{4+\sqrt{2}}{\sqrt{n}}\sigma\left[\sum\limits_{j=1}^{s}\left(\sqrt{\log(2p/j)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}}\leq\frac{G(u)}{\frac{4+\sqrt{2}}{\sqrt{n}}\sigma\sqrt{\sum\limits_{j=1}^{s}\log(2p/j)}}$
$\displaystyle\leq\frac{G(u)}{\frac{4+\sqrt{2}}{\sqrt{n}}\sigma\sqrt{s\log(2p/s)}}$
$\displaystyle\leq\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}},$

where we use the facts that $q\in[2,\infty]$ and
$\sum\limits_{j=1}^{s}\log(2p/j)\geq s\log(2p/s)$. In addition, the setting of
weights leads to

$\displaystyle
G(u)\leq\gamma\Lambda_{2}(s)\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}}\leq\gamma\Lambda_{q}(s)\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}},$ (34)

since $\Lambda_{2}(s)\leq\Lambda_{q}(s)$ for any $q\in[2,\infty]$. Therefore,
we obtain that

$\displaystyle\Delta^{*}$ $\displaystyle\leq 2(1+\tau)\lVert
u\rVert_{q}\Lambda_{q}(s)+4\sigma_{s}(\beta)_{*}+2G(u)$ $\displaystyle\leq
2(1+\gamma+\tau)\Lambda_{q}(s)\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}}+4\sigma_{s}(\beta)_{*}$
$\displaystyle\leq(1+\gamma+\tau)^{2}\Lambda_{q}^{2}(s)\frac{\log(1/\delta_{0})}{s\log(2p/s)}+\frac{\lVert
Xu\rVert_{2}^{2}}{n}+4\sigma_{s}(\beta)_{*}.$

(ii) If $\tilde{H}(u)>G(u)$, in which case $\tilde{H}(u)\leq\gamma(\lVert
u\rVert_{q}\Lambda_{q}(s)+\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp})$,
then we have

$\displaystyle\Delta^{*}$ $\displaystyle\leq 2\left((1+\tau)\lVert
u\rVert_{q}\Lambda_{q}(s)-(1-\tau)\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}+2\sigma_{s}(\beta)_{*}\right)+2\tilde{H}(u)$
$\displaystyle\leq\underbrace{2(1+\gamma+\tau)\lVert
u\rVert_{q}\Lambda_{q}(s)-2(1-\gamma-\tau)\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}}_{\Delta}+4\sigma_{s}(\beta)_{*}.$

If $\Delta\leq 0$, then the statement (28) holds trivially in view of (33). If
$\Delta>0$, then
$\sum\limits_{j=s+1}^{p}\lambda_{j}u_{j}^{\sharp}\leq\frac{1+\gamma+\tau}{1-\gamma-\tau}\lVert
u\rVert_{q}\Lambda_{q}(s)$. Furthermore, as a result of
$\sum\limits_{j=1}^{s}\lambda_{j}u_{j}^{\sharp}\leq\lVert
u\rVert_{q}\Lambda_{q}(s)$, it holds that

$\displaystyle\lVert
u\rVert_{*}=\sum\limits_{j=1}^{p}\lambda_{j}u_{j}^{\sharp}\leq(1+\frac{1+\gamma+\tau}{1-\gamma-\tau})\lVert
u\rVert_{q}\Lambda_{q}(s)=(1+c_{0})\lVert u\rVert_{q}\Lambda_{q}(s).$

Hence, $u$ belongs to the cone $C_{WRE}(q,s,c_{0})$. Then by using the
$WRE(q,s,c_{0})$ condition we have

$\displaystyle\Delta^{*}\leq\Delta+4\sigma_{s}(\beta)_{*}$ $\displaystyle\leq
2(1+\gamma+\tau)\lVert u\rVert_{q}\Lambda_{q}(s)+4\sigma_{s}(\beta)_{*}$
$\displaystyle\leq\frac{2(1+\tau+\gamma)\Lambda_{q}(s)\lVert
Xu\rVert_{2}/\sqrt{n}}{\nu_{q}(s,c_{0})}+4\sigma_{s}(\beta)_{*}$
$\displaystyle\leq\frac{(1+\tau+\gamma)^{2}\Lambda_{q}^{2}(s)}{\nu_{q}^{2}(s,c_{0})}+\frac{\lVert
Xu\rVert_{2}^{2}}{n}+4\sigma_{s}(\beta)_{*}.$

Consequently, for both cases it holds that
$\Delta^{*}\leq\underbrace{(1+\gamma+\tau)^{2}\left(\frac{\log(1/\delta_{0})}{s\log(2p/s)}\vee\frac{1}{\nu_{q}^{2}(s,c_{0}(\gamma,\tau))}\right)}_{C^{\prime}_{\gamma,\tau}(q,s,c_{0})}\Lambda_{q}^{2}(s)+\frac{\lVert
Xu\rVert_{2}^{2}}{n}+4\sigma_{s}(\beta)_{*}$, which implies that

$\displaystyle 2\tau\lVert\hat{\beta}-\beta\rVert_{*}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}+C^{\prime}_{\gamma,\tau}(q,s,c_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta)_{*}$
(35)

for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$. The proof of
(28) is completed.

To prove (29), let $f=X\beta^{*}$ and $\beta=\beta^{*}$ in (28), we
immediately obtain that

$\displaystyle 2\tau\lVert\hat{\beta}-\beta^{*}\rVert_{*}\leq
2\tau\lVert\hat{\beta}-\beta^{*}\rVert_{*}+\frac{1}{n}\lVert
X(\hat{\beta}-\beta^{*})\rVert_{2}^{2}\leq
C^{\prime}_{\gamma,\tau}(q,s,c_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta)_{*}.$

As for (30), when $\beta^{*}$ is $s$-sparse (i.e.,
$\sigma_{s}(\beta^{*})_{*}=0$), we set in what follows
$u=\hat{\beta}-\beta^{*}$, $\tau=0$ so that $c_{0}=\frac{1+\gamma}{1-\gamma}$
and consider the same two Cases as above.

(i) If $\tilde{H}(u)\leq G(u)$, then it is derived from

$\displaystyle\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta^{*}-f\rVert_{2}^{2}-\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}+\Delta^{*},$ (36)

that

$\displaystyle\frac{1}{n}\lVert Xu\rVert_{2}^{2}=\frac{1}{n}\lVert
X(\hat{\beta}-\beta^{*})\rVert_{2}^{2}\leq(1+\gamma)^{2}\Lambda_{q}^{2}(s)\left(\frac{\log(1/\delta_{0})}{s\log(2p/s)}\right).$

Combining this inequality and the fact that

$\displaystyle\lVert
u\rVert_{q}\leq\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}},$

we get

$\displaystyle\lVert u\rVert_{q}$
$\displaystyle\leq\sqrt{\frac{\log(1/\delta_{0})}{s\log(2p/s)}}\cdot\sqrt{(1+\gamma)^{2}\Lambda_{q}^{2}(s)\left(\frac{\log(1/\delta_{0})}{s\log(2p/s)}\right)}$
$\displaystyle\leq\sqrt{\frac{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}{(1+\gamma)^{2}}}\sqrt{(1+\gamma)^{2}\Lambda_{q}^{2}(s)\frac{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}{(1+\gamma)^{2}}}=\frac{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}{1+\gamma}\Lambda_{q}(s).$

(ii) If $\tilde{H}(u)>G(u)$, then $\Delta\geq\Delta^{*}$. It follows from (36)
with $\beta=\beta^{*}$ and $f=X\beta^{*}$ that
$\Delta^{*}\geq\frac{2}{n}\lVert Xu\rVert_{2}^{2}$. Thus $\Delta\geq 0$, which
implies that $u$ belongs to the cone $C_{WRE}(q,s,\frac{1+\gamma}{1-\gamma})$.
By applying the $WRE(q,s,\frac{1+\gamma}{1-\gamma})$ condition, we obtain that

$\displaystyle\lVert u\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}\nu_{q}(s,\frac{1+\gamma}{1-\gamma})}.$

Combining this bound and the fact that

$\displaystyle\frac{1}{n}\lVert
Xu\rVert_{2}^{2}\leq\frac{(1+\gamma)^{2}\Lambda_{q}^{2}(s)}{\nu_{q}^{2}(s,\frac{1+\gamma}{1-\gamma})},$

we have

$\displaystyle\lVert u\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}}{\sqrt{n}\nu_{q}(s,\frac{1+\gamma}{1-\gamma})}$
$\displaystyle\leq\frac{1}{\nu_{q}(s,\frac{1+\gamma}{1-\gamma})}\sqrt{\frac{(1+\gamma)^{2}\Lambda_{q}^{2}(s)}{\nu_{q}^{2}(s,\frac{1+\gamma}{1-\gamma})}}\leq\frac{\sqrt{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}}{1+\gamma}\sqrt{C^{\prime}_{\gamma,0}(q,s,\delta_{0})\Lambda_{q}^{2}(s)}=\frac{C^{\prime}_{\gamma,0}(q,s,\delta_{0})}{1+\gamma}\Lambda_{q}(s),$

which completes the proof of (30).

Finally, regarding the result (31) that allows $\beta^{*}$ to be not exactly
sparse, we let $f=X\beta^{*}$, $\beta=\beta^{*}$ and $u=\hat{\beta}-\beta^{*}$
in (28) and obtain

$\displaystyle 2\tau\lVert u\rVert_{*}+\frac{1}{n}\lVert Xu\rVert_{2}^{2}\leq
C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta^{*})_{*}.$
(37)

Then, if
$u\in\mathcal{C}_{WRE}(q,s,c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau})$,
the $WRE(q,s,c_{0})$ condition implies that

$\displaystyle\lVert u\rVert_{q}\leq\frac{\lVert
Xu\rVert_{2}/\sqrt{n}}{\nu_{q}(s,c_{0}(\gamma,\tau))}$
$\displaystyle\leq\frac{1}{\nu_{q}(s,c_{0}(\gamma,\tau))}\sqrt{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta)_{*}}$
$\displaystyle\leq\frac{\sqrt{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})}}{1+\gamma}\sqrt{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}^{2}(s)+4\sigma_{s}(\beta)_{*}}$
$\displaystyle\leq\frac{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})}{1+\gamma}\Lambda_{q}(s)+\frac{1}{1+\gamma}\left(2\sqrt{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}(s)}\cdot\Lambda_{q}(s)^{-1/2}\sqrt{\sigma_{s}(\beta^{*})_{*}}\right)$
$\displaystyle\leq\frac{2}{1+\gamma}C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}(s)+\frac{1}{1+\gamma}\Lambda_{q}(s)^{-1}\sigma_{s}(\beta^{*})_{*}.$
(38)

Otherwise, if
$u\notin\mathcal{C}_{WRE}(q,s,c_{0}=c_{0}(\gamma,\tau)=\frac{1+\gamma+\tau}{1-\gamma-\tau})$,
then by using (29) we have

$\displaystyle\lVert u\rVert_{q}<\frac{1}{1+c_{0}}\Lambda_{q}(s)^{-1}\lVert
u\rVert_{*}$
$\displaystyle<\frac{1-\gamma-\tau}{2}\Lambda_{q}(s)^{-1}\left(\frac{C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})}{2\tau}\Lambda_{q}^{2}(s)+\frac{2}{\tau}\sigma_{s}(\beta^{*})_{*}\right)$
$\displaystyle<\frac{1-\gamma-\tau}{4\tau}C^{\prime}_{\gamma,\tau}(q,s,\delta_{0})\Lambda_{q}(s)+\frac{1-\gamma-\tau}{\tau}\Lambda_{q}(s)^{-1}\sigma_{s}(\beta^{*})_{*}.$
(39)

As a consequence, (31) holds due to (38) and (39).

With $\gamma=1/2$, $\tau=1/4$ and
$\delta_{0}=(\frac{s}{2p})^{\frac{s}{\nu_{q}^{2}(s,7)}}$, it is
straightforward to get the following corollary.

###### Corollary 3

Let $s\in\\{1,\cdots,p\\}$. For any $2\leq q\leq\infty$, assume that the
$WRE(q,s,7)$ condition holds. Let the tuning parameters $\\{\lambda_{j}\\}$ be
defined by (26) with constant $A>2(4+\sqrt{2})$. Then, with probability at
least $1-\frac{1}{2}(\frac{s}{2p})^{\frac{s}{\nu_{q}^{2}(s,7)}}$, the Slope
estimator $\hat{\beta}$ with tuning parameters $\\{\lambda_{j}\\}$ satisfies

$\displaystyle\frac{1}{2}\lVert\hat{\beta}-\beta\rVert_{*}+\frac{1}{n}\lVert
X\hat{\beta}-f\rVert_{2}^{2}\leq\frac{1}{n}\lVert
X\beta-f\rVert_{2}^{2}+\frac{49\Lambda_{q}^{2}(s)}{16\nu_{q}^{2}(s,7)}+4\sigma_{s}(\beta)_{*},$

for all $\beta\in\mathbb{R}^{p}$ and all $f\in\mathbb{R}^{n}$. Furthermore, if
$f=X\beta^{*}$ for some $\beta^{*}$, then with probability at least
$1-\frac{1}{2}(\frac{s}{2p})^{\frac{s}{\nu_{q}^{2}(s,7)}}$, we have

$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{*}$
$\displaystyle\leq\frac{49\Lambda_{q}^{2}(s)}{8\nu_{q}^{2}(s,7)}+8\sigma_{s}(\beta^{*})_{*},$
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{49\Lambda_{q}(s)}{24\nu_{q}^{2}(s,7)},\quad(\text{when
$\beta^{*}$ is $s$-sparse})$
$\displaystyle\lVert\hat{\beta}-\beta^{*}\rVert_{q}$
$\displaystyle\leq\frac{49\Lambda_{q}(s)}{12\nu_{q}^{2}(s,7)}+\Lambda_{q}(s)^{-1}\sigma_{s}(\beta^{*})_{*}.$

##  4 Matching Lower Bounds

In this section, we move on to discuss the lower bounds for the $\ell_{q}$
estimation error over both the $\ell_{0}$-ball
$B_{0}(s):=\\{\beta\in\mathbb{R}^{p}:\lVert\beta\rVert_{0}\leq s\\}$ and the
$\ell_{r}$-balls
$B_{r}(R_{r}):=\\{\beta\in\mathbb{R}^{p}:\lVert\beta\rVert_{r}^{r}=\sum_{j=1}^{p}|\beta_{j}|^{r}\leq
R_{r}\\}$ with $0<r<1$.

###  4.1 Over the $\ell_{0}$-ball

In what follows, we borrow the main result from Section 7 in [1]. Let us
introduce the maximal $s$-sparse eigenvalue of the design matrix $X$ defined
as

$\displaystyle\bar{\theta}_{\mathrm{max}}(X,s)=\max\limits_{\delta\in
B_{0}(s)\setminus\\{0\\}}\frac{\lVert
X\delta\rVert_{2}}{\sqrt{n}\lVert\delta\rVert_{2}},$ (40)

with $\bar{\theta}_{\mathrm{max}}(X,1)=\max_{j=1,\cdots,p}\lVert
Xe_{j}\rVert_{2}/\sqrt{n}$, and $\psi_{n,q}=\sigma
s^{1/q}\sqrt{\frac{\log(ep/s)}{n}}$ for any $1\leq q\leq\infty$. Then,
according to Theorem 7.1 of [1], we have the following lemma, which
establishes the minimax lower bound for the $\ell_{q}$ estimation error over
the $\ell_{0}$-ball $B_{0}(s)$ for any design matrix $X$.

###### Lemma 4

Let $p\geq 2$, $s\in[1,p/2]$, $n\geq 1$ be integers and $1\leq q\leq\infty$.
Assume that $y=X\beta^{*}+\xi$ with $\xi\in\mathbb{R}^{n}\sim
N(0,\sigma^{2}I_{n\times n})$, $\sigma>0$. Then it holds that there exist
positive constants $\bar{b},\bar{c}$ depending on $q$ such that

$\displaystyle\inf\limits_{\hat{\tau}}\inf\limits_{X}\sup\limits_{\beta^{*}\in
B_{0}(s)}P\Big{(}\lVert\hat{\tau}-\beta^{*}\rVert_{q}\geq\psi_{n,q}\bar{b}^{-1}\bar{\theta}_{\mathrm{max}}^{-1}(X,1)\Big{)}\geq\bar{c},$
(41)

where $\inf_{\hat{\tau}}$ denotes the infimum over all estimators $\hat{\tau}$
of $\beta^{*}$ and $\inf_{X}$ denotes the infimum over all matrices
$X\in\mathbb{R}^{n\times p}$.

Hence, when the true parameter vector $\beta^{*}$ is exactly $s$-sparse, the
upper bounds for the Lasso and Slope estimators obtained in the previous
sections show that both the Lasso estimator with a tuning parameter of order
$\sqrt{\log(p/s)/n}$ and the Slope estimator with weights defined by (26)
achieve the minimax optimal rate $\sqrt{s\log(p/s)/n}$ for the $\ell_{2}$
estimation error. In fact, the Lasso estimator with a tuning parameter of
order $\sqrt{\log(p/s)/n}$ achieves the minimax optimal rate
$s^{1/q}\sqrt{\log(p/s)/n}$ for the $\ell_{q}$ estimation error with $1\leq
q\leq 2$, while a near-optimal rate $s^{1-1/q}\sqrt{\log(p/s)/n}$ for the
$\ell_{q}$ estimation error with $2<q\leq\infty$. The Slope estimator with
weights defined by (26) achieves the near-optimal rate
$s^{1-1/q}\sqrt{\log(p/s)/n}$ for the $\ell_{q}$ estimation error with
$2<q\leq\infty$ as well.

###  4.2 Over the $\ell_{r}$-balls

As shown in the following proposition, when the true parameter vector
$\beta^{*}$ is not exactly sparse, the error of its best $s$-term
approximation with respect to $\lVert\cdot\rVert_{*}$ can be well controlled
by its $\ell_{r}$ norms with $0<r<1$ so that the non-convex $\ell_{r}$-balls
$B_{r}(R_{r})$ serve as good models for vectors that are not exactly sparse.

###### Proposition 1

For any $s\in\\{1,\cdots,p\\}$,
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{p}\geq 0$, $0<r<1$ and
$\beta\in\mathbb{R}^{p}$,

$\displaystyle\sigma_{s}(\beta)_{*}\leq\lambda_{s}\cdot
s^{\frac{r}{1-r}}\lVert\beta\rVert_{r}.$ (42)

In particular, if $\lambda_{1}=\lambda_{2}=\cdots=\lambda_{p}=\lambda$ for
some $\lambda>0$, then $\sigma_{s}(\beta)_{*}=\lambda\sigma_{s}(\beta)_{1}$,
and we have

$\displaystyle\sigma_{s}(\beta)_{1}\leq
s^{\frac{r}{1-r}}\lVert\beta\rVert_{r}.$ (43)

Proof. Based on the definition of $\sigma_{s}(\beta)_{*}$, we have

$\displaystyle\sigma_{s}(\beta)_{*}=\sum\limits_{j=s+1}^{p}\lambda_{j}\beta_{j}^{\sharp}$
$\displaystyle\leq(\beta_{s}^{\sharp})^{1-r}\sum\limits_{j=s+1}^{p}\lambda_{j}(\beta_{j}^{\sharp})^{r}$
$\displaystyle\leq\left(\frac{1}{s}\sum\limits_{j=1}^{s}(\beta_{j}^{\sharp})^{r}\right)^{\frac{1-r}{r}}\cdot\sum\limits_{j=s+1}^{p}\lambda_{j}(\beta_{j}^{\sharp})^{r}$
$\displaystyle\leq\left(\frac{1}{s}\lVert\beta\rVert_{r}^{r}\right)^{\frac{1-r}{r}}\cdot\lambda_{s}\lVert\beta\rVert_{r}^{r}$
$\displaystyle\leq\lambda_{s}\cdot s^{\frac{r}{1-r}}\lVert\beta\rVert_{r},$

which completes the proof.

Unfortunately, how to generalize Lemma 4 mentioned above and thus obtain the
non-asymptotic minimax lower bound for the $\ell_{q}$ estimation error with
general $1\leq q\leq\infty$ and for any design matrix $X$ over the
$\ell_{r}$-balls remains open. The corresponding discussion is left for future
work.

##  5 Restricted Eigenvalue Conditions

In this section, we study the relationships between the proposed RE
conditions.

###### Proposition 2

Let $c_{0}>0$ and $s\in\\{1,\cdots,p\\}$. For any $q\in[2,\infty]$ we have if
condition $SRE(s^{\frac{2(q-1)}{q}},c_{0})$ holds, then condition
$SRE(q,s,c_{0})$ holds and
$\theta_{q}(s,c_{0})\geq\theta(s^{\frac{2(q-1)}{q}},c_{0})$.

Proof. For any $q\in[2,\infty]$, the cone $\mathcal{C}_{SRE(q,s,c_{0})}$ of
the $SRE(q,s,c_{0})$ is the set of all non-zero $\delta\in\mathbb{R}^{p}$ such
that $\lVert\delta\rVert_{1}\leq(1+c_{0})s^{1-1/q}\lVert\delta\rVert_{q}$. By
using the fact that $\lVert\delta\rVert_{q}\leq\lVert\delta\rVert_{2}$, we
have
$\lVert\delta\rVert_{1}\leq(1+c_{0})\sqrt{s^{2-2/q}}\lVert\delta\rVert_{2}$,
so that
$\mathcal{C}_{SRE(q,s,c_{0})}\subseteq\mathcal{C}_{SRE(s^{2-2/q},c_{0})}$. As
a consequence,

$\displaystyle\theta_{q}(s,c_{0}):=\min\limits_{\delta\neq
0,\delta\in\mathcal{C}_{SRE(q,s,c_{0})}}\frac{\lVert
X\delta\rVert_{2}}{\sqrt{n}\lVert\delta\rVert_{q}}\geq\min\limits_{\delta\neq
0,\delta\in\mathcal{C}_{SRE(s^{2-2/q},c_{0})}}\frac{\lVert
X\delta\rVert_{2}}{\sqrt{n}\lVert\delta\rVert_{2}}\cdot\frac{\lVert\delta\rVert_{2}}{\lVert\delta\rVert_{q}}\geq\theta(s^{\frac{2(q-1)}{q}},c_{0}).$

Hence, based on this proposition and the results in [1] for the $SRE(s,c_{0})$
condition, we can conclude that for a large class of random matrices with
i.i.d. rows, the $SRE(q,s,c_{0})$ condition holds with high probability when
$s^{\frac{2(q-1)}{q}}\log(ep/s)\leq cn$ with $c>0$ being a constant. In
addition, by using the following proposition we are able to obtain that the
$WRE(q,s,c_{0})$ holds with high probability whenever
$s^{\frac{2(q-1)}{q}}\log^{2}(ep/s)\leq Cn$ with $C>0$ being some constant.

###### Proposition 3

Let $c_{0}>0$, $s\in\\{1,\cdots,p\\}$ and $s_{q}=\lceil
s\left(\sqrt{\log(2ep/s)/\log 2}\right)^{\frac{q}{q-1}}\rceil$. For any
$q\in[2,\infty]$ we have if condition $SRE(q,s_{q},c_{0})$ holds, then
condition $WRE(q,s,c_{0})$ holds and
$\nu_{q}(s,c_{0})\geq\theta_{q}(s_{q},c_{0})$.

Proof. If $\delta\in\mathcal{C}_{WRE(q,s,c_{0})}$, then

$\displaystyle(1+c_{0})\left(\sum\limits_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}\lVert\delta\rVert_{q}\geq\lVert\delta\rVert_{*}=\sum\limits_{j=1}^{p}\lambda_{j}\delta_{j}^{\sharp}\geq\lambda_{p}\sum\limits_{j=1}^{p}\delta_{j}^{\sharp}=\lambda_{p}\lVert\delta\rVert_{1}=\frac{A\sigma}{\sqrt{n}}\sqrt{\log{2}}\lVert\delta\rVert_{1}.$

Meanwhile,
$\left(\sum\limits_{j=1}^{s}\lambda_{j}^{\frac{q}{q-1}}\right)^{1-1/q}\leq
s^{1/2-1/q}\left(\sum\limits_{j=1}^{s}\lambda_{j}^{2}\right)^{1/2}\leq\frac{A\sigma}{\sqrt{n}}s^{1/2-1/q}\sqrt{s\log(2ep/s)}=\frac{A\sigma}{\sqrt{n}}\left[s\left(\sqrt{\log(2ep/s)}\right)^{\frac{q}{q-1}}\right]^{1-1/q}$.
Thus, we have
$\lVert\delta\rVert_{1}\leq(1+c_{0})\left[s\left(\sqrt{\log(2ep/s)/\log
2}\right)^{\frac{q}{q-1}}\right]^{1-1/q}\lVert\delta\rVert_{q}$ and
$\delta\in\mathcal{C}_{SRE(q,s_{q},c_{0})}$, which implies that
$\mathcal{C}_{WRE(q,s,c_{0})}\subseteq\mathcal{C}_{SRE(q,s_{q},c_{0})}$ and
completes the proof.

##  6 Conclusion

In this paper, we have generalized the sharp results for the Lasso and the
Slope estimators in [1] to allow the case that the true parameter vector is
not exactly sparse, and obtained the results for any $q\in[1,\infty]$ by using
the corresponding extended Restricted Eigenvalue conditions. What we have done
could be further developed to other Slope type estimators including the
Square-Root Slope [6], the Group Slope [4] and the Sorted Concave Penalized
estimator [7], which are left for future works.

## References

  * [1] Bellec, P.C., Lecué, G., & Tsybakov, A.B. (2018). Slope meets lasso: improved oracle bounds and optimality.  Annals of Statistics, 46(6B), 3603-3642.
  * [2] Bickel, P.J., Ritov, Y.A., & Tsybakov, A.B. (2009). Simultaneous analysis of Lasso and Dantzig selector. Annals of Statistics, 37(4), 1705-1732.
  * [3] Bogdan, M., Van Den Berg, E., Sabatti, C., Su, W., & Candès, E.J. (2015). SLOPE—adaptive variable selection via convex optimization. Annals of Applied Statistics, 9(3), 1103.
  * [4] Brzyski, D., Gossmann, A., Su, W., & Bogdan, M. (2019). Group slope–adaptive selection of groups of predictors. Journal of the American Statistical Association, 114(525), 419-433.
  * [5] Bühlmann, P., & Van De Geer, S. (2011). Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media.
  * [6] Derumigny, A. (2018). Improved bounds for square-root lasso and square-root slope. Electronic Journal of Statistics, 12(1), 741-766.
  * [7] Feng, L., & Zhang, C. H. (2019). Sorted concave penalized regression. Annals of Statistics, 47(6), 3069-3098.
  * [8] Lecué, G., & Mendelson, S. (2018). Regularization and the small-ball method i: sparse recovery. Annals of Statistics, 46(2), 611-641.
  * [9] Raskutti, G., Wainwright, M.J., & Yu, B. (2011). Minimax rates of estimation for high-dimensional linear regression over $\ell_{q}$-balls. IEEE Transactions on Information Theory, 57(10), 6976-6994.
  * [10] Su, W., & Candes, E. (2016). SLOPE is adaptive to unknown sparsity and asymptotically minimax. Annals of Statistics, 44(3), 1038-1068.
  * [11] Tang, G., & Nehorai, A. (2011). Performance analysis of sparse recovery based on constrained minimal singular values. IEEE Transactions on Signal Processing, 59(12), 5734-5745.
  * [12] Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1), 267-288.
  * [13] Zhou, Z., & Yu, J. (2019). Sparse recovery based on $q$-ratio constrained minimal singular values. Signal Processing, 155, 247-258.
  * [14] Zhou, Z., & Yu, J. (2019). On $q$-ratio CMSV for sparse recovery. Signal Processing, 165, 128-132.


# A Semantic Segmentation Network for Urban-Scale Building Footprint
Extraction Using RGB Satellite Imagery

Aatif Jiwani
UC Berkeley
Lawrence Berkeley Lab
<EMAIL_ADDRESS>Shubhrakanti Ganguly
UC Berkeley
Lawrence Berkeley Lab
<EMAIL_ADDRESS>Chao Ding
Lawrence Berkeley Lab
<EMAIL_ADDRESS>Corresponding Author: Please send correspondance to
<EMAIL_ADDRESS>Nan Zhou
Lawrence Berkeley Lab
<EMAIL_ADDRESS>David Chan
UC Berkeley
<EMAIL_ADDRESS>
###### Abstract

Urban areas consume over two-thirds of the world’s energy and account for more
than 70% of global $CO_{2}$ emissions. As stated in IPCC’s Global Warming of
1.5 ºC report, achieving carbon neutrality by 2050 requires a clear
understanding of urban geometry. High-quality building footprint generation
from satellite images can accelerate this predictive process and empower
municipal decision-making at scale. However, previous Deep Learning-based
approaches face consequential issues such as scale invariance and defective
footprints, partly due to ever-present class-wise imbalance. Additionally,
most approaches require supplemental data such as point cloud data, building
height information, and multi-band imagery - which has limited availability
and are tedious to produce. In this paper, we propose a modified DeeplabV3+
module with a Dilated Res-Net backbone to generate masks of building
footprints from three-channel RGB satellite imagery only. Furthermore, we
introduce an F-Beta measure in our objective function to help the model
account for skewed class distributions and prevent false-positive footprints.
In addition to F-Beta, we incorporate an exponentially weighted boundary loss
and use a cross-dataset training strategy to further increase the quality of
predictions. As a result, we achieve state-of-the-art performances across
three public benchmarks and demonstrate that our RGB-only method produces
higher quality visual results and is agnostic to the scale, resolution, and
urban density of satellite imagery.111Code is publicly available at
https://github.com/aatifjiwani/rgb-footprint-extract/.

##  1 Introduction

Figure 1: Left: Visualizations of samples from each dataset used in this paper
(see Section 4.1 for details). Right: Visualizations of weighted boundary maps
($w_{0}=10$, $\sigma=7.5$).

Urban centers consume over two-thirds of the world’s energy and account for
more than 70 percent of global $CO_{2}$ emissions. Achieving carbon neutrality
by 2050, as stated in IPCC’s Global Warming of 1.5°C report [1], will require
a good understanding of the urban geometry at speed and scale [25]. Automatic
building footprint extraction from satellite imagery is currently being
pursued to support many urban science applications, such as urban planning,
energy efficiency, micro-climate modeling and emergency response [10, 9, 5].
Furthermore, in high-density urban regions where buildings are often close to
one another, an accurate distinction of adjacent buildings is required to
provide any meaningful support to architects and urban planners. However,
although building footprint extraction has received attention from the Deep
Learning community [24, 30, 12, 19, 7, 34, 2], approaches based on
convolutional neural networks (CNN) continue to face prominent issues such as
scale invariance and defective footprints. Building density and resolution can
vary significantly among satellite imagery, as can be seen in Figure 1,
presenting class imbalances that make it difficult for a CNN to be robust on
unseen data. Consequently, CNN-based approaches commonly suffer from sparse
false positives and adjacent footprints being predicted as a single entity,
drastically reducing the level of insight urban planners can glean from
results.

The Deep Learning community has made many approaches that attempt to resolve
conjoined and extraneous footprints, however, most approaches require
supplemental data such as point clouds, building height information, and
multi-band imagery - all of which are too expensive to produce or unattainable
for most cities worldwide. Contrary to these methods, we propose a novel
method that relies on easily attainable and globally available RGB satellite
images. In the following sections, we present a modified DeepLabV3+
architecture and unique two-part training objective, and demonstrate that our
method not only performs better in numerical performance, but also produces
cleaner footprint predictions and precisely separates buildings in densely
populated areas.

##  2 Related Work

###  2.1 Deep Learning and Building Segmentation

Building segmentation in remote sensing has long been established as an
important task in urban planning, inviting robust non-Deep Learning approaches
such as LIDAR reconstruction [14]. However, with processing power becoming
progressively cheaper and more accessible, Deep Learning approaches for this
task are becoming increasingly prominent and successful. Li _et al_. [19]
tackle urban building segmentation with a U-Net ensemble and attempt to
resolve the scale invariance problem by splitting their ensemble into two
sets: one receives a downsampled copy, and the other receives a stack of 9
equal sections from the original image. Delassus _et al_. [7] also use a U-Net
ensemble, but move in a different direction and attempt to separate footprints
by employing the DICE Coefficient [29, 8]. In our work, we demonstrate that
replacing the DICE Coefficient with the F-Beta measure has numerical and
visual benefits. Marmanis _et al_. [23] employ a simple multi-layer
perceptron, and attempt to separate conjoined footprints by framing the task
as a three-class classification problem. Similarly, Yang _et al_. [31] employ
a SegNet [3] and developed a signed-distance function to encode relative
distances between buildings within ground-truth masks. Using the distance
function, they transform the binary masks into masks with 128 classes wherein
pixels that are closer to buildings have a higher class than pixels that are
generally background. Inspired by these approaches, in our work we introduce
an exponentially weighted boundary loss to our objective that heavily
penalizes incorrect boundary predictions to achieve better separation of
buildings in close proximity. Instead of manipulating the objective, Zorzi _et
al_. [35] propose a pipeline that performs regularization and polygonization
on segmentation masks to produce clear-cut footprints. Unlike any of the
previous approaches, [35] employ generative adversarial networks with the
intention of cleaning up segmented masks before polygonization [13]. However,
as Zorzi _et al_. note, this method often hinders performance when buildings
are occluded by the presence of greenery, creating skewed footprints that do
not properly overlap with the ground-truth.

###  2.2 Loss Functions for Data Imbalance

Class-wise imbalance in the data is a tough problem that presents itself in
multifarious tasks, but we crucially highlight its presence in object
detection and image segmentation. In object detection, there is an inherent
imbalance as foreground objects are often just a small fraction of the full
image. Lin _et al_. [20] address the difficulty of training object detectors
with the Focal loss. Commonly applied in object detection tasks, the Focal
loss builds upon binary Cross-Entropy by adding a tunable factor that
effectively puts more emphasis on penalizing misclassifications by shifting
focus away from the common class. However, the Focal loss presupposes the
common class is unimportant, which does not translate well to building
segmentation as we observed copious false positives footprints. In binary
image segmentation, the common problem of class imbalance poses a downstream
problem for either precision or recall. Salehi _et al_. [28] developed the
Tversky index to shift the network’s focus on resolving false negatives. The
Tversky index, based upon the DICE coefficient [29, 8], is an ornate function
of the predicted and ground-truth masks with tunable weights $\alpha$ and
$\beta$ that shift emphasis towards precision and recall respectively.
Compared to [20] and [28], we introduce the F-Beta measure which requires only
a single parameter $\beta$ to analogously shift focus towards precision or
recall while not losing sight of the common class. Finally, Kervadec _et al_.
[18] proposed a distance-function-based boundary loss to resolve imbalances in
brain scans. While [18] have shown they improved the visual quality of
results, the issue of separating distinct entities remains extant. In this
work, we introduce a boundary loss aimed to ameliorate the separation of
distinct ground-truth footprints.

##  3 Approach

We propose a network architecture and training method closely modeled on [19]
and [7], however, with several major alterations to account for the strict use
of RGB imagery:

  1. 1.

We replace the U-Net encoder-decoder model with a DeepLabV3+ module [4].

  2. 2.

We swap the Aligned Xception model in the DeepLabV3+ with a Dilated ResNet
[32].

  3. 3.

We generalize the DICE loss to an F-Beta Measure and add an exponentially
weighted boundary loss to create a unique two-part training objective.

  4. 4.

We perform cross-dataset training to optimize performance on multiple
datasets.

We depict our overall training pipeline in Figure 2 and compare it side-by-
side against the default DeepLabV3+ module.

Figure 2: Left:  DeepLabV3+ Module as depicted by [4]. Right:  Training
pipeline depicting our modified semantic segmentation network.

###  3.1 Modified DeepLabV3+ Network

In our work, we found that for RGB data, as opposed to wideband satellite
imagery, the DeepLabV3+ architecture outperformed the U-Net based method. We
hypothesize that this is due to DeepLabV3+’s increased ability to model local
and global relationships between parts of the visual data, which stems from
two key features in the architecture. First, the spatial pyramid pooling helps
encode multi-scale contextual information in the model. Second, skip
connections in the encoder, with low-level features from the backbone, help
refine the prediction by allowing details (edges and corners of buildings) to
permeate the final layers.

We also found that by further replacing the Xception Module in the DeepLabV3+
architecture with dilated convolutions, we can reduce the loss of spatial
context information by introducing a larger receptive field (RF) for each
kernel image. This added scale invariance is clear in our approach (See Figure
4). Dilated convolutions consist of kernels with “holes” in them to achieve
better performance in downstream tasks, allowing for a larger RF in earlier
layers without drastically increasing the number of parameters. Downsampling
and pooling in the encoder can reduce spatial context in deeper layers, which
the larger RF mitigates and allows us to track less prominent features (ex.
smaller or narrow buildings).

###  3.2 Objective Function

$\mathcal{L}(y,\hat{y})=\mathcal{L}_{BCE}(y,\hat{y})+(1-D(y,\hat{y}))$ (1)

Methods for semantic segmentation commonly optimize Equation (1), where $D$ is
the DICE coefficient (a generalization of the F1 Score)[17]. Works that
utilize Eqn. (1) achieve relatively high numerical accuracy on the satellite
segmentation datasets, but encounter visual issues such as combined footprints
and sparse false building predictions (See Figure 4 ”BCE + 1” column). This
hinders the analysis of urban areas because we may not obtain an accurate
qualitative prediction of the building masks required for downstream energy
estimation. We speculate these visual inaccuracies are due to two major
causes. First, since the resolution of the data is not always high, the
building-to-background distinction can be blurry, making it hard to
differentiate tightly packed buildings. Second, false-positive building
clusters are abundantly predicted in footprint masks, which stems from the
distribution of building-to-background pixels being uneven (see Figure 1),
with far more background than building. We address both of these drawbacks
with a modified two-part loss formulated as follows:

$\mathcal{L}(y,\hat{y})=\mathcal{L}_{EWC}(y,\hat{y})+(1-F_{\beta}(y,\hat{y}))$
(2)

where

$F_{\beta}(y,\hat{y})=\frac{(1+\beta^{2})(y*\hat{y})}{\beta^{2}(y+\hat{y})}$
(3)

and

$\mathcal{L}_{WCE}(y,\hat{y})=\sum_{(i,j)}\mathcal{W}_{ij}(y)*log(p_{y_{ij}}(\hat{y}_{ij}))$
(4)

F-Beta Measure as a Loss Function: Due to imbalances in the training data,
high-parameter models such as the DeepLabV3+ tend to lean toward predicting
buildings rather than the more common background classes. To compensate for
the erroneous false positives, we introduce the F-Beta Measure to replace the
DICE coefficient in our two-part objective. Rooted from the general F1 Score,
we define the F-Beta Measure in Equation (3) as a configurable loss function
with a hyper-parameter $\beta$. However, although Eqn. (3) is a weighting of
[8], this weighting helps the F-Beta Measure serve as a crucial generalization
of the DICE coefficient. Note that when we set $\beta=1$, the F-Beta Measure
precisely becomes the DICE coefficient. Here, we argue that this simple yet
unique formulation of the F-Beta Measure allows us to tune our objective
toward prioritizing either false positives or false negatives. We will show
that by setting $\beta>1$, we place a higher emphasis on preventing false
negatives, thus increasing recall. Likewise, if we set $\beta<1$, we force the
network to focus on improving precision, consequently resolving false
positives and thus reducing the number of misplaced building clusters.

Exponential Weighted Boundary Loss (EWC): Similar to [23], which introduces a
third building boundary class, we add a weighted loss function [27] that
heavily penalizes wrong predictions close to and on building edges. Our
exponential boundary loss generates a weight map $w(\boldsymbol{x})$ that
forces the model to separate neighboring objects into distinct entities:

$w(\boldsymbol{x})=w_{c}(\boldsymbol{x})+w_{0}\cdot
exp\bigg{(}-\frac{(d_{1}(\boldsymbol{x})+d_{2}(\boldsymbol{x}))^{2}}{2\sigma^{2}}\bigg{)}$
(5)

where $\boldsymbol{x}$ is a ground-truth mask, $w_{c}(\boldsymbol{x})$ is a
separate weight map used to resolve class imbalance, and $w_{0}$ and $\sigma$
are constants that help tune the absolute loss value and relative decay
respectively. Using this mask not only helps us distinguish adjacent
buildings, but also increases the overall loss in high-density areas (ex.
Figure 1 top-right) where models traditionally exhibit a greater level of
uncertainty (see Section 5).

The evaluation of Equation (5) empirically produces values between $0$ and
$w_{0}$ per-pixel. Although we want to heavily penalize incorrect boundary
predictions, we still want to properly penalize all incorrect background
predictions. Therefore, we build upon Equation (5) to produce a new weight map
$\mathcal{W}(\boldsymbol{y})$

$\mathcal{W}(\boldsymbol{y})=exp(w(\boldsymbol{y}))^{p}$ (6)

that produces values between $1$ and $e^{p}$, where $p$ is an additional
hyper-parameter to further prevent incorrect boundary predictions without
affecting how we consider less important background predictions. Figure 1
visualizes these new weight maps on the three standard datasets. We
incorporate $\mathcal{W}(\boldsymbol{y})$ as part of the objective in
Equations (2) and (4) and claim it allows the network to separate previously
conjoined predictions.

Cross-Dataset Training Strategy: As Section 4.1 will quantify, there is a
stark imbalance in the number of samples across the datasets. Consequently, we
saw quick over-fitting and lack of quality results in Urban3D. To account for
this lack in overall performance, we adopt a cross-dataset training strategy
[33]. We first train on a synthesized set that combines augmented samples from
the datasets, and then further fine-tune on the individual dataset. We claim
and subsequently prove that by training on similar satellite images before
fine-tuning on the individual scale, we achieve better numerical performance
and more distinct visual results.

##  4 Experiments

###  4.1 Datasets

We evaluate our method on three datasets. Each dataset is split into an
(80-20)-20 partition, where 20% is reserved for the final test set, and the
remaining 80% is further split into (80-20) for training and validation sets,
respectively.

SpaceNet: The SpaceNet.ai Building Detection Dataset (SpaceNet) [30] contains
700,000 building footprints in five cities scattered across the globe. In this
study, we evaluate using the Vegas region which contains over 3,800 samples of
200m x 200m areas. Each input sample comes with an associated 650 x 650 pixel
RGB satellite image, a high-resolution panchromatic image, and a low-
resolution multi-spectral image. For our purposes, we only use the RGB
satellite image. The samples in their original form come in a TIFF raster
graphics format and the labels in geographical coordinates, so we use GDAL to
pre-process all samples by extracting RGB rasterizations and converting the
coordinates into grayscale masks [11].
AICrowd: The AICrowd Mapping Challenge dataset (AICrowd) [24] contains 340,000
total samples as 300 x 300 pixel RGB images. RGB image samples are provided in
JPEG format, and annotations are provided in MS-COCO format for which we use
the corresponding API to extract masks [21].
Urban3D: TopCoder’s Urban3D dataset (Urban3D) [12] contains 236 samples of
2048 x 2048 pixel images and labels, both in the TIFF compressed raster
format. We use similar pre-processing steps as SpaceNet to extract RGB images
and grayscale masks. As a similar note to SpaceNet, each RGB sample in this
dataset is accompanied by its Depth Surface Model and Digital Terrain Model,
which provides high-resolution building height information. As mentioned with
SpaceNet, we use the RGB image for our purposes only.

| Model |  AP |  AR |  F-1 |  mIOU
---|---|---|---|---|---
Urban3D | Dilated-RND |  82.0 |  78.5 |  79.6 |  81.0
|  Res-NetD |  81.5 |  77.3 |  78.6 |  80.1
| U-Net |  83.1 |  76.2 |  78.6 |  80.5
| FCN |  82.7 |  75.5 |  78.2 |  80.0
SpaceNet | Dilated-RND |  90.0 |  91.1 |  90.6 |  89.1
|  Res-NetD |  90.2 |  89.9 |  90.1 |  89.0
| U-Net |  90.6 |  89.1 |  89.7 |  88.2
| FCN |  90.1 |  88.9 |  89.5 |  88.4
AICrowd | Dilated-RND |  90.7.02 |  90.0.01 |  90.4.04 |  88.6.00
|  Res-NetD |  90.2.10 |  89.0.02 |  89.7.07 |  87.9.00
| U-Net |  88.4.16 |  86.3.06 |  87.0.08 |  85.3.00
| FCN |  89.6.02 |  88.1.00 |  88.8.02 |  86.9.00
Table 1: Results of different network architectures (Subscript $D$ indicates
DeepLabV3+) Figure 3: Avg. accuracy performance of three runs on different
values of $\beta$ on Urban3D

###  4.2 Experimental Evaluation and Implementation

Evaluation:  To evaluate each of our experiments on the datasets mentioned
above, we consider the standard accuracy metrics in the fields of both
semantic segmentation and binary classification: class-mean intersection-over-
union (mIOU) and the F1 Score. The F1 score, also known as the Sørenson-Dice
coefficient [29, 8] measures the balance between precision, the ratio between
true positives and all positive predictions, and recall, the ratio between
true positives and all ground-truth positives. In Section 5, we also report
the average precision and recall. The mIOU metric [16] is a measure of the
similarity between two sets using the ratio between the intersection and union
of the prediction and ground-truth.

General Training Details:  The experiments concerning our proposed method are
trained for 60 epochs using a batch size of 4 with standard Stochastic
Gradient Descent with a learning rate of $1e^{-4}$ and an L2 constant of
$1e^{-4}$. Empirically, we found that a power of 2 when using the
exponentially weighted boundary masks performs best. We select the checkpoint
epoch based on the best validation loss and mIoU score.

Because Urban3D inputs are too large to fit into memory, we employ a tiling
operation with a factor of 4. Each input 2048 x 2048 sample image is split
into 16 inputs of 512 x 512 pixels with the same image resolution. For only
the ablation studies, we introduce a constant amount of bias in training with
the AICrowd dataset by using only 15% of the dataset. We introduce this bias
both to speed up the training process, and to continue to analyze relative
performance. To account for variance, we report the mean and standard
deviation (reported in subscript) across 3 experiments for each study in
Tables 1 \- 3.

Cross-Dataset Training Details:  With cross-dataset training, we augment each
RGB sample to 256 x 256 pixels when combining the samples from all datasets.
For Urban3D and SpaceNet, we down-sample images to 512 x 512 and then split
each into 4 inputs. For AICrowd, we just resize to 256 x 256. After training
on the combined set for 20 epochs, we save the model at the epoch with the
best loss, and then further train on each of the three datasets individually.
As an implementation note, our final method was trained using this combined
set for only 5 epochs and included only 10% of the AICrowd training set.

Experiments are conducted on GPU nodes where each consists of an 8-core
Intel(R) Xeon(R) CPU @ 3.00 GHz, 64 GB of RAM, and either 4 GeForce RTX 2080
Ti GPUs or 2 Tesla V100 GPUs for training models in parallel. We use PyTorch
1.6.0 to develop our methods, re-implement previously published methods, and
build the training pipeline [26].

Loss | AP | AR | F-1 | mIOU
---|---|---|---|---
U+BCE | 80.09 | 78.04 | 78.88 | 80.31
U+F(1.0) | 80.99 | 78.31 | 79.16 | 80.66
U+BCE+F(0.1) | 84.31 | 77.91 | 82.79 | 83.60
U+BCE+F(1.0) | 82.05 | 78.55 | 79.65 | 81.00
U+BCE+F(4.0) | 79.50 | 79.02 | 79.25 | 80.64
S+BCE | 90.13 | 90.44 | 90.22 | 88.69
S+F(1.0) | 90.16 | 90.91 | 90.48 | 88.96
S+BCE+F(0.1) | 92.16 | 90.37 | 92.04 | 90.65
S+BCE+F(1.0) | 90.04 | 91.17 | 90.61 | 89.18
S+BCE+F(4.0) | 89.30 | 91.76 | 90.47 | 88.96
C+BCE |  90.19.06 |  88.42.05 |  89.18.08 |  87.42.08
C+F(1.0) |  90.43.04 |  89.20.05 |  90.20.05 |  88.55.03
C+BCE+F(0.1) | 91.71.02 |  89.53.03 | 91.55.03 | 89.96.02
C+BCE+F(1.0) |  90.74.02 |  90.08.01 |  90.40.04 |  88.64.00
C+BCE+F(4.0) |  89.64.04 | 90.79.01 |  90.25.02 |  88.60.02
Table 2: Ablation study of BCE and F-Beta, including both losses in isolation. Loss | AP | AR | F-1 | mIOU
---|---|---|---|---
U+EWC | 76.40 | 82.27 | 78.58 | 79.97
U+EWC+F(0.1) | 83.82 | 81.10 | 83.01 | 84.22
U+EWC+F(0.5) | 81.49 | 81.14 | 80.75 | 81.87
U+EWC+F(1.0) | 80.09 | 81.72 | 80.26 | 81.40
U+EWC+F(4.0) | 78.98 | 81.90 | 79.68 | 80.95
S+EWC | 88.90 | 91.51 | 90.13 | 88.55
S+EWC+F(0.1) | 92.70 | 91.70 | 92.41 | 90.94
S+EWC+F(0.5) | 90.41 | 91.74 | 91.02 | 89.53
S+EWC+F(1.0) | 89.36 | 92.19 | 90.70 | 89.37
S+EWC+F(4.0) | 89.25 | 92.34 | 90.52 | 88.98
C+EWC |  89.80.04 |  90.05.07 |  89.85.03 |  88.00.04
C+EWC+F(0.1) | 92.04.05 |  91.06.08 | 91.67.07 | 90.61.04
C+EWC+F(0.5) |  91.02.03 |  91.24.10 |  91.45.02 |  89.72.01
C+EWC+F(1.0) |  89.59.05 |  91.63.03 |  90.50.05 |  88.90.02
C+EWC+F(4.0) |  89.38.02 | 91.82.08 |  90.39.04 |  88.83.06
Table 3: Ablation study of EWC and F-Beta, including EWC in isolation.

##  5 Results

Figure 4: Visualizations of predictions from all datasets by four variants of our method and two baselines. Top-Down: (a) Urban3D [second row is a magnification of the first row for better visual comparison], (b) SpaceNet, (c) AICrowd. (Best viewed electronically) Dataset | Method | AP | AR | F-1 | mIOU |  IOUy=1
---|---|---|---|---|---|---
Urban3D |  R2U-Net [35] | - | - | - | - |  69.9±7.1
| U-Net | 84.6 | 79.2 | 81.0 | 80.8 |  65.9±15.1
| U-Net + DEM | 85.3 | 80.0 | 81.8 | 83.0 |  68.7±15.5
| Ours | 83.8 | 81.1 | 83.0 | 84.2 |  70.1±15.2
| Ours + Cross-Dataset | 84.5 | 81.3 | 83.4 | 84.5 | 70.2±15.3
SpaceNet |  U-Net Ensemble [7] | - | - | 86.4 | - | -
|  Mask-RCNN [34] | - | - | 88.1 | - | -
| Ours | 92.7 | 91.7 | 92.4 | 90.9 |  85.2±3.5
| Ours + Cross-Dataset | 93.2 | 92.0 | 92.6 | 91.1 | 85.5±3.6
AICrowd |  Mask-RCNN [35] | - | - | - | - |  74.2±14.5
|  R2U-Net [35] | - | - | - | - |  80.0±14.2
|  U-Net [6] | 94.3 | 95.4 | 94.8 | - | -
| Ours | 96.2 | 96.3 | 96.3 | 95.4 | 92.2±2.6
| Ours + Cross-Dataset | 96.3 | 96.0 | 96.1 | 95.2 |  91.9±3.1
Table 4: State-of-the-Art Comparisons. We use 100% of AICrowd to train/test
our final model.

In most tables, we use shorthand notation for datasets: U-Urban3D, S-SpaceNet,
C-AICrowd.

###  5.1 State-of-the-Art Comparisons

We compare our method to current state-of-the-art segmentation networks by
dataset. For AICrowd and Urban3D, we follow [35] which use an R2U-Net and
Mask-RCNN followed by an extensive regularization and polygonization process.
For only AICrowd, we follow the approach detailed by the winning submission
that used a U-Net with a ResNet-101 encoder, in total containing 51.52M
parameters [6]. Then for Urban3D, we follow the winning approach which
similarly takes advantage of a U-Net architecture with a ResNet-34 encoder
(24.43M parameters) but requires additional depth elevation models. We report
the performance of this architecture with and without the supplemental data.
For SpaceNet, we follow [34], an approach similar to [35] that employs a Mask-
RCNN (87.33M parameters) and a boundary regularizer in post-processing, and
[7], an approach that requires two forward passes in a U-Net Ensemble (31.53M
parameters). We note that [7] takes advantage of multi-spectral images which
offer information through 8-channels, while our model uses only 3-channel RGB
images. Our final network contains 58.26M parameters. Table 4 reports the
results from all methods, and we also show the results of our final method
with cross-dataset training. Additionally, we report the IOU on the building
class (IOUy=1) to compare with [35]. We show that despite data-level
disadvantages our method performs better than all architectures, notably
including the U-Net architectures across all datasets. We also note that
compared to [34] and [35], we do not require any post-processing after
segmentation. Additionally, while the U-Net + DEM nears our final performance,
it is at a significant advantage with an extra channel (see Figure 1). The
results we have presented in Table 4 quantitatively show our proposed method
is state-of-the-art, requiring a single end-to-end network and no additional
channels of information.

###  5.2 Network Architecture

Table 1 compares our base network and the three baseline architectures. We
compare our DeepLabV3+ and Dilated ResNet network (DRND) [4, 32] against three
primary baselines: the DeepLabV3 + ResNet-101 (RND) [15], as it is the most
common pairing in DeepLabV3+ related literature, a standard U-Net encoder-
decoder as it is the base network in many related works [27], and a vanilla
fully-connected network since it is a notable architecture that has been
tested on other building footprint datasets [22, 31]. The results indicate
that the baseline method performs quite well with precision but falls behind
with recall, thus creating an imbalance that brings their F1 performance down.
Although the ResNet-101 backbone does not perform as well in precision, it
offers a more balanced F1 Score performance and often outperforms in mIOU.
Finally, the numerical results show that the Dilated ResNet backbone
outperforms the ResNet backbone across all performance metrics. The
performance of the Dilated ResNet compared to the larger ResNet-101 model
supports the claims laid out in Section 3.1: dilated convolutions help
preserve the spatial structure of footprint predictions and expand the
contextual receptive field. The results of the Dilated Res-Net backbone and
baseline methods can be visualized in Figure 4. Empirically, the visual
results show that the FCN produces noisy footprints, especially on the border,
and the U-Net often produces more ”under-filled” footprints, thus the lack in
recall. The Dilated Res-Net backbone (labeled ”BCE+1”) provides significantly
sharper footprints notwithstanding the conjoined predictions.

###  5.3 $\beta$ in F-Beta Measure and Exponentially Weighted Boundary Loss

Figure 3 illustrates how precision, recall, and overall F-1 score vary as we
tune the $\beta$ in the F-Beta measure. Reinforcing the claims in Section 3.2,
the figure shows that recall increases with $\beta$, but at a much slower rate
compared to how precision proliferates as $\beta$ decreases. From this figure,
we claim that building segmentation is inherently a problem of precision, and
overall performance benefits from placing more emphasis on precision than
recall. We note that in addition to precision’s faster rate of growth, as we
bring $\beta$ closer to zero, the overall F-1 score increases exponentially.

We report the results of using the F-Beta Measure and the Exponentially
Weighted Boundary Loss (EWC) in the form of two tables. First, Table 2
concerns the ablation study between F-Beta and binary cross entropy (BCE). The
data shows that the network does not benefit from only BCE, and the
performance of using only the DICE measure ($\beta=1$) falls slightly short of
the performance reached by both losses combined. Furthermore, the table
illustrates the trade-off between low and high values of $\beta$ when
combining the BCE and F-Beta objective functions. With high $\beta$, we
achieve much better recall but suffer in all other metrics. With $\beta=0.1$,
we achieve considerable gains in precision and mIOU, and despite the lack in
recall we consistently achieve a higher F-1 score.

In Table 3, we report the results of F-Beta and EWC. We first note that EWC
alone performs slightly worse than BCE, despite placing more emphasis on
separating buildings. In addition, EWC tends to achieve higher performance in
recall than precision. This is because while EWC is focused on boundaries, it
is not focusing on preventing sparse, erroneous footprint predictions. On the
other hand, we incur overall performance benefits when we combine EWC and
F-Beta together. The relative precision and recall trade-offs of $\beta$ are
still maintained when using EWC, and $\beta=0.1$ continues to have better
overall F-1 and mIOU performance. Besides the increase in mIOU, when using EWC
over BCE in conjunction with F-Beta we generally observe that precision tends
to fall and recall improves. Consequently, this creates a more balanced
performance between precision and recall, thus consistently improving the F-1
score. Figure 4 shows the results of using EWC and $\beta=0.1$. Compared to
the previous iteration, we effectively resolved previously conjoined and
sparse false-positive footprints across all three datasets. For the footprints
that are still conjoined, we have improved separation.

###  5.4 Cross-Dataset Training

Table 4 reports the performance of our final network when using cross-dataset
training. Note that despite inter-dataset variance, as illustrated by Figure
1, the cross-dataset strategy achieved a slightly higher performance on both
Urban3D and SpaceNet. The same strategy did not perform similarly on the
AICrowd dataset, which leads us to believe that cross-dataset training is not
as effective on datasets with a saturated presence in the combined set.
Qualitatively, Figure 4 shows that our final method generates footprints with
a more defined shape and fewer conjoined predictions.

##  6 Conclusion

In order to better support urban energy simulation through Deep Learning based
approaches, convolutional neural networks must first be able to produce
quality results with distinct footprints, and be scale invariant to the fickle
nature of satellite imagery. To increase accessibility to this technology,
approaches should also be robust to the lack of special wideband imagery that
only few urban centers are able to produce.

In this paper, we present a new approach that brings Deep Learning closer to
perfecting building segmentation. In the presence of class imbalance, we
demonstrate that our proposed F-Beta measure is efficacious at resolving
false-positives without de-prioritizing the common class. We show that
combining F-Beta with our EWC loss creates a powerful tool to separate
distinct entities that were previously unified. By using these advances and a
DeeplabV3+ architecture with a Dilated ResNet backbone, we achieve state-of-
the-art performance on three standard datasets and provide a strong network
which can assist urban planners worldwide in climate related decision making.

## References

  * [1] Myles Allen, Mustafa Babiker, Yang Chen, and Heleen C. de Coninck.  IPCC SR15: Summary for Policymakers.  Intergovernmental Panel on Climate Change, Oct. 2018.
  * [2] Nicolas Audebert, Bertrand Le Saux, and Sebastien Lefevre.  Joint learning from earth observation and openstreetmap data to get faster better semantic maps.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [3] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  IEEE transactions on pattern analysis and machine intelligence, 39(12):2481–2495, 2017.
  * [4] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proceedings of the European conference on computer vision (ECCV), pages 801–818, 2018.
  * [5] Sean Andrew Chen, Andrew Escay, Christopher Haberland, Tessa Schneider, Valentina Staneva, and Youngjun Choe.  Benchmark dataset for automatic damaged building detection from post-hurricane remotely sensed imagery.  arXiv preprint arXiv:1812.05581, 2018.
  * [6] Jakub Czakon, Kamil Kaczmarek, Andrzej Pyskir, and Tarasiewicz Piotr.  Mapping challenge winning solution, September 2018.  [Online; posted 12-Sept-2018].
  * [7] Remi Delassus and Romain Giot.  Cnns fusion for building detection in aerial images for the building detection challenge.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 242–246, 2018.
  * [8] Lee R. Dice.  Measures of the amount of ecologic association between species.  Ecology, 26(3):297–302, 1945.
  * [9] Chao Ding and Khee Poh Lam.  Data-driven model for cross ventilation potential in high-density cities based on coupled cfd simulation and machine learning.  Building and Environment, 165:106394, 2019.
  * [10] Chao Ding and Nan Zhou.  Using residential and office building archetypes for energy efficiency building solutions in an urban scale: A china case study.  Energies, 13(12), 2020.
  * [11] GDAL/OGR contributors.  GDAL/OGR Geospatial Data Abstraction software Library.  Open Source Geospatial Foundation, 2021.
  * [12] Hirsh Goldberg, Myron Brown, and Sean Wang.  A benchmark for building footprint classification using orthorectified rgb imagery and digital surface models from commercial satellites.  In 2017 IEEE Applied Imagery Pattern Recognition Workshop (AIPR), pages 1–7, 2017.
  * [13] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * [14] Timothy L Haithcoat, Wenbo Song, and James D Hipple.  Building footprint extraction and 3-d reconstruction from lidar data.  In IEEE/ISPRS Joint Workshop on Remote Sensing and Data Fusion over Urban Areas (Cat. No. 01EX482), pages 74–78. IEEE, 2001.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [16] Paul Jaccard.  The distribution of the flora in the alpine zone.1.  New Phytologist, 11(2):37–50, 1912.
  * [17] Shruti Jadon.  A survey of loss functions for semantic segmentation.  2020 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), Oct 2020.
  * [18] Hoel Kervadec, Jihene Bouchtiba, Christian Desrosiers, Eric Granger, Jose Dolz, and Ismail Ben Ayed.  Boundary loss for highly unbalanced segmentation.  In International conference on medical imaging with deep learning, pages 285–296. PMLR, 2019.
  * [19] Weijia Li, Conghui He, Jiarui Fang, Juepeng Zheng, Haohuan Fu, and Le Yu.  Semantic segmentation-based building footprint extraction using very high-resolution satellite images and multi-source gis data.  Remote Sensing, 11(4), 2019.
  * [20] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [21] Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollár.  Microsoft coco: Common objects in context, 2014.  cite arxiv:1405.0312Comment: 1) updated annotation pipeline description and figures; 2) added new section describing datasets splits; 3) updated author list.
  * [22] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431–3440, 2015.
  * [23] Dimitris Marmanis, F. Adam, Mihai Datcu, Thomas Esch, and Uwe Stilla.  Deep neural networks for above-ground detection in very high spatial resolution digital elevation models.  ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, II-3/W4:103–110, 03 2015.
  * [24] Sharada Prasanna Mohanty.  Crowdai mapping challenge 2018:baseline with mask rcnn.  https://github.com/crowdai/crowdai-mapping-challenge-mask-rcnn, 2018\.
  * [25] Intergovernmental Panel on Climate Change.  Human Settlements, Infrastructure, and Spatial Planning, page 923–1000.  Cambridge University Press, 2015.
  * [26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
  * [27] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015.
  * [28] Seyed Sadegh Mohseni Salehi, Deniz Erdogmus, and Ali Gholipour.  Tversky loss function for image segmentation using 3d fully convolutional deep networks.  In International workshop on machine learning in medical imaging, pages 379–387. Springer, 2017.
  * [29] Thorvald A. Sorensen.  A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on danish commons.  Biol. Skar., 5:1–34, 1948.
  * [30] Adam Van Etten, Dave Lindenbaum, and Todd M Bacastow.  Spacenet: A remote sensing dataset and challenge series.  arXiv preprint arXiv:1807.01232, 2018.
  * [31] Hsiuhan Lexie Yang, Jiangye Yuan, Dalton Lunga, Melanie Laverdiere, Amy Rose, and Budhendra Bhaduri.  Building extraction at scale using convolutional neural network: Mapping of the united states.  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 11(8):2600–2614, 2018.
  * [32] Fisher Yu, Vladlen Koltun, and Thomas Funkhouser.  Dilated residual networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 472–480, 2017.
  * [33] Jing Zhang, Wanqing Li, and Philip Ogunbona.  Transfer learning for cross-dataset recognition: a survey.  arXiv preprint arXiv:1705.04396, 2017.
  * [34] Kang Zhao, Muhammad Kamran, and Gunho Sohn.  Boundary regularized building footprint extraction from satellite images using deep neural network.  arXiv preprint arXiv:2006.13176, 2020.
  * [35] Stefano Zorzi, Ksenia Bittner, and Freidrich Fraundorfer.  Machine-learned regularization and polygonization of building segmentation masks.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 3098–3105, Los Alamitos, CA, USA, jan 2021. IEEE Computer Society.

## Supplemental Materials

###  .1 Additional Visualizations

Besides Figure 4, we provide additional visualizations of model predictions on
the Urban3D [12], SpaceNet [30], and AICrowd [24] datasets in Figure 5.

###  .2 Further Analysis

As discussed in Section  4 of the main paper and supported by Figures 4 and 5,
the predictions by the fully-convolutional network [22] frequently exhibit
noisy and sparse predictions. Although the U-Net [27] resolves almost all of
these noisy predictions, thus the high average precision, the model does not
effectively capture the geometry of footprints which brings down the average
recall. This is especially evident in Figure 5 (b)(i), where the U-Net is
unable to capture the smaller buildings in the upper portion of the center
neighborhood in the satellite image.

The first iteration of our network (column ”BCE + 1”) solves the issues the
U-Net gave rise to as it is now able to capture more of the building
footprints. However, as discussed in the main paper, this iteration often
creates conjoined footprint predictions and curved building geometries. The
next iteration of our network (column ”ECW + 0.5”) employs the F-Beta measure
and the exponentially weighted boundary loss to encourage the network to
separate distinct footprints and create sharper edges. These claims are
observable primarily in the predictions of Urban3D and SpaceNet examples
(Figure 5 (a) and (b)). Notice that by using a new objective, we were able to
separate most of the combined footprints from the previous iteration and
create straighter edges. Finally, the last iteration of our network (column
”Final Network”) involved using a cross-task training strategy on only the
Urban3D and SpaceNet datasets to resolve any remaining prediction artifacts.
Observe from Figure 5 that this strategy consistently produces predictions
that improves upon the previous iteration by separating footprints that were
still combined, enforces sharper corners, and cleans up most remaining false
positives.

Figure 5: Additional two visualizations of predictions from each of the three
datasets used in this paper. Top-Down: (a) Urban3D [the second row of each
prediction is a magnification of the first row for better visual comparison],
(b) SpaceNet, (c) AICrowd. Turquiouse buildings are correctly predicted
footprints, yellow predictions are two conjoined ground-truth footprints, and
red predictions are false positive footprints.