- 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 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 -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 is the strongest result: GPU B&B reaches gaps rounded to 0.00% for and , and 0.01% for . Madelon is already much harder, with GPU terminal gaps between 12.61% and 19.82% after 1000 seconds. On Gisette with , 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. 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 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- 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 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?