Introduction

A neural network is a big bundle of numbers called weights. Show it examples — images, sentences, sounds — and "training" means nudging those weights until its predictions match the answers. Concretely, you define a loss (how wrong the network is) and search for the weights that make it smallest.

That search is optimization, and the universal tool is gradient descent: compute which way each weight should move to lower the loss (via backpropagation), take a small step, repeat millions of times. It's astonishingly effective — it's how every modern AI is built.

But here's the unsettling truth: finding the globally best weights is NP-hard, even for tiny networks. The loss landscape is wildly non-convex, full of valleys. So we don't find the optimum — we find a good-enough one. Modern AI is built on settling, gracefully, for local optima.

Train It

Try it. A tiny neural network starts with random weights — its prediction (the curve) is nonsense. Hit Train and watch gradient descent nudge the weights: the curve bends to fit the dots, and the loss drops step by step.

<p class="hint">A tiny neural net (5 hidden units) starts with random weights. Hit <b>Train</b>
and watch gradient descent bend the <span class="b">curve</span> to fit the
<span class="r">data</span> as the loss drops.</p>
<svg id="plot" viewBox="0 0 360 220" class="plot"></svg>
<div class="meter">
  <div>Epoch: <b id="epoch">0</b></div>
  <div>Loss: <b id="loss">—</b></div>
</div>
<div class="btns">
  <button id="train" type="button">Train</button>
  <button id="newstart" type="button">New start</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .b { color: #457b9d; font-weight: 700; } .hint .r { color: #c0392b; font-weight: 700; }
.plot { width: 100%; max-width: 480px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.pred { fill: none; stroke: #457b9d; stroke-width: 2.5; }
.pt { fill: #c0392b; }
.axis { stroke: #d2dae1; stroke-width: 1; }
.meter { display: flex; gap: 1.5rem; align-items: center; margin: .8rem 0 .6rem; font-size: 1.05rem; }
.meter b { color: #1d3557; font-family: ui-monospace, monospace; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1.1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .5; cursor: default; }

// A tiny 1-hidden-layer neural net trained by gradient descent + backprop.
// Globally optimal weights are NP-hard; this just finds a good local optimum,
// and a fresh random start converges to a different (also good) solution.
const H = 5;
// toy data: y = target(x) on x in [-1,1]
const target = x => 0.6 * Math.sin(3 * x) + 0.25 * x;
const DATA = [];
for (let i = 0; i < 11; i++) { const x = -1 + 2 * i / 10; DATA.push([x, target(x)]); }

let w, b, v, c; // hidden weights/bias, output weights/bias
function init() {
  const rnd = () => (Math.random() * 2 - 1);
  w = Array.from({ length: H }, () => rnd() * 2);
  b = Array.from({ length: H }, () => rnd());
  v = Array.from({ length: H }, () => rnd());
  c = rnd();
}
function forward(x) { let o = c; const hs = []; for (let i = 0; i < H; i++) { const hi = Math.tanh(w[i] * x + b[i]); hs.push(hi); o += v[i] * hi; } return { o, hs }; }
function loss() { let s = 0; for (const [x, y] of DATA) { const { o } = forward(x); s += (o - y) ** 2; } return s / DATA.length; }

function step(lr) {
  const gw = new Array(H).fill(0), gb = new Array(H).fill(0), gv = new Array(H).fill(0); let gc = 0;
  for (const [x, y] of DATA) {
    const { o, hs } = forward(x);
    const dO = 2 * (o - y) / DATA.length;
    gc += dO;
    for (let i = 0; i < H; i++) {
      gv[i] += dO * hs[i];
      const dz = dO * v[i] * (1 - hs[i] * hs[i]);
      gw[i] += dz * x; gb[i] += dz;
    }
  }
  for (let i = 0; i < H; i++) { w[i] -= lr * gw[i]; b[i] -= lr * gb[i]; v[i] -= lr * gv[i]; }
  c -= lr * gc;
}

const sx = x => 20 + (x + 1) / 2 * 320;
const sy = y => 110 - y * 80;

function render(epoch) {
  let s = '<line class="axis" x1="20" y1="110" x2="340" y2="110"/>';
  let d = '';
  for (let i = 0; i <= 100; i++) { const x = -1 + 2 * i / 100; const { o } = forward(x); d += (i ? 'L' : 'M') + sx(x).toFixed(1) + ' ' + Math.max(5, Math.min(215, sy(o))).toFixed(1) + ' '; }
  s += '<path class="pred" d="' + d + '"/>';
  DATA.forEach(([x, y]) => { s += '<circle class="pt" cx="' + sx(x) + '" cy="' + sy(y) + '" r="4"/>'; });
  document.getElementById('plot').innerHTML = s;
  document.getElementById('epoch').textContent = epoch;
  document.getElementById('loss').textContent = loss().toFixed(4);
}

let timer = null, epoch = 0;
function train() {
  if (timer) return;
  document.getElementById('train').disabled = true;
  timer = setInterval(() => {
    for (let k = 0; k < 6; k++) { step(0.15); epoch++; }
    render(epoch);
    if (epoch >= 1500 || loss() < 0.002) { clearInterval(timer); timer = null; document.getElementById('train').disabled = false; }
  }, 30);
}
function reset() { if (timer) { clearInterval(timer); timer = null; } document.getElementById('train').disabled = false; init(); epoch = 0; render(0); }

document.getElementById('train').addEventListener('click', train);
document.getElementById('newstart').addEventListener('click', reset);
init(); render(0);
Result
Console

Then hit New start to re-randomize and train again. It fits the data well once more — but the curve gets there by a different path and settles into a different set of weights. There's no single "correct" answer it homes in on; there are many good-enough solutions, exactly as non-convexity predicts.

The Hard Part

Training sits squarely in hard-problem territory — with a twist:

  • The loss is non-convex. A network's loss surface has countless valleys, so gradient descent lands in a minimum, not necessarily the deepest.
  • The global optimum is NP-hard. Even for very small networks, finding the weights that achieve the lowest possible loss is provably NP-hard. There's no efficient algorithm for the true optimum.
  • Yet SGD works astonishingly well. Stochastic gradient descent — taking noisy steps on small batches — reliably finds weights that generalize beautifully, far better than the worst case suggests.
  • Why? Active research. Overparameterization (more weights than data points) seems to smooth the landscape so that most local minima are nearly as good as the global one, and bad traps are rare. The full theory is still being written.
  • The practical art is in the optimizers (Adam, momentum), initialization, learning-rate schedules and regularization — engineering that turns an NP-hard problem into the engine of the AI era.

So neural-network training is the ultimate case study of this whole site: NP-hard in theory, spectacularly successful in practice.

Where It Matters

This single optimization underlies the entire AI revolution:

  • Language models: the chatbots and assistants trained on vast text.
  • Computer vision: image recognition, medical imaging, self-driving perception.
  • Speech: transcription, voice assistants, translation.
  • Recommendation and ranking: the feeds and search results you see daily.
  • Science: protein structure, drug discovery, climate and physics models.

Every one of them is, under the hood, gradient descent grinding down a non-convex loss — settling for excellent local optima because the global one is out of reach.

Conclusion

Training a neural network is the hard-problem story carried to its most consequential conclusion. The exact best weights are NP-hard to find, the landscape is a maze of valleys, and there's no guarantee gradient descent reaches the bottom. By the strict standards of optimization, training "fails" every time — it never proves it found the best answer.

And yet this graceful failure runs the modern world. The lesson of this whole site lands hardest here: NP-hardness is not a dead end. Sometimes you stop chasing the perfect optimum, take a good-enough one, and discover it's more than enough to recognize a face, translate a language, or hold a conversation.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/nn-training/Content licensed under CC BY-NC 4.0.