# How Big a Step? Ask 256 at Once

*Task 4 of 5 · [Gradient Descent](https://gpu.rocks/learn/gradient-descent-c94c3f22.md) · GPU.js Learn*

Where did `η = 0.1` come from? Nowhere. It was a guess, and guesses
are where gradient descent goes wrong: too small and you never arrive, too large and you
do not merely overshoot — you **diverge**, because the step lands you
further from the minimum than you started and the next one is longer still.

There is an exact limit. One step turns the error `e = θ − θ*` into
`(I − η·H)·e`, where `H` is the matrix of second derivatives, so
the walk shrinks the error only while `η < 2 / λ_max`. On this data
`H = 2I`, which makes `λ_max = 2` and the limit exactly
`η < 1` — and `η = 1/2` the rate that lands on the answer in a
single step. (A step size with a hard ceiling is not a quirk of optimisation. Explicit
time-stepping of a diffusion has one too, for the same eigenvalue reason.)

Believing that is optional; measuring it costs one launch. Give each of 256 threads
its own learning rate, let each run a complete 80-step descent on its own copy of
`m` and `c`, and read all 256 final losses back at once. This is
the axis flip that makes hyperparameter search a GPU problem: earlier tasks were
parallel *over data points*, and here the data is small (64 points, the identical
loss surface) while the *runs* are many — so the threads go one per run, and each
one walks its own slice of the data by itself.

## Figures

- **too short to arrive, exactly right, or thrown out of the bowl**

## Goal

**Goal:** give each thread its own learning rate and its own descent,
and return the final loss — so that rates `1/8` and `1/2` come
back at `0.5`, rate `1` sits at `25.5` forever, and
rate `3/2` is off the scale.

## Requirements

- Each thread reads exactly one rate: `rates[this.thread.x]`
- The step is scaled by that rate *and* by `this.constants.gradScale` (the 2/n)
- Return the mean squared residual after the last step, not `m` or `c`
- Log the losses at rates `1/8`, `1/2`, `1` and `3/2`

## Hint 1 — one thread, one rate

This is the same "which element is mine?" question every kernel asks, and
the answer is the same: `const rate = rates[this.thread.x];`. Leave it as
`rates[0]` and all 256 threads run the identical experiment.

## Hint 2 — the step

```js
m = m - rate * this.constants.gradScale * gm;
c = c - rate * this.constants.gradScale * gc;
```

`gradScale` is `2 / 64`, precomputed in JavaScript — two integer
constants would divide as integers in the shader and give you zero.

## Hint 3 — reading the result

The final losses tell a story in three parts: a band in the middle that
reached `0.5`, a few rates at the bottom still crawling towards it, and
everything past `η = 1` heading for infinity. The one at exactly
`η = 1` is the strangest: it neither converges nor explodes, because
`|1 − η·λ| = 1` means the error flips sign and keeps its size.

## Same idea elsewhere

Sweeping hyperparameters one per thread is the small, cheap version of what a
tuner does with whole models across a cluster — and when the per-run state fits in
registers there is no reason to leave the GPU between runs at all. The design decision
is which axis to parallelise: over data when the data is big, over runs when the runs
are many. Same kernel language, opposite layout.

## Starter code

```js
// 256 threads. 256 learning rates. One complete descent each.
// The dataset is 64 points from the same line — the same loss surface,
// L(m, c) = (m − 3)² + (c − 4)² + 0.5, at a size that fits in a loop.
const gpu = new GPU({ mode });

const sweep = gpu.createKernel(function (xs, ys, rates) {
  // TODO: this thread owns exactly ONE of the 256 learning rates.
  const rate = rates[0];

  let m = 0;
  let c = 0;
  for (let s = 0; s < this.constants.steps; s++) {
    let gm = 0;
    let gc = 0;
    for (let i = 0; i < this.constants.points; i++) {
      const r = m * xs[i] + c - ys[i];
      gm += r * xs[i];
      gc += r;
    }
    // TODO: the step is missing this thread's rate.
    m = m - this.constants.gradScale * gm;
    c = c - this.constants.gradScale * gc;
  }

  let loss = 0;
  for (let i = 0; i < this.constants.points; i++) {
    const r = m * xs[i] + c - ys[i];
    loss += r * r;
  }
  return loss * this.constants.invPoints;
}, {
  output: [256],
  constants: { points: 64, steps: 80, gradScale: 2 / 64, invPoints: 1 / 64 },
});

const finalLoss = await sweep(xs, ys, rates);

let converged = 0;
for (let k = 0; k < finalLoss.length; k++) {
  if (finalLoss[k] < 1) converged++;
}

console.log('rate 1/8 → loss', finalLoss[15]);
console.log('rate 1/2 → loss', finalLoss[63]);
console.log('rate 1   → loss', finalLoss[127]);
console.log('rate 3/2 → loss', finalLoss[191]);
console.log('rates that got under loss 1:', converged, 'of 256');
```

---

Interactive version: https://gpu.rocks/learn/gradient-descent-c94c3f22/4

[Previous task](https://gpu.rocks/learn/gradient-descent-c94c3f22/3.md) · [Next task](https://gpu.rocks/learn/gradient-descent-c94c3f22/5.md)