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.

Test Your Knowledge: Practice Questions for "Gradient Descent"

Single choice pitfall questions with instant feedback and mistake tracking.