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 Modern Introduction to Online Learning II: Online-to-Batch Conversion Turns a Regret Bound into a Risk Bound with Deviation 2√(2 ln(2/δ)/T)Textbook
An online learning algorithm chooses a decision before seeing each round's data and is judged by regret: how much more loss it incurs than a fixed decision chosen in hindsight. Statistical learning asks a different question. After seeing data drawn from a distribution, how small is the decision's expected loss on another draw? Chapter 3 of Orabona's textbook…
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition III: Randomized Coordinate Descent Has Expected Rate (1 − μ/(dL))^kResearch Paper
Coordinate descent changes one component of a parameter vector at a time. This matters when evaluating or updating a single component is cheaper than handling the full vector, for example in problems with sparse features. The coordinate chosen at each step can be random or selected from the current gradient. Karimi, Nutini, and Schmidt study these choices…
Joint Assortment Optimization and Customization under a Mixture of Multinomial Logit Models 2: Customization Raises the Optimal Expected Revenue by at Most a Factor m, and the Factor Is TightResearch Paper
An assortment decision determines which products a seller makes available to a customer. When customers differ, the seller may first choose a limited collection of products and then decide which of those products to display to each arriving customer. This is a concrete way to represent personalized product pages or offers with a common inventory or display…
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition II: SC → ESC → WSC → RSI → EB ≡ PL → QG, and RSI ≡ EB ≡ PL ≡ QG for Convex fResearch Paper
Gradient descent on a smooth function f:Rd→R converges at a linear rate (the optimality gap shrinks by a constant factor each step) under strong convexity. Many problems in machine learning and statistics are not strongly convex: least squares with a rank-deficient design, logistic regression on separable or degenerate data, and some…
Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 2: Positive Combinations Preserve the Balance Condition When Production and Consumption Sets Are DisjointResearch Paper
Stochastic models of chemical reaction networks in cell biology routinely combine species present in a handful of copies with species present in thousands, and rate constants that differ by orders of magnitude. Simulating such a system exactly is expensive, and model reduction replaces it with a lower-dimensional limit. A systematic approach, developed by Ba…
Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 3: The Second Time-Scale r₂ Is Strictly Slower than the First Time-Scale r₁Research Paper
Chemical reaction networks can contain reactions whose rates differ by powers of a large scaling parameter. A species may then change on one time scale while other combinations of species remain nearly fixed until a later one. This matters when replacing a detailed network by a smaller model: the quantities retained at the first scale need not be the…
Learning without Concentration: Least-Squares ERM in a Convex Class Is Within 2 max{α_N(γ, δ/4), βN(τQ{F−F}(2τ)/16)} of f* in L₂ under a Small-Ball ConditionResearch Paper
Least-squares regression over a class of functions is the basic problem of statistical learning theory: given an i.i.d. sample (Xi,Yi)i=1N from an unknown joint law, select a function in a class F whose prediction error E(f(X)−Y)2 is close to the best possible in F. The standard analysis of empirical risk minimization (ERM) compares empirical…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights III: The Generalized Nesterov Scheme Has f(x_k) − f⋆ ≤ (r − 1)²‖x₀ − x⋆‖²/(2s(k + r − 2)²)Research Paper
Nesterov's accelerated gradient method minimizes a smooth convex function with an error of order 1/k2 after k steps, against 1/k for plain gradient descent, and this rate is optimal among first-order methods. Its momentum coefficient (k−1)/(k+2) has long been regarded as delicate. Su, Boyd and Candès (arXiv:1503.01243, J. Mach. Learn. Res. 17(153), 2016)…
Intrinsic Robustness of the Price of Anarchy III: For Every Set of Cost Functions, Congestion Games Are Tight — the Worst-Case Pure Price of Anarchy Equals the Best Smoothness BoundResearch Paper
In a congestion game, each player chooses resources and pays a cost that depends on how many players use each chosen resource. Such games model shared facilities and network use, where independently chosen strategies can cost more in total than a coordinated choice. The price of anarchy measures this inefficiency by comparing the social cost of an…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights II: The ODE Solution Satisfies f(X(t)) − f⋆ ≤ 2‖x₀ − x⋆‖²/t²Research Paper
Nesterov's accelerated gradient method (Nesterov, 1983) minimizes a smooth convex function f with the update
Dynamic Type Matching: Under the Modified Monge Condition There Is an Optimal Matching Policy That Respects the Priority Relation ≻MsResearch Paper
Many platforms match two sides of a market over time: ride-hailing platforms match riders with drivers, blood banks match donated units with patients, organ allocation matches donors with recipients, and retailers pool inventory across fulfilment centres to serve orders from several regions. Demand and supply arrive in several types (locations, blood…
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition I: Gradient Descent with Step 1/L Satisfies f(x_k) − f* ≤ (1 − μ/L)^k (f(x_0) − f*)Research Paper
Gradient descent is often introduced with strong convexity as the condition that gives a geometric reduction in objective error. That condition excludes useful smooth objectives whose minimizer is not unique and some nonconvex objectives. Karimi, Nutini, and Schmidt place the Polyak–Łojasiewicz inequality at the center of a more general account: it controls…
A Solution to the 1-2-3 Conjecture: Every Finite Graph Without a K2 Component Has an Edge-Weighting from {1,2,3} Whose Weighted Degrees Properly Color the VerticesResearch Paper
Many graph-colouring questions ask whether a proper colouring can be produced indirectly, from local data, instead of being assigned vertex by vertex. In the 1-2-3 Conjecture, the colours are produced by weighting the edges of a graph and colouring each vertex with the sum of the weights at it. Karoński, Łuczak and Thomason asked in 2004 whether weights…
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition IV: Stochastic Gradient Rates LC²/(2kμ²) and (1 − 2μα)^k [f(x_0) − f*] + LC²α/(4μ)Research Paper
Stochastic gradient (SG) methods are the default algorithms for training machine-learning models: when an objective is an average over a very large number of training examples, computing its full gradient even a few times is infeasible, while the gradient of a single randomly chosen example is cheap. The classical convergence theory of SG rates its expected…
Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions III: The L²-Spectral Gap of Random Walk Metropolis for a Gaussian Target Vanishes Faster Than Any Power of the DimensionResearch Paper
Bayesian inverse problems and conditioned diffusions lead to probability measures on function spaces, and these are sampled in practice through finite-dimensional approximations on Rm with m large. A Markov chain Monte Carlo method is useful in this setting only if its convergence rate does not deteriorate as the discretisation is refined. Random…
The Statistical Complexity of Interactive Decision Making VII: Policy-Cover Inverse Gap Weighting Certifies dec_γ ≤ 95H³SA/γ for Tabular Reinforcement LearningResearch Paper
In episodic reinforcement learning, an agent learns the rewards and dynamics of a system while choosing actions that determine which states it observes. A bound on the number of states and actions alone does not prescribe how to explore: a policy can be valuable because it earns reward, because it visits an uncertain state-action pair, or both. Foster,…
Approximate Revenue Maximization with Multiple Items 4: Bundling k ≥ 2 I.I.D. Goods Guarantees a Fraction c/log k of the Optimal RevenueResearch Paper
A seller with several goods and a single buyer is the smallest setting in which multi-dimensional mechanism design differs from the one-good theory. For one good, Myerson's theorem (Myerson 1981) says the optimal mechanism posts a price. For two or more goods the optimal mechanism may use lotteries, may be non-monotone in the buyer's values, and is in…
Coexistence and Extinction for Stochastic Kolmogorov Systems 2: If a Boundary Ergodic Measure Is a Sink, then E(min_i X_i(t))^δ → 0 for Every Small δ > 0Research Paper
A population can disappear because its average growth rate is negative when it is rare, even if its deterministic dynamics would support coexistence. Interactions among several species make this harder to assess: a species may be rare while the remaining species fluctuate among several possible long-run configurations. Hening and Nguyen study this problem…
Coexistence and Extinction for Stochastic Kolmogorov Systems 1: If Every Boundary Ergodic Measure Repels, X Converges Exponentially Fast in Total Variation to a Unique Interior Stationary LawResearch Paper
Whether interacting species can coexist in a fluctuating environment is one of the basic questions of mathematical ecology. Deterministic models (Lotka–Volterra competition, predator–prey systems, food chains) answer it through invasion criteria: a population persists if, whenever it is rare, it grows. In a random environment the analogous criterion is…
Coexistence and Extinction for Stochastic Kolmogorov Systems 3: Almost Surely the Occupation Measures Settle on One Sink Measure µ, and Every Species Absent from µ Dies Out at Rate λ_i(µ) < 0Research Paper
Ecologists model interacting populations — competitors, predators and prey, food chains — by Kolmogorov systems, in which the growth of each species is proportional to its current abundance. Environmental fluctuations turn these into stochastic differential equations, and the basic question becomes which species persist and which go extinct. Hening and…
Approximate Revenue Maximization with Multiple Items 6: With n Buyers and Dominant-Strategy Implementation, Selling Two Independent Goods Separately Earns at Least Half the Optimal RevenueResearch Paper
A seller who owns several goods and faces buyers with private values must decide how to sell them. The revenue-maximizing mechanism is known in closed form only for one good: for a single buyer it is a posted price, and for several buyers it is Myerson's optimal auction (Myerson 1981). With two or more goods the optimal mechanism may use lotteries, may be…
Approximate Revenue Maximization with Multiple Items 3: Selling k ≥ 2 Independent Goods Separately Guarantees a Fraction c/log² k of the Optimal RevenueResearch Paper
A seller who knows the distributions of a buyer's values for several goods can, in principle, design a mechanism that offers lotteries and prices conditional on the buyer's reported values. Finding the best such mechanism can be difficult even with two goods. Separate selling is much simpler: choose a one-good price for each item and let the buyer decide…
Cycle Lengths in Expanding Graphs 2: Every α-Expander on n Vertices Has Ω(α³/log(1/α))·n Distinct Cycle LengthsResearch Paper
An expander graph has many edges leaving each small vertex set. This condition is useful when a graph must remain connected after local losses, and it also constrains the cycles that can occur. Knowing that one long cycle exists leaves open how many different lengths its cycles can have. For example, a bipartite graph has no odd cycle, so expansion alone…
The Statistical Complexity of Interactive Decision Making VI: Posterior Sampling Bounds the Dual DEC of Tabular Reinforcement Learning by 26H²SA/γResearch Paper
In episodic reinforcement learning, an agent acts repeatedly in an unknown system and must learn which policy earns the largest expected reward. Even when states and actions are finite, the agent's choices change which data it observes. Foster, Kakade, Qian, and Rakhlin use the decision-estimation coefficient (DEC) to connect this information constraint to…
The Statistical Complexity of Interactive Decision Making IV: Log-Loss Regret Controls Hellinger Estimation Error, Est_H ≤ Reg_KL + 2 log(1/δ) with Probability 1−δResearch Paper
Interactive decision methods often need an estimate of an unknown outcome law after each round. A learner can be good at decisions only if its model of the observations is accurate where future decisions will sample. Foster, Kakade, Qian and Rakhlin measure this accuracy by a cumulative squared Hellinger distance and use it in their regret bounds for…