Minimax-Optimal Univariate Function Selection in Sparse Additive Models: Rates, Adaptation, and the Estimation-Selection Gap

Shixiang LiuNeurIPS 2025 · OpenReview

In the realm of high-dimensional statistics, researchers frequently encounter the "curse of dimensionality." When confronted with thousands of potential predictors, it is often suspected that only a small fraction are genuinely influential. Sparse Additive Models (SpAM) have emerged as a powerful solution to this challenge. They offer a flexible way to capture non-linear relationships while maintaining interpretability by assuming the total effect is simply the sum of individual univariate functions.

However, a common assumption in the field—that successfully estimating these functions guarantees the correct selection of variables—has recently been challenged. A new paper by Shixiang Liu establishes that this is not always true, revealing a fundamental "Estimation-Selection Gap" that fundamentally alters how variable selection should be approached in complex, non-parametric models.

The Challenge of Variable Selection in SpAMs

Variable selection is the process of identifying which features (e.g., age, blood pressure, or gene expression) meaningfully influence an outcome. In a SpAM, the outcome is modeled as a sum of functions:

$$y = f_1(x_1) + f_2(x_2) + \dots + f_p(x_p)$$

"Sparsity" implies that the vast majority of these functions are exactly zero. Identifying the active functions presents a two-fold challenge:

  1. The High-Dimensional Needle: When the number of features ($p$) vastly exceeds the sample size, isolating the few non-zero functions is mathematically grueling.
  2. The Smoothness Factor: Unlike simple linear models where a variable's effect is captured by a single scalar coefficient, variables in SpAMs are represented by functions. These functions can be smooth, highly variable, or complex, and their exact mathematical properties are rarely known in advance.

Previous research has often treated variable selection as a mere byproduct of function estimation. This work asks a more fundamental question: What is the absolute minimum signal strength required to correctly identify the right variables, and does this threshold differ from what is needed for accurate estimation?

Methodology: A Theoretical Sandbox

To rigorously analyze this problem, the author utilizes a Gaussian White Noise (GWN) framework, which serves as a standard theoretical environment for non-parametric statistics.

To manage the complexity of the functions, the paper employs a series expansion approach. Each univariate function is decomposed into an infinite sum of basis functions (such as sines and cosines). The proposed algorithm, a Truncated Hard-Thresholding Selector, evaluates these functions by looking at the first $K$ coefficients of the series. If the combined "energy" of these $K$ coefficients exceeds a mathematically derived threshold, the variable is selected.

The paper provides a rigorous minimax analysis, proving that no other algorithm can achieve better separation rates under the stated conditions.

Key Insights: The Estimation-Selection Gap

The most striking discovery in this research is the Estimation-Selection Gap. In simple linear models, estimation and selection are closely linked. In SpAMs, however, they diverge significantly.

  • Diverging Truncation Levels: To obtain a good estimate of a function, one must truncate the series at a point ($K_e$) that perfectly balances bias and variance. However, to select the variable, the algorithm often needs to evaluate a larger number of coefficients ($K_s$) to capture enough signal energy to distinguish the function from random noise. Procedures optimized purely to estimate the shape of a function often fail to correctly identify if that function should be included in the model at all.
  • The Interplay of Sparsity and Smoothness: The difficulty of the selection problem (the minimax rate) is not merely the sum of a sparsity penalty and a smoothness penalty. Instead, the high-dimensional structure dictates how much of the function's smoothness can be safely ignored.
  • The Cost of Adaptation: If the smoothness of the functions is unknown (the "adaptation" problem), the model incurs a small mathematical penalty: an additional $\log(\log(\sigma^{-2}))$ term in the required signal strength.

Results and Validation

As a theoretical statistics paper, the work relies on simulated datasets to validate its theorems across varying dimensions ($p$ ranging from 10 to 10,000), noise levels, and smoothness parameters (Sobolev-smoothness).

The key results include:

  • Optimal Rates: The paper establishes the first finite-sample guarantees for univariate function selection in SpAMs, covering both False Discovery Rate (FDR) control and exact support recovery.
  • Support Recovery is Harder: The signal strength required to perfectly identify the exact set of variables is strictly higher than the strength needed to simply balance false positives and false negatives.
  • Suboptimality of Estimation: Theorem 7 mathematically proves that using a truncation level optimized for function estimation leads to strictly suboptimal selection performance in certain regimes.

Limitations and Future Directions

The primary limitation of this work is its reliance on the Gaussian White Noise model. While mathematically elegant and asymptotically equivalent to standard regression, it abstracts away some of the complexities found in real-world empirical data.

Future research directions include:

  • Beyond Sobolev Spaces: Extending these minimax results to Besov spaces, which are better equipped to handle functions with localized spikes or discontinuities.
  • Privacy Constraints: Investigating how these selection rates degrade under Local Differential Privacy constraints, a critical concern in modern data science.
  • Generalizing the Gap: Developing a broader theory of the estimation-selection gap that applies to a wider class of non-parametric and high-dimensional models.

Summary updated

Abstract

The sparse additive model (SpAM) offers a trade-off between interpretability and flexibility, and hence is a powerful model for high-dimensional research. This paper focuses on the variable selection, i.e., the univariate function selection problem in SpAM. We establish the minimax separation rates from both the perspectives of sparse multiple testing (FDR + FNR control) and support recovery (wrong recovery probability control). We further study how adaptation to unknown smoothness affects the minimax separation rate, and propose an adaptive selection procedure. Finally, we discuss the difference between estimation and selection in SpAM: Procedures achieving optimal function estimation may fail to achieve optimal univariate function selection.
BibTeX
@inproceedings{liu2025minimax,
  author = {Shixiang Liu},
  title = {{Minimax-Optimal Univariate Function Selection in Sparse Additive Models: Rates, Adaptation, and the Estimation-Selection Gap}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=QudbVyFaTu},
}

Loading related content...

Figure