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
Machine LearningStatistics·Captain: mikedeng1

Robustness and Generalization III: Quantile-Value and Truncated-Mean Generalization Bounds for Pseudo-Robust AlgorithmsResearch Paper

Classical generalization bounds control the gap between the expected loss of a learned hypothesis and its average loss on the training sample. The average is sensitive to outliers: when a non-negligible fraction of the sample is corrupted, the mean loss stops describing the quality of a solution, and quantile-type summaries such as the median become the…

7 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Robustness and Generalization II: A Learning Method Generalizes w.r.t. a Training Sequence If and Only If It Is Weakly Robust w.r.t. ItResearch Paper

Most generalization guarantees in statistical learning theory bound the gap between training error and expected error through a complexity measure of the hypothesis class: VC dimension, Rademacher complexity, covering numbers. Such bounds are sufficient conditions, and they say little about why a particular algorithm, run on a particular data stream, does…

8 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchStatistics·Captain: mikedeng1

Robustness and Generalization I: A Generalization Bound for Robust AlgorithmsResearch Paper

A learning algorithm maps a training set to a hypothesis. It generalizes when the loss it incurs on the training set is close to its expected loss on fresh data. The classical way to certify this bounds the complexity of the whole hypothesis class the algorithm may output, through its VC dimension, covering numbers or Rademacher complexity. A second…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program II: Stability of the Deterministic Equivalent Convex ProgramResearch Paper

A two-stage stochastic linear program with fixed recourse chooses a first-stage decision xxx before a random vector ξ\xiξ is observed, and then pays for a cheapest corrective action yyy once ξ\xiξ is known. It is the basic model of planning under uncertainty in operations research: capacity expansion, production planning with random demand, and energy dispatch are…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program I: The Induced Feasibility Region Is a Closed Convex Polyhedron When T Is FixedResearch Paper

A two-stage stochastic program with recourse is a linear program in which a decision xxx is taken before a random vector ξ\xiξ is observed, and a corrective (recourse) decision yyy is taken afterwards at a cost. It is the basic model of planning under uncertainty in operations research: capacity expansion, production planning, energy dispatch and inventory models…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies I: The Renewal Closed Form for the Discounted Cost of a Stationary (s, S) PolicyResearch Paper

The periodic-review inventory problem with a fixed ordering cost is one of the basic models of operations research. A firm reviews its stock once per period, may order at a cost KKK per order plus a unit cost, and then faces a random demand; unmet demand is backlogged. Scarf (1960) and Iglehart (1963) showed that for this model an (s,S)(s, S)(s,S) policy is optimal:…

12 thms2 active usersReviewed
🏆Completed
Functional AnalysisMarkov ChainStatistics·Captain: mikedeng1

A Note on Metropolis–Hastings Kernels for General State Spaces II: Off-Diagonal Domination Orders the Asymptotic Variances of Reversible Kernels (Peskun's Theorem)Research Paper

Markov chain Monte Carlo (MCMC) estimates an expectation ∫f dπ\int f\,d\pi∫fdπ by the average of fff along a Markov chain whose invariant distribution is π\piπ. Many chains share the same π\piπ: every Metropolis–Hastings acceptance rule that satisfies detailed balance, every mixture of such kernels, every choice of proposal. Practitioners need a criterion for preferring…

12 thms2 active usersReviewed
🏆Completed
Markov ChainStatistics·Captain: mikedeng1

A Note on Metropolis–Hastings Kernels for General State Spaces I: Necessary and Sufficient Conditions for a Metropolis–Hastings Kernel to Satisfy Detailed BalanceResearch Paper

The Metropolis–Hastings algorithm (Metropolis et al. 1953; Hastings 1970) is the basic construction of Markov chain Monte Carlo. It turns a target probability distribution π\piπ, known only up to a constant, into a Markov chain that has π\piπ as its invariant distribution. Bayesian computation depends on it, and a sampler is usually designed by proving one…

6 thms2 active usersReviewed
🏆Completed
Number TheoryTheoretical Computer Science·Captain: mikedeng1

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer 2: Factoring from a Random ResidueResearch Paper

Shor's 1997 paper (SIAM J. Comput. 26(5), arXiv:quant-ph/9508027) gives a polynomial-time quantum algorithm for factoring integers. The quantum computer does not factor directly: it finds the multiplicative order of an element modulo nnn. The step from order finding to factoring is classical and randomized, and goes back to Miller's 1976 work on primality…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 1: Under Production Diseconomy the Retailer Earns More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Retailers hold point-of-sale data that their suppliers cannot observe, and large retailers sell access to it through data-sharing programs (Costco's CRX, Walmart's Retail Link and similar programs). When one retailer carries the substitutable products of two competing manufacturers, sharing its demand information is a strategic decision: a manufacturer who…

17 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems II: Optimal Competitiveness for the Spin-Block ProblemResearch Paper

A process on a shared-memory multiprocessor that finds a lock held must decide what to do while it waits. It can spin, repeatedly testing the lock and occupying its processor, or it can block, giving the processor to another process and paying a fixed context-switch cost CCC to be descheduled and later restored. Spinning is cheap when the lock is released…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: mikedeng1

Approximately Optimal Approximate Reinforcement Learning I: Conservative Policy Iteration Improves Monotonically and Returns a Near-Greedy PolicyResearch Paper

Approximate policy iteration and policy gradient methods are the two classical families of reinforcement learning algorithms that work with approximate, sampled information instead of an exact model. Kakade and Langford (ICML 2002) observed that neither family answers three basic questions: is there a performance measure that is guaranteed to improve at…

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Bargaining under Incomplete Information III: Trade Probability and Expected Profits in the Uniform Linear EquilibriumResearch Paper

A buyer and a seller negotiate over a single indivisible good. Each knows what the good is worth to them but not what it is worth to the other side, and each shades their offer to exploit the other's uncertainty. Chatterjee and Samuelson (Bargaining under Incomplete Information, Operations Research 31(5), 1983) modelled this as a one-shot game in which both…

11 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Exit Problems for Spectrally Negative Lévy Processes and Applications to (Canadized) Russian Options III: Optimal Stopping for the Canadized Russian OptionResearch Paper

The Russian option of Shepp and Shiryaev pays its holder, at an exercise time of their choosing, the running maximum of the stock price, discounted, with no fixed maturity. It is the standard example of a perpetual lookback option, and its value is a model problem of optimal stopping for a two-dimensional Markov process (the price and its running maximum).…

18 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders II: Clause-Based Randomized Rounding for XOS BiddersResearch Paper

In a combinatorial auction a seller offers mmm indivisible items to nnn bidders, each of whom values bundles of items rather than single items. Allocating the items so as to maximize the total value (the social welfare) is the central optimization problem of the area: it models spectrum auctions, procurement and resource allocation, and it is NP-hard and hard…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders I: LP Rounding for Subadditive BiddersResearch Paper

In a combinatorial auction a seller offers mmm indivisible items to nnn bidders, each of whom values bundles of items rather than single items. Allocating the items to maximize total value is the basic welfare problem of spectrum auctions, procurement and resource allocation, and it is the running example of algorithmic mechanism design. For general valuations…

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes XVII: Random-Horizon Consumption-Investment and the De Finetti Dividend ProblemTextbook

An insurance company collects premia and pays claims each period; the difference is a random, signed quantity that can push the company's risk reserve up or down. At the start of every period, before that period's premia and claims are realized, the company's owners may pay themselves a dividend out of the current reserve — but once the reserve goes…

11 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Markov Decision Processes X: Partially Observable Markov Decision Processes and FilteringTextbook

Every model in Chapters 2-4 assumed the controller sees the whole state before acting. Real control problems rarely offer that: a machine's true wear level, a customer's private valuation, a hidden regime driving asset returns — these are exactly the situations a decision-maker must act on despite never observing them directly, learning about them only…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 2: Under Perfect Reliability the Flexibility Premium Is Nonnegative for Every Nondecreasing UtilityResearch Paper

A manufacturer that makes several products must decide, before demand is known, how much capacity to buy. It can buy dedicated capacity, one resource per product, or a single flexible resource that can make every product. Flexible capacity pools demand: a surplus of one product's demand can be served by capacity that would otherwise sit idle. A common…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 1: The Risk-Neutral Flexibility Premium Is Nonnegative for Every ReliabilityResearch Paper

A firm that sells several products must decide, before demand is known, how much production capacity to build and of what kind. Dedicated capacity makes one product; flexible capacity makes any of them. The classic argument for flexibility is demand pooling: capacity that can follow demand to whichever product needs it wastes less than capacity locked to…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Bargaining under Incomplete Information II: The Linear Equilibrium of the Sealed-Offer Rule for Uniform ValuesResearch Paper

A buyer and a seller negotiate over one indivisible good. Each knows the good's worth to themselves but not to the other side, so each shades their offer to exploit the other's uncertainty, and some mutually profitable trades fail. Chatterjee and Samuelson (Bargaining under Incomplete Information, Operations Research 31(5), 1983) modelled this as a one-shot…

10 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix V: Sample Bound for the Mixed Unit Vector Trace EstimatorResearch Paper

Many computations in numerical linear algebra, statistics and computational physics need the trace of a matrix AAA that is never formed explicitly: AAA may be an inverse, a matrix function f(B)f(B)f(B), or a product of large operators, and the only affordable access is a routine that returns AvAvAv or vTAvv^TAvvTAv for a given vector vvv. Monte Carlo trace estimators handle this…

10 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisRandom Matrix Theory·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix III: Sample Bound for Normalized Rayleigh-Quotient Trace EstimatorsResearch Paper

Many computations in numerical linear algebra, statistics and computational physics need the trace of a matrix AAA that is never formed explicitly: AAA may be an inverse, a matrix function f(B)f(B)f(B), or a product of large operators, and the only affordable access is a routine that returns AvAvAv for a given vector vvv. Examples include log-determinants and the generalized…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 4: Optimal Prices and Discount Time with Myopic Customers and Identical Declining ValuationsResearch Paper

Retailers of fashion and seasonal goods sell a fixed stock over a short season and routinely cut the price part-way through it. The markdown trades off two effects: a late discount keeps early, high-valuation customers paying the full price, while an early discount reaches customers whose interest in the product fades as the season goes on. Aviv and Pazgal (…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Distributional Interpretation of Robust Optimization III: Uncertainty Set Shrinkage Approximates a Two-Scenario Distributionally Robust ProblemResearch Paper

Robust optimization (RO) protects a decision against every parameter value in an uncertainty set. For a decision vvv and a parameter x∈Rmx \in \mathbb{R}^mx∈Rm with objective f(v,x)f(v, x)f(v,x) to be maximized, the robust problem around a nominal parameter x0x_0x0​ with a deviation set Δ\DeltaΔ is

7 thms2 active usersReviewed
PreviousPage 57 of 62Next

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