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.
Martingale Proofs of Many-Server Heavy-Traffic Limits for Markovian Queues 1: The Centered and √n-Scaled M/M/∞ Queue Converges in D to an Ornstein–Uhlenbeck ProcessResearch Paper
Large service systems (call centers, hospital wards, cloud server pools) run with many servers, and for many of them no exact formula describes how the number of busy servers moves over time. Heavy-traffic limits replace such a system by a diffusion process that is easier to analyze. The many-server regime, in which the number of servers and the arrival…
Basic Packing of Arborescences: A Digraph with Roots Has an M-Basic Packing of Arborescences iff π Is M-Independent and D Is M-ConnectedResearch Paper
Packing arc-disjoint arborescences is one of the basic tractable problems of combinatorial optimization. Edmonds' branching theorem (1973) says that a digraph D=(V,A) contains k arc-disjoint spanning arborescences rooted at a vertex r if and only if every non-empty vertex set X⊆V∖r is entered by at least k arcs. Its undirected counterpart…
Sample Size Selection in Optimization Methods for Machine Learning 1: With Batch Sizes n_k ≥ a^k, Dynamic Batch Steepest Descent Converges Linearly in Expectation, E[J(w_k) − J(w*)] ≤ Cρ^kResearch Paper
Training a model in machine learning means minimizing an expected loss over a data distribution, using a finite sample from it. Two families of methods dominate. Stochastic gradient methods step along the gradient of the loss at one data point: each step is cheap, but the noise forces small steps and many sequential iterations. Batch methods average the…
On the (Im)possibility of Obfuscating Programs 1: A Decidable Promise Problem Closed under Functional Equivalence Is Decided by a Simulator Given Only Oracle Access to ⟨M⟩ and the Size 1^|M|Research Paper
Program obfuscation asks for a compiler that turns a program into one computing the same function while revealing nothing beyond what black-box access to the function reveals. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012; conference version CRYPTO 2001) showed that this "virtual black box" notion cannot be achieved in…
Sample Size Selection in Optimization Methods for Machine Learning 2: Steepest Descent with Gradient Error ‖g_k − ∇J(w_k)‖ ≤ θ‖g_k‖ Contracts J by 1 − βλ/L per StepResearch Paper
Training a machine-learning model usually means minimizing an expected or empirical loss J(w) over parameters w∈Rm. Exact gradients of such objectives are expensive, because each one requires a pass over the whole data set; practical methods replace ∇J(wk) by a cheaper approximation gk, for instance a gradient computed on a subsample.…
On Augmented Lagrangian Methods with General Lower-Level Constraints II: Feasible Limit Points Satisfying CPLD Are KKT PointsResearch Paper
Augmented Lagrangian methods are among the standard ways to solve smooth nonlinear programs. They replace a constrained problem by a sequence of subproblems in which some constraints are moved into the objective through a penalty term and multiplier estimates. The method of Andreani, Birgin, Martínez and Schuverdt (SIAM J. Optim. 18(4), 2007) is the theory…
On the Convergence of the Proximal Algorithm for Nonsmooth Functions Involving Analytic Features: Bounded Proximal Sequences of Łojasiewicz Functions Have Finite Length and a Critical LimitResearch Paper
The proximal algorithm is the basic implicit scheme for minimizing a function f: from the current point xk it moves to a minimizer of f plus a quadratic penalty on the distance travelled. For convex f its convergence theory is classical (Martinet 1970, Rockafellar 1976). For nonconvex, nonsmooth f the situation is different: descent and boundedness give…
On Augmented Lagrangian Methods with General Lower-Level Constraints I: Bounded Penalties Give Feasible Limit Points; Otherwise KKT for the Infeasibility Problem or CPLD FailsResearch Paper
Augmented Lagrangian methods (the method of multipliers of Hestenes, Powell and Rockafellar) solve a constrained nonlinear program by a sequence of easier subproblems in which some constraints are moved into the objective through a penalty term plus a multiplier estimate. Andreani, Birgin, Martínez and Schuverdt (SIAM J. Optim. 18 (2007); preprint HAL…
Hardness of Approximating Flow and Job Shop Scheduling Problems 1: Every Schedule of the Flow Shop Instance F(r,d) Has Makespan at Least min(r, d/4)·lbResearch Paper
In shop scheduling, jobs consist of chains of operations, each to be processed on a prescribed machine, and the goal is to minimize the makespan, the time at which the last operation finishes. Almost every approximation algorithm for job shops, acyclic job shops and flow shops is analysed against one quantity: the trivial lower boundlb=max(C,D),…
Spectral Sparsification of Graphs 2: Every Graph with m Edges Has a (6 log_{4/3} 2m)⁻¹-Conductance Decomposition Cutting at Most Half of Its EdgesResearch Paper
A sparse graph that approximates a dense one, in the sense that both have nearly the same Laplacian quadratic form, can stand in for it in every algorithm that only reads cuts or solves Laplacian linear systems. Spielman and Teng introduced such spectral sparsifiers and built them in nearly linear time; the construction is the sparsification step of their…
Graph Sparsification by Effective Resistances 1: Sampling O(n log n/ε²) Edges by Effective Resistance Yields a (1±ε) Spectral Sparsifier with Probability 1/2Research Paper
Many graph algorithms run in time proportional to the number of edges. A sparsifier of a weighted graph G is a graph H on the same vertices with far fewer edges that approximates G for the purpose at hand, so that the algorithm can be run on H instead. Benczúr and Karger (1996) showed that every graph has a sparsifier with O(nlogn/ε2) edges…
Efficient Algorithms for Online Decision Problems 3: Follow the Lazy Leader (FLL, FLL*) Matches FPL, FPL* in Expectation Each Period and Updates with Probability at Most εAResearch Paper
In an online linear decision problem a decision maker chooses, on each period t=1,2,…, a decision dt from a set D⊂Rn, and only then learns a state vector st∈S⊂Rn and pays the cost dt⋅st. The online shortest path problem, the experts problem, online binary search trees and list update…
Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization 2: With Random Recourse, the SDP (3.14) Conservatively Approximates the Linear Decision Rule Problem, Exactly for l = 1Research Paper
In a one-stage stochastic program a decision maker observes a random outcome ξ and then picks a decision x(ξ), subject to constraints that depend on ξ, so as to minimize expected cost. The optimization variable is a whole function x, and computing the optimal value is #P-hard even for a uniform distribution on the unit cube (Dyer and Stougie, 2006,…
Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion 2: If λ ≥ 3‖M‖∞ on a Linear Subspace, a Sharp Oracle Inequality with the Restricted Constant μ₅(A)Research Paper
Estimating a large matrix that is approximately low rank from a few noisy linear measurements is a basic problem of high-dimensional statistics. It covers matrix completion (recovering a ratings table from a small sample of entries), multi-task regression and quantum state tomography. The standard estimator penalizes the nuclear norm, the sum of the…
Stochastic Machine Scheduling with Precedence Constraints 1: LP-Based Delayed List Scheduling Is a (1 + β)(1 + 1/β + max{1, (m − 1)Δ/m})-Approximation for P|r_j, prec|E[Σ w_j C_j]Research Paper
Scheduling jobs whose processing times are not known in advance is a basic problem of production planning, project management and computing systems. In the stochastic machine scheduling model only the distribution of each processing time is known beforehand; the actual duration of a job is revealed when the job completes. A solution is then not a schedule…
Conditional Risk Mappings: A Positively Homogeneous Lower Semicontinuous Conditional Risk Mapping Is the Supremum of Countably Many Conditional ExpectationsResearch Paper
Risk measures quantify the danger of an uncertain cost X by a single number. The axiomatic theory of coherent and convex risk measures (Artzner, Delbaen, Eber and Heath, Coherent measures of risk, 1999; Föllmer and Schied, Convex measures of risk and trading constraints, 2002) is static: the risk is evaluated once, with no information beyond what is known…
Efficient Algorithms for Online Decision Problems 2: For Nonnegative Decisions and States, FPL*(ε/2A) Has Expected Cost at Most (1 + ε)·min-cost_T + 4AD(1 + ln n)/εResearch Paper
Many sequential decision problems have a combinatorial decision set and a linear cost: choosing a path in a graph whose edge delays change every day, choosing a binary search tree for a stream of requests, or choosing one of n experts whose losses are revealed after each round. Classical weighted-majority algorithms keep one weight per decision, which is…
Efficient Algorithms for Online Decision Problems 1: Follow the Perturbed Leader FPL(ε) Has Expected Cost at Most min-cost_T + εRAT + D/εResearch Paper
In an online decision problem a decision maker chooses actions one period at a time, and only after each choice learns what that choice cost. The classical instance is prediction with expert advice: each day one of n experts is followed, and afterwards every expert's loss is revealed. The goal is a strategy whose total cost is close to that of the best…
Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 3: With N = k Variables Fixed and Equal Population Eigenvalues, √M(λ₁ − ℓ₁)/ℓ₁ Converges to G_kResearch Paper
Principal component analysis estimates the eigenvalues of a population covariance matrix Σ by those of the sample covariance matrixS. Before random matrix theory turned to the regime where the dimension grows with the sample size, the classical question was the opposite one: the number of variables N is fixed and the number of samples M tends to…
Theoretical and Numerical Comparison of Relaxation Methods for Mathematical Programs with Complementarity Constraints 2: MPEC-MFCQ Implies MFCQ for the Scholtes Relaxed Problems LocallyResearch Paper
A mathematical program with complementarity constraints (MPEC, also called MPCC) is a nonlinear program in which some pairs of constraint functions must be nonnegative with at least one of each pair equal to zero. Such programs model bilevel optimization, Stackelberg games, contact problems in mechanics, and traffic equilibrium design; see Luo, Pang and…
Randomized quasipolynomial-time mean-payoff gamesOpen Problem
Mean-payoff games ask which starting positions allow a player to guarantee a nonnegative long-run average reward. Binary-encoded weights make the bit cost of solving the complete winning set a central part of the question. The source manuscript presents the surrounding research claim.
Theoretical and Numerical Comparison of Relaxation Methods for Mathematical Programs with Complementarity Constraints 1: Scholtes Relaxation Limits Are C-Stationary under MPEC-MFCQResearch Paper
A mathematical program with complementarity constraints (MPCC, also called MPEC, mathematical program with equilibrium constraints) is a nonlinear optimization problem in which some pairs of constraint functions must be nonnegative with at least one of each pair equal to zero. Such constraints model equilibria inside an optimization problem: bilevel…
What Can We Learn Privately? V: Masked Parity Is Learnable by Adaptive but Not by Nonadaptive Statistical Queries Under the Uniform DistributionResearch Paper
In the local model of differential privacy, each individual randomizes their own data before handing it to an untrusted learner. Local protocols are the deployed form of private data collection, and in practice every round of interaction with the population is expensive: the learner must broadcast new instructions and wait for new reports. Kasiviswanathan,…
Flows and Decompositions of Games: Harmonic and Potential Games 4: Changing Only the Nonstrategic Component Makes the Pure Nash Equilibria Coincide with the Pareto Optimal ProfilesResearch Paper
A finite strategic game can be changed in ways that no player can detect strategically. Adding to player m's utility any function that does not depend on player m's own strategy leaves every unilateral comparison "is strategy a better for me than strategy b, given what the others do?" unchanged, so it leaves every best response and every pure Nash…
What Can We Learn Privately? IV: Any ε-Local Algorithm Is Simulated by a Statistical Query Algorithm with O(t·e^ε) Expected Queries up to Statistical Difference βResearch Paper
In the local model of differential privacy, no trusted curator holds the data: each individual randomizes their own record before handing it to the analyst. This is the model of randomized response in survey statistics and of the privacy-preserving telemetry deployed by large software vendors. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can…