Learning as Optimization

In supervised learning we are given a training set of $n$ pairs

where each $x_i$ is an input (a feature vector) and each $y_i$ is the desired output (a label or numeric target). We assume these pairs are drawn independently from some fixed but unknown probability distribution $P(x, y)$. This distribution encodes the true relationship between inputs and outputs, including any inherent noise. We pick a hypothesis class $\mathcal{H}$, a family of candidate functions $f_\theta: \mathcal{X} \to \mathcal{Y}$ indexed by a parameter vector $\theta$. For linear regression, $\mathcal{H}$ is all functions of the form $f_\theta(x) = \theta^\top x$. For a neural network, $\mathcal{H}$ is all functions computable by a fixed architecture as $\theta$ ranges over its weights. The hypothesis class is a modeling choice: it determines what kinds of patterns the learner can even represent, independent of how it will search for the best one. We then need a way to say how good a particular $f_\theta$ is. A loss function $\ell(f_\theta(x), y)$ measures the cost of predicting $f_\theta(x)$ when the true answer is $y$. Small loss means a good prediction; large loss means a bad one. Common choices include squared error $\ell(\hat{y}, y) = (\hat{y}-y)^2$ for regression, and cross-entropy for classification. The loss function is where domain knowledge about the cost of being wrong enters the picture — predicting a stock price too high by $1 may matter differently than predicting it too low by$1, and the loss function is the place to encode that asymmetry. The quantity we actually want to minimize is the expected risk (also called the true or population risk):

This is the average loss the model would incur over the entire population of possible inputs, weighted by how likely they are. It is exactly what we care about — how well the model performs on new, unseen data — but it is unobservable, since we do not know $P$ and cannot average over infinitely many examples. Instead we compute the empirical risk:

the average loss over the training set we actually have. Learning is then defined as the optimization problem

This principle — minimize empirical risk as a proxy for expected risk — is called Empirical Risk Minimization, and it is the foundation on which almost all of supervised learning theory is built. The gap between $\hat{R}(\theta)$ and $R(\theta)$ is the generalization gap, and controlling it is the central concern of learning theory.

Turning "learning" into "minimize $\hat{R}(\theta)$" is only useful if we can actually solve the minimization. The standard approach is iterative numerical optimization: start from some initial parameters, repeatedly compute how the objective changes as parameters change, and step in the direction that decreases it. This is gradient descent, and essentially all model training — linear regression via normal equations aside — reduces to a variant of it. The mechanism relies on the objective being differentiable (or having a usable subgradient) in $\theta$. At each step, we compute the gradient $\nabla_\theta \hat{R}(\theta)$, a vector pointing in the direction of steepest increase of the empirical risk. Moving a small step in the opposite direction decreases the risk, at least locally, as guaranteed by the first-order Taylor expansion of $\hat{R}$ around the current point. Repeating this many times, with a suitably chosen step size (learning rate), converges toward a minimum — a global one if $\hat{R}$ is convex in $\theta$, a local (but often good enough) one otherwise. In practice, computing the exact gradient over all $n$ training points at every step is expensive when $n$ is large. Stochastic gradient descent (SGD) replaces the full gradient with an estimate computed on a small random subset (a mini-batch), trading a small amount of noise for a large reduction in per-step cost. Because the mini-batch gradient is an unbiased estimator of the full gradient (its expectation over random batches equals the true gradient), the noisy steps still make progress on average. ``` ALGORITHM: Learning as Empirical Risk Minimization via (Stochastic) Gradient Descent INPUT: D # training set {(x_1,y_1), ..., (x_n,y_n)} f_theta # hypothesis class, parameterized by theta loss # per-example loss function ell(pred, y) eta # learning rate (step size) batch_size # size of mini-batch (batch_size = n gives full-batch GD) max_iters # stopping bound INITIALIZE: theta <- theta_0 # e.g. small random values FOR t = 1 TO max_iters: B <- sample batch_size examples uniformly at random from D

# (without replacement within an epoch) grad <- 0 FOR (x_i, y_i) IN B: pred_i <- f_theta(x_i) grad <- grad + gradient_wrt_theta( loss(pred_i, y_i) ) grad <- grad / batch_size # average gradient over the batch theta <- theta - eta * grad # descent step IF stopping_criterion_met(theta, grad): # e.g. ||grad|| < epsilon, or BREAK # validation loss stops improving RETURN theta ``` Every design choice in the recipe maps onto a concept students will meet repeatedly: `f_theta` is the hypothesis class, `loss` is the objective per example, the averaged `grad` computation is exactly $\nabla_\theta \hat{R}(\theta)$, and the stopping criterion is where concerns about generalization (not just training loss) start to enter, typically via a held-out validation set.

Time complexity. Suppose each gradient evaluation on a single example costs $O(d)$ time, where $d$ is the number of parameters (this is a reasonable estimate for linear models and is roughly the cost of a forward-and-backward pass for many networks, up to architecture-dependent factors). Full-batch gradient descent costs $O(nd)$ per iteration since it touches all $n$ examples; over $T$ iterations that is $O(Tnd)$. Stochastic or mini-batch gradient descent costs $O(bd)$ per step for batch size $b$, so $O(Tbd)$ over $T$ steps — independent of $n$ per step, which is exactly why SGD scales to enormous datasets where full-batch descent is infeasible. The tradeoff is that SGD needs more iterations to reach a comparable accuracy (its per-step progress is noisier), but each iteration is cheaper, and in practice the net effect is almost always a win for large $n$.

Space complexity. Both variants require $O(d)$ space to store the parameters and gradient. Full-batch descent may also need $O(nd)$ if the whole dataset is held in memory simultaneously (mini-batch methods avoid this by streaming batches from disk).

Convergence rate (why it works, quantitatively). If $\hat{R}$ is convex and $L$-smooth (its gradient is $L$-Lipschitz), gradient descent with step size $\eta \le 1/L$ satisfies

so the optimality gap shrinks as $O(1/T)$. If $\hat{R}$ is additionally $\mu$-strongly convex, convergence is linear (geometric): the gap shrinks as $O\big((1-\mu/L)^T\big)$, i.e. exponentially fast in $T$. These rates come directly from the descent lemma (a consequence of Taylor's theorem with the Lipschitz-gradient bound) applied inductively at each step — this is the calculus reasoning that justifies "just follow the gradient" rather than merely asserting it works.

Correctness argument for the framing itself. Why should minimizing $\hat{R}(\theta)$ over the training set say anything about $R(\theta)$, the risk on unseen data? This is where the Law of Large Numbers enters: for a fixed $\theta$, $\hat{R}(\theta)$ is a sample average of i.i.d. random variables $\ell(f_\theta(x_i), y_i)$ with mean $R(\theta)$, so $\hat{R}(\theta) \to R(\theta)$ as $n \to \infty$ by the law of large numbers, and concentration inequalities (Hoeffding, for bounded losses) give explicit finite-sample bounds on $|\hat{R}(\theta) - R(\theta)|$ with high probability. The subtlety is that $\hat{\theta}$ is not fixed — it is chosen after seeing the data, specifically to make $\hat{R}(\hat\theta)$ small, which can make $\hat{R}(\hat\theta)$ an optimistic (biased-low) estimate of $R(\hat\theta)$. This is exactly the overfitting phenomenon, and bounding the resulting generalization gap uniformly over the whole hypothesis class (via tools like VC dimension or Rademacher complexity) is the subject that later builds directly on this framing.

Honest tradeoffs.

• Convexity is a luxury: linear regression with squared loss and logistic regression with cross-entropy are convex in $\theta$, guaranteeing global convergence, but neural network losses are non-convex, so gradient descent only guarantees a stationary point, not a global minimum — though in practice, for large overparameterized networks, most stationary points found in this way tend to generalize surprisingly well.
• A smaller loss on training data is not the goal; the goal is small risk on new data. Empirical risk minimization can be actively harmful if the hypothesis class is too expressive relative to $n$, since the optimizer will happily exploit noise in the training set — the motivation for regularization, which augments $\hat{R}(\theta)$ with a penalty term to discourage overly complex solutions.
• The choice of loss function is not neutral: squared error is sensitive to outliers, 0/1 loss is not differentiable (hence rarely optimized directly), and different surrogate losses lead to different optimization landscapes and different trained models even for the same underlying task.

Consider a tiny regression problem: predicting exam score $y$ from hours studied $x$, hypothesis class $f_\theta(x) = \theta x$ (a line through the origin, one parameter for simplicity), and squared loss $\ell(\hat y, y) = (\hat y - y)^2$. Training set:

Empirical risk:

Gradient:

Set to zero for the closed-form optimum (possible here since the model is linear and the loss is convex):

Now trace gradient descent starting at $\theta_0 = 0$ with learning rate $\eta = 0.05$, using the full gradient each step (full-batch, since $n=3$ is tiny):

Notice $\theta_t$ is climbing monotonically toward $\theta^* \approx 2.071$, with the step size shrinking each time because the gradient magnitude shrinks as $\theta_t$ approaches the minimizer — exactly the geometric convergence predicted for a strongly-convex quadratic objective. After a few dozen more steps $\theta_t$ would settle within numerical precision of $2.071$, and $\hat{R}(\theta_t)$ would approach its minimum value. This tiny trace illustrates the whole pipeline: the hypothesis class ($\theta x$) fixed what could be represented, the loss (squared error) fixed what "wrong" meant, and gradient descent searched $\Theta = \mathbb{R}$ for the value minimizing the empirical risk — arriving, up to numerical precision, at the same answer the closed-form normal equation gives, confirming the optimizer is behaving correctly.

The optimization view of learning did not arrive all at once; it crystallized from threads in statistics, control theory, and computer science over roughly a century.

Every major machine learning framework — from `scikit-learn`'s linear models to PyTorch and TensorFlow's neural network training loops — is built directly on this loop: define parameters, define a loss, compute gradients, step. Recommendation systems at streaming and e-commerce platforms fit collaborative-filtering models by minimizing a reconstruction loss over billions of user-item interactions using exactly the mini-batch stochastic gradient descent skeleton shown above. Large language models are trained by minimizing a cross-entropy loss (next-token prediction error) over enormous text corpora, using variants of stochastic gradient descent (Adam, and its relatives) at a scale of trillions of tokens and billions of parameters — the core loop is unchanged from the one-dimensional worked example above, only the dimensionality and the optimizer's bookkeeping have grown. Beyond pure ML, this optimization framing underlies A/B testing analysis (which model of user behavior minimizes prediction error on holdout data), computer vision pipelines (loss functions tailored to bounding-box overlap or pixel-level segmentation accuracy), and reinforcement learning (where policies are optimized to minimize expected negative reward, a direct generalization of expected risk). Anywhere a system needs to "learn" a mapping from data rather than have it hand-coded, some version of this recipe — hypothesis class, loss, empirical risk, gradient-based search — is doing the work underneath.

Ask the tutor: How does adding a regularization term change the shape of the optimization landscape and the resulting generalization guarantees?