Source-linked AI summary
Minimax-optimal rates for sparse additive models over kernel classes via convex programming
Garvesh Raskutti, Martin J. Wainwright, Bin Yu
TL;DR
The paper addresses estimation of sparse additive regression functions whose univariate components lie in RKHSs, a setting that extends sparse linear models while avoiding general nonparametric dimensionality costs. It analyzes an ℓ1-regularized kernel estimator, derives matching minimax rates for several RKHS classes, and shows that global boundedness can yield faster rates when s=Ω(√n).
Problem
The paper studies high-dimensional sparse additive regression with unknown support and univariate RKHS components.
Method
It analyzes least-squares estimation with ℓ1 penalties based on empirical component norms and RKHS norms, reducible to a finite-dimensional convex program.
Results
Achievable L2(P) rates match algorithm-independent minimax lower bounds for finite-rank and Sobolev-type kernels up to constants when s=o(d).
Takeaways & Limitations
The analysis establishes minimax-optimal rates for sparse additive models while requiring boundedness only for individual univariate functions.
Takeaways & Limitations
The analysis assumes independent covariates and does not cover correlated designs or hierarchical sums of multivariate subsets.
Abstract
from arXiv · showhide
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 = Ω(\sqrt{n})$, showing that global boundedness is a significant restriction in the high-dimensional setting.
1 Introduction
The paper studies sparse additive nonparametric regression with RKHS components in high dimensions, proposing an ℓ1-regularized estimator and characterizing its achievable and minimax rates. It also shows that global boundedness can substantially alter rates when sparsity is sufficiently large.
- Problem setting: Sparse additive models combine an unknown s-variable subset with univariate component functions, extending sparse linear models beyond parametric relationships.The model reduces to sparse linear regression when each component is constrained to be linear.
- Method: The proposed polynomial-time estimator uses least-squares loss with ℓ1/L2(P_n) and ℓ1/∥·∥H penalties.These penalties separately reflect empirical component size and RKHS complexity.
- Main rates: Theorem 1 gives L2(P) and L2(P_n) error upper bounds without requiring global boundedness of the multivariate sparse-model class.The analysis assumes bounded univariate functions and uses M-estimation and kernel empirical-process techniques.
- Main rates: Theorem 2 supplies algorithm-independent L2(P) minimax lower bounds that match achievable rates for finite-rank and Sobolev-type classes up to constants when s=o(d).The lower bounds are expressed through metric entropy of the underlying univariate classes.
2 Background and problem set-up
The paper formulates sparse additive regression over univariate RKHSs under a product design, defines the relevant population and empirical norms, and models observations as additive signal plus intercept and Gaussian noise.
- Reproducing kernel Hilbert spaces: An RKHS is a complete function space with a kernel satisfying the reproducing relation f(x)=⟨f,K(·,x)⟩H.Its kernel admits an eigen-expansion whose eigenvalue decay determines univariate estimation rates.
- Function spaces: Each coordinate j has a univariate RKHS Hj, with component functions subject to a centering condition under Q.The centering condition is compatible with an observation model allowing a nonzero mean μ.
- Sparse additive models: For a support set S, H(S) contains sums of univariate functions on coordinates in S and uses a norm assembled from the component Hilbert norms.The overall class is indexed by ambient dimension d, sparsity s, and the collection of Hilbert spaces.
- Observation model: The design distribution is the product measure P=Q^d, and observations follow yi=μ+f*(xi)+wi.The covariates are sampled independently from P and the noise variables are standard normal.
- Error criteria: Estimation error is evaluated in both population L2(P) and empirical L2(P_n) norms.The population norm decomposes additively under the product structure, whereas the empirical norm does not exactly decouple across dimensions.
3 Main results and their consequences
The paper analyzes a polynomial-time convex estimator for sparse additive RKHS models, establishes upper and minimax lower bounds, and studies how global boundedness changes the rates.
- Estimator: The estimator combines least-squares loss with ℓ1/L2(P_n) and ℓ1/∥·∥H penalties for sparsity and smoothness.The infinite-dimensional problem reduces through the representer theorem to a convex program in R^n × R^d, specifically a second-order cone program.
- Upper bounds: Theorem 1 gives L2(P) and L2(P_n) upper bounds whose rate combines subset selection and s-dimensional function-estimation terms.The subset-selection term depends on d, while the function-estimation term depends on the univariate Hilbert space rather than ambient dimension.
- Minimax lower bounds: For finite-rank kernels and Sobolev-type classes, the minimax lower bounds match the achievable rates up to constants when s = o(d).The lower bounds are algorithm-independent and are specified through the metric entropy of the underlying univariate function classes.
- Sobolev classes: Sobolev RKHS results cover eigenvalue decay k^-2α with α > 1/2 and bounded eigenfunctions, yielding sharper rates for this class.Theorem 3 states probabilistic upper bounds under these Sobolev conditions.
- Global boundedness: Global boundedness can produce strictly faster minimax rates than the unrestricted sparse-additive class when KB(s,n) tends to zero.For example, with s = Ω(√n), the effective dimension is reduced and, for Sobolev smoothness α = 2 with s = O(n^4/5), the unrestricted rate can remain bounded away from zero while the bounded-class rate tends to zero.
4 Proofs
The proofs combine sparse-regression techniques, empirical-process bounds, decomposability, and a non-parametric restricted-strong-convexity argument to control estimation error without global boundedness.
- Proof strategy: Theorem 1 adapts sparse linear-regression error analysis to non-parametric kernel classes using empirical-process concentration.The proof requires more advanced concentration tools than the parametric setting.
- Complexity control: A Gaussian-complexity bound controls component errors through Hilbert and empirical norms, with the subset-selection term s log d arising from maximizing over d components.The maximum over all d coordinates produces the subset-selection contribution.
- Sparsity control: Decomposability confines the error to a cone-shaped set and reduces the analysis to the true support S.This is how the sparsity assumption enters the proof.
- Population-error control: A new argument combines Sudakov minoration with one-sided concentration to control the population norm despite the unbounded multivariate function class.The resulting lemma provides a non-parametric analogue of restricted strong convexity.
- Case analysis: The proof handles three cases according to the relative sizes of population, empirical, and threshold errors, completing the bound on the estimator.Each case reduces the relevant norm through quadratic inequalities or the restricted-convexity control.
5 Discussion
The paper characterizes minimax-optimal estimation rates for sparse additive RKHS models and emphasizes that global boundedness can substantially change the high-dimensional problem.
- Main results: Theorems 1 and 2 characterize minimax-optimal L2(P) rates for sparse additive models over finite-rank and polynomial-entropy kernel classes.The upper and lower bounds provide the characterization for bounded univariate functions.
- Methods: The estimator regularizes least-squares loss with ℓ1-based Hilbert and empirical norms, while lower bounds use approximation-theoretic and information-theoretic techniques.The two norms respectively encode component smoothness and empirical magnitude.
- Assumptions: The analysis assumes boundedness for each univariate function but not for the resulting multivariate sparse additive class.The multivariate sums may therefore grow with sparsity.
- Global boundedness: Under global boundedness, much faster rates are possible for Sobolev classes when s = Ω(√n), and those rates are not minimax optimal for the unbounded-univariate model.The comparison shows that global boundedness imposes a stringent high-dimensional restriction.
- Extensions: The analysis assumes independent covariates and leaves correlated covariates and hierarchical additive classes for future research.The authors anticipate that strong dependence may change optimal rates.
A A general result on equivalence of L2(P) and L2(Pn) norms
This appendix establishes high-probability equivalence between empirical and population L2 norms over uniformly bounded, star-shaped function classes.
- Conditions: The general result requires the function class to be uniformly bounded and star-shaped.These conditions are stated as bounded sup norm and closure under scaling by λ ∈ [0, 1].
- Scope: The result applies to each univariate Hilbert ball but not to the full multivariate sparse-additive class, which is not uniformly bounded.The coordinate-level condition is therefore weaker in scope than the full model class.
- Critical radius: The critical radius ϵn is defined through the population Rademacher complexity and determines the range t ≥ ϵn where the event is controlled.Star-shapedness ensures the defining complexity ratio is non-increasing.
- Norm comparison: For functions with sufficiently large population norm, the empirical norm is bounded by a multiplicative approximation with high probability.The result controls the empirical norm for g with ∥g∥2 ≥ t and for larger threshold levels.
- Probability guarantee: Both norm-comparison inequalities hold with probability at least 1 − c1 exp(−c2nt^2).The confidence improves exponentially in nt^2.
B Proof of Lemma 1
The proof of Lemma 1 bounds local Gaussian complexities for RKHS components using eigenvalue-based complexity rates and concentration arguments.
- Complexity definitions: The appendix introduces empirical and population Gaussian complexities for univariate RKHS classes.These complexities quantify stochastic fluctuations of kernel-class functions.
- Proof technique: The proof uses peeling, weighting, and concentration of measure for Lipschitz functions of Gaussian variables.These tools provide uniform control across complexity scales.
- Eigenvalue control: Kernel eigenvalues determine local complexity bounds through the spectrum of the univariate Hilbert space.The analysis assumes a non-negative ordered eigenvalue sequence.
- Related complexities: The same eigenvalue-based bounds apply to local Rademacher complexities for reproducing kernel Hilbert spaces.Thus the argument connects Gaussian and Rademacher complexity controls.
- Critical rates: The coordinate-specific critical rate is defined as the smallest positive solution of a local Gaussian-complexity inequality.This rate is linked to the population Gaussian complexity used in the paper’s univariate rate νn.
B.1 Some auxiliary results
The section establishes auxiliary concentration and complexity bounds used to control RKHS components uniformly across coordinates. It then applies peeling and union-bound arguments to obtain the required componentwise bound.
- Auxiliary lemmas: Lemmas 8 and 9 provide auxiliary concentration results for the empirical Gaussian-complexity quantities used in Lemma 1.Lemma 8 derives tail bounds from Lipschitz concentration, while Lemma 9 relates empirical and population norms under conditioning.
- Auxiliary lemmas: The bounds hold uniformly over j = 1, 2, . . . , d through a union bound and the choice of γn.For each fixed coordinate, the event fails with exponentially small probability; uniformity follows by aggregating these events.
- Proof of the componentwise bound: The proof of the componentwise inequality splits according to whether the empirical norm is at most γn or exceeds γn.The first case uses the critical-radius definition directly; the second studies rj = ∥fj∥n/∥fj∥H and uses peeling.
- Proof of the componentwise bound: Peeling partitions possible values of rj into finitely many scales, with M = 2 log2(1/γn) ensuring 2Mγn ≥ 1.The resulting scale-wise events are controlled by a union bound and the preceding tail bound.
C Proof of Lemma 2
The proof uses the M-estimator’s basic inequality and separates contributions from inactive and active coordinates. Norm inequalities and the selected regularization parameters then yield the stated bound.
- Basic inequality: The estimation error b∆ = bf − f ∗ minimizes the empirical objective, so eL(b∆) ≤ eL(0) supplies the starting inequality.The proof subsequently controls the resulting terms separately.
- Coordinate decomposition: For inactive coordinates j ∈ Sc, norm inequalities bound their contributions using the componentwise control from the preceding lemma.The argument combines the inequalities for empirical and RKHS norms with bound (66).
- Coordinate decomposition: For active coordinates j ∈ S, the triangle inequality controls the terms involving f ∗j and b∆j.These active-coordinate bounds are combined with the inactive-coordinate contribution.
- Conclusion: Rearranging the combined inequality with the chosen values of λn and ρn proves claim (33).The final step combines the preceding bound (67) with the regularization choices.
D Proof of Lemma 3
The proof establishes a uniform deviation bound over a localized function class using rescaling, proper coverings, concentration, and Gaussian complexity control. The argument concludes by combining these ingredients with Sudakov minoration.
- Localization: Star-shapedness reduces control over all nonzero functions in G(λn, ρn) to functions rescaled to L2 norm ˜δn.This reduction transfers the event B′(λn, ρn) to B(λn, ρn).
- Covering argument: A minimal ˜δn/8-proper covering of G′ in the L2(Pn)-norm reduces uniform control to finitely many covering elements.Proper covering numbers are related to ordinary covering numbers through Npr(ε; G, ρ) ≤ N(ε; G, ρ) ≤ Npr(ε/2; G, ρ).
- Concentration: Concentration controls the squared empirical norms of covering elements using a one-sided tail bound and fourth-moment control.The proof uses nonnegativity, variance bounded by the fourth moment, and the RKHS sup-norm bound.
- Entropy control: Sudakov minoration converts Gaussian-process control into an upper bound on the covering entropy of G′.The Gaussian process is constructed so that increments have variance equal to the squared empirical norm distance.
- Conclusion: Summing coordinatewise Gaussian-complexity bounds and choosing B sufficiently large completes the proof of Lemma 3.The argument uses the definition of G′, RKHS norm bounds, the regularization choice ρn ≥ γn^2, and the selected critical radius.
E Proof of Lemma 4
The proof constructs separated collections of sparse additive functions from coordinatewise RKHS packings. Hamming separation of coefficient vectors yields function separation, establishing the packing lower bounds.
- Combinatorial separation: Combinatorial counting constructs a large separated subset by choosing overlapping coordinates and augmenting it iteratively.The argument bounds the number of nearby vectors and repeatedly adds vectors outside the existing neighborhoods.
- Packing construction: Coordinatewise packings of the univariate RKHS unit ball index a collection of sparse additive functions contained in F.Each coefficient vector has at most s nonzero coordinates, so the associated additive function belongs to the sparse class.
- Packing construction: Hamming separation between coefficient vectors transfers to L2 separation between the corresponding additive functions.The construction seeks a subset whose pairwise Hamming distance is at least s/2.
- Combinatorial separation: For s ≤ d/4, the construction yields the stated lower bound for part (a) of Lemma 4.The conclusion follows from the combinatorial lower bound on the size of the separated set.
- Part (b): Part (b) modifies the construction by counting vectors according to their number of nonzero components and using log N = Ω(m).The resulting lower bound is combined with the Hamming separation and the inequality ∥fj∥2 ≤ ∥fj∥H.
- Part (b): Rescaling the constructed functions produces the final class of separated functions used in the lower-bound argument.The rescaled family is indexed by the constructed set of coefficient vectors.
F Results for proof of Theorem 3
This section parameterizes sparse additive RKHS functions using basis coefficients and eigenvalues, then establishes bounds for truncated classes. The proof uses coordinate-wise structure, norm inequalities, and uniform boundedness.
- Function-class representation: The class H(S, B) is represented by coefficient arrays indexed by active coordinates and basis functions, together with univariate RKHS eigenvalues.The truncated class is introduced by restricting the basis expansion to the first M terms.
- Coordinate-wise decomposition: The proof assumes S = {1, 2, ..., s} without loss of generality and decomposes functions into s coordinate-specific components.Each component acts on a different coordinate, enabling coordinate-wise control of the function norm.
- Coordinate-wise decomposition: Bounds are obtained by summing coordinate-wise estimates over all active coordinates.The resulting aggregation is stated for every M ≥1.
- Assumptions: The final bound relies on the uniform boundedness condition.This condition is invoked explicitly in the last step of the argument.
F.1 Proof of Lemma 5
The proof of Lemma 5 controls empirical-process quantities for sparse RKHS classes by combining Lipschitz concentration, Gaussian-complexity bounds, bounded-basis estimates, and a peeling argument. Truncation and eigenvalue decay determine the resulting rate.
- Concentration: The Gaussian process is treated as a Lipschitz function of the standard Gaussian vector, enabling concentration control.Its Lipschitz parameter is bounded in terms of t and n.
- Expectation bounds: Lemma 11 provides an upper bound on the relevant expectations for H(S, 2B).The lemma is the main expectation-control result used in the proof of Lemma 5.
- Class representation: Functions in H(S, 2B) have support at most 2s and are represented through coordinate-indexed basis functions Φj,k(x) = φj,k(xj).This representation maps the active coordinates into arrays of basis-function values.
- Complexity decomposition: The proof controls one term using Hölder’s inequality and bounded basis functions, yielding sub-Gaussian maxima over 2s × M terms.The same bound applies to both relevant Gaussian expectations.
- Complexity decomposition: The second term is controlled by the Gaussian complexity of 2s truncated univariate Hilbert spaces.Cauchy–Schwarz and the corresponding bound are used for both Gaussian expectations.
- Rate derivation: Substituting the component bounds and using eigenvalue decay µk ≃ k−2α yields the stated rate after selecting M.The argument then notes that the same reasoning applies to Rademacher complexity because the noise variables are sub-Gaussian.
- Proof completion: A peeling argument over the radius completes the proof because every g ∈ H(S, 2B) satisfies ∥g∥n ≤ 2B.The peeling step is analogous to the proof of Lemma 1.