Gradient Descent

Gradient descent minimizes a loss by iterating down the negative gradient: $w_{t+1} = w_t - \eta\nabla L(w_t)$. For an $L$-smooth ($\Vert\nabla L(w) - \nabla L(w')\Vert \le L\Vert w - w'\Vert$) and $\mu$-strongly convex loss with $\eta \le 2/L$ it converges, and with a fixed step size the error decays linearly as $\Vert w_t - w^*\Vert \le (1 - 1/\kappa)^t\Vert w_0 - w^*\Vert$, where $\kappa = \lambda_{\max}/\lambda_{\min}$ is the Hessian condition number. Larger $\kappa$ means flatter elliptical contours and slower zig-zag progress (roughly $\kappa$ iterations to make one step of progress along the long axis).

the workhorse for training nearly all ML/DL models; interviews compare batch GD, stochastic GD (SGD) and mini-batch. SGD estimates the gradient from one random sample, $g_t = \nabla L_{i_t}(w_t)$, which is an unbiased estimator of the full gradient since $\mathbb{E}[g_t] = \frac{1}{n}\sum_{i=1}^{n}\nabla L_i(w_t) = \nabla L(w_t)$; a mini-batch of size $B$ reduces the variance to $1/B$ of the single-sample variance (i.i.d. samples, $\mathrm{Var}[\hat g] = \mathrm{Var}[g]/B$) but leaves a noise ball: under strong convexity SGD settles in $\Vert w - w^*\Vert^2 \le \frac{\eta\sigma^2}{2\mu}$ and never hits the optimum exactly.

unlike closed-form solutions (e.g. the normal equation's $O(d^3)$ matrix inversion), GD needs only first-order information and $O(d)$ memory, scaling to millions of parameters; going from $\kappa=10$ to $\kappa=1000$ costs roughly two orders of magnitude more iterations — the fundamental motivation for momentum, adaptive (Adam) and second-order (Newton) methods.

Write the GD update $w_{t+1} = w_t - \eta\nabla L(w_t)$ and derive the step-size bound $\eta \le 2/L$ for an $L$-smooth convex loss?

How does the condition number $\kappa = \lambda_{\max}/\lambda_{\min}$ set the convergence rate $(1 - 1/\kappa)^t$? Why do ill-conditioned quadratics zig-zag?

Prove SGD's gradient is an unbiased estimate of the full gradient, $\mathbb{E}[g_t] = \nabla L(w_t)$; by what factor does mini-batching cut the variance?

Why does SGD hover around a noise ball — where does $\frac{\eta\sigma^2}{2\mu}$ come from, and how does it depend on the learning rate and batch size?

What happens with too-large or too-small learning rates? Why does momentum $v_t = \beta v_{t-1} + (1-\beta)\nabla L$ damp zig-zag oscillation?