May 29, 2026
Anchored fixed point and monotone equation methods, including Halpern iteration, extra anchored gradient, and their relatives, add a vanishing pull toward a reference point to obtain last-iterate guarantees. Existing anchored variants often achieve sharp last-iterate guarantees, but from the update-level perspective the placement of the anchor can be algorithm-specific and conceptually opaque. We show that anchoring admits a single operator-side construction: regularize the operator queried by the base method with a vanishing Tikhonov term, then run the unmodified base method. Applied to the Picard iteration, this recipe reproduces the Halpern iteration; applied to the forward step, extragradient (EG), and past extragradient (PEG, also known as Popov’s method), it yields three variants whose anchor placements inherit the base method’s query pattern. The forward-step instantiation gives a new residual convergence guarantee, while the EG and PEG instantiations give new regularized variants. The four analyses share a residual recurrence, recovering the \(O(1/k)\) Halpern residual-norm convergence rate, giving \(O(1/\sqrt{k})\) for the regularized forward step, and giving \(O(1/k)\) for the regularized EG and PEG variants in the unconstrained monotone Lipschitz setting.
Many equilibrium conditions and first-order convex optimality conditions can be written as fixed point or monotone equation problems. In a fixed point problem, one seeks \(\mathbf{x}^\star\) such that \(T(\mathbf{x}^\star)=\mathbf{x}^\star\). In a monotone equation problem, one seeks \(\mathbf{x}^\star\) such that \(F(\mathbf{x}^\star)=\mathbf{0}\), where \(F\) is monotone in the standard sense made precise in 2. For instance, the first-order conditions of a smooth unconstrained convex-concave minmax problem give a monotone saddle operator. In this work, we focus on last-iterate residual convergence, measured by \[\left\| T(\mathbf{x}_k)-\mathbf{x}_k \right\|, \qquad \left\| F(\mathbf{x}_k) \right\|.\]
The simplest fixed point method is Picard iteration, \(\mathbf{x}_{k+1}=T(\mathbf{x}_k)\). When \(T\) is a contraction, the usual contraction argument gives convergence; for a merely nonexpansive \(T\), that argument no longer applies. The corresponding method for \(F(\mathbf{x})=\mathbf{0}\) is the forward step \(\mathbf{x}_{k+1}=\mathbf{x}_k-\eta_k F(\mathbf{x}_k)\). When \(F=\nabla f\) for a smooth convex function \(f\), this is gradient descent. It behaves well, with suitable step sizes, under stronger assumptions such as cocoercivity, but for a merely monotone Lipschitz operator it can diverge.
Anchoring repairs or sharpens this last-iterate behavior by adding a vanishing pull toward a reference point \(\mathbf{x}_0\). Halpern iteration does this for nonexpansive fixed point problems [1]–[3]. Its Tikhonov interpretation is direct: the regularization makes the current problem better conditioned, and the regularization is then slowly removed. For extragradient (EG) and past extragradient (PEG, also known as Popov’s method), the picture is less clear. These methods already stabilize monotone Lipschitz problems by changing the query pattern and achieve last-iterate convergence [4]–[7]. Anchored variants of these methods improve the last-iterate residual rate in related settings [8]–[14]. These guarantees are obtained through method-specific analyses and sometimes carefully chosen Lyapunov functions. This leaves a basic structural question about the mechanism of acceleration: can the anchor placement be derived systematically from the query pattern of the base method?
This paper proposes to regularize the operator being queried, then run the original template method unchanged. For fixed point problems, the regularized map is \[T_k(\mathbf{x}) = (1-\delta_k)T(\mathbf{x})+\delta_k\mathbf{x}_0.\] For monotone equations, the regularized object is the scaled displacement queried by the method: \[G_k(\mathbf{x}) = \eta_kF(\mathbf{x})+\delta_k(\mathbf{x}-\mathbf{x}_0).\] The anchor terms that appear after expanding the update are then determined by the query points of the base method.
The fixed point case gives the first example. Applying Picard iteration to \(T_k\) gives \[\mathbf{x}_{k+1} = T_k(\mathbf{x}_k) = (1-\delta_k)T(\mathbf{x}_k)+\delta_k\mathbf{x}_0,\] which is Halpern iteration. As another example, extragradient shows the anchor-placement mechanism more visibly. With a fixed \(\eta\), applying the two-query template to \(G_k\) gives \[\mathbf{x}_{k+1/2} = \mathbf{x}_k-G_k(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k-G_k(\mathbf{x}_{k+1/2}).\] Expanding the second line yields \[\mathbf{x}_{k+1} = \mathbf{x}_k-\eta F(\mathbf{x}_{k+1/2}) -\delta_k(\mathbf{x}_{k+1/2}-\mathbf{x}_0).\] Hence, under this operator-side rule, the second anchor term is evaluated at the lookahead point because that is where the second operator query is made.
Existing anchored extragradient and Popov-type methods achieve accelerated last-iterate residual rates [8]–[12]. Instead of explaining why each of those particular anchored updates achieves acceleration, we give a separate operator-side route to anchored algorithms. The rule is simple: regularize the operator (or its scaled displacement) with a vanishing Tikhonov term, and run the unmodified base template on the result. Applied to Picard, the rule recovers Halpern iteration and the known \(O(R/k)\) residual bound. Applied to the forward step, it stabilizes the method and gives an \(O(LR/\sqrt{k})\) residual-norm guarantee under monotonicity and Lipschitz continuity, the first such guarantee without extragradient or the Popov-type past query.2 Applied to EG and PEG, it gives the new regularized variants Reg-EG and Reg-PEG, both with \(O(LR/k)\) residual-norm bounds. The four analyses then reduce to the same recurrence. This perspective results in a single intuitive derivation that produces new accelerated anchored variants and their analyses uniformly.
2 introduces the setup, base methods, and related work. 3 discusses the operator-side regularization principle and uses Halpern iteration as the fixed point prototype. 4 establishes the monotone equation results for the regularized forward step, Reg-EG, and Reg-PEG. 5 concludes.
We use two operator templates throughout the paper. The fixed point results study a map \(T\) and certify an iterate by its fixed point residual, while the monotone equation results study an operator \(F\) and certify an iterate by the norm of \(F(\mathbf{x})\). The notation differs slightly across the two settings, but the role of the residual is the same: it is the last-iterate certificate controlled by the regularized dynamics.
For fixed point problems, we work in a general normed space \((\mathcal{X},\left\| \cdot \right\|)\) with a map \(T:\mathcal{X}\to\mathcal{X}\). The map is nonexpansive if \[\left\| T(\mathbf{x})-T(\mathbf{y}) \right\| \le \left\| \mathbf{x}-\mathbf{y} \right\| \qquad \text{for all }\mathbf{x},\mathbf{y}\in\mathcal{X}.\] It is a contraction if the right-hand side can be multiplied by some \(\gamma<1\). For monotone equations, we work in a real Hilbert space \((\mathcal{H},\left\langle \cdot,\cdot \right \rangle)\) with a single-valued operator \(F:\mathcal{H}\to\mathcal{H}\). The operator is monotone if \[\left\langle F(\mathbf{x})-F(\mathbf{y}),\mathbf{x}-\mathbf{y} \right \rangle\ge0 \qquad \text{for all }\mathbf{x},\mathbf{y}\in\mathcal{H}.\] We use two standard quantitative refinements: \(F\) is \(\mu\)-strongly monotone if the left-hand side is at least \(\mu\left\| \mathbf{x}-\mathbf{y} \right\|^2\), and it is \(L\)-Lipschitz if \[\left\| F(\mathbf{x})-F(\mathbf{y}) \right\| \le L\left\| \mathbf{x}-\mathbf{y} \right\|.\] The operator \(F\) is \(\beta\)-cocoercive if \[\left\langle F(\mathbf{x})-F(\mathbf{y}),\mathbf{x}-\mathbf{y} \right \rangle \ge \beta\left\| F(\mathbf{x})-F(\mathbf{y}) \right\|^2.\] Cocoercivity is stronger than monotonicity and gives a direct bridge between the two settings: if \(F\) is \(\beta\)-cocoercive, then \(I-\eta F\) is nonexpansive for \(0<\eta\le2\beta\). The main monotone equation results below do not assume cocoercivity.
The corresponding solution sets are \[\operatorname{Fix}(T) = \left\{ \mathbf{x}\in\mathcal{X}:T(\mathbf{x})=\mathbf{x} \right \}, \qquad \operatorname{Zer}(F) = \left\{ \mathbf{x}\in\mathcal{H}:F(\mathbf{x})=\mathbf{0} \right \}.\] Every theorem assumes the relevant solution set is nonempty. We fix an anchor \(\mathbf{x}_0\), choose a reference solution \(\mathbf{x}^\star\), and write \[R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^\star \right\|.\] All bounds are stated relative to this anchored radius.
With this notation in place, the residuals reported throughout are \[r_T(\mathbf{x})\mathrel{\vcenter{:}}=\left\| T(\mathbf{x})-\mathbf{x} \right\|, \qquad r_F(\mathbf{x})\mathrel{\vcenter{:}}=\left\| F(\mathbf{x}) \right\|.\] The auxiliary residual \(\left\| G_k(\mathbf{x}) \right\|\) used in the analyses is introduced with \(G_k\) in 3.1.
A standard machine-learning instance of the monotone equation template is the saddle-point operator. Given a smooth convex-concave function \(\mathcal{L}(\mathbf{u},\mathbf{v})\), define \[F(\mathbf{u},\mathbf{v}) =\bigl(\nabla_{\mathbf{u}}\mathcal{L}(\mathbf{u},\mathbf{v}), -\nabla_{\mathbf{v}}\mathcal{L}(\mathbf{u},\mathbf{v})\bigr).\] This operator is monotone, and its zeros are the saddle points of \(\mathcal{L}\). This is the setting most commonly studied for EG and PEG-type methods.
The operator-side construction starts from the query pattern of a base method. For this reason, we record both the updates and the points where the operator is evaluated.
For a map \(T\), Picard iteration is \[\label{eq:picard95iteration} \mathbf{x}_{k+1}=T(\mathbf{x}_k).\tag{1}\] When \(T\) is a contraction, the Banach fixed point theorem gives convergence to the unique fixed point. 3 applies this template to the regularized map \(T_k\), which recovers Halpern iteration.
The explicit one-call update for solving \(F(\mathbf{x})=\mathbf{0}\) is \[\label{eq:forward95step95std} \mathbf{x}_{k+1} = \mathbf{x}_k-\eta_kF(\mathbf{x}_k).\tag{2}\] In optimization notation this is gradient descent when \(F=\nabla f\), and gradient descent-ascent when \(F\) is a saddle operator. For merely monotone Lipschitz operators, the forward step need not be stable. 4 shows that adding the operator-side Tikhonov term alone is enough to stabilize it.
The extragradient (EG) template uses one lookahead query and one correction query: \[\label{eq:eg95std} \mathbf{x}_{k+1/2} = \mathbf{x}_k-\eta F(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k-\eta F(\mathbf{x}_{k+1/2}).\tag{3}\] 4 applies the operator-side rule to this two-query pattern; the induced Reg-EG variant places the second anchor at the lookahead point and obtains an \(O(LR/k)\) residual-norm bound.
Past extragradient (PEG), also known as Popov’s method, can be written with an auxiliary sequence as \[\label{eq:og95std} \tilde{\mathbf{x}}_k = \mathbf{x}_k-\eta F(\tilde{\mathbf{x}}_{k-1}), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k-\eta F(\tilde{\mathbf{x}}_k).\tag{4}\] Below we use the initialization \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\). In unconstrained Euclidean saddle-point problems, the method is also called optimistic gradient descent-ascent (OGDA). 4 applies the same rule to the PEG query pattern, producing Reg-PEG with an \(O(LR/k)\) residual-norm bound, matching the known rates of nearby anchored PEG/OGDA variants.
Halpern iteration and Browder approximants are classical ways to stabilize nonexpansive fixed-point dynamics and select fixed points [1]–[3]. Viscosity approximation replaces the fixed anchor by a contraction, and Tikhonov–Mann variants are part of the same fixed-point regularization picture [17]–[19]. Quantitative analyses often describe bounds on \(\left\| \mathbf{x}_k-T(\mathbf{x}_k) \right\|\) as rates of \(T\)-asymptotic regularity; here these are fixed-point residual bounds, including the known \(O(1/k)\) Halpern behavior [20]–[25]. Tikhonov-regularized monotone flows also have fixed-point and Halpern specializations [26]. In this paper, the fixed-point result is a known theorem; we use it as the simplest instance of the operator-side tracking argument and provide a new analysis in a general normed space.
Tikhonov regularization goes back to [27], and related regularization ideas are classical in monotone operator theory. Proximal-point and resolvent regularization go back to [28], [29]; those methods solve regularized resolvent or proximal subproblems, often centered at the current iterate. A distinct iterative Tikhonov line adds a vanishing strongly monotone term, often relative to a fixed anchor or to the origin, in variational inequality, inclusion, Nash-equilibrium, and stochastic-approximation schemes [30]–[34]. Recent concurrent anchored-gradient analyses study closely related one-call updates in smooth convex-concave and monotone-inclusion settings [16], [35].
EG and PEG methods (also known as optimistic gradient descent-ascent methods in min-max optimization) stabilize monotone Lipschitz equations where the plain forward step (gradient descent-ascent in min-max optimization) can fail [4], [5]. Modern unanchored last-iterate analyses give \(O(1/k)\) bounds on squared residuals [6], [7]. In the residual norm used in this paper, that is an \(O(1/\sqrt{k})\) rate. The Reg-EG and Reg-PEG theorems below are stated directly as \(O(LR/k)\) residual-norm bounds.
Anchored EG-family variants, including EAG, FEG, flexible anchored G-EAG, and broader accelerated EG-type frameworks, establish improved guarantees under their own assumptions and for their own residual notions [8]–[10], [13]. Halpern-type splitting, anchored Popov/APV variants, fast OGDA, and moving-anchor Popov variants provide related anchored or Tikhonov mechanisms on the PEG side [11], [12], [14], [36]. These works are the closest algorithmic neighbors of the present paper. The Reg-EG and Reg-PEG variants below belong to the same anchored/Tikhonov family and match the accelerated residual-norm order in comparable settings, while deriving their anchor placements directly from the operator-side rule and using a common progress–drift–bias proof.
This section and 4 share a single design and a common tracking pattern. The design is to regularize the queried operator with a vanishing Tikhonov term, apply the standard iterative template to the moving regularized object, and track the resulting residual. For Picard iteration this recipe reproduces Halpern iteration; for the forward-step, extragradient, and past extragradient templates, it produces anchored variants whose anchor-evaluation pattern is different from common update-level anchored EG/PEG placements.
For fixed-point problems we allow a general normed space \(\mathcal{X}\); for monotone equations we work in a Hilbert space \(\mathcal{H}\). The regularized objects are \[\label{eq:reg-objects} T_k(\mathbf{x}) \mathrel{\vcenter{:}}= (1 - \delta_k)\,T(\mathbf{x}) + \delta_k\,\mathbf{x}_0, \qquad G_k(\mathbf{x}) \mathrel{\vcenter{:}}= \eta_k\,F(\mathbf{x}) + \delta_k\,(\mathbf{x} - \mathbf{x}_0),\tag{5}\] where \(\mathbf{x}_0\) is a fixed anchor and \(0<\delta_k\le1\), \(\delta_k\downarrow0\). The map \(T_k\) is a \((1-\delta_k)\)-contraction; the map \(G_k\) is the scaled displacement of a Tikhonov regularization of \(F\), with the operator step size \(\eta_k\) already folded in. A Picard, forward, EG or PEG step taken on these moving objects, when expanded, yields an anchored update with the anchor evaluated at the same point as the corresponding operator query.
The analysis follows a progress–drift–bias pattern. In each setting, an appropriately chosen residual potential \(E_k\)—the regularized fixed-point residual for \(T_k\), or a method-specific potential built from \(G_k\)—will be shown to satisfy a recurrence of the form \[\label{eq:master-recurrence} E_{k+1} \;\le\; (1 - \gamma\,\delta_k)\,\bigl(E_k + C\,(\delta_{k-1} - \delta_k)\,R\bigr),\tag{6}\] for problem-dependent constants \(\gamma,C>0\). The factor \(1-\gamma\delta_k\) records progress on the current regularized problem; the additive term records the drift between successive regularized objects. Solving 6 via the deterministic estimate 10 bounds \(E_k\), after which a final step bounds the regularization bias and recovers the original residual. The schedules below are chosen so that progress, drift, and bias decay at the same rate.
We now run this template on its simplest instance. Let \(\mathcal{X}\) be a normed space and let \(T \colon \mathcal{X} \to \mathcal{X}\) be nonexpansive with \(\operatorname{Fix}(T)\ne\varnothing\). Pick a reference \(\mathbf{x}^*\in\operatorname{Fix}(T)\). Taking a convex combination of \(T\) and the constant map \(\mathbf{x}\mapsto\mathbf{x}_0\) gives the moving contraction \[\label{eq:regularized95op} T_k(\mathbf{x}) \mathrel{\vcenter{:}}= (1 - \delta_k)\,T(\mathbf{x}) + \delta_k\,\mathbf{x}_0,\tag{7}\] which is a \((1-\delta_k)\)-contraction whenever \(\delta_k\in(0,1]\). A single Picard step on this map, \[\label{eq:halpern95iteration} \mathbf{x}_{k+1} = T_k(\mathbf{x}_k),\tag{8}\] is exactly Halpern iteration.
The connection between Halpern’s update and Browder-type contractive approximants is classical [1]–[3]. Quantitative asymptotic-regularity estimates for Halpern iterations have a longer history: proof-mining arguments gave effective rates in normed spaces [20], [21]; Sabach and Shtern obtained an explicit \(O(1/k)\) residual bound [22]; and later work sharpened constants or studied optimal worst-case bounds in Hilbert and normed settings [23]–[25]. The interest here is the explicit conceptual viewpoint in the analysis: \(T_k\) is contractive, so a Picard step on \(T_k\) shrinks the current regularized residual; the schedule \(\delta_k=2/(k+2)\) then balances this progress with the drift from \(T_{k-1}\) to \(T_k\) and the final bias back to \(T\). We give a short proof of the following known proposition to illustrate the tracking framework:
Proposition 1 (Halpern residual bound). Let \(T\) be a nonexpansive mapping with a fixed point. Let \((\mathbf{x}_k)_{k\ge0}\) be the Halpern iterates 8 , initialized at \(\mathbf{x}_0\), with \(\delta_k=2/(k+2)\). For any \(\mathbf{x}^*\in\operatorname{Fix}(T)\), \[r_T(\mathbf{x}_k) = \left\| T(\mathbf{x}_k)-\mathbf{x}_k \right\| \le \frac{8R}{k+1}, \qquad k\ge1,\] where \(R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|\).
Proof. We show boundedness, set up a recurrence for the moving residual \[E_k\mathrel{\vcenter{:}}=\left\| \mathbf{x}_k-T_{k-1}(\mathbf{x}_k) \right\|,\] solve the recurrence via 10, and convert back to \(r_T(\mathbf{x}_k)\).
For any \(\delta\in[0,1]\) and any \(\mathbf{x}\) with \(\left\| \mathbf{x}-\mathbf{x}^* \right\|\le R\), the map \(\mathbf{x}\mapsto(1-\delta)T(\mathbf{x})+\delta\mathbf{x}_0\) satisfies \[\left\| (1-\delta)T(\mathbf{x})+\delta\mathbf{x}_0-\mathbf{x}^* \right\| \le (1-\delta)\left\| \mathbf{x}-\mathbf{x}^* \right\| +\delta\left\| \mathbf{x}_0-\mathbf{x}^* \right\| \le R,\] using \(T(\mathbf{x}^*)=\mathbf{x}^*\) and nonexpansiveness of \(T\). Since the iteration starts at \(\mathbf{x}_0\), induction gives \(\left\| \mathbf{x}_k-\mathbf{x}^* \right\|\le R\) for all \(k\ge0\), and consequently \[\left\| T(\mathbf{x}_k)-\mathbf{x}_0 \right\| \le \left\| T(\mathbf{x}_k)-T(\mathbf{x}^*) \right\| +\left\| \mathbf{x}^*-\mathbf{x}_0 \right\| \le \left\| \mathbf{x}_k-\mathbf{x}^* \right\|+R \le 2R.\]
Since \(\mathbf{x}_{k+1}=T_k(\mathbf{x}_k)\) and \(T_k\) is a \((1-\delta_k)\)-contraction, \[E_{k+1} = \left\| T_k(\mathbf{x}_k)-T_k(T_k(\mathbf{x}_k)) \right\| \le (1-\delta_k)\left\| \mathbf{x}_k-T_k(\mathbf{x}_k) \right\|.\] The right-hand factor differs from \(E_k\) by the drift between \(T_{k-1}\) and \(T_k\). Inserting and removing \(T_{k-1}(\mathbf{x}_k)\), and using \[T_{k-1}(\mathbf{x})-T_k(\mathbf{x}) = (\delta_{k-1}-\delta_k)(\mathbf{x}_0-T(\mathbf{x})),\] we obtain \[\begin{align} \left\| \mathbf{x}_k-T_k(\mathbf{x}_k) \right\| &\le E_k+\left\| T_{k-1}(\mathbf{x}_k)-T_k(\mathbf{x}_k) \right\| \\ &= E_k+(\delta_{k-1}-\delta_k)\left\| \mathbf{x}_0-T(\mathbf{x}_k) \right\| \le E_k+2(\delta_{k-1}-\delta_k)R. \end{align}\] Thus, for \(k\ge1\), \[\label{eq:error95recurrence} E_{k+1} \le (1-\delta_k)\bigl(E_k+2(\delta_{k-1}-\delta_k)R\bigr).\tag{9}\]
With \(\delta_0=1\), the map \(T_0\) is constant at \(\mathbf{x}_0\), so \(\mathbf{x}_1=\mathbf{x}_0\) and \(E_1=0\). Applying 10 with \(\alpha=\beta=2\), \(\gamma=1\), \(c=2\), and \(c_1=2\) gives \[E_k\le\frac{4R}{k+1}.\]
The original residual differs from \(E_k\) by the bias \[T_{k-1}(\mathbf{x}_k)-T(\mathbf{x}_k) = \delta_{k-1}(\mathbf{x}_0-T(\mathbf{x}_k)).\] Therefore \[\left\| \mathbf{x}_k-T(\mathbf{x}_k) \right\| \le E_k+\delta_{k-1}\left\| \mathbf{x}_0-T(\mathbf{x}_k) \right\| \le \frac{4R}{k+1}+\frac{2}{k+1}\cdot2R = \frac{8R}{k+1}.\] ◻
The proof is not tied to the exact schedule \(\delta_k=2/(k+2)\). For example, \(\delta_k=\alpha/(k+\beta)\) with \(1<\alpha\le\beta\) gives the same \(O(1/k)\) residual decay, with different constants in 10. Nor is anchoring outside \(T\) the only fixed-point regularization covered by this argument. The inner-anchored map \[\widetilde{T}_k(\mathbf{x}) = T\bigl((1-\delta_k)\mathbf{x}+\delta_k\mathbf{x}_0\bigr)\] is again a \((1-\delta_k)\)-contraction, and is the pure inner-anchored special case of the Tikhonov–Mann scheme [19]. Replacing the constant anchor by a contraction \(g\) gives the viscosity version [17], [18]; the residual bound is stated in 7.2. Finally, because each \(T_k\) is contractive, one may take several Picard steps at a fixed regularization level before decreasing \(\delta_k\). This episodic variant is recorded in 7.
The fixed-point case has now displayed 6 in its cleanest form. We next replace moving contractions \(T_k\) by moving strongly monotone operators \(G_k\), and apply the same progress–drift–bias argument to explicit monotone-equation templates.
We now instantiate the tracking principle from 3.1 on three monotone-equation templates: the forward step, extragradient, and past extragradient. The forward-step result is the minimal stabilization example: the Tikhonov term turns a plain explicit step, which may be unstable for merely monotone Lipschitz operators, into a moving contractive problem and yields the \(O(LR/\sqrt{k})\) residual-norm rate below. The Reg-EG and Reg-PEG results apply the same operator-side rule to the EG and PEG templates, giving \(O(LR/k)\) residual-norm bounds in the unconstrained monotone-equation setting. Across all three cases, the object being tracked is built from the scaled regularized displacement \[G_k(\mathbf{x})=\eta_k F(\mathbf{x})+\delta_k(\mathbf{x}-\mathbf{x}_0),\] with \(\eta_k\equiv\eta\) in the Reg-EG and Reg-PEG sections. The scalar \(\eta\) or \(\eta_k\) is the step size.
The table gives an overview of the induced methods, parameter scales, and residual-norm rates. The numerical constants in the theorem statements are chosen for clean proofs and are not optimized.
| Method | Update on \(G_k\) | Parameter scale | Rate for \(\left\| F(\mathbf{x}_k) \right\|\) |
|---|---|---|---|
| Reg-Forward Step | \(\mathbf{x}_{k+1}=\mathbf{x}_k-G_k(\mathbf{x}_k)\) | \(\delta_k\asymp k^{-1}\), \(\eta_k\asymp (L\sqrt{k})^{-1}\) | \(O(LR/\sqrt{k})\) |
| Reg-EG | \(\begin{gathered}\mathbf{x}_{k+1/2}=\mathbf{x}_k-G_k(\mathbf{x}_k)\\ \mathbf{x}_{k+1}=\mathbf{x}_k-G_k(\mathbf{x}_{k+1/2})\end{gathered}\) | \(\delta_k\asymp k^{-1}\), \(\eta\asymp L^{-1}\) | \(O(LR/k)\) |
| Reg-PEG | \(\begin{gathered}\tilde{\mathbf{x}}_k=\mathbf{x}_k-G_k(\tilde{\mathbf{x}}_{k-1})\\ \mathbf{x}_{k+1}=\mathbf{x}_k-G_k(\tilde{\mathbf{x}}_k)\end{gathered}\) | \(\delta_k\asymp k^{-1}\), \(\eta\asymp L^{-1}\) | \(O(LR/k)\) |
For the three monotone-equation theorem statements below, unless stated otherwise, \(F:\mathcal{H}\to\mathcal{H}\) is a single-valued full-domain monotone \(L\)-Lipschitz operator on a real Hilbert space with \(L>0\), and \(\operatorname{Zer}(F)\ne\varnothing\). We fix an anchor \(\mathbf{x}_0\), choose a solution \(\mathbf{x}^*\in\operatorname{Zer}(F)\), and write \[R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|.\] For \(\delta>0\), define \[\label{eq:reg-eqn} \mathcal{F}_\delta(\mathbf{x}) \mathrel{\vcenter{:}}= F(\mathbf{x})+\delta(\mathbf{x}-\mathbf{x}_0).\tag{10}\] We refer to \(\mathcal{F}_\delta(\mathbf{x})=0\) as the regularized monotone equation and denote its solution, when it exists, by \(\mathbf{x}_\delta^*\). The facts below record existence, the basic location bound, and stability as \(\delta\) varies. The EG and PEG trajectory estimates use the moving regularized zeros; the forward-step proof uses the same regularized residual viewpoint but compares directly with the original zero \(\mathbf{x}^*\).
The first point is that the regularized equation has a unique single zero at each regularization level.
Lemma 1 (Existence of the regularized zero). For every \(\delta>0\), the regularized monotone equation \(\mathcal{F}_\delta(\mathbf{x})=0\) has a unique solution.
Proof. Since \(F\) is everywhere defined and Lipschitz, it is continuous. The maximal-monotonicity theorem for full-domain continuous monotone operators on Hilbert spaces gives that \(F\) is maximally monotone [37]. Therefore \(F+\delta I\) is maximally monotone and \(\delta\)-strongly monotone. By Browder–Minty surjectivity for maximally monotone strongly monotone operators [37], \(\operatorname{ran}(F+\delta I)=\mathcal{H}\). Hence there exists \(\mathbf{x}\in\mathcal{H}\) such that \[(F+\delta I)(\mathbf{x})=\delta\mathbf{x}_0,\] which is equivalent to \(\mathcal{F}_\delta(\mathbf{x})=0\). Strong monotonicity gives uniqueness. ◻
The next estimate says that this target stays in the ball determined by the anchor and any fixed solution of the original equation. This is the elementary geometric fact used later to remove the regularization bias.
Lemma 2 (Boundedness of the regularized zero). For every \(\delta>0\), \[\left\| \mathbf{x}_\delta^*-\mathbf{x}^* \right\|\le R, \qquad \left\| \mathbf{x}_\delta^*-\mathbf{x}_0 \right\|\le R.\]
Proof. Since \(\mathcal{F}_\delta(\mathbf{x}_\delta^*)=0\), we have \(F(\mathbf{x}_\delta^*)=-\delta(\mathbf{x}_\delta^*-\mathbf{x}_0)\). Monotonicity of \(F\) and \(F(\mathbf{x}^*)=\mathbf{0}\) give \[0 \le \left\langle F(\mathbf{x}_\delta^*)-F(\mathbf{x}^*), \mathbf{x}_\delta^*-\mathbf{x}^* \right \rangle = -\delta \left\langle \mathbf{x}_\delta^*-\mathbf{x}_0, \mathbf{x}_\delta^*-\mathbf{x}^* \right \rangle.\] Thus \(\left\langle \mathbf{x}_\delta^*-\mathbf{x}^*, \mathbf{x}_\delta^*-\mathbf{x}_0 \right \rangle\le0\). Plugging \[2\left\langle \mathbf{a},\mathbf{b} \right \rangle = \left\| \mathbf{a} \right\|^2+\left\| \mathbf{b} \right\|^2-\left\| \mathbf{a}-\mathbf{b} \right\|^2\] with \(\mathbf{a}=\mathbf{x}_\delta^*-\mathbf{x}^*\) and \(\mathbf{b}=\mathbf{x}_\delta^*-\mathbf{x}_0\), we obtain the stronger bound \[\left\| \mathbf{x}_\delta^*-\mathbf{x}^* \right\|^2 +\left\| \mathbf{x}_\delta^*-\mathbf{x}_0 \right\|^2 \le \left\| \mathbf{x}^*-\mathbf{x}_0 \right\|^2 = R^2.\] Hence, both displayed bounds follow. ◻
Finally, we show that the regularized target changes slowly as the regularization level varies. This is the form needed in the trajectory bounds for the EG and PEG variants.
Lemma 3 (Stability of the regularized zero). For \(\delta_1,\delta_2>0\), \[\left\| \mathbf{x}_{\delta_1}^*-\mathbf{x}_{\delta_2}^* \right\| \le \frac{|\delta_1-\delta_2|}{\max\{\delta_1,\delta_2\}}\,R.\]
Proof. Set \(\mathbf{u}=\mathbf{x}_{\delta_1}^*\), \(\mathbf{v}=\mathbf{x}_{\delta_2}^*\), and \(\mathbf{d}=\mathbf{u}-\mathbf{v}\). If \(\mathbf{d}=\mathbf{0}\), the claim is immediate. Otherwise, using \[F(\mathbf{u})=-\delta_1(\mathbf{u}-\mathbf{x}_0), \qquad F(\mathbf{v})=-\delta_2(\mathbf{v}-\mathbf{x}_0),\] and monotonicity of \(F\), \[\begin{align} 0 &\le \left\langle F(\mathbf{u})-F(\mathbf{v}),\mathbf{d} \right \rangle \\ &= -\delta_1\left\| \mathbf{d} \right\|^2 +(\delta_2-\delta_1)\left\langle \mathbf{v}-\mathbf{x}_0,\mathbf{d} \right \rangle. \end{align}\] Cauchy–Schwarz and 2 then give \[\delta_1\left\| \mathbf{d} \right\| \le |\delta_1-\delta_2|\,\left\| \mathbf{v}-\mathbf{x}_0 \right\| \le |\delta_1-\delta_2|\,R.\] Repeating the same argument with the roles of \(\delta_1\) and \(\delta_2\) swapped gives the same bound with \(\delta_2\) on the left. Taking the tighter of the two inequalities yields the denominator \(\max\{\delta_1,\delta_2\}\). ◻
The methods below apply explicit templates to the scaled displacement \[G_k(\mathbf{x}) = \eta_kF(\mathbf{x})+\delta_k(\mathbf{x}-\mathbf{x}_0).\] Since \(\eta_kF\) is again monotone and has the same zero set as \(F\), the preceding lemmas apply directly to \(G_k\) as the regularization of the operator \(\eta_kF\) with parameter \(\delta_k\). In the Reg-EG and Reg-PEG sections, where \(\eta_k\equiv\eta\), we denote the zero of \(G_k\) by \(\mathbf{x}_k^*\). For the non-increasing schedules used there, 3 gives \[\left\| \mathbf{x}_{k-1}^*-\mathbf{x}_k^* \right\| \le \frac{\delta_{k-1}-\delta_k}{\delta_{k-1}}\,R,\] which is the moving-zero estimate used in the trajectory bounds. The same operator \(G_k\) is also \(\delta_k\)-strongly monotone and has Lipschitz constant at most \(\eta_kL+\delta_k\), which are the constants used in the one-step progress estimates.
In this section, we discuss the forward step as the simplest monotone equation template. It queries \(F\) once per iteration and updates by the explicit rule \[\mathbf{x}_{k+1} = \mathbf{x}_k - \eta_k F(\mathbf{x}_k), \qquad \eta_k > 0.\] When \(F=\nabla f\), this is gradient descent; when \(F\) is the saddle operator of a minmax problem, it is gradient descent-ascent. If \(F\) is \(1/L\)-cocoercive, then \(I-\eta F\) is nonexpansive for \(\eta\in(0,2/L]\), and the usual averaged-map theory gives convergence under the standard stricter step-size conditions. Under mere monotonicity and Lipschitz continuity, however, it is well known that the forward step can diverge. In finite dimensions, the standard example is a full-rank skew-symmetric linear map (which includes bilinear minmax optimization) \(F(\mathbf{x})=\mathbf{A}\mathbf{x}\), for which \[\left\| \mathbf{x}-\eta F(\mathbf{x}) \right\|^2 = \left\| \mathbf{x} \right\|^2+\eta^2\left\| \mathbf{A}\mathbf{x} \right\|^2,\] so every nonzero step strictly recedes from the origin. Extragradient repairs this failure by using a second query, while PEG/Popov uses a staggered past query. Interestingly, the results in this section show that the iteratively regularized forward step alone achieves stabilization at the same last-iterate residual-norm rate as these two-query methods.
Recall from 3.1 the scaled regularized displacement \[G_k(\mathbf{x}) \mathrel{\vcenter{:}}= \eta_k F(\mathbf{x})+\delta_k(\mathbf{x}-\mathbf{x}_0),\] where the operator step size \(\eta_k\) has been folded into \(G_k\). Running a forward step on \(G_k\) produces the Tikhonov-regularized forward step \[\label{eq:reg95forward95step} \mathbf{x}_{k+1} = \mathbf{x}_k-G_k(\mathbf{x}_k) = \mathbf{x}_k-\eta_kF(\mathbf{x}_k)-\delta_k(\mathbf{x}_k-\mathbf{x}_0).\tag{11}\] Equivalently, this is the anchored forward step with operator weight \(\eta_k\) and anchor weight \(\delta_k\), with both terms evaluated at \(\mathbf{x}_k\). The update calls \(F\) once per iteration. With the schedule \(2\eta_kL=\sqrt{\delta_k}\) used below, the map \(\mathbf{x}\mapsto\mathbf{x}-G_k(\mathbf{x})\) is a contraction at each fixed \(k\); the Tikhonov term supplies the stability that the unregularized forward step lacks for merely monotone Lipschitz operators.
Theorem 1 (Tikhonov-Regularized Forward Residual Bound). Let \(F:\mathcal{H}\to\mathcal{H}\) be a monotone, \(L\)-Lipschitz operator with \(L>0\) and with a zero \(\mathbf{x}^*\in\mathcal{H}\). Let \(R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|\). Consider the iteration 11 with parameters satisfying \(2\eta_kL=\sqrt{\delta_k}\) and \(\delta_k=4/(k+4)\) for \(k\ge0\). Then, for every \(k\ge1\), \[r_F(\mathbf{x}_k) = \left\| F(\mathbf{x}_k) \right\| \le \frac{24LR}{\sqrt{k+3}}.\]
We record a few remarks on this result. The rate \(O(LR/\sqrt{k})\) has the same last-iterate residual rate as unanchored extragradient and Popov/PEG [6], [7], attained here with the literal one-call forward template; Reg-EG and Reg-PEG below improve it to \(O(LR/k)\). If \(F\) is also \(1/L\)-cocoercive, the map \(\mathbf{x}\mapsto\mathbf{x}-\eta F(\mathbf{x})\) is then nonexpansive and Halpern iteration already gives \(O(LR/k)\). In contrast to the constant \(\eta=1/(8L)\) used by the EG and PEG variants below, we require a vanishing step size without the extragradient or past-query stabilization.
The argument follows the progress-drift-bias pattern of 3.1, applied to the regularized residual \[E_k\mathrel{\vcenter{:}}=\left\| G_{k-1}(\mathbf{x}_k) \right\|,\qquad k\ge1.\] Step 1 shows that \(\mathbf{x}\mapsto\mathbf{x}-G_k(\mathbf{x})\) is a \((1-\delta_k/2)\)-contraction. Step 2 uses this contraction and the identity \(G_k(\mathbf{x}^*)=\delta_k(\mathbf{x}^*-\mathbf{x}_0)\) to keep the trajectory in a ball of radius \(2R\) around \(\mathbf{x}^*\). Step 3 closes the recurrence on \(E_k\): it inherits the contraction factor from Step 1 and absorbs a drift term \(3(\delta_{k-1}-\delta_k)R\) produced by the change \(G_{k-1}\to G_k\). Finally, 10 bounds \(E_k\), and the identity \(G_{k-1}=\eta_{k-1}F+\delta_{k-1}(\cdot-\mathbf{x}_0)\) converts this back to a bound on \(\left\| F(\mathbf{x}_k) \right\|\).
Proof of 1. We carry out the three steps in turn.
Consider the map \(S_k(\mathbf{x})\mathrel{\vcenter{:}}=\mathbf{x}-G_k(\mathbf{x})\). For any \(\mathbf{x},\mathbf{y}\in\mathcal{H}\), \[S_k(\mathbf{x})-S_k(\mathbf{y}) = (1-\delta_k)(\mathbf{x}-\mathbf{y}) -\eta_k\bigl(F(\mathbf{x})-F(\mathbf{y})\bigr).\] Squaring and using monotonicity of \(F\) to drop the cross term gives \[\begin{align} \left\| S_k(\mathbf{x})-S_k(\mathbf{y}) \right\|^2 &\le (1-\delta_k)^2\left\| \mathbf{x}-\mathbf{y} \right\|^2 +\eta_k^2\left\| F(\mathbf{x})-F(\mathbf{y}) \right\|^2 \\ &\le \bigl((1-\delta_k)^2+\eta_k^2L^2\bigr) \left\| \mathbf{x}-\mathbf{y} \right\|^2. \end{align}\] Substituting \(\eta_k^2L^2=\delta_k/4\) and using \(\delta_k\in(0,1]\), \[(1-\delta_k)^2+\frac{\delta_k}{4} = 1-2\delta_k+\delta_k^2+\frac{\delta_k}{4} \le \left(1-\frac{\delta_k}{2}\right)^2.\] Thus \(S_k\) is a \((1-\delta_k/2)\)-contraction.
Since \(F(\mathbf{x}^*)=\mathbf{0}\), \[G_k(\mathbf{x}^*)=\delta_k(\mathbf{x}^*-\mathbf{x}_0).\] Therefore, \[\left\| \mathbf{x}_{k+1}-\bigl(\mathbf{x}^*-G_k(\mathbf{x}^*)\bigr) \right\| = \left\| S_k(\mathbf{x}_k)-S_k(\mathbf{x}^*) \right\| \le \left(1-\frac{\delta_k}{2}\right)\left\| \mathbf{x}_k-\mathbf{x}^* \right\|.\] The triangle inequality gives \[\left\| \mathbf{x}_{k+1}-\mathbf{x}^* \right\| \le \left(1-\frac{\delta_k}{2}\right)\left\| \mathbf{x}_k-\mathbf{x}^* \right\| +\delta_k R.\] Induction yields \(\left\| \mathbf{x}_k-\mathbf{x}^* \right\|\le2R\) for all \(k\ge0\): the base case is immediate, and if \(\left\| \mathbf{x}_k-\mathbf{x}^* \right\|\le2R\), then \[\left\| \mathbf{x}_{k+1}-\mathbf{x}^* \right\| \le \left(1-\frac{\delta_k}{2}\right)2R+\delta_kR = 2R.\] Consequently, \[\left\| \mathbf{x}_k-\mathbf{x}_0 \right\| \le \left\| \mathbf{x}_k-\mathbf{x}^* \right\|+\left\| \mathbf{x}^*-\mathbf{x}_0 \right\| \le 3R.\]
Using \(\mathbf{x}_{k+1}=\mathbf{x}_k-G_k(\mathbf{x}_k)\) and the contraction of \(S_k\), \[\begin{align} \left\| G_k(\mathbf{x}_{k+1}) \right\| &= \left\| S_k(\mathbf{x}_{k+1})-S_k(\mathbf{x}_k) \right\| \qquad(\text{since }\mathbf{x}_{k+1}=S_k(\mathbf{x}_k)) \\ &\le \left(1-\frac{\delta_k}{2}\right)\left\| \mathbf{x}_{k+1}-\mathbf{x}_k \right\| = \left(1-\frac{\delta_k}{2}\right)\left\| G_k(\mathbf{x}_k) \right\|. \end{align}\] We next compare \(G_k(\mathbf{x}_k)\) to \(E_k=\left\| G_{k-1}(\mathbf{x}_k) \right\|\). From the definition of \(G_k\), \[G_k(\mathbf{x}_k) = \frac{\eta_k}{\eta_{k-1}}G_{k-1}(\mathbf{x}_k) + \left(\delta_k-\frac{\eta_k}{\eta_{k-1}}\delta_{k-1}\right) (\mathbf{x}_k-\mathbf{x}_0).\] Since \(\delta_k\le\delta_{k-1}\) and \(\eta_k/\eta_{k-1}=\sqrt{\delta_k/\delta_{k-1}}\le1\), \[\left|\delta_k-\frac{\eta_k}{\eta_{k-1}}\delta_{k-1}\right| = \sqrt{\delta_k\delta_{k-1}}-\delta_k \le \delta_{k-1}-\delta_k.\] Together with \(\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\le3R\), this gives \[\left\| G_k(\mathbf{x}_k) \right\| \le \frac{\eta_k}{\eta_{k-1}}E_k +(\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\| \le E_k+3(\delta_{k-1}-\delta_k)R.\] Setting \(E_{k+1}=\left\| G_k(\mathbf{x}_{k+1}) \right\|\), we obtain, for \(k\ge1\), \[E_{k+1} \le \left(1-\frac{\delta_k}{2}\right) \bigl(E_k+3(\delta_{k-1}-\delta_k)R\bigr).\] The base case follows from the contraction of \(S_0\), the identity \(G_0(\mathbf{x}_0)=\eta_0F(\mathbf{x}_0)\), and Lipschitzness around \(\mathbf{x}^*\): \[E_1 = \left\| G_0(\mathbf{x}_1) \right\| \le \left(1-\frac{\delta_0}{2}\right)\left\| \eta_0F(\mathbf{x}_0) \right\| \le \frac{R}{4}.\] Here \(\delta_0=1\), \(\eta_0=1/(2L)\), and \(\left\| F(\mathbf{x}_0) \right\|=\left\| F(\mathbf{x}_0)-F(\mathbf{x}^*) \right\|\le LR\). Applying 10 with \[\alpha=\beta=4,\qquad \gamma=\frac{1}{2},\qquad c=3,\qquad c_1=\frac{1}{4}\] yields \[E_k\le\frac{12R}{k+3}.\] Finally, since \[G_{k-1}(\mathbf{x}_k) = \eta_{k-1}F(\mathbf{x}_k) +\delta_{k-1}(\mathbf{x}_k-\mathbf{x}_0),\] we have \[\left\| F(\mathbf{x}_k) \right\| \le \frac{E_k+3\delta_{k-1}R}{\eta_{k-1}} \le \frac{24LR}{\sqrt{k+3}},\] where the last inequality uses \(\delta_{k-1}=4/(k+3)\), \(\eta_{k-1}=1/(L\sqrt{k+3})\), and \(E_k\le12R/(k+3)\). ◻
For a monotone Lipschitz operator \(F\) that need not be cocoercive, extragradient provides stabilization and achieves last-iterate residual-norm guarantees of order \(O(LR/\sqrt{k})\) [6]. Anchored EG-family variants, including EAG, FEG, and the flexible anchored G-EAG family, achieve the accelerated \(O(LR/k)\) residual-norm rate in their respective settings [8]–[10]. In this subsection, we show that the operator-side substitution of 3.1 leads to a different anchor placement and the same last-iterate residual-norm rate \(O(LR/k)\).
Applying EG to the scaled regularized displacement \[G_k(\mathbf{x}) \mathrel{\vcenter{:}}= \eta F(\mathbf{x}) + \delta_k(\mathbf{x} - \mathbf{x}_0)\] gives the regularized extragradient (Reg-EG) method: \[\label{eq:reg95eg} \mathbf{x}_{k+1/2} = \mathbf{x}_k - G_k(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k - G_k(\mathbf{x}_{k+1/2}),\tag{12}\] or, equivalently, after expanding \(G_k\), \[\mathbf{x}_{k+1/2} = \mathbf{x}_k-\eta F(\mathbf{x}_k)-\delta_k(\mathbf{x}_k-\mathbf{x}_0), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k-\eta F(\mathbf{x}_{k+1/2}) -\delta_k(\mathbf{x}_{k+1/2}-\mathbf{x}_0).\]
The relevant comparator is the base-anchored EG pattern introduced by Yoon–Ryu’s EAG method [8]. With fixed anchor \(\mathbf{x}_0\), the EAG and flexible G-EAG updates share, up to coefficient choices and affine rescalings, the skeleton [10] \[\mathbf{x}_{k+1/2} = \mathbf{x}_k+a_k(\mathbf{x}_0-\mathbf{x}_k)-b_kF(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k+\bar a_k(\mathbf{x}_0-\mathbf{x}_k)-\bar b_kF(\mathbf{x}_{k+1/2}).\] In this pattern, both anchor corrections are tied to the base displacement \(\mathbf{x}_0-\mathbf{x}_k\). Reg-EG has the same first-line form but differs in the second line: \[\mathbf{x}_{k+1} = \mathbf{x}_k-\eta F(\mathbf{x}_{k+1/2}) -\delta_k(\mathbf{x}_{k+1/2}-\mathbf{x}_0),\] where the anchor is placed at the lookahead point itself.
The main Reg-EG bound is as follows.
Theorem 2 (Last-Iterate Residual Bound for Reg-EG). Let \(F:\mathcal{H}\to\mathcal{H}\) be a monotone, \(L\)-Lipschitz operator with \(L>0\) and a solution \(\mathbf{x}^*\) such that \(F(\mathbf{x}^*) = \mathbf{0}\). Consider the regularized extragradient method 12 with parameters \(\eta = \frac{1}{8L}\) and \(\delta_k = \frac{4}{k+32}\) for \(k \ge 0\). Let \(R \mathrel{\vcenter{:}}= \left\| \mathbf{x}_0 - \mathbf{x}^* \right\|\). Then, for all \(k\ge1\), the iterates satisfy: \[r_F(\mathbf{x}_k)=\left\| F(\mathbf{x}_k) \right\| \le \frac{128LR}{k+31}.\]
The proof follows the shared progress–drift–bias architecture of 3.1, with one extra ingredient relative to the regularized forward-step argument. The Reg-EG update map \(\mathbf{x}\mapsto \mathbf{x}-G_k(\mathbf{x}-G_k(\mathbf{x}))\) is not a contraction, so the one-step contraction argument used for the forward step does not apply directly. We instead use two fixed-\(G_k\) EG estimates. The first, 4, contracts the distance to the zero of a fixed strongly monotone Lipschitz operator; together with stability of the moving regularized zeros, this gives the trajectory bound \(\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\le2R\) in 5. The second, proved below, is the residual contraction \[\left\| G_k(\mathbf{x}_{k+1}) \right\| \le \left(1-\frac{\delta_k}{2}\right)\left\| G_k(\mathbf{x}_k) \right\|.\] The drift from \(G_{k-1}\) to \(G_k\) then yields a recurrence for \(r_{k-1}(\mathbf{x}_k)=\left\| G_{k-1}(\mathbf{x}_k) \right\|\), controlled by the trajectory bound and solved by 10. Finally, \(G_{k-1}=\eta F+\delta_{k-1}(\cdot-\mathbf{x}_0)\) removes the regularization bias and recovers the stated bound on \(r_F(\mathbf{x}_k)\).
Linear convergence of extragradient in strongly monotone Lipschitz variational inequalities is known [38]. We include the following lemma for completeness with the constants needed below.
Lemma 4 (Linear Convergence of Extragradient). Let \(G: \mathcal{H} \to \mathcal{H}\) be \(\bar L\)-Lipschitz with \(\bar L>0\) and \(\mu\)-strongly monotone with \(\mu>0\). Let \(G(\mathbf{x}_G^*)=0\), and let \[\mathbf{x}_{t+1/2}=\mathbf{x}_t-\alpha G(\mathbf{x}_t), \qquad \mathbf{x}_{t+1}=\mathbf{x}_t-\alpha G(\mathbf{x}_{t+1/2})\] with \(0<\alpha\le 1/(4\bar L)\). Then \[\left\| \mathbf{x}_{t+1} - \mathbf{x}_G^* \right\| \le \left(1-\frac{\alpha\mu}{2}\right) \left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|.\]
Proof. We first establish a lower bound for \(\left\| \mathbf{x}_{t+1/2} - \mathbf{x}_G^* \right\|^2\): \[\begin{align} \left\| \mathbf{x}_{t+1/2} - \mathbf{x}_G^* \right\|^2 &= \left\| \mathbf{x}_t - \mathbf{x}_G^* - \alpha (G(\mathbf{x}_t) - G(\mathbf{x}_G^*)) \right\|^2 \\ &\ge \left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2 - 2\alpha\bar L \left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2 \\ &= \left( 1 - 2\alpha\bar L \right)\left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2. \end{align}\] The inequality uses Cauchy-Schwarz and the \(\bar L\)-Lipschitz continuity of \(G\).
Next, we bound \(\left\| \mathbf{x}_{t+1} - \mathbf{x}_G^* \right\|^2\): \[\begin{align} \left\| \mathbf{x}_{t+1} - \mathbf{x}_G^* \right\|^2 &= \left\| \mathbf{x}_t - \mathbf{x}_G^* - \alpha G(\mathbf{x}_{t+1/2}) \right\|^2 \nonumber \\ &= \left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2 - 2\alpha \langle \mathbf{x}_t - \mathbf{x}_G^*, G(\mathbf{x}_{t+1/2}) \rangle + \alpha^2 \left\| G(\mathbf{x}_{t+1/2}) \right\|^2. \label{eq:main95expansion} \end{align}\tag{13}\] We decompose the inner product term as follows: \[\langle \mathbf{x}_t - \mathbf{x}_G^*, G(\mathbf{x}_{t+1/2}) \rangle = \langle \mathbf{x}_{t+1/2} - \mathbf{x}_G^*, G(\mathbf{x}_{t+1/2}) \rangle + \alpha \langle G(\mathbf{x}_t), G(\mathbf{x}_{t+1/2}) \rangle.\] By \(\mu\)-strong monotonicity, the first term on the right-hand side is bounded below by \(\mu \left\| \mathbf{x}_{t+1/2} - \mathbf{x}_G^* \right\|^2\). For the second term, we use the identity \(2\langle \mathbf{a}, \mathbf{b} \rangle = \left\| \mathbf{a} \right\|^2 + \left\| \mathbf{b} \right\|^2 - \left\| \mathbf{a}-\mathbf{b} \right\|^2\) and the \(\bar L\)-Lipschitz property: \[\begin{align} 2\alpha^2 \langle G(\mathbf{x}_t), G(\mathbf{x}_{t+1/2}) \rangle &\geq \alpha^2 \left( \left\| G(\mathbf{x}_t) \right\|^2 + \left\| G(\mathbf{x}_{t+1/2}) \right\|^2 - \bar L^2 \left\| \mathbf{x}_t - \mathbf{x}_{t+1/2} \right\|^2 \right) \\ &= \alpha^2(1 - \alpha^2 \bar L^2)\left\| G(\mathbf{x}_t) \right\|^2 + \alpha^2\left\| G(\mathbf{x}_{t+1/2}) \right\|^2. \end{align}\] Substituting these bounds into 13 : \[\begin{align} \left\| \mathbf{x}_{t+1} - \mathbf{x}_G^* \right\|^2 &\leq \left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2 - 2\alpha\mu \left\| \mathbf{x}_{t+1/2} - \mathbf{x}_G^* \right\|^2 - \alpha^2(1 - \alpha^2\bar L^2)\left\| G(\mathbf{x}_t) \right\|^2. \end{align}\] Dropping the final non-positive term and using \(1-2\alpha\bar L\ge1/2\), we get \[\left\| \mathbf{x}_{t+1} - \mathbf{x}_G^* \right\|^2 \le \left( 1-\alpha\mu \right)\left\| \mathbf{x}_t - \mathbf{x}_G^* \right\|^2.\] Since \(\mu\le\bar L\) and \(\alpha\le1/(4\bar L)\), we have \(\alpha\mu\in[0,1]\). Taking square roots and using \(\sqrt{1-z}\le1-z/2\) with \(z=\alpha\mu\) proves the claim. ◻
Lemma 5 (Boundedness of the Trajectory). Let \(F:\mathcal{H}\to\mathcal{H}\) be monotone and \(L\)-Lipschitz with \(L>0\), and let \(\mathbf{x}^*\) satisfy \(F(\mathbf{x}^*)=\mathbf{0}\). Set \(R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|\). Let \((\mathbf{x}_k)_{k\ge0}\) be generated by the Reg-EG scheme 12 with parameters \(\eta=\frac{1}{8L}\) and a non-increasing sequence \((\delta_k)\) satisfying \(\delta_0 \le \frac{1}{8}\). Denote by \(\mathbf{x}_k^*\) the unique zero of \(G_k\). If \(\delta_k = \frac{c}{k+8c}\) for some \(c \ge 2\), then for every \(k\ge0\), we have \(\left\| \mathbf{x}_k - \mathbf{x}_0 \right\| \le 2R\).
Proof. At phase \(k\), the algorithm performs one EG step on the operator \(G_k\). This operator is \(\delta_k\)-strongly monotone and has Lipschitz constant at most \(\eta L+\delta_k\). With our choice of \(\eta = 1/(8L)\) and \(\delta_k \le 1/8\), we have \(\eta L+\delta_k \le 1/4\). We can apply Lemma 4 with \(G=G_k\), \(\mu=\delta_k\), \(\bar L=1/4\), and step size \(\alpha=1\). This gives the local contraction around the zero \(\mathbf{x}_k^*\): \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\| \le \left(1-\frac{\delta_k}{2}\right) \left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|.\] For \(k\ge1\), the triangle inequality and Lemma 3, applied to the monotone operator \(\eta F\), give the following bound, which handles the shift from \(\mathbf{x}_k^*\) to \(\mathbf{x}_{k-1}^*\): \[\begin{align} \left\| \mathbf{x}_k - \mathbf{x}_k^* \right\| &\le \left\| \mathbf{x}_k - \mathbf{x}_{k-1}^* \right\| + \left\| \mathbf{x}_{k-1}^* - \mathbf{x}_k^* \right\| \\ &\le \left\| \mathbf{x}_k - \mathbf{x}_{k-1}^* \right\| + \frac{\delta_{k-1}-\delta_k}{\delta_{k-1}} \left\| \mathbf{x}^*-\mathbf{x}_0 \right\|. \end{align}\] Combining these yields the recurrence: \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\| \le \left(1 - \frac{\delta_k}{2}\right) \left(\left\| \mathbf{x}_k - \mathbf{x}_{k-1}^* \right\| + \frac{\delta_{k-1} - \delta_k}{\delta_{k-1}} R \right),\qquad k\ge1.\] We show \(\left\| \mathbf{x}_k - \mathbf{x}_{k-1}^* \right\| \le R\) by induction for \(k\ge1\). For the base case \(k=1\), the local contraction gives \(\left\| \mathbf{x}_1-\mathbf{x}_0^* \right\|\le\left\| \mathbf{x}_0-\mathbf{x}_0^* \right\|\), and Lemma 2 gives \(\left\| \mathbf{x}_0-\mathbf{x}_0^* \right\|\le R\). For the inductive step, assume \(\left\| \mathbf{x}_k - \mathbf{x}_{k-1}^* \right\| \le R\). With \(\delta_k = \frac{c}{k+8c}\), we have \[\frac{\delta_{k-1}-\delta_k}{\delta_{k-1}}=\frac{1}{k+8c}, \qquad \frac{\delta_k}{2}=\frac{c}{2(k+8c)}\ge\frac{1}{k+8c},\] where the last inequality uses \(c\ge2\). The recurrence therefore gives \(\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\| \le R\). Indeed, with \(a=\delta_k/2\) and \(q=(\delta_{k-1}-\delta_k)/\delta_{k-1}\), the displayed inequalities give \(q\le a\), and hence \((1-a)(1+q)\le(1-a)(1+a)\le1\). The case \(k=0\) in the lemma is immediate, since \(\left\| \mathbf{x}_0-\mathbf{x}_0 \right\|=0\). For \(k\ge0\), the established induction bound at index \(k+1\), Lemma 2 applied through the scaled-operator reduction stated after 3, and the triangle inequality give \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_0 \right\| \le \left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\| + \left\| \mathbf{x}_k^* - \mathbf{x}_0 \right\| \le R + R = 2R.\] ◻
Step 1: Fixed-operator residual contraction. For a fixed phase \(k\), define the following shorthand notation for the residuals at step \(k\): \[\mathbf{v}_1 = G_{k}(\mathbf{x}_k),\quad \mathbf{v}_2 = G_{k}(\mathbf{x}_{k+1/2}),\quad \mathbf{v}_3 = G_{k}(\mathbf{x}_{k+1}).\] A direct expansion of the difference of squared norms yields: \[\begin{align} \|\mathbf{v}_3\|^2 - \|\mathbf{v}_1\|^2 &= \bigl\|(\mathbf{v}_3 - \mathbf{v}_2) + \mathbf{v}_2\bigr\|^2 - \bigl\|(\mathbf{v}_1 - \mathbf{v}_2) + \mathbf{v}_2\bigr\|^2 \\[-0.3em] &= \|\mathbf{v}_3 - \mathbf{v}_2\|^2 \;-\;\|\mathbf{v}_1 - \mathbf{v}_2\|^2 \;+\;2\bigl\langle \mathbf{v}_3 - \mathbf{v}_1,\;\mathbf{v}_2\bigr\rangle \\[-0.3em] &\le \bigl((\eta L + \delta_{k})^2 - 1\bigr)\,\|\mathbf{v}_1 - \mathbf{v}_2\|^2 \;-\;2\,\delta_{k}\,\|\mathbf{v}_2\|^2, \end{align}\] where the final inequality uses Lipschitz continuity and strong monotonicity of \(G_k\). For Lipschitz continuity, \[\|\mathbf{v}_3 - \mathbf{v}_2\|\le(\eta L + \delta_{k})\|\mathbf{x}_{k+1}-\mathbf{x}_{k+1/2}\| =(\eta L + \delta_{k})\,\|\mathbf{v}_1 - \mathbf{v}_2\|.\] For strong monotonicity, since \(\mathbf{x}_{k+1}-\mathbf{x}_k=-\mathbf{v}_2\), \[\left\langle \mathbf{v}_3-\mathbf{v}_1,-\mathbf{v}_2 \right \rangle = \left\langle G_k(\mathbf{x}_{k+1})-G_k(\mathbf{x}_k),\mathbf{x}_{k+1}-\mathbf{x}_k \right \rangle \ge \delta_k\left\| \mathbf{x}_{k+1}-\mathbf{x}_k \right\|^2 = \delta_k\left\| \mathbf{v}_2 \right\|^2.\] Thus \(\langle \mathbf{v}_3-\mathbf{v}_1,\mathbf{v}_2\rangle\le -\delta_k\left\| \mathbf{v}_2 \right\|^2\).
We can further simplify this expression. Given our choice of parameters, we have: \[1 - (\eta L + \delta_{k})\;\ge\; 1 - (\eta L + \delta_0) \;=\; \tfrac34.\] Furthermore, applying the Lipschitz continuity of \(G_k\) between \(\mathbf{x}_k\) and \(\mathbf{x}_{k+1/2}\) gives: \[\|\mathbf{v}_1 - \mathbf{v}_2\|\le(\eta L + \delta_{k})\|\mathbf{v}_1\|,\] and then, by the reverse-triangle inequality, \[\|\mathbf{v}_2\|\ge\|\mathbf{v}_1\| - \|\mathbf{v}_1 - \mathbf{v}_2\| \ge\bigl(1 - (\eta L+\delta_k)\bigr)\|\mathbf{v}_1\| \ge\tfrac34\|\mathbf{v}_1\|,\] which in turn implies the lower bound \(\|\mathbf{v}_2\|^2\ge\tfrac{9}{16}\|\mathbf{v}_1\|^2\). We weaken this to \(\|\mathbf{v}_2\|^2\ge\tfrac12\|\mathbf{v}_1\|^2\). Since \((\eta L+\delta_k)^2-1\le0\), the first term in the preceding upper bound is non-positive and can be dropped. Substituting the lower bound on \(\left\| \mathbf{v}_2 \right\|\) back into our main inequality, we get: \[\|\mathbf{v}_3\|^2 - \|\mathbf{v}_1\|^2 \;\le\;-2\,\delta_{k}\;\tfrac12\,\|\mathbf{v}_1\|^2 \;=\;-\,\delta_k \|\mathbf{v}_1\|^2,\] which gives a direct contraction for the norm: \[\|\mathbf{v}_3\|\le\sqrt{1 - \delta_{k}}\,\|\mathbf{v}_1\| \;\le\;(1 - \tfrac{\delta_{k}}{2})\,\|\mathbf{v}_1\|.\]
Step 2: Drift from \(G_{k-1}\) to \(G_k\). Define the error at step \(k+1\) as the residual: \[E_{k+1}\;\mathrel{\vcenter{:}}=\;\|G_{k}(\mathbf{x}_{k+1})\|\;=\;\|\mathbf{v}_3\|.\] To establish a recurrence relation for \(E_k\), we first relate \(G_k(\mathbf{x}_k)\) to \(G_{k-1}(\mathbf{x}_k)\): \[G_{k}(\mathbf{x}_k)-G_{k-1}(\mathbf{x}_k) =(\delta_{k}-\delta_{k-1})(\mathbf{x}_k-\mathbf{x}_0).\] Combining this with the previously derived contraction on \(\|\mathbf{v}_3\|\) yields the following master recurrence: \[\label{eq:monotone-norm-recurrence} E_{k+1} \;\le\; \left( 1 - \tfrac{\delta_{k}}{2} \right)\, \Bigl(E_k + (\delta_{k-1}-\delta_{k})\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\Bigr), \qquad k\ge1.\tag{14}\]
Step 3: Scalar recurrence. For the base case, we examine the initialization condition: \[E_1 = \left\| G_0(\mathbf{x}_1) \right\| \le \left( 1 - \tfrac{\delta_0}{2} \right) \left\| G_0(\mathbf{x}_0) \right\| \le \eta L \left\| \mathbf{x}_0 - \mathbf{x}^* \right\| = \frac{R}{8}.\] Using the boundedness from Lemma 5 (\(\left\| \mathbf{x}_k - \mathbf{x}_0 \right\| \le 2R\)) and the base case \(E_1 \le R/8\), we apply Lemma 10 with \(\delta_k = \frac{4}{k+32}\), that is, with \(\alpha=4\), \(\beta=32\), \(\gamma=1/2\), \(c=2\), and \(c_1=1/8\). Here \[M=\max\left\{\frac{2\cdot4}{(1/2)4-1},\frac{32}{8}\right\}R=8R.\] This yields the bound: \[E_{k+1} \le \frac{8}{k + 32} R.\]
Step 4: Bias removal. Finally, using the definition of \(G_{k-1}\) and the bound on \(E_k\), we can establish the convergence rate for the original problem: \[\left\| F(\mathbf{x}_k) \right\| \le \frac{E_k + 2\delta_{k-1} R}{\eta} \le \frac{128LR}{k + 31}.\]
The past-extragradient (PEG) update, also known as Popov’s method [5], is the one-new-evaluation counterpart of extragradient in the monotone-equation setting. Instead of making two fresh queries per iteration, PEG reuses the previous operator query in the first line and makes one new query in the second line; in unconstrained Euclidean saddle-point problems, closely related one-sequence forms are often called optimistic gradient or OGDA [7].
Anchored Popov and OGDA variants are now part of the accelerated monotone operator and min-max optimization landscape, including Tran-Dinh–Luo’s Halpern-type anchored Popov scheme [11], APV and broader anchored/past-call frameworks [10], [13], fast OGDA dynamics [12], and moving-anchor Popov variants [14]. From the operator-side viewpoint in 3.1, the variant below is distinguished by where the anchor is evaluated: the anchor follows the PEG operator-query points rather than being inserted as a base-iterate correction.
The standard one-new-evaluation PEG form, written with an auxiliary sequence \((\tilde{\mathbf{x}}_k)\), is \[\tilde{\mathbf{x}}_k = \mathbf{x}_k - \eta F(\tilde{\mathbf{x}}_{k-1}), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k - \eta F(\tilde{\mathbf{x}}_k);\] we use the EG-started variant with \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\), so that the first step coincides with an extragradient step. Replacing \(F\) by the scaled regularized displacement \[G_k(\mathbf{x}) \mathrel{\vcenter{:}}= \eta F(\mathbf{x})+\delta_k(\mathbf{x}-\mathbf{x}_0)\] gives the regularized PEG (Reg-PEG) method: \[\begin{align} \tilde{\mathbf{x}}_k &= \mathbf{x}_k - G_k(\tilde{\mathbf{x}}_{k-1}), \tag{15} \\ \mathbf{x}_{k+1} &= \mathbf{x}_k - G_k(\tilde{\mathbf{x}}_k), \tag{16} \end{align}\] or, equivalently, after expanding \(G_k\), \[\tilde{\mathbf{x}}_k =\mathbf{x}_k-\eta F(\tilde{\mathbf{x}}_{k-1}) +\delta_k(\mathbf{x}_0-\tilde{\mathbf{x}}_{k-1}),\qquad \mathbf{x}_{k+1} =\mathbf{x}_k-\eta F(\tilde{\mathbf{x}}_k) +\delta_k(\mathbf{x}_0-\tilde{\mathbf{x}}_k).\] The anchor terms land at the past and current PEG operator-call points, \(\tilde{\mathbf{x}}_{k-1}\) and \(\tilde{\mathbf{x}}_k\), rather than at the base iterate \(\mathbf{x}_k\).
The closest algebraic comparator is Tran-Dinh–Luo’s anchored Popov scheme [11], \[y_k = \beta_k\mathbf{x}_0+(1-\beta_k)\mathbf{x}_k-\eta_kF(y_{k-1}), \qquad \mathbf{x}_{k+1} = \beta_k\mathbf{x}_0+(1-\beta_k)\mathbf{x}_k-\eta_kF(y_k).\] Both Popov lines therefore share the same Halpern/base displacement \(\beta_k(\mathbf{x}_0-\mathbf{x}_k)\). Nearby APV/PEAG and anchored forward-reflected or optimistic-gradient frameworks vary the past-call direction, splitting model, or parameter schedule, but still organize anchoring through a base affine point or framework-level anchor [10], [13]. Moving-anchor Popov variants replace the fixed anchor by an evolving one and should be read as proximity context, with the Popov convergence theory still less settled in that line [14].
Reg-PEG differs at the source of the anchor. It is the ordinary PEG template applied to the regularized displacement \(G_k\), so expanding each operator call places the anchor at the corresponding Popov query point: \(\delta_k(\mathbf{x}_0-\tilde{\mathbf{x}}_{k-1})\) in the past-query line and \(\delta_k(\mathbf{x}_0-\tilde{\mathbf{x}}_k)\) in the current-query line. The distinction claimed here is this operator-call anchor placement and the residual-tracking proof for the resulting update, not a priority claim for anchored Popov or OGDA acceleration as a general theme. The theorem below is the PEG counterpart of the Reg-EG residual bound, attained at one new \(F\)-evaluation per iteration rather than two.
Theorem 3 (Last-Iterate Residual Bound for Reg-PEG). Let \(F:\mathcal{H}\to\mathcal{H}\) be a monotone, \(L\)-Lipschitz operator with \(L>0\) and a solution \(\mathbf{x}^*\) such that \(F(\mathbf{x}^*) = \mathbf{0}\). Consider the Reg-PEG method defined by 15 –16 , initialized with main iterate \(\mathbf{x}_0\) and \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\), with parameters \(\eta = \frac{1}{8L}\) and \(\delta_k = \frac{8}{k+64}\) for \(k \ge 0\). Let \(R \mathrel{\vcenter{:}}= \left\| \mathbf{x}_0 - \mathbf{x}^* \right\|\). Then, for all \(k\ge1\), the iterates satisfy: \[r_F(\mathbf{x}_k)=\left\| F(\mathbf{x}_k) \right\| \le \frac{256LR}{k+63}.\]
The proof, although more involved, follows the shared progress–drift–bias architecture, with a PEG residual potential adapted to the staggered operator-call points in 15 –16 . First, for a fixed \(G_k\), a PEG step contracts a two-component regularized-residual potential. Second, a Lyapunov argument gives the trajectory bound \(\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\le2R\). Third, the change from \(G_{k-1}\) to \(G_k\) adds the drift term \((\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\). Fourth, the recurrence lemma bounds the regularized residual potential, and the identity \(G_{k-1}(\cdot)=\eta F(\cdot)+\delta_{k-1}(\cdot-\mathbf{x}_0)\) removes the bias to recover \(r_F(\mathbf{x}_k)\).
Lemma 6 (One-step Reg-PEG displacement bound). For the Reg-PEG update at phase \(k\), suppose that \(G_k\) is \(\delta_k\)-strongly monotone, at most \(1/4\)-Lipschitz, and has zero \(\mathbf{x}_k^*\). Then \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 \le (1 - \delta_k)\left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|^2 - (1-2\delta_k)\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2 + \frac{1}{16}\left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2.\]
Proof. We begin by establishing a lower bound on the term \(2 \left\langle G_k(\tilde{\mathbf{x}}_k), \tilde{\mathbf{x}}_k - \mathbf{x}_k^* \right \rangle\). Using the \(\delta_k\)-strong monotonicity of \(G_k\) and the inequality \(\left\| \mathbf{a}+\mathbf{b} \right\|^2 \le 2\left\| \mathbf{a} \right\|^2 + 2\left\| \mathbf{b} \right\|^2\), we have: \[\begin{align} 2 \left\langle G_k(\tilde{\mathbf{x}}_k), \tilde{\mathbf{x}}_k - \mathbf{x}_k^* \right \rangle &\ge 2\delta_k\left\| \tilde{\mathbf{x}}_k-\mathbf{x}_k^* \right\|^2 \\ &\ge \delta_k\left(\left\| \mathbf{x}_k-\mathbf{x}_k^* \right\|^2 - 2\left\| \mathbf{x}_k-\tilde{\mathbf{x}}_k \right\|^2\right). \end{align}\] Next, we derive an upper bound for the same term. From the update rule, we know that \(G_k(\tilde{\mathbf{x}}_k) = \mathbf{x}_k - \mathbf{x}_{k+1}\). Substituting this into the expression gives: \[\begin{align} 2 \left\langle G_k(\tilde{\mathbf{x}}_k), \tilde{\mathbf{x}}_k - \mathbf{x}_k^* \right \rangle &= 2\left\langle \mathbf{x}_k-\mathbf{x}_{k+1}, \tilde{\mathbf{x}}_k-\mathbf{x}_k^* \right \rangle \\ &= \left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|^2 - \left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 - \left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2 + \left\| \tilde{\mathbf{x}}_k - \mathbf{x}_{k+1} \right\|^2. \end{align}\] The final term in this expression can be bounded using the Lipschitz property of \(G_k\): \[\left\| \tilde{\mathbf{x}}_k - \mathbf{x}_{k+1} \right\|^2 = \left\| G_k(\tilde{\mathbf{x}}_k) - G_k(\tilde{\mathbf{x}}_{k-1}) \right\|^2 \le \frac{1}{16} \left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2.\] Combining the lower and upper bounds and rearranging the terms yields the result. ◻
Lemma 7 (Boundedness of the Reg-PEG trajectory). Let \(F:\mathcal{H}\to\mathcal{H}\) be monotone and \(L\)-Lipschitz with \(L>0\), and let \(\mathbf{x}^*\) satisfy \(F(\mathbf{x}^*)=\mathbf{0}\). Set \(R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|\). For the Reg-PEG scheme 15 –16 with \(\eta=\frac{1}{8L}\), \(\delta_k=\frac{8}{k+64}\), and \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\), the iterates satisfy \[\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\le 2R,\qquad k\ge0.\]
Proof. Let \(\mathbf{x}_k^*\) denote the unique zero of \(G_k\). We set the step size to \(\eta = \frac{1}{8L}\) and use \(\delta_k \le \delta_0 = \frac{1}{8}\). This choice ensures that \(G_k\) is at most \(1/4\)-Lipschitz for any \(k \ge 0\). For \(k\ge1\), our immediate goal is to prove the following inequality, which indicates that a specific Lyapunov function is contracting: \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \le \left(1 - \delta_k\right) \left( \left\| \mathbf{x}_{k} - \mathbf{x}_k^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2 \right).\] We first apply 6, and then relate \(\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2\) to quantities from the previous iteration. By the triangle inequality and the update rule: \[\begin{align} \left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 &\le 2\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2 + 2\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \\ &\le 2\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2 + 2\left\| G_{k-1}(\tilde{\mathbf{x}}_{k-2}) - G_{k-1}(\tilde{\mathbf{x}}_{k-1}) \right\|^2 \\ &\le 2\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2 + \frac{1}{8} \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2. \end{align}\] Rearranging this gives a lower bound on \(\left\| \mathbf{x}_k - \tilde{\mathbf{x}}_k \right\|^2\), which we substitute into the result of 6: \[\begin{align} \left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 \le{}& \left(1-\delta_k\right)\left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|^2 + \frac{1}{16}\left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \\ & - \left(1-2\delta_k\right)\left(\frac{1}{2}\left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 - \frac{1}{16}\left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2\right) \\ =& \left(1-\delta_k\right)\left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|^2 + \left[\frac{1}{16} - \frac{1}{2}\left(1- 2 \delta_k\right)\right]\left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \\ & + \frac{1}{16}\left(1-2\delta_k\right)\left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2. \end{align}\] After rearranging, we get: \[\begin{align} &\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 + \left( \frac{7}{16} - \delta_k \right) \left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \\ &\qquad\le \left(1-\delta_k\right)\left\| \mathbf{x}_k - \mathbf{x}_k^* \right\|^2 + \frac{1}{16}\left(1-2\delta_k\right) \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2. \end{align}\] Given our choice of \(\delta_k \le 1/8\), we have \((7/16-\delta_k)\ge1/16\) and \((1-2\delta_k)/16\le(1-\delta_k)/16\). Therefore the previous display implies \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\|^2 +\frac{1}{16}\left\| \tilde{\mathbf{x}}_k - \tilde{\mathbf{x}}_{k-1} \right\|^2 \le (1-\delta_k)\left( \left\| \mathbf{x}_{k} - \mathbf{x}_k^* \right\|^2 +\frac{1}{16}\left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2 \right).\] This allows us to define the Lyapunov function. For \(j\ge1\), set \[B_j\mathrel{\vcenter{:}}= \sqrt{\left\| \mathbf{x}_{j} - \mathbf{x}_{j-1}^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_{j-1} - \tilde{\mathbf{x}}_{j-2} \right\|^2}.\] Then for \(k\ge1\), \[\begin{align} B_{k+1} &\le \sqrt{\left(1 - \delta_k\right) \left( \left\| \mathbf{x}_{k} - \mathbf{x}_k^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2 \right)} \\ &\le \left( 1 - \frac{\delta_k}{2} \right) \sqrt{ \left\| \mathbf{x}_{k} - \mathbf{x}_k^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2} \\ &\le \left( 1 - \frac{\delta_k}{2} \right) \left( \sqrt{ \left\| \mathbf{x}_{k} - \mathbf{x}_{k-1}^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_{k-1} - \tilde{\mathbf{x}}_{k-2} \right\|^2} + \left\| \mathbf{x}_{k-1}^* - \mathbf{x}_k^* \right\| \right). \end{align}\] Here, the second inequality uses \(\sqrt{1 - x} \le 1 - x/2\) for \(x \in [0,1]\), and the third inequality uses the triangle inequality property \(\sqrt{\left\| \mathbf{a} + \mathbf{b} \right\|^2 + \left\| \mathbf{c} \right\|^2} \le \sqrt{\left\| \mathbf{a} \right\|^2 + \left\| \mathbf{c} \right\|^2} + \left\| \mathbf{b} \right\|\). Applying the bound on the stability of the regularized solution from 3, we have: \[B_{k+1} \le \left( 1 - \frac{\delta_k}{2} \right) \left( B_k + \frac{\delta_{k-1} - \delta_k}{\delta_{k-1}} R \right).\] We now use induction to show that the iterates are bounded, i.e., \(B_k \le R\). For the base case \(k = 1\), we use the \(k=0\) instance of 6, add the term \(\frac{1}{16}\left\| \tilde{\mathbf{x}}_0-\tilde{\mathbf{x}}_{-1} \right\|^2\), and use \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\). Together with 2, this gives \[\begin{align} B_1^2 &= \left\| \mathbf{x}_{1} - \mathbf{x}_0^* \right\|^2 + \frac{1}{16} \left\| \tilde{\mathbf{x}}_0 - \tilde{\mathbf{x}}_{-1} \right\|^2 \\ &\le (1 - \delta_0)\left\| \mathbf{x}_0 - \mathbf{x}_0^* \right\|^2 - (1 - 2\delta_0) \left\| \mathbf{x}_0 - \tilde{\mathbf{x}}_0 \right\|^2 + \frac{1}{8}\left\| \mathbf{x}_0 - \tilde{\mathbf{x}}_0 \right\|^2 \\ &\le \left\| \mathbf{x}_0 - \mathbf{x}_0^* \right\|^2 \le R^2. \end{align}\] Assuming \(B_k \le R\) holds, and writing \(\delta_k = \frac{c}{k + 8c}\) with \(c=8\), we use \[\frac{\delta_{k-1}-\delta_k}{\delta_{k-1}}=\frac{1}{k+8c}, \qquad \frac{\delta_k}{2}=\frac{c}{2(k+8c)}\ge\frac{1}{k+8c},\] where the last inequality follows from the weaker bound \(c\ge2\). Therefore \[\begin{align} B_{k+1} \le \left( 1 - \frac{1}{k + 8c} \right) \left( R + \frac{1}{k + 8c} R \right) \le R. \end{align}\] This completes the induction. The case \(k=0\) is immediate because \(\left\| \mathbf{x}_0-\mathbf{x}_0 \right\|=0\). For \(k\ge0\), the induction bound at index \(k+1\) implies that the trajectory is bounded: \[\left\| \mathbf{x}_{k+1} - \mathbf{x}_0 \right\| \le \left\| \mathbf{x}_{k+1} - \mathbf{x}_k^* \right\| + \left\| \mathbf{x}_k^* - \mathbf{x}_0 \right\| \le R+R = 2R.\] ◻
Lemma 8 (PEG Residual-Potential Contraction). Let \(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\in\mathcal{H}\) and suppose \(0 < \delta \le \frac{1}{3}\). We assume the following two conditions hold: \[\begin{align} \langle \mathbf{b}-\mathbf{a}, \mathbf{c}\rangle &\ge \delta \left\| \mathbf{c} \right\|^{2}, && \text{(strong monotonicity)}\label{eq:monotone}\\ \left\| \mathbf{a}-\mathbf{c} \right\| &\le \frac{1}{3}\left\| \mathbf{c}-\mathbf{d} \right\|, && \text{(Lipschitzness)}\label{eq:lipschitz} \end{align}\] {#eq: sublabel=eq:eq:monotone,eq:eq:lipschitz} Define a potential function \(\Phi(\mathbf{x}, \mathbf{y}) := \left\| \mathbf{x} \right\|^{2} + 2\left\| \mathbf{x}-\mathbf{y} \right\|^{2}\). Then \[\Phi(\mathbf{a}, \mathbf{c}) \le \bigl(1 - \tfrac{\delta}{2}\bigr) \Phi(\mathbf{b}, \mathbf{d}).\label{eq:goal}\qquad{(1)}\]
Proof. The proof proceeds by establishing a lower bound on the difference \(\Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c})\) and showing that this is greater than or equal to \(\frac{\delta}{2}\Phi(\mathbf{b}, \mathbf{d})\).
Expand the difference between the potentials: \[\begin{align} \Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) &= \bigl(\left\| \mathbf{b} \right\|^{2}-\left\| \mathbf{a} \right\|^{2}\bigr) + 2\bigl(\left\| \mathbf{b}-\mathbf{d} \right\|^{2}-\left\| \mathbf{a}-\mathbf{c} \right\|^{2}\bigr). \end{align}\] We first find a lower bound for the term \(\left\| \mathbf{b} \right\|^{2}-\left\| \mathbf{a} \right\|^{2}\). By decomposing \(\mathbf{a}\) as \((\mathbf{a}-\mathbf{c})+\mathbf{c}\) and invoking the strong monotonicity condition from ?? , we obtain: \[\begin{align} \left\| \mathbf{b} \right\|^{2}-\left\| \mathbf{a} \right\|^{2} &= \left\| \mathbf{b}-\mathbf{a} \right\|^{2}+2\langle \mathbf{a}, \mathbf{b}-\mathbf{a}\rangle \\ &= \left\| \mathbf{b}-\mathbf{a} \right\|^{2}+2\langle \mathbf{a}-\mathbf{c}, \mathbf{b}-\mathbf{a}\rangle + 2\langle \mathbf{c}, \mathbf{b}-\mathbf{a}\rangle \\ &\ge \left\| \mathbf{b}-\mathbf{a} \right\|^{2}+2\langle \mathbf{a}-\mathbf{c}, \mathbf{b}-\mathbf{a}\rangle + 2\delta \left\| \mathbf{c} \right\|^{2}. \end{align}\] Using the identity \(\left\| \mathbf{x} \right\|^2 + 2\langle \mathbf{y}, \mathbf{x} \rangle = \left\| \mathbf{x}+\mathbf{y} \right\|^2 - \left\| \mathbf{y} \right\|^2\) with \(\mathbf{x} = \mathbf{b}-\mathbf{a}\) and \(\mathbf{y} = \mathbf{a}-\mathbf{c}\), the first two terms simplify to \(\left\| \mathbf{b}-\mathbf{c} \right\|^{2}-\left\| \mathbf{a}-\mathbf{c} \right\|^{2}\). This gives: \[\left\| \mathbf{b} \right\|^{2}-\left\| \mathbf{a} \right\|^{2} \ge \left\| \mathbf{b}-\mathbf{c} \right\|^{2}-\left\| \mathbf{a}-\mathbf{c} \right\|^{2}+2\delta \left\| \mathbf{c} \right\|^{2}.\] Substituting this result back into the expression for the potential difference yields: \[\label{eq:gf-first} \Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) \ge \left\| \mathbf{b}-\mathbf{c} \right\|^{2} + 2\left\| \mathbf{b}-\mathbf{d} \right\|^{2} - 3\left\| \mathbf{a}-\mathbf{c} \right\|^{2} + 2\delta \left\| \mathbf{c} \right\|^{2}.\tag{17}\] Next, we apply the Lipschitz bound from ?? to handle the negative term involving \(\mathbf{a}-\mathbf{c}\): \[\label{eq:gf-second} \Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) \ge \left\| \mathbf{b}-\mathbf{c} \right\|^{2} + 2\left\| \mathbf{b}-\mathbf{d} \right\|^{2} - \frac{1}{3}\left\| \mathbf{d}-\mathbf{c} \right\|^{2} + 2\delta \left\| \mathbf{c} \right\|^{2}.\tag{18}\]
Our next step is to relate this lower bound to \(\Phi(\mathbf{b}, \mathbf{d})\). We establish an upper bound for \(\frac{\delta}{2} \Phi(\mathbf{b}, \mathbf{d})\) by applying the triangle inequality in the form \(\left\| \mathbf{x}+\mathbf{y} \right\|^2 \le 2(\left\| \mathbf{x} \right\|^2 + \left\| \mathbf{y} \right\|^2)\), which gives \(\left\| \mathbf{b} \right\|^2 = \left\| (\mathbf{b}-\mathbf{c})+\mathbf{c} \right\|^2 \le 2(\left\| \mathbf{b}-\mathbf{c} \right\|^2 + \left\| \mathbf{c} \right\|^2)\). Therefore, \[\label{eq:half-g} \frac{\delta}{2} \Phi(\mathbf{b}, \mathbf{d}) = \frac{\delta}{2}\bigl(\left\| \mathbf{b} \right\|^{2}+2\left\| \mathbf{b}-\mathbf{d} \right\|^{2}\bigr) \le \delta\bigl(\left\| \mathbf{b}-\mathbf{c} \right\|^{2}+\left\| \mathbf{c} \right\|^{2}+\left\| \mathbf{b}-\mathbf{d} \right\|^{2}\bigr).\tag{19}\]
Finally, we combine our results. Subtracting the bound in 19 from the inequality in 18 yields: \[\begin{align} \Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) - \tfrac{\delta}{2} \Phi(\mathbf{b}, \mathbf{d}) &\ge (1-\delta)\left\| \mathbf{b}-\mathbf{c} \right\|^{2} + (2-\delta)\left\| \mathbf{b}-\mathbf{d} \right\|^{2} - \frac{1}{3}\left\| \mathbf{d}-\mathbf{c} \right\|^{2} + \delta \left\| \mathbf{c} \right\|^{2}. \end{align}\] To simplify the right-hand side, we again use the triangle inequality: \[\left\| \mathbf{d}-\mathbf{c} \right\|^{2} = \left\| (\mathbf{d}-\mathbf{b})+(\mathbf{b}-\mathbf{c}) \right\|^2 \le 2\left\| \mathbf{b}-\mathbf{d} \right\|^{2} +2\left\| \mathbf{b}-\mathbf{c} \right\|^{2}.\] This leads to: \[\begin{align} \bigl(1 - \tfrac{\delta}{2}\bigr)\Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) &\ge \bigl(1-\delta - \tfrac{2}{3}\bigr)\left\| \mathbf{b}-\mathbf{c} \right\|^{2} + \bigl(2-\delta - \tfrac{2}{3}\bigr)\left\| \mathbf{b}-\mathbf{d} \right\|^{2}+\delta \left\| \mathbf{c} \right\|^{2} \\ &= \bigl(\tfrac{1}{3}-\delta\bigr)\left\| \mathbf{b}-\mathbf{c} \right\|^{2} + \bigl(\tfrac{4}{3}-\delta\bigr)\left\| \mathbf{b}-\mathbf{d} \right\|^{2}+\delta \left\| \mathbf{c} \right\|^{2}. \end{align}\] Since we assumed \(0 < \delta \le \frac{1}{3}\), all the coefficients on the right-hand side are non-negative, which implies the entire expression is non-negative. Thus, \[\bigl(1 - \tfrac{\delta}{2}\bigr)\Phi(\mathbf{b}, \mathbf{d}) - \Phi(\mathbf{a}, \mathbf{c}) \ge 0,\] which rearranges to \(\Phi(\mathbf{a}, \mathbf{c}) \le \left( 1 - \delta/2 \right)\Phi(\mathbf{b}, \mathbf{d})\), the desired result. ◻
Lemma 9 (Two-component norm perturbation). Let \((\mathcal{X},\|\cdot\|)\) be a normed space. For any \(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\in\mathcal{X}\) with \(\|\mathbf{b}\|\le\|\mathbf{d}\|\), \[\sqrt{\|\mathbf{a}\|^{2}+\|\mathbf{b}\|^{2}} \;\le\; \sqrt{\|\mathbf{c}\|^{2}+\|\mathbf{d}\|^{2}} +\|\mathbf{a}-\mathbf{c}\|.\]
Proof. Since \(\|\mathbf{b}\|\le\|\mathbf{d}\|\), \[\sqrt{\|\mathbf{a}\|^{2}+\|\mathbf{b}\|^{2}} \le \sqrt{\|\mathbf{a}\|^{2}+\|\mathbf{d}\|^{2}}.\] We can view the pair of scalar norms \((\|\mathbf{a}\|,\|\mathbf{d}\|)\) as a vector in \(\mathbb{R}^{2}\) and write \[(\|\mathbf{a}\|,\|\mathbf{d}\|) = (\|\mathbf{c}\|,\|\mathbf{d}\|)+(\|\mathbf{a}\|-\|\mathbf{c}\|,0).\] Applying the standard triangle inequality for vectors in \(\mathbb{R}^{2}\) gives \[\sqrt{\|\mathbf{a}\|^{2}+\|\mathbf{d}\|^{2}} \le \sqrt{\|\mathbf{c}\|^{2}+\|\mathbf{d}\|^{2}} +|\|\mathbf{a}\|-\|\mathbf{c}\|| \le \sqrt{\|\mathbf{c}\|^{2}+\|\mathbf{d}\|^{2}} +\|\mathbf{a}-\mathbf{c}\|,\] where the last step follows from the reverse triangle inequality. Combining the two displayed inequalities yields the claim. ◻
Before the algebra, we record the bookkeeping. The fixed-\(G_k\) PEG step contracts a two-component residual potential at the staggered pair \((\mathbf{x}_{k+1},\tilde{\mathbf{x}}_k)\). Then 9 compares the \(G_k\)-potential at \(\mathbf{x}_k\) with the previous \(G_{k-1}\)-potential, losing only the drift term \((\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\). The trajectory bound turns this drift into \(2(\delta_{k-1}-\delta_k)R\), after which the scalar recurrence lemma gives the displayed residual rate.
Define \[E_0 \mathrel{\vcenter{:}}= \sqrt{\|G_0(\mathbf{x}_0)\|^2 +2\|G_0(\mathbf{x}_0)-G_0(\tilde{\mathbf{x}}_{-1})\|^2},\] and, for \(k\ge1\), \[E_k \mathrel{\vcenter{:}}= \sqrt{\|G_{k-1}(\mathbf{x}_k)\|^2 +2\|G_{k-1}(\mathbf{x}_k)-G_{k-1}(\tilde{\mathbf{x}}_{k-1})\|^2}.\]
Step 1: Fixed-operator residual-potential contraction. For a fixed \(k\), set \[\mathbf{a}=G_k(\mathbf{x}_{k+1}),\quad \mathbf{b}=G_k(\mathbf{x}_k),\quad \mathbf{c}=G_k(\tilde{\mathbf{x}}_k),\quad \mathbf{d}=G_k(\tilde{\mathbf{x}}_{k-1}).\] The update rules give \(\mathbf{c}=\mathbf{x}_k-\mathbf{x}_{k+1}\) and \(\tilde{\mathbf{x}}_k=\mathbf{x}_k-\mathbf{d}\). Hence \[\mathbf{d}-\mathbf{c} = (\mathbf{x}_k-\tilde{\mathbf{x}}_k)-(\mathbf{x}_k-\mathbf{x}_{k+1}) = \mathbf{x}_{k+1}-\tilde{\mathbf{x}}_k.\] Strong monotonicity of \(G_k\) gives \[\left\langle \mathbf{b}-\mathbf{a},\mathbf{c} \right \rangle = \left\langle G_k(\mathbf{x}_k)-G_k(\mathbf{x}_{k+1}),\mathbf{x}_k-\mathbf{x}_{k+1} \right \rangle \ge \delta_k\left\| \mathbf{c} \right\|^2.\] Since \(\delta_k\le\delta_0=1/8<1/3\) and \(\eta L+\delta_k\le1/4\), Lipschitzness gives \[\left\| \mathbf{a}-\mathbf{c} \right\| \le (\eta L+\delta_k)\left\| \mathbf{x}_{k+1}-\tilde{\mathbf{x}}_k \right\| \le \frac{1}{4}\left\| \mathbf{d}-\mathbf{c} \right\| \le \frac{1}{3}\left\| \mathbf{d}-\mathbf{c} \right\|.\] Applying 8 yields \[\begin{align} &\|G_k(\mathbf{x}_{k+1})\|^2 +2\|G_k(\mathbf{x}_{k+1})-G_k(\tilde{\mathbf{x}}_k)\|^2 \\ &\qquad\le \left(1-\frac{\delta_k}{2}\right) \left( \|G_k(\mathbf{x}_k)\|^2 +2\|G_k(\mathbf{x}_k)-G_k(\tilde{\mathbf{x}}_{k-1})\|^2 \right). \end{align}\] The left-hand side is \(E_{k+1}^2\) by the staggered definition of \(E_{k+1}\). Taking square roots and using \(\sqrt{1-z}\le1-z/2\) with \(z=\delta_k/2\) gives \[E_{k+1} \le \left(1-\frac{\delta_k}{4}\right) \sqrt{ \|G_k(\mathbf{x}_k)\|^2 +2\|G_k(\mathbf{x}_k)-G_k(\tilde{\mathbf{x}}_{k-1})\|^2}.\]
Step 2: Drift from \(G_{k-1}\) to \(G_k\). It remains to compare the \(G_k\)-potential at \(\mathbf{x}_k\) with \(E_k\). By monotonicity of \(F\) and \(\delta_k\le\delta_{k-1}\), \[\begin{align} &2\left\| G_k(\mathbf{x}_k)-G_k(\tilde{\mathbf{x}}_{k-1}) \right\|^2 -2\left\| G_{k-1}(\mathbf{x}_k)-G_{k-1}(\tilde{\mathbf{x}}_{k-1}) \right\|^2 \\ &= 4\eta(\delta_k-\delta_{k-1}) \left\langle F(\mathbf{x}_k)-F(\tilde{\mathbf{x}}_{k-1}),\mathbf{x}_k-\tilde{\mathbf{x}}_{k-1} \right \rangle {}+ 2(\delta_k^2-\delta_{k-1}^2) \left\| \mathbf{x}_k-\tilde{\mathbf{x}}_{k-1} \right\|^2 \le0. \end{align}\] Indeed, with \(\mathbf{u}=F(\mathbf{x}_k)-F(\tilde{\mathbf{x}}_{k-1})\) and \(\mathbf{w}=\mathbf{x}_k-\tilde{\mathbf{x}}_{k-1}\), monotonicity gives \(\left\langle \mathbf{u},\mathbf{w} \right \rangle\ge0\). Since \(\delta_k-\delta_{k-1}\le0\) and \(\delta_k^2-\delta_{k-1}^2\le0\), both terms in the displayed difference are non-positive. Moreover, \[\left\| G_k(\mathbf{x}_k)-G_{k-1}(\mathbf{x}_k) \right\| = (\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|.\] For the notation of 9, take \[\begin{align} \mathbf{a}&=G_k(\mathbf{x}_k),& \mathbf{c}&=G_{k-1}(\mathbf{x}_k),\\ \mathbf{b}&=\sqrt{2}\big(G_k(\mathbf{x}_k)-G_k(\tilde{\mathbf{x}}_{k-1})\big),& \mathbf{d}&=\sqrt{2}\big(G_{k-1}(\mathbf{x}_k)-G_{k-1}(\tilde{\mathbf{x}}_{k-1})\big). \end{align}\] The preceding display gives \(\left\| \mathbf{b} \right\|\le\left\| \mathbf{d} \right\|\), and the drift bound gives \(\left\| \mathbf{a}-\mathbf{c} \right\|\le(\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|\). Applying 9 to the two-component norm gives, for \(k\ge1\), \[E_{k+1} \le \left(1-\frac{\delta_k}{4}\right) \left( E_k+(\delta_{k-1}-\delta_k)\left\| \mathbf{x}_k-\mathbf{x}_0 \right\| \right).\] By 7, \[E_{k+1} \le \left(1-\frac{\delta_k}{4}\right) \left(E_k+2(\delta_{k-1}-\delta_k)R\right), \qquad k\ge1.\]
Step 3: Scalar recurrence. For the base case, since \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\), \[E_0=\left\| G_0(\mathbf{x}_0) \right\| =\eta\left\| F(\mathbf{x}_0) \right\| \le \eta L R=\frac{R}{8}.\] Because \(\tilde{\mathbf{x}}_{-1}=\mathbf{x}_0\), the right-hand potential in the fixed-operator contraction at \(k=0\) is exactly \(E_0\). Hence \(E_1\le(1-\delta_0/4)E_0\le E_0\le R/8\). Applying 10 with \[\delta_k=\frac{8}{k+64},\qquad \alpha=8,\qquad \beta=64,\qquad \gamma=\frac{1}{4},\qquad c=2,\qquad c_1=\frac{1}{8}\] gives \[E_k\le \frac{16R}{k+63},\qquad k\ge1.\]
Step 4: Bias removal. Finally, for \(k\ge1\), \[\left\| F(\mathbf{x}_k) \right\| \le \frac{E_k+\delta_{k-1}\left\| \mathbf{x}_k-\mathbf{x}_0 \right\|}{\eta} \le \frac{E_k+2\delta_{k-1}R}{\eta} \le \frac{256LR}{k+63}.\]
Anchoring is often presented as a structural change to the base algorithm, and the role of the anchor and its placement can be unintuitive, even when the resulting rates are sharp. This work focuses on an operator-side view of anchoring for fixed-point and monotone-equation methods: apply a vanishing Tikhonov term to the queried operator or displacement, then run the standard Picard, forward, extragradient, or Popov past-extragradient template on the resulting moving regularized object. A single analysis framework captures the intuition: the method makes more rapid progress on a better conditioned problem, while the parameters balance that progress against the bias with respect to the original problem. More importantly, this perspective clarifies the mechanism of anchoring “acceleration” and has directly led to several new results presented in this paper.
The results are established in a simple single-valued unconstrained setting to keep the mechanism transparent. Extensions to monotone inclusions and variational inequalities are natural follow-ups.
We use the following deterministic recurrence lemma throughout the manuscript.
Lemma 10. Let \(c,c_1,\alpha,\beta,\gamma>0\) and \(R\ge0\) with \(1 < \gamma \alpha \le \beta\) and define \[\delta_n \;=\; \frac{\alpha}{\,n+\beta\,}, \qquad n\ge0.\] Assume the sequence \((e_n)_{n\ge 1}\) satisfies \(e_1 \le c_1\,R\) and \[\label{eq:rec} e_{n+1} \le \bigl(1-\gamma\delta_n\bigr) \Bigl(e_{n}+c\,(\delta_{n-1}-\delta_n)\,R\Bigr), \qquad n\ge 1.\qquad{(2)}\] Then for every \(n\ge 1\), \[e_n \le \frac{M}{n + \beta - 1}, \quad \text{where } M := R\max\!\bigl\{ \tfrac{c\,\alpha}{\gamma\alpha-1}, \;c_1\beta \bigr\}.\]
Proof. We prove by induction that \(e_n\le M/(n+\beta-1)\) for all \(n\ge 1\).
Base case (\(n=1\)). By the definition of \(M\) we have \[e_1 \;\le\; c_1R \;\le\; \frac{M}{\beta}.\]
Inductive step. Assume \(e_{n}\le M/(n-1+\beta)\) for some \(n\ge 1\). Since \(\delta_{n-1}-\delta_n =\dfrac{\alpha}{(n-1+\beta)(n+\beta)},\) recurrence ?? yields \[\begin{align} e_{n+1} &\le \Bigl(1-\frac{\gamma\alpha}{n+\beta}\Bigr) \Bigl( \frac{M}{n-1+\beta} +\frac{c\alpha R}{(n-1+\beta)(n+\beta)} \Bigr) \\[4pt] &= \frac{M(1-\gamma\alpha)+c\alpha R -\dfrac{\gamma\alpha\,c\alpha R}{n+\beta}}{(n-1+\beta)(n+\beta)} \;+\; \frac{M}{n+\beta}. \end{align}\] By the definition of \(M\), \[M \;\ge\; \frac{c\alpha R}{\gamma\alpha-1} \;\Longrightarrow\; M(1-\gamma\alpha)+c\alpha R \;\le\; 0.\] Hence the first fraction is non-positive, giving \(e_{n+1}\le M/(n+\beta).\) Thus the inductive step closes and the claimed bound holds for all \(n\ge 1\), implying \(e_n=O(1/n)\). ◻
Here we present an episodic fixed-point variant of the tracking argument. From the operator-side viewpoint, this is a natural continuation scheme: for a fixed value of \(\delta_k\), the map \(T_k\) is contractive, so one may take several Picard steps on the current regularized problem and then warm-start the next, less regularized phase. The proposition below measures the resulting residual in terms of the total number of inner Picard steps.
Formally, at each phase \(k\), apply the operator \(T_k\) for \(t_k\) iterations, initialized from the output of the previous phase: \[\mathbf{x}_{k+1} = (T_k)^{t_k}(\mathbf{x}_k) \equiv \underbrace{T_k \circ \cdots \circ T_k}_{t_k \text{ times}}(\mathbf{x}_k).\]
Proposition 2 (Episodic Halpern Scheme with Geometric Rate). Let \(T\) be a nonexpansive mapping with \(\operatorname{Fix}(T) \ne \varnothing\). Consider the episodic scheme where \[\mathbf{x}_{k+1} = (T_k)^{t_k}(\mathbf{x}_k), \qquad T_k(\mathbf{x}) \mathrel{\vcenter{:}}= (1-\delta_k) T(\mathbf{x}) + \delta_k \mathbf{x}_0.\] Fix any \(\mathbf{x}^*\in\operatorname{Fix}(T)\) and set \(R\mathrel{\vcenter{:}}=\left\| \mathbf{x}_0-\mathbf{x}^* \right\|\). With \(\delta_k = 2^{-k}\) and \(t_k = \lceil \ln(4)/\delta_k \rceil\), the residual norm after \(K\) phases satisfies \[\left\| \mathbf{x}_K - T(\mathbf{x}_K) \right\| \le 12R\,2^{-K}, \qquad K\ge1.\] Furthermore, in terms of the total number of inner iterations \(N_K = \sum_{j=0}^{K-1} t_j\), this gives \[\left\| \mathbf{x}_K - T(\mathbf{x}_K) \right\| = O\left(\frac{R}{N_K}\right).\]
Proof. The analysis follows the same structure as the Halpern proof in the main text. The ball \(B(\mathbf{x}^*,R)\) is invariant under each \(T_k\): if \(\left\| \mathbf{x}-\mathbf{x}^* \right\|\le R\), then \[\left\| T_k(\mathbf{x})-\mathbf{x}^* \right\| \le (1-\delta_k)\left\| T(\mathbf{x})-\mathbf{x}^* \right\| +\delta_k\left\| \mathbf{x}_0-\mathbf{x}^* \right\| \le R.\] Thus \(\mathbf{x}_k\in B(\mathbf{x}^*,R)\) for all \(k\), and in particular \(\left\| T(\mathbf{x}_k)-\mathbf{x}_0 \right\|\le2R\). For \(k\ge1\), let \(E_k \mathrel{\vcenter{:}}= \left\| \mathbf{x}_k - T_{k-1}(\mathbf{x}_k) \right\|\). If \(S\) is a \(q\)-contraction, then \(\left\| S^t\mathbf{x}-S^{t+1}\mathbf{x} \right\|\le q^t\left\| \mathbf{x}-S\mathbf{x} \right\|\). Applying this with \(S=T_k\) gives \[E_{k+1} \le (1-\delta_k)^{t_k} \left(E_k + 2(\delta_{k-1} - \delta_k)R\right), \qquad k\ge1.\] For \(\delta_k = 2^{-k}\), we have \(\delta_{k-1} - \delta_k = \delta_k\) for \(k \ge 1\). Setting \(t_k = \lceil \ln(4)/\delta_k \rceil\) gives \((1-\delta_k)^{t_k} \le e^{-\delta_k t_k} \le 1/4\), and therefore \[E_{k+1} \le \frac{1}{4}(E_k + 2\delta_k R).\] Since \(\delta_0=1\), \(T_0\) is the constant map \(\mathbf{x}\mapsto \mathbf{x}_0\), so \(E_1=0\le 4R\delta_0\). We prove by induction that \(E_k\le 4R\delta_{k-1}\) for all \(k\ge1\). If \(E_{k} \le 4R\delta_{k-1}\), then \[E_{k+1} \le \frac{1}{4}(4R\delta_{k-1} + 2R\delta_k) = \frac{1}{4}(8R\delta_k + 2R\delta_k) = \frac{5}{2}R\delta_k \le 4R\delta_k.\] Hence, by induction, \[\left\| \mathbf{x}_k - T(\mathbf{x}_k) \right\| \le E_k + \delta_{k-1}\left\| \mathbf{x}_0 - T(\mathbf{x}_k) \right\| \le 4R\delta_{k-1} + 2R\delta_{k-1} = 6R\delta_{k-1}.\] At \(k=K\ge1\), this gives \(\left\| \mathbf{x}_K - T(\mathbf{x}_K) \right\|\le 6R\delta_{K-1}=12R2^{-K}\). Also, \[N_K=\sum_{j=0}^{K-1}\left\lceil (\ln 4)2^j\right\rceil \le (\ln4+1)(2^K-1),\] so \(N_K+\ln4+1\le(\ln4+1)2^K\), or equivalently \(2^{-K}\le(\ln4+1)/(N_K+\ln4+1)\). The same bound is therefore \(O(R/N_K)\). ◻
Here we present the viscosity generalization of the same fixed-point regularization. The fixed anchor \(\mathbf{x}_0\) is the special case of a constant contraction \(g\equiv\mathbf{x}_0\). Viscosity approximation replaces this constant map by a general contraction \(g\), a standard generalization of Halpern/Browder fixed-point regularization [17], [18]. The proposition below shows that the same moving-contraction tracking proof applies to this form. Given a map \(g:\mathcal{X}\to\mathcal{X}\) and parameters \((\delta_k)\), define \[\label{eq:halpern95viscosity} T_k(\mathbf{x}) \mathrel{\vcenter{:}}= (1-\delta_k)T(\mathbf{x})+\delta_k g(\mathbf{x}).\tag{20}\]
Proposition 3 (Viscosity residual bound). Assume the following setting. Let \(T\) be a nonexpansive mapping with \(\operatorname{Fix}(T)\ne\varnothing\), and let \(g\) be a contraction with factor \((1-\rho)\) for some \(\rho\in(0,1]\). Let \((\mathbf{x}_k)_{k\ge0}\) be generated by \(\mathbf{x}_{k+1}=T_k(\mathbf{x}_k)\) with \[\delta_k=\frac{2}{\rho k+2}.\] For any \(\mathbf{x}^*\in\operatorname{Fix}(T)\), define \[R\mathrel{\vcenter{:}}= \max\left\{ \left\| \mathbf{x}_0-\mathbf{x}^* \right\|,\,\frac{\left\| g(\mathbf{x}^*)-\mathbf{x}^* \right\|}{\rho} \right \}.\] Then, for all \(k\ge1\), \[\left\| \mathbf{x}_k-T(\mathbf{x}_k) \right\| \le \frac{8R}{\rho k+2-\rho}.\]
Proof. Since \(\delta_0=1\) and \((\delta_k)\) is non-increasing, \(\delta_k\in(0,1]\) for all \(k\). Hence \(T_k\) is a contraction with factor \(1-\rho\delta_k\): \[\left\| T_k(\mathbf{x})-T_k(\mathbf{y}) \right\| \le (1-\delta_k)\left\| \mathbf{x}-\mathbf{y} \right\| +\delta_k(1-\rho)\left\| \mathbf{x}-\mathbf{y} \right\| =(1-\rho\delta_k)\left\| \mathbf{x}-\mathbf{y} \right\|.\] We first show boundedness. If \(\left\| \mathbf{x}-\mathbf{x}^* \right\|\le R\), then \[\begin{align} \left\| T_k(\mathbf{x})-\mathbf{x}^* \right\| &\le (1-\delta_k)\left\| T(\mathbf{x})-T(\mathbf{x}^*) \right\| +\delta_k\left\| g(\mathbf{x})-\mathbf{x}^* \right\| \\ &\le (1-\delta_k)\left\| \mathbf{x}-\mathbf{x}^* \right\| +\delta_k(1-\rho)\left\| \mathbf{x}-\mathbf{x}^* \right\| +\delta_k\left\| g(\mathbf{x}^*)-\mathbf{x}^* \right\| \\ &\le (1-\rho\delta_k)R+\rho\delta_k R =R. \end{align}\] Thus \(\left\| \mathbf{x}_k-\mathbf{x}^* \right\|\le R\) for all \(k\) by induction.
Define \(E_k\mathrel{\vcenter{:}}=\left\| \mathbf{x}_k-T_{k-1}(\mathbf{x}_k) \right\|\) for \(k\ge1\). The contraction of \(T_k\) gives \[E_{k+1}\le (1-\rho\delta_k)\left\| \mathbf{x}_k-T_k(\mathbf{x}_k) \right\|.\] Moreover, \[\begin{align} \left\| \mathbf{x}_k-T_k(\mathbf{x}_k) \right\| &\le E_k+\left\| T_{k-1}(\mathbf{x}_k)-T_k(\mathbf{x}_k) \right\| \\ &\le E_k+(\delta_{k-1}-\delta_k)\left\| T(\mathbf{x}_k)-g(\mathbf{x}_k) \right\|. \end{align}\] The boundedness estimate implies \[\left\| T(\mathbf{x}_k)-g(\mathbf{x}_k) \right\| \le R+(1-\rho)R+\rho R=2R.\] Therefore \[E_{k+1}\le (1-\rho\delta_k)\left(E_k+2(\delta_{k-1}-\delta_k)R\right).\] Also \(E_1\le2R\). Indeed, since \(\delta_0=1\), we have \(\mathbf{x}_1=T_0(\mathbf{x}_0)=g(\mathbf{x}_0)\); the invariant-ball argument gives \(\mathbf{x}_1\in B(\mathbf{x}^*,R)\), and applying it once more gives \(T_0(\mathbf{x}_1)=g(\mathbf{x}_1)\in B(\mathbf{x}^*,R)\). Therefore \(E_1=\left\| \mathbf{x}_1-T_0(\mathbf{x}_1) \right\|\le2R\). Applying 10 with \[\alpha=\beta=\frac{2}{\rho},\qquad \gamma=\rho,\qquad c=2,\qquad c_1=2,\] gives \[E_k\le \frac{4R}{\rho k+2-\rho}.\] Finally, \[\left\| \mathbf{x}_k-T(\mathbf{x}_k) \right\| \le E_k+\delta_{k-1}\left\| T(\mathbf{x}_k)-g(\mathbf{x}_k) \right\| \le \frac{4R}{\rho k+2-\rho} +\frac{4R}{\rho k+2-\rho},\] which proves the claim. ◻