Minimax-optimal rates for sparse additive models over kernel classes via convex programming

Details Minimax-optimal rates for sparse additive models over kernel classes via convex programming Minimax-optimal rates for sparse additive models over kernel classes via convex programming

2010-08-21

arxiv.org/abs/1008.3654v2

Mathematics

Statistics Theory

Lower bounds presented in part in Proceedings of the NIPS Conference, December 2009 Revised version December 2011: new Theorem

Scientific paper

Sparse additive models are families of $d$-variate functions that have the additive decomposition $f^* = \sum_{j \in S} f^*_j$, where $S$ is an unknown subset of cardinality $s \ll 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 (upper bounds) in the $L^2(\mathbb{P})$ and $L^2(\mathbb{P}_n)$ norms over the class $\MyBigClass$ 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 multivariate 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.

Affiliated with

Also associated with

No associations

Rating

Minimax-optimal rates for sparse additive models over kernel classes via convex programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimax-optimal rates for sparse additive models over kernel classes via convex programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimax-optimal rates for sparse additive models over kernel classes via convex programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-189060