Optimisation for machine learning

In short

Optimisation is the machinery that actually *fits* a machine-learning model: you write the learning task as "minimise a loss function over parameters, possibly subject to constraints", then choose an algorithm that finds the minimum reliably and cheaply. It decides whether a model trains at all, how fast, and how well it generalises — the loss, the optimiser, the learning rate and the regularisation penalty are all optimisation objects. Indian university AI&DS syllabi (AICTE model curriculum, UGC CBCS) examine convexity, gradient and Newton-type methods, Lagrange multipliers, KKT conditions, duality and the modern SGD family; GATE DA (Data Science and AI, introduced 2024) has a dedicated "Machine Learning" and linear-algebra/calculus block where convexity and gradient methods appear. Interviewers at TCS Research, Fractal, Mu Sigma, ZS, Flipkart, Swiggy, Nvidia and Qualcomm India ask why Adam is the default, what the learning rate does, and why L1 gives sparsity.

Explained

The optimisation problem behind learning

• Standard form: minimise f(x) subject to gᵢ(x) ≤ 0 (inequality constraints) and hⱼ(x) = 0 (equality constraints), x ∈ ℝⁿ. f is the objective; a maximisation is handled as minimise −f.
• In ML: x is the parameter vector θ (weights), and f is empirical risk J(θ) = (1/n)Σ L(yᵢ, ŷᵢ(θ)) + λR(θ) — average loss over n training points plus a regularisation term.
• Loss types: squared error (regression), log-loss/cross-entropy (classification), hinge loss (SVM), Huber (robust to outliers).
• Feasible region: the set satisfying all constraints. Unconstrained problems (most deep learning) have none; constrained problems (SVM, portfolio weights, resource limits) do.
• Classification of problems: linear programming (linear f and constraints), quadratic programming (quadratic f, linear constraints — SVM dual), convex nonlinear, non-convex (neural nets), integer/combinatorial (feature selection), stochastic (noisy objective).
• Local vs global minimum: x* is a local minimum if f(x*) ≤ f(x) for all x in a neighbourhood; global if for all feasible x. Convexity is what makes the two coincide.

Convexity — why it is the dividing line

• A convex set contains the whole segment between any two of its points: λx + (1−λ)y ∈ C for λ ∈ [0,1].
• A convex function satisfies f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) — the chord never dips below the graph. Strictly convex if the inequality is strict.
• First-order test: f convex ⇔ f(y) ≥ f(x) + ∇f(x)ᵀ(y − x) (the tangent plane under-estimates everywhere).
• Second-order test: f twice differentiable is convex ⇔ Hessian H = ∇²f is positive semi-definite (all eigenvalues ≥ 0) on the domain; strictly convex if positive definite.
• Key consequence: for a convex f on a convex feasible set, any local minimum is global and the set of minimisers is convex. Hence linear/ridge regression, logistic regression and SVM have unique (or unique-up-to-flat-directions) solutions.
• Convex examples: xᵀAx with A PSD, ‖x‖ for any norm, eˣ, −log x, log-sum-exp, max of convex functions. Non-convex: neural network loss, k-means objective, L0 penalty.
• Optimality conditions (unconstrained): stationary point ∇f(x*) = 0; then H positive definite → local minimum, negative definite → local maximum, indefinite → saddle point.
• Convexity-preserving operations: non-negative weighted sums, composition with affine maps, pointwise maximum — used to prove a designed loss is convex.

Gradient-based first-order methods

1. Batch gradient descent: θ ← θ − η∇J(θ) using all n samples per step. Smooth, deterministic descent; cost O(n) per step, so impractical on crores of rows.
2. Stochastic gradient descent (SGD): one random sample per update. Cheap and noisy; the noise helps escape shallow local minima and saddles but prevents exact convergence, so the step size must decay.
3. Mini-batch SGD: the practical default — batches of 32–512 samples; vectorised on GPU, variance of the gradient falls as 1/B.
4. Learning rate η is the single most important hyper-parameter: too large → divergence or oscillation across the valley; too small → crawling, and stalling in flat regions.
5. Convergence (theory): for convex, L-smooth f, gradient descent with η ≤ 1/L gives f(θₖ) − f* = O(1/k); strongly convex gives linear (geometric) rate; SGD with decaying η gives O(1/k) for strongly convex, O(1/√k) convex.
6. Condition number κ = λmax/λmin of the Hessian governs speed: a large κ means elongated contours and zig-zagging — the standard reason to standardise features.
7. Momentum: v ← βv + ∇J(θ); θ ← θ − ηv (β ≈ 0.9). Averages past gradients, damping oscillation across the narrow axis and accelerating along the consistent one.
8. Nesterov accelerated gradient (NAG): evaluates the gradient at the look-ahead point θ − ηβv, giving a provable O(1/k²) rate for smooth convex problems.

Adaptive methods and schedules

• AdaGrad: accumulates squared gradients, G ← G + g², θ ← θ − η·g/(√G + ε) — a per-parameter rate, excellent for sparse features (text, one-hot IDs). Flaw: G only grows, so the effective rate dies.
• RMSProp: replaces the sum with an exponential moving average, E[g²] ← ρE[g²] + (1−ρ)g², ρ ≈ 0.9 — fixes AdaGrad's decay.
• Adam: momentum (first moment m) plus RMSProp (second moment v) with bias correction; defaults β₁ = 0.9, β₂ = 0.999, ε = 1e−8. Robust across architectures and the usual starting choice. AdamW decouples weight decay from the adaptive scaling and is the standard for transformers.
• Comparison in one line: SGD + momentum often generalises slightly better on vision tasks with careful tuning; Adam/AdamW converges faster with little tuning and dominates NLP and large models.
• Schedules: step decay, exponential decay, 1/t decay, cosine annealing, warm-up (linear ramp for the first few thousand steps — essential for transformers), cyclical rates, ReduceLROnPlateau.
• Practical aids: gradient clipping (clip ‖g‖ to a threshold) against exploding gradients in RNNs; batch normalisation smooths the loss surface; early stopping is implicit regularisation; weight initialisation (Xavier/He) decides whether gradients survive the first steps.
• Saddle points, not local minima, are the real obstacle in high dimensions — the number of directions grows with parameters, and gradient noise plus momentum usually carries SGD past them.

Second-order and derivative-free methods

• Newton's method: θ ← θ − H⁻¹∇f(θ). Quadratic convergence near the optimum and scale-invariant, but needs the n×n Hessian: O(n²) memory and O(n³) per solve — hopeless for a model with crores of parameters.
• Quasi-Newton (BFGS, L-BFGS): build an approximate inverse Hessian from successive gradients; L-BFGS keeps only the last m (5–20) vectors and is the workhorse for medium-scale convex problems — it is what scikit-learn's default logistic-regression solver (lbfgs) uses.
• Gauss–Newton / Levenberg–Marquardt: for least-squares residuals; LM interpolates between Gauss–Newton and gradient descent via a damping parameter.
• Conjugate gradient: solves large PSD linear systems and quadratic objectives without forming the Hessian.
• Coordinate descent: optimise one coordinate at a time — the standard solver for Lasso and for coordinate-separable objectives (glmnet style).
• Derivative-free / global: grid search, random search (usually better per unit compute for hyper-parameters), Bayesian optimisation (Gaussian-process or TPE surrogate — Optuna, Hyperopt), simulated annealing, genetic algorithms, particle swarm. Used for hyper-parameters and non-differentiable objectives, not for weights.
• EM algorithm optimises a likelihood with latent variables by alternating a lower-bound construction (E-step) and its maximisation (M-step) — monotone increase, no global guarantee.

Constrained optimisation: Lagrange, KKT and duality

• Equality constraints — Lagrange multipliers: form L(x, λ) = f(x) + Σλⱼhⱼ(x); set ∇ₓL = 0 and hⱼ(x) = 0 and solve. λ is the shadow price — the rate of change of the optimum per unit relaxation of the constraint.
• Inequality constraints — KKT conditions (necessary at an optimum under constraint qualification, and sufficient when the problem is convex), with L = f + Σμᵢgᵢ + Σλⱼhⱼ:
  1. Stationarity: ∇f + Σμᵢ∇gᵢ + Σλⱼ∇hⱼ = 0.
  2. Primal feasibility: gᵢ(x) ≤ 0, hⱼ(x) = 0.
  3. Dual feasibility: μᵢ ≥ 0.
  4. Complementary slackness: μᵢgᵢ(x) = 0 — a constraint is either tight (gᵢ = 0) or its multiplier is zero.
• Duality: the Lagrange dual g(μ, λ) = infₓ L is always concave; weak duality gives dual optimum ≤ primal optimum, and the gap is the duality gap. Strong duality (zero gap) holds for convex problems under Slater's condition (a strictly feasible point exists).
• SVM as the canonical case: the primal minimises ½‖w‖² + CΣξᵢ; the dual is a quadratic program in αᵢ with 0 ≤ αᵢ ≤ C and Σαᵢyᵢ = 0. Complementary slackness identifies the support vectors (αᵢ > 0), and the dual's inner products allow the kernel trick.
• Projected gradient / penalty / barrier methods: enforce constraints by projecting back onto the feasible set, or by adding a penalty (quadratic) or barrier (−log) term; interior-point methods follow a barrier path and solve LP/QP in polynomial time.
• Regularisation is constrained optimisation in disguise: minimising J + λ‖θ‖² is equivalent to minimising J subject to ‖θ‖² ≤ t for a corresponding t; λ and t are linked through the KKT multiplier.
• L1 vs L2: the L1 ball has corners on the axes, so the solution touches it at a vertex and coefficients become exactly zero (sparsity, feature selection); the L2 ball is smooth and only shrinks. Elastic net combines both.

Linear programming and the operations-research thread

• LP standard form: minimise cᵀx subject to Ax = b, x ≥ 0. The optimum, if it exists, lies at a vertex of the feasible polyhedron.
• Simplex method walks from vertex to vertex improving the objective; interior-point methods cut through the interior and are polynomial-time. Both appear in Indian university OR/optimisation papers.
• LP duality: every primal has a dual whose optimal value matches at optimum; dual variables are shadow prices used in resource-allocation and transportation problems.
• ML links: L1-regression and hinge-loss problems can be cast as LP/QP; integer programming handles subset selection and scheduling.

Key points

• Objective function - the quantity minimised; in ML it is loss plus regularisation, averaged over the training set.
• Convex function - chord above graph; equivalently PSD Hessian; guarantees every local minimum is global.
• Stationary point - ∇f = 0; Hessian's definiteness separates minimum, maximum and saddle.
• Condition number - λmax/λmin of the Hessian; large value means zig-zag and slow convergence, cured by feature scaling.
• Batch vs SGD vs mini-batch - exact and slow, noisy and cheap, and the practical compromise (B = 32–512).
• Learning rate - step multiplier; the top-priority hyper-parameter, almost always decayed on a schedule.
• Momentum - exponential average of gradients (β ≈ 0.9) that damps oscillation; Nesterov adds a look-ahead.
• AdaGrad / RMSProp / Adam - per-parameter rates: accumulated g², EMA of g², and both moments with bias correction.
• AdamW - Adam with decoupled weight decay; the default for transformers.
• Warm-up plus cosine decay - standard schedule for large models; prevents early instability.
• Newton's method - uses H⁻¹; quadratic convergence but O(n³) cost, so unusable at deep-learning scale.
• L-BFGS - limited-memory quasi-Newton; the default solver for logistic regression in scikit-learn.
• Lagrange multiplier λ - shadow price of a constraint; appears in the stationarity condition.
• KKT conditions - stationarity, primal feasibility, dual feasibility (μ ≥ 0), complementary slackness; sufficient for convex problems.
• Duality gap - primal minus dual optimum; zero for convex problems satisfying Slater's condition.
• Support vectors - the points with αᵢ > 0 in the SVM dual, identified by complementary slackness.
• L1 gives sparsity, L2 only shrinks - a consequence of the L1 ball's corners.
• Saddle points dominate - in high dimensions they, not local minima, slow training; noise and momentum escape them.
• Gradient clipping and early stopping - practical fixes for exploding gradients and over-fitting respectively.

Formulas and examples

Example 1 — gradient descent by hand, and the effect of η. Minimise f(θ) = θ² − 4θ + 5, so f′(θ) = 2θ − 4; the exact minimum is θ* = 2, f* = 1. With θ₀ = 0, η = 0.1: update θ ← θ − 0.1(2θ − 4) = 0.8θ + 0.4.

• θ₁ = 0.4, θ₂ = 0.72, θ₃ = 0.976, θ₄ = 1.1808, θ₅ = 1.34464.
• The error multiplies by 0.8 each step: after 20 steps |θ − 2| = 2 × 0.8²⁰ ≈ 0.023 — geometric (linear) convergence.

Now η = 1.1: θ ← θ − 1.1(2θ − 4) = −1.2θ + 4.4. θ₁ = 4.4, θ₂ = −0.88, θ₃ = 5.456 — the error multiplies by |−1.2| = 1.2, so it diverges. Here f″ = 2 = L, and stability needs η < 2/L = 1; η = 0.1 is safe, η = 1.1 is not.

Example 2 — convexity and a saddle point from the Hessian. (a) f(x, y) = x² + 3y² + xy. Hessian H = [[2, 1], [1, 6]]; trace = 8 > 0 and det = 2×6 − 1 = 11 > 0, so both eigenvalues are positive → positive definite → strictly convex, and the unique stationary point is a global minimum. Solving ∇f = 0: 2x + y = 0 and 6y + x = 0 → x = y = 0, f = 0. (b) f(x, y) = x² − y². H = [[2, 0], [0, −2]], eigenvalues +2 and −2 → indefinite, so (0,0) is a saddle point: a minimum along x, a maximum along y. Gradient descent started exactly on the y = 0 line would stall there. Condition number of (a): eigenvalues solve μ² − 8μ + 11 = 0 → μ = 4 ± √5 = 6.236 and 1.764, so κ ≈ 3.54 — mildly elongated contours.

Example 3 — Lagrange multipliers and the shadow price. Minimise f(x, y) = x² + y² subject to x + 2y = 10. L = x² + y² + λ(x + 2y − 10). ∂L/∂x = 2x + λ = 0 → x = −λ/2; ∂L/∂y = 2y + 2λ = 0 → y = −λ. Substituting: (−λ/2) + 2(−λ) = 10 → −2.5λ = 10 → λ = −4. So x = 2, y = 4, f = 4 + 16 = 20. Shadow price check: with the right-hand side b, f* = b²/5, so df*/db = 2b/5 = 4 at b = 10 — equal to −λ, confirming the multiplier measures sensitivity to the constraint (sign depends on the Lagrangian convention).

Example 4 — one Adam step versus one SGD step. Take g₁ = 0.1 at the first iteration, η = 0.001, β₁ = 0.9, β₂ = 0.999, ε = 1e−8.

• m₁ = 0.1 × 0.1 = 0.01; v₁ = 0.001 × 0.01 = 1×10⁻⁵.
• Bias correction: m̂ = 0.01/(1 − 0.9) = 0.1; v̂ = 1×10⁻⁵/(1 − 0.999) = 0.01, √v̂ = 0.1.
• Δθ = −0.001 × 0.1/0.1 = −0.001, i.e. exactly −η: after bias correction Adam's first step has magnitude η regardless of the gradient's size.
• Plain SGD with the same η: Δθ = −0.001 × 0.1 = −0.0001, ten times smaller. This scale-invariance is why Adam needs far less tuning — and why its η must be set much smaller than SGD's.

Example 5 — mini-batch economics on an Indian-scale dataset. A UPI fraud model has n = 50,00,000 (50 lakh) transactions; one gradient per sample costs ~1 µs of GPU time.

• Batch GD: one update needs 50,00,000 µs = 5 s; 100 epochs = 100 updates = 500 s of compute but only 100 parameter updates.
• Mini-batch B = 256: one epoch = 50,00,000/256 ≈ 19,531 updates; 100 epochs ≈ 19,53,125 updates for the same 500 s of gradient work.
• Gradient noise: the standard error of a mini-batch gradient scales as σ/√B, so B = 256 has 16× less noise than single-sample SGD (√256 = 16), while still giving ~19.5 thousand updates per epoch.

# Mini-batch SGD with momentum, written out - no library optimiser
v = np.zeros_like(theta)
for epoch in range(epochs):
    idx = np.random.permutation(n)
    for s in range(0, n, B):
        xb, yb = X[idx[s:s+B]], y[idx[s:s+B]]
        g = (xb.T @ (xb @ theta - yb)) / len(yb)   # MSE gradient
        v = 0.9 * v + g
        theta -= lr * v
    lr *= 0.95                                      # exponential decay

Where it is used

• Banking, lending and insurance analytics: HDFC, ICICI, Bajaj Finserv and credit bureaus train logistic-regression and gradient-boosting scorecards where L1/L2 penalties and the L-BFGS solver decide which features survive.
• E-commerce and delivery platforms: Flipkart, Myntra, Swiggy, Zomato and Zepto use Adam-trained ranking and ETA models, plus LP/integer programming for rider assignment, slot allocation and warehouse routing.
• Fintech and payments: UPI-scale fraud detection trains on crores of rows with mini-batch SGD; constrained optimisation sets exposure and risk limits.
• Telecom and ad-tech: Jio and Airtel use convex optimisation for spectrum, capacity and bid optimisation; AdaGrad-family methods suit the sparse one-hot features of click-through models.
• Job roles: data scientist, ML engineer, research engineer, quant analyst, operations-research/optimisation engineer; ML-systems roles at Nvidia, Qualcomm, AMD and Intel India tune learning-rate schedules and mixed-precision training.
• Public and academic use: IITs and IIITs, ISRO trajectory and scheduling work, and power-sector load dispatch (an LP/QP problem) all sit on the same mathematics.

Interview questions

• Q: Why does convexity matter so much in ML? A: For a convex objective on a convex feasible set every local minimum is global, so any descent method that converges finds the best solution and the result does not depend on initialisation.
• Q: Difference between batch, stochastic and mini-batch gradient descent? A: Batch uses all n samples per update (exact but slow), SGD uses one (cheap but noisy), mini-batch uses B samples — vectorisable on a GPU with gradient noise reduced by √B.
• Q: What happens if the learning rate is too high or too low? A: Too high and the loss oscillates or diverges because each step overshoots the valley; too low and training crawls and may stall in flat regions before converging.
• Q: How does momentum help? A: It accumulates an exponential average of past gradients, cancelling the oscillating component across a narrow ravine and reinforcing the consistent direction, which effectively increases the step along the useful axis.
• Q: Why is Adam usually the default, and when would you prefer SGD with momentum? A: Adam adapts a per-parameter step from the first and second gradient moments, so it works well with little tuning; well-tuned SGD + momentum often generalises marginally better on vision tasks and uses less optimiser memory.
• Q: Why is Newton's method not used for deep networks? A: It needs the Hessian and its inverse — O(n²) memory and O(n³) per step for n parameters, which is impossible for millions of weights, and the Hessian is indefinite in non-convex regions.
• Q: State the KKT conditions. A: Stationarity of the Lagrangian, primal feasibility, dual feasibility (non-negative multipliers for inequalities) and complementary slackness μᵢgᵢ = 0; they are necessary at an optimum under a constraint qualification and sufficient for convex problems.
• Q: What does a Lagrange multiplier mean physically? A: It is the shadow price — the rate at which the optimal objective improves per unit relaxation of that constraint; a zero multiplier means the constraint is not binding.
• Q: Why does L1 produce sparse weights while L2 does not? A: The L1 constraint region is a diamond with vertices on the axes, so the loss contour typically first touches it at a corner where some coordinates are exactly zero; the L2 ball is smooth and has no such corners.
• Q: In high dimensions, are local minima or saddle points the bigger problem? A: Saddle points — with many parameters it is improbable that all Hessian eigenvalues share a sign, and stochastic noise with momentum usually escapes saddles.
• Q: What is the duality gap and when is it zero? A: It is the difference between the primal and dual optimal values; weak duality makes it non-negative, and it is zero (strong duality) for convex problems satisfying Slater's condition, as in the SVM.
• Q: Why standardise features before gradient descent? A: Unequal scales make the Hessian ill-conditioned (large κ), so contours are elongated and descent zig-zags; scaling equalises curvature and allows a larger stable learning rate.
• Q: What is learning-rate warm-up for? A: A short linear ramp from near zero prevents huge early updates when adaptive moment estimates are still unreliable — standard practice when training transformers.

Common mistakes

• Treating ∇f = 0 as proof of a minimum without checking the Hessian — it may be a maximum or a saddle.
• Using the same learning rate for SGD and Adam; Adam's effective step is normalised, so it needs a value roughly an order of magnitude smaller.
• Forgetting Adam's bias correction when implementing it by hand, which makes the first steps far too small.
• Claiming a non-convex loss has a unique solution, or quoting "local minimum = global minimum" without the convexity assumption.
• Dropping the μᵢ ≥ 0 requirement or complementary slackness when writing KKT conditions, and applying equality-constraint Lagrange theory to inequalities.
• Not shuffling data between epochs, so mini-batches carry the file's ordering and the gradient becomes biased.
• Tuning the learning rate on the test set, or reporting the best epoch chosen by test loss — that is validation leakage, not performance.
• Confusing regularisation strength λ with the learning rate η, or forgetting that scikit-learn's logistic regression parameterises the penalty as C = 1/λ.

Related topics

Calculus and gradient descent · Linear algebra for machine learning · Supervised learning: regression and classification · Support vector machines and kernels · Deep learning and neural networks · Model evaluation and regularisation