Abstract:We study ergodic primal-dual gap rates for first-order primal-dual methods applied to \[
\min_x f(x)+g(x)+h(Ax), \] where $f$ is smooth and convex, $g$ and $h$ are proper, closed, convex functions, and $A$ is linear. Standard gap-rate proofs often impose the halved smooth-stepsize condition $\tau \le 1/L$, even though the corresponding convergence theory allows the larger range $\tau <2/L$. We introduce a residual-to-gap transfer principle: positive residual terms in the one-step gap inequality are controlled by the decrease of a Lyapunov function. This yields $O(1/K)$ ergodic primal-dual gap bounds with the unhalved primal stepsize $\tau <2/L$ for Condat--Vũ, PD3O, AFBA/PDDY, and PAPC/PDFP$^2$O, under their algorithm-dependent product conditions. We also give a two-dimensional counterexample showing that the fully separated rectangle $\tau <2/L$, $\tau\eta\|A\|^2<4/3$ cannot hold in the general three-function setting.
From: Sirong Dai [view email]
[v1]
Fri, 19 Jun 2026 14:34:11 UTC (14 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。