[proofplan] The lower bound is a metric testing argument. We construct many $k$-sparse vectors whose supports are well separated, scale their common amplitude so that the induced Gaussian measures have small Kullback-Leibler divergence, and then apply an elementary Fano testing bound. The lower restricted eigenvalue turns coefficient separation into prediction separation. For the upper bound we use the constrained least-squares estimator over $\Theta_k$ and control the largest Gaussian projection over all coordinate subspaces of dimension at most $2k$. [/proofplan]

[step:Fix the restricted eigenvalue normalization used throughout] For $1\le m\le d$, the restricted lower prediction eigenvalue of $X$ is \begin{align*} \kappa_-(m;X):=\inf\left\{\frac{|Xu|^2}{n|u|^2}:u\in\mathbb R^d\setminus\{0\},\ |\operatorname{supp}u|\le m\right\}. \end{align*} The restricted upper prediction eigenvalue of $X$ is \begin{align*} \kappa_+(m;X):=\sup\left\{\frac{|Xu|^2}{n|u|^2}:u\in\mathbb R^d\setminus\{0\},\ |\operatorname{supp}u|\le m\right\}. \end{align*} Thus every $2k$-sparse vector $u\in\mathbb R^d$ satisfies \begin{align*} a_0|u|^2\le \frac{1}{n}|Xu|^2\le A_0|u|^2. \end{align*} [/step]

[step:Build a sparse Hamming packing with logarithmic cardinality]We first record the combinatorial packing used in the lower bound. There exist a universal constant $c_1>0$ and vectors $z_1,\dots,z_M \in \{0,1\}^d$ such that $|\operatorname{supp} z_j| = k$ for every $j$, such that \begin{align*} |z_j-z_\ell|^2 \ge \frac{k}{2} \quad\text{whenever }j\ne \ell, \end{align*} and such that \begin{align*} \log M \ge c_1 k\log(d/k). \end{align*} Let \begin{align*} \mathcal{H}:=\{z\in\{0,1\}^d: |\operatorname{supp}z|=k\} \end{align*} denote the family of constant-weight support indicators. We use the following [constant-weight Gilbert-Varshamov packing estimate](/page/Gilbert-Varshamov%20Bound): there is a universal constant $c_1>0$ such that, whenever $1\le k\le d/2$, the family $\mathcal{H}$ contains a subset $\mathcal{P}$ satisfying $|z-w|^2\ge k/2$ for all distinct $z,w\in\mathcal{P}$ and \begin{align*} |\mathcal{P}|\ge \exp\{c_1 k\log(d/k)\}. \end{align*} The hypotheses of this estimate are exactly $1\le k\le d/2$ and constant weight $k$, both of which hold here. Enumerating $\mathcal{P}$ as $z_1,\dots,z_M$ gives the required vectors.[/step]

[guided]The goal is to produce many possible sparse coefficient vectors, all with the same sparsity $k$, so that no two are too close. We work first with support indicators rather than amplitudes. Define \begin{align*} \mathcal{H}:=\{z\in\{0,1\}^d: |\operatorname{supp}z|=k\}. \end{align*} Thus each $z\in\mathcal{H}$ records a $k$-element subset of $\{1,\dots,d\}$. For vectors in $\{0,1\}^d$, the Hamming distance is exactly $|z-w|^2$, since each differing coordinate contributes $1$ to the squared Euclidean distance. The [constant-weight Gilbert-Varshamov packing estimate](/page/Gilbert-Varshamov%20Bound) says that, under the hypotheses $1\le k\le d/2$ and constant weight $k$, there is a universal constant $c_1>0$ and a subset $\mathcal{P}\subset\mathcal{H}$ with pairwise Hamming distance at least $k/2$ such that \begin{align*} |\mathcal{P}|\ge\exp\{c_1 k\log(d/k)\}. \end{align*} These hypotheses hold because the theorem assumes $1\le k\le d/2$ and every element of $\mathcal{H}$ has exactly $k$ nonzero coordinates. Enumerating $\mathcal{P}$ as $z_1,\dots,z_M$ gives the required packing.[/guided]

[step:Scale the packing so prediction distances are large and divergences are small]For each $\beta\in\Theta_k$, let $P_\beta$ denote the law on $\mathbb R^n$ of the observation vector $Y=X\beta+\varepsilon$, where $\varepsilon\sim\mathcal N(0,\sigma^2I_n)$. Define \begin{align*} r^2 := \frac{c_2\sigma^2\log M}{A_0nk}, \end{align*} where $c_2>0$ is a universal constant to be chosen below, and define $\beta_j:=rz_j\in\Theta_k$ for $j=1,\dots,M$. For $j\ne \ell$, the vector $\beta_j-\beta_\ell$ is $2k$-sparse. By the lower restricted eigenvalue bound, \begin{align*} \frac{1}{n}|X(\beta_j-\beta_\ell)|^2 \ge a_0|\beta_j-\beta_\ell|^2 = a_0r^2|z_j-z_\ell|^2 \ge \frac{a_0r^2k}{2}. \end{align*} Set \begin{align*} s^2:=\frac{a_0r^2k}{2}. \end{align*} Then all distinct elements of the packing are separated by prediction distance at least $s$ in the loss metric. For each $j$, the Kullback-Leibler divergence between $P_{\beta_j}$ and $P_0$ is \begin{align*} D_{\mathrm{KL}}(P_{\beta_j}\|P_0) = \frac{|X\beta_j|^2}{2\sigma^2} \le \frac{nA_0|\beta_j|^2}{2\sigma^2} = \frac{nA_0r^2k}{2\sigma^2} = \frac{c_2}{2}\log M. \end{align*} Choosing $c_2\le 1/8$ gives \begin{align*} \frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_{\beta_j}\|P_0) \le \frac{1}{16}\log M. \end{align*}[/step]

[guided]For each $\beta\in\Theta_k$, $P_\beta$ denotes the law on $\mathbb R^n$ of $Y=X\beta+\varepsilon$ with $\varepsilon\sim\mathcal N(0,\sigma^2I_n)$. We choose the amplitude \begin{align*} r^2 := \frac{c_2\sigma^2\log M}{A_0nk}, \end{align*} where $c_2>0$ will be fixed small, and set $\beta_j:=rz_j$ for $j=1,\dots,M$. Since each $z_j$ has exactly $k$ nonzero entries, each $\beta_j$ belongs to $\Theta_k$. If $j\ne \ell$, then $\beta_j-\beta_\ell$ has support contained in $\operatorname{supp}z_j\cup\operatorname{supp}z_\ell$, so it is $2k$-sparse. The definition of $\kappa_-(2k;X)$ and the hypothesis $\kappa_-(2k;X)\ge a_0$ give \begin{align*} \frac{1}{n}|X(\beta_j-\beta_\ell)|^2 \ge a_0|\beta_j-\beta_\ell|^2 = a_0r^2|z_j-z_\ell|^2 \ge \frac{a_0r^2k}{2}. \end{align*} Thus, with \begin{align*} s^2:=\frac{a_0r^2k}{2}, \end{align*} the packing is separated by at least $s$ in the prediction loss metric. The same amplitude must keep the statistical models close enough for [Fano's inequality](/theorems/1654). For centered Gaussian measures with common covariance $\sigma^2I_n$ and means $X\beta_j$ and $0$, the Kullback-Leibler divergence is \begin{align*} D_{\mathrm{KL}}(P_{\beta_j}\|P_0) = \frac{|X\beta_j|^2}{2\sigma^2}. \end{align*} Since $\beta_j$ is $k$-sparse, it is also $2k$-sparse, so the definition of $\kappa_+(2k;X)$ and the hypothesis $\kappa_+(2k;X)\le A_0$ imply \begin{align*} D_{\mathrm{KL}}(P_{\beta_j}\|P_0) \le \frac{nA_0|\beta_j|^2}{2\sigma^2} = \frac{nA_0r^2k}{2\sigma^2} = \frac{c_2}{2}\log M. \end{align*} Choosing $c_2\le 1/8$ makes the average divergence satisfy \begin{align*} \frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_{\beta_j}\|P_0) \le \frac{1}{16}\log M. \end{align*} This is the exact small-divergence condition needed for the Fano step.[/guided]

[step:Convert Fano testing error into minimax prediction risk]We use the following elementary form of [Fano's inequality](/page/Fano%27s%20Inequality): if $P_1,\dots,P_M$ are probability measures and $P_0$ is another probability measure satisfying \begin{align*} \frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_j\|P_0)\le \alpha\log M \quad\text{with }0<\alpha<1/8, \end{align*} then every measurable test $\psi:\mathbb{R}^n\to\{1,\dots,M\}$ satisfies \begin{align*} \sup_{1\le j\le M}P_j(\psi\ne j)\ge c_3, \end{align*} where $c_3>0$ is a universal constant. This follows from the standard entropy proof of Fano's inequality applied to the uniform prior on $\{1,\dots,M\}$. Let $\hat\beta:\mathbb{R}^n\to\mathbb{R}^d$ be any estimator. Define a measurable nearest-packing selector $\psi_{\hat\beta}:\mathbb{R}^n\to\{1,\dots,M\}$ by choosing an index minimizing \begin{align*} j\mapsto |X(\hat\beta(Y)-\beta_j)|. \end{align*} If $\psi_{\hat\beta}(Y)\ne j$, then the triangle inequality and the packing separation imply \begin{align*} |X(\hat\beta(Y)-\beta_j)| \ge \frac{\sqrt{n}s}{2}. \end{align*} Therefore, under $P_{\beta_j}$, \begin{align*} \mathbb E_{\beta_j}\left[\frac{1}{n}|X(\hat\beta-\beta_j)|^2\right] \ge \frac{s^2}{4}P_{\beta_j}(\psi_{\hat\beta}\ne j). \end{align*} Taking the supremum over $j$ and then the infimum over $\hat\beta$ gives \begin{align*} \inf_{\hat\beta}\sup_{\beta\in\Theta_k} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta-\beta)|^2\right] \ge \frac{c_3s^2}{4}. \end{align*} By the definition of $s^2$, \begin{align*} \frac{c_3s^2}{4}=\frac{c_3a_0r^2k}{8}. \end{align*} By the definition of $r^2$, \begin{align*} \frac{c_3a_0r^2k}{8}=\frac{c_3a_0c_2}{8A_0}\sigma^2\frac{\log M}{n}. \end{align*} Since $\log M\ge c_1k\log(d/k)$, the lower bound follows with \begin{align*} c:=\frac{c_1c_2c_3a_0}{8A_0}. \end{align*}[/step]

[guided]We now convert separation of the finite packing into a lower bound for every estimator. The [Fano inequality](/page/Fano%27s%20Inequality) form used here requires probability measures $P_1,\dots,P_M$ and a reference measure $P_0$ satisfying \begin{align*} \frac{1}{M}\sum_{j=1}^M D_{\mathrm{KL}}(P_j\|P_0)\le \alpha\log M \quad\text{with }0<\alpha<1/8. \end{align*} The previous step verified this hypothesis for $P_j=P_{\beta_j}$ with $\alpha=1/16$. Therefore every measurable test $\psi:\mathbb R^n\to\{1,\dots,M\}$ satisfies \begin{align*} \sup_{1\le j\le M}P_{\beta_j}(\psi\ne j)\ge c_3, \end{align*} where $c_3>0$ is universal. Let $\hat\beta:\mathbb R^n\to\mathbb R^d$ be any estimator. From it we build a test by nearest-neighbour decoding in prediction norm: define $\psi_{\hat\beta}:\mathbb R^n\to\{1,\dots,M\}$ to be an index minimizing \begin{align*} j\mapsto |X(\hat\beta(Y)-\beta_j)|, \end{align*} with a fixed tie-breaking rule. If the true index is $j$ but $\psi_{\hat\beta}(Y)=\ell\ne j$, then the nearest-neighbour property gives \begin{align*} |X(\hat\beta(Y)-\beta_\ell)|\le |X(\hat\beta(Y)-\beta_j)|. \end{align*} Using the triangle inequality and the packing separation, \begin{align*} \sqrt{n}s \le |X(\beta_j-\beta_\ell)| \le |X(\hat\beta(Y)-\beta_j)|+|X(\hat\beta(Y)-\beta_\ell)| \le 2|X(\hat\beta(Y)-\beta_j)|. \end{align*} Hence on the event $\{\psi_{\hat\beta}(Y)\ne j\}$, \begin{align*} \frac{1}{n}|X(\hat\beta(Y)-\beta_j)|^2\ge \frac{s^2}{4}. \end{align*} Taking expectation under $P_{\beta_j}$ gives \begin{align*} \mathbb E_{\beta_j}\left[\frac{1}{n}|X(\hat\beta-\beta_j)|^2\right] \ge \frac{s^2}{4}P_{\beta_j}(\psi_{\hat\beta}\ne j). \end{align*} Now take the supremum over $j$ and use the Fano lower bound on testing error: \begin{align*} \sup_{1\le j\le M}\mathbb E_{\beta_j}\left[\frac{1}{n}|X(\hat\beta-\beta_j)|^2\right] \ge \frac{c_3s^2}{4}. \end{align*} Since $\{\beta_1,\dots,\beta_M\}\subset\Theta_k$, this lower bounds the supremum over all $\beta\in\Theta_k$. Taking the infimum over estimators and substituting \begin{align*} s^2=\frac{a_0r^2k}{2}, \qquad r^2=\frac{c_2\sigma^2\log M}{A_0nk}, \end{align*} yields \begin{align*} \inf_{\hat\beta}\sup_{\beta\in\Theta_k} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta-\beta)|^2\right] \ge \frac{c_3a_0c_2}{8A_0}\sigma^2\frac{\log M}{n}. \end{align*} Finally $\log M\ge c_1k\log(d/k)$, so the lower bound holds with \begin{align*} c:=\frac{c_1c_2c_3a_0}{8A_0}. \end{align*}[/guided]

[step:Control constrained least squares by Gaussian projections]For each support set $S\subset\{1,\dots,d\}$ with $|S|\le k$, let $X_S$ denote the submatrix of $X$ formed by the columns indexed by $S$, and let $X_S^+$ denote its Moore-Penrose pseudoinverse. Define $b_S:\mathbb{R}^n\to\Theta_k$ by placing $X_S^+Y$ on the coordinates in $S$ and placing $0$ on $S^c$. Among the finitely many supports $S$ with $|S|\le k$, choose one minimizing $|Y-Xb_S(Y)|^2$, with lexicographic tie-breaking on the ordered support. This gives a measurable estimator $\hat\beta_{\mathrm{cls}}:\mathbb{R}^n\to\Theta_k$, since each $b_S$ is linear and the finite lexicographic comparison is made by measurable inequalities. For $\beta\in\Theta_k$, let $\varepsilon:=Y-X\beta$. Since $\beta$ is feasible, \begin{align*} |Y-X\hat\beta_{\mathrm{cls}}|^2\le |Y-X\beta|^2. \end{align*} With $\Delta:=\hat\beta_{\mathrm{cls}}-\beta$, this becomes \begin{align*} |\varepsilon-X\Delta|^2\le |\varepsilon|^2, \end{align*} and hence \begin{align*} |X\Delta|^2\le 2\varepsilon\cdot X\Delta. \end{align*} The vector $\Delta$ is $2k$-sparse. For each set $S\subset\{1,\dots,d\}$ with $|S|\le 2k$, let $V_S:=\operatorname{Range}(X_S)\subset\mathbb{R}^n$, where $X_S$ is the submatrix of $X$ formed by the columns indexed by $S$, and let $\Pi_S:\mathbb{R}^n\to V_S$ be the Euclidean [orthogonal projection](/theorems/437). If $S=\operatorname{supp}\Delta$, then $X\Delta\in V_S$, so \begin{align*} |X\Delta|^2 \le 2|\Pi_S\varepsilon|\,|X\Delta| \end{align*} by the [Cauchy-Schwarz inequality](/theorems/432) in $\mathbb{R}^n$. Therefore, defining the maximum over all subsets of size at most $2k$ in prose to avoid a row break in the subscript, \begin{align*} |X\Delta|^2\le4\max_{S\subset\{1,\dots,d\}:\ |S|\le 2k}|\Pi_S\varepsilon|^2. \end{align*}[/step]

[guided]The constrained least-squares estimator is the natural upper-bound estimator because it searches only over the true sparsity class. Define \begin{align*} \hat\beta_{\mathrm{cls}}:\mathbb{R}^n\to\Theta_k \end{align*} to be any minimizer of $b\mapsto |Y-Xb|^2$ over $b\in\Theta_k$. Since the true $\beta$ belongs to $\Theta_k$, it is one of the candidates in this minimization. Hence \begin{align*} |Y-X\hat\beta_{\mathrm{cls}}|^2\le |Y-X\beta|^2. \end{align*} Write the noise vector as $\varepsilon:=Y-X\beta$ and define the estimation error \begin{align*} \Delta:=\hat\beta_{\mathrm{cls}}-\beta. \end{align*} Then $Y-X\hat\beta_{\mathrm{cls}}=\varepsilon-X\Delta$, so the previous inequality becomes \begin{align*} |\varepsilon-X\Delta|^2\le |\varepsilon|^2. \end{align*} Expanding the square in the Euclidean [inner product](/page/Inner%20Product) on $\mathbb{R}^n$ gives \begin{align*} |\varepsilon|^2-2\varepsilon\cdot X\Delta+|X\Delta|^2\le |\varepsilon|^2, \end{align*} and cancelling $|\varepsilon|^2$ yields \begin{align*} |X\Delta|^2\le 2\varepsilon\cdot X\Delta. \end{align*} Now $\hat\beta_{\mathrm{cls}}$ and $\beta$ are both $k$-sparse, so $\Delta$ is $2k$-sparse. For each set $S\subset\{1,\dots,d\}$ with $|S|\le 2k$, define $V_S:=\operatorname{Range}(X_S)\subset\mathbb{R}^n$, where $X_S$ is the submatrix of $X$ with columns indexed by $S$, and let $\Pi_S:\mathbb{R}^n\to V_S$ denote the Euclidean orthogonal projection. If $S=\operatorname{supp}\Delta$, then $X\Delta\in V_S$. Therefore \begin{align*} \varepsilon\cdot X\Delta=(\Pi_S\varepsilon)\cdot X\Delta. \end{align*} Applying the Cauchy-Schwarz inequality in $\mathbb{R}^n$ gives \begin{align*} |X\Delta|^2 \le 2|\Pi_S\varepsilon|\,|X\Delta|. \end{align*} If $|X\Delta|=0$, the desired bound is immediate. Otherwise divide by $|X\Delta|$ and square: \begin{align*} |X\Delta|^2\le 4|\Pi_S\varepsilon|^2. \end{align*} Since $S$ is one of the subsets of $\{1,\dots,d\}$ with cardinality at most $2k$, enlarging from this single support to the maximum over all such supports gives \begin{align*} |X\Delta|^2\le4\max_{T\subset\{1,\dots,d\}:\ |T|\le 2k}|\Pi_T\varepsilon|^2. \end{align*} This is the key deterministic inequality: the prediction error is controlled by the largest Gaussian projection onto a coordinate-generated subspace of dimension at most $2k$.[/guided]

[step:Bound the maximum projected noise energy]For a fixed set $S\subset\{1,\dots,d\}$ with $|S|\le2k$, the subspace $V_S$ has dimension at most $2k$, and \begin{align*} |\Pi_S\varepsilon|^2/\sigma^2 \end{align*} is stochastically dominated by a chi-square [random variable](/page/Random%20Variable) with $2k$ degrees of freedom. This follows because $\Pi_S\varepsilon$ is a centered Gaussian vector in the subspace $V_S$ with covariance operator bounded by $\sigma^2\Pi_S$. The number of sets $S$ with $|S|\le2k$ is at most $N$, where \begin{align*} N:=\sum_{m=0}^{2k}\binom{d}{m}. \end{align*} Using $2k\le d$ and the elementary binomial bound $\binom{d}{m}\le (ed/m)^m$ for $1\le m\le 2k$, there is a universal constant $c_4>0$ such that \begin{align*} N\le \exp\{c_4k\log(ed/k)\}. \end{align*} We now derive the needed maximal bound from a chi-square tail estimate. For a fixed $S$, the [Laurent-Massart chi-square tail bound](/page/Laurent-Massart%20Chi-Square%20Tail%20Bound) gives, for every $u>0$, \begin{align*} \mathbb P_\beta\left(|\Pi_S\varepsilon|^2>\sigma^2(2k+2\sqrt{2ku}+2u)\right)\le e^{-u}. \end{align*} Taking a union bound over the $N$ supports gives, for every $u>0$, \begin{align*} \mathbb P_\beta\left(\max_{S\subset\{1,\dots,d\}:\ |S|\le2k}|\Pi_S\varepsilon|^2>\sigma^2(2k+2\sqrt{2k(u+\log N)}+2(u+\log N))\right)\le e^{-u}. \end{align*} Using $2\sqrt{ab}\le a+b$ with $a=2k$ and $b=u+\log N$, there is a universal constant $c_6>0$ such that, for every $u>0$, \begin{align*} \mathbb P_\beta\left(\max_{S\subset\{1,\dots,d\}:\ |S|\le2k}|\Pi_S\varepsilon|^2>c_6\sigma^2(k+\log N+u)\right)\le e^{-u}. \end{align*} For the nonnegative random variable \begin{align*} Z:=\max_{S\subset\{1,\dots,d\}:\ |S|\le2k}|\Pi_S\varepsilon|^2, \end{align*} set $t_0:=c_6\sigma^2(k+\log N)$. The tail identity for nonnegative random variables gives \begin{align*} \mathbb E_\beta[Z] \le t_0+\int_{t_0}^\infty \mathbb P_\beta(Z>t)\,d\mathcal{L}^1(t), \end{align*} where $\mathcal{L}^1$ denotes one-dimensional [Lebesgue measure](/page/Lebesgue%20Measure). With the change of variables $t=t_0+c_6\sigma^2u$, this becomes \begin{align*} \mathbb E_\beta[Z] \le c_6\sigma^2(k+\log N)+c_6\sigma^2\int_0^\infty e^{-u}\,d\mathcal{L}^1(u). \end{align*} Since $\int_0^\infty e^{-u}\,d\mathcal{L}^1(u)=1$ and $\log N\le c_4k\log(ed/k)$, after enlarging constants there is a universal constant $c_5>0$ such that \begin{align*} \mathbb E_\beta\left[\max_{S\subset\{1,\dots,d\}:\ |S|\le2k}|\Pi_S\varepsilon|^2\right] \le c_5\sigma^2 k\log(ed/k). \end{align*} Combining this with the deterministic inequality from the previous step yields \begin{align*} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta_{\mathrm{cls}}-\beta)|^2\right]\le4c_5\sigma^2\frac{k\log(ed/k)}{n}. \end{align*} Taking the supremum over $\beta\in\Theta_k$ and then using that the minimax risk is at most the risk of $\hat\beta_{\mathrm{cls}}$ gives the upper bound with $C:=4c_5$.[/step]

[guided]We must bound the random variable \begin{align*} Z:=\max_{S\subset\{1,\dots,d\}:\ |S|\le2k}|\Pi_S\varepsilon|^2, \end{align*} where $\varepsilon\sim\mathcal N(0,\sigma^2I_n)$ and $\Pi_S$ is the Euclidean orthogonal projection onto $V_S=\operatorname{Range}(X_S)$. For a fixed $S$, the subspace $V_S$ has dimension at most $|S|\le2k$. Therefore $|\Pi_S\varepsilon|^2/\sigma^2$ is stochastically dominated by a chi-square random variable with $2k$ degrees of freedom. The number of possible supports is \begin{align*} N:=\sum_{m=0}^{2k}\binom{d}{m}. \end{align*} Since $2k\le d$, the binomial estimate $\binom{d}{m}\le (ed/m)^m$ for $1\le m\le2k$ implies, after absorbing the finite sum into a universal constant, that \begin{align*} N\le \exp\{c_4k\log(ed/k)\} \end{align*} for a universal constant $c_4>0$. For a fixed $S$, the [Laurent-Massart chi-square tail bound](/page/Laurent-Massart%20Chi-Square%20Tail%20Bound) gives, for every $v>0$, \begin{align*} \mathbb P_\beta\left(|\Pi_S\varepsilon|^2>\sigma^2(2k+2\sqrt{2kv}+2v)\right)\le e^{-v}. \end{align*} Apply this with $v=u+\log N$ and take a union bound over the $N$ supports. For every $u>0$, \begin{align*} \mathbb P_\beta\left(Z>\sigma^2(2k+2\sqrt{2k(u+\log N)}+2(u+\log N))\right)\le e^{-u}. \end{align*} Using $2\sqrt{ab}\le a+b$ with $a=2k$ and $b=u+\log N$, there is a universal constant $c_6>0$ such that \begin{align*} \mathbb P_\beta\left(Z>c_6\sigma^2(k+\log N+u)\right)\le e^{-u}. \end{align*} Set $t_0:=c_6\sigma^2(k+\log N)$. The tail identity for nonnegative random variables gives \begin{align*} \mathbb E_\beta[Z] \le t_0+\int_{t_0}^\infty \mathbb P_\beta(Z>t)\,d\mathcal L^1(t). \end{align*} With $t=t_0+c_6\sigma^2u$, the measure transforms as $d\mathcal L^1(t)=c_6\sigma^2\,d\mathcal L^1(u)$ and the domain $[t_0,\infty)$ becomes $[0,\infty)$. Hence \begin{align*} \mathbb E_\beta[Z] \le c_6\sigma^2(k+\log N)+c_6\sigma^2\int_0^\infty e^{-u}\,d\mathcal L^1(u) = c_6\sigma^2(k+\log N+1). \end{align*} Since $\log N\le c_4k\log(ed/k)$ and $k\ge1$, enlarging constants gives \begin{align*} \mathbb E_\beta[Z] \le c_5\sigma^2k\log(ed/k) \end{align*} for a universal constant $c_5>0$. Combining this with the deterministic inequality \begin{align*} |X(\hat\beta_{\mathrm{cls}}-\beta)|^2\le4Z \end{align*} gives \begin{align*} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta_{\mathrm{cls}}-\beta)|^2\right] \le 4c_5\sigma^2\frac{k\log(ed/k)}{n}. \end{align*} Taking the supremum over $\beta\in\Theta_k$ and comparing the minimax risk to this particular estimator proves the upper bound with $C:=4c_5$.[/guided]

[step:Combine the two bounds]The preceding lower-bound argument gives \begin{align*} \inf_{\hat\beta}\sup_{\beta\in\Theta_k} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta-\beta)|^2\right] \ge c\sigma^2\frac{k\log(d/k)}{n}, \end{align*} with $c>0$ depending only on $a_0$ and $A_0$. The constrained least-squares argument gives \begin{align*} \inf_{\hat\beta}\sup_{\beta\in\Theta_k} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta-\beta)|^2\right] \le C\sigma^2\frac{k\log(ed/k)}{n}, \end{align*} with a universal constant $C>0$, hence in particular with $C$ depending only on $a_0$ and $A_0$. This proves the claimed minimax sparse prediction rate.[/step]

[guided]The lower-bound steps proved that every estimator has prediction risk at least \begin{align*} c\sigma^2\frac{k\log(d/k)}{n}, \end{align*} where \begin{align*} c=\frac{c_1c_2c_3a_0}{8A_0}>0. \end{align*} Thus $c$ depends only on $a_0$ and $A_0$, because $c_1,c_2,c_3$ are universal constants. The upper-bound steps constructed the constrained least-squares estimator $\hat\beta_{\mathrm{cls}}$ and proved that, for every $\beta\in\Theta_k$, \begin{align*} \mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta_{\mathrm{cls}}-\beta)|^2\right] \le C\sigma^2\frac{k\log(ed/k)}{n} \end{align*} with $C:=4c_5$, a universal constant. Since the minimax risk is the infimum over all estimators, it is no larger than the risk of this particular estimator. Combining these two inequalities gives exactly \begin{align*} c\sigma^2\frac{k\log(d/k)}{n} \le \inf_{\hat\beta}\sup_{\beta\in\Theta_k}\mathbb E_\beta\left[\frac{1}{n}|X(\hat\beta-\beta)|^2\right] \le C\sigma^2\frac{k\log(ed/k)}{n}. \end{align*} This is the claimed minimax sparse prediction rate.[/guided]