← All setups

Step-Decay SGD in River Valleys

Descriptions may be stale. Consult the linked Lean sources.

Step-Decay SGD in River Valleys

We consider minimizing a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The objective combines a smooth function along a subspace with a positive quadratic penalty around a curved valley. Derivative bounds, curvature separation conditions, and a bound on the initial objective gap control this geometry. The oracle returns unbiased stochastic gradients with independent, identically distributed samples and separately bounded noise variances along and across the valley. Starting from a given x0∈E, step-decay SGD must return x¯∈E with EP∥∇f(x¯)∥≤ε, where ε>0 and P is the joint law of sampling and algorithm randomness.

The optimization problem is infx∈Ef(x). The norm on E is induced by its inner product. All operator and multilinear norms below are induced operator norms. The algorithm receives E, the measurable sample space Ω, the starting point x0, and the parameters 0<μ≤Lv,ε>0,Lh,ρh,G,Γ,LJ,ρJ,σu,σv,Δ≥0. The objective, its geometric decomposition, and the sampling distribution are accessed only through the oracle.

Our assumptions:

Assumption 1 (Valley geometry and regularity). There exist a linear subspace S⊆E, twice Fréchet differentiable maps h:E→R and ϕ:E→E, and a self-adjoint linear operator A:E→E. Write Πu and Πv for the orthogonal projections onto S⊥ and S, respectively. Then r(x)=Πvx−ϕ(Πux),f(x)=h(Πux)+12⟨Ar(x),r(x)⟩,x∈E. For every y,z∈E, the hill component satisfies ∥∇h(y)∥≤G,∥∇h(y)−∇h(z)∥≤Lh∥y−z∥,∥∇2h(y)−∇2h(z)∥op≤ρh∥y−z∥. Let J(y)=Dϕ(y):E→E, with derivative DJ(y) viewed as a bilinear operator on E×E. For every y,z∈E, ϕ(y)∈S,∥J(y)−J(z)∥op≤LJ∥y−z∥,∥DJ(y)−DJ(z)∥op≤ρJ∥y−z∥,∥AJ(y)Πuz∥≤Γμ∥Πuz∥. The quadratic operator preserves S and satisfies, for every v∈S, Av∈S,μ∥v∥2≤⟨Av,v⟩,∥Av∥≤Lv∥v∥.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Stochastic gradient oracle). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. At its kth query x, the oracle returns g(x,ξk), where the measurable random variables (ξk)k≥0 are independent with common law ν. Their joint law is independent of the algorithm’s randomness. Queries may be made anywhere in E.

For every fixed x∈E, the map g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). Writing e(x,ξ)=g(x,ξ)−∇f(x), both projected squared norms below are integrable and satisfy Eξ∼ν∥Πue(x,ξ)∥2≤σu2,Eξ∼ν∥Πve(x,ξ)∥2≤σv2.

Assumption 4 (Parameter separation). Define the following combinations of the given parameters: a=ΓLh+2LJG,b=2GρJ+2LJLh+Γρh+GLJ2,c=256a2μ+32Γa+2bσuLv,d=2Lhσu2+7c(σv2+σu2)+aσuσv+bσu3μ+bΓGσu2Lv+2LJ2σu4Lv,q=(2Gρh+Lh2)σu2+4Lv2σv2+20Γ2μ2σu2+8LvLJ2σu4μ+ΓμGLJσu24. They obey 16Γ≤1,64a≤μ,64bσu≤μLv,32Lhlog⁡(3+Lv2μ2+4Lv2qμ3(Lvε2+8d))≤μ.

Our result is algorithm-specific: we analyze step-decay SGD with a uniformly randomized switching time. The algorithm chooses two step sizes ηs,ηc>0 and integers T,K≥0 from its inputs. It draws τ uniformly from {0,…,T}, independently of the oracle samples, and starts at the given x0. At call k≥0, it queries xk and uses the recurrence xk+1={xk−ηsg(xk,ξk),k<τ,xk−ηcg(xk,ξk),τ≤k<τ+K,xk,k≥τ+K. After a budget of N≥0 oracle calls, the output is x¯=xN. Calls after τ+K still count toward N, although they leave the iterate unchanged.

The output must be measurable, its gradient norm must be integrable under P, and the required stationarity criterion is EP[∥∇f(x¯)∥]≤ε.

Results

In a finite-dimensional real inner-product space, f(x)=h(Qx)+12⟨A(Px−ϕ(Qx)),Px−ϕ(Qx)⟩, with unknown orthogonal split, ϕ(E)⊆K, symmetric A preserving K, and μI⪯A|K⪯LvI. The nonconvex river satisfies ∥∇h∥≤G; ∇h,∇2h,Dϕ,D2ϕ have Lipschitz constants Lh,ρh,LJ,ρJ, respectively, and ∥ADϕ(y)Q∥≤Γμ. Assume f(x0)−inff≤Δ, 0<μ≤Lv, ε>0, nonnegative remaining parameters, 16Γ≤1, 64c≤μ, 64dσu≤μLv, and 32Lhlog⁡R0≤μ. The jointly measurable, integrable oracle is IID and unbiased, with river/hill error second moments at most σu2,σv2. The setup requires two-phase constant-step SGD; tuning knows the scalar parameters, but not K,ϕ,A. Target: ∫∥∇f(xout(ω))∥dP(ω)≤ε, for the last iterate after a uniformly randomized first-phase duration and a fixed cooldown.

Annealed SGD for RiverValleyHillNoise.
Result Oracle complexity Novelty Limitations
(1) AnnealedSgdRiverValley (Ours) (⋆⋆⋆) (review) O(1+LvΔε2+ΔBε4+log2⁡R(Lvμ+Wμ2ε2))
(2) Randomized SGD (Ghadimi and Lan 2013), Cor. 2.2. Affine-river restriction: LJ=ρJ=0, L≍Lv. O(1+LvΔε2+LvΔs2ε4) (1): affine-river noise coefficient L′ instead of Lv; gain ≍min{σ2/ε2,Lv/L′,μ2Δ/(Lvε2log2⁡R)} when this minimum exceeds one. Scope: curved rivers at the displayed rate; unknown split. (1): extra cooldown can dominate when Lvε2log2⁡R>μ2Δ; same order for σ≲ε. Needs river structure and regularity; expected norm instead of expected squared norm.
(3) SGD (Li et al. 2023), Thm. 5.3. Generalized smoothness; covers curved rivers. O(1+ℓ(2H)Fε2+H2F2ε4)
Pr{T−1∑t<T∥∇f(xt)∥2≤ε2}≥1−δ.
(1): expected stationarity of one output on curved rivers. Rates are not comparable with (3)’s high-probability average criterion. (1): narrower quadratic-hill structure, bounded river gradient and higher regularity; no high-probability average guarantee.

Abbr: P=PK, Q=PK⊥; P is the execution law (IID samples and stopping randomization). Costs count individual stochastic-gradient calls, including cooldown. s2=σu2+σv2, σ=max{σu,σv}; c=ΓLh+2LJG, d=2GρJ+2LJLh+Γρh+GLJ2. B=2Lhσu2+7(256c2/μ+32Γc+2dσu/Lv)s2+cσuσv+dσu3/μ+dΓGσu2/Lv+2LJ2σu4/Lv. W=2Gρhσu2+μ2σu2+4Lv2σv2+8LvLJ2σu4/μ; V=(2Gρh+Lh2)σu2+4Lv2σv2+20Γ2μ2σu2+8LvLJ2σu4/μ+ΓμGLJσu2/4. R=3+Lv2/μ2+4Lv2W/[μ3(Lvε2+8B)]; R0 replaces W by V in R. L′=Lh+Γρhσ/μ+Γ2ρhG/Lv (affine-river comparison, L′>0). For (3), δ∈(0,1), ℓ(u)=Lh+(1+Γ)2Lv+LJu bounds ∥∇2f∥ at gradient norm u; F=8(Δ+s)/δ, H=sup{u≥0:u2≤2ℓ(2u)F}.

Ghadimi, Saeed, and Guanghui Lan. 2013. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. https://doi.org/10.48550/arXiv.1309.5549.
Li, Haochuan, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. 2023. Convex and Non-Convex Optimization Under Generalized Smoothness. https://doi.org/10.48550/arXiv.2306.01264.

Lean setup