A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Support Vector Machines III: Symmetric Positive Definite Functions Are KernelsTextbook
The support vector machine and every other kernel method (Gaussian processes, kernel ridge
regression, kernel PCA) is specified by choosing a kernel: a function k(x,x′) measuring
similarity between two inputs, used in place of an inner product on the raw data. This lets a
linear algorithm implicitly work in a very high- or infinite-dimensional feature space…
High-Dimensional Probability VI: The Hanson-Wright InequalityTextbook
Sums of independent random variables are well understood: Bernstein's inequality and its
relatives give sharp, non-asymptotic tail bounds for ∑iaiXi whenever the Xi are
independent and light-tailed. Many quantities that arise in high-dimensional statistics and
random matrix theory, however, are not linear but quadratic in an independent sample —…
Foundations of Machine Learning III: Structural Risk Minimization and Model SelectionTextbook
Chapters 2 and 3 bound the estimation error of a hypothesis chosen from a fixed hypothesis
set H, but the choice of H itself is left open: a richer H lowers the approximation
error (how close H comes to the Bayes classifier) at the price of a looser generalization
bound, and a poorer H does the reverse. Chapter 4 is the book's answer to this trade-off. It…
Support Vector Machines I: Zhang's Inequality Relating the Hinge Risk and the Classification RiskTextbook
Binary classification asks for a rule that predicts a label y∈{−1,1} from an observation
x. The natural loss for this task, the classification loss Lclass, is a step
function: minimizing its empirical average over a class of functions f is generally NP-hard,
because the objective is non-convex and discontinuous in f. Every practical…
Foundations of Machine Learning I: The PAC Learning FrameworkTextbook
How many labeled examples does a learning algorithm need to see before its output
generalizes well to unseen data? Chapter 2 of Foundations of Machine Learning answers this
question for the simplest nontrivial setting — a finite hypothesis set — and in doing so
introduces the book's central object, the Probably Approximately Correct (PAC) learning…
First-Order and Stochastic Optimization Methods for Machine Learning VII: Gradient Sliding for Composite OptimizationTextbook
Composite convex programs — objectives split into a smooth piece and a nonsmooth piece — are
ubiquitous in data analysis: LASSO-type inverse problems, regularized empirical-risk minimization,
and total-variation-type image reconstruction all minimize f(x)+h(x)+χ(x) over a convex set,
where f is smooth (a data-fidelity term, often expensive to…
First-Order and Stochastic Optimization Methods for Machine Learning III: Stochastic Mirror DescentTextbook
Machine learning's canonical training objective — minimize an expected or empirical risk over a
data distribution — is almost never observed exactly: at each step an algorithm sees only a noisy
gradient sample (a minibatch gradient, a single-example gradient, a simulation draw). Stochastic
mirror descent (Nemirovski, Juditsky, Lan & Shapiro 2009) is the…
Introduction to Online Convex Optimization XIII: Blackwell's Approachability Theorem and Online Convex OptimizationTextbook
Von Neumann's minimax theorem (Chapter VIII) settles two-player zero-sum games with scalar
payoffs. In 1956, Blackwell asked the natural generalization: what can a player guarantee in a
repeated game with vector-valued payoffs, where "winning" means driving the average payoff
into a target set rather than above a target value? For decades the resulting…
Introduction to Online Convex Optimization XII: The Online Boosting MethodTextbook
Chapter XI boosted a weak learner into a strong one for a single offline fit to a fixed sample.
Chapter 12 asks the analogous question online: when the pool of experts is too large to run
Hedge over directly (the contextual-learning setting, where "experts" are policies mapping
contexts to actions and their number is exponential), can black-box access to a…
Introduction to Online Convex Optimization IX: From Online Convex Optimization to PAC LearningTextbook
Every algorithm in Chapters I–VIII minimizes regret, an online, adversarial performance
measure with no reference to a data-generating distribution. Chapter 9 asks what regret
minimization buys in the classical statistical learning setting, where examples are drawn i.i.d.
from a fixed distribution and the goal is a hypothesis that generalizes well to unseen…
Introduction to Online Convex Optimization VII: The Online Conditional Gradient AlgorithmTextbook
Every algorithm through Chapter VI updates its iterate by a Euclidean projection onto the
decision set K. For many decision sets that arise in practice — bounded-nuclear-norm matrices
(matrix completion / recommendation systems), the flow polytope (network routing), the
Birkhoff–von Neumann polytope (ranking/permutations), matroid polytopes — a projection…
Introduction to Online Convex Optimization IV: The Online Newton Step AlgorithmTextbook
Online convex optimization measures a decision maker against the best fixed decision in
hindsight, and the standard guarantee — achieved, for instance, by online gradient descent — is
regret growing like O(T) over T rounds. This rate is unimprovable for general convex
losses: an adversary can always force Ω(T) regret against any algorithm.…
Introduction to Online Convex Optimization X: Efficient Adaptive Regret for Online Convex OptimizationTextbook
Every regret guarantee through Chapter IX compares the algorithm to the single best fixed
decision in hindsight. That comparison is meaningless when the environment itself changes: a
commuter's best route differs on weekdays versus weekends, an investor's best portfolio differs in
a bull versus a bear market. A standard sublinear-regret algorithm, competing…
Stochastic Networks III: Loss Networks and the Erlang Fixed PointTextbook
Erlang's formula, the subject of mission I of this series, sizes a single telephone link. Real
networks are not single links: a call occupies a circuit on every link of its route
simultaneously, and it is lost unless every one of those links has a free circuit. That is the
loss network, the model of Chapter 3 of Frank Kelly and Elena Yudovina's Stochastic…
High-Dimensional Probability III: Grothendieck's InequalityTextbook
Many hard combinatorial optimization problems — finding the maximum cut of a graph, deciding
the ground state of an Ising spin system, bounding the correlation of a physical system — can
be written as maximizing a bilinear form over sign vectors xi∈{−1,1}. Exhaustive
search over 2n sign patterns is intractable, so practitioners relax the problem:…
High-Dimensional Probability V: The Johnson-Lindenstrauss LemmaTextbook
Any dataset of N points can be described exactly by embedding it in Rn for n large
enough — but a large n is expensive: nearest-neighbor search, clustering, and streaming
algorithms all scale with the ambient dimension, not with N. The question that opens this
mission is whether the dimension can be cut down while leaving the data's geometry — the…
Supermodularity and Complementarity V: Existence of Equilibrium in Supermodular GamesTextbook
Existence of equilibrium is the first question any model of strategic interaction must
answer, and the classical answer — Nash's theorem via Kakutani's fixed point theorem —
asks for a convex, compact strategy space and continuous payoffs. Many of the models
economists actually use do not have that: a firm's technology set can be discrete or
irregular, and…
Introduction to Online Convex Optimization III: Online Gradient DescentTextbook
Online convex optimization (OCO) models a repeated decision process: at each round a
learner picks a point in a convex set, an adversary (or the world) reveals a convex cost
function, the learner pays that cost at its own point, and the process repeats. No
statistical assumption on the sequence of costs is made. This model, introduced by
Zinkevich…
Introduction to Online Convex Optimization I: Learning from Expert Advice and the Hedge AlgorithmTextbook
Consider a decision maker who must choose, at each of T rounds, between two actions on the
advice of N "experts," none of which is known in advance to be reliable. This is the
prediction-from-expert-advice problem, introduced by Littlestone and Warmuth
[Littlestone & Warmuth, The Weighted Majority Algorithm, FOCS 1989/Inf. Comput. 1994] and
generalized to…
Introduction to Stochastic Programming VI: Jensen and Edmundson-Madansky BoundsTextbook
Two-stage stochastic programs with recourse require evaluating Q(x)=Eξ[Q(x,ξ)],
the expected value of a recourse function, at every candidate first-stage decision x. When
ξ is high-dimensional or continuously distributed, this expectation is a multivariate
integral of a piecewise-linear, generally nondifferentiable integrand, and classical…
Primal-Dual Online Algorithms II: Finite LP Duality and Complementary SlacknessTextbook
Almost every competitive online algorithm built by the primal-dual method rests on the same two facts about a pair of linear programs. The first is weak duality: any feasible solution of the dual is a lower bound on any feasible solution of the primal. The second is complementary slackness: if a feasible primal-dual pair satisfies a local, per-coordinate…
Dynamic Programming and Optimal Control V: LQG and Certainty EquivalenceTextbook
The separation theorem — certainty equivalence for linear-quadratic control with imperfect state information — is one of the celebrated structural results of stochastic control: the optimal controller splits into a least-squares estimator and the deterministic LQR actuator, designed independently. It underlies every LQG autopilot and Kalman-filter-based…
Dynamic Programming and Optimal Control II: Label Correcting MethodsTextbook
Label correcting methods are the workhorse family of shortest-path algorithms — Dijkstra's method, Bellman–Ford, SLF/LLL variants and A* all fit the template analyzed in §2.3.1 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005), where shortest paths appear as the purely deterministic face of dynamic programming. The correctness…
Algorithmic Game Theory I: Existence of Nash EquilibriumTextbook
The strategic-form game is the basic object of noncooperative game theory, and the Nash equilibrium — a profile of randomized strategies from which no player benefits by deviating unilaterally — is its central solution concept. Nash proved in 1951 that every game with finitely many players and finite strategy sets has such an equilibrium (Nash, Non-cooperati…
Markov Chains and Mixing Times VIII: Path Coupling and Approximate CountingTextbook
The coupling method of Mission III asks for a coupling of two copies of a chain from every pair of starting states — often painful to construct globally. Chapter 14 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) replaces that global demand by a local one. The path coupling technique of Bubley and Dyer says: put a connected graph structure…