Introduction

Training a large neural network is expensive. You start with tens of millions of randomly initialized weights, run the data through thousands of times, and gradually push the errors down. When you're done, the network works — but it is also enormous, slow, and costly to run.

A natural instinct is to prune it: snip away the weights that seem unimportant, leaving a leaner model. Pruning after training has worked for decades. But in 2019, Jonathan Frankle and Michael Carlin noticed something striking — the sparse subnetwork that survives pruning is not just a compressed model. If you reset its surviving weights back to their initial values and retrain only that skeleton, it converges just as well as the full network, or better, and in fewer steps.

They called this the Lottery Ticket Hypothesis: every large, randomly initialized network contains a small winning ticket — a subnetwork whose initial weights happened to be just right for learning. The full network wins the lottery because it buys so many tickets. Most lose. One wins.

The hypothesis is empirically well-supported — it holds across image classifiers, language models, and reinforcement learning agents — but the theoretical question of why it is true, and how to find the winning ticket efficiently without training the full network first, remains open.

Prune and Retrain

Below is a tiny network learning to classify two groups of points. It has more weights than it needs. Follow the lottery ticket recipe:

  1. Train the full network until it converges.
  2. Prune the smallest weights (by absolute value) — strike out the losers.
  3. Reset the survivors to their original random values and retrain from that sparse start.
<p class="hint">A tiny 2-layer network learns to separate two point clouds. Train it, then prune the smallest weights and retrain only the survivors — reset to their lucky initial values.</p>
<canvas id="canvas" width="260" height="200"></canvas>
<div class="controls">
  <label>Prune ratio: <span id="prune-val">50%</span>
    <input type="range" id="prune-slider" min="0" max="90" step="10" value="50">
  </label>
</div>
<div class="btns">
  <button id="btn-train" type="button">1. Train full network</button>
  <button id="btn-prune" type="button" disabled>2. Prune & retrain ticket</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status"></div>
<div id="stats" class="stats"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block; background: #f7f9fb; }
.controls { margin: .5rem 0; font-size: .9rem; }
.controls label { display: flex; align-items: center; gap: .5rem; }
input[type=range] { flex: 1; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.run { color: #1d3557; }
.stats { font-size: .82rem; color: #555; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lottery Ticket Hypothesis demo
// Network: 2 inputs -> 6 hidden (ReLU) -> 1 output (sigmoid)
// Dataset: two linearly separable point clouds
// After training, prune smallest weights by magnitude, reset survivors to their initial values, retrain — the winning ticket recovers accuracy.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// --- Dataset ---
function makeData(n, seed) {
  let s = seed;
  function rand() { s = (s * 1664525 + 1013904223) & 0xffffffff; return (s >>> 0) / 4294967296; }
  const pts = [];
  for (let i = 0; i < n; i++) {
    const label = i < n / 2 ? 0 : 1;
    const cx = label === 0 ? -1.2 : 1.2;
    const cy = label === 0 ? -0.8 : 0.8;
    pts.push({ x: cx + (rand() - 0.5) * 1.4, y: cy + (rand() - 0.5) * 1.4, label });
  }
  return pts;
}
const DATA = makeData(60, 42);

// --- Network (2->6->1) ---
const N_IN = 2, N_H = 6, N_OUT = 1;

function randn(seed) {
  // Box-Muller via LCG
  let s = seed;
  return function() {
    s = (s * 6364136223846793005n + 1442695040888963407n) & 0xffffffffffffffffn;
    const u1 = Number((s >> 33n) & 0xfffffffn) / 268435455;
    s = (s * 6364136223846793005n + 1442695040888963407n) & 0xffffffffffffffffn;
    const u2 = Number((s >> 33n) & 0xfffffffn) / 268435455;
    return Math.sqrt(-2 * Math.log(u1 + 1e-9)) * Math.cos(2 * Math.PI * u2);
  };
}

function initWeights(seedVal) {
  const rng = randn(BigInt(seedVal));
  const scale1 = Math.sqrt(2 / N_IN);
  const scale2 = Math.sqrt(2 / N_H);
  // W1: N_H x N_IN, b1: N_H, W2: N_OUT x N_H, b2: N_OUT
  const W1 = Array.from({length: N_H}, () => Array.from({length: N_IN}, () => rng() * scale1));
  const b1 = Array(N_H).fill(0);
  const W2 = Array.from({length: N_OUT}, () => Array.from({length: N_H}, () => rng() * scale2));
  const b2 = Array(N_OUT).fill(0);
  return { W1, b1, W2, b2 };
}

function cloneWeights(w) {
  return {
    W1: w.W1.map(r => [...r]),
    b1: [...w.b1],
    W2: w.W2.map(r => [...r]),
    b2: [...w.b2]
  };
}

function sigmoid(x) { return 1 / (1 + Math.exp(-x)); }
function relu(x) { return x > 0 ? x : 0; }

function forward(net, x0, x1) {
  const h = Array(N_H);
  for (let j = 0; j < N_H; j++)
    h[j] = relu(net.W1[j][0] * x0 + net.W1[j][1] * x1 + net.b1[j]);
  let out = net.b2[0];
  for (let j = 0; j < N_H; j++) out += net.W2[0][j] * h[j];
  return sigmoid(out);
}

function accuracy(net) {
  let correct = 0;
  for (const p of DATA) {
    const pred = forward(net, p.x, p.y) > 0.5 ? 1 : 0;
    if (pred === p.label) correct++;
  }
  return correct / DATA.length;
}

// SGD with backprop
function trainStep(net, lr, mask) {
  // mask: same shape as weights, 0=frozen, 1=active
  const batchSize = DATA.length;
  const dW1 = net.W1.map(r => r.map(() => 0));
  const db1 = Array(N_H).fill(0);
  const dW2 = net.W2.map(r => r.map(() => 0));
  const db2 = Array(N_OUT).fill(0);

  let loss = 0;
  for (const p of DATA) {
    const x0 = p.x, x1 = p.y, y = p.label;
    // forward
    const pre = Array(N_H);
    const h = Array(N_H);
    for (let j = 0; j < N_H; j++) {
      pre[j] = net.W1[j][0] * x0 + net.W1[j][1] * x1 + net.b1[j];
      h[j] = relu(pre[j]);
    }
    let outPre = net.b2[0];
    for (let j = 0; j < N_H; j++) outPre += net.W2[0][j] * h[j];
    const out = sigmoid(outPre);
    loss += -(y * Math.log(out + 1e-9) + (1 - y) * Math.log(1 - out + 1e-9));
    // backward
    const dOut = out - y;
    db2[0] += dOut;
    for (let j = 0; j < N_H; j++) {
      dW2[0][j] += dOut * h[j];
      const dh = dOut * net.W2[0][j];
      const dpre = dh * (pre[j] > 0 ? 1 : 0);
      db1[j] += dpre;
      dW1[j][0] += dpre * x0;
      dW1[j][1] += dpre * x1;
    }
  }
  // apply gradients (with mask)
  for (let j = 0; j < N_H; j++) {
    for (let k = 0; k < N_IN; k++)
      net.W1[j][k] -= lr / batchSize * dW1[j][k] * (mask ? mask.W1[j][k] : 1);
    net.b1[j] -= lr / batchSize * db1[j] * (mask ? mask.b1[j] : 1);
  }
  for (let j = 0; j < N_H; j++)
    net.W2[0][j] -= lr / batchSize * dW2[0][j] * (mask ? mask.W2[0][j] : 1);
  net.b2[0] -= lr / batchSize * db2[0];
  return loss / batchSize;
}

// --- State ---
let initNet = null;       // original random weights
let trainedNet = null;    // fully trained network
let ticketNet = null;     // retrained winning ticket
let pruneMask = null;     // 1=keep, 0=pruned

function getState() {
  if (ticketNet) return 'ticket';
  if (trainedNet) return 'trained';
  return 'init';
}

// --- Pruning ---
function buildMask(net, ratio) {
  // Collect all (weight, ref) pairs (biases excluded from pruning for clarity)
  const entries = [];
  for (let j = 0; j < N_H; j++)
    for (let k = 0; k < N_IN; k++)
      entries.push({ abs: Math.abs(net.W1[j][k]), type: 'W1', j, k });
  for (let j = 0; j < N_H; j++)
    entries.push({ abs: Math.abs(net.W2[0][j]), type: 'W2', j });

  entries.sort((a, b) => a.abs - b.abs);
  const nPrune = Math.floor(entries.length * ratio);
  const pruned = new Set(entries.slice(0, nPrune).map((_, i) => i));

  const mask = {
    W1: net.W1.map(r => r.map(() => 1)),
    b1: Array(N_H).fill(1),
    W2: net.W2.map(r => r.map(() => 1)),
    b2: Array(N_OUT).fill(1)
  };
  entries.slice(0, nPrune).forEach(e => {
    if (e.type === 'W1') mask.W1[e.j][e.k] = 0;
    else mask.W2[0][e.j] = 0;
  });
  return { mask, nPrune, total: entries.length };
}

// --- Drawing ---
function toCanvas(v, lo, hi, dim) {
  return ((v - lo) / (hi - lo)) * dim;
}
const XLO = -3, XHI = 3, YLO = -2.5, YHI = 2.5;

function drawBackground(net) {
  const imgData = ctx.createImageData(W, H);
  for (let px = 0; px < W; px++) {
    for (let py = 0; py < H; py++) {
      const wx = XLO + (px / W) * (XHI - XLO);
      const wy = YHI - (py / H) * (YHI - YLO);
      const p = forward(net, wx, wy);
      const i = (py * W + px) * 4;
      if (p > 0.5) {
        imgData.data[i] = 220; imgData.data[i+1] = 235; imgData.data[i+2] = 255;
      } else {
        imgData.data[i] = 255; imgData.data[i+1] = 230; imgData.data[i+2] = 220;
      }
      imgData.data[i+3] = 255;
    }
  }
  ctx.putImageData(imgData, 0, 0);
}

function drawPoints(net) {
  for (const p of DATA) {
    const cx = toCanvas(p.x, XLO, XHI, W);
    const cy = H - toCanvas(p.y, YLO, YHI, H);
    ctx.beginPath();
    ctx.arc(cx, cy, 4.5, 0, Math.PI * 2);
    ctx.fillStyle = p.label === 1 ? '#1d6fbf' : '#c92f3c';
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.2;
    ctx.fill();
    ctx.stroke();
  }
}

function render(net) {
  ctx.clearRect(0, 0, W, H);
  drawBackground(net);
  drawPoints(net);
}

// Initial dummy net
function zeroNet() {
  return {
    W1: Array.from({length: N_H}, () => Array(N_IN).fill(0)),
    b1: Array(N_H).fill(0),
    W2: Array.from({length: N_OUT}, () => Array(N_H).fill(0)),
    b2: Array(N_OUT).fill(0)
  };
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + (cls || '');
}
function setStats(msg) { document.getElementById('stats').textContent = msg; }

// --- Button handlers ---
const btnTrain = document.getElementById('btn-train');
const btnPrune = document.getElementById('btn-prune');
const btnReset = document.getElementById('btn-reset');

function doReset() {
  initNet = null; trainedNet = null; ticketNet = null; pruneMask = null;
  render(zeroNet());
  setStatus('');
  setStats('');
  btnTrain.disabled = false;
  btnPrune.disabled = true;
}

function doTrain() {
  btnTrain.disabled = true;
  btnPrune.disabled = true;
  setStatus('Training full network…', 'run');
  initNet = initWeights(7);
  const net = cloneWeights(initNet);
  const EPOCHS = 300;
  let epoch = 0;
  function step() {
    for (let i = 0; i < 20; i++) trainStep(net, 0.8, null);
    epoch += 20;
    render(net);
    if (epoch < EPOCHS) {
      requestAnimationFrame(step);
    } else {
      trainedNet = cloneWeights(net);
      const acc = (accuracy(trainedNet) * 100).toFixed(1);
      setStatus(fmt('Full network trained. Accuracy: %acc%%', { acc: acc }), 'ok');
      setStats(fmt('All %v%%N_H% weights active.', { v: N_H * N_IN, N_H: N_H }));
      btnPrune.disabled = false;
    }
  }
  requestAnimationFrame(step);
}

function doPrune() {
  if (!trainedNet) return;
  btnPrune.disabled = true;
  btnTrain.disabled = true;
  const ratio = parseInt(document.getElementById('prune-slider').value) / 100;
  const { mask, nPrune, total } = buildMask(trainedNet, ratio);
  pruneMask = mask;

  // Build ticket: initial weights but zeroed where pruned
  const ticket = cloneWeights(initNet);
  for (let j = 0; j < N_H; j++)
    for (let k = 0; k < N_IN; k++)
      if (!mask.W1[j][k]) ticket.W1[j][k] = 0;
  for (let j = 0; j < N_H; j++)
    if (!mask.W2[0][j]) ticket.W2[0][j] = 0;

  setStatus(fmt('Retraining winning ticket (%v%/%total% weights)…', { v: total - nPrune, total: total }), 'run');

  const EPOCHS = 300;
  let epoch = 0;
  function step() {
    for (let i = 0; i < 20; i++) trainStep(ticket, 0.8, mask);
    epoch += 20;
    render(ticket);
    if (epoch < EPOCHS) {
      requestAnimationFrame(step);
    } else {
      ticketNet = cloneWeights(ticket);
      const accFull = (accuracy(trainedNet) * 100).toFixed(1);
      const accTicket = (accuracy(ticketNet) * 100).toFixed(1);
      const kept = total - nPrune;
      setStatus(
        fmt('Ticket accuracy: %accTicket%% vs full: %accFull%%%v%', { accTicket: accTicket, accFull: accFull, v: ' — ' + (parseFloat(accTicket) >= parseFloat(accFull) - 5 ? 'winning ticket! 🎫' : 'ticket lost this time.') }),
        parseFloat(accTicket) >= parseFloat(accFull) - 5 ? 'ok' : ''
      );
      setStats(fmt('%kept%/%total% weights kept (%round%% pruned). Size reduction: %round2%%.', { kept: kept, total: total, round: Math.round(ratio * 100), round2: Math.round((1 - kept / total) * 100) }));
      btnPrune.disabled = false;
    }
  }
  requestAnimationFrame(step);
}

btnTrain.addEventListener('click', doTrain);
btnPrune.addEventListener('click', doPrune);
btnReset.addEventListener('click', doReset);

document.getElementById('prune-slider').addEventListener('input', function() {
  document.getElementById('prune-val').textContent = this.value + '%';
});

// Initial render
doReset();
render(zeroNet());
Result
Console

Notice that the sparse subnetwork, reset to its lucky initial values, reaches accuracy close to the full network — the winning ticket was there from the beginning. Crank up the pruning ratio to strip away more weights and watch when the ticket finally stops winning.

The Real Complexity

What is the status of the Lottery Ticket Hypothesis?

  • Empirically supported. Frankle and Carlin (2019) showed winning tickets in small vision networks. Later work confirmed the pattern in ResNets, Transformers, BERT, and RL agents, though large networks often need rewinding to an early checkpoint rather than the very first initialization.
  • Theoretically murky. We have no proof that every architecture must contain a winning ticket, nor a precise formula for how sparse the ticket can be. Results from the theory of neural network training show that overparameterization helps optimization, which hints at why big networks find good solutions, but the connection to sparse subnetworks is not tight.
  • The hard algorithmic question is open. The standard recipe requires training the full network before you know which ticket won. Finding the winning subnetwork before full training — avoiding the expensive first pass entirely — is sometimes called the strong lottery ticket hypothesis and is an active research frontier. Some theoretical results show that random large networks contain subnetworks that approximate any smaller target network (the "strong" version), but exploiting this in practice without exhaustive search remains unsolved.
  • Connections to P vs NP. Pruning is related to the general problem of finding a minimal sufficient representation of a function computed by a circuit — a problem family that is known to be hard in the worst case.

The bottom line: the hypothesis is a striking empirical fact, a useful engineering tool, and a genuinely open theoretical question rolled into one.

Where It Matters

The lottery ticket idea touches nearly every part of modern machine learning:

  • Model compression for deployment: a winning ticket can be 10–100× smaller than the original network while matching its accuracy, making it practical to run on phones, microcontrollers, and edge devices where memory and power are tight.
  • Faster training: once a winning ticket is identified (even by pruning a smaller surrogate), retraining only its sparse structure can cut training time significantly.
  • Neural architecture search: rather than testing hundreds of hand-designed architectures, pruning-based methods can discover compact architectures automatically — winning tickets as architecture proposals.
  • Interpretability: the weights that survive pruning tend to encode the most critical patterns the network learned. Studying tickets helps researchers understand what a network is actually doing, a core challenge in AI safety.
  • Overparameterization theory: the hypothesis is evidence that we train large networks not because they need all their weights, but because the redundancy makes optimization easier — a key insight connecting to the theory of gradient descent and learning.

Understanding winning tickets is part of the broader question of why deep learning works at all — one of the deepest open problems in the theory of computation.

Conclusion

The Lottery Ticket Hypothesis offers a beautiful reframe of why we train enormous neural networks: we are not building a single intricate machine from scratch. We are buying a lottery ticket — millions of them, with random numbers, hoping one of them matches. Most weights are losers. A tiny, lucky subnetwork wins.

That winning ticket was set at initialization, before any data was seen. The full training run is, in a sense, just the process of discovering which ticket you already held.

What we still cannot do efficiently is identify the winning ticket without playing the full game first. That gap — between the existence of the ticket and our ability to find it cheaply — is where the theory remains open, and where the next breakthrough in efficient AI may be hiding.

For more on the interplay between overparameterization and learning, see neural network training. For the broader question of what makes problems hard to solve, see P vs NP.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lottery-ticket-hypothesis/Content licensed under CC BY-NC 4.0.