--- date: '2024-11-11' description: gradient descent but with smoothness properties (differentiable or sub-differentiable) id: Stochastic gradient descent modified: 2026-06-05 15:08:40 GMT-04:00 permalinks: - /SGD tags: - sfwr4ml3 - ml title: Stochastic gradient descent created: '2024-11-11' published: '2024-11-11' pageLayout: default slug: thoughts/university/twenty-four-twenty-five/sfwr-4ml3/Stochastic-gradient-descent permalink: https://aarnphm.xyz/thoughts/university/twenty-four-twenty-five/sfwr-4ml3/Stochastic-gradient-descent.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- See also [[thoughts/university/twenty-three-twenty-four/compsci-4x03/A4|that numerical assignment on ODEs and GD]], [[thoughts/PyTorch#SGD|SGD implementation in PyTorch]]
"\\begin{algorithm}\n\\caption{Stochastic Gradient Descent (SGD) update}\n\\begin{algorithmic}\n\\Require Learning rate schedule $\\{\\epsilon_1, \\epsilon_2, \\dots\\}$\n\\Require Initial parameter $\\theta$\n\\State $k \\gets 1$\n\\While{stopping criterion not met}\n \\State Sample a minibatch of $m$ examples from the training set $\\{x^{(1)}, \\dots, x^{(m)}\\}$ with corresponding targets $y^{(i)}$.\n \\State Compute gradient estimate: $\\hat{g} \\gets \\frac{1}{m} \\nabla_{\\theta} \\sum_{i} L\\bigl(f(x^{(i)};\\theta), y^{(i)}\\bigr)$\n \\State Apply update: $\\theta \\gets \\theta - \\epsilon_k \\hat{g}$\n \\State $k \\gets k + 1$\n\\EndWhile\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 1 Stochastic Gradient Descent (SGD) update

Require: Learning rate schedule {ϵ1,ϵ2,… }\{\epsilon_1, \epsilon_2, \dots\}

Require: Initial parameter θ\theta

1:k←1k \gets 1

2:while stopping criterion not met do

3:Sample a minibatch of mm examples from the training set {x(1),…,x(m)}\{x^{(1)}, \dots, x^{(m)}\} with corresponding targets y(i)y^{(i)}.

4:Compute gradient estimate: g^←1m∇θ∑iL(f(x(i);θ),y(i))\hat{g} \gets \frac{1}{m} \nabla_{\theta} \sum_{i} L\bigl(f(x^{(i)};\theta), y^{(i)}\bigr)

5:Apply update: θ←θ−ϵkg^\theta \gets \theta - \epsilon_k \hat{g}

6:k←k+1k \gets k + 1

7:end while

Intuition: you can think of it as online [[thoughts/gradient descent]], where the true gradient $Q(w)$ is approximated by a gradient at a single sample[^step-size]: $$ w \coloneqq w - \upeta \nabla Q_i(w) $$ [^step-size]: $\upeta$ is often considered as step-size during a linear-regression training run.