← All setups

Annealed Sgd River Valley — Step-Decay SGD in River Valleys

Descriptions may be stale. Consult the linked Lean sources.

Step-Decay SGD in River Valleys · Lean proof

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

Proved result

⌈256⋅Δ⋅(8⋅Lv+64⋅(2⋅Lh⋅σu2+(Γ⋅Lh+2⋅LJ⋅G)⋅((1792⋅(Γ⋅Lh+2⋅LJ⋅G)μ+224⋅Γ)⋅(σu2+σv2)+σu⋅σv)+(2⋅G⋅ρJ+2⋅LJ⋅Lh+Γ⋅ρh+G⋅LJ2)⋅σu⋅(14⋅(σu2+σv2)Lv+σu2μ+Γ⋅G⋅σuLv)+2⋅LJ2⋅σu4Lv)ε2)ε2+(log⁡(3+Lv2μ2+4⋅Lv2⋅(2⋅G⋅ρh⋅σu2+μ2⋅σu2+4⋅Lv2⋅σv2+8⋅Lv⋅LJ2⋅σu4μ)μ3⋅(Lv⋅ε2+8⋅(2⋅Lh⋅σu2+(Γ⋅Lh+2⋅LJ⋅G)⋅((1792⋅(Γ⋅Lh+2⋅LJ⋅G)μ+224⋅Γ)⋅(σu2+σv2)+σu⋅σv)+(2⋅G⋅ρJ+2⋅LJ⋅Lh+Γ⋅ρh+G⋅LJ2)⋅σu⋅(14⋅(σu2+σv2)Lv+σu2μ+Γ⋅G⋅σuLv)+2⋅LJ2⋅σu4Lv))))2⋅(16⋅Lvμ+512⋅(2⋅G⋅ρh⋅σu2+μ2⋅σu2+4⋅Lv2⋅σv2+8⋅Lv⋅LJ2⋅σu4μ)μ2⋅ε2)+1⌉+

OracleTemplate.Convergence LongTails.Setups.RiverValleyHillNoise.spec OracleTemplate.RiverValley.budget

Relevant previous results

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