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.
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…
Self-Scaled Barriers and Interior-Point Methods for Convex Programming IV: The Predictor-Corrector Path-Following Scheme Keeps π(τ, x) ≤ 1/4 and Multiplies τ by at Least 1 + 3/(8√ν + 2)Research Paper
Interior-point methods solve linear, second-order cone and semidefinite programs by following a smooth curve through the interior of the feasible region. Nesterov and Nemirovskii (1994) showed that the right object to build such methods on is a self-concordant barrier for the cone, and that the number of Newton steps needed by a path-following method is…
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…
Optimality of (s, S) Policies in Inventory Models with Markovian Demand II: In the Nonstationary Discounted Infinite-Horizon Problem, a State-Dependent (s, S) Policy Is OptimalResearch Paper
Periodic-review inventory models with a fixed ordering cost are the setting in which the (s,S) policy is optimal: when the stock falls below a reorder point s, order up to a level S, otherwise order nothing. Scarf (1960) proved this for independent demands over a finite horizon by introducing K-convexity, and Iglehart (1963) extended it to the discounted…
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 …