Minimax-Optimal Sparse Additive Models Over Kernel Classes via Convex Programming

⚠️ Curated Limitations & Negative Results

• Independence Assumption Across Covariates and Additive Univariate Decomposition: As noted in Section 2.2 (p. 5) and Section 5 (p. 23), the L^2(P) norm decoupling ||f||_{L^2(P)}^2 = sum_{j=1}^d ||f_j||_{L^2(Q)}^2 and the fourth-moment expansion in Lemma 3 (Appendix D, p. 30) rely on the product-measure assumption P = Q^d (independent covariates x_1, ..., x_d) and purely univariate additive components without higher-order interaction hierarchies.
• Univariate Sup-Norm Boundedness Condition: As stated in Section 3.2 (p. 8, Equation 15), Theorem 1 requires each function in the univariate RKHS unit ball B_H(1) to satisfy ||f_j||_infty <= c ||f_j||_H (which holds whenever the univariate kernel K is uniformly bounded on X x X), though it avoids any global sup-norm bound on the s-sparse sum f = sum_{j in S} f_j.
• Primary-Source Typographical Notes in Raskutti, Wainwright, & Yu (2012, arXiv:1008.3654v2): Verified five self-correcting typographical details during full-text inspection: (1) Section 2.1 (p. 4, Equation 3) prints Mercer's eigen-expansion as K(x, x') = sum_{k=1}^infty mu_k phi_k(x) phi_l(x') with subscript l instead of k on the second eigenfunction; (2) Section 4.1.5 (p. 17, Equation 40a) writes the remainder term +(1/32) s rho_n in the definition of G(lambda_n, rho_n) whereas Lemma 2 (p. 15, Equation 33) has +(1/2) s gamma_n^2 (which is upper bounded by (1/32) s rho_n when rho_n = 16 gamma_n^2, and contributes +(3/32) s rho_n when multiplied by 3 on p. 15); (3) Appendix C (p. 28, Proof of Lemma 2, first display) writes +y_bar_n instead of -y_bar_n inside L_tilde(Delta) := (1/(2n)) sum_{i=1}^n (w_i + mu + y_bar_n - Delta(x_i))^2 + ...; (4) Appendix D (p. 29, Proof of Lemma 3) writes 'since ||f||_n = ||g||_n = delta_tilde_n' on the fourth line from the bottom (where f, g in G' satisfy ||f||_2 = ||g||_2 = delta_tilde_n and ||f||_n <= ||f||_2 by Equation 40c) and omits the square on (g^k(x_i))^2 in the bottom display of p. 29 (restored as g^2(x_i) in Equations 68-69 on p. 30); and (5) Section 3.5 (p. 13, Remarks) writes f_B(s, n) = o(1) for K_B(s, n) = o(1), p. 23 Acknowledgements retains two '(INSERT NUMBER)' grant placeholders, and Reference [29] (p. 38) lists arXiv:0910.2042 (the identifier of Ref. [30]) instead of arXiv:1008.3654.
• All 38 pages of Raskutti, Wainwright, & Yu (2012, JMLR 13:389-427, arXiv:1008.3654v2) were read. Constructed numerical checks in research/discovery/minimax-optimal-sparse-additive-models-kernel-classes-boundaries.py verify (1) the critical univariate rate nu_n^2 = m / (1600 n) for rank-m kernels (Corollary 1), the Sobolev scaling nu_n^2 * n^{2 alpha / (2 alpha + 1)} -> const for alpha = 2 (Corollary 2), and the strict improvement of the Raskutti-Wainwright-Yu rate (0.065451) over the Meier et al. (2009) coupled-penalty rate (0.126886); (2) exact representer-theorem SOCP norm equivalence (Equations 10-11), the Lemma 2 decomposability cone inequality (Equations 33 & 40a), and the Lemma 3 fourth-moment bound E[g^4(x)] = 3.739648 <= 4 delta_tilde_n^2 + 6 delta_tilde_n^4 = 5.0176 <= 10 delta_tilde_n^2 = 6.4 despite ||g||_infty = 2s = 50.0; and (3) Lemma 10 Fourier l_1 bound and the Theorem 3 / Corollary 3 global boundedness phase transition at alpha = 2, s = n^{4/5} (unbounded rate = 1.0 vs. globally bounded rate 0.095971 at n = 10^5).