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.
Minimax Statistical Learning with Wasserstein Distances II: Excess Local Minimax Risk of Wasserstein ERM for a Uniformly Lipschitz ClassResearch Paper
In statistical learning a hypothesis f is chosen from a class F using n samples drawn from an unknown distribution P, and its quality is measured by the riskR(P,f)=EP[f(Z)]. When the distribution at deployment time may differ from the one that generated the data (domain drift, adversarial perturbation, model misspecification), a natural…
Probabilistic Analysis of Mean-Field Games 2: The Mean-Field Strategies Form an ε_N-Nash Equilibrium of the N-Player Game, with ε_N ≤ cN^{−1/(d+4)}Research Paper
Mean-field games were introduced by Lasry and Lions (2007) and by Huang, Malhamé and Caines (2006) as limits of stochastic differential games with many symmetric players, each interacting with the others only through the empirical distribution of their states. The limit replaces a game of N coupled players by one representative player facing a deterministic…
Probabilistic Analysis of Mean-Field Games 1: The McKean–Vlasov FBSDE of a Convex Mean-Field Game Has a Solution, with a Lipschitz FBSDE Value FunctionResearch Paper
A mean-field game describes a population of agents whose individual dynamics and costs depend on the distribution of the population's states. In a large population, an individual agent has negligible influence on that distribution but still responds to it. The mathematical problem is to find a control whose induced state law agrees with the distribution…
From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 2: For Convex Functions, KL Inequalities Give Error Bounds and Moderate Error Bounds Give KL InequalitiesResearch Paper
Complexity bounds for first-order methods (proximal gradient, forward–backward splitting, alternating minimization) rest on a quantitative description of how a function grows away from its set of minimizers. Two such descriptions are in common use. An error bound controls the distance to the minimizers by the function value; a Kurdyka–Łojasiewicz (KL)…
On a Perturbation Theory and on Strong Convergence Rates for Stochastic Ordinary and Partial Differential Equations with Nonglobally Monotone Coefficients: Stopped-Tamed Euler Converges at Rate 1/2Research Paper
Stochastic differential equations (SDEs) dXt=μ(Xt)dt+σ(Xt)dWt model physical, biological and financial systems whose drift μ often grows superlinearly: the stochastic Lorenz equation, the stochastic van der Pol and Duffing–van der Pol oscillators, Langevin dynamics. Solutions are rarely explicit, so they are simulated by time-stepping…
User-Friendly Tail Bounds for Sums of Random Matrices III: The Matrix Chernoff Inequality for Sums of Independent Positive-Semidefinite Random MatricesResearch Paper
The classical Chernoff bound controls the probability that a sum of independent, nonnegative, uniformly bounded random variables deviates from its mean, with exponentially small tails governed by the Kullback–Leibler divergence between two Bernoulli laws. Many problems in numerical linear algebra, graph sparsification, compressed sensing and randomized…
Optimization Methods on Riemannian Manifolds and Their Application to Shape Space 1: Riemannian BFGS with Isometric Vector Transport Converges R-Linearly under Uniform ConvexityResearch Paper
Many optimization problems in shape analysis, computer vision, numerical linear algebra and statistics have a feasible set that is not a vector space but a Riemannian manifold: spaces of curves modulo reparametrization, the Stiefel and Grassmann manifolds, fixed-rank matrices. On such a set the classical recipe "add a multiple of the search direction to the…
Differential Variational Inequalities 1: Under Any of Five Conditions on (K, F), the Initial-Value DVI with Lipschitz Data Has a Weak Carathéodory SolutionResearch Paper
A differential variational inequality (DVI) couples an ordinary differential equation for a state x(t) with a finite-dimensional variational inequality that the algebraic variable u(t) must solve at every instant. The class contains complementarity systems from contact mechanics and electrical circuits with diodes, linear complementarity systems from…
Clarke Subgradients of Stratifiable Functions II: The Nonsmooth Kurdyka–Łojasiewicz Inequality for Lower Semicontinuous Functions Definable in an O-minimal StructureResearch Paper
The Kurdyka–Łojasiewicz (KL) inequality is the analytic engine behind most global convergence proofs for descent methods on nonconvex problems: proximal point and proximal gradient schemes, alternating minimization, ADMM variants and subgradient flows all reach a critical point with finite trajectory length once the objective satisfies a KL inequality. Its…
Clarke Subgradients of Stratifiable Functions I: Every Clarke Subgradient of a Lower Semicontinuous Function with a Nonvertical Whitney-Stratified Graph Dominates the Stratum GradientResearch Paper
First-order methods for nonsmooth, nonconvex optimization (proximal algorithms, alternating minimization, subgradient-type descent) are analysed through generalized derivatives. Convergence and complexity arguments need a lower bound on the size of those derivatives away from critical points. For the Clarke subdifferential of a general lower semicontinuous…
Affine Processes on Positive Semidefinite Matrices II: Every Admissible Parameter Set Determines a Unique Affine Process on the PSD Cone with Generator (2.12)Research Paper
Stochastic models of covariance matrices need processes that stay in the cone of positive semidefinite matrices. Wishart processes (Bru, 1991) and their extensions underlie multivariate stochastic-volatility and term-structure models in finance (see §1 of Cuchiero et al. for the literature). They are used because their Laplace transforms are explicit: they…
Affine Processes on Positive Semidefinite Matrices III: For d ≥ 2, a Markov Family Is Infinitely Decomposable Iff It Is Affine with Zero Diffusion Iff It Is Affine and Infinitely DivisibleResearch Paper
Affine processes are Markov processes whose Laplace transform depends exponential-affinely on the initial state. On the cone Sd+ of positive semidefinite matrices they model stochastic covariance matrices in multivariate stochastic volatility, interest-rate and credit models. Examples include the Wishart process of Bru (Bru 1991) and Ornstein–Uhlenbeck…
An Optimal Variance Estimate in Stochastic Homogenization of Discrete Elliptic Equations: Scale-L Averages of the Approximate-Corrector Energy Density Have Variance ≲ L^−d, Times (ln T)^q if d = 2Research Paper
A random conductance model puts a random conductivity on every edge of the lattice Zd. It is the simplest discrete model of diffusion in a heterogeneous medium, and its generator is the generator of a random walk in a random environment. Classical stochastic homogenization shows that on large scales the random operator behaves like a…
Random Graphs with a Given Degree Sequence 2: The Closure of the β-Model Expected Degree Sequences Equals the Convex Hull of All Degree SequencesResearch Paper
A degree sequence records how many neighbours each vertex of a graph has. In network statistics it is often the only summary of a graph that is observed or trusted, and the natural probability models for graphs in which "the degree sequence captures the information" are exponential families whose sufficient statistic is the degree sequence. Chatterjee,…
Random Matrices: Universality of ESDs and the Circular Law 2: The ESD of A_n/√n Converges to μ iff the Normalized Log-Determinants of A_n/√n − zI Converge to μ's Log-Potential for a.e. zResearch Paper
The eigenvalues of a large non-Hermitian random matrix are hard to study directly. For Hermitian matrices, the empirical spectral distribution (ESD) is controlled by the resolvent and the Stieltjes transform, both stable under small perturbations. For non-Hermitian matrices no such tool exists: eigenvalues can move a long way under tiny perturbations, and…
The Primal-Dual Active Set Strategy as a Semismooth Newton Method III: Global Convergence under the Norm and Cone ConditionsResearch Paper
Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψ and λ≥0 with Ay+λ=f and λi(yi−ψi)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…
Random Matrices: Universality of ESDs and the Circular Law 1: For i.i.d. Zero-Mean Unit-Variance Entries, the ESD of (M_n + X_n)/√n Does Not Depend on the Entry Distribution in the LimitResearch Paper
The eigenvalues of a large random matrix with independent entries follow deterministic limiting laws. For non-Hermitian matrices with i.i.d. entries of mean zero and variance one, the circular law asserts that the eigenvalues of n1Xn become uniformly distributed on the unit disk. These laws are used across statistics (covariance and…
On Actor-Critic Algorithms: Convergence of Actor-Critic Algorithms with TD(1) and TD(λ) Critics on Finite MDPsResearch Paper
Reinforcement-learning methods for Markov decision processes split into critic-only methods, which learn an approximate value function and act greedily with respect to it, and actor-only methods, which adjust a parameterized policy along a simulated estimate of the gradient of its performance. Critic-only methods with function approximation can fail to…
Is Network Traffic Approximated by Stable Lévy Motion or Fractional Brownian Motion? 2: Superposed ON/OFF Input Under Slow Growth Converges (fidi) to α-Stable Lévy MotionResearch Paper
Measurements of Ethernet and Web traffic in the 1990s showed burstiness at every time scale, long-range dependence, and file sizes and transmission times with tails like x−α, 1<α<2 (Leland, Taqqu, Willinger and Wilson, 1994; Crovella and Bestavros, 1997). The standard explanation models each user as an ON/OFF source that alternates between…
Is Network Traffic Approximated by Stable Lévy Motion or Fractional Brownian Motion? 3: Infinite Source Poisson Input Under Fast Growth Converges in (D[0,∞), J₁) to Fractional Brownian MotionResearch Paper
Measurements of Ethernet and Internet traffic in the 1990s showed that cumulative traffic is self-similar and long-range dependent: correlations of the input rate decay so slowly that they are not summable, and fluctuations at large time scales do not average out the way Poisson-type models predict. A widely accepted explanation is that the lengths of…
Do Price and Volatility Jump Together?: The Observable Jump–Volatility Statistics U(F, kₙ) Converge in Probability to U(F) in the Skorokhod TopologyResearch Paper
Asset prices observed at high frequency show two kinds of discontinuity: jumps in the price itself and abrupt changes in its volatility. Whether the two occur at the same times matters for modelling. Many stochastic volatility models used in option pricing let the price and the volatility jump together (for example the affine jump-diffusion models of…
Ising Models on Locally Tree-Like Graphs 1: On Uniformly Sparse Locally Tree-Like Graphs the Ising Free Entropy Density Converges to the Bethe PredictionResearch Paper
The ferromagnetic Ising model is the basic model of statistical mechanics for interacting binary variables. On a finite graph it is a probability distribution over spin configurations, and its normalizing constant, the partition function, encodes the thermodynamics: the free entropy per vertex determines the magnetization, the correlations, and the location…
Small Gain Theorems for Large Scale Systems and Construction of ISS Lyapunov Functions 1: Rescaling Along an Ω-Path Gives the Network ISS Lyapunov Function maxᵢ σᵢ⁻¹(Vᵢ(xᵢ))Research Paper
Large engineered systems — power grids, chemical plants, logistics and communication networks — are usually modelled as many interacting subsystems. A stability certificate for the whole network is rarely available directly, but each subsystem can often be analysed on its own, treating the states of its neighbours as disturbances. Input-to-state stability (I…
Random Walks in a Random Environment 2: lim X_n/n = (1 − Eσ)/(1 + Eσ) if Eσ < 1, −(1 − E(σ⁻¹))/(1 + E(σ⁻¹)) if E(σ⁻¹) < 1, and 0 OtherwiseResearch Paper
A random walk in a random environment is a walk whose step probabilities are sampled once at each site and then reused whenever the walk returns there. Repeated visits therefore reveal the same local bias instead of drawing a fresh probability. This makes the walk different from an ordinary random walk with a single averaged step probability. Solomon's 1975…
Graph Minors. X. Obstructions to Tree-Decomposition IV: Mutually Distinguishable Tangles Have a Tree-Decomposition Separating Them by Their DistinctionsResearch Paper
Robertson and Seymour introduced tangles in Graph Minors. X (J. Combin. Theory Ser. B 52 (1991) 153–190) as the precise obstruction to tree-decompositions of small width: a graph has a tangle of large order exactly when it has no tree-decomposition of small width. A tangle points to a highly connected region of a graph without naming its vertices, by…