Pith. sign in

REVIEW 3 cited by

Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2206.03041 v2 pith:Q4DLHA5Z submitted 2022-06-07 math.OC

Olivier Fercoq (S2A , IDS , IP Paris) This is my paper · ORCID
classification math.OC
keywords gradienthybridprimal-dualquadraticboundconvergenceerrorlinear
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study the linear convergence of the primal-dual hybrid gradient method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems. Equipped with this tool, we manage to prove tighter convergence rates. Then, we show that averaging and restarting the primal-dual hybrid gradient allows us to leverage better the regularity constant. Numerical experiments on linear and quadratic programs, ridge regression and image denoising illustrate the findings of the paper.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity

    math.OC 2026-08 conditional novelty 6.0 of 10

    PDHCG-CQP is a matrix-free GPU solver that provably converges linearly under strict complementarity for conic quadratic programs and scales to 440 million variables on 8 GPUs.

  2. PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation

    math.OC 2025-06 conditional novelty 6.0 of 10

    A restarted primal-dual method with a per-buyer bisection inner solve, run on GPUs, computes Fisher equilibria at ten-million-buyer scale and extends to Arrow-Debreu markets via fixed-point iteration.

  3. An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

    math.OC 2025-06 unverdicted novelty 2.0 of 10

    A survey of GPU-based first-order LP solvers focusing on cuPDLP, its PDHG core, theory, benchmarks, and extensions to QP, SDP, and conic programming.

Pith tools