Research map / Optimization / Nonconvex and smooth optimization
Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends extragradient to alpha-symmetric (L0,L1)-Lipschitz root-finding operators with norm-adaptive step sizes, giving linear rates for strongly monotone and sublinear/local rates for monotone and weak Minty operators.
Problem
Extragradient convergence for root-finding/variational inequalities when the operator is not globally L-Lipschitz, i.e., its local Lipschitz constant grows with the operator norm.
Approach
Replaces the global L-Lipschitz assumption with an alpha-symmetric (L0,L1)-Lipschitz condition on the operator, and uses the adaptive extragradient step size gamma_k = 1/(c0 + c1*||F(x_k)||^alpha) (omega_k = gamma_k for monotone and strongly monotone cases, gamma_k/2 for weak Minty), proving convergence without exponential dependence on the initial distance in the strongly monotone case.
Key results
- For strongly monotone 1-symmetric (L0,L1)-Lipschitz operators, the proposed step size outperforms the baseline step size on a toy operator, with the baseline step size staying near 0.02 while the proposed step size grows above 0.032.
- For monotone problems, the adaptive step size with c0=10, c1=10 achieves the best results among 9 grid combinations and outperforms the best constant step size (c=10^5).
- Theory gives O(1/(K+1)) rate for min ||F(x_k)||^2 in the monotone alpha in (0,1) case, and the strongly monotone result removes exp(L1||x0-x*||) from the leading term.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the [cite] step size with γ_k = ω_k = ν/(L_0 + L_1 ||F(x_k)||) | EG on the strongly monotone problem · Strongly monotone problem | relative error | Helped |
| Use the proposed adaptive step size instead of the constant step size | EG on the monotone problem · Monotone problem | relative error | Helped |
| Use (c_0, c_1) = (10, 10) among the adaptive step-size choices (ablation) | EG with adaptive step size on the monotone problem · Monotone problem | relative error | Helped |
| Set the constant-step-size parameter to c=10^5 rather than other tested values (ablation) | EG with constant step size on the monotone problem · Monotone problem | relative error | Mixed |
| Increase the adaptive step size over iterations rather than keep the constant step size | EG on the monotone problem · Monotone problem | step size: larger than the constant step size | Helped |
Surprising findings
- The adaptive step size starts smaller than the best constant step size but grows over time and eventually exceeds it.
Limitations
- Analysis only covers unconstrained root-finding problems; constrained setting not handled.
- Monotone and weak Minty results depend exponentially on ||x0-x*|| when L1>0 (monotone 1-symmetric case), and weak Minty result is local, requiring x0 close to x* and rho small.
- Constants alpha, L0, L1 must be known; estimating them is left open.
Experimental setup
Benchmarks: strongly monotone toy operator monotone min-max problem with non-Lipschitz power objective GlobalForsaken weak Minty problem
Metrics: relative error ||x_k - x*||^2/||x_0 - x*||^2 step size magnitude ||F(x_k)||
Baselines: extragradient with constant step size extragradient with step sizes from Pethick et al. (2025) style L0L1 analysis
Builds on: extragradient method (L0,L1)-smoothness Korpelevich extragradient
Closest papers by meaning
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.87)
- A Primal-Dual Approach to Solving Variational Inequalities with General Constraints (ICLR 2024 · similarity 0.86)
- Adaptive Proximal Gradient Methods Are Universal Without Approximation (ICML 2024 · similarity 0.86)
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.85)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.85)
- Delving into the Convergence of Generalized Smooth Minimax Optimization (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.