← All setups

High-Dimensional Nonconvex Optimization with ABC Noise

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Nonconvex Optimization with ABC Noise

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d is a positive integer, with finite infimum f⋆ and an L-Lipschitz gradient, where L>0. The oracle returns g(x,ξ) at x, using independent real samples ξ with a common probability law. Its replies are unbiased and satisfy E∥g(x,ξ)−∇f(x)∥2≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C, where A,B,C≥0. For a tolerance ε>0, the goal is a measurable output x¯∈Rd satisfying E∥∇f(x¯)∥≤ε, with expectation over oracle samples and independent algorithm randomness.

The optimization problem is infx∈Rdf(x). Throughout, ∥⋅∥ denotes the Euclidean norm. A starting point x0∈Rd and an initial-gap bound Δ∈R are given. The algorithm receives d,L,A,B,C,Δ,ε, and x0.

Our assumptions:

Assumption 1 (Parameter and dimension regime). The parameters satisfy d∈N,L>0,A,B,C≥0,ε>0,226ε2≤LΔ,d≥240(1+LΔε2(1+B+AΔ+Cε2))4. In particular, these conditions imply Δ>0 and d>0.

Assumption 2 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd. Its infimum f⋆ is finite, and f⋆=infx∈Rdf(x)∈R,f(x0)−f⋆≤Δ.

Assumption 3 (IID stochastic gradients with ABC noise). There exist a probability measure ν on R and a jointly measurable map g:Rd×R→Rd. At call k, a query x∈Rd receives g(x,ξk), where (ξk)k≥0 is a sequence of measurable, mutually independent random variables with common law ν. This sequence is independent of the algorithm’s randomness. For every fixed x∈Rd, the 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]≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C.

Queries may be made at any point of Rd. Let P denote the joint law of the oracle samples and the independent algorithm randomness. After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be P-integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Results

L>0, A,B,C≥0, ε>0; f:Rd→R has L-Lipschitz gradient, finite f⋆=inff, and f(x0)−f⋆≤Δ. The jointly measurable IID oracle g(x,ξ) is integrable and unbiased, with integrable squared error satisfying Ep∥g(x,ξ)−∇f(x)∥2≤2A(f(x)−f⋆)+B∥∇f(x)∥2+C. Target: EP∥∇f(x^)∥≤ε, including algorithm randomness. Validity: 226ε2≤LΔ and d≥240(1+LΔε2(1+B+AΔ+Cε2))4. All randomized adaptive algorithms are allowed.

Lower bounds (necessary budgets) for HighDimensionalAbcNoiseNonconvex.
Result Oracle complexity Novelty Limitations
(1) AbcNoiseLowerBound (Ours) (⋆⋆⋆) (review) Necessary Ω(LΔε2(1+B+AΔ+Cε2)) IID gradient calls.
(2) (Arjevani et al. 2022; Carmon et al. 2019), Thms. 3 and 2 (p=1); bounded-variance special case A=B=0 Necessary Ω(LΔε2+LΔCε4) gradient calls; ε≤cLΔ, sufficiently large d. (1): adds BLΔ/ε2 and LAΔ2/ε4; A-term gain factor AΔ/max{C,ε2} when AΔ≫max{C,ε2}. For B=C=0: Ω(LΔ/ε2)→Ω(LAΔ2/ε4). Matches at A=B=0. (1): quartic dimension requirement; much worse universal constant on A=B=0.
(3) Derived bound from (Arjevani et al. 2022), Thm. 3; lower-offset model Necessary Ω(LAΔ2ε4) gradient calls for variance ≤2A(f−flow), B=C=0; A>0, ε≤cLΔ, sufficiently large d. (1): same A-term order with exact infimum instead of a lower offset. The offset reduction does not establish hardness for variance vanishing near minimizers.
(4) (Huang et al. 2022), Thm. 1; synchronous zero-respecting algorithms, n≥2 workers, unbiased compression Necessary Ω(n(1+ω)LΔε2+LΔσ2ε4) worker-gradient calls and compressed uplinks; T≥(1+ω)2; target E∥∇f(x^)∥2≤ε2. (1): arbitrary randomized algorithms with one IID oracle; (4) restricts algorithms and uses compression. Rates are not comparable across these models and accuracy criteria.

Abbr: p: sample law; P: execution law. Ω: necessary worst-case budget, not sufficient algorithm cost; c>0: universal constant. In (3), use initial gap Δ/2, constant variance AΔ, and flow=f⋆−Δ/2. In (4), n: workers; T: queries and compressed uplinks per worker; σ2>0: local gradient variance bound; ω≥0: unbiased-compressor relative variance parameter.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2022. Lower Bounds for Non-Convex Stochastic Optimization. https://doi.org/10.48550/arXiv.1912.02365.
Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2019. Lower Bounds for Finding Stationary Points I. https://doi.org/10.48550/arXiv.1710.11606.
Huang, Xinmeng, Yiming Chen, Wotao Yin, and Kun Yuan. 2022. Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression. https://doi.org/10.48550/arXiv.2206.03665.

Lean setup