EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.AttentionML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal and Big-O growth, each with pseudocode that highlights the line being run.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, and Boolean algebra, explained with worked examples and small interactive checkers.TheorySection · Finite-state machines, automata and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · A truth-table generator with CNF, DNF and LaTeX output, a graph-traversal visualiser for BFS, DFS and Dijkstra, and a recursion-tree visualiser.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
ML maths

Gradient descent, explained with a draggable loss curve

Gradient descent is how most machine-learning models are trained: measure how wrong the model is, work out which direction makes it less wrong, and take a small step that way. Repeat thousands of times. The size of that step, the learning rate, decides whether it converges, crawls or blows up.

Interactive: Draggable loss curve with learning-rate and step controlsUpdated

The setting

A model has parameters (weights) ww. A loss function L(w)L(w) measures how badly the model with those parameters fits the training data: the average squared error of a regression, say, or the cross-entropy of a classifier. Training means finding ww that makes L(w)L(w) as small as possible. Real models have millions or billions of parameters, so we can’t search exhaustively, but we can compute the slope.

The update rule

The derivative L′(w)L'(w) is the slope of the loss at ww. If it is positive, the loss increases to the right, so we should move left; if negative, move right. In both cases we step against the slope:

wt+1=wt−η L′(wt).w_{t+1} = w_t - \eta \, L'(w_t).

The constant η>0\eta > 0 (eta) is the learning rate. With many parameters the derivative becomes the gradient ∇L(w)\nabla L(w), the vector of partial derivatives, which points in the direction of steepest increase, and the rule is the same: wt+1=wt−η∇L(wt)w_{t+1} = w_t - \eta \nabla L(w_t). Near the minimum the slope shrinks, so the steps shrink automatically, even though η\eta is fixed.

Worked example: L(w)=(w−3)2L(w) = (w - 3)^2 from w0=0w_0 = 0 with η=0.1\eta = 0.1

The derivative is L′(w)=2(w−3)L'(w) = 2(w - 3), and the minimum is at w=3w = 3. Each step computes the slope, then moves.

twₜL(wₜ)L′(wₜ)Update
00.00009.0000−6.00000.0000 − 0.1 × (−6.0000) = 0.6000
10.60005.7600−4.80000.6000 − 0.1 × (−4.8000) = 1.0800
21.08003.6864−3.84001.0800 − 0.1 × (−3.8400) = 1.4640
31.46402.3593−3.07201.4640 − 0.1 × (−3.0720) = 1.7712
41.77121.5099−2.45761.7712 − 0.1 × (−2.4576) = 2.0170

Every step closes 20% of the remaining gap to 3. In fact wt+1−3=(wt−3)−0.2(wt−3)=0.8 (wt−3)w_{t+1} - 3 = (w_t - 3) - 0.2(w_t - 3) = 0.8\,(w_t - 3), so wt=3−3⋅0.8 tw_t = 3 - 3 \cdot 0.8^{\,t}: after 20 steps ww is within 0.04 of the minimum.

Try it

Drag the orange starting point anywhere on the curve, set the learning rate, and step through. The pink line is the tangent whose slope is being used. On the bowl, try the four learning-rate buttons; on the “two valleys” curve, notice that where you start decides which valley you end up in.

Gradient descent on a loss curveDrag the orange dot to choose where to start. Change η and watch the path.

Pseudocode

  1. w ← w₀
  2. for t = 1, 2, …:
  3. g ← L′(w) (the slope at w)
  4. w ← w − η · g (step downhill)
  5. stop when |g| is tiny, or w blows up

Now

Recent iterations

twL(w)L′(w)

When it converges and when it diverges

The worked example generalises. For L(w)=(w−3)2L(w) = (w - 3)^2 and any learning rate,

wt+1−3=(1−2η)(wt−3)⟹wt−3=(1−2η)t (w0−3).w_{t+1} - 3 = (1 - 2\eta)(w_t - 3) \quad\Longrightarrow\quad w_t - 3 = (1 - 2\eta)^{t}\,(w_0 - 3).

So everything depends on the factor 1−2η1 - 2\eta:

  • 0<η≤0.50 < \eta \le 0.5: the factor is in [0,1)[0, 1), and ww slides steadily towards 3 from one side. At exactly η=0.5\eta = 0.5 it lands on 3 in one step.
  • 0.5<η<10.5 < \eta < 1: the factor is negative but smaller than 1 in size, so ww overshoots, landing on alternate sides of 3, but still converges.
  • η=1\eta = 1: the factor is −1-1, and ww bounces between 0 and 6 forever.
  • η>1\eta > 1: each overshoot is bigger than the last, and ww diverges.

For a general smooth loss the same picture holds near a minimum, with the curvature L′′(w)L''(w) in place of 2: steps are stable when η<2/L′′\eta < 2 / L''. A sharply curved valley needs a small learning rate; a flat one tolerates a large one. That is why the shallow bowl preset needs η\eta in the tens before it misbehaves.

Diagnosing the learning rate If the training loss goes up or turns into NaN, the learning rate is almost certainly too high. If it falls but painfully slowly, it is probably too low. In practice people try values spaced by factors of about 3 or 10 (0.1, 0.03, 0.01, …) and keep the largest that trains stably.

Local minima and saddle points

Gradient descent only ever sees the local slope, so on a non-convex loss it finds a minimum, not necessarily the lowest one. On the two-valleys curve, starting on the right with a small learning rate gets stuck in the shallower right-hand valley, while starting on the left finds the deeper one. With a larger step the run can jump between valleys, which hints at why noisy updates sometimes help. In very high dimensions, poor local minima turn out to matter less than saddle points and flat regions, where the gradient is small in every direction and progress stalls.

What practitioners actually run

  • Stochastic and mini-batch gradient descent. Computing the exact gradient over a whole dataset is expensive, so each step estimates it from a small random batch of examples. The estimate is noisy but cheap, and many cheap noisy steps beat a few exact ones.
  • Momentum. Keep a running average of recent gradients and step along it. Oscillations across a narrow valley cancel out, while consistent movement along the valley builds up speed.
  • Adaptive methods. Adam scales each parameter’s step by running estimates of the gradient’s first and second moments, so parameters with small, consistent gradients still move. It is the default optimiser for training many neural networks.
  • Learning-rate schedules. Start with a short warm-up, then decay the rate over training, so early steps explore and late steps settle.

References

  1. S. Ruder, “An overview of gradient descent optimization algorithms”, 2016. arXiv:1609.04747
  2. D. P. Kingma and J. Ba, “Adam: a method for stochastic optimization”, ICLR 2015. arXiv:1412.6980
  3. I. Goodfellow, Y. Bengio and A. Courville, Deep Learning, MIT Press, 2016. Chapters 4 and 8.
  4. 3Blue1Brown, Neural networks, a visual series whose second chapter covers gradient descent.