zbMATH — the first resource for mathematics

Minimax-optimal rates for sparse additive models over kernel classes via convex programming. (English) Zbl 1283.62071
Summary: Sparse additive models are families of \(d\)-variate functions with the additive decomposition \(f^{*} = \sum _{j \in S} f^{*}_{j}\), where \(S\) is an unknown subset of cardinality \(s << d\). In this paper, we consider the case where each univariate component function \(f^{*}_{j}\) lies in a reproducing kernel Hilbert space (RKHS), and analyze a method for estimating the unknown function \(f^{*}\) based on kernels combined with \(\ell_{1}\)-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 \(L^{2}(P)\) and \(L^{2}(\mathbb P_{n})\) norms over the class \(F_{d,s,H}\) of sparse additive models with each univariate function \(f^{*}_{j}\) in the unit ball of a univariate RKHS with bounded kernel function. We complement our upper bounds by deriving minimax lower bounds on the \(L^{2}(\mathbb 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 = \Omega (\sqrt n)\), showing that global boundedness is a significant restriction in the high-dimensional setting.

62G05 Nonparametric estimation
90C25 Convex programming
62G08 Nonparametric regression and quantile regression
62J07 Ridge regression; shrinkage estimators (Lasso)
90C47 Minimax problems in mathematical programming
Full Text: Link arXiv