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 propose a unified proximal first-order algorithmic framework that is both linearly convergent and computationally efficient. We first develop a general theory for composite optimization problems satisfying specific geometric regularity conditions.

By establishing a rigorous link between primal quadratic growth and dual quadratic decay, we derive novel error bounds showing that the computable duality gap can serve as a tight proxy for the distance to the solution set. Leveraging this property, we design a restart scheme that upgrades generic sublinear algorithms to achieve provable linear convergence for both primal and dual objectives. We then instantiate this framework for the perspective relaxation of sparse GLMs.

We prove that standard GLM loss functions and the implicit perspective regularizer satisfy the required geometric conditions. Furthermore, we develop specialized algorithms to evaluate the non-smooth regularizer and its proximal operator exactly in log-linear time, avoiding the high cost of generic conic solvers. Extensive experiments on synthetic and real-world datasets demonstrate that our approach leverages GPU acceleration to speed up dual bound computations by orders of magnitude, significantly enhancing the capability of BnB to certify optimality for large-scale problems.