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

226–250 of 1285
Open1285Completed3527All4812
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: iris

Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive: Static Vertex Prices Earn One Third of the Prophet's Expected Matching ValueResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a prophet who sees every value in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) shows that a single threshold earns half of the prophet's expected maximum. These guarantees are the analytic core of poste…

18 thms3 active usersReviewed
Machine LearningOperations ResearchOptimization+1·Captain: iris

Langevin Dynamics Based Algorithm e-THεO POULA for Stochastic Optimization Problems with Discontinuous Stochastic Gradient: Non-Asymptotic Bound on the Expected Excess RiskResearch Paper

Many stochastic optimization problems in machine learning, finance and insurance minimize an expectation u(θ)=E[U(θ,X)]u(\theta)=E[U(\theta,X)]u(θ)=E[U(θ,X)] whose stochastic gradient is discontinuous in the parameter: quantile estimation, vector quantization, CVaR minimization and networks with ReLU activation all have this form. The objective may also be non-convex, and its gradient…

28 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: iris

Optimal Policy for Inventory Management with Periodic and Controlled Resets: Under the Discount-Factor Bound (29), a Four-Threshold (σ, s, S, Σ) Reset-and-Order Policy Is OptimalResearch Paper

Many stocked goods can be thrown out and restarted: a water reservoir that becomes contaminated, a product line that is replaced, perishable stock that is discarded. In each case a manager decides each period how much to order and also whether to reset, that is, discard the whole stock and start again from empty. Lee, Mintz, Aswani, Shen and Yang (arXiv:2209…

24 thms3 active usersReviewed
Bandit AlgorithmsDynamic ProgrammingMarkov Chain+1·Captain: iris

Unichain and Aperiodicity Are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits: The Set-Expansion Policy Has Optimality Gap at Most 256 r_max λ_W²|S|²/(β²√N)Research Paper

A restless bandit couples NNN identical Markov decision processes through a budget: at every time step exactly αN\alpha NαN of the NNN arms must be pulled, and every arm changes state whether it is pulled or not. The model, introduced by Whittle (1988), describes scheduling of machines or patients, sensor management, queueing control and recommendation. Computing…

23 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Online Resource Allocation under Partially Predictable Demand: The Non-Adaptive Threshold Algorithm Is p + (1−p)/(2−a) − O(√(log n / b)/(a(1−p)p)) CompetitiveResearch Paper

A firm sells bbb identical units over nnn periods. In each period at most one customer arrives, pays 111 (type 1) or a∈(0,1)a\in(0,1)a∈(0,1) (type 2), and must be accepted or rejected on arrival. This two-fare problem is the basic model of revenue management and of online resource allocation (advertising budgets, hotel rooms, cloud capacity). Two arrival models dominate its…

22 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

Delay-Adaptive Learning in Generalized Linear Contextual Bandits: Under Independent Delays with a Tail Envelope, DUCB-GLCB Satisfies the Regret Bound (16) with Probability at Least 1 − 5δResearch Paper

In many sequential decision problems the outcome of a decision arrives late. A recommendation's conversion, a clinical response or a sale is observed hours or weeks after the action, and in the meantime the decision maker has to keep acting. Contextual bandits model the decision side: at each round a learner sees side information, chooses one of KKK actions…

18 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

Rate-Optimal Bayesian Simple Regret in Best Arm Identification: Two-Stage Exploration Has Bayesian Simple Regret at Most Copt/T′+o(1/T)C_{\mathrm{opt}}/T' + o(1/T)Copt​/T′+o(1/T)Research Paper

A clinical trial, an A/B test or a simulation study often ends with one decision: which treatment to adopt. Multi-armed bandit theory calls this best arm identification. When the arm means are fixed, the frequentist simple regret after TTT pulls decays exponentially at each instance, with a rate that degenerates as the gap closes. A practitioner who has a…

39 thms3 active usersReviewed
AnalysisOperations ResearchOptimization·Captain: iris

The Exact Modulus of the Generalized Concave Kurdyka-Łojasiewicz Property: The Exact Modulus Is the Smallest Concave Desingularizing FunctionResearch Paper

The Kurdyka–Łojasiewicz (KL) inequality is the regularity condition behind most convergence proofs for first-order methods on nonconvex, nonsmooth problems: proximal gradient, PALM, proximal ADMM and their variants. Near a point xˉ\bar xxˉ, it asks that

16 thms3 active usersReviewed
CombinatoricsConvex OptimizationLinear Optimization+1·Captain: iris

On Polyhedral Approximations of the Positive Semidefinite Cone: Every Polytope Between (1−ε)(D − A) and D − A Has Extension Complexity at Least exp(c√n)Research Paper

Linear programs are the workhorse of optimization, and a recurring question is which convex sets can be described, or approximated, by a linear program of small size. The relevant measure is the extension complexity xc⁡(P)\operatorname{xc}(P)xc(P) of a polytope PPP: the smallest number of facets of a polytope that projects linearly onto PPP. If xc⁡(P)=N\operatorname{xc}(P)=Nxc(P)=N,…

26 thms3 active usersReviewed
AnalysisConvex OptimizationOptimization·Captain: iris

Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem: The KL Inequality Holds at Every Optimal Solution with Exponent 3/4 in the TRS-Ill Case and 1/2 OtherwiseResearch Paper

The trust region subproblem (TRS) asks for the minimum of a quadratic function over the Euclidean unit ball. It is the inner step of trust region methods for nonlinear optimization, and it also arises in robust optimization and regularized least squares. When the quadratic form is indefinite the problem is nonconvex, yet it has hidden convexity: strong…

49 thms3 active usersReviewed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: iris

Adaptive Discretization in Online Reinforcement Learning: AdaMB and AdaQL Have Regret Scaling with the Zooming DimensionResearch Paper

Reinforcement learning in operations problems (inventory control, ambulance routing, pricing, queue admission) often has continuous state and action spaces. A fixed grid of mesh ϵ\epsilonϵ wastes samples on regions where nothing is learned, and its regret grows with the ambient dimension of S×A\mathcal S\times\mathcal AS×A. Adaptive discretization refines a…

37 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: iris

Approximation Schemes for Capacity-Constrained Assortment Optimization Under the Nested Logit Model: A Dynamic Program Earns 1 − ε of Optimal in Time Polynomial in Input Size, 1/ε and γ⁺/γ⁻Research Paper

The Nested Logit model is one of the most widely used discrete choice models in revenue management. It captures substitution that the Multinomial Logit model cannot: products are grouped into nests, a customer first chooses a nest and then a product in it (Davis, Gallego, Topaloglu, 2014; Gallego, Topaloglu, 2014). A retailer that decides which products to…

24 thms3 active usersReviewed
Convex OptimizationProbabilityStochastic Systems·Captain: iris

An SDE Perspective on Stochastic Convex Optimization: The Gradient SDE Has a Unique Solution and, Under Square-Integrable Noise, Converges Almost Surely to a MinimizerResearch Paper

First-order methods for convex minimization rarely see an exact gradient: in stochastic gradient descent and its relatives the gradient is perturbed by sampling or measurement noise. A standard way to study the long-time behaviour of such methods is to pass to continuous time, where the deterministic gradient flow x˙=−∇f(x)\dot x=-\nabla f(x)x˙=−∇f(x) is replaced by a…

23 thms3 active usersReviewed
Algorithmic Game TheoryControl TheoryOperations Research+2·Captain: iris

Quantitative Convergence for Displacement Monotone Mean Field Games with Controlled Volatility: Open-Loop Nash Equilibria Converge to the Mean Field Equilibrium at Rate 1/NResearch Paper

Mean field games describe Nash equilibria of stochastic differential games with very many symmetric players, each of whom interacts with the others only through the empirical distribution of their states. The limiting model, introduced by Lasry and Lions and by Huang, Malhamé and Caines, replaces the population by a measure flow and the NNN-player equilibrium…

17 thms3 active usersReviewed
Convex OptimizationNumerical AnalysisOptimization·Captain: iris

A Squared Smoothing Newton Method for Semidefinite Programming: Under Primal and Dual Constraint Nondegeneracy the Huber-Based Method Converges Superlinearly with Order 1+τ1+\tau1+τResearch Paper

Semidefinite programming (SDP) minimizes a linear function of a symmetric matrix subject to linear equations and positive semidefiniteness. It is a standard modelling tool in control, combinatorial optimization, statistics and quantum information. Interior point methods solve SDPs accurately but each iteration factorizes a dense m×mm\times mm×m Schur complement,…

22 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Performance of the Smallest-Variance-First Rule in Appointment Sequencing: under the dilation ordering, svf with mean-based schedules costs at most four times the optimal sequenceResearch Paper

In outpatient clinics, surgery blocks and other appointment systems, a provider sees nnn clients one after another, each with a random service time. Two decisions determine how long clients wait and how long the provider sits idle: the sequence (who goes in which slot) and the schedule (how long each slot is). Finding the optimal sequence is hard even with…

16 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Compact Extended Formulations for Low-Rank Functions with Indicator Variables: cl⁡conv⁡(Q)\operatorname{cl}\operatorname{conv}(Q)clconv(Q) from the Pieces V(I)V(I)V(I) with ∣I∣≤k|I| \le k∣I∣≤k and the Ray Set RRRResearch Paper

Many optimization models in statistics, machine learning and finance minimize a convex function of a continuous vector x∈Rnx\in\mathbb R^nx∈Rn under logical conditions on its support. Best subset selection, sparse regression and sparse portfolio selection are standard cases. A binary indicator variable ziz_izi​ models such a condition: zi=0z_i=0zi​=0 forces xi=0x_i=0xi​=0, and zi=1z_i=1zi​=1 leave…

12 thms3 active usersReviewed
Numerical AnalysisOperations ResearchOptimization·Captain: iris

A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems: One PolyakBundle Step Gives f(x̃) − f* ≤ Cₛ(f(x) − f*)^(1+η) Near a Sharp (b)-Regular MinimizerResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R from first-order information alone. At a sharp minimum, where fff grows at least linearly away from its solution set, the Polyak step x+=x−f(x)−f∗∥v∥2vx^+=x-\frac{f(x)-f^*}{\|v\|^2}vx+=x−∥v∥2f(x)−f∗​v converges linearly (Polyak 1969; in the convex and weakly convex settings, Davis,…

15 thms3 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: iris

Static Pricing for Multi-unit Prophet Inequalities: The Static Price Equalizing E[min(Xₚ,k)]/k and P[Xₚ ≤ k − 1] Earns at Least φₖ, Its Poisson Value, of the Expected Optimal WelfareResearch Paper

A seller has kkk identical units and faces nnn buyers who arrive one at a time. Each buyer's value is drawn independently from a known distribution, but the arrival order is adversarial and unknown. The simplest selling policy posts one static price to every buyer until the units run out. Prophet inequalities compare such a policy with a prophet who sees all…

23 thms3 active usersReviewed
Operations ResearchProbabilityStatistics+1·Captain: iris

Diffusion Approximations for a Class of Sequential Experimentation Problems: The Optimal Stopping Value of the Belief Diffusion Is the Maximum of the Closed-Form Two-Action ValuesResearch Paper

A firm about to launch a product, a platform choosing which items to display, or a regulator testing a treatment must pick one action from a finite menu while uncertain about which of two states of the world holds. Before committing, it can run experiments, each of which shifts its belief. Experimenting has a cost in time, modelled by discounting, and the…

30 thms3 active usersReviewed
Machine LearningOptimizationProbability·Captain: iris

Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions: The Iterates Almost Surely Avoid Active Strict Saddles Satisfying the Verdier and Angle ConditionsResearch Paper

Training a neural network or fitting a nonsmooth statistical model usually means running the stochastic subgradient method on a function that is neither smooth nor convex. Convergence theory gives limit points that are Clarke critical (Davis et al., 2020; Bolte and Pauwels, 2021), but Clarke critical points include points that no one wants, and a…

27 thms3 active usersReviewed
Convex OptimizationDynamical SystemsOperations Research+1·Captain: iris

Fast Convex Optimization via Time Scale and Averaging of the Steepest Descent: Inertial Dynamics with Implicit Hessian Damping Converge Weakly with Gradient Rate o(1/s²)Research Paper

Second-order dynamics with vanishing damping are the continuous-time models of accelerated first-order methods, so a rate proved for such a dynamic predicts the behaviour of an algorithm class used across large-scale convex optimization. The line of work runs as follows.

25 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOperations Research+1·Captain: iris

Playing Divide-and-Choose Given Uncertain Preferences: For Independent Normal Priors, Algorithm 1 Is a Fully Polynomial-Time Approximation Scheme for the Divider's UtilityResearch Paper

Divide-and-choose is the oldest fair-division protocol: one player cuts, the other picks. With known preferences its analysis is classical: the chooser always gets at least half of her value (proportionality), and the divider, knowing her values, cuts so that she is indifferent and keeps everything above half that the difference in tastes allows. In…

31 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: iris

Diffusion Limit of Fair Resource Control: Under Aθ < 0 and Bounded Workload, Stationary Workloads Converge to the Diffusion Limit's Stationary Law, with Moments of Order m < p − 1Research Paper

Bandwidth-sharing networks model data transfers that each occupy several links of a communication network at once. Under proportional fair (PF) allocation, introduced by Kelly, Maulloo and Tan (J. Oper. Res. Soc. 1998), the capacity of the links is split among the active transfers by maximizing a weighted sum of logarithms. Exact steady-state distributions…

21 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchReinforcement Learning+1·Captain: iris

Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games: VI-LCB-Game Returns an ε-Nash Policy Pair with Probability 1−δ from c₁·C⋆_clipped·S(A+B)·log(N/δ)/((1−γ)³ε²) Offline SamplesResearch Paper

Many sequential decision problems with two adversaries are modelled as zero-sum Markov games (Shapley, 1953; Littman, 1994): two players act simultaneously in a shared state, one maximizes and the other minimizes the same discounted reward. In applications such as games, security and robust control, interaction with the system is expensive or unsafe, and…

19 thms3 active usersReviewed
PreviousPage 10 of 52Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36415412
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