Stochastic & ML optimization

Parent: optimization

When the problem is huge + non-convex + the gradient is noisy (a sum over millions of data points), exact deterministic descent dies. The shift: use noisy, cheap gradient estimates.

The ancestor

• Robbins–Monro (1951), stochastic approximation — find a root using noisy samples, with a decreasing step ηₖ (Σηₖ=∞, Σηₖ²<∞). SGD's grandfather.

SGD and its family

• SGD x ← x − η ĝ, ĝ = gradient on a minibatch (unbiased estimate);
• Momentum, AdaGrad (per-coordinate scaling), RMSprop, Adam (momentum + adaptive scaling — the default);
• Variance reduction: SVRG, SAG (get SGD's cheapness with GD's convergence, for convex).

Non-convex / deep-learning landscapes (why SGD works despite non-convexity)

• High-dim loss surfaces are dominated by saddle points, not bad local minima; noise helps escape saddles;
• Implicit regularization: SGD prefers flat minima (better generalization);
• Over-parameterization → many global minima, easy to reach.
• So "non-convex is hard" (classical) is empirically softened for deep nets — but there's no general guarantee; it's structure + luck, not a theorem.

The theme

From exact, deterministic, convex (solvable) → noisy, stochastic, non-convex (works in practice, weak theory). This is the era where "an optimizer converges" stops being guaranteed and starts being engineered/tuned — the same move our unsound-inner-optimizer harness makes (stages-gates-as-hard-optimization).