betaFeedback

WorksMathematics

Descending Everest, Part III: Oracle Complexity of Monotone Variational Inequalities with (L0,L1)(L_0,L_1)-Lipschitz Operators

Abstract

We consider monotone variational inequalities in which the Jacobian norm of the operator F:Rd→RdF:\mathbb{R}^d\to\mathbb{R}^d is bounded by an affine function of the norm of the operator itself: ∥DF(z)∥≤L0+L1∥F(z)∥\|DF(z)\|\le L_0+L_1\|F(z)\|. The main case is the problem on the whole space, that is, finding a zero of FF. We assume that a solution exists and that an upper bound RR on the distance from the starting point to the solution is known. Neither strong monotonicity nor cocoercivity is assumed. Global Lipschitz continuity is not assumed either: for L1>0L_1>0, the Jacobian norm may grow together with the norm of the operator. We obtain upper and lower bounds on the number of oracle calls sufficient to find a point z^\hat z with ∥F(z^)∥≤ε\|F(\hat z)\|\le\varepsilon. For L0R/ε≥1L_0R/\varepsilon\ge1, both bounds are, up to logarithmic factors in L1RL_1R, of order 1+L0R/ε+(L1R)6/51+L_0R/\varepsilon+(L_1R)^{6/5}. The upper bound is attained by a deterministic extragradient-type method, and the lower bound holds for arbitrary randomized methods. The same bounds are obtained for the Minty gap on the ball of radius RR, where L0R/εL_0R/\varepsilon is replaced by L0R2/ηL_0R^2/η. In addition, we show that for a variational inequality on a bounded set the numbers L0,L1L_0,L_1 and the diameter of the set are not sufficient: a uniform complexity bound requires additional information, for example, an upper bound on the norm of the operator at the solution.

Use of language models. The models Codex Astra 6 and Claude Opus 5.5 were used in obtaining the theoretical results of this work. They were also used to prepare and typeset the manuscript and to translate the original text into English. Nevertheless, every line of the paper, including every statement, every proof, and every computation, has been personally edited and checked by the authors. The authors bear sole responsibility for the correctness of all mathematical statements, proofs, and conclusions.

Introduction

We consider the problem of finding a point z∈Rdz\in\mathbb{R}^d such that F(z)=0F(z)=0, where F:Rd→RdF:\mathbb{R}^d\to\mathbb{R}^d is a continuous monotone operator, that is, ⟨F(u)−F(v),u−v⟩≥0\langle F(u)-F(v),u-v\rangle\ge0 for all u,v∈Rdu,v\in\mathbb{R}^d. A point z∗∈Zz^*\in Z is called a solution of the variational inequality on a convex set ZZ if $\langle F(z^),z-z^\rangle\ge 0 for all z∈Zz \in Z. For Z=RdZ = \mathbb{R}^d, the substitution z=z∗−tF(z∗)z = z^* - tF(z^*), t>0t > 0, shows that this condition is equivalent to the equality F(z∗)=0F(z^*) = 0. Therefore, finding a zero of the operator is a variational inequality on the whole space. The general theory of finite-dimensional variational inequalities is presented in the monograph Facchinei and Pang [8]. On the whole space, a solution may fail to exist. The constant operator F≡c≠0F \equiv c \ne0 is monotone and satisfies any smoothness conditions, but it has no zeros. On a compact set ZZ, a solution with the same operator exists: it is a minimizer of the linear function ⟨c,z⟩\langle c,z\rangle on ZZ, that is, a solution of a linear programming problem. Therefore, all bounds in this paper concern solvable problems: we assume that a solution exists.

The main source of monotone operators is saddle-point problems. If a function φ(x,y)\varphi(x,y) is convex in xx and concave in yy, then the operator F(x,y)=(∇xφ(x,y),−∇yφ(x,y))F(x,y) = (\nabla_x\varphi(x,y),-\nabla_y\varphi(x,y)) is monotone, and its zeros are the saddle points of φ\varphi. Nash equilibrium conditions in games where the loss function of each player is convex in the player’s own strategy are written in the same way: an equilibrium is a zero of the operator composed of the gradients of the players’ loss functions with respect to their strategies. If this operator is monotone, the game is called monotone. A condition of this type (diagonal strict concavity) was introduced by Rosen [22]. Some problems of training generative adversarial networks also reduce to monotone games ([10]). Another classical source is traffic equilibria: the Wardrop equilibrium in the Beckmann model is written as a variational inequality with the path cost operator, which is monotone when the link cost functions are nondecreasing (Dafermos [5]). Methods for finding equilibria in the Beckmann model and in the Nesterov–de Palma stable dynamics model are considered in Kubentayeva and Gasnikov [15]. The gradient of a convex function is a special case of a monotone operator, but in general FF is not a gradient. For φ(x,y)=xy\varphi(x,y) = xy, we obtain the rotation F(x,y)=(y,−x)F(x,y) = (y,-x), and the step z−hF(z)z - hF(z) moves the point away from the solution for every h>0h > 0: ∥z−hF(z)∥2=(1+h2)∥z∥2\lVert z - hF(z)\rVert^2 = (1+h^2)\lVert z\rVert^2. Therefore, the main method for such problems is the extragradient method (Korpelevich [14]), in which the operator is evaluated at an extrapolation point, and its variant with one operator evaluation per iteration (Popov [21]).

For a monotone operator with Lipschitz constant LL, the complexity is well studied. On a compact set ZZ, the accuracy of an approximate solution z∈Zz \in Z is usually measured by the quantity sup⁡u∈Z⟨F(u),z−u⟩\sup_{u \in Z}\langle F(u),z-u\rangle, which is also called the Minty gap, or the restricted gap function (Stonyakin et al. [25]). For a continuous monotone operator, it is nonnegative and vanishes exactly at the solutions of the variational inequality (Minty [16]). In the Russian-language literature, the inequality sup⁡u∈Z⟨F(u),z−u⟩≤η\sup_{u \in Z}\langle F(u),z-u\rangle\le\eta is used as an accuracy criterion for weak (Minty) variational inequalities (Gasnikov et al. [9]). If the diameter of ZZ equals DD, the method Mirror-Prox finds a point with Minty gap at most η\eta in O(LD2/η)O(LD^2/\eta) iterations (Nemirovski [17]), and for linear operators this order cannot be improved (Nemirovsky [18]). For the unconstrained problem, that is, the variational inequality on the whole space, the natural accuracy criterion is the norm of the operator. The Halpern iteration (Halpern [13]) constructs a new point as a convex combination of the starting point and a step of the method: zk+1=βkz0+(1−βk)T(zk)z_{k+1} = \beta_k z_0 + (1-\beta_k)T(z_k), where TT is a nonexpansive map, for example, the resolvent of the operator FF, and the weights βk\beta_k decrease to zero. The starting point keeps the iterates near itself, as an anchor holds a ship. This is why it is called an anchor, and such methods are called anchored methods. The meaning of the anchor is seen from the regularized problem F(z)+β(z−z0)=0F(z) + \beta(z-z_0) = 0, β>0\beta> 0. By the monotonicity of FF, its solution zβz_\beta satisfies ∥zβ−z0∥≤∥z∗−z0∥\lVert z_\beta-z_0\rVert\le\lVert z^*-z_0\rVert, hence ∥F(zβ)∥=β∥zβ−z0∥≤β∥z∗−z0∥\lVert F(z_\beta)\rVert= \beta\lVert z_\beta-z_0\rVert\le\beta\lVert z^*-z_0\rVert. Anchored methods track zβz_\beta with β\beta of order L/kL/k, and the norm of the operator at the last point decreases as 1/k1/k. The Halpern iteration made it possible to obtain a bound of order LR/εLR/\varepsilon up to a logarithm (Diakonikolas [7]) and the accelerated anchored extragradient method EAG (Extra Anchored Gradient) [31] gives ∥F(zk)∥2=O(L2R2/k2)\lVert F(z_k)\rVert^2 = O(L^2R^2/k^2), that is, O(LR/ε)O(LR/\varepsilon) oracle calls. Here RR is the distance from the starting point to the solution. For monotone operators, the optimal complexity scales linearly with 1/ε1/\varepsilon, whereas for convex minimization it is of order LR2/ε\sqrt{LR^2/\varepsilon}.

All these bounds rely on a global Lipschitz constant LL, which does not exist in many problems. For example, the function exe^x has an unbounded second derivative, but it does not exceed the first one. Such growth, when the local Lipschitz constant is bounded in terms of the norm of the operator itself, is described by the (L0,L1)(L_0,L_1)-smoothness condition. It was proposed for functions [32] to explain the success of methods with gradient clipping: the local smoothness constant can grow together with the gradient norm. In the first two parts of the Descending Everest series of papers, we found the oracle complexity of minimizing a single convex (L0,L1)(L_0,L_1)-smooth function [23] and a sum of such functions [24]. For operators, the analogous condition ∥DF(z)∥≤L0+L1∥F(z)∥\lVert DF(z)\rVert\le L_0+L_1\lVert F(z)\rVert was considered in [28], where convergence of adaptive projection and extragradient methods was proved under the additional pp-quasi-sharpness condition ⟨F(u),u−u∗⟩≥μdist⁡(u,U∗)p\langle F(u),u-u^*\rangle\ge\mu\operatorname{dist}(u,U^*)^p. For a monotone (L0,L1)(L_0,L_1)-Lipschitz operator without additional conditions, [3 {xrefext}]Theorem 3.6) showed that the extragradient method with stepsize inversely proportional to L0+L1∥F(xk)∥L_0+L_1\lVert F(x_k)\rVert finds a point with ∥F∥≤ε\lVert F\rVert\le\varepsilon in O(1+(L0R/ε+L1R)2)O(1+(L_0R/\varepsilon+L_1R)^2) oracle calls. The square arises because without an anchor the norm of the operator decreases as 1/k1/\sqrt{k}, and while the norm is large, the steps have length of order 1/L11/L_1. Subsequent developments include the extragradient method with a moving anchor [1], MAEG with a local stepsize test [26], the method PolyakEG with Polyak-type stepsizes [30], the method PF-AEG, which does not require knowledge of the parameters [4], and an analysis of the extragradient method and Popov’s method in the presence of constraints [12]. For a monotone operator without additional conditions, all these bounds either have the same quadratic order or are not expressed in terms of L0,L1,R,εL_0,L_1,R,\varepsilon alone. In the LongTails repository [27], a Lean-verified bound O(1+L0R/ε+(L1R)4/3)O(1+L_0R/\varepsilon+(L_1R)^{4/3}) was obtained for the same class (theorem RadiusGeneralizedMonotone). We worked on this problem in parallel and independently and obtained a stronger bound with exponent 6/56/5 on L1RL_1R, which is optimal up to logarithmic factors: it is matched by a lower bound for arbitrary randomized methods. A summary table of known bounds is given in Appendix § 11.

The main difficulty in this setting is that the distance to the solution gives only an exponential bound on the norm of the operator at the starting point. Grönwall’s lemma implies only the bound ∥F(z0)∥≤(L0/L1)(eL1R−1)\lVert F(z_0)\rVert\le(L_0/L_1)(e^{L_1R}-1), and it is attained. The length of a safe step is inversely proportional to L0+L1∥F(z)∥L_0+L_1\lVert F(z)\rVert, so the method has to pass through a region where the operator is exponentially large. For convex functions, in the first part of the series, the cost of passing through this region turned out to be L1RL_1R up to logarithms. Thus, continuing our series of papers, we pose a natural question: how many oracle calls does it cost to pass through this region for a monotone operator if only an upper bound RR on the distance to the solution is known? In this paper, we answer it.

Notation. Throughout, ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm of a vector and the spectral norm of a matrix, [x,y][x,y] is the segment with endpoints x,y∈Rdx,y\in\mathbb{R}^d, B(x,r)B(x,r) is the closed ball of radius rr centered at xx, eie_i is the ii-th standard basis vector, 1\mathbf{1} is the all-ones vector, and DFDF is the Jacobian matrix of the operator FF. The sum of the first kk terms of a sequence is denoted by the corresponding capital letter, for example, Λk=λ1+⋯+λk\Lambda_k=\lambda_1+\cdots+\lambda_k and Λ0=0\Lambda_0=0. The logarithm is natural, and log⁡+t=max⁡{0,log⁡t}\log_+ t=\max\{0,\log t\}.

Main result. We show that for L0R/ε≥1L_0R/\varepsilon\ge1 the minimax number of oracle calls T∗T^* required to find a point z^\hat{z} with ∥F(z^)∥≤ε\lVert F(\hat{z})\rVert\le\varepsilon satisfies the inequalities

References

  1. [1]J. K. Alcala, Y. T. Chow, and M. Sunkula. Moving anchor extragradient methods for smooth structured minimax problems. arXiv:2308.12359, 2023. URL https://arxiv.org/abs/2308.12359.
  2. [2]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184:71–120, 2020. URL https://arxiv.org/abs/1710.11606.
  3. [3]Sayantan Choudhury and Nicolas Loizou. Extragradient method for (L₀, L₁)-Lipschitz root-finding problems. In Advances in Neural Information Processing Systems, 2025. arXiv:2510.22421.
  4. [4]Zhaoyang Chu, Hongwei Liu, and Yakui Huang. Parameter-free adaptive extragradient methods for generalized-smooth variational inequalities. arXiv:2610.14839v1, 2026. URL https://arxiv.org/abs/2610.14839.
  5. [5]S. Dafermos. Traffic equilibrium and variational inequalities. Transportation Science, 14(1):42–54, 1980. doi: 10.1287/trsc.14.1.42.DOI
  6. [6]Michał Dereziński, Ethan N. Epperly, and Raphael A. Meyer. The matrix-vector complexity of Ax = b. In Conference on Learning Theory, 2026. arXiv:2602.04842v4.arxiv.org/abs/2602.04842
  7. [7]Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. In Conference on Learning Theory, 2020. arXiv:2002.08872.arxiv.org/abs/2002.08872
  8. [8]Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York, 2003.
  9. [9]A. V. Gasnikov, P. E. Dvurechensky, F. S. Stonyakin, and A. A. Titov. An adaptive proximal method for variational inequalities. Computational Mathematics and Mathematical Physics, 59(5):836–841, 2019.DOI
  10. [10]Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2019. arXiv:1802.10551.arxiv.org/abs/1802.10551
  11. [11]Eduard Gorbunov, Nazarii Tuptitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (L₀, L₁)-smooth optimization: Clipping, acceleration, and adaptivity. In International Conference on Learning Representations, 2025. arXiv:2409.14989.arxiv.org/abs/2409.14989
  12. [12]Ezra Greenberg and Nicolas Loizou. Extragradient and past extragradient methods for (L₀, L₁)-Lipschitz variational inequalities. arXiv:2610.16886v1, 2026. URL https://arxiv.org/abs/2610.16886.
  13. [13]Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6):957–961, 1967.DOI
  14. [14]G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976.
  15. [15]M. Kubentayeva and A. Gasnikov. Finding equilibria in the traffic assignment problem with primal-dual gradient methods for stable dynamics model and Beckmann model. Mathematics, 9(11):1217, 2021.DOI
  16. [16]George J. Minty. Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29(3):341–346, 1962.DOI
  17. [17]Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004.DOI
  18. [18]A. S. Nemirovsky. Information-based complexity of linear operator equations. Journal of Complexity, 8(2):153–175, 1992. doi: 10.1016/0885-064X(92)90013-2.DOI
  19. [19]A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York, 1983.
  20. [20]Yurii Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer, 2018.DOI
  21. [21]L. D. Popov. A modification of the Arrow–Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845–848, 1980.DOI
  22. [22]J. B. Rosen. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica, 33(3):520–534, 1965. doi: 10.2307/1911749.DOI
  23. [23]M. Rudomanov, I. Fomin, A. V. Gasnikov, and F. S. Stonyakin. Descending Everest with first-order oracles: Oracle complexity of convex optimization under (L₀, L₁)-smoothness. arXiv:2610.21461, 2026a. URL https://arxiv.org/abs/2610.21461.
  24. [24]M. Rudomanov, I. Fomin, A. V. Gasnikov, and F. S. Stonyakin. Descending Everest, part II: Oracle complexity of minimizing a sum of convex (L₀, L₁)-smooth functions. arXiv:2611.04171, 2026b. URL https://arxiv.org/abs/2611.04171.
  25. [25]F. Stonyakin, A. Gasnikov, P. Dvurechensky, A. Titov, and M. Alkousa. Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle. Journal of Optimization Theory and Applications, 194(3):988–1013, 2022.
  26. [26]D. Sun, L. Zhang, and W. Zhao. Convergence analysis of the restarted moving-anchored extra-gradient method in the absence of local Lipschitz continuity. arXiv:2607.07585v1, 2026. URL https://arxiv.org/abs/2607.07585.
  27. [27]Alexander Tyurin, QuocViet Pham, Valentin Khrulkov, and Ivan Oseledets. LongTails: Automated research in optimization. GitHub repository, 2026. URL https://github.com/k3nfalT/longtails.arxiv.org/abs/2611.13872
  28. [28]Daniil Vankov, Angelia Nedić, and Lalitha Sankar. Generalized smooth variational inequalities: Methods with adaptive stepsizes. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 49137–49170, 2024. URL https://proceedings.mlr.press/v235/vankov24a.html.
  29. [29]Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems, volume 29, 2016. URL https://arxiv.org/abs/1605.08003.
  30. [30]T. Yoon, S. Choudhury, E. Greenberg, and N. Loizou. Polyak-type extragradient methods for monotone root-finding problems. arXiv:2609.26581v1, 2026. URL https://arxiv.org/abs/2609.26581.
  31. [31]TaeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O(1/k²) rate on squared gradient norm. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, 2021. URL https://proceedings.mlr.press/v139/yoon21d.html.
  32. [32]Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020. arXiv:1905.11881.

Paper details

vlnc:W_uyy684xv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex Astra 6, Claude Opus 5.5

View statement
Looking for related papers…
Contents