--- date: '2024-12-10' description: and what is she descending from, really? id: gradient descent modified: 2026-06-05 15:08:24 GMT-04:00 tags: - ml title: gradient descent created: '2024-12-10' published: '2024-12-10' pageLayout: default slug: thoughts/gradient-descent permalink: https://aarnphm.xyz/thoughts/gradient-descent.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- Gradient descent is an iterative method for minimizing a differentiable function $f : \mathbb{R}^d \to \mathbb{R}$ by stepping against its [[thoughts/Vector calculus#gradient|gradient]]. At a parameter vector $w$, the gradient contains the partial derivatives: $$ \nabla f(w) = \begin{pmatrix} \frac{\partial f}{\partial w_1}(w) \\ \vdots \\ \frac{\partial f}{\partial w_d}(w) \end{pmatrix}. $$ ## idea Choose an initial point $w_0$ and a positive step size $\alpha$. Then, for $t = 0,1,\ldots$, $$ w_{t+1} = w_t - \alpha \nabla f(w_t). $$ Why subtract the gradient? For a small displacement $h$, the first-order approximation is $$ f(w+h) \approx f(w) + \nabla f(w)^\top h. $$ Substituting $h = -\alpha\nabla f(w)$ makes the predicted change $-\alpha\lVert\nabla f(w)\rVert_2^2$. A nonzero gradient therefore gives a direction of decrease. The approximation is local, so the step size still matters.[^smoothness] > \[!math\] 1. intuition > > These contours show $f(x,y) = x^2 + xy + y^2$. The arrows are four gradient steps with $\alpha = 0.2$, starting at $w_0 = (-2,3.65)$. Here $\nabla f(x,y) = (2x+y,x+2y)$. > >

Even the quadratic $f(x) = x^2/2$ can diverge with a bad step size: $$ x_{t+1} = (1-\alpha)x_t. $$ For $x_0 \ne 0$, the iterates converge to zero when $0 < \alpha < 2$. At $\alpha = 2$ they alternate between $x_0$ and $-x_0$; above that, their magnitudes grow. Convexity alone gives no permission to take an arbitrary step. A zero gradient only identifies a stationary point. For example, gradient descent on $f(x)=\cos x$ initialized at $x_0=0$ stays at a maximum. For a differentiable [[thoughts/Convex function|convex function]], a zero gradient does certify a global minimum. Reaching such a point requires further assumptions. ## calculate the gradient Suppose the training objective is a **sum** of per-example losses plus a differentiable regularizer: $$ \begin{aligned} E(w) &= L(w) + \lambda R(w), \qquad \lambda \ge 0, \\ L(w) &= \sum_{i=1}^{n} \ell(f_w(x_i),y_i), \\ \nabla E(w) &= \sum_{i=1}^{n}\nabla_w\ell(f_w(x_i),y_i) + \lambda\nabla R(w). \end{aligned} $$ Here $f_w$ is the prediction model, and differentiation passes through it to the parameters $w$. For $R(w)=\lVert w\rVert_2^2/2$, the regularizer contributes $\lambda w$. Splitting the data into disjoint batches $S_1,\ldots,S_m$ gives an exact decomposition, provided every gradient is evaluated at the same $w$: $$ g_j(w) = \sum_{i\in S_j}\nabla_w\ell(f_w(x_i),y_i), \qquad \nabla L(w) = \sum_{j=1}^{m}g_j(w). $$ A mini-batch update uses one batch to estimate the full gradient. If $B$ is sampled uniformly from all subsets of $b$ examples, then $$ \widehat g_B(w) = \frac{n}{b}\sum_{i\in B}\nabla_w\ell(f_w(x_i),y_i) + \lambda\nabla R(w), \qquad \mathbb{E}_B[\widehat g_B(w)] = \nabla E(w). $$ The factor $n/b$ matches the summed loss above. For a mean loss, use the batch mean instead. Keep that convention explicit: changing the loss scaling while keeping $\lambda$ fixed changes the relative weight of regularization. Updating $w$ between batches also means their gradients no longer sum to the full gradient at one shared point. ![[thoughts/university/twenty-four-twenty-five/sfwr-4ml3/Stochastic gradient descent|SGD]] ## convergence A useful assumption is that the **gradient** is $\beta$-Lipschitz, with $\beta > 0$: $$ \lVert\nabla f(u)-\nabla f(v)\rVert_2 \le \beta\lVert u-v\rVert_2 \qquad\text{for all }u,v\in\mathbb{R}^d. $$ This is also called $\beta$-smoothness. It bounds the error in the local approximation and gives $$ f(w-\alpha\nabla f(w)) \le f(w)-\alpha\left(1-\frac{\alpha\beta}{2}\right)\lVert\nabla f(w)\rVert_2^2. $$ Thus $0<\alpha<2/\beta$ decreases the objective whenever the gradient is nonzero. If $f$ is also convex and has a minimizer $w^\star$, taking $\alpha=1/\beta$ gives the bound[^convex-rate] $$ f(w_t)-f(w^\star) \le \frac{2\beta\lVert w_0-w^\star\rVert_2^2}{t+4}. $$ The function values approach the global minimum. Existence matters: the convex function $f(x)=\log(1+e^x)$ has a $1/4$-Lipschitz gradient, yet its infimum zero on $\mathbb{R}$ is never attained. Lipschitz continuity of $f$ itself is a different assumption. For example, $f(x)=|x|$ is Lipschitz and convex, yet has no gradient at zero. Nonsmooth problems need an appropriate method, such as subgradient descent, with its own step-size analysis. [^smoothness]: Aaron Sidford, [Smooth Functions](https://web.stanford.edu/~sidford/courses/20fa_opt_theory/sidford_mse213_2020fa_chap_2_smoothness.pdf), sections 1–3: local descent and the smoothness bound. [^convex-rate]: Aaron Sidford, [Convex Functions](https://web.stanford.edu/~sidford/courses/20fa_opt_theory/sidford_mse213_2020fa_chap_3_convexity.pdf), theorem 16 with the strong-convexity parameter set to zero.