# A Thousand Starts, Three Answers

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

Everything so far worked because the loss was a bowl: one minimum, and every
road leads to it. Most surfaces are not bowls. Here is one that is not — a single
parameter `w`, and a slope written out by hand, the way every gradient in
this module has been:

```js
f'(w) = w⁵ − 5w³ + 4w
      = w · (w² − 1) · (w² − 4)
```

Five roots: `−2, −1, 0, 1, 2`. Three are valleys (`−2`,
`0`, `+2`) and two are ridges (`±1`). Gradient descent
can see none of this. It reads the slope under its feet and steps, so
*where it ends up is decided entirely by where it began* — and the borders
between the three answers sit exactly at `w = ±1`.

Which is a question with 1,024 answers and 1,024 threads to answer it: one start
each, 200 steps each, one launch. The step size is fixed at `0.02`, well
under the `2/24 ≈ 0.083` the curvature at `w = ±2` allows. Watch
what comes back: `starts[300] = −1.0352` finishes at `−2` and
`starts[320] = −0.9375` finishes at `0` — two runs a tenth of a
unit apart, ending two whole units apart.

## Figures

- **the answer you get is the valley you started in**

## Goal

**Goal:** give each thread its own starting point, step it 200 times
against the slope, and return where it stopped — `308` threads should land
near `−2`, `409` near `0` and `307` near
`+2`.

## Requirements

- Each thread reads its own start: `starts[this.thread.x]`
- The slope is `w⁵ − 5w³ + 4w` — write it out with plain multiplications
- Step against it: `w = w - this.constants.rate * slope`
- Count how many threads finished in each of the three valleys and log the three counts

## Hint 1 — the slope, spelled out

No `Math.pow` needed, and no autodiff either — the derivative of
a polynomial is a polynomial:

```js
const slope = w * w * w * w * w - 5 * w * w * w + 4 * w;
```

## Hint 2 — the update is the same one

Identical to the line fit, with one parameter instead of two:
`w = w - this.constants.rate * slope;`. That is the entire algorithm; the
surface changed, not the method.

## Hint 3 — counting the basins

Every thread finishes within a rounding error of `−2`,
`0` or `+2`, so a two-way split on the returned value is
enough:

```js
if (ends[k] < -1) left++;
else if (ends[k] < 1) middle++;
else right++;
```

## Same idea elsewhere

Random-restart optimisation is a working tool, not a curiosity — basin hopping,
multi-start least squares, ensembles of annealing runs all do this, and every one of
them is embarrassingly parallel, which is why CUDA and Metal implementations launch
thousands of restarts at a time. The GPU does not make any single walk faster; it makes
a thousand of them fit in one launch.

## Starter code

```js
// f'(w) = w⁵ − 5w³ + 4w. Three valleys at −2, 0, +2;
// two ridges at ±1. 1,024 starts, one per thread.
const gpu = new GPU({ mode });

const walk = gpu.createKernel(function (starts) {
  // TODO: this thread owns ONE starting point.
  let w = starts[0];

  for (let s = 0; s < this.constants.steps; s++) {
    // TODO: the slope of the surface at w is w⁵ − 5w³ + 4w.
    const slope = 0;
    w = w - this.constants.rate * slope;
  }
  return w;
}, {
  output: [1024],
  constants: { steps: 200, rate: 0.02 },
});

const ends = await walk(starts);

let left = 0;
let middle = 0;
let right = 0;
for (let k = 0; k < ends.length; k++) {
  if (ends[k] < -1) left++;
  else if (ends[k] < 1) middle++;
  else right++;
}

console.log('landed near -2:', left, '| near 0:', middle, '| near +2:', right);
console.log('start', starts[300], '→', ends[300]);
console.log('start', starts[320], '→', ends[320]);
```

---

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

[Previous task](https://gpu.rocks/learn/gradient-descent-c94c3f22/4.md)