A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models

Ryan Lucas, Xiang Meng, Rahul Mazumder

arXivarxiv/2602.04551Feb 4, 2026math.OCscore 0

We study exact sparse linear regression with an $\ell_0-\ell_2$ penalty and develop a branch-and-bound (BnB) algorithm explicitly designed for GPU execution. Starting from a perspective reformulation, we derive an interval relaxation that can be solved by ADMM with closed-form, coordinate-wise updates. We structure these updates so that the main work at each BnB node reduces to batched matrix-vector operations with a shared data matrix, enabling fine-grained parallelism across coordinates and coarse-grained parallelism across many BnB nodes on a single GPU. Feasible solutions (upper bounds)…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.04551
curl -X POST /api/v1/records/arxiv/2602.04551/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.04551/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'