TL;DR
This paper introduces SDAR, a novel algorithm for fitting sparse, high-dimensional linear regression models. SDAR directly approximates solutions to the $L_0$-penalized least squares problem, achieving state-of-the-art error bounds and outperforming existing methods like Lasso and MCP in simulations, particularly in terms of speed and accuracy.
What Problem Does This Paper Address?
In high-dimensional settings where the number of features ($p$) far exceeds the number of observations ($n$), identifying the truly important predictors is a major challenge. Traditional least squares methods overfit the data. Regularization techniques like Lasso aim to address this by penalizing model complexity. However, the ideal penalty for sparsity is the $L_0$ norm (counting non-zero coefficients), which is computationally intractable due to its non-convexity. Existing methods that approximate $L_0$ regularization often struggle with computational complexity, theoretical guarantees, or require strong assumptions. This paper tackles the problem of efficiently and accurately finding sparse solutions in high-dimensional linear regression by developing a constructive algorithm that directly addresses the $L_0$ penalized problem.
Methods
The core of the paper is the SDAR (Sparse Detection and Root-finding) algorithm. SDAR is an iterative approach that leverages the Karush-Kuhn-Tucker (KKT) conditions for the $L_0$-penalized least squares problem. At each iteration, SDAR:
- Detects the support (active set of predictors): This is done by combining information from the current primal estimate ($\beta_k$) and the dual estimate ($d_k$).
- Solves a least squares problem: Once a potential support is identified, SDAR refits the model using ordinary least squares on that subset of predictors.
This process is repeated, with the regularization parameter effectively changing at each step, leading to a sequence of solutions. The algorithm also includes an adaptive version, ASDAR, which uses data-driven criteria (like BIC) to select the optimal model size when the true sparsity level is unknown.
Datasets
The paper does not introduce new datasets. Instead, it uses simulated datasets generated according to specific models described in Section 7.2. These simulations are designed to mimic real-world scenarios with varying parameters such as sample size ($n$), ambient dimension ($p$), sparsity level ($K$), correlation between predictors ($\rho$), and signal-to-noise ratio ($\sigma$).
Key Insights and Ideas
- Directly tackling $L_0$: Instead of relying on convex relaxations or approximations that can introduce bias (like Lasso), SDAR directly works with the KKT conditions of the $L_0$ problem, offering a more principled approach.
- Primal-Dual Support Detection: The novel aspect of SDAR is its use of both primal ($\beta_k$) and dual ($d_k$) information to identify the active set of predictors. This is more sophisticated than methods that rely solely on correlation (dual information).
- Guaranteed Convergence to Optimal Bounds: The paper provides strong theoretical guarantees, showing that SDAR's solution sequence converges to the minimax optimal error bounds in both $L_2$ and $L_\infty$ norms within a finite number of iterations.
- Independence of Sparsity Level for $L_\infty$ Error: A surprising theoretical result is that the number of iterations required to achieve the optimal $L_\infty$ error bound does not depend on the sparsity level $J$, but rather on the magnitude of coefficients ($R$). This is a significant advantage for very sparse models.
- Computational Efficiency: Despite its theoretical sophistication, SDAR has a per-iteration computational cost of $O(np)$, comparable to other methods, and its overall complexity is efficient, especially for large-scale problems.
Key Results
- Theoretical Guarantees: SDAR achieves sharp $L_2$ and $L_\infty$ estimation error bounds that decay exponentially with the number of iterations.
- $L_2$ error bound: $O(\log(R\sqrt{J}))$ iterations.
- $L_\infty$ error bound: $O(\log(R))$ iterations (surprisingly independent of $J$).
- Oracle Property: SDAR can recover the oracle least squares estimator (the best possible estimator if the true support were known) in a finite number of iterations with high probability.
- Simulation Performance: In simulations on moderately large-scale datasets ($n=5000, p=50000, K=400$), SDAR and its adaptive version ASDAR consistently outperformed Lasso, MCP, and two greedy methods (FoBa, GraDes) in terms of accuracy (lower relative error).
- Speed: SDAR/ASDAR was significantly faster than other methods, often by orders of magnitude, especially as the correlation between predictors increased. For example, SDAR was 3-100 times faster than other methods at low correlation and 20-100 times faster than MCP at higher correlations.
Limitations and Future Work
- Linear Regression Only: The current work focuses solely on linear regression models. The authors suggest generalizing SDAR to models with more general loss functions or other sparsity structures as an interesting future direction.
- Parallel/Distributed Versions: For extremely large datasets, developing parallel or distributed versions of SDAR would be beneficial.
- Assumptions: The theoretical guarantees rely on certain conditions on the design matrix (Sparse Riesz Condition, mutual coherence) and the noise distribution (sub-Gaussian tails). While these are common in the literature, their practical implications and robustness to violations could be further explored.
Summary updated