← All setups

Strongly Monotone Hidden-Potential Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Strongly Monotone Hidden-Potential Root Finding

We seek a zero of a map F:E→E on a real Hilbert space E. The map is μ-strongly monotone, where μ>0, and admits a hidden differentiable potential φ:E→R whose gradient is L-Lipschitz, with L≥0, while F−∇φ is s-Lipschitz, with s≥0. A given point x0∈E lies within distance R≥0 of a zero x⋆. The oracle returns F(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥x¯−x⋆∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is find x⋆∈E such that F(x⋆)=0. Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, x0, μ, L, s, R, and ε; the potential φ is not supplied.

Our assumptions:

Assumption 1 (Strong monotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥μ∥x−y∥2.

Assumption 2 (Hidden potential). There exists an everywhere Fréchet differentiable function φ:E→R such that, for every x,y∈E, ∥∇φ(x)−∇φ(y)∥≤L∥x−y∥,∥(F−∇φ)(x)−(F−∇φ)(y)∥≤s∥x−y∥.

Assumption 3 (Initial distance). There exists x⋆∈E satisfying F(x⋆)=0,∥x0−x⋆∥≤R.

Queries may be made at any point of E. Strong monotonicity makes the zero x⋆ unique. After the allotted oracle calls, the output must satisfy ∥x¯−x⋆∥≤εP-a.s.

Results

On a real Hilbert space, F is μ-strongly monotone and admits an unknown decomposition F=∇φ+S, with differentiable φ, L-Lipschitz ∇φ, and s-Lipschitz S. Neither convexity of φ nor monotonicity of S is assumed. Public parameters satisfy μ,ε>0 and L,s,R≥0; F(x⋆)=0 and ∥x0−x⋆∥≤R. Only exact evaluations of F are available. Target: ∥xout−x⋆∥≤ε, deterministically for (1). The setup imposes no algorithm restriction.

Hidden-potential strongly monotone root finding: HiddenPotentialStronglyMonotone.
Result Oracle complexity Novelty Limitations
(1) HiddenPotentialOracleComplexity (Ours) (⋆⋆) (review) O((μ+s)(L+μ+s)μhℓ) combined calls.
(2) Past extragradient (Gidel et al. 2020, Thm. 1) O(1+L+sμℓ) combined calls; one per step. (1): gain (L+s)/(μ+s)/h when L+s≫(μ+s)h2. At s≤μ, O(κℓ) versus O(κℓ); at s=Lμ, O(κ3/4(1+log⁡κ)ℓ) versus O(κℓ), for κ≫1. (1): loses factor h when s≳L; needs L,s separately instead of L+s.
(3) (Wang and Li 2020, Thm. 3) O(Lμ+L¯sμ2(1+log⁡(L¯/μ))3
×[1+log(1+L¯2Rμ2ε)]) combined calls. Finite-dimensional public saddle partition; block moduli μ, smoothness L, coupling s.
(1): on bilinear overlap with s≤L, matches polynomial order, removes roughly log2⁡(L/μ) and condition dependence inside accuracy log. Scope: hidden decomposition, nonlinear residuals without blocks. (1) does not cover the general nonlinear-coupling saddle class of (3); outside the bilinear overlap, rates are not comparable.
(4) APDG (Kovalev et al. 2022, Thm. 4.2, Sec. 5.1) O(1+[L/μ+s/μ]
×[1+log+⁡(C/ε2)]) combined calls, including component recovery. Finite-dimensional bilinear saddle; public partition, μ-strongly convex, L-smooth components, ∥A∥≤s. Initialization constant C unexpanded.
(1): scope extends to hidden partitions and nonlinear residuals. On the stated restriction, component gradients and matrix products require only constantly many combined calls. (1) has worse polynomial dependence for μ≪s≪L: Ls/μ versus L/μ+s/μ, with additional logarithms.
(5) Restarted AG-EG (Yuan et al. 2023, Cor. 2.8) O([L/μ+s/μ]ℓ) total split evaluations of ∇φ and S, zero noise. Finite-dimensional; φ μ-strongly convex, S monotone. (1): only combined F access; no revealed decomposition, convexity of φ, or monotonicity of S required. (1) has larger polynomial cost when μ≪s≪L: Ls/μ versus L/μ+s/μ. Oracles differ; this is not an identical-access comparison.

Abbr: ℓ=1+log⁡(1+R/ε); h=1+log⁡(1+s/μ); κ=L/μ; L¯=max{L,s}; log+⁡t=max{0,log⁡t}. Combined call: one evaluation of F; split call: one evaluation of ∇φ or S. C>0 is the initialization and parameter dependent squared-distance scale in (4). Bilinear overlap: F(x,y)=(∇f(x)+A⊤y,∇g(y)−Ax), with f,g μ-strongly convex and L-smooth, ∥A∥≤s.

Gidel, Gauthier, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. 2020. A Variational Inequality Perspective on Generative Adversarial Networks. https://doi.org/10.48550/arXiv.1802.10551.
Kovalev, Dmitry, Alexander Gasnikov, and Peter Richtárik. 2022. Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling. https://doi.org/10.48550/arXiv.2112.15199.
Wang, Yuanhao, and Jian Li. 2020. Improved Algorithms for Convex-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2006.06359.
Yuan, Huizhuo, Chris Junchi Li, Gauthier Gidel, Michael I. Jordan, Quanquan Gu, and Simon S. Du. 2023. “Optimal Extragradient-Based Algorithms for Stochastic Variational Inequalities with Separable Structure.” Advances in Neural Information Processing Systems 36. https://proceedings.neurips.cc/paper_files/paper/2023/file/69ce18ad9f53f28e8e7ac1649ae02337-Paper-Conference.pdf.

Lean setup