Empirical entropy, minimax regret and minimax risk

Introduction

with $C>1$ and not for the excess risk. In this paper, we obtain sharp oracle inequalities, which allows us to consider the excess risk formulation of the problem as described above.

In what follows we assume that $\mathcal{Y}=$. For results in expectation, the extension to unbounded $\mathcal{Y}$ with some condition on the tails of the distribution is straightforward. For high probability statements, more care has to be taken, and the requirements on the tail behavior are more stringent. To avoid this extra level of complication, we assume boundedness.

From a minimax point of view, the object of interest in Statistical Learning Theory can be written as the minimax regret

where $\mathcal{P}$ is the set of all probability distributions on $\mathcal{X}\times\mathcal{Y}$ and $\inf_{\hat{f}}$ denotes the infimum over all estimators. We observe that the study of this object leads to a distribution-free theory, as no model is assumed. Instead, the goal is to achieve predictive performance competitive with a reference class $\mathcal{F}$. In view of (2), an equivalent way to write $V_{n}(\mathcal{F})$ is

The minimax regret can be interpreted as a measure of performance of estimators for misspecified models. The study of $V_{n}(\mathcal{F})$ will be further referred to as misspecified model setting.

where $\mathcal{P}_{\mathcal{F}}$ is the set of all distributions $P_{XY}$ on $\mathcal{X}\times\mathcal{Y}$ such that $\eta\in\mathcal{F}$. It is not difficult to see that

yet the minimax risk and the minimax regret are quite different and the question is whether the two quantities can be of the same order of magnitude for particular $\mathcal{F}$. We show below that the answer is positive for major cases of interest except for very massive classes $\mathcal{F}$, namely, those having the empirical $\varepsilon$-entropy of the order $\varepsilon^{-p}$, $p>2$, for small $\varepsilon$. We also prove that this entropy condition is tight in the sense that the minimax regret and the minimax risk can have different rates of convergence when it is violated. Furthermore, we show that the optimal rates for the minimax regret and minimax risk are attained by one and the same procedure – the aggregation-of-leaders estimator – that we introduce below.

Observe a certain duality between $W_{n}(\mathcal{F})$ and $V_{n}(\mathcal{F})$. In the former, the assumption about the reality is placed on the way data are generated. In the latter, no such assumption is made, yet the assumption is placed in the term that is being subtracted off. As we describe in Section 7, the study of these two quantities represents two parallel developments: the former has been a subject mostly studied within nonparametric statistics, while the second – within Statistical Learning Theory. We aim to bring out a connection between these two objects. In Section 4, we introduce a more general risk measure that realizes a smooth transition between $W_{n}(\mathcal{F})$ and $V_{n}(\mathcal{F})$ depending on the magnitude of the approximation error. The minimax risk and the minimax regret appear as the two extremes of this scale.

The paper is organized as follows. In Section 3, we present the aggregation-of-leaders estimator and the upper bounds on its risk. These include the main oracle inequality in Theorem 1 and its consequences for particular classes $\mathcal{F}$ in Theorems 2–4. Section 4 discusses a more general setting allowing for a smooth transition between $W_{n}(\mathcal{F})$ and $V_{n}(\mathcal{F})$ in terms of the approximation error. Lower bounds for the minimax risk and minimax regret are proved in Section 5. In Section 6, we compare the aggregation-of-leaders estimator with the two closest competitors – skeleton aggregation and global ERM. Section 7 provides an overview and comparison of our results to those in the literature. Proofs of the theorems are given in Sections 8–10. The Appendix contains some technical results and proofs of the lemmas.

Notation

Set $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$. For $S=\{z_{1},\ldots,z_{n}\}\in\mathcal{Z}^{n}$ and a class $\mathcal{G}$ of real-valued functions on $\mathcal{Z}$, consider the Rademacher average of $\mathcal{G}$:

Given $r>0$, we denote by $\mathcal{G}[r,S]$ the set of functions in $\mathcal{G}$ with empirical average at most $r$ on $S$:

for all $r>0$ will be called an upper function for the class $\mathcal{G}$. We will sometimes write $\phi_{n}(r)=\phi_{n}(r,\mathcal{G})$ to emphasize the dependence on $\mathcal{G}$. It can be shown (cf., e.g., Lemma 8 below) that any class of uniformly bounded functions admits an upper function satisfying the sub-root property: $\phi_{n}$ is non-negative, non-decreasing, and $\phi_{n}(r)/\sqrt{r}$ is non-increasing. We will denote by $r^{*}=r^{*}(\mathcal{G})$ the corresponding localization radius, that is, an upper bound on the largest solution of the equation $\phi_{n}(r)=r$. Clearly, $r^{*}$ is not uniquely defined since we deal here with upper bounds.

for $S=\{z_{1},\ldots,z_{n}\}$ with $z_{i}=(x_{i},y_{i})$.

and for any $\varepsilon>0$ denote by $\mathcal{N}_{2}(\mathcal{F},\varepsilon,S)$ the $\varepsilon$-covering number of a class $\mathcal{F}$ of real-valued functions on $\mathcal{X}$ with respect to this pseudo-metric. Recall that a covering number at scale $\varepsilon$ is the smallest number of balls of radius $\varepsilon$ required to cover the set. Denote by $\mathcal{N}_{\infty}(\mathcal{F},\varepsilon,S)$ the $\varepsilon$-covering number of the class $\mathcal{F}$ with respect to the supremum norm (over $S$).

Although not discussed here explicitly, some standard measurability conditions are needed to apply results from the theory of empirical processes as well as to ensure that the ERM estimators we consider below are measurable. This can be done in a very general framework and we assume throughout that these conditions are satisfied. For more details we refer to Chapter 5 of , see also , page 17.

The minimum risk on the class of functions $\mathcal{F}$ is denoted by

Main results

Clearly, $N$ is finite since $\mathcal{F}$ is included in the set of all functions with values in $$, which is totally bounded with respect to$d_{S}(\cdot,\cdot)$. Let$\hat{c}_{1},\ldots,\hat{c}_{N}$be an$\varepsilon$-net on$\mathcal{F}$with respect to$d_{S}(\cdot,\cdot)$. We assume without loss of generality that it is proper, that is,$\hat{c}_{i}\in\mathcal{F}$for$i=1,\ldots,N$, and that$N\geq 2$. Let$\hat{\mathcal{F}}_{1}^{S},\ldots,\hat{\mathcal{F}}_{N}^{S}$be the following partition of$\mathcal{F}$induced by$\hat{c}_{i}$’s:

with ties broken in an arbitrary way. Now, for each $\hat{\mathcal{F}}_{i}^{S}$, define the least squares estimators over the subsets $\hat{\mathcal{F}}_{i}^{S}$ with respect to the second subsample $S^{\prime}$:

We will assume that such a minimizer exists; a simple modification of the results is possible if $\hat{f}_{i}^{S,S^{\prime}}$ is an approximate solution of (8).

There exists a constant $C>0$ such that, for any $\delta>0$,

with probability at least $1-\delta$ over the sample $S^{\prime\prime}$, conditionally on $S\cup S^{\prime}$.

where $\theta_{i}$ are some random weights measurable with respect to $S^{\prime\prime}$. Either of the aggregates of satisfy the sharp MS-aggregation property and thus can be used at the third step of our procedure.

The next theorem provides the main oracle inequality for aggregation-of-leaders estimators.

with $\gamma=\sqrt{\varepsilon^{2}+r^{*}+\beta}$ and $\beta=(\log(1/\delta)+\log\log n)/n$.

The term $\Xi(n,\varepsilon,S^{\prime})$ in Theorem 1 is a bound on the rate of convergence of the excess risk of ERM $\hat{f}_{i}^{S,S^{\prime}}$ over the cell $\hat{\mathcal{F}}^{S}_{i}$. If, in particular instances, there exists a sharper bound for the rate of ERM, one can readily use this bound instead of the expression for $\Xi(n,\varepsilon,S^{\prime})$ given in Theorem 1.

In Theorem 1 we can use the localization radius $r^{*}=r^{*}(\hat{\mathcal{G}}_{i})$ for $\hat{\mathcal{G}}_{i}=\{(f-g)^{2}\colon\ f,g\in\hat{\mathcal{F}}^{S}_{i}\}$ instead of the larger quantity $r^{*}(\mathcal{G})$. Inspection of the proof shows that the oracle inequality (11) generalizes to

where $\Xi_{i}(n,\varepsilon,S^{\prime})$ is defined in the same way as $\Xi(n,\varepsilon,S^{\prime})$ with the only difference that $r^{*}(\mathcal{G})$ is replaced by $r^{*}(\hat{\mathcal{G}}_{i})$.

The oracle inequality (11) of Theorem 1 depends on two quantities that should be specified: the entropy $\log\mathcal{N}_{2}(\mathcal{F},\cdot,\cdot)$, and the localization radius $r^{*}$. The crucial role in determining the rate belongs to the empirical entropies. We further replace in (11) these random entropies by their upper bound

and refer to the above quantity as the empirical entropy.

The next theorem is a corollary of Theorem 1 in the case of polynomial growth of the empirical entropy characteristic for nonparametric estimation problems. It gives upper bounds on the minimax regret and on the minimax risk.

The second message of Theorem 2 is that $W_{n}(\mathcal{F})$ has faster rate than $V_{n}(\mathcal{F})$ for $p>2$, that is, for very massive classes $\mathcal{F}$. Note that here we compare only the upper bounds. However, in Section 5 we will provide a lower bound showing that the effect indeed occurs. Namely, we will exhibit a marginal distribution of $X$ and a class $\mathcal{F}$ of regression functions satisfying the above entropy assumptions such that $V_{n}(\mathcal{F})$ is of the order $n^{-1/(p-1)}$, which is slower than the rate $n^{-2/(2+p)}$ for $W_{n}(\mathcal{F})$.

Observe also that in both cases, $p\in(0,2)$ and $p\in[2,\infty)$, we can use the same value $\varepsilon=n^{-1/(2+p)}$ to obtain the rates given in ((i)). We remark that this $\varepsilon$ satisfies the balance relation

We will further comment on this choice in Section 6.

We now turn to the consequences of Theorem 1 for low complexity classes $\mathcal{F}$, such as Vapnik–Chervonenkis (VC) classes and intersections of balls in finite-dimensional spaces. They roughly correspond to the case “$p\approx 0$”, and the rates for the minimax risk $W_{n}(\mathcal{F})$ are the same as for the minimax regret $V_{n}(\mathcal{F})$.

Assume first that the empirical covering numbers of $\mathcal{F}$ exhibit the growth

The rate of convergence of the excess risk as in (17) for VC-type classes has been obtained previously under the assumption that $L^{*}=0$ or for convex classes $\mathcal{F}$ (see discussion in Section 7 below). Theorem 3 does not rely on either of these assumptions.

In Section 5, we show that the bound of Theorem 3 is tight; there exists a function class such that, for any estimator, there exists a distribution on which the estimator differs from the regression function by at least $C(v/n)\log(en/v)$ with positive fixed probability. So, the extra logarithmic factor $\log(en/v)$ in the rate is necessary, even when the model is well-specified.

The next theorem deals with classes of functions

where $|\theta|_{0}$ denotes the number of non-zero components of $\theta$. We will also consider the simplex

Let $\mathcal{Y}=$, and $0\leq f_{j}\leq 1$ for $j=1,\ldots,M$. Then there exists an absolute constant $C>0$ such that

Inspection of the proofs shows that Theorems 2–4 as well as Theorem 5 below provide bounds on the risk not only in expectation but also in deviation. For example, under the assumptions of Theorem 3, along with (17) we obtain that there exists a constant $C>0$ depending only on $A$ such that, for any $t>0$,

The “in deviation” versions of Theorems 2, 4 and 5 are analogous and we skip them for brevity. We also note that all the results trivially extend to the case $\mathcal{Y}=[a,b]$, $\mathcal{F}\subseteq\{f\colon\ a\leq f\leq b\}$, where $-\infty<a<b<\infty$.

Adapting to approximation error rate of function class

In Theorem 2, we have shown that for $p>2$ our estimator has the rate of $n^{-2/(2+p)}$ when $\eta\in\mathcal{F}$ and achieves the rate of $n^{-1/p}$ if not. A natural question one can ask is what happens if $\eta\notin\mathcal{F}$ but the approximation error $\inf_{f\in\mathcal{F}}\|\eta-f\|^{2}$ is small. This can be viewed as an intermediate setting between the pure statistical learning and pure estimation. In such situation, one would expect to achieve rates varying between $n^{-1/p}$ and $n^{-2/(2+p)}$ depending on how small the approximation error is. This is indeed the case as described in the next theorem.

where $\Delta^{2}=\inf_{f\in\mathcal{F}}\|f-\eta\|^{2}$, $C_{p}>0$ is a constant depending only on $p$ and $A$, and

for $p>2$. At $p=2$ the rate $\bar{\psi}_{n,p}(\Delta)$ is $n^{-1/2}\log n$ independently of $\Delta$.

The proof of this theorem is given in Section 8.

Theorem 5 naturally suggests to study a minimax problem which is more general than those considered in Statistical Learning Theory or Nonparametric Estimation. Introduce the class of $\Delta$-misspecified models

and define the $\Delta$-misspecified regret as

Note that by definition, $V^{\Delta}_{n}(\mathcal{F})=W_{n}(\mathcal{F})$ when $\Delta=0$ and $V^{\Delta}_{n}(\mathcal{F})=V_{n}(\mathcal{F})$ when $\Delta=1$ (the diameter of $\mathcal{F}$). In general, $V^{\Delta}_{n}(\mathcal{F})$ measures the minimax regret when we consider the statistical estimation problem with approximation error at most $\Delta$. Theorem 5 implies that the rate of convergence of $\Delta$-misspecified regret admits the bound $V^{\Delta}_{n}(\mathcal{F})\leq C_{p}\bar{\psi}_{n,p}(\Delta)$.

Lower bounds

In this section, we show that the upper bounds obtained in Theorems 2, 3, and 5 cannot be improved. First, we exhibit a VC-subgraph class $\mathcal{F}$ with VC-dimension at most $d$ such that

where $C>0$ is a numerical constant. In fact, we will prove a more general lower bound, for the risk in probability rather than in expectation.

In the next theorem, $\mathcal{X}=\{x^{1},x^{2},\ldots\}$ is a countable set of elements and $\mathcal{F}$ is the following set of binary-valued functions on $\mathcal{X}$:

where $a>0$, ${\mathbf{1}}\{\cdot\}$ denotes the indicator function, $|W|$ is the cardinality of $W$, and $d$ is an integer. It is easy to check that $\mathcal{F}$ is a VC-subgraph class with VC-dimension at most $d$.

Let $d$ be any integer such that $n\geq d$, and $a=3/4$. Let the random pair $(X,Y)$ take values in $\mathcal{X}\times\{0,1\}$. Then there exist a marginal distribution $\mu_{X}$ and numerical constants $c,c^{\prime}>0$ such that

The proof of Theorem 6 is given in Section 10.

The next theorem provides lower bounds on $V_{n}(\mathcal{F})$ and $W_{n}(\mathcal{F})$ when the $\varepsilon$-entropy of $\mathcal{F}$ behaves as $\varepsilon^{-p}$. It implies that the rates for $V_{n}(\mathcal{F})$ and $W_{n}(\mathcal{F})$ in Theorem 2 are tight when $p<2$.

where $A$ is a constant depending only on $p$. Furthermore, for this $\mathcal{F}$, there exists an absolute positive constant $c$ such that the minimax risk satisfies, for any $n\geq 1$,

and the minimax regret satisfies, for any $p\geq 2$ and any $n\geq 1$,

The proof of Theorem 7 is given in Section 10. We remark that the lower bound (24) (for $p>2$) holds, up to logarithmic factors, for any class satisfying the entropy growth $\Omega(\varepsilon^{-p})$, but we omit the longer proof of this fact. We also remark that for $p>2$, the $n^{-1/p}$ lower bound can be shown for any estimator taking values within the class $\mathcal{F}$. Obtaining such a lower bound for any estimator remains an open problem.

Comparison with global ERM and with skeleton aggregation

Among the methods of estimation designed to work under general entropy assumptions on $\mathcal{F}$, the global ERM or the ERM on $\varepsilon$-nets hold a dominant place in the literature (see an overview in Section 7). Somewhat less studied method is skeleton aggregation . In this section, we discuss the deficiencies of these two previously known methods that motivated us to introduce aggregation-of-leaders.

Recall that the aggregation-of-leaders procedure has three steps. The first one is to find an empirical $\varepsilon$-net (that we will call a skeleton) from the first subsample and partition the function class based on the skeleton using the empirical distance on this subsample. In the next step, using the second subsample we find empirical risk minimizers within each cell of the partition. Finally, we use the third sample to aggregate these ERM’s. A simpler and seemingly intuitive procedure that we will call the skeleton aggregation consists of steps one and three, but not two. This method directly aggregates centers of the cells $\hat{\mathcal{F}}_{i}^{S}(\varepsilon)$, that is, the elements ${\hat{c}}_{i}$ of the $\varepsilon$-net obtained from the first subsample $S$. Such kind of procedure was studied by Yang and Barron in the context of well-specified models. The setting in is different from ours since in that paper the $\varepsilon$-net is taken with respect to a non-random metric and the bounds on the minimax risk $W_{n}(\mathcal{F})$ are obtained when the regression errors are Gaussian. Under this model, provides the bounds not for skeleton aggregation but for a more complex procedure that comprises an additional projection in Hellinger metric. We argue that, while the skeleton aggregation achieves the desired rates for well-specified models (i.e., for the minimax risk), one cannot expect it to be successful for the misspecified setting. This will explain why aggregating ERM’s in cells of the partition, and not simply aggregating the centers of cells, is crucial for the success of the aggregation-of-leaders procedure.

with probability at least $1-\delta$ over the sample $S^{\prime\prime}$, conditionally on $S$ (the subsample $S^{\prime}$ is not used here). If the model is well-specified, $L^{*}=L(\eta)$, and $\|f-\eta\|^{2}=L(f)-L^{*}$, $\forall f\in\mathcal{F}$. Hence, with probability $1-5\delta$,

Let us now consider the misspecified model setting (i.e., the statistical learning framework). Here, the balance relation for the skeleton aggregation takes the form $n\varepsilon\asymp\mathcal{H}_{2}(\mathcal{F},\varepsilon)$, which yields suboptimal rates unless the class $\mathcal{F}$ is finite. Indeed, without the assumption that the regression function $\eta$ is in $\mathcal{F}$, we only obtain the bounds

where $\eta_{\mathcal{F}}\in\mathcal{F}$ is such that $\|\eta_{\mathcal{F}}-\eta\|^{2}\leq\inf_{f\in\mathcal{F}}\|f-\eta\|^{2}+1/n$. The crucial difference from (6) is that here $L(\hat{c}_{i})-L^{*}$ behaves itself as a norm $\|\hat{c}_{i}-\eta_{\mathcal{F}}\|$ and not as a squared norm $\|\hat{c}_{i}-\eta\|^{2}$. Using (6) and arguing analogously to (6), we find that for misspecified models, with probability $1-5\delta$,

We can now compare the following three estimators. First, we consider the global ERM over $\mathcal{F}$ defined by

The rates for finite $\mathcal{F}$ in Table 1 are obtained in a trivial way by taking the skeleton that coincides with the $M$ functions in the class $\mathcal{F}$. In parametric and nonparametric regime, the rates for the proposed method are taken from Theorems 2 and 3, while for the skeleton aggregate they follow from (6) with optimized $\varepsilon$ combined with the bounds on $r^{*}$ in Lemma 8 and in (33), (41) below. The rate $\sqrt{v/n}$ for the excess risk of ERM in parametric case is well-known, cf., for example, . For the nonparametric regime, the rates for ERM in Table 1 follow from Lemma 11 and the bounds on $\mathfrak{R}_{n}(\mathcal{F})$ in (33) and (41) below. Moreover, for finite $\mathcal{F}$, it can be shown that the slow rate $\sqrt{\frac{\log M}{n}}$ cannot be improved neither for ERM, nor for any other selector, that is, any estimator with values in $\mathcal{F}$, cf. .

In conclusion, for finite class $\mathcal{F}$ aggregation-of-leaders and skeleton aggregation achieve the excess risk rate $\frac{\log M}{n}$, which is known to be optimal , whereas the global ERM has a suboptimal rate. For a very massive class $\mathcal{F}$, when the empirical entropy grows polynomially as $\varepsilon^{-p}$ with $p\geq 2$ both ERM and aggregation-of-leaders enjoy similar guarantees of rates of order $n^{-1/p}$ while the skeleton aggregation only gets a suboptimal rate of $n^{-1/(p+1)}$. For all other cases, while aggregation-of-leaders is optimal, both ERM and skeleton aggregation are suboptimal. Thus, in the misspecified case, skeleton aggregation is good only for very meager (finite) classes while ERM enjoys optimality only for the other extreme – massive nonparametric classes. Note also that, unless $\mathcal{F}$ is finite, skeleton aggregation does not improve upon ERM in the misspecified case.

Turning to the well-specified case, both aggregation-of-leaders and skeleton aggregation achieve the optimal rate for the minimax risk while the global ERM is, in general, suboptimal.

Historical remarks and comparison with previous work

The role of entropy and capacity in establishing rates of estimation has been recognized for a long time, since the work of Le Cam , Ibragimov and Has’minskiĭ and Birgé . This was also emphasized by Devroye and Devroye et al. in the study ERM on $\varepsilon$-nets. The common point is that optimal rate is obtained as a solution to the balance equation $n\varepsilon^{2}=\mathcal{H}(\varepsilon)$, with an appropriately chosen non-random entropy $\mathcal{H}(\cdot)$. Yang and Barron present a general approach to obtain lower bounds from global (rather than local) capacity properties of the parameter set. Once again, the optimal rate is shown to be a solution to the bias-variance balance equation described above, with a generic notion of a metric on the parameter space and non-random entropy. Under the assumption that the regression errors are Gaussian, also provides an achievability result via a skeleton aggregation procedure complemented by a Hellinger projection step. Van de Geer invokes the empirical entropy rather than the non-random entropy to derive rates of estimation in regression problems.

In all these studies, it is assumed that the unknown density, regression function, or parameter belongs to the given class, that is, the model is well-specified. In parallel to these developments, a line of work on pattern recognition that can be traced back to Aizerman, Braverman and Rozonoer and Vapnik and Chervonenkis focused on a different objective, which is characteristic for Statistical Learning. Without assuming a form of the distribution that encodes the relationship between the predictors and outputs, the goal is formulated as that of performing as well as the best within a given set of rules, with the excess risk as the measure of performance (rather than distance to the true underlying function). Thus, no assumption is placed on the underlying distribution. In this form, the problem can be cast as a special case of stochastic optimization and can be solved either via recurrent (e.g., gradient descent) methods or via empirical risk minimization. The latter approach leads to the question of uniform convergence of averages to expectations, also called the uniform Glivenko–Cantelli property. This property is, once again, closely related to entropy of the class, and sufficient conditions have been extensively studied (see and references therein).

Independently of this work on the excess risk in the distribution-free setting of statistical learning, Nemirovskii proposed to study the problem of aggregation, or mimicking the best function in the given class, for regression models. Nemirovskii outlined three problems: model selection, convex aggregation, and linear aggregation. The notion of optimal rates of aggregation based on the minimax regret is introduced in , along with the derivation of the optimal rates for the three problems. In the following decade, much work has been done on understanding these and related aggregation problems . For recent developments and a survey we refer to .

In parallel with this research, the study of the excess risk blossomed with the introduction of Rademacher and local Rademacher complexities . These techniques provided a good understanding of the behavior of the ERM method. In particular, if $\mathcal{F}$ is a convex subset of $d$-dimensional space, Koltchinskii obtained a sharp oracle inequality with the correct rate $d/n$ for the excess risk of least squares estimator on $\mathcal{F}$. Also, for convex $\mathcal{F}$ and $p\in(0,2)$, the least squares estimator on $\mathcal{F}$ attains the correct excess risk rate $n^{-2/(p+2)}$ under the assumptions of Theorem 2. This can be deduced from Theorem 5.1 in , remarks after it and in Example 4 on page 87 of . However, the convexity assumption appears to be crucial; without this assumption Koltchinskii , Theorem 5.2, obtains for the least squares estimator only a non-sharp inequality with leading constant $C>1$, cf. (3). As follows from the results in Section 3 our procedure overcomes this problem.

Among a few of the estimators considered in the literature for general classes $\mathcal{F}$, empirical risk minimization on $\mathcal{F}$ has been one of the most studied. As mentioned above, ERM and other selector methods are suboptimal when the class $\mathcal{F}$ is finite. For the regression setting with finite $\mathcal{F}$, the approach that was found to achieve the optimal rate for the excess risk in expectation is through exponential weights with averaging of the trajectory . However, Audibert showed that, for the regression with random design, exponential weighting is suboptimal when the error is measured by the probability of deviation rather than by the expected risk. He proposed an alternative method, optimal both in probability and in deviation, which involves finding an ERM on a star connecting a global ERM and the other $|\mathcal{F}|-1$ functions. In , the authors exhibited another deviation optimal method which involves sample splitting. The first part of the sample is used to localize a convex subset around ERM and the second – to find an ERM within this subset. Recently yet another procedure achieving the deviation optimality has been proposed in . It is based on a penalized version of exponential weighting and extends the method of originally proposed for regression with fixed design. The methods of provide examples of sharp MS-aggregates that can be used at the third step of our procedure.

We close this short summary with a connection to a different literature. In the context of prediction of deterministic individual sequences with logarithmic loss, Cesa-Bianchi and Lugosi considered regret with respect to rich classes of “experts”. They showed that mixture of densities is suboptimal and proposed a two-level method where the rich set of distributions is divided into small balls, the optimal algorithm is run on each of these balls, and then the overall output is an aggregate of outputs on the balls. They derived a bound where the upper limit of the Dudley integral is the radius of the balls. This method served as an inspiration for the present work.

Proofs of Theorems 2–4 and 5

The following values can be taken as localization radii $r^{*}=r^{*}(\mathcal{G})$ for $\mathcal{G}=\{(f-g)^{2}\colon\ f,g\in\mathcal{F}\}$. (

For any class $\mathcal{F}\subseteq\{f\colon\ 0\leq f\leq 1\}$, and $n\geq 2$,

If $\mathcal{F}\subseteq\{f\colon\ 0\leq f\leq 1\}$ and the empirical covering numbers exhibit polynomial growth $\sup_{S\in\mathcal{Z}^{n}}\mathcal{N}_{2}(\mathcal{F},\rho,S)\leq(\frac{A}{\rho})^{v}$ for some constants $A<\infty$, $v>0$, then

whenever $n\geq C_{A}v$ with $C_{A}>1$ large enough depending only on $A$.

If $\mathcal{F}$ is a finite class with $|\mathcal{F}|\geq 2$,

The proof of this lemma is given in the Appendix. The following lemma is a direct consequence of Theorem 14 proved in the Appendix.

For any class $\mathcal{F}\subseteq\{f\colon\ 0\leq f\leq 1\}$ and $\delta>0$, with probability at least $1-4\delta$,

where $\beta=(\log(1/\delta)+\log\log n)/n$, and $r^{*}=r^{*}(\mathcal{G})$ for $\mathcal{G}=\{(f-g)^{2}\colon\ f,g\in\mathcal{F}\}$.

We will also use the following bound on the Rademacher average in terms of the empirical entropy .

For any class $\mathcal{F}\subseteq\{f\colon\ 0\leq f\leq 1\}$,

Proof of Theorem 2 Consider the case $p\in(0,2)$. Assume without loss of generality that $A=1$, that is, $\sup_{S\in\mathcal{Z}^{n}}\log\mathcal{N}_{2}(\mathcal{F},\rho,S)\leq\rho^{-p}$. For $p\in(0,2)$, the bound (32) with $\alpha=0$ combined with (30) yields

These inequalities together with (11) and (12) yield that for $0<\delta<1/2$, with probability at least $1-2\delta$,

The value of $\varepsilon$ minimizing the right-hand side in (36) is $\varepsilon=n^{-1/(2+p)}$, which justifies the choice made in the theorem. Notably, the logarithmic factor arising from $r^{*}$ only appears together with the lower order terms and the summand $\gamma\sqrt{r^{*}}$ does not affect the rate. For $\varepsilon=n^{-1/(2+p)}$ the right-hand side of (36) is bounded by $Cn^{-2/(2+p)}$ ignoring the terms with $\log(1/\delta)$ that disappear when passing from the bound in probability to that in expectation. Thus, the expected excess risk is bounded by $Cn^{-2/(2+p)}$, which proves ((i)) for $p\in(0,2)$.

Next, consider the case $p>2$. From (32) with $\alpha=n^{-1/p}$, $\hat{\mathfrak{R}}_{n}(\mathcal{F},S)\leq Cn^{-1/p}$ and $r^{*}=(\log n)^{3}n^{-2/p}$. Choosing $\varepsilon=n^{-1/(2+p)}$,

The first statement of the theorem follows from (12) with the choice $\alpha=n^{-1/p}$ and by noting that $\frac{\varepsilon^{-p}}{n}$ is of the lower order than $n^{-1/p}$. The case of $p=2$ follows similarly (see proof of Theorem 5). The second part of the theorem follows from Theorem 5.

Proof of Theorem 3 Throughout this proof, $C$ is a generic notation for positive constants that may depend only on $A$. Since $\varepsilon=n^{-1/2}$ the expression for $r^{*}$ in Lemma 8(ii) leads to the bounds $\gamma\leq C(\sqrt{\frac{v\log(en/v)}{n}}+\sqrt{\frac{\log(1/\delta)}{n}})$, and $\gamma\sqrt{r^{*}}\leq C(\frac{v\log(en/v)}{n}+\frac{\log(1/\delta)}{n})$. Next, since $\mathcal{N}_{2}(\mathcal{F},\rho,S^{\prime})\leq\max\{1,(A/\rho)^{v}\}$ we get

where the last inequality is due to (Appendix). We assume w.l.o.g. that in the last expression $C$ is large enough to guarantee that the function $\gamma\mapsto\gamma\sqrt{\log({C}/{\gamma})\vee 1}$ is increasing, so that we can replace $\gamma$ by the previous upper bound. This yields, after some algebra,

if $n\geq Cv$ for $C$ large enough. The above inequalities together with (11) and (12) imply that, with probability at least $1-2\delta$,

Proof of Theorem 4 By definition of the estimator, for any fixed integer $m\leq s$ and $\nu$ such that $|\nu|=m$ we first construct the least squares estimators over the cells $\mathcal{F}_{\nu,m}$:

Proof of Theorem 5 Without loss of generality assume in this proof that $A=1$, that is, that $\sup_{S\in\mathcal{Z}^{n}}\log\mathcal{N}_{2}(\mathcal{F},\rho,S)\leq\rho^{-p}$. Using (32) we bound ${\mathfrak{R}}_{n}(\mathcal{F})$ for $p>2$ as follows:

For $p>2$, the balance equation $\alpha=n^{-1/2}\alpha^{-(p-2)/2}$ yields $\alpha=n^{-1/p}$. This and (30) lead to the bounds

Consider the case $p>2$. Let $\eta_{\mathcal{F}}\in\mathcal{F}$ be such that $\|\eta_{\mathcal{F}}-\eta\|^{2}\leq\inf_{f\in\mathcal{F}}\|f-\eta\|^{2}+1/n$. Lemma 9, (30) and (41) imply that, with probability at least $1-4\delta$, for all $i=1,\ldots,N$,

Since $\min_{i=1,\ldots,N}d_{S}(\hat{f}_{i}^{S,S^{\prime}},\eta_{\mathcal{F}})\leq 2\varepsilon$ and $\varepsilon=n^{-1/(2+p)}$ we get that, with probability at least $1-4\delta$,

Further, Lemma 11 and (41) imply that, with probability at least $1-2\delta$,

Combining this bound with (8) we can conclude that, with probability at least $1-6\delta$,

Together with (9), this yields the next bound that holds with probability at least $1-7\delta$:

and (20) follows. For $p=2$, the above bound gains a factor $\log n$ in front of $n^{-1/p}$ only.

Proof of Theorem 1

We start with the following bound on the risk of least squares estimators in terms of Rademacher complexity.

The proof of this lemma is given in the Appendix and is based on combination of results from . Note that here we have both the remainder term of the order $1/n$ and the leading constant 1, which is crucial for our purposes.

Recall that $N=\mathcal{N}_{2}(\mathcal{F},\varepsilon,S)$. Setting $t=\log(4N/\delta)$ and using (44) and (9) we obtain that, with probability at least $1-(3/2)\delta$,

To complete the proof of (12) we need to evaluate the Rademacher complexities appearing in (45):

The difficulty here is that the set $\hat{\mathcal{F}}_{i}^{S}=\hat{\mathcal{F}}_{i}^{S}(\varepsilon)$ is defined via the pseudo-metric $d_{S}$ based on sample $S$ while the empirical Rademacher complexity is evaluated on another sample $S^{\prime}$. To match the metrics, we embed $\hat{\mathcal{F}}_{i}^{S}(\varepsilon)$ into $d_{S^{\prime}}$-balls with properly chosen radius $\bar{\gamma}$:

where the pseudo-metric $d_{S^{\prime}}$ is taken with respect to the set $S^{\prime}$ while the $\varepsilon$-net $\hat{c}_{1},\ldots,\hat{c}_{N}$ is constructed with respect to $d_{S}$. The next lemma shows that, with high probability, $\hat{\mathcal{F}}_{i}^{S}(\varepsilon)$ is included into $\hat{\mathcal{F}}^{S,S^{\prime}}_{i}(\bar{\gamma})$ for an appropriate choice of $\bar{\gamma}$.

Applying this to $g=\hat{c}_{i}$ and taking a union bound over $i=1,\ldots,N$, completes the proof. ∎

Let $r^{*}=r^{*}(\mathcal{G})$ for $\mathcal{G}=\{(f-g)^{2}\colon\ f,g\in\mathcal{F}\}$. Then, for any $\bar{\gamma}\geq\sqrt{r^{*}}$ we have

Throughout the proof, we fix the samples $S$ and $S^{\prime}$. We have

where we have used the decomposition $(f(x)-y)^{2}=(f(x)-\hat{c}_{i}(x))^{2}+(\hat{c}_{i}(x)-y)^{2}+2(f(x)-\hat{c}_{i}(x))(\hat{c}_{i}(x)-y)$, $\forall x,y$, and the fact that $(\hat{c}_{i}(x)-y)^{2}$ does not depend on $f$. Conditionally on the sample $S$, the functions $\hat{c}_{i}$ are fixed. Consider the sets of functions

Recall that we assume $\hat{c}_{i}\in\mathcal{F}$ (the $\varepsilon$-net is proper). Thus $\mathcal{G}^{\prime}_{i}\subseteq\mathcal{G}[\bar{\gamma}^{2},S^{\prime}]$ for $\mathcal{G}=\{(f-g)^{2}\colon\ f,g\in\mathcal{F}\}$, which implies

where $\phi_{n}(\bar{\gamma}^{2})=\phi_{n}(\bar{\gamma}^{2},\mathcal{G})$ and the last inequality is due to the assumption $\bar{\gamma}^{2}>r^{*}$ and the fact that $\phi_{n}(r)/\sqrt{r}$ is non-increasing.

We now turn to the cross-product term in (9). Define the following sets of functions on $\mathcal{X}\times\mathcal{Y}$:

Observe that, for any $g_{f}\in\mathcal{G}_{i}^{S,S^{\prime}}$,

since $\hat{c}_{i}$ and $y$ take values in $\mathcal{Y}=$. For the same reason,

implying $\mathcal{N}_{2}(\mathcal{G}^{S,S^{\prime}}_{i},\rho,S^{\prime})\leq\mathcal{N}_{2}(\hat{\mathcal{F}}^{S,S^{\prime}}_{i}(\bar{\gamma}),\rho,S^{\prime})$ for all $\rho>0$. Hence, by Lemma 10,

where the integration goes to $\bar{\gamma}$ in view of (49). The lemma now follows from (9)–(48) and (9). ∎

Combining (45), Lemma 12 with $t=\log(16N/\delta)$, and Lemma 13 we find that, with probability at least $1-2\delta$,

Proofs of the lower bounds

Proof of Theorem 6 Fix some $0<\alpha<1$ and set $k=\lceil d/\alpha\rceil$. Let $\mathcal{C}$ be the set of all binary sequences $\omega\in\{0,1\}^{k}$ with at most $d$ non-zero components. By the $d$-selection lemma (see, e.g., Lemma 4 in ), for $k\geq 2d$ there exists of a subset $\mathcal{C}^{\prime}$ of $\mathcal{C}$ with the following properties: (a) $\log|\mathcal{C}^{\prime}|\geq(d/4)\log(k/(6d))$ and (b) $\rho_{H}(\omega,\omega^{\prime})\geq d$ for any $\omega,\omega^{\prime}\in\mathcal{C}^{\prime}$. Here, $\rho_{H}(\omega,\omega^{\prime})=\sum_{j}{\mathbf{1}}\{\omega_{j}\neq\omega^{\prime}_{j}\}$ denotes the Hamming distance where $\omega_{j},\omega^{\prime}_{j}$ are the components of $\omega,\omega^{\prime}$. To any $\omega\in\mathcal{C}^{\prime}$ we associate a function $g_{\omega}$ on $\mathcal{X}$ defined by $g_{\omega}(x^{i})=\omega_{i}$ for $i=1,\ldots,k$ and $g_{\omega}(x^{i})=0$, $i\geq k+1$, where $\omega_{i}$ is the $i$th component of $\omega$.

Consider now a set of functions $\mathcal{F}^{\prime}=\{\eta_{\omega}\colon\ \omega\in\mathcal{C}^{\prime}\}\subset\mathcal{F}$. Observe that, by construction,

On the other hand, the Kullback–Leibler divergence between $\mathbf{P}_{\omega}$ and $\mathbf{P}_{\omega^{\prime}}$ has the form

Using the inequality $-\log(1+u)\leq-u+u^{2}/2$, $\forall u>-1$, and the fact that $1/2\leq\eta_{\omega}(X)\leq 3/4$ for all $\omega\in\mathcal{C}^{\prime}$ we obtain that the expression under the expectation in the previous display is bounded by $2(\eta_{\omega}(X)-\eta_{\omega^{\prime}}(X))^{2}$, which implies

From (53), (54) and Theorem 2.7 in , the result of Theorem 6 follows if we show that

where $C_{1},C_{2}>0$ are constants. Assume first that $d\geq 4$. Then, using the inequalities $\log(|\mathcal{F}^{\prime}|-1)\geq\log(|\mathcal{C}^{\prime}|/2\geq(d/4)\log(k/(6d))-\log 2\geq(d/4)\log(1/(12\alpha))$ it is enough to show that

Using that $x\geq 2\log x$ for $x\geq 0$ it is easy to check that the inequality in the last display holds if we choose, for example, $C_{1}=1/16,C_{2}=1/(12C_{1})$. In the case $d\leq 3$, it is enough to consider $\alpha=(C_{1}/n)\log(C_{2}n)$ and (55) is also satisfied for suitable $C_{1},C_{2}$.

which implies that $|\mathcal{M}|\leq\exp(J/p)$. Thus (22) follows.

Proof of (23). Fix $d=\lceil n^{p/(2+p)}\rceil$. Let $\Omega_{d}=\{0,1\}^{d}$ be the set of all binary sequences of length $d$. Define $\mu_{X}$ as the distribution on $\mathcal{X}$ which is uniform on $\{\e_{1},\ldots,\e_{d}\}$, putting probability $1/d$ on each of these $\e_{j}$ and probability 0 on all $\e_{j}$ with $j\geq d+1$. For any $\omega\in\Omega_{d}$, denote by $\mathbf{P}_{\omega}$ the joint distribution of $(X,Y)$ having this marginal $\mu_{X}$ and $Y\in\{0,1\}$ with the conditional distribution defined by the relation

where $\hat{\omega}_{i}$ is the closest to $4d^{1/p}(\hat{f}_{i}-1/2)$ element of the set $\{0,1\}$. Therefore,

where $\rho_{H}(\cdot,\cdot)$ is the Hamming distance. From Assouad’s lemma (cf. Theorem 2.12(iv) in ),

where $\alpha=\max\{K(\mathbf{P}_{\omega},\mathbf{P}_{\omega^{\prime}})\colon\ \omega,\omega^{\prime}\in\Omega_{d},\rho_{H}(\omega,\omega^{\prime})=1\}$. Here, $\mathbf{E}^{(n)}_{\omega}$ denotes the distribution of the $n$-sample $D_{n}$ when $(X_{i},Y_{i})\sim\mathbf{P}_{\omega}$ for all $i$. Since $1/2\leq\eta_{\omega}(X)\leq 3/4$, the Kullback–Leibler divergence can be bounded in the same way as in (54):

for all $\omega,\omega^{\prime}\in\Omega_{d}$ such that $\rho_{H}(\omega,\omega^{\prime})=1$. Combining this result with (56) and (57), we find

for some absolute constant $c_{*}>0$. Now, the set $\{\eta_{\omega}\colon\ \omega\in\Omega_{d}\}$ is contained in $\mathcal{F}$, so that

and (23) follows immediately from (58) and (59).

Proof of (24). Set $d=2\lceil n^{p/(p-1)}\rceil$ and define the joint distribution $\mathbf{P}_{\omega}$ of $(X,Y)$ as in the proof of (23) with the difference that now we choose the conditional probabilities as follows:

where $f_{\omega}=\{f_{\omega}(\e_{j})\}\in\mathcal{F}$ is a sequence with components

For $j=1,\ldots,d$, denote by $\hat{f}[j]$ and $r_{j}$ the components of $\hskip 4.0pt{\bar{\hat{f}}}$ and of ${\bar{\eta}}_{\omega}$, respectively. We will sometimes write $\hat{f}[j]=\hat{f}[j,D_{n}]$ to emphasize the dependence on the sample $D_{n}=\{(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\}$. Then, we can rewrite the above integral in the form

Consider the random vector composed of indicators $\zeta=(I(X_{1}=e_{j}),\dots,I(X_{n}=e_{j}))$. For any $j$ and any fixed $r_{1},\ldots,r_{d}$,

where $G$ is some measurable function. Indeed, under the condition $\zeta=0$ the distribution of $D_{n}$ coincides with that of $\{(X_{i},Y_{i})\colon\ X_{i}\neq e_{j}\}$, which is entirely defined by $\{r_{k}\colon\ k\neq j\}$. Thus,

Using that $1-x\geq\exp(-3x/2)$ for $0<x\leq 1/2$ we have $(1-\frac{1}{d})^{n}\geq\exp(-3n/(2d))\geq 1-3n/(2d)$ for $d\geq 2n$. Since $d=2\lceil n^{p/(p-1)}\rceil$ we find

Appendix

The following result is a modification of Theorem 6.1 in .

where $\mathcal{G}_{k}=\{g\in\mathcal{G}\colon\ \delta_{k+1}\leq Pg\leq\delta_{k}\}$, $\delta_{k}=b2^{-k}$ for $k\geq 0$, and $k_{0}>0$ be the largest integer such that $\delta_{k_{0}+1}\geq b/n$. A straightforward modification of the argument in leading to (3) yields that, on the event ${\mathcal{B}}$,

Denote the event where (Appendix) holds by ${\mathcal{B}}^{\prime}$, and define

On the event ${\mathcal{B}}^{\prime}$ we have $P_{n}g\leq U^{\prime}$ for any $g\in\mathcal{G}^{\prime}$, so that

where $\phi_{n}(\cdot)=\phi_{n}(\cdot,\mathcal{G})$ is an upper function for $\mathcal{G}$ satisfying the sub-root property. In view of this property,

and thus, on the event ${\mathcal{B}}^{\prime}$,

On the other hand, $\mathcal{L}=\mathcal{G}[r,S]$, and $\mathfrak{R}_{n}(\mathcal{H})\leq 2\mathfrak{R}_{n}(\mathcal{F})$, so that

Now define the function $\phi_{n}(r)$ as the right-hand side of this inequality. This immediately yields a localization radius

Proof of (ii). Let $(f-g)^{2}$ and $(\bar{f}-\bar{g})^{2}$ be two elements of $\mathcal{G}$, where $f,g,\bar{f},\bar{g}\in\mathcal{F}$. Since all these functions take values in $$we get that, for any$x\in\mathcal{X}$,

Thus, if $d_{S}(f,\bar{f})\leq\varepsilon$ and $d_{S}(g,\bar{g})\leq\varepsilon$ for some $\varepsilon>0$, then $d_{S}((f-g)^{2},(\bar{f}-\bar{g})^{2})\leq 4\varepsilon$. This implies the relation between the empirical entropies: $\mathcal{N}_{2}(\mathcal{G},\rho,S)\leq\mathcal{N}_{2}(\mathcal{F},\rho/4,S)$ for all $\rho>0$. Using it together with the bound $\mathcal{N}_{2}(\mathcal{F},\rho/4,S)\leq\max\{1,(4A/\rho)^{v}\}$ and applying Lemma 10 we obtain

where we have used that, integrating by parts,

In view of (Appendix), we can take $\phi_{n}(r)=24\sqrt{\frac{vr}{n}}(\log(4eA/\sqrt{r})\vee 1)^{1/2}$ as an upper function in (7). Now, we are looking for $r^{*}$, which is an upper bound on the solution of the equation $\phi_{n}(r)=r$. Since the function $u\mapsto(a/u)(\log(b/u)\vee 1)^{1/2}$, for $a,b>0$, is decreasing when $u>0$ one can check that $u^{*}=a(\log(b/a)\vee 1)^{1/2}$ as an upper bound on the solution of $(a/u)(\log(b/u)\vee 1)^{1/2}=1$ whenever $b\geq ea>0$. That is, for $n\geq Cv$ with $C>0$ large enough depending only on $A$, we can take

for some constant $C>0$ depending only on $A$.

Proof of (iii). For a finite class $\mathcal{F}$, the covering numbers satisfy $\mathcal{N}_{2}(\mathcal{F},\varepsilon,S)\leq|\mathcal{F}|$ for all $\varepsilon>0$ and, along the lines of (Appendix),

so that we can take $r^{*}=144(\log|\mathcal{F}|)/n$.

Acknowledgements

We gratefully acknowledge the support of NSF under Grants CAREER DMS-0954737 and CCF-1116928. The work of the third author was supported by GENES, and by the French National Research Agency (ANR) under the Grants Idex ANR-11-IDEX-0003-02, Labex ECODEC (ANR-11-LABEX-0047), and IPANEMA (ANR-13-BSH1-0004-02).

References