[2603.01306] GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs

Mathematics > Optimization and Control arXiv:2603.01306 (math) [Submitted on 1 Mar 2026] Title:GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs Authors:Jiachang Liu, Andrea Lodi, Soroosh Shafiee View a PDF of the paper titled GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs, by Jiachang Liu and 2 other authors View PDF HTML (experimental) Abstract:We investigate the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through a cardinality constraint. While Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations, existing methods for solving these relaxations are computationally intensive, limiting their scalability. To address this challenge, we reformulate the relaxations as composite optimization problems and develop a unified proximal framework that is both linearly convergent and computationally efficient. Under specific geometric regularity conditions, our analysis links primal quadratic growth to dual quadratic decay, yielding error bounds that make the Fenchel duality gap a sharp proxy for progress towards the solution set. This leads to a duality gap-based restart scheme that upgrades a broad class of sublinear proximal methods to provably linearly convergent methods, and applies beyond the sparse GLM setting. For the implicit perspective regularizer, we further derive specialized routines ...