Source-linked AI summary
Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions
Dimitris Bertsimas, Bart Van Parys
TL;DR
Exact sparse regression is NP-hard, motivating heuristic approaches and convex proxies that can have difficulty recovering sparsity patterns. This paper introduces a binary convex reformulation and cutting plane algorithm, reporting provably optimal solutions for instances with dimensions in the 100,000s and new computational phase transitions.
Problem
Exact sparse regression is NP-hard, so much prior work has focused on heuristic approaches and convex surrogate formulations rather than the discrete problem.
Method
The paper develops a binary convex reformulation and a cutting plane algorithm for solving exact sparse regression to provable optimality.
Results
The approach solves exact sparse regression instances with sample sizes and regressor dimensions in the 100,000s, improving by two orders of magnitude over known exact approaches.
Takeaways & Limitations
As the sample size increases, sparse regression becomes easier computationally and the solution perfectly recovers the true signal support, while small-sample instances take substantially longer.
Takeaways & Limitations
Lasso and Elastic Net can recover sparsity patterns poorly, and Lasso produces biased regressors because its ℓ1 penalty shrinks coefficients.
Abstract
from arXiv · showhide
We present a novel binary convex reformulation of the sparse regression problem that constitutes a new duality perspective. We devise a new cutting plane method and provide evidence that it can solve to provable optimality the sparse regression problem for sample sizes n and number of regressors p in the 100,000s, that is two orders of magnitude better than the current state of the art, in seconds. The ability to solve the problem for very high dimensions allows us to observe new phase transition phenomena. Contrary to traditional complexity theory which suggests that the difficulty of a problem increases with problem size, the sparse regression problem has the property that as the number of samples $n$ increases the problem becomes easier in that the solution recovers 100% of the true signal, and our approach solves the problem extremely fast (in fact faster than Lasso), while for small number of samples n, our approach takes a larger amount of time to solve the problem, but importantly the optimal solution provides a statistically more relevant regressor. We argue that our exact sparse regression approach presents a superior alternative over heuristic methods available at present.
1 Introduction
The paper formulates sparse regression as an NP-hard cardinality-constrained optimization problem and develops an exact, scalable alternative to heuristic proxy methods. Its binary convex reformulation and cutting-plane algorithm enable large-scale optimal solutions and reveal phase transitions in recovery and computational difficulty.
- Problem formulation: Sparse regression minimizes regularized prediction error subject to an ℓ0 sparsity constraint, limiting the number of nonzero coefficients to k.Tikhonov regularization controls the penalty weight γ and helps reduce input-noise effects.
- Motivation and related methods: The problem is NP-hard, motivating heuristic approaches such as Elastic Net and Lasso despite their limitations in recovering sparsity patterns.The ℓ1 penalty can bias coefficients by shrinking large and small coefficients uniformly.
- Exact reformulation: The paper replaces the big-M formulation with a binary convex reformulation based on a dual perspective, avoiding auxiliary constants.The direct big-M approach becomes burdensome as the regression dimension p grows, and its data-dependent constant must be chosen carefully.
- Scalable algorithm: A tailored cutting-plane algorithm solves exact sparse regression to optimality for instances with n and p in the 100,000s, an improvement of two orders of magnitude over known exact approaches.The method removes the computational edge historically attributed to heuristics such as Elastic Net and Lasso.
- Phase transitions: For n above a threshold n_t, exact sparse regression recovers the true support with A% = 100 and F% = 0 while solving in seconds; for smaller n, solution time increases and recovery is harder.The recovery threshold for exact sparse regression is reported as smaller than the corresponding Lasso threshold n_1.
- Extensions: The approach also generalizes to sparse kernel regression, providing a nonlinear sparse-selection alternative to black-box methods such as neural networks.The paper presents this nonlinear extension as a potential competitor rather than as an established empirical conclusion.
2 A convex binary reformulation of sparse linear regression
The section develops a dual, kernel-based view of sparse regression by separating support selection from coefficient optimization and reformulating the problem as a convex pure-binary optimization. This perspective enables subset selection over kernel components rather than regressors.
- Problem formulation: Sparse regression combines continuous coefficients with a discrete support vector, making the problem a mixed continuous-discrete optimization problem.The support is represented by binary selection variables, while the regressor remains continuous.
- Regression loss: The regression loss is convex in the kernel outer product and admits explicit and semidefinite-representable characterizations.These characterizations support the subsequent reformulation and efficient evaluation.
- Binary reformulation: The sparse regression problem can be reformulated as a pure binary optimization problem over support variables and micro kernel matrices.The reformulation follows by separating the support from its nonzero coefficients and solving the inner regression problem explicitly.
- Binary reformulation: The resulting formulation is a convex integer optimization problem whose objective is convex in the binary support vector.The method avoids explicitly constructing the CIO formulation and instead solves it with a cutting plane algorithm developed in the next section.
- Kernel connection: The formulation takes a dual perspective by selecting kernels rather than regressors, and reduces to the standard kernel matrix when sparsity is omitted.The dual problem scales with the number of samples n and is insensitive to input dimension p.
- Relaxation: The continuous relaxation selects the k largest α^T K_j α terms and provides an effective warm start for exact sparse regression.This relaxation constructs an optimal dual lower bound from the k largest kernel contributions.
3 A cutting plane algorithm
The paper solves the convex binary formulation with an outer-approximation cutting plane method that iteratively improves lower bounds until exact optimality. Efficient loss evaluation, subgradient computation, and warm starts make the method scalable in practice.
- Outer approximation: The tailored solver applies outer approximation by iteratively solving increasingly accurate mixed-integer approximations of the convex binary formulation.Each cutting plane contributes to a piecewise-affine lower bound on the regression loss.
- Outer approximation: Each nonoptimal binary solution is cut off by a tangent inequality, progressively refining the feasible region and the approximation to the regression loss.The process stops when the current binary solution satisfies the optimality condition.
- Guarantee and complexity: The cutting plane procedure terminates after finitely many cuts and returns the exact sparse regression solution.This establishes provable optimality for the method, despite potentially exponential worst-case cutting-plane and branch-and-bound complexity.
- Efficient evaluation: Evaluating the loss and subgradients can be reduced to O(k^3 + nk) floating-point operations instead of O(n^3).The reduction uses the matrix inversion lemma and a smaller capacitance matrix when n is substantially larger than k.
- Implementation improvements: The algorithm uses a high-quality warm start from the continuous relaxation, formed by selecting the k largest dual kernel contributions.A better initial cutting plane can accelerate convergence, although any feasible initial selection preserves eventual optimality.
4 Scalability and phase transitions
The cutting plane algorithm solves exact sparse regression at scale and reveals linked accuracy, complexity, and false-alarm phase transitions. As sample size increases, recovery becomes statistically reliable and computation becomes easier, while feature dimension has only minor influence on the transition.
- Scalability: The cutting plane algorithm reaches provable optimality in seconds for regression problems with n and p in the 100,000s.This scale is reported as two orders of magnitude beyond known exact sparse regression methods.
- Scalability: Exact sparse regression can be significantly faster than Lasso even on very large instances, although Lasso returns an entire regularization path.The comparison therefore involves one exact regression model versus a path of Lasso solutions.
- Phase transition phenomena: For n > nt, exact sparse regression recovers 100% of the true signal and solves rapidly; for n < nt, solution time becomes large, with a statistically relevant but computationally infeasible region near n0 ≈ 50.The paper describes this as a complexity phase transition, contrary to the usual expectation that larger problems are harder.
- Parametric dependency: The transition depends strongly on n/k and SNR, but only weakly on p; above the n/k threshold, A% = 100 and F% = 0 with solution time of order seconds.Below the threshold, support recovery falls, false alarms surge, and solution time grows combinatorially; noisier data shifts the transition later.
5 The road towards nonlinear feature discovery
The paper extends sparse regression to nonlinear feature discovery by lifting the data with selected transformations while enforcing sparsity. Experiments illustrate accurate feature recovery in favorable settings but expose limitations for feature-product nonlinearities.
- Method: The nonlinear extension augments each original regressor with nonlinear transformations and restricts the final model to k selected features.The lifted feature matrix can be much larger than the original regressor dimension.
- Method: The nonlinear sparse regression problem is solved through the same reformulation framework as the linear problem, using kernel matrices Kj := ψj(X)ψj(X)⊤.The nonlinear corollary differs from the linear theorem through the definition of the kernel matrices.
- Results: For a = 0, n = 200 suffices to identify the correct nonlinear features in the reported model.The experiment uses 160 nonlinear features and adds 16 irrelevant regressors to obscure the four relevant features.
- Results: For a = 1, A% = 100 for n ≥200, but F% > 0 because the product term aX1X2 prevents exact recovery of the underlying model.The reported experiments use medians over five independent runs and select k by cross-validation.
- Limitations: The approach is presented as an illustration rather than a general solution for arbitrary nonlinearities, because broader discovery could sacrifice statistical power.The authors describe it as a potential competitor to black-box approaches such as neural networks.
6 Conclusions
The paper introduces an exact sparse regression approach that scales to very high-dimensional instances and reveals phase transitions in recovery and computational difficulty. As sample size increases, recovery becomes perfect and the method can become faster than Lasso.
- Conclusions: The binary convex reformulation and cutting plane algorithm solve exact sparse regression to provable optimality with n and p in the 100,000s.This is reported as a two-orders-of-magnitude improvement over known exact sparse regression approaches.
- Conclusions: As n increases, sparse regression becomes easier: the solution perfectly recovers the true support and the approach can solve the problem faster than Lasso.For small n, the approach takes longer, while its optimal solution remains statistically more relevant.
- Conclusions: The results expose phase transition phenomena that become observable because the approach handles very high-dimensional sparse regression problems.These transitions contrast with the usual expectation that larger problem size necessarily increases difficulty.