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 XV: Online Learning Bounds Rademacher Complexity, Giving Massart's Lemma G∞√(2 ln d)/√TTextbook
Learning theory asks whether a rule that fits an observed sample will also perform well on future observations. A class with many functions can fit accidental patterns in the sample, so its size and geometry affect the reliability of empirical risk estimates. Empirical Rademacher complexity measures this ability to fit noise: attach an independent random…
A Modern Introduction to Online Learning X: The Weighted Average Algorithm with a Uniform Prior Has Regret (d/α)(1 + ln(T/d + 1)) on α-Exp-Concave LossesTextbook
Online prediction compares the losses of a sequence of decisions with the losses of one fixed decision chosen after the sequence is known. A learner would like a regret guarantee that remains valid for every such competitor, even when the losses arrive in an arbitrary order. Exponentially weighted averaging is a way to make each decision from all feasible…
Isotropic Gaussian Random Fields on the Sphere: Regularity, Fast Simulation and Stochastic Partial Differential Equations I: u ∈ V^η(−1,1) iff Σ u_ℓ²(2ℓ+1)(1+ℓ^{2η}) < ∞Research Paper
A centered isotropic Gaussian random fieldT on the unit sphere S2 is determined by its angular power spectrum(Aℓ)ℓ≥0: its covariance is
A Modern Introduction to Online Learning XIV: Optimistic FTRL Self-Play on a Smooth Convex-Concave Function Has Duality Gap at Most a Constant over TTextbook
A saddle-point problem asks one player to choose a decision that keeps a payoff small while another chooses a decision that makes it large. Such problems include two-player zero-sum games and constrained optimization written through a Lagrangian. Online convex optimization supplies a way to construct approximate saddle points from repeated play: each player…
A Modern Introduction to Online Learning VI: Follow-the-Regularized-Leader with a µ-Strongly Convex Regularizer Has Regret ((ψ(u) − min ψ)/α + α)·L√T/√µTextbook
In online convex optimization, a learner chooses a point before seeing the loss assigned to that round. Its performance is measured against a fixed point that could have been chosen after the full sequence became known. A learner that merely minimizes accumulated past losses can react sharply when successive losses favor different points. Follow-the-Regulari…
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…