∇ProvenDecisions
Ctrl K

Optimization for machine learning

Most of machine learning is optimization: training a model means choosing the weights that make a loss as small as possible. This page writes common ML problems as optimization models, names the problem class (which decides whether the solver's answer is the global best), and gives a small example for each. Solve this opens the example in Solve, where ProvenDecisions solves it with a real solver, checks the answer and walks you through the model step by step.

Regression and maximum likelihood are shared with applied statistics; those rows say so.

ML problems as optimization models

Linear regression (least squares) Convex QP

Fit a line to data by making the squared prediction errors as small as possible. No constraints, a convex quadratic objective: the normal equations are its optimality condition.

Example. Four students studied 1, 2, 3 and 4 hours and scored 52, 55, 61 and 64 points. Fit score = a + b × hours. Answer. a = 47.5 points, b = 4.2 points per hour; sum of squared errors 1.8 points².

Solve this · Tutorial: least squares as optimization (Student plan) · also applied statistics

Ridge regression (L2 regularization) Convex QP

Least squares plus a penalty on the size of the weights. The penalty shrinks the slope toward zero, which trades a little fit for less variance; the problem stays a convex QP with a unique answer.

Example. The same four students, with penalty λ = 5 on the slope b. Answer. a = 52.75 points, b = 2.1 points per hour (the slope halves: 21 / (5 + 5)).

Solve this · Tutorial: regularization (Student plan) · also applied statistics

Lasso (L1 regularization) Convex QP (after rewriting |.|)

Least squares plus a penalty on the absolute size of the weights. Unlike ridge, a large enough penalty sets weights exactly to zero, so the lasso also selects features. Convex, not smooth.

Example. The same four students, with penalty λ = 20 on |b|. Answer. a = 52.5 points, b = 2.2 points per hour ((21 − 10) / 5); at λ = 42 or more, b would be exactly 0.

Solve this · Tutorial: regularization (Student plan) · also applied statistics

Robust regression (least absolute deviations) LP (after rewriting |.|)

Fit a line by making the absolute errors small instead of the squared ones, so one wild point pulls the line much less. It becomes a linear program, with one helper variable per data point.

Example. Six students studied 1 to 6 hours and scored 52, 55, 85, 64, 68 and 73 points; the 85 is a wrong entry (it should be 61). Answer. a = 48 points, b = 4 points per hour, total absolute error 27 points: close to the clean data's least-squares slope of 4.2, while least squares on the bad data drops to about 3.51.

Solve this · Tutorial: robust regression least absolute deviations (Student plan) · also applied statistics

Logistic regression Convex (exponential cone)

Predict a yes/no outcome: choose weights that make the observed outcomes most likely (maximum likelihood). The negative log-likelihood is convex, so the solver's answer is the global best.

Example. Six students studied 1 to 6 hours; those at 3, 5 and 6 hours passed, those at 1, 2 and 4 failed. Fit P(pass) = 1 / (1 + exp(−(w × hours + c))). Answer. w ≈ 1.214 per hour, c ≈ −4.249: a 50% chance of passing at exactly 3.5 hours (the data are symmetric about 3.5 hours).

Solve this · Tutorial: logistic regression maximum likelihood (Standard plan) · also applied statistics

Support vector machine (soft margin) Convex QP (after rewriting max)

Separate two classes with the widest possible margin, paying a hinge penalty for each point on the wrong side of its margin. A convex QP; its dual is where the support vectors and kernels come from.

Example. Points (2, 2) and (3, 1) are class +1; points (0, 0) and (1, 0) are class −1; C = 1. Answer. w = (2/3, 2/3), c = −5/3: the line x1 + x2 = 2.5, with every point on or outside its margin.

Solve this · Tutorial: support vector machines (Standard plan)

k-means clustering Nonconvex (exact by enumeration for small sets)

Split points into k groups so each point is close to its group's centre. Nonconvex: the usual algorithm finds a local answer; for a small set ProvenDecisions checks every split, so the answer is exact.

Example. Six points in the plane: (1, 1), (1.5, 2), (2, 1), (8, 8), (9, 8.5), (8.5, 9); k = 2. Answer. The three points near (1.5, 1.3) and the three near (8.5, 8.5); total squared distance 2.17 (13/6).

Solve this · Tutorial: nonconvex and local optima (Pro plan)

Gradient descent: the best step size Convex QP (one variable)

Training a model moves the weights against the gradient. How far to move is itself a one-variable optimization problem (an exact line search): minimize the loss along the step.

Example. Loss f(x, y) = x² + 10y² at the point (1, 1), where the gradient is (2, 20). Answer. t = 404/8008 ≈ 0.0504; the loss drops from 11 to about 0.81 in one step.

Solve this · Tutorial: gradient descent step size (Student plan)

Optimal transport (earth mover's distance) LP

How far apart are two distributions? The cheapest way to reshape one pile of mass into the other, paying distance times mass, is a transportation problem. Used to compare histograms and in Wasserstein GANs.

Example. 0.5, 0.3 and 0.2 tonnes of sand at 1, 2 and 3 km must become 0.2, 0.3 and 0.5 tonnes; moving costs the distance in km per tonne. Answer. 0.6 tonne-km, the gap between the two running totals (0.3 + 0.3); the cheapest plan is not unique, the distance is.

Solve this · Tutorial: optimal transport earth movers distance (Student plan)

Quantile regression (the 90th percentile) LP

Predict a percentile instead of the average, for promises and prediction intervals. The lopsided pinball loss charges τ per unit above the line and 1 − τ below it: a linear program.

Example. Eight deliveries over 1 to 8 km took 12, 15, 14, 22, 20, 25, 35 and 28 minutes; τ = 0.9. Answer. about 8.17 + 3.83 minutes per km: no delivery lies above it (the median line is 9.4 + 2.6 per km).

Solve this · Tutorial: quantile regression (Student plan) · also applied statistics

Best-subset feature selection Mixed-integer QP

Use at most k features and pick the best ones: a yes/no variable per feature, a big-M link to its coefficient, and a limit on how many are on. Solved with a proof of optimality.

Example. Five observations, three candidate features, at most k = 2 of them, M = 10. Answer. features 1 and 2 (β ≈ 1.40 and 0.70), squared error about 0.460; trying all six subsets of size one or two gives the same winners.

Solve this · Tutorial: best subset feature selection (Standard plan) · also applied statistics

Reinforcement learning: a Markov decision process LP

The best long-run behaviour of an agent, as a linear program over state values: each value is at least what every action earns. The dual values show which actions the best policy uses.

Example. A robot in two rooms, discount 0.9 per step: room 1 stay $1, move $0; room 2 stay $2, move back $0.5. Answer. V1 = $18, V2 = $20: in room 1 move, in room 2 stay (2 / (1 − 0.9) = 20 and 0.9 × 20 = 18).

Solve this · Tutorial: reinforcement learning mdp linear program (Standard plan)

Why the class matters

Least squares, ridge, lasso, robust regression, logistic regression, support vector machines, optimal transport, quantile regression and the Markov decision process are convex (several are plain linear programs): any local best is the global best, and a dual certificate proves it. Best-subset selection is a mixed-integer program: branch and bound proves the best subset without trying every one. k-means and neural-network training are nonconvex: methods like gradient descent find a local answer, and ProvenDecisions labels such answers as local unless it can check every case, as it does for small k-means problems. See Problem classes and Primal and dual.

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: