← All setups

Nonsmooth Hidden Convex Stochastic — Nonsmooth Hidden Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Nonsmooth Hidden Convex Minimization · Lean proof

Nonsmooth Hidden Convex Minimization

We consider minimizing F=H∘c on a finite-dimensional real Hilbert space E, where H:E→R is convex and c:E→E is a differentiable bi-Lipschitz homeomorphism with Lipschitz derivative. The objective F can be nonsmooth and nonconvex. A global minimizer x⋆ exists, and F(0)≤F(y) whenever ∥y∥=R, for a given radius R>0. The oracle returns independent-sample estimates of a subgradient of H pulled back through the adjoint derivative of c, with unbiased means and uniformly bounded second moments. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[F(x¯)−F(x⋆)]≤ε, averaging over sampling and algorithm randomness.

The optimization problem is minx∈EF(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. Operator norms ∥⋅∥op are the induced operator norms. The parameters satisfy 0<μ≤Lc,LJ≥0,G>0,R>0,ε>0. The algorithm receives E, a measurable sample space Ω, and μ,Lc,LJ,G,R,ε; the functions F,H,c, their derivative field, and the oracle distribution are accessible only through the specified oracle replies.

Our assumptions:

Assumption 1 (Hidden convex structure). The function H:E→R is convex: for all u,v∈E and t∈[0,1], H((1−t)u+tv)≤(1−t)H(u)+tH(v). The map c:E→E is a homeomorphism, Fréchet differentiable at every point, with derivative J(x):E→E. For all x,y∈E, F(x)=H(c(x)),μ∥x−y∥≤∥c(x)−c(y)∥≤Lc∥x−y∥,∥J(x)−J(y)∥op≤LJ∥x−y∥.

Assumption 2 (Attainment and boundary condition). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E. The objective also satisfies F(0)≤F(y)for every y∈E with ∥y∥=R.

Assumption 3 (Stochastic pulled subgradients). There is a field g:E→E such that, for every x∈E, some sx∈E satisfies H(c(x))+⟨sx,u−c(x)⟩≤H(u)for all u∈E,g(x)=J(x)∗sx, where J(x)∗ is the adjoint of J(x).

Let ν be a probability measure on Ω. The oracle map a:E×Ω→E is jointly measurable. For every x∈E, a(x,⋅) is Bochner integrable and ∥a(x,⋅)∥2 is integrable under ν, with Eξ∼ν[a(x,ξ)]=g(x),Eξ∼ν[∥a(x,ξ)∥2]≤G2. At call k, a query x∈E receives a(x,ξk). The measurable samples (ξk)k≥0 are independent with common law ν under a joint probability law Q on ΩN. The algorithm’s randomness is independent of this sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable, its gap F(x¯)−F(x⋆) must be integrable, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Proved result

⌈10000000000⋅((1+64⋅LJ⋅Rμ)⋅(Lcμ+G2⋅Lc3⋅R2μ3⋅ε2))⋅(log⁡(10000000000⋅(2+(1+64⋅LJ⋅Rμ)⋅(Lcμ+G2⋅Lc3⋅R2μ3⋅ε2))))3⌉+

OracleTemplate.Convergence LongTails.Setups.NonsmoothHiddenConvex.spec OracleTemplate.NonsmoothHidden.budget

Relevant previous results

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