Pith. sign in

REVIEW 2 major objections 4 minor 65 references

Halpern Iteration Achieves $\tilde{\mathcal{O}}(\epsilon^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Using a large-step, inexact Halpern iteration with an anchored tensor inner solver, this paper achieves $\tilde{O}(\epsilon^{-1/p})$ p-th order oracle complexity for smooth monotone variational inequalities, improving all prior rates for…

desk verdict Halpern-NPE's p=2 rate is a genuine advance; the p≥2 generalization hangs on a misstated local contraction lemma that needs fixing before the main theorem is credible. read the letter →

arxiv 2608.08463 v1 pith:OB4VK2KZ submitted 2026-08-09 math.OC cs.AI

Lesi Chen , Xinliang Zhang , Hengyu Wang , Chengchang Liu , Yongchao Chen , Jingzhao Zhang This is my paper · ORCID
classification math.OCcs.AI MSC 90C3365K1590C47
keywords monotonevariationalinequalityHalperniterationhigher-orderoraclecomplexityanchoredtensormethodproximalresidualminimaxoptimizationstronglyoperatorNewtonextragradient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that smooth monotone variational inequalities can be solved with p-th order oracle complexity $\tilde{O}(D (L_p/\epsilon)^{1/p})$ for every integer $p\ge 2$, where $D$ is the distance from the initial point to a solution. The construction is a double-loop method: an outer inexact Halpern iteration anchored at the starting point, run with a stepsize $\eta$ that grows with the horizon $T$, and an inner solver for the proximal subproblem. For $p=2$ the inner solver is a restarted Newton proximal extragradient (NPE); for general $p$ the paper introduces an Anchored Tensor Method (ATM) that forces every tensor step into a local superlinear region by a decreasing anchored regularization. The resulting rate $\tilde{O}(T^{-p})$ on the proximal residual improves the classical $O(T^{-(p+1)/2})$ MVI rate and the recent $O(T^{-(3p+1)/4})$ minimax rate, and it matches the extragradient exponent at $p=1$. If the proof's local-contraction lemma holds as quoted, the $p=2$ complexity sits within an $\epsilon^{-1/10}$ factor of the known lower bound.

What carries the argument

The machinery is the large-step inexact Halpern iteration coupled with an anchored tensor sub-solver. The Halpern update $x_{t+1}=\frac{1}{t+2}x_0+\frac{t+1}{t+2}y_t$, where $y_t$ approximates the resolvent $P_{\eta F+N_X}(x_t)$, is guaranteed by Lemma 4.1 to give $\operatorname{res}(x_T)\le 4D/(\eta(T+1))$ once each inner solve meets the accuracy $\delta_t=O(R_t/(\sqrt{t}\log t))$. Taking $\eta=\Theta(T^{p-1}/L_p)$ converts this into $\tilde{O}(T^{-p})$. To keep the inner solves cheap, the Anchored Tensor Method (ATM) operates in two phases: it runs tensor steps on the anchored operator $G_k(y)=G(y)+(\mu_k-\mu)(y-y_0)$ with coefficients $\mu_k$ scheduled by equation (19) so that every step stays inside the local contraction region $\rho(\mu)$ of Lemma 5.1, then finishes with pure tensor steps that contract superlinearly; the phase-one count is $K=O(R(L_p/\mu)^{1/(p-1)})$, which is exactly what the outer large-step Halpern analysis needs.

What would settle it

Use the specific constant $C_p:=2p(5p-2)/p!$ from Lemma 5.1 on a one-dimensional $L_p$-smooth, $\mu$-strongly monotone operator like $G(y)=\mu y + c|y|^{p-1}\operatorname{sign}(y)$; test points $y$ with $\|y-y^*\|\le \rho(\mu)$ and check whether the next tensor step obeys $\|y^+-y^*\|\le \theta_p\rho(\mu)$ with $\theta_p=2^{-(p-1)/2}$. A single violation would falsify the lemma in the exact form the proof uses and break the inner-solver bound.

Watch

Extended reading notes

Core claim

The central discovery is that Halpern acceleration is not merely a device for converting convergence in the gap function into convergence in the residual; in the high-order regime it genuinely accelerates the rate. The paper proves that, under Assumptions 2.1--2.4, for every integer $p\ge 2$ there is an algorithm with p-th order oracle complexity $\tilde{O}(D (L_p/\epsilon)^{1/p})$. The proof runs an inexact Halpern iteration on the resolvent operator $P_\eta$ with anchor $x_0$ and coefficient $\beta_t=1/(t+2)$, chooses the step $\eta=\Theta(T^{p-1}/L_p)$, and solves each proximal subproblem with the new Anchored Tensor Method. The inner problem at time $t$ is $\eta^{-1}$-strongly monotone, and the required accuracy is only $\delta_t \approx R_t/(\sqrt{t}\log t)$ with $R_t=O(D/t)$, so each inner solve costs $\tilde{O}(1)$ amortized. The result is $\operatorname{res}(x_T)=O(L_p D^p/T^p)$, i.e., $\tilde{O}(T^{-p})$ convergence in the proximal residual, which improves every prior MVI and minimax bound for $p\ge 2$.

Load-bearing premise

The rate for $p\ge2$ rests on one quoted estimate, Lemma 5.1, that a single tensor step contracts once the point is in a local region; since the lemma as printed has an undefined parameter and an exponent that does not clearly produce the contraction region used later, the entire $\tilde{O}(\epsilon^{-1/p})$ claim would collapse to the old rate if that estimate does not hold exactly as invoked.

Editorial extensions

If this is right

  • For $p=2$, the paper's Halpern-NPE method achieves second-order oracle complexity $\tilde{O}(\epsilon^{-1/2})$, improving the classical $O(\epsilon^{-2/3})$ NPE rate and the minimax-specific $O(\epsilon^{-4/7})$ rate.
  • For every $p\ge 2$, the p-th order oracle complexity becomes $\tilde{O}(\epsilon^{-1/p})$, beating all previous upper bounds for MVIs and for convex-concave minimax problems.
  • Because convex-concave minimax problems are instances of MVIs, the same $\tilde{O}(\epsilon^{-1/p})$ guarantee applies to them, superseding the prior $\tilde{O}(\epsilon^{-4/(3p+1)})$ minimax rate.
  • The method outputs a point with proximal residual at most $\epsilon$, which by Proposition 2.2 yields a strong (Stampacchia) solution and, on compact sets, a weak (Minty) solution; the same guarantee transfers to the restricted gap function up to a diameter factor.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A modular reading of the proof suggests that any inner solver meeting the complexity $O(R(L_p/\mu)^{1/(p-1)})$ would plug into the outer Halpern loop and still yield $\tilde{O}(\epsilon^{-1/p})$; the paper does not state this general recipe, but the induction in Theorem 5.2 does not depend on ATM-specific details after the inner-solver bound.
  • The remaining $p=2$ gap ($\epsilon^{-1/10}$) sits in the outer Halpern rate, not the inner solver, so a more aggressive anchoring schedule or a multi-scale Halpern scheme is a natural next target; this is an inference, not a claim of the paper.
  • A low-dimensional numerical test at $p=3$ on a strongly monotone MVI would cleanly separate the predicted $\epsilon^{-1/3}$ rate from the old $\epsilon^{-1/2}$ rate and would also probe the validity of the quoted local-contraction lemma.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a Halpern-iteration framework for monotone variational inequalities (MVIs) that combines an outer inexact Halpern iteration on the resolvent with a high-order inner solver. For p = 2, the inner solver is a restarted NPE, and the authors prove a convergence rate res(x_T) = O(L_2 D^2 / T^2) with total oracle complexity O(T log log T), equivalently O(D(L_2/epsilon)^{1/2}). For general p ≥ 2, the paper introduces an Anchored Tensor Method (ATM) claimed to solve strongly monotone subproblems in O((L_p/mu)^{1/(p-1)}) iterations, and plugging it into the same Halpern framework yields res(x_T) = O(L_p D^p / T^p) with total complexity O(D(L_p/epsilon)^{1/p}). The advertised rates improve on the classical O(epsilon^{-2/(p+1)}) for MVIs and the recent O(epsilon^{-4/(3p+1)}) for minimax problems.

Significance. The p = 2 result appears correct and is a meaningful improvement over the long-standing NPE rate O(epsilon^{-2/3}); the proof is short and self-contained given the cited lemmas. The high-level mechanism of using the Halpern anchor to allow a large resolvent stepsize is elegant and clearly explained. The p ≥ 2 generalization, if correct, would be a substantial advance with broad implications for higher-order MVI and minimax optimization. However, the p ≥ 2 claim rests on a local contraction lemma (Lemma 5.1) that is not stated correctly or proved, so the main theorem is not yet fully substantiated.

major comments (2)
  1. [Section 5.1, Lemma 5.1] The bound in Lemma 5.1 as printed is not a valid mathematical statement because it involves an undefined parameter eta, and the proof is omitted. The subsequent implication (18), the schedule (19), and the complexity bound K = O(R(L_p/mu)^{1/(p-1)}) in Theorem 5.1 all depend on the exact constant and exponent in this local contraction result. If eta is intended to be 1/mu, then the algebra leading to (18) is consistent; however, the lemma must be restated with the correct dependence on mu and proved or precisely referenced. As written, the p ≥ 2 claim of Theorem 5.2 is not established.
  2. [Section 5.1, Theorem 5.1 proof] The proof of Theorem 5.1 states the induction base as 'r_0 = R by definition', but equation (19) defines r_0 = max(rho(mu), R), so the equality is not true when rho(mu) > R. The induction can be repaired by using r_0 >= R, and the argument still goes through, but the text as written is inaccurate and should be corrected.
minor comments (4)
  1. [Theorem 5.2 and Appendix C] The phrase 'total second-order oracle complexity' appears in Theorem 5.2 and in the sentence following equation (21) where the p-th order complexity is meant; this should be 'total p-th order oracle complexity'.
  2. [Section 5.1, first paragraph] The text says 'we first introduce an Anchored Tensor Method (ATM) that achieves the required convergence rate of O(T^{-p})', but the correct rate for ATM is O(T^{-(p-1)}), as stated in the abstract and in the section title; this appears to be a typo.
  3. [Lemma 5.1] The statement introduces a constant C but the bound uses a different constant C_p; the relationship between C and C_p is not explained, and the undefined eta should be removed or explicitly defined to avoid ambiguity.
  4. [Appendix D] Appendix D presents a different 'triple-looped' algorithm that is not analyzed in the main text; stating explicitly that the final method is Algorithm 3 would improve clarity, since the appendix algorithm is not the one used in the proofs.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the Halpern-ATM rate is a derived induction built on external subproblem solvers, not a restatement of its own inputs.

full rationale

Walking the derivation chain, the claimed rate is assembled from three external ingredients: the inexact Halpern residual bound (Lemma 4.1, cited to Alacaoglu et al.), the second-order subproblem solver guarantee (Lemma 4.2, cited to Huang and Zhang), and the local contraction of the tensor step (Lemma 5.1, cited to Lin and Jordan). None of these assume the paper's target rate. The new material is the large-step parameter choice and the ATM anchoring schedule; those are analyzed by induction in Theorems 4.1 and 5.1, with Lemmas 5.3 and 5.4 proved in the appendices. The only self-citation that enters the proof, Lemma 5.2 from Chen and Luo [17], is a parameter-free stability bound whose assumptions do not include the target result; it is real evidence and does not force the conclusion by construction. The citation of [19] for lower bounds and prior minimax rates is comparative and not used to derive the upper bound. No fitted parameter is renamed as a prediction, no equation is defined in terms of the result it is supposed to prove, and no uniqueness theorem is imported from the authors' own prior work to exclude alternative choices. The printed Lemma 5.1 contains an undefined parameter η and the coefficient should evidently be read as sqrt(C_p L_p / μ); this is an exposition and correctness risk, not a circularity argument.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claim relies on standard smoothness and monotonicity assumptions, plus the quoted local contraction lemma for tensor steps. The algorithmic parameters T and eta are chosen by analysis, not fitted to data. The only hidden input is D, the distance to the solution, which must be known a priori. No new physical or mathematical entities are postulated.

free parameters (2)
  • D (distance to optimal solution) = unknown
    The methods require D to set T and the large stepsize eta; without knowing D, the stated complexity and parameter choices cannot be instantiated.
  • eta (Halpern stepsize) = Theta(T/L2) for p=2, Theta(T^{p-1}/(L_p D^{p-1})) for p>=2
    Chosen analytically to balance the outer Halpern rate O(1/(eta T)) and inner solver cost; not fitted to data.
assumptions (3)
  • domain assumption Assumptions 2.1-2.4 (compact convex X, existence of solution, monotonicity, L_p smoothness)
    Standard for the MVI problem class.
  • domain assumption Lemma 5.1 (local contraction of tensor step) as quoted from Lin and Jordan
    The ATM proof relies on this contraction; the statement as printed has an undefined eta and the exponent is suspect.
  • domain assumption The proximal subproblem can be solved in polynomial time (tensor step oracle)
    The paper assumes the tensor step is efficiently implementable; it cites cutting plane and interior point methods.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Halpern Iteration Achieves $\tilde{\mathcal{O}}(\epsilon^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities." pith.science (2026). https://pith.science/paper/OB4VK2KZ

@misc{pith2026260808463,
  author       = {Pith},
  title        = {Pith review of: Halpern Iteration Achieves $\tilde\mathcalO(\epsilon^-1/p)$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OB4VK2KZ}},
  note         = {Machine review of arXiv:2608.08463}
}
abstract

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at the rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to $\tilde{\mathcal{O}}( T^{-1.75})$ . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of $\tilde{\mathcal{O}}(T^{-2})$ for solving MVIs. We also provide the $p$th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of $\mathcal{O}(T^{-(p-1)})$, and then combine it with the Halpern iteration to achieve a faster convergence rate of $\tilde{\mathcal{O}}(T^{-p})$. This improves all prior results for $p \ge 2$ and matches the classical extragradient method for $p=1$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 33 canonical work pages

  1. [1]

    Optimal methods for higher-order smooth monotone variational inequalities.arXiv preprint arXiv:2205.06167, 2022

    Deeksha Adil, Brian Bullins, Arun Jambulapati, and Sushant Sachdeva. Optimal methods for higher-order smooth monotone variational inequalities.arXiv preprint arXiv:2205.06167, 2022

    arXiv 2022

  2. [2]

    Lower bounds for higher-order convex optimization

    Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. InCOLT, 2018

    work page 2018

  3. [3]

    Ahmet Alacaoglu, Donghwan Kim, and Stephen J. Wright. Revisiting inexact fixed-point iterations for min-max problems: Stochasticity and structured nonconvexity. InICML, 2024

    work page 2024

  4. [4]

    Optimal black-box reductions between optimization objectives

    Zeyuan Allen-Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives. In NeurIPS, 2016

    work page 2016

  5. [5]

    Marques Alves and Benar F

    M. Marques Alves and Benar F. Svaiter. A search-freeO(1/k3/2)homotopy inexact proximal-newton extragradient algorithm for monotone variational inequalities.SIAM Journal on Optimization, 34(4): 3235–3258, 2024

    work page 2024

  6. [6]

    Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    2019

  7. [7]

    Doubly optimal no-regret online learning in strongly monotone games with bandit feedback.Operations Research, 73(6):3219–3244, 2025

    Wenjia Ba, Tianyi Lin, Jiawei Zhang, and Zhengyuan Zhou. Doubly optimal no-regret online learning in strongly monotone games with bandit feedback.Operations Research, 73(6):3219–3244, 2025

    work page 2025

  8. [8]

    Near-optimal method for highly smooth convex optimization

    Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. InCOLT, 2019

    2019

Show all 65 references
  1. [9]

    Brian Bullins and Kevin A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities.SIAM Journal on Optimization, 32(3):2208–2229, 2022

    2022

  2. [10]

    Variance reduced halpern iteration for finite-sum monotone inclusions

    Xufeng Cai, Ahmet Alacaoglu, and Jelena Diakonikolas. Variance reduced halpern iteration for finite-sum monotone inclusions. InICLR, 2024

    2024

  3. [11]

    Accelerated single-call methods for constrained min-max optimization

    Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. InICLR, 2023

    2023

  4. [12]

    Finite-time last-iterate convergence for learning in multi-player games

    Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. InNeurIPS, 2022

    2022

  5. [13]

    Accelerated algorithms for constrained nonconvex- noncancave min-max optimization and comonotone inclusion

    Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for constrained nonconvex- noncancave min-max optimization and comonotone inclusion. InICML, 2024

    2024

  6. [14]

    Distributionally robust optimization via ball oracle acceleration

    Yair Carmon and Danielle Hausler. Distributionally robust optimization via ball oracle acceleration. In NeurIPS, 2022

    2022

  7. [15]

    Optimal and adaptive monteiro-svaiter acceleration

    Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. InNeurIPS, 2022

    2022

  8. [16]

    Cambridge university press, 2006

    Nicolo Cesa-Bianchi and Gábor Lugosi.Prediction, learning, and games. Cambridge university press, 2006

    2006

  9. [17]

    Near-optimal algorithms for making the gradient small in stochastic minimax optimization.JMLR, 25(387):1–44, 2024

    Lesi Chen and Luo Luo. Near-optimal algorithms for making the gradient small in stochastic minimax optimization.JMLR, 25(387):1–44, 2024. 12

    2024

  10. [18]

    Solving convex-concave problems with O(ϵ−4/7)second-order oracle complexity

    Lesi Chen, Chengchang Liu, Luo Luo, and Jingzhao Zhang. Solving convex-concave problems with O(ϵ−4/7)second-order oracle complexity. InCOLT, 2025

    2025

  11. [19]

    Solving convex- concave problems withO(ϵ−4/(3p+1)) pth-order oracle complexity.arXiv preprint arXiv:2604.19462, 2026

    Lesi Chen, Xinliang Zhang, Chengchang Liu, Junru Li, Luo Luo, and Jingzhao Zhang. Solving convex- concave problems withO(ϵ−4/(3p+1)) pth-order oracle complexity.arXiv preprint arXiv:2604.19462, 2026

    2026 arXiv

  12. [20]

    Monotone operator theory in convex optimization: Pl combettes.Mathematical Programming, 170(1):177–206, 2018

    Patrick L Combettes. Monotone operator theory in convex optimization: Pl combettes.Mathematical Programming, 170(1):177–206, 2018

    2018

  13. [21]

    Fast linear algebra is stable.Numerische Mathematik, 108(1):59–91, 2007

    James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable.Numerische Mathematik, 108(1):59–91, 2007

    2007

  14. [22]

    Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities

    Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. InCOLT, 2020

    2020

  15. [23]

    Faster matrix multiplication via asymmetric hashing

    Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In FOCS, 2023

    2023

  16. [24]

    Springer, 2003

    Francisco Facchinei and Jong-Shi Pang.Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

    2003

  17. [25]

    Near-optimal lower bounds for convex optimization for all orders of smoothness

    Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. InNeurIPS, 2021

    2021

  18. [26]

    Optimal tensor methods in smooth convex and uniformly convexoptimization

    Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A Uribe. Optimal tensor methods in smooth convex and uniformly convexoptimization. In COLT, 2019

    2019

  19. [27]

    Springer, 1995

    Franco Giannessi, Antonino Maugeri, et al.Variational inequalities and network equilibrium problems. Springer, 1995

    1995

  20. [28]

    Generative adversarial networks.Communications of the ACM, 63(11): 139–144, 2020

    Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks.Communications of the ACM, 63(11): 139–144, 2020

    2020

  21. [29]

    Fixed points of nonexpanding maps

    Benjamin Halpern. Fixed points of nonexpanding maps. 1967

    1967

  22. [30]

    On some non-linear elliptic differential-functional equations

    Philip Hartman and Guido Stampacchia. On some non-linear elliptic differential-functional equations. 1966

    1966

  23. [31]

    An approximation-based regularized extra-gradient method for monotone variational inequalities.SIAM Journal on Optimization, 35(3):1469–1497, 2025

    Kevin Huang and Shuzhong Zhang. An approximation-based regularized extra-gradient method for monotone variational inequalities.SIAM Journal on Optimization, 35(3):1469–1497, 2025

    2025

  24. [32]

    An optimal high-order tensor method for convex optimization.Mathematics of Operations Research, 46(4):1390–1412, 2021

    Bo Jiang, Haoyue Wang, and Shuzhong Zhang. An optimal high-order tensor method for convex optimization.Mathematics of Operations Research, 46(4):1390–1412, 2021

    2021

  25. [33]

    An improved cutting plane method for convex optimization, convex-concave games, and its applications

    Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. InSIGACT, 2020

    2020

  26. [34]

    Generalized optimistic methods for convex-concave saddle point problems.SIAM Journal on Optimization, 35(3):2066–2097, 2025

    Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems.SIAM Journal on Optimization, 35(3):2066–2097, 2025

    2025

  27. [35]

    Adaptive and optimal second-order optimistic methods for minimax optimization

    Ruichen Jiang, Ali Kavis, Qiujiang Jin, Sujay Sanghavi, and Aryan Mokhtari. Adaptive and optimal second-order optimistic methods for minimax optimization. InNeurIPS, 2024

    2024

  28. [36]

    Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback.Operations Research, 73(3):1675–1702, 2025

    Michael Jordan, Tianyi Lin, and Zhengyuan Zhou. Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback.Operations Research, 73(3):1675–1702, 2025. 13

    2025

  29. [37]

    An introduction to variational inequalities and their applications

    David Kinderlehrer and Guido Stampacchia. An introduction to variational inequalities and their applications. 2000

    2000

  30. [38]

    The extragradient method for finding saddle points and other problems.Matecon, 12:747–756, 1976

    Galina M Korpelevich. The extragradient method for finding saddle points and other problems.Matecon, 12:747–756, 1976

    1976

  31. [39]

    The first optimal acceleration of high-order methods in smooth convex optimization

    Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. InNeurIPS, 2022

    2022

  32. [40]

    Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems

    Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. InNeurIPS, 2021

    2021

  33. [41]

    On the convergence rate of the halpern-iteration.Optimization letters, 15(2):405–418, 2020

    Felix Lieder. On the convergence rate of the halpern-iteration.Optimization letters, 15(2):405–418, 2020

    2020

  34. [42]

    Monotone inclusions, acceleration, and closed-loop control.Mathematics of Operations Research, 48(4):2353–2382, 2023

    Tianyi Lin and Michael I Jordan. Monotone inclusions, acceleration, and closed-loop control.Mathematics of Operations Research, 48(4):2353–2382, 2023

    2023

  35. [43]

    Tianyi Lin and Michael I. Jordan. Perseus: A simple high-order regularization method for variational inequalities.Mathematical Programming, pages 1–42, 2024

    2024

  36. [44]

    Monotone (nonlinear) operators in hilbert space

    George J Minty. Monotone (nonlinear) operators in hilbert space. 1962

    1962

  37. [45]

    A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. InAISTATS, 2020

    2020

  38. [46]

    Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems.SIAM Journal on Optimization, 22(3):914–935, 2012

    Renato DC Monteiro and Benar Fux Svaiter. Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems.SIAM Journal on Optimization, 22(3):914–935, 2012

    2012

  39. [47]

    An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.SIAM Journal on Optimization, 23 (2):1092–1125, 2013

    Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods.SIAM Journal on Optimization, 23 (2):1092–1125, 2013

    2013

  40. [48]

    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

    2004

  41. [49]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  42. [50]

    A method for solving the convex programming problem with convergence rateO(1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with convergence rateO(1/k2). InDokl akad nauk Sssr, volume 269, page 543, 1983

    1983

  43. [51]

    Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2-3):319–344, 2007

    Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems.Mathematical Programming, 109(2-3):319–344, 2007

    2007

  44. [52]

    Accelerating the cubic regularization of newton’s method on convex problems.Mathe- matical Programming, 112(1):159–181, 2008

    Yurii Nesterov. Accelerating the cubic regularization of newton’s method on convex problems.Mathe- matical Programming, 112(1):159–181, 2008

    2008

  45. [53]

    Lectures on convex optimization

    Yurii Nesterov. Lectures on convex optimization. 137, 2018

    2018

  46. [54]

    High-order reduced-gradient methods for composite variational inequalities.arXiv preprint arXiv:2311.15154, 2023

    Yurii Nesterov. High-order reduced-gradient methods for composite variational inequalities.arXiv preprint arXiv:2311.15154, 2023

    2023 arXiv

  47. [55]

    Cubic regularization of newton method and its global performance

    Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006

    2006

  48. [56]

    Numerical optimization

    Jorge Nocedal and Stephen J Wright. Numerical optimization. 1999

    1999

  49. [57]

    Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities

    Petr Ostroukhov, Rinat Kamalov, Pavel Dvurechensky, and Alexander Gasnikov. Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities. arXiv preprint arXiv:2012.15595, 2020. 14

    2012 arXiv

  50. [58]

    Smoothing functions and smoothing newton method for complementarity and variational inequality problems.Journal of Optimization Theory and Applications, 113:121–147, 2002

    Liqun Qi and Defeng Sun. Smoothing functions and smoothing newton method for complementarity and variational inequality problems.Journal of Optimization Theory and Applications, 113:121–147, 2002

    2002

  51. [59]

    Superlinear convergence of an interior-point method despite dependent constraints.Mathematics of Operations Research, 25(2):179–194, 2000

    Daniel Ralph and Stephen J Wright. Superlinear convergence of an interior-point method despite dependent constraints.Mathematics of Operations Research, 25(2):179–194, 2000

    2000

  52. [60]

    Tyrrell Rockafellar

    R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm.SIAM journal on control and optimization, 14(5):877–898, 1976

    1976

  53. [61]

    Ryu and Stephen Boyd

    Ernest K. Ryu and Stephen Boyd. Primer on monotone operator methods.Appl. comput. math, 15(1): 3–43, 2016

    2016

  54. [62]

    Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems.arXiv preprint arXiv:1905.10899, 2019

    Ernest K Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems.arXiv preprint arXiv:1905.10899, 2019

    1905 arXiv

  55. [63]

    Stochastic online auc maximization

    Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. InNeurIPS, 2016

    2016

  56. [64]

    TaeHo Yoon and Ernest K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems withO(1/k 2)rate on squared gradient norm. InICML, 2021

    2021

  57. [65]

    Mitigating unwanted biases with adversarial learning

    Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. InProceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335–340, 2018. 15 A Proof of Lemma 5.3 Proof. The first-order optimality conditions ofy∗ ...

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.