Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

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.

1285 open missions

Missions

851–875 of 1285
Open1285Completed3527All4812
Dynamic ProgrammingOptimizationReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 1: If the Policy Class Is Closed Under Policy Improvement, Every Stationary Point of the Policy Gradient Objective Is Globally OptimalResearch Paper

Policy gradient methods optimize a parameterized policy for a Markov decision process by running gradient descent on its expected cost. They underlie most large-scale reinforcement learning, from robotics to game playing, and are also natural in operations research, where structured policy classes (linear feedback, base-stock levels, thresholds) are…

9 thms2 active usersReviewed
Information TheoryProbabilityRandom Matrix Theory·Captain: mikedeng1

Universality in Polytope Phase Transitions and Message Passing Algorithms 1: Polynomial AMP Iterates Have the Same Asymptotic Moments for All Sub-Gaussian Matrices with Equal Entry VariancesResearch Paper

Approximate message passing (AMP) is a family of iterative algorithms driven by a large random matrix. It was introduced for compressed sensing by Donoho, Maleki and Montanari (PNAS 2009), and it is also used for low-rank matrix estimation, regression and spin-glass optimization. Its main appeal is that, for Gaussian random matrices, the empirical…

9 thms2 active usersReviewed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

An Optimal Algorithm for Stochastic and Adversarial Bandits III: α-Tsallis-INF With Gap-Tuned Asymmetric Regularization Has Logarithmic Pseudo-Regret When the Best Arm Is UniqueResearch Paper

In the multi-armed bandit problem a learner repeatedly chooses one of KKK actions and observes only the loss of the action it chose. Two models of the environment dominate the literature. In the stochastic model the losses of each arm are drawn i.i.d. from a fixed distribution, and the optimal pseudo-regret grows like ∑i≠i∗log⁡(T)/Δi\sum_{i\ne i^*}\log(T)/\Delta_i∑i=i∗​log(T)/Δi​, where …

14 thms2 active usersReviewed
Markov ChainMathematical PhysicsProbability·Captain: mikedeng1

The Endpoint Distribution of Directed Polymers 1: In the Low-Temperature Phase the Endpoint Distribution Is Asymptotically Purely Atomic, and at High Temperature It Is NotResearch Paper

A directed polymer in a random environment is a random walk whose paths are weighted by the disorder they encounter. The walk favors paths with large accumulated weight, and its endpoint distribution can concentrate on a small number of sites even though the number of possible paths grows exponentially. Understanding how much probability remains spread…

21 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Turán Graphs with Bounded Matching Number 2: For Color-Critical H of Chromatic Number k+1 > 2, Large s and n ≫ s, H-Free Graphs with Matching Number at Most s Have at Most g(n,k,s) EdgesResearch Paper

Two classical extremal results bound the number of edges of an nnn-vertex graph under a single restriction. Turán's theorem (1941) says that a graph with no clique on k+1k+1k+1 vertices has at most t(n,k)t(n,k)t(n,k) edges, the edge count of the balanced complete kkk-partite graph. The Erdős–Gallai theorem (1959) gives the maximum number of edges of an nnn-vertex graph whose…

11 thms2 active usersReviewed
Algorithmic Game TheoryEconomics·Captain: mikedeng1

Competitive Equilibrium with Indivisible Goods and Generic Budgets 1: Two Additive Agents with Almost Equal but Unequal Budgets Have a Competitive Equilibrium Giving Each Agent Her Truncated ShareResearch Paper

Many allocation problems divide indivisible goods among agents who are entitled to different shares but cannot pay with real money: course seats among students, shifts among workers, inherited items among heirs. A standard mechanism gives each agent a budget of artificial currency and lets a market run. When budgets are equal this is the competitive…

9 thms2 active usersReviewed
Differential GeometryFunctional AnalysisProbability·Captain: mikedeng1

Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 5: A Product of Riemannian Energy Measure Spaces with BE(K,N_X) and BE(K,N_Y) Satisfies BE(K,N_X+N_Y)Research Paper

A lower bound KKK on the Ricci curvature of a Riemannian manifold and an upper bound NNN on its dimension can be expressed without coordinates in two ways. The Bakry–Émery condition BE(K,N)\mathrm{BE}(K,N)BE(K,N) is a property of the heat semigroup and its generator: the iterated carré du champ Γ2\Gamma_2Γ2​ dominates KΓ+1N(Δf)2K\Gamma+\frac1N(\Delta f)^2KΓ+N1​(Δf)2 (Bakry–Émery 1985). The Riemannian…

7 thms2 active usersReviewed
Operations ResearchPartial Differential EquationsProbability+1·Captain: mikedeng1

Global C¹ Regularity of the Value Function in Optimal Stopping Problems 1: Probabilistic Regularity of the Boundary Makes the Value Function Continuously DifferentiableResearch Paper

An optimal stopping rule chooses when to end a stochastic process in order to collect a terminal reward, possibly after earning or paying a running reward. The resulting value function often solves a free-boundary problem: the state space splits into a region where stopping is optimal and one where continuing is better. Smoothness inside either region does…

15 thms2 active usersReviewed
AlgebraCombinatoricsDiscrete Geometry+1·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 5: For h ≥ 2, Two h-Scattered Linear Sets Are PΓL(r, qⁿ)-Equivalent iff Their Subspaces Are ΓL(r, qⁿ)-EquivalentResearch Paper

Linear sets are point sets of a finite projective space defined by a subspace over a subfield. They appear throughout finite geometry, for instance in the study of semifields and, through the correspondence studied by Sheekey and Van de Voorde (arXiv:1806.05929), maximum rank distance (MRD) codes; see Polverino's survey (doi:10.1016/j.disc.2009.04.007). In…

9 thms2 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

A Mean Field Game of Optimal Portfolio Liquidation 1: Under Weak Interaction the Liquidation Mean Field Game Has a Unique Equilibrium, Given by a Singular Conditional Mean-Field FBSDEResearch Paper

Large traders who must unwind a position by a deadline face a trade-off between trading fast, which moves prices against them, and trading slowly, which exposes them to price risk. When many traders liquidate at once, each one's execution price also depends on the aggregate selling rate of the others. Fu, Graewe, Horst and Popier (arXiv:1804.04911) model…

15 thms2 active usersReviewed
Algorithmic Game TheoryControl TheoryOperations Research+2·Captain: mikedeng1

A Mean Field Game of Optimal Portfolio Liquidation 3: The Mean-Field Equilibrium Strategies Form an O(1/√N)-Nash Equilibrium of the N-Player Liquidation GameResearch Paper

A trader who must sell a large position within a fixed horizon faces a trade-off: selling fast moves the price against her (temporary price impact), selling slowly exposes her to price risk. Since Almgren and Chriss, this optimal liquidation problem has been studied as a stochastic control problem with a terminal state constraint: the remaining position…

11 thms2 active usersReviewed
Optimal TransportProbabilityStatistics·Captain: mikedeng1

On the Rate of Convergence in Wasserstein Distance of the Empirical Measure II: Concentration Inequalities for T_p(μ_N, μ) under Exponential or Polynomial Moments (Theorem 2)Research Paper

Approximating an unknown probability measure μ\muμ by the empirical measure μN=1N∑k=1NδXk\mu_N=\frac1N\sum_{k=1}^N\delta_{X_k}μN​=N1​∑k=1N​δXk​​ of an i.i.d. sample is the basic operation of statistics, Monte Carlo integration, quantization and particle approximations of nonlinear PDEs. The natural way to compare μN\mu_NμN​ with μ\muμ on Rd\mathbb R^dRd is an optimal-transport cost, because it…

13 thms2 active usersReviewed
Algorithmic Game TheoryControl TheoryProbability·Captain: mikedeng1

A Probabilistic Weak Formulation of Mean Field Games and Applications 2: Under Unique Hamiltonian Maximizers and Lasry–Lions Monotonicity, the Mean Field Game Has at Most One SolutionResearch Paper

Mean field games, introduced independently by Lasry and Lions (Mean field games, Jpn. J. Math. 2007) and by Huang, Malhamé and Caines (2006), describe the Nash equilibria of games with a very large number of symmetric players, each of whom reacts only to the empirical distribution of the others. In the limit, an equilibrium is a fixed point: a flow of…

13 thms2 active usersReviewed
Optimal TransportProbabilityStatistics·Captain: mikedeng1

On the Rate of Convergence in Wasserstein Distance of the Empirical Measure I: Non-Asymptotic Moment Bounds on E T_p(μ_N, μ) under a q-th Moment Condition (Theorem 1)Research Paper

How fast does the empirical measure of an i.i.d. sample approach the law it is drawn from? When distance is measured by optimal transport, the answer enters the analysis of statistical estimators built from empirical distributions, quantization of probability measures, Monte Carlo and particle approximations of nonlinear PDEs (McKean–Vlasov systems), and…

11 thms2 active usersReviewed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 2: The Shadow of γ1 + γ2 in ν Is the Shadow of γ1 Plus the Shadow of γ2 in What RemainsResearch Paper

The martingale optimal transport problem asks for a coupling of two probability measures μ,ν\mu,\nuμ,ν on R\mathbb RR that is the law of a one-step martingale and minimizes an expected cost. It arises in robust finance, where the marginals are the risk-neutral laws of an asset at two dates implied by option prices, and model-independent price bounds for exotic…

18 thms2 active usersReviewed
Dynamical SystemsMachine LearningOptimization+1·Captain: mikedeng1

Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization 5: Decreasing-Step Adam Converges Almost Surely to the Critical Points of FResearch Paper

Adam (Kingma and Ba, 2015) is the default optimizer for training neural networks: a stochastic gradient method that keeps an exponential moving average mnm_nmn​ of past gradients and an exponential moving average vnv_nvn​ of their coordinatewise squares, and divides the first by the square root of the second. Its practical success came well before any convergence…

16 thms2 active usersReviewed
Operations ResearchOptimal TransportOptimization+1·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 5: For c = ϕ(x)ψ(y), ψ Strictly Convex, ϕ Strictly Decreasing, the Left-Curtain Coupling Is the Unique OptimizerResearch Paper

Martingale optimal transport asks for the cheapest way to couple two given laws μ\muμ and ν\nuν on R\mathbb RR by a one-step martingale: a pair (X,Y)(X,Y)(X,Y) with X∼μX\sim\muX∼μ, Y∼νY\sim\nuY∼ν and E[Y∣X]=XE[Y\mid X]=XE[Y∣X]=X. The problem arises in mathematical finance, where μ\muμ and ν\nuν are the risk-neutral laws of an asset at two maturities, implied by quoted vanilla option prices, and the…

11 thms2 active usersReviewed
Algorithmic Game TheoryControl TheoryProbability·Captain: mikedeng1

A Probabilistic Weak Formulation of Mean Field Games and Applications 1: When the Hamiltonian's Maximizer Sets Are Convex, the Mean Field Game in Weak Formulation Has a SolutionResearch Paper

Mean field games (MFGs) describe Nash equilibria of stochastic differential games with a very large number of symmetric players, each of whom interacts with the others only through the empirical distribution of their states (and, in this paper, of their controls). They were introduced independently by Lasry and Lions and by Huang, Malhamé and Caines around…

16 thms2 active usersReviewed
Convex OptimizationOptimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods I: For the Proximal Gradient Method, the Error Bound Condition Is Equivalent to Quadratic GrowthResearch Paper

A large share of the optimization problems solved in statistics, signal processing and machine learning have the composite form

13 thms2 active usersReviewed
AlgebraCombinatoricsDiscrete Geometry·Captain: mikedeng1

Maximum Scattered Linear Sets and Complete Caps in Galois Spaces 2: For q = 2^t, t Even, and n ≥ 4 Even, AG(n, q) Has a Complete Cap of Size 2√(q^(n−1))Research Paper

A cap in an affine or projective space over a finite field is a set of points no three of which are collinear; a cap is complete when it is maximal with respect to inclusion, so that every point outside it lies on a line through two of its points. Caps are closely connected with error-correcting codes: projective caps can serve as parity-check columns for…

14 thms2 active usersReviewed
Dynamical SystemsMachine LearningOptimization·Captain: mikedeng1

Convergence and Dynamical Behavior of the ADAM Algorithm for Nonconvex Stochastic Optimization 2: The Continuous-Time Adam Trajectory Converges to the Critical Points of FResearch Paper

Adam (Kingma and Ba, 2015) is the default optimizer for training neural networks. At step nnn it keeps an exponential moving average mnm_nmn​ of stochastic gradients and an exponential moving average vnv_nvn​ of their squared coordinates, corrects both for their initialization at zero (the bias correction or debiasing step), and moves the iterate by …

14 thms2 active usersReviewed
AlgebraCombinatoricsDiscrete Geometry+1·Captain: mikedeng1

Maximum Scattered Linear Sets and Complete Caps in Galois Spaces 1: Scattered 𝔽_q-Linear Sets of Rank rt/2 Exist in PG(r − 1, q^t) for t Even, in Three Families of (q, t)Research Paper

Linear sets are the main tool for building point sets with few intersection sizes in finite projective spaces: sets meeting every hyperplane, two-intersection sets, translation ovoids, and the geometric side of finite semifields and rank-metric codes (Polverino, 2010). Among them, scattered linear sets are those whose points all carry the smallest possible…

15 thms2 active usersReviewed
Convex OptimizationDynamical SystemsOptimization·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping I: Under (G₂)–(G₃), (DIN-AVD)α,β,b Trajectories Satisfy f(x(t)) − min f = O(1/(t²w(t)))Research Paper

Accelerated first-order methods for convex minimization, starting with Nesterov's 1983 scheme, reach the rate f(xk)−min⁡f=O(1/k2)f(x_k)-\min f=\mathcal O(1/k^2)f(xk​)−minf=O(1/k2), which is optimal for the class of convex functions with Lipschitz gradient. Su, Boyd and Candès (NIPS 2014; JMLR 2016) showed that Nesterov's method is a discretization of the second-order ODE …

7 thms2 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization 3: Under Refined Dual Strong Convexity, SDCA Reaches Expected Dual Sub-optimality ε after 2(n/s)·log(2/ε) IterationsResearch Paper

Regularized loss minimization covers support vector machines, logistic and ridge regression, and the absolute-deviation regression of robust statistics. Stochastic dual coordinate ascent (SDCA) solves these problems by maximizing the Fenchel dual one randomly chosen coordinate at a time. Shalev-Shwartz and Zhang (arXiv:1209.1873, JMLR 2013) gave the first…

13 thms2 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

From Data to Decisions: Distributionally Robust Optimization Is Optimal 3: On a Compact Continuous State Space the Relative-Entropy Robust Predictor Is Feasible and Strongly OptimalResearch Paper

A decision maker who chooses xxx to minimize an expected cost c(x,P)=EP[γ(x,ξ)]c(x,\mathbb P)=\mathbb E_{\mathbb P}[\gamma(x,\xi)]c(x,P)=EP​[γ(x,ξ)] rarely knows the distribution P\mathbb PP of the random parameter ξ\xiξ. What is available is a sample ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​. Any rule that turns the sample into a cost estimate can disappoint: the realized expected cost may exceed the estimate. In a…

13 thms2 active usersReviewed
PreviousPage 35 of 52Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36515432
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82895261

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me