Pith. sign in

REVIEW 3 major objections 4 minor 67 references

Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Both GRTR and LMNegCur reach an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point in $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ outer iterations, while the inexact variants use only…

desk verdict A genuinely useful complexity improvement, but the proof of the advertised ε^-1.75 HVP bound has a real gap around the Chebyshev-approximated Hessian that needs fixing before the claim stands. read the letter →

arxiv 2411.15769 v2 pith:6HYZZLOM submitted 2024-11-24 math.OC cs.LGstat.ML

Jun-Lin Wang , Zi Xu This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C4790C2690C30
keywords nonconvex-stronglyconcaveminimaxgradientnormregularizationtrust-regionmethodLevenberg-Marquardtnegativecurvaturesecond-orderstationarypointiterationcomplexityHessian-vectorproduct
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

The paper establishes that second-order methods for nonconvex-strongly concave minimax problems can reach a second-order stationary point at the best known outer-iteration count while spending less work per iteration. The GRTR algorithm adds a Hessian regularization and a trust-region radius that both scale with the square root of the gradient norm; the LMNegCur algorithm replaces the trust-region subproblem by a Levenberg-Marquardt linear system, using a negative-curvature step when the approximate Hessian is too negative. Both are proved to find an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point within $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ outer iterations. The inexact variants IGRTR and ILMNegCur preserve this bound and need only $\tilde{O}(\ell^{2.25}\rho^{0.25}\mu^{-1.75}\epsilon^{-1.75})$ Hessian-vector products, improving the $\epsilon$ dependence of earlier inexact cubic-regularization methods. The significance is a concrete algorithm pair that combines the robustness of trust-region and Levenberg-Marquardt steps with a matching complexity guarantee and cheaper per-iteration linear algebra.

What carries the argument

The load-bearing object is the gradient-norm regularized trust-region subproblem (2.3): it uses $\tilde H_t = H_t + \sigma\|g_t\|^{1/2}I$ in the quadratic model and a ball of radius $r\max\{\|g_t\|^{1/2},\epsilon^{1/2}\}$. The dual multiplier $\lambda_t$ in its optimality conditions classifies each iteration into a descent case or a contraction case, which is what converts the function-value gap into an iteration count. For LMNegCur the corresponding mechanism is the negative-curvature test on $\lambda_{\min}(H_t)$: if it is at most $-\frac12\sqrt{L_2}\max\{\|g_t\|,\epsilon\}$, the algorithm steps along a unit curvature direction of length $\sqrt{\max\{\|g_t\|,\epsilon\}/L_2}$; otherwise it solves the LM system with regularization $\sqrt{L_2\|g_t\|}I$. The inner loop of accelerated gradient ascent (length $N_t$ chosen in (2.8)) is what makes the approximate gradient and Hessian accurate enough for Lemma 2.4 and hence for both algorithms.

What would settle it

Run GRTR on a nonconvex-strongly concave instance with known constants, for example the synthetic problem (4.1) with $n=10$, $L=1$, $\gamma=1$, and count outer iterations until $\|\nabla P(x)\le \xi\epsilon$ and $\nabla^2P(x)\succeq -\theta\sqrt{\epsilon}I$; if for some $\epsilon$ the count exceeds a fixed multiple of $\sqrt{L_2}(P(x_0)-P^*)\epsilon^{-3/2}\ln(1/\epsilon)$ with $L_2=\rho(1+\kappa)^3$, Theorem 2.1's bound is violated, and the same counting test on LMNegCur would settle Theorem 3.1.

Watch

Extended reading notes

Core claim

In the paper's own terms, gradient-norm regularization is sufficient to carry a second-order minimax method to an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point at rate $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$. At iteration $t$, accelerated gradient ascent on $y$ supplies an approximate gradient $g_t$ and Hessian $H_t$ that are within $\epsilon_1$ and $\epsilon_2$ of the true ones for $P(x)=\max_y f(x,y)$. GRTR then solves a trust-region subproblem with regularized Hessian $H_t+\sigma\|g_t\|^{1/2}I$ and radius $r\max\{\|g_t\|^{1/2},\epsilon^{1/2}\}$; the optimality conditions show that the iteration either cuts the function value by order $\|g_t\|^{3/2}$ or contracts $\|g_t\|$ by a factor of $1/3$, and the two cases are balanced by the function-value gap $P(x_0)-P^*$. LMNegCur uses the same approximate information but detects negative curvature and takes a step of length $\sqrt{\max\{\|g_t\|,\epsilon\}/L_2}$ along it, otherwise solving the linear system $(H_t+\sqrt{L_2\|g_t\|}I)s=-g_t$. The inexact variants apply trust-region Newton-CG and randomized Lanczos/CG solvers, giving the Hessian-vector product bound stated in Corollaries 2.1 and 3.1.

Load-bearing premise

The proof needs the user to know the strong-concavity coefficient $\mu$, the Lipschitz constants $\ell$ and $\rho$, and the gap $P(x_0)-P^*$ to set the inner-loop lengths and regularization parameters; without those constants the descent and stopping arguments do not apply, and the paper gives no adaptive estimation procedure.

Editorial extensions

If this is right

  • Both GRTR and LMNegCur match the best known outer-iteration complexity $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ for finding an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point.
  • The inexact variants bring the Hessian-vector product count down to $\tilde{O}(\ell^{2.25}\rho^{0.25}\mu^{-1.75}\epsilon^{-1.75})$, improving the $\epsilon$ exponent from $-2$ to $-1.75$ relative to the IMCN and ICLM algorithms.
  • The total number of gradient ascent steps is $\tilde{O}(\ell^2\rho^{0.5}\mu^{-2}\epsilon^{-1.5})$ for all four variants, matching earlier algorithms.
  • GRTR needs no function values of $P(x)=\max_y f(x,y)$ and no bounded-gradient assumption, unlike MINIMAX-TRACE; its trust-region radius adapts to the gradient norm instead of staying fixed.
  • LMNegCur avoids solving a trust-region subproblem altogether: each iteration requires at most one minimum-eigenvalue estimate and one positive-definite linear solve, so the hard case of trust-region subproblems does not arise.

Reading between the lines

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

  • The same descent-versus-contraction dichotomy suggests that gradient-norm regularization could be ported to stochastic or Hessian-free settings, but strong concavity in $y$ is used decisively in Lemma 2.4, so such extensions would need a new inner-loop accuracy argument.
  • The paper does not give an adaptive way to set $\epsilon_1,\epsilon_2,\sigma,r$ when the problem constants are unknown; a natural next step is a parameter-free or self-tuning version of GRTR, and its absence is the main practical gap.
  • The $\epsilon^{-1/4}$ improvement in Hessian-vector products should make IGRTR and ILMNegCur noticeably cheaper than IMCN and ICLM on large-scale problems where matrix-vector products dominate; this is directly testable by benchmarking Hessian-vector product counts rather than wall-clock time on the adversarial deep learning problem in Section 4.3.
  • Because LMNegCur detects negative curvature early via the Lanczos procedure, its saddle-escaping behavior may be less sensitive to trust-region radius and hard-case geometry than GRTR; the numerical experiments point in that direction, though the paper does not isolate this as a separate claim.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proposes two second-order algorithms for nonconvex-strongly concave minimax problems: GRTR, a trust-region method with a gradient-norm-regularized Hessian and radius proportional to the square root of the gradient norm, and LMNegCur, a Levenberg-Marquardt method with negative-curvature correction. It claims that both methods find an O(ε,√ε)-second-order stationary point in Õ(ℓ^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5}) outer iterations, and that the inexact variants IGRTR and ILMNegCur require only Õ(ℓ^{2.25}ρ^{0.25}μ^{-1.75}ε^{-1.75}) Hessian-vector products and Õ(ℓ^2ρ^{0.5}μ^{-2}ε^{-1.5}) gradient ascent steps with high probability. The analysis follows the standard monotone-descent plus gradient-contraction template, with inner-loop accelerated gradient ascent to approximate the maximizer y*(x_t). Numerical experiments on synthetic problems, a sinusoidal perturbation problem, and an adversarial deep learning problem are reported.

Significance. If fully established, the outer-iteration bounds match the best known complexity for this problem class and the Hessian-vector product exponent improves on IMCN and ICLM, which would be a meaningful contribution. The algorithms are clearly specified and the experiments give qualitative evidence of practical efficiency. However, two technical gaps currently block acceptance: a scaling error in a key descent lemma and an unproven step in the inexact Hessian-vector product analysis. The paper also omits the proof of a main theorem. These issues should be addressed before the claims can be relied upon.

major comments (3)
  1. [Section 2.1, Lemma 2.6 and Eq. (2.25)] The stationarity and descent claims are not correct as stated. Substituting λ_t ≤ √L2 ε, σ∥g_t∥^{1/2} ≤ (√L2/2)√ε, and ϵ2 = (√L2/12)√ε into the inequality preceding (2.25) gives a lower bound of order -√L2√ε I, not -√L2 ε I; the displayed constant 19/12 cannot be obtained for small ε. Moreover, the descent P(x_{t+1}) ≤ P(x_t) - (1/(128√L2))ε^{3/2} for λ_t ≥ √L2 ε does not follow by 'replacing ∥g_t∥ with ε': with ∥s_t∥ = r ε^{1/2}, the negative term in (2.16) is -1/2(σ∥g_t∥^{1/2}+λ_t)∥s_t∥^2, which is only O(√L2∥g_t∥^{1/2}ε + √L2 ε^2) and can be much smaller than ε^{3/2} when ∥g_t∥ is small. Since the partition into F and G in (2.27)-(2.28) requires this ε^{3/2} descent, Theorem 2.1 is not justified.
  2. [Section 2.3, Corollary 2.1 and Section 3.3, Corollary 3.1] The Hessian-vector product complexity is not supported. The algorithm descriptions in Section 2.2 state the subproblem termination conditions (2.34)-(2.36) in terms of H_t, but Corollary 2.1 replaces the inverse (∇^2_yy f)^{-1} inside H_t by a Chebyshev approximation, yielding \hat H_t. The paper does not specify whether the CG/Lanczos procedures operate on H_t or \hat H_t, and does not prove that the termination conditions survive the replacement. If \hat H_t is used, the descent bounds (2.40) and (3.25) gain an extra term (1/2)∥H_t-\hat H_t∥∥s_t∥^2, which is not absorbed by the constants in (2.37) and (3.23). If H_t is used exactly, the cost of computing H_t is not counted. In either case the advertised Õ(ε^{-1.75}) exponent is not established.
  3. [Section 3.1, Theorem 3.1] The proof is omitted with the comment that it is 'almost identical' to Theorem 2.1. This is not self-evident, since Lemma 3.1 has a different descent inequality (3.7) and the G set in (3.19) uses contraction factor 1/2 instead of 1/3. The bound on consecutive G-iterations, which in Lemma 2.8 depends on the contraction factor and the uniform bound G, must be verified for the new constants \bar C_1, \bar C_2, \bar G. The theorem should be proved or the missing steps supplied.
minor comments (4)
  1. [Throughout] There are numerous typos and duplicated phrases, e.g., 'satifies' in Assumption 2.1, 'respectivelly' in Section 1.2, and 'for a given xt' twice in the description of Algorithm 2.
  2. [Section 4.3] The baseline algorithm is called 'IMINIMAX-TR' in this section, while earlier it is 'MINIMAX-TR'; please make the notation consistent.
  3. [Sections 2.1, 2.3, 3.1, 3.3] The parameter choices in (2.11), (2.37), (3.5), and (3.23) require knowledge of L1, L2, and P(x0)-P*; the paper should explicitly state that the methods are not parameter-free and discuss the practical implications.
  4. [Eq. (2.41)] The second term should be 2ϵ2 ε^{1/2}∥s_t∥ before using ε ≤ ∥g_t∥; the displayed bound relies on ε < 1 and should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity bounds are derived from stated assumptions and analytic parameter choices, not from fitted or self-referential inputs.

full rationale

The paper's central claims are upper bounds on iteration and Hessian-vector-product complexity for finding O(epsilon, sqrt(epsilon))-second-order stationary points. The parameters sigma, r, epsilon_1, and epsilon_2 are chosen analytically in (2.11), (2.37), (3.5), and (3.23) to balance descent terms against inexactness errors; they are not fitted to reproduce a target exponent. Lemmas 2.4-2.6 and 3.1-3.3 derive descent and gradient-contraction inequalities directly from Assumption 2.1, the optimality conditions of the trust-region subproblem, and the chosen parameter values. Theorems 2.1-3.2 then count iterations by combining a finite function-value decrease with a bounded number of gradient contractions, which is a standard and self-contained argument. The inexact-variant Corollaries 2.1 and 3.1 combine these outer-iteration bounds with external CG/Lanczos and Chebyshev results; whether that composition is fully justified is a technical correctness question, not a circularity, because the claimed HVP count is not equivalent to an input by construction. Self-citations to [62] and [53] are used as comparison baselines or background, not as load-bearing justifications for the present results. No step defines the target stationary point or its complexity in terms of the algorithm's own output, and no fitted quantity is renamed as a prediction. The derivation is therefore self-contained with respect to circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The convergence proofs do not fit constants to data. The listed free parameters are analytic algorithm hyperparameters chosen in the proofs; if the problem constants are unknown, these choices cannot be made, which is a standard oracle limitation rather than a post-hoc fit. No invented physical or mathematical entities appear; the proposed algorithms are methods, not entities.

free parameters (4)
  • GRTR regularization coefficient sigma = sigma = sqrt(L2)/2 (eq. 2.11); other values in (2.37) and (3.5)
    Chosen by hand to balance descent and gradient-contraction terms. The central complexity proof depends on this value.
  • GRTR trust-region radius factor r = r = 1/(4 sqrt(L2)) (eq. 2.11)
    Chosen by hand to keep subproblem steps within the radius where the Taylor expansion is valid. The complexity bound depends on this choice.
  • Inner accuracy thresholds epsilon_1 and epsilon_2 = epsilon_1 = min(1/96, sqrt(L2)/(16 L1)) epsilon^(3/2); epsilon_2 = sqrt(L2)/12 epsilon^(1/2)
    Analytically selected constants that control the error from the inexact gradient and Hessian estimates in Lemma 2.4. They are not fitted to numerical data.
  • Gradient ascent parameters eta_y, theta, N_t = eta_y = 1/ell, theta = (sqrt(kappa)-1)/(sqrt(kappa)+1), N_t per (2.8)
    Chosen to make Nesterov accelerated gradient ascent reach the accuracy required by Lemma 2.4. The proof requires these values to be known.
assumptions (4)
  • domain assumption Assumption 2.1: f has ell-Lipschitz gradients, rho-Lipschitz second derivatives, and P(x) = max_y f(x,y) is bounded below.
    This is the standard smoothness and boundedness setting for nonconvex-strongly concave minimax complexity analysis. It is stated in Assumption 2.1 and used throughout.
  • domain assumption P has L1-smooth gradient and L2-Lipschitz Hessian with L1 = (kappa+1)ell and L2 = rho(1+kappa)^3.
    Derived in Lemmas 2.1 and 2.2 from Assumption 2.1. These constants determine sigma, r, and all complexity bounds.
  • standard math Nesterov accelerated gradient ascent converges with rate (sqrt(kappa)+1) exp(-N/(2 sqrt(kappa))).
    Used in Lemma 2.4 to choose N_t. This is a cited background result from Nesterov's convex optimization book, reference [36].
  • standard math Randomized Lanczos, conjugate gradient, and Chebyshev inverse approximation provide the required approximate eigendirections and Hessian-vector products with high probability.
    Used in Corollaries 2.1 and 3.1 for the inexact variants. The paper cites [8, 24, 32, 47] and does not provide a self-contained derivation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems." pith.science (2026). https://pith.science/paper/6HYZZLOM

@misc{pith2026241115769,
  author       = {Pith},
  title        = {Pith review of: Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6HYZZLOM}},
  note         = {Machine review of arXiv:2411.15769}
}
abstract

In this paper, we study second-order algorithms for solving nonconvex-strongly concave minimax problems, which have attracted much attention in recent years in many fields, especially in machine learning.We propose a gradient norm regularized trust-region (GRTR) algorithm to solve nonconvex-strongly concave minimax problems, where the objective function of the trust-region subproblem in each iteration uses a regularized version of the Hessian matrix, and the regularization coefficient and the radius of the ball constraint are proportional to the square root of the gradient norm. The iteration complexity of the proposed GRTR algorithm to obtain an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point is proved to be upper bounded by $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$, where $\mu$ is the strong concave coefficient, $\ell$ and $\rho$ are the Lipschitz constant of the gradient and Jacobian matrix respectively, which matches the best known iteration complexity of second-order methods for solving nonconvex-strongly concave minimax problems. We further propose a Levenberg-Marquardt algorithm with a gradient norm regularization coefficient and use the negative curvature direction to correct the iteration direction (LMNegCur), which does not need to solve the trust-region subproblem at each iteration. We also prove that the LMNegCur algorithm achieves an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point within $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ number of iterations.The inexact variants of both algorithms can still obtain $O(\epsilon,\sqrt{\epsilon})$-second-order stationary points with high probability, but only require $\tilde{O}(\ell^{2.25}\rho^{0.25}\mu^{-1.75}\epsilon^{-1.75})$ Hessian-vector products and $\tilde{O}(\ell^{2}\rho^{0.5}\mu^{-2}\epsilon^{-1.5})$ gradient ascent steps.

Figures

Figures reproduced from arXiv: 2411.15769 by the authors.

Figure 1
Figure 1. Numerical results of the tested algorithms for solving (4.1) with different [PITH_FULL_IMAGE:figures/full_fig_p027_1.png] view at source ↗
Figure 2
Figure 2. Numerical results of the nine tested algorithms for solving (4.2) with dif [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗
Figure 3
Figure 3. Numerical results of the five tested algorithms for solving (4.3). [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 57 canonical work pages

  1. [1]

    D. Adil, B. Bullins, A. Jambulapati, and S. Sachdeva. Line search-free methods for higher- order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167, 2022

    arXiv 2022

  2. [2]

    Arjovsky, S

    M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. International Conference on Machine Learning, PMLR, pages 214–223, 2017

    work page 2017

  3. [3]

    Ben-Tal, L

    A. Ben-Tal, L. EL Ghaoui, and A. Nemirovski. Robust Optimization, volume 28. Princeton University Press, 2009

    work page 2009

  4. [4]

    Beznosikov, A

    A. Beznosikov, A. Sadiev, and A. Gasnikov. Gradient-free methods with inexact oracle for convex-concave stochastic saddle-point problem. International Conference on Mathemati- cal Optimization Theory and Operations Research. Springer, Cham, 105–119, 2020

    work page 2020

  5. [5]

    R. I. Bot ¸ and A. B¨ ohm.Alternating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. SIAM Journal on Optimization, 33(3):1884–1913, 2023

    work page 1913

  6. [6]

    Bullins and K

    B. Bullins and K. A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization, 32(3):2208–2229, 2022. Title Suppressed Due to Excessive Length 31

    work page 2022

  7. [7]

    Z. Chen, Z. Hu, Q. Li, Z. Wang, and Y. Zhou. A cubic regularization approach for find- ing local minimax points in nonconvex minimax optimization. Transactions on Machine Learning Research, pages 2835–8856, 2023

    work page 2023

  8. [8]

    F. E. Curtis, D. P. Robinson, C. W. Royer, and S. J. Wright.Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization . SIAM Journal on Optimization, 31(1):518–544, 2021

    work page 2021

Show all 67 references
  1. [9]

    S. S. Du, C. Jin, J. D. Lee, M. I. Jordan, A. Singh, and B. Poczos. Gradient descent can take exponential time to escape saddle points . Advances in Neural Information Processing Systems, pages 1068–1078, 2017

    2017

  2. [10]

    G. H. Golub, and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 2013

    2013

  3. [11]

    Gao and A.J

    R. Gao and A.J. Kleywegt. Distributionally robust stochastic optimization with wasser- stein distance. Mathematics of Operations Research, 48(2):603–655, 2023

    2023

  4. [12]

    Goodfellow, J

    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, pages 2672–2680, 2014

    2014

  5. [13]

    Gratton, S

    S. Gratton, S. Jerad, and P. L Toint. Yet another fast variant of Newton ’s method for nonconvex optimization. IMA Journal of Numerical Analysis, drae021, 2024

    2024

  6. [14]

    J. A. Hanley and B. J. McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1):29–36, 1982

    1982

  7. [15]

    C. He , Y. Jiang, C. Zhang, D. Ge, B. Jiang, and Y. Ye. Homogeneous second-order descent framework: a fast alternative to Newton-type methods. arXiv preprint arXiv:2306.17516, 2024

    2024 arXiv

  8. [16]

    Huang, J

    K. Huang, J. Zhang, and S. Zhang. Cubic regularized Newton method for the saddle point models: A global and local convergence analysis. Journal of Scientific Computing, 91(2):1– 31, 2022

    2022

  9. [17]

    Huang and S

    K. Huang and S. Zhang. An approximation-based regularized extra-gradient method for monotone variational inequalities. arXiv preprint arXiv: 2210.04440, 2022

    2022 arXiv

  10. [18]

    Jiang, A

    R. Jiang, A. Kavis, Q. Jin, S. Sanghavi, and A. Mokhtari. Adaptive and optimal second- order optimistic methods for minimax optimization. arXiv preprint arXiv:2406.02016, 2024

    2024 arXiv

  11. [19]

    Jiang and A

    R. Jiang and A. Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint arXiv: 2202.09674, 2022

    2022 arXiv

  12. [20]

    Jiang, C

    Y. Jiang, C. He, C. Zhang, D. Ge, B. Jiang, and Y. Ye. A universal trust-region method for convex and nonconvex optimization. arXiv preprint arXiv:2311.11489, 2023

    2023

  13. [21]

    C. Jin, P. Netrapalli, and M. I. Jordan. Minmax optimization: stable limit points of gra- dient descent ascent are locally optimal . International conference on machine learning, PMLR, pages 4880–4889, 2020

    2020

  14. [22]

    Kong and R

    W. Kong and R. D. C. Monteiro An accelerated inexact proximal point method for solving nonconvex concave min-max problems . SIAM Journal on Optimization, 31(4):2558–2585, 2021

    2021

  15. [23]

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

    1976

  16. [24]

    Kuczy´ nski and H

    J. Kuczy´ nski and H. Wo´ zniakowski.Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applica- tions, 13(4):1094–1122, 1992

    1992

  17. [25]

    Liu and L

    C. Liu and L. Luo. Regularized Newton methods for monotone variational inequalities with H ¨older continuous Jacobians. arXiv preprint arXiv:2212.07824, 2022

    2022 arXiv

  18. [26]

    T. Lin, C. Jin, amd M. I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems . International Conference on Machine Learning, PMLR, pages 6083– 6093, 2020

    2020

  19. [27]

    T. Lin, C. Jin, amd M. I. Jordan. Near-optimal algorithms for minimax optimization . Conference on Learning Theory, PMLR, pages 2738–2779, 2020

    2020

  20. [28]

    Lin and M

    T. Lin and M. I. Jordan. Perseus: a simple high-order regularization method for variational inequalities. Mathematical Programming, 1–42, 2024

    2024

  21. [29]

    T. Lin , P. Mertikopoulos, and M. I. Jordan. Explicit second-order min-max optimization methods with optimal convergence guarantee. arXiv preprint arXiv:2210.12860, 2022

    2022 arXiv

  22. [30]

    S. Liu, S. Lu, X. Chen, Y. Feng, K. Xu, A. Al-Dujaili, and U. M. O’Reilly. Min-max optimization without gradients: convergence and applications to black-box evasion and poisoning attacks. International conference on machine learning. PMLR, pages 6282–6293, 2020. 32 Junlin Wang, Zi Xu

    2020

  23. [31]

    S. Lu, I. Tsaknakis, M. Hong, and Y. Chen. Hybrid block successive approximation for one-sided nonconvex min-max problems: algorithms and applications . IEEE Transactions on Signal Processing, 68:3676–3691, 2020

    2020

  24. [32]

    L. Luo, Y. Li, and C. Chen. Finding second-order stationary points in nonconvex-strongly- concave minimax optimization. Advances in Neural Information Processing Systems, pages 36667–36679, 2022

    2022

  25. [33]

    Mishchenko

    K. Mishchenko. Regularized Newton method with global O(1/k2) convergence. SIAM Jour- nal on Optimization, 33(3):1440–1462, 2023

    2023

  26. [34]

    R. D. C. Monteiro and B. F. Svaiter. Iteration-complexity of a Newton proximal extragra- dient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization, 22(3):914–935, 2012

    2012

  27. [35]

    Nemirovski

    A. 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

  28. [36]

    Nesterov

    Y. Nesterov. Lectures on Convex Optimization. Springer, 2018

    2018

  29. [37]

    Nesterov

    Y. Nesterov. Cubic Regularization of Newton ’s Method for Convex Problems with Con- straints. Econometrics: Econometric & Statistical Methods - Special Topics eJournal, 2006

    2006

  30. [38]

    Nesterov

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

    2007

  31. [39]

    Nocedal and S

    J. Nocedal and S. J. Wright. Numerical optimization. Springer, 1999

    1999

  32. [40]

    Nouiehed, M

    M. Nouiehed, M. Sanjabi, T. Huang, and J. D. Lee. Solving a class of non-convex min- max games using iterative first order methods . Advances in Neural Information Processing Systems, pages 14934–14942, 2019

    2019

  33. [41]

    D. M. Ostrovskii, A. Lowy, and M. Razaviyayn. Efficient search of first-order nash equi- libria in nonconvex-concave smooth min-max problems . SIAM Journal on Optimization, 31(4):2508–2538, 2021

    2021

  34. [42]

    Ostroukhov, R

    P. Ostroukhov, R. Kamalov, P. Dvurechensky, and A. Gasnikov. Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities. arXiv preprint arXiv:2012.15595, 2020

    2012 arXiv

  35. [43]

    Ouyang and Y

    Y. Ouyang and Y. Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1–35, 2021

    2021

  36. [44]

    W. Pan, J. Shen, and Z. Xu. An efficient algorithm for nonconvex-linear minimax op- timization problem and its application in solving weighted maximin dispersion problem . Computational Optimization and Applications, 78(1):287–306, 2021

    2021

  37. [45]

    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

    1980

  38. [46]

    Rafique, M

    H. Rafique, M. Liu, Q. Lin, and T. Yang. Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning . Optimization Methods and Software, 37(3):1087–1121, 2022

    2022

  39. [47]

    C. W. Royer and S. J. Wright. Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization . SIAM Journal on Optimization, 28(2):1448–1477, 2018

    2018

  40. [48]

    C. W. Royer, M. O’Neill, and S. J. Wright. A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 180:451– 488, 2020

    2020

  41. [49]

    Sadiev, A

    A. Sadiev, A. Beznosikov, P. Dvurechensky, and A. Gasnikov. Zeroth-order algorithms for smooth saddle-point problems. International Conference on Mathematical Optimization Theory and Operations Research. Springer, Cham, 71–85, 2021

    2021

  42. [50]

    Sinha, H

    A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled adversarial training. International Conference on Learning Representations, 2018

    2018

  43. [51]

    J. Shen, Z. Wang, and Z. Xu. Zeroth-order single-loop algorithms for nonconvex-linear minimax problems. Journal of Global Optimization, 87:551–580, 2023

    2023

  44. [52]

    K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, pages 12680– 12691, 2019

    2019

  45. [53]

    J. Wang, J. Yang, and Z. Xu. A fully parameter-free second-order algorithm for convex-concave minimax problems with optimal iteration complexity. arXiv preprint arXiv:2407.03571, 2024

    2024 arXiv

  46. [54]

    Z. Wang, K. Balasubramanian, S. Ma, and M. Razaviyayn. Zeroth-order algo- rithms for nonconvex minimax problems with improved complexities. arXiv preprint arXiv:2001.07819, 2020. Title Suppressed Due to Excessive Length 33

    2001 arXiv

  47. [55]

    M. Xu, B. Jiang, Y.-F. Liu, and A. M.-C. So. A Riemannian alternating descent ascent algorithmic framework for nonconvex-linear minimax problems on Riemannian manifolds. arXiv preprint arXiv:2409.19588, 2024

    2024

  48. [56]

    T. Xu, Z. Wang, Y. Liang, and H. V. Poor. Gradient free minimax optimization: variance reduction and faster convergence. arXiv preprint arXiv:2006.09361, 2020

    2006 arXiv

  49. [57]

    Z. Xu, Z. Wang, J. Shen, and Y. Dai. Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems. SIAM Journal on Optimization, 34(2): 1879–1908, 2024

    1908

  50. [58]

    Z. Xu, Z. Wang, J. Wang, and Y. Dai. Zeroth-order alternating gradient descent ascent algorithms for a class of nonconvex-nonconcave minimax problems. Journal of Machine Learning Research, 24(313):1–25, 2023

    2023

  51. [59]

    Z. Xu, H. Zhang, Y. Xu, and G. Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems . Mathemat- ical Programming, Series A, 201:635–706, 2023

    2023

  52. [60]

    H. Yang, L. Luo , J. Li , M. I. Jordan, and Fazel M. Accelerating inexact hypergradient de- scent for bilevel optimization. Workshop on Optimization for Machine Learning (NeurIPS Workshop), 2023

    2023

  53. [61]

    L. Yann, B. L´ eon, B. Yoshua, and H. Patrick.Gradient-based learning applied to document recognition. Proceedings of IEEE, 86(11):2278–2324, 1998

    1998

  54. [62]

    Yao and Z

    T. Yao and Z. Xu. Two trust region type algorithms for solving nonconvex-strongly concave minimax problems. Science China Mathematics (Chinese) arXiv preprint arXiv:2402.09807, 2024

    2024 arXiv

  55. [63]

    Y. Ying, L. Wen, and S. Lyu. Stochastic online AUC maximization. Advances in Neural Information Processing Systems, pages 451–459, 2016

    2016

  56. [64]

    Zhang, P

    J. Zhang, P. Xiao, R. Sun, and Z. Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Advances in Neural Information Pro- cessing Systems, 33:7377–7389, 2020

    2020

  57. [65]

    Zhang, J

    S. Zhang, J. Yang, C. Guzm´ an, N. Kiyavash, and N. He. The complexity of nonconvex- strongly-concave minimax optimization . Uncertainty in Artificial Intelligence, PMLR, pages 482–492, 2021

    2021

  58. [66]

    Zhang, Q

    X. Zhang, Q. Xu, and N. S. Aybat. AGDA+: proximal alternating gradient descent ascent method with a nonmonotone adaptive step-size search for nonconvex minimax problems . arXiv preprint arXiv:2406.14371, 2024

    2024 arXiv

  59. [67]

    Zheng, L

    T. Zheng, L. Zhu, A. M.-C. So, J. Blanchet, and J. Li. Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization . Advances in Neural Informa- tion Processing Systems 36, 2023

    2023

Pith tools

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