Optimisation, Approximation and Guarantees

Part oneThe valley is not the destination

The word “solution” compresses several distinct achievements. An iterate can be close to the minimum of a sampled surrogate while remaining far from the best available decision.

Start with the simplest promise an optimiser can make. Given an objective function f, a feasible set and an information source such as exact gradients, it generates a sequence of candidate points. A convergence statement compares some property of that sequence with a reference: objective value, distance to a minimiser, gradient norm, constraint violation or regret. The reference and the property are part of the theorem. They are not interchangeable.

Suppose a classifier is trained by minimising cross-entropy. A statement of the form “the empirical cross-entropy is within 0.01 of its infimum” says nothing directly about false-negative cost, calibration under a changed population, latency, fairness constraints or the cost of an irreversible action. Those may correlate with the surrogate. Correlation is not a bound. A decision-relevant claim needs a bridge that turns surrogate excess into target excess.

Three errors that are often collapsed

Classical learning theory distinguishes at least three gaps. Approximation error asks how close the best member of the chosen model class can come to the target. Estimation error asks how far finite-sample performance is from population performance. Optimisation error asks how far the returned iterate is from the chosen empirical optimum. Bottou and Bousquet showed why finite computation makes this decomposition operational rather than merely pedagogical: on large problems, spending more compute to reduce optimisation error can be worse than processing more data or changing the model class.[4]

The decomposition is not a licence to add arbitrary numbers. Each term must share compatible risks, domains and reference points. The useful insight is causal: improving one gap changes the total only to the extent that the other gaps and the translation between them remain controlled.

Approximation is not optimisation waiting to happen

A universal approximation theorem says that a sufficiently expressive function class can represent functions to a stated accuracy under stated conditions. It is an existence claim. It does not say that finite data identify the desired function, that finite precision represents it efficiently, or that a particular algorithm reaches the needed parameters. Cybenko’s theorem for sigmoidal networks is foundational precisely because it establishes representational density, not a training recipe.[6]

The distinction matters in both directions. A poor optimiser can fail inside an adequate class. An excellent optimiser can faithfully solve the wrong approximation problem. Adding parameters may reduce the best achievable approximation error while making the optimisation landscape, statistical variance or deployment cost harder to control. Conversely, a restricted class may produce a slightly higher surrogate minimum but a more stable, auditable decision.

What is a solution indexed to?

A parameter vector is not useful in the abstract. Its status depends on an objective, a comparator, a data distribution, an action rule, a resource budget and a cost model. Change any one of these and the same vector can move from adequate to unacceptable without its training loss changing. The word “solution” should therefore be read as shorthand for a relationship, not as a property stored inside the weights.

Consider a score of 0.73 for a suspected payment. Under one policy, scores above 0.70 are blocked. Under another, they enter a review queue that can inspect only one case in fifty. The model output is identical, but the ranking near the capacity boundary, the cost of delay and the tolerance for false positives now determine value. A surrogate that preserves average log loss may fail to preserve the few ordering relations that the queue actually uses.

A useful solution is a returned state plus the decision contract under which that state will be interpreted. This contract identifies the target, action boundary, comparator and permissible uncertainty. Once it is explicit, approximation asks whether the model class can support that contract, estimation asks whether the available sample identifies it, and optimisation asks whether the training process reaches a sufficiently good member of the class.

Part twoGeometry decides what a step means

An update rule has no convergence meaning in isolation. Its behaviour emerges from the interaction among the objective’s geometry, the information returned by the oracle and the size of each step.

A quadratic small enough to hold in the head

Let the objective be f(x) = ½a x², where a is positive. The minimum is at zero. The gradient is a x. Gradient descent with step size η gives:

If ηa = 0.5, each step halves the distance. If ηa = 1, one step lands at the minimum. If ηa = 1.5, the sign flips at every step but the magnitude shrinks. If ηa = 2, the sequence bounces forever with unchanged magnitude. Above 2, it diverges. The same algorithm can be calm, oscillatory or explosive because the step is meaningful only relative to curvature.

Worked example: when a harmless scaling breaks the step

Return to the quadratic f(x) = ½ax² with a = 20. A learning rate of η = 0.04 gives the multiplier 1 − ηa = 0.2, so distance contracts fivefold at each step. Now change only the implementation of loss aggregation. Instead of averaging four identical item losses, sum them. The minimiser is unchanged, but the effective curvature becomes 80. The same nominal learning rate now gives 1 − ηa = −2.2. Magnitude grows by a factor of 2.2 and the iterates alternate across the minimum.

Nothing in the configuration label “gradient descent, learning rate 0.04” reveals the change. Dividing the learning rate by four restores ηa = 0.8 and the original multiplier. This small calculation explains failures seen in larger systems when batch losses switch between sum and mean, gradient accumulation changes normalisation, or regularisation is applied on a different scale. The theorem was not disproved. The executable objective no longer matched its curvature clause.

Step-size guarantees attach to the scaled update actually executed, not to a hyperparameter name. A run manifest should therefore record loss reduction semantics, batch and accumulation normalisation, regularisation placement and any gradient rescaling before it imports a stability interval from theory.

From one curvature to a ravine

In several dimensions, a quadratic can curve gently in one direction and sharply in another. Let μ be the smallest curvature and L the largest. Their ratio κ = L/μ is the condition number. A circle has κ near one. A narrow ravine has a large κ. A step small enough not to explode across the steep wall makes painfully slow progress along the shallow floor.

For an L-smooth, μ-strongly convex objective, gradient descent with a suitable fixed step contracts geometrically, with a worst-case rate governed by κ. Accelerated first-order methods improve the condition-number dependence under the same structural regime.[1][2] The guarantee is valuable because it tells us which terrain properties make fast progress possible. It is limited because real objectives may satisfy those properties only locally, approximately or not at all.

What changes when convexity disappears

Convexity makes every local descent direction globally meaningful. Strong convexity adds a floor that rises at least quadratically away from the minimiser. The Polyak–Łojasiewicz condition is weaker: it can yield linear convergence without convexity, but it still rules out suboptimal stationary points.[8] Remove these properties and the promise changes.

For a general smooth non-convex objective, a standard first-order certificate is not “near the global minimum”. It is “the expected squared gradient norm is small” at a selected iterate. Under common unbiased-gradient and bounded-variance assumptions, canonical stochastic methods achieve rates of order 1/√T for this stationarity measure.[7] A stationary point might be a local minimum, a saddle or a flat region. The certificate is honest, but weaker than ordinary language often suggests.

Noise adds another distinction. With a constant step, stochastic gradients can keep an iterate moving around a basin even after systematic descent has become smaller than random fluctuation. A decreasing step can shrink that noise floor, but it also reduces responsiveness. Mini-batch size, averaging and variance reduction therefore change both cost and certificate. Reporting iterations without reporting oracle calls or processed examples can make two rates appear comparable when their information budgets differ.[3]

Bounds are envelopes, not forecasts

A worst-case convergence bound says that no admissible problem in a declared class can force the algorithm outside an envelope. It need not predict the curve of a typical run. The envelope may be loose for the current data, yet indispensable for ruling out catastrophic behaviour. Conversely, a pleasing empirical curve says little about an untested corner of the class.

Oracle-complexity lower bounds add a second discipline. They show that, given only a specified kind of information, no algorithm can uniformly beat a rate beyond stated constants and dimensions. They are not pessimism. They tell us when faster progress requires new structure, a stronger oracle, a smaller problem class or a different success criterion. Computer-assisted performance estimation can tighten worst-case analyses for finite iteration counts, but it still inherits the declared class and oracle.[14]

Asymptotic notation can also hide the practical answer. Two methods may both have an O(1/T) rate while differing sharply in curvature constants, per-step cost, memory traffic and the iteration at which the bound becomes informative. A rate should therefore be read with its constants, initial distance, failure probability and unit of work. When those quantities cannot be estimated, the theorem still explains mechanism, but it does not yet price the run. The operational comparison is time or cost to reach a declared certificate, not the exponent alone.

Part threeThe optimiser can choose the answer

When many parameter settings fit the observed data, optimisation dynamics become a selection rule. Final loss may hide which solution was selected and why.

Two minima with the same score

Consider linearly separable points. Many separating lines can achieve zero training error, and logistic loss has no finite minimiser on perfectly separable data because increasing the weight norm keeps reducing the loss. Gradient descent nevertheless has a structured asymptotic bias: under restricted conditions, its direction approaches the maximum-margin separator.[12] This is not visible in the statement “training loss approaches zero”. The trajectory, parametrisation and geometry select among solutions.

Early stopping is part of the model

Stopping is often described as a budget decision after the optimiser has done its work. In many systems it is a selection mechanism. Along a trajectory, simple or high-signal directions may be fitted before weak or noisy directions. Stopping chooses a point on that path. In linear least squares, recent analysis shows that early-stopped gradient descent can correspond to a generalised ridge solution, while the benefit depends on the learning-rate schedule, spectrum, noise and existing regularisation.[13]

This yields an uncomfortable but useful conclusion: “train to convergence” is not neutral. It privileges the empirical objective over the regularising effect of the path. Early stopping can help, harm or merely duplicate explicit regularisation. Its status must be tested, not romanticised.

Adaptive methods: empirical success and theorem scope

Adam combines moving averages of gradients and squared gradients to produce coordinate-wise adaptive steps.[9] Its practical influence is undeniable. Its theoretical story also demonstrates why algorithm names are poor guarantees. Reddi et al. gave a simple convex online example in which vanilla Adam can fail to converge, then proposed AMSGrad.[10] Later analyses recovered convergence for Adam or related methods under different parameter and noise conditions, while newer variants such as ADOPT alter update ordering to obtain guarantees under another assumption set.[11]

The right conclusion is not that Adam is unsafe or that one variant is universally superior. It is that the executable algorithm is the equations plus hyperparameters, schedules, numerical details and data process, not the family name printed in a configuration file. A guarantee must match that executable object.

Compare information budgets, not epoch labels

Even when two implementations optimise the same expression, an epoch is a poor common currency. One method may take many cheap noisy steps; another may form fewer expensive estimates. A preconditioner can reduce iterations while increasing memory movement. A line search can spend several objective and gradient evaluations before accepting one update. Hyperparameter search can consume more compute than the reported training run.

Suppose procedure A makes 1,000 updates with batches of 256, while procedure B makes 4,000 updates with batches of 64. Both process 256,000 examples, but they experience different gradient noise and take different numbers of sequential decisions. If B also receives forty tuning trials while A receives four, the final loss comparison mixes update rule with search budget. Neither update count nor example count alone resolves the comparison.

An optimiser comparison is a comparison of configured information-and-compute policies. Report at least examples processed, oracle calls, wall time, peak memory, precision, tuning budget and the stopping event. Then plot the target-relevant certificate against cost. This produces a frontier rather than a ceremonial winner, and it makes clear whether a gain comes from geometry, extra information, more search or a different endpoint.

Part fourBuild a useful-solution contract

A practical assurance instrument should expose every bridge needed to move from an iterate to a decision, then refuse to produce a stronger conclusion when a bridge is missing.

The five-link composition

Let ĤFₙ be the empirical surrogate, F the population surrogate on a reference distribution, R the target loss on that distribution and H the model class. Let hₜ be the returned model. The following clauses are sufficient to build one useful form of bound.

First, the optimiser supplies an empirical certificate: ĤFₙ(hₜ) − inf_h∈H ĤFₙ(h) ≤ ε_opt. Second, a two-sided uniform estimation bound gives sup_h∈H|F(h) − ĤFₙ(h)| ≤ ε_est. Together they imply population surrogate excess no larger than ε_opt + 2ε_est. Third, a calibrated regret bridge Ψ converts surrogate excess into target excess within H. Fourth, ε_app bounds the price of restricting the target to H. Fifth, ε_shift bounds how much target regret can worsen between the reference and deployment distributions.

Bartlett, Jordan and McAuliffe developed quantitative relationships between convex surrogate risk and classification risk, showing why computationally convenient losses need statistical calibration.[5] The displayed composition extends that logic into an operational contract. It is not a universal theorem: each term is a slot that must be filled by a valid result, a conservative measurement or an explicit unknown.

The novel discipline is to treat an unknown term as a broken certificate, not as zero. If no deployment-shift bound exists, report the objective and reference-distribution results without promoting them to a deployment guarantee. If no surrogate bridge exists for the actual metric, evaluate the metric directly or redesign the surrogate.

How each bridge earns its place

The five terms require different evidence. Optimisation error comes from a theorem matched to the executed update, a computable duality gap, or a reproducible empirical stopping test. Estimation error comes from a sampling argument or held-out procedure that accounts for model and stopping selection. The surrogate bridge comes from a calibration result or decision analysis for the actual target. Approximation error requires a comparator outside the chosen class, not merely another run inside it. Shift requires a sensitivity, transport or stress argument tied to target regret rather than a generic distance between input distributions.

These pieces are not automatically independent or additive. Repeatedly selecting checkpoints on one validation set makes that set part of the training procedure. Estimating shift after seeing deployment failures can bias the claimed envelope. A calibration curve averaged across a population may hide the subgroup or operating region that controls cost. When dependencies cannot be bounded, the honest representation is a conditional claim with a named gap, not a falsely precise total.

The contract should therefore permit three outcomes. Certified means every required span has evidence within its stated scope. Reference-bounded means the objective and target are connected only on the measured distribution. Open means one or more spans remain unbounded. The last two are not failed experiments. They identify the next useful measurement.

The smallest practical implementation is a typed bridge record, not a single convergence score. For each span, record its quantity, unit, comparator, scope, assumptions, evidence, confidence form, expiry trigger and accountable owner. A missing value remains missing. This prevents a tight optimisation number from visually overwhelming a weak or absent decision bridge.

Read every bound as an assumption ledger

Before using a theorem, write its clauses in operational language. What is the objective? Is the feasible set fixed? Are gradients exact, unbiased or merely bounded in expectation? Is noise independent across steps? Does the proof require bounded gradients, bounded variance, smoothness everywhere, a known Lipschitz constant, a unique minimiser or a particular averaging rule? Does the implementation use the same epsilon placement, bias correction and weight decay semantics?

The exercise often changes an engineering decision. A weaker rate under plausible assumptions can be more useful than a fast rate whose constants are unknowable or whose noise model is false. A high-probability bound may matter more than an expectation when a single bad run is costly. A local guarantee may be enough when the system has a verified entry region and a monitor that prevents escape.

A run manifest before an optimiser comparison

A fair comparison needs more than matched epoch counts. Record six items before looking at results. Name the operational target and its cost asymmetries. Freeze the model class, initialisation distribution and regularisation semantics. Specify the oracle in units of examples, gradient evaluations and numerical precision. Set a common resource budget, including hyperparameter search. Declare the stopping rule before viewing the test set. Finally, state the strongest permitted conclusion if the run succeeds.

This manifest prevents a common confound. One optimiser is often granted a tuned schedule, longer search or a different weight-decay implementation while another receives defaults. The resulting comparison mixes algorithm, budget and objective. A matched manifest does not guarantee scientific truth, but it makes causal attribution possible. It also reveals when the practical question is not “Which optimiser is faster?” but “Which entire training protocol reaches a decision-sufficient region with the least review and recovery cost?”

An executable optimiser and bound checker

The lab below uses a two-dimensional strongly convex quadratic with known curvature. It compares gradient descent, momentum and Adam on the same terrain. For deterministic gradient descent, it checks whether the selected step satisfies a conservative theorem clause and displays the actual objective gap beside a geometric upper bound. Add gradient noise or select another optimiser and the certificate is withdrawn rather than silently transferred.

This artefact tests a narrow but important idea: whether a visible convergence curve and a valid bound are the same thing. A positive result permits a statement about objective gap for this quadratic under exact arithmetic and declared settings. A negative result means only that the checker cannot certify the run. It does not prove divergence. The lab cannot establish generalisation, calibration, global optimality for non-convex models or deployment usefulness.

#!/usr/bin/env python3
"""Run a 2D quadratic optimiser experiment and check a GD bound."""
from __future__ import annotations

import argparse
import csv
import math
import random
import sys
from dataclasses import dataclass
from typing import Iterable


@dataclass(frozen=True)
class Config:
    optimiser: str
    kappa: float
    learning_rate: float
    steps: int
    noise_sd: float
    beta: float
    seed: int


def objective(x: float, y: float, kappa: float) -> float:
    return 0.5 * (x * x + kappa * y * y)


def gradient(x: float, y: float, kappa: float) -> tuple[float, float]:
    return x, kappa * y


def trajectory(cfg: Config) -> Iterable[tuple[int, float, float, float, float]]:
    rng = random.Random(cfg.seed)
    x = y = 4.0
    vx = vy = 0.0
    mx = my = 0.0
    sx = sy = 0.0
    eps = 1e-8

    for t in range(cfg.steps + 1):
        gx, gy = gradient(x, y, cfg.kappa)
        yield t, x, y, objective(x, y, cfg.kappa), math.hypot(gx, gy)
        if t == cfg.steps:
            break

        ngx = gx + rng.gauss(0.0, cfg.noise_sd)
        ngy = gy + rng.gauss(0.0, cfg.noise_sd)

        if cfg.optimiser == "gd":
            x -= cfg.learning_rate * ngx
            y -= cfg.learning_rate * ngy
        elif cfg.optimiser == "momentum":
            vx = cfg.beta * vx + ngx
            vy = cfg.beta * vy + ngy
            x -= cfg.learning_rate * vx
            y -= cfg.learning_rate * vy
        elif cfg.optimiser == "adam":
            b1, b2 = cfg.beta, 0.999
            mx = b1 * mx + (1.0 - b1) * ngx
            my = b1 * my + (1.0 - b1) * ngy
            sx = b2 * sx + (1.0 - b2) * ngx * ngx
            sy = b2 * sy + (1.0 - b2) * ngy * ngy
            step = t + 1
            mx_hat = mx / (1.0 - b1 ** step)
            my_hat = my / (1.0 - b1 ** step)
            sx_hat = sx / (1.0 - b2 ** step)
            sy_hat = sy / (1.0 - b2 ** step)
            x -= cfg.learning_rate * mx_hat / (math.sqrt(sx_hat) + eps)
            y -= cfg.learning_rate * my_hat / (math.sqrt(sy_hat) + eps)
        else:
            raise ValueError(f"unknown optimiser: {cfg.optimiser}")


def gd_bound(cfg: Config, initial_gap: float, t: int) -> float | None:
    # For this quadratic, mu=1 and L=kappa. We deliberately use the
    # conservative smooth/strongly-convex clause eta <= 1/L.
    if cfg.optimiser != "gd" or cfg.noise_sd != 0.0:
        return None
    if not (0.0 < cfg.learning_rate <= 1.0 / cfg.kappa):
        return None
    return initial_gap * (1.0 - cfg.learning_rate) ** t


def parse_args() -> Config:
    parser = argparse.ArgumentParser()
    parser.add_argument("--optimiser", choices=("gd", "momentum", "adam"), default="gd")
    parser.add_argument("--kappa", type=float, default=20.0)
    parser.add_argument("--learning-rate", type=float, default=0.05)
    parser.add_argument("--steps", type=int, default=80)
    parser.add_argument("--noise-sd", type=float, default=0.0)
    parser.add_argument("--beta", type=float, default=0.9)
    parser.add_argument("--seed", type=int, default=7)
    args = parser.parse_args()
    if args.kappa < 1 or args.learning_rate <= 0 or args.steps < 1:
        parser.error("require kappa >= 1, learning rate > 0 and steps >= 1")
    return Config(args.optimiser, args.kappa, args.learning_rate,
                  args.steps, args.noise_sd, args.beta, args.seed)


def main() -> int:
    cfg = parse_args()
    rows = list(trajectory(cfg))
    initial_gap = rows[0][3]
    writer = csv.writer(sys.stdout)
    writer.writerow(("step", "x", "y", "objective_gap", "gradient_norm", "valid_bound"))
    for t, x, y, gap, grad_norm in rows:
        bound = gd_bound(cfg, initial_gap, t)
        writer.writerow((t, f"{x:.10g}", f"{y:.10g}", f"{gap:.10g}",
                         f"{grad_norm:.10g}", "" if bound is None else f"{bound:.10g}"))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Part fiveThe decision this changes

Do not ask only, “Which optimiser reaches the lowest loss?” Ask, “Which configured training process gives the strongest defensible statement about the decision under the available data, compute and failure cost?” The change sounds verbal. It alters experiment design.

Before training, name the target risk and the surrogate bridge. During training, record the actual update equations, oracle properties, arithmetic, stopping rule and resource budget. At evaluation, report the certified quantity in its own type: objective gap, stationarity, regret or constraint violation. Then add estimation, approximation and shift evidence without pretending they are optimisation outputs.

When two procedures are close on the target, prefer the one whose assumptions can be monitored and whose failure can be detected. When the target bridge is unknown, run an intervention or collect the evaluation data needed to estimate it. When a theorem’s assumptions do not match the executable system, treat the theorem as design guidance rather than release evidence.

The practical consequence is to allocate effort by the largest unclosed gap, not by the most fashionable optimiser. Sometimes the answer is better conditioning, variance reduction or a safer step. Sometimes it is more representative data, a calibrated surrogate, a smaller model class, a different threshold or a deployment monitor. Optimisation matters enormously. It matters as one span in a bridge whose far bank is a real decision.