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

1076–1100 of 1285
Open1285Completed3527All4812
ProbabilityStochastic Systems·Captain: Shuze Chen

Optimal Stopping and Free-Boundary Problems IV: Sharp Logarithmic Maximal InequalitiesTextbook

A process may make a large excursion before returning to a small terminal value. A maximal inequality quantifies how much information about that excursion is retained by a terminal observation. For nonnegative submartingales, logarithmic moments provide a useful level of control between a first moment and a fixed higher power moment. This mission concerns…

8 thms1 active userReviewed
Control TheoryProbability·Captain: Shuze Chen

Entropy Regularization for Mean Field Games with Learning: Explicit Nash equilibrium with enhanced entropyResearch Paper

A large population of interacting agents can make individual decisions depend on the distribution of everyone else's states and actions. A mean field game describes this interaction through a representative agent and population distributions. Randomizing actions allows an agent to explore while still responding to the population. Entropy regularization…

6 thms1 active userReviewed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Stability of Queueing Networks III: Fluid-Limit Stability Implies Positive Harris RecurrenceTextbook

A queueing network can have spare capacity at every station and still accumulate an ever-growing population of jobs. Service priorities and routing can prevent the available capacity from being used where it is needed. For networks with general interarrival and service distributions, an explicit stationary distribution is usually unavailable. The stability…

17 thms1 active userReviewed
Markov ChainOperations ResearchProbability+1·Captain: Shuze Chen

Stability of Queueing Networks I: Product-Form Stationary DistributionsTextbook

A queueing network describes jobs that receive service at several stations and move between them before leaving. A stationary distribution answers questions about the network at a typical time: how many jobs are waiting, which classes they belong to, and how jobs are arranged at each station. Such distributions can be difficult to determine because a…

9 thms1 active userReviewed
Convex OptimizationInformation TheoryMachine Learning+1·Captain: mikedeng1

Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal: under d^(2−δ) bits of memory, first-order methods need Ω̃(d^(1+δ/3)) queriesResearch Paper

Minimizing a convex Lipschitz function over the unit ball of Rd\mathbb R^dRd to accuracy ϵ\epsilonϵ takes Θ(dlog⁡(1/ϵ))\Theta(d\log(1/\epsilon))Θ(dlog(1/ϵ)) first-order queries when ddd is small compared with 1/ϵ1/\epsilon1/ϵ, and cutting-plane methods such as the center-of-mass method attain this rate (Nemirovski–Yudin 1983). They do so by storing their whole cutting history, about …

18 thms1 active userReviewed
Machine LearningOptimizationReinforcement Learning·Captain: mikedeng1

Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima: Neural TD with Stochastic Semigradients Converges to the Global Optimum of the MSPBE at Rate 1/√TResearch Paper

Temporal-difference (TD) learning estimates the value of a policy in a Markov decision process from sampled transitions, by repeatedly moving a parametrized value function towards a one-step bootstrapped target (Sutton, 1988). With a linear parametrization its behaviour is well understood: TD converges to the fixed point of the projected Bellman equation (Ts…

10 thms1 active userReviewed
Differential GeometryLinear algebraOptimization·Captain: mikedeng1

On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization: Gradient and Hessian Connections for Fixed-rank PSD Matrices via YYᵀResearch Paper

Many estimation problems in statistics, signal processing and machine learning ask for a low-rank positive semidefinite matrix: phase retrieval, matrix sensing, PCA-type problems and the Burer–Monteiro approach to semidefinite programs. A standard formulation is

14 thms1 active userReviewed
Actuarial ScienceOperations ResearchProbability·Captain: mikedeng1

A Theory for Measures of Tail Risk: A Tail Risk Measure Is Coherent, Convex or Monetary if and Only if Its Generator IsResearch Paper

Banking and insurance regulation measures capital requirements with risk measures that look only at the tail of a loss distribution. The Basel framework moved from Value-at-Risk (VaR) to Expected Shortfall (ES) for market risk (BCBS, Minimum capital requirements for market risk, 2016), and both VaR and ES at level ppp depend on a loss only through its…

15 thms1 active userReviewed
Convex OptimizationOperations ResearchOptimization+1·Captain: Shuze Chen

Robust Optimization XII: Finite-Horizon Robust Bellman RecursionTextbook

A routing decision can have a known immediate cost while its consequences depend on uncertain weather. A controller observes the current state, chooses an action, and then faces a random next state. A policy optimized for one estimated transition model may perform poorly when those estimates change. Chapter 13 of Ben-Tal, El Ghaoui and Nemirovski, Robust…

4 thms1 active userReviewed
Algebraic GeometryOptimizationRepresentation Theory·Captain: mikedeng1

A Convex Form That Is Not a Sum of Squares: For k ≥ 17 the Octonionic Cauchy–Schwarz Form Plus (1/4)(‖x‖² + ‖y‖²)² Is a Convex Quartic in 16k Variables That Is Not a Sum of SquaresResearch Paper

A convex form is a homogeneous polynomial of even degree whose value is convex as a function of its real variables. Every convex form is nonnegative, so it is natural to ask whether it can always be written as a sum of squares (SOS) of real polynomials. This matters in polynomial optimization because an SOS certificate can be searched for through…

11 thms1 active userReviewed
Differential GeometryNumerical AnalysisOptimization·Captain: mikedeng1

Active-Set Newton Methods and Partial Smoothness: Transversal C² Manifolds with a Constant-Rank Map Between Them Yield a Quadratically Convergent Active-Set Newton IterationResearch Paper

Active-set methods for optimization and variational problems run in two phases. A globally convergent first phase identifies which constraints are active at the solution; once they are identified the problem simplifies locally, and a second phase converges fast, typically by linearizing the simplified problem. Sequential quadratic programming for nonlinear…

9 thms1 active userReviewed
Algorithmic Game TheoryEconomicsMechanism Design·Captain: mikedeng1

Interim Rationalizable Implementation of Functions: Weak Interim Rationalizable Monotonicity and the Weak No-Worst-Rule Condition Suffice for Implementation in Interim Rationalizable StrategiesResearch Paper

A mechanism designer chooses a rule for turning agents’ messages into an outcome. When agents know their own types but have only beliefs about the others, the designer cannot assume that they use a single equilibrium strategy. Interim correlated rationalizability instead keeps every message that is a best response to some belief consistent with the agent’s…

12 thms1 active userReviewed
Algebraic GeometryOptimization·Captain: mikedeng1

Exploiting Sign Symmetries in Minimizing Sums of Rational Functions: The Sign-Symmetry-Adapted Block-Diagonal SOS Hierarchy Converges Monotonically to the Global MinimumResearch Paper

A sum of rational functions is a common objective when several performance measures each have a polynomial numerator and a positive polynomial denominator. Such problems appear, for example, in the applications to computer vision and signal processing cited by Guo, Wang and Zheng in their 2024 preprint. Even when all constraints and numerators are…

13 thms1 active userReviewed
Algorithmic Game TheoryControl TheoryProbability·Captain: mikedeng1

A Probabilistic Approach to Extended Finite State Mean Field Games: With Lipschitz Rates and Costs and a Unique Hamiltonian Minimizer, a Nash Equilibrium in Closed-Loop Strategies ExistsResearch Paper

Mean field games describe the limit of stochastic differential games with a large number of statistically identical players, each interacting with the others only through the empirical distribution of their states (Lasry and Lions, Mean field games, 2007; Huang, Malhamé and Caines, 2006). Models whose players move among finitely many states (an infection…

12 thms1 active userReviewed
Bandit AlgorithmsMachine LearningProbability+1·Captain: mikedeng1

Nonasymptotic Analysis of Monte Carlo Tree Search: UCB with a Polynomial Bonus on a Non-Stationary Bandit Converges and Concentrates PolynomiallyResearch Paper

Monte Carlo tree search repeatedly chooses actions using estimates built from earlier simulations. The rewards attached to an action need not form an independent, identically distributed sequence: deeper parts of the search tree change as the search proceeds. Shah, Xie and Xu isolate this difficulty in a non-stationary multi-armed bandit and study a version…

9 thms1 active userReviewed
Machine LearningProbabilityReinforcement Learning+1·Captain: mikedeng1

Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Asymptotic Normality of the RNPG Error, with Reuse Shrinking the Joint-Noise Covariance by 1/KResearch Paper

In reinforcement learning, each policy update may require new interaction with an environment. When interaction is costly, an optimizer can retain past trajectories and use them again, provided it corrects for the different policy that generated them. Lin, Wang, and Zhou study this idea for natural policy gradient, using importance weights to reuse earlier…

10 thms1 active userReviewed
CombinatoricsProbabilityStochastic Systems·Captain: mikedeng1

Conditional Uniformity and Hawkes Processes: Given Its Size, a Hawkes Cluster's Compensator Points Are ρ Times the Order Statistics of a Uniform Random Parking Function Minus i.i.d. UniformsResearch Paper

Hawkes processes are point processes in which every event raises the rate of future events. They are used to model contagion in financial markets, earthquake aftershocks, the spread of posts on social networks and arrivals to service systems (Hawkes 1971; Hawkes and Oakes 1974). Hawkes and Oakes showed that a stationary Hawkes process is a Poisson stream of…

10 thms1 active userReviewed
AlgebraAlgebraic GeometryOptimization·Captain: mikedeng1

A Sparse Version of Reznick’s Positivstellensatz: Under the Running Intersection Property, a Sparse Positive Definite Form Is a Sum of Sparse SOS Fractions with Uniform DenominatorsResearch Paper

A polynomial that is positive away from the origin can be certified by writing it as a sum of squares after multiplication by a suitable power of the squared Euclidean norm. This is the uniform denominator theorem of Reznick (1995). In polynomial optimization, the size of a sum of squares certificate is governed by the number of variables in each square. A…

10 thms1 active userReviewed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes: The SmoothBandit Algorithm Has Regret Õ(T^((β+d−αβ)/(2β+d)) + 1) on Every Hölder-Smooth InstanceResearch Paper

In a contextual bandit a decision maker repeatedly observes a context XtX_tXt​, chooses one of two actions, and sees the reward of that action only. Personalised medicine, dynamic pricing and online advertising have this structure: the reward of the action not taken is never observed, so learning and earning must be balanced. Performance is measured by the regret…

11 thms1 active userReviewed
Optimal TransportOptimizationProbability·Captain: mikedeng1

Convergence Rates for Regularized Optimal Transport via Quantization: Entropic and f-Divergence Rates for Costs with Bounded Second Derivative via Martingale Quantization of an Optimal PlanResearch Paper

Optimal transport asks how cheaply several prescribed probability distributions can be coupled. Adding a divergence penalty relative to their independent product makes the problem amenable to numerical methods, but changes its value. A quantitative bound on that change tells users of regularized transport how much bias a chosen regularization parameter can…

7 thms1 active userReviewed
Algorithmic Game TheoryConvex OptimizationEconomics+1·Captain: mikedeng1

Constrained Information Design: The Value of an Information Design Problem with Equality and Inequality Constraints Equals the Concave Hull of the Constraint-Modified Objective at the PriorResearch Paper

In information design (Bayesian persuasion), a designer commits to a signal about an unknown state, and every signal induces a distribution over the receiver's posterior beliefs. Kamenica and Gentzkow (2011) showed that the distributions a signal can induce are exactly the Bayes-plausible ones, those whose mean posterior is the prior, and that the…

7 thms1 active userReviewed
EconomicsProbabilityStatistics·Captain: mikedeng1

The Distortion in Prices Due to Passive Investing: Market Indexing Leaves the Price Efficiency of the Market Portfolio Unchanged and Erodes That of Every Other Portfolio at an Increasing RateResearch Paper

Passive funds hold a market index rather than selecting individual stocks. In the model of Baruch and Zhang (2022), this difference matters for what prices reveal. An investor who studies individual stocks can bring information about their payoffs into trading; an investor restricted to the market portfolio cannot make the same stock-by-stock trades. The…

8 thms1 active userReviewed
Machine LearningProbabilityStochastic Systems·Captain: mikedeng1

Mean Field Analysis of Deep Neural Networks: The SGD-Trained Two-Hidden-Layer Network Converges, as Its Layer Widths Grow in Turn, to the Unique Solution of a Limiting Integro-Differential SystemResearch Paper

A neural network can change its behavior substantially when both its width and its training duration grow. For a network with two hidden layers, the parameters of the layers interact during training, so a large-width description must account for the output of the actual optimization algorithm. Sirignano and Spiliopoulos study this question for online…

9 thms1 active userReviewed
Algorithmic Game TheoryControl TheoryProbability·Captain: mikedeng1

Terminal Ranking Games: The Rank-Based Mean Field Tournament Has an Equilibrium, Characterized by an Explicit Quantile Formula, a Fixed-Point Equation for the Mean and an Explicit Game ValueResearch Paper

Tournaments and contests reward agents by their relative standing: sales bonuses for the top performers, promotions, prizes for the first to finish, research competitions. Since Lazear and Rosen (Rank-order tournaments as optimum labor contracts, 1981) such rank-order incentives have been a standard object in economics and operations research, and the…

7 thms1 active userReviewed
Algorithmic Game TheoryControl TheoryProbability+1·Captain: mikedeng1

Dynamic Set Values for Nonzero-Sum Games with Multiple Equilibriums: The Set Value of a Continuous-Time Nonzero-Sum Stochastic Differential Game Satisfies the Dynamic Programming PrincipleResearch Paper

A nonzero-sum game can have several Nash equilibria with different cost vectors. Selecting one equilibrium before asking how the game behaves over time loses information and may make a proposed dynamic rule depend on that selection. Feinstein, Rudloff and Zhang study the entire set of equilibrium cost vectors and ask whether it can be evaluated consistently…

14 thms1 active userReviewed
PreviousPage 44 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