arxiv: 2604.03658 · v1 · submitted 2026-04-04 · 🧮 math.OC

Recognition: 2 theorem links

· Lean Theorem

A Hybrid Algorithm for Monotone Variational Inequalities

Reza Rahimi Baghbadorani , Peyman Mohajerin Esfahani , Sergio Grammatico

Authors on Pith no claims yet

Pith reviewed 2026-05-13 16:56 UTC · model grok-4.3

classification 🧮 math.OC

keywords variational inequalitiesmonotone operatorsgolden ratio algorithmhybrid algorithmsconvergence accelerationgame theoryoptimization

0 comments

The pith

Switching momentum parameters in the golden ratio algorithm accelerates convergence for monotone variational inequalities.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces hybrid algorithms that switch between small and large momentum parameters to solve monotone variational inequalities more quickly. Building on the adaptive Golden Ratio Algorithm, it shows that using momentum beyond the golden ratio can speed up convergence. This switching strategy is designed to maintain convergence guarantees while improving practical performance. The methods are demonstrated on applications such as Nash equilibrium seeking and zero-sum games, where they compare favorably to standard approaches. This matters for efficient computation in optimization and game theory problems arising in machine learning and control.

Core claim

By selecting the momentum parameter beyond the golden ratio in aGRAAL, convergence speed can be improved, which motivates a hybrid approach of switching between small and large momentum parameters to accelerate convergence while preserving the theoretical properties for monotone operators.

What carries the argument

The adaptive switching rule between small and large momentum parameters within the aGRAAL framework for variational inequalities.

If this is right

The algorithms converge to solutions of monotone variational inequalities without requiring additional problem-specific tuning.
Improved convergence speed is observed in numerical tests on Nash equilibrium seeking, composite minimization, Markov decision processes, and zero-sum games.
The hybrid methods outperform existing algorithms in the tested classes of problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The switching mechanism could potentially be applied to other first-order methods to achieve acceleration.
Exploring the optimal switching thresholds might lead to even faster variants tailored to specific problem classes.
Since no extra conditions are needed, this could simplify implementation in large-scale applications.

Load-bearing premise

The operator defining the variational inequality is monotone and the proposed switching rule preserves convergence.

What would settle it

Running the algorithm on a known monotone variational inequality where it diverges when using the large momentum parameter would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.03658 by Peyman Mohajerin Esfahani, Reza Rahimi Baghbadorani, Sergio Grammatico.

**Figure 2.** Figure 2: Nash-Cournot equilibrium (1). in Algorithm 1 and aGRAAL, and in Algorithm 2, ϕ¯ = 1, α = 1.5, and λ0 = λ¯ = 1. The stepsizes for PrGD and PrRefGD are selected in each problem based on the Lipschitz constant of the underlying operator or the largest values that prevent divergence. Note that projection operators in all examples are evaluated using the solver OSQP solver1 . (1) Nash–Cournot equilibrium proble… view at source ↗

**Figure 5.** Figure 5: Performance in MDP for different values of γ (4). (5) Strongly monotone affine operator [3]. One popular VI problem with a strongly monotone operator is (1) with affine operator F(x) = Mx + q, where M generated randomly as M = AA⊤ + B + D, where each entry of the n × n matrix A and the skew-symmetric matrix B is uniformly sampled from the interval (−5, 5), and every entry of diagonal matrix D is uniformly … view at source ↗

**Figure 3.** Figure 3: Logistic regression (2). 0 1000 2000 3000 4000 5 10-4 10-2 100 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 6.** Figure 6: Strongly monotone operator (5). 0 100 200 300 400 10-10 10-5 100 105 1010 [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗

read the original abstract

Inspired by the adaptive Golden Ratio Algorithm (aGRAAL), we propose two new methods for solving monotone variational inequalities. We show that by selecting the momentum parameter beyond the golden ratio in aGRAAL, the convergence speed can be improved, which motivates us to study the switching between small and large momentum parameters to accelerate convergence. We validate the performance of our proposed algorithms on several classes of variational inequality problems studied in the machine learning and control literature, including Nash equilibrium seeking, composite minimization, Markov decision processes, and zero-sum games, and compare them to that of existing methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The hybrid aGRAAL adds a momentum switch that may help in practice on standard monotone VIs, but the convergence argument for large-momentum steps looks incomplete under plain monotonicity.

read the letter

The paper extends aGRAAL with a hybrid rule that switches between small and large momentum parameters to accelerate convergence on monotone variational inequalities. The motivation comes from noticing that momentum past the golden ratio can sometimes improve speed, leading to the switching strategy as the main new idea. They test the approach on Nash equilibrium seeking, composite minimization, Markov decision processes, and zero-sum games, with comparisons to existing methods in those areas. Those experiments give a reasonable picture of where the method helps in ML and control settings. The practical side is the clearest part of the work. The soft spot is the theory. Standard aGRAAL proofs rely on momentum staying at or below the golden ratio to keep the contraction or Lyapunov decrease intact. Introducing larger-momentum steps and then switching back risks breaking that property for arbitrary monotone operators, and the abstract does not sketch how the gap is closed or what extra conditions might be needed. If the full paper supplies a new potential function or adaptive argument that handles the hybrid case cleanly, the claim holds; otherwise the central guarantee rests on unshown analysis. This is for researchers who implement or tune solvers for monotone VIs in optimization and games. Someone already working with aGRAAL or similar accelerated methods would get the most out of the comparisons and the switching heuristic. I would send it to peer review so the proofs and experimental details can be examined directly.

Referee Report

3 major / 2 minor

Summary. The paper proposes two hybrid algorithms extending the adaptive Golden Ratio Algorithm (aGRAAL) for monotone variational inequalities. It claims that selecting the momentum parameter beyond the golden ratio improves convergence speed, motivating a switching strategy between small and large momentum values to accelerate convergence, and validates the methods empirically on Nash equilibrium seeking, composite minimization, Markov decision processes, and zero-sum games.

Significance. If the convergence of the switching rule can be established under monotonicity, the hybrid approach would provide a practical acceleration technique for variational inequality solvers in machine learning and control, extending aGRAAL without requiring problem-specific tuning.

major comments (3)

[Theoretical analysis (Section 3)] The manuscript asserts convergence of the hybrid switching rule (alternating or selecting between momentum < golden ratio and momentum > golden ratio) under only monotonicity, but provides no proof sketch, Lyapunov analysis, or contraction argument showing that the potential function decreases when a large-momentum step is taken. Standard aGRAAL analysis requires the momentum bound for the contraction to hold; this gap is load-bearing for the central claim.
[Abstract and Section 2] No error bounds, iteration complexity, or rate improvement are derived for the case of momentum beyond the golden ratio, despite the abstract stating that convergence speed can be improved by this choice. The empirical observation on momentum values does not substitute for the required analysis.
[Numerical experiments (Section 4)] The weakest assumption—that the proposed switching rule preserves global convergence for any monotone operator without additional conditions—is not verified; the experiments on standard problem classes do not address whether the rule fails on operators where the potential decrease is violated.

minor comments (2)

[Algorithm description] The description of the switching rule (e.g., exact criterion for choosing small vs. large momentum) is presented without pseudocode or explicit algorithmic statement, making reproduction difficult.
[Section 4] Step-size adaptation and initialization details for the hybrid methods are not fully specified, hindering direct comparison with baselines.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and constructive suggestions. We address each major comment below and will revise the manuscript accordingly to strengthen the theoretical guarantees and clarify the empirical claims.

read point-by-point responses

Referee: [Theoretical analysis (Section 3)] The manuscript asserts convergence of the hybrid switching rule (alternating or selecting between momentum < golden ratio and momentum > golden ratio) under only monotonicity, but provides no proof sketch, Lyapunov analysis, or contraction argument showing that the potential function decreases when a large-momentum step is taken. Standard aGRAAL analysis requires the momentum bound for the contraction to hold; this gap is load-bearing for the central claim.

Authors: We acknowledge this gap in the current manuscript. The Section 3 analysis extends the standard aGRAAL contraction but does not explicitly handle the large-momentum steps in the switching rule. In the revised version we will supply a full convergence proof under monotonicity, including a Lyapunov function argument that bounds the potential decrease across switches by relating the large-momentum update to a controlled perturbation of the standard aGRAAL step. revision: yes
Referee: [Abstract and Section 2] No error bounds, iteration complexity, or rate improvement are derived for the case of momentum beyond the golden ratio, despite the abstract stating that convergence speed can be improved by this choice. The empirical observation on momentum values does not substitute for the required analysis.

Authors: The referee correctly notes that the abstract's claim of improved speed rests on numerical observation rather than derived rates. We will revise the abstract to state that larger momentum yields faster empirical convergence and add to Section 2 a short analysis of the contraction factor under strong monotonicity, showing that the linear rate constant improves for momentum values above the golden ratio while clarifying that no improved rate is claimed for the general monotone case. revision: partial
Referee: [Numerical experiments (Section 4)] The weakest assumption—that the proposed switching rule preserves global convergence for any monotone operator without additional conditions—is not verified; the experiments on standard problem classes do not address whether the rule fails on operators where the potential decrease is violated.

Authors: We agree that the current experiments use standard benchmark problems and do not explicitly probe potential violations of the decrease condition. In the revision we will add a new subsection in Section 4 containing synthetic monotone operators constructed to test the boundary of the potential decrease, together with a discussion of the precise conditions under which global convergence is guaranteed. revision: yes

Circularity Check

0 steps flagged

No circularity: hybrid switching rule derived independently from monotonicity analysis

full rationale

The paper proposes new hybrid methods extending aGRAAL by allowing momentum beyond the golden ratio and introducing a switching strategy between small and large values. The central claims rest on a fresh convergence analysis under the standard monotonicity assumption plus numerical validation across problem classes; no equation reduces by construction to a fitted parameter, no load-bearing step collapses to a self-citation chain, and the switching rule is not defined in terms of the target convergence result itself. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on monotonicity of the operator (standard domain assumption) and the existence of a switching rule that accelerates without breaking convergence guarantees; no new entities are postulated and the momentum parameters are chosen rather than fitted to data.

free parameters (1)

momentum parameter
Selected beyond the golden ratio or switched between small and large values; no specific fitted numerical value is given in the abstract.

axioms (1)

domain assumption The operator defining the variational inequality is monotone.
Invoked as the setting for which the algorithms are designed and for which convergence is claimed.

pith-pipeline@v0.9.0 · 5393 in / 1114 out tokens · 23174 ms · 2026-05-13T16:56:30.649571+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel; phi_fixed_point echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

by selecting the momentum parameter beyond the golden ratio in aGRAAL... switching between small and large momentum parameters... ϕ∈(1,1+√5/2], ρ=1/ϕ+1/ϕ²
IndisputableMonolith/Foundation/BranchSelection.lean branch_selection refines

?

refines
Relation between the paper passage and the cited Recognition theorem.

Theorem 2.1 (Variable momentum in aGRAAL): ... ϕk+1/(ϕk+1-1) ∥x̄k+1-x∥² + ... - (λk/λk-1 ϕk - θk)∥xk+1-xk∥²

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 1 internal anchor

[1]

Linear-quadratic dynamic games as receding-horizon variational inequalities,

E. Benenati and S. Grammatico, “Linear-quadratic dynamic games as receding-horizon variational inequalities,”IEEE Transactions on Automatic Control, 2025, to appear

work page 2025
[2]

Optimal control of a class of variational inequalities of the second kind,

J. C. De los Reyes, “Optimal control of a class of variational inequalities of the second kind,”SIAM Journal on Control and Optimization, vol. 49, no. 4, pp. 1629–1658, 2011

work page 2011
[3]

A Douglas-Rachford Splitting Method for Solving Monotone Variational Inequalities in Linear-quadratic Dynamic Games

R. R. Baghbadorani, E. Benenati, and S. Grammatico, “A douglas- rachford splitting method for solving monotone variational inequal- ities in linear-quadratic dynamic games,”preprint available at arXiv:2504.05757, 2025

work page internal anchor Pith review Pith/arXiv arXiv 2025
[4]

Regularity properties of a semismooth reformulation of variational inequalities,

F. Facchinei, A. Fischer, and C. Kanzow, “Regularity properties of a semismooth reformulation of variational inequalities,”SIAM Journal on Optimization, vol. 8, no. 3, pp. 850–869, 1998

work page 1998
[5]

A new generalization of the schauder fixed point theorem,

F. E. Browder, “A new generalization of the schauder fixed point theorem,”Mathematische Annalen, vol. 174, no. 4, pp. 285–290, 1967

work page 1967
[6]

Problem complexity and method efficiency in optimization,

A. S. Nemirovskij and D. B. Yudin, “Problem complexity and method efficiency in optimization,” 1983

work page 1983
[7]

Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games,

G. Belgioioso and S. Grammatico, “Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games,”IEEE Transactions on Automatic Control, vol. 68, no. 1, pp. 140–155, 2021

work page 2021
[8]

A unified distributed method for constrained networked optimization via saddle-point dynamics,

Y . Huang, Z. Meng, J. Sun, and W. Ren, “A unified distributed method for constrained networked optimization via saddle-point dynamics,” IEEE Transactions on Automatic Control, pp. 1818–1825, 2023

work page 2023
[9]

A game–theoretic approach for generative adversarial networks,

B. Franci and S. Grammatico, “A game–theoretic approach for generative adversarial networks,” in2020 59th IEEE conference on decision and control (CDC). IEEE, 2020, pp. 1646–1651

work page 2020
[10]

Extragradient method for finding saddle points and other problems,

G. Korpelevich, “Extragradient method for finding saddle points and other problems,”Matekon, vol. 13, no. 4, pp. 35–49, 1977

work page 1977
[11]

Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems,

F. Yousefian, A. Nedi´c, and U. V . Shanbhag, “Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems,” in53rd IEEE conference on decision and control. IEEE, 2014

work page 2014
[12]

Collaborative pricing in a power-transportation coupled network: A variational inequality approach,

S. Xie, Q. Wu, N. D. Hatziargyriou, M. Zhang, Y . Zhang, and Y . Xu, “Collaborative pricing in a power-transportation coupled network: A variational inequality approach,”IEEE Transactions on Power Systems, vol. 38, no. 1, pp. 783–795, 2022

work page 2022
[13]

Projected reflected gradient methods for monotone variational inequalities,

Y . Malitsky, “Projected reflected gradient methods for monotone variational inequalities,”SIAM Journal on Optimization, 2015

work page 2015
[14]

On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems,

S. Cui and U. V . Shanbhag, “On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems,” in2016 IEEE 55th conference on decision and control (CDC). IEEE, 2016, pp. 4510–4515

work page 2016
[15]

A variational inequality approach to bayesian regression games,

W. Guo, M. I. Jordan, and T. Lin, “A variational inequality approach to bayesian regression games,” in2021 60th IEEE Conference on Decision and Control (CDC). IEEE, 2021, pp. 795–802

work page 2021
[16]

Distributed projected–reflected–gradient algorithms for stochastic generalized Nash equilibrium problems,

B. Franci and S. Grammatico, “Distributed projected–reflected–gradient algorithms for stochastic generalized Nash equilibrium problems,” in 2021 European Control Conference (ECC). IEEE, 2021, pp. 369–374

work page 2021
[17]

Golden ratio algorithms for variational inequalities,

Y . Malitsky, “Golden ratio algorithms for variational inequalities,” Mathematical Programming, vol. 184, no. 1-2, pp. 383–410, 2020

work page 2020
[18]

Stochastic generalized Nash equilibrium- seeking in merely monotone games,

B. Franci and S. Grammatico, “Stochastic generalized Nash equilibrium- seeking in merely monotone games,”IEEE Transactions on Automatic Control, vol. 67, no. 8, pp. 3905–3919, 2021

work page 2021
[19]

An extremum seeking algorithm for monotone Nash equilibrium problems,

S. Krilaševi´c and S. Grammatico, “An extremum seeking algorithm for monotone Nash equilibrium problems,” in2021 60th IEEE Conference on Decision and Control (CDC). IEEE, 2021, pp. 1232–1237

work page 2021
[20]

Nash equilibrium seeking for a class of quadratic-bilinear Wasserstein distributionally robust games,

G. Pantazis, R. R. Bahbadorani, and S. Grammatico, “Nash equilibrium seeking for a class of quadratic-bilinear Wasserstein distributionally robust games,”preprint available at arXiv:2411.09636, 2024

work page arXiv 2024
[21]

monviso: A python package for solving monotone variational inequalities,

N. Mignoni, R. R. Baghbadorani, R. Carli, P. M. Esfahani, M. Dotoli, and S. Grammatico, “monviso: A python package for solving monotone variational inequalities,” inEuropean Control Conference., 2025

work page 2025
[22]

Liberzon,Switching in systems and control

D. Liberzon,Switching in systems and control. Springer, 2003

work page 2003
[23]

Hybrid dynamical systems,

R. Goebel, R. G. Sanfelice, and A. R. Teel, “Hybrid dynamical systems,” IEEE control systems magazine, vol. 29, no. 2, pp. 28–93, 2009

work page 2009
[24]

A hybrid systems approach for distributed nonsmooth optimization in asynchronous multi-agent sampled-data systems,

J. I. Poveda and A. R. Teel, “A hybrid systems approach for distributed nonsmooth optimization in asynchronous multi-agent sampled-data systems,”IFAC-PapersOnLine, vol. 49, no. 18, pp. 152–157, 2016

work page 2016
[25]

Hybrid extremum seeking for black-box optimization in hybrid plants: An analytical framework,

J. I. Poveda, R. Kutadinata, C. Manzie, D. Neši ´c, A. R. Teel, and C.-K. Liao, “Hybrid extremum seeking for black-box optimization in hybrid plants: An analytical framework,” in2018 IEEE Conference on Decision and Control (CDC). IEEE, 2018, pp. 2235–2240

work page 2018
[26]

Beyond the golden ratio for variational inequality algorithms,

A. Alacaoglu, A. Böhm, and Y . Malitsky, “Beyond the golden ratio for variational inequality algorithms,”Journal of Machine Learning Research, vol. 24, no. 172, pp. 1–33, 2023

work page 2023
[27]

Facchinei and J.-S

F. Facchinei and J.-S. Pang,Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

work page 2003
[28]

Regularized newton method with global convergence,

K. Mishchenko, “Regularized newton method with global convergence,” SIAM Journal on Optimization, vol. 33, no. 3, pp. 1440–1462, 2023

work page 2023
[29]

A fast iterative shrinkage-thresholding algorithm for linear inverse problems,

A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,”SIAM journal on imaging sciences, vol. 2, no. 1, pp. 183–202, 2009

work page 2009
[30]

Equilibrium points of bimatrix games,

C. E. Lemke and J. T. Howson, Jr, “Equilibrium points of bimatrix games,”Journal of the Society for industrial and Applied Mathematics, vol. 12, no. 2, pp. 413–423, 1964

work page 1964
[31]

Generative adversarial nets,

I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y . Bengio, “Generative adversarial nets,” Advances in neural information processing systems, vol. 27, 2014

work page 2014
[32]

From optimization to control: Quasi policy iteration,

M. A. S. Kolarijani and P. M. Esfahani, “From optimization to control: Quasi policy iteration,”preprint available at arXiv:2311.11166, 2023

work page arXiv 2023