GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal \(k\)-sparse GLMs¶

会议: ICML2025
arXiv: 2603.01306
代码: 待确认
领域: 其他
关键词: 稀疏GLM, 透视松弛, 分支定界, 线性收敛, GPU加速, 对偶间隙重启, 近端方法

一句话总结¶

提出GPU友好的线性收敛一阶方法，通过复合重构+对偶间隙重启策略，将透视松弛求解加速1-2个数量级，实现大规模稀疏GLM的最优性认证。

研究背景与动机¶

稀疏GLM是机器学习和统计中的核心工具，广泛应用于医疗、金融等高风险场景，需要可认证的全局最优解而非近似解
问题本质是NP-hard的\(\ell_0\)约束优化，标准方法是分支定界(BnB)框架
BnB的核心瓶颈在于每个节点的下界计算：标准big-M松弛过松，透视松弛(perspective relaxation)更紧但求解代价高
内点法(IPM)求解透视松弛有立方复杂度且无法GPU并行、不能warm-start
现有一阶方法（ADMM、坐标下降）存在两个问题：
1. 收敛速度仅为次线性，且安全下界的收敛率缺乏理论保证
2. ADMM需解线性系统、坐标下降本质串行，均不适合GPU

方法详解¶

1. 复合重构¶

将透视松弛重构为无约束复合优化问题：

\[\inf_{\boldsymbol{\beta} \in \mathbb{R}^p} \left\{ \Phi(\boldsymbol{\beta}) := F(\boldsymbol{X}\boldsymbol{\beta}) + G(\boldsymbol{\beta}) \right\}\]

其中 \(F(\boldsymbol{X}\boldsymbol{\beta}) = f(\boldsymbol{X}\boldsymbol{\beta}, \boldsymbol{y})\) 为损失函数，\(G(\boldsymbol{\beta}) = 2\lambda_2 g_{\mathcal{N}}(\boldsymbol{\beta})\) 为隐式透视正则项。关键在于定义隐式正则函数：

\[g_{\mathcal{N}}(\boldsymbol{\beta}) := \inf_{\boldsymbol{z}} \left\{ \frac{1}{2}\sum_{j} \beta_j^2 / z_j : (\boldsymbol{\beta}, \boldsymbol{z}) \in \mathcal{D} \right\}\]

将透视项 \(\beta_j^2/z_j\) 和基数/分支约束统一编码进正则器。

2. 几何分析：原始二次增长 + 对偶二次衰减¶

在正则条件（Firm convexity、多面体次微分）下证明关键几何性质：

原始二次增长：\(\Phi(\boldsymbol{\beta}) \geq \Phi^\star + \frac{\alpha}{2}\text{dist}^2(\boldsymbol{\beta}, \mathcal{B}^\star)\)
对偶二次衰减（本文首次提出）：\(-\Psi(\boldsymbol{\zeta}) \leq -\Psi^\star + \frac{\kappa}{2}\|\boldsymbol{\zeta} - \boldsymbol{\zeta}^\star\|^2\)

二者形成对称关系。进一步证明原始最优性间隙严格控制对偶误差：

\[\frac{\sigma}{2}\|\boldsymbol{\zeta} - \boldsymbol{\zeta}^\star\|^2 \leq \Phi(\boldsymbol{\beta}) - \Phi^\star, \quad \Psi^\star - \Psi(\boldsymbol{\zeta}) \leq \frac{\kappa}{\sigma}(\Phi(\boldsymbol{\beta}) - \Phi^\star)\]

3. 对偶间隙重启方案¶

基于Fenchel对偶间隙 \(\Delta(\boldsymbol{\beta}, \boldsymbol{\zeta}) = \Phi(\boldsymbol{\beta}) - \Psi(\boldsymbol{\zeta})\) 设计重启策略：

每次从当前迭代重启FISTA等加速方法
当对偶间隙下降到阈值时触发重启
将次线性 \(O(1/k^2)\) 的加速方法升级为线性收敛
适用于固定步长、线搜索、无线搜索等多种近端方法变体
该框架具有通用性，不局限于稀疏GLM

4. 高效GPU实现¶

针对隐式透视正则器：

证明其函数值和近端算子均可在 \(O(p \log p)\) 时间精确计算（排序+阈值）
避免了昂贵的锥规划求解器
每次迭代的主要计算量为矩阵-向量乘法 \(\boldsymbol{X}\boldsymbol{\beta}\) 和 \(\boldsymbol{X}^\top\boldsymbol{\zeta}\)，天然适合GPU并行

实验关键数据¶

实验设置	对比方法	本文方法加速比
合成数据 CPU 下界计算	IPM / ADMM / CD	1-2个数量级
真实数据 CPU 下界计算	IPM / ADMM / CD	1-2个数量级
GPU vs CPU（本文方法）	本文CPU版本	额外1个数量级
大规模BnB认证	标准求解器	BnB可扩展性显著提升

在合成和真实数据集上均验证了对偶下界的快速收敛
GPU加速使得在大规模实例上BnB认证成为可行
安全下界的线性收敛率在实验中与理论预测一致

亮点与洞察¶

对偶二次衰减概念的首次提出，揭示了原始-对偶几何的对称性结构
对偶间隙重启是通用框架，可将任意次线性近端方法升级为线性收敛，适用范围远超稀疏GLM
隐式透视正则器的 \(O(p\log p)\) 精确求解避免了通用锥求解器，是GPU友好性的关键
从理论到工程的完整闭环：几何分析→收敛保证→高效实现→GPU加速→BnB集成
与FDPG的对比：FDPG从对偶出发仅得次线性原始收敛，本文从原始出发实现双线性收敛

局限与展望¶

几何正则条件（Firm convexity等）在某些非标准损失函数下可能不满足，适用范围有限制
线性收敛的常数 \(\alpha, \kappa, \sigma\) 依赖于具体问题结构，理论界可能不紧
实验主要集中在稀疏线性/逻辑回归，更复杂的GLM（如泊松回归）的表现未充分验证
GPU实现依赖矩阵 \(\boldsymbol{X}\) 可完整加载到GPU显存，对于超大规模特征可能受限
BnB框架中的分支策略仍使用标准方案，与一阶方法的联合优化有进一步空间

评分¶

新颖性: ⭐⭐⭐⭐ — 对偶二次衰减和间隙重启框架有理论原创性
实验充分度: ⭐⭐⭐⭐ — 合成+真实+GPU+BnB多维度验证
写作质量: ⭐⭐⭐⭐⭐ — 数学严谨、结构清晰、动机阐述充分
价值: ⭐⭐⭐⭐ — 为大规模稀疏优化的最优性认证提供了实用且有理论保证的方案