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.
Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 3: Lipschitz and Pointwise Gradient Bounds on the Heat Semigroup Make Its Dual Semigroup a W₂ ContractionResearch Paper
A lower bound on Ricci curvature can be expressed in two ways that make sense far beyond smooth manifolds. The Eulerian way bounds the gradient of the heat semigroup: Bakry and Émery's Γ2-calculus gives ∣∇Ptf∣2≤e−2KtPt∣∇f∣2. The Lagrangian way bounds how heat flow moves probability measures in optimal…
Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 2: The Dirichlet Form of an Energy Measure Space Is Twice the Cheeger Energy Iff It Is Upper-RegularResearch Paper
There are two standard ways to do analysis on a non-smooth space. The first starts from an energy: a Dirichlet form E on L2(X,m), its heat semigroup and its carré du champ Γ. This is the setting of Bakry–Émery Γ-calculus and of the curvature-dimension condition BE(K,N). The second starts from a metric measure space(X,d,m): slopes of…
Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 6: BE(K,N) on Riemannian Energy Measure Spaces Is Stable Under Sturm–Gromov–Hausdorff ConvergenceResearch Paper
Curvature bounds on a smooth Riemannian manifold control diffusion and the behavior of probability measures. Metric measure spaces extend these questions to limits that need not be smooth. A useful curvature condition must continue to hold when a sequence of spaces converges. Ambrosio, Gigli, and Savaré prove that their analytic Bakry–Émery…
On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 3: Under Convexity Every Markovian ε-Nash Equilibrium Is a Closed-Loop ε-Nash EquilibriumResearch Paper
In an n-player stochastic differential game each player controls the drift of its own diffusion and is rewarded through a running and a terminal payoff that depend on its own state and on the empirical distribution of all states. A player's strategy can be closed-loop (path-dependent), reacting to the whole observed history of all states, or Markovian (in…
A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization 2: Randomized BSUM-M Converges to Primal-Dual Optimal Solutions Almost SurelyResearch Paper
Many large convex problems in signal processing, networking and statistics have a separable objective coupled by linear constraints: K blocks of variables, each with its own nonsmooth regularizer and its own feasible set, tied together by ∑kEkxk=q. The alternating direction method of multipliers (ADMM) is the standard tool for such problems when K=2.…
Global C¹ Regularity of the Value Function in Optimal Stopping Problems 2: In Finite Horizon, Probabilistic Regularity of the Boundary Makes the Time Derivative of the Value Function ContinuousResearch Paper
In an optimal stopping problem the value function V and the gain function G agree on the stopping setD={V=G}, and V>G on the continuation setC. The smooth fit principle says that, at the boundary ∂C between them, V meets G with matching first derivatives. Smooth fit is one of the boundary conditions in the free-boundary problems that…
A Mean Field Game of Optimal Portfolio Liquidation 2: The Value Functions of the Penalized Mean Field Games Converge in L¹ to the Value Function of the Liquidation-Constrained GameResearch Paper
Optimal portfolio liquidation asks how a trader should unwind a position of X shares over a horizon [0,T] when trading moves prices. Since Almgren and Chriss (2001) the standard model charges a quadratic cost ηtξt2 for trading at rate ξt (temporary impact) and a risk penalty λtXt2 on the open position, and imposes the liquidation…
A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization 1: Cyclic BSUM-M Converges to Primal-Dual Optimal SolutionsResearch Paper
Many problems in signal processing, machine learning and power systems have the form of a convex objective that is a sum of a smooth coupled term and nonsmooth block-separable terms, minimized subject to linear equality constraints that couple K blocks of variables: basis pursuit, demand response control in smart grids, and distributed estimation are the…
Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 1: The Weak, Pointwise and Gradient Forms of the Bakry–Émery Condition BE(K,N) Are EquivalentResearch Paper
On a Riemannian manifold, a lower bound Ric≥K together with a dimension bound N can be read off from the heat flow alone. This is the Bakry–Émery curvature-dimension conditionBE(K,N): Bochner's inequality Γ2(f)≥KΓ(f)+N1(Δf)2 for the iterated carré du champ. The condition makes sense for any diffusion: weighted…
From Nonlinear Fokker-Planck Equations to Solutions of Distribution Dependent SDE: Density-Dependent McKean–Vlasov SDEs Have Weak Solutions Whose Marginals Solve the Nonlinear FPEResearch Paper
A McKean–Vlasov stochastic differential equation, or distribution dependent SDE, is an SDE whose coefficients depend on the law of the solution itself:
On Viscosity Solutions of Path Dependent PDEs: Comparison Principle for Viscosity Sub- and Supersolutions of Semilinear PPDEs, and u^0 from the BSDE Is the Unique Viscosity SolutionResearch Paper
Many quantities in stochastic control, mathematical finance and stochastic differential games depend on the whole past of a Brownian path rather than on its current position: the price of an Asian or lookback option, the value of a control problem with delay, the solution of a non-Markovian backward stochastic differential equation (BSDE). For Markovian…
A Probabilistic Weak Formulation of Mean Field Games and Applications 3: Distributed Controls from a Mean Field Game Solution Form an ε_n-Nash Equilibrium of the n-Player Game, ε_n → 0Research Paper
Mean field games (MFGs) were introduced by Lasry and Lions (Jpn. J. Math. 2007) and by Huang, Malhamé and Caines (Commun. Inf. Syst. 2006) as limits of stochastic differential games with many symmetric players whose interaction runs through the empirical distribution of their states. An MFG is a fixed point problem for one representative player facing a…
From the Master Equation to Mean Field Game Limit Theory: Large Deviations and Concentration of Measure 2: Nash Equilibrium Empirical Measure Flows Satisfy a Weak LDP Under Common NoiseResearch Paper
A mean field game describes the Nash equilibria of n symmetric players whose states interact only through their empirical distribution, in the limit n→∞. The law of large numbers for the equilibria — convergence of the empirical measure of the n-player equilibrium to the mean field equilibrium — was proved in the diffusion setting by Cardaliaguet,…
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods IV: For Prox-Regular Compositions h∘c, Subregularity of the Subdifferential and of the Prox-Gradient Map CoincideResearch Paper
Linear convergence of first-order methods is usually proved through an error bound: near a solution, the distance to the solution set is controlled by the size of a computable residual, such as the length of a proximal-gradient step. For the prox-linear method, which minimizes a composition h(c(x)) of a nonsmooth outer function h with a smooth map c by…
Mean Field Games Master Equations with Nonseparable Hamiltonians and Displacement Monotonicity: Under Displacement Monotone H and G, the Master Equation Has a Unique Global Classical SolutionResearch Paper
Mean field games (Lasry–Lions 2006–2007; Huang–Malhamé–Caines 2006) describe Nash equilibria of games with a very large number of symmetric players, each interacting with the others only through the empirical distribution of their states. When all players are also exposed to a common noise, the equilibrium is no longer described by a forward–backward pair…
From the Master Equation to Mean Field Game Limit Theory: Large Deviations and Concentration of Measure 1: Without Common Noise, n-Player Nash Equilibria Concentrate Dimension-FreeResearch Paper
A large stochastic game has one state process per player. Each player's feedback changes with the empirical distribution of all states, so a finite population remains coupled even when the idiosyncratic Brownian motions are independent. A useful quantitative question is whether a statistic of the entire collection of equilibrium trajectories can deviate…
Riemannian Proximal Gradient Methods II: The Riemannian Proximal Gradient Method Converges at Rate O(1/k) under Retraction ConvexityResearch Paper
Many problems in statistics, signal processing and machine learning minimize a smooth loss plus a nonsmooth regularizer over a set with manifold structure: sparse principal component analysis over the Stiefel manifold, sparse blind deconvolution over the sphere, and clustering and dictionary-learning models with orthogonality constraints. In Euclidean space…
Functional Itô Calculus and Stochastic Integral Representation of Martingales 2: The Vertical Derivative Extends to a Bijective Isometry W^{1,2}(X) → L²(X) Inverting the Itô IntegralResearch Paper
Every square-integrable martingale of a Brownian filtration is a stochastic integral, Y(T)=E[Y(T)]+∫0Tϕ⋅dW (Itô's representation theorem). The classical theorem gives no formula for ϕ. In hedging, ϕ is the replicating strategy of a claim. In filtering and stochastic control it is the quantity one has to compute. The Clark–Haussmann–Ocone…
Riemannian Proximal Gradient Methods I: Every Accumulation Point of the Riemannian Proximal Gradient Method Is Stationary, with an Explicit Iteration BoundResearch Paper
Many problems in statistics, signal processing and machine learning minimize a smooth loss plus a nonsmooth regularizer over a set that is a manifold rather than a vector space: sparse principal component analysis over the Stiefel manifold, sparse blind deconvolution over the sphere, low-rank recovery over fixed-rank matrices. In Euclidean space the…
Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization 4: Constant-Step Adam Iterates Converge in Probability to the ODE Solution as γ → 0Research Paper
Adam (Kingma and Ba, 2015, arXiv:1412.6980) is one of the most widely used optimizers for training neural networks. It is a stochastic gradient method that keeps exponential moving averages of the stochastic gradients and of their coordinatewise squares, rescales both by bias-correction factors, and divides the first by the square root of the second. Its…
Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 5: Worst-Case Displacements √δ G_δ Grow Monotonically in δ Along Straight LinesResearch Paper
A distributionally robust decision evaluates a rule against every data distribution within a specified transport budget of a baseline law. The budget is a modeling choice: increasing it expresses more uncertainty about the data. A robust objective value can increase with that budget, but the value alone does not describe how the adverse distribution…
Functional Itô Calculus and Stochastic Integral Representation of Martingales 1: Functional Itô Formula for C^{1,2}_b Nonanticipative Functionals of a Continuous SemimartingaleResearch Paper
Many quantities in stochastic analysis and mathematical finance depend on the whole past of a process, not only on its current value: running maxima, averages, integrals against the quadratic variation, payoffs of path-dependent options, conditional expectations of path functionals. The classical Itô formula describes the evolution of f(t,X(t)) for a smooth…
Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization 1: The Continuous-Time Adam ODE Has a Unique Bounded Global Solution from (x₀, 0, 0)Research Paper
Adam (Kingma and Ba, 2015, arXiv:1412.6980) is the default optimizer for training deep neural networks. At each step it keeps exponential moving averages mn and vn of the stochastic gradients and of their coordinatewise squares, corrects both for their initialization at zero (the bias-correction or debiasing step m^n=mn/(1−αn), …
Mean-Field Stochastic Differential Equations and Associated PDEs: The Mean-Field Value Function Is the Unique Classical Solution of Its PDE on [0,T] × ℝ^d × P₂(ℝ^d)Research Paper
A McKean–Vlasov or mean-field stochastic differential equation is an SDE whose coefficients depend on the law of the solution itself. Such equations describe the limit of large systems of weakly interacting particles (Kac's kinetic models, McKean's propagation of chaos) and are the state dynamics of mean-field games and mean-field control. For a classical…
Minimax Statistical Learning with Wasserstein Distances III: Excess Local Minimax Risk of Wasserstein ERM When One Hypothesis Is SmoothResearch Paper
In ordinary statistical learning, a hypothesis is chosen from training data drawn from a distribution P and judged by its risk under that same P. In practice the test distribution often differs from the training one: covariate shift, domain drift, adversarial perturbation of inputs. Distributionally robust learning replaces the risk at P by the worst risk…