Sharp oracle bounds for monotone and convex regression through aggregation

Introduction

We will measure the error of an estimator $\boldsymbol{\hat{\mu}}$ of $\boldsymbol{\mu}$ by the distance $\|\boldsymbol{\hat{\mu}}-\boldsymbol{\mu}\|$. Let $\mathcal{S}^{\uparrow}$ be the set of all non-decreasing sequences:

A well-studied estimator under the monotonicity and convexity assumptions is the least squares estimator

In Nemirovski et al. 1985 it was shown that $\boldsymbol{\hat{\mu}}^{LS}({\cal S})$ attains, up to logarithmic factors, the rates $n^{-2/3}$ and $n^{-4/5}$ of the mean squared risk for classes ${\cal S}$ of monotone and convex functions respectively and that these rates are optimal up to logarithmic factors when the minimax squared risk is used as a criterion. Under monotonicity constraints, the rate $n^{-2/3}$ was later observed in different settings, see for instance Banerjee and Wellner 2001; Balabdaoui and Wellner 2007.

One class of monotone functions we will be interested in here is defined as

where $V(\boldsymbol{\mu})=\mu_{n}-\mu_{1}$ for any $\boldsymbol{\mu}=(\mu_{1},\dots,\mu_{n})\in\mathcal{S}^{\uparrow}$, and $V>0$ is a given constant. In Meyer and Woodroofe 2000; Zhang 2002 it was shown that for any $\boldsymbol{\mu}\in\mathcal{S}^{\uparrow}$ we have

for $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{LS}(\mathcal{S}^{\uparrow})$ and some absolute constant $c>0$. This immediately implies an upper bound on the minimax risk on $\mathcal{S}^{\uparrow}(V)$. A recent paper Chatterjee et al. 2015 establishes the oracle inequality

valid for all $\boldsymbol{\mu}\in\mathcal{S}^{\uparrow}$ where either $C_{*}=6,c_{*}=1$ (Chatterjee et al. 2015, inequality (18)) or $C_{*}=4,c_{*}=4$ (Chatterjee et al. 2015, inequality (30)). Here, $k(\boldsymbol{u})\geq 1$ for $\boldsymbol{u}=(u_{1},\dots,u_{n})\in\mathcal{S}^{\uparrow}$ is the integer such that $k(\boldsymbol{u})-1$ is the number of inequalities $u_{i}\leq u_{i+1}$ that are strict for $i=1,\dots,n-1$ (number of jumps of $\boldsymbol{u}$). Inequality (1.6) implies (up to a logarithmic factor) a bound as in (1.5) and also gives some more insight into the problem. For example, (1.6) shows that the fast rate $\frac{\log n}{n}$ is achieved if $\boldsymbol{\mu}$ has only one jump or a fixed, independent of $n$, number of jumps. This is not granted by (1.5).

Along with the least squares estimator, one may consider estimation of monotone functions via penalized least squares with total variation penalty. The corresponding estimator $\boldsymbol{\hat{\mu}}^{TV}$ is defined as

where $\lambda>0$ is a tuning parameter. Statistical properties of this estimator were first studied in Mammen and van de Geer 1997 where it was shown that $\|\boldsymbol{\hat{\mu}}^{TV}-\boldsymbol{\mu}\|$ attains the optimal rate $n^{-1/3}$ in probability on the class of functions of bounded variation (and thus on $\mathcal{S}^{\uparrow}(V)$). Recently, the performance of $\boldsymbol{\hat{\mu}}^{TV}$ was analyzed in Dalalyan et al. 2014 by considering $\boldsymbol{\hat{\mu}}^{TV}$ as a special instance of the Lasso estimator. If $\boldsymbol{\mu}^{\uparrow}$ is the projection of $\boldsymbol{\mu}$ onto $\mathcal{S}^{\uparrow}$, $\delta\in(0,1)$ is a constant, and the tuning parameter $\lambda$ is given by

the estimator $\boldsymbol{\hat{\mu}}^{TV}$ satisfies with probability greater than $1-2\delta$ the following oracle inequality (Dalalyan et al. 2014, Proposition 6):

The expressions on the right hand sides of (1.6) and (1.10) are small if the unknown sequence $\boldsymbol{\mu}$ is well approximated by a piecewise constant sequence with not too many pieces. In this regard, the two bounds have some similarity to sparsity oracle inequalities in high-dimensional linear regression, cf. Rigollet and Tsybakov 2011; Rigollet and Tsybakov 2012; Tsybakov 2014. This similarity can be easily explained as follows. Write (1.1) in the equivalent form

Sparsity pattern aggregation for piecewise constant sequences

For any non-empty set $J\subseteq\{1,...,n-1\}$, let $|J|$ denote the cardinality of $J$ and define

where ${\boldsymbol{\hat{\theta}}}$ is the solution of the optimization problem

This optimization problem is a convex quadratic program with a simplex constraint. It performs aggregation of the linear estimators $(P_{J}\mathbf{y})_{J\subseteq\{1,...,n-1\}}$ using the $Q$-aggregation procedure Dai et al. 2012; Dai et al. 2014; Bellec 2014 with the prior weights (2.1). As the size of this quadratic program is of order $2^{n}$, it is a computationally hard problem. The estimator $\boldsymbol{\hat{\mu}}^{Q}$ satisfies the following sharp oracle inequalities.

Let $J\subseteq\{1,...,n-1\}$. Denote by $d=|J|+1$ the dimension of the subspace $V_{J}$. Then, the projection estimator $P_{J}\mathbf{y}$ satisfies with probability at least $1-\delta$ (see, for example, Hsu et al. 2012):

The sharp oracle inequality from Bellec 2014 yields that with probability at least $1-2\delta$ for all $J\subseteq\{1,...,n-1\}$ we have

for some absolute constant $C>0$. Combining (2.7) and (2.8) with the union bound and the inequality (cf. (Rigollet and Tsybakov 2012, (5.4))) $\log(1/\pi_{J})\leq 2(|J|+1)\log(en/(|J|+1))+1/2$, we find that with probability at least $1-3\delta$,

We now discuss some corollaries of Theorem 1. First, it follows that (1.11) is satisfied for $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{Q}$, so the remarks after (1.11) apply. Next, in view of (2.6), for the class of monotone sequences with at most $k$ jumps $\mathcal{S}^{\uparrow}_{k}=\{\boldsymbol{u}\in\mathcal{S}^{\uparrow}:k(\boldsymbol{u})\leq k\}$ we have the following bounds for the maximal expected regrets

where $c>0$ is an absolute constant. The same bounds hold for the minimax risks over $\mathcal{S}^{\uparrow}_{k}$ since the minimax risk is smaller than the minimax regret. Proposition 4 below shows that the bounds (2.9) and (2.10) are optimal up to logarithmic factors.

Finally, consider the consequences of Theorem 1 for the class $\mathcal{S}^{\uparrow}(V)$. To this end, define the integer $k^{*}$ such that

Let $\boldsymbol{\mu}\in\mathcal{S}^{\uparrow}$ and let $1\leq k\leq n$ be an integer. Then there exists a sequence $\bar{\boldsymbol{u}}\in\mathcal{S}^{\uparrow}_{k}$ such that

Next, there exists a sequence $\bar{\boldsymbol{u}}\in\mathcal{S}^{\uparrow}_{k^{*}}$ such that

To construct the sequence $\bar{\boldsymbol{u}}$, consider the $k$ intervals

and $I_{k}=[\mu_{1}+\frac{k-1}{k}V(\boldsymbol{\mu}),\mu_{n}]$. For all $j=1,...,k$, let

For any $i\in\{1,...,n\}$ there exists a unique $j\in\{1,...,k\}$ such that $i\in I_{j}$. Let $\bar{u}_{i}=\mu_{1}+\frac{j-1/2}{k}V(\boldsymbol{\mu})$ for all $i\in I_{j}$. Then the sequence $\bar{\boldsymbol{u}}=(\bar{u}_{1},\dots,\bar{u}_{n})$ is non-decreasing, it has at most $k$ pieces, i.e., $k(\bar{\boldsymbol{u}})\leq k$, and $|\bar{u}_{i}-\mu_{i}|\leq\frac{V(\boldsymbol{\mu})}{2k}$ for $i=1,...,n$. Thus (2.11) follows. Next, note that if $k^{*}=1$, then $V(\boldsymbol{\mu})^{2}\leq\sigma^{2}\log(en)/n$. If $k^{*}>1$, then by definition of $k^{*}$, $V(\boldsymbol{\mu})^{2}/(k^{*})^{2}\leq(\sigma^{2}V(\boldsymbol{\mu})\log(en)/n)^{2/3}$. Thus, (2.12) follows. The bound (2.13) is straightforward by studying the cases $k^{*}=1$ and $k^{*}>1$ separately. ∎

We can now derive the following corollary of Theorem 1.

Under the assumptions of Theorem 1, there exists an absolute constant $c>0$ such that, for any $\boldsymbol{\mu}\in\mathcal{S}^{\uparrow}$,

From (2.6) and the fact that the function $x\mapsto x\log\left(\frac{en}{x}\right)$ is increasing for $1\leq x\leq n$ we get

for an absolute constant $c^{\prime\prime}>0$ where the last inequality follows from (2.12) and (2.13). ∎

Finally, the following result shows that the upper bounds (2.9) and (2.10) are optimal up to logarithmic factors.

Let $n\geq 2,V>0\text{ and }\sigma>0$. There exist absolute constants $c,c^{\prime}>0$ such that for any positive integer $k\leq n$ satisfying $k^{3}\leq 16nV^{2}/\sigma^{2}$ we have

For $k=1,...,n$, take any $V>0$ large enough to satisfy $k^{3}\leq 16nV^{2}/\sigma^{2}$. Then, Proposition 4 and Markov’s inequality yield the following lower bounds on the minimax risks over the class $\mathcal{S}^{\uparrow}_{k}$:

As the minimax risk is smaller than the minimax regret, (2.19) also provides lower bounds for the corresponding minimax regrets over $\mathcal{S}^{\uparrow}_{k}$. Combining this with (2.9) and (2.10) we find that the estimator $\boldsymbol{\hat{\mu}}^{Q}$ achieves up to logarithmic factors the optimal rate with respect to the minimax regret.

Next, Proposition 4 implies the following lower bound on the minimax deviation risk on $\mathcal{S}^{\uparrow}(V)$.

Let $n\geq 2,V>0\text{ and }\sigma>0$. There exist absolute constants $c,c^{\prime}>0$ such that

To prove this corollary it is enough to note that if $16nV^{2}/\sigma^{2}\geq 1$, by choosing $k$ in Proposition 4 as the integer part of $(16nV^{2}/\sigma^{2})^{1/3}$, we obtain the lower bound corresponding to $\left(\frac{\sigma^{2}V}{n}\right)^{2/3}$ under the maximum in (2.20). On the other hand, if $16nV^{2}/\sigma^{2}<1$ the term $\frac{\sigma^{2}}{n}$ is dominant, so that we need to have the lower bound of the order $\frac{\sigma^{2}}{n}$, which is trivial (it follows from a reduction to the bound for the class composed of two constant functions).

It follows from (2.20) and (2.16) that the estimator $\boldsymbol{\hat{\mu}}^{Q}$ achieves, up to logarithmic factors, the optimal rate with respect to the minimax risk on the class $\mathcal{S}^{\uparrow}(V)$. Using (2.17) and the fact that the minimax risk is smaller than the minimax regret, we conclude that it is also the optimal rate up to logarithmic factors for the minimax regret.

We assume for simplicity that $n$ is a multiple of $k$. The general case is treated analogously. For any ${\boldsymbol{\omega}},{\boldsymbol{\omega}}^{\prime}\in\{0,1\}^{k}$, let $d_{H}({\boldsymbol{\omega}},{\boldsymbol{\omega}}^{\prime})=|\{i=1,...,k:\omega_{i}\neq\omega_{i}^{\prime}\}|$ be the Hamming distance between ${\boldsymbol{\omega}}$ and ${\boldsymbol{\omega}}^{\prime}$. By the Varshamov-Gilbert bound (Tsybakov 2009, Lemma 2.9), there exists a set $\Omega\subset\{0,1\}^{k}$ such that

where $\gamma=(1/8)\sqrt{\sigma^{2}k/n}$, and $\lfloor x\rfloor$ denotes the maximal integer smaller than $x$. For any ${\boldsymbol{\omega}}\in\Omega$, $\boldsymbol{u}^{\boldsymbol{\omega}}$ is a piecewise constant sequence with $k(\boldsymbol{u}^{\boldsymbol{\omega}})\leq k$, $\boldsymbol{u}^{\boldsymbol{\omega}}$ is a non-decreasing sequence because $\gamma\leq V/(2k)$, and by construction $V(\boldsymbol{u}^{\boldsymbol{\omega}})\leq V$. Thus, $\boldsymbol{u}^{\boldsymbol{\omega}}\in\mathcal{S}^{\uparrow}_{k}\cap\mathcal{S}^{\uparrow}(V)$ for all ${\boldsymbol{\omega}}\in\Omega$. Moreover, for any ${\boldsymbol{\omega}},{\boldsymbol{\omega}}^{\prime}\in\Omega$,

Applying (Tsybakov 2009, Theorem 2.7) with $\alpha=1/16$ completes the proof. ∎

Estimation of convex sequences by aggregation

Assume that $n\geq 3$ and define the set of convex sequences $\mathcal{S}^{\rm C}$ as follows:

The performance of the least squares estimator over convex sequences $\boldsymbol{\hat{\mu}}^{LS}(\mathcal{S}^{\rm C})$ has been recently studied in Guntuboyina and Sen 2013. If the unknown vector $\boldsymbol{\mu}$ belongs to the set $\mathcal{S}^{\rm C}$, Guntuboyina and Sen 2013 shows that the estimator $\boldsymbol{\hat{\mu}}^{LS}(\mathcal{S}^{\rm C})$ satisfies the risk bound

where $R(\boldsymbol{\mu})=\max(1,\min\{\left\|\boldsymbol{\tau}-\boldsymbol{\mu}\right\|^{2},\boldsymbol{\tau}\text{ is affine}\})$ and $c>0$ is an absolute constant. It is proved in (Chatterjee et al. 2015, Example 2.3) that the least squares estimator $\boldsymbol{\hat{\mu}}^{LS}(\mathcal{S}^{\rm C})$ satisfies the oracle inequality

where $c>0$ is an absolute constant. The right hand side of (3.2) is small if the unknown vector $\boldsymbol{\mu}$ can be well approximated by a piecewise linear sequence in $\mathcal{S}^{\rm C}$ with not too many pieces.

The leading constant in (3.2) is 6. We will show that sparsity pattern aggregation achieves a substantially better performance. We obtain the sharp oracle inequality (3.5) below, improving upon (3.2) not only in the fact that the leading constant is 1 but also in the rate of the remainder term; we will see that the exponent $5/4$ of the logarithmic factor is reduced to 1.

For any set $J\subseteq\{2,...,n-1\}$, define

where ${\boldsymbol{\hat{\theta}}}$ is the solution of the optimization problem

The structure of this minimization problem is the same as of its analog introduced in Section 2. This is a quadratic program that aggregates the linear estimators $(Q_{J}\mathbf{y})_{J\subseteq\{2,...,n-1\}}$ using the $Q$-aggregation procedure Dai et al. 2012; Dai et al. 2014; Bellec 2014 with the prior weights (3.3).

The proof of this theorem is the same as that of Theorem 1 with the only difference that $J$ is now a subset of $\{2,...,n-1\}$ rather than that of $\{1,...,n-1\}$, and we replace the notation $P_{J}$ and $V_{J}$ by $Q_{J}$ and $W_{J}$ respectively.

The leading constant of the oracle inequality (3.5) is 1, and the remainder term is proportional to $q(\boldsymbol{u})\log(en/q(\boldsymbol{u}))$. These are two improvements upon (3.2), where the leading constant is 6 and the remainder term is proportional to $q(\boldsymbol{u})\log(en/q(\boldsymbol{u}))^{5/4}$.

In view of (3.5), for the class of piecewise linear convex sequences with at most $q$ linear pieces, $\mathcal{S}^{\rm C}_{q}=\{\boldsymbol{u}\in\mathcal{S}^{\rm C}:q(\boldsymbol{u})\leq q\}$ we have the following bounds for the maximal expected regrets

where $c>0$ is an absolute constant. The same bounds hold for the minimax risks over $\mathcal{S}^{\rm C}_{q}$ since the minimax risk is smaller than the minimax regret.

The following proposition shows that the rates of convergence in (3.6) and (3.7) are optimal up to logarithmic factors. We omit the discussion since it is similar to that after Proposition 4.

Let $n\geq 3$. There exist absolute constants $c,c^{\prime}>0$ such that, for any positive integer $q\leq n$,

where the infimum is taken over all estimators.

Assume that $q\geq 2$ since for $q=1$ the result is trivial. We also assume for simplicity that $n$ is a multiple of $q$. Let $m=n/q$ and $\gamma=(1/8)\sqrt{\sigma^{2}q/n}$. Set $\beta_{0}=0,\alpha_{0}=0$ and define, for all integers $j\geq 1$,

The sequence $\boldsymbol{u}^{\boldsymbol{\omega}}$ is piecewise linear. It is linear with slope $\alpha_{j}$ on the set $\{jm+1,...,(j+1)m\}$ for any $j=0,...,q-1$. Thus, $q(\boldsymbol{u}^{\boldsymbol{\omega}})=q$. Next, we prove that $\boldsymbol{u}^{\boldsymbol{\omega}}\in\mathcal{S}^{\rm C}$ for all ${\boldsymbol{\omega}}\in\Omega$. It is enough to check the convexity condition at the endpoints of the linear pieces:

for all $j=1,...,q-1$. Using (3.9) we get that, for all $j=1,...,q-1$,

Hence, $\alpha_{j-1}\leq u^{\boldsymbol{\omega}}_{jm+1}-u^{\boldsymbol{\omega}}_{jm}\leq\alpha_{j}$. Since also $\alpha_{j-1}=u^{\boldsymbol{\omega}}_{jm}-u^{\boldsymbol{\omega}}_{jm-1}$ and $\alpha_{j}=u^{\boldsymbol{\omega}}_{jm+2}-u^{\boldsymbol{\omega}}_{jm+1}$, it follows that the two inequalities (3.10) hold, for all $j=1,...,q-1$. Thus, $\boldsymbol{u}^{\boldsymbol{\omega}}\in\mathcal{S}^{\rm C}$. In summary, we have proved that $\boldsymbol{u}^{\boldsymbol{\omega}}\in\mathcal{S}^{\rm C}_{q}$ for all ${\boldsymbol{\omega}}\in\Omega$.

Now, from the Varshamov-Gilbert bound, cf. (2.21), for ${\boldsymbol{\omega}},{\boldsymbol{\omega}}^{\prime}\in\Omega$ we have

where $d_{H}(\cdot,\cdot)$ is the Hamming distance. Finally, similarly to (2.23), the Kullback-Leibler divergence between $P_{\boldsymbol{\omega}}$ and $P_{\bf 0}$ satisfies $K(P_{\boldsymbol{\omega}},P_{\bf 0})\leq\frac{\log(|\Omega|-1)}{16}$. Applying (Tsybakov 2009, Theorem 2.7) with $\alpha=1/16$ completes the proof. ∎

Concluding remarks and discussion

In this short note, we have shown that the estimators $\boldsymbol{\hat{\mu}}^{Q}$ and $\boldsymbol{\hat{\mu}}^{Q-conv}$ based on sparsity pattern aggregation (in its $Q$-aggregation version) achieve oracle inequalities that improve on some previous results for isotonic and convex regression.

Another improvement is that we obtain oracle inequalities both with high probability and in expectation, which was not the case in the previous work.

Finally, note that instead of $Q$-aggregation we could have used sparsity pattern aggregation by the Exponential Screening procedure of Rigollet and Tsybakov 2011. This would lead to sharp oracle inequalities in expectation of the form (2.6) and (3.5) but not to inequalities with high probability such as (2.5) and (3.4). This is the reason why we have opted for $Q$-aggregation rather than for Exponential Screening in this paper. On the other hand, Exponential Screening estimators are computationally more attractive than $Q$-aggregation since they can be successfully approximated by MCMC algorithms (see Rigollet and Tsybakov 2011; Rigollet and Tsybakov 2012 for details).

Acknowledgement. This work was supported by GENES and by the French National Research Agency (ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02), and Labex ECODEC (ANR - 11-LABEX-0047). It was also supported by the "Chaire Economie et Gestion des Nouvelles Données", under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.

References