A Parameter-Free Adaptive Reflected Gradient Method for Monotone Variational Inequalities
Abstract
We analyze a one-evaluation-per-iteration method for VI(C,B) with monotone L-Lipschitz B: xk+1=PC(xk−λB(uk)), uk=xk+θk(xk−xk−1)+βk(xk−uk−1), θk+βk=1. For constant step and summable filter (∑kβk<∞) we prove weak convergence via a Lyapunov function with exact rational dissipation budgets, including Malitsky's reflected gradient method. It is robust to summable operator errors; if C is bounded, the constant-step range reaches λ<(√2−1)/L. For unbounded C this reduces to an a priori boundedness statement, certified to λL=0.387 by dissipation trading; for affine B on polyhedral C, dist(xn,S)→0 with ∑ndist2(xn,S)<∞, strong convergence for bounded C, and R-linear rates after face identification. The main result is a safeguarded adaptive step-size rule needing no L and no extra evaluations, proved weakly convergent unconditionally: a data-driven Lyapunov weight removes L from the dissipation budgets. For affine B with C=ℋ, sharpness of λL=1/√3 via a rotation lower bound; the same constant is sharp for unconstrained nonlinear B, with convergence for square-summable operator values. Unconditional convergence below 1/(√3 L) reduces to a marginal-pole absolute-stability statement; the projected case remains open. Under strong monotonicity we prove R-linear convergence with explicit contraction, and certify Ω(L) speedups over constant steps. Numerics confirm the gains.
Related
- Averaged proximal reflected gradient method for monotone variational inequalities
- GRAAL for variational inequalities revisited: sharp parameter range and adaptive step sizes
- Parameter-Free Adaptive Extragradient Methods for Generalized-Smooth Variational Inequalities
- Parameter-Free First-Order Method for Constrained Variational Inequalities
- An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity
BibTeX
@misc{shehu2026parameterfree,
title = {{A Parameter-Free Adaptive Reflected Gradient Method for Monotone Variational Inequalities}},
author = {Yekini Shehu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18355},
eprint = {2609.18355},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18355},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Parameter-Free Adaptive Reflected Gradient Method for Monotone Variational Inequalities
AU - Yekini Shehu
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18355
UR - https://arxiv.org/abs/2609.18355
AB - We analyze a one-evaluation-per-iteration method for VI(C,B) with monotone L-Lipschitz B: x_k+1=P_C(x_k−λB(u_k)), u_k=x_k+θ_k(x_k−x_k−1)+β_k(x_k−u_k−1), θ_k+β_k=1. For constant step and summable filter (∑_kβ_k<∞) we prove weak convergence via a Lyapunov function with exact rational dissipation budgets, including Malitsky's reflected gradient method. It is robust to summable operator errors; if C is bounded, the constant-step range reaches λ<(√2−1)/L. For unbounded C this reduces to an a priori boundedness statement, certified to λL=0.387 by dissipation trading; for affine B on polyhedral C, dist(x_n,S)→0 with ∑_ndist^2(x_n,S)<∞, strong convergence for bounded C, and R-linear rates after face identification. The main result is a safeguarded adaptive step-size rule needing no L and no extra evaluations, proved weakly convergent unconditionally: a data-driven Lyapunov weight removes L from the dissipation budgets. For affine B with C=ℋ, sharpness of λL=1/√3 via a rotation lower bound; the same constant is sharp for unconstrained nonlinear B, with convergence for square-summable operator values. Unconditional convergence below 1/(√3 L) reduces to a marginal-pole absolute-stability statement; the projected case remains open. Under strong monotonicity we prove R-linear convergence with explicit contraction, and certify Ω(L) speedups over constant steps. Numerics confirm the gains.
ER -