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.
Online Learning and Online Convex Optimization 1: Follow-the-Regularized-Leader with a σ-Strongly-Convex Regularizer Has Regret at Most R(u) − min R + TL²/σResearch Paper
Online convex optimization is a repeated game between a learner and an environment. In each round the learner commits to a vector, the environment then reveals a convex loss function, and the learner pays the loss of its vector. No statistical assumption is made about how the losses are generated; they may be chosen adversarially. Performance is measured…
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 2: On a Regularized Objective, RCDM(1, x₀) Finds an ε-Solution with Probability ≥ β Within the Iteration Bound (3.11)Research Paper
Randomized coordinate descent updates one block of variables per iteration, chosen at random. For problems whose dimension makes even one full gradient expensive (the "huge-scale" problems of the title, such as sparse least squares or truss topology design), a coordinate step can cost a tiny fraction of a gradient step. Nesterov's paper (CORE Discussion…
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 2: For F Smooth at the Optimum, SGD's Last and Averaged Iterates Attain 2µG²/(λ²T) and 16µG²/(λ²T)Research Paper
Stochastic gradient descent (SGD) is the standard method for minimizing an expected loss F(w)=Ez[ℓ(w,z)] when only noisy gradients are available: in machine learning, w is a predictor, z a random example, and each step uses the gradient of the loss on one fresh example. When F is strongly convex, as for regularized learning problems such as…
Load balancing on identical parallel links is the example Koutsoupias and Papadimitriou used to define the price of anarchy: the ratio of the social cost of a Nash equilibrium to the social optimum (Koutsoupias–Papadimitriou 2009). Theorem 3 of the journal version is the two-link case. It is the first sharp bound in that paper, and the later two-speed bound…
Matroid Prophet Inequalities 2: On an Intersection of p Matroids, the Summed-Threshold Algorithm Earns at Least 1/(4p−2) of the Expected OptimumResearch Paper
A prophet inequality compares a gambler who sees independent random rewards one at a time, and must accept or reject each on arrival, with a prophet who sees all rewards in advance. The classical inequality of Krengel, Sucheston and Garling (1977–78, as cited in the paper) says that when only one reward may be kept, a single threshold rule earns at least…
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 1: Random Block Coordinate Descent RCDM(α, x₀) Has Expected Error at Most 2·S_α·R²_{1−α}(x₀)/(k + 4)Research Paper
Many large optimization problems arising in machine learning, statistics and network analysis have so many variables that computing a single full gradient is already expensive, while a single partial derivative, or a gradient with respect to a small block of variables, is cheap. Coordinate descent methods exploit this: at each iteration they update one…
Distributed Verification and Hardness of Distributed Approximation: Simulation Theorem — Time R < (dᵖ−1)/2 on G(Γ,d,p) with B-Bit Messages Gives an ε-Error Two-Party Protocol with 2dpB·R BitsResearch Paper
In distributed computing, many graph problems (minimum spanning tree, shortest paths, connectivity checks) are solved by processors that sit at the vertices of the input network and communicate only along its edges. When every edge can carry only a few bits per round, the number of rounds an algorithm needs can be far larger than the network's diameter.…
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets 2: For n ≥ 8L/μ, SAG with Step 1/(2nμ) after an SG Warm Start Converges at Rate (1 − 1/(8n))ᵏResearch Paper
Many problems in machine learning are finite-sum problems: minimize the average of n loss functions, one per training example,
Synchronization and Transient Stability in Power Networks and Nonuniform Kuramoto Oscillators 2: λ₂(L(P_ij cos φ_ij)) > λ_critical Gives Phase Cohesiveness and Exponential Frequency SynchronizationResearch Paper
Transient stability of a power grid asks whether the generators of the network return to synchronous operation after a large disturbance such as a fault or a line trip. In the classical network-reduced model the rotor angles obey second-order swing equations, and stability certificates usually come from energy functions evaluated numerically. Dörfler and…
New Proofs of Plünnecke-type Estimates for Product Sets in Groups 2: If |BB| ≤ α|B| and |BbB| ≤ β|B| for All b ∈ B, Then |Bʰ| ≤ α^(8h−17) β^(h−2) |B| for Every h > 2Research Paper
Plünnecke-type inequalities turn information about a set and one product (or sum) of it into bounds on all of its iterated products. In an abelian group, Plünnecke's theorem (Plünnecke 1970) and its extension by Ruzsa say that ∣A+A∣≤α∣A∣ implies ∣hA∣≤αh∣A∣ for every h. Such bounds are a basic tool in additive combinatorics, and their…
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 3: SGD with Full Averaging Suffers an Ω(log(T)/T) Rate on a Non-Smooth Strongly Convex ProblemResearch Paper
Stochastic gradient descent (SGD) is the standard first-order method for stochastic convex optimization and for training linear predictors on large data sets: at each step it queries a noisy subgradient of the objective, takes a step against it and projects back onto the feasible set. When the objective is strongly convex, the classical online-learning…
Nonsmooth Optimization via Quasi-Newton Methods III: The Secant Method on |x| Generates the Alternating Binary Expansion of x₀Research Paper
Quasi-Newton methods such as BFGS were designed for smooth objectives, yet in practice they are routinely run on nonsmooth functions and they often work well there: on many nonsmooth problems the iterates converge to a minimizer at a linear rate, measured against the total number of function evaluations. Lewis and Overton (Math. Program. 141 (2013) 135–163)…
New Proofs of Plünnecke-type Estimates for Product Sets in Groups 3: If |AB| ≤ α|A|, |AbB| ≤ β|A| for b ∈ B and |A| ≤ γ|B|, Some S ⊆ A Has |SBʰ| ≤ α^(8h−9) β^(h−1) γ^(4h−5) |S| for h > 1Research Paper
Plünnecke–Ruzsa inequalities bound the size of iterated sumsets: if A and B are finite subsets of an abelian group with ∣A+B∣≤α∣A∣, then ∣hB∣≤αh∣A∣ for every h, where hB=B+⋯+B. They are a basic tool of additive combinatorics, used in Freiman-type structure theorems, sum–product estimates and the study of approximate groups.…
Nonsmooth Optimization via Quasi-Newton Methods I: With an Exact Line Search on the Euclidean Norm in ℝ², Quasi-Newton Iterates Converge Q-Linearly at Rate 1/2, Turning by π/3Research Paper
Quasi-Newton methods, BFGS above all, are the standard tool for smooth unconstrained minimization. They are also used directly on nonsmooth functions, where in practice they often converge to stationary points with linearly converging function values; the paper documents applications such as the design of low-order controllers (Lewis–Overton 2013, abstract…
Quantity Flexibility Contracts and Supply Chain Performance 1: Under the Minimum Commitment Policy a Flex Node With At Least Its Customer's Flexibility Keeps Zero InventoryResearch Paper
Manufacturers and their suppliers rarely trade on fixed orders. A buyer sends a rolling schedule of intended purchases for the coming periods and revises it every period as its own forecasts change. Left unconstrained, such revisions pass demand volatility up the supply chain and amplify it, the phenomenon studied as the bullwhip effect (Lee, Padmanabhan &…
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 3: Low-Influence Functions Have Level-One Fourier Weight at Most 2/π + CδResearch Paper
Fourier analysis of functions on the discrete cube {−1,1}n is the main tool behind tight inapproximability results under the Unique Games Conjecture. In the MAX-CUT reduction of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comput. 2007), soundness rests on the Majority Is Stablest theorem: among bounded functions in which no coordinate has large…
Spectral Sparsification of Graphs 3: Sparsifying the Contraction and Pulling It Back Approximates a Graph with Heavy Intra-Part Edges to Within (1+ε)(1+1/c)²Research Paper
A spectral sparsifier of a weighted graph G is a graph G on the same vertices, with few edges, whose Laplacian quadratic form is within a factor σ of that of G on every vector. Spielman and Teng introduced the notion in their work on nearly-linear-time solvers for symmetric diagonally dominant linear systems (Spielman–Teng 2004; arXiv:0808.41…
On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues: If m > k(n − k), Extreme Optima of Affine EV_k Have λ_k = λ_{k+1} with Multiplicity ≥ n − τResearch Paper
Minimizing the sum of the k largest eigenvalues of a symmetric matrix that depends affinely on parameters is a basic problem of eigenvalue optimization (survey: A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica 5, 1996, doi:10.1017/S0962492900002646). Its objective is convex, and fk is differentiable at B exactly when …
New Techniques for Noninteractive Zero-Knowledge 4: The Decisional-Linear Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper
A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. Groth, Ostrovsky and Sahai (J. ACM 59(3), 2012) gave NIZK proofs for Circuit SAT of size O(∣C∣k) for a circuit C and security parameter k, the first perfect NIZK arguments for all of NP, and…
A Single-Item Inventory Model for a Nonstationary Demand Process: With Adaptive Base-Stock Control at Two Stages, Upstream Inventory Is N(y₀, σ²∑_{i<K}(1+(L+i)α)²)Research Paper
New Techniques for Noninteractive Zero-Knowledge 3: The Subgroup-Decision (BGN) Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper
A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. NIZK proofs are a basic building block of public-key cryptography: chosen-ciphertext secure encryption, signature schemes and secure multi-party computation all use them. Groth, Ostrovsky and…
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis: Bernoulli Thompson Sampling Has Regret (1+ε)Σ Δ_a(ln T + ln ln T)/K(μ_a, μ*) + CResearch Paper
Thompson Sampling is the oldest bandit algorithm: Thompson proposed it in 1933 for allocating patients between two treatments (Thompson 1933). It keeps a posterior distribution over the unknown mean reward of every action, draws one sample from each posterior, and plays the action whose sample is largest. It is simple, widely used, and in experiments…
Spectral Sparsification of Graphs 1: Sampling Each Edge of a High-Conductance Graph with Probability min(1, Υ/min(dᵢ, dⱼ)) Gives a (1+ε)-Spectral Approximation with Few EdgesResearch Paper
A spectral sparsifier of a graph is a much sparser weighted graph whose Laplacian quadratic form is within a factor σ of the original on every vector. Spielman and Teng introduced the notion in Spectral Sparsification of Graphs as a strengthening of the cut sparsifiers of Benczúr and Karger: a spectral sparsifier preserves every cut, and in addition…
A Note on Probability Distributions with Increasing Generalized Failure Rates II: For IGFR X with Support (α, ∞) and g(ξ) → κ, E[Xⁿ] Is Finite iff κ > nResearch Paper
Many models in operations management and economics need the demand or valuation distribution to be regular in some way, so that an optimal price, order quantity or contract is unique. Pricing a service to one customer whose valuation X has survival function Φˉ is a typical example. The seller maximizes pΦˉ(p). The first-order condition is …
AdWords and Generalized On-line Matching I: The Tradeoff Algorithm with ψ_k(i) = Σ_{j≥i} y*_j Is (1 − 1/e)-Competitive as k → ∞ When Bids Are SmallResearch Paper
Search engines sell advertising space query by query. Each advertiser states a bid for each keyword and a daily budget; queries arrive one at a time, and each must be assigned to an advertiser immediately, without knowledge of the queries still to come. The revenue-maximizing assignment of the day can only be computed offline. The adwords problem asks how…