Research map / Learning theory and algorithms / Matrix and tensor methods
Scalable First-order Method for Certifying Optimal k-Sparse GLMs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a restarted FISTA with an exact log-linear PAVA-based proximal operator to solve the perspective relaxation of cardinality-constrained GLMs, providing fast safe lower bounds for branch-and-bound certification of optimal k-sparse GLMs.
Problem
Certifying optimality for sparse GLMs with an l0 cardinality constraint requires tight dual lower bounds at each branch-and-bound node, but existing bound computations (IPM, ADMM, MIP solvers) are too expensive or converge slowly at large scale.
Approach
Reformulate the perspective relaxation as an unconstrained convex composite problem with the implicit function g (conjugate TopSum_k of Huber losses), compute its proximal operator exactly via a customized PAVA in O(p log p), and accelerate FISTA with a function-value restart that uses an exact O(p + p log k) evaluation of g.
Key results
- Certifies optimality on synthetic n=16k, p=16k linear regression in 79 s with 0.0% gap, while Gurobi and MOSEK hit the 1800 s limit.
- Proximal operator evaluation for p=10^5 takes about 0.01 s, roughly two orders of magnitude faster than SOCP solvers.
- On DOROTHEA (n=2300, p=89989) logistic regression, certifies optimality in 230 s versus MOSEK 1814 s with 0.63% gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed method instead of Gurobi | Branch-and-bound certification for synthetic linear regression · Synthetic linear regression (n=16k, p=16k, k=10, M=2) | time (s): 1800 -> 79 | Helped |
| use the proposed method instead of MOSEK | Branch-and-bound certification for synthetic linear regression · Synthetic linear regression (n=16k, p=16k, k=10, M=2) | time (s): 1915 -> 79 | Helped |
| use the proposed method instead of MOSEK | Branch-and-bound certification for Cancer Drug Response · Cancer Drug Response (n=822, p=2300, k=5, M=5) | time (s): 188 -> 41 | Helped |
| use the proposed method instead of Gurobi | Branch-and-bound certification for Cancer Drug Response · Cancer Drug Response (n=822, p=2300, k=5, M=5) | opt. gap (%): 0.89 -> 0.0 | Helped |
| use the proposed method instead of MOSEK | Branch-and-bound certification for synthetic logistic regression · Synthetic logistic regression (n=16k, p=16k, k=10, M=2) | time (s): 2446 -> 626 | Helped |
| use the proposed method instead of MOSEK | Branch-and-bound certification for DOROTHEA logistic regression · DOROTHEA (n=2300, p=89989, k=10, M=2) | time (s): 1814 -> 230 | Helped |
| use the proposed method instead of MOSEK | Branch-and-bound certification for DOROTHEA logistic regression · DOROTHEA (n=2300, p=89989, k=10, M=2) | opt. gap (%): 0.63 -> 0.0 | Helped |
| use the GPU implementation instead of CPU | Proposed method on linear regression · Linear regression (p=1k) | running time (s): 0.19 -> 0.29 | Hurt |
| use the GPU implementation instead of CPU | Proposed method on linear regression · Linear regression (p=2k) | running time (s): 0.48 -> 0.19 | Helped |
| use the GPU implementation instead of CPU | Proposed method on linear regression · Linear regression (p=4k) | running time (s): 1.54 -> 0.26 | Helped |
| use the GPU implementation instead of CPU | Proposed method on linear regression · Linear regression (p=8k) | running time (s): 4.80 -> 0.59 | Helped |
| use the GPU implementation instead of CPU | Proposed method on linear regression · Linear regression (p=16k) | running time (s): 19.52 -> 2.09 | Helped |
Limitations
- Lower bound quality depends on the perspective relaxation, which does not account for the loss term in the convex hull
- Certification experiments use a minimalist BnB without cutting planes or presolve
- Restart-induced linear convergence is empirical rather than proven
Experimental setup
Datasets: synthetic linear regression data synthetic logistic regression data Cancer Drug Response DOROTHEA
Benchmarks: Cancer Drug Response DOROTHEA synthetic linear and logistic regression
Metrics: running time (s) optimality gap (%)
Baselines: Gurobi MOSEK SCS Clarabel PGD FISTA
Builds on: FISTA PAVA perspective reformulation function-value restart
Closest papers by meaning
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.88)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.86)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 2025 · similarity 0.86)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.86)
- Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence (ICML 2024 · similarity 0.85)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.