Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

MNL-Bandit: A Dynamic Learning Approach to Assortment Selection I: The Epoch-Based UCB Policy Has Regret at Most C₁√(NT log NT) + C₂N log² NT Under the No-Purchase AssumptionResearch Paper

A retailer that decides which products to display, an online platform that decides which items to show in a recommendation slot, and an airline that decides which fare classes to open all face the same problem: the set of options offered changes what customers buy, and the substitution pattern is not known in advance. The multinomial logit (MNL) model is…

15 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Stochastic Matching: Beating 1-1/e 1: When OPT = Ω(n), the Two Suggested Matchings Algorithm Achieves ALG/OPT ≥ (1 − 2/e²)/(4/3 − 2/(3e)) − ε ≈ 0.670 with Probability 1 − e^(−Ω(n))Research Paper

Online bipartite matching models a platform that must commit each arriving request to a resource immediately. The motivating application of Feldman, Mehta, Mirrokni and Muthukrishnan is display advertising: an ad server knows from past traffic how many impressions of each type (web page, audience segment) to expect, sells them to advertisers in advance, and…

28 thms5 active users
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Coordinating Inventory Control and Pricing Strategies with Random Demand and Fixed Ordering Cost: The Finite Horizon Case 1: Additive Demand: k-Concave Profit-to-Go, Optimal (s, S, p) PolicyResearch Paper

A retailer that sets both its replenishment quantities and its prices over a finite selling season faces a coupled decision: the price shapes the demand that the inventory must serve, and the inventory position shapes which price is worth charging. With a fixed cost per order, the classical inventory answer is the (s, S) policy of Scarf (1960): when the…

11 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XV: SVRG with η = 1/(10β) and k = 20κ Contracts the Expected Optimality Gap by 0.9 per EpochTextbook

Many optimization problems in machine learning minimize an average of losses, one loss for each observation. A full gradient step examines every observation, while a stochastic gradient step examines one. The latter is cheaper per step, but its sampled gradient can remain noisy even near the optimum. Section 6.3 of Bubeck's monograph studies stochastic…

14 thms5 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 3: Monotone, Absolutely Homogeneous, Convex-Hull Invariant and Subadditive R_n, and the 2L Bound for L-Lipschitz Maps Fixing 0Research Paper

Generalization bounds in statistical learning theory control the gap between the empirical and the true performance of a predictor chosen from a class FFF. Bartlett and Mendelson (JMLR 3, 2002) showed that this gap is governed by the Rademacher complexity of a loss class built from FFF, and that, unlike the VC dimension, this complexity can be estimated from…

7 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

Asymptotic Optimality of Order-up-to Policies in Lost Sales Inventory Systems: Ordering Up to the Newsvendor Level for Penalty b + τh Is Asymptotically Optimal as b → ∞Research Paper

Periodic-review inventory systems face a simple choice each period: how much to order before the next demand is known. When unmet demand is lost, the order can affect the stock available several periods later without preserving a backlog that records earlier shortages. This makes the optimal policy difficult to describe when replenishment takes time. An orde…

16 thms5 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 1: With Probability 1 − δ, Expected Loss ≤ Empirical Dominating Cost + R_n(φ̃∘F) + √(8 ln(2/δ)/n) for Every f in FResearch Paper

A learning algorithm picks a predictor fff from a class FFF after looking at nnn training examples, and the quantity of interest is its expected loss on a fresh example. Since fff depends on the data, its training error is a biased estimate of that loss, and a risk bound quantifies the bias uniformly over the class: with high probability, every f∈Ff \in Ff∈F has expected…

10 thms5 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Reversibility and Stochastic Networks II: Migration Processes with Blocking — Reversibility and Product-Form EquilibriumTextbook

A migration process is a continuous-time Markov model of a population spread over JJJ sites, called colonies, in which individuals move one at a time: between colonies, out of the system, or into it from outside. The model was introduced by Whittle (1967) and Kingman (1969) and is the framework of Chapter 2 of F. P. Kelly, Reversibility and Stochastic Networks…

10 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Analysis of Thompson Sampling for the Multi-armed Bandit Problem 1: Logarithmic Regret for Two ArmsResearch Paper

Thompson Sampling (TS) is the oldest heuristic for the stochastic multi-armed bandit problem: it was proposed by Thompson in 1933 (Biometrika 25) and is used in practice for online advertising and recommendation, where it often performs as well as or better than upper-confidence-bound methods (Chapelle and Li, NIPS 2011; Scott 2010). Until 2012 its…

12 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Introduction to the Scenario Approach I: The Violation Distribution of the Scenario SolutionTextbook

Many design problems in control, finance and operations research are convex programs with uncertain constraints: a decision θ\thetaθ must satisfy θ∈Θδ\theta\in\Theta_\deltaθ∈Θδ​ for a parameter δ\deltaδ that is not known in advance. Enforcing the constraint for every possible δ\deltaδ (robust optimization) is often intractable or too conservative, and a chance-constrained…

16 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems III: The Optimal Randomized Two-Server Ratio on the 1-d-d Isosceles TriangleResearch Paper

The k-server problem of Manasse, McGeoch and Sleator (J. Algorithms 11 (1990)) asks how kkk mobile servers in a metric space should respond, on-line, to a sequence of requests at points of the space, each of which must be covered by a server. It is the central model of on-line computation: paging is the special case of a uniform metric, and many caching and…

9 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Optimal Best Arm Identification with Fixed Confidence IV: Asymptotic Optimality of the Track-and-Stop StrategyResearch Paper

In best arm identification with fixed confidence, a learner samples KKK unknown distributions (arms) sequentially and must, as early as possible, name the arm with the largest mean, while being wrong with probability at most a prescribed risk δ\deltaδ. The problem models adaptive A/B/n testing, clinical and simulation-based selection among alternatives, and the…

17 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Optimal Best Arm Identification with Fixed Confidence I: Non-Asymptotic Lower Bound on the Sample ComplexityResearch Paper

Best arm identification with fixed confidence is the pure-exploration counterpart of the multi-armed bandit problem. A learner faces KKK unknown reward distributions ("arms"), samples them sequentially, and must stop and name the arm with the largest mean, being wrong with probability at most a prescribed δ\deltaδ. The question is how many samples this…

15 thms5 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities III: Uniform Convergence and the Entropy per ObservationResearch Paper

Estimating a probability by the relative frequency of the event in an independent sample is justified for one event by the law of large numbers. Statistics and learning theory need more: the frequencies of a whole class of events SSS must approach their probabilities simultaneously, so that a quantity chosen after looking at the data (the empirical risk…

20 thms5 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research+1·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 2: Mean–Gini Optimal Portfolios Exist and Are SSD-EfficientResearch Paper

Portfolio selection and other decisions under risk are routinely solved as mean–risk models: maximize the expected outcome minus a multiple of a risk measure over the feasible set. Such a model is computationally convenient, but it is only defensible if its answers agree with the preferences of risk-averse decision makers. The standard formal expression of…

13 thms5 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Limits of Permutation Sequences II: Convergence Is Equivalent to Being Cauchy in the Rectangular DistanceResearch Paper

For dense graphs, convergence of subgraph densities was shown by Lovász and Szegedy (2006) to have graphons as limit objects, and Borgs, Chayes, Lovász, Sós and Vesztergombi (2008) proved that the same convergence is metric: a graph sequence converges exactly when it is Cauchy in the cut distance. The metric view is what makes the space of graphons compact…

23 thms5 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningRandom Matrix Theory+1·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion II: Exact Nuclear-Norm Recovery from Nearly Minimally Many EntriesResearch Paper

Many data sets are large matrices of which only a small fraction of the entries is observed, and of which the underlying object is believed to have low rank: user–item rating tables in collaborative filtering, distance matrices in sensor-network localization, and measurement matrices in structure-from-motion. Matrix completion asks when the missing entries…

22 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 1: Exact Worst-Case VaR under Known Mean and Covariance and Its SDP RepresentationsResearch Paper

Value-at-Risk (VaR) is the standard regulatory measure of downside risk of a portfolio: the loss level that is exceeded only with a prescribed small probability ε\varepsilonε. Computing it requires the full distribution of asset returns, which is rarely known. In practice one estimates a mean vector and a covariance matrix and then assumes a Gaussian…

8 thms5 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Limits of Permutation Sequences I: Every Convergent Permutation Sequence Has a Limit Permutation, and Every Limit Permutation Is a LimitResearch Paper

Large combinatorial structures are often best understood through their limits. For dense graphs, Lovász and Szegedy (2006) showed that every sequence of graphs whose subgraph densities converge has a limit object, a graphon, and that every graphon arises this way. Borgs, Chayes, Lovász, Sós and Vesztergombi (2008) related this convergence to the cut…

18 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

On Properties of Stochastic Inventory Systems I: Using the EOQ Order Quantity in the Stochastic (Q, r) Model Raises Costs by at Most 1/8Research Paper

The economic order quantity (EOQ) is the most widely used formula in inventory management. It assumes that demand is a deterministic constant stream. Real demand is random, and the model that accounts for this, the continuous-review (Q,r)(Q, r)(Q,r) policy with stochastic demand, has no closed-form optimum: for decades its optimal parameters were computed…

18 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchOptimization·Captain: naimengye

Multi-armed Bandit Allocation Indices III: Superprocesses, Condition D and the Index Theorem for a SFASTextbook

The index theorem says that among several Markov reward processes, of which one may be advanced at each decision time, the right one to advance is the one of greatest Gittins index. Chapter 4 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), asks how far this extends when the constituents are not…

10 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchOptimization·Captain: naimengye

Multi-armed Bandit Allocation Indices II: Jobs, Parallel Machines, Search and Bandit-Dependent DiscountingTextbook

Chapter 3 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), asks which of the assumptions behind the index theorem can be dropped and which cannot, using the simplest bandit processes there are: jobs, which pay a single reward when they complete. Along the way it settles three questions that matter…

8 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: naimengye

Multistage Stochastic Optimization III: Distortion Risk Functionals and Their Dual RepresentationTextbook

A decision maker who does not want to be judged by expected loss alone needs a functional that weighs the bad outcomes more heavily than the good ones and still behaves well under optimization: monotone, convex, unchanged by shifting the loss, and scaling with it. Kusuoka's theorem (mission II) says every such law-invariant functional on an atomless space…

11 thms5 active usersReviewed
🏆Completed
Functional Analysis·Captain: mikedeng1

Markov Processes: Characterization and Convergence 15: Diffusions in smooth bounded regionsTextbook

Diffusion models in a bounded region need a rule for what happens when a path reaches the boundary. Two standard mechanisms are absorption, where the boundary kills the generator contribution, and oblique reflection, where a prescribed vector field pushes the process back into the region. Ethier and Kurtz treat these mechanisms as neighboring variants of…

46 thms5 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization I: Kantorovich Duality and Strong Duality for the Worst-Case RiskTextbook

Every data-driven decision problem faces the same trap. A decision-maker estimates a risk functional R(P,ℓ)=EP[ℓ(ξ)]R(P,\ell) = \mathbb{E}_P[\ell(\xi)]R(P,ℓ)=EP​[ℓ(ξ)] from a nominal distribution P^N\hat P_NP^N​ built from NNN training samples, then optimizes a loss function ℓ\ellℓ against P^N\hat P_NP^N​ instead of the unknown true distribution PPP. Because the optimizer adapts to the noise in P^N\hat P_NP^N​,…

23 thms5 active users
PreviousPage 7 of 110Next

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