← All setups

Local Hidden Convex Stochastic Minimization

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

In a finite-dimensional real Hilbert space, F is globally L-smooth and has a global minimizer x⋆∈B―(x0,R). On B(x0,3R), F=H∘c, with H convex and differentiable on an open convex set U. On B―(x0,2R), c(x)∈U, Dc(x)=J(x), ∥J(x)v∥≥μ∥v∥, and J is LJ-Lipschitz; 32LJR≤μ. Here L,R,μ,ε>0 and LJ,σ≥0. IID samples have law p; the jointly measurable oracle g satisfies ∫g(x,ω)dp=∇F(x) and ∫∥g(x,ω)−∇F(x)∥2dp≤σ2, with the required integrability. Target: ∫[F(xK)−F(x⋆)]dP≤ε, P=p⊗N. Result (1) constructs safeguarded similar triangles, using L,R,σ,x0; stopping also needs ε.

Local hidden-convex stochastic optimization: LocalHiddenConvexStochastic.
Result Oracle complexity Novelty Limitations
(1) HiddenConvexAcceleratedStochastic (Ours) (⋆⋆⋆) (review) O(1+(LR2ε+σ2R2ε2)ℓ2) stochastic-gradient calls.
(2) Momentum P-SGD (Fatkhullin et al. 2024, Thm. 8) O((1+Ld2ε+Ld4σ2ε3)ℓ0) calls, including initialization. Restriction: compact convex X∋x0,x⋆, convex c(X), and c−1 is 1/μc-Lipschitz; d=DU/μc. (1): On the overlap d≍R, ε−1→ε−1/2 and LR4σ2/ε3→σ2R2/ε2, up to logarithms; total gain for fixed parameters and sufficiently small ε. Scope: no compact convex image required. Adaptivity: updates need neither ε,DU,μc; stopping needs ε. (1) adds local C1,1 regularity and 32LJR≤μ; requires an unconstrained global minimizer. Classes are incomparable.
(3) (Bhaskara et al. 2025, Thm. 5.4) O(1+D2ρ+D24G3ρ(αβ)4ε3) calls. Restriction: global invertible c, ∥J∥≤1/α, ∥J−1∥≤1/β, ρ-Lipschitz J; G-Lipschitz H, ∥g∥≤G a.s.; known radii D1,D2 with the radial level-set ordering of (A3). (1): On the smooth overlap, fixed positive parameters and ε↓0, ε−3→ε−2ℓ2. Scope: bounded variance replaces bounded gradients; local replaces global Jacobian regularity. Full parameter bounds are not comparable. (1) requires global L-smoothness and 32LJR≤μ; loses nonsmooth objectives and the unrestricted global regime.
(4) AC-SA (Lan 2012, Cor. 1) O(1+LR2ε+σ2R2ε2) calls. Special case: LJ=0, with optimization restricted to B―(x0,R), where F is convex. (1): Scope extends convex optimization to locally near-affine hidden convexity, including nonconvex, non-quasar-convex objectives. (1) loses a factor ℓ2 on the convex overlap.

Abbr: L: gradient Lipschitz constant; R: initial-distance bound; σ2: variance bound; ε: expected objective-gap target; μ: least singular-value bound for J; LJ: Jacobian Lipschitz constant; ℓ=log⁡(2+LR2/ε+σ2R2/ε2). In (2), DU=diam(c(X)), d=DU/μc, and ℓ0=log⁡(2+(LR2+σ2/L)/ε) for one-sample gradient initialization. In (3), G denotes the paper’s bound H, ρ its Jacobian Lipschitz constant, α,β its distortion parameters, and D1,D2 its radial bounds about x0; radial ordering means F(y)≥F(x) whenever ∥x−x0∥=D1, ∥y−x0∥=D2.

Bhaskara, Aditya, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. 2025. “Descent with Misaligned Gradients and Applications to Hidden Convexity.” International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2025/hash/c40fc068ed2b4ad43bff4f3f3206691e-Abstract-Conference.html.
Fatkhullin, Ilyas, Niao He, and Yifan Hu. 2024. Stochastic Optimization Under Hidden Convexity. https://doi.org/10.48550/arXiv.2401.00108.
Lan, Guanghui. 2012. “An Optimal Method for Stochastic Composite Optimization.” Mathematical Programming 133 (1–2): 365–97. https://doi.org/10.1007/s10107-010-0434-y.

Lean setup