Source-linked AI summary
A first-order primal-dual algorithm with linesearch
Yura Malitsky, Thomas Pock
TL;DR
The paper addresses the need for practical stepsize selection in primal-dual methods without evaluating operator norms or adding expensive computations. It proposes linesearch-based primal-dual algorithms, proves convergence and improved rates under strong convexity, and extends the approach to problems with a smooth term. The methods avoid additional matrix-vector multiplications in important cases, although extensions such as inertial or relaxed variants remain nontrivial.
Problem
Primal-dual methods require operator-norm or Lipschitz-constant information that can be expensive or conservative, motivating practical linesearch procedures.
Method
The paper develops primal-dual algorithms with linesearch, including variants for strongly convex prox-functions and saddle-point problems with an additional smooth term.
Results
The proposed methods converge, achieve an ergodic O(1/N) rate, and under strong convexity obtain O(1/N^2) primal-dual gap bounds.
Takeaways & Limitations
The linesearch avoids evaluating operator norms and can permit larger steps without additional matrix-vector multiplications in many important cases.
Takeaways & Limitations
Deriving inertial or relaxed extensions still requires nontrivial effort, and the smooth-term extension additionally requires knowledge of the gradient Lipschitz constant.
Abstract
from arXiv · showhide
The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic $O(1/N)$ rate of convergence for our method. In case one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.
1 Preliminaries
The paper sets up a finite-dimensional primal-dual framework with convex functions, a bounded linear operator, saddle points, and proximal updates. It recalls the primal-dual gap and introduces the linesearch-based algorithm under standard convergence assumptions.
- Problem setting: The framework uses proper lower semicontinuous convex functions g and f*, together with a bounded linear operator K.The operator norm is L = ∥K∥, and K* denotes its adjoint.
- Problem setting: The primal-dual formulation is assumed to have a saddle point, linking the primal and dual problems.The saddle point yields nonnegative primal and dual residual expressions.
- Proximal tools: The proximal operator is characterized through an inequality involving the function values and inner products.The paper also records the cosine-rule identity used in subsequent analysis.
- Optimality measure: The primal-dual gap G(x,y) combines primal and dual residuals and is convex in both variables for a fixed saddle point.It is defined as G = P + D.
- Algorithmic setup: The proposed primal-dual linesearch algorithm updates the primal variable by a proximal step and adjusts the stepsize through extrapolation and a linesearch condition.Its initialization uses x0, y1, τ0, μ, δ, β, and θ0 = 1.
- Algorithmic setup: The original method converges under θ = 1, positive τ and σ, and the condition τσL^2 < 1.The paper introduces the linesearch to incorporate adaptive steps into this primal-dual scheme.
2 Linesearch
PDAL incorporates an adaptive linesearch that updates one variable during inner iterations, preserves convergence guarantees, and often keeps per-iteration cost close to PDA while avoiding prior knowledge of operator norms.
- Linesearch design: PDAL chooses primal and dual step sizes through a linesearch that can start from either the largest allowed step or the previous step.The method also permits compromise choices between these strategies and can use fixed steps, in which case it coincides with PDA.
- Linesearch design: Each linesearch iteration updates only the dual variable, while the primal and dual roles can be exchanged to select the simpler proximal operator.During the linesearch, Kxk is computed once and reused through the extrapolated quantity Kx̄k.
- Computational cost: For regularized least squares, the method avoids knowing ∥A∥ and requires no additional matrix-vector multiplication compared with standard backtracking methods.For the listed affine-proximal cases, PDAL uses two matrix-vector multiplications per iteration, reusing prior products; sparse operators can alter the cost comparison.
- Linesearch guarantees: The linesearch always terminates, and the step sizes remain bounded away from zero while θk remains bounded above.These properties support the convergence analysis and prevent indefinite inner-loop reduction.
- Convergence: PDAL converges to a saddle-point solution under the stated assumptions, with whole-sequence convergence when g restricted to its domain is continuous and step sizes are bounded above.The paper notes that these continuity conditions cover several common function classes.
- Convergence: The ergodic sequence achieves the same O(1/N) convergence rate as earlier methods, although it is defined differently.The rate is established through the weighted ergodic sequence used in the theorem.
- Limitations: A limitation is that deriving inertial or relaxed extensions still requires nontrivial effort because the proof does not rely on PDA’s proximal interpretation.The paper identifies a need for a more general approach to the method and its extensions.
3 Acceleration
The paper accelerates PDAL when the primal or dual objective is strongly convex, obtaining improved convergence rates while retaining comparable per-iteration complexity. The resulting guarantees include O(1/N) iterate convergence and O(1/N^2) ergodic gap rates.
- Acceleration: Strong convexity of g or f* enables accelerated variants of the primal-dual linesearch method.The corresponding algorithms modify the linesearch and, in the accelerated variant, vary β at every iteration.
- g is strongly convex: For the g-strongly-convex accelerated method, convergence of the dual sequence cannot be proved, so δ is set to 1.
- g is strongly convex: The g-strongly-convex variant achieves ||x_N − x̂|| = O(1/N) and G(X_N, Y_N) = O(1/N^2).
- f* is strongly convex: The f*-strongly-convex variant achieves ||y_N − ŷ|| = O(1/N) and G(X_N, Y_N) = O(1/N^2).
- Both objectives strongly convex: When both g and f* are strongly convex, the paper notes that Algorithms 2 and 3 can be combined into a new accelerated algorithm.
4 A more general problem
The paper extends the primal-dual linesearch to saddle-point problems containing an additional smooth convex term with Lipschitz-continuous gradient. The generalized scheme avoids requiring the gradient’s Lipschitz constant and is shown to converge under the stated assumptions.
- Problem and assumptions: The generalized problem adds a smooth convex function h with an L_h-Lipschitz-continuous gradient.
- Motivation: The generalized linesearch is introduced because knowing the operator norm and L_h can be expensive or conservative, while local information may permit larger steps.
- Generalized linesearch: The new scheme combines the original linesearch stopping criterion with the descent lemma for smooth functions.
- Generalized linesearch: When h is identically zero, Algorithm 4 reduces exactly to Algorithm 1.
- Convergence: Under the stated assumptions, convergence of the primal and dual sequences to a saddle point follows similarly to the basic method.
5 Numerical Experiments
The numerical section evaluates PDA, PDAL, accelerated variants, and comparison methods on matrix games and regularized least-squares problems. The experiments report convergence against CPU time and highlight that the linesearch can avoid extra matrix-vector multiplications in relevant least-squares cases.
- Test problems: The experiments evaluate the proposed methods on matrix games, l1-regularized least squares, and another regularized least-squares problem.
- Matrix game: For matrix games, performance is compared using the primal-dual gap G(x_k, y_k) plotted against CPU time.
- l1-regularized least squares: In the regularized least-squares formulation, the proximal operator is affine, so the linesearch requires no additional matrix-vector multiplication.
- l1-regularized least squares: The comparison includes PDA, PDAL, APDA, APDAL, FISTA, and SpaRSA, with predefined step sizes required for methods other than PDAL and SpaRSA.
- l1-regularized least squares: For l1-regularized least squares, convergence is plotted as φ(x_k) − φ* against CPU time, with φ* approximated from a long run.
- Observed performance: The paper notes that non-accelerated methods with a properly chosen σ/τ ratio can sometimes be faster than accelerated variants.
6 Conclusion
The paper presents primal-dual algorithms with linesearch that avoid operator-norm evaluation, can take larger steps, and are numerically efficient without many additional expensive operations.
- The proposed linesearch avoids evaluating the operator norm and allows larger steps.
- In many important cases, the linesearch requires no additional expensive operations such as matrix-vector multiplications or prox-operators.
- The authors prove convergence for all proposed methods.
- Numerical experiments confirm the numerical efficiency of the proposed methods.