← All setups

Cohypomonotone Root Finding with Adjoints

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Root Finding with Adjoints

We seek a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map is L-Lipschitz and ρ-cohypomonotone, and its derivative J(x):E→E is L2-Lipschitz, where L>0, L2≥0, and ρ≥0. A given point x0∈E lies within distance R≥0 of a zero. The oracle returns F(x) or the adjoint product J(x)∗w for x,w∈E. For ε>0, the goal is an output x¯∈E satisfying ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is to find x∈E such that F(x)=0. The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives only E, L, L2, ρ, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Differentiability and Lipschitz bounds). The map F is Fréchet differentiable at every x∈E, with derivative J(x). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥,∥J(x)−J(y)∥op≤L2∥x−y∥.

Assumption 2 (Cohypomonotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥−ρ∥F(x)−F(y)∥2.

Assumption 3 (Initial distance to a zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Oracle queries may use any x,w∈E. Both reply types are exact, with the adjoint characterized by ⟨J(x)∗w,h⟩=⟨w,J(x)h⟩,h∈E. Each evaluation of F(x) or J(x)∗w counts as one call toward a shared oracle-call budget. After the allotted calls, the output must satisfy ∥F(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, F:E→E is differentiable and L-Lipschitz, with L2-Lipschitz Jacobian and ⟨F(x)−F(y),x−y⟩≥−ρ∥F(x)−F(y)∥2. A zero x⋆ satisfies ∥x0−x⋆∥≤R, where L>0 and L2,ρ,R≥0. Exact queries return F(x) or DF(x)∗w. The target is ∥F(x^)∥≤ε, ε>0, almost surely; the constructed algorithms are deterministic. Their updates use L,L2,ρ; R,ε enter their budgets. The setup imposes no algorithm restriction.

Comparison for CohypomonotoneAdjoint.
Result Oracle complexity Novelty Limitations
(1) AdjointAcceleratedCohypomonotone (Ours) (⋆⋆) (review) O((T+1+ρL)log⁡(e+ρL)+(1+ρL)5log⁡(e+ρL)L2RLℓ2) total F/adjoint calls
(2) AdjointAnchoredCohypomonotone (Ours) (⋆⋆) (review) O(((1+ρL)T+(1+ρL)2)⋅log⁡(e+ρL)+(1+ρL)4L2RLℓ2) total F/adjoint calls
(3) Inexact Halpern (Alacaoglu et al. 2026), Thm. 2.1, Cor. 2.2; G=0, ρL<1 O(1+T/ddlog⁡(e+T/d)) F calls; η=(ρ+1/L)/2 (1), (2): Scope extends to every ρ with adjoints and Lipschitz Jacobian. On d>0, cost becomes O(1+T+(L2R/L)ℓ2). For L=R=L2=1, d=10−2, ε≤10−2: O(ε−1+ℓ2) versus O(104ε−1log⁡(e+100/ε)). (1), (2) need adjoints and known L2; add (L2R/L)ℓ2 burn-in. This can dominate for larger ε. No general G extension.
(4) EAG (Yoon and Ryu 2021), Cor. 1 and monotone-operator extension; ρ=0 O(1+LR/ε) F calls (1), (2): No established improvement on ρ=0; scope extends to ρ>0 with the stronger oracle and Jacobian regularity. (1), (2) add (L2R/L)ℓ2 and require adjoints and known Lipschitz-Jacobian constant L2.
(5) Exact proximal point (Gorbunov et al. 2023), Thm. 3.1; maximally ρ-cohypomonotone O(1+R2γ(γ−2ρ)ε2) exact (I+γF)−1 calls, γ>2ρ (1), (2) implement inexact resolvents with finite F/adjoint budgets for every ρ; oracle costs are not comparable. Within this realization, (1) versus (2) removes a leading 1+ρL factor for ρL≥1, ε(1+ρL)4L2ℓ2≪L2. (1), (2) require Lipschitz F and Jacobian. Internally, (1) versus (2) increases burn-in by (1+ρL)log⁡(e+ρL); no uniform dominance.

Abbr: T=LR/ε; ℓ=log⁡(e+LR/ε); d=1−ρL; DF(x)∗ is the Jacobian adjoint; I is the identity; γ is the proximal step size. Total F/adjoint cost counts each evaluation separately. ≪ denotes a sufficiently small universal-factor comparison.

Alacaoglu, Ahmet, Donghwan Kim, and Stephen J. Wright. 2026. Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity. arXiv:2402.05071v3. https://doi.org/10.48550/arXiv.2402.05071.
Gorbunov, Eduard, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. 2023. “Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: The Case of Negative Comonotonicity.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 11614–41. https://proceedings.mlr.press/v202/gorbunov23a.html.
Yoon, Taeho, and Ernest K. Ryu. 2021. “Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm.” In Proceedings of the 38th International Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol. 139. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v139/yoon21d.html.

Lean setup