← All setups

Constrained Generalized Monotone — Constrained Generalized Monotone Inequalities

Descriptions may be stale. Consult the linked Lean sources.

Constrained Generalized Monotone Inequalities · Lean proof

Constrained Generalized Monotone Inequalities

We consider a variational inequality for a continuous monotone operator F:E→E on a convex set X in a real inner product space E. The operator satisfies a segmentwise generalized Lipschitz condition with constants L0>0 and L1≥0. A given point x0∈X has bounded distance to a solution, with operator norms bounded at both points. Two exact oracles return F(x) and the projection of x onto X. For ε>0, the goal is a feasible output x¯ admitting ξ∈E with ⟨ξ,w−x¯⟩≤0 for every w∈X and ∥F(x¯)+ξ∥≤ε, almost surely under P, the law of the algorithm’s randomness.

The variational inequality asks for x⋆∈X such that ⟨F(x⋆),w−x⋆⟩≥0for every w∈X. The norm ∥⋅∥ is induced by the inner product on E. The parameters satisfy L0>0,L1≥0,R>0,G≥0,G0≥0,ε>0. The algorithm receives only E, L0, L1, and x0; the parameters R, G, G0, and ε may enter the oracle-call budgets but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convex constraints and projection). The set X⊆E is convex. There exists a map ΠX:E→E satisfying, for every z∈E, ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0for every w∈X.

Assumption 2 (Monotonicity and generalized Lipschitz continuity). The operator F is continuous on E and satisfies ⟨F(x)−F(y),x−y⟩≥0for all x,y∈E. For every x,y∈E and M∈R, the segment bound ∥F(x+θ(y−x))∥≤Mfor all θ∈[0,1] implies ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Initial point and solution bounds). The given starting point satisfies x0∈X and ∥F(x0)∥≤G0. There exists a solution x⋆ of the variational inequality such that ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G.

Queries to either oracle may be made at any point of E. The operator oracle returns F(x) at x, and the projection oracle returns ΠX(z) at z. Calls to these two oracles are counted separately.

For a feasible point x, define its normal cone by NX(x)={ξ∈E:⟨ξ,w−x⟩≤0 for every w∈X}. After the allotted oracle calls, the output must satisfy the normal-cone residual criterion x¯∈X,∃ξ∈NX(x¯):∥F(x¯)+ξ∥≤εP-a.s.

Proved result

Oracle 0:2⋅(⌈16⋅(L0+L1⋅G)⋅(1+8⋅L1⋅R)⋅Rε+(132⋅L1⋅R⋅(1+L1⋅R)+4)⋅log⁡(2+8⋅R⋅(L0+2⋅L1⋅G0)ε)⌉++1) Oracle 1:⌈16⋅(L0+L1⋅G)⋅(1+8⋅L1⋅R)⋅Rε+(132⋅L1⋅R⋅(1+L1⋅R)+4)⋅log⁡(2+8⋅R⋅(L0+2⋅L1⋅G0)ε)⌉++1

OracleTemplate.Convergence LongTails.Setups.ConstrainedGeneralizedMonotone.spec
  OracleTemplate.ConstrainedMonotone.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.