Empirical risk minimization is optimal for the convex aggregation problem

Introduction and main results

when $f$ is a real-valued function defined on $\mathcal{X}$ and by

when $\widehat{f}$ is a function constructed using the data $\mathcal{D}$. For the sake of simplicity, throughout this article, we restrict ourselves to functions $f$ and random variables $(X,Y)$ for which $|Y|\leq b$ and $|f(X)|\leq b$ almost surely, for some fixed $b\geq 0$. Note that $b$ does not have to be known from the statistician for the construction of the procedures we are studying in this note.

Given a finite set $F$ of real-valued measurable functions defined on $\mathcal{X}$ (usually called a dictionary), there are three main types of aggregation problems:

Model selection aggregation: construct a procedure whose risk is as close as possible to the risk of the best element in $F$ (cf. ).

Convex aggregation: construct a procedure whose risk is as close as possible to the risk of the best function in the convex hull of $F$ (cf. ).

Linear aggregation: construct a procedure whose risk is as close as possible to the risk of the best function in the linear span of $F$ (cf. ).

In , the author defined the optimal rates of the convex aggregation, by the smallest price in the minimax sense that one has to pay to solve the convex aggregation problem. The definition of is given in expectation, as a function of the cardinality $M$ of the dictionary $F$ and of the sample size $n$. It has been proved in (see also and ) that the optimal rate of convex aggregation is

This rate is defined up to some multiplying constant. Note that the rate $\psi_{n}^{(C)}(M)$ was achieved in in expectation for the Gaussian regression model with a known variance and a known marginal distribution of the design. In , the authors were able to remove these assumptions at a price of an extra $\log n$ factor for $1\leq M\leq\sqrt{n}$ (results are still in expectation). Last year, there has been some striking results on different problems of aggregation including the convex aggregation problem. To mention few of them, we refer the reader to . Finally, we also refer the reader to for non-exact oracle inequalities (inequalities like (1) where $\min_{f\in\operatorname{conv}(F)}R(f)$ is multiplied by a constant strictly larger than $1$) in the context of convex aggregation.

A lower bound in deviation for the convex aggregation problem follows from the arguments of : there exist absolute positive constants $c_{0},c_{1}$ and $c_{2}$ such that for any sample cardinality $n\geq 1$, any cardinality of dictionary $M\geq 1$ such that $\log M\leq c_{0}n$, there exists a dictionary $F$ of size $M$ such that for any aggregation procedure $\bar{f}_{n}$, there exists a random couple $(X,Y)$ such that $|Y|\leq b$ and $\max_{f\in F}|f(X)|\leq b$ a.s. and with probability larger than $c_{1}$,

This means that, from a minimax point of view, one cannot do better than the rate $\psi_{n}^{(C)}(M)$ for the convex aggregation problem. Therefore, any procedure achieving the rate $\psi_{n}^{(C)}(M)$ for any dictionary $F$ and couple $(X,Y)$ such that $|Y|\leq b$ and $\max_{f\in F}|f(X)|\leq b$ a.s. in an oracle inequality like (1) is called an optimal procedure in deviation for the convex aggregation problem.

The procedure constructed in achieves the rate $\psi_{n}^{(C)}(M)$ in expectation (i.e., a procedure satisfying (1) in expectation with the optimal residual term $\psi_{n}^{(C)}(M)$). An optimal procedure in deviation has been constructed in Theorem 2.8.1 in . In both cases, the construction of these optimal aggregation procedures require the aggregation of an exponential number in $M$ of functions in $\operatorname{conv}(F)$ and thus cannot be used in practice. On the other side, it would be much simpler and natural to consider the classical procedure of empirical risk minimization (cf. ) over the convex hull of $F$ to solve the convex aggregation problem:

In , the authors prove that, for every $x>0$, with probability greater than $1-4\exp(-x)$

Another motivation for this work comes from what is known about ERM in the context of the three aggregation schemes mentioned above. It is well known that ERM in $F$ is, in general, a suboptimal aggregation procedure for the model selection aggregation problem (see or ). It is also known that ERM in the linear span of $F$ is an optimal procedure for the linear aggregation problem (cf. Theorem 13 and Example 1) or . Therefore, studying the performances of ERM in the convex hull of $F$ in the context of convex aggregation can be seen as an “intermediate” problem which remained open. In fact, a lot of effort has been invested in finding any procedure that would be optimal for the convex aggregation problem. For example, many boosting algorithms (see or for recent results on this topic) are based on finding the best convex combination in a large dictionary (for instance, dictionaries consisting of “decision stumps”), while random forest algorithms can be seen as procedures that try finding the best convex combination of decision trees. Thus, finding an optimal procedure for the problem of convex aggregation for a general dictionary is of high practical importance. In the following result, we prove that empirical risk minimization is an optimal procedure for the convex aggregation problem.

The optimality also holds in expectation:

Preliminaries on isomorphic properties of functions classes

We recall the machinery developed in to prove isomorphic results between the empirical and actual structures of functions classes.

Let $(\mathcal{Z},\sigma)$ be a measurable space, $Z,Z_{1},\ldots,Z_{n}$ be $n+1$ i.i.d. random variables with values in $\mathcal{Z}$ distributed according to $P_{Z}$ and $G$ be a class of real-valued measurable functions defined on $\mathcal{Z}$. We consider the star shaped hull of $G$ in zero and its localized set at some level $\lambda>0$:

There exists $G_{0}\subset G$ such that $G_{0}$ is countable and for any $g\in G$, there exists a sequence $(g_{k})_{k}$ in $G_{0}$ such that for any $z\in\mathcal{Z}$, $(g_{k}(z))_{k}$ tends to $g(z)$ when $k$ tends to infinity.

There exists an absolute constant $c_{0}>0$ such that the following holds. Let $G$ be a class of real-valued measurable functions defined on $\mathcal{Z}$ satisfying condition (M) and such that $Pg^{2}\leq BPg,\forall g\in G$ for some constant $B>0$. Let $\lambda^{*}>0$ be such that

For every $x>0$, with probability greater than $1-4\exp(-x)$, for every $g\in G$,

For the reader convenience, we recall the short proof of .

Proof of Theorem 2.1 Without loss of generality, we can assume that $G$ is countable. From a limit argument, the result holds for classes of functions satisfying condition (M).

Fix $\lambda>0$ and $x>0$, and note that by Talagrand’s concentration inequality (cf. ), with probability larger than $1-4\exp(-x)$,

where $K$ is an absolute constant. Clearly, we have $\|V(G)_{\lambda}\|_{\infty}\leq\|G\|_{\infty}$ and

Combined with (5), there exists an event $\Omega_{0}(x)$ of probability greater than $1-4\exp(-x)$, and on $\Omega_{0}(x)$,

as long as $c_{0}\geq 64(K^{2}+K)$. Hence, on $\Omega_{0}(x)$, if $g\in V(G)$ satisfies that $Pg\leq\rho_{n}(x)$, then $|Pg-P_{n}g|\leq(1/2)\rho_{n}(x)$. Moreover, if $g\in V(G)$ is such that $Pg>\rho_{n}(x)$, then $h=\rho_{n}(x)g/Pg\in V(G)_{\rho_{n}(x)}$; hence $|Ph-P_{n}h|\leq(1/2)\rho_{n}(x)$, and so in both cases $|Pg-P_{n}g|\leq(1/2)\max(Pg,\rho_{n}(x))$.

Therefore, if one applies Theorem 2.1 to obtain isomorphic properties between the empirical and actual structures, one has to check the condition $Pg^{2}\leq BPg,\forall g\in G$, called the Bernstein condition in , and to find a point $\lambda^{*}$ satisfying (4).

A point $\lambda^{*}$ such that (4) holds can be found thanks to the peeling argument of : for any $\lambda>0$,

where, for any $\mu>0$, $G_{\mu}=\{g\in G\colon\ Pg\leq\mu\}$. Then if $\lambda^{*}>0$ is such that $\lambda^{*}/8$ upper bounds the RHS in (6) this point also satisfies (4).

Moreover, since $|Y|\leq b$ and $\sup_{f\in F}|f(X)|\leq b$ a.s. then

Proof of Theorem A

The proof of Theorem A for the case $M\leq\sqrt{n}$ is now very classical and can be found in (cf. Theorem 13 and Example 1). Nevertheless, we reproduce here this short proof in order to provide a self-contained note. The proof for the case $M>\sqrt{n}$ is more tricky and relies on isomorphic properties of an exponential number of segments in $\operatorname{conv}(F)$ together with Maurey’s empirical method (cf. ) which was first used in the context of convex aggregation in and . Note that segments are models of particular interest in Learning theory because they are convex models (in particular, they satisfy the Bernstein condition) and they are of small complexity (essentially the same complexity as a model of cardinality two). On the contrary to the classical entropy based approach which essentially consists in approximating a set by finite sets, approaching models by union of segments may be of particular interest in Learning theory beyond the convex aggregation problem. Note that finite models have no particular geometrical structure and therefore are somehow “bad models” as far as ERM procedures are concerned.

Proofs are given for the deviation result of Theorem A. The result in expectation of Theorem A follows from a direct integration argument.

We apply Theorem 2.1 to excess loss functions classes indexed by segments. First, note that segments of bounded functions are functions classes satisfying condition (M). We consider a set $\mathcal{C}^{\prime}=\{g_{1},\ldots,g_{N}\}$ of real-valued measurable functions defined on $\mathcal{X}$ such that $\max_{g\in\mathcal{C}^{\prime}}|g(X)|\leq b$ a.s. For every $i,j\in\{1,\ldots,N\}$, we consider the segment $[g_{i},g_{j}]=\{\theta g_{i}+(1-\theta)g_{j}\colon\ 0\leq\theta\leq 1\}$ and take $g^{*}_{ij}\in\operatorname{argmin}_{g\in[g_{i},g_{j}]}R(g)$ where $R(\cdot)$ is the squared risk. We consider the excess loss functions class

Note that when $g_{i}=g_{j}$ the result is also true. Now, we use the peeling argument of (6) to obtain

Now, we can apply Theorem 2.1 to the family of excess loss functions classes $(\mathcal{L}^{ij})_{1\leq i,j\leq N}$ together with a union bound to obtain the following result.

Now, we want to apply the isomorphic result of Proposition 3.1 to a wisely chosen subset $\mathcal{C}^{\prime}$ of $\mathcal{C}=\operatorname{conv}(F)$. For that, we consider the integer

and the set $\mathcal{C}^{\prime}$ is defined by

The set $\mathcal{C}^{\prime}$ is an approximating set of the convex hull $\operatorname{conv}(F)$. We will, for instance, use the following approximation property:

Denote by $N=|\mathcal{C}^{\prime}|$ the cardinality of $\mathcal{C}^{\prime}$ and by $g_{1},\ldots,g_{N}$ the functions in $\mathcal{C}^{\prime}$. For simplicity, assume that $R(g_{1})=\min_{g\in\mathcal{C}^{\prime}}R(g)$. Thanks to for the first inequality and , page 218, or , Proposition 2, for the second inequality, we know that

Let $x>0$. Consider the event $\Omega(x)\subset\Omega$ such that the following isomorphic property holds for all the segments $[g_{1},g_{j}],j=1,\ldots,N$:

and the same holds for the empirical risk:

Note that $g_{\Theta}$ is a random point in $\mathcal{C}^{\prime}$ (as a measurable function from $\Omega^{\prime}$ to $\mathcal{C}^{\prime}$) and that, on the event $\Omega(x)$, the following isomorphic property on the segment $[g_{1},g_{\Theta}]$ holds:

First note that for every $\Theta_{1},\ldots,\Theta_{m}$, we have

By definition of $g^{*}_{1i_{\Theta}}\in\operatorname{argmin}_{g\in[g_{i_{\Theta}},g_{1}]}R(g)$, we have $R(g^{*}_{1i_{\Theta}})\leq R(g_{1})=\min_{g\in\mathcal{C}^{\prime}}R(g)$ and according to (9), we have $\min_{f\in\mathcal{C}^{\prime}}R(f)\leq\min_{f\in\mathcal{C}}R(f)+(4b^{2})/m$. Therefore, it follows from (15) that

On the event $\Omega(x)$, we use (14) to obtain for every $\Theta_{1},\ldots,\Theta_{m}$

Moreover, by definition of ${\widehat{f}}_{n}^{\mathit{ERM}\mbox{{{{-}}}}C}$, we have

Therefore, on the event $\Omega(x)$, we have for every $\Theta_{1},\ldots,\Theta_{m}$

In particular, one can take the expectation with respect to $\Theta_{1},\ldots,\Theta_{m}$ (defined on $\Omega^{\prime}$) in the last inequality. We have on $\Omega(x)$,

where the last inequality follows from (10) and the definition of $m$.

2 The case M≤n𝑀𝑛M\leq\sqrt{n}

Let $x>0$. Assume that we can find some $\rho_{n}(x)>0$ such that with probability greater than $1-4\exp(-x)$, for any $f\in\mathcal{C}$,

Then, the ERM over $\operatorname{conv}(F)$ would satisfy with probability greater than $1-4\exp(-x)$,

This means that if we can prove some isomorphic properties between the empirical and the actual structures of the functions class $\mathcal{L}_{\mathcal{C}}$ like in (17), then we can derive oracle inequalities for ${\widehat{f}}_{n}^{\mathit{ERM}\mbox{{{{-}}}}C}$. This is the strategy used in that we follow here.

We use the peeling argument of Section 2 together with the following observations due to (cf. Example 1) to find a fixed point $\lambda^{*}$. Let $S$ be the linear subspace of $L^{2}(P_{X})$ spanned by the dictionary $F$ and consider an orthonormal basis $(e_{1},\ldots,e_{M^{\prime}})$ of $S$ in $L^{2}(P_{X})$ (where $M^{\prime}={\dim}(S)\leq M$). For any $\mu>0$, it follows from the symmetrization argument and the contraction principle (cf. Chapter 4 in ) that

Now, it follows from Theorem 2.1 that for any $x>0$, with probability greater than $1-4\exp(-x)$,

This concludes the proof for the case $M\leq\sqrt{n}$.

Then, it follows from Theorem 2.1 and the argument used previously in this section that for any $x>0$, with probability greater than $1-4\exp(-x)$,

The same result can be found in under very weak moment assumptions.

Acknowledgements

We would like to thank Alexandre Tsybakov for helping us for the presentation of this result. Supported by French Agence Nationale de la Recherche ANR Grant “Prognostic” ANR-09-JCJC-0101-01.

References