How Learning Differs from Pure Optimization · Empirical Risk · Surrogate Loss

§8.1 Learning is not pure optimization

Of all the optimization problems in deep learning, training a neural network is the hardest — routinely days to months on hundreds of machines. But it is also a peculiar kind of optimization, and the differences matter. In pure optimization, minimizing $J$ is the goal in itself. In machine learning we minimize $J$ only indirectly: what we truly care about is a performance measure $P$ (say classification accuracy) defined on the test set and often intractable. We reduce a different, tractable cost $J(\theta)$ and hope $P$ improves. Three consequences flow from this, covered below.

§8.1.1 Empirical risk minimization

The quantity we actually want to minimize is the risk — the expected loss over the true data-generating distribution. We cannot compute it (we do not know $p_\text{data}$ ), so we substitute the training-set average:

Term by term

J^*(\theta) = \mathbb{E}_{(x,y)\sim p_\text{data}} L(f(x;\theta),y) \;\;\approx\;\; J(\theta) = \frac{1}{m}\sum_{i=1}^{m} L\big(f(x^{(i)};\theta), y^{(i)}\big)

$J^*(\theta)$	the RISK: expected loss over the real distribution p_data — the thing we actually want minimized, but p_data is unknown	true goal
$\frac{1}{m}\sum_i L$	the EMPIRICAL risk: the average loss on the finite training set — our computable stand-in	what we minimize
$\approx$	empirical risk minimization hopes that lowering the training average also lowers the true risk — but it overfits (high-capacity models just memorize), and losses like 0-1 have no useful gradient	the leap of faith

The empirical risk is a finite-sample stand-in for an expectation over the whole distribution — think of it as summing over the spikes of the empirical distribution instead of integrating the smooth true density:

§8.1.2 Surrogate loss functions and early stopping

The loss we care about is often impossible to optimize directly. Minimizing the expected 0-1 loss (classification error) is intractable — its gradient is zero or undefined everywhere. So we optimize a surrogate loss : a proxy with better properties. The negative log-likelihood of the correct class is the usual surrogate for 0-1 loss — it is a smooth upper bound with a real gradient. Compare the surrogates as a function of the margin $m = y\,f(x)$ (positive = correct, and more positive = more confident):

Classification losses vs the margin m = y·f(x): the 0-1 loss (the real target) is a step with no gradient; the NLL/logistic and hinge surrogates are smooth upper bounds that keep a gradient even when correct

0-1 loss (target)= 0.000logistic / NLL= 0.684hinge= 0.500

margin m = y·f(x)0.50

A surrogate can teach you more than the real loss

Surprisingly, the test 0-1 loss often keeps decreasing long after the training 0-1 loss has already hit zero — when training on the log-likelihood surrogate. Even once every training example is correctly classified, the NLL keeps pushing the classes further apart, producing a more confident, robust classifier and extracting more information from the data than simply minimizing 0-1 error would. The surrogate’s smooth slope (visible above even at large positive margin) is exactly what enables this.

Training halts differently, too

The third difference: a training algorithm usually does not halt at a local minimum. It minimizes the surrogate but stops on an early-stopping criterion measured on the true loss (e.g. 0-1 error on a validation set), designed to quit when overfitting begins. Training often halts while the surrogate still has large derivatives — the opposite of pure optimization, which is considered converged only when the gradient becomes tiny.

Next: how the objective decomposes over examples (batch vs minibatch) and the first big obstacle, ill-conditioning — batch/minibatch & ill-conditioning.

Check yourself — learning vs optimization, empirical risk, surrogate loss

1.In what sense does machine learning optimize 'indirectly'?

2.What is the difference between the risk J*(θ) and the empirical risk J(θ)?

3.Why does deep learning rarely use empirical risk minimization directly?

4.In the surrogate-loss plot, at a large POSITIVE margin (a confidently-correct example), how do the 0-1 loss and the logistic/NLL surrogate differ?

5.How does a training algorithm's stopping criterion differ from pure optimization's?

5 questions