Robust inference for general framework of projection structures

We develop a general framework of projection structures and study the problem of inference on the unknown parameter within this framework by using empirical Bayes and penalization methods. The main inference problem is the uncertainty quantification, but on the way we solve the estimation and posterior contraction problems as well (and a weak version of the structure recovery problem). The approach is local in that the quality of the inference procedures is measured by the local quantity, the oracle rate, which is the best trade-off between the approximation error by a projection structure and the complexity of that approximating projection structure. The approach is also robust in that the stochastic part of the general framework is assumed to satisfy only certain mild condition, the errors may be non-iid with unknown distribution. We introduce the excessive bias restriction (EBR) under which we establish the local (oracle) confidence optimality of the constructed confidence ball. As the proposed general framework unifies a very broad class of high-dimensional models interesting and important on their own right, the obtained general results deliver a whole avenue of results (many new ones and some known in the literature) for particular models and structures as consequences, including white noise model and density estimation with smoothness structure, linear regression and dictionary learning with sparsity structures, biclustering and stochastic block models with clustering structure, covariance matrix estimation with banding and sparsity structures, and many others. Various adaptive minimax results over various scales follow also from our local results.


Introduction
Suppose we observe a random element (Y, X) ∈ (Y × X ): where P θ is the probability measure of Y (E θ is the corresponding expectation) depending on an unknown high-dimensional parameter of interest θ. By default, Θ = Y = R N , X = R d X for "big" N, d X ∈ N (with the usual norm · ), unless stated otherwise. In some particular models (see Section 6), Y, Θ ⊆ R ∞ can be infinite dimensional and Θ can be a proper subset of Y, e.g., Y = R ∞ and Θ = ℓ 2 . Those particular models can also be reduced to the high-dimensional case by assuming that any θ ∈ Θ ⊆ R ∞ can be arbitrarily well approximated byθ ∈ R N for sufficiently large N ∈ N.
Useful inference in high-dimensional models is not possible without some (approximate) structure on the parameter of interest, the basic idea is to reduce the "effective" dimensionality of the high-dimensional θ. The most popular structural assumptions are smoothness, sparsity and clustering. These structures and many others can be represented via appropriate families of linear spaces L I ⊆ Y, I ∈ I. Precisely, we introduce a finite (or countable) family I of possible structures I and an associated family of linear subspaces {L I , I ∈ I} of Y, which express these structures. This in turn determines the family of corresponding projection operators {P I , I ∈ I} onto linear subspaces {L I , I ∈ I}. The true θ is "approximately structured" according to the family I if θ − P I * θ 2 = min I∈I θ − P I θ 2 is close to zero. If θ − P I * θ 2 = 0, the true θ happens to be exactly structured, i.e., θ ∈ L I * and I * has the meaning of the "true structure" of the true θ.
Let σξ = Y − E θ Y (any Y is its expectation plus zero mean "noise"), σ > 0 be the "noise intensity", then Y = θ(X) + σξ = θ + σξ with E θ ξ = 0. (1.1) The (known) parameter σ is introduced to accommodate certain asymptotic regimes in particular models, σ → 0 reflects an information increase. How the underlying measure P θ,X of Y (and θ = θ(X) = E θ Y ) depends on X will only be exploited when constructing specific families of structures I = I(X) (e.g., in the linear regression model from Section 6.7). We skip the dependence of structures on X in further notation.
The goal is to make inference on the parameter θ based on the data (Y, X): recovery of θ (estimation and posterior contraction), structure recovery, and uncertainty quantification by constructing an optimal confidence set. We pursue local inference in the sense that no structure on θ is a priori imposed, rather we aim to extract as much structure (according to the family of structures I, once I is chosen) as there is in the underlying θ. We will make this notion precise later. We also pursue robust inference in the sense that the distribution of ξ is unknown and can depend on θ (often we suppress this dependence in notation), the coordinates ξ i 's of ξ do not have to be iid, even not independent. The distribution of ξ is assumed to satisfy only certain mild condition; see Condition (A1) in Section 2. We derive non-asymptotic results, which imply asymptotic assertions if needed. Possible asymptotic regimes are: high-dimensional setup N → ∞ (the leading case in the literature for high-dimensional models Y = R N ), decreasing noise level σ → 0, or their combination, e.g., σ = N −1/2 and N → ∞.
For inference on θ, we exploit the empirical Bayes approach and make connection with the penalization method. Since any Bayesian approach always delivers also a posterior π(ϑ|Y ) (in the posteriors, we will use the variable ϑ to distinguish it from the true parameter θ), an accompanying problem of interest is the contraction of the resulting (empirical Bayes) posterior to the "true" structured θ from the frequentist perspective of the "true" measure P θ , which is the distribution of data Y from (1.1). The quality of posterior is characterized by the the posterior contraction rate. In this paper we allow this to be a local quantity, i.e., depending on the true θ, while usually in the literature on Bayesian nonparametrics it is a global quantity related to the minimax estimation rates over certain classes. Despite the rapidly growing number of papers about particular high-dimensional and nonparametric models and structures, there are very few approaches in both frequentist and Bayesian literature that can deal with general classes of high-dimensional and nonparametric models: general posterior contraction rate results are studied in [29,58,28,30], general frameworks for estimation in [28,37]. We should especially highlight the paper [28] which provided us with important insights for the present study (although our approach is very different). However, all estimation (and posterior contraction) results do not reveal how far the optimal estimator (posterior) is from the "true" θ. It is of great importance to quantify this uncertainty, which can be cast into the problem of constructing confidence sets for θ.

Uncertainty quantification problem
One of the prime goals in this paper is to construct confidence sets with optimal properties for model (1.1). The size of a confidence set is measured by the smallest radius of a ball containing this set, hence it suffices to consider confidence balls. For the usual norm · in Θ, a random ball in Θ is B(θ,r) = {θ ∈ Θ : θ − θ ≤r}, where the centerθ =θ(Y ) : Y → Θ and radiusr =r(Y ) : Y → R + = [0, +∞] are measurable functions of the data Y . Let us introduce the optimality framework for uncertainty quantification. The goal is to construct such a confidence ball B(θ, Cr) that for any α 1 , α 2 ∈ (0, 1] and some functional R(θ) = R σ,N (θ), R : Θ → R + , there exist C, c > 0 such that sup θ∈Θ 0 P θ θ / ∈ B(θ, Cr) ≤ α 1 , sup for some Θ 0 , Θ 1 ⊆ Θ. The function R(θ), called the radial rate, is a benchmark for the effective radius of the confidence ball B(θ, Cr). The first expression in (1.2) is called coverage relation and the second size relation. Notice that our approach is local (and hence genuinely adaptive) as the radial rate R(θ) is a function of the "true" parameter θ. The minimax adaptive version of (1.2) for a scale {Θ s , s ∈ S} (indexed by a structural parameter s ∈ S, e.g., smoothness or sparsity) would be obtained by taking Θ 0 = Θ 1 = Θ s and the global radial rate R(θ) = r(Θ s ), for all θ ∈ Θ s , s ∈ S, where r 2 (Θ s ) = infθ sup θ∈Θs E θ θ − θ 2 is the minimax estimation rate over the sets Θ s . Coming back to our local framework ( 1.2), it is desirable to find the smallest R(θ) and the biggest Θ 0 , Θ 1 , for which (1.2) holds. These are contrary requirements, so we have to trade them off against each other. There are different ways of doing this, leading to different optimality frameworks. A traditional optimality framework commonly pursued in the literature (in earlier papers on the topic) was to insist on Θ 0 = Θ in (1.2), i.e., considered confidence sets (called "honest" in some papers) must satisfy the coverage property uniformly over the entire space. Then one tries to find a "honest" confidence set with the fastest radial rate R(θ) and the biggest set Θ 1 (preferably Θ = R N ). However, it turned out that pursuing such an optimality framework often leads to discarding many good procedures and optimality of uninteresting ones. Many "good" confidence sets are not "honest", therefore cannot be optimal and effectively excluded from the consideration. Besides, the results of [39,3] (formulated for the high-dimensional setting Θ = R N ) say basically that the radial rate R(θ) cannot be of a faster order than σN 1/4 for every θ and is at least of the order σN 1/2 for some θ. This means that, in the situations when the targeted optimal size r(θ) (local oracle or global minimax r(Θ s )) can be of a smaller order than σN 1/4 for some θ's (which is typically the case, e.g., for smoothness and sparsity structures), this optimal size cannot be attained in the size relation uniformly over Θ and necessarily R(θ) ≫ r(θ) for some θ ∈ Θ ′ . Thus, insisting on Θ 0 = Θ implies that either the radial rate R(θ) or the set Θ 1 in the size relation has to be sacrificed: Θ 1 = Θ but R(θ) ≫ r(θ) for θ ∈ Θ ′ , or R(θ) = r(θ) but Θ 1 = Θ\Θ ′ .
Another, seemingly more reasonable approach to optimality developed recently in the literature is to sacrifice in the set Θ 0 = Θ\Θ dec by removing a preferably small portion of "deceptive parameters" Θ dec from Θ in the coverage property, so that the size property would then hold with R(θ) = r(θ) uniformly over Θ 1 = Θ. To summarize, there are situations when the overall uniform coverage and optimal size properties cannot hold together and it is necessary to sacrifice at least one of these. This is the core of the so called deceptiveness issue in the uncertainty quantification problem. This deceptiveness phenomenon is well understood only for smoothness and sparsity structures; see [4,8] and further references therein. Typically, global radial rates for specific smoothness (or sparsity) structures are studied in the literature. Local results, delivering also (global) adaptive minimax results for smoothness and sparsity structures, are obtained in [4,8].

The scope
The keywords summarizing the main novel features of our approach in this paper are general, robust, local, refined, and EBR-scale.
The approach is general because we develop a general framework of projection structures and study inference problems within this framework by using empirical Bayes and penalization methods. The main inference problem is the uncertainty quantification, but on the way we solve the estimation problem, posterior contraction problem and (a weak version of ) structure recovery problem as well. As the proposed general framework unifies a broad class of models with various structures, interesting and important on their own right (including graphical/network models), the general framework results deliver a whole avenue of results (many new ones and some known in the literature) for particular models and structures as consequences. There are numerous examples of models and structures falling into our general framework. In Section 6 of this paper, we consider the following models and structures: 1) signal+noise model with smoothness structure (Sobolev ellipsoids and hyperrectangles, analytic and tail classes); 2) signal+noise model under wavelet basis (Besov balls); 3) signal+noise model with (multi-level) sparsity structure (multi-level sparsity is considered for the first time); 4) noisy function on a large graph (Laplacian graph) with smoothness structure; 5) density estimation with smoothness structure; 6) biclustering model (also for stochastic block model and graphon classes); 7) linear regression with sparsity structure, with group sparsity, with group clustering, and with mixture structure; 8) aggregation in nonparametric regression; 9) isotonic, unimodal and convex regressions; 10) dictionary learning; 11) mean matrix with submatrix sparsity; 12) covariance matrix with banding and sparsity structures. Almost all the results on uncertainty quantification problem are new, many known results are improved (obtained local rates improve upon global ones from the literature), some new structures (like multi-level sparsity) are studied for the first time. We emphasize that the scope of our approach extends further than just these specific cases. In fact, the results are readily obtained for any specific model and structure falling into the proposed general framework.
The approach is robust in that the model is allowed to be misspecified. Namely, we introduce a family of normal priors, propose an empirical Bayes procedure, and use the normal likelihood, whereas the true model (1.1) does not have to be normal. In fact, the distribution of ξ in (1.1) is not known, the ξ i 's are not necessarily iid (and not even independent), but only satisfying certain mild exchangeable exponential moment condition; see Condition (A1) in Section 2.
The approach is local in that the quality of the inference procedures is measured by the local quantity, the oracle rate r(θ) (the best rate over a certain family of local rates) which is the best trade-off between the approximation error by a projection structure and the complexity of that approximating projection structure. In a way, it measures the amount of projection structure for each θ: the smaller r(θ), the more structured θ. To the best of our knowledge, there is no general framework on uncertainty quantification, neither in global nor in local settings. This paper attempts to fill this gap by developing the novel local approach, namely, the radial rate R(θ) in ( 1.2) is allowed to be a function of θ, preferably coinciding with the oracle rate r(θ). The proposed local approach is more powerful than global in that we do not need to impose any specific projection structure, because the local approach automatically exploits the "effective" projection structure of each underlying θ, and our local results imply a whole panorama of global minimax adaptive results over various scales at once, see examples in Section 6. We construct a confidence ball by using the empirical Bayes posterior quantities. Since we want the size of our confidence sets to be of the oracle rate order, this comes with the price that the coverage property can hold uniformly only over some set of parameters satisfying the so called excessive bias restriction (EBR) Θ 0 = Θ eb ⊆ Θ. The main result consists in establishing the optimality (1.2) of the constructed confidence ball for the optimality framework Θ 0 = Θ eb , Θ 1 = Θ and the local radial rate r(θ). In addition, we also treat the optimality framework with Θ 0 = Θ 1 = Θ in (1.2) by constructing an alternative confidence ball such that its radius is of the order σN 1/4 + r(θ). Thus, insisting on the overall uniformity in the coverage and size relations leads to the extra term σN 1/4 in the expression for the effective radial rate R(θ) = r(θ) + σN 1/4 . This fact has also been observed by [45] for the case of linear regression with two sparsity classes. Interestingly, this alternative construction of confidence ball is more preferable for some particular models and structures, e.g., biclustering model (stochastic block model), dictionary learning; see Section 6. The point is that, for those models and structures, the extra term σN 1/4 does not increase the order of the radial rate because σN 1/4 ≤ cr(θ) for the "majority" of θ's, precisely, for all θ ∈ Θ\Θ, with some "thin" setΘ. The setΘ can be informally described as a set of "highly structured" parameters. This means that, modulo the setΘ of "highly structured" parameters, there is no deceptiveness issue for those cases. (Speaking informally, these models and structures are already "too difficult" for the term σN 1/4 to spoil the radial rate. ) The approach is refined, namely, we derive the local posterior contraction result for the resulting empirical Bayes posteriorπ(ϑ|Y ) in the refined non-asymptotic exponential probability bound formulation: sup θ∈Θ E θπ ( ϑ − θ 2 ≥ M 0 r 2 (θ) + M σ 2 |Y ) ≤ H 0 e −m 0 M for some fixed M 0 , H 0 , m 0 > 0 and arbitrary M ≥ 0, uniformly in θ ∈ Θ. Besides, we obtain the local estimation result for the empirical Bayes posterior mean estimator, also as a non-asymptotic exponential probability bound. This refined formulation provides a rather sharp characterization of the quality of the posterior and the estimator, (finer than, e.g., traditional oracle inequalities in expectation or asymptotic claims for posterior contraction), allowing subtle analysis for various asymptotic regimes. These results, besides being ingredients for the uncertainty quantification problem, are of interest and importance on its own as they establish the local (oracle) optimality of the empirical Bayes posterior and estimator in this refined formulation. As we have mentioned already, the local results imply in turn the corresponding global (minimax adaptive) results, also in the refined formulation.
Finally, recall that in order to have the targeted optimal radial rate r(θ) in the size relation of the optimality framework (1.2), the overall uniformity in the coverage property of (1.2) must be sacrificed: Θ 0 = Θ eb ⊆ Θ, where Θ eb is a set of parameters satisfying the so called excessive bias restriction (EBR). This set is expected to be of the same type for all models and structures coming from the general framework (1.1): Θ eb = Θ eb (t) = {θ ∈ Θ : b(θ) ≤ tV (θ)}, where b(θ) and V (θ) are the approximation and complexity (or "bias" and "variance") parts of the squared oracle rate r 2 (θ) = b(θ) + V (θ) for the corresponding particular model and structure. It turns out that the EBR leads to a new EBR-scale {Θ eb (t), t ≥ 0}, which gives a slicing of the entire space: Θ = ∪ t≥0 Θ eb (t). This slicing is very suitable for uncertainty quantification and provides a new perspective at the deceptiveness issue: basically, each parameter θ is deceptive (or non deceptive) to some extent. It is the parameter t that measures the deceptiveness in Θ eb (t) and affects the size of the confidence ball needed to provide a guaranteed high coverage uniformly over Θ eb (t).
The paper is organized as follows. In Section 2 we introduce the notation, the prior, describe the empirical Bayes procedure in detail, make a link with the penalization method, and provide some conditions. Section 3, where we also introduce the EBR, contains the main results of the paper. The proofs of the lemmas and theorems are given in Sections 4 and 5 respectively. In Section 6, we demonstrate how the main general results specify to the above mentioned examples of models and structures in local and minimax settings.

Preliminaries
First we introduce some notation and notions, then introduce some conditions and a mixture normal prior. Next, by applying the empirical Bayes approach to the normal likelihood (recall that the true model does not have to be normal), we derive an empirical Bayes posterior which we will use in the construction of the estimator and the confidence ball.
At first reading, one may want to skip this section and go ahead to Section 3 (one will only need to consult some definitions from Section 2) which contains the main results of the paper.

Notation
For n ∈ N, denote [n] = {1, 2, . . . , n} and [n] 0 = {0} ∪ [n]; for a Hilbert space Y, y, z denotes the scalar product between y, z ∈ Y, R + = [0, +∞], N 0 = {0}∪N. For an (n 1 ×n 2 )matrix x = (x ij ) ∈ R n 1 ×n 2 , we will interchangeably use the same notation x to denote the vector x = vec (x ij ) = (x 11 , x 12 . . . , x n 1 n 2 ) T . Conversely, for any x ∈ R n 1 n 2 we can use matricized indexing x = (x 11 , x 12 , . . . , x n 1 n 2 ) T . Most of the time the vector notation will be used, and it should be clear from the context which notation is meant in each expression. For two nonnegative sequences (a l ) and (b l ), a l b l means a l ≤ cb l for all l (its range should be clear from the context) with some absolute c > 0, and a l ≍ b l means that a l b l and b l a l .
For a set S, |S| denotes its cardinality. We will often denote matrices and operators by upright capital letters, the identity matrix is denoted by I, 1 E = 1{E} stands for the indicator function of the event E. As usual, N(µ, Σ) is the multivariate normal distribution with mean µ and covariance matrix Σ, its density at point x is denoted by ϕ(x, µ, Σ). The dimensions of matrices and normal distributions should be clear from the context. Let P ⊥ I = I − P I be the projection operator onto the orthogonal complement L ⊥ I of L I . We use both notation P I and P L I (P ⊥ I and P ⊥ L I ) to denote the projection operator onto the linear subspace L I (onto the orthogonal complement L ⊥ I of L I ).

Slicing into structural layers, complexity of a layer
As we mentioned in the introduction, useful inference is not possible without some structure on parameter θ. The structure on each θ ∈ Θ is represented by the slicing Θ ⊆ ∪ I∈I L I . Indeed, then for any θ ∈ Θ there exists an I ∈ I such that θ ∈ L I , this I (and L I ) has the meaning of the structure of that θ. Structure I of θ is always determined via the corresponding linear space L I ∋ θ, so by saying "I is the structure of θ" we mean that θ ∈ L I (or can be well approximated by P I θ).

Remark 1.
There may be L I = L I ′ for different I, I ′ ∈ I, in other words, the family of structures I can have redundancy. Without loss of generality, we could assume that the family I is "cleaned up" in the sense that each subspace L ∈ L I is represented in I by only one (arbitrary) element J = J(L) from the set {I ∈ I : L I = L}. Mathematically, this means that the resulting "cleaned up" family I of structures consists of equivalence classes on the original collection of all structures with the equivalence relation: I 1 ∼ I 2 if and only if L I 1 = L I 2 , so that |I| = |L I | in this case.
However, in general |L I | ≤ |I| and this redundancy can be beneficial in some practical situations when searching (or optimizing in an inference procedure) over a possibly redundant family of structures I can be described and realized easier than over the "cleaned up" version of it. The only price for this redundancy is a bigger sum (because of more terms) in Condition (A2), resulting in a bigger constant C ν in Condition (A2) for a redundant I. In many situations this is a mild price, see for example Sections 6.7.3 and 6. 7.4. Clearly, θ can have many structures, and we would like to distinguish the "simplest" structure of θ. For that, we introduce a measure of structure complexity below. Suppose the following condition is fulfilled for the vector ξ from (1.1): for some α > 0 and (d I ) I∈I with d I ≥ 0, The quantity d I can be seen as statistical dimension of structure I, reflecting in a way the complexity of the structure I (space L I ): the bigger d I , the more complex the structure I. Notice that if the distribution of ξ does not depend on θ, then there is no sup θ∈Θ in (2.1).
Typically, in such cases d I ≍ dim(L I ). The bound (A0) holds, for example, for standard normal ξ with α = 0.43 and d I = dim(L I ); see Remark 5 below.
A subfamily J ⊆ I of structures is called structural layer (or just layer) in I. By L J = {L I , I ∈ J } we denote the corresponding layer in the family of all linear subspaces L I = {L I , I ∈ I}. Now we characterize the complexity of a layer J ⊆ I. A version of this key notion (in a different context) is present in [28]. Let us give a simple (but important) heuristics for controlling the maximal projected error max I∈J P I ξ 2 over a layer J . Denote d J = max I∈J d I . Using (A0) and Jensen's inequality, we derive Hence, under (A0) we control the maximal projected error max I∈J P I ξ 2 up to the order of d J + log |L J |. It is this sum that characterizes the complexity of the layer J (layer L J ). Define the complexity of the layer J (layer L J ) as The second equality holds because in general |L J | ≤ |J | in view of Remark 1. Next, introduce a surjective function s : I → S, for some set S, called the structural slicing mapping. This function slices the family I in layers I s = {I ∈ I : s(I) = s}, s ∈ S, i.e., I = ∪ s∈S I s , S marks the collection of all layers I s . Clearly, the structure I belongs to the layer I s(I) , and any slicing of I can be realized by appropriate function s(I), I ∈ I. This also leads to the corresponding slicing of the parameter space Θ ⊆ ∪ s∈S L Is . The quantity s(I) typically describes some features of the space L I . For example, s(I) can be the dimension (or some function of it) of L I .
According to (2.3) and Remark 1, the complexity of the layer I s is then where, slightly abusing notation, we adopted the following notional conventions for brevity: c(s) = c(I s ), d s = d Is = max I∈Is d I , L s = L Is = {L I , I ∈ I s }, with c(J ) defined by (2.3).

Conditions
Recall that we have introduced a structural slicing mapping s : I → S, which slices the family of structures I and the parameter space Θ in structural layers: I = ∪ s∈S I s and Θ ⊆ ∪ s∈S L s , s ∈ S, where I s = {I ∈ I : s(I) = s} and L s = {L I : s(I) = s}.
In previous section we proposed condition (A0) which led to the notion (2.3) of layer complexity c(J ). We can relax condition (A0) by imposing it on the layers I s only (instead of all I ∈ I). Precisely, throughout the rest of the paper we impose the following so called exchangeable exponential moment condition on the random vector ξ from (1.1).
Condition (A1). For some structural slicing mapping s : I → S, sequence (d s ) s∈S and α > 0, Without loss of generality, assume α ∈ (0, 1] and d s(I) dim(L I ), I ∈ I. Remark 5. Condition (A1) holds for high-dimensional independent normal ξ i 's with d s(I) = dim(L I ), irrespective of the linear spaces L I , I ∈ I. In fact, in this case even stronger 432. By taking t = 0.4, we derive Ee 0.4 P I ξ 2 ≤ e d I . Hence, Condition (A0) is fulfilled with α = 0.4 and d I = dim(L I ).
Importantly, Condition (A1) allows quite some flexibility, which is crucial when treating concrete models and significantly broadens the range of models falling into our general framework. First, the distribution of ξ may depend on θ (note however that in many important models from Section 6, the distribution of ξ does not depend on θ). Besides, the coordinates ξ i 's of ξ do not have to be iid and may even be non-independent. For example, for the "signal+noise" model with the sparsity structure, it was shown in [8] that Condition (A1) is fulfilled for the ξ i 's generated according an autoregressive model. In case of "signal+noise" model with the sparsity structure, one can relate (cf. [8]) Condition (A1) to the so called sub-gaussianity condition on ξ = (ξ i , i ∈ [N ]). The vector ξ is called sub-gaussian with parameter ρ > 0 if In this case, in [8] we showed that the sub-gaussianity condition is equivalent to Condition (A1) for independent ξ i 's; for dependent ξ i 's, the sub-gaussianity condition (2.5) and Condition (A1) are close, but in general incomparable. For example, if ξ i = ξ 0 , i ∈ [n], for some bounded random variable ξ 0 (say, uniform on [−1, 1]), then a version of Condition (A1) (for the sparsity structure) trivially holds whereas the sub-gaussianity condition is not fulfilled. It is desirable to use a slicing s : I → S that is parsimonious in the sense that the maximum d s = max I∈Is d I degenerates, i.e., d I = d J for all I, J ∈ I s , so d s(I) = d I . In other words, d I = h(s(I)), I ∈ I, for some function h : S → N 0 . Since typically d I ≍ dim(L I ), in many examples of Section 6 we will take a slicing s such that dim(L I ) = h(s(I)), I ∈ I, for some function h.
The complexity c(s) of the layer I s is defined in the previous section by (2.4). Instead, from now on we will work with a majorant of the layer complexity, some function ρ : S → R + such that ρ(s) ≥ d s + log |I s | ≥ c(s), s ∈ S.
(2.6) Remark 6. We can use an up-to-a-constant majorant ρ(s) c(s) instead of (2.6) by adjusting α ∈ (0, 1] in (A1), but without loss of generality we stick to (2.6) for the sake of a clean mathematical exposition.
The reasoning in (2.2) gives a heuristic explanation why later on at least a multiple of the complexity c(s) must be present in the prior on I (and as penalty term in the penalization method). This quantity will also enter the local (oracle) rate. It is therefore desirable to use the smallest possible majorant ρ(s) in (2.6) in order to derive stronger results. In this light, the best majorant in (2.6) is the complexity itself ρ(s) = d s + log |I s | = c(s) for the "cleaned up" family of structures I (see Remark 1). On the other hand, in the end any majorant ρ(s) c(s) will do the job. The reason to allow an arbitrary majorant ρ(s) is that d s and |I s | (or |L s |) may be difficult to compute, whereas some closed form upper bounds can be derived. Of course, this comes at the price of a bigger resulting local rate because this majorant will then enter the local rate.
In the proof of Theorem 1 below, we will need a bound for E θ P I ξ 4 1/2 , for each I ∈ I. Condition (A1) ensures such a bound. Indeed, since x 2 ≤ e 2x for all x ≥ 0, by the Hölder inequality and (A1), we obtain for any t ∈ (0, 1/2] and I ∈ I, In case ξ i ind ∼ N(0, 1), Condition (A0) is fulfilled with d I = dim(L I ), so that (A1) holds also with d s = max I∈Is d I . As P I ξ 2 ∼ χ 2 d I , instead of (2.7), a better bound can be used in this case: E P I ξ 4 1/2 = d 2 We finish this section by introducing the conditions on the family of structures I and the majorant ρ(s) from (2.6), which we will need in the theorems.
Remark 7. Notice that in view of (2.6), for ν ≥ 1 we obtain the bound So, (A2) is satisfied if s∈S e −νds ≤ C ν for ν ≥ 1. Informally, this condition means that the majorant ρ is large enough to match the massiveness (reflected by the cardinalities |I s |, s ∈ S) and the complexity (reflected by the sequence (d s ) s∈S ) of the family of structures I.
The constants α ∈ (0, 1] and ν > 0 will be fixed throughout and we omit the dependence on these constants in all further notation.

Multivariate normal prior
In this section we construct an (empirical) Bayesian procedure and make connection with the penalization method for making inference on θ. Recall that the true parameter θ is assumed to be well approximated by its structured version P I * θ (e.g., it itself can be structured θ = P I * θ), for some "true" structure I * ∈ I. The true structure I * is unknown, so at a later stage we will put a prior on the family of structures I. For now, given a structure I, consider the model Y = P I θ + σξ, approximating the original model (1.1), where P I is the projection operator onto space L I , and put first an "unstructured" prior Π on the "unstructured" θ ∈ Θ as follows: θ ∼ Π = N(µ, κσ 2 I), where κ = e − 1 and the parameter µ ∈ Y is to be chosen by the empirical Bayes method later. The "unstructured" prior Π on θ leads to the "structured" prior π I on the "structured" θ I P I θ: π I (ϑ) = N(P I µ, κσ 2 P I ), I ∈ I, κ = e − 1.
( 2.8) In this way, we constructed the conditional prior on θ given I: θ|I ∼ π I (ϑ). The rather specific choice of κ = e − 1 is made for the sake of clean mathematical exposition in later calculations, many other choices are actually possible. The next very important step in the Bayesian analysis below is that we use the normal likelihood ℓ(θ, Y ) = i N(θ i , σ 2 ), whereas the "true" model Y ∼ P θ is not assumed to be normal, but only satisfying Condition (A1). Formally applying Bayesian approach to this prior and the normal likelihood ℓ(θ, Y ) delivers the marginal distribution Y ∼ P Y,I = N(P I µ, I + κP I ) and the following posterior distribution on θ: Note that in general the covariance matrix in (2.8) is not invertible, but the Bayes formula for the conjugate normal-normal model still holds with the Moore-Penrose inverse P − I of P I instead of the usual inverse (recall that P − = P for any projection operator P).

Empirical Bayes posterior
The parameter µ is yet to be chosen in the prior. We apply the empirical Bayes approach. The marginal likelihood P Y is readily maximized with respect to µ:  which is essentially the penalization method with the penalty pen(I) = 2κρ(s(I))+dim(L I ).

Main results
In this section we present the main results of the paper.

Oracle rate
For I ∈ I, consider the projection estimator P I Y for estimating θ. By Condition (A1) and Jensen's inequality, we obtain the following upper bound for the estimator P I Y : for some C > 0, Ideally, we would like to mimic the local rate for the best (oracle) choice of the projection structure min I∈I θ − P I θ 2 + σ 2 d s(I) , uniformly in θ ∈ Θ. However, as is shown for some particular models, this is impossible unless we use a majorant ρ(s(I)) ≥ d s(I) + log |I s(I) | instead of just d s(I) . The layer complexity term log |I s(I) | is the "price" for not knowing the structure. This motivates the following definition. Introduce the family of local rates r 2 (I, θ) = θ − P I θ 2 + σ 2 ρ(s(I)), I ∈ I, for some ρ(s) satisfying (2.6) and the slicing mapping s(I) from Condition (A1). For each θ there exists the best structure I o = I o (θ) = I o (θ, σ 2 ) (if not unique, take any minimizer) corresponding to the fastest local rate representing the optimal trade-off between the approximation term θ − P Io θ 2 and the complexity term ρ(s(I o )) satisfying (2.6). We call I o by oracle structure (or just oracle) and the quantity r 2 (θ) by oracle rate.
Remark 10. Often we will have that d s(I) = dim(L I ) = d I and ρ(s(I)) = d I + log |I s(I) |. This is the case in many particular models and structures that we consider in Section 6. If I * ∈ I is the true structure, i.e., θ ∈ L I * , s * = s(I * ) and I s * = {I * }, then, by the oracle definition (3.1) and the facts that θ − P I * θ 2 = 0 and L I * ⊆ R N , we have r 2 (θ) ≤ r 2 (I * , θ) = σ 2 ρ(s(I * )) = σ 2 d s( If such a true structure does not exist, we can assume without loss of generality that there is anĪ ∈ I such that LĪ = R N ,s = s(Ī) and Is = {Ī}. This would lead again to the bound (3.2): r 2 (θ) ≤ r 2 (Ī, θ) = σ 2 dim(LĪ) = N σ 2 . This is of course not surprising as the oracle performance should not be worse than that of the simplistic procedureθ = Y .
Remark 11. Suppose we have two different family of structures I 1 and I 2 , with corresponding (different) families of linear spaces L I and (different) majorants. We say that the family I 1 covers the family I 2 if for any I ∈ I 2 there exists I ′ = I ′ (I) ∈ I 1 such that r 2 (I ′ , θ) ≤ r 2 (I, θ) for all θ ∈ Θ (up-to-a-constant relation will do as well). If I 1 covers I 2 , there is no point in considering the family I 2 , one should use the family I 1 . The family I 1 and the family I 2 covered by I 1 could be of very different natures. But sometimes I 1 can be a subfamily of I 2 . This happens when a chunk of structures in I 2 can be dominated by just one structure. Then we can remove those structures without any harm, obtaining a new adjusted family I 1 . The complexity term in the majorant gets adjusted for some I ∈ I 1 , leading to an elbow effect in the rate and improving the resulting oracle rate. We will see how this elbow effect is exhibited in several examples of Section 6.

Estimation and contraction results with oracle rate
Recall the quantities: the empirical Bayes posteriorπ(ϑ|Y ), which is either EBMA posterior π(ϑ|Y ) defined by (2.15) or EBMS posteriorπ(ϑ|Y ) defined by (2.20); the empirical Bayes posterior meanθ, which is eitherθ defined by (2.18) orθ defined by (2.20); and the oracle rate r(θ) defined by (3.1). The following theorem establishes that the empirical Bayes posteriorπ(ϑ|Y ) contracts (from the frequentist P θ -perspective) to θ with the oracle rate r(θ), and the empirical Bayes posterior meanθ converges to θ with the oracle rate r(θ), uniformly over the entire parameter space.
The constants in the theorem depend only on α and some also on κ, the exact expressions can be found in the proof.

Remark 12.
Notice that already claim (3.3) of Theorem 1 contains an oracle bound for the estimatorθ. Indeed, by Jensen's inequality, we get the oracle inequality in expectation: Similarly we can show that also (3.4) implies (3.5). This means that claim (3.4) is actually stronger than (3.5) and therefore requires a separate proof.
Remark 13. The non-asymptotic exponential probability bounds in the both claims of the theorem provide a very refined characterization of the quality of the posteriorπ(ϑ|Y ) and estimatorθ, finer than, e.g., the traditional oracle inequalities in expectation like (3.5) (since (3.5) follows from (3.4), see Remark 12). This refined formulation allows for subtle analysis in various asymptotic regimes (N → ∞, σ → 0, or their combination) as we can let M depend in any way on N , σ, or both.
When proving the above theorem, as byproduct we also obtain a result about the frequentist behavior of the structure selectorÎ and the empirical Bayes posterior for I, saying basically thatÎ andπ(I|Y ) "live" on a set that is, in a sense, almost as good as the oracle I o .
(i) Let c 1 , c 2 , c 3 be the constants defined in Lemma 2. Then (ii) Let κ ≥ α −1 ν (implied by (2.11)) and Condition (A3) be fulfilled. Then there exists m ′ 1 > 0 such that where I * = I * (θ, δ) is defined by (3.7). We can interpret the above theorem as structure recovery, but in a somewhat weak sense. Namely, Theorem 2 says basically that the empirical Bayes posteriorπ(I|Y ) and the structure selectorÎ "live" in the set of structures resembling the oracle structure I o , in the sense that the rates and complexities for the structures from this set are in a proximity of the oracle rate and complexity, respectively. Recall that in general the oracle structure is not the same as the true structure. Notice that this weak structure recovery is always possible as there are no conditions on θ.

Confidence ball under EBR
Theorem 1 establishes strong local optimal properties of the empirical Bayes posterior π(ϑ|Y ) and meanθ, but this is not enough to solve the uncertainty quantification problem yet. As a first candidate for confidence ball, let us construct a credible ball by using the EBMS posteriorπ(ϑ|Y ) =π(ϑ|Y ) defined by (2.20). Asπ(ϑ|Y ) = N θ , κ κ+1 σ 2 PÎ , denoting by Since χ 2 dim(LÎ ),α is bounded by a constant multiple of dim(LÎ ), for simplicity the latter can replace the former to obtain a credible ball. Then B(θ, M σ[dim(LÎ )] 1/2 ) is a credible ball for θ, which can be guaranteed to have a given level of credibility by choosing a sufficiently large M . However, B(θ, M σ[dim(LÎ )] 1/2 ) cannot have a guaranteed coverage, since otherwise in some particular models (cf. [8]) this would mean that the estimatorθ would converge to θ uniformly in θ ∈ Θ at the smaller oracle rate withρ(s(I o )) = dim(L Io ) instead of ρ(s(I o )) = d s(Io) + log |I s(Io) |. But log |I s(Io) | can be the dominating term in ρ(s(I o )), e.g., for sparsity structures (see [8] and Section 6). This would contradict the lower bounds from the literature. Basically, the posteriorπ(ϑ|Y ) is well concentrated (in fact, " too concentrated"), but not around the truth, rather around its meanθ which in general is away from the truth by the distance of a bigger order than the concentration rate. Hence, to obtain coverage, the radius of confidence balls must be at least of the order ρ(s(I o )) = d s(Io) + log |I s(Io) |. Of course, the oracle structure I o is not known, but we have the structure selectorÎ defined by (2.19), which is in a way close to the oracle structure, according to Theorem 2.
The above heuristics suggests to use ρ(s(Î)) as a proxy for ρ(s(I o )). According to Theorem 2,Î lives in the "complexity shell" δσ 2 ρ(s(I * )) − M σ 2 ≤ σ 2 ρ(s(Î)) ≤ c 3 r 2 (θ) + M σ 2 with a large probability. So, if we want the size of confidence ball to be not of a bigger order than oracle rate, it seems reasonable to use the following data dependent radiuŝ r 2 =r 2 (Y ) = σ 2 + σ 2 ρ(s(Î)). (3.9) We will show that the size property holds for the radial rate equal to the oracle rate, uniformly over θ ∈ Θ. But then there is an inevitable problem with coverage: the coverage property does not hold uniformly. Indeed, the complexity shell can be too wide if σ 2 ρ(s(I * )) ≪ r 2 (θ). If this happens (for deceptive θ's), then the coverage property of a ball with radius of orderr cannot be guaranteed because its radius can be of a smaller order than the oracle rate r 2 (θ). This problem will not occur for those θ's (called non-deceptive) for which the approximation term of the oracle rate is within a multiple of its complexity term. This discussion motivates introducing the following condition.
Condition EBR. We say that θ ∈ Θ satisfies the excessive bias restriction (EBR) condition with structural parameter t ≥ 0 if θ ∈ Θ eb (t), where the corresponding set (called the EBR class) is where the τ 0 -oracle structure I * = I o (θ, τ 0 σ 2 ) is defined by (3.7). The condition EBR essentially requires that the approximation term of the τ 0 -oracle rate r 2 (I * , θ) is dominated by a multiple of its complexity term (additional σ 2 is needed to handle the case ρ(s(I * )) = 0). Clearly, Θ eb (t 1 ) ⊆ Θ eb (t 2 ) for t 1 ≤ t 2 . Now we use the centerθ and the radiusr to construct a confidence ball for θ. The following theorem describes the coverage and size properties of the confidence ball based onθ andr.
The size (second) relation holds uniformly in θ ∈ Θ without Condition (A3). Moreover, if, instead of Condition (A3), stronger Condition (A3') is fulfilled, then a stronger version of the size relation holds: Recall that I * from (3.10) is actually the τ 0 -oracle. It may be desirable to impose an EBR condition in terms of the "standard" oracle I o rather than the τ 0 -oracle. By rewriting the original model ( is not difficult to see that we can construct a confidence ball with the radius √ τ 0RM satisfying the coverage property as above, but now uniformly over Θ eb (t, 1).

Remark 15.
When proving the coverage relation of Theorem 3, we actually established the following uniform local assertion: there exist constants M 2 , α 1 , m ′′ 1 , H 2 , m 2 > 0 such that for any θ ∈ Θ and any M ≥ 0, where the constants H 1 , m 1 are defined in Theorem 1, C ν is from Condition (A2), and the quantity b(θ) (called excessive bias ratio) is defined by .
Although the newly formulated coverage relation (3.11) is now uniform over the entire space θ ∈ Θ, the main (and unavoidable) problem is its dependence on b(θ). That is why we introduced the EBR condition which essentially provides control over the quantity b(θ): Remark 16. The smaller constant τ 0 (involved in the definition of the EBR condition) is, the less restrictive the EBR condition is, the limiting case τ 0 ↓ 0 corresponds basically to no condition. We treat a general situation, with only Condition (A1) assumed for ξ, so that we have a lower bound for τ 0 in terms of α which is possibly too conservative for each specific distribution of ξ. However, even for any specific distribution of ξ, the value of the constant τ 0 > 0 in the EBR condition is always bounded away from zero (further from zero for "bad" ξ's).

Remark 17.
The EBR leads to the new EBR-scale {Θ eb (t), t ≥ 0} which gives a slicing of the entire space Θ = ∪ t≥0 Θ eb (t) This slicing is very suitable for uncertainty quantification and provides a new perspective at the deceptiveness issue (discussed in the Introduction): basically, each parameter θ is deceptive (or non deceptive) to some extent. It is the parameter t that measures the deceptiveness in Θ eb (t) and affects the size of the confidence ball needed to provide a guaranteed high coverage uniformly over Θ eb (t).

Confidence ball of N 1/4 -radius without EBR
Suppose we want to construct a confidence ball of a full coverage uniformly over the whole space Θ. Recall however that for "signal+noise" models, in view of the negative results of [39,18,3,45] mentioned in the Introduction, no data dependent ball can have uniform coverage and adaptive size simultaneously. When insisting on the uniform coverage, one must have an additional term of the order σN 1/4 in the radial radius. Let us give a heuristics behind this. An idea is to mimic the quantity θ −θ 2 byR 2 = Y −θ 2 . Clearly, there is a lot of bias inR 2 , the biggest part of which is due to the term σ 2 ξ 2 contained inR.
To de-bias for that part, we need to subtract its expectation σ 2 E ξ 2 . However, even the de-biased version ofR 2 can only be controlled up to a margin of the order σ 2 √ N . That is why a term of the order σN 1/4 is necessary in the radius of the confidence ball to provide coverage uniformly over the whole space Θ.
To handle some technical issues, we impose the following condition.
Indeed, in this case we can "duplicate" the observations by randomization at the cost of doubling the variance in the following manner: create samples If the sub-gaussianity condition (2.5) is fulfilled for ξ ′ , then ψ 1 (M ) = e −ρM . By Chebyshev's inequality, we see that the second relation in (A4) is fulfilled with function Coming back to the problem of constructing a confidence ball of full coverage uniformly over Θ, letθ andÎ be based on the sample Y and defined as before. We propose to mimic θ −θ 2 by the de-biased quantity Y ′ −θ 2 − σ 2 V (Y ′ ) plus additional σ 2 √ N -order term to control its oscillations, leading us to the following data dependent radius By taking large enough M , we can ensure the coverage and size relations uniformly over the entire space Θ. Thus, the results of Theorem 4 are to be interpreted as the coverage and size relations in the optimality framework (1.2) with Θ 0 = Θ 1 = Θ and the effective radial rate R(θ) = g M (θ, N ) ≍ r(θ) + σN 1/4 (for now disregarding the constants and the inflating factor M as we consider only the order of the radial rate). Since the both sets Θ 0 = Θ 1 = Θ = R N are the biggest possible, the deceptiveness phenomenon manifests itself only in the effective radial rate R(θ), which can be of a bigger order than the oracle rate r(θ) for θ ∈Θ, where (for some c > 0) (3.14) Equivalently, this can be seen as the optimality framework (1.2) with Θ 0 = Θ = R N , Θ 1 = Θ\Θ = R N \Θ and the effective radial rate R(θ) ≍ r(θ) + σN 1/4 Cr(θ) is of the oracle rate order for θ ∈ Θ 1 . Now the deceptiveness phenomenon manifests itself in the fact that Θ 1 = Θ\Θ, not the whole Θ.
In fact, the massiveness of the setΘ measures how much the deceptiveness phenomenon is present in particular models and structures. Loosely speaking, models and structures, where "good" estimation (r 2 (θ) σ 2 N 1/2 ) is possible for "many" θ's (Θ is massive), suffer more from the deceptiveness phenomenon. For example, these are all models with sparsity structures in Section 6.7, as the setΘ is a substantial part of Θ = R N in those cases.
On the other hand, the deceptiveness phenomenon becomes effectively marginal for some "uninformative" particular models and structures, e.g., biclustering model (stochastic block model), dictionary learning (see Section 6), because in these cases the setΘ is a very "thin" subset of R N and can informally be described as set of highly structured parameters. In these cases the extra term σN 1/4 in the radial rate R(θ) does not increase its order as σN 1/4 r(θ) for the "majority" of θ's: θ ∈ Θ 1 = Θ\Θ. This means that, modulo the set Θ of highly structured parameters, there is no deceptiveness issue for those cases. Indeed, there is no payment in terms of removing deceptive parameters from the parameter space Θ in the coverage relation and the size relation holds uniformly over Θ 1 = Θ\Θ which is "almost" the whole space Θ.

Technical lemmas
We provide a couple of technical lemmas used in the proofs of the main results. Recall that π(I|Y ) is eitherπ(I|Y ) defined by (2.17) orπ(I|Y ) = 1{I =Î} defined by (2.21). In the latter case E θπ (I|Y ) = P θ (Î = I). In what follows, denotep I =π(I|Y ) for brevity. Lemma 1. Let Condition (A1) be fulfilled. Then for any θ ∈ Θ and I, I 0 ∈ I where the constants A α = α 3 and D α = 1 + α 2 . If holds for any I, I 0 ∈ I. Using the relations P I − P I 0 = (P I − P I 0 )P L I +L I 0 , P L I +L I 0 x 2 ≤ P I x 2 + P I 0 x 2 , x ∈ Y, and the inequality 2ab ≤ a 2 /4 + 4b 2 (for any a, b ∈ R), we derive The last bound and (4.1) imply that In casep I =π(I|Y ) =π(I|Y ) = 1{Î = I}, (2.17), the definition (2. 19) ofÎ and the Markov inequality imply that, for any I, I 0 ∈ I and any h ≥ 0, Combining (4.2) and (4.3), we derive for any I, I 0 ∈ I and any h ∈ [0, 1], The lemma follows for h = α 4 from the last display and the relation which is in turn obtained by using the Hölder inequality and Condition (A1).
In case L I ⊆ L I 0 , take h = α in (4.4) and, instead of (4 In case L I 0 ⊆ L I , take h = α in (4.4) and, instead of (4 Note that above lemma holds for any I 0 ∈ I. By taking I 0 = I o defined by (3.1), we derive the next lemma.
The definition (2.10) of λ I entails that Combining the last relation with Lemma 1 (for I 0 = I o ), we derive that which completes the proof with the constants

Proofs of the theorems
Here we gather the proofs of all the theorems. By C 1 , C 2 etc., we denote constants which are different in different proofs.
Proof of Theorem 1. Recall the constants c 1 , c 2 , c 3 defined in the proof of Lemma 2 and the notationp I =π(I|Y ). For any θ ∈ Θ, M ≥ 0 and some constant M 0 to be chosen later, I ∈ I, where constants C 1 , C 2 > 0 are to be chosen later. We havê Now we need to bound the quantities E θ T 1 , E θ T 2 and E θ T 3 . By using the Markov inequality and Condition (A1), we have The last relation and Condition (A2) yield the bound for E θ T 1 : Using this, Lemma 2 and the fact that I∈I e −c 1 ρ(s(I)) ≤ C ν (in view of Condition (A2) and because c 1 > 2ν), we bound E θ T 2 as follows: It remains to establish the last bound for E θ T 3 . For I ∈ O M , we have that Recall that, in view of (2.16),π I (ϑ|Y ) = N(P I Y, (1 − e −1 )σ 2 P I ). Let P Z be the measure Using this, the last display and the fact that r 2 (θ) This completes the proof of the first assertion since, in view of (5.1), (5.2), (5.3) and the last display, we established the claim (3.
, the fact that θ T (P L I −P I 0 )θ = P L I ∩L ⊥ Io θ 2 ≤ σ 2 ρ(s(I)) and Lemma 1 (in case L I 0 ⊆ L I ) with h = α, we obtain for each Combining the last display with Condition (A2) completes the proof: Proof of Theorem 3. We first establish the coverage property. The constants M 1 , H 1 and m 1 are defined in Theorem 1. Take is given by (3.12). Combining this with the claim (3.4) from Theorem 1, the claim (ii) from Theorem 2 and the definition (3.9) ofr yields the coverage property: Remind the notationp I =π(I|Y ) = 1{I =Î} defined by (2.21). From Lemma 2 and the last relation, it follows that for all I ∈ G(M ) The last display implies that, for any θ ∈ Θ, If, instead of Condition (A3), stronger Condition (A3') is fulfilled, then the stronger version of the size relation follows immediately from property (iii) of Theorem 2: Proof of Theorem 4. Since Y ′ = P I * θ + ξ ′ , we rewrite (3.13) as . According to Condition (A4),θ andÎ are based on Y and independent of ξ ′ . Using this fact, the first relation from (A4) and Theorem 1, we obtain that Combining this with (5.11), (5.12) and the second relation from (A4) yields the coverage property: Let us show the size property. By ( 5.12),

Applications
In this section we introduce a number of particular models and structures which fall in the studied general framework and for which local and adaptive (global) minimax results (for all the three problems: estimation, posterior contraction rate and confidence sets) can be derived as consequences of our local results for the general framework. For all the examples (of particular models with particular structures) considered below, we specify the structures I, the structural slicing mapping s : I → S and the layer complexity function ρ(s). We will further verify Conditions (A1), (A2), (A3) and (A4), whenever appropriate. In view of Remarks 5 and 18, Conditions (A1) and (A4) hold with d s(I) = dim(L I ) in all particular models with ξ i ind ∼ N(0, 1). Therefore, we will not verify Conditions (A1) and (A4) for models with ξ i ind ∼ N(0, 1). We keep the same notation for all the quantities involved as for the general framework, with the understanding that these are specialized for the particular models and structures, and some constants must be adjusted. First we summarize the results of Theorems 1, 2, 3 and 4 by the following two corollaries.
If in addition Condition (A4) is fulfilled, then for any M ≥ 0, Remark 19. The properties (ii) and (iii) of Theorem 2 can also be included in Corollary 1, but we omit it, because these properties are only auxiliary results used for proving the size relations of Theorem 3. If additionally Condition (A3') is assumed for the property (iv), then the stronger uniform version of (iv) holds: sup θ∈Θ P θ r 2 ≥ M ′ 0 ρ(s(I o ))σ 2 + (M + 1)σ 2 ≤ C ν e −M/2 . Claim (v) of Corollary 1 can be formulated for the local version of coverage relation of Theorem 3 in terms of b(θ) (given by (3.12)) if needed.
If (6.1) holds, we say that the oracle r 2 (θ) covers the scale {Θ β , β ∈ B}. Under (6.1), the adaptive (with respect to the structural parameter β ∈ B) minimax result follows immediately from Theorem 1: In case the radius of confidence ball is of the order r(θ) + σN 1/4 , we assume that the conditions of Theorem 4 instead of Theorem 3 are fulfilled and the third claim of Corollary 2 is replaced as follows: We do not specialize Theorem 2 and the coverage relation of Theorems 3 and 4 for the scale {Θ β , β ∈ B}, because it does not make much sense to specialize these claims for any scale. Theorem 2 holds uniformly in θ ∈ Θ, hence uniformly over any Θ β . The coverage relation in Theorem 3 holds uniformly over the EBR class Θ eb , so it will certainly hold uniformly over the intersection Θ eb ∩ Θ β . Similarly, the coverage relation in Theorem 4 will certainly hold uniformly over Θ β .
Below we verify the required conditions to obtain Corollaries 1 and 2 for concrete models and structures. For brevity sake, for some examples and some claims of Corollaries 1 and 2, we will not present all the computations for verifying the required conditions, since these computations can be done similarly to the previously considered cases.

Signal+noise model with smoothness structure
Assume that the data Y = (Y i ) i∈N come from the model where θ = (θ i ) i∈N ∈ Θ = ℓ 2 is an unknown parameter and ξ i ind ∼ N(0, 1). A local approach for this model, delivering also the adaptive minimax results for many smoothness structures simultaneously, is considered by [1,28] for posterior contraction rates and by [4] for uncertainty quantification problem.
Admittedly, this is an infinite dimensional model as compared with the default highdimensional general framework (1.1), but in this case all the results go through with one minor adjustment: all the sums over I ∈ I become countable infinite instead of finite. Alternatively, we could consider a finite dimensional model approximating the original infinite dimensional model with arbitrary accuracy.
In this case, the smoothness structure is modeled by the linear spaces Recall that, in view of Remarks 5 and 18, Conditions (A1) and (A4) hold with d s( As consequence of our general results, we obtain the local results of Corollary 1 for this case with the local rate r 2 (θ) defined above. In turn, by virtue of Corollary 2 the local results will imply global minimax adaptive results at once over all scales {Θ β , β ∈ B} covered by the oracle rate r 2 (θ) (i.e., for which (6.1) holds). Below we present a couple of examples of scales {Θ β , β ∈ B} covered by the oracle rate r 2 (θ).

Analytic and tail classes
Similarly, we can derive the adaptive minimax results for two more scales of exponential ellipsoids (or analytic classes) and tail classes. Exponential ellipsoids are defined as follows: For the analytic scale, the relation (6.1) is sup θ∈Θ β r 2 (θ) r 2 (Θ β ) ≍ log n n . The tail classes are In this case, the relation (6.1) is sup θ∈Θ β r 2 (θ) r 2 (Θ β ) ≍ n −β/(β+1) . Corollary 2 follows for the both scales with the corresponding minimax rates r 2 (Θ β ) defined above.

Signal+noise model under wavelet basis
We adopt the notation and conventions from [32]. Consider the observations This model is obtained as the result of the orthogonal wavelet transform of an additive regression function observed in Gaussian noise with σ 2 = n −1 , or just as a sequence version (with respect to some wavelet basis) of the continuous white noise model. We could also consider a high dimensional "projected" (see (9.57) in [32]) variant, where j ∈ [J o ] with 2 J 0 +1 = n. For details and many interesting connections and relations to the function estimation theory we refer to the very comprehensive and insightful account [32] on this topic.
The smoothness structure of θ = (θ jk , (jk) ∈ K) is modeled by the linear spaces Finally, for any I 0 , I 1 ∈ I define j ′′ 0 = min{j 0 0 , j 1 0 }, j ′ 0 = max{j 0 0 , j 1 0 } and I ′ (I 0 , I 1 ) ∈ I such that I ′ (I 0 , I 1 ) = (I 0 0 ∪ I 1 0 , I 0 1 ∪ I 1 1 , . . . , I 0 which entails Condition (A3). As consequence of our general results, we obtain Corollary 1 for this case with the local rate r 2 (θ) = min I∈I θ − P I θ 2 + 1 n ρ(s(I)) . Below we present the example of Besov scale, for which the global minimax adaptive results follow from the local results. We should mention that there are of course more scales covered by the oracle rate r 2 (θ), the reader is invited to make computations for other interesting scales. Besides, the results can be extended to non-normal, not independent ξ jk 's, but only satisfying Condition (A1).

Besov scale
Assume that the true signal θ belongs to a Besov ball Θ β p,q (Q) = θ : for some p, q, Q > 0 and β ≥ 1/p. The minimax rate over Θ β p,q (Q) is known to be r 2 (Θ β p,q (Q)) ≍ n − 2β 2β+1 . The adaptive minimax results for the scale of the class Θ β p,q (Q) were considered by [51,31,28] and many others for posterior contraction rates, and [16] for constructing optimal confidence balls.

Signal+noise model with (multi-level) sparsity structure
Assume that the data Y = (Y i ) i∈[n] come from the model where θ = (θ i ) i∈[n] ∈ Θ = R n is an unknown parameter and ξ i ind ∼ N(0, 1). The highdimensional vector θ is assumed to be sparse. A local approach for this model, delivering also the adaptive minimax results for various sparsity structures simultaneously, is considered in [8,28] for posterior contraction rates and by [8] for uncertainty quantification problem.
The classical sparsity structure is modeled by the linear spaces In this case, d I = dim(L I ) = |I|, θ − P I θ 2 = i∈I c θ 2 i , the structural slicing mapping is defined to be s(I) = |I| ∈ S Finally, for any I 0 , I 1 ∈ I define I ′ = I 0 ∪ I 1 . Then (L I 0 ∪ L I 1 ) ⊆ L I ′ = L I 0 + L I 1 and |I ′ | log en |I ′ | ≤ |I 0 | log en |I 0 | + |I 1 | log en |I 1 | , which entails Condition (A3).

Remark 21.
We can take a slightly better majorant, ρ ′ (s(I)) = max{|I|, log n |I| }. As a consequence of our general results, we obtain Corollary 1 with the local rate r 2 (θ) = min I∈I θ − P I θ 2 + σ 2 ρ(s(I)) . In view of Remark 21, the results hold also with the local rate r 2 (θ) = min I∈I θ − P I θ 2 + σ 2 ρ ′ (s(I)) . As ρ ′ (s) ≤ ρ(s) for all s ∈ S, the local rate with ρ ′ (s) is smaller than the rate with ρ(s) implying a stronger version of Corollary 1. However, the quantity ρ(s) is easier to compute and we will thus use the majorant ρ(s).
Below we present a couple of examples of scales {Θ β , β ∈ B}, for which the global minimax adaptive results follow from the local results. Recall that the results can be extended to non-normal and not necessarily independent ξ i 's, but only satisfying Condition (A1). For example, as demonstrated in [8], ξ i 's originating from a certain AR(1)-model also satisfy Condition (A1). 6.3.1. Minimax results for nearly black vectors ℓ 0 and weak ℓ q -balls Nearly black vectors ℓ 0 . By I * (θ) and s(θ), we denote respectively the active index set and the sparsity of θ ∈ R n . For p ∈ [n], introduce the sparsity class (also called nearly black vectors) The minimax estimation rate over the class of nearly black vectors ℓ 0 [p] with the sparsity parameter p is known to be r 2 (ℓ 0 [p]) ≍ σ 2 p log( n p ) (usually in the literature p = p n = o(n) as n → ∞, but we do not impose this restriction); see [24]. The adaptive minimax results for nearly black vectors were considered in [8,22,43,56] and many others for posterior contraction rates, and in [8,57] for constructing optimal confidence balls.
Weak ℓ q -balls. For q ∈ (0, 2), the weak ℓ q -ball of sparsity p n is defined by where are the ordered θ 2 1 , . . . , θ 2 n . This class can be thought of as Sobolev hyperrectangle for ordered (with unknown locations) coordinates: , with the convention that in the case θ 2 The minimax estimation rate over this class is r 2 (m q [p n ]) = n( pn n ) q [σ 2 log( nσ pn )] 1−q/2 when n 2/q ( pn n ) 2 ≥ σ 2 log n, and r 2 (m q [p n ]) = n 2/q ( pn n ) 2 + σ 2 when n 2/q ( pn n ) 2 < σ 2 log n, as n → ∞; see [25,14]. The adaptive minimax results for the scale of weak ℓ q -balls were considered in [8,22] for posterior contraction rates and in [8] for constructing optimal confidence balls. We take The case n 2/q ( pn n ) 2 < σ 2 log n is treated similarly by taking p * n = 0. Corollary 2 follows for this case with the minimax rate r 2 (m q [p n ]) defined above.

Multi-level sparsity (clustering) structure
Consider the same model ( 6.4), but now with the so called multi-level sparsity structure, an extension of the traditional sparsity structure. In the usual one-level sparsity structure we have just one known sparsity level, which is by default zero. The first attempt to study a version of such structure has been undertaken in [9], here we propose a systematic approach to this from the general perspective of the linear spaces for the first time. To the best of our knowledge, this structure has never been systematically studied in the literature.
Next, we extend the one-level sparsity structure to the multi-level sparsity structure (with unknown sparsity levels) by introducing the following linear spaces: for a partition I = (I i , i ∈ [m] 0 ) of the set [n] into m + 1 parts, where I = I m is the family of all partitions of [n] into m + 1 parts (some possibly empty), and m = 2, . . . , n − 1. This can also be seen as clustering structure, where the partition I determines clustering of the coordinates of θ into m + 1 groups. In this case, compute Unfortunately, we were unable to establish Condition (A3) for this structure, which is needed for the uncertainty quantification results under the EBR condition. What we can claim are the relations (i)-(iv) and (vi)-(vii) of Corollary 1 with the local rate For m = 1 we get the classical one-level local sparsity results which also imply the global minimax results over sparsity scales, as is considered in the previous paragraph. For m ≥ 2, the obtained local results (i)-(iv) and (vi)-(vii) of Corollary 1 are new to the best of our knowledge. The most problematic term is log n |I 0 |,...,|Im| , this term is of a smaller order than n if |I 0 | and any m − 1 values among |I 1 |, . . . , |I m | (e.g., |I 0 |, |I 1 |, . . . , |I m−1 |) are themselves of the smaller order than n.

Remark 22.
It is an open problem to establish Condition (A3). This is important in the uncertainty quantification problem, namely, the coverage relation (v) from Corollary 1 relies on this condition.
If we are to verify Condition (A3), for any I, I ′ ∈ I we would define Clearly, L I ′ ⊆ L I ′′ , L I ⊆ L I ′′ ⊆ L I + L I ′ and max{s(I), s(I ′ )} ≤ s(I ′′ ) ≤ s(I) + s(I ′ ), implying ρ(s(I ′′ )) ≤ ρ(s(I)) + ρ(s(I ′ )), and seems that Condition (A3) is fulfilled. However, the problem is that the resulting I ′′ may in general not lie in I but rather in I m 2 . An idea to fix this would be to let the number m of parts in partitions I ∈ I free (any integer from 0 to n). But then the problem will emerge in another place: there are too many choices as the family S of all compositions of n becomes |S| = 2 n−1 . Then we will have to put the term log |S| ≍ n in the complexity majorant ρ(s(I)) to meet Condition (A2), which makes the local rate r 2 (θ) nσ 2 trivially large and therefore uninteresting.

Remark 23.
We should mention that the global minimax multi level sparsity results are not going to be useful, at least if we try to extend one-level sparsity scales to multi-level sparsity scales in the usual way. Indeed, even if we assume sparsity in the sense that |I 0 | ≤ s for some small s = s n ≪ n, i.e., θ ∈ Θ s = ∪ I∈I:|I 0 |≤s L I , the minimax rate over Θ s will presumably be and this is not a useful result. This means that the multilevel counterpart Θ s for the traditional one-level sparsity class ℓ 0 [s] is too "massive" in the minimax sense.

Function on a large graph with smoothness structure
We adopt the notation and conventions from [33]. Let G be a connected, simple (i.e., no loops, multiple edges or weights), undirected graph with n vertices labelled as 1, . . . , n. A function f on the (vertices of the) graph is a mapping f : [n] → R. We will write f both for the function and for the associated vector of function values (f (1), f (2), ..., f (n)) in R n . We assume that Y 1 , . . . , Y n are the observations at the vertices of the graph, satisfying where f = (f (i)) i∈[n] ∈ R n is the vector of values of unknown function on the graph G and Condition (A3) is also fulfilled. Indeed, for any I 0 , I 1 ∈ I define I ′ (I 0 , I 1 ) = I 0 ∨ I 1 , then (L I 0 ∪ L I 1 ) ⊆ L I ′ and ρ(s(I ′ )) = I 0 ∨ I 1 ≤ I 0 + I 1 = ρ(s(I 0 )) + ρ(s(I 1 )).
As consequence of our general results, we obtain the local results of Corollary 1 for this case with the local rate r 2 (f ) defined above. In turn, by virtue of Corollary 2 the local results will imply global minimax adaptive results over all scales {Θ β , β ∈ B} at once, covered by the oracle rate r 2 (f ) (i.e., for which (6.1) holds). Below we present the Laplacian scale {H β , β > 0} and show that it is covered by the oracle rate r 2 (f ).

Minimax results for a Laplacian graph
One common approach to learn functions on graphs is Laplacian regularisation; see, for example, [11,33]. The graph Laplacian is defined as L = D − A, where A is the adjacency matrix of the graph and D is the diagonal matrix with the degrees of the vertices on the diagonal. When viewed as a linear operator, the Laplacian acts on a function f as where we write i ∼ j if vertices i and j are connected by an edge. Denote the Laplacian eigenvalues, ordered by magnitude, by λ 1 ≤ λ 2 ≤ . . . ≤ λ n . As in [33], we assume without loss of generality that there exist i 0 ∈ N, C 1 > 0 such that for all n large enough and r ≥ 1, (1 + n 2β/r λ β i )f 2 (i) ≤ Q}, with smoothness β > 0. The minimax estimation rate over the class H β is 2β+r ; see [34].
By taking I 0 = ⌊n r/(2β+r) ⌋, we establish (6.1) in this case: Hence, Corollary 2 follows for this case with the minimax rate r 2 (H β ) defined above. As compared to the Theorems 3.2 and 3.3 in [33], there is no restriction on the range of the smoothness β in Corollary 2, and we do not have any extra logarithmic factor in the rate.

Density estimation with smoothness structure
We observe X 1 , . .  1], in the L 2 -sense. Due to Parseval's identity, the problem of estimating the density function f in the L 2 -sense can be converted into the problem of estimating the parameter θ = (θ i ) i∈N in the ℓ 2 -sense: where θ = (θ i ) i∈N is an unknown high-dimensional parameter of interest with n n l=1 ϕ i (X l )| ≤ c ϕ , we have σ n |ξ i | ≤ |Y i | + |θ i | ≤ 2c ϕ and Var(σ n ξ i ) ≤ c 2 ϕ n . The parameter σ n will be chosen later, for now it is any sequence σ n ∈ [0, 1].
Notice that we reduced the original density estimation problem to a finite dimensional version of the model from Section 6.1, however the errors ξ i 's are now not iid normals, which complicates the study of the present model. Consider the same smoothness structure (6.2) as in Section 6.1, with the difference that we restrict the family of structures I ∈ I = [n] 0 . The oracle rate becomes Conditions (A2) and (A3) are met in the same way as for the signal+noise model from Section 6.1. However, in order to derive at least the local estimation and posterior contraction results, we also need Condition (A1). This condition is now not immediate since the errors ξ i 's are non-normal and dependent in the model (6.7) (actually, the ξ i 's are asymptotically normal, but we are not going to rely on this). We apply the following strategy: introduce certain event and establish that the probability of this event is exponentially small (in n); next, under this event establish Condition (A1); finally, combine these two facts to derive the local estimation and posterior contraction results.
The following proposition is a direct consequence of McDiarmid's inequality; see, for instance Theorem 6.2 in [15].
The relation P(max i∈[n] |ξ i | ≥ t) ≤ i∈[n] P(|ξ i | ≥ t) and Proposition 1 imply that, for Now, by using (6.8), we ensure Condition (A1) under the event We have thus verified the conditional version of Condition (A1) (under event E) and Conditions (A2) and (A3) for the model (6.7). This means that we can derive results on estimation, posterior contraction and uncertainty quantification for the density f in terms of the model (6.7). These are the counterparts of claims (i)-(v) of Corollary 1 summarized by Theorem 5 below. To the best of our knowledge, local results on uncertainty quantification for the density are new. In the below theorem, we keep the same notation for all the quantities involved as in the general framework, with the understanding that these are specialized for the model (6.7) with the smoothness structure and the oracle rate r 2 (θ). Let us outline the idea of the proof (which is omitted) of the first claim of the above theorem; the same reasoning applies to the remaining claims. The expectation of the empirical Bayes posterior probability E θ Π = E θπ θ − ϑ 2 ≥ M 0 r 2 (θ) + M σ 2 n |Y is bounded by the sum of two terms E θ Π ≤ P θ (E c ) + E θ Π1 E . The first term is evaluated by using (6.8) (obtaining the bound 2e −nσ 2 n +log n ); the second term is evaluated exactly in the same way as in the proof Theorem 1, because Condition (A1) is fulfilled under the event E according to (6.9). Counterparts of assertions (ii) and (iii) of Theorem 2 can also be formulated and proved in the same way. Notice that the results that rely on Condition (A4) are not claimed as we are unable to verify this condition at the moment.
As to the choice of σ 2 n in the oracle rate, clearly, we would want it to be as small as possible. On the other hand, we want the claims of the theorem to be non-void, which is ensured only if σ 2 n n ≥ C log n, or σ 2 n ≥ C log n n , for sufficiently large C > 0. In the sequel we take therefore σ 2 n = C log n n . An extra log factor thus appeared which will also enter the minimax rates in the global results. We conjecture that one can get rid of that factor by using more accurate concentration inequalities when establishing Condition (A1).
As usually, the local results of Theorem 5 will imply global minimax adaptive results simultaneously over all scales {Θ β , β ∈ B} covered by the oracle rate r 2 (θ) (i.e., for which (6.1) holds). Hence, the same adaptive minimax results for the same scales as in Section 6.1 follow, up to a log factor as we have σ 2 n ≍ log n n in the model (6.7) instead of n −1 in the model from Section 6.1. The reader is invited to formulate a number of local and adaptive minimax results for this case. We should mention that it seems possible to extend the results to other structures (e.g., sparsity) and scales (e.g., Besov scales).

Biclustering model
Suppose we observe a matrix Y = (Y ij ) ∈ R n 1 ×n 2 : where θ = (θ ij ) ∈ R n 1 ×n 2 is an unknown high-dimensional parameter of interest with biclustering structure, σ > 0 is the known noise intensity, ξ = (ξ ij ) ∈ R n 1 ×n 2 is a random matrix with E θ ξ ij = 0. These model and structure were studied at length in [10], here we demonstrate that the results obtained in [10] also follow from our general framework results.
The essence of biclustering structure is to reduce dimensionality of a large matrix of parameters by simultaneous grouping of the rows and columns. For example, if the rows of θ correspond to objects and the columns to features, a biclustering structure means that only a few features are relevant for identifying a few groups of similar objects. Biclustering structure means that the rows and columns of the matrix θ = (θ ij ) ∈ R n 1 ×n 2 are split into k 1 and k 2 clusters, respectively, and the values θ ij are the same for i, j from the same clusters. Let us give the mathematical formalization of this idea. For where I 1 i = z −1 1 (i) and I 2 j = z −1 2 (j). The biclustering structure is nothing else but just this partition I = I(z) = (I 1 , I 2 ), where I 1 = I 1 (z 1 ) = (I 1 i : i ∈ [k 1 ]) is the row partition and I 2 = I 2 (z 2 ) = (I 2 j : j ∈ [k 2 ]) is the column partition. So, the collection of all mappings A biclustering structure I ∈ I in terms of parameter θ is expressed by imposing θ ∈ L I ⊆ R n 1 n 2 , where the linear subspace L I is defined as Let us propose a reasonable majorant ρ(s) for the layer complexity d s + log |I s | = s 1 s 2 + log |I s |. Clearly, |I s | ≤ N (n 1 , s 1 )N (n 2 , s 2 ), where N (n, k) is the number of ways to put n different objects into k different boxes so that each box contains at least one object. Notice that S(n, k) = N (n, k)/k! = 1 k! k j=0 (−1) k−j k j j n is a Stirling number of the second kind. To have a simple closed form expression for a majorant of the complexity, instead of N (n 1 , s 1 )N (n 2 , s 2 ) we can use its upper bound s n 1 1 s n 2 2 (all the partitions of [n 1 ] × [n 2 ] into s 1 × s 2 blocks, some of which are possibly empty). However, the bound |I s | ≤ s n 1 1 s n 2 2 becomes too crude for some s ∈ S. In particular, this bound is too crude for the cases (i) (s 1 , s 2 ) ∈ S 1 = {(s 1 , s 2 ) ∈ [n 1 ] × [n 2 ] : s 1 < n 1 , s 2 = n 2 }, (ii) (s 1 , s 2 ) ∈ L I(z 1 ,z 2 ) = L I(idn 1 ,idn 2 ) for all z 1 ∈ [n 1 ] n 1 , z 2 ∈ [n 2 ] n 2 . Hence, |I s | ≤ [s 1 ] [n 2 ] ≤ s n 1 1 for (s 1 , s 2 ) ∈ S 1 , |I s | ≤ s n 2 2 for (s 1 , s 2 ) ∈ S 2 , and |I s | ≤ 1 for (s 1 , s 2 ) ∈ S 3 . Thus, we improve the bound d s + log |I s | ≤ s 1 s 2 + log(s n 1 1 s n 2 2 ) by proposing the following majorant ρ(s) for the complexity of the layer I s : d s + log |I s | ≤ ρ(s), where ρ(s) is defined as follows: s 1 s 2 + n 1 log s 1 + n 2 log s 2 , s 1 < n 1 , s 2 < n 2 , s 1 n 2 + n 1 log s 1 , s 1 < n 1 , s 2 = n 2 , n 1 s 2 + n 2 log s 2 , s 1 = n 1 , s 2 < n 2 , n 1 n 2 , s 1 = n 1 , s 2 = n 2 .
Note that in this case the error distribution depends on θ. We represent the projection P I = BB T , where B is the (n 1 n 2 × k 1 k 2 )-matrix whose columns (b I 1 I 2 , (I 1 , I 2 ) ∈ I) form an orthonormal basis of L I . Then P I ξ 2 = B T ξ 2 = η 2 , with η = (η I 1 I 2 , (I 1 , I 2 ) ∈ I), η I 1 I 2 = b T I 1 I 2 ξ. We choose the following orthogonal basis of L I : Hoeffding's inequality implies that for any t ≥ 0 P θ (|η I 1 I 2 | ≥ t) ≤ 2e −t 2 /2 , for all (I 1 , I 2 ) ∈ I.
Let us verify Condition (A2): for any ν ≥ 1, Thus, the properties (i)-(iv) of Corollary 1 follow for the biclustering model with the ξ i ' that are independent and either normal or binomial, in fact, for any ξ satisfying Condition (A1).
One can also check Condition (A3), so that the coverage property (v) of Corollary 1 holds under EBR as well. However, the peculiarity of the biclustering structure is that the size and coverage claims (vi)-(vii) for the confidence ball B(θ,R M ) are stronger and more useful in this case than the corresponding claims (iv)-(v) for the confidence ball B(θ,R M ).
Indeed, the coverage property (v) holds uniformly only under the EBR, whereas the coverage property (vii) is uniform over the entire space Θ = R n 1 ×n 2 . So, basically the deceptiveness issue is not present in the coverage property (vii) for the confidence ball B(θ,R M ), it appears only marginally in the size relation (vi) of Corollary 1. Indeed, the sizeR M of the ball is of the oracle rate order uniformly in θ ∈ Θ\Θ = R n 1 ×n 2 \Θ, wherẽ Θ is defined by (3.14). By the definition ofΘ, r 2 (θ) ≥ cσ 2 √ n 1 n 2 for θ ∈ Θ\Θ. For the biclustering model, we can take c = log 2 andΘ can be written asΘ = {θ ∈ R n 1 ×n 2 : min{s o1 (θ), s o2 (θ)} = 1} with (s o1 (θ), s o2 (θ)) = s(I o (θ)), where the oracle I o (θ) is defined by (3.1). Hence, for the biclustering model,Θ is indeed a "thin" subset of R n 1 ×n 2 consisting of highly structured parameters, whose oracle number of either row or block columns is 1. As we have already discussed at the end of Section 3.4, this means that, modulo highly structured parameters, there is no deceptiveness phenomenon in the biclustering model.
Notice that for some s ∈ S, the quantityr 2 (Θ s ) can be less than the minimax rate r 2 (Θ s ) = s 1 s 2 + n 1 log s 1 + n 2 log s 2 . Recall however that the minimax rate r 2 (Θ s ) is claimed in [26] only under the assumption log s 1 ≍ log s 2 , and, in this case, indeed r 2 (Θ s ) ≍r 2 (Θ s ). In general, the minimax rate over Θ s for arbitrary s ∈ S cannot be bigger thanr 2 (Θ s ), we conjecture that it isr 2 (Θ s ) for all s ∈ S.
Remark 25. In view of Remark 18, Condition (A4) is always fulfilled whenever ξ i ind ∼ N(0, 1). However, for the biclustering model (and the stochastic block model, described below), a more appropriate distribution for the observations is binomial, i.e., Y ij ind ∼ Bernoulli(θ ij ). This case is important in relation to network modeling. Unfortunately, we were unable to establish Condition (A4) for the binomial case (hence, unable to establish claims (vi)-(vii) of Corollary 1). Verification of Condition (A4) for the binomial observations essentially boils down to the problem of estimating the functional F (θ) = i,j θ 2 ij with the rate √ N = √ n 1 n 2 . It is not known to us whether it is possible to construct such an estimator (possibly exploiting the biclustering structure of θ), which is an interesting and challenging problem on its own.

Stochastic block model
Here we briefly discuss a particular case of biclustering model, the stochastic block model (SBM) which is used in the literature on networks to model undirected network graphs.
Oracle estimation and posterior contraction rate results for stochastic block model were recently derived in [28,36]. Precisely, to get the SBM from the biclustering model, we assume additionally s 1 = s 2 = s, n 1 = n 2 = n, z 1 = z 2 = z. For a mapping z ∈ [s] [n] , the pertinent row partition in the SBM is , which is the same as the column partition.
In the binomial case Y ij ind ∼ Bernoulli(θ ij ), the observations Y ij can be associated with network data. In this case Y ij stands for the presence or absence of an edge between vertices i and j in the network interpretation. To model undirected network graphs, some conditions (called network conditions) are then additionally assumed: the "no self-loop" condition Y ii = θ ii = 0 and symmetry condition Y ij = Y ji and θ ij = θ ji . Denote by Θ net the parameters θ ∈ R n 1 ×n 2 satisfying these additional network conditions.
All the quantities, conditions and claims specialize to the SBM by setting s 1 = s 2 = s, n 1 = n 2 = n, z 1 = z 2 = z in all the above formulas for the biclustering model. The linear subspaces L I defined by (6.10) will get adjusted since z 1 = z 2 , the family I s can be associated with the collection of all possible partitions of [n] into s blocks, parametrized by mappings z ∈ [s] [n] . |I s | ≤ s n , s ∈ S [n]. The structural slicing mapping s(I) is the number of blocks in the partition I. Notice that under additional network conditions cs 2 (I) ≤ dim(L I ) ≤ s 2 (I), so that we can use s 2 (I) (instead of the true d I = dim(L I )) in the complexity part of the local rate as it is still of the same order, although some constants can be improved because of this extra network structure. We have d s(I) = d I = dim(L I ) ≤ s 2 (I), log |I s | ≤ n log s, and we take ρ(s(I)) = s 2 (I) + n log s(I). Conditions (A1)-(A4) are fulfilled in the same way as for the biclustering model, leading to Corollary 1. As to the binomial case, see Remark 25. Consider a couple of examples of scales {Θ β , β ∈ B} covered by the local rate r 2 (θ).

Minimax results for the stochastic block model
In [26] (cf. [36]), classes Θ k were introduced. In our notation, Θ s = ∪ I∈Is Θ I , where s = k, Θ I = L I ∩ Θ net ∩ [0, 1] n 2 , I ∈ I s , s ∈ S. So, we have the scale {Θ s , s ∈ S} and the adaptive minimax results over this scale follow from the local results given by Corollary 1. Indeed, as is shown in [26], the minimax rate over Θ s in the SBM is r 2 (Θ s ) = infθ sup θ∈Θs E θ θ −θ 2 ≍ s 2 + n log s = ρ(s). On the other hand, for each θ ∈ Θ s there exists I ∈ I s such that θ ∈ L I . Hence, P I θ = θ and r 2 (θ) ≤ r 2 (I, θ) = ρ(s) ≍ r 2 (Θ s ). This implies Corollary 2 for this scale.

Remark 26.
As to the deceptiveness phenomenon in the SBM, for the confidence ball B(θ,R M ) we again have the coverage property uniformly over the whole scale {Θ s , s ∈ S}, whereas the size property with the optimal radial rate holds over all classes {Θ s , s = 2, . . . , n}, but one: Θ 1 . Indeed, the class Θ 1 consists of highly structured parameters θ ∈ R n 2 , whose coordinates are all equal. The case θ ∈ Θ 1 reduces to just one-dimensional signal+noise model with N = n 2 observations. Since the effective radial rate g M (θ, N ) for the confidence ball B(θ,R M ) is always at least of the order nσ 2 ≫ σ 2 = r 2 (Θ 1 ), we could not attain the optimal rate r 2 (Θ 1 ) in the size relation only for the highly structured parameters θ ∈ Θ 1 .

Graphon classes
It is also possible to derive the global minimax results for the function class of graphons as consequence of our local results. We use the same notation as in [26]. Consider a random graph with adjacency matrix {Y ij } ∈ {0, 1} n×n . Assume again the network conditions: For any i > j, Y ij is sampled as follows: The function f on [0, 1] 2 , which is assumed to be symmetric, is called graphon. Introduce the derivative operator ∇ jk f (x, y) = ∂ j+k ∂x j ∂y k f (x, y), with the convention ∇ 00 f (x, y) = f (x, y). For β > 0, the Hölder norm is defined by For β, Q > 0, the Hölder graphon class is Recall that θ ij = f (ξ i , ξ j ). Slightly abusing notation, we will write θ ∈ F β (Q) if f ∈ F β (Q).
The next proposition is Lemma 2.1 from [26], which we give here (in our notation) for completeness. The proof can be found in [26].

Linear regression with various structures
Let us consider a general setting for linear regression: (6.13) where X = diag(X 1 , . . . , X m ) ∈ R mn×mp is a block diagonal matrix, whose blocks X 1 , . . . , X m ∈ R n×p are design matrices, σ > 0 is the known noise intensity, β = (β 1 , . .  We should emphasize that in this section we denote by β the vector of unknown parameters in (6.13), notation commonly used in the literature. This is not to be confused with the structural parameter β for indexing the scales of classes {Θ β , β ∈ B} which we use in other sections, in this section we will instead use the notation {Θ γ , γ ∈ Γ} for scales.
Many particular linear models can be put in (6.13) by choosing appropriately m, p and X. The case m = 1, p = n, X = I is already considered in Section 6.1 for the smoothness structure and in Section 6.3 for the sparsity structure. In the following subsections we consider several other specific models and structures in detail.
Remark 27. The true model does not have to be exactly of the form (6.13), it can be Y = θ + σξ, where θ = Xβ. In that case, ( 6.13) is an approximating model of the true model and all the local results hold with θ substituted everywhere instead of Xβ. The global minimax results will have to be modified by including the approximation term sup θ∈Θγ E θ θ − P Io θ 2 in the minimax rate r 2 (Θ γ ). 6.7.1. Linear regression with sparsity structure, inference on β Consider the classical linear regression model, i.e., for m = 1 in (6.13). In the highdimensional setting, typically p ≫ n. So, to be able to make sensible inference, one needs to exploit a structure on β. The vector β = (β 1 , . . . , β p ) T ∈ R p with a structure I ⊆ [p] is assumed to be sparse in the sense that β i = 0 for i ∈ I c , that is, the predictors (X i : i ∈ I c ) of design matrix X = (X 1 , . . . , X p ) are irrelevant from the perspective of structure I. Denote r = r(X) = rank(X).
A local approach for this model, delivering also the adaptive minimax results for many sparsity structures simultaneously, is considered in [28,6] for the posterior contraction rates. In [6] also the uncertainty quantification is treated. Note that "signal+noise" model is a special case of linear regression with X = I and p = n, and it has been considered in several previous sections.
In this model, the sparsity structure is expressed by the linear spaces Notice that we could use a smaller majorant ρ ′ (s(I)) = d I + log p |I| for I ∈ I 1 (the best choice), but this majorant is not practical to use.

Remark 28.
In the majorant ρ(s(I)) defined above, we see the elbow effect mentioned in Remark 11, this elbow effect will enter the rate as well. Let us explain how this elbow effect has emerged in this model.
Here we considered an important case when a seemingly right (full) familyĪ of structures can be reduced to a subfamily I ⊂Ī that has a reduced complexity but still covers the original familyĪ in the sense of Remark 11, thus improving the resulting oracle rate. This is a typical situation exhibiting the "elbow effect" in the complexity term of the rate; below there are a couple of more such example (Sections 6.7.3, 6.7.4 and 6.10).

Remark 29.
We could further reduce the family of structures to I ′ = {I r } ∪ I ′ 1 , with I ′ 1 = {I ⊆ I 1 : the columns (X i , i ∈ I) are linearly independent} (with the same structural slicing mapping s(I) = |I|), so that I ′ ⊆ I. In this case, we have d I = dim(L I ) = |I|, |I| ≤ r ≤ min{n, p} for each I ∈ I ′ , the layer is I s(I) = {J ⊆ I 1 : dim(L J ) = dim(L I )} for I ∈ I ′ 1 and I s(Ir) = {I r }. Then we can take the majorantρ(s(I)) = (|I| + log |I s(I) |)1{I ∈ I 1 }+r1{I = I r }. When implementing the Bayesian or penalization procedure, the majorant ρ(s(I)) = 2|I| log(ep/|I|)1{I ∈ I 1 } + r1{I = I r } is more practical to use also for the family I ′ . But then I also covers I ′ , thus boiling down to the same resulting oracle rate. Therefore, as soon as we use the same majorant, it does not matter which family of structures, I or I ′ , we take. A slightly bigger constant in Condition (A2) will be for the family I as there are more terms in the sum. We will use the family I.
Model selection. Besides inference on θ = Xβ, several interesting corollaries were established in [6] and they follow from our results exactly in the same way, we provide them here for completeness.
The first corollary concerns a bound on the size of the selected model. Similar to [21] and [42], the following assertion shows that the models with substantially higher size than the true one are unlikely according to the posteriorπ(I|Y ) (which is in essence the penalization method in caseπ(I|Y ) =π(I|Y )). The above claim, being non-asymptotic and uniform in β ∈ R p , can be specialized to certain situations. In particular, it leads to an interesting conclusion under the asymptotic setting p = p n → ∞ and β 0 ≤ s n = o(p n ) as n → ∞. Then the probability bound goes to 0 as n → ∞, uniformly in β ∈ ℓ 0 [s n ] {β : β 0 ≤ s n }. Further, when s n = o(p n ), the constant C 0 can be chosen smaller, which makes the conclusion of the claim stronger.

Proof. Note that for any
Inference on β under the compatibility condition. The next several corollaries concern inference on β rather than on θ. Besides optimal prediction, it is of interest to infer on the parameter β itself. Because the dimension p may be (and generally is) larger than n, the correspondence between Xβ and β is not unique, and hence additional conditions are necessary even in the noiseless situation. As is commonly adopted in the literature (see, e.g., [28]), we will need to assume a condition lower bounding the norm of Xβ by a positive multiple of a norm on β for sparse vectors which is in turn a condition on the design matrix X.
There is yet another issue: recall that inference in the general framework is on θ and is based on the posteriorπ(ϑ|Y ) for θ = Xβ, not for β. In order to infer on β, we need to construct a prior Π on β that leads to an (empirical Bayes) posteriorΠ(b|Y ) such that ϑ = Xb ∼π(ϑ|Y ). This is not difficult: indeed, recall the construction (2.8) of the conditional prior π I (ϑ|Y ) on θ. Since in this case the unstructured θ = Xβ and the conditional prior π I (ϑ|Y ) was formally constructed as prior on θ I = P I θ = P I Xβ = X I β, we can derive the corresponding conditional prior Π I (b|Y ) for β = (X T I X I ) −1 θ I because θ I = X I β is invertible with respect to β for any I ∈ I. The corresponding conditional prior on β becomes which means that subvector β I with coordinates in I is normally distributed with the above parameters, and the remaining coordinates I c of β are set to zero. From this point on, we can apply the (empirical) Bayesian approach in the same way as for θ. We thus construct the (empirical Bayes) posteriors on β:Π I (b|Y ), Π(b|Y ),Π(b|Y ),Π(b|Y ); and the estimators β = I∈Iβ Iπ (I|Y ) andβ =βÎ , whereÎ is defined by (2.19) andβ I = (X T I X I ) −1 X I Y is just the ordinary least squares estimator of β based on the design matrix X I of full column rank as I ∈ I. Similarly, we can defineΠ(β|Y ) as being eitherΠ(β|Y ) orΠ(β|Y ), andβ as being eitherβ orβ. The details of Bayesian construction for β can be found in [6]. For us what only matters is the fact that if β ∼Π(b|Y ) then θ = Xβ ∼π(ϑ|Y ).
Introduce some additional notation. Recall that β 0 denotes the number of nonzero elements of β. Further let β 1 = p j=1 |β j | be the ℓ 1 -norm of β and X max = max k=1,...,p X k (notice that if the design matrix X is normalized so that X k 2 = n, k ∈ [p], then X max = √ n). For l ∈ N, let : β 0 ≤ l, supp(β) ∈ I , (6.17) Because β 1 ≤ β 0 β , it follows that φ 1 (l) ≥ φ 2 (l). Positivity of φ 1 at an argument l is called the compatibility condition, and is stronger if φ 1 (l) is larger. If any of φ 1 or φ 2 is zero at its argument, then the corresponding result below becomes trivial but remains valid.
The following claims say basically that, under the compatibility condition, the (empirical Bayes) posteriorΠ(b|Y ) on β contracts around the truth with the optimal rate.

Proof.
By the definition of compatibility coefficient, on models I with |I| ≤ C 0 β 0 , the quantity b − β 1 is bounded by since the cardinality of supp(b − β) is at most (C 0 + 1) β 0 . By Theorem 1, the E βexpectation of the posterior probability of X(b − β) = ϑ − θ > M 0 r 2 (θ) + M σ 2 is bounded by H 0 e −m 0 M , while by Proposition 3, the event {I : |I| ≥ C 0 β 0 } has probability bounded by . The first assertion follows, the proof of the second claim is similar.
Notice that the above result implies the Corollary 5.4 in [28] and obtains optimal estimation rates for both ℓ 1 and ℓ 2 loss functions. Moreover, the dependence on the quantities φ 1 (l) and φ 2 (l) are optimal; cf. [48]. Next, we also obtain the optimal estimation result for both ℓ 1 -and ℓ 2 -norms.

Linear regression with group sparsity
Assume that the unknown regression vectors β 1 , . . . , β m ∈ R p in ( 6.13) share the same support. Note that the model considered in Section 6.7.1 is a special case of linear regression with group sparsity with m = 1. Local results for linear regression with group sparsity were derived in [40], and posterior contraction rate results in [28]. The group sparsity structure is modeled by the linear spaces Clearly, |I| ≤ 2 p and d I = dim(L I ) ≤ m|I| for I ∈ I 1 and d Ip = r. In this case, θ = Xβ with β = (β 1 , . . . , β m ) ∈ R mp , the structural slicing mapping is s(I) = |I| ∈ S [p] 0 . Further, we have |I s(I) | = p |I| for I ∈ I 1 and |I s(Ip) | = 1, hence log |I s(I) | = log p |I| ≤ |I| log(ep/|I|) for I ∈ I 1 and log |I s(Ip) | = 0. Since d s(I) +log |I s(I) | ≤ m|I| + |I| log(ep/|I|) for I ∈ I 1 and d Ip + log |I s(Ip) | = r, we take the majorant ρ(s(I)) = m|I| + |I| log(ep/|I|) 1{I ∈ I 1 } + r1{I = I p }, I ∈ I.
Notice the elbow effect in the majorant that emerges here for the same reason as in Section 6.7. 1. Conditions (A2) and (A3) are fulfilled in the same way as for the model in Section 6.7.1. As consequence of our general results, we obtain Corollary 1 for this case with the local rate r 2 (β) = min I∈I r 2 (I, β) = min I∈I (I − P I )Xβ 2 + σ 2 ρ(s(I)) .

Remark 30.
We can redefine the structural slicing mapping as s(I) = dim(L I ), and the bound log |I s | = log p s ≤ s log(ep/s) would still be valid. Notice further that we can slightly improve the above oracle rate by using the exact quantity d s(I) = d I = dim(L I ) instead of its upper bound m|I| in the expression for the complexity ρ(s(I)), which would make the oracle rate r 2 (β) slightly smaller.
Thus, this structure redundancyĪ\I 1 does not affect the final local rate, only constant C ν becomes slightly larger (and the condition p log m has to hold).
As consequence of our general results, we obtain the local results of Corollary 1 for these model and structure with the local rate r 2 (β) = min I∈I (I − P I )Xβ 2 + σ 2 ρ(s(I)) .
Summarizing, r 2 (β) ≤ σ 2 min{ps + m log s, pm}. We thus established the relation (6.1) for this scale, and Corollary 2 follows with the minimax rate r 2 (Θ GS (s)) defined above. 6.7.4. Linear regression with mixture structure Consider the regression model ( 6.13) with p ∈ [n] such that X 1 = . . . = X m =X,X = (X ij ) ∈ {0, 1} n×p , and j∈[p]X ij = 1 for all i ∈ [n], i.e., each row of the matrixX has n − 1 zeros and only one entry equals to 1. Recently, some estimation results for this model were derived in [37]. To the best of our knowledge, there are no local results on posterior contraction rate and uncertainty quantification problems for mixture model.
Condition (A3) can also be verified, which would ensure the coverage property (v) of Corollary 1 under EBR as well. However, there is no point in verifying Condition (A3) because for this linear regression model with mixture structure we have the same peculiar situation as for the biclustering model from Section 6.6: the size and coverage claims (vi)-(vii) for the confidence ball B(θ,R M ) are stronger and more useful than the corresponding claims (iv)-(v) for the confidence ball B(θ,R M ). Let us demonstrate that the linear regression with mixture structure does not suffer from the deceptiveness phenomenon, modulo the so called highly structured parameters.
Indeed, as consequence of our general results, we obtain the local results (i)-(iv) and (vi)-(vii) of Corollary 1 for this case with the local rate r 2 (β) = min I∈I (I − P I )Xβ 2 + σ 2 ρ(s(I)) , with P I as projection onto L I defined above and the majorant ρ(s(I)) defined by (6.19). The coverage property (v) for the confidence ball B(θ,R M ) can be shown to hold also, but uniformly only under the EBR, whereas the coverage property (vii) for the confidence ball B(θ,R M ) is uniform over the entire space Θ = R n×m . The sizeR M is of the oracle rate order (as the radiusR M ) uniformly in θ ∈ Θ\Θ = R n×m \Θ whereΘ is defined by (3.14). Since in this model the total number of observations is N = nm, it is easy to see thatΘ ⊆ {θ ∈ R n×m : p(I o (θ)) = 1} (i.e.,X Io = 1 n , where 1 n is the n-dimensional column of 1's) where the oracle structure I o (θ) is defined by (3.1). Clearly, the m-dimensionalΘ is a "thin" subset of R n×m consisting of highly structured parameters θ whose oracle number of columns in the design matrixX Io is p(I o (θ)) = 1. As we have already discussed at the end of Section 3.4, this means that, modulo these highly structured parameters, there is no deceptiveness phenomenon in this model.

Remark 33.
Notice that our local results for the linear regression model with mixture structure actually improve upon the results of [37] as we have mr(I) ≤ mp(I) instead of mp(I) (as in [37]) in the expression of the the local rate r 2 (β). This means that this oracle rate r 2 (β) defined above is smaller than the one from [37]. Notice that the below global minimax results over the considered class cannot be improved as the worst case of the both local rates is the same.
Finally, by virtue of Corollary 2 the local results will imply global minimax adaptive results at once over all scales {Θ γ , γ ∈ Γ} covered by the oracle rate r 2 (β) (i.e., for which (6.1) holds). Below we present one such scale, covered by the oracle rate r 2 (β).
Minimax results for mixture model. Define the class Θ M (p) = ∪ I∈Ī:p(I)≤p L I .
Piecing these together, we obtain that r 2 (β) ≤ σ 2 min{mp + n log p, nm} for all β such that θ = Xβ ∈ Θ M (p). We thus established the relation (6.1) for this scale, and Corollary 2 follows with the minimax rate r 2 (Θ M (p)) defined above.

Aggregation
Aggregation in nonparametric regression has been considered by [44,17,50,55] and many others. We consider the regression model with a fixed design. The observation model is as follows: (6.20) where x i ∈ X are nonrandom, X is an arbitrary set, f : X → R is an unknown function, and ξ i ind ∼ N(0, 1). We use the notation f 2 = i∈[n] f 2 (x i ). Assume we are given a collection of functions {f 1 , ..., f p }, called dictionary. For β ∈ R p , let f β = p j=1 β j f j . By choosing a rich dictionary {f 1 , ..., f p } and an appropriate β ∈ B ⊆ R p , one can expect f β to be close to f under some assumptions. For a certain choice of B, the so called aggregation problem consists basically in determining the "best"β ∈ B on the basis of the data Y such that First recall the main estimation results from [50] (lower bounds are also established in that paper). The so called exponential screening estimator fβ ES is proposed in [50]. Under the assumptions max j∈[p] f j ≤ √ n, p ≥ 2, n ≥ 1, s ∈ [p], the following oracle estimation result is derived in [50]: for some constant C > 0, where ψ n,p (B) = min{ψ * n,p (B), r} is the optimal rate of aggregation for the corresponding classes B ∈ {B (M S) , B (C) , B (L) , B (Ls) , B (Cs) }, r = rank(X), ψ * n,p (B) is defined as follows: An advantageous feature of the above results is its universality: the aggregation is attained over the five classes simultaneously.  [50] in our notation reads as follows: for any p, n ≥ 1 A very useful fact concluded in [50] is that, under the condition max j∈[p] f j ≤ √ n, any estimator satisfying (6.22) (possibly with different constants in the right hand side) leads to the universal oracle inequality ( 6.21).
Let us demonstrate that we can derive the same type of estimation results as in [50], again as consequences of our general approach for particular choice of sparsity structures. In fact, we improve upon certain aspects and also provide the results on uncertainty quantification, again as consequence of our general framework results.
The aggregation problem considered here for the model ( 6.20) can be associated with the standard linear regression problem (6.13) (with m = 1) studied in Section 6.7.1. Indeed, let θ = (f (x i ), i ∈ [n]) and notice that the vector f β = (f β (x i ), i ∈ [n]) can be represented as Xβ, where β ∈ R p is the unknown high-dimensional parameter and the design (n × p)matrix X has the entries X ij = f j (x i ), (i, j) ∈ [n] × [p]. In doing so, we arrive to the general setting Y = θ + σξ, but now we take the same family of structures I and the corresponding family of linear spaces given by (6.14), as in Section 6.7.1. The conditions are already verified in Section 6.7.1. Then, according to Remark 27, the general results imply Corollary 1 with the oracle rate r 2 (θ) = min I∈I r 2 (I, θ) = min I∈I θ − P I θ 2 + σ 2 ρ(s(I)) , where the majorant ρ(s(I)) is defined by (6.15).
Recall the full family of structuresĪ = {J : J ⊆ [p]}. Since θ − P Ir θ 2 = min I∈I θ − P I θ 2 = min I∈Ī θ − P I θ 2 , it is easy to see that In particular, property (ii) of Corollary 1 entails that for some C 0 , C 1 > 0 where r 2 (θ) is defined by (6.23), which is in fact property (6.22) for our estimatorθ. As is mentioned above, [50] established that, under the additional assumption max j∈[p] f j ≤ √ n, this in turn leads to the universality property ( 6.21), now for the estimatorθ: for some We should mention that the constants in the universality property for our estimatorθ may be worse than those for the estimatorf β ES . On the other hand, notice that the claim (ii) of Corollary 1, being a uniform exponential inequality in probability, is itself finer and stronger versions of the corresponding oracle result in expectation (like (6.21)). Moreover, we additionally obtain claims (i) and (iv)-(vii) of Corollary 1 for the posterior concentration rate and uncertainty quantification. Global results over appropriate scales can also be derived as consequences of Corollary 2. Besides, we can drop the normality and independence assumptions and impose only Condition (A1) instead. One can readily formulate these results.

Isotonic, unimodal and convex regressions
Assume that the observations are Y = (Y i ) i∈[n] according to the model where ξ i ind ∼ N(0, 1) and θ = (θ 1 , . . . , θ n ) ∈ R n is the unknown high-dimensional parameter, possibly belonging to one of the three classes: The isotonic, unimodal and convex regression problems concern the classes S ↑ , U m and C, respectively. Recently, oracle estimation results for these problems were derived by [23,12,13]. To the best of our knowledge, there are no local results on posterior contraction rate and uncertainty quantification problems for these structures. First, to model parameters from S ↑ and U m , introduce the linear spaces The structural slicing mapping in this case is s ′ (I) = |I|, so that S ′ = {2, . . . n − 1}. Compute |I s ′ (I) | = n−2 |I| , hence log |I s ′ (I) | ≤ |I| log( en |I| ). Since d s ′ (I) + |I s ′ (I) | ≤ 2|I| + 1 + |I| log( en |I| ) ≤ 1 + 3|I| log( en |I| ), we take the majorant ρ ′ (s ′ (I)) = 1 + 3|I| log( en |I| ). We introduced two different families of structures with two corresponding (different) families of linear spaces, but the majorants in the both cases can be chosen the same (up to a multiplicative constant). Conditions (A1)-(A4) for the both cases are fulfilled in the same way as for the model considered in Section 6.3, we omit the argument and computations that are very much along the same lines as in Section 6. 3. As consequence of our general results, we obtain the local results of Corollary 1 for the both cases with the local rate r 2 (θ) = min I∈I θ − P I θ 2 + σ 2 ρ(s(I)) and r ′2 (θ) = min I∈I ′ θ − P I θ 2 + σ 2 ρ ′ (s ′ (I)) . In turn, by virtue of Corollary 2 the local results will imply global minimax adaptive results at once over all scales {Θ β , β ∈ B} covered by the oracle rate r 2 (θ) and r ′2 (θ) (i.e., for which (6.1) holds). Below we present a couple of examples of such scales {Θ β , β ∈ B}.

Minimax results for isotonic, unimodal and convex regressions
Following [12], for θ ∈ R n , denote the number of relations θ i = θ i+1 for i ∈ [n − 1] by k(θ) − 1 (number of jumps of θ), and for θ ∈ C, the number of inequalities 2θ i ≤ θ i+1 + θ i−1 that are strict for i = 2, . . . , n − 1 by q(θ) − 1. Let U = ∪ n m=1 U m , where U m is defined by ( 6.25). Define the classes of monotone and unimodal parameters with at most k jumps and the class of piecewise linear convex parameters with at most q linear pieces as follows: for k, q ≥ 1, where S ↑ and C are defined by (6.24) and (6.26). Define Θ ↑ k = ∪ I∈I:|I|+1≤k L I and notice that for each θ ∈ S ↑ k (or θ ∈ U k ) there exists I * ∈ I such that θ ∈ L I * and k(θ) = |I * | + 1, implying that S ↑ k ⊆ Θ ↑ k (and U k ⊆ Θ ↑ k ). Similarly, we define Θ q = ∪ I∈I ′ :|I|+1≤q L ′ I and derive that C q ⊆ Θ q .
This means that we also established the relation (6.1) and hence also Corollary 2 with the minimax rate (up to a logarithmic factor) for the class C(V ). Below we present some further remarks and extensions for isotonic, unimodal and convex regressions.

Log factor and universality of the results
It should be recognized that we attain the minimax rates for the classes S ↑ k , U k , C q , S ↑ (V ), U (V ) and C(V ) only up to a logarithmic factor. On the other hand, we obtain the optimal rates over the bigger scales {Θ ↑ k , k ∈ [n]} and {Θ k , k ∈ [n]}. Moreover, as consequence of our general results we have also solved the uncertainty quantification problem and the problem of structure recovery (in a weak sense). Our constants in the estimation results may be worse than those from the above mentioned references, but on the other hand we do not require that the vector ξ is normal and its coordinates are independent, only mild Condition (A1) is to be fulfilled.
Interestingly, this extra log factor in the local rate can also be seen as "price" for certain universality in the results. Indeed, recall that the results for the family of structures I with corresponding linear spaces L I , I ∈ I, cover the scale {Θ ↑ k , k ∈ [n]}. This in turn implies the minimax results for the scales {S ↑ k , k ∈ [n]} and {U k , k ∈ [n]} (adaptively with respect to k ∈ [n]) and over the global shape-restricted classes S ↑ (V ) and U (V ) of monotone and unimodal parameters, simultaneously for all the mentioned scales. Thus, at the log factor price, one approach handles several structures at once.
Actually our approach allows to extend the universality property even further. Indeed, let us unite the two structuresĪ = I ∪ I ′ and the corresponding families of the linear spaces {L I , I ∈Ī} and consider the resulting procedure. This procedure makes sense because the majorants for the both families are of the same order, so we only need to adjust a multiplicative constant in front of the majorant ρ(s(I)) = 1 + 2|I| log( en |I| ) that will now handle the both families of structures. In doing so, we get the local result with the oracle rate over the both families at the price of a bigger multiple of the majorant. This means that the resulting procedure will mimic the oracle structure over the union of the two families, i.e., the resulting oracle rate will cover both scales {Θ ↑ k , k ∈ [n]} and {Θ k , k ∈ [n]} simultaneously. This in turn implies the minimax results for the scales {S ↑ k , k ∈ [n]}, {U k , k ∈ [n]} and {C q , q ∈ [n]} (adaptively with respect to k, q ∈ [n]) and over the global shape-restricted classes S ↑ (V ), U (V ) and C(V ) of monotone, unimodal and convex parameters, simultaneously for all the mentioned scales.

No EBR-like condition for shape-restricted structures
The last important aspect to discuss for this model and the considered shape-restricted structures is one peculiar phenomenon recently discovered by some researchers in related settings: for certain shape-restricted classes, the uniform coverage and optimal size properties in the uncertainty quantification problem can be derived without imposing any EBRlike condition. For example, one can construct a confidence ball for monotone θ's with a high coverage and a radius of the optimal order n 1/3 (σ 2 V ) 2/3 , uniformly over monotone θ ∈ S ↑ (V ) and without any EBR-like condition.
Let us show that we can also achieve this (up to a logarithmic factor) by using our approach. We consider only the family of structures I (and the corresponding family of linear spaces) for modeling monotone and unimodal θ's, similar argument can be given for the family of structures I ′ . To ensure the EBR-condition, we simply restrict the family of structures I to the subfamily I 1 = {I ∈ I : |I| ≥ C(n/σ 2 ) 1/3 } for some sufficiently large C > 0. Then the results go through in the same way as before with the difference that the oracle rate is now r 2 (θ) = min I∈I 1 θ − P I θ 2 + σ 2 ρ(s(I)) , with respect to the family I 1 , rather than I. Since for any I ∈ I 1 , |I| ≥ C(n/σ 2 ) 1/3 , this and Proposition 6 imply that for any I ∈ I 1 and any θ ∈ S ↑ (V ) (or θ ∈ U (V )) there exists a θ * ∈ Θ ↑ I such that which ensures the EBR condition (3.10). Thus, the EBR condition is fulfilled automatically for the family of structures I 1 . At the same time, the oracle rate r 2 (θ) covers the both scales S ↑ (V ) and U (V ). Indeed, by taking I * ∈ I 1 such that |I * | = ⌊C(n/σ 2 ) 1/3 ⌋ + 1, we obtain that uniformly over θ ∈ S ↑ (V ) ∪ U (V ) which is the minimax rate (up to a logarithmic factor) over the both classes S ↑ (V ) and U (V ) simultaneously.

Dictionary learning
Dictionary learning can be considered as a linear regression problem when the design matrix and (sparse) vector of regressors are both unknown. The data Y = (Y i ) i∈ [mn] are observed according to the model: . . , D} ∈ R mn×mp is an m block diagonal matrix with p ∈ N, whose block D = (D 1 , . . . , D p ) ∈ R n×p is an unknown dictionary matrix, p ≤ n without loss of generality, σ > 0 is the known noise intensity, r = (r 1 , . . . , r m ) ∈ R mp is a concatenation of unknown representations r 1 , . . . , r m ∈ R p such that each entry r j i of each r j comes from a (known) finite set of numbers: r j i ∈ R K = {r 1 , . . . ,r K } (for instance, R 3 = {−1, 0, 1}), for somer k ∈ R, k ∈ [K]. Recently, posterior contraction rate and oracle estimation results for this model were derived by [28] and [37], respectively. To the best of our knowledge, there are no local results on uncertainty quantification problem for dictionary learning.
In this model, we have θ =Dr. The structure I consists of two parts: m sparsity patterns I m (I 1 , . . . , I m ) ⊆ [p] m (I j determines which columns are taken in the j-th diagonal block D ofD) and m sparse versions of representation vectors R I m (r 1 I 1 , . . . , r m Im ) according to the sparsity patterns I m , where r j We encode the structure I as I = (I m , R I m ), and the whole family of structures is The structural slicing mapping is defined as s(I) = (|I k |, k ∈ [m]) ∈ S [p] m 0 . Further, introduce the subfamily I 1 ofĪ: where the quantity l K (I) is defined as |I j |. (6.27) This quantity has the meaning of the log of the cardinality of the structural layer I s(I) and its motivation to appear here will become clear later.
The structures in this model are modeled by the linear spaces where I ∈ I I 1 ∪ {Ī} andĪ is one special structure (the finest possible) such that s(Ī) = (p, . . . , p) (m-dimensional vector of p's) and the associated linear space is LĪ = vec(x 1 , . . . , x m ) ∈ R nm : x j ∈ R n , j ∈ [m] . If some I j = ∅, then the corresponding column D I j r j I j is the zero column. In this case, θ =Dr ∈ R n×m (recall that whenever appropriate we treat θ as vector: θ ∈ R nm ), where l K (I) is introduced by (6.27). The last relation explains the origin of the quantity l K (I). Since d s(I) + log |I s(I) | ≤ np + l K (I) for I ∈ I 1 and d s(Ī) + log |I s(Ī) | = nm, we take the majorant ρ(s(I)) = np + l K (I) 1{I ∈ I 1 } + nm1{I =Ī}. (6.28) As for some previous models and structures, we have an elbow effect expressed basically by the quantity l K (I) in the majorant and there is no need to consider the structures I ∈Ī\I, because these structures are dominated by the structureĪ, the same reasoning applies as in Remark 31.  Remark 34. Notice the emerging condition m np. This is not completely surprising: m should not be too big in order not to have too many structures in the layers. Alternatively, instead of imposing this condition, we can make the majorant slightly bigger by setting np ∨ m instead of just np in ( 6.28). Yet another fix would be to remove those structures I from I 1 for which j∈[m] |I j | < m. One can show that in this case the above sum will be uniformly bounded.
As for the previous model (linear regression with mixture structure), there is no point in verifying Condition (A3) because the size and coverage claims (vi)-(vii) for the confidence ball B(θ,R M ) are stronger and more useful for this model and this structure than the corresponding claims (iv)-(v) for the confidence ball B(θ,R M ). Let us demonstrate that this model in essence does not suffer from the deceptiveness phenomenon, modulo the so called highly structured parameters.
Indeed, as consequence of our general results, we obtain the local results (i)-(iv) and (vi)-(vii) of Corollary 1 for this case with the local rate r 2 (θ) = min I∈I (I − P I )θ 2 + σ 2 ρ(s(I)) , where θ =Dr, with majorant ρ(s(I)) defined above and P I , the projection onto L I defined above. The coverage property (v) for the confidence ball B(θ,R M ) can be shown to hold also, but uniformly only under the EBR, whereas the coverage property (vii) for the confidence ball B(θ,R M ) is uniform over the entire space θ =Dr ∈ Θ = R n×m . The sizeR M is of the oracle rate order (as the radiusR M ) uniformly in θ ∈ Θ\Θ = R n×m \Θ, whereΘ is defined by (3.14). In this model the total number of observations is N = nm and Θ = {θ ∈ R n×m : σ −2 (I − P Io(θ) )θ 2 + np + l K (I o (θ)) √ N = √ nm}, where I o (θ) is the oracle structure defined by (3.1). Clearly,Θ is a "thin" subset of R n×m consisting of highly structured parameters θ, in this case ultra-sparse parameters as their oracle structure must be very sparse: l K (I o (θ)) ≤ C √ nm − np. Actually,Θ = ∅ if m p 2 n which is a very mild assumption on the dimensions n, p, m only. To summarize, under the assumption m p 2 n, in the dictionary learning model there is no deceptiveness issue at all.
We thus established the relation (6.1) for this scale, and Corollary 2 follows with the minimax rate r 2 (Θ SDL (s)) defined above.

Mean matrix with submatrix sparsity
Suppose we observe a matrix Y = (Y ij ) ∈ R n 1 ×n 2 : where σ > 0 is the known noise intensity, ξ ij ind ∼ N(0, 1), θ = (θ ij ) ∈ R n 1 ×n 2 is an unknown high-dimensional parameter of interest with at most k 1 nonzero rows and k 2 nonzero columns, which are not necessarily consecutive. To the best of our knowledge, there are no local results on estimation, posterior contraction rate and uncertainty quantification problems for this model.
The submatrix sparsity structure is modeled by the linear subspaces |I i | log( en i |I i | ).
Here, λ max (M) and λ min (M) are the maximum and minimum eigenvalues of M. We assume that X i ind ∼ N(0 n , Σ), where 0 n is the n-dimensional vector of zeros. The normality assumption is not important to us, this only plays a role in that we can use certain auxiliary result below (Proposition 7) which is available only for the normal case.
We are interested in recovering the covariance matrix Σ = {Σ ij } 1≤i,j≤p which is assumed to have the banding or sparsity structure, to be specified later. The maximum likelihood estimator of Σ isΣ = 1 n n l=1 (X l −X)(X l −X) T = 1 n n l=1 X l X T l −XX T , whereX = 1 n n l=1 X l . SinceXX T is a higher order term (see Remark 1 in [19]), we shall ignore this term and focus on the dominating term 1 n n l=1 X l X T l for estimating the covariance matrix Σ.
Let Y = (Y ij ) i,j∈[p] = 1 n n l=1 X l X T l , Y = vec (Y ij ) = (Y 11 , Y 12 . . . , Y pp ) T . We obtained the following model: (6.29) where σ n ξ ij = Y ij − EY ij = Y ij − Σ ij , so that Eξ ij = 0 and The parameter σ n will be chosen later, for now it is any sequence σ n ∈ [0, 1]. We thus have a particular case of general framework model (1.1), where the parameter of interest is now denoted by Σ instead of θ. Recall that we work with the usual norm of vectorized version of the parameter Σ = (Σ ij ) i,j∈ [p] , that is, if Σ is seen as matrix, then Σ means its Frobenius norm. We denote the probability measure of Y from the model (6.29) by P Σ , and the corresponding expectation E Σ .

Banding structure
Assume that the covariance matrix Σ = (Σ ij ) i,j∈[p] has a banding structure, i.e., Σ ij = 0 for all i, j ∈ [p] such that |i − j| > I for some I ∈ Condition (A2) is fulfilled, since I∈I e −νρ(s(I)) ≤ s∈S e −νs ≤ e ν e ν −1 = C ν for any ν > 0. However, in order to derive at least the local estimation and posterior contraction results, we also need Condition (A1). This condition is now not easy to check since the errors ξ ij 's are dependent in the model ( 6.29). We apply the following strategy (in the same spirit as in Section 6.5): introduce certain event and establish that the probability of this event is exponentially small (in n); next, under this event establish Condition (A1); finally, combine these two facts to derive the local estimation and posterior contraction results.
The following proposition (formulated in our notation) is Lemma 12 from Appendix of supplementary material [38] and is given here for completeness, its proof can be found in [38].
We have thus verified the conditional version of Condition (A1) (under the event E) and Conditions (A2) and (A3) for the model ( 6.29) with the banding structure. This means that we can derive results on estimation, posterior contraction and uncertainty quantification for this model. These are the counterparts of claims (i)-(v) of Corollary 1 summarized by Theorem 6 below. To the best of our knowledge, there are no local results on estimation, posterior contraction rate and uncertainty quantification problems for this model.
A couple of conventions concerning notation in Theorem 6: as compared to the general framework notation, in the model ( 6.29), the parameter of interest is denoted by Σ instead of θ and the corresponding estimator becomesΣ instead ofθ; in the posteriors for Σ we use the variable Σ to distinguish it from the "true" Σ ∈ C ε 0 . We keep the same notation for all other quantities involved as in the general framework (liker,R M , B(Σ,R M )), with the understanding that these are specialized for the model ( 6.29) with the banding structure and the oracle rate r 2 (Σ). Let us outline the idea of the proof (which is omitted) of the first claim of the above theorem; the same reasoning applies to the remaining claims. The expectation of the empirical Bayes posterior probability E Σ Π = E Σπ Σ −Σ 2 ≥ M 0 r 2 (Σ)+M σ 2 n |Y is bounded by the sum of two terms E Σ Π ≤ P Σ (E c ) + E Σ Π1 E . The first term is evaluated by using (6.8) (obtaining the bound H ′ e −c 1 nσ 2 n +c 2 log p ); the second term is evaluated exactly in the same way as in the proof Theorem 1 because Condition (A1) is fulfilled under the event E according to (6.31). Counterparts of assertions (ii) and (iii) of Theorem 2 can also be formulated and proved in the same way.
As to the choice of σ 2 n , this quantity is in the oracle rate, so that we would want it to be as small as possible. On the other hand, we want the claims of the theorem to be non-void, which is ensured only if σ 2 n n ≥ C log p, or σ 2 n ≥ C log p n , for sufficiently large C > 0. In the sequel we take therefore σ 2 n = C log p n . An extra log factor thus appeared which will also enter the minimax rates in the global results. We conjecture that one can get rid of that factor by using more accurate concentration inequalities when establishing Condition (A1).
As usually, the local results of Theorem 6 will imply global minimax adaptive results at once over all scales {Θ β , β ∈ B} covered by the oracle rate r 2 (Σ) (i.e., for which (6.1) holds). Below we present the example of scales {Θ β , β ∈ B} covered by the oracle rate r 2 (Σ). 6. 12.2. Minimax results for the scale {G β , β > 0} For β, L, ε 0 > 0, define The rate r 2 (G β ) = min pn − 2β+1 2(β+1) , p 2 n −1 is minimax over the class G β under the Frobenius norm; see [19]. If ( n log p ) 1 2(β+1) ≤ p, taking I * = ⌊(n/ log p) 1 2(β+1) ⌋ and recalling σ 2 n = C log p n , we derive that, uniformly in Σ ∈ G β , If ( n log p ) 1 2(β+1) > p, we take I * = p to derive sup Σ∈G β r 2 (Σ) p 2 ( n log p ) −1 . To summarize, we established that sup Σ∈G β r 2 (Σ) min p( n log p − 2β+1 2(β+1) , p 2 n log p −1 =r 2 (G β ), wherer 2 (G β ) is the minimax rate (up to a logarithmic factor) for the class G β . Then the last relation and Theorem 6 imply the global minimax results for the scale {G β , β > 0}. These results will look as the ones from Theorem 6 with the difference that the class G β stands instead C ε 0 and the rater 2 (G β ) stands instead of r 2 (Σ). For the results to be most useful, we take σ 2 n = C log p n with sufficiently large C > 0 and M = M n → ∞ as n → ∞ such that M n σ 2 n ≍r 2 (G β ). Remark 36. The obtained local and global results on uncertainty quantification for the covariance matrix with a banding structure are new to the best of our knowledge. Notice however that we derived only the uncertainty quantification results based on the EBR condition, whereas counterparts of claims (vi)-(vii) of Corollary 1 could not be established because we were unable to verify Condition (A4). The point is that the setΘ of highly structured parameters defined by (3.14) is empty in this case: as N = p 2 , r 2 (Σ) ≥ σ 2 n ρ(s(I)) σ 2 n p = σ 2 n N 1/2 .
This means that the uncertainty quantification claims based on Condition (A4) would be more valuable for this model because they are free of the deceptiveness phenomenon. Indeed, if we would have established Condition (A4), then the confidence ball B(Σ,R M ) would have been of asymptotically full coverage and of the optimal oracle size, uniformly over C ε 0 (becauseΘ turns out to be empty in this case).
It is an open problem to verify Condition (A4) for the model ( 6.29), the main issue is to find an appropriate statistics V (Y ′ ) for which the second relation of Condition (A4) is fulfilled.

Sparsity structure
Here we briefly discuss the case of sparsity structure for the model ( 6.29). Denote by Σ −i the i-th column of Σ with Σ ii removed. Let p ≥ 2. For any i ∈ [p] the vector Σ −i ∈ R p−1 is assumed to be sparse so that Σ ki = 0, k ∈ I i (or Σ ik = 0), where I i ⊆ [p]\{i}. To model this sparsity structure, introduce the linear spaces  for sufficiently large ν > 1.
Next, along the same lines as in Section 6.12.1, we can verify the conditional version of Condition (A1) (under event E) and Conditions (A2) and (A3) for the model ( 6.29) with the sparsity structure. This means that we can derive results on estimation, posterior contraction and uncertainty quantification for the model ( 6.29), now with the sparsity structure. We can readily formulate a theorem containing the local results for this structure: it will take the form of Theorem 6 with the oracle rate r 2 (Σ) = min I∈I Σ−P I Σ 2 +σ 2 n ρ(s(I)) , where σ 2 n = C log p n with sufficiently large C > 0. To the best of our knowledge, there are no local results on estimation, posterior contraction rate and uncertainty quantification problems for this model. Also for this sparsity structure we have the same issue (described in Remark 36) with Condition (A4) as for the banding structure.
Finally, consider one scale covered by the oracle rate for the sparsity structure.

Minimax results for weak ℓ q -balls
Recall the weak ℓ q ball of radius c in R m containing elements with fast decaying ordered magnitudes of components, where |ζ| (k) denotes the kth largest element in magnitude of the vector ζ. For 0 ≤ q < 1, define the class G q (c n,p ) of covariance matrices by G q (c n,p ) = {Σ ∈ C ε 0 : Σ −j ∈ B p−1 q (c n,p ), j ∈ [p]}, that is, each column Σ −j of Σ ∈ G q (c n,p ) must be in a weak ℓ q ball, j ∈ [p]. The minimax estimation rate over this class is r 2 (G q (c n,p )) = pc n,p log p n 1−q/2 + p n ; see [20]. Recall σ 2 n = C log p n and take I * = I * (Σ) = (I * 1 , . .  j −2/q + σ 2 n p c n,p n q/2 (log p) 1−q/2 + σ 2 n p pc n,p log p n 1−q/2 + p n log p. This relation and the local results imply the global minimax results (up to the logarithmic factor log p) on estimation, posterior contraction and uncertainty quantification for the model (79) for the scale G q (c n,p ).