arXiv:2605.22188cs.LGmath.OC2026-05

用批量处理提升稀疏GLM优化速度,实现零误差最优解。

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

论文配图:From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs
图 1 · 摘自论文原文
  • GPU批量处理分支定界节点,避免串行计算
  • 实测提速10~100倍,且保证解的最优性
  • 适合需要精确解和变量重要性分析的场景

GPU显著加速了大规模连续优化中的梯度类方法,但在含离散变量、组合结构和非线性目标的问题中表现不佳,例如对稀疏广义线性模型进行最优性验证。主要挑战在于分支定界(BnB)中异构节点的串行处理以及频繁的CPU-GPU数据交换。本文提出一种简单、通用且模块化的CPU-GPU框架,可在GPU上批量处理多个BnB节点。该框架基于少量高效的GPU操作,结合填充与轻量级自定义核函数,解决节点数据结构不规则的问题。实验表明,在复杂实例上可实现1到2个数量级的速度提升,且保持零最优性差距。该框架还可扩展用于收集完整的Rashomon集,支持下游统计分析,如变量重要性评估及基于用户特定指标(如分类任务中的AUC)的模型选择。

原文摘要 · Abstract (English)

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).

稀疏建模分支定界GPU加速最优性验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。