acceptodds
Withdrawn from ICLR 2027

GPU-Accelerated Branch-and-Bound and Conditional Screening for Sparse Logistic Regression

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sparse logistic regression selects a small set of predictors, but optimizing over feature subsets requires many closely related continuous solves. We develop a branch-and-bound framework that batches ridge-logistic subproblems on a GPU and uses gradient residuals to obtain valid lower bounds from inexact solves. A complementary analysis of conditional greedy screening gives a finite-sample support-containment guarantee with a controlled number of competitive irrelevant selections. The analysis accommodates signals that become detectable only after conditioning and separates the statistical screening guarantee from the deterministic pruning bounds. Synthetic experiments show faster support recovery for conditional screening than for marginal screening in a correlated suppressor design. On two classification datasets, the GPU implementation attains smaller terminal optimality gaps than the tested CPU baselines and lower batch runtimes for moderate and large batch sizes. These results support batched GPU computation for exact sparse classification.

Primary area:
optimization
Keywords:
Sparse classification, cardinality-constrained optimization, branch-and-bound, GPU-accelerated optimization, conditional feature screening, support recovery

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_iiSFOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies cardinality-constrained ridge logistic regression and combines conditional screening with GPU-batched branch-and-bound.

The screening analysis follows a conditional greedy path. Under the stated population assumptions, the theorem controls how many competitive irrelevant variables may enter before the ridge-population support has been covered.

For optimization, each branch-and-bound node uses a masked ridge-logistic relaxation. An unfinished continuous solve can still provide a lower bound through its masked gradient residual and strong convexity. Related node problems are evaluated jointly on a GPU.

The experiments include a synthetic support-recovery study and optimization results on Myocardial Infarction Complications and Madelon. Larger Gisette and TCGA experiments are included in the appendix.

The theoretical construction is careful in several places. The main uncertainty is whether the experimental use of “exact” and the reported CPU–GPU gains match the narrower guarantees established by the analysis.

Critical strengths

The paper clearly separates statistical screening from deterministic branch-and-bound certification. Conditional scores can improve feasible candidates, but the full search does not rely on the population screening theorem when deciding whether a node can be removed. This is an important design choice.

The residual-based node bound is another strong aspect. The current objective value of an unfinished solver is not incorrectly treated as a lower bound. Instead, the paper corrects it using the masked gradient residual and the strong-convexity parameter.

The screening experiment also illustrates a setting where conditioning matters. In the correlated suppressor example, the conditional method reaches the generating support much earlier than SIS, whereas the difference is small in the independent design.

GPU batching is well motivated by the repeated algebra in the node relaxations. The same design matrix is reused across many masked problems, and Figure 3 shows a substantial runtime advantage once the batch size is large enough.

Critical weaknesses

The first concern is how the experimental solver gaps should be interpreted. Proposition 3 gives the residual lower bound for exact real-valued arithmetic. Appendix E then discusses the additional numerical control needed before the same statement can be treated as a machine-level certificate. In particular, ordinary double-precision evaluation is not sufficient by itself. The experiments report GPU bound gaps, including values rounded to 0.00%, but the manuscript does not indicate that verified rounding or an explicit numerical-error enclosure is used in those runs. If the implementation evaluates the bound using ordinary CuPy arithmetic, the reported gap is still useful as a numerical optimization result, but it should be distinguished from a formally verified floating-point certificate.

The pre-screened experiments have a different certification issue. Full branch-and-bound searches the original feature set, whereas the pre-screened variant first retains only MkMk features and then solves that smaller problem. A zero gap after this reduction certifies the reduced problem. It does not by itself certify the original pp-feature problem. The screening theorem does not close this gap because its target is the support of the population ridge-risk minimizer under assumptions (D1)–(D4), rather than the optimizer of the finite-sample cardinality-constrained problem in Equation (1). In several experiments the screened set preserves the best upper bound found by the full solver, which is reassuring empirically, but this observation should not be presented as a full-space certificate. The table would be clearer if the screened-subproblem gap were labelled separately from the full-feature bound gap.

The CPU–GPU end-to-end comparison also changes the branching strategy. The CPU implementation uses a largest-coefficient rule, while the GPU implementation evaluates candidate exclusions before choosing a branch. These two searches can visit very different trees. The terminal-gap difference therefore mixes two effects: faster batched continuous solves and a different branching policy. A cleaner comparison would keep the branching rule fixed across CPU and GPU. A second run with candidate-branch evaluation on CPU, or with the largest-coefficient rule on GPU, would help show how much of the reported improvement comes from the search strategy.

Hardware details further complicate the runtime comparison. The GPU side uses an NVIDIA RTX 6000, while the CPU runs are described through the PACE cpu-small environment. The main text does not make the CPU core count, threading policy, BLAS backend, or solver thread configuration easy to recover. It is also not fully clear whether all reported timings include setup work such as initialization, transfers, synchronization, and branch-candidate evaluation. Since runtime is central to the empirical contribution, these details should be stated explicitly.

The scalability picture is mixed. Myocardial with p=111p=111 is the strongest result: GPU B&B reaches gaps rounded to 0.00% for k=4k=4 and k=6k=6, and 0.01% for k=8k=8. Madelon is already much harder, with GPU terminal gaps between 12.61% and 19.82% after 1000 seconds. On Gisette with p=5000p=5000, the reported GPU gaps are 83.74–96.02%, and the TCGA runs remain around 97–99%. These larger experiments show improved optimization progress within a fixed budget, but they do not yet demonstrate practically scalable exact solution of the full-feature problems.

This is also where the role of pre-screening becomes important. The large speedups often appear after aggressive feature reduction, but that variant no longer has the same full-feature certification status unless the discarded variables can be ruled out safely for the finite-sample optimization problem. The practical method may therefore be very useful as a heuristic-plus-certification pipeline on a reduced space, but that is a different statement from scalable exact optimization over all original features.

The screening theorem itself depends on a strong uniform condition. Assumption (D3) requires one common set of competitive irrelevant variables to work over all admissible active sets along the greedy path. MnM_n is also defined through population weighted-Hessian quantities that are not directly available from the observed sample. The theorem is coherent under these assumptions, but the paper gives limited evidence about how demanding they are beyond the constructed synthetic settings. A broader simulation varying correlation structure and competitor strength would help show when the theoretical regime is realistic.

There is also some distance between the statistical target and the optimization target. Section 2 studies the sparse support S⋆S^\star of the population ridge minimizer. Branch-and-bound later solves the empirical cardinality-constrained problem using a sparsity budget specified for that optimization problem. The manuscript acknowledges this distinction, and the full solver is correctly designed so that the screening theorem is not needed for pruning. This makes conditional screening primarily an incumbent-construction device. The pre-screening experiments should preserve that interpretation and avoid suggesting that the population result automatically justifies permanent feature removal for Equation (1).

The comparison with closely related GPU sparse-optimization methods is limited. Related Work cites recent approaches that batch branch-and-bound nodes for sparse GLMs and other GPU methods for certifying sparse models. These methods are closer to the proposed computational contribution than the CPU B&B and MOSEK baselines used in the experiments. A direct comparison may be difficult if implementations are unavailable, but without one it remains hard to place the practical contribution relative to the nearest GPU alternatives.

The masked relaxation may also contribute to the large gaps on difficult datasets. At nonterminal nodes, the remaining cardinality restriction is dropped, producing a relaxation that is cheap to solve but potentially loose. The Gisette and TCGA results make this trade-off worth examining directly. The paper already discusses stronger big-MM and perspective relaxations, so a small comparison of bound quality and wall-clock cost would help show why the proposed masked relaxation is the right choice.

Questions for authors

Does the released GPU code use verified rounding, interval arithmetic, or another explicit numerical-error enclosure when evaluating the reported bounds?

If not, should the 0.00% entries be interpreted as numerical optimization gaps rather than machine-verified certificates?

For the pre-screened experiments, does the lower bound refer to the original feature space or only to the retained MkMk variables?

Is there a result establishing that the pre-screened set contains the optimizer of the finite-sample problem in Equation (1)?

Can CPU B&B be evaluated using the candidate-branch rule employed by GPU B&B?

What happens when GPU B&B instead uses the CPU largest-coefficient rule?

Please report the CPU hardware and threading configuration used for the runtime experiments, including the settings used by MOSEK.

Which costs are included in the reported GPU wall-clock times? In particular, are setup, data movement, synchronization, and branch-candidate evaluation counted?

Can one of the closest GPU sparse-GLM optimization methods cited in Related Work be included as an experimental reference?

How sensitive is the screening result to violations of the common-competition-set assumption (D3)?

Can the masked relaxation be compared with a stronger relaxation under a matched wall-clock budget?

For Gisette and TCGA, is the intended claim improved optimization progress under a cutoff rather than practical exact solution of the full problem?

Reviewer_VnsGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies cardinality-constrained ridge logistic regression and proposes two main components: (i) a GPU-accelerated branch-and-bound framework that batches masked ridge-logistic subproblems and derives valid lower bounds from residuals of inexact solves, and (ii) a conditional greedy screening analysis that provides a finite-sample support-containment guarantee while allowing a bounded number of irrelevant selections. The optimization and screening components are deliberately separated: screening is used to construct good feasible solutions, while deterministic lower bounds provide global certification. Experiments demonstrate an advantage of conditional over marginal screening in a synthetic suppressor setting and faster batched subproblem evaluation on GPU, with mixed end-to-end exact optimization results across datasets.

Critical strengths
  1. Careful handling of inexact optimization within branch-and-bound. The paper correctly distinguishes an approximate primal objective from a valid node lower bound and uses strong convexity to obtain a residual-corrected certificate. The global lower-bound bookkeeping is also explicitly specified. This is important because using unfinished continuous solves naively could invalidate pruning.

  2. Clear separation of screening from certification. The conditional screening result addresses settings where relevant variables can become detectable only after conditioning, and the paper is careful not to use this statistical result as an unsafe pruning rule. The synthetic suppressor example provides a useful illustration of the difference from marginal screening.

Critical weaknesses
  1. The empirical evidence for scalable exact optimization is substantially weaker than the headline motivation. On the full problem, the GPU method obtains essentially closed gaps for the smaller Myocardial instances, but all Madelon runs remain at substantial gaps after the 1000-second cutoff. The larger Gisette and TCGA experiments in the appendix have very large remaining gaps. In contrast, the extremely fast 0.00% gaps reported for pre-screened problems certify optimization only over the reduced candidate set unless an additional safe-screening argument is available. This matters because the paper itself explicitly separates conditional screening from the deterministic machinery used for exact certification of the full problem. Consequently, the current evidence demonstrates useful GPU acceleration of the search, but does not yet convincingly establish scalability of exact sparse logistic regression on the larger instances.

  2. The experiments do not cleanly establish the advantage over the closest exact sparse-GLM methods or isolate the source of the observed speedup. In particular, the CPU and GPU B&B implementations use different branching strategies, so the end-to-end comparison changes both the continuous solver and the search policy. Moreover, the paper cites very closely related recent work on first-order certification and GPU-batched branch-and-bound for sparse GLMs, but does not provide an end-to-end comparison against these methods. Given the substantial overlap in problem setting and GPU/B&B motivation, a matched comparison or ablation seems important for establishing the practical significance of the proposed method.

Questions for authors
  1. Clarification that could materially affect my assessment: Are the 0.00% gaps of the pre-screened variants certificates for the original full-feature problem, or only for the reduced problem after screening? If they are only reduced-problem gaps, can the authors provide a valid full-problem lower bound or a safe-screening result that justifies interpreting these runs as globally exact?

  2. Comparison/ablation that could materially affect my assessment: Can the authors provide either an end-to-end comparison with the closest recent exact sparse-GLM methods, particularly the perspective-relaxation and GPU-batched B&B approaches cited in the paper, or an ablation in which the CPU and GPU implementations use the same branching/search policy? This would help determine how much of the observed improvement is attributable specifically to GPU batching.

  3. Clarification on the screening theory: Can the authors verify or quantitatively bound the competition-set quantity MnM_n (or the assumptions controlling it) for the correlated suppressor experiment or another nontrivial correlated model representative of the experiments? The appendix verifies that the generating support equals the ridge-population target in the suppressor example, but it is less clear to me how the path-uniform competition condition underlying the theorem is instantiated there. This would help assess how informative the theoretical guarantee is beyond the stated sufficient conditions.

Reviewer_tCJvOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies ridge logistic regression with at most kk selected features. It combines conditional greedy screening with branch-and-bound search by refitting the model after each selection to reveal signals hidden by correlated features. The branch-and-bound search utilizes GPU to solve continuous subproblems and uses gradient residuals to obtain valid lower bounds even when those subproblems have not fully converged. Under stated statistical conditions, the screening path contains the full support of the population ridge solution within k+Mnk+M_n selections with probability at least 1−δ1-\delta, allowing up to MnM_n irrelevant selections along the way.

The experiments examine the effectiveness of screening methods, the runtime of batch subproblems, and the optimization progress of the entire search. In correlated suppressor design, conditional screening typically covers the target support faster than univariate screening. In designs with independent features, both perform similarly. The GPU solver runs faster on medium and large batches and achieves a smaller termination optimality gap than the CPU baselines in every reported setting. However, significant gaps remain at the time limit for more difficult or larger problems. Pre-screening can shorten search time, but its optimality conclusions only apply to the retained features.

Critical strengths

1: Under stated assumptions, the paper proves that the conditional greedy screening procedure includes all target features after a bounded number of selections with high probability. Its analysis covers the adaptive selection path, permits signals that become detectable only after conditioning, and allows a bounded number of competitive irrelevant selections. In the synthetic correlated feature experiment, conditional screening contains all target features after fewer selections than marginal screening.

2: The paper uses strong convexity and gradient residuals to turn approximate solutions of masked ridge-logistic problems into valid branch-and-bound lower bounds. This prevents premature pruning based on an unfinished solve and lets the search report a global optimality gap while using faster, inexact continuous optimization.

Critical weaknesses
  1. When fewer than k features have been included, the node relaxation can use every feature that has not been excluded. Including another feature therefore does not strengthen this bound until the budget is filled. This can leave the bound far below the best feasible objective and require more nodes to be explored. The full feature experiments report gaps rounded to 0.00% for Myocardial at k=4,6, but a 0.01% gap at k=8 and substantially larger gaps on the higher-dimensional datasets. The paper does not show whether the lower cost of its masked solves offsets a potentially larger search tree. A comparison with a tighter perspective relaxation, such as the approach of Scalable First-order Method for Certifying Optimal k-Sparse GLMs (Liu et al., 2025), would clarify this tradeoff.

  2. The CPU and GPU branch-and-bound implementations use different branching rules, so their results cannot be attributed to hardware alone. Figure 3 shows faster GPU batch solves at moderate and large batch sizes, but compares different solvers and does not establish which batch sizes occur in the full search. In Algorithm 1, a node has at most k−∣F+∣k-|F^+| candidate exclusions to evaluate together. The optimization experiments also omit settings needed to interpret the comparisons, including the stopping tolerances, the percentage gap formula, details of the end-to-end MOSEK baseline, and the CPU configuration and threading.

  3. The zero gap of pre-screened experiments in Table1 means it is the best solution for those retained features. However there is no theoretical guarantee that it is also the best solution for all original features. The screening theorem does not establish this missing guarantee. It studies the features used by a population ridge model. The optimization experiments seek the best model with at most kk features on a given dataset. These two models can use different features. For Myocardial at k=4k=4, the lower bounds for some pre-screened runs are above 0.6271. The full feature search found a feasible solution with value 0.6271. Those retained feature sets therefore cannot contain an optimum of the full problem. The paper should state clearly that the pre-screened experiments only guarantee the optimality on reduced problems.

  4. Closely related methods have already studied GPU-accelerated branch-and-bound for sparse GLMs, such as Liu & Lodi (2026) and Liu et al. (2026). Although these works are cited, the paper does not compare against them. It is unclear what advantages the proposed framework provides over these existing methods, especially given its weaker masked relaxation.

Questions for authors
  1. What values of λ\lambda, the global stopping tolerance ϵ\epsilon, and the subproblem gradient tolerances were used in Tables 1 and 3? In the full GPU search, what batch sizes were used, and how was runtime divided among GPU solves, CPU search management, and data transfers?

  2. If the CPU and GPU implementations use the same branching and feasible-solution rules, how much of the performance difference remains? How would a perspective node relaxation change bound quality, node counts, time per node, and total runtime on the same problems?

  3. How were the pre-screening multipliers chosen for each dataset? Is there evidence that the retained features contain an optimum of the original problem?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.