← All setups

Hidden Convex Accelerated Stochastic — Local Hidden Convex Stochastic Minimization

Descriptions may be stale. Consult the linked Lean sources.

Local Hidden Convex Stochastic Minimization · Lean proof

Local Hidden Convex Stochastic Minimization

We minimize a differentiable, possibly nonconvex function F:E→R on a finite-dimensional real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E is within distance R>0 of a global minimizer x⋆. Locally, F is a convex function composed with a differentiable change of coordinates whose derivative is uniformly nonsingular and varies slowly. The oracle returns unbiased stochastic gradients with variance at most σ2, where σ≥0, using independent samples. For ε>0, the goal is a measurable output x¯∈E with integrable gap and E[F(x¯)−F(x⋆)]≤ε, averaging over oracle and independent algorithm randomness.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. Write B(x,r) and B―(x,r) for the open and closed balls. The algorithm receives only E, the measurable sample space Ω, L, R, σ, and x0; the parameters μ>0, LJ≥0, and ε>0 may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Local hidden convexity). There exist functions H:E→R and c:E→E, an open convex set U⊆E, and a map J assigning a linear operator J(x):E→E to each x∈E, such that F(x)=H(c(x)),x∈B(x0,3R). The function H is differentiable on U and satisfies H((1−t)u+tv)≤(1−t)H(u)+tH(v),u,v∈U,t∈[0,1]. For every x∈B―(x0,2R), we have c(x)∈U, the map c is Fréchet differentiable at x with derivative J(x), and μ∥v∥≤∥J(x)v∥,v∈E. The derivative satisfies ∥J(x)−J(y)∥op≤LJ∥x−y∥,x,y∈B―(x0,2R),32LJR≤μ.

Assumption 2 (Global smoothness). The function F is Fréchet differentiable everywhere on E, and ∥∇F(x)−∇F(y)∥≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial distance). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 4 (Stochastic gradient oracle). Let ν be a probability measure on Ω. The oracle is a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇F(x)∥2 is integrable for ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇F(x),Eξ∼ν[∥g(x,ξ)−∇F(x)∥2]≤σ2. At the kth query x, the oracle returns g(x,ξk), where (ξk)k≥0 are independent with common law ν and are independent of the algorithm’s randomness.

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

Proved result

⌈300000⋅(L⋅R2ε+σ2⋅R2ε2)⋅(log⁡(300000⋅(2+L⋅R2ε+σ2⋅R2ε2)))2⌉+

OracleTemplate.Convergence LongTails.Setups.LocalHiddenConvexStochastic.spec OracleTemplate.LocalHiddenConvex.budget

Relevant previous results

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