Regularization and the small-ball method I: sparse recovery

Introduction

The focus of this article is on regularization, which is one of the most significant methods in modern statistics. To give some intuition on the method and on the reasons behind its introduction, consider the following standard problem.

with the underlying assumption that $f^{*}$ exists and is unique.

Unlike problems in approximation theory, neither the target $Y$ nor the underlying measure $\mu$ are known. Therefore, computing the $L_{2}$ distance between functions in $F$ and $Y$ is impossible. Instead, one is given partial information: a random sample $(X_{i},Y_{i})_{i=1}^{N}$, selected independently according to the joint distribution of $X$ and $Y$.

Because of the random nature of the sample and the limited information it provides, there is no real hope of identifying $f^{*}$, but rather, only of approximating it. In an estimation problem one uses the sample to produce a random function $\hat{f}\in F$, and the success of the choice is measured by the distance between $\hat{f}$ and $f^{*}$ in the $L_{2}(\mu)$ sense. Thus, one would like to ensure that with high probability with respect to the samples $(X_{i},Y_{i})_{i=1}^{N}$, the error rate

is small. More accurately, the question is to identify the way in which the error rate depends on the structure of the class $F$ and scales with the sample size $N$ and the required degree of confidence (probability estimate).

It is not surprising (and rather straightforward to verify) that the problem becomes harder the larger $F$ is. In contrast, if $F$ is small, chances are that $f^{*}(X)$ is very far from $Y$, and identifying it, let alone approximating it, is pointless.

In situations we shall refer to as learning problems, the underlying assumption is that $F$ is indeed small, and the issue of the approximation error – the distance between $Y$ and $f^{*}$ is ignored.

While the analysis of learning problems is an important and well-studied topic, the assumption that $F$ is reasonably small seems somewhat restrictive; it certainly does not eliminate the need for methods that allow one to deal with very large classes.

Regularization was introduced as an alternative to the assumption on the ‘size’ of $F$. One may consider large classes, but combine it with the belief that $f^{*}$ belongs to a relatively small substructure in $F$. The idea is to penalize a choice of a function that is far from that substructure, which forces the learner to choose a function in the ‘right part’ of $F$.

Let $\lambda>0$ and for a sample $(X_{i},Y_{i})_{i=1}^{N}$, set

$\hat{f}$ is called a regularization procedure, $\Psi$ is the regularization function and $\lambda$ is the regularization parameter.

In the classical approach to regularization, the substructure of $f^{*}$ is quantified directly by $\Psi$. The underlying belief is that $\Psi(f^{*})$ is not ‘too big’ and one expects the procedure to produce $\hat{f}$ for which $\Psi(\hat{f})$ is of the order of $\Psi(f^{*})$. Moreover, the anticipated error rate $\|\hat{f}-f^{*}\|_{L_{2}(\mu)}$ depends on $\Psi(f^{*})$. In fact, an optimistic viewpoint is that regularization could perform as well as the best learning procedure in the class $\{f:\Psi(f)\leq\Psi(f^{*})\}$, but without knowing $\Psi(f^{*})$ beforehand.

Among the regularization schemes that are based on the classical approach are reproducing kernel Hilbert spaces (RKHS), in which the RKHS norm serves as the penalty. Since RKHS norms capture various notions of smoothness, in RKHS regularization one is driven towards a choice of a smooth $\hat{f}$ – as smooth as $f^{*}$ is.

In more modern regularization problems the situation is very different. Even when penalizing with a norm $\Psi$, one no longer cares whether or not $\Psi(f^{*})$ is small; rather, one knows (or at least believes) that $f^{*}$ is sparse in some sense, and the hope is that this sparsity will be reflected in the error rate.

In other words, although one uses certain norms as regularization functions – norms that seemingly have nothing to do with ‘sparsity’ – the hope is that the sparse nature of $f^{*}$ will be exposed by the regularization procedure, while $\Psi(f^{*})$ will be of little importance.

for the choice $\Psi(t)=\|t\|_{1}=\sum_{i=1}^{d}|t_{i}|$.

The remarkable property of the LASSO (see and ) is that for a well-chosen regularization parameter $\lambda$, if $t^{*}$ is supported on at most $s$ coordinates (and under various assumptions on $X$ and $Y$ to which we will return later), then with high probability,

Thus, the error rate of the LASSO does not depend on $\Psi(t^{*})=\|t^{*}\|_{1}$, but rather on the degree of sparsity of $t^{*}$, measured here by the cardinality of its support $\left\|t^{*}\right\|_{0}=|\{i:t_{i}^{*}\not=0\}|$.

A standard (yet somewhat unconvincing) explanation of this phenomenon is that the penalty $\|t\|_{1}$ is a convexified version of $\|t\|_{0}=|\{i:t_{i}\not=0\}|$, though this loose connection hardly explains why $\|t^{*}\|_{0}$ has any effect on the error rate of the LASSO.

A similar phenomenon occurs for other choices of $\Psi$, such as the SLOPE and trace-norm regularization, which will be explored in detail in what follows. In all these cases and others like them, the regularization function is a norm that does not appear to be connected to sparsity, nor to other natural notions of low-dimensional structures for that matter. Yet, and quite mysteriously, the respective regularization procedure emphasizes those very properties of $t^{*}$.

The aim of this note is to offer a framework that can be used to tackle standard learning problems (small $F$) and regularized problems alike. Moreover, using the framework, one may explain how certain norms lead to the emergence of sparsity-based bounds.

In what follows we will show that two parameters determine the error rate of regularization problems. The first one captures the ‘complexity’ of each set in the natural hierarchy in $F$

Applying results from , the ‘complexity’ of each $F_{\rho}$ turns out to be the optimal (in the minimax sense) error rate of the learning problem in that set. To be more precise, the main ingredient in obtaining a sharp error rate of a learning problem in a class $H$ is an accurate analysis of the empirical excess squared loss functional

Since the minimizer $\hat{f}$ of the functional (1.1) satisfies $P_{N}{\cal L}_{\hat{f}}\leq 0$, one may obtain an estimate on the error rate by showing that with high probability, if $\|f-f^{*}\|_{L_{2}(\mu)}\geq r$ then $P_{N}{\cal L}_{f}>0$. This excludes functions in the set $\{f\in H:\|f-f^{*}\|_{L_{2}(\mu)}\geq r\}$ as potential empirical minimizers. That ‘critical level’ turns out to be the correct (minimax) error rate of a learning problem in $H$. That very same parameter is of central importance in regularization problems — specifically, the ‘critical level’ $r(\rho)$ for each one of the sets $\{f\in F:\Psi(f-f^{*})\leq\rho\}$ (see Section 2.1 for an accurate definition of $r(\rho)$ and its role in the analysis of learning problems and regularization problems).

The second parameter, which is the main ingredient in our analysis of regularization problems, measures the ‘size’ of the subdifferential of $\Psi$ in points that are close to $f^{*}$: recall that the subdifferential of $\Psi$ in $f$ is

where $E^{*}$ is the dual space of the normed space $(E,\Psi)$, and that if $f\neq 0$, the subdifferential consists of all the norm one linear functionals $z^{*}$ for which $z^{*}(f)=\Psi(f)$.

Fix $\rho>0$ and let $\Gamma_{f^{*}}(\rho)$ be the collection of functionals that belong to the subdifferential $(\partial\Psi)_{f}$ for some $f\in F$ that satisfies $\Psi(f-f^{*})\leq\rho/20$. Set

Hence, $\Gamma_{f^{*}}(\rho)$ is a subset of the unit sphere of $E^{*}$ when $0\notin\{f\in F:\Psi(f-f^{*})\leq\rho/20\}$ and it is the entire unit ball of $E^{*}$ otherwise. And, since $H_{\rho}$ consists of functions whose $\Psi$ norm is $\rho$, it is evident that $\Delta(\rho)\leq\rho$. Therefore, if $\Delta(\rho)\geq\alpha\rho$ for a fixed $0<\alpha\leq 1$ then $\Gamma_{f^{*}}(\rho)$ is rather large: for every $h\in H_{\rho}$ there is some $z^{*}\in\Gamma_{f^{*}}(\rho)$ for which $z^{*}(h)$ is ‘almost extremal’—that is, at least $\alpha\rho$.

Our main result (Theorem 3.2 below) is that if $\Gamma_{f^{*}}(\rho)$ is large enough to ensure that $\Delta(\rho)\geq 4\rho/5$, and the regularization parameter $\lambda$ is set to be of the order of $\frac{r^{2}(\rho)}{\rho}$, then with high probability, the regularized minimizer in $F$, $\hat{f}$, satisfies that $\|\hat{f}-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$ and $\Psi(\hat{f}-f^{*})\leq\rho$.

Theorem 3.2 implies that one may analyze regularization problems by selecting $\rho$ wisely, keeping in mind that points in a $\Psi$-ball of radius $\sim\rho$ around $f^{*}$ must generate a sufficiently large subdifferential. And the fact that functionals in $\Gamma_{f^{*}}(\rho)$ need to be ‘almost extremal’ only for points in $H_{\rho}$ rather than for the entire sphere is crucial; otherwise, it would have forced $\Gamma_{f^{*}}(\rho)$ to be unreasonably large – close to the entire dual sphere.

As will be clarified in what follow, sparsity, combined with the right choice of $\Psi$, contributes in two places: firstly, if $f^{*}$ is sparse in some sense and $\Psi$ is not smooth on sparse elements, then $\Gamma_{f^{*}}(\rho)$, which contains the subdifferential $(\partial\Psi)_{f^{*}}$, is large; secondly, for the right choice of $\rho$ the ‘localization’ $H_{\rho}$ consists of elements that are well placed: if $\Psi(f-f^{*})=\rho$ and $\|f-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$, there is some $z^{*}\in\Gamma_{f^{*}}(\rho)$ for which $z^{*}(f-f^{*})$ is large enough. The fact that $H_{\rho}$ is well placed is an outcome of some compatibility between $\Psi$ and the $L_{2}(\mu)$ norm.

Of course, to find the right choice of $\rho$ one must first identify $r(\rho)$, which is, in itself, a well-studied yet nontrivial problem.

Before we dive into technical details, let us formulate some outcomes of our main result. We will show how it can be used to obtain sparsity-driven error rates in three regularization procedures: the LASSO, SLOPE and trace norm regularization. In all three cases our results actually extend the known estimates in various directions.

The LASSO has been studied extensively in the last two decades. Even though some recent advances have shown the LASSO to have its limitation, historically, it has been the benchmark estimator of high-dimensional statistics — mainly because a high dimensional parameter space does not significantly affect its performance as long as $t_{0}$ is sparse. This was shown for example, in in the context of estimation and sparse oracle inequalities, in for support recovery results; and in various other instances as well; we refer the reader to the books for more results and references on the LASSO.

Let $A$ be a matrix and set $(\sigma_{i}(A))$ to be its singular values, arranged in a non-increasing order. For $p\geq 1$, $\|A\|_{p}=(\sum\sigma_{i}^{p}(A))^{1/p}$ is the $p$-Schatten norm.

Note that the trace-norm is simply the $1$-Schatten norm, the Hilbert-Schmidt norm is the $2$-Schatten norm and the operator norm is the $\infty$-Schatten norm.

The trace norm regularization procedure is

and it was introduced for the reconstruction of low-rank, high-dimensional matrices .

As will be explained in what follows, our main result holds in rather general situations and may be implemented in examples once the ‘critical levels’ $r(\rho)$ are identified. Since the examples we present serve mainly as “proof of concept”, we will focus only on one scenario in which $r(\rho)$ may be completely characterized for an arbitrary class of functions.

Assume that the underlying measure $\mu$ is isotropic and $L$-subgaussian, and that for f^{*}=\bigl{<}t^{*},\cdot\bigr{>} (or f^{*}=\bigl{<}A^{*},\cdot\bigr{>} in the matrix case), the noiseIn what follows we will refer to $\xi$ as ‘the noise’ even though it depends in general on $Y$ and $X$. The reason for using that term comes from the situation in which $Y=f^{*}(X)-W$ for a symmetric random variable $W$ that is independent of $X$ (independent additive noise); thus $\xi=W$. We have opted to call $\xi$ ‘the noise’ because its role in the general case and its impact on the error rate is rather similar to what happens for independent noise. $\xi=f^{*}(X)-Y$ belongs to $L_{q}$ for some $q>2$.

In the supplementary material we study a general $X$ without assuming it is isotropic, which means dealing with less natural Euclidean structures in the examples we present. It is also possible to go beyond the subgaussian case, we refer the reader to where other moment assumptions on $X$ are considered.

Applying our main result we will show the following:

If $\lambda=c_{2}(L,\delta)\|\xi\|_{L_{q}}\sqrt{\log(ed)/N}$ and $N\geq s\log(ed/s)$, then with probability at least $1-\delta$ the LASSO estimator with regularization parameter $\lambda$ satisfies that for every $1\leq p\leq 2$

The error rate in Theorem 1.4 coincides with the standard estimate on the LASSO (cf. ), but in a broader context: $t^{*}$ need not be sparse but only approximated by a sparse vector; the target $Y$ is arbitrary and the noise $\xi$ may be heavy tailed and need not be independent of $X$.

Let $1\leq s\leq d$ satisfy that $s/d=o(1)$ and $(s\log d)/N=o(1)$ when $N\rightarrow\infty$. If $0<\varepsilon<1$, $N\rightarrow\infty$ and $\lambda=2\sigma/\sqrt{N}$, the SLOPE estimator with weights $(\beta_{i})_{i=1}^{d}$ and regularization parameter $\lambda$ satisfies

Note that Theorem 1.5 is asymptotic in nature and not ‘high-dimensional’. Moreover, it only holds for a Gaussian $X$, independent Gaussian noise $W$, a specific choice of weights $(\beta_{i})_{i=1}^{d}$ and $t^{*}$ that is $s$-sparse.

We consider a more general situation. Let $\beta_{i}\leq C\sqrt{\log(ed/i)}$ and set $\Psi(t)=\sum_{i=1}^{d}\beta_{i}t_{i}^{\sharp}$.

then for $N\geq c_{2}s\log(ed/s)$ and with the choice of $\lambda=c_{2}\|\xi\|_{L_{q}}/\sqrt{N}$, one has

Finally, let us consider trace norm regularization.

one has the following. Let $N\geq c_{2}s\max\{m,T\}$ and $\lambda=c_{3}\|\xi\|_{L_{q}}\sqrt{\frac{\max\{m,T\}}{N}}$. Then with probability at least $1-\delta$, for any $1\leq p\leq 2$

The constants $c_{1},c_{2},c_{3}$ and $c_{4}$ depends only on $L$ and $\delta$.

A result of a similar flavour to Theorem 1.7 is Theorem 9.2 from .

Let $X$ be an isotropic and $L$-subgaussian vector, and $W$ that is mean-zero, independent of $X$ and belongs to the Orlicz space $L_{\psi_{\alpha}}$ for some $\alpha\geq 1$. If Y=\bigl{<}A^{*},X\bigr{>}+W and

then with probability at least $1-3\exp(-t)-\exp(-c_{2}(L)N)$

Clearly, the assumptions of Theorem 1.8 are more restrictive than those of Theorem 1.7, as the latter holds for a heavy tailed $\xi$ that need not be independent of $X$, and for $A^{*}$ that can be approximated by a low-rank matrix. Moreover, if $\|A^{*}\|_{1}$ is relatively large and the error rate in Theorem 1.8 is the sparsity-dominated $\lambda^{2}{\rm rank}(A^{*})$, then the error rate in Theorem 1.7 is better by a logarithmic factor.

The proofs of the error rates in all the three examples will be presented in Section 5.

We end the introduction with some standard notation.

Throughout, absolute constants are denoted by $c,c_{1}...$, etc. Their value may change from line to line. When a constant depends on a parameter $\alpha$ it will be denoted by $c(\alpha)$. $A\lesssim B$ means that $A\leq cB$ for an absolute constant $c$, and the analogous two-sided inequality is denoted by $A\sim B$. In a similar fashion, $A\lesssim_{\alpha}B$ implies that $A\leq c(\alpha)B$, etc.

Let $E\subset L_{2}(\mu)$ be a vector space and set $\Psi$ to be a norm on $E$. For a set $A\subset E$, $t\in E$ and $r>0$, let $rA+t=\{ra+t:a\in A\}$.

Denote by $B_{\Psi}=\{w\in E:\Psi(w)\leq 1\}$ the unit ball of $(E,\Psi)$ and set $S_{\Psi}=\{f\in E:\Psi(f)=1\}$ to be the corresponding unit sphere. $B_{\Psi}(\rho,f)$ is the ball of radius $\rho$ centred in $f$ and $S_{\Psi}(\rho,f)$ is the corresponding sphere. Also, set $D$ to be the unit ball in $L_{2}(\mu)$, $S$ is the unit sphere there, and $D(\rho,f)$ and $S(\rho,f)$ are the ball and sphere centred in $f$ and of radius $\rho$, respectively.

For every $x=(x_{i})_{i=1}^{d}$, $(x_{i}^{\sharp})_{i=1}^{d}$ denotes the non-increasing rearrangement of $(|x_{i}|)_{i=1}^{d}$.

Finally, if $(X_{i},Y_{i})_{i=1}^{N}$ is a sample, $P_{N}h=\frac{1}{N}\sum_{i=1}^{N}h(X_{i},Y_{i})$ is the empirical mean of $h$.

Preliminaries: The regularized functional

Let ${\cal L}_{f}(X,Y)=(f(X)-Y)^{2}-(f^{*}(X)-Y)^{2}$ be the excess squared loss functional and for $\lambda>0$ let

be its regularized counterpart. Thus, for a random sample $(X_{i},Y_{i})_{i=1}^{N}$, the empirical (regularized) excess loss functional is

This simple observation shows that the random set $\{f\in F:P_{N}{\cal L}_{f}^{\lambda}>0\}$ may be excluded from our considerations, as it does not contain potential minimizers. Therefore, if one can show that with high probability,

then on that event, $\|\hat{f}-f^{*}\|_{L_{2}(\mu)}\leq r$.

We will identify when $P_{N}{\cal L}_{f}^{\lambda}>0$ by considering the two parts of the empirical functional: the empirical excess loss $P_{N}{\cal L}_{f}$ and the regularized part $\lambda(\Psi(f)-\Psi(f^{*}))$.

Because of its crucial role in obtaining error estimates in learning problems, the functional $f\to P_{N}{\cal L}_{f}$ has been studied extensively using the small-ball method, (see, e.g., ). Thus, the first component in the machinery we require for explaining both learning problems and regularization problems is well understood and ready-to-use; its details are outlined below.

Set $\xi=\xi(X,Y)=f^{*}(X)-Y$ and observe that

Since $F$ is convex, the characterization of the nearest point map in a Hilbert space shows that

for every $f\in F$. Hence, setting $\xi_{i}=f^{*}(X_{i})-Y_{i}$, one has

The decomposition of the empirical excess loss to the quadratic component (${\cal Q}_{f-f^{*}}$) and the multiplier one (${\cal M}_{f-f^{*}}$) is the first step in applying the small-ball method to learning problems. One may show that on a large event, if $\|f-f^{*}\|_{L_{2}(\mu)}$ is larger than some critical level then $P_{N}{\cal Q}_{f-f^{*}}\geq\theta\|f-f^{*}\|_{L_{2}}^{2}$ and dominates $P_{N}{\cal M}_{f-f^{*}}$; hence $P_{N}{\cal L}_{f}>0$.

To identify this critical level, let us define the following parameters:

Let $H\subset F$ be a convex class that contains $f^{*}$. Let $(\varepsilon_{i})_{i=1}^{N}$ be independent, symmetric, $\{-1,1\}$-valued random variables that are independent of $(X_{i},Y_{i})_{i=1}^{N}$.

The main outcome of the small-ball method is that for the right choices of $\gamma_{M}$ and $\gamma_{Q}$, $r=\max\{r_{M},r_{Q}\}$ is the above-mentioned ‘critical level’ in $H$, once $H$ satisfies a weak small-ball condition.

Assume that there are constants $\kappa>0$ and $0<\varepsilon\leq 1$, for which, for every $f,h\in F\cup\{0\}$,

There are numerous examples in which the small-ball condition may be verified for $\kappa$ and $\varepsilon$ that are absolute constants. We refer the reader to for some of them.

Let $H$ be a closed, convex class of functions that contains $f^{*}$ and satisfies Assumption 2.1 with constants $\kappa$ and $\varepsilon$. If $\theta=\kappa^{2}\varepsilon/16$ then for every $0<\delta<1$, with probability at least $1-\delta-2\exp(-N\varepsilon^{2}/2)$ one has:

$\bullet$ If $f\in H$ and $\|f-f^{*}\|_{L_{2}(\mu)}\geq r_{Q}\left(H,\kappa\varepsilon/32\right)$ then

In particular, with probability at least $1-\delta-2\exp(-N\varepsilon^{2}/2)$,

From now on, we will assume that $F$ satisfies the small-ball condition with constants $\kappa$ and $\varepsilon$, and that $\theta=\kappa^{2}\varepsilon/16$.

In what follows we will abuse notation and omit the dependence of $r_{M}$ and $r_{Q}$ on $f^{*}$, $\kappa$, $\varepsilon$ and $\delta$.

Let $r(\cdot)$ be a function that satisfies $r(\rho)\geq\sup_{f^{*}\in F}\max\{r_{Q}(\rho),r_{M}(\rho)\}.$ Finally, put

Using the notation introduced above, on an event of probability at least $1-\delta-2\exp(-N\varepsilon^{2}/2)$, if $f\in F\cap B_{\Psi}(\rho,f^{*})$ and $\|f-f^{*}\|_{L_{2}(\mu)}\geq r(\rho)$ then

Moreover, it follows from and that under mild structural assumptions on $F$, $r(\rho)$ is the best possible error rate of any learning procedure in $F\cap B_{\Psi}(\rho,f^{*})$ – i.e., the minimax rate in that class.

Let ${\cal A}$ be the event from Corollary 2.4 and set

$\gamma_{\cal O}$ will be of little importance in what follows, because it may be upper bounded by $(\theta/8)r^{2}(\rho)$. However, it will be of the utmost importance in , where complexity-based regularization is studied (see Section 6 for more details).

The main result

Let us turn to the second part of the regularized functional – namely, $\lambda(\Psi(f)-\Psi(f^{*}))$. Let $E^{*}$ be the dual space to $(E,\Psi)$ and set $\Psi^{*}$ to be the dual norm. $B_{\Psi^{*}}$ and $S_{\Psi^{*}}$ denote the dual unit ball and unit sphere, respectively; i.e., $B_{\Psi^{*}}$ consists of all the linear functionals $z^{*}$ on $E$ for which $\sup_{\Psi(x)=1}|z^{*}(x)|\leq 1$.

The functional $z^{*}\in S_{\Psi^{*}}$ is a norming functional for $z\in E$ if $z^{*}(z)=\Psi(z)$.

In the language of Convex Analysis, a functional is norming for $x$ if and only if it belongs to $(\partial\Psi)_{x}$, the subdifferential of $\Psi$ in $x$.

Let $\Gamma_{f^{*}}(\rho)$ be the collection of functionals that are norming for some $f\in B_{\Psi}(\rho/20,f^{*})$. In particular, $\Gamma_{f^{*}}(\rho)$ contains all the norming functionals of $f^{*}$.

Note that if $z^{*}\in\Gamma_{f^{*}}(\rho)$ and $h\in S_{\Psi}(\rho,f^{*})$ then $|z^{*}(h-f^{*})|\leq\Psi(h-f^{*})=\rho$. Thus, a lower bound of the form $\Delta(\rho)\geq(1-\delta)\rho$ implies that $\Gamma_{f^{*}}(\rho)$ is a relatively large subset of the dual unit sphere: each point in $F\cap S_{\Psi}(\rho,f^{*})\cap D(r(\rho),f^{*})$ has an ‘almost norming’ functional in $\Gamma_{f^{*}}(\rho)$.

Our main result is that if $\Gamma_{f^{*}}(\rho)$ is indeed large enough to ensure that $\Delta(\rho)\geq 4/5\rho$ then with high probability $\|\hat{f}-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$ and $\Psi(\hat{f}-f^{*})\leq\rho$.

Assume that $F$ is closed and convex. Let $\rho>0$ and set ${\cal A}$ to be an event on which Corollary 2.4 holds. If $\Delta(\rho)\geq 4\rho/5$ and

then on the event ${\cal A}$, a regularized empirical minimizer $\hat{f}\in{\rm argmin}_{f\in F}P_{N}{\cal L}_{f}^{\lambda}$ satisfies

Moreover, since $r_{\cal O}(\rho)\leq(\theta/8)r^{2}(\rho)$, the same assertion holds if

The proof of the theorem follows in three steps: first, one has to show that $P_{N}{\cal L}_{f}^{\lambda}$ is positive on the set $F\cap S_{\Psi}(\rho,f^{*})$. Second, thanks to certain homogeneity properties of the functional, it is positive in $F\backslash B_{\Psi}(\rho,f^{*})$, because it is positive on the ‘sphere’ $F\cap S_{\Psi}(\rho,f^{*})$. Finally, one has to study the functional in $F\cap B_{\Psi}(\rho,f^{*})$ and verify that it is positive in that set, provided that $\|f-f^{*}\|_{L_{2}(\mu)}\geq r(\rho)$.

Proof. Fix $h\in F\cap S_{\Psi}(\rho,f^{*})$ and we shall treat two different cases: when $\|h-f^{*}\|_{L_{2}(\mu)}\geq r(\rho)$ and when $\|h-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$.

If $\|h-f^{*}\|_{L_{2}}\geq r(\rho)$, then by the triangle inequality for $\Psi$,

Hence, for $(X_{i},Y_{i})_{i=1}^{N}\in{\cal A}$ and by the upper estimate in the choice of $\lambda$,

Next, if $\|h-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$ then

Consider $u,v\in E$ that satisfy $f^{*}=u+v$ and $\Psi(u)\leq\rho/20$. Let $z^{*}$ be any norming functional of $v$; thus, $z^{*}\in S_{\Psi^{*}}$ and $z^{*}(v)=\Psi(v)$. Since $\Psi(h)=\sup_{x^{*}\in B_{\Psi^{*}}}x^{*}(h)$ it follows that

This holds for any $v\in B_{\Psi}(\rho/20,f^{*})$, and by the definition of $\Delta(\rho)$ and for an optimal choice of $z^{*}$,

where the last inequality holds because $\Delta(\rho)\geq 4\rho/5$ and $\lambda\geq 3\gamma_{\cal O}(\rho)/\rho$. Also, since $\gamma_{\cal O}(\rho)\leq(\theta/8)r^{2}(\rho)$, it suffices that $\lambda\geq(3\theta/8)r^{2}(\rho)/\rho$ to ensure that $P_{N}{\cal L}_{h}^{\lambda}>0$ in (3.2). This completes the proof of the first step – that $P_{N}{\cal L}_{h}^{\lambda}>0$ on $F\cap S_{\Psi}(\rho,f^{*})$.

Turning to the second step, one has to establish a similar inequality for functions outside $B_{\Psi}(\rho,f^{*})$. To that end, let $f\in F\backslash B_{\Psi}(\rho,f^{*})$. Since $F$ is convex and $\Psi$ is homogeneous, $f=f^{*}+\alpha(h-f^{*})$ for some $h\in F\cap S_{\Psi}(\rho,f^{*})$ and $\alpha>1$. Therefore,

moreover, $\Psi(f-f^{*})=\alpha\Psi(h-f^{*})$ and for every functional $z^{*}$, $z^{*}(f-f^{*})=\alpha z^{*}(h-f^{*})$.

Thus, by (3.1), when $\|h-f^{*}\|_{L_{2}(\mu)}\geq r(\rho)$, $P_{N}{\cal L}_{f}^{\lambda}>0$, and when $\|h-f^{*}\|_{L_{2}(\mu)}\leq r(\rho)$,

Finally, when $h\in F\cap B_{\Psi}(\rho,f^{*})$ and $\left\|h-f^{*}\right\|_{L_{2}(\mu)}\geq r(\rho)$, (3.1) shows that $P_{N}{\cal L}_{f}^{\lambda}>0$.

Note that if $\rho\geq\Psi(f^{*})$ there is no upper limitation on the choice of $\lambda$. Indeed, if $\|h-f^{*}\|_{L_{2}(\mu)}\geq r(\rho)$ and $\Psi(h)=\rho\geq\Psi(f^{*})$ then $\lambda(\Psi(h)-\Psi(f^{*}))\geq 0$, and $P_{N}{\cal L}_{h}^{\lambda}>0$ just as in (3.1). The rest of the proof remains unchanged.

It follows from the proof that the quadratic component $P_{N}{\cal Q}_{f-f^{*}}$ and the regularization one $\lambda(\Psi(f)-\Psi(f^{*}))$ dominate the multiplier component $2P_{N}{\cal M}_{f-f^{*}}$ in different parts of $F$. The behaviour of $P_{N}{\cal Q}_{f-f^{*}}$ allows one to exclude the set $(F\cap B_{\psi}(\rho,f^{*}))\backslash D(r(\rho),f^{*})$, as well as any point in $F$ for which the interval $[f,f^{*}]$ intersects $(F\cap S_{\psi}(\rho,f^{*}))\backslash D(r(\rho),f^{*})$. This exclusion is rather free-of-charge, as it holds with no assumptions on the norm $\Psi$.

The situation is more subtle when trying to exclude points for which the interval $[f,f^{*}]$ intersects $F\cap S_{\psi}(\rho,f^{*})\cap D(r(\rho),f^{*})$. That is precisely the region in which the specific choice of $\Psi$ is important and the regularization component is the reason why $P_{N}{\cal L}_{f}^{\lambda}>0$.

Figure 1 shows this idea: $P_{N}{\cal L}_{f}^{\lambda}>0$ for two different reasons: either $Q>M$ – the quadratic component dominates the multiplier component, or $R>M$ – the regularization component dominates the multiplier component.

Note that an output of the sparsity equation is that the descent cone $T_{\Psi}(f^{*})=\cup_{\tau>0}\{h:\Psi(f^{*}+\tau h)\leq\Psi(f^{*})\}$ does not intersect $S_{\Psi}(\rho,f^{*})\cap D(r(\rho),f^{*})$ when the “sparsity condition” $\Delta(\rho)\geq 4\rho/5$ is satisfied (cf. Figure 2).

The role of Δ​(ρ)Δ𝜌\Delta(\rho)

It is clear that $\Delta(\rho)$ plays a crucial role in the proof of Theorem 3.2, and that the larger $\Gamma_{f^{*}}(\rho)$ is, the better the lower bound on $\Delta(\rho)$.

Having many norming functionals of points in $B_{\Psi}(\rho/20,f^{*})$ can be achieved somewhat artificially, by taking $\rho\sim\Psi(f^{*})$. If $\rho$ is large enough, $B_{\Psi}(\rho/20,f^{*})$ contains a $\Psi$-ball centred in . Therefore, $\Gamma_{f^{*}}(\rho)$ is the entire dual sphere and $\Delta(\rho)=\rho$. This is the situation when one attempts to derive complexity-based bounds (see Section 6 and ), i.e., when one wishes to find $\hat{f}$ that inherits some of $f^{*}$’s ‘good qualities’ that are captured by $\Psi(f^{*})$.

Here, we are interested in cases in which $\rho$ may be significantly smaller than $\Psi(f^{*})$ and enough norming functionals have to be generated by other means.

If $\Psi$ is smooth, each $f\not=0$ has a unique norming functional, and for a small $\rho$, the norming functionals of points in $B_{\Psi}(\rho/20,f^{*})$ are close to the (unique) norming functional of $f^{*}$; hence there is little hope that $\Gamma_{f^{*}}(\rho)$ will be large enough to ensure that $\Delta(\rho)\sim\rho$. It is therefore reasonable to choose $\Psi$ that is not smooth in $f^{*}$ or in a neighbourhood of $f^{*}$.

Another important fact is that $\Gamma_{f^{*}}(\rho)$ need not be as large as the entire dual sphere to ensure that $\Delta(\rho)\sim\rho$. Indeed, it suffices if $\Gamma_{f^{*}}(\rho)$ contains ‘almost norming’ functionals only to points that satisfy $\|w\|_{L_{2}(\mu)}\leq r(\rho)/\rho$ and $\Psi(w)=1$, rather than to every point in the sphere $S_{\Psi}$.

It turns out that the combination of the right notion of sparsity with a wise choice of a norm $\Psi$ ensures that $\Gamma_{f^{*}}(\rho)$ contains enough ‘almost norming’ functionals precisely for the subset of the sphere one is interested in.

To give an indication of how this happens, let us show the following:

Let $Z\subset S_{\Psi^{*}}$, $W\subset S_{\Psi}$ and $0<\eta_{1},\eta_{2}<1$. If every $w\in W$ can be written as $w=w_{1}+w_{2}$, where $\Psi(w_{1})\leq\eta_{1}\Psi(w)$ and $\sup_{z^{*}\in Z}z^{*}(w_{2})\geq(1-\eta_{2})\Psi(w_{2})$, then

In particular, if $\eta_{1},\eta_{2}\leq 1/20$ then $\inf_{w\in W}\sup_{z^{*}\in Z}z^{*}(w)\geq 4/5$.

Proof. Let $w=w_{1}+w_{2}$ and observe that $\Psi(w_{2})\geq\Psi(w)-\Psi(w_{1})\geq(1-\eta_{1})\Psi(w)$. Thus, for the optimal choice of $z^{*}\in Z$,

and the claim follows because $w\in S_{\Psi}$.

For every such $t$, consider $w\in\rho S_{\Psi}$ and set $w_{1}=P_{I}w$ and $w_{2}=P_{I^{c}}w$, the coordinate projections of $w$ onto ${\rm span}(e_{i})_{i\in I}$ and ${\rm span}(e_{i})_{i\in I^{c}}$, respectively. Hence, there is a functional $z^{*}=z_{0}^{*}+(1-\eta_{2})u^{*}$ that is norming for $t$ and also satisfies

Therefore, Lemma 4.1 may be applied once $\Psi(P_{I}w)\leq\eta_{1}\Psi(w)$.

Naturally, such a shrinking phenomenon need not be true for every $w\in S_{\Psi}$; fortunately, it is only required for $w\in S_{\Psi}\cap(r(\rho)/\rho)D$ – and we will show that it is indeed the case in the three examples we present. In all three, the combination of sparsity and the right choice of the norm helps in establishing a lower bound on $\Delta(\rho)$ in two ways: firstly, the set $\Gamma_{t^{*}}(\rho)$ consists of functionals that are ‘almost norming’ for any $x$ whose support is disjoint from the support of $t^{*}$; and secondly, a coordinate projection ‘shrinks’ the $\Psi$ norm of points in $\rho S_{\Psi}\cap r(\rho)D$.

2 Δ​(ρ)Δ𝜌\Delta(\rho) in the three examples

Let us show that in the three examples, the LASSO, SLOPE and trace norm regularization, $\Delta(\rho)\geq(4/5)\rho$ for the right choice of $\rho$, and that choice depends on the degree of sparsity in each case.

If $t^{*}=v+u$ for $u\in(\rho/20)B_{1}^{d}$ and $100|{\rm supp}(v)|\leq(\rho/r(\rho))^{2}$ then $\Delta(\rho)\geq 4\rho/5$.

Since $\left\|w\right\|_{2}\leq r(\rho)$, one has $\left\|P_{I}w\right\|_{1}\leq\sqrt{s}\left\|P_{I}w\right\|_{2}\leq\sqrt{s}r(\rho)$. Therefore,

Let $\beta_{1}\geq\beta_{2}\geq...\geq\beta_{d}>0$ and recall that $\Psi(t)=\sum_{i=1}^{d}\beta_{i}t_{i}^{*}$.

Note that \Psi(t)=\sup_{z\in Z}\bigl{<}z,t\bigr{>}, for

Therefore, the extreme points of the dual unit ball are of the form $\sum_{i=1}^{d}\varepsilon_{i}\beta_{\pi_{i}}e_{i}$.

Let $1\leq s\leq d$ and set ${\cal B}_{s}=\sum_{i\leq s}\beta_{i}/\sqrt{i}$. If $t^{*}$ is $\rho/20$ approximated (relative to $\Psi$) by an $s$-sparse vector and if $40{\cal B}_{s}\leq\rho/r(\rho)$ then $\Delta(\rho)\geq 4\rho/5$.

Proof. Let $t^{*}=u+v$, for $v$ that is supported on at most $s$ coordinates and $u\in(\rho/20)B_{\Psi}$. Set $I\subset\{1,...,d\}$ to be the support of $v$ and let $z=(z_{i})_{i=1}^{d}$ be a norming functional for $v$ to be specified later; thus, $z\in\Gamma_{t^{*}}(\rho)$.

Given $t$ for which $\Psi(t-t^{*})=\rho$ and $\|t-t^{*}\|_{2}\leq r(\rho)$, one has

Since $v$ is supported in $I$, one may optimize the choice of $z$ by selecting the right permutation of the coordinates in $I^{c}$, and

Since $\|t-t^{*}\|_{2}\leq r(\rho)$, it is evident that $(t-t^{*})_{i}^{\sharp}\leq r(\rho)/\sqrt{i}$, and

Hence, if $\rho\geq 40r(\rho){\cal B}_{s}$ then $\Delta(\rho)\geq 4\rho/5$.

If $A^{*}=V+U$, where $\|U\|_{1}\leq\rho/20$ and $400{\rm rank}(V)\leq(\rho/r(\rho))^{2}$, then $\Delta(\rho)\geq 4\rho/5$.

The fact that a low-rank matrix has many norming functionals is well known and follows, for example, from .

Proof of Lemma 4.4. Recall that $S_{1}$ is the unit sphere of the trace norm and that $B_{2}$ is the unit ball of the Hilbert-Schmidt norm. Hence,

All that remains is to estimate the trace norms of the three components that are believed to be ‘low-dimension’ - in the sense that their rank is at most $s$.

Recall that $(\sigma_{i}(A))$ are the singular values of $A$ arranged in a non-increasing order. It is straightforward to verify (e.g., using the characterization of the singular values via low-dimensional approximation), that

Moreover, $\|W\|_{2}\leq r(\rho)$, therefore, being rank-$s$ operators, one has

Therefore, if $400s\leq(\rho/r(\rho))^{2}$, then $\Delta(\rho)\geq 4\rho/5$.

The three examples revisited

The estimates on $\Delta(\rho)$ presented above show that in all three examples, when $f^{*}$ is well approximated by a function whose ‘degree of sparsity’ is $\lesssim(\rho/r(\rho))^{2}$, then $\Delta(\rho)\geq 4\rho/5$ and Theorem 3.2 may be used. Clearly, the resulting error rates depend on the right choice of $\rho$, and thus on $r(\rho)$.

Because $r(\rho)$ happens to be the minimax rate of the learning problem in the class $F\cap B_{\Psi}(\rho,f^{*})$, its properties have been studied extensively. Obtaining an estimate on $r(\rho)$ involves some assumptions on $X$ and $\xi$, and the one setup in which it can be characterized for an arbitrary class $F$ is when the class is $L$-subgaussian and $\xi\in L_{q}$ for some $q>2$ (though $\xi$ need not be independent of $X$). It is straightforward to verify that an $L$-subgaussian class satisfies the small-ball condition of Assumption 2.1 for $\kappa=1/2$ and $\varepsilon=c/L^{4}$ where $c$ is an absolute constant. Moreover, if the class is $L$-subgaussian, the natural complexity parameter associated with it is the expectation of the supremum of the canonical Gaussian process indexed by the class.

Let $F\subset L_{2}(\mu)$ and set $\{G_{f}:f\in F\}$ to be the canonical Gaussian process indexed by $F$; that is, each $G_{f}$ is a centred Gaussian variable and the covariance structure of the process is endowed by the inner product in $L_{2}(\mu)$. The expectation of the supremum of the process is defined by

It follows from a standard chaining argument that if $F$ is $L$-subgaussian then

Turning to $r_{M}$, we shall require the following fact from .

Let $q>2$ and $L\geq 1$. For every $0<\delta<1$ there is a constant $c=c(\delta,L,q)$ for which the following holds. If $H$ is an $L$-subgaussian class and $\xi\in L_{q}$, then with probability at least $1-\delta$,

The complete version of Theorem 5.2 includes a sharp estimate on the constant $c$. However, obtaining accurate probability estimates is not the main feature of this note and deriving such estimates leads to a cumbersome presentation. To keep our message to the point, we have chosen not to present the best possible probability estimates in what follows.

A straightforward application of Theorem 5.2 shows that

for a constant $c$ that depends on $L,q$ and $\delta$.

for the standard Gaussian vector $G=(g_{1},...,g_{d})$ in the case of the LASSO and SLOPE and the Gaussian matrix $G=(g_{ij})$ in the case of trace norm minimization. Hence, one may obtain a bound on $r(\rho)$ by estimating this expectation in each case.

The LASSO and SLOPE. Let $(\beta_{i})_{i=1}^{d}$ be a non-increasing positive sequence and set $\Psi(t)=\sum_{i=1}^{d}t_{i}^{\sharp}\beta_{i}$.

There exists an absolute constant $C$ for which the following holds. If $\beta$ and $\Psi$ are as above, then

(and if $k=1$, the first term is set to be ).

Proof. Fix $1\leq k\leq d$. Let $J$ be the set of indices of the $k$ largest coordinates of $(|g_{i}|)_{i=1}^{d}$, and for every $w$ let $I_{w}$ be the sets of indices of the $k$ largest coordinates of $(|w_{i}|)_{i=1}^{d}$. Put $J_{w}=J\cup I_{w}$ and note that $|J_{w}|\leq 2k$. Hence,