State the convergence condition on the learning rate for stochastic gradient descent on a convex objective, and give the rate for a fixed step size against a decaying one. Say what a fixed step size converges to and why.

State the convergence condition on the learning rate for stochastic gradient descent on a convex objective, and give the rate for a fixed step size against a decaying one. Say what a fixed step size converges to and why.

Approach: Compare the bias term that shrinks with the number of steps against the noise term that scales with the step size and the gradient variance.

A fixed step size eta converges only to a noise ball of radius proportional to eta*sigma^2 around the optimum, while a decaying schedule satisfying the Robbins-Monro conditions sum eta_t = infinity and sum eta_t^2 < infinity converges to the optimum itself, at rate O(1/sqrt(t)) for a general convex objective and O(1/t) for a strongly convex one. The standard bound decomposes the expected suboptimality into a term like ||b_0 - b*||^2/(2*eta*t), which needs eta large to decay quickly, and a term like eta*sigma^2/2 where sigma^2 bounds the gradient noise variance, which needs eta small. With eta fixed the first term vanishes and the second does not, so the iterates keep bouncing with a stationary variance proportional to eta. Optimising the bound over eta for a fixed horizon t gives eta proportional to 1/sqrt(t) and the O(1/sqrt(t)) rate. The first condition on the schedule ensures the steps can still travel an unbounded distance so any starting point is reachable, and the second ensures the accumulated noise is finite. In practice eta_t = eta_0/(1 + t/tau) or a step decay is used, and the visible symptom of a step size held too high is a training loss that plateaus at a level above the achievable one and oscillates rather than descends.

Follow-up: Averaging the iterates recovers a better rate at a constant step size. What is the averaging scheme and what rate does it achieve?

Key concepts: learning rate, convergence rate, noise ball, Robbins-Monro conditions.