Regularization, sparse recovery, and median-of-means tournaments

Introduction

However, in statistical problems, the joint distribution of $(X,Y)$ is unknown and the regression function is impossible to compute. Instead, a sample $\mathcal{D}_{N}=((X_{1},Y_{1}),\ldots,(X_{N},Y_{N}))$ of independent copies of the pair $(X,Y)$ is available (such that $\mathcal{D}_{N}$ and the pair $(X,Y)$ are independent).

has an acceptable performance, and the standard assumption is that the minimum is attained and $f^{*}\in{\mathcal{F}}$ is unique. We assume that ${\mathcal{F}}$ is a closed and convex subset of $L_{2}(\mu)$—where $\mu$ denotes the distribution of $X$—, guaranteeing the existence and uniqueness of $f^{*}$.

The quality of a learning procedure is typically measured by the mean squared error, which is the conditional expectation

where, for $q\geq 1$, we use the notation

A closely related, though not equivalent, measure of performance is the excess risk, defined by the conditional expectation

The goal of a statistical learning problem is to find a learning procedure that achieves a good accuracy with a high confidence. In particular, for $r>0$ and $\delta\in(0,1)$, we say that a procedure performs with accuracy parameter $r$ with confidence $1-\delta$ in the class ${\mathcal{F}}$ (e.g., for the mean squared error) if

High accuracy and high confidence (i.e., small $r$ and small $\delta$) in the given class are obviously conflicting requirements. The achievable tradeoff has been thoroughly studied and it is fairly well understood. We refer the reader to Lecué and Mendelson , Lugosi and Mendelson for recent accounts.

The most standard approach for a learning procedure is empirical risk minimization (erm), also known as least squares regression in which

(where we assume that the minimum is achieved). One may show (see, e.g., Lecué and Mendelson ) that unless the function class and target are sub-GaussianHere, Sub-Gaussian means that the $\psi_{2}$ and the $L_{2}$ norms are equivalent in ${\mathcal{F}}\cup\{0\}$; that is, there is a constant $L$ such that for any $f,h\in{\mathcal{F}}\cup\{0\}$ and any $p\geq 2$, $\|f-h\|_{L_{p}}\leq L\sqrt{p}\|f-h\|_{L_{2}}$, and that the same holds for any $Y-f(X)$ for any $f\in{\mathcal{F}}$., then empirical risk minimization is far from achieving the optimal accuracy/confidence tradeoff. The reason for the suboptimal behaviour of empirical risk minimization is that outliers distort the empirical means unless the problem is very close to being Gaussian. Thankfully, learning procedures that can tackle heavy-tailed problems exist, as it was recently pointed out by Lugosi and Mendelson with the introduction of the median-of-means tournament.

A common problem that all learning procedures encounter is that of overfitting, which occurs when the underlying class is too big relative to the (random) information at the learner’s disposal. A standard way of dealing with learning problems involving classes that are too large is giving priority to functions in the class according to some prior belief of “simplicity”. For example, in regularized risk minimization, one selects a norm $\Psi$ defined on a vector space $E$ containing ${\mathcal{F}}$. A small value of $\Psi(f)$ is interpreted as simplicity and simple functions are given priority by way of adding a penalty term to the empirical risk that is proportional to $\Psi(f)$. In particular, for some regularization parameter $\lambda>0$, a regularized risk minimizer selects

and the term $\Psi(f)$ is sometimes called the penalty.

Just as the tournament procedure from outperforms empirical risk minimization (in fact, the tournament procedure attains the optimal tradeoff between accuracy and confidence under minimal assumptions), the regularized tournament which we present here, outperforms regularized risk minimization. Since regularized procedures require the minimization of a functional that has the empirical mean as a component, they suffer from the same disadvantages as empirical risk minimization. Therefore, the accuracy/confidence tradeoff exhibited by regularized risk minimization is suboptimal once one leaves the sub-Gaussian realm, and deteriorates further if the problem is more heavy-tailed. In contrast, we show that the regularized tournament attains the optimal accuracy/confidence tradeoff under rather minimal conditions and, in particular, in heavy-tailed problems.

The paper is organized as follows. In Section 2 we introduce a new regularized “tournament” procedure in a quite general framework and illustrate how it works on an important specific case, the tournament lasso (see Section 2.1). In Section 3 the main general performance bound is presented for the regularized tournament procedure under certain specific choice of the parameters of the procedure. The proof of the main result is detailed in Section 4. Finally, in Section 5 two examples are worked out. The first is a “tournament” version of lasso (introduced in Section 2.1) and the second is the tournament slope, a generalized version of tournament lasso.

The procedure

Let us now describe the regularized tournament procedure. Recall that the learner is given a closed and convex class of functions ${\mathcal{F}}\subset L_{2}(\mu)$ and a regularization function $\Psi$ which is assumed to be a norm on ${\rm span}({\mathcal{F}})$.

The first three stages of the procedure use independent data. In order to accommodate this, one needs to split the available data into three independent parts. For simplicity of the presentation, we assume that these parts have equal size, each containing $N$ samples. (Thus, the total sample size is $3N$ rather than $N$ but this change of convention only affects the constants in the bounds that we do not make explicit in any case.)

$(2)$ split $(X_{i})_{i=1}^{N}$ to $n_{1}$ disjoint blocks $(I_{j})$ of equal size, denoted by $m_{1}=N/n_{1}$;

More accurately, the second phase is defined as follows:

(observe that it is possible that $f\gg h$ and $h\gg f$ at the same time);

The fourth phase: naming a winner

The first three phases are the key components of the procedure. Out of the three, the first one is an adaptation of the distance oracle used in and which had been introduced in ; the third component is essentially the same as the champions league stage in the tournament procedure from .

The truly new component is the second phase. Its analysis combines ideas from (which focused on regularized risk minimization in ‘sparse’ problems) and from . As it is the main novelty in this article we present it in detail and only sketch the arguments needed in the analysis of the other components.

1 The tournament lasso

The problem with the lasso is that when either the class members $\left\langle t,X\right\rangle$ or the target $Y$ are heavy-tailed, the tradeoff between the accuracy with which the lasso performs and the confidence with which that accuracy is attained is far from optimal. That suboptimal tradeoff is what the tournament lasso aims to remedy.

Let us go through the four phases of the tournament lasso.

In what follows, $C(L),C_{0}(L),\ldots,C_{4}(L)$ denote appropriately chosen constants whose value depends only on $L$. (The precise form may be extracted from the analysis but it is of secondary importance for our purpose.)

The fourth phase

The following theorem, proved in Section 5.1, summarizes the performance of the tournament lasso.

Theorem 2.6 shows that the tournament lasso attains the optimal accuracy/confidence tradeoff even though $f^{*}(X)-Y$ can be heavy-tailed. In fact, the estimate is what one would expect in the most friendly of scenarios: if $X$ were a sub-Gaussian random vector (i.e., linear forms exhibiting a $\psi_{2}-L_{2}$ norm equivalence with constant $L$ rather than an $L_{p}-L_{2}$ moment equivalence going only up to $p\sim\log d$), and $f^{*}(X)-Y$ were a Gaussian random variable, independent of $X$. The lasso does not come close to such an accuracy/confidence tradeoff under the weak moment assumption of Theorem 2.6.

Note that $r=c_{3}\|W\|_{L_{2}}\sqrt{\frac{s}{N}\log\left(\frac{ed}{s}\right)}$ is the best accuracy parameter one can hope for even if the learner knows that $t_{0}$ is $s$-sparse and $X$ and $W$ are Gaussian. The difference between the performance of the tournament lasso and the standard lasso can be seen in the confidence with which this accuracy is attained. In the situation described in Theorem 2.6, the standard lasso performs with that accuracy parameter only with constant confidence, because all that we assume on $W$ is that it is square-integrable. In contrast, the tournament lasso attains the accuracy (2.6) with the optimal exponential probability estimate (2.4).

The tournament lasso does not require prior information on the degree of sparsity of $t_{0}$ to be carried out, but its success does depend on having a large-enough sample and on that $\widehat{r}$ is in the right range. The former is a constraint that any recovery procedure faces while the latter is easily achieved by running the procedure for $\widehat{r}_{j}=r_{0}/2^{j}$ for a large initial value of $r_{0}$, followed by a standard validation argument at each step.

The one item that does require extra attention is that an upper estimate on $\|W||_{L_{2}}$ is used in the choice of parameters of the tournament lasso. At times one is simply given that information; this is often the case in signal processing problems, where the nature of the ‘noise’ is known to the learner. If not, one may use the data-dependent procedure from which holds for more general noise models: it leads to upper and lower estimates on $\|f^{*}(X)-Y\|_{L_{2}}$ that are sharp up to absolute multiplicative constants and under minimal assumptions.

Of course, proving Theorem 2.6 requires some work, and the choice of parameters used in the first three phases has to be clarified. We explain the choice in the general case in the next two sections and return to the example of the tournament lasso in Section 5.

The main result

In the general setup we study, we merely assume a rather weak fourth-moment assumption. More precisely, we work under the following conditions.

Let ${\mathcal{F}}\subset L_{2}(\mu)$ be a locally compact, convex class of functions. Let $Y\in L_{2}$ and assume that, for some constant $L>0$,

$\bullet$ for every $f,h\in{\mathcal{F}}$, $\|f-h\|_{L_{4}}\leq L\|f-h\|_{L_{2}}$;

$\bullet$ $\|f^{*}-Y\|_{L_{4}}\leq\sigma_{4}$ for a known value $\sigma_{4}$.

The condition that $\|f^{*}-Y\|_{L_{4}}\leq\sigma_{4}$ may easily be replaced by a combination of two assumptions: that for every $f\in{\mathcal{F}}$, $\|f-Y\|_{L_{4}}\leq L\|f-Y\|_{L_{2}}$; and that $\|f^{*}-Y\|_{L_{2}}\leq\sigma$ for some known constant $\sigma>0$. Also, in the case of independent additive noise, that is, when $Y=f_{0}(X)+W$ where $f_{0}\in{\mathcal{F}}$ and $W$ that is mean-zero, square-integrable and independent of $X$, the assumption that $\|f^{*}-Y\|_{L_{4}}\leq\sigma_{4}$ may be replaced by the weaker one, that $\|W\|_{L_{2}}\leq\sigma$ for a known constant $\sigma$.

The necessary modifications to the proofs are straightforward and we do not explore this observation further. Also, as noted previously, we refer the reader to for a data-dependent procedure of estimating $\|f^{*}-Y\|_{L_{2}}$ which may be easily modified to an estimate on $\|f^{*}-Y\|_{L_{4}}$. Since that is not the main focus of this paper we do not pursue it further and instead assume that the learner has access to $\sigma_{4}$ or to $\sigma$.

The complexity is measured in terms of four parameters, depending both on the class ${\mathcal{F}}$ and the distribution of $(X,Y)$. The four play an essential role in describing the optimal performance of learning procedures and for detailed discussion on the meaning we refer to Mendelson and Lugosi and Mendelson .

Before we define the four parameters we need some notation. Denote the unit ball in $L_{2}(\mu)$ by $D=\{f:\|f\|_{L_{2}}\leq 1\}$ and let $S=\{f:\|f\|_{L_{2}}=1\}$ be the unit sphere. For $h\in L_{2}(\mu)$ and $r>0$, we write $D_{h}(r)=\{f:\|f-h\|_{L_{2}}\leq r\}$. In a similar fashion for the norm $\Psi$ used as a regularization function, let ${\cal B}=\{f:\Psi(f)\leq 1\}$, set $\rho{\cal B}=\{f:\Psi(f)\leq\rho\}$ and ${\cal B}_{h}(\rho)=\{f:\Psi(f-h)\leq\rho\}$.

In what follows we make two important modifications to the definitions of the complexity parameters used in . First, just like in the above-mentioned articles, we are interested in “localized” classes. However, because regularized procedures are affected by two norms, $\Psi$ and $L_{2}(\mu)$, the localization has to be with respect to both of them. Therefore, the “localization” of ${\mathcal{F}}$, centred in $h$ and of radii $\rho,r>0$ is defined by

The second minor modification is that each complexity parameter is associated with the ‘worse case’ centre $h\in{\mathcal{F}}^{\prime}$ for some fixed ${\mathcal{F}}^{\prime}\subset{\mathcal{F}}$, and not necessarily with the whole of ${\mathcal{F}}$.

Two of the four parameters are defined using the notion of packing numbers.

Given a set $H\subset L_{2}(\mu)$ and $\varepsilon>0$, denote the $\varepsilon$-packing number of $H$ by ${\cal M}(H,\varepsilon D)$. In other words, ${\cal M}(H,\varepsilon D)$ is the maximal cardinality of a subset $\{h_{1},\ldots,h_{m}\}\subset H$, for which $\|h_{i}-h_{j}\|_{L_{2}}\geq\varepsilon$ for every $i\not=j$.

Fix $\rho>0$ and $h\in{\mathcal{F}}$. For $\kappa,\eta>0$, set

For ${\mathcal{F}}^{\prime}\subset{\mathcal{F}}$ let

Fix $h\in{\mathcal{F}}$ and $\rho>0$. Let $\kappa>0$, $0<\eta<1$, and define

Also, for ${\mathcal{F}}^{\prime}\subset{\mathcal{F}}$ let

For the remaining two complexity parameters, 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}$.

Fix $h\in{\mathcal{F}}$ and $\rho>0$. For $\kappa>0$ let

and for ${\mathcal{F}}^{\prime}\subset{\mathcal{F}}$ set $r_{E}(\kappa,\rho)=\sup_{h\in{\mathcal{F}}^{\prime}}r_{E}(\kappa,h,\rho)$.

Finally, suppose that the distribution of $(X,Y)$ is such that $\|Y-f^{*}(X)\|_{L_{4}}\leq\sigma_{4}$ for a known constant $\sigma>0$. The “complexity” of ${\mathcal{F}}$ relative to centres in ${\mathcal{F}}^{\prime}$ and radius $\rho$ is

Here $c_{1},c_{2}$ are appropriate positive numerical constants. (“Appropriate” means that $r^{*}({\mathcal{F}},{\mathcal{F}}^{\prime},\rho)$ satisfies Propositions 4.1, 4.4 and 4.7 below). The existence of such constants is proved in when ${\mathcal{F}}^{\prime}={\mathcal{F}}$, i.e., when any function in ${\mathcal{F}}$ is a ‘legal choice’ of a centre, and under Assumption 3.1. In that case, the constants depend only on the value of $L$.

When ${\mathcal{F}}$ and ${\mathcal{F}}^{\prime}$ are clear from the context, we simply write $r^{*}(\rho)$ for $r^{*}({\mathcal{F}},{\mathcal{F}}^{\prime},\rho)$.

2 Properties of the hierarchy

Recall that ${\mathcal{F}}$ is a (convex) subset of a normed space $(E,\Psi)$; $E$ is also a subspace of $L_{2}(\mu)$, though the norms $\Psi$ and $\|\cdot\|_{L_{2}(\mu)}$ may have nothing to do with each other. Let $B_{\Psi^{*}}$ and $S_{\Psi^{*}}$ denote the unit ball and unit sphere in the dual space to $(E,\Psi)$, respectively. Therefore, $B_{\Psi^{*}}$ consists of all the linear functionals $z\in E^{*}$ for which $\sup_{\{x\in E:\Psi(x)=1\}}|z(x)|\leq 1$. A linear functional $z^{*}\in S_{\Psi^{*}}$ is a norming functional for $f\in E$ if $z^{*}(f)=\Psi(f)$.

Let $\Gamma_{f}(\rho)\subset S_{\Psi^{*}}$ be the collection of functionals that are norming for some $v\in{\cal B}_{f}(\rho/20)$. Set

where the inner infimum is taken in the set

A lower bound on the term $\Psi(h)-\Psi(f)$ plays an essential role in the study of the elimination phase of the regularized tournament, when one has to compare

(1) ${\mathcal{F}}={\mathcal{F}}_{1}\supset{\mathcal{F}}_{2}\supset\cdots\supset{\mathcal{F}}_{K}$ is a finite hierarchy;

We are now ready to specify the parameters used in the definition of a regularized tournament.

$\bullet$ Let $\alpha$, $\beta$, $m_{1}$, $\theta_{1}$ and $\theta_{2}$ be well chosen constants that depend only on the norm equivalence constant $L$ from Assumption 3.1, and assume that one has access to the value $\sigma_{4}$ from that assumption.

We set the following choice of parameters:

With these choices set in place, let us formulate the main result of this article.

3 Discussion

We emphasize that Theorem 3.9 is quite general though finding the adequate parameters of the procedure requires additional work. For the “tournament” version of lasso and slope we work out the details in Section 5 under certain assumptions (such as isotropic design vector $X$ and approximately sparse linear regression function) for illustration. Some of these assumption may be weakened but we prefer to keep the presentation as simple as possible.

Related work. The sensitivity of empirical risk minimization (or least squares regression) to heavy-tailed distributions has been pointed out and several proposals of robust regression function estimates have been made that avoid this sensitivity. We refer to Audibert and Catoni , Hsu and Sabato , Lerasle and Oliveira , Minsker , Brownlees, Joly, and Lugosi , Lugosi and Mendelson for a sample of the literature. This paper mostly builds upon the methodology of median-of-means tournaments, developed in , (see also Lugosi and Mendelson ). Here we extend this methodology to the analysis of regularized robust risk minimization similarly to how the paper of Lecué and Mendelson analyzes standard regularized risk minimization. The analysis of the lasso and slope procedures of was extended and generalized by Bellec, Lecué, and Tsybakov . In an independent parallel work to ours, and building on the arguments developed in , Lecué and Lerasle point out a connection of median-of-means tournaments to Le Cam’s estimators, develop a version of lasso–the so-called mom-lasso–and prove a performance bound quite similar to Theorem 2.6.

Analyzing the four phases

where ${\rm Med}_{m}(w)$ is a median of the $n$ values $\frac{1}{m}\sum_{i\in I_{j}}|(f-h)(X_{i})|$.

The behaviour of $\Phi$ described below has been established in Mendelson (see also Lugosi and Mendelson ):

Let ${\mathcal{F}}$ satisfy Assumption 3.1. There exist constants $m$, $0<\alpha<1<\beta$, and $\kappa,\eta$ and $c$, all of them depending only on $L$, for which the following holds.

Then, with probability at least $1-2\exp(-cN)$, for any $h\in{\mathcal{F}}$ that satisfies $\Psi(f,h)\leq\rho$,

$(1)$ if $\Phi_{\mathcal{C}_{1}}(f,h)\geq\beta r$ then

$(2)$ if $\Phi_{\mathcal{C}_{1}}(f,h)<\beta r$ then $\|f-h\|_{L_{2}}\leq(\beta/\alpha)r$.

Although Proposition 4.1 is formulated for a designated single centre $f$, it is straightforward to extend it to any centre in ${\mathcal{F}}$ and obtain a uniform distance oracle that holds for any pair $f,h\in{\mathcal{F}}$.

for a well-chosen constant $\theta_{1}$ that depends only on the equivalence constant $L$ from Assumption 3.1. We also set

with the choices of both constants $\theta_{1}$ and $\theta_{2}$ specified below.

The function $f$ defeats $h$ (denoted by $f\succ h)$ if

1 Proof of Proposition 4.4—highlights

To explain why this elimination phase preforms well even when ${\mathcal{F}}$ is very large, define, for each block $I_{j}$ ($j=1,\ldots,n$),

Note that the regularized empirical excess risk of $h$ on block $I_{j}$ is $B^{\lambda}_{h,f^{*}}(j)$.

which is the natural decomposition of the empirical excess risk functional into its quadratic and multiplier components. Setting

The first observation we require is a version of a deterministic result from [8, Theorem 3.2] (see the appendix for the proof).

and if also $\|h-f^{*}\|_{L_{2}}\geq r$ then

Moreover, if $f\in{\mathcal{F}}$ such that $f=f^{*}+\alpha(h-f^{*})$ for $\alpha>1$ then also

The fact that we have the required control over coordinate blocks is formulated in the following lemma. Its proof may be found in the appendix.

Recall that the function $f$ wins its home match against $h$ (denoted by $f\gg h$) if

Combining all these observations, Corollary 4.8 describes the outcome of the first three phases in the regularized tournament procedure, for each member of the hierarchy.

Selection of a final winner

which completes the proof of Theorem 3.9.

Examples

In what follows we present two examples: a tournament version of lasso, and also, a tournament version of another popular sparse recovery procedure—slope.

the value of the constant $c_{1}$ is given in Theorem 5.2.

Assume further that $\|f^{*}(X)-Y\|_{L_{4}}\leq\sigma_{4}$ for a known constant $\sigma_{4}$.

In other words, Assumption 5.1 means that linear forms satisfy a sub-Gaussian moment growth, but only up to a rather low exponent—logarithmic in the dimension of the underlying space. This moment assumption is a sufficient and almost necessary condition for the celebrated basis pursuit procedure to have a unique minimizer (see ), and as such, it is a natural assumption when studying such sparsity-driven bounds. Note that even with Assumption 5.1 replacing Assumption 3.1, the fact that the ‘noise’ $\xi=f^{*}(X)-Y$ may only be in $L_{4}$ means that there is not hope that

exhibits a fast tail decay, even in the extreme case when $|T|=1$. This indicates why regularized risk minimization can only perform with a rather weak accuracy/confidence tradeoff in such situations.

On the other hand, (5.1) suffices to obtain bounds on the expectation of empirical and multiplier processes, as long as the indexing set has enough symmetries, and a suitable bound on the expectation suffices for the analysis of regularized tournaments.

Given a vector $x=(x_{i})_{i=1}^{n}$, let $(x_{i}^{*})_{i=1}^{n}$ be the non-increasing rearrangement of $(|x_{i}|)_{i=1}^{n}$.

The following fact has been established in :

There exists an absolute constant $c_{1}$ and for $K\geq 1$, $L\geq 1$ and $q_{0}>2$ there exists a constant $c_{2}$ that depends only on $K$, $L$ and $q_{0}$ for which the following holds. Consider

$\bullet$ $\xi\in L_{q_{0}}$ for some $q_{0}>2$,

If $(X_{i},\xi_{i})_{i=1}^{N}$ are independent copies of $(X,\xi)$ then

Therefore, as long as $V$ is sufficiently symmetric and linear forms exhibit a sub-Gaussian moment growth up to $p\sim\log d$, the expectations of empirical and multiplier processes indexed by $V$ behave as if $X$ were the standard Gaussian vector and $\xi$ were independent of $X$. In the cases we are interested in the indexing sets have enough symmetries, and since $\xi\in L_{4}$, the conditions of Theorem 5.2 hold for $q_{0}=4$.

In this section we prove Theorem 2.6, the performance bound of the “tournament lasso” procedure.

Note that for any $h=\left\langle t_{0},\cdot\right\rangle$ and every $\rho,r>0$,

respectively. The indexing set $V_{\rho,r}=\rho B_{1}^{d}\cap rB_{2}^{d}$ is invariant under coordinate permutations and sign reflections, and therefore satisfies the conditions of Theorem 5.2. Hence, an upper bound on $r_{E}$ follows if

Equations (5.4) and (5.5) cannot be improved; they are tight bounds on (5.2) and (5.3) when, for example, $X=(g_{1},\ldots,g_{d})$ and $\xi$ is a Gaussian variable that is independent of $X$.

which is precisely the type of condition in (5.4).

On the other hand, there is a functional $z$ that is norming for both $t_{0}$ and $P_{I^{c}}t=\sum_{i\in I^{c}}t_{i}e_{i}$; hence,

This shows that, as long as the ratio $\rho/r$ is larger than the square-root of the degree of sparsity of vectors we are interested in, $\Delta(\rho,r)\geq(4/5)\rho$ as our procedure requires. A similar observation is true if $t_{0}$ is not sparse, but rather well approximated by an $s$-sparse vector (see for a detailed argument).

Set $k=(\rho/r)^{2}$ and assume without loss of generality that $k$ is an integer. We also restrict ourselves to values $1\leq k\leq d$, intuitively because the above implies that $(\rho/r)^{2}$ should capture the degree of sparsity. Recall that

(see, e.g. for the standard proof). Hence, (5.4) becomes

We consider only the case $N\leq Cd$, which is the more interesting range in sparse recovery—when the number of given linear measurements is significantly smaller than the dimension of the underlying space. An argument following the same path may be used when $N\geq Cd$ and we omit it.

It follows from a rather tedious computation that (5.6) holds provided that

as long as $\|\xi\|_{L_{4}}d/\sqrt{N}\rho\geq c^{\prime}$.

Using the constraint that $\rho/r\geq c\sqrt{s}$, it is evident from (5.8) that

$s\leq c(L)N/\log\left({ed}/{N}\right)$, and that

Therefore, to have a ‘legal’ choice of $\rho$ and $r$, we must have

This naturally leads to the choices made in Section 2.1: set

2 The tournament slope

As a second example, we present and analyze a “tournament” version of the regularized risk minimization procedure slope. slope is defined using a set of non-increasing weights $(\beta_{i})_{i=1}^{d}$. The corresponding norm is

where as always, $(z_{i}^{*})_{i=1}^{d}$ denotes the non-increasing rearrangement of $(|z_{i}|)_{i=1}^{d}$. Clearly, slope is a generalized version of lasso, as the latter is given by the choice $\beta_{i}=1$ for $1\leq i\leq d$.

Just like the lasso, most of the known results on the performance of slope hold only when both the random vector $X$ and the target $Y$ have well behaved tails.

The tournament slope we present below is defined for the penalty $\Psi(z)=\sum_{i=1}^{d}\beta_{i}z_{i}^{*}$, where $\beta_{i}\leq C\sqrt{\log(ed/i)}$. We obtain the following performance bound:

the tournament slope produces $\widehat{t}$ that satisfies

The estimate corresponds to the optimal accuracy/confidence tradeoff any procedure can attain even if the learner knows that $t_{0}$ is $s$-sparse. Moreover, in the heavy-tailed situations we study here, the performance of slope is significantly weaker than in Theorem 5.3.

The argument we use here is similar to the one used for the tournament lasso, and so we skip most of the details.

In tournament slope one selects $\beta_{i}\leq c_{0}\sqrt{\log(ed/i)}$ and therefore the corresponding indexing set is contained in

Because $V_{\rho,r}$ has enough symmetries, one may apply Theorem 5.2, leading to an upper bound on $r_{E}$ when

Next, one may verify (see Lemma 4.3 in ) that if we set $B_{s}=\sum_{i\leq s}\beta_{i}/\sqrt{i}$ and if $B_{s}\lesssim r/\rho$, then $\Delta(\rho,r)\geq(4/5)\rho$ for centres that are ‘well approximated’ by $s$-sparse vectors. Also, for our choice of $\beta_{i}$, $B_{s}\lesssim C\sqrt{s\log(ed/s)}$. Hence, for a fixed degree of sparsity $1\leq s\leq d$, one has the constraint that

for a constant $C_{1}$ that depends only on $c_{0}$.

Following the same path used for the tournament lasso let

Appendix A Additional proofs

The proofs of Lemma 4.5 and Lemma 4.6 are, in fact, the same as in and , respectively. The minor modifications to the original proofs are presented in this appendix solely for the sake of completeness and not in full detail.

The proof of Lemma 4.5 follows the same path as that of Theorem 3.2 in . Let us begin by examining

Fix $v\in{\cal B}_{f^{*}}(\rho/20)$ and write $f^{*}=u+v$; thus $\Psi(u)\leq\rho/20$. Set $z$ to be a linear functional that is norming for $v$ and observe that for any $f\in E$,

In other words, if $\lambda$ is chosen to satisfy both (A.2) and (A.5), $f\in{\mathcal{F}}$ and $\Psi(f-f^{*})=\rho$, it follows that

Next, if $\Psi(f-f^{*})>\rho$, there are $\theta\in(0,1)$ and $h\in{\mathcal{F}}$ that satisfy

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

If, on the other hand, $\|h-f^{*}\|_{L_{2}}\leq r$, then

Now, all that remains is to control $f\in{\mathcal{F}}\cap{\cal B}_{f^{*}}(\rho)$ and show that if $\|f-f^{*}\|_{L_{2}}\geq r$, then

Proof of Lemma 4.6

The first part of Lemma 4.6 is identical to Lemma 5.1 from , with the trivial modification that the constant $-C/4$ replaces $-3C/4$ used in . The second part of Lemma 4.6 was not needed in , but its proof follows the same path as Lemma 5.1 from .

and by a straightforward symmetrization argument,

Applying Assumption 3.1, it is evident that

where we use the fact that $\sqrt{n/N}\leq\sqrt{\theta}r/\sigma_{4}$ and select $t=Cr^{2}/8$ and $\theta=\theta(\tau,L)$. Therefore,

and with probability at least $1-2\exp(-c\tau^{2}n)$,

The rest of the argument is identical to the proof of Lemma 5.1 from : let ${\mathcal{H}}$ be a maximal separated subset of ${\mathcal{F}}\cap{\cal B}_{f^{*}}(\rho)\cap D_{f^{*}}(r)$ with respect to the $L_{2}$ norm, of cardinality $\exp(c\tau^{2}n/2)$, and with the following property: for any $f\in{\mathcal{F}}\cap{\cal B}_{f^{*}}(\rho)\cap D_{f^{*}}(r)$ there is $h\in{\mathcal{H}}$ for which

here $\varepsilon$ denotes the mesh of the net. The existence of such a separated set is established in (see Lemma 5.3), and one may show that the mesh $\varepsilon$ is a small proportion of $r$.

By (A.6), we have that with probability at least $1-2\exp(-c\tau^{2}n/2)$, for every $h\in{\mathcal{H}}$

For every $f\in{\mathcal{F}}\cap{\cal B}_{f^{*}}(\rho)\cap D_{f^{*}}(r)$ let $\pi f\in{\mathcal{H}}$ be as in (A.7), and at the heart of the proof of Lemma 5.4 in is that with probability at least $1-2\exp(-c_{1}\tau^{2}n)$,

Combining (A.8) and (A.9), there is an event of probability at least $1-2\exp(-c_{2}\tau^{2}n)$ on which for any $f\in{\mathcal{F}}\cap{\cal B}_{f^{*}}(\rho)\cap D_{f^{*}}(r)$ there is a set of coordinate blocks $(I_{j})_{j\in J}$, of cardinality $|J|\geq(1-\tau)n$ and for $j\in J$,

Acknowledgements

We thank the referees for valuable suggestions that significantly helped us improve the presentation.

References