Tung Duy Luu

Jalal Fadili
email: jalal.fadili@ensicaen.fr

Christophe Chesneau
email: christophe.chesneau@unicaen.fr

Tung Duy Luu
email: duy-tung.luu@ensicaen.fr

Sharp Oracle Inequalities for Low-complexity Priors

Keywords: High-dimensional estimation, Exponential weighted aggregation, Penalized estimation, Oracle inequality, Low complexity models

In this paper, we consider a high-dimensional statistical estimation problem in which the the number of parameters is comparable or larger than the sample size. We present a unified analysis of the performance guarantees of exponential weighted aggregation and penalized estimators with a general class of data losses and priors which encourage objects which conform to some notion of simplicity/complexity. More precisely, we show that these two estimators satisfy sharp oracle inequalities for prediction ensuring their good theoretical performances. We also highlight the differences between them. When the noise is random, we provide oracle inequalities in probability using concentration inequalities. These results are then applied to several instances including the Lasso, the group Lasso, their analysis-type counterparts, the ∞ and the nuclear norm penalties. All our estimators can be efficiently implemented using proximal splitting algorithms.

Introduction

Problem statement

Our statistical context is the following. Let y = (y 1 , y 2 , • • • , y n ) be n observations with common marginal distribution, and X ∈ R n×p a deterministic design matrix. The goal to estimate a parameter vector θ ∈ R p of the observations marginal distribution based on the data y and X.

Let F : R n × R n → R be a loss function supposed to be smooth and convex that assigns to each θ ∈ R p a cost F (Xθ, y). Let θ 0 ∈ Argmin θ∈R p E [F (Xθ, y)] be any minimizer of the population risk. We regard θ 0 as the true parameter. A usual instance of this statistical setting is the standard linear regression model based on n pairs (y i , X i ) of response-covariate that are linked linearly y = Xθ 0 + ξ, and F (u, y) =1 2 yu 2 2 . Our goal is to provide general oracle inequalities in prediction for two estimators of θ 0 : the penalized estimator and exponential weighted aggregation. In the setting where "p larger than n (possibly much larger), the estimation problem is ill-posed since the rectangular matrix X has a kernel of dimension at least p -n. To circumvent this difficulty, we will exploit the prior that θ 0 has some low-complexity structure (among which sparsity and low-rank are the most popular). That is, even if the ambient dimension p of θ 0 is very large, its intrinsic dimension is much smaller than the sample size n. This makes it possible to build estimates X θ with good provable performance guarantees under appropriate conditions. There has been a flurry of research on the use of low-complexity regularization in ill-posed recovery problems in various areas including statistics and machine learning.

Penalized Estimators

Regularization is now a central theme in many fields including statistics, machine learning and inverse problems. It allows one to impose on the set of candidate solutions some prior structure on the object to be estimated. This regularization ranges from squared Euclidean or Hilbertian norms to non-Hilbertian norms (e.g. 1 norm for sparse objects, or nuclear norm for lowrank matrices) that have sparked considerable interest in the recent years. In this paper, we consider the class of estimators obtained by solving the convex optimization problem

1 θ PEN n ∈ Argmin θ∈R p {V n (θ) def = 1 n F (Xθ, y) + λ n J(θ)}, (1)
where the regularizing penalty J is a proper closed convex function that promotes some specific notion of simplicity/low-complexity, and λ n > 0 is the regularization parameter. A prominent member covered by (1) is the Lasso [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]; [START_REF] Tibshirani | Regression shrinkage and selection via the Lasso[END_REF]; [START_REF] Osborne | A new approach to variable selection in least squares problems[END_REF]; [START_REF] Donoho | For most large underdetermined systems of linear equations the minimal 1 -norm solution is also the sparsest solution[END_REF]; [START_REF] Candès | Near-ideal model selection by 1 minimization[END_REF]; Bickel et al (2009); Bühlmann and van de Geer (2011); [START_REF] Koltchinskii | Oracle inequalities in empirical risk minimization and sparse recovery problems[END_REF] and its variants such the analysis/fused Lasso [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF]; [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF], SLOPE [START_REF] Bogdan | Slope -adaptive variable selection via convex optimization[END_REF]; Su and Candès (2015) or group Lasso [START_REF] Bakin | Adaptive regression and model selection in data mining problems[END_REF]; [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]; [START_REF] Bach | Consistency of the group lasso and multiple kernel learning[END_REF]; [START_REF] Wei | Consistent group selection in high-dimensional linear regression[END_REF]. Another example is the nuclear norm minimization for low rank matrix recovery motivated by various applications including robust PCA, phase retrieval, control and computer vision [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF]; [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]; [START_REF] Fazel | A rank minimization heuristic with application to minimum order system approximation[END_REF]; [START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF]. See [START_REF] Negahban | A unified framework for highdimensional analysis of M-estimators with decomposable regularizers[END_REF]; Bühlmann and van de Geer (2011); van de Geer (2014); Vaiter et al (2015b) for generalizations and comprehensive reviews.

Exponential Weighted Aggregation (EWA)

An alternative to the penalized estimator (1) is the aggregation by exponential weighting, which consists in substituting averaging for minimization. The aggregators are defined via the probability density function

µ n (θ) = exp (-V n (θ)/β) Θ exp (-V n (ω)/β)dω , (2)
where β > 0 is called temperature parameter. If all θ are candidates to estimate the true vector θ 0 , then Θ = R p . The aggregate is thus defined by

θ EWA n = R p
θµ n (θ)dθ.

(3)

Aggregation by exponential weighting has been widely considered in the statistical and machine learning literatures, see e.g., [START_REF] Dalalyan | Aggregation by exponential weighting and sharp oracle inequalities[END_REF], 2008, 2009[START_REF] Verzelen | Minimax risks for sparse regressions: Ultra-high dimensional phenomenons[END_REF]; [START_REF] Nemirovski | Topics in non-parametric statistics[END_REF]; [START_REF] Yang | Aggregating regression procedures to improve performance[END_REF]; [START_REF] Rigollet | Linear and convex aggregation of density estimators[END_REF]; [START_REF] Lecué | Simultaneous adaptation to the margin and to complexity in classification[END_REF]; [START_REF] Guedj | PAC-bayesian estimation and prediction in sparse additive models[END_REF]; Duy [START_REF] Luu | PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting[END_REF] to name a few. The technique used in these papers were initiated by [START_REF] Leung | Information theory and mixing least-squares regressions[END_REF] (use of Stein's identity to study an early version of EWA) and [START_REF] Catoni | A PAC-bayesian approach to adaptive classification Catoni O (2007) PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical Learning[END_REF]Catoni ( , 2007) ) (PAC-Bayesian theory). θ

EWA n can also be interpreted as the posterior conditional mean in the Bayesian sense if F/(nβ) is the negative-loglikelihood associated to the noise ξ with the prior density π(θ) ∝ exp (-λ n J(θ)/β).

Oracle inequalities

Oracle inequalities, which are at the heart of our work, quantify the quality of an estimator compared to the best possible one among a family of estimators. These inequalities are well adapted in the scenario where the prior penalty promotes some notion of low-complexity (e.g. sparsity, low rank, etc.). Given two vectors θ 1 and θ 2 , let R n (θ 1 , θ 2 ) be a nonnegative error measure between their predictions, respectively Xθ 1 and Xθ 2 . A popular example is the averaged prediction squared error 1 n Xθ 1 -Xθ 2 2 2 , where • 2 is the 2 norm. R n will serve as a measure of the performance of the estimators θ . More precisely, we aim to prove that θ EWA n and θ PEN n mimic as much as possible the best possible model. This idea is materialized in the following type of inequalities (stated here for EWA)

R n θ EWA n , θ 0 ≤ C inf θ∈R p R n (θ, θ 0 ) + ∆ n,p,λn,β (θ) , (4)
where C ≥ 1 is the leading constant of the oracle inequality and the remainder term ∆ n,λn,β (θ) depends on the performance of the estimator, the complexity of θ, the sample size n, the dimension p, and the regularization and temperature parameters (λ n , β). An estimator with good oracle properties would correspond to C close to 1 (ideally, C = 1, in which case the inequality is said "sharp"), and ∆ n,p,λn,β (θ) is small and decreases rapidly to 0 as n → +∞.

Contributions

We provide a unified analysis where we capture the essential ingredients behind the low-complexity priors promoted by J, relying on sophisticated arguments from convex analysis and our previous work [START_REF] Fadili | Stable recovery with analysis decomposable priors[END_REF]; Vaiter et al (2015a[START_REF] Vaiter | Model consistency of partly smooth regularizers[END_REF][START_REF] Vaiter | The degrees of freedom of partly smooth regularizers[END_REF]Vaiter et al ( , 2015b)). Our main contributions are summarized as follows:

• We show that the EWA estimator θ

EWA n in (2) and the penalized estimator θ

PEN n in (1) satisfy (deterministic) sharp oracle inequalities for prediction with optimal remainder term, for general data losses F beyond the usual quadratic one, and J is a proper finite-valued sublinear function (i.e. J is finite-valued convex and positively homogeneous). We also highlight the differences between the two estimators in terms of the corresponding bounds.

• When the observations are random, we prove oracle inequalities in probability. The theory is non-asymptotic in nature, as it yields explicit bounds that hold with high probability for finite sample sizes, and reveals the dependence on dimension and other structural parameters of the model. • For the standard linear model with Gaussian or sub-Gaussian noise, and a quadratic loss, we deliver refined versions of these oracle inequalities in probability. We underscore the role of the Gaussian width, a concept that captures important geometric characteristics of sets in R n . • These results yield naturally a large number of corollaries when specialized to penalties routinely used in the literature, among which the Lasso, the group Lasso, their analysis-type counterparts (fused (group) Lasso), the ∞ and the nuclear norms. Some of these corollaries are known and others novel.

The estimators θ

EWA n and θ

PEN n can be easily implemented thanks to the framework of proximal splitting methods, and more precisely forwardbackward type splitting. While the latter is well-known to solve (1) Vaiter et al (2015b), its application within a proximal Langevin Monte-Carlo algorithm to compute θ EWA n with provable guarantees has been recently developed by the authors in Duy [START_REF] Luu | PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting[END_REF] to sample from log-semiconcave densities2 , see also [START_REF] Durmus | Sampling from convex non continuously differentiable functions, when Moreau meets Langevin[END_REF] for log-concave densities.

Relation to previous work

Our oracle inequality for θ EWA n extends the work of [START_REF] Dalalyan | On the Exponentially Weighted Aggregate with the Laplace Prior[END_REF] with an unprecedented level of generality, far beyond the Lasso and the nuclear norm. Our prediction sharp oracle inequality for θ PEN n specializes to that of [START_REF] Sun | Scaled sparse linear regression[END_REF] in the case of the Lasso (see also the discussion in [START_REF] Dalalyan | On the prediction performance of the lasso[END_REF] and references therein) and that of [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] for the case of the nuclear norm. Our work also goes much beyond that in van de Geer (2014) on weakly decomposable priors, where we show in particular that there is no need to impose decomposability on the regularizer, since it is rather an intrinsic property of it.

Paper organization

Section 2 states our main assumptions on the data loss and the prior penalty. All the concepts and notions are exemplified on some penalties some of which are popular in the literature. In Section 3, we prove our main oracle inequalities, and their versions in probability. We then tackle the case of linear regression with quadratic data loss in Section 4. Concepts from convex analysis that are essential to this work are gathered in Section A. A key intermediate result in the proof of our main results is established in Section B with an elegant argument relying on Moreau-Yosida regularization.

Notations

Vectors and matrices For a d-dimensional Euclidean space R d , we endow it with its usual inner product •, • and associated norm • 2 . Id d is the identity matrix on R d . For p ≥ 1, • p will denote the p norm of a vector with the usual adaptation for p = +∞.

In the following, if T is a vector space, P T denotes the orthogonal projector on T , and θ T = P T θ and X T = X P T .

For a finite set C we denote C its cardinality. For I ⊂ {1, . . . , p}, we denote by I c its complement. θ I is the subvector whose entries are those of θ restricted to the indices in I, and X I the submatrix whose columns are those of X indexed by I. For any matrix X, X denotes its transpose and X + its Moore-Penrose pseudo-inverse. For a linear operator A, A * is its adjoint.

Sets For a nonempty set C ∈ R p , we denote conv (C) the closure of its convex hull, and ι C its indicator function, i.e. ι C (θ) = 0 if θ ∈ C and +∞ otherwise. For a nonempty convex set C, its affine hull aff(C) is the smallest affine manifold containing it. It is a translate of its parallel subspace par(C), i.e. par(C) = aff(C) -θ = R(C -C); for any θ ∈ C. The relative interior ri(C) of a convex set C is the interior of C for the topology relative to its affine full.

Functions A function f : R p → R ∪ {+∞} is closed (or lower semicontinu- ous (lsc)) if so is its epigraph. It is coercive if lim θ 2 →+∞ f (θ) = +∞, and strongly coercive if lim θ 2 →+∞ f (θ)/ x 2 = +∞. The effective domain of f is dom(f ) = θ ∈ R p : f (θ) < +∞ and f is proper if dom(f ) = ∅
as is the case when it is finite-valued. A function is said sublinear if it is convex and positively homogeneous. The Legendre-Fenchel conjugate of f is f * (z) = sup θ∈R p z, θ -f (θ). For f proper, the functions (f, f * ) obey the Fenchel-Young inequality

f (θ) + f * (z) ≥ z, θ , ∀(θ, z) ∈ R p × R p . ( 5
)
When f is a proper lower semicontonuous and convex function, (f, f * ) is actually the best pair for which this inequality cannot be tightened. For a function g on R + , the function g

+ : a ∈ R + → g + (a) = sup t≥0 at -g(t)
is called the monotone conjugate of g. The pair (g, g + ) obviously obeys (5) on

R + × R + . For a C 1 -smooth function f , ∇f (θ) is its (Euclidean) gradient. For a bi- variate function g : (η, y) ∈ R n × R n → R that is C 2 with
respect to the first variable η, for any y, we will denote ∇g(η, y) the gradient of g at η with respect to the first variable.

The subdifferential ∂f (θ) of a convex function f at θ is the set

∂f (θ) = η ∈ R p : f (θ ) ≥ f (θ) + η, θ -θ , ∀θ ∈ dom(f ) .
An element of ∂f (θ) is a subgradient. If the convex function f is differentiable at θ, then its only subgradient is its gradient, i.e. ∂f (θ) = {∇f (θ)}.

The Bregman divergence associated to a convex function f at θ with respect to η ∈ ∂f (θ) = ∅ is

D η f θ, θ = f (θ) -f (θ) -η, θ -θ .
The Bregman divergence is in general nonsymmetric. It is also nonnegative by convexity. When f is differentiable at θ, we simply write D f θ, θ (which is, in this case, also known as the Taylor distance).

Estimation with low-complexity penalties

The estimators θ PEN n and θ

EWA n in (1) and (3) require two essential ingredients: the data loss term F and the prior penalty J. We here specify the class of such functions covered in our work, and provide illustrating examples.

Data loss

The class of loss functions F that we consider obey the following assumptions:

(H.1) F (•, y) : R n → R is C 1 (R n ) and uniformly convex for all y of modulus ϕ, i.e. F (v, y) ≥ F (u, y) + ∇F (u, y), v -u + ϕ( v -u 2 ),
where ϕ : R + → R + is a convex non-decreasing function that vanishes only at 0. (H.2) For any θ ∈ R p and y ∈ R n , R p exp (-F (Xθ, y)/(nβ)) ∇F (Xθ, y), X(θθ) dθ < +∞.

Recall that by Lemma 2, the monotone conjugate ϕ + of ϕ is a proper, closed, convex, strongly coercive and non-decreasing function on R + that vanishes at 0. Moreover, ϕ ++ = ϕ. The function ϕ + is finite-valued on R + if ϕ is strongly coercive, and it vanishes only at 0 under e.g. Lemma 2(iii).

The class of data loss functions in (H.1) is fairly general. It is reminiscent of the negative log-likelihood in the regular exponential family. For the moment assumption (H.2) to be satisfied, it is suffient that

R p exp -ϕ Xθ 2 /(nβ) ∇F (Xθ + u , y) 2 Xθ + (u -Xθ) 2 dθ < +∞,
where u be a minimizer of F (•, y), which is unique by uniform convexity. We here provide an example.

Example 1 Consider the case where3 ϕ(t) = t q /q, q ∈]1, +∞[, or equivalently ϕ + (t) = t q * /q * where 1/q + 1/q * = 1. For q = q * = 2, (H.1) amounts to saying that F (•, y) is strongly convex for all y. In particular, (Bauschke and Combettes 2011, Proposition 10.13) shows that F (u, y) = uy q 2 /q is uniformly convex for q ∈ [2, +∞[ with modulus ϕ(t) = C q t q /q, where C q > 0 is a constant that depends solely on q.

For (H.2) to be verified, it is suffient that

R p exp Ä -Xθ q 2 /(qnβ) ä ∇F (Xθ + u , y) 2 (Xθ + u ) -Xθ 2 dθ < +∞.
In particular, taking F (u, y) = u-y q 2 /q, q ∈ [2, +∞[, we have ∇F (u, y) 2 = uy q-1 2 , and thus (H.2) holds since

R p exp Ä -Xθ q 2 /(qnβ) ä y -(Xθ + u ) q-1 2
Xθ -(Xθ + u ) 2 dθ < +∞.

Prior penalty

Recall the main definitions and results from convex analysis that are collected in Section A. Our main assumption on J is the following.

(H.3) J : R p → R is the gauge of a non-empty convex compact set containing the origin as an interior point.

By Lemma 4, this assumption is equivalent to saying that J def = γ C is proper, convex, positively homogeneous, finite-valued and coercive. In turn, J is locally Lipschitz continuous on R p . Observe also that by virtue of Lemma 5 and Lemma 3, the polar gauge J • def = γ C • enjoys the same properties as J in (H.3).

Decomposability of the prior penalty

We are now in position to provide an important characterization of the subdifferential mapping of a function J satisfying (H.3). This characterization will play a pivotal role in our proof of the oracle inequality. We start by defining some essential geometrical objects that were introduced in Vaiter et al (2015a).

Definition 1 (Model Subspace) Let θ ∈ R p . We denote by e θ as e θ = P aff(∂J(θ)) (0).

We denote

S θ = par(∂J(θ)) and

T θ = S ⊥ θ .
T θ is coined the model subspace of θ associated to J.

It can be shown, see (Vaiter et al 2015a, Proposition 5), that θ ∈ T θ , hence the name model subspace. When J is differentiable at θ, we have e θ = ∇J(θ) and T θ = R p . When J is the 1 -norm (Lasso), the vector e θ is nothing but the sign of θ. Thus, e θ can be viewed as a generalization of the sign vector.

Observe also that e θ = P T θ (∂J(θ)), and thus e θ ∈ T θ ∩ aff(∂J(θ)). However, in general, e θ ∈ ∂J(θ).

We now provide a fundamental equivalent description of the subdifferential of J at θ in terms of e θ , T θ , S θ and the polar gauge J • .

Theorem 1 Let J satisfy (H.3). Let θ ∈ R p and f θ ∈ ri(∂J(θ)).

(i) The subdifferential of J at θ reads

∂J(θ) = aff(∂J(θ)) ∩ C • = {η ∈ R n : η T θ = e θ and inf τ ≥0 max J • τ e θ + η S θ + (τ -1) P S θ f θ , τ ≤ 1 ™ . (ii) For any ω ∈ R p , ∃η ∈ ∂J(θ) such that J(ω S θ ) = η S θ , ω S θ .
Proof (i) This follows by piecing together (Vaiter et al 2015a, Theorem 1, Proposition 4 and Proposition 5(iii)).

(ii) From (Vaiter et al 2015a, Proposition 5(iv)), we have

σ ∂J(θ)-f θ (ω) = J(ω S θ ) -P S θ f θ , ω S θ .
Thus there exists a supporting point v ∈ ∂J(θ) -f θ ⊂ S θ with normal vector ω (Bauschke and Combettes 2011, Corollary 7.6(iii)), i.e.

σ ∂J(θ)-f θ (ω) = v, ω S θ .
Taking η = v + f θ concludes the proof.

Remark 1 The coercivity assumption in (H.3) is not needed for Theorem 1 to hold.

The decomposability of described in Theorem 1(i) depends on the particular choice of the mapping θ → f θ ∈ ri(∂J(θ)). An interesting situation is encountered when e θ ∈ ri(J(θ)), so that one can choose f θ = e θ . Strong gauges, see (Vaiter et al 2015a, Definition 6), are precisely a class of gauges for which this situation occurs, and in this case, Theorem 1(i) has the simpler form

∂J(θ) = aff(∂J(θ)) ∩ C • = η ∈ R n : η T θ = e θ and J • (η S θ ) ≤ 1 . (6)
The Lasso, group Lasso and nuclear norms are typical examples of (symmetric) strong gauges. However, analysis sparsity penalties (e.g. the fused Lasso) or the ∞ -penalty are not strong gauges, though they obviously satisfy (H.3). See the next section for a detailed discussion.

Calculus with the prior family

The family of penalties complying with (H.3) form a robust class enjoying important calculus rules. In particular it is closed under the sum and composition with an injective linear operator as we now prove.

Lemma 1 The set of functions satisfying (H.3) is closed under addition4 and pre-composition by an injective linear operator. More precisely, the following holds:

(i) Let J and G be two gauges satisfying (H.3). Then H def and e G θ ) are the model subspace and vector at θ associated to

J (resp. G); (b) H • (ω) = max ρ∈[0,1] conv (inf (ρJ • (ω), (1 -ρ)G • (ω))).
(ii) Let J be a gauge satisfying (H.3), and D : R q → R p be surjective. Then

H def = J • D also fulfills (H.3). Moreover, (a) T H θ = Ker(D S J u
) and e H θ = P T H θ De J u , where T J u and e J u are the model subspace and vector at

u def = D θ associated to J; (b) H • (ω) = J • (D + ω), where D + = D DD -1 .
The outcome of Lemma 1 is naturally expected. For instance, assertion (i) states that combining several penalties/priors will promote objects living on the intersection of the respective low-complexity models. Similarly, for (ii), one promotes low-complexity in the image of the analysis operator D . It then follows that one has not to deploy an ad hoc analysis when linearly precomposing or combining (or both) several penalties (e.g. 1 +nuclear norms for recovering sparse and low-rank matrices) since our unified analysis in Section 3 will apply to them just as well.

Proof (i) Convexity, positive homogeneity, coercivity and finite-valuedness are straightforward.

(a) This is (Vaiter et al 2015a, Proposition 8(i)-(ii)).

(b) We have from Lemma 5 and calculus rules on support functions,

H • (ω) = σ J(θ)+G(θ)≤1 (ω) = sup J(θ)+G(θ)≤1 ω, θ = max ρ∈[0,1] sup J(θ)≤ρ,G(θ)≤1-ρ ω, θ = max ρ∈[0,1] conv inf σ J(θ)≤ρ (ω), σ G(θ)≤1-ρ (ω) = max ρ∈[0,1] conv inf ρσ J(θ)≤1 (ω), (1 -ρ)σ G(θ)≤1 (ω) = max ρ∈[0,1] conv (inf (ρJ • (ω), (1 -ρ)G • (ω))),
where

H • (ω) = sup D θ∈C ω, θ (D is injective) = sup D θ∈C D + ω, D θ = sup u∈C∩Span(D ) D + ω, u = conv inf J • (D + ω), ι Ker(D) (D + ω) = J • (D + ω).
where in the last equality, we used the fact that D + ω ∈ Span D = Ker(D) ⊥ , and thus ι Ker(D) (D + ω) = +∞ unless ω = 0, and J • is continuous and convex by (H.3) and Lemma 5. In the fourth equality, we invoked (Hiriart-Urruty and Lemaréchal 2001, Theorem V.3.3.3) and Lemma 5.

Examples

Lasso

The Lasso regularization is used to promote the sparsity of the minimizers, see Bühlmann and van de Geer ( 2011) for a comprehensive review. It corresponds to choosing J as the 1 -norm

J(θ) = θ 1 = p i=1 θ i . (7)
It is also referred to as 1 -synthesis in the signal processing community, in contrast to the more general 1 -analysis sparsity penalty detailed below.

We denote (a i ) 1≤i≤p the canonical basis of R p and supp(θ)

def = i ∈ {1, . . . , p} : θ i = 0 . Then, T θ = Span{(a i ) i∈supp(θ) }, (e θ ) i = ® sign(θ i ) if i ∈ supp(θ) 0 otherwise , and J • = • ∞ . (8)

Group Lasso

The group Lasso has been advocated to promote sparsity by groups, i.e. it drives all the coefficients in one group to zero together hence leading to group selection, see [START_REF] Bakin | Adaptive regression and model selection in data mining problems[END_REF]; [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]; [START_REF] Bach | Consistency of the group lasso and multiple kernel learning[END_REF]; [START_REF] Wei | Consistent group selection in high-dimensional linear regression[END_REF] to cite a few. The group Lasso penalty with L groups reads

J(θ) = θ 1,2 def = L i=1 θ bi 2 , (9)
where L i=1 b i = {1, . . . , p}, b i , b j ⊂ {1, . . . , p}, and b i ∩ b j = ∅ whenever i = j. Define the group support as supp B (θ) def = i ∈ {1, . . . , L} : θ bi = 0 . Thus, one has

T θ = Span{(a j ) j : ∃i∈supp B (θ),j∈bi }, (e θ ) bi =    θ b i θ b i 2 if i ∈ supp B (θ) 0 otherwise
, and

J • (ω) = max i∈{1,...,L} ω bi 2 .
(10)

Analysis (group) Lasso

One can push the structured sparsity idea one step further by promoting group/block sparsity through a linear operator, i.e. analysis-type sparsity. Given a linear operator D : R q → R p (seen as a matrix), the analysis group sparsity penalty is

J(θ) = D θ 1,2 . ( 11
)
This encompasses the 2-D isotropic total variation [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF]. For when all groups of cardinality one, we have the analysis-1 penalty (a.k.a. general Lasso), which encapsulates several important penalties including that of the 1-D total variation [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF], and the fused Lasso [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF]. The overlapping group Lasso Jacob et al ( 2009) is also a special case of ( 9) by taking D to be an operator that exactract the blocks Peyré et al ( 2011); Chen et al (2010) (in which case D has even orthogonal rows).

Let

Λ θ = i∈supp B (D θ) b i and Λ c θ its complement.
From Lemma 1(ii) and ( 10), we get

T θ = Ker(D Λ c θ ), e θ = P T θ De 1,2 D θ where e 1,2 D θ bi =      (D θ) b i (D θ) b i 2 if i ∈ supp B (D θ) 0 otherwise. (12)
If, in addition, D is surjective, then by virtue of Lemma 1(ii) we also have

J • (ω) = D + ω ∞,2 def = max i∈{1,...,L} (D + ω) bi 2 . (13)

Anti-sparsity

If the vector to be estimated is expected to be flat (anti-sparse), this can be captured using the ∞ norm (a.k.a. Tchebychev norm) as prior

J(θ) = θ ∞ = max i∈{1,...,p} θ i . ( 14
)
The ∞ regularization has found applications in several fields [START_REF] Jégou | Anti-sparse coding for approximate nearest neighbor search[END_REF]; [START_REF] Lyubarskii | Uncertainty principles and vector quantization[END_REF]; [START_REF] Studer | Slope is adaptive to unknown sparsity and asymptotically minimax[END_REF]. Suppose that θ = 0, and define the saturation support of θ as I sat (Vaiter et al 2015a, Proposition 14), we have

θ def = i ∈ {1, . . . , p} : θ i = θ ∞ = ∅. From
T θ = θ ∈ R p : θ I sat θ ∈ R sign(θ I sat θ ) , (e θ ) i = ® sign(θ i )/|I sat θ | if i ∈ I sat θ 0 otherwise , and
J • = • 1 .
(15)

Nuclear norm

The natural extension of low-complexity priors to matrices θ ∈ R p1×p2 is to penalize the singular values of the matrix. Let rank(θ) = r, and θ = U diag(λ(θ))V be a reduced rank-r SVD decomposition, where U ∈ R p1×r and V ∈ R p2×r have orthonormal columns, and λ(θ)

∈ (R + \ {0}) r is the vec- tor of singular values (λ 1 (θ), • • • , λ r (θ)) in non-increasing order. The nuclear norm of θ is J(θ) = θ * = λ(θ) 1 . ( 16
)
This penalty is the best convex surrogate to enforce a low-rank prior.

T θ = U A + BV : A ∈ R p2×r , B ∈ R p1×r , e θ = U V and J • (ω) = |||ω||| 2→2 = λ(ω) ∞ . ( 17
)
3 Oracle inequalities for a general loss Before delving into the details, in the sequel, we will need a bit of notations. We recall T θ and e θ the model subspace and vector associated to θ (see Definition 1). Denote S θ = T ⊥ θ . Given two coercive finite-valued gauges J 1 = γ C1 and J 2 = γ C2 , and a linear operator A, we define |||A||| J1→J2 the operator bound as

|||A||| J1→J2 = sup θ∈C1 J 2 (Aθ).
Note that |||A||| J1→J2 is bounded (this follows from Lemma 4(v)). Furthermore, we have from Lemma 5 that

|||A||| J1→J2 = sup θ∈C1 sup ω∈C • 2 A ω, θ = sup ω∈C • 2 sup θ∈C1 A ω, θ = sup ω∈C • 2 J • 1 (A ω) = A J • 2 →J • 1 .
In the following, whenever it is clear from the context, to lighten notation when J i is a norm, we write the subscript of the norm instead of J i (e.g. p for the p norm, * for the nuclear norm, etc.).

Our main result will involve a measure of well-conditionedness of the design matrix X when restricted to some subspace T . More precisely, for c > 0, we introduce the coefficient

Υ (T, c) = inf ω∈R p : J(ω S )<cJ(ω T ) |||P T ||| 2→J Xω 2 n 1/2 (J(ω T ) -J(ω S )/c) . ( 18
)
This generalizes the compatibility factor introduced in van de Geer and Buhlmann (2009) for the Lasso (and used in [START_REF] Dalalyan | On the Exponentially Weighted Aggregate with the Laplace Prior[END_REF]). The experienced reader may have recognized that this factor is reminescent of the null space property and restricted injectivity that play a central role in the analysis of the performance guarantees of penalized estimators (1); see [START_REF] Fadili | Stable recovery with analysis decomposable priors[END_REF]; Vaiter et al (2015a[START_REF] Vaiter | Model consistency of partly smooth regularizers[END_REF][START_REF] Vaiter | The degrees of freedom of partly smooth regularizers[END_REF]Vaiter et al ( , 2015b)). One can see in particular that Υ (T, c) is larger than the smallest singular value of X T .

The oracle inequalites will provided in terms of the loss

R n θ, θ 0 = 1 n D F (Xθ, Xθ 0 ).

Oracle inequality for θ

EWA n

We are now ready to establish our first main result: an oracle inequality for the EWA estimator (3).

Theorem 2 Consider the EWA estimator θ

EWA n in (3) with the density (2), where F and J satisfy Assumptions (H.1)-(H.2) and (H.3). Then, for any

τ > 1 such that λ n ≥ τ J • Ä -X ∇F (Xθ 0 , y) ä /n, the following holds, R n θ EWA n , θ 0 ≤ inf θ∈R p Ñ R n θ, θ 0 + 1 n ϕ + Ñ λ n √ n τ J • (e θ ) + 1 |||P T θ ||| 2→J τ Υ Ä T θ , τ J • (e θ )+1 τ -1 ä éé + pβ. (19)
Remark 2

1. It should be emphasized that Theorem 2 is actually a deterministic statement for a fixed choice of λ n . Probabilistic analysis will be required when the result is applied to particular statistical models as we will see later.

For this, we will use concentration inequalities in order to provide bounds that hold with high probability over the data. 2. The oracle inequality is sharp. The remainder in it has two terms. The first one encodes the complexity of the model promoted by J. The second one, pβ, captures the influence of the temperature parameter. In particular, taking β sufficiently small of the order O (pn) -1 , this term becomes

O(n -1 ). 3. When ϕ(t) = νt 2 /2, i.e. F (•, y) is ν-strongly convex, then ϕ + (t) = t 2 /(2ν),
and the reminder term becomes

λ 2 n τ J • (e θ ) + 1 2 |||P T θ ||| 2 2→J 2τ 2 νΥ Ä T θ , τ J • (e θ )+1 τ -1 ä 2 . ( 20
)
If, moreover, ∇F is also κ-Lipschitz continuous, then it can be shown that R n θ, θ 0 is equivalent to a quadratic loss. This means that the oracle inequality in Theorem 2 can be stated in terms of the quadratic prediction error. However, the inequality is not anymore sharp in this case as a constant factor equal to the condition number κ/ν ≥ 1 naturally multiplies the right-hand side. 4. If J is such that e θ ∈ ∂J(θ) ⊂ C • (typically for a strong gauge by ( 6)), then J • (e θ ) ≤ 1 (in fact an equality if θ = 0). Thus the term J • (e θ ) can be omitted in (19). 5. A close inspection of the proof of Theorem 2 reveals that the term pβ can be improved to the smaller bound

pβ + V n ( θ EWA n ) -E µn [V n (θ)] ,
where the upper-bound is a consequence of Jensen inequality.

Proof By convexity of J and assumption (H.1), we have for any η ∈ ∂V n (θ) and any θ ∈ R p ,

D η Vn θ, θ ≥ 1 n ϕ Xθ -Xθ 2 .
Since ϕ is non-decreasing and convex, ϕ • • 2 is a convex function. Thus, taking the expectation w.r.t. to µ n on both sides and using Jensen inequality, we get

V n (θ) ≥ E µn [V n (θ)] + E µn η, θ -θ + 1 n E µn ϕ Xθ -Xθ 2 ≥ V n ( θ EWA n ) + E µn η, θ -θ + 1 n ϕ Xθ -X θ EWA n 2 .
This holds for any η ∈ ∂V n (θ), and in particular at the minimal selection ∂V n (θ) 0 (see Section B for details). It then follows from the pillar result in Proposition 55 that

E µn î ∂V n (θ) 0 , θ -θ ó = -pβ.
We thus deduce the inequality

V n ( θ EWA n ) -V n (θ) ≤ pβ - 1 n ϕ X θ EWA n -Xθ 2 , ∀θ ∈ R p . ( 21
)
By definition of the Bregman divergence, we have

R n θ EWA n , θ 0 -R n θ, θ 0 = 1 n F (X θ EWA n , y) -F (Xθ, y) + -X ∇F (Xθ 0 , y)), θ EWA n -θ = V n ( θ EWA n ) -V n (θ) + 1 n -X ∇F (Xθ 0 , y), θ EWA n -θ -λ n J( θ EWA n ) -J(θ) .
By virtue of the duality inequality (42), we have

R n θ EWA n , θ 0 -R n θ, θ 0 ≤ V n ( θ EWA n ) -V n (θ) + 1 n J • Ä -X ∇F (Xθ 0 , y) ä J( θ EWA n -θ) -λ n J( θ EWA n ) -J(θ) ≤ V n ( θ EWA n ) -V n (θ) + λ n τ J( θ EWA n -θ) -τ J( θ EWA n ) -J(θ) .
Denote ω = θ

EWA n -θ. By virtue of (H.3), Theorem 1 and (42), we obtain

J(ω) -τ J( θ EWA n ) -J(θ) ≤ J(ω T θ ) + J(ω S θ ) -τ e θ , ω T θ -τ J(ω S θ ) ≤ J(ω T θ ) + J(ω S θ ) + τ J • (e θ )J(ω T θ ) -τ J(ω S θ ) = τ J • (e θ ) + 1 J(ω T θ ) -(τ -1)J(ω S θ ) ≤ τ J • (e θ ) + 1 Ä J(ω T θ ) - τ -1 τ J • (e θ )+1 J(ω S θ ) ä .
This inequality together with (21) (applied with θ = θ) and ( 18) yield

R n θ EWA n , θ 0 -R n θ, θ 0 ≤ pβ - 1 n ϕ Xω 2 + λ n τ J • (e θ ) + 1 |||P T θ ||| 2→J Xω 2 n 1/2 τ Υ Ä T θ , τ J • (e θ )+1 τ -1 ä ≤ pβ + 1 n ϕ + Ñ λ n √ n τ J • (e θ ) + 1 |||P T θ ||| 2→J τ Υ Ä T θ , τ J • (e θ )+1 τ -1 ä é ,
where we applied Fenchel-Young inequality (5) to get the last bound. Taking the infimum over θ ∈ R p yields the desired result.

Stratifiable functions Theorem 2 has a nice instanciation when R p can be partitioned into a collection of subsets {M i } i that form a stratification of R p . That is, R p is a finite disjoint union ∪ i M i such that the partitioning sets M i (called strata) must fit nicely together and the stratification is endowed with a partial ordering for the closure operation. For example, it is known that a polyhedral function has a polyhedral stratification, and more generally, semialgebraic functions induce stratifications into finite disjoint unions of manifolds; see, e.g., [START_REF] Coste | An introduction to semialgebraic geometry[END_REF]. Another example is that of partly smooth convex functions thoroughly studied in Vaiter et al (2015a[START_REF] Vaiter | Model consistency of partly smooth regularizers[END_REF][START_REF] Vaiter | The degrees of freedom of partly smooth regularizers[END_REF]Vaiter et al ( , 2015b) ) for various statistical and inverse problems. These functions induce a stratification into strata that are C 2 -smooth submanifolds of R p . In turns out that all popular penalty functions discussed in this paper are partly smooth (see [START_REF] Vaiter | The degrees of freedom of partly smooth regularizers[END_REF]Vaiter et al ( , 2015b))). Let's denote M the set of strata associated to J. With this notation at hand, the oracle inequality (19) now reads

R n θ EWA n , θ 0 ≤ inf M∈M θ∈M Ñ R n θ, θ 0 + 1 n ϕ + Ñ λ n √ n τ J • (e θ ) + 1 |||P T θ ||| 2→J τ Υ Ä T θ , τ J • (e θ )+1 τ -1 ä éé + pβ. ( 22
)
3.2 Oracle inequality for θ

PEN n

The next result establishes that θ

PEN n satisfies a sharp prediction oracle inequality that we will compare to (19).

Theorem 3 Consider the penalized estimator θ PEN n in (1), where F and J satisfy Assumptions (H.1) and (H.3). Then, for any τ > 1 such that

λ n ≥ τ J • Ä -X ∇F (Xθ 0 , y) ä /n, the following holds, R n θ PEN n , θ 0 ≤ inf θ∈R p Ñ R n θ, θ 0 + 1 n ϕ + Ñ λ n √ n τ J • (e θ ) + 1 |||P T θ ||| 2→J τ Υ Ä T θ , τ J • (e θ )+1 τ -1 ä éé . (23)
Proof The proof follows the same lines as that of Theorem 2 except that we use the fact that θ

PEN n is a global minimizer of V n , i.e. 0 ∈ ∂V n ( θ PEN n
). Indeed, we have for any

θ ∈ R p V n (θ) ≥ V n ( θ PEN n ) + 1 n ϕ Xθ -X θ PEN n 2 . ( 24
)
Continuing exactly as just after (21), replacing θ

EWA n with θ

PEN n and invoking (24) instead of (21), we arrive at the claimed result.

Remark 3

1. Observe that the penalized estimator θ PEN n does not require the moment assumption (H.2) for (23) to hold. The convexity assumption on ϕ in (H.1), which was important to apply Jensen's inequality in the proof of (19), is not needed either to get (23). 2. As we remarked for Theorem 2, Theorem 3 is also a deterministic statement for a fixed choice of λ n that holds for any minimizer θ . To simplify the discussion, we will focus on the case of linear regression (30) with Gaussian noise ξ ∼ N (0, σ 2 Id n ) and F is the quadratic loss.

The chief advantage of θ

EWA n is its stability as a function of the data and hyperparameters. It has been shown that for a large class of penalties J, including those studied here, the prediction X θ PEN n is a smooth function of y outside a set of Lebesgue measure zero; see (Vaiter et al 2017, Theorem 2). Those authors also provided in (Vaiter et al 2017, Theorem 3) an expression of the Stein unbiased risk estimator (SURE). For instance, when J is the gauge of a polytope, the SURE is given by

y -X θ PEN n 2 2 + σ 2 dim T θ PEN n -nσ 2 .
The SURE was advocated as an automatic and objective way to choose λ. However, one can see that dim T θ PEN n is a non-smooth function of λ, which may lead to numerical instabilities in practice. In contrast, the SURE of θ EWA n , whose closed-form is given in (Dalalyan et al 2018, (10)), is such that X θ EWA n is a continuous function of (λ, β) ∈]0, +∞[ 2 and y ∈ R n . This better regularity suggests that it would be wiser to use the SURE associated to θ EWA n for an automatic choice of λ.

Oracle inequalities in probability

It remains to check when the event E = {λ n ≥ τ J • Ä -X ∇F (Xθ 0 , y) ä /n} holds with high probability when y is random. We will use concentration inequalities in order to provide bounds that hold with high probability over the data. Toward this goal, we will need the following assumption.

(H.4) y = (y 1 , y 2 , • • • , y n ) are independent random observations, and F (u, y) = n i=1 f i (u i , y i ), f i : R × R → R. Moreover, (i) E f i ((Xθ 0 ) i , y i ) < +∞, ∀1 ≤ i ≤ n ; (ii) f i ((Xθ 0 ) i , t) ≤ g(t), where E [g(y i )] < +∞, ∀1 ≤ i ≤ n; (iii) Bernstein moment condition: ∀1 ≤ i ≤ n and all integers m ≥ 2, E î f i ((Xθ 0 ) i , y i ) m ó ≤ m!κ m-2 σ 2 i /2 for some constants κ > 0, σ i > 0 independent of n. Let σ 2 = max 1≤i≤n σ 2 i .
Observe that under (H.4), and by virtue of Lemma 5(iv) and (Hiriart-Urruty and Lemaréchal 2001, Proposition V.3.3.4), we have

J • -X ∇F (Xθ 0 , y) = σ C -X ∇F (Xθ 0 , y) = sup z∈X(C) - n i=1 f i ((Xθ 0 ) i , y i )z i . (25)
Thus, checking the event E amounts to establishing a deviation inequality for the supremum of an empirical process6 above its mean under the weak Bernstein moment condition (H.4)(iii), which essentially requires that the f i ((Xθ 0 ) i , y i ) have sub-exponential tails, We will first tackle the case where C is the convex hull of a finite set (i.e. C is a polytope).

Polyhedral penalty

We here suppose that J is a finite-valued gauge of C = conv (V), where V is finite, i.e. C is a polytope with vertices (Rockafellar 1996, Corollary 19.1.1).

Our first oracle inequality in probability is the following.

Proposition 1 Consider the estimators θ

EWA n and θ

PEN n

, where F and J def = γ C satisfy Assumptions (H.1), (H.2), (H.3) and (H.4), and C is a polytope with vertices V. Suppose that rank(X) = n and let s(X) = max v∈V Xv ∞ . Choose

λ n ≥ τ σs(X) 2δ log(|V|) n 1 + √ 2κ/σ δ log(|V|) n ,
for some τ > 1 and δ > 1. Then (19) and (23) hold with probability at least 1 -2|V| 1-δ .

Proof In view of Assumptions (H.1) and (H.4), one can differentiate under the expectation sign (Leibniz rule) to conclude that E [F (X•, y)] is C 1 at θ 0 and ∇E [F (Xθ 0 , y)] = X E [∇F (Xθ 0 , y)]. As θ 0 minimizes the population risk, one has ∇E [F (Xθ 0 , y)] = 0. Using the rank assumption on X, we deduce that

E [f i ((Xθ 0 ) i , y i )] = 0, ∀1 ≤ i ≤ n. Moreover, (25) specializes to J • -X ∇F (Xθ 0 , y) = sup z∈X(V) - n i=1 f i ((Xθ 0 ) i , y i )z i .
Let t = λ n n/τ and t = t /s(X). By the union bound and (25), we have

P Ä J • -X ∇F (Xθ 0 , y) ≥ t ä ≤ P max z∈X(V) - n i=1 f i ((Xθ 0 ) i , y i )z i ≥ t ≤ |V| max z∈X(V) P n i=1 f i ((Xθ 0 ) i , y i )z i ≥ t ≤ |V|P s(X) n i=1 f i ((Xθ 0 ) i , y i ) ≥ t = |V|P n i=1 f i ((Xθ 0 ) i , y i ) ≥ t .
Owing to assumption (H.4)(iii), we are in position to apply the Bernstein inequality to get

P Ä J • -X ∇F (Xθ 0 , y) ≥ t ä ≤ 2|V| exp Å - t 2 2(κt + nσ 2 ) ã . Every t such that t ≥ » δ log(|V|) κ » δ log(|V|) + » κ 2 δ log(|V|) + 2nσ 2 , satisfies t 2 ≥ 2δ log(|V|)(κt + nσ 2 ). Applying the trivial inequality √ a + b ≤ √ a + √ b
to the bound on t, we conclude.

Remark 4 In the monograph (Bühlmann and van de Geer 2011, Lemma 14.12), the authors derived an exponential deviation inequality for the supremum of an empirical process with finite V and possibly unbounded empirical processes under a Bernstein moment condition similar to ours (in fact ours implies theirs).

The very last part of our proof can be obtained by applying their result. We detailed it here for the sake of completeness.

Lasso To lighten the notation, let I θ = supp(θ). From (8), it is easy to see that

|||P T θ ||| 2→1 = » |I θ | and J • (e θ ) = sign(θ I θ ) ∞ ≤ 1,
where last bound holds as an equality whenever θ = 0. Further the 1 norm is the gauge of the cross-polytope (i.e. the unit 1 ball). Its vertex set V is the set of unit-norm one-sparse vectors (±a i ) 1≤i≤p , where we recall (a i ) 1≤i≤p the canonical basis. Thus

|V| = 2p and s(X) = max v∈V Xv ∞ = max 1≤i≤p X i ∞ .
Inserting this into Proposition 1, we obtain the following corollary.

Corollary 1 Consider the estimators θ

EWA n and θ

PEN n

, where where J is the Lasso penalty and F satisfies Assumptions (H.1), (H.2) and (H.4). Suppose that rank(X) = n and take

λ n ≥ τ σs(X) 2δ log(2p) n 1 + √ 2κ/σ δ log(2p) n ,
for some τ > 1 and δ > 1. Then, with probability at least 1 -2(2p) 1-δ , the following holds

R n θ EWA n , θ 0 ≤ inf I⊂{1,...,p} θ: supp(θ)=I R n θ, θ 0 + 1 n ϕ + λn √ n(τ +1) √ |I| τ Υ Ä Span{ai} i∈I , τ +1 τ -1 ä + pβ, (26)
and

R n θ PEN n , θ 0 ≤ inf I⊂{1,...,p} θ: supp(θ)=I R n θ, θ 0 + 1 n ϕ + λn √ n(τ +1) √ |I| τ Υ Ä Span{ai} i∈I , τ +1 τ -1 ä . (27)
For θ

PEN n

, we recover a similar scaling for λ n and the oracle inequality as in van de Geer (2008), though in the latter the oracle inequality is not sharp unlike ours. Note that the above oracle inequality extends readily to the case of analysis/fused Lasso D • 1 where D is surjective. We leave the details to the interested reader (see also the analysis group Lasso example in Section 4).

Anti-sparsity From Section 2.5.4, recall the saturation support I sat θ of θ. From (15), we get

|||P T θ ||| 2→∞ = 1 and J • (e θ ) = sign(θ I sat θ ) 1 /|I sat θ | ≤ 1,
with equality whenever θ = 0. In addition, the ∞ norm is the gauge of the hypercube whose vertex set is V = {±1} p . Thus |V| = 2 p .

We have the following oracle inequalities.

Corollary 2 Consider the estimators θ

EWA n and θ

PEN n

, where where J is antisparsity penalty (14), and F satisfies Assumptions (H.1), (H.2) and (H.4). Suppose that rank(X) = n and let s(X) = max i,j |X i,j |. Choose

λ n ≥ τ σs(X) » 2δ log(2) … p n Å 1 + 2κ/σ » δ log(2) … p n ã ,
for some τ > 1 and δ > 1. Then, with probability at least 1 -2 -p(δ-1)+1 , the following holds

R n θ EWA n , θ 0 ≤ inf I⊂{1,...,p} θ: I sat θ =I R n θ, θ 0 + 1 n ϕ + λn √ n(τ +1) τ Υ Ä θ : θ I ∈R sign(θ I ) , τ +1 τ -1 ä + pβ, (28) and R n θ PEN n , θ 0 ≤ inf I⊂{1,...,p} θ: I sat θ =I R n θ, θ 0 + 1 n ϕ + λn √ n(τ +1) τ Υ Ä θ : θ I ∈R sign(θ I ) , τ +1 τ -1 ä . ( 29
)
We are not aware of any result of this kind in the literature. The bound imposed on X is similar to what is generally assumed in the vector quantization literature [START_REF] Lyubarskii | Uncertainty principles and vector quantization[END_REF]; [START_REF] Studer | Slope is adaptive to unknown sparsity and asymptotically minimax[END_REF].

General penalty

Extending the above reasoning to a general penalty requires a deviation inequality for the supremum of an empirical process in (25) under the Bernstein moment condition (H.4)(iii), but without the need of uniform boundedness. This can be achieved via generic chaining along a tree using entropy with bracketing; see (van de Geer and Lederer 2013, Theorem 8). The resulting deviation bound will thus depend on the entropies with bracketing. These quantities capture the complexity of the set X(C) but are intricate to compute in general. This subject deserves further investigation that we leave to a future work.

Remark 5 (Group Lasso) Using the union bound, we have

P Å max i∈{1,...,L} X bi ∇F (Xθ 0 , y) 2 ≥ λ n n/τ ã ≤ L max i P Ä X bi ∇F (Xθ 0 , y) 2 ≥ λ n n/τ ä .
This requires a concentration inequality for quadratic forms of independent random variables satisfying the Bernstein moment assumption above. We are not aware of any such result. But if our moment condition is strengthened to

E î f i ((Xθ 0 ) i , y i ) 2m ó ≤ m!κ 2(m-1) σ 2 i /2, ∀1 ≤ i ≤ n, ∀m ≥ 1,
then one can use (Bellec 2014, Theorem 3). Indeed, assuming max i X i 2 ≤ √ n, which is a natural normalization on the design, we have by independence that

E î X bi ∇F (Xθ 0 , y) 2 ó ≤ E î X bi ∇F (Xθ 0 , y) 2 2 ó 1/2 = σ » tr(X bi X bi )/2= σ j∈bi X j 2 2 /2≤ σ » Kn/2.
It then follows that taking

λ n ≥ τ σ √ K + 16κ δ log(L) √ n , δ > 1,
the oracle inequalities ( 34) and ( 35) hold for the group Lasso with probability at least 1 -L 1-δ . A similar result can be proved for the analysis group Lasso just as well (see Section 4.3.3).

Oracle inequalities for low-complexity linear regression

In this section, we consider the classical linear regression problem where the n response-covariate pairs (y i , X i ) are linked as

y = Xθ 0 + ξ, ( 30
)
where ξ is a noise vector. The data loss will be set to

F (u, y) = 1 2 y-u 2 2 . This in turn entails that ϕ = ϕ + = 1 2 (•) 2 on R + and R n θ, θ 0 = 1 2n Xθ -Xθ 0 2 2 .
In this section, we assume that the noise ξ is a zero-mean sub-Gaussian vector in R n with parameter σ. That is, its one-dimensional marginals ξ, z are sub-Gaussian random variables ∀z ∈ R n , i.e. they satisfy

P ξ, z ≥ t ≤ 2e -t 2 /(2 z 2 2 σ 2 ) , ∀z ∈ R n . ( 31
)
In this case, the bounds of Section 3.4 can be improved.

General penalty

As we will shortly show, the event E will depend on the Gaussian width, a summary geometric quantity which, informally speaking, measures the size of the bulk of a set in R n .

Definition 2 The Gaussian width of a subset S ⊂ R n is defined as

w(S) def = E [σ S (g)] ,
where g ∼ N (0, Id n ).

The concept of Gaussian width has appeared in the literature in different contexts. In particular, it has been used to establish sample complexity bounds to ensure exact recovery (noiseless case) and mean-square estimation stability (noisy case) for low-complexity penalized estimators from Gaussian measurements; see e.g. Rudelson and Vershynin (2008); [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]; Tropp (2015a); [START_REF] Vershynin | Estimation in high dimension : A geometric perspective[END_REF]; Vaiter et al (2015b).

The Gaussian width has deep connections to convex geometry and it enjoys many useful properties. It is well-known that it is positively homogeneous, monotonic w.r.t. inclusion, and invariant under orthogonal transformations. Moreover, w(conv (S)) = w(S). From Lemma 3(ii)-(iii), w(S) is a non-negative finite quantity whenever the set S is bounded and contains the origin.

We are now ready to state our oracle inequality in probability with sub-Gaussian noise.

Proposition 2 Let the data generated by (30) where ξ is a zero-mean sub-Gaussian random vector with parameter σ. Consider the estimators θ , for some τ > 1 and 0 < δ < min(c 2 , 1), where c 1 and c 2 are positive absolute constants. Then with probability at least 1 -δ, (19) and (23) hold with the remainder term given by (20) with ν = 1.

The proof requires sophisticated ideas from the theory of generic chaining [START_REF] Talagrand | The generic chaining. Upper and lower bounds of stochastic processes[END_REF], but we only apply these results. The constants c 1 and c 2 can be traced back to the proof of these results as detailed in [START_REF] Talagrand | The generic chaining. Upper and lower bounds of stochastic processes[END_REF].

Proof First, from (31), we have the bound

P ξ, z -z ≥ t ≤ 2e -t 2 /(2 z-z 2 2 σ 2 ) , ∀z, z ∈ R n ,
i.e. the increment condition (Talagrand 2005, (0.4)) is verified. Thus combining ( 25) with the probability bound in (Talagrand 2005, page 11), the generic chaining theorem (Talagrand 2005, Theorem 1.2.6) and the majorizing measure theorem [START_REF] Talagrand | The generic chaining. Upper and lower bounds of stochastic processes[END_REF], Theorem 2.1.1), we have

P Ä J • (X ξ) ≥ λ n n/τ ä ≤ P Ç sup z∈X(C) ξ, z ≥ σc 1 » 2 log(c 2 /δ)w(X(C)) å ≤ c 2 exp Å - σ 2 2 log(c 2 /δ) 2σ 2 ã = δ.
If the noise is Gaussian, an enhanced version can be proved by invoking Gaussian concentration of Lipschitz functions [START_REF] Ledoux | The concentration of measure phenomenon[END_REF].

Proposition 3 Let the data generated by (30) with noise ξ ∼ N (0, σ 2 Id n ). Proof Thanks to sublinearity (see Lemma 4(i) and Lemma 5), the function ξ 25), we also have

Consider the estimators θ

→ J • (X ξ) is Lipschitz continuous with Lipschitz constant X 2→J • = |||X||| J→2 . From (
E î J • X ξ ó = σw(X(C)).
Observe that X(C) is a convex compact set containing the origin. Setting = λ n n/τ -σw(X(C)) ≥ δσw(X(C)), it follows from (25) and the Gaussian concentration of Lipschitz functions [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] that

P Ä J • (X ξ) ≥ λ n n/τ ä ≤ P Ä J • (X ξ) -E î J • (X ξ) ó ≥ ä ≤ P Ä J • (X ξ/σ) -w(X(C)) ≥ δw(X(C)) ä ≤ exp Ç - δ 2 w(X(C)) 2 2|||X||| 2 J→2
å .

Estimating theoretically the Gaussian width of a set7 is a non-trivial problem that has been extensively studied in the areas of probability in Banach spaces and stochastic processes. There are classical bounds on the Gaussian width (Sudakov's and Dudley's inequalities), but they are difficult to estimate in most cases and neither of these bounds is tight for all sets. When the set is a convex cone (intersected with a sphere), tractable estimates based on polarity arguments were proposed in, e.g., [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF].

Polyhedral penalty

When C and is polytope, enhanced oracle inequalities can be obtained by invoking a simple union bound argument.

Proposition 4 Let the data generated by (30) where ξ is a zero-mean sub-Gaussian random vector with parameter σ. Consider the estimators θ , for some τ > 1 and δ > 1. Then with probability at least 1 -2|V| 1-δ , (19) and (23) hold with the remainder term given by (20) with ν = 1.

In particular, if

max v∈V Xv 2 = C √ n, for a positive constant C, then one can take λ n ≥ Cτ σ » 2δ log(|V|) n .
Proof From (25) we have

J • X ξ = max v∈C Xv, ξ = max v∈V Xv, ξ ,
where in the last inequality, we used the fact that a convex function attains its maximum on C at an extreme point V. Let = σ max v∈V Xv 2 2δ log(|V|).

By the union bound, ( 31) and ( 25), we have

P Ä J • X ξ ≥ λ n n/τ ä ≤ P Å max v∈V Xv, ξ ≥ ã ≤ |V| max v∈V P ( Xv, ξ ≥ ) ≤ |V| max v∈V P Xv, ξ ≥ ≤ 2|V| exp -2 / 2σ 2 max v∈V Xv 2 2 ≤ 2|V| 1-δ .

Applications

In this section, we exemplify our oracle inequalities for the penalties described in Section 2.5.

Lasso

Recall the derivations for the Lasso in Section 3.4.1. We obtain the following corollary of Proposition 4.

Corollary 3 Let the data generated by (30) where ξ is a zero-mean sub-Gaussian random vector with parameter σ. Assume that X is such that

max i X i 2 ≤ √ n. Consider the estimators θ EWA n and θ PEN n
, where J is the Lasso penalty (7) and F satisfies Assumptions (H.1)-(H.2). Suppose that

λ n ≥ τ σ » 2δ log(2p) n
, for some τ > 1 and δ > 1. Then, with probability at least 1 -2(2p) 1-δ , the following holds

1 n X θ EWA n -Xθ 0 2 2 ≤ inf I⊂{1,...,p} θ: supp(θ)=I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 |I| τ 2 Υ Ä Span{ai} i∈I , τ +1 τ -1 ä 2 + 2pβ, (32) and 1 n X θ PEN n -Xθ 0 2 2 ≤ inf I⊂{1,...,p} θ: supp(θ)=I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 |I| τ 2 Υ Ä Span{ai} i∈I , τ +1 τ -1 ä 2 . ( 33
)
The normalization on the design is natural. The remainder term grows as

|I| log(p) n
. The oracle inequality (33) recovers (Dalalyan et al 2018, Theorem 1) in the exactly sparse case, and (33) the one in (Sun and Zhang 2012, Theorem 4) (see also (Koltchinskii et al 2011, Theorem 11) and (Dalalyan et al 2017, Theorem 2)). It is worth mentioning, however, that (Dalalyan et al 2018, Theorem 1) handles the inexactly sparse case while we do not. For the choice β = O σ 2 |I| log(2p)/(pn) , the remainder terms in (32) and ( 33) are of the same order. Observe that this choice of the temperature parameter is optimal in view of the results of [START_REF] Castillo | Bayesian linear regression with sparse priors[END_REF]. These authors proved that for the 1 penalty, orthonormal design, noise ξ ∼ N (0, σ 2 Id n ), and all choices of the form λ = Cσ log(n)/n, then the pseudo-posterior µ n in (2) with temparature β σ 2 /n puts asymptotically no mass on the ball centered at θ 0 of radius ∼ log(n)/n.

Group Lasso

Recall the notations in Section 2.5.2, and denote I θ = supp B (θ) the set indexing active blocks in θ. From (10), we have

|||P T θ ||| 2→J = » |I θ | and J • (e θ ) = e θ ∞,2 ≤ 1,
where the last bound holds as an equality whenever θ = 0. We have the following oracle inequalities as corollaries of Proposition 2 and Proposition 3. , where F satisfies Assumptions (H.1)-(H.2), and J is the group Lasso (9) with L non-overlapping blocks of equal size K. Let

s(X) = … max i X bi X bi 2→2 /n.
(i) ξ is a zero-mean sub-Gaussian random vector with parameter σ: suppose that

λ n ≥ 3τ σs(X)c 1 √ 2 log(c2/δ) √ K+ √ 2 log(L) √ n
, for some τ > 1 and 0 < δ < min(c 2 , 1), where c 1 and c 2 are the positive absolute constants in Proposition 2. Then, with probability at least 1 -δ, the following holds

1 n X θ EWA n -Xθ 0 2 2 ≤ inf I⊂{1,...,L} θ: supp B (θ)=I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 |I| τ 2 Υ Ä Span{aj } j∈b i ,i∈I , τ +1 τ -1 ä 2 + 2pβ, (34)
and

1 n X θ PEN n -Xθ 0 2 2 ≤ inf I⊂{1,...,L} θ: supp B (θ)=I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 |I| τ 2 Υ Ä Span{aj } j∈b i ,i∈I , τ +1 τ -1 ä 2 . ( 35
) (ii) ξ ∼ N (0, σ 2 Id n ): suppose that λ n ≥ τ σs(X) √ K+ √ 2δ log(L) √ n
, for some τ > 1 and δ > 1. Then, with probability at least 1 -L 1-δ , (34) and (35) hold.

When s(X) = O(1)8 , the first remainder term is on the

|I| √ K+ √ 2 log(L) 2 n
. This is similar to the scaling that has been provided in the literature for EWA with other group sparsity priors and noises [START_REF] Rigollet | Sparse estimation by exponential weighting[END_REF]; Duy [START_REF] Luu | PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting[END_REF]. Similar rates were given for θ PEN n with the group Lasso in [START_REF] Negahban | A unified framework for highdimensional analysis of M-estimators with decomposable regularizers[END_REF]; [START_REF] Lounici | Oracle inequalities and optimal inference under group sparsity[END_REF]; van de Geer (2014).

Proof

(i) This is a consequence of Proposition 2, for which we need to bound

w(X(C)) = E ï max i∈{1,...,L} X bi g 2 ò .
We first have, for any block b

i E î X bi g 2 ó ≤ E î X bi g 2 2 ó 1/2 ≤ s(X) √ Kn. Furthermore, X bi • 2 is Lipschitz continuous with Lipschitz constant s(X) √ n.
Thus the union bound and Gaussian concentration of Lipschitz functions [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] yield, for any t > 0,

P Å max i∈{1,...,L} X bi g 2 ≥ s(X) √ Kn + t ã ≤ L i=1 P Ä X bi ξ 2 -E î X bi ξ 2 ó ≥ t ä ≤ L exp Å - t 2 2s(X) 2 n ã . Let κ = s(X) Ä √ Kn + 2n log(L) ä . w(X(C)) can be expressed as w(X(C)) = ∞ 0 P Å max i∈{1,...,L} X bi g 2 ≥ u ã du ≤ κ 0 du + ∞ κ e -(u-s(X) √ Kn) 2 -2s(X) 2 n log(L) 2n du = κ + s(X) √ n ∞ κ/(s(X) √ n) e -(s-√ K) 2 -2 log(L) 2 du ≤ κ + s(X) √ n ∞ κ/(s(X) √ n) e -s-κ/(s(X) √ n) 2 du = κ + 2s(X) √ n ≤ 3κ.
(ii) The proof follows the lines of Proposition 3 where we additionally use the union bound. Indeed,

P Å max i∈{1,...,L} X bi ξ 2 ≥ λ n n/τ ã ≤ L i=1 P Ä X bi ξ 2 -E î X bi ξ 2 ó ≥ λ n n/τ -E î X bi ξ 2 óä ≤ L i=1 P Ä bi ξ 2 -E î X bi ξ 2 ó ≥ λ n n/τ -σs(X) √ Kn ä ≤ L i=1 P X bi ξ 2 -E î X bi ξ 2 ó ≥ σs(X) » 2δn log(L) ≤ L exp (-δ log(L)) = L 1-δ ,
where used the Gaussian concentration of Lipschitz functions [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] in the last inequality.

We observe in passing that another way to prove the oracle inequalities in the sub-Gaussian is to use Dudley's inequality on the sphere in R K after applying a union bound on the L blocks. In addition, in the Gaussian case, the (similar) bound λ n ≥ 3δτ σs(X)

√ K+ √ 2 log(L) √ n
can be obtained by combining Proposition 3 and the estimate w(X(C)) ≤ 3s(X)( √ Kn + 2n log(L)) in the proof of (i). The corresponding probability of success would be at least 1 -L -9(δ-1) 2 .

Analysis group Lasso

We now turn to the prior penalty (11). Recall the notations in Section 2.5.3, and remind Λ θ = i∈supp B (D θ) b i . We assume that D is a frame of R p , hence surjective, meaning that there exist c, d > 0 such that for any ω

∈ R p d ω 2 2 ≤ D ω 2 2 ≤ c ω 2 2 .
This together with ( 12)-( 13) and Cauchy-Schwarz inequality entail

|||P T θ ||| 2→J = sup ω T θ 2 ≤1 D ω T θ 1,2 ≤ √ c sup D ω T θ 2 ≤1 D ω T θ 1,2 = √ c sup D Λ θ ω T θ 2 ≤1 D Λ θ ω T θ 1,2 = √ c » |supp B (D θ)|.
Note, however, that from (12), we do not have in general

C(D, θ) def = D + P Ker(D Λ c θ ) De 1,2 D θ ∞,2 ≤ 1.
With exactly the same arguments to those for proving Corollary 4, replacing X by XD, we arrive at the following oracle inequalities. (i) ξ is a zero-mean sub-Gaussian random vector with parameter σ: suppose that

λ n ≥ 3τ σs(XD)c 1 √ log(c2/δ) √ K+ √ 2 log(L) √ n
, for some τ > 1 and 0 < δ < min(c 2 , 1), where c 1 and c 2 are the positive absolute constants in Proposition 2. Then, with probability at least 1 -δ, the following holds

1 n X θ EWA n -Xθ 0 2 2 ≤ inf I⊂{1,...,L} θ: supp B (D θ)=I 1 n Xθ -Xθ 0 2 2 + cλ 2 n τ C(D,θ)+1 2 |I| τ 2 Υ Ker(D Λ c θ ), τ C(D,θ)+1 τ -1 2 + 2pβ, (36) and 1 n X θ PEN n -Xθ 0 2 2 ≤ inf I⊂{1,...,L} θ: supp B (D θ)=I 1 n Xθ -Xθ 0 2 2 + cλ 2 n τ C(D,θ)+1 2 |I| τ 2 Υ Ker(D Λ c θ ), τ C(D,θ)+1 τ -1 2 . ( 37
)
(ii) ξ ∼ N (0, σ 2 Id n ): suppose that λ n ≥ τ σs(XD)

√ K+ √ 2δ log(L) √ n
, for some τ > 1 and δ > 1. Then, with probability at least 1 -L 1-δ , (36) and (37) hold.

To the best of our knowledge, this result is new to the literature. The scaling of the remainder term is the same as in Duy [START_REF] Luu | PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting[END_REF] and [START_REF] Rigollet | Sparse estimation by exponential weighting[END_REF] with analysis sparsity priors different from ours (the authors in the latter also assume that D is invertible).

Anti-sparsity

Recall the derivations for the ∞ norm example in Section 3.4.1. We have the following oracle inequalities from Proposition 4.

Corollary 6 Let the data generated by (30) where ξ is a zero-mean sub-Gaussian random vector with parameter σ. Assume that X is such that max i,j |X i,j | ≤ 1/p. Consider the estimators θ EWA n and θ

PEN n

, where F satisfies Assumptions (H.1)-(H.2), and J is the anti-sparsity penalty (14). Suppose that λ n ≥ τ σ 2δ log(2) » p n , for some τ > 1 and δ > 1. Then, with probability at least 1 -2 -p(δ-1)+1 , the following holds

1 n X θ EWA n -Xθ 0 2 2 ≤ inf I⊂{1,...,p} θ: I sat θ =I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 τ 2 Υ Ä θ : θ I ∈R sign(θ I ) , τ +1 τ -1 ä 2 + 2pβ, (38) and 1 n X θ PEN n -Xθ 0 2 2 ≤ inf I⊂{1,...,p} θ: I sat θ =I 1 n Xθ -Xθ 0 2 2 + λ 2 n (τ +1) 2 τ 2 Υ Ä θ : θ I ∈R sign(θ I ) , τ +1 τ -1 ä 2 . ( 39
)
The first remainder term scales as p n which reflects that anti-sparsity regularization requires an overdetermined regime to ensure good stability performance. This is in agreement with (Vaiter et al 2015a, Theorem 7). This phenomenon was also observed by [START_REF] Donoho | Counting the faces of randomly-projected hypercubes and orthants[END_REF] who studied sample complexity thresholds for noiseless recovery from random projections of the hypercube.

Nuclear norm

We now turn to the nuclear norm case. Recall the notations of Section 2.5.5. For matrices θ ∈ R p1×p2 , a measurement map X takes the form of a linear operator whose ith component is given by the Frobenius scalar product

X(θ) i = tr((X i ) θ) = X i , θ F ,
where X i is a matrix in R p1×p2 . We denote • F the associated norm. From (17), it is immediate to see that whenever θ = 0,

J • (e θ ) = U V 2→2 = 1.
Moreover, from (17), we have

|||P T θ ||| F→ * = sup θ ∈T θ θ * θ F = sup θ ∈T θ λ(θ ) 1 λ(θ ) 2 ≤ sup θ ∈T θ » rank(θ ) ≤ » min(r, p 1 ) + min(r, p 2 ) ≤ √ 2r.
To apply Proposition 2 and Proposition 3, we need to bound w(X(C)) (C is the nuclear ball), or equivalently, to bound

E [|||X * (g)||| 2→2 ] = E n i=1 X i g i 2→2 , g ∼ N (0, σ 2 Id n ),
which is the expectation of the operator norm of a random series with matrix coefficients. Thus using (Tropp 2015b, Theorem 4.1.1(4.1.5)) to get this bound, and inserting it into Proposition 2 and Proposition 3, we get the following oracle inequalities for the nuclear norm. Define , where F satisfies Assumptions (H.1)-(H.2), and J is the nuclear norm (16).

s(X) = Ã max n i=1 X i (X i ) 2→2 , n i=1 (X i ) X i 2→2 /n.
(i) ξ is a zero-mean sub-Gaussian random vector with parameter σ: suppose that

λ n ≥ 2τ σs(X)c 1 » log(c2/δ) log(p1+p2) n
, for some τ > 1 and 0 < δ < min(c 2 , 1), where c 1 and c 2 are the positive absolute constants in Proposition 2. Then, with probability at least 1 -δ, the following holds

1 n X θ EWA n -Xθ 0 2 2 ≤ inf r∈{1,...,min(p1,p2)} θ: rank(θ)=r 1 n Xθ -Xθ 0 2 2 + 2λ 2 n (τ +1) 2 r τ 2 Υ Ä T θ , τ +1 τ -1 ä 2 + 2p 1 p 2 β, (40) and 1 n X θ PEN n -Xθ 0 2 2 ≤ inf r∈{1,...,min(p1,p2)} θ: rank(θ)=r 1 n Xθ -Xθ 0 2 2 + 2λ 2 n (τ +1) 2 r τ 2 Υ Ä T θ , τ +1 τ -1 ä 2 . ( 41
) (ii) ξ ∼ N (0, σ 2 Id n ): suppose that λ n ≥ (1 + δ)τ σs(X) » 2 log(p1+p2) n
, for some τ > 1 and δ > 0. Then, with probability at least 1 -(p 1 + p 2 ) -δ 2 , (40) and (41) hold.

The set over which the infimum is taken just reminds us that the nuclear norm is partly smooth (see above) relative to the constant rank manifold (which is a Riemannian submanifold of R p1×p2 ) (Daniilidis et al 2014, Theorem 3.19). In the iid Gaussian noise case, we recover the same rate as in (Dalalyan et al 2018, Theorem 3) . If s(X) = O( √ p 1 + p 2 ), then the first remainder term scales as r(p1+p2) log(p1+p2) n . For low-rank matrix recovery, the same rate was also independently proved in [START_REF] Mai | A bayesian approach for noisy matrix completion: Optimal rate under general sampling distribution[END_REF]; [START_REF] Suzuki | Convergence rate of bayesian tensor estimator and its minimax optimality[END_REF] 9 for EWA and the posterior conditional mean respectively, in the temperature regime β = C/n, though with completely different priors, but without requiring the compatibility factor assumption.

The assumption s(X) = O( √ p 1 + p 2 ) on the design is mild and verified in many situations. Indeed, by Jensen's inequality we have

s(X) 2 ≤ n -1 n i=1 max X i (X i ) 2→2 , (X i ) X i 2→2 ≤ X i 2 2→2 .
If, for example, (X i ) i are independent copies of a standard random Gaussian matrix, then classical concentration bounds of the largest eigenvalue of a Wishart matrix entail that X i

2→2

concentrates around its mean

E X i 2→2 ≤ √ p 1 + √ p 2 ≤ 2(p 1 + p 2 ).

Discussion of minimax optimality

In this section, we discuss the optimality of the estimators θ

EWA n and θ

PEN n

(we remind the reader that the design X is fixed). Recall the discussion on stratification at the end of Section 3.1. Let M 0 ∈ M be the stratum active at θ 0 ∈ M 0 . In this setting, choosing β = C(1 + δ) 2 σ 2 w(X(C))

2 P T θ 0 2 2→J /(pn 2 ) for some constant C > 0, (22) and Proposition 3 ensure that

1 n X θ EWA n -Xθ 0 2 2 ≤ (1 + δ) 2 σ 2 w(X(C)) 2 P T θ 0 2 2→J n 2 Ö τ J • (e θ0 ) + 1 2 Υ T θ0 , τ J • (e θ 0 )+1 τ -1 2 + C è 1 n X θ PEN n -Xθ 0 2 2 ≤ (1 + δ) 2 σ 2 w(X(C)) 2 P T θ 0 2 2→J n 2 τ J • (e θ0 ) + 1 2 Υ T θ0 , τ J • (e θ 0 )+1 τ -1 2 ,
with high probability. In particular, for a polyhedral gauge penalty, in which case M 0 = T θ0 (see

X θ EWA n -Xθ 0 2 2 ≤ 2δσ 2 P M0 2 2→J log(|V|) n Ö τ J • (e θ0 ) + 1 2 Υ M 0 , τ J • (e θ 0 )+1 τ -1 2 + C è 1 n X θ PEN n -Xθ 0 2 2 ≤ 2δσ 2 P M0 2 2→J log(|V|) n τ J • (e θ0 ) + 1 2 Υ M 0 , τ J • (e θ 0 )+1 τ -1 2 ,
with high probability. Thus the risk bounds only depend on M 0 . A natural question that arises is whether the above bounds are optimal, i.e. whether an estimator can achieve a significantly better prediction risk than θ uniformly on M 0 . A classical way to answer this question is the minimax point of view. This amounts to finding a lower bound on the minimax probabilities of the form inf

θ sup θ∈M0 Pr Ä 1 n X θ -Xθ 2 2 ≥ ψ n ä ,
where ψ n is the rate, which ideally, should be comparable to the risk bounds above. A standard path to derive such a lower bound is to exhibit a subset of M 0 of well-separated points while controlling its diameter, see (Tsybakov 2008, Chapter 2) or (Massart 2007, Section 4.3). This however must be worked out on a case-by-case basis.

Example 2 (Lasso) In this case, M 0 = T θ0 is the subspace of vectors whose support is contained in that of θ 0 . Let I = supp(θ 0 ) and s = θ 0 0 . Define the set B 0 = θ ∈ R p : θ I ∈ {0, 1} s and θ I c = 0 .

We have B 0 ⊂ M 0 and θθ 0 ≤ 2s for all (θ, θ ) ∈ B 0 . Define F 0 def = rXθ : θ ∈ B 0 , for r > 0 to be specified later. Due to the Varshamov-Gilbert lemma (Massart 2007, Lemma 4.7), given a ∈]0, 1[, there exists a subset B ⊂ B 0 with cardinality |B| ≥ 2 ρs/2 such that for two distinct elements Xθ and Xθ in F 0

X(θ -θ ) 2 2 ≥ κr 2 θ -θ 2 2 ≥ 2(1 -a)κr 2 s, X(θ -θ ) 2 2 ≤ κr 2 θ -θ 2 2 ≤ 4κr 2 s, where κ = inf θ∈M0 Xθ 2 2 θ 2 2 ≤ κ = sup θ∈M0 Xθ 2 2 θ 2 2 .
Standard results from random matrix theory, see Tropp (2015a), ensure that κ > 0 for a Gaussian design with high probability as long as n ≥ s + C √ s for some positive absolute constant C.

Then choosing r 2 = cρσ 2 4κ , where c ∈]0, 1/8[ and ρ = (1 + a) log(1 + a) + (1 -a) log(1 -a), we get the bounds

X(θ -θ ) 2 2 ≥ σ 2 c(1 -a)ρκ 2κ s, X(θ -θ ) 2 2 ≤ 2σ 2 c log(|B|).
We are now in position to apply (Tsybakov 2008, Theorem 2.5) to conclude that there exists η ∈]0, 1[ (that depends on a) such that inf

θ sup θ∈M0 Pr Å 1 n X θ -Xθ 2 2 ≥ σ 2 c(1 -a)ρκ 4κ s n ã ≥ η.
This lower bound together with Corollary 3 show that θ One can generalize this reasoning to get a minimax lower bound over the larger class of s-sparse vectors, i.e.

V = Span{(a j ) 1≤j≤p } : dim(V ) = s , which is a finite union of subspaces that contains M 0 . Let (a, b) ∈]0, 1[ 2 such that 1 ≤ s ≤ abp and a(-1 + b -log(b)) ≥ log(2)10 , c ∈]0, 1/8[. Then combining (Tsybakov 2008, Theorem 2.5) and (Massart 2007, Lemma 4.6 and Lemma 4.10), we have for η As usual, γ C (θ) = +∞ if the infimum is not attained.

Lemma 4 hereafter recaps the main properties of a gauge that we need. In particular, (ii) is a fundamental result of convex analysis that states that there is a one-to-one correspondence between gauge functions and closed convex sets containing the origin. This allows to identify sets from their gauges, and vice versa. (iii) γ C is finite-valued if, and only if, 0 ∈ int(C), in which case γ C is Lipschitz continuous. (iv) γ C is finite-valued and coercive if, and only if, C is compact and 0 ∈ int(C).

See Vaiter et al (2015a) for the proof.

Observe that thanks to sublinearity, local Lipschitz continuity valid for any finite-valued convex function is streghthned to global Lipschitz continuity. Moreover, γ C is a norm, having C as its unit ball, if and only if C is bounded with nonempty interior and symmetric.

We now define the polar gauge.

B Expectation of the inner product

We start with some definitions and notations that will be used in the proof. For a non-empty closed convex set C ∈ R p , we denote C 0 its minimal selection, i.e. the element of minimal norm in C. This element is of course unique. For a proper lsc and convex function f and γ > 0, its Moreau envelope (or Moreau-Yosida regularization) is defined by

γ f (θ) def = min θ∈R p 1 2γ θ -θ 2 2 + f (θ).
The Moreau envelope enjoys several important properties that we collect in the following lemma.

Lemma 6 Let f be a finite-valued and convex function. Then (i) ( γ f (θ)) γ>0 is a decreasing net, and ∀θ ∈ R p , γ f (θ) f (θ) as γ 0. (ii) γ f ∈ C 1 (R p ) with γ -1 -Lipschitz continuous gradient. (iii) ∀θ ∈ R p , ∇ γ f (θ) → ∂f (θ) 0 and ∇ γ f (θ)

2 ∂f (θ) 0 2
as γ 0.

Proof (i) (Bauschke and Combettes 2011, Proposition 12.32). (ii) (Bauschke and Combettes 2011, Proposition 12.29). (iii) Since f is finite-valued and convex, it is is subdifferentiable everywhere and its subdifferential is a maximal monotone operator with full domain R p , and the result follows from (Bauschke and Combettes 2011, Corollary 23.46(i)).

We are now equipped to prove the following important result 11 . To study EWA, [START_REF] Leung | Information theory and mixing least-squares regressions[END_REF]) used Stein's identity and Catoni (2003, 2007); [START_REF] Dalalyan | Aggregation by exponential weighting, sharp PACbayesian bounds and sparsity[END_REF]; [START_REF] Mai | A bayesian approach for noisy matrix completion: Optimal rate under general sampling distribution[END_REF] used PAC-Bayesian bounds. Our result hereafter turns out to be instrumental to study EWA in the low-temperature regime for general penalties. This result covers of course the situation where J fulfills (H.3). In this case, since ∂J(θ) ⊂ C • by Theorem 1(i), we have ρ = 0 and R = diam(C • ), the diameter of the convex compact set C • containing the origin. It can be shown that, when F (•, y) is strongly coercive, the coercivity assumption (c) can be equivalently stated as J∞(θ) > 0, ∀θ ∈ ker(X) \ {0}, where J∞ is the recession/asymptotic function of J; see e.g. [START_REF] Rockafellar | On sparse reconstruction from Fourier and Gaussian measurements[END_REF].

Proof Let V γ n (θ) We now check that µ γ n (θ)∇V γ n (θ), θθ is dominated by an integrable function. From the definition of the Moreau envelope, we have .

V γ n (θ) = min
11 It will be proved here using Moreau-Yosida regularization. Yet another alternative proof could be based on mollifiers for approximating subdifferentials.

  we used (Hiriart-Urruty and Lemaréchal 2001, Theorem V.3.3.3) in third row, positive homogeneity in the fourth, and Lemma 5 in the fifth. (ii) Again, convexity, positive homogeneity and finite-valuedness are immediate. Coercivity holds by injectivity of D . (a) This is (Vaiter et al 2015a, Proposition 10(i)-(ii)). (b) Denote J = γ C . We have

  not unique in general. The condition on λ n is similar to the one in[START_REF] Negahban | A unified framework for highdimensional analysis of M-estimators with decomposable regularizers[END_REF] where authors established different guarantees for θ term pβ (or rather its lower-bound in Remark 2-5). In particular, for β = O (pn) -1 , this term is on the order O(n -1 ). This choice can be refined in most situations. In particular, for the case of quadratic loss, one can take β = O to remainder terms in (19) and (23) of the same order. In view of this discussion, one may wonder what are the actual benefits of using θ EWA n instead of θ PEN n . Generalizing the arguments of Dalalyan et al (2018), we will show that θ EWA n enjoys one main advantage compared to θ PEN n

  and J def = γ C satisfy Assumptions (H.1)-(H.2) and (H.3). Suppose that λ n ≥ τ σc1 √ 2 log(c2/δ)w(X(C)) n

  and J def = γ C satisfy Assumptions (H.1)-(H.2) and (H.3). Suppose that λ n ≥ (1+δ)τ σw(X(C)) n , for some τ > 1 and δ > 0. Then with probability at least 1 -exp -δ 2 w(X(C)) and (23) hold with the remainder term given by (20) with ν = 1.

  and J def = γ C satisfy Assumptions (H.1)-(H.2) and (H.3), and moreover C is a polytope with vertices V. Suppose that λ n ≥ τ σ max v∈V Xv 2 √ 2δ log(|V|) n

Corollary 4

 4 Let the data generated by (30). Consider the estimators θ EWA n and θ PEN n

Corollary 5

 5 Let the data generated by (30). Consider the estimators θ EWA n and θ PEN n , where F satisfies Assumptions (H.1)-(H.2), and J is the analysis group Lasso (11) with L blocks of equal size K. Assume that D is a frame, and le s(XD) = … max i D bi X XD bi 2→2 /n.

  s log(2p)/(pn) ) and θ PEN n are nearly minimax (up to a logarithmic factor) over M 0 .

  where ρ = -a(-1 + b -log(b))/ log(ab), and κ and κ are now the restricted isometry constants of X of degree 2s, i.e.The set C • is closed convex and contains the origin. When C is also closed and contains the origin, then it coincides with its bipolar, i.e. C •• = C.Let C ⊆ R p be a non-empty closed convex set containing the origin. The gauge of C is the function γ C defined on R p by γ C (θ) = inf λ > 0 : θ ∈ λC .

  γ C is a non-negative, lsc and sublinear function.(ii) C is the unique closed convex set containing the origin such thatC = θ ∈ R p : γ C (θ) ≤ 1 .

Definition 4 (

 4 Polar Gauge) The polar of a gauge γ C is the function γ • C defined byγ • C (ω) = inf µ ≥ 0 : θ, ω ≤ µγ C (θ), ∀θ .An immediate consequence is that gauges polar to each other have the propertyθ, u ≤ γ C (θ)γ • C (u) ∀(θ, u) ∈ dom(γ C ) × dom(γ • C ),(42)just as dual norms satisfy a duality inequality. In fact, polar pairs of gauges correspond to the best inequalities of this type.Lemma 5 Let C ⊆ R p be a closed convex set containing the origin. Then,(ii) γ • C is a gauge function and γ •• C = γ C . (iii) γ • C = γ C • , or equivalently C • = θ ∈ R p : γ • C (θ) ≤ 1 .(iv) The gauge of C and the support function of C are mutually polar, i.e.γ C = σ C • and γ C • = σ C .See[START_REF] Rockafellar | Convex analysis[END_REF]; Hiriart-Urruty and Lemaréchal (2001);Vaiter et al (2015a) for the proof.

Proposition 5

 5 Let the density µn in (2), where (a) F satisfies Assumptions (H.1)-(H.2); (b) J is a finite-valued lower-bounded convex function, and ∃R > 0 and ρ ≥ 0, such that ∀θ ∈ R p ,

F

  (Xθ, y) + λn γ J(θ) and define µ γ n (θ) def = exp -V γ n (θ)/β /Z, where 0 < Z < +∞ is the normalizing constant of the density µn. Assumption (H.1) and Lemma 6(ii)-(iii) tell us that V γ n ∈ C 1 (R p ) and ∇V γ n (θ) → ∂Vn(θ) 0 as γ → 0γ n (θ), θθ dθ.

  Corollary 7 Let the data generated by (30) with a linear operator X : R p1×p2 → R n . Consider the estimators θ

	EWA n	and θ	PEN n

  for θ

	Theorem 2) for θ	PEN n	EWA n	and in (Koltchinskii et al 2011,

To avoid trivialities, the set of minimizers is assumed non-empty, which holds for instance if J is also coercive.

In a forthcoming paper, this framework was extended to cover the even more general class of prox-regular functions.

We consider a scaled version of ϕ for simplicity, but the same conclusions remain valid if we take ϕ(t) = Ct q /q, with C > 0.

It is obvious that the same holds with any positive linear combination.

In the appendix, we provide a self-contained proof based on a novel Moreau-Yosida regularization argument. In (Dalalyan et al 2018, Corollary 1 and 2), an alternative proof is given using an absolute continuity argument since µn is locally Lipschitz, hence a Sobolev function.

As X(C) is compact, it has a dense countable subset.

Not to mention its image with a linear operator as for X(C).

This is for instance the case if X is drawn from the standard Gaussian ensemble andK = O(n) (the O(•) is in fact even o(•)as the remainder term is supposed to go to 0 as n → +∞). In this case, classical concentration bounds of the largest eigenvalue of a Wishart matrix allow to conclude that s(X) = O(1 + K/n) = O(1) with high probabilty.

The noise is iid Gaussian in[START_REF] Suzuki | Convergence rate of bayesian tensor estimator and its minimax optimality[END_REF] and subexponential in[START_REF] Mai | A bayesian approach for noisy matrix completion: Optimal rate under general sampling distribution[END_REF]. The assumptions on the design are also different.

E.g. take b = 1/(1 + e a √2).

Acknowledgements This work was supported by Conseil Régional de Basse-Normandie and partly by Institut Universitaire de France.

Example 3 (Group Lasso) For the group Lasso with L groups of equal size K, M 0 is the subspace group sparse vectors whose group support is included in that of θ 0 . Let s be the number of non-zero (active) groups in θ 0 . Following exactly the same reasoning as for the Lasso, one can show that the risk lower bound in probability scales as Cσ 2 sK/n, which together with Corollary 4, shows that θ EWA n (with β = O σ 2 s √ K + 2 log(L) 2 /(pn) ) and θ

PEN n are nearly minimax (up again to a logarithmic factor) over M 0 . One can also derive the lower bound Cσ 2 s(K + log(L/s))/n over the set of s-block sparse vectors. Such minimax lower bound is comparable to the one in [START_REF] Lounici | Oracle inequalities and optimal inference under group sparsity[END_REF].

Example 4 (Anti-sparsity) Denote the saturation support of θ 0 as I sat and recall the subspace T θ0 form (15). Thus, M 0 = T θ0 is the subspace of vectors which are collinear to sign(θ 0 ) on I sat and free on its complement. Observe that dim(M 0 ) = p -s + 1, where s = |I sat |. Define the set

By construction, B 0 ⊂ M 0 , and θθ 0 ≤ 2(p -s) for all (θ, θ ) ∈ B 0 . Thus following the same arguments as for the Lasso example (using again Varshamov-Gilbert lemma and (Tsybakov 2008, Theorem 2.5)), we conclude that there exists η ∈]0, 1[ (that depends on a) such that inf

where the restricted isometry constants are defined similarly to the Lasso but with respect to the model subspace M 0 of the ∞ norm. Again, for a Gaussian design, κ > 0 with high probability as long as n ≥ (p -s + 1) + C √ p -s + 1 Tropp (2015a).

The obtained minimax lower bound is consistent with the sample complexity thresholds derived in [START_REF] Donoho | Counting the faces of randomly-projected hypercubes and orthants[END_REF] for noiseless recovery from random projections of the hypercube. For a saturation support size s small compared to p, the bound of Corollary 6 (with β = O σ 2 /n 2 ) comes close to the minimax lower bound.

Example 5 (Nuclear norm) Let r = rank(θ 0 ), where θ 0 ∈ R p1×p2 , and p = max(p 1 , p 2 ). For the nuclear norm, M 0 is the manifold of rank-r matrices. Thus arguing as in (Koltchinskii et al 2011, Theorem 5) (who use the Varshamov-Gilbert lemma [START_REF] Massart | Concentration inequalities and model selection[END_REF] to find the covering set), one can show that the minimax risk lower bound over M 0 is Cσ 2 r/n. In view of Corollary 7, we deduce that θ

are nearly minimax over the constant rank manifolds.

A Pre-requisites from convex analysis

We here collect some ingredients from convex analysis that are essential to our exposition.

Monotone conjugate

Lemma 2 Let g be a non-decreasing function on R + that vanishes at 0. Then the following hold:

(i) g + is a proper closed convex and non-decreasing function on R + that vanishes at 0. (ii) If g is also closed and convex, then g ++ = g. (iii) Let f : t ∈ R → g(|t|) such that f is differentiable on R, where g is finite-valued, strictly convex and strongly coercive. Then g + is likewise finite-valued, strictly convex, strongly coercive, and

In particular, both g and g + are strictly increasing on R + .

Proof (i) By (Bauschke and Combettes 2011, Proposition 13.11), g + is a closed convex function. We have inf t≥0 g(t) = -sup t≥0 t • 0 -g(t) = -g + (0). Since g is non-decreasing and g(0) = 0, then g + (0) = -inf t≥0 g(t) = -g(0) = 0. In addition, by ( 5), we have g + (a) ≥ a•0-g(0) = 0, ∀a ∈ R + . This shows that g + is non-negative and dom(g + ) = ∅, and in turn, it is also proper. Let a, b in R + such that a < b. Then

That is, g + is non-decreasing on R + . (ii) This follows from (Rockafellar 1996, Theorem 12.4). (iii) By definition of f , f is a finite-valued function on R, strictly convex, differentiable and strongly coercive. It then follows from (Hiriart-Urruty and Lemaréchal 2001, Corollary X.4.1.4) that f * enjoys the same properties. In turn, using the fact that both f and f * are even, we have g + is strongly coercive, and strict convexity of f (resp. f * ) is equivalent to that of g (resp. g + ). Altogether, this shows the first claim. We now prove that g vanishes only at 0 (and similary for g + ). As g is non-decreasing and strictly convex, we have, for any

We recall the following properties whose proofs can be found in e.g. [START_REF] Rockafellar | Convex analysis[END_REF]; Hiriart-Urruty and Lemaréchal (2001).

Lemma 3 Let C be a non-empty set.

(i) σ C is proper lower semicontonuous (lsc) and sublinear.

(iv) If C is convex and compact with 0 ∈ int(C), then σ C is finite-valued and coercive.

Gauges and polars

Definition 3 (Polar set) Let C be a nonempty convex set. The set C • given by

From coercivity of Vn, the objective in the min is also coercive in (θ, θ) by (Rockafellar and Wets 1998, Exercise 3.29(b)). It then follows from (Rockafellar and Wets 1998, Theorem 3.31) that V γ n is also coercive. In turn, (Rockafellar and Wets 1998, Theorem 11.8(c) and 3.26(a)) allow to assert that for some a ∈]0, +∞[, ∃b ∈] -∞, +∞[ such that for all γ > 0 and θ ∈ R p

Lemma 6-(iii) and assumption (b) on J entail that for any θ ∈ R p ,

Altogether, we have

where the constant C > 0 reflects the lower-boundedness of J. It is easy to see that the function in this upper-bound is integrable, where we also use (H.2). Hence, we can apply the dominated convergence theorem to get

Now, by simple differential calculus (chain and product rules), we have

Integrating the first term, we get by Fubini theorem and the Newton-Leibniz formula

where we used coercivity of V γ n (see ( 43)) to conclude that lim |θ i |→+∞ µ γ n (θ)(θ i -θ i ) = 0. For the second term, we have from Lemma 6(i) that µ γ n → µn as γ → 0. Thus, arguing again as in (43), we can apply the dominated convergence theorem to conclude that lim This concludes the proof.