# From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 56 references that are in the map.
- First posted on arXiv 21 May 2026.

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

- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [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)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [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)
- [The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance](https://mlsanity.com/paper/2309.13775/) (2023)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [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)
- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [Rashomon Sets for Prototypical-Part Networks: Editing Interpretable Models in Real-Time](https://mlsanity.com/paper/2503.01087/) (2025)
- [Sparse and Smooth Signal Estimation: Convexification of L0 Formulations](https://mlsanity.com/paper/1811.02655/) (2018)
- [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)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)
- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C language](https://mlsanity.com/paper/2312.14832/) (2023)
- [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)
- [Leveraging Predictive Equivalence in Decision Trees](https://mlsanity.com/paper/2506.14143/) (2025)
- [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)
- [A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programs](https://mlsanity.com/paper/2505.00311/) (2025)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models](https://mlsanity.com/paper/2602.04551/) (2026)

## Abstract (arXiv)

GPUs have significantly accelerated first-order methods for large-scale optimization, especially in continuous optimization. However, this success has not transferred cleanly to problems with discrete variables, combinatorial structure, and nonlinear objectives, such as certifying optimal solutions for cardinality-constrained generalized linear models. Major challenges include the sequential processing of heterogeneous nodes in branch and bound (BnB) and frequent data movement between the CPU and GPU. We propose a simple, generic, and modular CPU--GPU framework that processes multiple BnB nodes in batches on GPUs. The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures. Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances. The framework can also be extended to collect the entire Rashomon set, enabling downstream statistical analysis such as variable-importance analysis and model selection under secondary user-specific measures (e.g., AUC in classification).