Source-linked AI summary
Last-Iterate Convergence of Anchored Gradient Descent
Yang Cai, Weiqiang Zheng
TL;DR
The paper addresses whether anchored gradient descent can extend from the unconstrained setting to general monotone inclusions. It proposes a proximal anchored method using resolvent operators and proves an O(1/√T) last-iterate tangent-residual rate. The rate is not optimal, since optimism combined with anchoring can achieve O(1/T).
Problem
Anchored gradient descent had been studied only for unconstrained problems, leaving its extension to general monotone inclusions open.
Source: §1 · p. 3Method
The paper proposes proximal anchored gradient descent using the resolvent operator and extends the unconstrained proof with auxiliary c-vectors from [COZ24].
Source: §1.1 · p. 3, §3 · p. 6Results
P-AGD achieves an O(1/√T) last-iterate convergence rate for the tangent residual under the theorem’s assumptions.
Source: §1.1 · p. 4, §3 · p. 6Takeaways & Limitations
Anchoring alone extends to composite monotone inclusions, but combining optimism and anchoring remains necessary for the optimal O(1/T) rate.
Source: §1.1 · p. 4The achieved O(1/√T) rate is not optimal for monotone inclusion problems.
Source: §1.1 · p. 4, §3 · p. 6
Abstract
from arXiv · showhide
We study the monotone inclusion problem $0\in F(z)+A(z)$, where $F$ is monotone and Lipschitz, and $A$ is maximally monotone, a framework that encompasses monotone variational inequalities and convex-concave saddle-point problems with constraints or regularization. It is well known that vanilla gradient descent diverges for this problem, whereas optimism-based methods such as Extragradient and accelerated methods that combine both optimism and anchoring, such as Extra Anchored Gradient, achieve last-iterate convergence. However, the anchoring-only method, anchored gradient descent, has been studied only in the unconstrained setting [RYY19, SST+26]. In this note, we extend the anchored gradient descent method to the monotone inclusion problem and prove a last-iterate convergence rate of $O(1/\sqrt{T})$ in terms of the tangent residual. We build on the recent proof in the unconstrained setting [SST+26] and use techniques from [COZ24] to extend it to the general inclusion setting.
1 Introduction
The paper extends anchored gradient descent from unconstrained problems to general monotone inclusions, encompassing variational inequalities and convex-concave saddle-point problems. It proposes proximal anchored gradient descent and proves an O(1/√T) last-iterate tangent-residual rate, while optimism-plus-anchoring methods remain optimal at O(1/T).
1 Introduction
- Monotone inclusions use a Lipschitz monotone operator F and maximally monotone operator A, covering variational inequalities and convex-concave min-max problems.The tangent residual upper bounds the natural residual and implies bounds on the gap function.Source: §1 · p. 2
- Vanilla gradient descent can oscillate and fail to converge even on simple bilinear min-max problems, motivating optimism and anchoring.Extragradient uses a look-ahead correction, whereas anchoring regularizes updates toward a fixed anchor point.Source: §1 · pp. 2–3
- Prior anchored gradient descent results achieved last-iterate convergence only in the unconstrained setting A = 0, leaving the composite generalization open.The paper explicitly answers the open generalization question posed by Ryu, Yuan, and Yin [RYY19].Source: §1 · p. 3, §1.1 · p. 3
1.1 Our Results
- The proposed proximal anchored gradient descent method applies the anchored update through the resolvent J_αtA, which covers projections and proximal operators.It uses the schedule from Surina et al. [SST+26] and generalizes anchored GD to composite monotone inclusions.Source: §1.1 · p. 3
- P-AGD achieves an O(1/√T) last-iterate convergence rate for the tangent residual under Lipschitz monotonicity, maximal monotonicity, and the stated step-size schedule.Theorem 1 applies for any solution z⋆, initialization z0, γ ≥ 2, and all T ≥ 1.Source: §1.1 · pp. 3–4
- Anchoring alone is not optimal for general monotone inclusions: combining optimism and anchoring yields O(1/T) methods such as EAG, FEG [LK21], and composite extensions.Figure 1 places P-AGD alongside optimism-only and optimism-plus-anchoring mechanisms in the last-iterate convergence landscape.Source: §1.1 · p. 4, Figure 1 · p. 4
- The proof extends the unconstrained analysis of Surina et al. [SST+26] by introducing auxiliary vectors from the resolvent update, following the c-vector technique of.This rewrites the proximal iteration in an unconstrained-looking form and bounds the resulting operator residual, which controls the tangent residual.Source: §1.1 · p. 5
2 Preliminaries
The paper studies monotone inclusions under monotonicity, Lipschitz, maximal-monotonicity, and solution-existence assumptions. It introduces resolvent-based tools and uses the tangent residual as the composite problem’s optimality measure.
2 Preliminaries
- The framework assumes F is monotone and L-Lipschitz, A is maximally monotone, and the solution set zer(F + A) is nonempty.Source: §2 · p. 5
2.1 Resolvents, Normal Cones, and Prox Operators
- Resolvents of maximally monotone operators are single-valued and non-expansive, while normal cones and subdifferentials yield projections and proximal operators.Source: §2.1 · p. 5
2.2 Residuals
- The tangent residual is the primary optimality measure for the composite problem and reduces to ∥F(z)∥ when A ≡ 0.Source: §2.2 · p. 5
- The tangent residual characterizes approximate stationarity through 0 ∈ F(z) + A(z) + B(0, ε).Source: §2.2 · p. 5
- The natural residual is always bounded above by the tangent residual.Source: §2.2 · p. 6
3 Main Result
The paper proposes proximal anchored gradient descent for composite monotone inclusions, using a resolvent update and an anchoring schedule. Its analysis adapts the unconstrained proof with auxiliary vectors from the composite setting to obtain a last-iterate tangent-residual rate.
3 Main Result
- P-AGD generalizes anchored gradient descent to monotone inclusions through a resolvent update that covers projections and proximal operators.Source: §3 · p. 6
- The method uses α_t = 1/(L√t + γ) and β_t = γ/(t + γ), with γ ≥ 2.Source: §3 · p. 6
- The proof introduces c_{t+1} ∈ A(z_{t+1}) using the c-vector trick, converting the composite update into an unconstrained-looking form.Source: §3 · pp. 6–7
- Theorem 2 establishes a last-iterate tangent-residual bound of O(1/√T) for P-AGD under assumptions (A1)–(A4).Source: §3 · p. 6
- The resulting bound also yields the same O(1/√T) rate for the natural residual.Source: §3 · p. 6
4 Proof of the Main Theorem
The proof follows a three-step route: establish bounded iterates, control consecutive differences, and convert iterate stability into a last-iterate tangent-residual bound.
4 Proof of the Main Theorem
- The proof fixes a solution z⋆ and a⋆∈A(z⋆) satisfying F(z⋆)+a⋆=0, then introduces centered iterates and auxiliary quantities.These variables support the subsequent boundedness and stability arguments.Source: §4 · p. 7, §4.1 · p. 7
4.1 Step 1: Bounded Iterates
- The first step establishes bounded iterates by induction using the anchored update, monotonicity, convexity of the squared norm, and the prescribed parameter choices.The induction starts at t=0 and uses the squared-norm expansion to control the update.Source: §4.1 · pp. 7–8
4.2 Step 2: One-Step Recursion and Stability of Iterates
- The second step rewrites the method as the composite analogue of anchored GDA and proves the consecutive-difference stability bound ∥d_t∥≤E/(t+γ).The bound is obtained by induction through a one-step recursion and parameter inequalities.Source: §4.2 · pp. 8, 10
4.3 Step 3: From Iterate Stability to Residual
- F,A(z_T)≤L(2E+γD)/√(T−1+γ), yielding the last-iterate tangent-residual rate.The proof bounds the residual using a selected c_T∈A(z_T), then uses E=12γD to obtain the stated theorem bound.Source: §4.3 · p. 11