Minimax Estimation Rates for High-Dimensional Linear Regression Over l_q-Balls

⚠️ Curated Limitations & Negative Results

• Computational Intractability of Non-Convex l_q-Ball Constrained Least Squares for q in [0, 1): As emphasized in Section 2.2 (p. 6) and Section 3.3 (pp. 11-15), the minimax upper-bound estimator beta_hat in argmin_{beta in B_q(R_q)} ||Y - X beta||_2^2 is a non-convex optimization problem for q in [0, 1) (requiring exhaustive subset search over (d choose s) supports when q = 0), whereas polynomial-time convex relaxations such as the Lasso and Dantzig selector require the strictly stronger l_1 Restricted Eigenvalue condition Assumption 3(gamma; s) to achieve the same rates.
• Sub-Linear Sparsity Regime Requirement s = o(d) for Matching Hard-Sparsity Bounds: As noted in Remark (a) after Theorem 2 (p. 6) and Section 2.3 (p. 7), for q = 0 the lower bounds in Theorems 1(b) and 3(b) scale with s log(d/s)/n under s <= d/4, whereas the upper bounds in Theorems 2(b) and 4(b) can be stated with s log(d - s)/n or s log(d/s)/n, matching up to constant factors across the sub-linear sparsity regime s = o(d).
• Primary-Source Typographical Notes in Raskutti, Wainwright, & Yu (2011, arXiv:0910.2042v1): Verified five self-correcting typographical details during full-text inspection: (1) Section 1.1 (p. 3, Equation 5) prints |beta_hat_j - beta*_j|_p^p with an extra subscript p on the scalar absolute value; (2) Section 3.1 (p. 9, Corollary 1, Equation 22) omits the radius factor R_q in the Gaussian sequence model display (absorbing R_q into the constants c'_q, c_q); (3) Section 3.2 (p. 9, Equation 23) defines rho(Sigma) := max_j Sigma_{jj} (the maximum diagonal variance) and prints max_j ||X_j||_2 / sqrt(n) <= rho(Sigma) (1 + sqrt(32 log d / n)) without a square root on rho(Sigma), whereas Equation (25) and Appendix F (p. 34) use the dimensionally consistent sqrt(rho(Sigma)); (4) Section 4.2.1 (p. 18, Proof of Theorem 1b) writes (delta_n / sqrt(s)) H_tilde right after defining sqrt(2/s) delta_n H_tilde, and Section 4.2.2 (p. 20, Proof of Theorem 3b) writes (delta_n^2 / (2s)) H_tilde and includes an extra 1/n in the denominator (s/(2n)) log((d - s)/(s/2)) before canceling n in the final line delta_n^2 = (kappa_l^2 / (64 kappa_u^2)) sigma^2 (s/n) log((d - s)/(s/2)); and (5) Section 4.3.1 (p. 21, Proof of Theorem 2a) substitutes tau = (2 sigma kappa_c / kappa_l^2) sqrt(3 log d / n) into 4 max{b^2, |c|} = 8 R_q tau^{2-q}, where tau^{2-q} carries factor 12^{1-q/2} (giving 8 * 12^{1-q/2} R_q), whereas p. 21 and Equation (12) print prefactor 24 = 8 * 3 (omitting 4^{1-q/2} from 2^2 inside tau^2), and at the bottom of p. 21 (Proof of Theorem 2b) the display omits the factor 2 before squaring to 6.
• All 38 pages of Raskutti, Wainwright, & Yu (2011, arXiv:0910.2042v1, IEEE Trans. Inf. Theory 57(10):6976-6994) were read. Constructed numerical checks in research/discovery/minimax-rates-high-dimensional-linear-regression-lq-balls-boundaries.py verify (1) the explicit 2x3 design matrix X = [[1, -2, -1], [2, -3, -3]] in Section 3.3.1 (p. 12, Equation 29) where ker(X) = span{[1, 1/3, 1/3]^T} satisfies B_0(2) cap ker(X) = {0} (so l_0-constrained least squares recovers beta* = [1, 0, 0]^T) yet Delta = [1, 1/3, 1/3]^T in Gamma(1, 1) cap ker(X) violates RE(1; 1) and causes noiseless Basis Pursuit to recover beta_hat = [0, -1/3, -1/3]^T with ||beta_hat||_1 = 2/3 < 1 = ||beta*||_1; (2) Lemma 1 nullspace diameter bound diam_2(N_q(X)) <= f_l / kappa_l, Lemma 2 l_p/l_2 interpolation over B_q(2 R_q), and Lemma 7 quadratic root-bounding in Theorem 2(a) (x_root^2 = 3.348872 <= 4 max{b^2, c} = 5.116621); and (3) Lemma 5 greedy ternary Hamming packing on H(s) for d = 10, s = 4 (yielding 181 packing points >= ((d-s)/(s/2))^{s/2} = 9 with pairwise distances in [delta_n^2, 8 delta_n^2]) and the exact role reversal of design eigenvalue sensitivity between l_2-parameter and l_2-prediction risks.