Research map / Learning theory and algorithms / Combinatorial and search optimization
A New Branch-and-Bound Pruning Framework for $\ell_0$-Regularized Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a dual-based pruning test for branch-and-bound solvers of l0-regularized problems that jointly screens all direct successors of a node at near-zero extra cost, avoiding a convex relaxation solve per node.
Problem
Branch-and-bound methods for l0-regularized learning problems spend most of their time solving convex relaxations to evaluate pruning tests at each node, creating a computational bottleneck.
Approach
Uses Fenchel-Rockafellar dual lower bounds that are cheap to evaluate: the dual objective at a node differs from its direct successors by simple nonnegative per-coordinate terms, so all successor pruning tests can be evaluated jointly from inner products already computed by first-order solvers, and the dual point is taken from the current primal iterate's subgradient.
Key results
- On synthetic instances (k=5, m=500, n=1000, rho=0.9, tau=10), the proposed method solves all instances within a budget where competitors solve none, an acceleration of at least one order of magnitude.
- Across all tested synthetic scenarios the solving time improves by at least a factor 5, with gains increasing with n and rho.
- On real datasets, time savings reach up to four orders of magnitude versus MIP solvers (Mosek, Cplex, Gurobi) and up to two orders of magnitude versus L0bnb in best cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add simultaneous pruning tests to standard branch-and-bound pruning | El0ps · Synthetic data (k=5, m=500, n=1000, ρ=0.9, τ=10) | solving time: at least one order of magnitude | Helped |
| Add simultaneous pruning tests to standard branch-and-bound pruning (ablation) | El0ps · Synthetic data (varying one parameter at a time) | solving time: at least a factor 5 | Helped |
| Increase dimension parameter n | El0ps with simultaneous pruning tests · Synthetic data | solving time acceleration | Helped |
| Increase correlation parameter ρ | El0ps with simultaneous pruning tests · Synthetic data | solving time acceleration | Helped |
| Vary sparsity level k or signal-to-noise ratio τ | El0ps with simultaneous pruning tests · Synthetic data | solving time acceleration | No clear effect |
| Add simultaneous pruning tests to standard branch-and-bound pruning | El0ps · Riboflavin, Bctcga, Colon cancer, Leukemia, Breast cancer, Arcene | solving time: up to four orders of magnitude | Helped |
| Add simultaneous pruning tests to standard branch-and-bound pruning | El0ps · Riboflavin, Bctcga, Colon cancer, Leukemia, Breast cancer, Arcene | solving time: up to two orders of magnitude | Helped |
Limitations
- Dual bound is looser than the standard convex relaxation bound, so pruning requires enough deep nodes to succeed
- Requires assumptions on f and h (convex, closed, 0 accumulation point of dom(h), h(0)=0) and O(m) conjugate evaluation
Experimental setup
Datasets: Riboflavin Bctcga Colon cancer Leukemia Breast cancer Arcene
Benchmarks: synthetic l0-regularized regression instances Riboflavin Bctcga Colon cancer Leukemia Breast cancer Arcene
Metrics: solving time fraction of instances solved within time budget acceleration factor
Baselines: Mosek Cplex Gurobi L0bnb
Builds on: L0bnb screening rules via duality
Closest papers by meaning
- Scalable First-order Method for Certifying Optimal k-Sparse GLMs (ICML 2025 · similarity 0.84)
- Sparsest Models Elude Pruning: An Exposé of Pruning’s Current Capabilities (ICML 2024 · similarity 0.84)
- SAFE: Finding Sparse and Flat Minima to Improve Pruning (ICML 2025 · similarity 0.84)
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.84)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.84)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.