TL;DR
This paper introduces the "Discrete Dantzig Selector" (DDS), a novel method for identifying sparse linear models by directly minimizing the number of non-zero coefficients. By reformulating this problem as a Mixed Integer Linear Optimization (MILO) problem, the authors achieve certifiably optimal solutions and demonstrate superior statistical performance and computational efficiency compared to existing methods, especially for high-dimensional datasets.
What Problem Does This Paper Address?
In high-dimensional statistics, a common goal is to build accurate linear models when the number of potential predictor variables ($p$) far exceeds the number of observations ($n$). A key challenge is to identify a sparse model, meaning only a small subset of the predictors are truly relevant. Traditional methods like the Lasso and the original Dantzig Selector (l1-Dantzig) achieve sparsity indirectly by minimizing an L1-norm penalty on the coefficients. However, these methods can struggle with highly correlated predictors, sometimes selecting dense models or missing important variables. This paper addresses the need for an estimator that directly targets sparsity (minimizing the count of non-zero coefficients) while maintaining good data-fidelity and computational tractability, especially for large-scale problems.
Methods
The core innovation is the Discrete Dantzig Selector (DDS), defined by the optimization problem:
$$ \min_{\beta} ||\beta||_0 \quad \text{s.t.} \quad ||X^T(y - X\beta)||_{\infty} \leq \delta $$
where $||\beta||_0$ is the L0-norm (number of non-zero coefficients), $X$ is the design matrix, $y$ is the response vector, and $\delta$ is a data-fidelity parameter.
The authors reformulate this non-convex problem into a Mixed Integer Linear Optimization (MILO) problem. This is achieved by introducing binary variables $z_i$ that are linked to the continuous coefficients $\beta_i$ such that $z_i=0$ if $\beta_i=0$ and $\beta_i$ is unconstrained if $z_i=1$. This MILO formulation allows for finding certifiably optimal global solutions.
To further enhance computational performance, they develop discrete first-order methods. These algorithms, inspired by convex optimization techniques, provide high-quality feasible solutions that are used as "warm-starts" for the MILO solvers. This hybrid approach significantly speeds up the process of finding optimal solutions and obtaining optimality certificates.
Datasets
The paper uses several types of synthetic datasets and one real-world dataset for evaluation:
- Type-Synth: Generated Gaussian ensembles with varying correlation structures ($\rho$), number of observations ($n$), number of features ($p$), and number of true non-zero coefficients ($k^*$).
- Semi-synthetic: The Radiation sensitivity gene expression dataset (from Hastie et al.'s "Elements of Statistical Learning") was used, with features downsampled to $p=2000$ and $n=58$.
- Gisette dataset: A real-world dataset used for large-scale experiments.
Key Insights and Ideas
- Direct Sparsity: By minimizing the L0-norm, DDS directly targets the number of non-zero coefficients, offering a more explicit approach to sparsity than L1-based methods. This is crucial when parsimony is the primary goal.
- MILO for Optimality: Reformulating the L0-minimization problem as a MILO problem is a key enabler. It allows for finding globally optimal solutions, a strong advantage over heuristic methods.
- Warm-Starts Matter: The development of discrete first-order methods that provide warm-starts for MILO solvers is critical. This hybrid approach dramatically improves computational efficiency, making large-scale problems tractable.
- Statistical Superiority: DDS, both in its raw and polished forms, demonstrates better statistical properties (estimation error, variable selection accuracy) compared to L1-based methods, especially in scenarios with correlated predictors.
- Scalability: The proposed MILO approach, enhanced by warm-starts, scales to problems with $p$ up to 10,000 features, achieving certifiably optimal solutions within reasonable timeframes.
Key Results
- Computational Efficiency: The proposed MILO approach with warm-starts significantly outperforms standalone MILO solvers and other methods like MIPGO, achieving certifiably optimal solutions for problems with $p \approx 10,000$ in hours, whereas other methods struggle or take much longer.
- Statistical Performance: DDS consistently shows better or comparable estimation and prediction error bounds compared to L1-based methods. Crucially, it achieves significantly higher sparsity, meaning it selects fewer, more relevant variables.
- Variable Selection: DDS demonstrates superior variable selection properties, particularly in cases with highly correlated predictors where L1-methods can falter.
- Scalability: The method successfully handles large-scale problems, with computations for $p=10,000$ taking around an hour for optimal solutions and up to 40 hours for optimality certificates.
Limitations and Future Work
- Computational Tractability: While MILO is considered "computationally tractable" in the sense of providing certifiable optimality, it is not polynomial-time tractable. The paper acknowledges that for very large problems, obtaining certificates of optimality can still take considerable time (e.g., up to 40 hours for $p=10,000$).
- Tuning Parameter $\delta$: Like other data-fidelity based methods, the choice of the tuning parameter $\delta$ influences the results. The paper discusses how to select $\delta$ based on data-fidelity and statistical properties.
- Future Work: The paper suggests exploring further enhancements to MILO formulations and data-driven strategies for parameter estimation. The authors also highlight the potential for applying their framework to other discrete optimization problems in statistical estimation.
Summary updated