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

826–850 of 1285
Open1285Completed3527All4812
OptimizationProbability·Captain: visuddhi

VC Theory for Inventory Policies: Xie–Ma–Xin BoundsResearch Paper

An inventory policy chooses how much stock to order before demand is observed. Its quality is assessed by the holding and backlogging costs it incurs on future demand. A policy chosen to perform well on historical demand can overfit those observations. A useful statistical guarantee therefore controls the difference between historical and future costs…

6 thms2 active usersReviewed
Computational GeometryLinear algebraMachine Learning·Captain: mikedeng1

Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering I: The Rank-m SVD Truncation Plus Its Residual Preserves the Cost of Every j-Dimensional ShapeResearch Paper

Large data sets make clustering and subspace fitting expensive because a candidate solution must be evaluated against every input point. A dimensionality reduction replaces the data by a lower-rank matrix whose costs approximate those of the original input for an entire class of candidate solutions. Feldman, Schmidt, and Sohler study reductions that retain…

11 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Personalized Dynamic Pricing with Machine Learning: High-Dimensional Features and Heterogeneous Elasticity 2: Under Unknown Sparsity, Lasso-Based ILQX Pricing Has Regret at Most Cs√T(log d + log T)Research Paper

Online sellers of loans, insurance, travel and retail goods observe data about each arriving customer before quoting a price. Using that data to price individually is attractive only if the seller can learn, from its own sales, how demand responds to price for customers with given characteristics. Two features make this hard in practice. The number of…

6 thms2 active usersReviewed
Machine LearningOptimal TransportProbability+1·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization and Variation Regularization III: With Probability 1 − e^(−t), E_Pn[(ρ − d(z, D_f))₊] ≤ Cρ² + 2ρ·E[Rademacher] + ρ√(t/2n) for Every fResearch Paper

Wasserstein distributionally robust optimization (DRO) replaces the empirical risk EPn[f]\mathbb E_{P_n}[f]EPn​​[f] of a loss fff by its worst case over all distributions within Wasserstein distance ρ\rhoρ of the empirical law PnP_nPn​. Gao, Chen and Kleywegt (arXiv:1712.06050; Operations Research, 2024, doi:10.1287/opre.2022.2383) show that, for small radii, this worst-case risk…

8 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 1: In the Well-Separated Case, Algorithm-I with m Price Changes Has Regret at Most KT^(1/(m+1))Research Paper

Retailers set prices and stock levels without knowing how demand responds to price. They must learn the demand curve from their own sales while still earning money, which is the exploration–exploitation trade-off of dynamic pricing with learning (den Boer 2015). Two features of practice make the problem harder than the textbook bandit. First, demand is…

10 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Personalized Dynamic Pricing with Machine Learning: High-Dimensional Features and Heterogeneous Elasticity 1: Under Known Sparsity, ILSX Pricing Has Regret at Most Cs√T log TResearch Paper

A seller who changes prices while learning demand faces two costs: a price experiment may earn less revenue now, while insufficient experimentation leaves later prices poorly calibrated. Customer features make the balance harder because both willingness to buy and sensitivity to price may vary between customers. Ban and Keskin study this problem when the…

6 thms2 active usersReviewed
Bandit AlgorithmsMachine LearningProbability+1·Captain: mikedeng1

The Multi-Armed Bandit Problem with Covariates I: Successive Elimination Has Expected Regret at Most 392γ²(1 + n/T)(K/Δ)log(TΔ²/18γ²) + nΔ⁻ Under a Random HorizonResearch Paper

In a multi-armed bandit, a decision maker repeatedly chooses an arm, observes a reward, and tries to learn which arm has the highest average reward while losing little reward during learning. A policy that requires the number of future pulls in advance cannot be used unchanged when stopping time is uncertain. Perchet and Rigollet study successive elimination…

10 thms2 active usersReviewed
CombinatoricsDiscrete Geometry·Captain: mikedeng1

Many Non-Equivalent Realizations of the Associahedron 4: For Every Seed Triangulation, Santos' Cones Form a Complete Simplicial Fan That Is the Normal Fan of a PolytopeResearch Paper

An associahedron of dimension nnn is a simple polytope whose nonempty faces correspond, reversing inclusion, to the sets of pairwise non-crossing diagonals of a convex (n+3)(n+3)(n+3)-gon: its vertices are the triangulations of the polygon and its facets are the diagonals. Associahedra appear in the combinatorics of parenthesizations (Tamari, Stasheff), in the theory…

10 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Central Limit Theorems and Bootstrap in High Dimensions 2: Gaussian Multiplier Bootstrap for Simple Convex Sets with Error C[Δ̄ₙ^{1/3} log^{2/3}(pn) + n⁻¹ log^{1/2}(pn)]Research Paper

Many procedures in high-dimensional statistics reduce to computing the probability that a normalized sum of independent random vectors falls into a set: simultaneous confidence intervals for many means, max-type tests, multiple testing with family-wise error control, and inference after model selection. When the dimension ppp is comparable to or much larger…

10 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

Central Limit Theorems and Bootstrap in High Dimensions 1: Gaussian Approximation of Normalized Sums over All Hyperrectangles with Error K₁[(L̄ₙ² log⁷p/n)^{1/6} + Mₙ(φₙ)/L̄ₙ]Research Paper

Many statistical procedures look at a large number of averages at once: simultaneous confidence intervals for ppp means, multiple testing of ppp hypotheses, the maximum of ppp ttt-statistics. Their calibration needs the joint law of a ppp-dimensional normalized sum, and in modern applications ppp is comparable to, or much larger than, the sample size nnn. Classical…

9 thms2 active usersReviewed
AnalysisOptimization·Captain: mikedeng1

Semismooth and Semiconvex Functions in Constrained Optimization II: A Semismooth Composition of Semismooth Functions Is Semismooth, with a Chain Rule for Generalized GradientsResearch Paper

Optimization models often build an objective from several intermediate quantities: constraints, penalties, and transformed measurements are evaluated first, then combined by an outer function. These intermediate and outer functions can be Lipschitz without being differentiable at the point of interest. Ordinary differentiation supplies no chain rule there.…

13 thms2 active usersReviewed
Control TheoryMachine LearningOperations Research+2·Captain: mikedeng1

Convergence Analysis of Machine Learning for Mean Field Control, Finite Horizon: The N-Agent Discrete-Time Neural-Net Value Is Within O(N^{-1/max(d,4)} + n_in^{-1/(3(d+1))} + √Δt) of the MKV OptimumResearch Paper

Mean field control studies the optimal control of a very large population of interacting agents through the limit in which the population is replaced by its distribution. The limit problem is a McKean–Vlasov (MKV) control problem: the dynamics and the cost of a representative agent depend on the law of its own state. Such problems arise in systemic risk,…

15 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices 3: In a Lemma 11 Instance, Two Vertices of Xᵢ Have Neighbor Triples Joined by an EdgeResearch Paper

A graph is 3-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding 3-colorability is NP-complete in general, and one of the standard ways to map the boundary between easy and hard cases is to forbid an induced subgraph. For the path PtP_tPt​ on ttt vertices, 3-colorability of P6P_6P6​-free graphs was known…

9 thms2 active usersReviewed
CombinatoricsGraph TheoryMathematical Logic·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 5: First-Order Interpretations of a Class of Graphs of Bounded Twin-width Have Bounded Twin-widthResearch Paper

Twin-width is a graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant in Twin-width I: Tractable FO Model Checking (J. ACM 69(1), Article 3, 2021; arXiv:2004.14789). Its main algorithmic consequence is that first-order model checking is fixed-parameter tractable on graphs given with a contraction sequence of bounded width. A parameter of this…

15 thms2 active usersReviewed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Graphon Mean Field Systems V: On Percolated Graphs Sampled From a Lipschitz Graphon the Mean-Square Error Is at Most κ(q)/(nβₙ)^{1/q}Research Paper

Large systems of interacting diffusions — neurons, oscillators, agents in a network game, particles in a queueing or load-balancing model — are usually analysed through their mean-field limit: as the population grows, each particle interacts with the empirical law of the others, and the system is replaced by a single nonlinear (McKean–Vlasov) equation. The…

15 thms2 active usersReviewed
Machine LearningNumerical AnalysisOptimization·Captain: mikedeng1

Conservative Set Valued Fields, Automatic Differentiation, Stochastic Gradient Methods and Deep Learning 2: Forward and Reverse Mode Automatic Differentiation Yield Conservative FieldsResearch Paper

Training a neural network means running a first-order method on a loss that is built from compositions of elementary operations, many of them nonsmooth: ReLU, max-pooling, absolute values, sorting, norms. The gradient the optimizer uses is not computed by hand. It is computed by automatic differentiation (autodiff), most often in its reverse mode, backpropag…

13 thms2 active usersReviewed
AnalysisProbability·Captain: mikedeng1

Discrete Analogues of Self-Decomposability and Stability 1: A p.g.f. Is Discrete Self-Decomposable iff P(z) = exp{−λ∫_z^1 (1−G(u))/(1−u) du}, iff It Is Infinitely Divisible with Nonincreasing r_nResearch Paper

A probability distribution on the real line is self-decomposable (of class L) if its characteristic function satisfies φ(t)=φ(αt) φα(t)\varphi(t)=\varphi(\alpha t)\,\varphi_\alpha(t)φ(t)=φ(αt)φα​(t) for every α∈(0,1)\alpha\in(0,1)α∈(0,1), with φα\varphi_\alphaφα​ again a characteristic function. Equivalently, a random variable XXX can be written as X=dαX′+XαX\overset{d}{=}\alpha X'+X_\alphaX=dαX′+Xα​ with X′X'X′ a copy of XXX independ…

9 thms2 active usersReviewed
Control TheoryOperations ResearchProbability·Captain: mikedeng1

Dynamic Pricing with a Prior on Market Response: Decay-Balancing Prices Earn at Least One Third of the Optimal Expected Discounted RevenueResearch Paper

A vendor holding a finite stock of a product must set prices over time without knowing how many customers will come. Each price does two things: it earns revenue now, and through the sales it generates it reveals information about demand that improves future prices. This tension between earning and learning is central in revenue management with demand…

21 thms2 active usersReviewed
Convex OptimizationRandom Matrix TheoryStatistics·Captain: mikedeng1

Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization: Convex Relaxation Attains Near-Optimal Frobenius, Entrywise and Spectral Norm ErrorsResearch Paper

Matrix completion asks for a low-rank matrix from a small random subset of its entries. It models collaborative filtering (recommendation systems), sensor-network localisation, and structure from motion. In practice the revealed entries are corrupted by noise, and the most widely used estimator is nuclear-norm regularized least squares: fit the observed…

17 thms2 active usersReviewed
AnalysisControl TheoryDynamical Systems+1·Captain: mikedeng1

Continuous-Time Average-Preserving Opinion Dynamics with Opinion-Dependent Communications 2: Regular Initial Opinions Converge to Clusters with |B − A| ≥ 1 + min{W_A, W_B}/max{W_A, W_B}Research Paper

Bounded-confidence opinion dynamics model a population in which each agent repeatedly moves its opinion towards the opinions of those agents whose views lie within a fixed distance of its own. Introduced in discrete time by Krause (1997) and studied as the Hegselmann–Krause model, these systems are a standard test case for multi-agent coordination with state…

11 thms2 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 5: A Dynamic Program Gives the Minimum Number of Late Jobs of One Agent When the Other Accepts at Most Q Late JobsResearch Paper

Multi-agent scheduling studies a machine shared by parties with their own jobs and their own objectives. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced the two-agent single-machine model: agents AAA and BBB each own a set of jobs, and the schedule must serve both. The paper frames this within multiagent systems, where agents…

10 thms2 active users
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Graphon Mean Field Systems III: With Edge Weights Sampled From a Lipschitz Graphon, Each Particle Is Within κ/n of Its Graphon Limit in Mean SquareResearch Paper

Classical mean-field theory describes nnn diffusions that interact symmetrically, each feeling the empirical average of all the others, and shows that as n→∞n\to\inftyn→∞ every particle behaves like an independent copy of a single McKean–Vlasov process. Many systems of interest are not symmetric: neurons, agents in a financial network, or oscillators interact…

10 thms2 active usersReviewed
Dynamic ProgrammingOptimizationReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 3: Under Closure up to Inherent Bellman Error ε, Every Stationary Point Is Within κε/(1−γ) of OptimalResearch Paper

Policy gradient methods search for a policy by changing a finite vector of parameters. The method can reach a stationary point of its objective without finding an optimal policy: a small change in the available parameters might not represent the policy improvement that the underlying control problem calls for. Bhandari and Russo identify a condition on the…

10 thms2 active usersReviewed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

More Risk-Sensitive Markov Decision Processes 2: The Finite-Horizon Discounted Problem Is Solved by Value Iteration on the State Extended by Accumulated Cost and DiscountResearch Paper

Sequential decisions often have costs whose timing matters. A controller may choose an action now, observe a random next state, and choose again. Ordinary expected-cost minimization averages the sum of the costs. A risk-sensitive criterion first applies an increasing function UUU to the total cost and then takes its expectation. The curvature of UUU changes how…

6 thms2 active usersReviewed
Information TheoryProbabilityRandom Matrix Theory+1·Captain: mikedeng1

Universality in Polytope Phase Transitions and Message Passing Algorithms 2: State Evolution, Empirical Averages of Polynomial AMP Iterates Converge to Gaussian ExpectationsResearch Paper

Approximate message passing (AMP) is an iterative method for large systems with random matrices. At each step, every coordinate receives a weighted combination of nonlinear messages from all other coordinates, together with a correction for dependence created by earlier steps. For symmetric random matrices, the correction makes a simple description of the…

12 thms2 active usersReviewed
PreviousPage 34 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