Minimax-Optimal Rates For Sparse Additive Models Over Kernel Classes Via Convex Programming

By Garvesh Raskutti, Martin J. Wainwright, Bin Yu. 2010

302 citations recorded by the source corpus.

Sparse additive models are families of d-variate functions with the additive decomposition f* = Σj∈S fj*, where S is an unknown subset of cardinality s < d. In this paper, we consider the case where each univariate component function fj* lies in a reproducing kernel Hilbert space (RKHS), and analyze a method for estimating the unknown function f* based on kernels combined with l1-type convex regularization. Working within a high-dimensional framework that allows both the dimension d and sparsity s to increase with n, we derive convergence rates in the L2(P) and L2(Pn) norms over the class Fd,s,H of sparse additive models with each univariate function fj* in the unit ball of a univariate RKHS with bounded kernel function. We complement our upper bounds by deriving minimax lower bounds on the L2(P) error, thereby showing the optimality of our method. Thus, we obtain optimal minimax rates for many interesting classes of sparse additive models, including polynomials, splines, and Sobolev classes. We also show that if, in contrast to our univariate conditions, the d-variate function class is assumed to be globally bounded, then much faster estimation rates are possible for any sparsity s = Ω(√n), showing that global boundedness is a significant restriction in the high-dimensional setting.

Subfields: Computational Mechanics, Numerical Analysis, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Generalized Sparse Additive Models (2019, background): “General-purpose convex solvers have also been suggested [Koltchinskii and Yuan, 2010, Raskutti et al., 2012, Yuan and Zhou, 2015] as an alternative for solving problem (2), but they roughly scale as O ( n 3 p 3 ) and are hence ineﬃcient.”
Additive models with trend filtering (2017, background): “Sup norm boundedness is a pretty common assumption in the analysis of additive models (with growing dimension), though some authors, such as Raskutti et al. (2012), avoid it.”
Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, background): “This lower bound follows from Theorem 2(a) of Raskutti et al. (2012) with s = d = 1.”
Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions (2011, methodology): “ F ≥ δ 2, for all j 6= k, and (71a) |||Γj|||2 F ≤ 64δ 2, (71b) and such that each Γj has at most s non-zero columns. This claim follows by suitably adapting Lemma 5(b) in the paper by Raskutti et al. [24] on minimax rates for kernel classes. In particular, we view column j of a matrix Γ as deﬁning a”
Learning Sparse Additive Models with Interactions in High Dimensions (2016, background): “There exist several for learning these models; we refer to [9, 10, 11, 12, 13] and references therein.”
Divide and Conquer Kernel Ridge Regression (2013, unknown): “This lower bound follows from Theorem 2(a) of Raskutti et al. (2012) with s = d = 1.”
Doubly penalized estimation in additive regression with high-dimensional data (2019, methodology): “Previously, the same rate was obtained for high-dimensional additive regression only with reproducing kernel Hilbert spaces (including the Sobolev space Wm 2 ) by Koltchinskii & Yuan (2010) and Raskutti et al. (2012), but under more restrictive conditions. They studied hybrid penalized estimation pr”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, methodology): “This function arises via analysis of the local Rademacher complexity of the kernel class (e.g., [ 6, 17, 22, 25]).”
A General Framework for Robust Testing and Confidence Regions in High-Dimensional Quantile Regression (2014, methodology): “As a by-product, we establish the rate of convergence of the L1-penalized CQR that is optimal for estimation in s-sparse linear regression (Raskutti et al., 2012), and a bound on the number of selected components ŝ.”
STANDARDIZATION AND THE GROUP LASSO PENALTY (2012, methodology): “The √ pl factor is important to make sure groups with larger column spaces play on even ground with smaller groups — though future work does something similar using kernel norms [Yu et al., 2010] and smoothness penalties [Meier et al., 2009]”
On Bayes Risk Lower Bounds (2014, background): “, 2011), classification (Yang, 1999), additive models over kernel classes (Raskutti et al., 2012), and crowdsourcing (Zhang et al.”
Tight conditions for consistency of variable selection in the context of high dimensionality (2011, background): “To complete the picture, let us mention that estimation and hypotheses testing problems for high-dimensional nonparametric regression under sparse additive modeling were recently addressed in [25, 33, 19].”
Cross-validation for selecting a model selection procedure (2015, background): “Raskutti et al. (2012) construct an estimator based on model selection that achieves the rate ( d n (1 + log(p n /d n ))/n + d n n − 2α 2α+1 ) ∧ 1, which is also shown to be minimax rate optimal.”
High-Dimensional Feature Selection by Feature-Wise Kernelized Lasso (2012, methodology): “…(QPFS) (Rodriguez-Lujan et al. , 2010), kernel target alignment (KTA) (Shawe-Taylor and Kandola, 2002; Cortes et al. , 2012), Hilbert-Schmidt Feature Selection (HSFS) (Masaeli et al. , 2010), and sparse additive models (SpAM) (Ravikumar et al. , 2009; Liu et al. , 2009; Raskutti et al. , 2012).”
Group Lasso for high dimensional sparse quantile regression models (2011, methodology): “The application of the group Lasso (and its variants) to the estimation of non-parametric additive models has recently gained a lot of attention (Ravikumar et al., 2009; Meier et al., 2009; Huang et al., 2010; Koltchinskii and Yuan, 2010; Raskutti et al., 2010).”
Local Inference in Additive Models with Decorrelated Local Linear Estimator (2019, background): “Additionally, the proposed DLL estimator is also compatible with the estimators proposed in [23,26,30,31,37].”