Kullback-Leibler aggregation and misspecified generalized linear models

Introduction

The last decade has witnessed a growing interest in the general problem of aggregation, which turned out to be a flexible way to capture many statistical learning setups. Originally introduced in the regression framework by Nemirovski (2000) and Juditsky and Nemirovski (2000) as an extension of the problem of model selection, aggregation became a mature statistical field with the papers of Tsybakov (2003) and Yang (2004) where optimal rates of aggregation were derived. Subsequent applications to density estimation [Rigollet and Tsybakov (2007)] and classification [Belomestny and Spokoiny (2007)] constitute other illustrations of the generality and versatility of aggregation methods.

The general problem of aggregation can be described as follows. Consider a finite family $\mathcal{H}$ (hereafter called dictionary) of candidates for a certain statistical task. Assume also that the dictionary $\mathcal{H}$ belongs to a certain linear space so that linear combinations of functions in $\mathcal{H}$ remain plausible candidates. Given a subset $\mathcal{C}$ of the linear span $\operatorname{span}(\mathcal{H})$ of $\mathcal{H}$, the goal of aggregation is to mimic the best element of $\mathcal{C}$.

One salient feature of aggregation as opposed to standard statistical modeling is that it does not rely on an underlying model. Indeed, the goal is not to estimate the parameters of an underlying “true” model but rather to construct an estimator that mimics the performance of the best model in a given class, whether this model is true or not. From a statistical analysis standpoint, this difference is significant since performance cannot be measured in terms of parameters: there is no true parameter. Rather, a stochastic optimization point of view is adopted. If $R(\cdot)$ denotes a convex risk function, the goal pursued in aggregation is to construct an aggregate estimator $\hat{h}$ such that

where $\varepsilon$ is a small term that characterizes the performance of the given aggregate $\hat{h}$. As illustrated below, the remainder term $\varepsilon$ is an explicit function of the size $M$ of the dictionary and the sample size $n$ that shows the interplay between these two fundamental parameters. Such oracle inequalities with optimal remainder term $\varepsilon$ were originally derived by Yang (2000) and Catoni (2004) for model selection in the problems of density estimation and Gaussian regression, respectively. They used a method, called progressive mixture, that was later extended to more general stochastic optimization problems in Juditsky, Rigollet and Tsybakov (2008). However, only bounds in expectation have been derived for this estimator and it is argued in Audibert (2008) that this estimator cannot achieve optimal remainder terms with high probability. In the same paper, Audibert suggests a different estimator that satisfies such an oracle inequality with high probability at the cost of large constants in the remainder term. One contribution (Theorem 3.2) of the present paper is to develop a new estimator that enjoys this desirable property with small constants. We also study two other aggregation problems: linear and convex aggregation.

When the model is misspecified, the minimum risk satisfies $\min_{f\in\mathcal{C}}R(f)>0$, and it is therefore important to obtain a leading constant $C=1$ in (1). Many oracle inequalities with leading constant term $C>1$ can be found in the literature for related problems. Yang (2004) derives oracle inequalities with $C>1$ but where the class $\mathcal{C}=\mathcal{C}_{n}$ actually depends on the sample size $n$ so that $\min_{f\in\mathcal{C}_{n}}R(f)$ goes to as $n$ goes to infinity under additional regularity assumptions. In this paper, we focus on the so-called pure aggregation setup as defined by Nemirovski (2000) and Tsybakov (2003) where the class $\mathcal{C}$ is fixed and remains very general. As a result, we are only seeking oracle inequalities that have leading constant $C=1$. Because they hold for finite $M$ and $n$, such oracle inequalities are truly finite sample results.

The pure aggregation framework departs from the original problem of aggregation, where the goal was to achieve adaptation by mimicking the best of given estimators built from an independent sample. Thus a typical aggregation procedure consists in splitting the sample in two parts, using the first part to construct estimators and the second to aggregate them [see, e.g., Lecué (2007), Rigollet and Tsybakov (2007)]. This procedure relies heavily on the fact that the observations are identically distributed, which is not the case in the fixed design regression framework studied in the rest of the paper. It is worth mentioning that in the case of model selection aggregation for Gaussian regression with fixed design, the dictionary can be taken to be a family of projection or even affine estimators built from the same sample. This specific case has been investigated in more detail by Alquier and Lounici (2011), Dalalyan and Salmon (2011), Rigollet and Tsybakov (2011), but is beyond the scope of this paper. Nevertheless, pure aggregation, where the dictionary $\mathcal{H}$ is deterministic, has grown into a field of its own [see, e.g., Bunea, Tsybakov and Wegkamp (2007), Juditsky and Nemirovski (2000), Juditsky, Rigollet and Tsybakov (2008), Lounici (2007), Nemirovski (2000), Tsybakov (2003)]. In the case of regression with fixed design studied in this paper, the dictionary can be thought of as a family of functions with minimal conditions that is expected to have good approximation properties.

Pure aggregation turns out to be a stochastic optimization problem, where the goal is to minimize an unknown risk function $R$ over a certain set $\mathcal{C}$. This paper is devoted to the case where the risk function is given by the Kullback–Leibler divergence, and three constraint sets that were introduced in Nemirovski (2000) are investigated.

We consider an extension of aggregation for Gaussian regression that encompasses distributions for responses in a one-parameter exponential family, with particular focus on the family of Bernoulli distributions in order to cover binary classification. A natural measure of risk in this problem is related to the Kullback–Leibler divergence between the distribution of the actual observations and that of observations generated from a given model. In a way, this extension is close to generalized linear models [see, e.g., McCullagh and Nelder (1989)], which are optimally solved by maximum likelihood estimation [see, e.g., Fahrmeir and Kaufmann (1985)]. However, in the present aggregation framework, it is not assumed that there is one true model but we prove that maximum likelihood estimators still perform almost as well as the optimal solution of a suitable stochastic optimization problem. This generalized framework encompasses logistic regression as a particular case.

The paper is organized as follows. In the next section, we define the problem of Kullback–Leibler aggregation, in the context of misspecified generalized linear models. In particular, we exhibit a natural measure of performance that suggests the use of constrained likelihood maximization to solve it. Exact oracle inequalities, both in expectation and with high probability, are gathered in Section 3 and their optimality for finite $M$ and $n$ is assessed in Section 4. These oracle inequalities for the case of large $M$ are illustrated on a logistic regression problem, similar to the problem of training a boosting algorithm, in Section 5. Finally, Section 6 contains the proofs of the main results together with useful properties on the concentration and the moments of sums of random variables with distribution in an exponential family.

Kullback–Leibler aggregation

Using this inner product, we can also denote the average of a function $f$ by $\langle f,{\mathbh{1}}\rangle$, where ${\mathbh{1}}(\cdot)$ is the function in $Q_{1:n}$ that is identically equal to 1.

A detailed treatment of exponential families of distributions together with examples can be found in Barndorff-Nielsen (1978), Brown (1986), McCullagh and Nelder (1989) and in Lehmann and Casella (1998). Several examples are also presented in Section 5 of the present paper. It can be easily shown that if $Y$ admits a density given by (2), then

We assume hereafter that the distribution of $Y$ is not degenerate so that (3) ensures that $b$ is strictly convex and $b^{\prime}$ is onto its image space.

2 Aggregation and misspecified generalized linear models

The optimal rate of convex aggregation in the Gaussian case is $(M/n)\wedge\sqrt{\log(1+M/\sqrt{n})/n}$. In practice, the regression function $f$ is unknown and it is impossible to perfectly solve (5). Our goal is therefore to recover an approximate solution of this problem in the following sense. We wish to construct an estimator $\hat{\lambda}_{n}$ such that

is as small as possible. An inequality that provides an upper bound on the (random) quantity in (7) in a certain probabilistic sense is called oracle inequality.

The notion of Kullback–Leibler aggregation defined in the next subsection broadens the scope of the above problem of aggregation to encompass other distributions for $Y$.

3 Kullback–Leibler aggregation

Recall that the ubiquitous squared norm $\|\cdot\|^{2}$ as a measure of performance for regression problems takes its roots in the Gaussian regression model. The Kullback–Leibler divergence between two probability distributions $P$ and $Q$ is defined by

Denote by $P_{f}$ the joint distribution of the observations $Y_{i},i=1,\ldots,n$. If $P_{f}$ denotes an $n$-variate Gaussian distribution with mean $(f(x_{1}),\ldots,f(x_{n}))^{\top}$ and variance $\sigma^{2}I_{n}$, where $I_{n}$ denotes the $n\times n$ identity matrix, then $\mathcal{K}(P_{f}\|\allowbreak P_{g})=\frac{n}{2\sigma^{2}}\|f-g\|^{2}$. In order to allow an easier comparison between the results of this paper and the literature, consider a normalized Kullback–Leibler divergence defined by $\bar{\mathcal{K}}(P_{f}\|P_{g})=\mathcal{K}(P_{f}\|P_{g})/n$. In the Gaussian regression setup, the quantity of interest in (7) can be written

up to a multiplicative constant term equal to $2\sigma^{2}$. Nevertheless, the quantity in (8) is meaningful for other distributions in the exponential family.

Whereas KL-aggregation is a purely finite sample problem, it bears connections with the asymptotic theory of model misspecification as defined in White (1982), following LeCam (1953) and Akaike (1973). White (1982) proves that if the regression function $f$ is not of the form $f=b^{\prime}\circ\mathsf{h}_{\lambda}$ for some $\lambda$ in the set of parameters $\Lambda$, then under some identifiability and regularity conditions, the maximum likelihood estimator converges to $\lambda^{*}$ defined by

Upper bounds on the excess-KL can be interpreted as finite sample versions of those original results.

Note that assuming that $Y_{i}$ admits a density of the form (2) with known cumulant function $b(\cdot)$ is a strong assumption unless $Y_{i}$ has Bernoulli distribution, in which case identification of this distribution is trivial from the context of the statistical experiment. We emphasize here that model misspecification pertains only to the systematic component.

Main results

where ${\operatorname{Ent}}(P_{f})$ denotes the entropy of $P_{f}$ and is defined by

For estimators of the form $\hat{\theta}_{i}=\mathsf{h}_{\lambda}(x_{i})$, maximizing the log-likelihood is equivalent to maximizing

over a certain set $\Lambda$ that depends on the problem at hand.

We now give bounds for the problem of KL-aggregation for the choices of $\Lambda$ corresponding to the three problems of aggregation introduced in the previous section. All proofs are gathered in Section 6 and rely on the following conditions, which can be easily checked given the cumulant function $b$.

We say that the couple $(\mathcal{H},\Lambda)$ satisfies Condition 2 if there exists a positive constant $\kappa^{2}$ such that

uniformly for all $x\in\mathcal{X}$ and all $\lambda\in\Lambda$.

Conditions 1 and 2 are discussed in the light of several examples in Section 5. Condition 1 is used only to ensure that the distributions of $Y_{i}$ have uniformly bounded variances and sub-Gaussian tails, whereas Condition 2 is a strong convexity condition that depends not only on the cumulant function $b$ but also on the aggregation problem at hand that is characterized by the couple $(\mathcal{H},\Lambda)$.

Note that the criterion maximized in the above equation is the sum of the log-likelihood and a linear interpolation of the values of the log-likelihood at the vertices of the flat simplex. As argued above, both of these terms are needed. Indeed, using only the linear interpolation would lead us to choose $\hat{\lambda}$ to be one of the vertices of the simplex which, as mentioned above, is a suboptimal choice.

The proofs of both theorems are gathered in Section 6.2.

2 Linear aggregation

are convex coercive. Thus, the aggregates $\mathsf{h}_{\lambda^{*}}$ and $\mathsf{h}_{\hat{\lambda}_{n}}$ are uniquely defined as functions in the quotient space $Q_{1:n}$, even though $\lambda^{*}$ and $\hat{\lambda}_{n}$ may not be unique.

where $D\leq M$ is the dimension of $\operatorname{span}(\mathcal{H})$ and $\lambda^{*}\in\mathop{\arg\min}_{\lambda\in\Lambda}\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$.

Theorem 3.3 is valid in expectation. The following theorem shows that these bounds are not only valid in expectation but also with high probability.

where $\lambda^{*}\in\mathop{\arg\min}_{\lambda\in\Lambda}\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$.

We see that the price to pay to obtain bounds with high probability is essentially the same as for the bounds in expectation up to an extra multiplicative term of order $\log(1/\delta)$.

3 Convex aggregation

In this subsection, we assume that $\Lambda\subset\Lambda_{1}^{+}$ is a closed convex set. Note that both a maximum likelihood estimator $\hat{\lambda}_{n}$ and an oracle $\lambda^{*}\in\mathop{\arg\min}_{\lambda\in\Lambda}\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$ exist.

Recall that if $(\mathcal{H},\Lambda)$ satisfies Condition 2, Theorems 3.3 and 3.4 also hold. The following theorems ensure a better rate for the maximum likelihood aggregate $\mathsf{h}_{\hat{\lambda}_{n}}$ over $\Lambda$ when $D$, and thus $M$, becomes much larger than $n$. It extends the problem of convex aggregation defined by Nemirovski (2000), Juditsky and Nemirovski (2000) and Tsybakov (2003) to the case where the distribution of the response variables is not restricted to be Gaussian.

Let $\Lambda$ be any closed convex subset of the flat simplex $\Lambda_{1}^{+}$ defined in (6). Let Condition 1 hold and assume that the dictionary $\mathcal{H}$ consists of functions satisfying $\|h_{j}\|\leq R$, for any $j=1,\ldots,M$ and some $R>0$. Then, the maximum likelihood aggregate $\mathsf{h}_{\hat{\lambda}_{n}}$ over $\Lambda$ satisfies

Moreover, if $(\mathcal{H},\Lambda)$ satisfies Condition 2, then

where $\lambda^{*}\in\mathop{\arg\min}_{\lambda\in\Lambda}\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$.

The bounds of Theorem 3.5 also have a counterpart with high probability as shown in the next theorem.

Let $\Lambda$ be any closed convex subset of the flat simplex $\Lambda_{1}^{+}$ defined in (6). Fix $M\geq 3$, let Condition 1 hold and assume that the dictionary $\mathcal{H}$ consists of functions satisfying $\|h_{j}\|\leq R$, for any $j=1,\ldots,M$ and some $R>0$. Then, for any $\delta>0$, with probability $1-\delta$, the maximum likelihood aggregate $\mathsf{h}_{\hat{\lambda}_{n}}$ over $\Lambda$ satisfies

Moreover, if $(\mathcal{H},\Lambda)$ satisfies Condition 2, then on the same event of probability $1-\delta$, it holds

where $\lambda^{*}\in\mathop{\arg\min}_{\lambda\in\Lambda}\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$.

Most of the existing bounds for convex aggregation hold for the expected excess-KL. Many papers provide bounds with high probability [see, e.g., Koltchinskii (2011), Massart (2007), Mitchell and van de Geer (2009) and references therein] but they typically do not hold for the excess-KL itself but for a quantity related to

where $C>1$ is a constant. When the quantity $\min_{\lambda\in\Lambda}\bar{\mathcal{K}}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$ is not small enough, such bounds can become uninformative. A notable exception is Nemirovski et al. [(2008), Proposition 2.2] where the authors derive a result similar to Theorem 3.6 under a different but similar set of assumptions. Most importantly, their bounds do not hold for the maximum likelihood estimator but for the output of a recursive stochastic optimization algorithm.

4 Discussion

As mentioned before, it is worth noticing that the technique employed in proving the bounds in expectation of the previous subsection yield bounds with high probability at almost no extra cost.

Optimal rates of aggregation

For linear and model selection aggregation, these rates are known to be optimal in the Gaussian case where the design is random but with known distribution [Tsybakov (2003)] and where the design is deterministic [Rigollet and Tsybakov (2011)]. For convex aggregation, it has been established by Tsybakov (2003) [see also Rigollet and Tsybakov (2011)] that the optimal rate for Gaussian regression is of order $\sqrt{\log(1+eM/\sqrt{n})/n}$, which is equivalent to the upper bounds obtained in Theorems 3.5–3.6 of the present paper when $M\gg\sqrt{n}$ but is smaller in general. To obtain better upper bounds, one may resort to more complicated, combinatorial procedures such as the ones derived in the papers cited above but the full description of this idea goes beyond the scope of this paper. Note that in the case of bounded regression with quadratic risk and random design, Lecué (2012) recently proved that the constrained empirical risk minimizer attains the optimal rate $\sqrt{\log(1+eM/\sqrt{n})/n}$ without any modification.

In this section, we prove that these rates are minimax optimal under weaker conditions that are also satisfied by the Bernoulli distribution. The notion of optimality for aggregation employed here is a natural extension of the one introduced by Tsybakov (2003). Before stating the main result of this section, we need to introduce the following definition. Fix $\kappa^{2}>0$ and let $\Gamma(\kappa^{2})$ be the level set of the function $b^{\prime\prime}$ defined by

To state the minimax lower bounds properly, we use the notation

that makes the dependence in the regression function $f$ explicit. Finally, we denote by $E_{f}$ the expectation with respect to the distribution $P_{f}$.

where the infimum is taken over all estimators and where

This theorem covers the Gaussian and the Bernoulli case for which Condition 1 is satisfied. Lower bounds for aggregation in the Gaussian case have already been proved in Rigollet and Tsybakov [(2011), Section 6] in a weaker sense. Indeed, we enforce here that $\mathcal{H}\in\bar{\mathcal{D}}$ and has rank bounded by $D$, whereas Rigollet and Tsybakov (2011) use unbounded dictionaries with rank that may exceed $D$ by a logarithmic multiplicative factor.

Observe that from (26), the least favorable regression functions are of the form $f=b^{\prime}\circ\mathsf{h}_{\lambda},\lambda\in\Lambda$, as it is the case for Gaussian aggregation [see, e.g., Tsybakov (2003)].

A consequence of Theorem 4.1 is that the rates of convergence obtained in Section 3, both in expectation and with high probability, cannot be improved without further assumptions except for the logarithmic term of convex aggregation. The proof of Theorem 4.1 is provided in the supplementary material [Rigollet (2012)].

Examples

Observe first that only the Normal and Bernoulli distributions satisfy Condition 1. Indeed, all other distributions in the table do not have sub-Gaussian tails and therefore, we cannot use Lemma 6.1 to control the deviations and moments of the sum of independent random variables. Therefore, only Theorem 3.3 applies to the remaining distributions even though direct computation of the moments can yield results of the same type as Theorems 3.5 and 3.6 but with bounds that are larger by orders of magnitude.

Another important message of Table 1 is that the constant $\kappa^{2}$ can depend on the constant $H_{\infty}$ defined in (24). Consequently the $L_{2}$ distance $\|\mathsf{h}_{\hat{\lambda}_{n}}-\mathsf{h}_{\lambda^{*}}\|^{2}$ is affected by the constant $\kappa^{2}$ and thus by $H_{\infty}$. However, the constant $B^{2}$ does not depend on $H_{\infty}$. Therefore, the bounds on the excess-KL presented in Theorems 3.5 and 3.6 hold without extra assumption of the dictionary. For the Normal distribution, $\kappa^{2}=B^{2}=1$ regardless of the value $H_{\infty}$, which makes it a particular case.

2 Bounds for logistic regression with a large dictionary

Let us now focus on the Bernoulli distribution. Recall that in the setup of binary classification, we observe a collection of independent random couples $(x_{1},Y_{1}),\ldots,\allowbreak(x_{n},Y_{n})$ such that $Y_{i}\in\{0,1\}$ has Bernoulli distribution with parameter $f(x_{i})$, $i=1,\ldots,n$. As shown in the survey by Boucheron, Bousquet and Lugosi (2005), there exists a tremendous amount of work in this topic and we will focus on the so-called boosting type algorithms. A dictionary of base classifiers $\mathcal{H}=\{h_{1},\ldots,h_{M}\}$, that is, functions taking values in $$, is given and training a boosting algorithm consists in combining them in such a way that$\mathsf{h}_{\lambda}(x_{i})$predicts$f(x_{i})$ well.

up to the normalizing constant $\log 2$ that appears to ensure that $\varphi(0)=1$. For the choice of $\varphi$ defined in (28), we have

In boosting algorithms, the size of the dictionary $M$ is much larger than the sample size $n$ so that the results of Theorems 3.3 and 3.4 are useless and it is necessary to constrain $\lambda$ to be in the rescaled flat simplex $R\Lambda_{1}^{+}$ so that $H_{\infty}=R$. Given that for the Bernoulli distribution, we have $a=1,B^{2}=1/4$, the constants in the main theorems can be explicitly computed and in fact, they remain low. We can therefore apply Theorems 3.5 and 3.6 to obtain the following corollary that gives oracle inequalities for the $\varphi$-risk $R_{\varphi}$, both in expectation and with high probability. We focus on the case where $M$ is (much) larger than $n$ as it is usually the case in boosting.

Consider the boosting problem with a given dictionary of base classifiers and let $\varphi$ be the convex function defined in (28). Then, the maximum likelihood aggregate $\mathsf{h}_{\hat{\lambda}_{n}}$ over the rescaled flat simplex $R\Lambda_{1}^{+}$, $R>0$, defined in (16) satisfies

Moreover, for any $\delta>0$, with probability $1-\delta$, it holds

Proof of the main results

It can be easily shown [see, e.g., Lehmann and Casella (1998), Theorem 5.10] that the moment generating function of $Y$ is given by

Using (30) we can derive the Chernoff-type bounds presented in the following lemma.

where $C_{r}=r(2aB^{2})^{r/2}\Gamma(r/2)$ and $\Gamma(\cdot)$ denotes the Gamma function.

Using, respectively, (30), (3) and (12), we get

The same inequality holds with $s$ replaced by $-s$ so (31) holds.

The proof of (32) follows from (31) together with a Chernoff bound. Next, note that

where we used (32) in the last inequality. Using a change of variable, it is not hard to see that this bound yields (33).

2 Proof of Theorems 3.1 and 3.2

According to (10), minimizing $\lambda\mapsto\mathcal{K}(P_{f}\|P_{b^{\prime}\circ\mathsf{h}_{\lambda}})$ is equivalent to maximizing $\lambda\mapsto L(\lambda)$ where

Moreover, for any $\lambda\in\Lambda,\lambda^{*}\in\Lambda^{*}$, we have

For any fixed $\lambda\in\Lambda_{1}^{+}$, define the following quantities:

Let $\beta>0$ be a parameter to be chosen later. By definition of $\hat{\lambda}$, we have for any $\lambda\in\Lambda_{1}^{+}$ that

where $\Delta_{n}(\lambda)=2\sum_{i=1}^{n}(Y_{i}-f(x_{i}))\mathsf{h}_{\hat{\lambda}-\lambda}(x_{i})-\beta\log M$. The following lemma is useful to control the term $\Delta_{n}(\lambda)$ both in expectation and with high probability.

Under Condition 1, for any $\lambda\in\Lambda_{1}^{+}$ we have

For any $\lambda\in\Lambda_{1}^{+}$, $j=1,\ldots,M$, define $\Upsilon_{j}$ by

Jensen’s inequality and the fact that $\log M=\sum_{j=1}^{M}\hat{\lambda}_{j}(\log M)$ yield

Now, from (31), which holds under Condition 1, we have for any $\lambda\in\Lambda_{1}^{+}$, $j=1,\ldots,M$, that

and the result of the lemma follows from the previous two displays.

Take any $\bar{\lambda}\in\mathop{\arg\max}_{\lambda\in\Lambda_{1}^{+}}S(\lambda)$ and observe that Condition 2 together with a second-order Taylor expansion of the function $S(\cdot)$ around $\bar{\lambda}$ gives for any $\lambda\in\Lambda_{1}^{+}$

where $\nabla_{\lambda}S({\bar{\lambda}})$ denotes the gradient of $\lambda\mapsto S(\lambda)$ at $\bar{\lambda}$. Since $\bar{\lambda}$ is a maximizer of $\lambda\mapsto S(\lambda)$ over the set $\Lambda_{1}^{+}$ to which $\lambda$ also belongs, we find that $\nabla_{\lambda}S({\bar{\lambda}})^{\top}(\lambda-\bar{\lambda})\leq 0$ so that, together with (36), the previous display yields

The previous display combined with (37) gives

It implies that for $\beta\geq 8B^{2}a/\kappa^{2}$

Observe now that a second-order Taylor expansion of the function $L(\cdot)$ around $\hat{\lambda}$, together with Condition 2, gives for any $\lambda\in\Lambda_{1}^{+}$

Combined with (38), the above inequality yields

for $\beta\geq 8B^{2}a/\kappa^{2}$. Note that for any $j=1,\ldots,M$, $S({\bar{\lambda}})\geq S(e_{j})=2nL(e_{j})$ so that from (35), we get

Proof of Theorem 3.2 From Lemma 6.2 and a Chernoff bound, we get for any $\lambda\in\Lambda_{1}^{+}$ and any $\delta>0$ that

Thus, the event $\mathcal{A}_{\lambda}(\delta)=\{\Delta_{n}(\lambda)\leq\frac{2B^{2}an}{\beta}\sum_{j=1}^{M}\hat{\lambda}_{j}\|h_{j}-\mathsf{h}_{\lambda}\|^{2}+\beta\log(1/\delta)\}$ has probability greater than $1-\delta$. Theorem 3.2 follows by applying the same steps as in the proof of Theorem 3.1 but on the event $\mathcal{A}_{\bar{\lambda}}(\delta)$ instead of in expectation.

3 Proofs of Theorems 3.3–3.6

The following lemma exploits the strong convexity property stated in Condition 2.

where $\zeta_{j}=\frac{1}{n}\sum_{i=1}^{n}Y_{i}\phi_{j}(x_{i})-\langle f,\phi_{j}\rangle,j=1,\ldots,D$. Moreover, if $\Lambda\subset\Lambda_{1}^{+}$ is a closed convex set, then ${\hat{\lambda}_{n}}$ satisfies

where $\xi_{j}=\frac{1}{n}\sum_{i=1}^{n}Y_{i}h_{j}(x_{i})-\langle f,h_{j}\rangle,j=1,\ldots,M$.

A second-order Taylor expansion of the function $L(\cdot)$ around $\lambda^{*}$ gives for any $\lambda\in\Lambda$

where we used Condition 2 and where $\nabla_{\lambda}L({\lambda^{*}})$ denotes the gradient of $\lambda\mapsto L(\lambda)$ at $\lambda^{*}$. Since $\lambda^{*}$ is a maximizer of $\lambda\mapsto L(\lambda)$ over the set $\Lambda$ to which $\lambda$ also belongs, we find that $\nabla_{\lambda}L({\lambda^{*}})^{\top}(\lambda-\lambda^{*})\leq 0$ so that

for any $\lambda\in\Lambda$, which gives the left inequalities in (39) and (40).

Next, from the definition of $\hat{\lambda}_{n}$, we have

Since $T_{n}(\lambda^{*}-\hat{\lambda}_{n})\geq-V_{n}\|\mathsf{h}_{\lambda^{*}-\hat{\lambda}_{n}}\|$, it yields together with (42) that

Combining (43) and (41) with $\lambda=\hat{\lambda}_{n}$, we get (39).

We now turn to the proof of (40). From (42), and the Hölder inequality, we have

Combined with (41), this inequality yields (40).

In view of (35), to complete the proof of Theorems 3.3–3.6, it is sufficient to bound from above the quantities appearing on the right-hand side of (39) and (40). This is done using results from Section 6.1 and by observing that the random variables $\zeta_{j}$ and $\xi_{j}$ are of the form

if $\max_{1\leq j\leq M}\|h_{j}\|\leq R$. {pf*}Proof of Theorem 3.3 Since the random variables $Y_{i},i=1,\ldots,n$, are mutually independent, we have

Together with (35) and (39), this bound completes the proof of Theorem 3.3. {pf*}Proof of Theorem 3.4 For any $s,t>0$, we have

where we used, respectively: the Markov inequality, the Jensen inequality and Fatou’s lemma. Observe now that (33), which holds under Condition 1, and (44) yield

Therefore, the last two displays with $s=n/(4aB^{2})$ yield

Theorem 3.4 follows by taking $t=\frac{4aB^{2}D}{n}\log(4/\delta)$ in the previous display together with (35) and (39).

Before completing the proof of Theorems 3.5 and 3.6, observe that (31) and (45) imply that for any $j=1,\ldots,M$, the random variable $|\xi_{j}|$ is sub-Gaussian with variance proxy $\sigma^{2}=(RB)^{2}a/n$, that is,

Proof of Theorem 3.5 It follows from Lemma 2.3 in Massart (2007) with the above choice of variance proxy that

Combined with (35) and (40) the previous inequality completes the proof of Theorem 3.5. {pf*}Proof of Theorem 3.6 Using, respectively, a union bound, a Chernoff bound and (46), we find

Together with (35) and (40), this bound completes the proof of Theorem 3.6 by taking $t=RB\sqrt{\frac{2a\log(M/\delta)}{n}}$.

Acknowledgments

The author would like to thank Ramon van Handel, Guillaume Lecué and Vivian Viallon for helpful comments and suggestions.

Minimax lower bounds \slink[doi]10.1214/11-AOS961SUPP \sdatatype.pdf \sfilenameaos961_supp.pdf \sdescriptionUnder some convexity and tail conditions, we prove minimax lower bounds for the three problems of Kullback–Leibler aggregation: model selection, linear and convex. The proof consists in three steps: first, we identify a subset of admissible estimators, then we reduce the problem to a usual problem of regression function estimation under the mean squared error criterion and finally, we use standard minimax lower bounds to complete the proof.

References