Learning without Concentration for General Loss Functions

Introduction

Next, one may choose a procedure that uses the data $(X_{i},Y_{i})_{i=1}^{N}$ to produce a (random) function $\hat{f}\in F$.

The effectiveness of $\hat{f}$ may be measured in several ways, and the two we will focus on here lead to the prediction/estimation problem.

Given a procedure $\hat{f}$, find the ‘smallest’ functions ${\cal E}_{p}$ and ${\cal E}_{e}$ possible for which the following holds. If $F\subset L_{2}(\mu)$ is a class of functions and $Y$ is the unknown target, then with probability at least $1-\delta$ over samples $(X_{i},Y_{i})_{i=1}^{N}$,

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

The functions ${\cal E}_{p}$ and ${\cal E}_{e}$ may depend on the structure of $F$, the sample size $N$, the probability $\delta$, some ‘global’ properties of $Y$ (e.g., its $L_{q}$ norm), etc.

${\cal E}_{p}$ measures the ‘predictive capabilities’ of $\hat{f}$, that is, whether $\hat{f}$ is likely to be almost as effective as the best possible in the class - $f^{*}$. ${\cal E}_{e}$ measures the distance between $\hat{f}$ and $f^{*}$, with respect to the underlying $L_{2}(\mu)$ metric.

The amount of literature centred around the theory of prediction and estimation is extensive and goes well beyond what can be reasonably surveyed here. We refer the reader to the manuscripts , , , , , and as possible starting points for information on the history of the problem as well as for more recent progress.

The procedure we will focus on here is empirical risk minimization (ERM), in which ${\hat{f}}$ is selected to be a function in $F$ that minimizes the empirical risk

where here, and throughout the article, $P_{N}$ denotes the empirical mean associated with the random sample.

Unfortunately, some of the assumptions that are commonly used in literature are highly restrictive, though seemingly benign. And, among the more harmful assumptions are that the loss is a Lipschitz function and that functions in $F$ and $Y$ are uniformly bounded.

The origin of these assumptions is technical: they are an outcome of the ‘classical’ method of analysis used to tackle Problem 1.2. The method itself is based on tools from Empirical Processes Theory, most notably, on contraction and concentration arguments that are simply false without imposing the right assumptions on the class, the target and the loss. However, the assumptions leave a large number of natural problems out of reach.

We will present an example of the ‘classical’ method in Appendix A in some detail, but for the time being, let us present an outline of its main ideas and shortcomings.

To that end, consider the excess loss functional associated with $f\in F$,

Naturally, concentration results come at a cost, and estimates such as

require strong assumptions on the random variables involved – for example, that functions in $F$ and $Y$ are uniformly bounded (see the books for more details on concentration of measure phenomena).

The need for two-sided concentration estimates has been the driving force behind the assumption that functions in $F$ and $Y$ are uniformly bounded. And, although one can relax the uniform boundedness assumption (see, e.g., ) and still obtain (1.1), a necessary condition for two-sided inequalities like (1.1) is that class members exhibit rapidly decaying tails (e.g. a subgaussian behaviour), still forcing one to impose strong tail assumptions.

Finally, and possibly the most costly step in the classical method is contraction, in which one combines the fact that class members and the target are uniformly bounded functions and that the loss is Lipschitz on the ranges of the functions $f(X)-Y$. This combination allows one to bound the empirical process indexed by the excess loss class using an empirical process indexed by functions of the form $f-f^{*}$ (see Appendix A for more details).

One result that is based on the classical method and that uses the full strength of the two assumptions – that class members and the target are uniformly bounded and that the loss is Lipschitz, is Theorem 1.3 below, proved originally in . It will serve as a preliminary benchmark for our discussion.

Let $D_{f^{*}}$ be the $L_{2}(\mu)$ ball of radius $1$, centred in $f^{*}$. Thus, $\{f\in F:\|f-f^{*}\|_{L_{2}}\leq r\}=F\cap rD_{f^{*}}$. For every $r>0$, let

where $(\varepsilon_{i})_{i=1}^{N}$ are independent, symmetric, $\{-1,1\}$-valued random variables that are independent of $(X_{i})_{i=1}^{N}$, and the expectation is taken with respect to both $(X_{i})_{i=1}^{N}$ and $(\varepsilon_{i})_{i=1}^{N}$. Finally, set

A version of (1.5) will be presented in Appendix A.

$\bullet$ $Y$ is not bounded (because of the gaussian noise).

An additional downside of Theorem 1.3 is that even in situations that do fall within its scope, resulting bounds are often less than satisfactory.

One example (out of many) indicating the suboptimal nature of Theorem 1.3 is the persistence problem, which will be presented in Appendix B.

The suboptimal behaviour of Theorem 1.3 goes well beyond an isolated example. It is endemic and is caused by the nature of the complexity parameter used to govern the rates ${\cal E}_{p}$ and ${\cal E}_{e}$.

Indeed, when considering likely sources of error in prediction or estimation, two generic reasons spring to mind:

$\bullet$ $(X_{1},..,X_{N})$ is merely a sample and two functions in $F$ can agree on that sample, but still be very different. This leads to the notion of the version space: a random subset of $F$, defined by

and measures the way in which a random sample can be used to distinguish between class members. Clearly, the $L_{2}(\mu)$ diameter of the version space is an intrinsic property of the class $F$ and has nothing to do with the noiseWe will refer to $f^{*}(X)-Y$ as the noise of the problem. This name makes perfect sense when $Y=f_{0}(X)+W$ for a symmetric random variable $W$ that is independent of $X$, and we will use it even when the target does not have that particular form. $\xi=f^{*}(X)-Y$. Standard arguments show (see, e.g. ) that even in noiseless problems, when $Y=f_{0}(X)$ for some $f_{0}\in F$, it is impossible to construct a procedure whose error rates constantly outperform the $L_{2}$ diameter of the version space.

$\bullet$ Measurements are noisy: one does not observe $f^{*}(X_{i})$, but rather $Y_{i}$. Since results in certain specific cases, as well as common sense, indicate that the ‘closer’ $Y$ is to $F$, the better the behaviour of ${\cal E}_{p}$ and ${\cal E}_{e}$ should be, ${\cal E}_{p}$ and ${\cal E}_{e}$ should depend, in one way or another, on the ‘noise level’ of the problem, as captured by a natural distance between the target and the class.

With this in mind, it is reasonable to conjecture that ${\cal E}_{p}$ and ${\cal E}_{e}$ should exhibit two regimes, captured by two different complexity parameters. Firstly, a ‘low noise’ regime, in which the ‘noise’ $\xi=f^{*}(X)-Y$ is sufficiently close to zero in the right sense, and the behaviour of ERM is similar to its behaviour in the noise-free problem – essentially the $L_{2}$ diameter of the version space. Secondly, a ‘high noise’ regime, in which mistakes occur because of the way the loss affects the interaction between class members and the noise.

Theorem 1.3 yields only one regime that is governed by a single complexity parameter. This parameter does not depend on the noise $\xi=f^{*}(X)-Y$, except via a trivial $L_{\infty}$ bound, and depends solely on the correlation of the set $\{(f(X_{i}))_{i=1}^{N}:f\in F\}$ (the so-called random coordinate projection of $F$) with a generic random noise model, represented by a random point in $\{-1,1\}^{N}$ that may have nothing to do with the actual noise.

The main goal of this article is to address Problem 1.2 by showing that ${\cal E}_{p}$ and ${\cal E}_{e}$ indeed have two regimes. Each one of those regimes is captured by a different parameter: firstly, an ‘intrinsic parameter’ that depends only on the class and not on the target or on the loss, and which governs low-noise problems, in which $Y$ is sufficiently close to $F$; secondly, an external parameter that captures the interaction of the class with the noise and with the loss, and dominates in high-noise situations, when $Y$ is far from $F$.

Moreover, a solution to Problem 1.2 has to hold without the restrictive assumptions of Theorem 1.3, namely:

$\bullet$ The class $F$ need not be bounded in $L_{\infty}$, but rather satisfies weaker tail conditions.

$\bullet$ The target $Y$ need not be bounded (in fact, $Y\in L_{2}$ suffices in most cases).

The two noise regimes and the fact that they are captured by an intrinsic parameter in low-noise situations, and an external parameter in high noise cases was first observed in for the problem of subgaussian learning relative to the squared loss. We will sketch that argument here, as it will serve as a more useful benchmark than Theorem 1.3 in what follows. Also, for the sake of brevity, we will only study the estimation problem, as the prediction problem requires an additional argument (see the presentation in for more details).

By the Giné-Zinn symmetrization theorem , the latter is essentially equivalent to the symmetrized multiplier process

Assume that on an event with high probability, one has:

$\bullet$ If $\|f-f^{*}\|_{L_{2}}>r_{Q}$ then

$\bullet$ If $\|f-f^{*}\|_{L_{2}}>r_{M}$ then

(which is equivalent to a similar inequality for the symmetrized process in (1.8)).

Hence, on that event, if $\|f-f^{*}\|_{L_{2}}\geq\max\{r_{Q},r_{M}\}$ then $P_{N}{\cal L}_{f}>0$ and $f$ is not an empirical minimizer. Therefore,

This decomposition is at the heart of the argument used in , under the assumption that $F$ is a convex, $L$-subgaussian class of functions:

and $f\in L_{\psi_{2}}$ if $\|f\|_{\psi_{2}}<\infty$.

A class of functions is $L$-subgaussian if for every $f,h\in F\cup\{0\}$, $\|f-h\|_{\psi_{2}}\leq L\|f-h\|_{L_{2}}$.

To formulate the result from and, in particular, identify in the subgaussian case the parameters $r_{Q}$, $r_{M}$ and the high probability event, one requires several additional definitions.

It turns out that one may identify $r_{Q}$ and $r_{M}$ using the gaussian parameters $s_{Q}$ and $s_{M}$ defined below. For the sake of simplicity, we will assume that $F$ is centrally-symmetric (that is, if $f\in F$ then $-f\in F$), though the modifications needed in the definition when it is not are minor – as the symmetry allows one to use a ball centred in rather than in $f^{*}$.

Let $D$ be the unit ball in $L_{2}(\mu)$. For every $\eta_{1},\eta_{2}>0$, let

In both cases, if the set is empty, set $s_{M}(\eta_{1})=d_{F}(L_{2})$ (resp. $s_{Q}(\eta_{2})=d_{F}(L_{2})$).

The key feature of the subgaussian setup is that the quadratic and multiplier processes exhibit a strong concentration phenomenon:

There exists absolute constants $c_{1}$ and $c_{3}$, and a constant $c_{2}$ that depends only on $L$ for which the following holds.

Assume that $F$ is an $L$-subgaussian class of functions and that $\xi\in L_{\psi_{2}}$. For any $t\geq c_{1}$, with probability at least $1-2\exp(-c_{2}(L)t^{2}k_{F})$,

The fixed point $s_{M}$ arises from the symmetrized multiplier process. Indeed, by the first part of Theorem 1.7, if $H$ is an $L$-subgaussian class and $\xi\in L_{\psi_{2}}$, then with high probability,

Note that if $F$ is a convex, centrally symmetric class then

Thus, $s_{M}$ is chosen to ensure that with high probability,

In a similar way, the second part of Theorem 1.7 leads to the choice of $s_{Q}$.

Combining these observations, the following is a bound on the estimation problem for the squared loss in a subgaussian setup, and which achieves the minimax rates in rather general situations (see for more details).

For every $L\geq 1$ there exist constants $c_{1},c_{2},c_{3}$ and $c_{4}$ that depend only on $L$ for which the following holds. Let $F$ be a convex, centrally symmetric, $L$-subgaussian class of functions and assume that $\|Y-f^{*}(X)\|_{\psi_{2}}\leq\sigma$. Set $\eta_{1}=c_{1}/\sigma$ and $\eta_{2}=c_{2}$, and put $s_{M}=s_{M}(\eta_{1})$ and $s_{Q}=s_{Q}(\eta_{2})$.

1. If $\sigma\geq c_{3}s_{Q}$ then with probability at least $1-4\exp(-c_{4}N\eta_{1}^{2}s_{M}^{2})$, $\|\hat{f}-f^{*}\|_{L_{2}}\leq s_{M}^{2}$.

2. If $\sigma\leq c_{3}s_{Q}$ then with probability at least $1-4\exp(-c_{4}N\eta_{2}^{2})$, $\|\hat{f}-f^{*}\|_{L_{2}}\leq s_{Q}^{2}$.

The multiplier process has a geometric interpretation: for every $(X_{i})_{i=1}^{N}$ and $(\xi_{i})_{i=1}^{N}=(f^{*}(X_{i})-Y_{i})_{i=1}^{N}$ (that need not be independent of the $X_{i}$’s), it measures the width (or correlation) of the set

relative to the weighted Bernoulli random vector $(\varepsilon_{i}\xi_{i})_{i=1}^{N}$. The width clearly increases with the length of the random vector, and so, with noise level of the problem, captured here by $\|f^{*}(X)-Y\|_{\psi_{2}}$. Therefore, once enough noise is introduced to the problem, the impact of the multiplier process increases and $s_{M}(c_{1}/\sigma)$ becomes dominant.

Observe that there is a link between the two parameters and the structure of the excess loss. Not only are there two noise regimes, each captured by a different parameter, but also each regime originates from a different part of the excess loss functional: the intrinsic parameter from the quadratic part and the external parameter from the multiplier component. The transition between a low-noise problem and a high-noise one occurs based on the dominating component of the loss.

2 Towards a general theory - preliminary remarks

If one wishes, as we do, to extend the results from the subgaussian case outlined above to a more general scenario, one must overcome two main obstacles.

First, one has to modify the concentration-based argument used in Theorem 1.8, simply because versions of Theorem 1.7 are false in heavy-tailed situations; second, one must find a way of studying general loss functions, rather than the squared loss.

Bypassing concentration-based arguments is possible thanks to the small-ball condition.

A random variable $Z$ satisfies a small-ball condition with constants $\kappa>0$ and $0<\varepsilon<1$ if

A class of functions $F$ defined on the probability space $(\Omega,\mu)$ satisfies a small-ball condition with constants $\kappa$ and $0<\varepsilon<1$ if for every $f\in F$,

This small-ball condition has been introduced in the context of estimation problems in , and is the most important feature of our presentation. Being a rather weak assumption that is almost universally satisfied (see for some examples), it serves as a replacement for concentration that comes almost free of charge.

As for more general loss functions, the need for a theory that can handle those extends beyond the obvious reason – that the square loss is not the only loss used in applications. A more subtle and interesting reason has to do with the existence of outliers.

The combination of the rapid growth of the squared loss with heavy-tailed sampling inevitably leads to outliers – sample points that are misleading (because of the heavy tails) and have a significant impact on ERM (because the loss grows quickly).

It is highly desirable to find a way of removing the ill-effects of outliers, and we will show that one possibility is choosing a loss that is calibrated to fit the noise level and the intrinsic structure of the underlying class.

If one wishes the loss to be convex, its growth from any point must be at least linear. Therefore, it seems natural to consider loss functions that are strongly convex in an interval around zero, thus mimicking the local behaviour of the squared loss; and, away from zero, exhibit a linear, or almost linear growth, hopefully limiting the negative effect of outliers.

Typical examples of such losses are the Huber loss with parameter $\gamma$, defined by

The general framework that will be developed here aims at going beyond the subgaussian theory and the squared loss:

$\bullet$ We will extend the natural decomposition of the squared excess loss to more general losses, leading to a better understanding of the important features of the loss, and to the correct notions of ‘high-noise’ and ‘low-noise’ regimes.

$\bullet$ We will develop suitable one-sided lower bounds that are based on a small-ball argument, replacing the restrictive concentration-based two-sided estimates.

$\bullet$ We will explain how the choice of the loss may be used to address the outliers issue, with a particularly striking effect when the class is well behaved and the target is heavy tailed.

3 Some notation

Throughout the article, absolute constants are denoted by $c_{1},c_{2},...$; their value may change from line to line. We write $A\lesssim B$ if there is an absolute constant $c_{1}$ for which $A\leq c_{1}B$, and $A\sim B$ if $c_{1}A\leq B\leq c_{2}A$ for absolute constants $c_{1}$ and $c_{2}$. $A\lesssim_{r}B$ or $A\sim_{r}B$ means that the constants depend on some parameter $r$. $\kappa_{0}$, $\kappa_{1}$,… etc, denote constants whose value remains fixed.

For $\alpha\geq 1$, $L_{\psi_{\alpha}}$ is the Orlicz space of all measurable functions, for which the $\psi_{\alpha}$ norm, defined by

is finite. Some basic facts on Orlicz spaces may be found, for example, in .

A class of functions $H$ is star-shaped around if for every $h\in H$ and every $\lambda\in$, $\lambda h\in H$. In other words, if $h\in H$ then $H$ contains the entire interval connecting $h$ to .

It is straightforward to verify that if $F$ is convex and $f\in F$ then $H_{f}=F-f=\{h-f:h\in F\}$ is star-shaped around .

A class that is star-shaped around zero has some regularity. The star-shape property implies that if $r<\rho$, then $H\cap rS(L_{2})$ contains a ‘scaled-down’ version of $H\cap\rho S(L_{2})$. Indeed, if $h\in H\cap\rho S(L_{2})$ and since $r/\rho\in$, it follows that $(r/\rho)h\in H\cap rS(L_{2})$. In particular, normalized ‘layers’ of a star-shaped class become richer the closer the layer is to zero.

Finally, if $A$ is a finite set, we denote by $|A|$ its cardinality.

4 The Organization of the article

The rest of the article is arranged as follows. In Section 2 we will present the new scheme for dealing with a general loss function. Then, in Section 3 and Section 4 we will define $r_{Q}$ – the intrinsic complexity of the class, and use the small-ball condition to derive uniform lower bounds on the ‘quadratic component’ of a general loss function.

Next, in Section 5, we will identify the external parameter, $r_{M}$, that captures the interaction of the class, the noise and the loss. This will be followed by proofs of the main results of this article – a solution of Problem 1.2 for a general loss, without any tail restrictions on the class, nor on the target, while satisfying the entire ‘wish-list’ outlined earlier.

Finally, in Section 6 we will show how the main results may be used for three loss functions (the squared loss, the logistic loss and the Huber loss). Moreover, we will show that a wise choice of the loss may be used to treat the issue of outliers in heavy-tailed scenarios.

As will be explained in Section 6, one of the outcomes of the general theory developed here is that (roughly and somewhat inaccurately put) by selecting a loss that grows linearly in the ray $[c\max\{r_{Q},\|\xi\|_{L_{2}}\},\infty)$ and that is strongly convex in the interval $[0,c\max\{\|\xi\|_{L_{2}},r_{Q}\})$, one obtains the same error rates as if $\xi$ were a gaussian variable, independent of $X$. In particular, this shows that the impact of outliers generated because of a heavy-tailed target can be negated using a well-calibrated loss that fits both the intrinsic complexity of the class (via $r_{Q}$) and the level of the noise (via $\|\xi\|_{L_{2}}$).

The general scheme – beyond the squared loss

As explained earlier, the analysis of ERM is based on exclusion: showing that a large (random) part of the class cannot contain the empirical minimizer because the empirical risk is positive for functions that belong to it.

One may exclude $F^{\prime}\subset F$ by showing that the empirical mean of the quadratic term (2) is positive on $F^{\prime}$, while the empirical mean of the multiplier component (1) cannot be very negative there.

Therefore, when applied to $(X,Y)$ and a fixed $f\in F$, the quadratic component in the decomposition is

For every $f,f^{*}\in F$ and $(X,Y)$, set

representing the multiplier component of the excess loss and the quadratic one, respectively.

A structural assumption that will be needed throughout this exposition is the following:

Assumption 2.1 is not really restrictive:

Under Assumption 2.1, given a sample $(X_{i},Y_{i})_{i=1}^{N}$ and $f\in F$, there are mid-points $Z_{i}$ that fall between $f^{*}(X_{i})-Y_{i}$ and $f(X_{i})-Y_{i}=(f-f^{*})(X_{i})+\xi_{i}$, for which

Assume that on a high-probability event ${\cal A}$, for every $f\in F$,

for well chosen values $r_{M}$ and $\theta$. Assume further that on a high probability event ${\cal B}$, for every $f\in F$ with $\|f-f^{*}\|_{L_{2}}\geq r_{Q}$,

If $F$ satisfies Assumption 2.1, then on the event ${\cal A}\cap{\cal B}$, $\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\{r_{M},r_{Q}\}$.

Hence, on the event ${\cal A}\cap{\cal B}$, if $\|f-f^{*}\|_{L_{2}}\geq\max\{r_{M},r_{Q}\}$ then $P_{N}{\cal L}_{f}\geq(\theta/4)\|f-f^{*}\|_{L_{2}}^{2}>0$, and $f$ cannot be an empirical minimizer.

Therefore, to resolve the estimation problem it suffices to identify $r_{M}$ and $r_{Q}$ for which the event ${\cal A}\cap{\cal B}$ is sufficiently large.

Assume that there is a constant $\beta$ for which, for every $f\in F$ with $\|f-f^{*}\|_{L_{2}}\leq\max\{r_{M},r_{Q}\}$, one has

In the following sections we will develop the necessary machinery leading to a uniform lower estimate on the quadratic term $f\to P_{N}{\cal Q}_{f-f^{*}}$ and to an upper estimate on the multiplier term $f\to P_{N}{\cal M}_{f-f^{*}}$. Combining the two, we will identify the values $r_{Q}$ and $r_{M}$, as well as the right choice of $\theta$.

Preliminary estimates

Let $(Z_{i})_{i=1}^{N}$ be independent copies of a random variable $Z$ and set $(Z_{i}^{*})_{i=1}^{N}$ to be a monotone non-increasing rearrangement of $(|Z_{i}|)_{i=1}^{N}$.

This section is devoted to the derivation of upper and lower estimates on various function of $(Z_{i}^{*})_{i=1}^{N}$. All the bounds presented here are well-known and straightforward applications of either a concentration inequality for $\{0,1\}$-valued random variables (selectors) with mean $\delta$, or, alternatively, a rather crude binomial estimate.

for a suitable absolute constant $c$. Hence, taking $t=u\delta$,

with probability at least $1-2\exp(-cN\delta\min\{u^{2},u\})$.

The binomial estimate is based on the fact that

Assume that one has information on $\|Z\|_{L_{q}}$ for some $q\geq 2$ and set $L=\|Z\|_{L_{q}}/\|Z\|_{L_{2}}$. Applying Chebyshev’s inequality,

Hence, if ${\cal P}=(|Z|<w\|Z\|_{L_{2}})$ it follows that one may take $\delta=1-(L/w)^{q}$, which can be made arbitrarily close to $1$ by selecting $w$ that is large enough. This implies that with high probability, an arbitrary large proportion of $\{|Z_{1}|,...,|Z_{N}|\}$ are not very large.

There exists absolute constants $c_{1}$ and $c_{2}$ for which the following holds. Let $Z\in L_{2}$. For every $0<\varepsilon<1$, with probability at least $1-2\exp(-c_{1}\varepsilon N)$ there exists a subset $I\subset\{1,...,N\}$, $|I|\geq(1-\varepsilon)N$, and for every $i\in I$,

Proof. Fix $\varepsilon$ as above and note that $Pr(|Z|\geq 2\|Z\|_{L_{2}}/\sqrt{\varepsilon})\leq\varepsilon/4$. Hence, by a binomial estimate,

Given a vector $a=(a_{i})_{i=1}^{N}$, the $L_{q}$ norm of $a$, when considered as a function on the space $\{1,...,N\}$ endowed with the uniform probability measure, is

The weak-$L_{q}$ norm of the vector $a$ is

where $d_{a}(t)=N^{-1}|\{i:|a_{i}|>t\}|$.

The next observation is that sampling preserves the $L_{q}$ structure of $Z$, in the sense that if $Z\in L_{q}$, then with high probability, $\|(Z_{i})_{i=1}^{N}\|_{L_{q,\infty}^{N}}\lesssim\|Z\|_{L_{q}}$.

Let $1\leq q\leq r$. If $Z\in L_{r}$, $u\geq 2$ and $1\leq k\leq N/2$, then

with probability at least $1-u^{-kr}\left(\frac{eN}{k}\right)^{-k((r/q)-1)}$.

In particular, with probability at least $1-2u^{-r}N^{-((r/q)-1)}$,

Proof. Let $\eta=(r/q)-1$, fix $1\leq k\leq N/2$ and set $v>0$ to be named later. The binomial estimate implies that

The second part of the claim follows by summing up the probabilities for $k\leq N/2$, using that $Z_{k}^{*}\leq Z_{N/2}^{*}$ for $k\geq N/2$ and that $(u^{-kr})_{k=1}^{N/2}$ is a geometric progression.

The upper estimates presented above are based on the fact that if $Z\in L_{q}$ and $p\leq q$ then $Pr(|Z|\geq t\|Z\|_{L_{p}})$ can be made arbitrarily close to $1$ for a choice of $t$ that is independent of $Z$. Similar arguments are true if one simply assumes that $Pr(|Z|\geq t)<\varepsilon$, even without moment assumptions. Of course, under such an assumption one has no information whatsoever on the largest $\varepsilon N$ coordinates of $(|Z_{1}|,....,|Z_{N}|)$, but rather, only on a certain proportion that is slightly smaller than $(1-\varepsilon)N$ of the coordinates.

Also, observe that $\|(Z_{i}^{*})_{i\geq j}\|_{L_{q,\infty}^{N}}\lesssim\|Z\|_{L_{q}}$ with a probability estimate that improves exponentially in $j$.

2 Lower estimates using a small-ball property

A similar line of reasoning to the one used above is true for lower estimates. Because the applications considered below require many of the $|Z_{i}|$’s to be at least of the order of $\|Z\|_{L_{2}}$, that norm is used as a point of reference in the definition of the small-ball condition, that

for constants $\kappa$ and $0<\varepsilon<1$.

Of course, the notion of ‘small-ball’ can be modified to fit other norms, as well as situations in which $Z$ does not have any moments.

There exists an absolute constant $c$ for which the following holds. Assume that $Z$ satisfies a small-ball condition with constants $\kappa_{0}$ and $0<\varepsilon<1$ and let $(Z_{i})_{i=1}^{N}$ be independent copies of $Z$. Then, with probability at least $1-2\exp(-cN\varepsilon)$, there is a subset $I$ of $\{1,...,N\}$ of cardinality at least $(3/4)\varepsilon N$, and for every $i\in I$, $|Z_{i}|\geq\kappa_{0}\|Z\|_{L_{2}}$.

Combining the upper estimate from Lemma 3.1 and lower one from Lemma 3.4 yields the following corollary:

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. Assume that $Z\in L_{2}$ and that it satisfies the small-ball condition for constants $\kappa_{0}$ and $\varepsilon$. Then, with probability at least $1-2\exp(-c_{1}\varepsilon N)$, there is $J\subset\{1,...,N\}$, $|J|\geq\varepsilon N/2$ and for every $j\in J$,

Corollary 3.5 allows one to control the behaviour of $(Z_{i})_{i=1}^{N}$ on a subset of $\{1,...,N\}$ of cardinality $\sim\varepsilon N$, and with exponentially high probability. Moreover, by modifying $c_{1}$ and $c_{2}$, the cardinality of $J$ can be made arbitrarily close to $\varepsilon N$.

Note that by the union bound, a version of Corollary 3.5 holds uniformly for a collection of $\exp(c_{1}N\varepsilon/2)$ random variables with probability at least $1-2\exp(-c_{1}N\varepsilon/2)$ – an observation that will be used extensively in what follows.

A uniform estimate on the quadratic process

The goal of this section is to study the structure of a typical coordinate projection of a class $H$, $P_{\sigma}H=\{(h(X_{i}))_{i=1}^{N}:h\in H\}$, and show that with high probability, for every function in $H$ of sufficiently large $L_{2}$ norm, most of the coordinates of $P_{\sigma}h$ are of the order of $\|h\|_{L_{2}}$. Such a result is an extension of the ‘lower part’ of Corollary 3.5 from a single function to a class of functions that is not very big in some sense. The class we will focus on later is $H_{f^{*}}=\{f-f^{*}:f\in F\}$.

Given a class of functions $H\subset L_{2}(\mu)$, a sample size $N$ and positive constants $\zeta_{1}$ and $\zeta_{2}$ set

where $D$ is, as always, the unit ball of $L_{2}(\mu)$.

When the class $H$ and sample size $N$ are obvious from the context, we will denote the fixed points by $r_{1,Q}(\zeta_{1})$ and $r_{2,Q}(\zeta_{2})$ respectively.

By a straightforward application of the Central Limit Theorem, one may show that if $H$ consists of mean-zero functions then

therefore, $r_{2,Q}$ is larger than $r_{1,Q}$, at least asymptotically.

For a fixed $N$, comparing the two parameters is more difficult. In one direction, one has the following lower bound:

Let $H\subset L_{2}$ be a class of functions and assume that for every $h_{1},h_{2}\in H$, $Pr(|h_{1}-h_{2}|\geq\kappa\|h_{1}-h_{2}\|_{L_{2}})\geq\varepsilon$. Then

where the supremum is taken with respect to all subsets of $H$ of cardinality $m\leq\exp(c_{2}(\varepsilon)N)$.

On the other hand, a standard chaining argument combined with the Majorizing Measures Theorem shows that if $H$ is an $L$-subgaussian class then

(see, e.g. and the manuscript as a general reference for chaining methods).

Thus, the two complexity terms are not that far apart when $H$ is an $L$-subgaussian class.

If $H$ is star-shaped around , it is straightforward to show that when $r>r_{1,Q}(\zeta_{1})$, one has

A similar observation is true for $r_{Q,2}(\zeta_{2})$.

The following is the main technical tool needed for the study of the quadratic component.

There exist absolute constants $c_{0},c_{1},c_{2},c_{3},c_{4}$ and $c_{5}$ for which the following holds. Let $H$ be a class of functions that is star-shaped around and that satisfies a small-ball condition with constants $\kappa_{0}$ and $\varepsilon$. If $\zeta_{1}=c_{1}\kappa_{0}\varepsilon^{3/2}$, $\zeta_{2}=c_{2}\kappa_{0}\varepsilon$ and $r>r_{Q}(\zeta_{1},\zeta_{2})$, there is $V_{r}\subset H\cap rS(L_{2})$ and an event $\Omega^{\prime}$ of probability at least $1-2\exp(-c_{0}\varepsilon^{2}N)$, with the following properties:

1. $|V_{r}|\leq\exp(c_{3}\varepsilon N)$ for $c_{3}\leq 1/1000$.

2. On the event $\Omega^{\prime}$, for every $v\in V_{r}$ there is a subset $I_{v}\subset\{1,...,N\}$, $|I_{v}|\geq\varepsilon N/2$ and for every $i\in I_{v}$,

3. On the event $\Omega^{\prime}$, for every $h\in H\cap rS(L_{2})$ there is some $v\in V_{r}$ and a subset $J_{h}\subset I_{v}$, consisting of at least $3/4$ of the coordinates of $I_{v}$ (and in particular, $|J_{h}|\geq\varepsilon N/4$), and for every $j\in J_{h}$,

The idea of the proof is to find an appropriate net in $H\cap rS(L_{2})$ (the set $V_{r}$), and show that each point in the net has many ‘well-behaved’ coordinates in the sense of (2). Also, if $\pi h$ denotes the best approximation of $h\in H\cap rS(L_{2})$ in $V_{r}$ with respect to the $L_{2}$ norm, then

is not very big, showing that $|(h-\pi h)(X_{i})|$ cannot have too many large coordinates. Since $h(X_{i})=(\pi h)(X_{i})+(h-\pi h)(X_{i})$, the first term is dominant on a proportional number of coordinates, leading to (3).

Proof. Recall that by Corollary 3.5, if $Z\in L_{2}$ satisfies the small-ball condition with constants $\kappa_{0}$ and $\varepsilon$ then with probability at least $1-2\exp(-c_{1}\varepsilon N)$, there is $I\subset\{1,...,N\}$, $|I|\geq\varepsilon N/2$ and for every $i\in I$,

Fix $\zeta_{1}$ and $\zeta_{2}$ to be named later, let $r>r_{Q}(\zeta_{1},\zeta_{2})$ and set $V_{r}\subset H\cap rS(L_{2})$ to be a maximal $\eta$-separated set whose cardinality is at most $\exp(c_{1}^{\prime}\varepsilon N/2)$, for $c_{1}^{\prime}=\min\{c_{1},1/500\}$. Therefore, by Corollary 3.5 and the union bound, it follows that with probability at least $1-2\exp(-c_{1}\varepsilon N/2)$ for every $v\in V_{r}$ there is a subset $I_{v}$ as above, i.e., $|I_{v}|\geq\varepsilon N/2$ and for every $i\in I_{v}$,

By Sudakov’s inequality (see, e.g. ) and since $r\geq r_{Q,1}(\zeta_{1})$,

for $c_{4}=\sqrt{2}c_{3}/\sqrt{c_{1}^{\prime}}$.

Let $\phi(t)=t/(\kappa_{0}r/2)$ and note that pointwise, for every $u_{h}\in U_{r}$, $u_{h}(X)\leq\phi(|h-\pi h|(X))$.

Applying the Giné-Zinn symmetrization theorem and recalling that $r>r_{Q,2}(\zeta_{2})$, one has

provided that $\zeta_{1}\sim\kappa_{0}\varepsilon^{3/2}$ and $\zeta_{2}\sim\kappa_{0}\varepsilon$.

Let $\psi(X_{1},...,X_{N})=\sup_{u\in U_{r}}\frac{1}{N}\sum_{i=1}^{N}u(X_{i})$. By the bounded differences inequality (see, for example, ), with probability at least $1-\exp(-c_{5}t^{2})$,

Thus, for $t=\varepsilon\sqrt{N}/32$, with probability at least $1-\exp(-c_{6}\varepsilon^{2}N)$, $\psi(X_{1},...,X_{N})\leq\varepsilon/16$, implying that for every $h\in H\cap rS(L_{2})$,

Recall that $\pi h\in V_{r}$ and that $|I_{\pi h}|\geq\varepsilon N/2$. Let

and thus $|J_{h}|\geq\varepsilon N/4$. Moreover, for every $j\in J_{h}$,

which also shows that ${\rm sgn}(h(X_{j}))={\rm sgn}(\pi h(X_{j}))$.

The upper estimate follows from a similar argument, using that $|h(X_{j})|\leq|\pi h(X_{j})|+|(h-\pi h)(X_{j})|$.

Observe that by the star-shape property of $H$, if $\rho_{1}>\rho_{2}$, then

Therefore, certain features of $H\cap\rho_{2}S(L_{2})$ are automatically transferred to $H\cap\rho_{1}S(L_{2})$, and in particular, a version of Theorem 4.3 holds uniformly for every level that is ‘larger’ than $2r_{Q}(\zeta_{1},\zeta_{2})$. Indeed, assume that one has chosen $\rho_{2}=2r_{Q}$ in Theorem 4.3 and fix $h\in H\cap\rho_{1}S(L_{2})$. By applying Theorem 4.3 to $h^{\prime}=(\rho_{2}/\rho_{1})h\in H\cap\rho_{2}S(L_{2})$ it follows that on the event $\Omega^{\prime}$ there is a subset $J$ of $\{1,...,N\}$ of cardinality at least $\varepsilon N/4$ on which

Next, let $F\subset L_{2}$ be a convex set, fix $f^{*}\in F$ and put $H_{f^{*}}=\{f-f^{*}:f\in F\}$. Since $H_{f^{*}}$ is clearly star-shaped around and $H_{f^{*}}\subset F-F$ one has:

If $F$ is a convex class of functions, $F-F$ satisfies the small-ball condition with constants $\kappa_{0}$ and $\varepsilon$, and $r=2r_{Q}(F-F,N,\zeta_{1},\zeta_{2})$, then with probability at least $1-2\exp(-c_{0}\varepsilon^{2}N)$, the following holds. For every $f_{1},f_{2}\in F$ that satisfy $\|f_{1}-f_{2}\|_{L_{2}}\geq r$, there is a subset $J_{f_{1},f_{2}}\subset\{1,...,N\}$ of cardinality at least $\varepsilon N/4$ and for every $j\in J_{f_{1},f_{2}}$,

Theorem 4.6 generalizes a similar result from for the squared loss.

Turning to the more difficult problem of a loss that need not be strongly convex, we begin with the case of independent noise.

Assume that $Y=f_{0}(X)+W$, for a fixed but unknown $f_{0}\in F$ and a symmetric random variable $W\in L_{2}$ that is independent of $X$ and for which

Clearly, (4.5) is a rather minimal assumption, as a small-ball condition for a single function and at one level holds when the function is absolutely continuous, by selecting the right value $\kappa_{1}$.

There exist absolute constants $c_{1},c_{2},c_{3}$ and $c_{4}$ for which the following holds. Let $F$ and $W$ be as above. With probability at least $1-2\exp(-c_{1}\varepsilon^{2}N)$, for every $f\in F$ that satisfies $\|f-f^{*}\|_{L_{2}}\geq 2r_{Q}$ one has

The proof of Theorem 4.7 is based on several observations leading to accurate information on the ‘location’ of the midpoints $Z_{i}$ in the lower bound on ${\cal Q}_{f-f^{*}}(X_{i},Y_{i})$. For every $(X,Y)$, the corresponding mid-point belongs to interval whose end-points are $(f-f^{*})(X)-W$ and $-W$. If $I_{f}$ is the set of coordinates on which $|(f-f^{*})(X_{i})|$ is of the order of $\|f-f^{*}\|_{L_{2}}$, and since $X$ and $W$ are independent and $W$ is symmetric, then on roughly half of these coordinates the signs of $(f-f^{*})(X_{i})$ coincide with the signs of $-W_{i}$. Thus,

Moreover, by excluding a further, sufficiently small proportion of the coordinates in $I_{f}$ it follows that $|W_{i}|\sim\|W\|_{L_{2}}$, as long as $W$ is not highly concentrated around zero – which is the reason for (4.5).

The difficulty is in making this argument uniform, in the sense that it should hold for every $f\in F$, rather than for a specific choice of $f$. The first step towards a uniform result is the following lemma.

Let $1\leq k\leq m/40$ and set ${\cal S}\subset\{-1,0,1\}^{m}$ of cardinality at most $\exp(k)$. For every $s=(s(i))_{i=1}^{m}\in{\cal S}$ put $I_{s}=\{i:s(i)\not=0\}$ and assume that $|I_{s}|\geq 40k$. If $(\varepsilon_{i})_{i=1}^{m}$ are independent, symmetric $\{-1,1\}$-valued random variables then with probability at least $1-2\exp(-k)$,

Fix $r$ as in Theorem 4.3 for the class $H_{f^{*}}=F-f^{*}$ and let $\Omega^{\prime}$ be the event on which its assertion holds. Using the notation of that theorem, consider $r=2r_{Q}$ and the set $V_{r}$. For every $v\in V_{r}$ and a sample $(X_{1},...,X_{N})\in\Omega^{\prime}$, let $I_{v}=\{i:\kappa_{0}r\leq|v(X_{i})|\leq c_{1}r/\sqrt{\varepsilon}\}$ and set

By Theorem 4.3, $Pr(\Omega^{\prime})\geq 1-2\exp(-c_{2}\varepsilon^{2}N)$ and on $\Omega^{\prime}$,

Conditioned on $\Omega^{\prime}$, with probability at least $1-2\exp(-c_{0}\varepsilon N)$ with respect to the uniform measure on $\{-1,1\}^{N}$, the following holds. For every $h\in H_{f^{*}}$ with $\|h\|_{L_{2}}\geq r$, there is subset ${\cal I}_{h}\subset\{1,...,N\}$ of cardinality at least $\varepsilon N/24$, and for every $i\in{\cal I}_{h}$,

Proof. Fix $h\in H$ with $\|h\|_{L_{2}}=r$ and let $\pi h=v\in V_{r}$ be as in Theorem 4.3. Recall that there is a subset $J_{h}\subset I_{v}$ consisting of at least $3/4$ of the coordinates of $I_{v}$, on which

Applying Lemma 4.8 to the set ${\cal S}=\{s_{v}:v\in V_{r}\}$ for $k=\varepsilon N/1000$, and noting that for every $s_{v}\in{\cal S}$, $|\{i:s_{v}(i)\not=0\}|\geq\varepsilon N/2\geq 40k$, it follows that with probability at least $1-2\exp(-c_{2}\varepsilon N)$ (relative to the uniform measure on $\{-1,1\}^{N}$), for every $v\in V_{r}$, $s_{v}(i)=\varepsilon_{i}$ on at least $1/3$ of the coordinate of $I_{v}$.

Since the set $J_{h}$ contains at least $3/4$ of the coordinates of $I_{v}$ and $v(X_{i})=\varepsilon_{i}$ on at least a $1/3$ of the coordinates of $I_{v}$ it follows that on the coordinates that belong to the intersection of these two sets (at least $1/12$ of the coordinates in $I_{v}$), both conditions hold, as asserted.

Finally, the claim is positive homogeneous and because $H_{f^{*}}$ is star-shaped around , it holds on the same event when $\|h\|_{L_{2}}\geq r$.

There exist absolute constants $c_{0}$ and $c_{1}$ for which the following holds. Let $F$ and $W$ be as above. With probability at least $1-2\exp(-c_{0}\varepsilon^{2}N)$ with respect to the product measure $(X\otimes W)^{N}$, for every $f\in F$ with $\|f-f^{*}\|_{L_{2}}\geq 2r_{Q}$ there is a subset ${\cal J}_{f}\subset\{1,...,N\}$ of cardinality at least $\varepsilon N/100$, and for every $j\in{\cal J}_{f}$,

1. $(\kappa_{0}/2)\|f-f^{*}\|_{L_{2}}\leq|(f-f^{*})(X_{j})|\leq c_{1}(\kappa_{0}+1/\sqrt{\varepsilon})\|f-f^{*}\|_{L_{2}}$,

2. ${\rm sgn}((f-f^{*})(X_{i}))={\rm sgn}(-W)$, and

3. $\kappa_{1}\|W\|_{L_{2}}\leq|W_{j}|\leq c_{2}\|W\|_{L_{2}}/\sqrt{\varepsilon}$.

Proof. Since $W$ is symmetric, it has the same distribution as $\eta|W|$, for a symmetric $\{-1,1\}$-valued random variable $\eta$ that is independent of $|W|$ and of $X$.

If $(W_{i})_{i=1}^{N}=(\eta_{i}|W_{i}|)_{i=1}^{N}$, a direct application of Lemma 4.9 shows that with probability at least $1-2\exp(-c_{0}\varepsilon^{2}N)$, if $\|f-f^{*}\|_{L_{2}}\geq 2r_{Q}$, there is a subset ${\cal I}_{f}\subset\{1,...,N\}$ of cardinality at least $\varepsilon N/24$, and for every $i\in{\cal I}_{f}$,