← All setups

Nonsmooth Hidden Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, F=H∘c attains its minimum, H is finite convex, and c is a differentiable homeomorphism with μ∥x−y∥≤∥c(x)−c(y)∥≤Lc∥x−y∥ and LJ-Lipschitz Jacobian. Known R>0 satisfies F(0)≤F(y) on ∥y∥=R. Jointly measurable IID oracle samples satisfy ∫g(x,ω)dp(ω)=Dc(x)∗sx, sx∈∂H(c(x)), and ∫∥g(x,ω)∥2dp(ω)≤G2. The target is ∫[F(x^)−F(x⋆)]dP≤ε, with P the IID sampling law. Parameters satisfy 0<μ≤Lc, LJ≥0, G,ε>0.

Nonsmooth hidden convexity: NonsmoothHiddenConvex.
Result Oracle complexity Novelty Limitations
(1) NonsmoothHiddenConvexStochastic (Ours) (⋆⋆⋆) (review) O(Wlog3⁡(2+W))
(2) (Bhaskara et al. 2025), Thm. 5.4 O(1+G3R4Lc4ρ′μ4ε3); ρ′=max{LJ/μ,μ/(LcR2)}. Almost-sure bound ∥g∥≤G; two-sphere condition specialized to D1=0,D2=R. (1): ε−2 instead of ε−3 up to logarithms; gain when GR/ε≫log3⁡(2+W). For LJR≥μ, factor GLcR/(μεlog3⁡(2+W)). Only second moments required.
(3) SGD (Bubeck 2015), Thm. 6.1; affine special case LJ=0 O(1+G2R2/ε2) stochastic subgradients. (1): scope extends to nonlinear hidden maps; no rate improvement on LJ=0. (1) costs an extra (Lc/μ)3log3⁡(2+W) for LJ=0, ε<GR.
(4) (Fatkhullin et al. 2024), Thm. 2, Cor. 1 Not comparable: requires closed convex X and bounded convex c(X); the target has c(E)=E. (1) handles the global unconstrained problem. No bounded-domain reduction is supplied; rates are not comparable. (1) requires a global smooth homeomorphism and barrier radius; (4) permits constrained problems and nonsmooth maps.

Abbr: W=(1+LJR/μ)(Lc/μ+G2Lc3R2/(μ3ε2)); x⋆ is a global minimizer; x^ is the final epoch center in (1); costs count individual stochastic oracle calls.

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.
Bubeck, Sébastien. 2015. “Convex Optimization: Algorithms and Complexity.” Foundations and Trends in Machine Learning 8 (3–4): 231–358. https://doi.org/10.1561/2200000050.
Fatkhullin, Ilyas, Niao He, and Yifan Hu. 2024. Stochastic Optimization Under Hidden Convexity. https://doi.org/10.48550/arXiv.2401.00108.

Lean setup