Source-linked AI summary
Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
Simon S. Du, Wei Hu
TL;DR
The paper asks whether linear convergence is possible without strong convexity in the primal variable. It develops a proof strategy for the primal-dual gradient method and applies it to finite-sum SVRG; linear convergence is established under smoothness, convexity, strong-convexity, and rank assumptions.
Problem
Method
The paper develops a novel proof strategy for the primal-dual gradient method and applies the analysis to primal-dual SVRG for finite-sum problems.
Source: §6 · p. 8Results
The vanilla primal-dual gradient method can converge linearly without strong convexity in the primal variable, and the analysis also establishes linear convergence for finite-sum primal-dual SVRG.
Source: §6 · p. 8Takeaways & Limitations
Linear convergence is possible under the paper’s stated assumptions even when the primal function is not strongly convex.
Source: §1.1 · p. 2The result assumes smooth f and g, convex f, strongly convex g, and a full-column-rank coupling matrix A.
Source: §3 · p. 4
Abstract
from arXiv · showhide
We consider the convex-concave saddle point problem $\min_{x}\max_{y} f(x)+y^\top A x-g(y)$ where $f$ is smooth and convex and $g$ is smooth and strongly convex. We prove that if the coupling matrix $A$ has full column rank, the vanilla primal-dual gradient method can achieve linear convergence even if $f$ is not strongly convex. Our result generalizes previous work which either requires $f$ and $g$ to be quadratic functions or requires proximal mappings for both $f$ and $g$. We adopt a novel analysis technique that in each iteration uses a "ghost" update as a reference, and show that the iterates in the primal-dual gradient method converge to this "ghost" sequence. Using the same technique we further give an analysis for the primal-dual stochastic variance reduced gradient (SVRG) method for convex-concave saddle point problems with a finite-sum structure.
1 Introduction
The paper asks whether the vanilla primal-dual gradient method can converge linearly when only the dual function is strongly convex. It answers affirmatively under stated smoothness, convexity, and coupling-rank conditions, and extends its analysis to finite-sum problems.
1.3 Comparison with Previous Results
- Earlier linear-convergence results without strong convexity in f required quadratic f and g or proximal mappings for both functions, while this paper addresses the general smooth setting.The quadratic analysis relies on a linear dynamic system, whereas the proximal-method analysis relies on proximal mappings.Source: §1 · p. 2, §1.3 · p. 3
1.1 Our Contributions
- When f and g are smooth, f is convex, g is strongly convex, and A has full column rank, the vanilla primal-dual gradient method converges linearly.The result answers the question of linear convergence without strong convexity in the primal variable.Source: §1 · p. 1, §1.1 · p. 2
- A ghost sequence based on a gradient-descent step for the primal problem serves as a reference for showing that the primal-dual iterates remain close to it.The analysis addresses the difficulty that the primal and dual iterate sequences are related.Source: §1.1 · p. 2
- The same analysis technique yields a linear-convergence analysis for primal-dual SVRG on saddle-point problems with finite-sum structure.SVRG uses a full-gradient snapshot and variance-reduced stochastic gradients in its inner loop.Source: §1.1 · p. 2
1.2 Motivating Examples
- Examples of saddle-point applications include robust optimization, policy evaluation, and empirical risk minimization.For policy evaluation, the saddle-point formulation has a finite-sum structure and a gradient that can be computed more efficiently than in the original formulation.Source: §1.2 · pp. 2–3
2 Preliminaries
The preliminaries establish notation and definitions used in the analysis, including smoothness and conjugate functions. They also summarize assumptions used by prior linear-convergence results.
2 Preliminaries
- The paper uses Euclidean norms and inner products, singular values for matrices, gradients for functions, and [n] for the index set.The identity matrix is denoted I_d.Source: §2 · pp. 3–4
- Table 1 compares assumptions sufficient for linear convergence, noting that proximal mappings for f and g remove the need for smoothness.The table concerns primal-dual gradient methods for Problem (1).Source: Table 1 · p. 4
- A differentiable function is β-smooth when its gradient is β-Lipschitz, and the section introduces strong convexity and conjugate-function properties.For smooth, strongly convex functions, the conjugate has properties stated in Fact 2.1.Source: §2 · p. 4
3 Linear Convergence of the Primal-Dual Gradient Method
Under the stated smoothness, convexity, strong-convexity, and full-column-rank conditions, the primal-dual gradient method converges linearly. The proof uses a primal gradient-descent reference and combines primal and dual tracking errors in a geometrically shrinking potential.
3 Linear Convergence of the Primal-Dual Gradient Method
- With f convex and smooth, g smooth and strongly convex, and A full column rank, Algorithm 1 converges to the optimal solution at a linear rate.The proof tracks P_t = λa_t + b_t and shows it shrinks geometrically.Source: §3 · p. 4, §3.1 · p. 6
3.1 Proof of Theorem 3.1
- The proof’s one-step “ghost” update is gradient descent on the primal objective, and the actual primal iterate is compared with this reference.The auxiliary update uses h(x) = g*(Ax) and is defined only for the proof.Source: §3.1 · p. 5
- The primal objective used by the ghost update is smooth and strongly convex, using smoothness of f, strong convexity of g*, and full column rank of A.These properties let the proof apply a linear-convergence bound for gradient descent.Source: §3.1 · p. 5
- The dual tracking error is measured against ∇g*(Ax_t), which decreases geometrically up to an error term as the primal iterate changes.The proof accounts for the change from x_t to x_(t+1) when bounding this error.Source: §3.1 · p. 6
4 Extension to Primal-Dual SVRG
The paper extends primal-dual methods to finite-sum saddle-point problems with an SVRG algorithm that combines snapshot gradients and variance-reduced stochastic updates. Under the stated assumptions, it establishes linear convergence and an SVRG-style running-time bound.
4 Extension to Primal-Dual SVRG
- The analysis assumes a finite-sum structure and conditions on the overall objective, while component functions need only be smooth, not convex.The stated setup also assumes the sum of the component coupling matrices has full column rank.Source: §4 · pp. 6–7
- Each outer loop computes a full gradient at a snapshot, then runs N inner updates using a variance-reduced stochastic gradient.The update combines the sampled gradient with a snapshot correction, keeping the estimate unbiased while reducing variance.Source: §4 · p. 7
- Theorem 4.1 establishes linear convergence of primal-dual SVRG for suitable parameters and epoch length, with Q_t contracting geometrically.The parameter and epoch-length choices are polynomial in β, ρ, M, 1/α, and 1/σ_min(A).Source: §4 · p. 7
- The method reaches an ε-close solution in O((n + N)d log(1/ε)) time, with N independent of n.Each epoch costs O(nd + Nd): one full gradient and N inner iterations.Source: §4 · p. 7
5 Preliminary Empirical Evaluation
The preliminary experiments test batch and SVRG primal-dual methods on smoothed-L1-regularized regression. Both methods show linear convergence; SVRG is faster, while the primal-dual methods remain within a factor of three of their primal counterparts in the reported examples.
5 Preliminary Empirical Evaluation
- The evaluation compares batch-gradient and SVRG methods on smoothed-L1-regularized regression with d = 200 and n = 500.The data-generation cases yield small, medium, and large condition numbers for A.Source: §5 · pp. 7–8, Figure 1 · p. 8, Figure 2 · p. 8
- The smoothed-L1 regularizer is smooth but not strongly convex and has no closed-form proximal mapping.This is the stated setting for the regression experiment.Source: §5 · p. 8
- Both primal-dual methods achieve linear convergence; they are at most 3 times slower than corresponding primal methods, while SVRG is especially faster when the condition number is large.The plots use tuned step sizes to observe optimal convergence rates.Source: §5 · p. 8
6 Conclusion
The vanilla primal-dual gradient method can converge linearly without strong convexity in the primal variable. The paper also applies its proof strategy to primal-dual SVRG for finite-sum saddle-point problems.
6 Conclusion
- The vanilla primal-dual gradient method can achieve linear convergence without strong convexity in the primal variable.Source: §6 · p. 8
- The same proof strategy establishes linear convergence for primal-dual SVRG on finite-sum saddle-point problems.Source: §6 · p. 8
- Whether the technique applies to non-convex problems remains an open question posed by the authors.Source: §6 · p. 8
A.1 Finishing the Proof of Theorem 3.1
The proof verifies that its parameter choices meet the stated requirements and yield linear convergence when the contraction factors are below one.
A.1 Finishing the Proof of Theorem 3.1
- Contraction factors strictly below 1 imply linear convergence.Source: §A.1 · p. 11
- It then calculates c1 and c2 to establish the desired upper bound on their maximum.Source: §A.1 · pp. 11–12
- The proof checks that the chosen step sizes satisfy the requirements in Propositions 3.2 and 3.4.Source: §A.1 · p. 11
A.2 Proof of Theorem 4.1
The proof tracks primal error and dual discrepancy relative to a reference map, then combines bounds over the inner-loop updates. It selects polynomially scaled parameters to obtain the stated bound.
A.2 Proof of Theorem 4.1
- The proof measures dual discrepancy against θ(x)=∇g*(Ax), with θ(x*)=y*.The aggregate quantities include primal distance to x* and dual discrepancy from θ(xtilde).Source: §A.2 · pp. 12, 15
- The analysis conditions on prior iterations and bounds the primal and dual inner-loop updates before combining their expectations.Source: §A.2 · pp. 12, 13, 15
- Choosing μ and N sufficiently large polynomially, and η1 and η2 sufficiently small inverse-polynomially, gives the stated bound 2(pt + μqt).Source: §A.2 · p. 15