Minimax Semiparametric Learning With Approximate Sparsity

Jelena Bradić, Victor Chernozhukov, Whitney K. Newey, Yinchu ZhuarXiv 2019 · DOI · arXiv

Abstract

Estimating linear, mean-square continuous functionals is a pivotal challenge in statistics. In high-dimensional contexts, this estimation is often performed under the assumption of exact model sparsity, meaning that only a small number of parameters are precisely non-zero. This excludes models where linear formulations only approximate the underlying data distribution, such as nonparametric regression methods that use basis expansion such as splines, kernel methods or polynomial regressions. This paper formalizes the concept of approximate sparsity through classical semi-parametric theory. We derive minimax rates under this formulation for a regression slope and an average derivative, finding these bounds to be substantially larger than those in low-dimensional, semi-parametric settings. We identify several new phenomena, including regimes where root-$n$ estimation is possible even when rate double robustness does not hold. Our findings further reveal distinct optimality boundaries for ordered versus unordered nonparametric regression estimation.

Introduction: Beyond Exact Sparsity

Modern high-dimensional statistics frequently relies on the assumption of exact sparsity—the notion that in a model with $p$ predictors and $n$ observations ($p \gg n$), only a small subset of variables has any effect. However, in complex domains like genomics or finance, this is often an oversimplification. Real-world data is more accurately described as approximately sparse. In these settings, many variables may have small, non-zero effects, and the model improves as more variables are included, though it never reaches a state of perfect, low-dimensional sparsity.

This research addresses the fundamental limits of estimation under approximate sparsity, specifically focusing on the "cost of ignorance" when the relative importance of variables is unknown. By establishing minimax rates, the authors define the absolute speed limits for statistical estimation in these complex environments.

Theoretical Framework

The study formalizes approximate sparsity using semi-parametric theory, defining function classes where approximation error decays at a polynomial rate (denoted by $\xi$) as the number of variables increases. The researchers investigate two primary scenarios:

  1. Ordered Models: Where the researcher knows the hierarchy of variable importance (e.g., low-frequency terms in a Fourier series are more significant than high-frequency ones).
  2. Unordered Models: Where the researcher does not know which variables are most important, requiring the estimator to discover the structure.

Geometric Boundaries of Success

A central contribution of this work is the mapping of "regions of possibility" for statistical estimation. The researchers demonstrate that the ability to achieve the parametric $\sqrt{n}$ estimation rate depends on the decay rates of the regression model ($\xi_1$) and its associated precision matrix ($\xi_2$).

Figure 1: Phase diagram of estimation regimes for approximately sparse models.

As illustrated in Figure 1, the boundaries for success differ significantly between ordered and unordered models. For unordered models, $\sqrt{n}$ estimation is possible if and only if $\max\{\xi_1, \xi_2\} > 1/2$ (Regions A, B, and C). In contrast, ordered models can achieve this rate under a more lenient "sum" condition. Region D represents a critical "impossible zone" for unordered models—a regime where estimation is feasible if the variable order is known, but impossible if it is not.

Methodology: A Novel Multi-Step Estimator

To prove that these theoretical minimax limits are attainable, the authors developed a novel multi-step estimator. This approach combines a Dantzig-type selector with a sophisticated non-symmetric cross-fitting strategy.

Unlike standard symmetric data splitting, this non-symmetric procedure is designed to balance residuals and correct for high-dimensional biases. By leveraging Riesz Representer Theory, the estimator can target specific linear functionals (like regression slopes) without needing to perfectly estimate every underlying parameter in the high-dimensional space.

Key Results and Insights

  • Challenging "Double Robustness": The paper identifies new regimes where the traditional "Rate Double Robustness" (RDR) condition—the requirement that two model components be moderately accurate—fails, yet root-$n$ estimation remains possible. If one component is sufficiently strong, it can compensate for a significantly weaker second component.
  • The $\sqrt{n}$ Threshold: The authors establish that the parametric rate is achievable in approximately sparse, unordered models if the decay rate of either the regression or the precision matrix exceeds $1/2$.
  • Robustness and Efficiency: The proposed estimator is shown to be semiparametrically efficient and robust against difficult data conditions, including heteroscedasticity and heavy-tailed error distributions.

Limitations and Future Work

While this work provides a comprehensive theory for individual coefficients, several avenues for future research remain. The "impossible zone" (Area D) highlights a fundamental gap in high-dimensional inference that may require additional structural assumptions to bridge. Furthermore, the current framework assumes the model can be well-approximated; investigating the impact of significant model misspecification or extending these results to complex non-linear functionals represents the next frontier in this line of research.

Summary updated

Abstract

Estimating linear, mean-square continuous functionals is a pivotal challenge in statistics. In high-dimensional contexts, this estimation is often performed under the assumption of exact model sparsity, meaning that only a small number of parameters are precisely non-zero. This excludes models where linear formulations only approximate the underlying data distribution, such as nonparametric regression methods that use basis expansion such as splines, kernel methods or polynomial regressions. Many recent methods for root-$n$ estimation have been proposed, but the implications of exact model sparsity remain largely unexplored. In particular, minimax optimality for models that are not exactly sparse has not yet been developed. This paper formalizes the concept of approximate sparsity through classical semi-parametric theory. We derive minimax rates under this formulation for a regression slope and an average derivative, finding these bounds to be substantially larger than those in low-dimensional, semi-parametric settings. We identify several new phenomena. We discover new regimes where rate double robustness does not hold, yet root-$n$ estimation is still possible. In these settings, we propose an estimator that achieves minimax optimal rates. Our findings further reveal distinct optimality boundaries for ordered versus unordered nonparametric regression estimation.
BibTeX
@misc{bradic2019minimax,
  author = {Jelena Bradić and Victor Chernozhukov and Whitney K. Newey and Yinchu Zhu},
  title = {{Minimax Semiparametric Learning With Approximate Sparsity}},
  year = {2019},
  eprint = {1912.12213},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.12213},
}
Figure