Skip to content
nonconvexcard

Reading the Robbins–Monro conditions off the proof

ProofIntermediate⏱ 30 minSGDrobbins-monrostep sizeschedule

Problem

From the recursion et+1≤(1−ηtμ)et+ηt2σ2e_{t+1}\le(1-\eta_t\mu)e_t+\eta_t^2\sigma^2, explain why the conditions

∑tηt=∞,∑tηt2<∞\sum_t\eta_t = \infty,\qquad \sum_t\eta_t^2<\infty

are exactly what is needed for et→0e_t\to0. Check which of ηt=η\eta_t = \eta, ηt=c/t\eta_t = c/\sqrt t, ηt=c/t\eta_t = c/t satisfy them, and what each gives.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
The exact step-size threshold on a quadraticOptimizationProofBeginner15 min
Mini-batching and the compute budgetSGDNumericalIntermediate30 min
SGD on convex Lipschitz objectivesSGDProofIntermediate30 min
Expected error does not give a high-probability guaranteeSGDProofAdvanced30 min
Implement SGD and locate the noise floor runSGDCodingAdvanced3 hours