Source-linked AI summary
Sparse Additive Models
Pradeep Ravikumar, John Lafferty, Han Liu, Larry Wasserman
TL;DR
High-dimensional nonparametric models need flexibility without retaining every covariate, while ordinary additive models are limited when p is large relative to n. SpAM combines additive smoothing with sparsity through a convex formulation and backfitting algorithms. The paper reports asymptotic sparsity-pattern recovery and risk consistency, with an example where seven codewords achieve RSS 0.0206 versus eight and RSS 0.0561 for a sparse linear model.
Problem
Additive models are interpretable and easier to fit than fully multivariate nonparametric models, but their usefulness is limited when p is large relative to n.
Method
SpAM combines sparse additive modeling with convex optimization, backfitting, functional soft thresholding, and smoothing procedures that can be chosen independently.
Results
The paper reports asymptotic recovery of the correct sparsity pattern and persistence, while an example obtains RSS 0.0206 with seven codewords versus RSS 0.0561 with eight for a sparse linear model.
Takeaways & Limitations
SpAM provides a sparse nonparametric framework for high-dimensional regression and classification, with an algorithm that can use arbitrary nonparametric smoothers.
Takeaways & Limitations
The theoretical analyses use truncated orthogonal-basis smoothing, and the experiments and theory use plug-in bandwidths and truncation dimensions rather than automatic adaptive selection.
Abstract
from arXiv · showhide
We present a new class of methods for high-dimensional nonparametric regression and classification called sparse additive models (SpAM). Our methods combine ideas from sparse linear modeling and additive nonparametric regression. We derive an algorithm for fitting the models that is practical and effective even when the number of covariates is larger than the sample size. SpAM is closely related to the COSSO model of Lin and Zhang (2006), but decouples smoothing and sparsity, enabling the use of arbitrary nonparametric smoothers. An analysis of the theoretical properties of SpAM is given. We also study a greedy estimator that is a nonparametric version of forward stepwise regression. Empirical results on synthetic and real data are presented, showing that SpAM can be effective in fitting sparse nonparametric models in high dimensional data.
1. Introduction.
High-dimensional nonparametric regression is difficult, while additive models are interpretable and computationally manageable but lose effectiveness as variables approach or exceed sample size. SpAM combines additive modeling with sparsity and provides optimization, algorithms, and theory for this setting.
- Motivation: High-dimensional linear regression becomes challenging when p > n, motivating sparse methods such as the lasso.The lasso uses an ℓ1 penalty to encourage many estimated coefficients to be zero.
- Motivation: General nonparametric regression relaxes linearity assumptions but becomes more difficult in high dimensions.Additive models address part of this difficulty by combining univariate component functions.
- Motivation: Additive models are interpretable and can be fitted by backfitting, but their statistical and computational behavior deteriorates when p is large relative to n.This limits their usefulness in high-dimensional settings.
- Sparse additive models: SpAM imposes sparsity on the set of nonzero additive component functions, extending sparse linear-model ideas to nonparametric additive models.The paper relates this formulation to COSSO and other sparse-function methods.
- Contributions: The paper formulates a convex optimization problem, derives an efficient backfitting algorithm, and analyzes effectiveness in high-dimensional settings.The theoretical results include asymptotic sparsity-pattern recovery and persistence, a form of risk consistency.
2. Notation and Assumptions.
The model represents the regression function as an additive sum of centered univariate functions in Hilbert subspaces, with smoothness controlled through basis-based function classes. The setup assumes bounded covariates and specifies norms, bases, and smoothness conditions.
- Data and function spaces: The data consist of covariate-response pairs with Xi in [0,1]^p and a joint distribution P.The covariates are represented componentwise as Xi = (Xi1, …, Xip)^T.
- Data and function spaces: Each component function fj depends on one scalar covariate Xj, has finite L2(P) norm, and is centered so E(fj(Xj)) = 0.These functions form the Hilbert subspaces Hj.
- Data and function spaces: The additive function space consists of functions m(x) = Σj fj(xj), with each fj belonging to its corresponding Hj.The full space is the direct sum H1 ⊕ H2 ⊕ … ⊕ Hp.
- Smoothness assumptions: Component functions are represented using uniformly bounded orthonormal bases and are restricted to smoothness classes Tj.The default smoothness order is νj = 2, although other fixed levels are allowed.
- Notation: The notation includes minimum and maximum eigenvalues of matrices and vector norms used in the theoretical analysis.
3. Sparse Backfitting.
SpAM estimates sparse additive functions by combining coordinate-wise backfitting with functional soft thresholding. Its formulation separates smoothness from sparsity, supports arbitrary smoothers computationally, and admits connections to grouped lasso and orthogonal-series theory.
- Population formulation: The population algorithm updates each component by a soft-thresholded conditional expectation of the current residual, iterating over coordinates.Sample estimates replace these conditional expectations with smoothed residuals.
- Sparse optimization: The optimization imposes an ℓ1-type constraint on component scales while retaining separate smoothness constraints on the functions.This is equivalent to a penalized Lagrangian formulation.
- Sample algorithm: The sample procedure estimates residual projections with linear smoothers such as local linear or kernel smoothers, then applies coordinate-wise backfitting updates.The algorithm initializes all component estimates at zero and iterates until convergence.
- Algorithmic interpretation: The SpAM backfitting algorithm is a functional version of lasso coordinate descent, reducing to lasso-style soft thresholding in an appropriate large-bandwidth case.This connects the procedure to ordinary backfitting and coordinate descent.
- Basis representation and theory: With orthogonal-series smoothing, each smoother projects onto a truncated orthonormal basis, and the usual choice d ≍ n^1/5 gives truncation bias O(n^-4/5) under |S| = O(1).Theoretical analysis in the section assumes this particular smoother.
- Connections: SpAM can be viewed as a functional grouped lasso, while its key advantage over COSSO is decoupling smoothness and sparsity.The resulting algorithm can use any nonparametric smoother and scale to high dimensions.
4. Sparse Nonparametric Logistic Regression.
The sparse backfitting procedure extends to nonparametric logistic regression by embedding weighted backfitting within Newton-style local scoring. Functional sparsity is imposed through thresholded component updates.
- Logistic extension: SpAM extends to additive logistic regression for classification.The extension uses the generalized additive-model local scoring framework.
- Logistic extension: Each local-scoring iteration computes a transformed response and weights based on the current fitted probabilities, then performs weighted backfitting.The weighted smoother operates on the transformed response and covariates.
- Penalized updates: The sparsity penalty yields a stationary condition involving the residual probability term and a subgradient for each component.The nonlinear condition is linearized around the current estimate.
- Penalized updates: In the finite-sample algorithm, a component is set to zero when the smoothed weighted residual norm is below λ; otherwise the nonlinear update is iterated.When λ = 0, the procedure reduces to the standard local-scoring update.
5. Choosing the Regularization Parameter.
The regularization parameter λ is selected by minimizing estimated risk, using Cp and generalized cross-validation with a model-specific degrees-of-freedom definition. These criteria are heuristic because their validity as risk estimates has not been proved, and risk-based selection may overfit.
- λ is chosen by minimizing an estimate of risk, using effective degrees of freedom for each smoother and an estimate of the variance.For smoother j, ν_j is defined as trace(S_j), where S_j is its smoothing matrix.
- The two risk estimates considered are Cp and generalized cross-validation with degrees of freedom defined by df(λ).
- The validity of these risk estimates has not been proved, so the authors regard them as heuristics.
- Risk-based selection of λ may lead to overfitting, based on results about the lasso.
- The estimate can be further cleaned by testing whether each fitted function f_j is zero, using tests such as those of Fan and Jiang (2005).
6. Examples.
Examples apply SpAM to simulated, housing, email-spam, and image-reconstruction data, illustrating sparse variable selection, classification, and functional sparse coding. Across these settings, the method selects relevant components and can improve reconstruction accuracy with fewer codewords.
- Synthetic Data: 150 observations in 200 dimensions contain four nonzero additive components and 196 irrelevant dimensions, providing a high-dimensional sparse test case.The synthetic response uses f1 through f4 plus Gaussian noise, with fj(x)=0 for j≥5.
- Boston Housing: SpAM identifies six nonzero components in the 30-dimensional Boston housing dataset and correctly zeros out both types of irrelevant variables.The augmented data include 20 irrelevant variables: random Uniform(0,1) variables and permutations of the original covariates.
- Boston Housing: The Boston housing solution highlights rm, lstat, ptratio, and crim, while nox and b are borderline under the reported analysis.Using Cp for selection, indux, age, dist, and tax are estimated to be irrelevant.
- Email Spam: Logistic SpAM selects 33 email attributes in its best error-rate model, covering 80% of significant predictors identified by previous hypothesis tests.The example uses 4,601 observations, 57 numeric attributes, and plug-in bandwidths.
- Functional Sparse Coding: A sparse code trained on 200,000 natural-image patches uses 200 codewords that capture edge features across scales and spatial orientations.Each training patch is 16 × 16 pixels, and the code is learned using the lasso and stochastic gradient descent.
- Functional Sparse Coding: In one image-patch reconstruction, SpAM uses seven codewords with RSS 0.0206, versus eight codewords with RSS 0.0561 for the sparse linear model.The comparison uses codewords learned under the sparse linear model and local linear Gaussian-kernel smoothing with h=0.05.
7. Theoretical Properties.
The theoretical analysis extends sparsity-selection and prediction-consistency results to sparse additive models under stated design, truncation, and penalty conditions. It also compares sparse image reconstruction using lasso and SpAM.
- 7.1. Sparsistency: SpAM extends lasso-style sparsistency results to additive models under orthogonal function regression and design conditions.The analysis targets recovery of the true support rather than only prediction accuracy.
- 7.1. Sparsistency: For ν = 2, choosing d_n = n^1/5 achieves the one-dimensional minimax error rate under the stated assumptions.
- 7.1. Sparsistency: Under the corollary’s design assumptions, p_n can be as large as e^n3/5 when n ≍ 1, with λ_n = Cn^-1.
- 7.2. Persistence: SpAM is persistent relative to an l1-bounded additive function class, even when the true regression function is not additive.Persistence is defined relative to the best predictive approximation in the class.
8. Discussion.
The discussion emphasizes that SpAM combines theoretical extensions of l1 regularization with a flexible sparse backfitting algorithm, while identifying smoothing theory, bandwidth selection, and interactions as open directions.
- 8. Discussion: Sparse backfitting decouples smoothing and sparsity, allowing arbitrary nonparametric smoothers while retaining backfitting’s properties.
- 8. Discussion: The theory currently relies on truncated orthogonal-basis smoothing, motivating extensions to more general smoothing operators.
- 8. Discussion: Automatic bandwidth selection and adaptation to different smoothness levels across dimensions remain future-work directions.
- 8. Discussion: Extending basic additive models to interactions requires suitable incoherence conditions for recovering the interaction graph.
9. Proofs.
The proofs derive sparse backfitting updates and establish support recovery and risk results through stationary conditions, subgradient arguments, Gaussian bounds, and empirical-process control.
- Proofs: The sparse backfitting update is obtained by differentiating the Lagrangian with respect to one function while holding the others fixed.
- Proofs: The coordinate update uses conditional expectation of the residual as the projection onto the component function space.
- Proofs: Soft thresholding sets a component function to zero when its residual projection does not overcome the regularization threshold.
- Proofs: The sparsistency proof constructs a coefficient-subgradient pair whose support matches the true support and verifies stationary conditions with high probability.
- Proofs: Gaussian comparison and concentration arguments show that the required probability bounds vanish under the theorem’s conditions.
- Proofs: The persistence proof controls empirical-process deviations using bracketing numbers, bracketing integrals, and Markov’s inequality.