Performance of empirical risk minimization in linear aggregation

Introduction and main results

Let $(\mathcal{X},\mu)$ be a probability space, set $X$ to be distributed according to $\mu$ and put $Y$ to be an unknown target random variable.

is the risk of the function $\hat{f}$ that is chosen by the procedure, using the observations $(X_{i},Y_{i})_{i=1}^{N}$.

There are many different ways in which one may construct learning procedures (see, e.g., the books for numerous examples), but in general, there is no ‘universal’ choice of an optimal learning procedure.

The variety of learning algorithms motivated the introduction of aggregation or ensemble methods, in which one combines a batch or dictionary, created by learning procedures, in the hope of obtaining a function with ‘better’ prediction capabilities than individual members of the dictionary.

Aggregation procedures have been studied extensively (see, e.g., and references therein), and among the more well-known aggregation procedures are boosting and bagging .

This type of inequality is called an oracle inequality and the function $f^{*}$ for which $R(f^{*})=\inf_{f\in\operatorname{span}(F)}R(f)$ is called the oracle.

Of course, in (1) one is looking for the smallest possible residual term $r_{N}(M)$, that holds uniformly for all choices of couples $(X,Y)$ and dictionaries $F$ that satisfy certain assumptions.

The linear aggregation problem has been studied in in the Gaussian white noise model; in for the Gaussian model with random design; in for the density estimation problem and in in the learning theory setup, under moment conditions. And, based on these cases, it appears that the best possible residual term $r_{N}(M)$ that one may hope for is of the order of $M/N$.

This rate is usually called the optimal rate of linear aggregation and, in fact, its optimality holds in some minimax sense, introduced in .

The only procedure we will focus on here is empirical risk minimization (ERM) performed in the span of the dictionary:

We do not claim that ERM is always the best procedure for the linear aggregation problem, but rather, our aim is to identify conditions under which it achieves the optimal rate of $M/N$.

If $x>0$ satisfies that $2/N\leq 2\exp(-x)\leq 1$ and

then with probability at least $1-2\exp(-x)$,

It follows from Theorem 1.1 that under an $L_{4}$ assumption on $Y-f^{*}(X)$ and the equivalence between the $L_{2}$ and $L_{\infty}$ norms on the span of $F$, ERM achieves a rate of convergence of order $B^{2}M/N$ when $N\geq cB^{3}M$ for an absolute constant $c$.

However, it should be noted that the best probability estimate one may obtain in Theorem 1.1 is $1-2/N$; also, it is possible to show that the constant $B$ defined in (2) is necessarily larger than the dimension $M$ of $\operatorname{span}(F)$. For the sake of completeness, we shall provide a proof of that fact in the Appendix. Therefore, the rate that Theorem 1.1 guarantees is, at best, of the order of $M^{3}/N$, to achieve that rate, at least $N\geq cM^{4}$ observations are needed, and even with that sample size, the probability estimate is, at best, $1-2/N$. This estimate is far from the anticipated rate of $M/N$, which should be achieved when $N\geq cM$ and preferably, with significantly higher probability.

Nevertheless, the optimal rate of $M/N$ can be obtained by relaxing assumption (2) and using a different method of proof. Recall that the $\psi_{2}$ norm of a function $f$ is

One may show that $\|f\|_{\psi_{2}}\leq c\|f\|_{L_{\infty}}$ for a suitable absolute constant $c$ (see, e.g., Section 1 in ). Therefore, assuming that the $\psi_{2}$-norm and the $L_{2}$-norm are equivalent in $\operatorname{span}(F)$ is a weaker requirement than the one in (2). The assumption that for every $f\in\operatorname{span}(F)$,

Naturally, the analysis of ERM under a sub-Gaussian assumption requires a more sophisticated technical machinery than in situations in which the $L_{2}/L_{\infty}$ equivalence assumption used in Theorem 1.1 holds. Invoking the main result from , one can show that if $Y-f^{*}(X)$ is sub-Gaussian and $\operatorname{span}(F)$ is a sub-Gaussian class, then for every $x>0$, ERM achieves a rate $r_{N}(M)=c_{1}xM/N$ with probability at least $1-\exp(-c_{2}xM)$.

Although the sub-Gaussian case is interesting, the goal of this note is the study of ERM as a linear aggregation procedure under much weaker assumptions.

Let $F=\{f_{1},\ldots,f_{M}\}$ and assume that there are constants $\kappa_{0}$ and $\beta_{0}$ for which

for every $f\in\operatorname{span}(F)$. Let $N\geq(400)^{2}M/\beta_{0}^{2}$ and set $\zeta=Y-f^{*}(X)$. Assume further that one of the following two conditions holds:

Then, for every $x>0$, with probability at least $1-\exp(-\beta_{0}^{2}N/4)-(1/x)$,

Since the loss is the squared one, one has to assume that $Y$ and functions in $\operatorname{span}(F)$ have a second moment. It follows from Theorem A that in some cases, this is (almost) all that is needed for an optimal rate. Indeed, if $\zeta=Y-f^{*}(X)$ is independent of the design $X$ – as is the case in any regression model with independent noise $Y=f^{*}(X)+\zeta$, and if (4) holds, ERM achieves the optimal rate $M/N$.

Consider the regression model $Y=f^{*}(X)+\zeta$ where $\zeta$ is a mean-zero noise that is independent of $X$. Assume that $\zeta\in L_{2}$ and that $f^{*}\in\operatorname{span}(F)$. If $\operatorname{span}(F)$ satisfies (4) and $N\geq(400)^{2}M/\beta_{0}^{2}$, then for every $x>0$, with probability at least $1-\exp(-\beta_{0}^{2}N/4)-1/x$,

It is possible to slightly modify the assumptions of Theorem A and still obtain the same type of estimate. For example, it is straightforward to verify that the small-ball condition (4) holds when the $L_{2}$ and $L_{p}$ norms are equivalent on $\operatorname{span}(F)$ for some $p>2$. This type of $L_{p}/L_{2}$ equivalence assumption on $\operatorname{span}(F)$ is weaker than the equivalence between the $L_{\psi_{2}}$ and the $L_{2}$ norms in (3) because for every $p\geq 1$, $\|f\|_{L_{p}}\leq c\sqrt{p}\|f\|_{\psi_{2}}$ for a suitable absolute constant $c$. And, it is clearly weaker than the $L_{\infty}/L_{2}$ equivalence assumption (2) used in Theorem 1.1.

It turns out that if the $L_{2}$ and $L_{4}$ norms are equivalent on $\operatorname{span}(F)$, one may obtain the optimal rate for an arbitrary target $Y$, as long as $\zeta=Y-f^{*}(X)$ has a fourth moment. The difference between such a result and Theorem A is that $\zeta$ need not be independent of $X$, nor must it be bounded.

There exist absolute constants $c_{0},c_{1}$ and $c_{2}$ for which the following holds. Assume that there exists $\theta_{0}$ for which

One may show that a possible choice of constants in Theorem 1.3 is $c_{0}=1600$, $c_{1}=64$ and $c_{2}=(256)^{2}$, but since we have not made any real attempt of optimizing the choice of constants – because identifying the correct rate is the main focus of this note – we will not keep track of the values of constants in what follows.

One example in which Theorem 1.3 may be used is the regression problem with a misspecified model: $Y=f_{0}(X)+W$ where the regression function $f_{0}$ may not be in the model $\operatorname{span}(F)$ and $\zeta=(f_{0}-f^{*})(X)+W$ has a fourth moment. If $\operatorname{span}(F)$ satisfies (4), then with high probability,

The standard way of analyzing the performance of ERM is via certain trade-offs between concentration and complexity. However, in the case we study here, the functions involved may have ‘heavy tails’, and empirical means do not exhibit strong, two-sided concentration around their true means – which is a crucial component in the standard method of analysis. Therefore, a completely different path must be taken if one is to obtain the results formulated above.

The method we shall employ here has been introduced in for problems in Learning Theory; in in the context of the geometry of convex bodies; in for applications in random matrix theory; and in for Compressed Sensing.

Obviously, and regardless of the method of analysis, the (seemingly) unsatisfactory probability estimate is the price one pays for the moment assumptions on the ‘noise’ $Y-f^{*}(X)$. The next result shows that without stronger moment assumptions, only weak polynomial probability estimates are true.

Finally, we would like to address the problem of linear aggregation under the classical boundedness assumptions: that $|Y|\leq 1$ and $|f(X)|\leq 1$ almost surely for every $f\in F$.

These are the standard assumptions that have been considered for the three problems of aggregation with a random design. For instance, optimal rates of aggregation have been obtained under these assumptions for the model selection aggregation problem in and for the convex aggregation problem in . And, it has been established that while ERM is suboptimal for the model selection aggregation problem (see, e.g., Section 3.5 in or ), it is optimal for the convex aggregation problem. However, the optimality of ERM in the linear aggregation problem under the boundedness assumption was left open. The final result of this article addresses that problem – and it turns out that the answer is negative in a very strong way.

For every $0<\eta<1$ and integers $N$ and $M$, there exists a couple $(X,Y)$ and a dictionary $F=\{f_{1},\ldots,f_{M}\}$ with the following properties:

$|Y|\leq 1$ almost surely and $|f(X)|\leq 1$ almost surely for every $f\in F$.

With probability at least $\eta$, for every $\kappa>0$ there is some

Proposition 1.6 shows that even if one assumes that $|Y|\leq 1$ and $|f(X)|\leq 1$ almost surely for every function in the dictionary, and despite the convexity of $\operatorname{span}(F)$, the empirical risk minimization procedure performs poorly. This illustrates the major difference between assuming that the class is well bounded in $L_{\infty}$ and assuming that the $L_{2}$ and $L_{p}$ norms are equivalent on its span: while the latter suffices for an optimal bound, the former is rather useless.

An obvious outcome of Proposition 1.6 is that ERM should not be used to solve the linear aggregation problem under the boundedness assumption and one has to look for different procedures in the bounded setup. It should also be noted that since Proposition 1.6 is a non-asymptotic lower bound and $X$ may depend on $N$ and $M$, the asymptotic result appearing in Theorem 2.1 in does not apply here.

thus, $R(f)-R(f^{*})=P\mathcal{L}(X,Y)\geq 0$. The empirical measure over the data is denoted by $P_{N}$ and

Finally, all absolute constants are denoted by $c_{1},c_{2}$, etc. Their value may change from line to line. We write $A\lesssim B$ if there is an absolute constant $c$ for which $A\leq cB$, and $A\lesssim_{\alpha}B$ if $A\leq c(\alpha)B$ for a constant $c$ that depends only on $\alpha$.

Proofs of Theorem A and Theorem 1.3

The starting point of the proof of Theorem A is the same as in : a decomposition of the excess loss function

to a sum of quadratic and linear terms in $(f-f^{*})(X)$. The idea of the proof is to control the quadratic term from below using a ‘small-ball’ argument, and the linear term from above using standard methods from empirical processes theory. A combination of these two bounds suffices to show that if $\|f-f^{*}\|_{L_{2}}\geq r_{N}^{*}$ for an appropriate choice of $r_{N}^{*}$, the quadratic term dominates the linear one, and in particular, for such functions $P_{N}\mathcal{L}_{f}>0$. Since the empirical excess loss of the empirical minimizer is non-positive, it follows that $\|\hat{f}-f^{*}\|_{L_{2}}<r_{N}^{*}$.

There exists an absolute constant $c_{0}$ for which the following holds. Assume that there are $\kappa_{0}$ and $\beta_{0}$ for which

for every $f\in\operatorname{span}(F)$. If $N\geq c_{0}M/\beta_{0}^{2}$, then with probability at least $1-\exp(-\beta_{0}^{2}N/4)$, for every $f\in\operatorname{span}(F)$,

Since $N$ independent copies of $X$, $X_{1},\ldots,X_{N}$, endow $N$ independent copies of $W$, denoted by $W_{1},\ldots,W_{N}$, it follows that

By the bounded differences inequality (see, e.g., Theorem 6.2 in ), with probability at least $1-\exp(-x^{2}/2)$,

(one may show the $c_{1}\leq 100$ using a rough estimate on Dudley’s entropy integral combined with Exercise 2.6.4 in ). Therefore, if $c_{1}\sqrt{M/N}\leq\beta_{0}/4$ and $(1/2)\sqrt{x/N}=\beta_{0}/4$, then with probability at least $1-\exp(-\beta_{0}^{2}N/4)$, $H\leq\beta_{0}/2$.

it follows that on the event $\{H\leq\beta_{0}/2\}$,

Therefore, (9) holds with probability at least $1-\exp(-\beta_{0}^{2}N/4)$. ∎

Let $\zeta=Y-f^{*}(X)$ and assume that one of the following two conditions hold:

Then, for every $x>0$, with probability larger than $1-(1/x)$,

Let $\varepsilon_{1},\ldots,\varepsilon_{N}$ be independent Rademacher variables that are also independent of the couples $(X_{i},Y_{i})_{i=1}^{N}$. A standard symmetrization argument shows that

If $Z_{1},\ldots,Z_{N}$ are independent copies of $Z$, it follows that

The claim now follows from Markov’s inequality. ∎

Proof of Theorem A Combining Lemma 2.1 and Lemma 2.2 when $N\geq c_{0}M/\beta_{0}^{2}$, it follows that with probability at least $1-\exp(-\beta_{0}^{2}N/4)-(1/x)$, if $f\in\operatorname{span}(F)$ and

Proof of Theorem 1.3 The proof of Theorem 1.3 is almost identical to the proof of Theorem A, and we will only outline the minor differences.

The small-ball condition (4) follows from the Paley–Zygmund inequality (see, for instance, Proposition 3.3.1 in ): if $V$ is a real-valued random variable then

and thus the assertion of Lemma 2.1 holds for $\kappa_{0}=1/2$ and $\beta_{0}=(4\theta_{0}^{4})^{-1}$.

As for the analogous version of Lemma 2.2, the one change in its proof is that

Proof of Proposition 1.6

Fix $Y=1$ as the target and let $\mathcal{X}=\bigcup_{j=0}^{M}\mathcal{X}_{j}$ be some partition of $\mathcal{X}$. Consider a random variable $X$ which is distributed as follows: fix $k\geq M$ to be chosen later; for $1\leq j\leq M$, set $P(X\in\mathcal{X}_{j})=\frac{1}{k}$ and put $P(X\in\mathcal{X}_{0})=1-\frac{M}{k}$.

Note that $|Y|\leq 1$ almost surely and that for every $f\in F$, $|f(X)|\leq 1$ almost surely. It is straightforward to verify that the oracle in $\operatorname{span}(F)$ is $f^{*}=\sum_{j=1}^{M}f_{j}(\cdot)$, and thus

Let $X_{1},\ldots,X_{N}$ be independent copies of $X$. Given $0<\eta<1$ and $k$ large enough (for instance, $k\geq c(\eta)N/\log M$ for a sufficiently large constant $c(\eta)$ would suffice), there exists an event $\Omega_{0}$ of probability at least $\eta$ on which the following holds: there exists $j_{0}\in\{1,\ldots,M\}$ for which $X_{i}\notin\mathcal{X}_{j_{0}}$ for every $1\leq i\leq N$ (this is a slight modification of the coupon-collector problem).

For every sample in $\Omega_{0}$, let $j_{0}\in\{1,\ldots,N\}$ be the index for which $X_{i}\notin\mathcal{X}_{j_{0}}$ for every $1\leq i\leq N$. Therefore,

and the claim follows by selecting $\xi$ large enough.

Appendix

We begin by presenting a proof of the well-known fact that if the $L_{\infty}$ and $L_{2}$ norms are $\sqrt{B}$-equivalent on the span of $M$ linearly-independent functions, then $B\geq M$.

Let $F=\{f_{1},\ldots,f_{M}\}\subset L_{2}$ be a dictionary whose span is of dimension $M$, and recall that

For $\mu$-almost every $x\in\mathcal{X}$,

Hence, for $\mu$-almost every $x\in\mathcal{X}$,

Let us begin by showing that, conditionally on $\zeta_{1},\ldots,\zeta_{N}$, and if $\hat{\sigma}_{N}^{2}=\frac{1}{N}\sum_{i=1}^{N}\zeta_{i}^{2}$, then with probability at least $1-2\exp(-c_{0}N)$,

and that for every sample, if $r_{1}<r_{2}$ and

one has that for any $\zeta_{1},\ldots,\zeta_{N}$

for suitable absolute constants $c_{1}$ and $c_{2}$. We refer the reader to Lemma 2.6.4 and Theorem 2.6.5 in for more details on the techniques used to obtain these observations.

Hence, by (13), it follows that for $N\geq c_{0}M$ and conditioned on $\zeta_{1},\ldots,\zeta_{N}$, with probability at least $1-2\exp(-c_{3}N)$,

Now, all that remains is to show that $P(\hat{\sigma}_{N}^{2}\geq x)\geq c_{5}/x$.

For every $N\geq 2$ and $x\geq 1$, there exists a mean-zero, variance one random variable $\zeta$ for which

Let $\zeta_{i}=R\varepsilon_{i}\eta_{i}$, $i=1,\ldots,N$ be independent copies of $\zeta$. Recall that $NR^{-2}x=1$ and that $\delta N\leq 1$. Therefore,

Acknowledgment

Shahar Mendelson was supported by the Mathematical Sciences Institute – The Australian National University and by ISF Grant 900/10.

References