Accelerated primal dual fixed point algorithm
Ya-Nan Zhu · 2025
Read Accelerated primal dual fixed point algorithm by Ya-Nan Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00385.txt.
Introduction
Ya-Nan Zhu proposes APDFP, a faster algorithm for composite optimization problems that mix a smooth term with a nonsmooth term passed through a linear operator. Such problems sit inside logistic regression with graph guidance and CT image reconstruction. The method adds Nesterov-style acceleration, the momentum trick behind many fast gradient methods, to a primal-dual fixed-point scheme with fully decoupled steps.
The payoff is a proved speedup: the partial primal-dual gap now shrinks with the square of the step count rather than linearly, measured against the smooth term's Lipschitz constant. Tests on graph-guided logistic regression and CT reconstruction confirm the theory and show the efficiency gain in practice. The scheme generalizes Nesterov acceleration to settings where the linear operator is not the identity.
Catalog record
| CREATOR | Ya-Nan Zhu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00385
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerated primal dual fixed point algorithm Thanks: Submitted to the editors DATE. Ya-Nan Zhu Abstract This work proposes an Accelerated Primal–Dual Fixed-Point (APDFP) method that employs Nesterov type acceleration to solve composite problems of the form min x f ( x ) + g ∘ B ( x ) \min_{x}\,f(x)+g\circ B(x) , where g g is nonsmooth and B B is a linear operator. The APDFP features fully decoupled iterations and can be regarded as a generalization of Nesterov’s accelerated gradient the setting where the B B can be non identity matrix. Theoretically, we improve the convergence rate of the partial primal-dual gap with respect to the Lipschitz constant of gradient of f f from 𝒪 ( 1 k ) \mathcal{O}(\frac{1}{k}) to 𝒪 ( 1 k 2 ) \mathcal{O}(\frac{1}{k^{2}}) . Numerical experiments on graph-guided logistic regression and CT image reconstruction are conducted to validate the correctness and demonstrate the efficiency of the proposed method. keywords Nesterov acceleration, primal dual fixed point method † † runningheads: Accelerated primal dual fixed point algorithm / Yanan Zhu 1 Introduction. In this work, we consider the following structured convex optimization problem: \min_{x\in\mathbb{R}^{d}}~F(x):=f(x)+g\circ B(x), (1) where f:\mathbb{R}^{d}\to\mathbb{R}\cup\{+\infty\} is a proper smooth convex function with an L_{f} -Lipschitz continuous gradient, g:\mathbb{R}^{r}\to\mathbb{R}\cup\{+\infty\} is a proper, convex, and lower semi-continuous (l.s.c.) function that may notbe differentiable, and B\in\mathbb{R}^{r\times d} is a matrix. The composite nature of the objective function F(x) makes it well-suited for a broad class of applications such as graph-guided fused lasso [ 27 , 44 ] , low-rank matrix completion [ 8 ] , total variation-based image reconstruction [ 42 , 11 , 1 , 20 ] , sparse coding [ 40 , 29 ] , compressed sensing [ 18 , 9 , 10 ] , etc. Given the potentially large-scale nature of problem ( 1 ), efficient optimization methods are essential. In particular, first-order proximal splitting algorithms have gained widespread popularity due to their scalability, simplicity, and strong theoretical guarantees [ 5 , 28 , 17 , 38 ] . These methods are particularly appealing when the proximal operators of f or g (or their Fenchel conjugates) admit closed-form solutions or can be computed efficiently.Over the past decade, considerable progress has been made in designing first-order splitting algorithms for problem ( 1 ). Below, we briefly review some representative algorithms. 1.1 B=I . We now turn to a special case of problem ( 1 ), namely the composite minimization problem \min_{x\in\mathbb{R}^{d}}~F(x):=f(x)+g(x), (2) which corresponds to setting B=I in ( 1 ) . A widely used approach for solving ( 2 ) is the Proximal Gradient Descent (PGD) method, also known as the proximal forward–backward splitting algorithm [ 16 ] . As summarized in Algorithm 1 , PGD updates the iterate by first performing a gradient descent step on f , followed by applying the proximity operator of \gamma g : \mathrm{Prox}_{\gamma g}(s)=\arg\min_{y\in\mathbb{R}^{d}}\left\{\gamma g(y)+\frac{1}{2}\|y-s\|_{2}^{2}\right\}, (3) For the problems we are concern, we assume its proximity operator of g has closed-form solution. Algorithm 1 Proximal Gradient Descent (PGD) 0: Initial point x_{1}\in\mathbb{R}^{d} , step size \gamma_{k}>0 , and maximum iteration number K . 1: for k=1,2,\dots,K do 2: x_{k+1}=\mathrm{Prox}_{\gamma_{k}g}(x_{k}-\gamma_{k}\nabla f(x_{k})) 3: end for 3: x_{K+1} Thanks to its simplicity and scalability, PGD has found widespread applications in large-scale data analysis, signal recovery, and image reconstruction. Theoretically, PGD has \mathcal{O}(1/k) convergence rate in terms of the function value, where k denotes the iteration counter. Nevertheless, in practice PGD often converges slowly, particularly for ill-conditioned problems. This drawback has motivated the development of various acceleration techniques. One of the most influential acceleration methods is the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA, Algorithm 2 ) proposed by Beck and Teboulle [ 6 ] , which is inspired by Nesterov’s seminal work on accelerated gradient methods [ 39 ] . Compared to PGD, FISTA introduces an extrapolation step that leverages both the current and previous iterates. This seemingly simple modification improves the convergence rate of PGD to \mathcal{O}(1/k^{2}) in terms of the function value, which is optimal for smooth convex problems, and has made FISTA one of the most widely adopted first-order methods in large-scale optimization. Algorithm 2 Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) 0: Initial points x_{0}=x_{1}\in\mathbb{R}^{d} , step size \gamma_{k}>0 , and maximum iteration number K . 1: for k=1,2,\dots,K do 2: y_{k}=x_{k}+\frac{k-1}{k+2}(x_{k}-x_{k-1}) 3: x_{k+1}=\mathrm{Prox}_{\gamma_{k}g}(y_{k}-\gamma_{k}\nabla f(y_{k})) 4: end for 4: x_{K+1} In parallel, Nesterov introduced an alternative acceleration framework (Algorithm 3 ), commonly referred to as Nesterov’s Accelerated Gradient (Algorithm 3 )(NAG) [ 35 , 36 , 37 ] . Compared to FISTA, which extrapolates iterates through a single momentum term, NAG maintains two coupled sequences: a primary sequence updated by gradient steps, and an aggregated sequence (the superscript “ag” is used to denote this aggregated sequence) that serves as the search point for gradient evaluation. This sequence construction provides a principled mechanism for generating momentum and yields the optimal \mathcal{O}(1/k^{2}) convergence rate as FISTA. Algorithm 3 Nesterov’s Accelerated Gradient (NAG) 0: Initial point x_{1}=x_{1}^{\text{ag}}\in\mathbb{R}^{d} , parameters \gamma_{k}>0 , and maximum iteration number K . 1: for k=1,2,\dots,K do 2: \theta_{k}=\frac{2}{k+1} 3: x_{k}^{\text{md}}=(1-\theta_{k})x_{k}^{\text{ag}}+\theta_{k}x_{k} 4: x_{k+1}=\mathrm{Prox}_{\frac{\gamma_{k}}{\theta_{k}}g}\left(x_{k}-\frac{\gamma_{k}}{\theta_{k}}\nabla f(x_{k}^{\text{md}})\right) 5: x_{k+1}^{\text{ag}}=(1-\theta_{k})x_{k}^{\text{ag}}+\theta_{k}x_{k+1} 6: end for 6: x_{K+1}^{\text{ag}} 1.2 B\not=I . When the matrix B is not the identity, directly applying above algorithms encounters the difficulty of evaluating the proximal operator of the composite function g\circ B(\cdot) . While the proximity operator of g alone is often admits a closed-form solution, that of the composition g\circ B(\cdot) is generally not easy and typically necessitates a specialized subroutine. In the following, we summarize several existing strategies to circumvent this problem. 1.2.1 Primal Dual Hybrid Gradient. To bypass the annoying matrix B , one can reformulate problem ( 1 ) as the following saddle-point (min-max) problem: \min_{x\in\mathbb{R}^{d}}\max_{y\in Y}~f(x)+\langle Bx,y\rangle-g^{*}(y), (4) where g^{*} denotes the convex conjugate of g , defined on domain Y . (Here, we omit some technical assumptions under which problems ( 1 ) and ( 4 ) are equivalent; interested readers are referred to [ 4 ] for details.) Under this min-max reformulation, the challenge of evaluating the proximity operator of the composite function g\circ B is transformed into computing the proximal operator of g^{*} . Since the proximity operator of g often admits a closed-form expression, the same typically holds for its convex conjugate g^{*} , via the application of the Moreau decomposition [ 4 ] . One of the most widely used algorithms for solving ( 4 ) is the modified Primal-Dual Hybrid Gradient method (PDHGm, Algorithm 4 ) [ 1 , 48 , 20 ] , also known as the Chambolle–Pock algorithm (CP) [ 11 ] . PDHGm proceeds by alternating between evaluating the proximity operators of f and g^{*} , followed by an extrapolation step on the primal variable x . Even though PDHGm circumvents the difficulty associated with the proximity operator of g\circ B , computing the proximity operator of f remains challenging in many practical scenarios. To address this issue, one can exploit the smoothness of f and fully decouple the iterations by linearizing f , i.e., \displaystyle x_{k+1} \displaystyle=\mathrm{Prox}_{\tau_{k}f}(x_{k}-\tau_{k}B^{T}y_{k+1}) (5) \displaystyle=\arg\min_{x\in\mathbb{R}^{d}}~f(x)+\frac{1}{2\tau_{k}}\|x-(x_{k}-\tau_{k}B^{T}y_{k+1})\|_{2}^{2} \displaystyle=\arg\min_{x\in\mathbb{R}^{d}}~f(x)+\langle x,B^{T}y_{k+1}\rangle+\frac{1}{2\tau_{k}}\|x-x_{k}\|_{2}^{2} \displaystyle Linearization \displaystyle\Rightarrow \displaystyle x_{k+1} \displaystyle=\arg\min_{x\in\mathbb{R}^{r}}~f(x_{k})+\langle\nabla f(x_{k}),x-x_{k}\rangle+\frac{1}{2\eta_{k}}\|x-x_{k}\|_{2}^{2}+\langle x,B^{T}y_{k+1}\rangle \displaystyle+\frac{1}{2\tau_{k}}\|x-x_{k}\|_{2}^{2} \displaystyle\Rightarrow x_{k+1} \displaystyle=x_{k}-\gamma_{k}\nabla f(x_{k})-\gamma_{k}B^{T}y_{k+1} where \gamma_{k}=\frac{\eta_{k}\tau_{k}}{\eta_{k}+\tau_{k}} . Algorithm 4 Modified