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.
K-Adaptability in Two-Stage Robust Binary Programming 4: The ε-Approximations (6ε) Converge Uniformly to the K-Adaptability ProblemResearch Paper
Two-stage robust optimization models decisions taken in two steps around an uncertain parameter: a here-and-now decision x is fixed before the parameter ξ is revealed, and a wait-and-see decision y adapts to it, and the decision maker guards against the worst ξ in an uncertainty set Ξ. When the second-stage decisions are binary, as in routing,…
Isoperimetric Inequalities in Simplicial Complexes 1: For a Finite d-Complex with a Complete Skeleton, the Spectral Gap Is at Most the Cheeger Constant, λ(X) ≤ h(X)Research Paper
For a finite graph, the Cheeger constant measures how hard it is to cut the vertex set into two pieces, and the spectral gap of the graph Laplacian measures how fast random walks mix. The two Cheeger inequalities (Dodziuk 1984; Alon and Milman 1985; Alon 1986) bound each quantity by a function of the other, and they underlie the theory of expander graphs,…
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints II: Gradients of m-Strongly Convex Functions with L-Lipschitz Gradient Satisfy the Weighted Off-by-One ρ-Hard IQCResearch Paper
First-order methods (gradient descent, Nesterov's accelerated method, the Heavy-ball method) are the workhorses of large-scale convex optimization, and their worst-case convergence rates on smooth strongly convex functions are classical objects of study. Lessard, Recht and Packard (arXiv:1408.3595v7, SIAM J. Optim. 26(1), 2016, doi:10.1137/15M1009597)…
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints III: Heavy-Ball Tuned for Quadratics Converges to a 3-Cycle, Not the Minimizer, of a Strongly Convex f with L/m = 25Research Paper
The Heavy-ball method of Polyak, xk+1=xk−α∇f(xk)+β(xk−xk−1), adds a momentum term to gradient descent. On strongly convex quadratics with curvature between m and L, a classical eigenvalue analysis gives the step size and momentum that minimise the worst-case linear rate, α=4/(L+m)2 and …
Distributionally Robust Joint Chance Constraints with Second-Order Moment Information II: Over Scaling Parameters, Worst-Case CVaR Is Essentially Exact for Joint Chance ConstraintsResearch Paper
A chance constraint asks that a decision x∈Rn satisfy uncertain inequalities with high probability. In the setting of Zymler, Kuhn and Rustem (Math. Program. 137, 2013), m affine inequalities yi0(x)+yi(x)⊤ξ~≤0, whose coefficients depend affinely on x, must hold jointly with probability at least 1−ϵ. Joint chance constraints…
Distributionally Robust Convex Optimization III: The Lifting Theorem — a Conic Bound on E[g(z̃)] Describes Exactly the z̃-Marginals of a Lifted Ambiguity SetResearch Paper
Distributionally robust optimization asks a decision to perform well against every probability distribution in an ambiguity setP, a family of distributions consistent with partial information about an uncertain parameter z~∈RP. Which kinds of information an ambiguity set can encode decides which models a solver can handle.…
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…
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…