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.
A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization II: Interchangeability Holds for Diagonally Dominant Functions iff Measurable Projection and Weak Selection DoResearch Paper
In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P. Every tractable reformulation rests on a strong duality theorem that replaces the supremum over distributions by a one-dimensional minimization over a multiplier …
Optimization-Based Algorithms for Tensor Decompositions: Canonical Polyadic Decomposition, Decomposition in Rank-(Lr, Lr, 1) Terms, and a New Generalization 1: Block Structure of the Gramian JᴴJResearch Paper
Tensor decompositions express a multiway array as a sum of simple terms. The canonical polyadic decomposition (CPD) writes an N-th order tensor T∈CI1×⋯×IN as a sum of R outer products of vectors; block term decompositions replace each rank-one term by a term of higher multilinear rank. These models are used in signal…
Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz Algorithm: SGD with Step γ < 1/sup L Has E‖x_k − x⋆‖² ≤ [1 − 2γμ(1 − γ sup L)]^k ‖x₀ − x⋆‖² + γσ²/(μ(1 − γ sup L))Research Paper
Stochastic gradient descent (SGD) minimizes an objective that is an expectation, F(x)=Ei∼Dfi(x), by stepping along the gradient of one randomly drawn component at a time. It is the workhorse of large-scale machine learning, where F is an average loss over training examples, and it also contains the randomized Kaczmarz method for…
Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 3: Hankel-Matrix SDP Lower Bounds for Minimizing a Power Sum Subject to Fixed Lower Power SumsResearch Paper
Many polynomial optimization problems are invariant under permuting the variables: the objective and the constraints are symmetric polynomials. Lasserre's moment–sum-of-squares hierarchy solves such problems by a sequence of semidefinite programs whose size grows quickly with the number of variables and the degree, and symmetry is the main tool for…
Triangle-Free Intersection Graphs of Line Segments with Large Chromatic Number: For Every k ≥ 1 There Is a Triangle-Free Family of Plane Line Segments with Chromatic Number Greater than kResearch Paper
A proper coloring of a graph assigns colors to its vertices so that adjacent vertices get different colors; the least number of colors that suffices is the chromatic numberχ(G). The clique numberω(G) is the size of a largest set of pairwise adjacent vertices, and χ(G)≥ω(G) always. A class of graphs is χ-bounded if χ is bounded by a…
Linear-Quadratic Optimal Control Problems for Mean-Field Stochastic Differential Equations: Two Riccati Equations Give the Optimal State-Feedback Control and the Value ⟨Π(0)x, x⟩Research Paper
Linear-quadratic (LQ) control is the setting in which stochastic optimal control has a closed-form answer: the optimal control is a linear feedback of the state, and the feedback gain comes from a Riccati differential equation. In the mean-field version, the expectation E[X] of the state and E[u] of the control appear in the dynamics and in…
Tight Complexity Bounds for Optimizing Composite Objectives I: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(mLB/ε) Queries on Sums of m Convex L-Lipschitz FunctionsResearch Paper
Many optimization problems minimize the average of component losses: one loss per observation, machine, or term in an objective. When an algorithm can inspect one component at a time, the number of component queries is a useful measure of work. A component oracle can provide more than a value or subgradient: a proximal point summarizes a global minimization…
A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization I: Worst-Case Loss = min over λ ≥ 0 of λρ + E[sup f − λc] for All ρ > 0 iff Interchangeability HoldsResearch Paper
Wasserstein distributionally robust optimization (DRO) hedges a decision against every probability distribution within a given transport distance of a nominal one, typically the empirical distribution of data. The inner problem, the worst-case loss, is an optimization over an infinite-dimensional set of measures, and every practical use of Wasserstein DRO —…
A Modern Introduction to Online Learning XI: Constrained Online Convex Optimization Reduces to Unconstrained Learning on Distance-Penalized Surrogate LossesTextbook
An online learner repeatedly chooses a point, observes a loss, and is judged by the difference between its accumulated loss and that of a fixed competitor. In practice, an available learner may operate on a broad feasible set W, while the application permits decisions only in a smaller set V. Replacing each output by a feasible point changes the learner's…
A Modern Introduction to Online Learning XIII: Online Mirror Descent Has Dynamic Regret (B_ψ(u_T; x_1) + Q·P(u_1, …, u_T))/η + (η/(2λ)) Σ_t ‖g_t‖⋆²Textbook
In online learning, a learner chooses a point before seeing each round's loss. Ordinary regret compares the learner with one fixed point chosen after all rounds. That comparison can be too coarse when a useful action changes over time. A portfolio allocation, a prediction rule, or an operating point may need to move after the environment shifts. Dynamic…
Fast Rates for Contextual Linear Optimization 3: Under the Margin Condition, a Plug-In Policy Whose Estimate Has Pointwise Sub-Gaussian Tails at Rate aₙ Has Regret O(B·aₙ^(−(1+α)/2))Research Paper
Many operational decisions are linear programs whose cost vector is uncertain but predictable from side information: routing with travel times that depend on weather and time of day, procurement with prices that depend on market signals, assignment with costs that depend on observed features. Contextual linear optimization (CLO) formalizes this: observe…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights V: The Speed Restarted ODE Converges Linearly for Strongly Convex fResearch Paper
Nesterov's accelerated gradient method minimizes a convex function f with L-Lipschitz gradient at the rate O(1/k2), which is optimal among first-order methods. For a μ-strongly convex f the method with the generic momentum coefficient (k−1)/(k+2) does not exploit the strong convexity: Su, Boyd and Candès show in §4.2 of arXiv:1503.01243 that its rate…
Phase Recovery, MaxCut and Complex Semidefinite Programming 1: For Injective A, Nonzero b and Solvable |Ax| = b, PhaseCutMod Is Tight Whenever PhaseLift IsResearch Paper
Phase recovery (also called phase retrieval) asks to reconstruct a complex signal from the magnitudes of linear measurements of it, the phases being lost. It arises wherever detectors record intensities only: X-ray crystallography, diffraction imaging, astronomy and optics, where a sensor measures ∣⟨ai,x⟩∣2 and not ⟨ai,x⟩. The…
Relatively Smooth Convex Optimization by First-Order Methods, and Applications III: The Primal Gradient Scheme Solves D-Optimal Design to Accuracy ε within 2n ln(2(f(x⁰)−f*)/ε)/ε IterationsResearch Paper
In D-optimal design, a statistician chooses weights for a collection of candidate observations. The weights determine an information matrix, and maximizing its determinant favors a design that estimates several parameters jointly with a small confidence region. The same determinant objective appears in the minimum-volume enclosing ellipsoid problem. These…
A Modern Introduction to Online Learning V: Online Mirror Descent with a λ-Strongly Convex Regularizer Has Regret max_t B_ψ(u; x_t)/η_T + Σ_t η_t‖g_t‖⋆²/(2λ)Textbook
Online learning studies repeated decisions made before their losses are known. A learner chooses a point, observes a loss function, and then uses that observation to choose the next point. The natural performance measure is regret: the learner's cumulative loss minus the cumulative loss of one fixed competitor chosen after the sequence is known. A regret…
Robust Markov Decision Processes 2: The Affine Reward-to-Go Semidefinite Program Is Exact for One Quadratic Constraint and Conservative for SeveralResearch Paper
A Markov decision process (MDP) evaluates a policy by its expected discounted reward, which requires the transition probabilities. In practice these are estimated from data, and the optimal policy of the estimated model can perform badly under the true kernel. Robust MDPs replace the kernel by an ambiguity set of kernels and judge a policy by its worst-case…
Distributionally Robust Convex Optimization II: The Naïve Approximation Implies the Infimal Convolution Bound, Which Implies the Distributionally Robust ConstraintResearch Paper
A constraint E[v(x,z~)]≤w on a decision x needs the distribution of the random vector z~, which in practice is known only through partial information: a support, some moments, the probability mass of a few regions. Distributionally robust optimization requires the constraint for every distribution consistent with that information.…
Robustness May Be at Odds with Accuracy 1: Every Classifier with Standard Accuracy ≥ 1 − δ Has ℓ∞ Robust Accuracy ≤ pδ/(1 − p) Against ε ≥ 2ηResearch Paper
Classifiers trained to be robust against small, adversarially chosen input perturbations routinely lose standard accuracy. Adversarial training (Madry et al., 2018) improves worst-case accuracy under an ℓp-bounded attack, but on MNIST, CIFAR-10 and ImageNet the resulting models are measurably less accurate on unperturbed inputs, and the loss grows with…
Limit Theorems for Nearly Unstable Hawkes Processes 3: The Nearly Unstable Hawkes-Based Price Model Converges in Law to a Heston-Type ProcessResearch Paper
High-frequency prices move by discrete ticks, and successive moves are strongly correlated: an upward tick tends to be followed by a downward one. Bacry, Delattre, Hoffmann and Muzy (BDHM12, BDHM13b) proposed to model the upward and downward price jumps as the two components of a bidimensional Hawkes process, a pair of counting processes in which every…
An Introduction to Matrix Concentration Inequalities II: A Random Row-and-Column Submatrix Z = PBR Satisfies E‖Z‖² ≤ 3(p/d)(r/n)‖B‖² Plus Logarithmic Row, Column and Entry TermsTextbook
Large matrices are often reduced by retaining only some rows or columns. The reduced matrix is cheaper to store and apply, but its spectral norm can be distorted by a single unusually large row, column, or entry. A useful estimate must show both the average effect of sampling and the cost of these local concentrations. In §5.2 of Tropp's monograph, matrix…
Intrinsic Robustness of the Price of Anarchy II: Outcome Sequences with Vanishing Average Regret Have Average Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper
In a game, each participant chooses a strategy while the cost of that choice depends on what everyone else does. A network user may choose a route, for example, but its travel time depends on the routes chosen by other users. The price of anarchy compares the cost of self-interested outcomes with the best joint outcome. A guarantee restricted to a Nash…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights IV: For Strongly Convex f, f(X(t)) − f⋆ ≤ C‖x₀ − x⋆‖²/(μ^((α−2)/2) t^α) for 2 ≤ α ≤ 2r/3Research Paper
Accelerated gradient methods minimize smooth convex functions with a characteristic momentum term. Su, Boyd, and Candès identified a continuous-time differential equation whose trajectories model that acceleration. The equation replaces an iteration index by continuous time and makes the effects of damping visible. This mission concerns the paper's strongly…
Relatively Smooth Convex Optimization by First-Order Methods, and Applications II: The Dual Averaging Scheme Attains min_{i≤k} f(x^i) − f(x) ≤ μh(x)/((1+μ/(L−μ))^k − 1) ≤ (L−μ)h(x)/kResearch Paper
Classical complexity bounds for first-order methods assume that the gradient of the objective is Lipschitz continuous, or that the objective is strongly convex, with respect to a norm. Many convex problems of practical interest satisfy neither assumption: the objective of D-optimal experimental design, −lndet(∑ixiaiai⊤), has a gradient that…
An Introduction to Matrix Concentration Inequalities I: A Matrix Gaussian Series Satisfies v(Z) ≤ E‖Z‖² ≤ 2v(Z)(1 + log(d₁ + d₂))Textbook
Random matrices arise when observations, signs, or model coefficients fluctuate. Their spectral norm measures the largest amplification they can cause to a vector. A bound on that norm can turn entrywise randomness into a statement about the behavior of an entire linear operator. Tropp's chapter develops a common framework for Gaussian and Rademacher sums…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights I: The ODE Ẍ + (3/t)Ẋ + ∇f(X) = 0 with X(0) = x₀, Ẋ(0) = 0 Has a Unique Global SolutionResearch Paper
Nesterov’s accelerated gradient method is a discrete procedure for minimizing a smooth convex function. Its iterates use both a gradient step and a momentum term, so the position at the next step depends on recent motion as well as on the current gradient. Su, Boyd, and Candès study a continuous-time model of that behavior: a trajectory whose acceleration…