# Scalable First-order Method for Certifying Optimal k-Sparse GLMs

arXiv: https://arxiv.org/abs/2502.09502 · HTML: https://mlsanity.com/paper/2502.09502/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 70 references that are in the map.
- First posted on arXiv 13 Feb 2025.

## Builds on (most cited first, 30 of 31)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Conditional Adapters: Parameter-efficient Transfer Learning with Fast Inference](https://mlsanity.com/paper/2304.04947/) (2023)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Learning Optimized Risk Scores](https://mlsanity.com/paper/1610.00168/) (2016)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Clarabel: An interior-point solver for conic programs with quadratic objectives](https://mlsanity.com/paper/2405.12762/) (2024)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Learning Sparse Nonlinear Dynamics via Mixed-Integer Optimization](https://mlsanity.com/paper/2206.00176/) (2022)
- [Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives](https://mlsanity.com/paper/2001.06471/) (2020)
- [FasterRisk: Fast and Accurate Interpretable Risk Scores](https://mlsanity.com/paper/2210.05846/) (2022)
- [Integer Programming for Learning Directed Acyclic Graphs from Continuous Data](https://mlsanity.com/paper/1904.10574/) (2019)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [Sparse and Smooth Signal Estimation: Convexification of L0 Formulations](https://mlsanity.com/paper/1811.02655/) (2018)
- [New Perspectives on k-Support and Cluster Norms](https://mlsanity.com/paper/1512.08204/) (2015)
- [Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks](https://mlsanity.com/paper/2005.14346/) (2020)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming](https://mlsanity.com/paper/2311.07710/) (2023)
- [cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language](https://mlsanity.com/paper/2312.14832/) (2023)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Subset Selection for Multiple Linear Regression via Optimization](https://mlsanity.com/paper/1701.07920/) (2017)
- [Supermodularity and valid inequalities for quadratic optimization with indicators](https://mlsanity.com/paper/2012.14633/) (2020)
- [A New Branch-and-Bound Pruning Framework for ℓ0-Regularized Problems](https://mlsanity.com/paper/2406.03504/) (2024)
- [Deep Neural Networks pruning via the Structured Perspective Regularization](https://mlsanity.com/paper/2206.14056/) (2022)
- [Compact extended formulations for low-rank functions with indicator variables](https://mlsanity.com/paper/2110.14884/) (2021)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [On the power of linear programming for K-means clustering](https://mlsanity.com/paper/2402.01061/) (2024)
- [Accelerating Low-Rank Factorization-Based Semidefinite Programming Algorithms on GPU](https://mlsanity.com/paper/2407.15049/) (2024)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)

## Built on by (most cited first, 1 of 1)

- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)

## Abstract (arXiv)

This paper investigates the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through an ℓ0 cardinality constraint. While branch-and-bound (BnB) frameworks can certify optimality by pruning nodes using dual bounds, existing methods for computing these bounds are either computationally intensive or exhibit slow convergence, limiting their scalability to large-scale problems. To address this challenge, we propose a first-order proximal gradient algorithm designed to solve the perspective relaxation of the problem within a BnB framework. Specifically, we formulate the relaxed problem as a composite optimization problem and demonstrate that the proximal operator of the non-smooth component can be computed exactly in log-linear time complexity, eliminating the need to solve a computationally expensive second-order cone program. Furthermore, we introduce a simple restart strategy that enhances convergence speed while maintaining low per-iteration complexity. Extensive experiments on synthetic and real-world datasets show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.