Valid Inference for L2-Boosting

David Rügamer, Sonja GrevenarXiv 2018 · OpenReview

TL;DR

This paper introduces a robust framework for conducting valid statistical inference—think p-values and confidence intervals—after using $L_2$-Boosting for variable selection. By leveraging Monte Carlo sampling and conditioning on the set of selected variables rather than the specific selection path, the authors provide a way to quantify uncertainty in high-dimensional, additive models without the "double-dipping" bias common in post-selection analysis.

What Problem Does This Paper Address?

In modern data science, we often use algorithms like Lasso or Boosting to pick the most important variables from a large pool. However, there is a catch: if you use the same data to select a model and then test its significance, your p-values will be artificially small and your confidence intervals too narrow. This is known as post-selection bias.

While methods exist for "selective inference" in simpler models (like Forward Stepwise Regression), $L_2$-Boosting presents a unique challenge. It is a "slow learner" that updates the model iteratively, often selecting the same variable multiple times across hundreds of steps. Existing methods that try to track the exact "path" of selection end up being too restrictive, leading to a massive loss of statistical power—essentially making it impossible to find significant results even when they exist.

Methods

The authors propose a selective inference framework tailored for the component-wise functional gradient descent algorithm (CFGD), specifically $L_2$-Boosting.

Key technical components include:

  • Selective Conditioning: Instead of conditioning on the entire selection path (the order and signs of every update), they condition only on the final set of selected variables. This makes the "inference region" (the subset of possible data outcomes that would lead to the same model) a complex union of polyhedra rather than a single simple shape.
  • Monte Carlo Approximation: Because the geometry of this inference region is too complex to describe analytically, they use an importance sampling routine. They "refit" the boosting model many times on perturbed versions of the data to empirically map out the boundaries of the selection event.
  • Line Search Refinement: To make the sampling efficient, they implement a line search to find the truncation limits of the distribution, ensuring they don't waste computation on samples that fall outside the selection region.
  • Extensibility: The framework is designed to handle not just linear effects, but also grouped variables, penalized splines (non-linear effects), and models where the stopping iteration ($m_{stop}$) is chosen via cross-validation.

Datasets

The authors evaluate their method using:

  1. Synthetic Simulations: Linear and spline-based models with varying signal-to-noise ratios (SNR) and dimensions (including $p > n$ settings).
  2. Tehran Residential Apartments Dataset: A real-world dataset from the UCI Machine Learning Repository containing 372 observations and 105 covariates (economic indicators and physical attributes) used to predict sales prices.

Key Insights and Ideas

  • Path vs. Set: The "aha moment" is that for iterative algorithms, conditioning on the path is a power-killer. By moving to the set of variables, the authors preserve enough information to actually detect significant effects.
  • Bypassing Geometry: Most selective inference papers spend pages on high-dimensional geometry (polyhedral constraints). This paper argues that for complex algorithms, we should stop trying to solve the geometry analytically and start sampling it.
  • Handling Non-linearity: Unlike many post-selection tools that only work for linear Lasso, this framework naturally extends to additive models and splines, which are bread-and-butter for practitioners in fields like ecology or medicine.

Key Results

  • Validity: In simulations, the proposed sampling approach produced p-values that were uniform under the null hypothesis, meaning the false positive rate was correctly controlled.
  • Power: The sampling approach showed significantly higher power to detect true effects compared to the traditional "polyhedron" approach, which often had near-zero power in boosting scenarios.
  • Confidence Interval Coverage: Selective confidence intervals achieved the target 95% coverage, whereas "naive" intervals (ignoring selection) failed miserably.
  • Real-world Application: When applied to the Tehran housing data, the method identified significant non-linear drivers of price (like population size and square meter price) that standard linear models or unadjusted boosting might have missed or misrepresented.

Limitations and Future Work

  • Computational Cost: The primary drawback is speed. Because the method requires refitting the boosting model $B$ times (e.g., 1,000 times) for every hypothesis test, it can be computationally intensive for very large datasets, though the authors note it is highly parallelizable.
  • Discrete Responses: The current work assumes normally distributed errors. Extending this to Generalized Linear Models (GLMs) with discrete responses (like Poisson or Binomial) remains a challenging future direction due to the way discrete data restricts the response space.
  • Infinite Intervals: Like all selective inference methods, there is a small chance (~5% in their tests) of producing "infinite" confidence intervals when the data is right on the edge of a selection boundary.

Summary updated

Abstract

We propose a statistical inference framework for the component-wise functional gradient descent algorithm (CFGD) under normality assumption for model errors, also known as $L_2$-Boosting. The CFGD is one of the most versatile tools to analyze data, because it scales well to high-dimensional data sets, allows for a very flexible definition of additive regression models and incorporates inbuilt variable selection. Due to the variable selection, we build on recent proposals for post-selection inference. However, the iterative nature of component-wise boosting, which can repeatedly select the same component to update, necessitates adaptations and extensions to existing approaches. We propose tests and confidence intervals for linear, grouped and penalized additive model components selected by $L_2$-Boosting. Our concepts also transfer to slow-learning algorithms more generally, and to other selection techniques which restrict the response space to more complex sets than polyhedra. We apply our framework to an additive model for sales prices of residential apartments and investigate the properties of our concepts in simulation studies.
BibTeX
@misc{rugamer2018valid,
  author = {David Rügamer and Sonja Greven},
  title = {{Valid Inference for L2-Boosting}},
  year = {2018},
  eprint = {1805.01852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.01852},
}
Figure