An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity

arXiv:2609.15936 · math.OC · Submitted 2026-09-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity".

Emmy: Here's the gist of the paper. An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity solves inclusion problems involving a maximally monotone operator and a monotone Lipschitz continuous operator by proposing a linesearch-free adaptive variant of the forward-reflected-backward splitting, which is significant because it computes the stepsize in closed form from local Lipschitz estimates without requiring knowledge of a global Lipschitz constant <ref:2609.15936#pg15>.

Ada: Problem Formulation and Existing Methods The work addresses the monotone inclusion problem 0 ∈ Tx:= Fx + ∂g(x), where F is monotone and locally Lipschitz-continuous, and ∂g is the subdifferential of a proper convex lsc function g <ref:2609.15936#pg2>.

Emmy: This formulation is equivalent to finding x⋆ ∈ dom g such that g(x) − g(x⋆) + ⟨F(x⋆), x − x⋆⟩ ≥ 0 ∀x ∈ dom g <ref:2609.15936#pg3>.

Ada: Among widely studied methods are Korpelevich’s extragradient method and Tseng’s forward-backward-forward (FBF) method, both of which require two evaluations of F per iteration <ref:2609.15936#pg3>.

Paper summary: Ada: So we're looking at this paper called "An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity." Essentially, they've taken an existing method, the forward-reflected-backward splitting, and made it adaptive.

Emmy: That means they’ve changed how the step size and that reflection coefficient adjust during each iteration based on what's happening right there in the problem. The main claim is that this new approach figures out the step size directly from a local estimate of how much the operator F changes locally, without needing to know a big global Lipschitz constant for F.

Kolya: That part about not needing a global Lipschitz constant is interesting because knowing that number upfront can be really hard in practice when you don't have it. What they claim is that this adaptive variant of the forward-reflected-backward splitting still maintains the iteration cost of the original FRB method while getting these benefits.

Ada: Right, so they propose a linesearch-free way to handle monotone inclusion problems where you have both a monotone operator and a Lipschitz continuous operator. The formulation they use is finding an x star that satisfies g of x minus g of x star plus the inner product with F at some point, for all other points in the set.

Emmy: That setup is essentially what we call an inclusion problem or sometimes a hemivariational inequality when you look at it structurally. It covers things like convex minimization, saddle-point problems, and even Nash equilibrium models in game theory eight <ref:2609.15936#pg1>.

Kolya: And the traditional methods they are comparing this to, like Korpelevich’s extragradient method and Tseng’s forward-backward-forward method, they both require two evaluations of F every time you take a step. That's a cost we want to avoid if possible.

Ada: Exactly. The paper claims their proposed method, called adaFRB alpha, updates the step size in closed form using this local Lipschitz estimate L k, which is the norm of the difference between F evaluated at x k and F evaluated at x k minus one scaled by the distance between those two points.

Emmy: That local estimate L k is defined as the norm of that difference divided by how far apart x k and x minus one are, so it's a measure of how much F is changing near where you are right now. They use this to set the step size update rule in a way that can recover after encountering regions where L k is large.

Paper summary: Kolya: If L k gets big, the step size needs to adjust accordingly to keep things stable and converge efficiently. The paper says this adjustment is guaranteed within at most two such steps, which sounds like a manageable local problem for the algorithm.

Ada: And they define a parameter alpha between one and two that controls how much they adapt the reflection coefficient and step size. This alpha dictates the specific update rule used in Algorithm one so it's a tunable part of their approach <ref:2609.15936#pg1>.

Emmy: The structure of this paper is about how to use these adaptive coefficients to ensure convergence when you're dealing with locally Lipschitz continuous operators F and the subdifferential g of a proper convex function. It connects the structural properties of the problem to how we choose our iteration parameters.

Kolya: So, what does this mean for someone actually running this on a computer? Is it practical?

Ada: Well, they show that by following their rules, specifically ensuring terms Ak plus one, Bk plus one and Ck plus one are all greater than or equal to zero at every step k, the sequence of iterates is guaranteed to be bounded. This boundedness is a necessary first step for convergence analysis.

Emmy: And once they have that bound, they use a new Lyapunov function U alpha k of x star. The claim there is that this function will never increase over time, meaning it stays less than or equal to its initial value, which means the sequence of iterates has to stay within a certain region.

Kolya: Boundedness is good for stability, but what about actually getting close to the solution x star? The paper talks about a gap function called V k of x star. What does that analysis tell us about how fast we approach that solution?

Ada: The analysis shows an explicit nonasymptotic rate for the Stampacchia gap function V k of x star, which means it decreases at a rate related to one over the step size update rule, specifically O one over gamma k <ref:2609.15936#pg1>.

Paper summary: Emmy: That relates the convergence speed directly to how aggressively they are changing their step size parameter gamma k. They also derive a lower bound on these generated step sizes, saying they must be greater than or equal to some minimum value related to alpha and that local Lipschitz constant Lk.

Kolya: So, if I'm driving a car and I'm running this on my system, what are the real constraints? Does this method work well when F is just locally Lipschitz instead of globally Lipschitz?

Ada: The paper specifically focuses on the local Lipschitz continuity setting, which is important because we often don't know the global constant anyway. Their analysis shows that if you follow their conditions for Ak plus one, Bk plus one and Ck plus one being non-negative, then every assertion in theorems about convergence holds.

Emmy: The main point they emphasize is that this method computes the step size in closed form from that local estimate L k without needing to know a global Lipschitz constant beforehand. That's what makes it much more practical for many real-world scenarios where those global constants are just out of reach.

Kolya: So, summarizing the core idea: they've adapted FRB to be adaptive, figuring out the step size from local information about F, and they have a convergence proof based on a Lyapunov function that shows bounded iterates and a gap function shrinking at a predictable rate.

Ada: And finally, what this paper means for us in terms of application? It gives us an algorithm that can handle these complex inclusion problems where we only have local smoothness information about the operator F.

Emmy: It suggests that instead of being stuck with methods that require two evaluations of F per iteration, you can get a step size update based on local changes, which might save computation time in certain settings.

Kolya: I see. So the method is mathematically sound under these specific conditions, and the results are quantified by those convergence rates involving gamma k.

Ada: Exactly. The convergence analysis is quite detailed about how the error term shrinks relative to the step size updates, which gives us a concrete idea of what kind of performance we can expect when we use this adaFRB alpha method for solving these variational inequalities.

Conclusion: Ada: So we're wrapping up this look at "An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity."

Emmy: Yeah, that’s the title, and the authors are Alacaoglu, Böhm, and Malitsky. They're tackling these monotone inclusion problems.

Kolya: It seems like they've taken an existing method called forward-reflected-backward splitting and made it adaptive in a linesearch-free way.

Ada: Exactly. The main idea is that they figure out the step size directly from a local estimate, without needing that big global Lipschitz constant for the operator F.

Emmy: That’s pretty significant because knowing that global constant upfront is usually impossible in real applications. It lets you compute the step size using only what's happening right there in your current data points.

Kolya: So, this method allows us to solve these problems even when we only have local smoothness information about the operator F, not a global one.

Ada: Right. They prove that if you follow their update rules for the step size parameter and the reflection coefficient, the sequence of iterates stays bounded.

Emmy: That boundedness is good because it means we know the algorithm won't just fly off to infinity when solving these kinds of inclusion problems.

Kolya: And they show that this bound leads to a gap function shrinking at a rate tied directly to how aggressively you update your step size parameter, alpha.

Ada: So, the implication is that you can get a solution in these monotone inclusion problems with an explicit convergence rate based on those parameters, without needing any extra line search steps.

Emmy: It moves the focus from searching for a general global constant to designing a rule that handles local variations efficiently.

Kolya: It’s about making the algorithm work reliably under less information, which is what matters when you're actually trying to run this on something like a large dataset.

Hongjia Ou, Andreas Themelis, Puya Latafat

Kyushu University · IMT School for Advanced Studies Lucca

math.OC

Submitted: 2026-09-14

Updated: 2026-11-13

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity solves inclusion problems involving a maximally monotone operator and a monotone Lipschitz…

Key concepts

Monotone Inclusion Problem
This is a mathematical problem seeking a point x that satisfies an inclusion involving two operators: F (which is monotone) and ∂g (the subdifferential of a convex function g). It's equivalent to finding x such that g(x) - g(x⋆) + ⟨F(x⋆), x - x⋆⟩ ≥ 0 for all points x.
Forward-Reflected-Backward Splitting (FRB)
FRB is an iterative algorithm used to solve variational inequalities. It combines forward steps with a reflection step and backward steps. The proposed method adapts the stepsize within this framework using local Lipschitz estimates to improve performance without needing a global constant.
Adaptive Step-size Mechanism
The algorithm dynamically adjusts the stepsize (γk) based on local measures of change in F, specifically the local Lipschitz estimate Lk. This mechanism ensures that the stepsize recovers effectively when encountering regions where F changes rapidly, leading to robust convergence.

Terminology

Summary

An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity solves inclusion problems involving a maximally monotone operator and a monotone Lipschitz continuous operator by proposing a linesearch-free adaptive variant of the forward-reflected-backward splitting, which is significant because it computes the stepsize in closed form from local Lipschitz estimates without requiring knowledge of a global Lipschitz constant <ref:2609. p. 015936#pg15>.

Problem Formulation and Existing Methods

The work addresses the monotone inclusion problem 0 ∈ Tx:= Fx + ∂g(x), where F is monotone and locally Lipschitz-continuous, and ∂g is the subdifferential of a proper convex lsc function g <ref:2609.15936#pg2>. This formulation is equivalent to finding x⋆ ∈ dom g such that g(x) − g(x⋆) + ⟨F(x⋆), x − x⋆⟩ ≥ 0 ∀x ∈ dom g <ref:2609. p. 115936#pg3>. Among widely studied methods are Korpelevich’s extragradient method and Tseng’s forward-backward-forward (FBF) method, both of which require two evaluations of F per iteration <ref:2609. p. 115936#pg3>. The forward-reflected-backward (FRB) method extends Popov’s approach to the composite setting for a fixed γ ∈ (0, 1/2L), defined by xk+1 = proxγgxk − 2γF(xk) + γF(xk−1) <ref:2609. p. 0 p. 115936#pg3>.

Adaptive Step-size Mechanism

The proposed adaptive algorithm adaFRBα sets the reflection coefficient α ∈ [1, 2] and updates the stepsize by computing γk+1 = min n γk q 1/α + ρk, 2/3 + 2α/5 γk, c Lk o <ref:2609.15936#pg7>. The local Lipschitz estimate Lk is defined as∥F(xk)−F(xk−1)∥∥xk−xk−1∥, and the rule allows the stepsize to recover after encountering regions with large Lk, guaranteed within at most two such steps <ref:2609. p. 215936#pg8>. A sharper scheme, adaFRB+α, refines this by evaluating inner products exactly and folding a tighter Young-type equality into the stepsize itself <ref:2609. p. 215936#pg9>.

Convergence Analysis via Lyapunov Function

The convergence analysis relies on a new Lyapunov function Uαk(x⋆) that combines the distance to a solution, successive differences of iterates, and a gap-type term <ref:2609.15936#pg7>. The proof establishes that 0 ≤ Uαk+1(x⋆) ≤ Uαk(x⋆) holds for any solution x⋆ of (1. p. 41), which implies the sequence (xk)k∈ is bounded <ref:2609. p. 715936#pg8>. Furthermore, the analysis derives an explicit nonasymptotic rate for the Stampacchia gap function Vk(x⋆), showing that mink≤K Vk(x⋆) decreasing at a rate O 1/Pk=1 γk <ref:2609. p. 315936#pg9>.

Convergence Guarantees

Theorem 3.4 states that if the stepsize updates satisfy the conditions Ak+1, Bk+1, Ck+1 ≥ 0, then for any solution x⋆ to (1. p. 01), all assertions of Theorems 2. p. 74(i), 2.4(ii) and 2.4(iii) hold <ref:2609. p. 715936#pg9>. Specifically, the sequence (xk)k∈ converges to a solution x∞ with Uαk(x∞) → 0 <ref:2609. p. 615936#pg9>. The analysis also yields an explicit lower bound on the generated stepsizes, γk ≥ min n γ0, √ c/αLF,V o <ref:2609. p. 015936#pg9>.

Experimental Validation

Simulations on minimax problems and Cournot–Nash equilibrium problems confirm the performance of the proposed methods <ref:2609.15936#pg8>. The stepsize plots exhibit intended adaptive behavior, showing that for a given α, the two schemes operate at essentially the same stepsize level, with smaller values of α sustaining visibly larger stepsizes <ref:2609. p. 215936#pg9>. The methods are compared against classical schemes like FRB and EG <ref:2609.15936#pg8>.

Appendix Details

Lemma A.2 provides a lower bound on the generated stepsize sequence, showing that γk ≥ √1/α min n γ0, smin ∀k ∈ <ref:2609. p. 615936#pg9>. Lemma A.4 establishes a relationship between the gap function and the iterates, leading to a convex combination of G(x, xj) bounded by Uα2(x) <ref:2609. p. 015936#pg9>. The proof of Example 2. p. 11 shows that for α > 1/2 the iteration diverges for every γ > 0 if α ≤ 1/2 and the admissible stepsize shrinks like 1/α, consistent with c(α) ∼ 1/α <ref:2609. p. 415936#pg9>. The analysis also shows that the parameter c¯ is the largest safety coefficient that the cap β allows, and for adaFRB+α it can afford a more volatile upper bound on the ratio γk+1 ≤ βkγk <ref:2609. p. 715936#pg9>. The convergence proof relies on verifying that Ak+1, Bk+1, Ck+1 ≥ 0 for every k <ref:2609. p. 115936#pg9>. The final result shows that lim infk→∞ Vk(x⋆) = 0 and xk converges to a solution x∞ <ref:2609. p. 415936#pg9>. The paper concludes by showing that the entire sequence (xk)k∈ converges to x∞ <ref:2609. p. 615936#pg9>.

References

[1] Ahmet Alacaoglu, Axel Böhm, and Yura Malitsky. Beyond the golden ratio for variational inequality algorithms <ref:2609. p. 515936#pg9>.

[2] Jean-François Aujol, Jérémie Bigot, and Camille Castera. Stochastic adaptive gradient descent without descent <ref:2609. p. 215936#pg9>.

[3] Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, and Sergio Grammatico. A hybrid algorithm for monotone variational inequalities <ref:2609. p. 015936#pg9>.

[4] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces <ref:2609. p. 015936#pg9>.

[5] Radu Ioan Boţ, Ernö Robert Csetnek, and Dang-Khoa Nguyen. Fast optimistic gradient descent ascent (ogda) method in continuous and discrete time <ref:2609. p. 115936#pg9>.

[6] Volkan Cevher and Băng Công V˜u. A reflected forward-backward splitting method for monotone inclusions involving lipschitzian operators <ref:2609. p. 015936#pg9>.

[7] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines <ref:2609. p. 015936#pg9>.

[8] Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems <ref:2609. p. 115936#pg9>.

[9] Junhyung Lyle Jang, Tao Sun, Wotao Yin, and Ernest K. Ryu. ALiA: Adaptive linearized ADMM <ref:2609. p. 015936#pg9>.

[10] G. M. Korpelevich. p. 1 The extragradient method for finding saddle points and other problems <ref:2609. p. 115936#pg9>.

[11] Puya Latafat, Andreas Themelis, and Panagiotis Patrinos. p. 0 On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms <ref:2609. p. 215936#pg9>.

[12] Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. p. 0 Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient <ref:2609. p. 015936#pg9>.

[13] Xinmeng Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization <ref:2609. p. 015936#pg9>.

[14] Yura Malitsky. p. 2 Golden ratio algorithms for variational inequalities <ref:2609. p. 315936#pg9>.

[15] Yura Malitsky and Konstantin Mishchenko. p. 2 Adaptive gradient descent without descent <ref:2609. p. 215936#pg9>.

[16] Yura Malitsky and Konstantin Mishchenko. p. 2 Adaptive proximal gradient method for convex optimization <ref:2609. p. 415936#pg9>.

[17] Yura Malitsky and Matthew K. p. 2 Tam. A forward-backward splitting method for monotone inclusions without cocoercivity <ref:2609. p. 015936#pg9>.

[18] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems <ref:2609. p. 315936#pg9>.

[19] Konstantinos Oikonomidis, Emanuel Laude, Puya Latafat, Andreas Themelis, and Panagiotis Patrinos. p. 0 Adaptive proximal gradient methods are universal without approximation <ref:2609. p. 415936#pg9>.

[20] Hongjia Ou, Puya Latafat, and Andreas Themelis. p. 0 Linesearch-free adaptive Bregman proximal gradient for convex minimization without relative smoothness <ref:2609. p. 215936#pg9>.

[21] L. D. Popov. A modification of the Arrow–Hurwicz method for search of saddle points <ref:2609.15936#pg9>.

[22] Santanu Soe, V. Vetrivel, and Jen-Chih Yao. On generalized forward-reflected-backward method for monotone inclusion problems <ref:2609. p. 015936#pg9>.

[23] Quoc Tran-Dinh and Nghia Nguyen-Trung. Revisiting extragradient-type methods: Part 1—Generalizations and sublinear convergence rates <ref:2609.15936#pg9>.

[24] Paul Tseng. p. 1 A modified forward-backward splitting method for maximal monotone mappings <ref:2609. p. 015936#pg9>.

[25] Manu Upadhyaya, Puya Latafat, and Pontus Giselsson. p. 0 A Lyapunov analysis of Korpelevich’s extragradient method with fast and flexible extensions <ref:2609. p. 115936#pg9>.

[26] Ziyuan Wang, Andreas Themelis, Hongjia Ou, and Xianfu Wang. p. 0 A mirror inertial forward–reflected–backward splitting: Convergence analysis beyond convexity and Lipschitz smoothness <ref:2609. p. 315936#pg9>.

[27] Ryoki Yagishita and Masaru Ito. Simple linesearch-free first-order methods for nonconvex optimization <ref:2609. p. 015936#pg9>.

[28] TaeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k2) rate on squared gradient norm <ref:2609.15936#pg9>.

--- Page 27 ---

Lemma A.1 (FNE-like lemma). p. 4 Consider xk, xk+1 generated via (1. p. 44b) for some xk−1, uk, uk+1 ∈ n <ref:2609. p. 015936#pg9>.

Lemma A.2. Suppose that a sequence (γk)k∈ satisfies γk+1 ≥ min n γk q 1/α + ρk, sk for some α ∈ [1, 2], where ρ0 ≥ 1 and ρk+1 = γk+1/γk for k ≥ 0 <ref:2609. p. 515936#pg9>.

Lemma A.3. In the setting of Lemma A. p. 02, suppose that (γk)k∈ satisfies the stronger inequality γk+1 ≥ min n γk q 1/α + ρk, sk for some α ∈ [1, 2], where sk ≥ smin for all k <ref:2609. p. 315936#pg9>.

--- Page 28 ---

Lemma A.4. For every k ∈ and every x ∈ dom g, γkVk(x) ≤ 1/2∥xk−1 − x∥2 − 1/2∥xk − x∥2 − 1/2∥xk−1 − xk‖2 + γk⟨uK−F(xk), x - xK⟩ <ref:2609. p. 915936#pg9>.

--- Page 29 ---

Lemma A.4. For every k ∈ and every x ∈ dom g, γkVk(x) ≤ 1/2∥xk−1 − x∥2 − 1/2∥xk − x‖2 - 1/2∥xk−1 − xk‖2 + γk⟨uK-F(xk), x - xK⟩ <ref:2609. p. 915936#pg9>.

--- Page 30 ---

Lemma A.4. For every k ∈ and every x ∈ dom g, γkVk(x) ≤ 1/2∥xk−1 − x∥2 − 1/2∥xk - x‖2 - 1/2∥xk−1 − xk‖2 + γk⟨uK-F(xk), x - xK⟩ <ref:2609. p. 9 p. 9 p. 915936#pg9>.

--- Page 31 ---

Lemma A.4. For every k ∈ and every x ∈ dom g, γkVk(x) ≤ 1/2∥xk−1 − x∥2 − 1/2∥xk - x‖2 - 1/2∥xk−1 − xk‖2 + γk⟨uK-F(xk), x - xK⟩ <ref:2609.15936#pg9>.

--- Page 32 ---

Lemma A.4. For every k ∈ and every x ∈ dom g, γkVk(x) ≤ 1/2∥xk−1 − x∥2 − 1/2∥xk - x‖2 - 1/2∥xk−1 − xk‖2 + γk⟨uK-F(xk), x - xK⟩ <ref:2609.15936#pg9>.

--- Page 33 ---

Theorem 3.4 (convergence recipe). p. 1 Consider the iterates generated by (1. p. 64) with ϑk+1 = αγk+1/γk for some α ∈ [1, 2] <ref:2609. p. 715936#pg9>.

Convergence analysis

The proof of Theorem 3. p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 14 shows that the first term in the minimum at Step 1. p. 21 enforces ρk+1 ≤ q 1/α + ρk, which is precisely Ak+1 ≥ 0 <ref:2609. p. 015936#pg9>. The second term enforces ρk+1 ≤ β:= min 2/3 + 2α/5, and the third one enforces γk+1Lk ≤ c <ref:2609. p. 515936#pg9>.

Pruning redundant reasoning tokens

The proof of Theorem 3.4 shows that Ak+1, Bk+1, Ck+1 ≥ 0 for every k <ref:2609. p. 4 p. 415936#pg9>. This implies that (x k)k∈ is bounded <ref:2609. p. 0 p. 015936#pg9>. The proof of Theorem 3.4 shows that lim infk→∞ Vk(x⋆) = 0 and any cluster point of the (bounded) ergodic sequence x¯K:= Pk=2 αγk(1/α + ρk − ρ2k+1) xk−1 + (1 + αrK+1)γK+1 xK <ref:2609. p. 715936#pg9>. The proof of Theorem 3.4 shows that Gapx⋆,δ(¯x K) ≤ sup Uα2(x) x ∈ dom g ∩ B(x⋆; δ) Pk=1 γk+1 <ref:2609. p. 5 p. 515936#pg9>. The proof of Theorem 3.4 shows that infk∈ γk > 0, so that PK+1 k=1 γk grows linearly in K <ref:2609. p. 7 p. 715936#pg9>.

Where the gains come from

The convergence analysis is based on the identification of a Lyapunov function for the iterates generated by the proposed algorithms <ref:2609.15936#pg9>. The proof of Theorem 3.4 shows that Uαk+1(x) ≤ Uαk(x) − αγkAk+1Vk−1(x) − (αρkγk)2Bk+1∥∆k−1 F∥2 - Ck+1∥∆kx⟩ <ref:2609. p. 915936#pg9>. The proof of Theorem 3.4 shows that Ak+1, Bk+1, Ck+1 ≥ 0 for every k <ref:2609.15936#pg9>. This implies that (x k)k∈ is bounded <ref:2609.15936#pg9>. The proof of Theorem 3.4 shows that lim infk→∞ Vk(x⋆) = 0 and any cluster point of the (bounded) ergodic sequence x¯K:= Pk=2 αγk(1/α + ρk − ρ2k+1) xk−1 + (1 + αrK+1)γK+1 xK solves (1. p. 71) <ref:2609.15936#pg9>. The proof of Theorem 3.4 shows that Gapx⋆,δ(¯x K) ≤ sup Uα2(x) x ∈ dom g ∩ B(x⋆; δ) Pk=1 γk+1 <ref:2609.15936#pg9>. The proof of Theorem 3.4 shows that infk∈ γk > 0, so that PK+1 k=1 γk grows linearly in K <ref:2609.15936#pg9>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Adaptive Step Size Selection for Local Geometry: The system can compute an adaptive stepsize in closed form from a simple local Lipschitz estimate without needing a global Lipschitz constant, which maintains the iteration cost of Forward-Reflected-Backward splitting while allowing for faster convergence in regions with varying curvature.

  2. Convergence Guarantees under Local Lipschitz Continuity: The system can guarantee convergence to a solution of the monotone inclusion problem when the operator F is only locally Lipschitz continuous by using a new Lyapunov function that combines distance to a solution, successive differences of iterates, and a gap-type term.

  3. Step Size Bounds and Rates: The system can derive explicit lower bounds on generated stepsizes and achieve nonasymptotic rates such as O(1/K) for the minimum Stampacchia gap function by showing that the average stepsize satisfies the sharper bound 1/K Pk=1 gammak >= min c/L.

  4. Robustness to Operator Structure: The system can handle composite structures involving a maximally monotone operator and a monotone Lipschitz continuous operator by solving inclusion problems, specifically through the forward-reflected-backward splitting method.

  5. Performance in Complex Problems: The system can be tested and demonstrated effective on various challenging problems including minimax quadratic problems, bilinear zero-sum games with simplex constraints, linear Cournot–Nash equilibrium models, nonlinear Cournot–Nash models, and sparse logistic regression with l1 regularization.

Sources

Related papers