Supplementary material: A non-asymptotic risk bound for model selection in a high-dimensional mixture of experts via joint rank and variable selection

TrungTin Nguyen; Dung Ngoc Nguyen; Hien Duy Nguyen; Faicel Chamroukhi

S-1 Proof sketch of Theorem 1

It is worth noting that to deal with random sub-collection, we need to use a general model selection theorem for MLE under a random sub-collection (cf. (4, Theorem 5.1) or (6, Theorem 7.3)). This is the extension of (3, Theorem 2), which dealt with conditional density estimation but not random sub-collection, and (12, Theorem 7.11), which only works for density estimation. We then explain how we use S-1 to obtain the oracle inequality, Theorem 1. To do this, our model collection must satisfy some regularity assumptions, which are proved in Section S-3. The main difficulties in proving our oracle inequality lie in bounding the bracketing entropy of the weights and means restricted to relevant variables, as well as in rank sparse models, and in particular with block-diagonal covariance matrices for the SGaBloME model. To overcome the first problem, we extend and adapt the strategies of [14] ; [5] . For the second, we extend the recent novel result on block-diagonal covariance matrices in [6] for Gaussian mixture models from [9] ; [13] .

S-1.0.1 General model selection theorem for MLE among a random sub-collection.

First, we impose a structural assumption on each model indexed by $𝐦 \in ℳ$ regarding the bracketing entropy, defined by (S-2), conditioned on the model $𝒮_{𝐦}$ w.r.t. a tensorized squared Hellinger (TSH) distance $d^{2 \otimes n}$ . In fact, this is an extension of the squared Hellinger distance $d^{2 \otimes n}$ , as follows

d^{2 \otimes n} (s, t) = 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} d^{2} (s (\cdot ∣ 𝐗_{n}), t (\cdot ∣ 𝐗_{n}))] .

(S-1)

Recall that the bracketing entropy of a set $S$ with respect to an arbitrary distance $d$ , denoted by $ℋ_{[\cdot], d} ((δ, S))$ , is defined as the logarithm of the minimal number $𝒩_{[\cdot], d} (δ, S)$ of brackets $[t^{-}, t^{+}]$ covering $S$ , such that $d (t^{-}, t^{+}) \leq δ$ . That is,

𝒩_{[\cdot], d} (δ, S) : = \min {n \in ℕ^{⋆} : \exists t^{-}_{1}, t^{+}_{1}, \dots, t^{-}_{n}, t^{+}_{n} s.t. d (t^{-}_{k}, t^{+}_{k}) \leq δ, S \subset ⋃_{k = 1}^{n} [t^{-}_{k}, t^{+}_{k}]},

(S-2)

where the term $s \in [t^{-}_{k}, t^{+}_{k}]$ is defined by $t^{-}_{k} (𝐱, 𝐲) \leq s (𝐱, 𝐲) \leq t^{+}_{k} (𝐱, 𝐲)$ , $\forall (𝐱, 𝐲) \in 𝒳 \times 𝒴$ . This leads to the following Assumption 1 (H).

Assumption 1 (H).

For every model $𝒮_{𝐦}$ in the collection $𝒮$ , there is a non-decreasing function $ϕ_{𝐦}$ such that $δ \mapsto \frac{1}{δ} ϕ_{𝐦} (δ)$ is non-increasing on $(0, \infty)$ and for every $σ \in ℝ^{+}$ ,

\int_{0}^{σ} \sqrt{ℋ_{[.], d^{\otimes n}} (δ, 𝒮_{𝐦} (\tilde{s}, σ))} d δ \leq ϕ_{𝐦} (σ),

where $𝒮_{𝐦} (\tilde{s}, σ) = {s_{𝐦} \in 𝒮_{𝐦} : d^{\otimes n} (\tilde{s}, s_{𝐦}) \leq σ}$ . The model complexity $𝒟_{𝐦}$ of $𝒮_{𝐦}$ is then defined as $N σ^{2}_{𝐦}$ , where $σ_{𝐦}$ is the unique root of $\frac{1}{σ} ϕ_{𝐦} (σ) = \sqrt{N} σ$ .

This bracketing entropy integral, often call Dudley integral, plays an important role in empirical processes theory (cf. [16] ; [8] ; [11] ). Observe that the model complexity does not depend on the bracketing entropies of the global models $𝒮_{𝐦}$ , but rather on those of smaller localized sets $𝒮_{𝐦} (\tilde{s}, σ)$ .

For technical reasons, a separability assumption, always satisfied in the setting of this paper, is also required. Assumption 2 (Sep) is a mild condition, which is classical in empirical process theory [16] ; [8] and allows us to work with a countable subset.

Assumption 2 (Sep).

For every model $𝒮_{𝐦}$ , there exists some countable subset $S^{'}_{𝐦}$ of $𝒮_{𝐦}$ and a set $𝒴^{'}_{𝐦}$ with $ι (𝒴 ∖ 𝒴^{'}_{𝐦}) = 0$ , where $ι$ denotes Lebesgue measure, such that for every $t \in 𝒮_{𝐦}$ , there exists some sequence $(t_{k})_{k \in ℕ^{⋆}}$ of elements of $S^{'}_{𝐦}$ , such that for every $𝐱 \in 𝒳$ and every $𝐲 \in 𝒴^{'}_{𝐦}, \ln (t_{k} (𝐲 | 𝐱)) \overset{k \to + \infty}{\to} \ln (t (𝐲 | 𝐱))$ .

To control the complexity of our collection, we also need an information-theoretic assumption. We assume the existence of a Kraft-type inequality for the collection [12] ; [1] .

Assumption 3 (K).

There is a family $(ξ_{𝐦})_{𝐦 \in ℳ}$ of non-negative numbers and a real number $Ξ$ such that $\sum_{𝐦 \in ℳ} e^{- ξ_{𝐦}} \leq Ξ < + \infty .$

We can now state the main result of (4, Theorem 5.1) for the model selection theorem for MLE under a random sub-collection.

Theorem S-1.

Let $(𝐗_{n}, 𝐘_{n})_{n \in [N]}$ be the observations coming from an unknown conditional density $s_{0}$ . Let the model collection $𝒮 = (𝒮_{𝐦})_{𝐦 \in ℳ}$ be an at most countable collection of conditional density sets. Assume that Assumption 1 (H), Assumption 2 (Sep), and Assumption 3 (K) hold for every $𝐦 \in ℳ$ . Let $ϵ_{K L} > 0$ , and $\bar{s}_{𝐦} \in 𝒮_{𝐦}$ , such that

K L^{\otimes N} (s_{0}, \bar{s}_{𝐦}) \leq i n f_{t \in 𝒮_{𝐦}} K L^{\otimes N} (s_{0}, t) + \frac{ϵ_{K L}}{N},

and let $τ > 0$ , such that

\bar{s}_{𝐦} \geq e^{- τ} s_{0} .

(S-3)

Next, we introduce $(𝒮_{𝐦})_{𝐦 \in \tilde{ℳ}}$ a random sub-collection of $(𝒮_{𝐦})_{𝐦 \in ℳ}$ and consider the collection $(\hat{s}_{𝐦})_{𝐦 \in \tilde{ℳ}}$ of $η$ -LLMs defined in (9). Then, for any $ρ \in (0, 1)$ , and any $C_{1} > 1$ , there are two constants $κ_{0}$ and $C_{2}$ depending only on $ρ$ and $C_{1}$ , such that, for every index $𝐦 \in ℳ$ ,

pen (𝐦) \geq κ [𝒟_{𝐦} + (1 \lor τ) ξ_{𝐦}], κ > κ_{0},

where the model complexity $𝒟_{𝐦}$ is defined in Assumption 1, the $η^{'}$ -PMLE $\hat{s}_{\hat{𝐦}}$ , defined in (10) on the subset $\tilde{ℳ}$ instead of $ℳ$ , satisfies

	$𝔼_{𝐗_{[N]}, 𝐘_{[N]}} [J K L_{ρ}^{\otimes N} (s_{0}, \hat{s}_{\hat{𝐦}})]$	$\leq C_{1} 𝔼_{𝐗_{[N]}, 𝐘_{[N]}} [i n f_{𝐦 \in \tilde{ℳ}} (i n f_{t \in 𝒮_{𝐦}} K L^{\otimes N} (s_{0}, t) + 2 \frac{pen (𝐦)}{N})]$
		$+ C_{2} (1 \lor τ) \frac{Ξ^{2}}{N} + \frac{η^{'} + η}{N} .$

S-1.0.2 Strategy for the proof of Theorem 1

We will briefly show how S-1 can be used to prove Theorem 1. All we need to do is check that Assumption 3 (K), Assumption 2 (Sep) and Assumption 1 (H) hold for every $𝐦 \in ℳ$ . According to the result of (4, Section 5.3), Assumption 2 (Sep) holds if we consider Gaussian densities, and the assumption defined by (S-3) is true if we further assume that the true conditional density $s_{0}$ is bounded and compactly supported. Furthermore, since we have restricted to a finite collection of models, it is true that there exists a family $(ξ_{𝐦})_{𝐦 \in ℳ}$ and $Ξ > 0$ such that Assumption 3 (K) is satisfied. Therefore, the remaining most difficult step of the proof for Assumption 1 (H) is presented in Section S-2. All technical results are moved to Section S-3.

S-2 Proof of Theorem 1

Note that the definition of model complexity in Assumption 1 (H) is related to a classical entropy dimension of a compact set w.r.t. a Hellinger type divergence $d^{\otimes n}$ , thanks to the following Proposition S-1, which is established in (3, Proposition 2).

Proposition S-1.

If we have

	$ℋ_{[.], d^{\otimes n}} (δ, 𝒮_{𝐦})$	$\leq dim (𝒮_{𝐦}) (C_{𝐦} + \ln (\frac{1}{δ})), for any δ \in (0, \sqrt{2}], then the function$
	$ϕ_{𝐦} (δ)$	$= δ \sqrt{dim (𝒮_{𝐦})} (\sqrt{C_{𝐦}} + \sqrt{π} + \sqrt{\ln (\frac{1}{\min (δ, 1)})})$

satisfies Assumption 1 (H). Furthermore, the unique solution $δ_{𝐦}$ of $\frac{1}{δ} ϕ_{𝐦} (δ) = \sqrt{N} δ$ satisfies

N δ_{𝐦}^{2} \leq dim (𝒮_{𝐦}) (2 (\sqrt{C_{𝐦}} + \sqrt{π})^{2} + (\ln \frac{N}{(\sqrt{C_{𝐦}} + \sqrt{π})^{2} dim (𝒮_{𝐦})})_{+}) .

Then, we claim that Proposition S-1 implies Assumption 1 (H) because of the fact that

ℋ_{[.], d^{\otimes n}} (δ, 𝒮_{𝐦}) \leq dim (𝒮_{𝐦}) (C_{𝐦} + \ln (\frac{1}{δ})),

(S-4)

where $C_{𝐦}$ is a constant depending on the model.

Next, recall that the definition from (4) is defined as follows:

	$𝒮_{𝐦}$	$= {s_{𝝍_{𝐦}} \equiv s_{𝝍_{K}} \in 𝒮 : 𝝍_{𝐦} = (𝝎_{0}, 𝝎, 𝝊_{0}, 𝚼, 𝚺 (𝐁)) \in 𝚿_{𝐦},$
		$𝚿_{𝐦} = ℝ^{K} \times 𝐖_{J}^{K \times D_{W}} \times ℝ^{K \times Q} \times 𝐕_{J, 𝐑}^{K \times D_{V}} \times 𝛀_{𝐁}^{K}} .$		(S-5)

Here, $𝐦 = (K, D_{W}, D_{V}, 𝐁, J, 𝐑)$ , $𝐖_{J}$ is the set of vectors restricted to the set of indices of relevant input variables $J_{i n}$ , $𝐕_{J, 𝐑}$ the set of matrices with relevant columns indexed by $J_{i n}$ and ranks $𝐑$ , and $𝛀_{𝐁}$ the set of positive definite block-diagonal matrices depending on partitions $𝐁$ .

If $P$ and $Q$ are not too large, we do not need to select relevant variables and/or use rank sparse models. We can then work on the structures for means and weights as in LinBoSGaME [14] . However, to deal with high-dimensional data and to simplify the interpretation of sparsity, we propose to use monomials for weights and polynomial regression models for the soft-max gating functions and the means of Gaussian experts. It is worth mentioning that here we provide a proof of a more general result compared to the model defined as in (4). More precisely, we replace the polynomial constructions for the weighting functions with monomials that allow interactions between covariates as follows:

𝐖_{K, D_{W}}

= {0} \otimes 𝐖^{K - 1}, 𝐖 = {𝒳 ∋ 𝐱 \mapsto \sum_{α \in 𝒜} 𝝎_{α} 𝐱^{𝜶} \in ℝ : \max_{𝜶 \in 𝒜} | ω_{𝜶} | \leq C_{𝝎}} .

(S-6)

Here, note that the multi-index $𝜶 = (α_{p})_{p \in [P]}, α_{p} \in ℕ^{⋆} ⋃ {0} \equiv ℕ, \forall p \in [P]$ , is an $P$ -tuple of nonnegative integers that satisfies $𝐱^{𝜶} = \prod_{p = 1}^{P} x^{α_{p}}_{p}$ and $| 𝜶 | = \sum_{p = 1}^{P} α_{p}$ . Then, for all $l \in [D_{W}]$ , we define $𝒜 = ⋃_{l = 0}^{D_{W}} 𝒜_{| l |}$ , $𝒜_{| l |} = {𝜶 = (α_{p})_{p \in [P]} \in ℕ^{P}, | 𝜶 | = l}$ . The number $𝜶$ is called the order or degree of monomials $𝐱^{𝜶}$ . By using the well-known stars and bars methods, e.g., (7, Chapter 2), the cardinality of the set $𝒜$ , denoted by $c a r d (𝒜)$ , equals $(\binom{D_{W} + P}{P})$ . Note that, for all $d \in [D_{𝚼}]$ , we define $𝐱^{d}$ as $(x^{d}_{p})_{p \in [P]}$ for the means, which are often used for polynomial regression models. Here, $𝒜_{J}$ is the set of multi-index (vector) in $ℝ^{P}$ restricted to the set of indices of relevant input variables $J_{i n}$ , that is, $𝒜_{J} = {𝜶 = (α_{t})_{t \in [p]} \in 𝒜 : α_{j} > 0, j \in J_{i n}}$ . Furthermore, given a regressor $𝐱$ , for all $l \in [D_{W}]$ , $p \in [P]$ , we define $𝝎^{(p, l)}_{k} = {ω_{k 𝜶} \in ℝ : 𝜶 = (α_{p})_{p \in [P]} \in 𝒜_{| l |}, α_{p} > 0}$ . We then generalize the definition of relevant variables for monomials as follows. Note that we call a couple $(X_{p}, Y_{q})$ irrelevant if the elements $(𝚼_{k d})_{q p} = 0$ and $𝝎^{(p, l)}_{k} = 𝟎$ for all $k \in [K]$ , $d \in [D_{V}]$ , $l \in [D_{W}]$ .

We also require some additional definitions of the following sets:

	$𝒫_{(K, D_{W}, J)}$	$= {𝒳 ∋ 𝐱 \mapsto (g_{k} (𝐰 (𝐱)))_{k \in [K]} : g_{k} (𝐰 (𝐱)) = \frac{\exp (w_{k} (𝐱))}{\sum_{l = 1}^{K} \exp (w_{l} (𝐱))},$
		$𝐰 = (w_{k})_{k \in [K]} \in 𝐖_{(K, D_{W}, J)}},$
	$𝐖_{(K, D_{W}, J)}$	$= {0} \otimes 𝐖_{J}^{K - 1}, 𝐕_{(K, D_{V}, J, 𝐑)} = R^{K \times Q} \times 𝐕_{J, 𝐑}^{K \times D_{V}},$
	$𝐖_{J}$	$= {𝒳 ∋ 𝐱 \mapsto w (𝐱) = \sum_{\| 𝜶 \| = 0}^{D_{W}} ω_{𝜶} 𝐱^{𝜶} : 𝜶 \in 𝒜_{J}, \max_{𝜶 \in 𝒜} \| ω_{𝜶} \| \leq C_{𝝎}},$
	$𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$	$= {𝒳 \times 𝒴 ∋ (𝐱, 𝐲) \mapsto (ϕ (𝐲; 𝐯_{k} (𝐱), 𝚺_{k} (B_{k})))_{k \in [K]} :$
		$𝒗 \in 𝐕_{(K, D_{V}, J, 𝐑)}, 𝚺 (𝐁) \in 𝛀_{𝐁}^{K}} .$

We define the following distance over conditional densities:

sup_{𝐱} d_{𝐲} (s, t) = sup_{𝐱 \in 𝒳} d_{𝐲} (s, t), where d_{𝐲} (s, t) = (\int_{𝒴} (\sqrt{s (𝐲 ∣ 𝐱)} - \sqrt{t (𝐲 ∣ 𝐱)})^{2} d 𝐲)^{1 / 2} .

This leads straightforwardly to $d^{2 \otimes n} (s, t) \leq sup_{𝐱} d_{𝐲} (s, t)$ . Then, we also define

sup_{𝐱} d_{k} (𝐠, 𝐠^{'}) = sup_{𝐱 \in 𝒳} (\sum_{k = 1}^{K} (\sqrt{g_{k} (𝐱)} - \sqrt{g^{'}_{k} (𝐱)})^{2})^{1 / 2},

for any gating functions $𝐠 = (g_{k})_{k \in [K]}$ and $𝐠^{'} = (g^{'}_{k})_{k \in [K]}$ . To this end, given any densities $s$ and $t$ over $𝒳$ , the following distance, depending on $𝐲$ , is constructed as follows:

	$sup_{𝐲} \max_{k} d_{𝐱} (s, t)$	$= sup_{𝐲 \in 𝒴} \max_{k \in [K]} d_{𝐱} (s_{k} (\cdot, 𝐲), t_{k} (\cdot, 𝐲))$
		$= sup_{𝐲 \in 𝒴} \max_{k \in [K]} (\int_{𝒳} (\sqrt{s_{k} (𝐱, 𝐲)} - \sqrt{t_{k} (𝐱, 𝐲)})^{2} d 𝐱)^{1 / 2} .$

Moreover, given any $𝐠^{+}, 𝐠^{-} \in 𝒫_{(K, D_{W}, J)}$ and $ϕ^{+}, ϕ^{-} \in 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ , let us define

	$d^{2}_{𝒫_{(K, D_{W}, J)}} (𝐠^{+}, 𝐠^{-})$	$= 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} d^{2}_{k} (𝐠^{+} (𝐗_{n}), 𝐠^{-} (𝐗_{n}))],$
	$d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ^{+}, ϕ^{-})$	$= 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} \sum_{k = 1}^{K} d^{2}_{𝐲} (ϕ^{+}_{k} (\cdot \| 𝐗_{n}), ϕ^{-}_{k} (\cdot \| 𝐗_{n}))] .$

Next (S-4) can be obtained by first decomposing the entropy term between the softmax gating functions and the Gaussian experts via Lemma S-1, which is immediately obtained from (14, Lemma 6), an extension of the results in (9, Theorem 2), [10] , (3, Lemma 7) and [2] .

Lemma S-1.

For all $δ \in (0, \sqrt{2}]$ , it holds that

ℋ_{[\cdot], d^{\otimes n}} (δ, 𝒮_{𝐦}) \leq ℋ_{[\cdot], d_{𝒫_{(K, D_{W}, J)}}} (\frac{δ}{2}, 𝒫_{(K, D_{W}, J)}) + ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) .

Then, we define the metric entropy of the set $𝐖_{(K, D_{W}, J)}$ : $ℋ_{d_{∥ sup ∥_{\infty}}} (δ, 𝐖_{(K, D_{W}, J)})$ , which measures the logarithm of the minimum number of spheres with radius at most $δ$ , corresponding to the distance $d_{∥ sup ∥_{\infty}}$ needed to cover $𝐖_{(K, D_{W}, J)}$ , where

d_{∥ sup ∥_{\infty}} ((𝐬_{k})_{k \in [K]}, (𝐭_{k})_{k \in [K]}) = \max_{k \in [K]} sup_{𝐱 \in 𝒳} ∥ 𝐬_{k} (𝐱) - 𝐭_{k} (𝐱) ∥_{2},

(S-7)

for arbitrary $K$ -tuples of the functions $(𝐬_{k})_{k \in [K]}$ and $(𝐭_{k})_{k \in [K]}$ . Here $𝐬_{k}, 𝐭_{k} : 𝒳 ∋ 𝐱 \mapsto 𝐬_{k} (𝐱), 𝐭_{k} (𝐱) \in ℝ^{P}, \forall k \in [K]$ , and given $𝐱 \in 𝒳, k \in [K]$ , $∥ 𝐬_{k} (𝐱) - 𝐭_{k} (𝐱) ∥_{2}$ is the Euclidean distance in $ℝ^{P}$ .

Based on this metric, one can first relate the bracketing entropy of $𝒫_{(K, D_{W}, J)}$ to $ℋ_{d_{∥ sup ∥_{\infty}}} (δ, 𝐖_{(K, D_{W}, J)})$ , and then obtain the upper bound for its entropy via Lemma S-2, which is proved in Section S-3.1.

Lemma S-2.

For all $δ \in (0, \sqrt{2}]$ ,

	$H_{[\cdot], d_{𝒫_{(K, D_{W}, J)}}} (\frac{δ}{2}, 𝒫_{(K, D_{W}, J)})$	$\leq H_{d_{∥ sup ∥_{\infty}}} (\frac{3 \sqrt{3} δ}{8 \sqrt{K - 1}}, 𝐖_{(K, D_{W}, J)})$
		$\leq dim (𝐖_{(K, D_{W}, J)}) (C_{𝐖_{(K, D_{W}, J)}} + \ln (\frac{8 \sqrt{K - 1}}{3 \sqrt{3} δ})),$		(S-8)

where $dim (𝐖_{(K, D_{W}, J)}) = (K - 1) c a r d (𝒜_{J})$ , $c a r d (𝒜_{J}) = (\binom{D_{W} + c a r d (J_{i n})}{c a r d (J_{i n})})$ and $C_{𝐖_{(K, D_{W}, J)}} = \ln (\sqrt{2} + \frac{C_{𝛚} D_{W}}{3 \sqrt{3}})$ .

Lemma S-3 allows us to construct the Gaussian brackets to handle with the entropy metric for Gaussian experts, which is established in Section S-3.2.

Lemma S-3.

For all $δ \in (0, \sqrt{2}]$ ,

ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) \leq dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\frac{1}{δ})) .

(S-9)

Finally, (S-4) is proved via Lemmas S-1, S-2 and S-3. Indeed, with the fact that

dim (𝒮_{𝐦}) = dim (𝐖_{(K, D_{W}, J)}) + dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}),

it follows that

		$ℋ_{[\cdot], d^{\otimes n}} (δ, 𝒮_{𝐦}) \leq H_{[\cdot], d_{𝒫_{(K, D_{W}, J)}}} (\frac{δ}{2}, 𝒫_{(K, D_{W}, J)}) + ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$
		$\leq dim (𝐖_{(K, D_{W}, J)}) (C_{𝐖_{(K, D_{W}, J)}} + \ln (\frac{8 \sqrt{K - 1}}{3 \sqrt{3} δ}))$
		$+ dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\frac{1}{δ}))$
		$= : dim (𝒮_{𝐦}) (C_{𝐦} + \ln (\frac{1}{δ})), where$
	$C_{𝐦}$	$= \frac{dim (𝐖_{(K, D_{W}, J)})}{dim (𝒮_{𝐦})} (C_{𝐖_{(K, D_{W}, J)}} + \ln (\frac{8 \sqrt{K - 1}}{3 \sqrt{3}})) + \frac{dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}}{dim (𝒮_{𝐦})}$
		$\leq C_{𝐖_{(K, D_{W}, J)}} + \ln (\frac{8 \sqrt{K_{\max} - 1}}{3 \sqrt{3}}) + C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} : = ℭ .$

It is interesting that the constant $ℭ$ does not depend on the dimension of the model $𝐦$ thanks to the hypothesis that $C_{𝐖_{(K, D_{W}, J)}}$ is common for every model $𝐦$ in the collection. Therefore, Proposition S-1 implies that, given $C = 2 (\sqrt{ℭ} + \sqrt{π})^{2}$ , the model complexity $𝒟_{𝐦}$ satisfies

	$𝒟_{𝐦} \equiv N δ^{2}_{𝐦}$	$\leq dim (𝒮_{𝐦}) (2 (\sqrt{ℭ} + \sqrt{π})^{2} + (\ln \frac{N}{(\sqrt{ℭ} + \sqrt{π})^{2} dim (𝒮_{𝐦})})_{+})$
		$\leq dim (𝒮_{𝐦}) (C + \ln N) .$

To this end, S-1 implies that to a collection of PSGaBloME models $𝒮 = (𝒮_{𝐦})_{𝐦 \in ℳ}$ with the penalty functions satisfies $pen (𝐦) \geq κ [dim (𝒮_{𝐦}) (C + \ln N) + (1 \lor τ) ξ_{𝐦}]$ with $κ > κ_{0}$ the oracle inequality of Theorem 1 holds.

S-3 Lemma proofs

S-3.1 Proof of Lemma S-2

It holds that

H_{[\cdot], d_{𝒫_{(K, D_{W}, J)}}} (\frac{δ}{2}, 𝒫_{(K, D_{W}, J)})

\leq H_{d_{∥ sup ∥_{\infty}}} (\frac{3 \sqrt{3} δ}{8 \sqrt{K - 1}}, 𝐖_{(K, D_{W}, J)}) .

Next, we need to find an upper bound of $H_{d_{∥ sup ∥_{\infty}}} (\frac{3 \sqrt{3} δ}{8 \sqrt{K - 1}}, 𝐖_{(K, D_{W}, J)})$ . Note that for all $𝐰, 𝐯 \in 𝐖_{(K, D_{W}, J)}$ , we obtain the following important inequality

	$d_{∥ sup ∥_{\infty}} (𝐰, 𝐯)$	$= \max_{k \in [K - 1]} sup_{𝐱 \in 𝒳} \| \sum_{\| 𝜶 \| = 0}^{D_{W}} ω^{𝐰}_{k, 𝜶} 𝐱^{𝜶} - \sum_{\| 𝜶 \| = 0}^{D_{W}} ω^{𝐯}_{k, 𝜶} 𝐱^{𝜶} \|$
		$\leq \max_{k \in [K - 1]} \sum_{\| 𝜶 \| = 0}^{D_{W}} \| ω^{𝐰}_{k, 𝜶} - ω^{𝐯}_{k, 𝜶} \| sup_{𝐱 \in 𝒳} 𝐱^{𝜶} \leq c a r d (𝒜_{J}) \max_{k \in [K - 1], 𝜶 \in 𝒜_{J}} \| ω^{𝐰}_{k, 𝜶} - ω^{𝐯}_{k, 𝜶} 𝐱^{𝜶} \| .$

Therefore, given the fact that $c a r d (𝒜_{J}) = (\binom{D_{W} + c a r d (J_{i n})}{c a r d (J_{i n})})$ , for all $δ \in (0, \sqrt{2}]$ , it holds that

	$H_{[\cdot], d_{𝒫_{(K, D_{W}, J)}}} (\frac{δ}{2}, 𝒫_{(K, D_{W}, J)})$
	$\leq H_{d_{∥ sup ∥_{\infty}}} (\frac{3 \sqrt{3} δ}{8 \sqrt{K - 1}}, 𝐖_{(K, D_{W}, J)})$
	$\leq H_{∥ \cdot ∥_{\infty}} (\frac{3 \sqrt{3} δ}{8 \sqrt{K - 1} c a r d (𝒜_{J})}, {𝝎 \in ℝ^{(K - 1) c a r d (𝒜_{J})} : ∥ 𝝎 ∥_{\infty} \leq C_{𝝎}})$
	$\leq (K - 1) c a r d (𝒜_{J}) \ln (1 + \frac{8 \sqrt{K - 1} C_{𝝎} c a r d (𝒜_{J})}{3 \sqrt{3} δ})$
	$= (K - 1) c a r d (𝒜_{J}) [\ln (\sqrt{2} + \frac{C_{𝝎} c a r d (𝒜_{J})}{3 \sqrt{3}}) + \ln (\frac{8 \sqrt{K - 1}}{3 \sqrt{3} δ})]$
	$= dim (𝐖_{(K, D_{W}, J)}) (C_{𝐖_{(K, D_{W}, J)}} + \ln (\frac{8 \sqrt{K - 1}}{3 \sqrt{3} δ})) .$

S-3.2 Proof of Lemma S-3

It is worth noting that without restriction on relevant variables, rank sparse models on the means and structures on covariance matrices of Gaussian experts from the collection $ℳ$ , the upper bound of the bracketing entropy of Gaussian experts from Lemma S-3 is directly implied from Proposition 2 and arguments from Appendix B.2.3 of [14] . However, in order to overcome the much more challenging problems with random subcollection based on relevant variables, rank sparse models on the means and block-diagonal covariance matrices, we have to reply on a much more constructive bracketing entropy in the spirits of works developed in [13] ; [14] ; [4] ; [5] ; [6] .

Given any $k \in [K]$ , we first define the following set and its corresponding distance as

$𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$	$= {𝒳 \times 𝒴 ∋ (𝐱, 𝐲) \mapsto ϕ (𝐲; 𝐯_{(D_{V}, J, 𝐑_{k})} (𝐱), 𝚺_{k} (B_{k})) :$
	$𝐯_{(D_{V}, J, 𝐑_{k})} \in 𝐕_{(D_{V}, J, 𝐑_{k})}, 𝚺_{k} (B_{k}) \in 𝛀_{B_{k}}},$
$d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ_{k}^{+}, ϕ_{k}^{-})$	$= 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} d^{2} (ϕ^{+}_{k} (\cdot \| 𝐗_{n}), ϕ^{-}_{k} (\cdot \| 𝐗_{n}))] .$	(S-10)

We need to specific block-diagonal structures for $𝚺_{k} (B_{k})$ . To be more precise, for $k \in [K]$ , we decompose $𝚺_{k} (B_{k})$ into $G_{k}$ blocks, $G_{k} \in ℕ^{⋆}$ , and we denote by $d^{[g]}_{k}$ the set of variables into the $g$ th group, for $g \in [G_{k}]$ , and by $c a r d (d^{[g]}_{k})$ the number of variables in the corresponding set. Then, we define $B_{k} = (d^{[g]}_{k})_{g \in [G_{k}]}$ to be a block structure for the cluster $k$ , and $𝐁 = (B_{k})_{k \in [K]}$ to be the output indexes into each group for each cluster. In this way, to construct the block-diagonal covariance matrices, up to a permutation, we make the following definition: $𝛀_{𝐁}^{K} = (𝛀_{B_{k}})_{k \in [K]}$ , for every $k \in [K]$ , for every $k \in [K]$ ,

𝛀_{𝐁}^{K} = {𝚺_{k} (B_{k}) \in 𝒮_{Q}^{+ +} | \begin{matrix} 𝚺_{k} (B_{k}) = 𝐏_{k} (\begin{matrix} 𝚺_{k}^{[1]} & 𝟎 & \dots & 𝟎 \\ 𝟎 & 𝚺_{k}^{[2]} & \dots & 𝟎 \\ 𝟎 & 𝟎 & ⋱ & 𝟎 \\ 𝟎 & 𝟎 & \dots & 𝚺_{k}^{[G_{k}]} \end{matrix}) 𝐏^{- 1}_{k}, \\ 𝚺_{k}^{[g]} \in 𝒮^{+ +}_{c a r d (d^{[g]}_{k})}, \forall g \in [G_{k}] \end{matrix}} .

(S-13)

Here, $𝐏_{k}$ corresponds to the permutation leading to a block-diagonal matrix in cluster $k$ . It is worth pointing out that outside the blocks, all coefficients of the matrix are zeros and we also authorize reordering of the blocks: e.g., ${(1, 3); (2, 4)}$ is identical to ${(2, 4); (1, 3)}$ , and the permutation inside blocks: e.g., the partition of $4$ variables into blocks ${(1, 3); (2, 4)}$ is the same as the partition ${(3, 1); (4, 2)}$ .

Then, it follows that $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)} = \prod_{k = 1}^{K} 𝒢_{(D_{V}, 𝐁_{k}, J, 𝐑_{k})}$ , where $\prod$ stands for the Cartesian product, and Lemma S-4, established in S-3.2.1.

Lemma S-4.

Given $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)} = \prod_{k = 1}^{K} 𝒢_{(D_{V}, 𝐁_{k}, J, 𝐑_{k})}$ , it holds that

ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) \leq \sum_{k = 1}^{K} ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2 \sqrt{K}}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) .

Next, we claim that Lemma S-3 is implied immediately via Lemma S-4 and the following important Lemma S-5, which is proved in S-3.2.2.

Lemma S-5.

For all $δ \in (0, \sqrt{2}]$ and $k \in [K]$ , there exists a constant $C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ such that

ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) \leq dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\frac{1}{δ})) .

(S-14)

To this end, by combining the previous two Lemmas S-4 and S-5, we have

	$ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$
	$\leq \sum_{k = 1}^{K} dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\sqrt{K}) + \ln (\frac{1}{δ}))$
	$= dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\frac{1}{δ})) .$

Here,

	$dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$	$= \sum_{k = 1}^{K} dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}),$
	$dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$	$= dim (𝐕_{(D_{V}, J, 𝐑_{k})}) + D_{B_{k}},$
	$C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$	$= \sum_{k = 1}^{K} C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\sqrt{K}),$
	$D_{B_{k}}$	$= dim (𝛀_{B_{k}}) = \sum_{g = 1}^{G_{k}} \frac{c a r d (b^{(g)}_{k}) (c a r d (b^{(g)}_{k}) + 1)}{2} .$

S-3.2.1 Proof of Lemma S-4

It is sufficient to verify that

𝒩_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) \leq \prod_{k = 1}^{K} 𝒩_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2 \sqrt{K}}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) .

By (S-2), for each $k \in [K]$ , let ${[ϕ^{l, -}_{k}, ϕ^{l, +}_{k}]}_{1 \leq l \leq 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}}$ be a minimal covering of $δ_{k}$ -bracket for $d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ with cardinality $𝒩_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (δ_{k}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) = : 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ . By definition, we have

\forall l \in [𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ^{l, -}_{k}, ϕ^{l, +}_{k}) \leq δ_{k} .

This leads to the set ${\prod_{k = 1}^{K} [ϕ^{l, -}_{k}, ϕ^{l, +}_{k}]}_{1 \leq l \leq 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}}$ is a covering of $δ / 2$ -bracket for $d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ with cardinality $\prod_{k = 1}^{K} 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ . Indeed, let any $ϕ = (ϕ_{k})_{k \in [K]} \in 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ . Consequently, for each $k \in [K], ϕ_{k} \in 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ , and there exists $l (k) \in [𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}]$ , such that

ϕ^{l (k), -}_{k} \leq ϕ_{k} \leq ϕ^{l (k), +}_{k}, d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ^{l (k), +}_{k}, ϕ^{l (k), -}_{k}) \leq (δ_{k})^{2} .

Then, it follows that $ϕ \in [ϕ^{-}, ϕ^{+}] \in {\prod_{k = 1}^{K} [ϕ^{l, -}_{k}, ϕ^{l, +}_{k}]}_{1 \leq l \leq 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}}$ , with $ϕ^{-} = (ϕ^{l (k), -}_{k})_{k \in [K]}$ , $ϕ^{+} = (ϕ^{l (k), +}_{k})_{k \in [K]}$ , which leads to ${\prod_{k = 1}^{K} [ϕ^{l, -}_{k}, ϕ^{l, +}_{k}]}_{1 \leq l \leq 𝒩_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}}$ is a bracket covering of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ .

Now, we want to verify that the size of this bracket is $δ / 2$ via choosing $δ_{k} = \frac{δ}{2 \sqrt{K}}, \forall k \in [K]$ . It holds that

	$d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ^{-}, ϕ^{+})$	$= 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} \sum_{k = 1}^{K} d^{2} (ϕ^{l (k), -}_{k} (\cdot \| 𝐗_{n}), ϕ^{l (k), +}_{k} (\cdot \| 𝐗_{n}))]$
		$= \sum_{k = 1}^{K} 𝔼_{𝐗_{[N]}} [\frac{1}{N} \sum_{n = 1}^{N} d^{2} (ϕ^{l (k), -}_{k} (\cdot \| 𝐗_{n}), ϕ^{l (k), +}_{k} (\cdot \| 𝐗_{n}))]$
		$= \sum_{k = 1}^{K} d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (ϕ^{l (k), -}_{k}, ϕ^{l (k), +}_{k}) \leq K (\frac{δ}{2 \sqrt{K}})^{2} = (\frac{δ}{2})^{2} .$

Finally, Lemma S-4 is followed by the definition of a minimal $δ / 2$ -bracket covering number for $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ .

S-3.2.2 Proof of Lemma S-5

We need to bound the bracketing entropy in (S-14). To do this, we need to construct an extension to the multidimensional Gaussian mixture of [9] , defining a net over the parameter space of Gaussian experts. Next, we aim to construct a bracket covering of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ according to the tensorized Hellinger distance, $d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ based on Gaussian dilatations.

Step 1: Construction of a net for the block-diagonal covariance matrices.

Firstly, for a given matrix $𝚺_{k} (B_{k}) \in 𝛀_{B_{k}}, k \in [K]$ , we denote by $A d j (𝚺_{k} (B_{k}))$ the adjacency matrix associated to the covariance matrix $𝚺_{k} (B_{k})$ . Note that this matrix of size $Q^{2}$ can be defined by a vector of concatenated upper triangular vectors. We are going to make use of the result from [6] to handle the block-diagonal covariance matrices $𝚺_{k} (B_{k})$ , via its corresponding adjacency matrix. To do this, we need to construct a discrete space for ${0, 1}^{Q (Q - 1) / 2}$ , which is a one-to-one correspondence (bijection) with

𝒜_{B_{k}} = {𝐀_{B_{k}} \in 𝒮_{Q} ({0, 1}) : \exists 𝚺_{k} (B_{k}) \in 𝛀_{B_{k}} s.t A d j (𝚺_{k} (B_{k})) = 𝐀_{B_{k}}},

where $𝒮_{Q} ({0, 1})$ is the set of symmetric matrices of size $Q$ taking values on ${0, 1}$ .

Then, we want to deduce a discretization of the set of covariance matrices. Let $h$ denotes Hamming distance on ${0, 1}^{Q (Q - 1) / 2}$ defined by

d (z, z^{'}) = \sum_{n = 1}^{N} 𝕀 {z \neq z^{'}}, for all z, z^{'} \in {0, 1}^{Q (Q - 1) / 2} .

Let ${0, 1}_{B_{k}}^{Q (Q - 1) / 2}$ be the subset of ${0, 1}^{Q (Q - 1) / 2}$ of vectors for which the corresponding graph has structure $B_{k} = (b^{(g)}_{k})_{g \in [G_{k}]}$ . Then, given any $ϵ > 0$ , Corollary 1 and Proposition 2 from Supplementary Material A of [6] lead to that there exists some subset $ℛ$ of ${0, 1}^{Q (Q - 1) / 2}$ , as well as its equivalent $𝒜^{d i s c}_{B_{k}}$ for adjacency matrices satisfy

$∥ 𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k}) ∥_{2}^{2}$	$\leq \frac{D_{B_{k}}}{2} \land ϵ^{2}, \forall (𝚺_{k} (B_{k}), \tilde{𝚺}_{k} (B_{k})) \in (\tilde{S}^{d i s c}_{B_{k}} (ϵ))^{2} s.t. 𝚺_{k} (B_{k}) \neq \tilde{𝚺}_{k} (B_{k}),$
$c a r d (\tilde{S}^{d i s c}_{B_{k}} (ϵ))$	$\leq (⌊ \frac{2 C_{𝚺}}{ϵ} ⌋ \frac{Q (Q - 1)}{2 D_{B_{k}}})^{D_{B_{k}}},$	(S-15)
$D_{B_{k}}$	$= dim (𝛀_{B_{k}}) = \sum_{g = 1}^{G_{k}} \frac{c a r d (b_{k}^{(g)}) (c a r d (b_{k}^{(g)}) - 1)}{2},$	(S-16)

where

	$\tilde{S}^{d i s c}_{B_{k}} (ϵ)$	$= {𝚺_{k} (B_{k}) \in 𝒮_{Q}^{+ +} (ℝ) : A d j (𝚺_{k} (B_{k})) \in 𝒜^{d i s c}_{B_{k}},$
		$(𝚺_{k} (B_{k}))_{i, j} = σ_{i, j} ϵ, σ_{i, j} \in [\frac{- C_{𝚺}}{ϵ}, \frac{C_{𝚺}}{ϵ}] ⋂ ℤ} .$

Therefore, by choosing $ϵ^{2} \leq \frac{D_{B_{k}}}{2}$ , given $𝚺_{k} (B_{k}) \in 𝛀_{B_{k}}$ , there exists $\tilde{𝚺}_{k} (B_{k}) \in \tilde{S}^{d i s c}_{B_{k}} (ϵ)$ , such that

∥ 𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k}) ∥_{2}^{2} \leq ϵ^{2} .

(S-17)

Based on $\tilde{𝚺}_{k} (B_{k})$ , we can construct the following bracket covering of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ via defining suitable nets for the means of Gaussian experts. More precisely, given any $δ_{𝐕_{(D_{V}, J, 𝐑_{k})}} > 0$ , we claim that the set

{[l, u] | \begin{matrix} l (𝐱, 𝐲) = (1 + 2 α)^{- D_{V}} ϕ (𝐲; \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱), (1 + α)^{- 1} \tilde{𝚺}_{k} (B_{k})), \\ u (𝐱, 𝐲) = (1 + 2 α)^{D_{V}} ϕ (𝐲; \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱), (1 + α) \tilde{𝚺}_{k} (B_{k})), \\ \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} \in G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}), \tilde{𝚺}_{k} (B_{k}) \in \tilde{S}^{d i s c}_{B_{k}} (ϵ) \end{matrix}},

is an $δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}$ -brackets set over $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ where the constant $α > 0$ and function $𝒳 ∋ 𝐱 \mapsto \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱)$ and its corresponding space $G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}})$ will be specified later. Indeed, we consider any function $𝒳 \times 𝒴 ∋ (𝐱, 𝐲) \mapsto f (𝐱, 𝐲) = ϕ (𝐲; 𝐯_{(D_{V}, J, 𝐑_{k})} (𝐱), 𝚺_{k} (B_{k}))$ that belongs to $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ , where $𝐯_{(D_{V}, J, 𝐑_{k})} \in 𝐕_{(D_{V}, J, 𝐑_{k})}$ and $𝚺_{k} (B_{k}) \in 𝛀_{B_{k}}$ . According to (S-17), there exists $\tilde{𝚺}_{k} (B_{k}) \in \tilde{S}^{d i s c}_{B_{k}} (ϵ)$ such that

∥ 𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k}) ∥_{2}^{2} \leq ϵ^{2} .

Step 2: Construction of a net for the mean functions.

We claim that given any $δ_{𝐕_{(D_{V}, J, 𝐑_{k})}} > 0$ , any $𝐯_{(D_{V}, J, 𝐑_{k})} \in 𝐕_{(D_{V}, J, 𝐑_{k})}$ , there exist a minimal covering of $δ_{k}$ -bracket $G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}})$ and a function $\tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} \in G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}})$ such that

	$sup_{𝐱 \in 𝒳} ∥ \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱) - 𝐯_{(D_{V}, J, 𝐑_{k})} (𝐱) ∥_{2}^{2}$	$\leq δ^{2}_{𝐕_{(D_{V}, J, 𝐑_{k})}},$		(S-18)
	$c a r d (G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}))$	$\leq (\frac{\exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}})^{dim (𝐕_{(D_{V}, J, 𝐑_{k})})} .$		(S-19)

To accomplish this, we use the singular value decomposition of $𝚼_{k d}^{R_{k d}} = \sum_{r = 1}^{R_{k d}} (σ_{k d})_{r} (𝐮_{k d})_{∙, r} (𝐯_{k d}^{⊤})_{r, ∙}$ , $k \in [K], d \in [D_{V}]$ , with $(σ_{k d})_{r}, r \in [R_{k d}]$ , denote the singular values of $𝚼_{k d}^{R_{k d}}$ , with corresponding orthogonal unit vectors $((𝐮_{k d})_{∙, r})_{r \in [R_{k d}]}$ and $((𝐯_{k d}^{⊤})_{r, ∙})_{r \in [R_{k d}]}$ . Then, we construct $\tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱) = \tilde{𝚼}_{k 0} + \sum_{d = 1}^{D_{V}} \tilde{𝚼}_{k d}^{R_{k d}} 𝐱^{d}$ , where $\tilde{𝝊}_{k 0}$ and $\tilde{𝚼}_{k d}^{R_{k d}} = \sum_{r = 1}^{R_{k d}} (\tilde{σ}_{k d})_{r} (\tilde{𝐮}_{k d})_{∙, r} (\tilde{𝐯}_{k d}^{⊤})_{r, ∙}$ , $k \in [K], d \in [D_{V}]$ , are determined so that (S-18) and (S-19) are satisfied. Note that for each $k \in [K], d \in [D_{V}]$ , it holds that

	$∥ \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱) - 𝐯_{(D_{V}, J, 𝐑_{k})} (𝐱) ∥_{2}$	$= ∥ \tilde{𝝊}_{k 0} - 𝝊_{k 0} + \sum_{d = 1}^{D_{V}} (\tilde{𝚼}_{k d}^{R_{k d}} - 𝚼_{k d}^{R_{k d}}) 𝐱^{d} ∥_{2}$
		$\leq ∥ \tilde{𝝊}_{k 0} - 𝝊_{k 0} ∥_{2} + \sum_{d = 1}^{D_{V}} ∥ (\tilde{𝚼}_{k d}^{R_{k d}} - 𝚼_{k d}^{R_{k d}}) 𝐱^{d} ∥_{2}$
		$\leq \sqrt{Q} ∥ \tilde{𝝊}_{k 0} - 𝝊_{k 0} ∥_{\infty} + P \sqrt{Q} \sum_{d = 1}^{D_{V}} \| \| \| \tilde{𝚼}_{k d}^{R_{k d}} - 𝚼_{k d}^{R_{k d}} \| \| \|_{\infty} ∥ 𝐱^{d} ∥_{\infty}$
		$\leq \sqrt{Q} ∥ \tilde{𝝊}_{k 0} - 𝝊_{k 0} ∥_{\infty} + P \sqrt{Q} \sum_{d = 1}^{D_{V}} \| \| \| \tilde{𝚼}_{k d}^{R_{k d}} - 𝚼_{k d}^{R_{k d}} \| \| \|_{\infty},$

where we used the fact that for all $d \in [D_{V}]$ , $𝐱 \in 𝒳$ , $∥ 𝐱^{d} ∥_{\infty} \leq 1$ as $𝒳 = [0, 1]^{P}$ . Thus, (S-18) is immediately followed if we now choose $\tilde{𝝊}_{k 0}$ and $\tilde{𝚼}_{k d}^{R_{k d}}$ such that

	$\sqrt{Q} ∥ 𝝊_{k 0} - \tilde{𝝊}_{k 0} ∥_{\infty}$	$\leq \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{2},$		(S-20)
	$\| \| \| 𝚼_{k d}^{R_{k d}} - \tilde{𝚼}_{k d}^{R_{k d}} \| \| \|_{\infty}$	$\leq \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{2 D_{V} P \sqrt{Q}} .$		(S-21)

Let us now see how to construct $\tilde{𝝊}_{k 0}$ to get (S-20). This task can be accomplished if for all $k \in [K]$ , $q \in [Q]$ , we set

	$B$	$= ℤ \cap [⌊ - A_{𝐮, 𝐯} \frac{2 \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}} ⌋, ⌊ A_{𝐮, 𝐯} \frac{2 \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}} ⌋],$
	$(\tilde{𝝊}_{k 0})_{q}$	$= \arg \min_{b \in B} \| (𝝊_{k 0})_{q} - \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{2 \sqrt{Q}} b \| .$

Next, let us now see how to construct $\tilde{𝚼}_{k d}^{R_{k d}}$ to get (S-21). The boundedness assumption in (7) implies that

	$\| \| \| 𝚼_{k d}^{R_{k d}} - \tilde{𝚼}_{k d}^{R_{k d}} \| \| \|_{\infty}$	$= \max_{q \in [Q], p \in [P]} \| \sum_{r = 1}^{R_{k d}} [(σ_{k d})_{r} (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p} - (\tilde{σ}_{k d})_{r} (\tilde{𝐮}_{k d})_{q, r} (\tilde{𝐯}_{k d}^{⊤})_{r, p}] \|$
		$= \max_{q \in [Q], p \in [P]} \| \sum_{r = 1}^{R_{k d}} [((σ_{k d})_{r} - (\tilde{σ}_{k d})_{r}) (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p}$
		$- (\tilde{σ}_{k d})_{r} ((\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r}) (\tilde{𝐯}_{k d}^{⊤})_{r, p}$
		$- (\tilde{σ}_{k d})_{r} (𝐮_{k d})_{q, r} ((𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p})] \|$
		$\leq \max_{r \in [R_{k d}]} \| (σ_{k d})_{r} - (\tilde{σ}_{k d})_{r} \| \max_{q \in [Q], p \in [P]} \sum_{r = 1}^{R_{k d}} \| (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p} \|$
		$+ \max_{q \in [Q], r \in [R_{k d}]} \| (\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r} \| \max_{p \in [P]} \sum_{r = 1}^{R_{k d}} \| (\tilde{σ}_{k d})_{r} (\tilde{𝐯}_{k d}^{⊤})_{r, p} \|$
		$+ \max_{r \in [R_{k d}], p \in [P]} \| (𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p} \| \max_{q \in [Q]} \sum_{r = 1}^{R_{k d}} \| (\tilde{σ}_{k d})_{r} (𝐮_{k d})_{q, r} \|$
		$\leq R_{k d} A_{𝐮, 𝐯}^{2} \max_{r \in [R_{k d}]} \| (σ_{k d})_{r} - (\tilde{σ}_{k d})_{r} \|$
		$+ R_{k d} A_{𝐮, 𝐯} A_{σ} (\max_{q \in [Q], r \in [R_{k d}]} \| (\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r} \|$
		$+ \max_{r \in [R_{k d}], p \in [P]} \| (𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p} \|) .$

Therefore, (S-21) is immediately implied if we now choose $(\tilde{σ}_{k d})_{r}$ , $(\tilde{𝐮}_{k d})_{q, r}$ and $(\tilde{𝐯}_{k d}^{⊤})_{r, p}$ such that

	$\max_{r \in [R_{k d}]} \| (σ_{k d})_{r} - (\tilde{σ}_{k d})_{r} \|$	$\leq \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}},$
	$\max_{q \in [Q], r \in [R_{k d}]} \| (\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r} \|$	$\leq \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}},$
	$\max_{r \in [R_{k d}], p \in [P]} \| (𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p} \|$	$\leq \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}} .$

This task can be accomplished as follows: for all $r \in [R_{k d}]$ , $p \in [P]$ , $q \in [Q]$ , set

	$S$	$= ℤ \cap [0, ⌊ A_{σ} \frac{6 R_{k d} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}} ⌋],$
	$(\tilde{σ}_{k d})_{r}$	$= \arg \min_{ζ \in S} \| (σ_{k d})_{r} - \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}} ζ \|,$
	$U$	$= ℤ \cap [⌊ - A_{𝐮, 𝐯} \frac{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}} ⌋, ⌊ A_{𝐮, 𝐯} \frac{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}} ⌋],$
	$(\tilde{𝐮}_{k d})_{q, r}$	$= \arg \min_{μ \in U} \| (𝐮_{k d})_{q, r} - \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}} μ \|,$
	$(\tilde{𝐯}_{k d}^{⊤})_{r, p}$	$= \arg \min_{υ \in U} \| (𝐯_{k d}^{⊤})_{r, p} - \frac{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{6 R_{k d} A_{𝐮, 𝐯} A_{σ} D_{V} P \sqrt{Q}} υ \| .$

Note that, according to (15, I.8), we only need to determine the vectors $(((\tilde{𝐮}_{k d})_{q, r})_{q \in [Q - r]})_{r \in [R_{k d}]}$ and $(((\tilde{𝐯}_{k d})_{r, p})_{j \in [c a r d (J_{i n}) - r]})_{r \in [R_{k d}]}$ since the remaining elements of such vectors belong to the the nullspace of $𝚼_{k d}^{R_{k d}}$ and $𝚼_{k d}^{R_{k d} ⊤}$ . The number of total free parameters in the previous two vectors are

	$\sum_{r = 1}^{R_{k d}} (Q - r)$	$= R_{k d} (\frac{2 Q - R_{k d} - 1}{2}),$
	$\sum_{r = 1}^{R_{k d}} (c a r d (J_{i n}) - r)$	$= R_{k d} (\frac{2 c a r d (J_{i n}) - R_{k d} - 1}{2}) .$

To this end, for all $k \in [K]$ , $d \in [D_{V}]$ , and $q \in [Q]$ , we let

(\tilde{𝚼}_{k d}^{R_{k d}})_{q, p} = {\begin{matrix} \sum_{r = 1}^{R_{k d}} (\tilde{σ}_{k d})_{r} (\tilde{𝐮}_{k d})_{q, r} (\tilde{𝐯}_{k d}^{⊤})_{r, p} & if p \in J_{i n}, \\ 0 & if p \in [P] ∖ J_{i n} . \end{matrix}

In particular, (S-19) is proved by the following entropy controlling

	$c a r d (G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}))$
	$\leq [\frac{4 A_{𝐮, 𝐯} \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}]^{Q} \prod_{d = 1}^{D_{V}} [\frac{6 R_{k d} A_{σ} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}]^{R_{k d}} [\frac{12 R_{k d} A_{σ} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}]^{R_{k d} (q + c a r d (J_{i n}) - R_{k d} - 1)}$
	$= [\frac{\exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}}]^{dim (𝐕_{(D_{V}, J, 𝐑_{k})})}, where$
	$dim (𝐕_{(D_{V}, J, 𝐑_{k})}) = Q + \sum_{d = 1}^{D_{V}} R_{k d} (Q + c a r d (J_{i n}) - R_{k d}), C_{𝐕_{(D_{V}, J, 𝐑_{k})}} = \frac{\ln (C_{(D_{V}, J, 𝐑_{k})})}{dim (𝐕_{(D_{V}, J, 𝐑_{k})})},$
	$and C_{(D_{V}, J, 𝐑_{k})} = [4 A_{𝐮, 𝐯} \sqrt{Q}]^{Q} [12 R_{k d} A_{σ} A_{𝐮, 𝐯}^{2} D_{V} P \sqrt{Q}]^{\sum_{d = 1}^{D_{V}} R_{k d} (Q + c a r d (J_{i n}) - R_{k d})} 2^{- \sum_{d = 1}^{D_{V}} R_{k d}} .$

Step 3: Upper bound of the number of the bracketing entropy for $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ .

Next, in order to evaluate the ratio of two Gaussian densities, we make use of Lemma S-6.

Lemma S-6 (Proposition C.1 from [13] ).

Let $ϕ (\cdot; 𝛍_{1}, 𝚺_{1})$ and $ϕ (\cdot; 𝛍_{2}, 𝚺_{2})$ be two Gaussian densities. If $𝚺_{2} - 𝚺_{1}$ is a positive definite matrix then for all $𝐲 \in ℝ^{Q}$ ,

\frac{ϕ (𝐲; 𝝁_{1}, 𝚺_{1})}{ϕ (𝐲; 𝝁_{2}, 𝚺_{2})} \leq \sqrt{\frac{| 𝚺_{2} |}{| 𝚺_{1} |}} \exp [\frac{1}{2} (𝝁_{1} - 𝝁_{2})^{⊤} (𝚺_{2} - 𝚺_{1})^{- 1} (𝝁_{1} - 𝝁_{2})] .

Then, Lemma S-7 allows us to fulfill the assumptions of Lemma S-6.

Lemma S-7 (Similar to Lemma B.8 from [13] ).

Assume that $0 < ϵ < c_{𝚺}^{2} / 9$ , and set $α = 3 \sqrt{ϵ} / c_{𝚺}$ . Then, for every $k \in [K]$ , $(1 + α) \tilde{𝚺}_{k} (B_{k}) - 𝚺_{k} (B_{k})$ and $𝚺_{k} (B_{k}) - (1 + α)^{- 1} \tilde{𝚺}_{k} (B_{k})$ are both positive definite matrices. Moreover, for all $𝐲 \in ℝ^{Q}$ ,

𝐲^{⊤} [(1 + α) \tilde{𝚺}_{k} (B_{k}) - 𝚺_{k} (B_{k})] 𝐲 \geq ϵ ∥ 𝐲 ∥_{2}^{2}, 𝐲^{⊤} [𝚺_{k} (B_{k}) - (1 + α)^{- 1} \tilde{𝚺}_{k} (B_{k})] 𝐲 \geq ϵ ∥ 𝐲 ∥_{2}^{2} .

Proof.

For all $𝐲 \neq 𝟎$ , since $sup_{λ \in v p (𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k}))} | λ | = ∥ 𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k}) ∥_{2} \leq ϵ$ , $- ϵ \geq - c_{𝚺} / 3$ , and $α = 3 ϵ / c_{𝚺}$ , it follow that

	$𝐲^{⊤} [(1 + α) \tilde{𝚺}_{k} (B_{k}) - 𝚺_{k} (B_{k})] 𝐲$	$= (1 + α) 𝐲^{⊤} [\tilde{𝚺}_{k} (B_{k}) - 𝚺_{k} (B_{k})] 𝐲 + α 𝐲^{⊤} 𝚺_{k} (B_{k}) 𝐲$
		$\geq - (1 + α) ∥ \tilde{𝚺}_{k} (B_{k}) - 𝚺_{k} (B_{k}) ∥_{2} ∥ 𝐲 ∥_{2}^{2} + α c_{𝚺} ∥ 𝐲 ∥_{2}^{2}$
		$\geq (α c_{𝚺} - (1 + α) ϵ) ∥ 𝐲 ∥_{2}^{2} = (α c_{𝚺} - α ϵ - ϵ) ∥ 𝐲 ∥_{2}^{2}$
		$\geq (\frac{2}{3} α c_{𝚺} - ϵ) ∥ 𝐲 ∥_{2}^{2} = ϵ ∥ 𝐲 ∥_{2}^{2} > 0,$

and

	$𝐲^{⊤} [𝚺_{k} (B_{k}) - (1 + α)^{- 1} \tilde{𝚺}_{k} (B_{k})] 𝐲$
	$= (1 + α)^{- 1} 𝐲^{⊤} [𝚺_{k} (B_{k}) - \tilde{𝚺}_{k} (B_{k})] 𝐲 + (1 - (1 + α)^{- 1}) 𝐲^{⊤} 𝚺_{k} (B_{k}) 𝐲$
	$\geq (\frac{α c_{𝚺} - ϵ}{1 + α}) ∥ 𝐲 ∥_{2}^{2} = \frac{2 ϵ}{1 + α} ∥ 𝐲 ∥_{2}^{2} \geq ϵ ∥ 𝐲 ∥_{2}^{2} > 0 .$

∎

By using Lemma S-6 and the same argument as in the proof of Lemma B.9 from [13] , given $0 < ϵ < c_{𝚺} / 3$ , where $ϵ$ is chosen later, and $α = 3 ϵ / c_{𝚺}$ , we obtain

\max {\frac{l (𝐱, 𝐲)}{f (𝐱, 𝐲)}, \frac{f (𝐱, 𝐲)}{u (𝐱, 𝐲)}} \leq (1 + 2 α)^{- \frac{Q}{2}} \exp (\frac{∥ 𝐯_{(D_{V}, J, 𝐑_{k})} (𝐱) - \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱) ∥_{2}^{2}}{2 ϵ}) .

(S-22)

Because $\ln (\cdot)$ is a non-decreasing function, $\ln (1 + 2 α) \geq α, \forall α \in [0, 1]$ . Combined with (S-18) where $δ^{2}_{𝐕_{(D_{V}, J, 𝐑_{k})}} = Q α ϵ$ , we conclude that

\max {\ln (\frac{l (𝐱, 𝐲)}{f (𝐱, 𝐲)}), \ln (\frac{f (𝐱, 𝐲)}{u (𝐱, 𝐲)})}

\leq - \frac{Q}{2} \ln (1 + 2 α) + \frac{δ^{2}_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{2 ϵ} \leq - \frac{Q}{2} α + \frac{δ^{2}_{𝐕_{(D_{V}, J, 𝐑_{k})}}}{2 ϵ} = 0 .

This means that $l (𝐱, 𝐲) \leq f (𝐱, 𝐲) \leq u (𝐱, 𝐲), \forall (𝐱, 𝐲) \in 𝒳 \times 𝒴$ . Hence, it remains to bound the size of bracket $[l, u]$ w.r.t. $d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}$ .

To this end, we aim to verify that $d^{2}_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} (l, u) \leq \frac{δ}{2}$ . To accomplish this, we make use of Lemma S-8.

Lemma S-8 (Proposition C.3 from [13] ).

Let $ϕ (\cdot; 𝛍_{1}, 𝚺_{1})$ and $ϕ (\cdot; 𝛍_{2}, 𝚺_{2})$ be two Gaussian densities with full rank covariance. It holds that

	$d^{2} (ϕ (\cdot; 𝝁_{1}, 𝚺_{1}), ϕ (\cdot; 𝝁_{2}, 𝚺_{2}))$
	$= 2 {1 - 2^{q / 2} \| 𝚺_{1} 𝚺_{2} \|^{- 1 / 4} \| 𝚺_{1}^{- 1} + 𝚺_{2}^{- 1} \|^{- 1 / 2} \exp [- \frac{1}{4} (𝝁_{1} - 𝝁_{2})^{⊤} (𝚺_{1} + 𝚺_{2})^{- 1} (𝝁_{1} - 𝝁_{2})]} .$

Therefore, using the fact that $\cosh (t) = \frac{e^{- t} + e^{t}}{2}$ , Lemma S-8 leads to, for all $𝐱 \in 𝒳$ ,

	$d^{2} (l (𝐱, \cdot), u (𝐱, \cdot))$	$= \int_{𝒴} [l (𝐱, 𝐲) + u (𝐱, 𝐲) - 2 \sqrt{l (𝐱, 𝐲) u (𝐱, 𝐲)}] d 𝐲$
		$= (1 + 2 α)^{- Q} + (1 + 2 α)^{Q} - 2$
		$+ d^{2} (ϕ (\cdot; \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱), (1 + α)^{- 1} \tilde{𝚺}_{k} (B_{k})), ϕ (\cdot; \tilde{𝐯}_{(D_{V}, J, 𝐑_{k})} (𝐱), (1 + α) \tilde{𝚺}_{k} (B_{k})))$
		$= 2 \cosh [Q \ln (1 + 2 α)] - 2$
		$+ 2 [1 - 2^{Q / 2} [(1 + α)^{- 1} + (1 + α)]^{- Q / 2} \| \tilde{𝚺}_{k} (B_{k}) \|^{- 1 / 2} \| \tilde{𝚺}_{k} (B_{k}) \|^{1 / 2}]$
		$= 2 \cosh [Q \ln (1 + 2 α)] - 2 + 2 - 2 [\cosh (\ln (1 + α))]^{- Q / 2}$
		$= 2 g (Q \ln (1 + 2 α)) + 2 h (\ln (1 + α)),$

where $g (t) = \cosh (t) - 1 = \frac{e^{- t} + e^{t}}{2} - 1$ , and $h (t) = 1 - \cosh (t)^{- Q / 2}$ . The upper bounds of terms $g$ and $h$ separately imply that, for all $𝐲 \in 𝒴$ ,

d^{2} (l (𝐱, \cdot), u (𝐱, \cdot)) \leq 2 (2 \cosh (\frac{1}{\sqrt{6}}) α^{2} Q^{2} + \frac{1}{4} α^{2} Q^{2}) \leq 6 α^{2} Q^{2} = \frac{δ^{2}}{4},

where we choose $α = \frac{3 ϵ}{c_{𝚺}}, ϵ = \frac{δ c_{𝚺}}{6 \sqrt{6} Q}$ , $\forall δ \in (0, 1], Q \in ℕ^{⋆}, c_{𝚺} > 0$ , which appears in (S-22) and satisfies $α = \frac{δ}{2 \sqrt{6} Q}$ and $0 < ϵ < \frac{c_{𝚺}}{3}$ . Indeed, studying functions $g$ and $h$ yields

	$𝐠^{'} (t)$	$= \sinh (t), 𝐠^{''} (t) = \cosh (t) \leq \cosh (c), \forall t \in [0, c], c \in ℝ_{+},$
	$h^{'} (t)$	$= \frac{Q}{2} \cosh (t)^{- Q / 2 - 1} \sinh (t),$
	$h^{''} (t)$	$= \frac{Q}{2} (- \frac{Q}{2} - 1) \cosh (t)^{- Q / 2 - 2} \sinh^{2} (t) + \frac{Q}{2} \cosh (t)^{- Q / 2}$
		$= \frac{Q}{2} (1 - (\frac{Q}{2} + 1) (\frac{\sinh (t)}{\cosh (t)})^{2}) \cosh (t)^{- Q / 2} \leq \frac{Q}{2},$

where we used the fact that $\cosh (t) \geq 1$ . Then, since $g (0) = 0, 𝐠^{'} (0) = 0, h (0) = 0, h^{'} (0) = 0$ , by applying Taylor’s Theorem, it is true that

	$g (t)$	$= g (t) - g (0) - 𝐠^{'} (0) t = R_{0, 1} (t) \leq \cosh (c) \frac{t^{2}}{2}, \forall t \in [0, c],$
	$h (t)$	$= h (t) - h (0) - h^{'} (0) t = R_{0, 1} (t) \leq \frac{Q}{2} \frac{t^{2}}{2} \leq \frac{Q^{2}}{2} \frac{t^{2}}{2}, \forall t \geq 0 .$

We wish to find an upper bound for $t = Q \ln (1 + 2 α)$ , $Q \in ℕ^{⋆}$ , $α = \frac{δ}{2 \sqrt{6} Q}$ , $δ \in (0, 1]$ . Since $\ln (\cdot)$ is an increasing function, then we have

t = Q \ln (1 + \frac{δ}{\sqrt{6} Q}) \leq Q \ln (1 + \frac{1}{\sqrt{6} Q}) \leq Q \frac{1}{\sqrt{6} Q} = \frac{1}{\sqrt{6}}, \forall δ \in (0, 1],

since $\ln (1 + \frac{1}{\sqrt{6} Q}) \leq \frac{1}{\sqrt{6} Q}$ , $\forall Q \in ℕ^{⋆}$ . Then, since $\ln (1 + 2 α) \leq 2 α, \forall α \geq 0$ ,

	$g (Q \ln (1 + 2 α))$	$\leq \cosh (\frac{1}{\sqrt{6}}) \frac{(Q \ln (1 + 2 α))^{2}}{2} \leq \cosh (\frac{1}{\sqrt{6}}) \frac{Q^{2}}{2} 4 α^{2},$
	$h (\ln (1 + α))$	$\leq \frac{Q^{2}}{2} \frac{(\ln (1 + α))^{2}}{2} \leq \frac{Q^{2} α^{2}}{4} .$

Next, note that the set of $δ / 2$ -brackets $[l, u]$ over $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ is totally defined by the parameter spaces $\tilde{S}^{d i s c}_{B_{k}} (ϵ)$ and $G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}})$ . This leads to an upper bound of the $δ / 2$ -bracketing entropy of $𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}$ is evaluated from an upper bound of the two set cardinalities. Hence, given any $δ > 0$ , by choosing $ϵ = \frac{δ c_{𝚺}}{6 \sqrt{6} Q}$ , $α = \frac{3 ϵ}{c_{𝚺}} = \frac{δ}{2 \sqrt{6} Q}$ , and $δ^{2}_{𝐕_{(D_{V}, J, 𝐑_{k})}} = Q α ϵ = Q \frac{δ}{2 \sqrt{6} Q} \frac{δ c_{𝚺}}{6 \sqrt{6} Q} = \frac{δ^{2} c_{𝚺}}{72 Q}$ , it holds that

	$𝒩_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$
	$\leq c a r d (\tilde{S}^{d i s c}_{B_{k}} (ϵ)) \times c a r d (G_{𝐕_{(D_{V}, J, 𝐑_{k})}} (δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}))$
	$\leq (⌊ \frac{2 C_{𝚺}}{ϵ} ⌋ \frac{Q (Q - 1)}{2 D_{B_{k}}})^{D_{B_{k}}} (\frac{\exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{δ_{𝐕_{(D_{V}, J, 𝐑_{k})}}})^{dim (𝐕_{(D_{V}, J, 𝐑_{k})})} (using (S-16) and (S-19))$
	$\leq (\frac{2 C_{𝚺} 6 \sqrt{6} Q}{δ c_{𝚺}} \frac{Q (Q - 1)}{2 D_{B_{k}}})^{D_{B_{k}}} (\frac{6 \sqrt{2 Q} \exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{δ \sqrt{c_{𝚺}}})^{dim (𝐕_{(D_{V}, J, 𝐑_{k})})}$
	$= (\frac{6 \sqrt{6} C_{𝚺} Q^{2} (Q - 1)}{c_{𝚺} D_{B_{k}}})^{D_{B_{k}}} (\frac{6 \sqrt{2 Q} \exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{\sqrt{c_{𝚺}}})^{dim (𝐕_{(D_{V}, J, 𝐑_{k})})} (\frac{1}{δ})^{D_{B_{k}} + dim (𝐕_{(D_{V}, J, 𝐑_{k})})} .$

To this end, note that $dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) = D_{B_{k}} + dim (𝐕_{(D_{V}, J, 𝐑_{k})})$ , we obtain

	$ℋ_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})$
	$= \ln (𝒩_{[\cdot], d_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}}} (\frac{δ}{2}, 𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}))$
	$\leq D_{B_{k}} \ln (\frac{6 \sqrt{6} C_{𝚺} Q^{2} (Q - 1)}{c_{𝚺} D_{B_{k}}}) + dim (𝐕_{(D_{V}, J, 𝐑_{k})}) \ln (\frac{6 \sqrt{2 Q} \exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{\sqrt{c_{𝚺}}})$
	$+ (D_{B_{k}} + dim (𝐕_{(D_{V}, J, 𝐑_{k})})) \ln (\frac{1}{δ})$
	$= dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}) (C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} + \ln (\frac{1}{δ})),$

where $C_{𝒢_{(K, D_{V}, 𝐁, J, 𝐑)}} = \frac{D_{B_{k}} \ln (\frac{6 \sqrt{6} C_{𝚺} Q^{2} (Q - 1)}{c_{𝚺} D_{B_{k}}}) + dim (𝐕_{(D_{V}, J, 𝐑_{k})}) \ln (\frac{6 \sqrt{2 Q} \exp (C_{𝐕_{(D_{V}, J, 𝐑_{k})}})}{\sqrt{C_{𝚺}}})}{dim (𝒢_{(K, D_{V}, 𝐁, J, 𝐑)})}$ .

Supplementary References

(1) Barron, A.R., Huang, C., Li, J., Luo, X.: The MDL principle, penalized likelihoods, and statistical risk. Festschrift in Honor of Jorma Rissanen on the Occasion of his 75th Birthday pp. 33–63 (2008) ↩ S-1.0.1
(2) Cohen, S.X., Le Pennec, E.: Partition-based conditional density estimation. ESAIM: Probability and Statistics 17, 672–697 (2013) ↩ S-2
(3) Cohen, S., Le Pennec, E.: Conditional density estimation by penalized likelihood model selection and applications. Technical report, INRIA (2011) ↩ S-1 S-2
(4) Devijver, E.: Finite mixture regression: a sparse variable selection by model selection for clustering. Electronic Journal of Statistics 9(2), 2642–2674 (2015) ↩ S-1 S-1.0.1 S-1.0.2 S-3.2
(5) Devijver, E.: Joint rank and variable selection for parsimonious estimation in a high-dimensional finite mixture regression model. Journal of Multivariate Analysis 157, 1–13 (2017) ↩ S-1 S-3.2
(6) Devijver, E., Gallopin, M.: Block-diagonal covariance selection for high-dimensional Gaussian graphical models. Journal of the American Statistical Association 113(521), 306–314 (2018) ↩ S-1 S-3.2 S-3.2.2
(7) Feller, W.: An introduction to probability theory and its applications, vol. 1. John Wiley (1957) ↩ S-2
(8) Van de Geer, S.: Empirical Processes in M-estimation, vol. 6. Cambridge University Press (2000) ↩ S-1.0.1
(9) Genovese, C.R., Wasserman, L.: Rates of convergence for the Gaussian mixture sieve. The Annals of Statistics 28(4), 1105–1127 (2000) ↩ S-1 S-2 S-3.2.2
(10) Ghosal, S., van der Vaart, A.W.: Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities. The Annals of Statistics 29(5), 1233–1263 (2001) ↩ S-2
(11) Kosorok, M.R.: Introduction to empirical processes and semiparametric inference. Springer Science & Business Media (2007) ↩ S-1.0.1
(12) Massart, P.: Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003. Springer (2007) ↩ S-1 S-1.0.1
(13) Maugis, C., Michel, B.: A non asymptotic penalized criterion for Gaussian mixture model selection. ESAIM: Probability and Statistics 15, 41–68 (2011) ↩ S-1 S-3.2 S-3.2.2
(14) Montuelle, L., Le Pennec, E., et al.: Mixture of Gaussian regressions model with logistic weights, a penalized maximum likelihood approach. Electronic Journal of Statistics 8(1), 1661–1695 (2014) ↩ S-1 S-2 S-3.2
(15) Strang, G.: Linear algebra and learning from data. Wellesley-Cambridge Press Cambridge (2019) ↩ S-3.2.2
(16) Van Der Vaart, A., Wellner, J.: Weak convergence and empirical processes: With applications to statistics. Springer 58, 59 (1996) ↩ S-1.0.1

[bib.bib1] (1) Barron, A.R., Huang, C., Li, J., Luo, X.: The MDL principle, penalized likelihoods, and statistical risk. Festschrift in Honor of Jorma Rissanen on the Occasion of his 75th Birthday pp. 33–63 (2008) ↩ S-1.0.1

[bib.bib2] (2) Cohen, S.X., Le Pennec, E.: Partition-based conditional density estimation. ESAIM: Probability and Statistics 17, 672–697 (2013) ↩ S-2

[bib.bib3] (3) Cohen, S., Le Pennec, E.: Conditional density estimation by penalized likelihood model selection and applications. Technical report, INRIA (2011) ↩ S-1 S-2

[bib.bib4] (4) Devijver, E.: Finite mixture regression: a sparse variable selection by model selection for clustering. Electronic Journal of Statistics 9(2), 2642–2674 (2015) ↩ S-1 S-1.0.1 S-1.0.2 S-3.2

[bib.bib5] (5) Devijver, E.: Joint rank and variable selection for parsimonious estimation in a high-dimensional finite mixture regression model. Journal of Multivariate Analysis 157, 1–13 (2017) ↩ S-1 S-3.2

[bib.bib6] (6) Devijver, E., Gallopin, M.: Block-diagonal covariance selection for high-dimensional Gaussian graphical models. Journal of the American Statistical Association 113(521), 306–314 (2018) ↩ S-1 S-3.2 S-3.2.2

[bib.bib7] (7) Feller, W.: An introduction to probability theory and its applications, vol. 1. John Wiley (1957) ↩ S-2

[bib.bib8] (8) Van de Geer, S.: Empirical Processes in M-estimation, vol. 6. Cambridge University Press (2000) ↩ S-1.0.1

[bib.bib9] (9) Genovese, C.R., Wasserman, L.: Rates of convergence for the Gaussian mixture sieve. The Annals of Statistics 28(4), 1105–1127 (2000) ↩ S-1 S-2 S-3.2.2

[bib.bib10] (10) Ghosal, S., van der Vaart, A.W.: Entropies and rates of convergence for maximum likelihood and Bayes estimation for mixtures of normal densities. The Annals of Statistics 29(5), 1233–1263 (2001) ↩ S-2

[bib.bib11] (11) Kosorok, M.R.: Introduction to empirical processes and semiparametric inference. Springer Science & Business Media (2007) ↩ S-1.0.1

[bib.bib12] (12) Massart, P.: Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003. Springer (2007) ↩ S-1 S-1.0.1

[bib.bib13] (13) Maugis, C., Michel, B.: A non asymptotic penalized criterion for Gaussian mixture model selection. ESAIM: Probability and Statistics 15, 41–68 (2011) ↩ S-1 S-3.2 S-3.2.2

[bib.bib14] (14) Montuelle, L., Le Pennec, E., et al.: Mixture of Gaussian regressions model with logistic weights, a penalized maximum likelihood approach. Electronic Journal of Statistics 8(1), 1661–1695 (2014) ↩ S-1 S-2 S-3.2

[bib.bib15] (15) Strang, G.: Linear algebra and learning from data. Wellesley-Cambridge Press Cambridge (2019) ↩ S-3.2.2

[bib.bib16] (16) Van Der Vaart, A., Wellner, J.: Weak convergence and empirical processes: With applications to statistics. Springer 58, 59 (1996) ↩ S-1.0.1

	$\| \| \| 𝚼_{k d}^{R_{k d}} - \tilde{𝚼}_{k d}^{R_{k d}} \| \| \|_{\infty}$	$= \max_{q \in [Q], p \in [P]} \| \sum_{r = 1}^{R_{k d}} [(σ_{k d})_{r} (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p} - (\tilde{σ}_{k d})_{r} (\tilde{𝐮}_{k d})_{q, r} (\tilde{𝐯}_{k d}^{⊤})_{r, p}] \|$
		$= \max_{q \in [Q], p \in [P]} \| \sum_{r = 1}^{R_{k d}} [((σ_{k d})_{r} - (\tilde{σ}_{k d})_{r}) (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p}$
		$- (\tilde{σ}_{k d})_{r} ((\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r}) (\tilde{𝐯}_{k d}^{⊤})_{r, p}$
		$- (\tilde{σ}_{k d})_{r} (𝐮_{k d})_{q, r} ((𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p})] \|$
		$\leq \max_{r \in [R_{k d}]} \| (σ_{k d})_{r} - (\tilde{σ}_{k d})_{r} \| \max_{q \in [Q], p \in [P]} \sum_{r = 1}^{R_{k d}} \| (𝐮_{k d})_{q, r} (𝐯_{k d}^{⊤})_{r, p} \|$
		$+ \max_{q \in [Q], r \in [R_{k d}]} \| (\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r} \| \max_{p \in [P]} \sum_{r = 1}^{R_{k d}} \| (\tilde{σ}_{k d})_{r} (\tilde{𝐯}_{k d}^{⊤})_{r, p} \|$
		$+ \max_{r \in [R_{k d}], p \in [P]} \| (𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p} \| \max_{q \in [Q]} \sum_{r = 1}^{R_{k d}} \| (\tilde{σ}_{k d})_{r} (𝐮_{k d})_{q, r} \|$
		$\leq R_{k d} A_{𝐮, 𝐯}^{2} \max_{r \in [R_{k d}]} \| (σ_{k d})_{r} - (\tilde{σ}_{k d})_{r} \|$
		$+ R_{k d} A_{𝐮, 𝐯} A_{σ} (\max_{q \in [Q], r \in [R_{k d}]} \| (\tilde{𝐮}_{k d})_{q, r} - (𝐮_{k d})_{q, r} \|$
		$+ \max_{r \in [R_{k d}], p \in [P]} \| (𝐯_{k d}^{⊤})_{r, p} - (\tilde{𝐯}_{k d}^{⊤})_{r, p} \|) .$