\section{Introduction and notation}

Assume that we have noisy observations
\begin{equation}\label{1}
    y_i = f_i + \xi_i,
    \qquad
    i = 1,...,n,
\end{equation}
where $\xi_1,...,\xi_n$ are i.i.d. centered Gaussian random variables with variance $\sigma^2$, and ${\mathbf{f}}=(f_1,...,f_n)^T\in\R^n$ is an unknown mean vector.
In vector form, the model \eqref{1} can be rewritten as $\mathbf{y} = {\mathbf{f}} + {\boldsymbol{\xi}}$ where ${\boldsymbol{\xi}}=(\xi_1,...,\xi_n)^T$ and $\mathbf{y} = (y_1,...,y_n)^T$.
Let $\mathbb{X}\in\R^{n\times p}$ be a matrix with $p$ columns that we will call the design matrix. We consider the problem of estimation of ${\mathbf{f}}$ by $\mathbb{X} {\boldsymbol{\hat\beta}}(\mathbf{y})$ where  ${\boldsymbol{\hat\beta}}(\mathbf{y})$ is an estimator valued in $\R^p$. Specifically, we restrict our attention to penalized least squares estimators of the form
\begin{equation}
    {\boldsymbol{\hat\beta}}(\mathbf{y}) \in \argmin_{{\boldsymbol{\beta}}\in\R^p} \left(\norm{\mathbf{y} - \mathbb{X}{\boldsymbol{\beta}}}^2 + 2 F({\boldsymbol{\beta}})\right),
    \label{eq:def-hbeta-pen}
\end{equation}
where $\norm{\cdot}$ is the scaled Euclidean norm defined by
$\norm{{\mathbf{u}}}^2 = \frac 1 n \sum_{i=1}^n u_i^2$ for any ${\mathbf{u}}=(u_1,...,u_n)$, and $F:\R^p\rightarrow[0,+\infty]$ is a proper convex function, that is, a nonnegative convex function such that $F({\boldsymbol{\beta}})<+\infty$ for at least one ${\boldsymbol{\beta}}\in\R^p$. If the context prevents any ambiguity, we will omit the dependence on $\mathbf{y}$ and
write ${\boldsymbol{\hat\beta}}$ for the estimator ${\boldsymbol{\hat\beta}}(\mathbf{y})$.

The object of study in this paper is  the prediction error of the estimator ${\boldsymbol{\hat\beta}}(\mathbf{y})$, that is, the value $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}$. We show that, for any design matrix $\mathbb{X}$ and for any proper convex penalty $F$, the prediction error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}$ is a subgaussian random variable concentrated around its median and its expectation.
Furthermore, when $F$ is a norm, we obtain an explicit formula for the predictor $\mathbb{X} {\boldsymbol{\hat\beta}}(\mathbf{y})$ in terms of the projection on the dual ball.  Finally, we apply the subgaussian concentration property around the median to derive sharp oracle inequalities for the prediction error of the LASSO, the group LASSO and the SLOPE estimators, both in probability and in expectation.
The inequalities in probability improve upon the previous work on the LASSO type estimators (see, e.g., the papers \cite{bickel2009simultaneous,koltchinskii2011nuclear,lptv2011,dalalyan2014prediction}
or the monographs \cite{giraud2014introduction,buhlmann2011statistics,vdgeer}) since, in contrast to the results of these works, our bounds hold at any given confidence level for estimators with tuning parameter that does not depend on the confidence level. This is also the reason why we are able to establish bounds in expectation, while the previously known techniques did not allow for the control of the expected risk. In addition, we show that the concentration rate in the oracle inequalities
is better than it was commonly understood before.
Similar results have been obtained quite recently in \cite{bellec2016slope} by a different and somewhat more involved construction conceived specifically for the LASSO and the SLOPE estimators. The techniques of the present paper are more general since they can be used not only for these two estimators but for any penalized least squares estimators with convex penalty.

\section{Notation}

For any random variable $Z$, let $\Med[Z]$ be a median of $Z$, i.e.,
any real number $M$ such that $\mathbb P(Z\ge M) = \mathbb P (Z\le M) = 1/2$.
For  a vector
${\mathbf{u}}=(u_1,...,u_n)$, the sup-norm, the Euclidean norm and the $\ell_1$-norm will be denoted
by
$\norma{{\mathbf{u}}}_\infty = \max_{i=1,...,n} |u_i|$,
$\norma{{\mathbf{u}}}_1 = \sum_{i=1}^n |u_i|$
and
$
\norma{{\mathbf{u}}}_2 = (
    \sum_{i=1}^n u_i^2
)^{1/2}
$. The inner product in $\R^n$ is denoted by $\langle\cdot,\cdot\rangle$. We also denote by  $\supp({\mathbf{u}})$ the support of ${\mathbf{u}}$, and by $|{\mathbf{u}}|_0$ the cardinality of $\supp({\mathbf{u}})$. We denote by $I(\cdot)$ the indicator function.
For any $S\subset\{1,...,p\}$ and a vector ${\mathbf{u}}=(u_1,...,u_p)$, we set ${\mathbf{u}}_S=(u_jI(j\in S))_{j=1,...,p}$, and we denote by $|S|$ the cardinality of~$S$.

\section{The prediction error of convex penalized estimators is subgaussian}
\label{s:machinery}

The aim of this section is
to show that the prediction error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}$
is subgaussian and concentrates around its median
for any estimator ${\boldsymbol{\hat\beta}}(\mathbf{y})$ defined by \eqref{eq:def-hbeta-pen}.
The results of the present section will allow us to carry out a unified analysis of LASSO, group LASSO  and SLOPE estimators
in Sections \ref{s:lasso} -- \ref{s:slope}.

\begin{proposition}\label{prop1}
Let $\boldsymbol{\hat \mu}:\R^n\rightarrow\R^n$ be an $L$-Lipschitz function,
that is, a function satisfying
\begin{equation}
    \label{eq:lipschitz-hmu}
    \norm{\boldsymbol{\hat \mu}(\mathbf{y}) - \boldsymbol{\hat \mu}(\mathbf{y}')} \le L \norm{\mathbf{y} - \mathbf{y}'},
    \qquad \forall
    \mathbf{y},\mathbf{y}'\in\R^n.
\end{equation}
    Let $f({\mathbf{z}}) = \norm{\boldsymbol{\hat \mu}({\mathbf{f}}+\sigma {\mathbf{z}}) - {\mathbf{f}}}$
    for some fixed ${\mathbf{f}}\in\R^n$ and
    ${\mathbf{z}}\sim\mathcal N({\mathbf{0}},I_{n\times n})$.
    Then,
     for all $t>0$,
    \begin{equation}
        \label{eq:lipschitz-concentration}
            \mathbb{P}
            \left(
                f({\mathbf{z}})>\Med[f({\mathbf{z}})] + \frac{\sigma L t}{ \sqrt{n}}
            \right) \le 1-\Phi(t),
                       \end{equation}
where $\Phi(\cdot)$ is the $\mathcal N(0,1)$ cumulative distribution function.

\end{proposition}
\begin{proof}
    \smartqed
    The result
    follows immediately from the Gaussian concentration inequality  (cf., e.g.,  \cite[Theorem 6.2]{lifshits})

    and the fact that $f(\cdot)$ satisfies the Lipschitz condition
    \begin{equation*}
        \left|
            f({\mathbf{u}})
            -
            f({\mathbf{u}}')
        \right|
        \le
        \norm{\boldsymbol{\hat \mu}({\mathbf{f}}+\sigma {\mathbf{u}}) - \boldsymbol{\hat \mu}({\mathbf{f}}+\sigma {\mathbf{u}}')}
        \le \frac{\sigma L}{\sqrt n} \norma{{\mathbf{u}} - {\mathbf{u}}'}_2, \qquad \forall
    {\mathbf{u}},{\mathbf{u}}'\in\R^n.
    \end{equation*}
        \qed
\end{proof}

We now show  that $\boldsymbol{\hat \mu}(\mathbf{y})=\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$ where ${\boldsymbol{\hat\beta}}(\mathbf{y})$ is  estimator \eqref{eq:def-hbeta-pen} with any proper convex penalty satisfies the Lipschitz condition \eqref{eq:lipschitz-hmu} with $L=1$.

We first consider estimators penalized by a norm in $\R^p$, for which we get a sharper result. Namely, in this case the explicit expression for $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$ is available. In addition, we get a stronger property than the Lipschitz condition \eqref{eq:lipschitz-hmu}.
Let $N:\R^p\rightarrow\R_+$ be a norm and let $N_\circ(\cdot)$
be the corresponding dual norm defined by $N_\circ({\mathbf{u}}) = \sup_{{\mathbf{v}}\in\R^p: N({\mathbf{v}}) = 1} {\mathbf{u}}^T{\mathbf{v}}$.
For any $\mathbf{y}\in\R^n$, define ${\boldsymbol{\hat\beta}}(\mathbf{y})$ as a solution of the following minimization problem:
\begin{equation}
    {\boldsymbol{\hat\beta}}(\mathbf{y}) \in \argmin_{{\boldsymbol{\beta}}\in\R^p} \left(\norm{\mathbf{y} - \mathbb{X}{\boldsymbol{\beta}}}^2 + 2 N({\boldsymbol{\beta}})\right).
    \label{eq:def-hbeta-norm-N}
\end{equation}
The next two propositions are crucial  in proving that the concentration bounds \eqref{eq:lipschitz-concentration} apply when $f({\mathbf{z}})$ is the prediction error associated with ${\boldsymbol{\hat\beta}}(\mathbf{y})$.

\begin{proposition}\label{prop2}
Let $N:\R^p\rightarrow\R_+$ be a norm and let  ${\boldsymbol{\hat\beta}}(\mathbf{y})$ be a solution of \eqref{eq:def-hbeta-norm-N}.
    For all $\mathbf{y}\in\R^n$ and all matrices $\mathbb{X}\in\R^{n\times p}$ , we have:\\
    (i)
    $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) = \mathbf{y}-P_C(\mathbf{y})$
    where  $P_C(\cdot):\R^n\rightarrow C$
    is the operator of projection onto the closed convex set
    $C = \{{\mathbf{u}}\in\R^n: N_\circ(\mathbb{X}^T{\mathbf{u}}) \le 1/n \}$, \\
    (ii) the function $\boldsymbol{\hat \mu}(\mathbf{y}) = \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$
    satisfies
    $$
    \norm{\boldsymbol{\hat \mu}(\mathbf{y}) - \boldsymbol{\hat \mu}(\mathbf{y}')}^2 \le \norm{\mathbf{y} - \mathbf{y}'}^2 - \frac1n |P_C(\mathbf{y})- P_C(\mathbf{y}')|_2^2.
    $$
\end{proposition}

\begin{proof}
    \smartqed
    Since $C$ is a closed convex set, we have that ${\boldsymbol{\theta}} = P_C(\mathbf{y})$ if and only if
    \begin{equation}\label{obtu}
        (\mathbf{y} - {\boldsymbol{\theta}})^T({\boldsymbol{\theta}} - {\mathbf{u}}) \ge 0
        \qquad
        \text{for all }
        {\mathbf{u}}\in C.
    \end{equation}
 Thus, to prove statement (i) of the proposition, it is enough to check that \eqref{obtu} holds for ${\boldsymbol{\theta}} = \mathbf{y} - \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$.
  Since \eqref{obtu} is trivial when ${\boldsymbol{\hat\beta}}(\mathbf{y})=0$, we assume in what follows that ${\boldsymbol{\hat\beta}}(\mathbf{y})\ne0$. Any solution ${\boldsymbol{\hat\beta}}(\mathbf{y})$ of the convex minimization problem in \eqref{eq:def-hbeta-norm-N} satisfies
    \begin{equation}\label{moreau}
        \frac1{n}\mathbb{X}^T(\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - \mathbf{y}) + {\mathbf{v}} ={\mathbf{0}}

    \end{equation}
    where ${\mathbf{v}}$ is an element of the subdifferential of $N(\cdot)$ at ${\boldsymbol{\hat\beta}}(\mathbf{y})$.
    Recall that the subdifferential of any norm  $N(\cdot)$ at ${\boldsymbol{\hat\beta}}(\mathbf{y})\ne 0$ is the set
    $\{{\mathbf{v}}\in\R^p: N({\mathbf{v}}) = 1 \text{ and } {\mathbf{v}}^T{\boldsymbol{\hat\beta}}(\mathbf{y}) = N({\boldsymbol{\hat\beta}}(\mathbf{y})) \}$ \cite[Section 2.6]{ATF}.
    Therefore, taking an inner product of \eqref{moreau} with ${\boldsymbol{\hat\beta}}(\mathbf{y})$ yields
    \begin{align*}
    (\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}))^T (\mathbf{y} - \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}))

    =
    nN({\boldsymbol{\hat\beta}}(\mathbf{y}))
    &=
    n \max_{{\boldsymbol{w}}\in\R^p:N_\circ({\boldsymbol{w}}) = 1} {\boldsymbol{\hat\beta}}(\mathbf{y})^T{\boldsymbol{w}}
    \\
    &\ge
    \max_{{\mathbf{u}}\in\R^n:N_\circ(\mathbb{X}^T{\mathbf{u}}) = 1/n} (\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}))^T{\mathbf{u}}= \max_{{\mathbf{u}}\in C} (\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}))^T{\mathbf{u}}.
    \end{align*}
    This proves \eqref{obtu} with ${\boldsymbol{\theta}} = \mathbf{y} - \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$. Thus,
    we have established that $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) = \mathbf{y} - P_C(\mathbf{y})$.

To prove part  (ii) of the proposition, we use that, for any closed
    convex subset $C$ of $\R^n$ and any $\mathbf{y},\mathbf{y}'\in \R^n$,
    $$
     |P_C(\mathbf{y})- P_C(\mathbf{y}')|_2^2 \le \langle P_C(\mathbf{y})- P_C(\mathbf{y}'), \mathbf{y}- \mathbf{y}'\rangle,
    $$
    see, e.g., \cite[Proposition 3.1.3]{hiriart_lemarechal}.  This immediately implies
 $$
     |\mathbf{y} - P_C(\mathbf{y})- (\mathbf{y}' -P_C(\mathbf{y}'))|_2^2 \le  |\mathbf{y}- \mathbf{y}' |_2^2- |P_C(\mathbf{y})- P_C(\mathbf{y}')|_2^2.
  $$
  Part (ii) of the proposition follows now from part (i) and the last display.
     \qed
\end{proof}

We note that Propostion \ref{prop2} generalizes to any norm $N(\cdot)$ an analogous result obtained for the $\ell_1$-norm in \cite[Lemma 3]{tibshirani2012}.

 We now turn to the general case assuming that $F$ is any convex penalty.

\begin{proposition}\label{prop3}
    Let $F: \R^p\rightarrow [0,+\infty]$ be any proper convex function.
    For all $\mathbf{y}\in\R^n$, let ${\boldsymbol{\hat\beta}}(\mathbf{y})$ be any solution of the convex minimization problem \eqref{eq:def-hbeta-pen}.
    Then the estimator $\boldsymbol{\hat \mu}(\mathbf{y}) = \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y})$
    satisfies \eqref{eq:lipschitz-hmu}
    with $L=1$.
\end{proposition}
\begin{proof}
    \smartqed
    Let $\mathbf{y},\mathbf{y}'\in\R^n$.
    The case $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) = \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}')$ is trivial so we assume in the following that
    $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) \ne \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}')$.
    The optimality condition and the Moreau-Rockafellar Theorem \cite[Theorem 3.30]{peypouquet2015convex}
    yield that
    there exist an element ${\mathbf{h}}\in\R^p$ of the subdifferential $\partial F({\boldsymbol{\hat\beta}}(\mathbf{y}))$ of $F(\cdot)$ at ${\boldsymbol{\hat\beta}}(\mathbf{y})$
    and ${\mathbf{h}}'\in \partial F({\boldsymbol{\hat\beta}}(\mathbf{y}'))$ such that
    \begin{equation*}
       \frac1{n}   \mathbb{X}^T(\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - \mathbf{y}) + {\mathbf{h}}= {\mathbf{0}}, \quad \text{and} \quad
        \frac1{n}  \mathbb{X}^T(\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}') - \mathbf{y}') + {\mathbf{h}}' = {\mathbf{0}}.
    \end{equation*}
    Taking the difference of these two equalities we obtain
    \begin{equation*}
        \mathbb{X}^T(\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - \mathbb{X} {\boldsymbol{\hat\beta}}(\mathbf{y}')) - \mathbb{X}^T(\mathbf{y} - \mathbf{y}')
        = n ({\mathbf{h}}' - {\mathbf{h}}).
    \end{equation*}
    Let ${\boldsymbol{\Delta}} = {\boldsymbol{\hat\beta}}(\mathbf{y}) - {\boldsymbol{\hat\beta}}(\mathbf{y}')$. Since $F$ is a proper convex function, we have that
    ${\boldsymbol{\Delta}}^T({\mathbf{h}} - {\mathbf{h}}')=\langle {\mathbf{h}} - {\mathbf{h}}', {\boldsymbol{\hat\beta}}(\mathbf{y}) - {\boldsymbol{\hat\beta}}(\mathbf{y}')\rangle \ge 0$ for any ${\mathbf{h}}\in \partial F({\boldsymbol{\hat\beta}}(\mathbf{y}))$ and any ${\mathbf{h}}'\in \partial F({\boldsymbol{\hat\beta}}(\mathbf{y}'))$
    (see, e.g., \cite[Proposition 3.22]{peypouquet2015convex}). Therefore,
    \begin{equation*}
        {\boldsymbol{\Delta}}^T \mathbb{X}^T\mathbb{X} {\boldsymbol{\Delta}} - {\boldsymbol{\Delta}}^T \mathbb{X}^T(\mathbf{y} - \mathbf{y}')
        =
       n {\boldsymbol{\Delta}}^T({\mathbf{h}}' - {\mathbf{h}}) \le 0.
    \end{equation*}
    This and the Cauchy-Schwarz inequality yield
    \begin{equation}
        \norma{\mathbb{X}{\boldsymbol{\Delta}}}^2_2
        \le
        {\boldsymbol{\Delta}}^T \mathbb{X}^T(\mathbf{y} - \mathbf{y}')
        \le \norma{\mathbb{X}{\boldsymbol{\Delta}}}_2 \norma{\mathbf{y} - \mathbf{y}'}_2,
    \end{equation}
    which implies $\norma{\mathbb{X}{\boldsymbol{\Delta}}}_2\le \norma{\mathbf{y} - \mathbf{y}'}_2$ since $\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) \ne \mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}')$.
    \qed
\end{proof}
Combining the above two propositions we obtain the following theorem.

\begin{theorem}\label{cor3}
    Let $R\ge0$ be a constant and ${\mathbf{f}}\in\R^n$.
    Assume that ${\boldsymbol{\xi}}\sim \mathcal N({\mathbf{0}},\sigma^2 I_{n\times n})$ and let $\mathbf{y} = {\mathbf{f}} + {\boldsymbol{\xi}}$.
    Let $F: \R^p\rightarrow [0,+\infty]$ be any proper convex function.
    Assume also that the estimator ${\boldsymbol{\hat\beta}}$ defined in \eqref{eq:def-hbeta-norm-N}
    satisfies
    \begin{equation}\label{rough_bound}
        \mathbb{P}\left(\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}} \le R\right) \ge 1/2,
     \end{equation}
     or equivalently, the median of the prediction error
     satisfies $\Med[\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}]\le R$.
         Then,
    for all $t>0$,
    \begin{equation}\label{cor3_3}
        \mathbb{P}\left(\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}} \le
            R
            +  \frac{\sigma t}{ \sqrt{n}}
\right) \ge \Phi(t)
    \end{equation}
and consequently,
     for all $x>0$,
    \begin{equation}\label{cor3_3a}
        \mathbb{P}\left(\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}} \le
            R
            + \sigma \sqrt{2 x / n}\right) \ge 1-e^{-x}.
    \end{equation}
     Furthermore,
     \begin{equation}\label{integration}
        \E \norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}
        \le
        R
        + \frac{\sigma}{ \sqrt{2 \pi n}}.
    \end{equation}
\end{theorem}
\begin{proof}
    \smartqed
    Fix ${\mathbf{f}}\in\R^n$ and let ${\mathbf{z}}\sim\mathcal N({\mathbf{0}},I_{n\times n})$.
    Proposition~\ref{prop3} implies that  the function
    $f({\mathbf{z}}) = \norm{\mathbb{X}{\boldsymbol{\hat\beta}}({\mathbf{f}}+\sigma {\mathbf{z}}) - {\mathbf{f}}}$
    satisfies
    \eqref{eq:lipschitz-concentration}
    with $L=1$ for all $x>0$.
    Thus, we can apply Proposition~\ref{prop1} and \eqref{cor3_3a}  follows from \eqref{eq:lipschitz-concentration}.
   The bound \eqref{cor3_3a} is a simplified version of \eqref{cor3_3} using that $1-\Phi(t)\le e^{-t^2/2}, \ \forall t>0$.
    Finally, inequality \eqref{integration} is obtained by integration of \eqref{cor3_3}.
    \qed
\end{proof}

Note that condition \eqref{rough_bound} in Theorem \ref{cor3} is a weak property. To satisfy it, is enough to have a rough bound on $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}$. Of course, we would like to have a meaningful value of $R$. In the next two sections, we give examples of such $R$. Namely, we show that Theorem \ref{cor3} allows one to derive sharp oracle inequalities for the prediction risk of such estimators as LASSO, group LASSO, and SLOPE.

\begin{remark}Along with the concentration around the median, the prediction error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}$ also concentrates around its expectation. Using the Lipschitz property of Proposition~\ref{prop1}, and the theorem about Gaussian concentration with respect to the expectation (cf., e.g., \cite[Theorem B.6]{giraud2014introduction}) we find that, if $F:\R^n\rightarrow [0,+\infty]$ is a proper convex function,
 \begin{equation}\label{cor3_3b}
        \mathbb{P}\left(\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}} \le
            \E \norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}
            + \sigma \sqrt{2 x / n}\right) \ge 1-e^{-x}
    \end{equation}
    and
    \begin{equation}\label{cor3_3bb}
        \mathbb{P}\left(\norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}} \ge
            \E \norm{\mathbb{X}{\boldsymbol{\hat\beta}}(\mathbf{y}) - {\mathbf{f}}}
            - \sigma \sqrt{2 x / n}\right) \ge 1-e^{-x}.
    \end{equation}
For the special case of identity design matrix $\mathbb{X}=I_{n\times n}$, these properties have been proved in
\cite{vandegeer2015concentration} where they were applied to some problems of nonparametric estimation.
However, the bounds \eqref{cor3_3b} and \eqref{cor3_3bb} dealing with the concentration around the expectation
are of no use for the purposes of the present paper since initially we have no control of the expectation. On the other hand,
a meaningful control of the median is often easy to obtain as shown in the examples below. This is the reason why we focus on the concentration around the median.
\end{remark}

\section{Application to LASSO}
\label{s:lasso}

The LASSO is a convex regularized estimator defined by the relation
\begin{equation}
    {\boldsymbol{\hat\beta}} \in \argmin_{{\boldsymbol{\beta}}\in\R^p} \left(\norm{\mathbf{y} - \mathbb{X}{\boldsymbol{\beta}}}^2 + 2\lambda \norma{{\boldsymbol{\beta}}}_1 \right)
    \label{eq:def-lasso}
\end{equation}
where $\lambda>0$ is a tuning parameter.
Risk bounds for the LASSO estimator are established under some conditions on the design matrix $\mathbb{X}$
that measure the correlations between its columns.
The Restricted Eigenvalue (RE) condition \cite{bickel2009simultaneous} is defined as follows.
For any $S\subset\{1,...,p\}$ and $c_0> 0$,
we define the Restricted Eigenvalue constant $\kappa(S,c_0)\ge 0$ by the formula
\begin{equation}
    \kappa^2(S,c_0) \triangleq \min_{{\boldsymbol{\Delta}}\in\R^p: |{\boldsymbol{\Delta}}_{S^c}|_1\le c_0|{\boldsymbol{\Delta}}_{S}|_1} \frac{\norm{\mathbb{X}{\boldsymbol{\Delta}}}^2}{|{\boldsymbol{\Delta}}|_2^2}.
    \label{eq:def-kappa}
\end{equation}
She RE condition $RE(S,c_0)$ is said to hold if $\kappa(S,c_0) > 0$. Note that \eqref{eq:def-kappa} is slightly different from the original definition given in \cite{bickel2009simultaneous} since we have ${\boldsymbol{\Delta}}$ and not ${\boldsymbol{\Delta}}_S$ in the denominator. However, the two definitions are equivalent up to a constant depending only on $c_0$, cf. \cite{bellec2016slope}.
In terms of the Restricted Eigenvalue constant, we have the following deterministic result.
\begin{proposition}
    \label{prop:lasso-deterministic}
    Let $\lambda>0$ be a tuning parameter.
    On the event
    \begin{equation}
        \left\{ \frac 1 n \norma{\mathbb{X}^T {\boldsymbol{\xi}}}_\infty \le \frac \lambda 2 \right\},
        \label{eq:lasso-event}
    \end{equation}
    the LASSO estimator \eqref{eq:def-lasso} with tuning parameter $\lambda$ satisfies
    \begin{equation}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        \le
        \min_{S\subset \{1,...,p\} }
               \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
             \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }^2
            + \frac{9 |S| \lambda^2}{4\kappa^2(S,3)}
        \right]
        \label{eq:soi-squared-lasso}
    \end{equation}
    with the convention that $a/0=+\infty$ for any $a>0$.
\end{proposition}
An oracle inequality as in Proposition \ref{prop:lasso-deterministic} has been first established in \cite{bickel2009simultaneous}
with a multiplicative constant greater than $1$ in front of the right hand side of \eqref{eq:soi-squared-lasso}.
The fact that this constant can be reduced to 1, so that the oracle inequality becomes sharp, is due to \cite{koltchinskii2011nuclear}.
For the sake of completeness, we provide below a sketch of the proof of
Proposition \ref{prop:lasso-deterministic}.
\begin{proof
    \smartqed
    We will use the following fact \cite[Lemma A.2]{bellec2016slope}.
    \begin{lemma}\label{lem1}
    Let $F:\R^p\rightarrow\R$ be a convex function,
    let ${\mathbf{f}}, {\boldsymbol{\xi}}\in \R^n$, $\mathbf{y}={\mathbf{f}}+{\boldsymbol{\xi}}$ and let $\mathbb{X}$ be any $n\times p$ matrix.
    If ${\boldsymbol{\hat\beta}}$ is a solution of the minimization problem \eqref{eq:def-hbeta-pen},
        then ${\boldsymbol{\hat\beta}}$ satisfies, for all ${\boldsymbol{\beta}}\in\R^p$,
    \begin{equation*}
        \norm{\mathbb{X}{\boldsymbol{\hat\beta}} - {\mathbf{f}}}^2
        -
        \norm{\mathbb{X}{\boldsymbol{\beta}} - {\mathbf{f}}}^2
        \le
        2\left(\frac 1 n {\boldsymbol{\xi}}^T\mathbb{X}({\boldsymbol{\hat\beta}} - {\boldsymbol{\beta}})
        + F({\boldsymbol{\beta}})
        - F({\boldsymbol{\hat\beta}})\right)
        - \norm{\mathbb{X}({\boldsymbol{\hat\beta}} - {\boldsymbol{\beta}})}^2.
        \label{eq:almost-sure}
    \end{equation*}
\end{lemma}

    Let $S\subset\{1,...,p\}$ and ${\boldsymbol{\beta}}$ be minimizers of the right hand side of
    \eqref{eq:soi-squared-lasso} and let ${\boldsymbol{\Delta}} = {\boldsymbol{\hat\beta}} - {\boldsymbol{\beta}}$. We will assume that $\kappa(S,3)>0$ since otherwise the claim is trivial.
    From Lemma \ref{lem1} with $F({\boldsymbol{\beta}})=\lambda  |{\boldsymbol{\beta}}|_1$ we have
    \begin{equation*}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        -
        \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }^2
        \le 2\left( \tfrac 1 n {\boldsymbol{\xi}}^T\mathbb{X} {\boldsymbol{\Delta}} + \lambda |{\boldsymbol{\beta}}|_1 - \lambda |{\boldsymbol{\hat\beta}}|_1\right)
        - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2
        \triangleq D.
    \end{equation*}
    On the event \eqref{eq:lasso-event}, using the duality inequality ${\mathbf{x}}^T{\boldsymbol{\Delta}} \le |{\mathbf{x}}|_\infty |{\boldsymbol{\Delta}}|_1$
    valid for all ${\mathbf{x}},{\boldsymbol{\Delta}}\in\R^p$
    and the triangle inequality for the $\ell_1$-norm, we find that
    the right hand side of the previous display satisfies
    \begin{equation*}
        D
        \le
        2\lambda \left[
            \frac 1 2|{\boldsymbol{\Delta}}|_1
            + |{\boldsymbol{\beta}}|_1 - |{\boldsymbol{\hat\beta}}|_1
        \right] - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2
        \le
        2\lambda \left[
            \frac 3 2 |{\boldsymbol{\Delta}}_S|_1
            - \frac 1 2 |{\boldsymbol{\Delta}}_{S^c}|_1
        \right] - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2.
    \end{equation*}
    If $|{\boldsymbol{\Delta}}_{S^c}|_1 > 3|{\boldsymbol{\Delta}}_S|_1$ then the claim follows trivially.
    Otherwise, if $|{\boldsymbol{\Delta}}_{S^c}|_1 \le 3|{\boldsymbol{\Delta}}_S|_1$ we have
    $|{\boldsymbol{\Delta}}|_2 \le \norm{\mathbb{X}{\boldsymbol{\Delta}}}/\kappa(S,3)$
    and thus,
    by the Cauchy-Schwarz inequality,
    \begin{equation}\label{eq:last}
        3\lambda|{\boldsymbol{\Delta}}_S|_1
        \le
        3 \lambda\sqrt{|S|} |{\boldsymbol{\Delta}}_S|_2
        \le
        \frac{9|S|\lambda^2}{4\kappa^2(S,3)} + \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2.
    \end{equation}
    Combining the above three displays yields \eqref{eq:soi-squared-lasso}.
    \qed
\end{proof}

\begin{theorem}
    \label{thm:lasso}
    Let $p\ge 2$ and $\lambda\ge 2 \sigma \sqrt{2\log(p)/n}$.
    Assume that the diagonal elements of matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ are not greater than 1.
    Then for any $\delta\in(0,1)$, the LASSO estimator \eqref{eq:def-lasso} with tuning parameter $\lambda$
    satisfies
    \begin{equation}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{S\subset \{1,...,p\}}
         \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
        \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }
        + \frac{3\lambda\sqrt{|S|}}{2\kappa(S,3)}  \right]
        + \frac{\sigma \Phi^{-1}(1-\delta)}{\sqrt{n}}
        \label{eq:all-delta-lasso}
    \end{equation}
    with probability at least $1-\delta$, noting that $\Phi^{-1}(1-\delta)\le \sqrt{2\log (1/\delta)}$. Furthermore,
    \begin{equation}
      \E  \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{S\subset \{1,...,p\}}
        \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
        \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }
        + \frac{3\lambda\sqrt{|S|}}{2\kappa(S,3)}
                \right]
        + \frac{\sigma}{ \sqrt{2 \pi n}}.
        \label{eq:all-delta-lasso-bis}
         \end{equation}
\end{theorem}
Theorem \ref{thm:lasso} is a simple consequence of Proposition \ref{prop:lasso-deterministic} and Theorem \ref{cor3}.
Its proof is given at the end of the present section.

Previous works on the LASSO estimator established that
for some fixed $\delta_0\in (0,1)$
the estimator  \eqref{eq:def-lasso} with tuning parameter $\lambda= c_1 \sigma \sqrt{2\log(c_2p/\delta_0)}$, where  $c_1>1, c_2\ge 1$ are some constants,
satisfies an oracle inequality of the form \eqref{eq:soi-squared-lasso}
with probability at least $1-\delta_0$,
see for instance \cite{bickel2009simultaneous,koltchinskii2011nuclear,dalalyan2014prediction}
or the books on high-dimensional statistics \cite{giraud2014introduction,buhlmann2011statistics,vdgeer}.
Thus, such oracle inequalities
were available only for one fixed confidence level $1-\delta_0$
tied to the tuning parameter $\lambda$.
Remarkably, Theorem \ref{thm:lasso} shows that the LASSO estimator with a universal (not level-dependent) tuning parameter, which can be as small as $2 \sigma \sqrt{(2\log p)/n}$, satisfies \eqref{eq:all-delta-lasso} for all confidence levels $\delta\in(0,1)$. As a consequence, we can obtain an oracle inequality \eqref{eq:all-delta-lasso-bis} for the expected error, while control of the expected error was not achievable with the previously known methods of proof. Furthermore, bounds for any moments of the prediction error can be readily obtained by integration of \eqref{eq:all-delta-lasso}. Analogous facts have been shown recently in \cite{bellec2016slope}
using different techniques.
To our knowledge, the present paper and \cite{bellec2016slope}
provide the first evidence of such properties of the LASSO estimator.

In addition, Theorem \ref{thm:lasso} shows that the rate of concentration in the oracle inequalities
is better than it was commonly understood before. Let $S\subset\{1,...,p\}$, $s=|S|$
and set $\delta = \exp(-2 s \lambda^2n/ \sigma^2\kappa^2(S,3) )$.
For this choice of $\delta$, Theorem \ref{thm:lasso} implies that
if $\lambda\ge 2\sigma\sqrt{2\log(p)/n}$ then
\begin{equation*}
    \mathbb P
    \left(
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
        \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }
        + \frac{7\lambda\sqrt{|S|}}{2\kappa(S,3)}
    \right) \ge
    1 - e^{-2 s \lambda^2 n/ \sigma^2\kappa^2(S,3) }
    .
\end{equation*}
Since the diagonal elements of $\frac 1 n \mathbb{X}^T\mathbb{X}$ are at most
1, we have $\kappa(S,3) \le 1$.
Thus, the probability on the right hand side of the last display is at least $1-p^{-16s}$.
Interestingly, this probability depends on the sparsity $s$ and tends to 1 exponentially fast as $s$ grows.
The previous proof techniques
\cite{bickel2009simultaneous,koltchinskii2011nuclear,dalalyan2014prediction,buhlmann2011statistics}
provided, for the same type of probability, only an estimate of the form $1-p^{-b}$
for some fixed constant $b>0$ independent of $s$.

The oracle inequality \eqref{eq:soi-squared-lasso} holds for the error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}} - {\mathbf{f}}}$.
In order to obtain an oracle inequality for the squared error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}} - {\mathbf{f}}}^2$,
one can combine \eqref{eq:all-delta-lasso}
with the basic inequality $(a+b+c)^2\le 3(a^2+b^2+c^2)$.
This yields that under the assumptions of Theorem \ref{thm:lasso},
the LASSO estimator with tuning parameter $\lambda\ge 2\sigma\sqrt{2\log(p)/n}$ satisfies,
with probability at least $1-\delta$,
\begin{equation*}
    \norm{
        \mathbb{X}{\boldsymbol{\hat\beta}}
        -
        {\mathbf{f}}
    }^2
    \le
    \min_{S\subset \{1,...,p\}}  \left[
    \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
          3 \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }^2
        + \frac{27\lambda^2|S|}{4\kappa^2(S,3)} \right]
        + \frac{6\log(1/\delta)}{n}
   .
\end{equation*}
The constant $3$ in front of the
$
\norm{
    \mathbb{X}{\boldsymbol{\beta}}
    -
    {\mathbf{f}}
}^2$
can be reduced to 1 using the techniques developed in \cite{bellec2016slope}.

{\it Proof of Theorem \ref{thm:lasso}.}
    The random variable $|\mathbb{X}^T{\boldsymbol{\xi}}|_\infty / \sqrt n$
    is the maximum of $p$ centered Gaussian random variables
    with variance at most $\sigma^2$.
    If $\eta\sim\mathcal N(0,1)$,
    a standard approximation of the Gaussian tail gives
        $\mathbb P(|\eta|> x) \le \sqrt{2/\pi} (e^{-x^2/2}/x)$ for all $x>0$.
    This approximation with $x=\sqrt{2\log p}$ together with
    and the union bound imply
    that the event \eqref{eq:lasso-event} with $\lambda\ge 2\sigma \sqrt{(2\log p)/n}$ has probability
    at least
    $1 - 1/\sqrt{\pi\log p}$,
    which is greater than $1/2$ for all $p\ge 3$. For $p=2$, the probability of this event is bounded from below by $1-2\mathbb P(|\eta|> \sqrt{2\log 2})>1/2$. Thus, Proposition \ref{prop:lasso-deterministic} implies that condition \eqref{rough_bound} is satisfied with $R$ being the square root of the right hand side of \eqref{eq:soi-squared-lasso}.
    Let $S$ and ${\boldsymbol{\beta}}$ be minimizers of the right hand side of
    \eqref{eq:all-delta-lasso}.
    Applying Theorem \ref{cor3} and the inequality $\sqrt{a+b}\le \sqrt a + \sqrt b$ with
    $\sqrt a = \norm{\mathbb{X}{\boldsymbol{\beta}} - {\mathbf{f}}}$
    and
    $\sqrt b = 3\lambda\sqrt{|S|}/(2\kappa(S,3))$
    completes the proof.

\section{Application to group LASSO and related penalties}
\label{s:glasso}

The above arguments can be used to establish oracle inequalities for the group LASSO estimator similar to those obtained in Section \ref{s:lasso} for the usual LASSO. The improvements as compared to the previously known oracle bounds (see, e.g., \cite{lptv2011} or the books \cite{giraud2014introduction,buhlmann2011statistics,vdgeer}) are the same as above -- independence of the tuning parameter on the confidence level, better concentration, and derivation of bounds in expectation.

Let $G_1,...,G_M$ be a partition of $\{1,...,p\}$. The group LASSO estimator is a solution of the convex minimization problem
\begin{equation}
    {\boldsymbol{\hat\beta}} \in \argmin_{{\boldsymbol{\beta}}\in\R^p}\left(
    \norm{\mathbf{y}-\mathbb{X}{\boldsymbol{\beta}}}^2
    + 2  \lambda \sum_{k=1}^M |{\boldsymbol{\beta}}_{G_k}|_2\right),
    \label{eq:def-glasso}
\end{equation}
 where $\lambda>0$ is a tuning parameter. In the following, we assume that the groups $G_k$ have the same cardinality $|G_k|= T=p/M$, $k=1,...,M$.

 We will need the following group analog of the RE constant introduced in~\cite{lptv2011}. For any $S\subset\{1,...,M\}$ and $c_0> 0$,
we define the group Restricted Eigenvalue constant $\kappa_G(S,c_0)\ge 0$ by the formula
\begin{equation}
    \kappa^2_G(S,c_0) \triangleq \min_{{\boldsymbol{\Delta}}\in\mathcal C(S,c_0)} \frac{\norm{\mathbb{X}{\boldsymbol{\Delta}}}^2}{|{\boldsymbol{\Delta}}|_2^2},
    \label{eq:def-kappa-g}
\end{equation}
where $\mathcal C(S,c_0)$ is the cone
$$
\mathcal C (S,c_0)\triangleq \{{\boldsymbol{\Delta}}\in\R^p: \sum_{k\in S^c}|{\boldsymbol{\Delta}}_{G_k}|_2\le c_0\sum_{k\in S}|{\boldsymbol{\Delta}}_{G_k}|_2\}.
$$
Denote by $\mathbb{X}_{G_k}$ the $n\times |G_k|$ submatrix of $\mathbb{X}$ composed from all the columns of $\mathbb{X}$ with indices in $G_k$. For any ${\boldsymbol{\beta}}\in \R^p$, set ${\mathcal K}({\boldsymbol{\beta}})=\{k\in\{1,...,M\}: {\boldsymbol{\beta}}_{G_k}\ne {\mathbf{0}}\}$. The following deterministic result holds.
\begin{proposition}
    \label{prop:glasso-deterministic}
    Let $\lambda>0$ be a tuning parameter.
    On the event
    \begin{equation}
        \left\{ \max_{k=1,...,M} \,\frac 1 n |\mathbb{X}_{G_k}^T {\boldsymbol{\xi}} |_2 \le \frac \lambda 2 \right\},
        \label{eq:glasso-event}
    \end{equation}
    the group LASSO estimator \eqref{eq:def-glasso} with tuning parameter $\lambda$ satisfies
    \begin{equation}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        \le
        \min_{S\subset \{1,...,M\} }
               \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: {\mathcal K}({\boldsymbol{\beta}})=S}
             \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }^2
            + \frac{9 |S| \lambda^2}{4\kappa^2_G(S,3)}
        \right]
        \label{eq:soi-squared-glasso}
    \end{equation}
    with the convention that $a/0=+\infty$ for any $a>0$.
\end{proposition}
\begin{proof} We follow the same lines as in the proof of Proposition~\ref{prop:lasso-deterministic}. The difference is that
we replace the $\ell_1$ norm by the group LASSO norm $\sum_{k=1}^M |{\boldsymbol{\beta}}_{G_k}|_2$,   and the value $D$ now has the form
 \begin{eqnarray*}
 D&=&2\left( \tfrac 1 n {\boldsymbol{\xi}}^T\mathbb{X} {\boldsymbol{\Delta}} + \lambda\sum_{k=1}^M |{\boldsymbol{\beta}}_{G_k}|_2 - \lambda \sum_{k=1}^M |{\boldsymbol{\hat\beta}}_{G_k}|_2\right)
        - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2.
         \end{eqnarray*}
            Then, on the event \eqref{eq:glasso-event} we obtain
             \begin{eqnarray*}
        D&\le& 2\lambda\left( \frac 1 2 \sum_{k=1}^M |{\boldsymbol{\Delta}}_{G_k}|_2 + \sum_{k=1}^M |{\boldsymbol{\beta}}_{G_k}|_2 -\sum_{k=1}^M |{\boldsymbol{\hat\beta}}_{G_k}|_2\right)
        - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2\\
        &\le& 2\lambda\left( \frac 3 2 \sum_{k\in S} |{\boldsymbol{\Delta}}_{G_k}|_2  -\frac 1 2 \sum_{k\in S^c}|{\boldsymbol{\Delta}}_{G_k}|_2 \right)
        - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2,
           \end{eqnarray*}
           where the last inequality uses the fact that ${\mathcal K}({\boldsymbol{\beta}})=S$. The rest of the proof is quite analogous to that of Proposition~\ref{prop:lasso-deterministic} if we replace there
$\kappa(S,3)$ by $\kappa_G(S,3)$.
\qed
            \end{proof}

            To derive the oracle inequalities for group LASSO, we use the same argument as in the case of LASSO. In order to apply Theorem~\ref{cor3},
we need to find a ``weak bound" $R$ on the error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}} - {\mathbf{f}}}$, i.e., a bound valid
with probability at least $1/2$. The next lemma gives a range of values of $\lambda$ such that the event \eqref{eq:glasso-event} holds with probability at least 1/2.  Then, due to Proposition~\ref{prop:glasso-deterministic}, we can take as $R$ the square root of the right hand side of \eqref{eq:soi-squared-glasso}.

Denote by $\|\mathbb{X}_{G_k}\|_{\rm sp}\triangleq \sup_{|{\mathbf{x}}|_2\le 1}|\mathbb{X}_{G_k}{\mathbf{x}}|_2$ the spectral norm of matrix $\mathbb{X}_{G_k}$, and set $\psi^*  =\max_{k=1,...,M}\|\mathbb{X}_{G_k}\|_{\rm sp}/\sqrt{n}$.

\begin{lemma} \label{lem:group}
Let the diagonal elements of matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ be not greater than 1. If
\begin{equation}\label{lambda:glasso}
\lambda \ge \frac{2\sigma}{\sqrt{n}}\left(\sqrt{T} + \psi^* \sqrt{2\log(2 M)}\right),
\end{equation}
then the event \eqref{eq:glasso-event} has probability at least 1/2.
\end{lemma}
\begin{proof} Note that the function ${\mathbf{u}}\mapsto |\mathbb{X}_{G_k}{\mathbf{u}}|_2$ is $\psi^*\sqrt{n}$-Lipschitz with respect to the Euclidean norm. Therefore, the Gaussian concentration inequality, cf., e.g., \cite[Theorem B.6]{giraud2014introduction}, implies that, for all $x>0$,
$$
\mathbb{P} \left( |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2 \ge \E |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2 + \sigma\psi^*\sqrt{2xn} \right)\le e^{-x}, \qquad k=1,...,M.
$$
Here, $ \E |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2\le \left( \E |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2^2\right)^{1/2}=\sigma \|\mathbb{X}_{G_k}\|_F$, where $\|\cdot\|_F$ is the Frobenius norm. By the assumption of the lemma, all columns of $\mathbb{X}$ have the Euclidean norm at most~$\sqrt{n}$. Since $\mathbb{X}_{G_k}$ is composed from $T$ columns of  $\mathbb{X}$ we have $\|\mathbb{X}_{G_k}\|_F^2 \le nT$, so that $ \E |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2\le\sigma \sqrt{nT}$ for $k=1,...,M$. Thus, for all $x>0$,
$$
\mathbb{P} \left( |\mathbb{X}_{G_k}{\boldsymbol{\xi}}|_2 \ge \sigma (\sqrt{nT} +\psi^*\sqrt{2xn}) \right)\le e^{-x}, \qquad k=1,...,M,
$$
and the result of the lemma follows by application of the union bound.
\qed
\end{proof}

Combining Proposition~\ref{prop:glasso-deterministic}, Lemma~\ref{lem:group} and Theorem~\ref{cor3} we get the following result.

\begin{theorem}
    \label{thm:glasso}
    Assume that the diagonal elements of matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ are not greater than 1. Let $\lambda$ be such that \eqref{lambda:glasso} holds.
    Then for any $\delta\in(0,1)$, the group LASSO estimator \eqref{eq:def-glasso} with tuning parameter $\lambda$
    satisfies, with probability at least $1-\delta$, the oracle inequality \eqref{eq:all-delta-lasso} with $\kappa(S,3)$ replaced by $\kappa_G(S,3)$, and $\supp({\boldsymbol{\beta}})$ replaced by ${\mathcal K}({\boldsymbol{\beta}})$. Furthermore, it satisfies \eqref{eq:all-delta-lasso-bis} with the same modifications.
\end{theorem}

We can consider in a similar way a more general class of penalties generated by cones \cite{micchelli}. Let ${\mathcal A}$ be a convex cone in $(0,+\infty)^p$. For any $\beta\in \R^p$, set
\begin{equation}
\|\beta\|_{\mathcal A} \triangleq \inf_{a\in {\mathcal A}} \frac12 \sum_{j=1}^p\left(\frac{\beta_j^2}{a_j} +a_j\right)= \inf_{a\in {\mathcal A}: |a|_1\le 1}\sqrt{\sum_{j=1}^p\frac{\beta_j^2}{a_j}}
 \label{eq:cone-penalty}
         \end{equation}
and consider the penalty $F(\beta)=\lambda \|\beta\|_{\mathcal A}$ where $\lambda>0$. The function $\|\cdot\|_{\mathcal A}$ is convex since it is a minimum of a convex function of the couple $(\beta,a)$ over $a$ in a convex set \cite[Corollary 2.4.5]{hiriart_lemarechal}. In view of its positive homogeneity, it is also a norm.
The group LASSO penalty is a special case of \eqref{eq:cone-penalty} corresponding to the cone of all vectors $a$ with positive components that are constant on the blocks $G_k$ of the partition. Many other interesting examples are given in \cite{micchelli,maurer_pontil}, see also \cite[Section 6.9]{vdgeer}.

Such penalties induce a class of admissible sets of indices $S\subset \{1,...,p\}$. This is a generalization of the sets of indices corresponding to vectors $\beta$ that vanish on entire blocks in the case of group LASSO.  Roughly speaking, the set of indices $S$ would be suitable for our construction if, for any $a\in {\mathcal A}$, the vectors $a_S$ and $a_{S^c}$ belong to ${\mathcal A}$.
However, this is not possible since, by definition, the elements of ${\mathcal A}$ must have positive components. Thus, we slightly modify this condition on~$S$. A~set $S\subset \{1,...,p\}$ will be called {\it admissible} with respect to ${\mathcal A}$ if, for any $a\in {\mathcal A}$ and any $\epsilon>0$, there exist vectors $b_{S^c}\in \R^p$ and $b_{S}\in \R^p$ supported on $S^c$ and $S$ respectively with all components in $(0,\epsilon)$ and such that
$a_S+b_{S^c}\in {\mathcal A}$, and $a_{S^c}+b_{S}\in {\mathcal A}$.

The following lemma shows that, for admissible $S$, the norm $\|\cdot\|_{\mathcal A}$ has the same decomposition property as the $\ell_1$ norm.

\begin{lemma}\label{lem2}
If $S\subset \{1,...,p\}$ is an {\it admissible} set of indices with respect to ${\mathcal A}$, then
$$
\|\beta\|_{\mathcal A} = \|\beta_S\|_{\mathcal A} + \|\beta_{S^c}\|_{\mathcal A}.
$$
\end{lemma}
\begin{proof}
As $\|\cdot\|_{\mathcal A} $ is a norm, we have to show only that $
\|\beta\|_{\mathcal A} \ge \|\beta_S\|_{\mathcal A} + \|\beta_{S^c}\|_{\mathcal A}.
$ Obviously,
\begin{equation}
\|\beta\|_{\mathcal A} \ge \inf_{a\in {\mathcal A}} \frac12 \sum_{j\in S}\left(\frac{\beta_j^2}{a_j} +a_j\right)+\inf_{a\in {\mathcal A}} \frac12 \sum_{j\in S^c}\left(\frac{\beta_j^2}{a_j} +a_j\right).
 \label{eq:lem1}
         \end{equation}
Since $S$ is admissible, adding the sum $\sum_{j\in S^c}a_j$ under the infimum in the first term on the right hand side does not change the result:
\begin{eqnarray*}
\inf_{a\in {\mathcal A}} \frac12 \sum_{j\in S}\left(\frac{\beta_j^2}{a_j} +a_j\right) = \inf_{a\in {\mathcal A}} \frac12 \left[\sum_{j\in S}\left(\frac{\beta_j^2}{a_j} +a_j\right) + \sum_{j\in S^c}a_j \right] =  \|\beta_S\|_{\mathcal A}.
\end{eqnarray*}
The second term on the right hand side of \eqref{eq:lem1} is treated analogously.
\qed
\end{proof}
Next, for any $S\subset\{1,...,p\}$ and $c_0> 0$,
we need an analog of the RE constant corresponding to the penalty $\|\cdot\|_{\mathcal A}$, cf. \cite{vdgeer}. We define
$q_{\mathcal A}(S,c_0)\ge 0$ by the formula
\begin{equation}
    q^2_{\mathcal A}(S,c_0) \triangleq \min_{{\boldsymbol{\Delta}}\in\mathcal C'(S,c_0)} \frac{\norm{\mathbb{X}{\boldsymbol{\Delta}}}^2}{\|{\boldsymbol{\Delta}}_S\|_{\mathcal A}^2},
    \label{eq:def-kappa-cone}
\end{equation}
where $\mathcal C'(S,c_0)$ is the cone
$$
\mathcal C' (S,c_0)\triangleq \{{\boldsymbol{\Delta}}\in\R^p: \|{\boldsymbol{\Delta}}_{S^c}\|_{\mathcal A}\le c_0\|{\boldsymbol{\Delta}}_{S}\|_{\mathcal A}\}.
$$
As in the previous examples, our starting point will be  a deterministic bound that holds on a suitable event. This result  is analogous to Propositions \ref{prop:lasso-deterministic} and \ref{prop:glasso-deterministic}. To state it, we define
$$
\|{\boldsymbol{\beta}}\|_{\mathcal A, \circ} = \sup_{a\in {\mathcal A}: |a|_1\le 1}\sqrt{\sum_{j=1}^p a_j \beta_j^2}
$$
which is the dual norm to $\|\cdot\|_{\mathcal A}$.
\begin{proposition}
    \label{prop:cone-deterministic}
    Let ${\mathcal A}$ be a convex cone in $(0,+\infty)^p$, and let ${\mathbb S}_{\mathcal A}$ be set of all $S\subset \{1,...,p\}$ that are admissible with respect to ${\mathcal A}$.
    Let $\lambda>0$ be a tuning parameter.
    On the event
    \begin{equation}
        \left\{\|\tfrac 1 n \mathbb{X}^T {\boldsymbol{\xi}}\|_{\mathcal A, \circ}  \le \frac \lambda 2 \right\},
        \label{eq:cone-event}
    \end{equation}
    the estimator \eqref{eq:def-hbeta-pen} with penalty $F(\cdot)=\lambda\|\cdot\|_{\mathcal A}$ satisfies
    \begin{equation}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        \le
        \min_{S\in {\mathbb S}_{\mathcal A}}
               \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp ({\boldsymbol{\beta}})=S}
             \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }^2
            + \frac{9 \lambda^2}{4 q^2_{\mathcal A}(S,3)}
        \right]
        \label{eq:soi-squared-cone}
    \end{equation}
    with the convention that $a/0=+\infty$ for any $a>0$.
\end{proposition}
\begin{proof} \smartqed In view of Lemma \ref{lem2}, we can follow exactly the lines of the proof of  Proposition~\ref{prop:lasso-deterministic} by replacing there the $\ell_1$ norm by the norm $\|\cdot\|_{\mathcal A}$ and taking into account the duality bound $\tfrac 1 n {\boldsymbol{\xi}}^T\mathbb{X} \Delta\le \|\tfrac 1 n \mathbb{X}^T {\boldsymbol{\xi}}\|_{\mathcal A, \circ} \|\Delta\|_{\mathcal A}$. At the end, instead of \eqref{eq:last}, we use that
 \begin{equation*
        3\lambda\|\Delta_S\|_{\mathcal A}
        \le
        3 \lambda \frac{\norm{\mathbb{X}{\boldsymbol{\Delta}}}}{q_{\mathcal A}(S,3)}
        \le
        \frac{9\lambda^2}{4 q_{\mathcal A}^2(S,3)} + \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2.
    \end{equation*}
\qed
\end{proof}
Our next step is to find a range of values of $\lambda$ such that the event \eqref{eq:cone-event} holds with probability at least 1/2. We will consider only the case when ${\mathcal A}$ is a polyhedral cone, which corresponds to many examples considered in \cite{micchelli,maurer_pontil}. We will denote by ${\mathcal A}'$ the closure of the set ${\mathcal A}\cap \{a: |a|_1\le 1\}$.
\begin{lemma} \label{lem:cone}
Let the diagonal elements of matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ be not greater than 1. Let ${\mathcal A}$ be a polyhedral cone, and let ${\mathcal E}_{\mathcal A'}$ be the set of extremal points of ${\mathcal A}'$. If
\begin{equation}\label{lambda:cone}
\lambda \ge \frac{2\sigma}{\sqrt{n}}\left(1 +  \sqrt{2\log(2 |{\mathcal E}_{\mathcal A'}|)}\right),
\end{equation}
then the event \eqref{eq:cone-event} has probability at least 1/2.
\end{lemma}
\begin{proof} Denote by $\eta_j=\tfrac 1 n e_j^T\mathbb{X}^T {\boldsymbol{\xi}}$ the $j$th component of $\tfrac 1 n \mathbb{X}^T {\boldsymbol{\xi}}$. We have
\begin{equation}\label{proof:lambda:cone}
\|\tfrac 1 n \mathbb{X}^T {\boldsymbol{\xi}}\|_{\mathcal A, \circ}  = \sup_{a\in {\mathcal A}: |a|_1\le 1}\sqrt{\sum_{j=1}^p a_j \eta_j^2}= \max_{a\in {\mathcal E}_{\mathcal A'}} \sqrt{\sum_{j=1}^p a_j \eta_j^2},
\end{equation}
where the last equality is due to the fact that ${\mathcal A'}$ is a convex polytope. Let ${\mathbf{z}}={\boldsymbol{\xi}}/\sigma$ be a standard normal $\mathcal N({\mathbf{0}},I_{n\times n})$ random vector. Note that, for all $a$ such that $|a|_1\le 1$, the function $f_a({\mathbf{z}}) = \sigma \sqrt{\sum_{j=1}^p a_j (\tfrac 1 n e_j^T\mathbb{X}^T {\mathbf{z}})^2}$ is $\sigma/\sqrt{n}$-Lipschitz with respect to the Euclidean norm. Indeed,
\begin{eqnarray*}
|f_a({\mathbf{z}})-f_a({\mathbf{z}}')|&\le&{\sigma}\sqrt{\sum_{j=1}^p a_j (\tfrac 1 n e_j^T\mathbb{X}^T ({\mathbf{z}}-{\mathbf{z}}'))^2}\le  \frac{\sigma}{\sqrt{n}} \sqrt{\sum_{j=1}^p a_j \| \mathbb{X} e_j \|^2 |{\mathbf{z}}-{\mathbf{z}}'|_2^2}
\\
&\le & \frac{\sigma}{\sqrt{n}} |{\mathbf{z}}-{\mathbf{z}}'|_2,\qquad \forall \ |a|_1\le 1,
\end{eqnarray*}
since $\max_j  \| \mathbb{X} e_j \|^2\le 1$ by the assumption of the lemma. Therefore, the Gaussian concentration inequality, cf., e.g., \cite[Theorem B.6]{giraud2014introduction}, implies that, for all $x>0$,
$$
\mathbb{P} \left( f_a({\mathbf{z}})  \ge \E  f_a({\mathbf{z}}) + \sigma\sqrt{\frac{2x}{n}} \right)\le e^{-x}.
$$
Here, $f_a({\mathbf{z}})=\sqrt{\sum_{j=1}^p a_j \eta_j^2}$ and  $\E \sqrt{\sum_{j=1}^p a_j \eta_j^2}\le \left(\E \sum_{j=1}^p a_j \eta_j^2\right)^{1/2} \le \sigma/\sqrt{n}$ for all $a$ in the positive orthant such that $|a|_1\le 1$ where we have used that $\E\eta_j^2\le \sigma^2/n$ for $j=1,...,p$. Thus, for all $a$ in the positive orthant such that $|a|_1\le 1$ and all $x>0$ we have
$$
\mathbb{P} \left( \sqrt{\sum_{j=1}^p a_j \eta_j^2} \ge  \frac{\sigma}{\sqrt{n}} ( 1+\sqrt{2x}) \right)\le e^{-x}.
$$
The result of the lemma follows immediately from this inequality, \eqref{proof:lambda:cone} and the union bound.
\qed
\end{proof}
Finally, from  Proposition~\ref{prop:cone-deterministic}, Lemma~\ref{lem:cone} and Theorem~\ref{cor3} we get the following theorem.

\begin{theorem}
    \label{thm:cone}
    Assume that the diagonal elements of matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ are not greater than 1. Let $\lambda$ be such that \eqref{lambda:cone} holds.
    Then for any $\delta\in(0,1)$, the estimator \eqref{eq:def-hbeta-pen} with penalty $F(\cdot)=\lambda\|\cdot\|_{\mathcal A}$
    satisfies
    \begin{equation*}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{S\in {\mathbb S}_{\mathcal A} }
               \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: \supp({\boldsymbol{\beta}})=S}
             \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }
            + \frac{3  \lambda}{2q_{\mathcal A}(S,3)}
        \right]
        + \frac{\sigma \Phi^{-1}(1-\delta)}{\sqrt{n}}
        \label{eq:all-delta-cone}
    \end{equation*}
    with probability at least $1-\delta$. Furthermore,
    \begin{equation*}
      \E  \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{S\in {\mathbb S}_{\mathcal A} }
               \left[
        \min_{{\boldsymbol{\beta}}\in\R^p:\supp({\boldsymbol{\beta}})=S}
             \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }
            + \frac{3 \lambda}{2q_{\mathcal A}(S,3)}
        \right]
        + \frac{\sigma}{ \sqrt{2 \pi n}}.
        \label{eq:all-delta-cone-bis}
         \end{equation*}
\end{theorem}
Note that, in contrast to Theorems \ref{thm:lasso} and \ref{thm:glasso}, Theorem \ref{thm:cone} is a less explicit result.
Indeed, the form of the oracle inequalities depends on the value $q_{\mathcal A}(S,3)$ and, through $\lambda$, on the value
$|{\mathcal E}_{\mathcal A'}|$. Both quantities are solutions of nontrivial geometric problems depending on the form of the cone ${\mathcal A}$.  Little is known about them. Note also that the knowledge of $|{\mathcal E}_{\mathcal A'}|$ (or of an upper bound on it) is required to find the appropriate~$\lambda$.

\section{Application to SLOPE}
\label{s:slope}

This section studies the SLOPE estimator introduced in \cite{bogdan}, which is yet another convex regularized estimator.
Define the norm $|\cdot|_*$ in $\R^p$ by the relation
\begin{equation*}
    |{\mathbf{u}}|_* \triangleq \max_{\phi} \sum_{j=1}^p  \mu_j u_{\phi(j)} ,
    \qquad
    {\mathbf{u}}=(u_1,...,u_p) \in\R^p,
\end{equation*}
where the maximum is taken over all permutations $\phi$ of $\{1,...,p\}$ and $\mu_j>0$ are some weights. In what follows,
we assume that
\begin{equation*}
    \mu_j = \sigma\sqrt{\log(2p/j) /n}, \qquad j=1,...,p.
\end{equation*}
For any ${\mathbf{u}}=(u_1,...,u_p)\in\R^p$,
let $u_1^*\ge u_2^*\ge...\ge u_p^*\ge 0$
be a non-increasing rearrangement of $|u_1|,...,|u_p|$.
Then the norm $|\cdot|_*$ can be equivalently defined  as
\begin{equation*}
    |{\mathbf{u}}|_* = \sum_{j=1}^p  \mu_j u_i^*,
    \qquad
    {\mathbf{u}}=(u_1,...,u_p) \in\R^p.
\end{equation*}
Given a tuning parameter $A>0$, we define the SLOPE estimator ${\boldsymbol{\hat\beta}}$
as a solution of the optimization problem
\begin{equation}
    {\boldsymbol{\hat\beta}} \in \argmin_{{\boldsymbol{\beta}}\in\R^p}\left(
    \norm{ \mathbf{y}-\mathbb{X}{\boldsymbol{\beta}}}^2
    + 2 A |{\boldsymbol{\beta}}|_*\right).
    \label{eq:def-slope}
\end{equation}
As $|\cdot|_*$ is a norm, it is a convex function
so Proposition \ref{prop3} and Theorem \ref{cor3} apply.
For any $s\in \{1,...,p\}$ and any $c_0>0$, the Weighted Restricted Eigenvalue (WRE) constant $\vartheta(s,c_0)\ge 0$ is defined as follows:
\begin{equation*}
    \vartheta^2(s,c_0)
    \triangleq
    \min_{
        {\boldsymbol{\Delta}}\in\R^p:
        \sum_{j=s+1}^p \mu_j \delta_j^* \le c_0 (\sum_{j=1}^s \mu_j^2)^{1/2} |{\boldsymbol{\Delta}}|_2
    }
    \frac{\norm{\mathbb{X}{\boldsymbol{\Delta}}}^2}{|{\boldsymbol{\Delta}}|_2^2}.
\end{equation*}
The $WRE(s,c_0)$ condition is said to hold if $\vartheta(s,c_0)>0$.

We refer the reader to  \cite{bellec2016slope}
for a comparison of this RE-type constant with other restricted eigenvalue constants such as \eqref{eq:def-kappa}. A high level message is that the WRE condition is only slightly stronger than the RE condition.
It is also established in \cite{bellec2016slope}
that a large class of random matrices $\mathbb{X}$ with independent and possibly anisotropic rows satisfies the condition $\vartheta(s,c_0) > 0$ with high probability
provided that $n > C s \log(p/s)$ for some absolute constant $C>0$.

For $j=1,...,p$, let $g_j = \frac{1}{\sqrt n}{\boldsymbol{e}}_j \mathbb{X}^T {\boldsymbol{\xi}}$, where ${\boldsymbol{e}}_j$ is the $j$th canonical basis vector in $\R^p$,
and let $g_1^*\ge g_2^*\ge...\ge g_p^*\ge 0$
be a non-increasing rearrangement of $|g_1|,...,|g_p|$.
Consider the event
\begin{equation}
\Omega_* \triangleq
    \cap_{j=1}^p
    \left\{
        g_j^*
        \le 4\sigma\sqrt{\log(2p/j)}
    \right\} .
    \label{eq:def-Omega-star}
\end{equation}
The next proposition establishes a deterministic result for the SLOPE estimator on the event \eqref{eq:def-Omega-star}.

\begin{proposition}
    \label{prop:deterministic-slope}
    On the event \eqref{eq:def-Omega-star}, the SLOPE estimator ${\boldsymbol{\hat\beta}}$ defined by \eqref{eq:def-slope}
    with $A\ge8$ satisfies
    \begin{equation}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        \le
        \min_{s \in\{1,...,p\}} \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: |{\boldsymbol{\beta}}|_0 \le s}
                   \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }^2
            + \frac{9 A^2 \sigma^2 s \log(2ep/s)}{4 n \vartheta^2(s,3)}
        \right]
        \label{eq:soi-squared-slope}
    \end{equation}
    with the convention that $a/0=+\infty$ for any $a>0$.
\end{proposition}
\begin{proof
    \smartqed
    Let $s\in\{1,...,p\}$ and ${\boldsymbol{\beta}}$ be minimizers of the right hand side of
    \eqref{eq:soi-squared-slope} and let ${\boldsymbol{\Delta}} \triangleq {\boldsymbol{\hat\beta}} - {\boldsymbol{\beta}}$. We will assume that $\vartheta(s,3)>0$ since otherwise the claim is trivial.
     From Lemma \ref{lem1} with $F({\boldsymbol{\beta}})= A|{\boldsymbol{\beta}}|_*$ we have
     \begin{equation*}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }^2
        -
        \norm{
            \mathbb{X}{\boldsymbol{\beta}}
            -
            {\mathbf{f}}
        }^2
        \le 2\left( \tfrac 1 n {\boldsymbol{\xi}}^T\mathbb{X} {\boldsymbol{\Delta}} + A |{\boldsymbol{\beta}}|_* - A|{\boldsymbol{\hat\beta}}|_*\right)
        - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2
        \triangleq D.
    \end{equation*}
    On the event \eqref{eq:def-Omega-star},
    the right hand side of the previous display satisfies
    \begin{equation*}
       D
        \le
        2A \left[
            \frac 1 2|{\boldsymbol{\Delta}}|_*
            + |{\boldsymbol{\beta}}|_* - |{\boldsymbol{\hat\beta}}|_*
        \right] - \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2.
    \end{equation*}
    By \cite[Lemma A.1]{bellec2016slope},
    $
    \frac 1 2|{\boldsymbol{\Delta}}|_*
        + |{\boldsymbol{\beta}}|_* - |{\boldsymbol{\hat\beta}}|_*
        \le
        \frac 3 2 (\sum_{j=1}^s \mu_j^2)^{1/2} |{\boldsymbol{\Delta}}|_2 - \frac 1 2 \sum_{j=s+1}^p \mu_j \delta_j^*
    $.

    If $3 (\sum_{j=1}^s \mu_j^2)^{1/2} |{\boldsymbol{\Delta}}|_2 \le  \sum_{j=s+1}^p \mu_j \delta_j^*$,
    then the claim follows trivially.
   If the reverse inequality holds, we have $|{\boldsymbol{\Delta}}|_2 \le \norm{\mathbb{X}{\boldsymbol{\Delta}}}/\vartheta(s,3)$.
    This implies
    \begin{equation*}
        3A  (\sum_{j=1}^s \mu_j^2)^{1/2}   |{\boldsymbol{\Delta}}|_2
        \le
        \frac{9 A^2\sum_{j=1}^s \mu_j^2}{4\vartheta^2(s,3)} + \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2
        \le
        \frac{9 A^2 \sigma^2s\log(2ep/s)}{4 n \vartheta^2(s,3)} + \norm{\mathbb{X}{\boldsymbol{\Delta}}}^2,
    \end{equation*}
    where for the last inequality we have used that, by Stirling's formula,
    $\log(1/s!) \le s\log(e/s)$ and thus $\sum_{j=1}^s \mu_j^2 \le \sigma^2 s\log(2ep/s)/n$. Combining the last three displays yields the result.
    \qed
\end{proof}

We now follow the same argument as in Sections \ref{s:lasso} and \ref{s:glasso}. In order to apply Theorem~\ref{cor3},
we need to find a ``weak bound" $R$ on the error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}} - {\mathbf{f}}}$, i.e., a bound valid
with probability at least $1/2$. If the event $\Omega_*$ holds with probability at least 1/2 then, due to Proposition~\ref{prop:deterministic-slope}, we can take as $R$ the square root of the right hand side of \eqref{eq:soi-squared-slope}.
Since ${\boldsymbol{\xi}}\sim \mathcal N({\mathbf{0}}, \sigma^2 I_{n\times n})$
and the diagonal elements of $\frac 1 n
\mathbb{X}^T \mathbb{X}$ are bounded by 1,
the random variables  $g_1,...,g_p$
are centered Gaussian with variance
    at most $\sigma^2$.
The following proposition from \cite{bellec2016slope} shows
that the event \eqref{eq:def-Omega-star} has probability at least $1/2$.

\begin{proposition}{\rm\cite{bellec2016slope}}
    \label{prop:proba-estimate-slope}
    If $g_1,...,g_p$ are centered Gaussian random variables with variance
    at most $\sigma^2$,
    then the event
    \eqref{eq:def-Omega-star}
    has probability at least $1/2$.
\end{proposition}
Proposition \ref{prop:proba-estimate-slope} cannot be substantially improved
without additional assumptions.
To see this, let $\eta\sim\mathcal N(0,1)$
and set $g_j = \sigma \eta $ for all $j=1,...,p$.
The random variables $g_1,...,g_p$ satisfy the assumption of Proposition \ref{prop:proba-estimate-slope}.
In this case, the event \eqref{eq:def-Omega-star} satisfies
$\mathbb P ( \Omega_*) = \mathbb P( |\eta| \le 4\sqrt{\log 2})$
so that $\mathbb P(\Omega_*)$ is an absolute constant.
Thus, without additional assumptions
on the random variables $g_1,...,g_p$,
there is no hope to prove a lower bound better than $\mathbb P(\Omega_*) \ge c$ for some fixed numerical constant $c\in (0,1)$ independent of $p$.

By combining Propositions \ref{prop:deterministic-slope}
and \ref{prop:proba-estimate-slope},
we obtain that the oracle bound \eqref{eq:soi-squared-slope}
holds with probability at least $1/2$.
At first sight, this result is uninformative as it cannot
even imply the consistency, i.e., the convergence of the error $\norm{\mathbb{X}{\boldsymbol{\hat\beta}}
- {\mathbf{f}}}$ to 0 in probability.
But the SLOPE estimator is a convex regularized estimator
and the argument of Section \ref{s:machinery} yields
that a risk bound with probability $1/2$ is in fact
very informative:
Theorem \ref{cor3} immediately
implies the following oracle inequality for any confidence level $1-\delta$ as well as an oracle inequality in expectation.

\begin{theorem}
    \label{thm:slope}
    Assume that the diagonal elements of the matrix $\frac 1 n
    \mathbb{X}^T \mathbb{X}$ are not greater than 1.
    Then for all $\delta\in(0,1)$, the SLOPE
    estimator ${\boldsymbol{\hat\beta}}$ defined by \eqref{eq:def-slope} with tuning parameter $A\ge 8$
    satisfies
    \begin{equation*}
        \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{s \in\{1,...,p\}}
        \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: |{\boldsymbol{\beta}}|_0 \le s}
            \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }
            + \frac{3\sigma A }{2 \vartheta(s,3)}
              \sqrt{\frac{s \log(2ep/s)}{n}}
        \right]
            + \frac{\sigma \Phi^{-1}(1-\delta)}{\sqrt{n}}
        \label{eq:all-delta-slope}
    \end{equation*}
    with probability at least $1-\delta$. Furthermore,
    \begin{equation*}
      \E  \norm{
            \mathbb{X}{\boldsymbol{\hat\beta}}
            -
            {\mathbf{f}}
        }
        \le
        \min_{s \in\{1,...,p\}}
        \left[
        \min_{{\boldsymbol{\beta}}\in\R^p: |{\boldsymbol{\beta}}|_0 \le s}
            \norm{
                \mathbb{X}{\boldsymbol{\beta}}
                -
                {\mathbf{f}}
            }
            + \frac{3\sigma A }{2 \vartheta(s,3)}
              \sqrt{\frac{s \log(2ep/s)}{n}}
        \right]
               + \frac{\sigma}{ \sqrt{2 \pi n}}.
        \label{eq:}
         \end{equation*}
\end{theorem}
  The proof is similar to that of Theorem \ref{thm:lasso},
    and thus it is omitted. Remarks analogous to the discussion after Theorem \ref{thm:lasso} apply here as well.

\section{Generalizations and extensions}\label{s:Generalizations}

The list of applications of Theorem~\ref{cor3} considered in the previous sections can be further extended. For instance, the same techniques can be applied when, instead of prediction by $\mathbb{X} {\boldsymbol{\beta}}$ for ${\mathbf{f}}$, one uses a trace regression prediction. In this case, the estimator ${\boldsymbol{\hat\beta}}\in\R^{m_1\times m_2}$ is a matrix satisfying
\begin{equation}
    {\boldsymbol{\hat\beta}}(\mathbf{y}) \in \argmin_{{\boldsymbol{\beta}}\in\R^{m_1\times m_2}} \left(\frac1n \sum_{i=1}^n (y_i - {\rm trace}(X_i^T{\boldsymbol{\beta}}))^2 + 2 F({\boldsymbol{\beta}})\right),
    \label{eq:def-hbeta-trace-reg}
\end{equation}
where $X_1,...,X_n$ are given deterministic matrices in  $\R^{m_1\times m_2}$, $F:\R^{m_1\times m_2}\to \R$ is a convex penalty. A popular example of $F({\boldsymbol{\beta}})$ in this context is the nuclear norm of ${\boldsymbol{\beta}}$.  The methods of this paper apply for such an estimator as well, and we obtain analogous bounds. Indeed, \eqref{eq:def-hbeta-trace-reg} can be rephrased as \eqref{eq:def-hbeta-pen} by vectorizing ${\boldsymbol{\beta}}$ and defining a new matrix~$\mathbb{X}$. Thus, Theorem~\ref{cor3} can be applied. Next, note that the examples of application of Theorem~\ref{cor3} considered above required only two ingredients: a deterministic oracle inequality and a weak bound on the probability of the corresponding random event.  The deterministic bound is obtained here quite analogously to the previous sections or following the same lines as in \cite{koltchinskii2011nuclear} or in \cite[Corollary 12.8]{vdgeer}. A bound on the probability of the random event can be also borrowed from \cite{koltchinskii2011nuclear}.  We omit further details.

Finally, we observe that Proposistion~\ref{prop3} and Theorem~\ref{cor3} generalize to Hilbert space setting.
Let $H, H'$ be two Hilbert spaces and $\mathbb{X} : H'\to H$ a bounded linear operator. If $H$ is equipped with a norm $\|\cdot\|_H$, and $F:H'\to [0,+\infty]$ is a proper convex function, consider for any $\mathbf{y}\in H$ a solution
\begin{equation}
    {\boldsymbol{\hat\beta}}(\mathbf{y}) \in \argmin_{{\boldsymbol{\beta}}\in H'} \left(\|\mathbf{y} - \mathbb{X} {\boldsymbol{\beta}}\|_H^2 + 2 F({\boldsymbol{\beta}})\right).
    \label{eq:def-hbeta-hilbert}
\end{equation}
\begin{proposition}
Under the above assumptions, any solution  ${\boldsymbol{\hat\beta}}(\mathbf{y})$ of \eqref{eq:def-hbeta-hilbert} satisfies $\|\mathbb{X} ({\boldsymbol{\hat\beta}}(\mathbf{y})-{\boldsymbol{\hat\beta}}(\mathbf{y}'))\|_H\le \|\mathbf{y}-\mathbf{y}'\|_H$.
\end{proposition}
The proof of this proposition is completely analogous to that of Proposistion~\ref{prop3}. It suffices to note that the properties of convex functions used in the proof of Proposistion~\ref{prop3} are valid when these functions are defined on a Hilbert space, cf. \cite{peypouquet2015convex}.
This and the fact that the Gaussian concentration property extends to Hilbert space valued Gaussian variables \cite[Theorem 6.2]{lifshits} immediately imply a Hilbert space analog of Theorem~\ref{cor3}.

\bibliographystyle{plainnat}


\section{Introduction}
The spectrum of excited nucleon states reflects the dynamics of QCD in the non-perturbative regime. It has been studied for many years using pion beams. However, the spectrum of known nucleon resonances is in conflict with predictions from quark models \cite{isgur77,loring01}. Most obvious is the missing resonance problem: the fact that more states are predicted by  models at higher masses than have been observed experimentally. But also the ordering of excited states with positive and negative parity is partly in disagreement with experiments, the most prominent example being the $N(1440)\,1/2^+$ which is predicted by most quark models to be heavier than the $N(1535)\,1/2^-$. QCD calculations on the lattice \cite{edwards11}, though using unphysically large quark masses, yield a similar pattern as the non-relativistic quark model. Measuring the properties of the known resonances more precisely and searching for new resonances is essential to understanding the discrepancies between theory and experiment.

Photoproduction experiments allow access to resonances with small $\pi N$ couplings and therefore have great potential to observe the missing resonances. The contributing resonances are extracted from the measured data in a partial wave analysis (PWA). To determine the contributing amplitudes in an unambiguous way, a complete experiment \cite{chiang97} is needed, which requires the measurement of polarisation observables.
In this paper, a selection of recent measurements of single and double polarisation observables accessible with linearly or circulary polarised photon beam and a longitudinally or transversely polarised proton target is shown, and their impact on the PWA is discussed.

\section{Experimental setup}
The data presented here were obtained with the CBELSA/TAPS experiment at ELSA \cite{hillert06}. A linearly polarised photon beam was produced from the incident $\SI{3.2}{GeV}$ electron beam via coherent bremsstrahlung off a carefully aligned diamond crystal \cite{elsner09}. For a coherent edge at $E_{\gamma} = \SI{950}{MeV}$ a maximum polarisation of $\SI{65}{\percent}$ was reached. A circularly polarised photon beam was produced from a longitudinally polarised $\SI{2.4}{GeV}$ electron beam provided by ELSA. The polarisation was measured with a M\o ller polarimeter, a maximum electron polarisation of $\SI{64}{\percent}$ was reached.
The electrons, after hitting the radiator target, passed through a magnet onto a tagging hodoscope which defined the energy of the bremsstrahlung photons. The photon beam impinged on a frozen spin butanol target \cite{bradtke99} providing transversely polarised protons with an average target polarisation degree of $\SI{74}\%$.

\begin{figure}[b]
	\centering
	\includegraphics[width=.9\textwidth]{setup}
	\caption{The experimental setup of the CBELSA/TAPS experiment.}
	\label{fig:setup}
\end{figure}
The detector system, which is shown in Figure~\ref{fig:setup}, consisted of two electromagnetic calorimeters, the Crystal Barrel \cite{aker92} and the MiniTAPS detector \cite{novotny91}, together covering the polar angle range from $1^\circ$ to $156^\circ$ and the full azimuthal angle. For charged particle identification, a three-layer scintillating fibre detector \cite{suft05} surrounding the target, and plastic scintillators in forward direction could be used. The detector setup provided a high detection efficiency for photons and is therefore ideally suited to measure single and double polarisation observables in reactions with neutral mesons decaying into photons in the final state.

\section{Results}
The cross-section for photoproduction of single pseudoscaler mesons with a polarised beam off a polarised target can be written in the form \cite{barker75}
\begin{align}
	\label{eq:xsect}
	\frac{\ensuremath{\mathrm{d}}\sigma}{\ensuremath{\mathrm{d}}\varOmega} = \left(\frac{\ensuremath{\mathrm{d}}\sigma}{\ensuremath{\mathrm{d}}\varOmega}\right)_{0} \cdot \Big[
		& {1} - {\varSigma}{\delta_\ell\cos(2\phi)} + {T}{\varLambda_y} - {P}{\varLambda_y\delta_\ell\cos(2\phi)} \\
		& - {E}{\varLambda_z\delta_\odot} + {F}{\varLambda_x\delta_\odot} + {G}{\varLambda_z\delta_\ell\sin(2\phi)} + {H}{\varLambda_x\delta_\ell\sin(2\phi)} \Big], \nonumber
\end{align}
where $\left(\frac{\ensuremath{\mathrm{d}}\sigma}{\ensuremath{\mathrm{d}}\varOmega}\right)_0$ is the unpolarised cross section, $\delta_\ell$ ($\delta_\odot$) denotes the linear (circular) polarisation degree of the photon beam, and $\varLambda_{x,y,z}$ is the polarisation degree of the target protons in the centre-of-mass (CM) coordinate frame. In a polarised butanol (C$_4$H$_9$OH) target, not only the polarised protons, but also unpolarised nucleons in the C and O nuclei contribute to the count rate. This effectively reduces the target polarisation and can be taken into account by the dilution factor $d$: $\varLambda \to d\,\varLambda$. To determine $d$, the background contribution from bound nucleons needs to be determined, e.g.\@ using a background measurement with a carbon target. For details, see e.g.\@ \cite{gottschall14,hartmann15}.

\subsection{\boldmath $\pi^0$ photoproduction}
\begin{figure}[b]
	\centering%
	\hfill%
	\includegraphics[width=.4\textwidth]{pi0_E}%
	\hfill%
	\includegraphics[width=.4\textwidth]{pi0_G}%
	\hfill%
	\vspace*{-2mm}%
	\caption{Results for the observables $E$ (left) \cite{gottschall14} and $G$ (right) \cite{thiel12,thiel16} for four different angular bins, compared to different PWA predictions: MAID (green, dotted) \cite{maid07}, SAID CM12 (red, dashed-dotted) \cite{said12}, BnGa 2011-02 (black, solid) \cite{anisovich12}, and J\"uBo 13-01 (blue, dashed) \cite{roenchen14}.}%
	\label{fig:pi0_EG}%
\end{figure}
With circularly polarised photons and longitudinally polarised protons, the helicity asymmetry $E$ is accessible. It can be determined from the asymmetry of events with parallel ($N_{3/2}$) and anti-parallell ($N_{1/2}$) spins of the initial-state particles as
\begin{equation}
	E = \frac{N_{1/2} - N_{3/2}}{N_{1/2} + N_{3/2}} \cdot \frac{1}{d\,\varLambda_z\,\delta_\odot}.
\end{equation}
With linearly polarised photons and logitudinally polarised protons, the double polarisation observable $G$ can be deduced from the correlation between the photon polarisation plane and the scattering plane. The number of events $N$ as a function of the azimuthal angle $\phi$ between the two planes is given by
\begin{equation}
	N(\phi) / N_0 = 1 - \delta_\ell\,\varSigma_\mathrm{eff} \cos(2\phi) + d\,\varLambda_z\,\delta_\ell\,G \sin(2\phi),
\end{equation}
where $N_0$ is given by averaging $N(\phi)$ over $\phi$. $\varSigma_\mathrm{eff}$ mixes the beam asymmetry from free and bound nucleons.
Results for both $E$ and $G$ are shown in Fig.~\ref{fig:pi0_EG} in comparison to different PWA predictions.

With linearly polarised photons and transversely polarised protons, the observables $T$, $P$, and $H$ can be measured simultaneously. In this case, the azimuthal distribution of events is given by
\begin{align}
	N(\phi) / N_0 = 1 &- \delta_\ell\,\varSigma_\mathrm{eff} \cos(2\phi) + d\,\varLambda_T\,T \sin(\phi-\varphi) \\
	                  &- d\,\varLambda_T\,\delta_\ell P\cos(2\phi)\sin(\phi-\varphi) + d\,\varLambda_T\,\delta_\ell H \sin(2\phi)\cos(\phi-\varphi), \nonumber
\end{align}
where $\varphi$ is the azimuthal angle between the target polarisation vector and the photon polarisation plane. Results are shown in Fig.~\ref{fig:pi0_TPH}.
\begin{figure}[t]
	\centering%
	\hfill%
	\includegraphics[height=7.5cm]{pi0_T}%
	\hfill%
	\includegraphics[height=7.5cm]{pi0_P}%
	\hfill%
	\includegraphics[height=7.5cm]{pi0_H}%
	\hfill%
	\vspace*{-2mm}%
	\caption{Results for the observables $T$, $P$, and $H$ \cite{hartmann14,hartmann15} as a function of the scattering angle and the $\gamma p$ invariant mass W (in GeV, only every third bin is shown here). References to earlier data (red points) are given in \cite{anisovich12}, Refs. [49-71] therein. The solid black line represents the BnGa2014 fit \cite{hartmann15}. The data are compared to predictions (dashed curves) from BnGa2011-02 (red) \cite{anisovich12}, MAID (green) \cite{maid07}, SAID CM12 (blue) \cite{said12}, and J\"uBo 2015 (magenta) \cite{roenchen15}.}%
	\label{fig:pi0_TPH}%
\end{figure}

Our data up to $E_{\gamma} = \SI{930}{MeV}$ were used as a basis for an energy-independent PWA \cite{hartmann14}, allowing for the determination of the $N(1520)\,3/2^-$ helicity amplitudes with minimal model dependence.
All the data were included in the BnGa multi-channel PWA, together with further data on other channels.%
\footnote{For a complete list, see \cite{hartmann15}, Ref. [25] therein.}
Starting from the previous solutions BnGa2011-01 and BnGa2011-02 \cite{anisovich12} all parameters were re-optimised. The newly determined multipoles are compatible with the previous ones at the $2\sigma$ level over the full mass range. The errors are significantly reduced, on average by a factor of 2.25 \cite{hartmann15}. The impact of the new data on the BnGa, SAID, and J\"uBo analyses was recently investigated in a joint effort of the analysis groups \cite{pwa16}. To quantify the discrepancy between different analyses, the variance of the 16 (complex) multipole amplitudes $\mathcal{M}$ up to $L=4$ can be used, defined as
\begin{equation}
	\mathrm{var}(1,2) = \frac{1}{2} \sum\limits_{i=1}^{16} \bigl( \mathcal{M}_1(i)-\mathcal{M}_2(i)\bigr) \bigl( \mathcal{M}^*_1(i)-\mathcal{M}^*_2(i)\bigr).
\end{equation}
Once the new data are included, the discrepancy between all three analyses is significantly reduced, as can be seen in Fig.~\ref{fig:pwa_var}.
\begin{figure}[t]
	\centering%
	\sidecaption
	\includegraphics[width=.5\textwidth]{pwa_var}%
	\vspace*{-2mm}%
	\caption{The variance of all three PWAs summed over all $\gamma p \to \pi^0 p$ multipoles up to $L=4$ \cite{pwa16}. The range covered by the new double-polarisation observables is indicated by shaded areas. Over the largest part of the energy range the new data have enforced an improvement of the overall consistency. The improvement is displayed as a light green area and, separately, as difference of the variance. Ranges with an overall deterioration are marked in red.}%
	\label{fig:pwa_var}%
\end{figure}

\subsection{\boldmath $\eta$ photoproduction}
\begin{figure}[b]
	\centering%
	\hfill%
	\includegraphics[height=5.2cm]{eta_T}%
	\hfill%
	\includegraphics[height=5.2cm]{eta_P}%
	\hfill%
	\includegraphics[height=5.2cm]{eta_H}%
	\hfill%
	\vspace*{-2mm}%
	\caption{Preliminary results for the observables $T$, $P$, and $H$ as a function of the scattering angle and the $\gamma p$ invariant mass W (in GeV, only every second bin is shown here). Earlier ELSA data (red) \cite{bock98} and recent MAMI results (green) \cite{akondi14} are shown for comparison. The solid black line represents a preliminary BnGa fit. The data are compared to predictions (dashed curves) from BnGa2011-02 (red) \cite{anisovich12}, MAID (green) \cite{maid07}, SAID GE09 (blue) \cite{mcnicoll10}, and J\"uBo 2015 (magenta) \cite{roenchen15}.}%
	\label{fig:eta_TPH}%
\end{figure}
Preliminary results for the polarisation observables $T$, $P$, and $H$ are shown in Figure~\ref{fig:eta_TPH}.
Large deviations from the data are observed for the predictions from MAID \cite{maid07}, SAID \cite{mcnicoll10}, BnGa2011 \cite{anisovich12}, Gie\ss{}en \cite{shklyar13}, and the J\"uBo model \cite{roenchen15}, emphasising how important these new data are to constrain the amplitudes for $\eta$ photoproduction.

The analysis by the BnGa group of our new data on $T$, $P$, and $H$, together with not yet published data on $E$ and $G$ and further data from Mainz ($T$, $F$) \cite{akondi14} and Jefferson Laboratory \cite{senderovich15} ($E$) is presently ongoing. The results will be published in the near future \cite{mueller16}.

\section{Summary and outlook}
In $\pi^0$ photoproduction, the unprecedented precision of the data significantly reduces the errors of the PWAs, leading to a more precise determination of resonance parameters. In $\eta$ photoproduction, where several observables are now measured for the first time, the new data are crucial to constrain the photoproduction amplitudes. Further reaction channels are also being investigated. In particular multi-meson final states like $p \pi^0 \pi^0$ or $p \pi^0 \eta$ are sensitive to cascade decays of higher-mass resonances via intermediate $N^*$ and $\varDelta^*$ states \cite{sokhoyan15a,sokhoyan15b,mahlberg16}. \medskip

\begin{acknowledgement}%
We thank the technical staff of ELSA, the polarised target group, and the participating institutions for their invaluable contributions to the success of the experiment.
We acknowledge support from the \textit{Deutsche Forschungsgemeinschaft} (SFB/TR16) and \textit{Schweizerischer Nationalfonds}.
\end{acknowledgement}