Why Training AI Isn't Exact

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.

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">{{hint}}</p>
<svg id="plot" viewBox="0 0 360 220" class="plot"></svg>
<div class="meter">
  <div>{{label_epoch}}: <b id="epoch">0</b></div>
  <div>{{label_loss}}: <b id="loss">—</b></div>
</div>
<div class="btns">
  <button id="train" type="button">{{btn_train}}</button>
  <button id="newstart" type="button">{{btn_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; }

// Code not found

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.

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.

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.

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.