Learning subgaussian classes : Upper and minimax bounds

Preface

Most the results contained in this note have been presented at the SMF meeting, which took place in May 2011; the rest have been obtained shortly after the time of the meeting.

The question we study has to do with the optimality of Empirical Risk Minimization as a learning procedure in a convex class – when the problem is subgaussian. Subgaussian learning problems are a natural object because they are the simplest unbounded learning scenarios. However, an additional reason for studying such problems was that at the time of the SMF meeting, the technical machinery required for the analysis of more heavy-tailed problems was simply not known. Since 2011, significant progress has been made in the understanding of learning problems in heavy-tailed situations , though this progress does not make the results presented here obsolete. We show that ERM performed in a convex class is an optimal learning procedure (in a sense that will be clarified) when the learning problem is subgaussian. This happens to be a rather special feature of subgaussian learning problems, and under weaker tail assumptions ERM fails to deliver the optimal accuracy/confidence trade-off at the high level of accuracy we are interested in here.

The results presented here are complemented in , which also focuses on subgaussian learning problems and addresses some of the cases that have not been resolved in this note.

Introduction and main results

In the classical statistics setup, one usually assumes that the regression function of $Y$ given $X$ belongs to some particular function space (called a statistical model). In contrast, in the learning setup on which we focus here, one is given a function class ${\mathcal{F}}$ (sometimes, called a model as well), and the goal is to construct a procedure $\hat{f}_{N}$ that satisfies a sharp or exact oracle inequality (following ; such bounds are called excess risk bounds in and ). An exact oracle inequality ensures that with high probability,

and one would like to make the residue in (1.1) as small as possible.

For the sake of simplicity, we assume that there is some $f^{*}\in{\mathcal{F}}$ minimizing the risk in ${\mathcal{F}}$ (though the claims presented here remain true even without that assumption), and we set

Note that in (1.1) the performance of the procedure ${\hat{f}_{N}}$ is compared to the best performance possible in ${\mathcal{F}}$, i.e., to the risk of the best element $f^{*}\in{\mathcal{F}}$. This exhibits the point of view of Learning Theory, where one wishes to identify a function that is almost as good as the best possible in ${\mathcal{F}}$, regardless of whether the best function in ${\mathcal{F}}$ has a small risk. It is different from typical questions in classical Statistics, where a statistical model is given and the risk of an estimator is compared to the one of the regression function (or Bayes rule). The latter are usually called excess risk bounds (cf. ) and are actually very different from exact oracle inequalities like (1.1) (see, for example, or Chapter 1.3 in for more details on those differences).

The performance of a procedure is measured relative to a set of admissible targets $Y$ in some class of random variables ${\cal Y}$. Naturally, one would like to make ${\cal Y}$ as large as possible, for example, all random variables $Y$ bounded by $1$, all the random variables $Y$ in $L_{p}$ for some $p>2$, or a similar weak condition of that flavor.

Clearly, while the true risk of $f$ is not known, simply because $X$ and $Y$ are not known, one still has access to its empirical counterpart:

Thus, a natural procedure that comes to mind is finding a function in ${\cal F}$ that best fits the data: a minimizer of the empirical risk in ${\mathcal{F}}$. This procedure is called empirical risk minimization (ERM) and is defined by

ERM has been studied extensively over the last $40$ years (see, e.g. , , and references therein), and the main goal has always been to identify connections between the structure of ${\mathcal{F}}$ and the accuracy and confidence that ERM yields, while trying to minimize the restrictions on ${\cal Y}$. Among the natural questions regarding the performance of ERM are:

1. Given any confidence parameter $0<\delta_{N}<1/2$, what is the error rate $\varepsilon_{N}$ that one may obtain using ERM, and what features of ${\mathcal{F}}$ govern that rate?

2. Given any $0<\delta_{N}<1/2$, is ERM an optimal procedure for the confidence level $\delta_{N}$? In other words, is there a procedure that can perform with a better accuracy than ERM, given the same confidence level?

and set $k_{N}^{*}(\gamma)=\inf\left\{r>0:8k_{N}(r)\leq\gamma r^{2}\sqrt{N}\right\}$.

There exist absolute constants $c_{0},c_{1}$ and $q>2$ for which the following holds. If ${\cal Y}$ consists of functions that are bounded by $1$ and ${\mathcal{F}}$ is a convex class of functions that are bounded by $1$, then for any $Y\in{\cal Y}$ and every $t>0$, with probability at least $1-c_{0}\exp(-t)$,

A result of a similar flavor was obtained in : let $N(A,B)$ be the number of translates of $B$ needed to cover $A$. Set $D$ to be the unit ball in $L_{2}(\mu)$ and let

for absolute constants $c_{0},c_{1},c_{2}$.

The result in is that under various assumptions on the class ${\mathcal{F}}$ (assumptions that allow one to upper bound the function $k_{N}(r)$ using the entropy integral in (1.4)), $(\sigma^{*})^{2}$ may serve as a residual term.

These two facts rely heavily on the assumption that ${\mathcal{F}}$ and ${\cal Y}$ are bounded in $L_{\infty}$ and their proofs do not extend beyond the bounded case.

Let $\mu$ be a probability measure and let $X$ be distributed according to $\mu$. The $\psi_{2}(\mu)$-norm of a function $f$ is

The space of functions with a finite $\psi_{2}$-norm is denoted by $L_{\psi_{2}}=L_{\psi_{2}(\mu)}$.

A function class ${\mathcal{F}}\subset L_{2}(\mu)$ is $L$-subgaussian with respect to the probability measure $\mu$ if for every $f,h\in{\mathcal{F}}\cup\{0\}$, $\left\|f-h\right\|_{\psi_{2}(\mu)}\leq L\left\|f-h\right\|_{L_{2}(\mu)}$.

Note that for any $f\in L_{\psi_{2}}$, $\left\|f\right\|_{L_{2}(\mu)}\leq\left\|f\right\|_{\psi_{2}(\mu)}$. A class is a subgaussian class when the reverse inequality holds, and in particular when the $\psi_{2}$ and $L_{2}$ norms are equivalent on ${\mathcal{F}}$.

Note that norm equivalence is very different from being bounded. Having such a norm equivalence implies that $|f|\sim\|f\|_{L_{2}(\mu)}$ on a relatively large event. In contrast, even though a bounded function has a finite $\psi_{2}$ norm (by selecting $c\sim\|f\|_{L_{\infty}}$ in the definition of the $\psi_{2}$ norm), the fact that $f$ is bounded does not mean that $\|f\|_{\psi_{2}}$ is equivalent to $\|f\|_{L_{2}}$, nor that $|f|\sim\|f\|_{L_{2}(\mu)}$ on a relatively large event. Because of the substantial difference between the two notions, one should not expect that learning procedures exhibit the same performance when one assumes that ${\mathcal{F}}$ is bounded in $L_{\infty}$ or when the $\psi_{2}(\mu)$ and $L_{2}(\mu)$ norms are equivalent on ${\mathcal{F}}$.

where here, and throughout this note we write $u\lesssim v$ if $u\leq c_{0}v$ for an absolute constant $c_{0}$. Thus, the measure associated with the random vector $X=(x_{1},...,x_{d})$ is $cL$-subgaussian. Also, the measure is clearly isotropic.

By Khintchine’s inequality (see, for example, ),

$\bullet$ If $x$ is a mean-zero, variance one, $L$-subgaussian random variable, and $X=(x_{i,j})$ is a matrix whose coordinates are independent copies of $x$, then $X$ defines a $cL$ subgaussian, isotropic measure on the space of matrices of the right dimensions, relative to the natural trace inner product. The same holds if $X$ has independent rows, distributed according to an isotropic, $L$-subgaussian random vector. The proof of both facts is straightforward and are omitted.

The strategy we use here for the study of ERM is the isomorphic method, introduced in and analyzed there in the bounded setup. Before presenting it, recall that the excess loss of $f$ is

A rather obvious but very useful observation is that for every $f\in{\mathcal{F}}$, $P{\mathcal{L}}_{f}\geq 0$, while the empirical minimizer $\hat{f}$ satisfies that $P_{N}{\mathcal{L}}_{\hat{f}}\leq 0$.

The isomorphic method is based on the following idea. Consider an event $\Omega_{0}$, on which for every function $f$ in the set $\{f\in{\mathcal{F}}:P{\mathcal{L}}_{f}\geq\lambda_{N}\}$,

It follows that on $\Omega_{0}$, ERM produces $\hat{f}$ that satisfies

because $P_{N}{\mathcal{L}}_{\hat{f}}\leq 0$; therefore, $\hat{f}\not\in\{f\in{\mathcal{F}}:P{{\mathcal{L}}_{f}}\geq\lambda_{N}\}$.

Consequently, an exact oracle inequality with a confidence parameter $\delta_{N}$ may be derived by identifying $\lambda_{N}$ for which $\Omega_{0}$ has probability at least $1-\delta_{N}$; that is, the level $\lambda_{N}$ for which

with probability at least $1-\delta_{N}$ (see Theorem 4.4 in for results of a similar flavor).

Note that only the lower estimate in (1.6) is needed for the argument outlined above to work. This observation is the key in the application of the recent works on the small-ball method in learning theory (cf. ), which allows one to deal with heavy-tailed scenarios that are far more general than subgaussian problems.

Just like $k_{N}^{*}$ in (1.3) and $\sigma^{*}$ in (1.4) – and many other well known estimates on the performance of ERM (e.g. ) – the residual term we use is defined in terms of fixed points. Unlike $k_{N}^{*}$ and $\sigma^{*}$, the geometric complexity measure we use here is based on gaussian averages associated with localizations of the class. We refer the reader to Chapter 12 in for more details on gaussian processes (in particular to Theorem 12.1.3 for the existence of such a process and to Theorem 12.1.4 for its linearity).

This supremum is called the lattice supremum (see Chapter 2.2 in for more details).

We are now in a position to introduce the two complexity parameters that will serve as residual terms in the exact oracle inequalities satisfied by ERM.

For any $s\geq 0$, set $sD=\{f\in L_{2}(\mu):\left\|f\right\|_{L_{2}(\mu)}\leq s\}$ and ${\mathcal{F}}-{\mathcal{F}}=\{f-h:f,h\in{\mathcal{F}}\}$. For every $\eta>0$, let

In what follows we will always assume without mentioning it explicitly that the sets in (1.7) and (1.8) are nonempty (for example, this forces that $Q\geq c/\sqrt{N}$).

With these definitions in place, one may formulate a restricted version of the upper bound on the performance of ERM – for a convex, $L$-subgaussian class of functions.

Theorem A. 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 ${\mathcal{F}}\subset L_{2}(\mu)$ be a convex, $L$-subgaussian class of functions, assume that $\|Y-f^{*}(X)\|_{\psi_{2}}\leq\sigma$ and set $\eta=c_{1}/(L\sigma)$ and $Q=c_{2}/L^{2}$.

1. If $\sigma\geq c_{3}r_{N}^{*}(Q)$ then with probability at least $1-6\exp(-c_{4}N\eta^{2}(s_{N}^{*}(\eta))^{2})$,

2. If $\sigma\leq c_{3}r_{N}^{*}(Q)$ then with probability at least $1-6\exp(-c_{4}NQ^{2})$,

Hence, with probability at least $1-6\exp\left(-c_{4}N\min\{\eta^{2}(s_{N}^{*}(\eta))^{2},Q^{2}\}\right)$,

Once noise is introduced to the problem and passes a certain threshold, it is no longer realistic to expect that an intrinsic parameter, which does not depend on the noise level, can serve as an upper bound. And, indeed, $s_{N}^{*}(\eta)$ measures the interaction between the ‘noise’We keep the terminology from Statistics: the difference between the output variable $Y$ and the target function $f^{*}(X)$ is called the noise. This coincides with the classical definition of noise in Statistics when $f^{*}$ is the regression function. $f^{*}(X)-Y$ and the class through the choice of $\eta\sim 1/\sigma$. Thus, beyond a certain noise-level $\sigma$, which depends on the ‘complexity’ of the class ${\mathcal{F}}$, $s_{N}^{*}(c/\sigma)$ becomes the dominant term in the upper bound.

Note that in the free-noise case, $\sigma=0$, one has $s_{N}^{*}(c/\sigma)=0$. Therefore, the error rate of ERM depends only on $r_{N}^{*}(Q)$. Also, when the number of observations $N$ is large enough, one also has $r_{N}^{*}(Q)=0$, leading to exact reconstruction.

Of course, Theorem A would be better justified if one could obtain matching lower bounds, showing that ERM is an optimal procedure for subgaussian problems. To that end, it seems natural to employ minimax theory (see, e.g., for more details on minimax bounds).

What is a reasonable way of identifying a lower bound on the performance of a learning procedure is to see what accuracy and confidence it can guarantee for a minimal set of admissible targets ${\cal Y}$, and a natural choice of a minimal set of targets is

for every $f\in{\mathcal{F}}$ and $W$ that is a centered gaussian random variable that has variance $\sigma^{2}$ and is independent of $X$. Thus, this minimal set of targets consists of ‘independent perturbations’ of realizable learning problems, and thus is arguably the smallest set of ‘noisy’ targets. The minimax rate is (at least) the best accuracy/confidence trade-off that a learning procedure may attain in ${\mathcal{F}}$ for the set targets (1.9). Our main focus will be on the accuracy/confidence tradeoff for the accuracy level described in Theorem A.

Standard minimax bounds are based on information-theoretical results such as Fano’s Lemma, Assouad’s Lemma or Pinsker’s inequalities. Unfortunately, these results do not yield lower bounds in the high probability realm of Theorem A; rather, these results are restricted to constant confidence or hold in expectation. To treat the high probability regime, we present a new minimax bound that is based on the gaussian shift theorem (and therefore on the gaussian isoperimetric inequality).

Note that no assumption on the underlying measure $\mu$ is required in Theorem A′. Moreover, Theorem A′ makes a natural connection between accuracy and confidence: the higher the confidence $1-\delta_{N}$ the larger $\varepsilon_{N}$ must be.

An important outcome of Theorem A and Theorem A′ is that for the set of admissible targets ${\cal Y}$ as in (1.9), and as long as the class ${\mathcal{F}}$ is convex and $L$-subgaussian, ERM is optimal in the following sense:

Theorem A′′. There exist absolute constants $c_{1},...,c_{4}$ for which the following holds. Let ${\mathcal{F}}$ be a convex, $L$-subgaussian class of functions and consider the set of admissible targets ${\cal Y}$ as in (1.9). Set $\eta=c_{1}/(L\sigma)$ and $Q=c_{2}/L^{2}$. If $\sigma\geq c_{3}r_{N}^{*}(Q)$ then for any target $Y^{f}\in{\cal Y}$, the ERM $\hat{f}$ satisfies

Thus, up to the constant in the exponent, the upper bound and the lower bound match and the ERM achieves this bound.

The second question we wish to address is what happens when the desired confidence is an absolute constant – for example, when $1-\delta_{N}$ is, say, $1/2$, but the noise level is nontrivial in the sense that $s_{N}^{*}$ dominates $r_{N}^{*}$. We will show that in such a situation, Theorem A is optimal in a minimax sense under some regularity assumptions on ${\mathcal{F}}$. This complements Theorem A′′ which proves the optimality of ERM (under no extra structural assumption) in the high probability case – when $\delta_{N}\sim\exp(-c\eta^{2}(s_{N}^{*}(\eta))^{2}N)$.

To explore the constant confidence regime, let us consider the ‘Sudakov analog’ of the gaussian-based parameter $s_{N}^{*}(\eta)$: recall that by Sudakov’s inequality (see, for example, ), for any $r>0$,

Put $C(r)=\sup_{f\in{\mathcal{F}}}r\log^{1/2}N(({\mathcal{F}}-f)\cap 2rD,rD)$ and set

Theorem B is known, and may be derived from Theorem 2.5 in or from . The proof presented here is new, and follows the same path as the proof of Theorem A′.

With Theorem A in mind, Theorem B implies that if the learning problem is subgaussian, $s_{N}^{*}(\eta)$ and $q_{N}^{*}(\eta^{\prime})$ are equivalent for $\eta,\eta^{\prime}\sim 1/\sigma$ and $\sigma\gtrsim r_{N}^{*}$, the minimax rate in the constant probability regime is attained by ERM.

Finally, let us consider the low-noise case, in which $\sigma\lesssim r_{N}^{*}$. Although it is not clear if $r_{N}^{*}$ is an optimal bound in that range (except when $\sigma\sim r_{N}^{*}$), it turns out that it is not far from optimal.

with the probability taken with respect to the product measures endowed by $(Y_{i}^{f},X_{i})_{i=1}^{N}$.

and by Theorem C, $c_{N}(T)/8$ is a lower bound on the minimax rate in the constant confidence regime. Therefore, when $r_{N}^{*}\sim c_{N}(T)$, it follows that for every $0\leq\sigma\lesssim r_{N}^{*}$, $r_{N}^{*}$ is the constant-probability minimax rate, and that rate is achieved by ERM.

It should be noted that although our presentation focuses on oracle inequalities in a given class, oracle inequalities for model selection and regularized procedures can be derived from the isomorphic method in general, specifically, from Theorem 2.8 below. This strategy is rather standard and has been used, for example, in , in Chapter 3.6 of or recently in . We will not present results on regularization methods or model selection methods in what follows since those may be easily obtained from results on ERM.

We end this introduction with a word about notation. Throughout, absolute constants or constants that depend on other parameters are denoted by $c$, $C$, $c_{1}$, $c_{2}$, etc., (and, of course, we will specify when a constant is absolute and when it depends on other parameters); their values may change from line to line. The notation $x\sim y$ (resp. $x\lesssim y$) means that there exist absolute constants $0<c<C$ for which $cy\leq x\leq Cy$ (resp. $x\leq Cy$). If $b>0$ is a parameter then $x\lesssim_{b}y$ means that $x\leq C(b)y$ for some constant $C(b)$ that depends only on $b$.

The proofs of our main results are presented in the next two sections. We then present several examples of applications of those results, in which the rates established in Theorem A are shown to be sharp in both the high and constant confidence regimes. The final section contains some concluding remarks.

Proof of Theorem A

The proof of Theorem A shows that it is more general than stated. Rather than convexity, the two properties that are actually needed are the following:

A class ${\mathcal{H}}$ is star-shaped around $h_{0}\in{\mathcal{H}}$ if for every $h\in{\mathcal{H}}$, the interval $[h,h_{0}]$ is contained in ${\mathcal{H}}$.

We will assume that ${\mathcal{F}}-{\mathcal{F}}=\{f-h:f,h\in{\mathcal{F}}\}$ is star-shaped around , otherwise, one may consider the star-shaped hull of ${\mathcal{F}}-{\mathcal{F}}$ with , that is, the set

which is not much larger than ${\mathcal{F}}-{\mathcal{F}}$. The second property required is a variant of the Bernstein condition (cf. ).

A class ${\mathcal{F}}$ is $B$-Bernstein relative to the target $Y$, if for every $f\in{\mathcal{F}}$,

In what follows, we shall assume that ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around and that ${\mathcal{F}}$ satisfies the Bernstein condition (2.1).

The next lemma (which will be proved in the Appendix) shows that the assumption that ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around adds some regularity to the gaussian process $\{G_{f}:f\in{\mathcal{F}}-{\mathcal{F}}\}$.

For $\eta>0$ and any $s\geq s_{N}^{*}(\eta)$, $\psi(s)\leq\eta s^{2}\sqrt{N}$, and for any $0<s<s_{N}^{*}(\eta)$, $\psi(s)\geq\eta s^{2}\sqrt{N}$.

Let $Q>\sqrt{\pi/2N}$. For any $r\geq r_{N}^{*}(Q)$, $\psi(r)\leq Qr\sqrt{N}$ and for any $0<r<r_{N}^{*}(Q)$, $\psi(r)>Qr\sqrt{N}$.

A straightforward outcome of Lemma 2.3 which will be used later is as follows:

Let $c,\sigma,Q>0$, set $\eta=c/\sigma$ and consider $s_{N}^{*}(\eta)$ and $r_{N}^{*}(Q)$ as introduced in Definition 1.6.

If $\sigma\geq(c/Q)r_{N}^{*}(Q)$ then $s_{N}^{*}(\eta)\geq r_{N}^{*}(Q)$, and if $\sigma\leq(c/Q)r_{N}^{*}(Q)$ then $s_{N}^{*}(\eta)\leq r_{N}^{*}(Q)$.

If $s_{N}^{*}(\eta)\geq r_{N}^{*}(Q)$ then $\eta s_{N}^{*}(\eta)\leq 4Q$.

The proof of Lemma 2.4 will also be presented in the Appendix.

When considering the parameters $r_{N}^{*}(Q)$ and $s_{N}^{*}(\eta)$, what may seem odd at first glance is the different normalization in their definition – the first condition is linear, while the second is quadratic. The two originate from the need to compare the way in which two processes, the quadratic component and the multiplier component of the excess loss functional scale with $\|f-f^{*}\|_{L_{2}(\mu)}$. Indeed, note that

and that is the source of the seemingly less-natural normalization in the definition of $s_{N}^{*}(\eta)$.

Let us begin with an estimate on the quadratic component, which is based on a functional Bernstein type inequality (see ).

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. Let ${\cal H}$ be an $L$-subgaussian class. For every $u>0$, with probability at least $1-2\exp(-c_{1}\min(u^{2},u\sqrt{N}))$,

The following result is a straightforward application of Theorem 2.5 and illustrates the role of $r_{N}^{*}(Q)$.

There exist absolute constants $c_{1},c_{2}$ and $c_{3}$ for which the following holds. Let ${\mathcal{F}}$ be an $L$-subgaussian class, assume that ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around and let $f^{*}\in{\mathcal{F}}$. If $0<Q\leq 1$ and $r>r_{N}^{*}(Q)$, then with probability at least 1-2\exp\big{(}-c_{1}Q^{2}N\big{)},

Remark. Using the notation of Lemma 2.5, consider $Q\leq\min\{1/(2c_{2}L^{2}),1\}$. If (2.3) holds then for every $f\in{\mathcal{F}}$ that satisfies $\|f-f^{*}\|_{L_{2}(\mu)}\geq r>r_{N}^{*}(Q)$, one clearly has

The second ingredient required for the proof of Theorem A is a bound on multiplier processes.

[Theorem 4.4 in ] There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. If ${\cal H}$ is an $L$-subgaussian class and $\xi\in L_{\psi_{2}}$, then for every $u,w\geq 8$, and every integer $s_{0}\geq 1$, with probability at least

Combining the estimates on the quadratic and multiplier process leads to the following ratio estimate:

For every $L\geq 1$ and $B\geq 1$ there exist constants $c_{0},c_{1},c_{2}$ and $c_{3}$ that depend only on $B$ and $L$ for which the following holds. Let ${\cal F}$ be an $L$-subgaussian class that is $B$-Bernstein relative to the target $Y$. Assume that ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around and that $\|Y-f^{*}(X)\|_{\psi_{2}}\leq\sigma$. Set $\eta=c_{0}/(LB\sigma)$ and $Q=c_{1}/(L^{2}B)$.

1. If $\sigma\geq c_{2}r_{N}^{*}(Q)$, then with probability at least $1-6\exp\left(-c_{3}N\cdot\eta^{2}(s_{N}^{*}(\eta))^{2}\right)$,

2. If $\sigma\leq c_{2}r_{N}^{*}(Q)$, then with probability at least $1-6\exp\left(-c_{3}Q^{2}N/B\right)$,

Fix $\lambda>0$ and let ${\cal F}_{\lambda}=\{f\in{\mathcal{F}}:P{\cal L}_{f}\geq\lambda\}$. Since ${\mathcal{F}}$ satisfies the $B$-Bernstein condition relative to $Y$, it follows that for every $f\in{\mathcal{F}}$, $\|f-f^{*}\|^{2}_{L_{2}(\mu)}\leq BP{\cal L}_{f}$. Moreover, if $f\in{\cal F}_{\lambda}$ then

and ${\cal H}=({\cal F}-{\cal F})\cap\sqrt{\lambda B}D$. Recall that ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around , and by (2.5) one has that

Fix $\eta=c_{0}/(LB\sigma)$ and $Q=c_{1}/(L^{2}B)$ for suitable absolute constants $c_{0}$ and $c_{1}$. Set $r>r_{N}^{*}(Q)$ and note that by Lemma 2.4, if $\sigma\geq c_{2}r_{N}^{*}(Q)$ then $r_{N}^{*}(Q)\leq s_{N}^{*}(\eta)$ and $\eta s_{N}^{*}(\eta)\geq 4Q$, and if $\sigma\leq c_{2}r_{N}^{*}(Q)$ then $r_{N}^{*}(Q)\geq s_{N}^{*}(\eta)$; also $c_{2}=c_{0}/LBQ=c_{0}L/c_{1}$.

First, consider the case $\sigma\geq c_{2}r_{N}^{*}(Q)$. Applying Lemma 2.6 for $\lambda=(s_{N}^{*}(\eta))^{2}/B$, it follows that with probability at least $1-2\exp(-c_{3}Q^{2}N)$

provided that $Q\leq 1/(4c_{4}L^{2}B)$. Moreover, by (2.4), and because $\eta s_{N}^{*}(\eta)\geq 4Q$, one has that with probability at least

Thus, for any $Q\lesssim 1/L^{2}B$ and $\eta\lesssim 1/\sigma LB$, if $\sigma\geq c_{2}Lr_{N}^{*}(Q)$ then with probability at least $1-6\exp(-c_{8}N\cdot\eta^{2}(s_{N}^{*}(\eta))^{2})$, the following holds: for every $f\in{\mathcal{F}}$ that satisfies that $P{\mathcal{L}}_{f}\geq\lambda$,

Next, let us consider that case $\sigma\leq c_{2}r_{N}^{*}(Q)$ which follows a very similar path to the first case. Recall that $r_{N}^{*}(Q)\geq s_{N}^{*}(\eta)$. Setting $\lambda=(r_{N}^{*}(Q))^{2}/B$, it follows from Lemma 2.6 and (2.4) that with probability at least

as long as $Q\lesssim 1/(L^{2}B)$ and $\eta\lesssim 1/(\sigma LB)$. The claim now follows because $\eta\sim 1/\sigma$ and by the choice of $\sigma$, namely, that $r_{N}^{*}(Q)/\sigma\geq c_{2}$.

Theorem A is an immediate outcome of Theorem 2.8 for $B=1$ and the isomorphic method described in the introduction.

Minimax lower bounds (proofs of Theorem A′, B and C)

where ${\mathcal{L}}_{h}(X,Y^{f})=(Y^{f}-h(X))^{2}-(Y^{f}-f(X))^{2}$.

The first estimate presented here is the high probability lower bound, formulated in Theorem A′.

The main component in the proof of Lemma 3.3 is a version of the gaussian shift theorem.

Let $B=(A-u)/\sigma$, $w=(u-v)/\sigma$ and set $\nu(B)=\alpha$. Using the notation of Theorem 3.4, the corresponding halfspace is

and the claim follows from Theorem 3.4 and the definition of $w$.

Next, let us turn to the proof of Theorem B, which is a straightforward application of the next observation:

Proof. Observe that if $a_{N}\geq(1/2)d_{{\mathcal{F}}}(L_{2})$ then $|\Lambda|=1$ and Theorem 3.5 is trivially true. Hence, one may assume that $a_{N}<(1/2)d_{{\mathcal{F}}}(L_{2})$.

Let $a=a_{N}$, set $D(f,r)=\{h\in{\mathcal{F}}:\|f-h\|_{L_{2}(\mu)}\leq r\}$ and put $\Lambda$ to be a maximal $2a$-separated subset of ${\mathcal{F}}\cap(f+\theta aD)$ with respect to the $L_{2}(\mu)$ norm. Thus, $\{D(f,a):f\in\Lambda\}$ is a family of disjoint subsets of ${\mathcal{F}}\cap(f+\theta aD)$.

where $\varphi$ is a density function of a the standard gaussian ${\mathcal{N}}(0,1)$ and

and it remains to lower bound each expectation.

Another application of Chebyshev’s inequality shows that with $\mu^{N}$-probability at least $2/3$,

because $v\in D(v_{0},\theta a)$. Therefore, with $\mu^{N}$-probability at least $1/3$,

and since $\beta+(3/2)\sqrt{N}\theta a/\sigma>0$,

Thus, by (3.2), 1\gtrsim|\Lambda|\exp\big{(}-c_{3}N\theta^{2}a^{2}/\sigma^{2}\big{)}, as claimed.

Taking the expectation in ($*$) with respect to $\delta$,

and if $\sigma\lesssim r_{N}^{*}(Q)$, the error rate obtained in Theorem A is the minimax rate in the constant probability range.

Examples

In this section, we present two examples in which our results lead to sharp upper and lower minimax bounds, thus showing the optimality (in some minimax sense) of ERM.

and if $s\leq 2\rho/\sqrt{d}$ then $2\rho B_{1}^{d}\cap sB_{2}^{d}=sB_{2}^{d}$ and

Setting $\eta=c_{0}/(L\sigma)$ and $Q=c_{1}/L^{2}$, it is straightforward to verify that

where $c_{1}$ and $c_{2}$ are constants that depend only on $L$.

When $N\sim d$, $(r_{N}^{*}(Q))^{2}$ decays rapidly from $(\rho^{2}/N)\log(ed/N)$ to . Thus, when $c_{1}d\leq N\leq c_{2}d$ one only has an upper estimate on $(r_{N}^{*}(Q))^{2}$, and we will therefore only consider the cases $N\leq c_{1}d$ and $N\geq c_{2}d$.

Let us present the exact oracle inequalities satisfied by the ERM in $\rho B_{1}^{d}$ that follow from Theorem A. First, assume that $N\leq c_{1}d$. If $\sigma\gtrsim r_{N}^{*}(Q)$ then $\sigma^{2}d^{2}\gtrsim N\rho^{2}$, and

and applying Theorem A, it follows that if $\sigma\geq c_{3}\rho\sqrt{\log(ed/N)/N}$, then with probability at least $1-\delta_{N}$,

and if $\sigma\leq c_{3}\rho\sqrt{\log(ed/N)/N}$, then with probability at least $1-6\exp(-c_{4}N)$,

for constants $c_{3},c_{4},c_{5}$ that depend on $L$.

In a similar fashion, if $N\geq c_{2}d$ then $r_{N}^{*}=0$, and thus, if $\sigma\neq 0$, $\sigma\geq r_{N}^{*}$. Therefore, the error rate of ERM is given by $s_{N}^{*}$. When $\sigma=0$ (the noise-free case) then $s_{N}^{*}(\eta)=r_{N}^{*}(Q)=0$ and with probability larger than $1-6\exp(-c_{4}N)$, $\hat{f}=f^{*}$, implying exact reconstruction.

Turning to the lower estimate, assume that the set of admissible targets contains every Y^{t}=\bigl{<}t,x\bigr{>}+W, for $t\in\rho B_{1}^{d}$ and $W$ that is a centered gaussian random variable with variance $\sigma^{2}$ that is independent of $X$. It follows from Theorem A′′ that if $\sigma\gtrsim r_{N}^{*}(Q)$, ERM is an optimal procedure in the following sense: it achieves the accuracy

if $\rho^{2}N\geq\sigma^{2}\log d$, and the accuracy

if $(\sigma^{2}/\log d)\lesssim\rho^{2}N\leq\sigma^{2}\log d$ (note that when $(\sigma^{2}/\log d)\gtrsim\rho^{2}N$ then $\delta_{N}$ in (4.1) is larger than $1$ and the probability estimate $1-\delta_{N}$ is negative).

For a minimax lower bound that holds with constant probability we shall apply Theorem B. To that end, let us bound the covering numbers $\log N(\rho B_{1}^{d}\cap 2rB_{2}^{d},rB_{2}^{d})$ from below. First note that

and it suffices to study the covering numbers $N(B_{1}^{d}\cap 2rB_{2}^{d},rB_{2}^{d})$ for various choices of $r$.

Fix $1/\sqrt{d}\leq 2r<1$, and without loss of generality assume that $k=1/(2r)^{2}$ is an integer. For $I\subset\{1,...,d\}$, let $S^{I}$ be the Euclidean sphere supported on the coordinates $I$, and note that

Moreover, one can prove (via Maurey’s empirical method) that this estimate is sharp (see, e.g., ). Thus it follows that for any $\rho/\sqrt{d}\leq 2r\leq\rho$,

If $2r\leq\rho/\sqrt{d}$ than $\rho B_{1}^{d}\cap 2rB_{2}^{d}=2rB_{2}^{d}$ and by a volumetric estimate, $\log N(\rho B_{1}^{d}\cap 2rB_{2}^{d},rB_{2}^{d})\sim d$. If, on the other hand, $2\rho>2r\geq\rho$ then $\rho B_{1}^{d}\cap 2rB_{2}^{d}=\rho B_{1}^{d}$ and since $\log N(\rho B_{1}^{d},rB_{2}^{d})\sim\log(edr^{2}/\rho^{2})\sim\log d$ (which is evident from the argument used above), then $\log N(\rho B_{1}^{d}\cap 2rB_{2}^{d},rB_{2}^{d})\sim\log d$. Finally, when $2r\geq 2\rho$, $\log N(\rho B_{1}^{d}\cap 2rB_{2}^{d},rB_{2}^{d})=0$.

We conclude that when $\sigma\gtrsim r_{N}^{*}(Q)$ (and in particular, when $\sigma^{2}d^{2}\gtrsim N\rho^{2}$), and if $\rho^{2}N\geq\sigma^{2}\log d$, then $q_{N}^{*}(c_{0}/\sigma)\sim s_{N}^{*}(\eta)$. This estimate also exhibits that Sudakov’s inequality for the set $\rho B_{1}^{d}\cap 2rB_{2}^{d}$ is sharp at the scale $\varepsilon=r$ in the following sense: for every $0<r<\rho$,

Therefore, by Theorem B, one has that if $\sigma\gtrsim r_{N}^{*}(Q)$ and if the set of admissible targets contains every Y^{t}=\bigl{<}X,t\bigr{>}+W as above, then the minimax rate in the constant confidence regime is $(s_{N}^{*}(\eta))^{2}$ and that ERM is optimal procedure when $\rho^{2}N\geq\sigma^{2}\log d$.

Note that when $\rho^{2}N\leq\sigma^{2}\log d$ the estimates on $(q_{N}^{*}(c_{0}/\sigma))^{2}$ and on $(s_{N}^{*}(\eta))^{2}$ do not coincide. And, it turns out that if one extends the set of admissible targets, ERM cannot perform with a better accuracy than $\sim(s_{N}^{*}(\eta))^{2}$ in this range. Indeed, consider the one dimensional case $d=1$ and a target $Y$ defined as follows: the marginal law of $Y$ given $X$ is

for $\delta$ that will be specified later, and $X$ that is distributed uniformly in $\{-1,1\}$. The corresponding class of one-dimensional linear functionals is ${\mathcal{F}}=\{f_{t}=tx\ :\ -\rho\leq t\leq\rho\}$.

It is straightforward to verify that for every $t\in[-\rho,\rho]$,

and if $2\sigma\delta\geq\rho$ then the minimizer of $R(t)$ in $[-\rho,\rho]$ is $t=\rho$.

Next, let us identify the minimizer of the empirical risk $R_{N}(t)=N^{-1}\sum_{i=1}^{N}(Y_{i}-tX_{i})^{2}$. Given the sample $(X_{i},Y_{i})_{i=1}^{N}$, let $J=\{i:Y_{i}=\sigma X_{i}\}$. Observe that for every $t\in[-\rho,\rho]$,

Thus, when $\sigma\delta\geq\rho$ (i.e., when $\rho^{2}N\lesssim\sigma^{2}$), the best accuracy that ERM can achieve with constant probability is $\sim(s_{N}^{*}(\eta))^{2}$.

Finally, turning to the low noise regime ($\sigma\lesssim r_{N}^{*}(Q)$), one can show that the rate $(r_{N}^{*}(Q))^{2}$ is actually sharp. Recall that by Theorem C it suffices to show that the Gelfand $N$-width of $\rho B_{1}^{d}$ satisfies $c_{N}(\rho B_{1}^{d})\sim r_{N}^{*}$. By a result due to Garanaev and Gluskin , when $d\geq N$ one has

and $c_{N}(\rho B_{1}^{d})=0$ when $d<N$. Therefore, $c_{N}(\rho B_{1}^{d})\sim r_{N}^{*}(Q)$ when either $N\leq c_{1}d$ or $N>c_{2}d$. In particular, when $0\leq\sigma\lesssim r_{N}^{*}(Q)$, the minimax rate is $(r_{N}^{*}(Q))^{2}$ and it is achieved by the ERM.

2 Low-rank matrix inference via the max-norm

In this section, the goal is to estimate the real-valued output $Y$ by a linear function of a low-rank (or approximately low rank) matrix. Since the rank is not a convex constraint, one may consider “a convex relaxation” given by the factorization-based norm

Let ${\mathcal{B}}_{max}$ be the unit ball relative to that norm and set {\mathcal{F}}=\{f_{A}=\bigl{<}\cdot,A\bigr{>}:A\in{\mathcal{B}}_{max}\}. Thus,

Assume that $X$ is isotopic and $L$-subgaussian relative to the normalized Frobenius norm, and in particular,

To apply Theorem A, one has to estimate the fixed points $r_{N}^{*}(Q)$ and $s_{N}^{*}(\eta)$ for $Q$ that depends only on $L$ and $\eta\sim_{L}\sigma^{-1}$.

Let $B_{F}$ be the unit ball relative to the Frobenius norm. Since $X$ is isotropic, the relative $L_{2}$ unit ball is

and the corresponding gaussian process has a covariance structure given by

A simple application of Grothendieck’s inequality (see, e.g., ) shows that

where $K_{G}$ is the Grothendieck constant and ${\mathcal{X}}_{\pm}=\{uv^{\top}:u\in\{\pm 1\}^{p},v\in\{\pm 1\}^{q}\}$; in particular, ${\rm diam}({\mathcal{B}}_{max},L_{2})\sim 1$.

Let $\mathfrak{G}=(g_{ij})_{1\leq i\leq p:1\leq j\leq q}$ be a matrix with independent, centered gaussian entries with variance $(pq)^{-1}$. Thus, for every $s>0$,

By standard properties of gaussian processes,

In the reverse direction, by Lemma 3.1 in , if

Hence, it follows from Sudakov’s inequality that in that range of $s$,

as long as both are smaller than $1$ and larger than $1/\min\{p,q\}$; that is, when $p+q\lesssim N\lesssim pq$, $p+q\lesssim\sigma^{2}N$ and $\sigma^{2}(p+q)\min(p,q)^{2}\gtrsim N$.

Applying Theorem A, if $\sigma\gtrsim_{Q,L}\sqrt{(p+q)/N}$ then with probability at least $1-2\exp(-c_{1}\sqrt{N(p+q)}/\sigma)$, ERM satisfies that

and if $\sigma\lesssim_{Q,L}\sqrt{(p+q)/N}$, then with probability at least $1-2\exp(-c_{1}N)$,

To see that the estimate is sharp in the minimax sense when $\sigma\gtrsim\sqrt{(p+q)/N}$ (and as long as $s_{N}^{*},r_{N}^{*}\lesssim 1$, i.e., $\sigma\lesssim\sqrt{N/(p+q)}$), observe that Theorem A′′ implies that ERM achieves the minimax rate for the confidence parameter $\delta_{N}=\exp(-c_{1}\sqrt{N(p+q)}/\sigma)$. Moreover, by Theorem B and (4.4), any procedure with confidence parameter $\delta_{N}\leq 1/4$ has accuracy $\varepsilon_{N}\gtrsim\sigma\sqrt{\frac{p+q}{N}}$, matching the upper bound.

Concluding remarks

Subgaussian classes are the first family of unbounded classes one is likely to consider, and it turns out that just like bounded classes, the study of subgaussian learning problems may be carried out using a two-sided concentration argument. Unfortunately, this is as far as concentration goes: the substantial technical machinery needed for the proof of Theorem A is not true beyond the subgaussian framework, and the analysis of more ‘heavy-tailed’ problems requires a totally different machinery (see ). Moreover, in more heavy-tailed situations, ERM does not attain the optimal accuracy/confidence tradeoff.

as long as $T$ is convex and centrally-symmetric. No procedure can outperform this rate, say with confidence at least $3/4$ provided that:

Let us mention once again that a complete characterization of the minimax rate in this case was recently established in , and the optimal procedure happens to be a minor modification of ERM: it is ERM performed in an appropriate net in $T$.

The parameter $s_{N}^{*}$ may be compared with the fixed points used in . In all those cases, the fixed points are associated with Dudley’s entropy integral for the localized class, rather than with the localized gaussian process; as such, the resulting bounds are always weaker than ours. For example, the results in which deal with the same situation as Theorem A′′ show that if the noise level is large enough and there is no gap in both Sudakov’s AND Dudley’s inequalities at the correct level (given by the fixed point), ERM is a minimax procedure in expectation. Theorem A′′ clearly improves that result.

Finally, although the importance of convexity may have been obscured by the Bernstein condition, a uniform Bernstein condition implies that the class is convex, at least if a nontrivial error rate is to be expected.

Indeed, observe that if ${\mathcal{F}}\subset L_{2}(\mu)$ is closed but not locally compact in $L_{2}(\mu)$ then the minimax rate of $Y^{f}=f(X)+W$ does not tend to as the sample size tends to infinity. This is an immediate outcome of Theorem B and the fact that there is some $r>0$ and $f\in{\mathcal{F}}$ for which $f+rD$ contains an infinite set that is $r/4$ separated in $L_{2}(\mu)$. Thus, one may restrict oneself to classes that are locally compact, and, in which case, one has the following:

Let $\mu$ be a probability measure and let $X$ be distributed according to $\mu$. If ${\mathcal{F}}$ is a locally compact subset of $L_{2}(\mu)$, the following are equivalent:

Proof. If ${\mathcal{F}}$ is a nonempty, closed and convex subset of a Hilbert space, the metric projection $Y\to f^{*}$ exists and is unique. By its characterization, \bigl{<}f(X)-f^{*}(X),Y-f^{*}(X)\bigr{>}\leq 0 for every $f\in{\mathcal{F}}$, and

In the reverse direction, if ${\mathcal{F}}$ is locally compact, the set-value metric projection onto ${\mathcal{F}}$ exists, and since it is $1$-Bernstein for any $Y$, the metric projection is unique. Indeed, if $f^{*}_{1},f_{2}^{*}\in{\mathcal{F}}$ are minimizers then by the Bernstein condition,

Thus, any $Y\in L_{2}$ has a unique best approximation in ${\mathcal{F}}$, making ${\mathcal{F}}$ a locally compact Chebyshev set in a Hilbert space. By a result due to Vlasov , (see also , Chapter 12), ${\mathcal{F}}$ is convex.

Appendix A Additional proofs

First note that the canonical gaussian process we are interested in is a restriction of the isonormal process on $L_{2}(\mu)$ to a subset (see Section 12 in ). In particular, it inherits the linearity of the isonormal process – a fact we shall use below.

Proof of Lemma 2.3. Fix $s_{1}>s_{2}>0$ and $f,h\in{\mathcal{F}}$. Assume that $s_{2}\leq\|f-h\|_{L_{2}(\mu)}\leq s_{1}$ and observe that since ${\mathcal{F}}-{\mathcal{F}}$ is star-shaped around and $0<s_{2}/\|f-h\|_{L_{2}(\mu)}<1$, it follows that

Since (A.1) clearly holds if $\|f-h\|_{L_{2}(\mu)}\leq s_{2}$, by taking the supremum over all possible choices of $f-h\in s_{1}D\cap({\mathcal{F}}-{\mathcal{F}})$,

which is equivalent to $\psi(s_{1})/s_{1}\leq\psi(s_{2})/s_{2}$; therefore, $\phi$ is non-increasing on $(0,+\infty)$.

The two other parts of the claim can be established using a similar argument and their proofs are omitted.

Proof of Lemma 2.4. First, assume that $\sigma\geq(c/Q)r_{N}^{*}(Q)$. Let $r<r_{N}^{*}(Q)$ and note that by Lemma 2.3,

For the reverse direction, let $\sigma\leq(c/Q)r_{N}^{*}(Q)$ and set $r>r_{N}^{*}(Q)$. Thus, by Lemma 2.3,

Hence, if $Q/r\leq c/\sigma$ then $r\geq s_{N}^{*}(c/\sigma)$. But $Q/r\leq c/\sigma$ if $\sigma\leq(c/Q)r$, which clearly holds.

References