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
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 2: The Decomposition Policy Is Average-Cost OptimalResearch Paper

Many supply chains move stock through a central warehouse to the retail locations that face customer demand. Deciding how much the warehouse should order from outside, and how much it should ship to each retailer and when, is a stochastic dynamic program whose state contains every stock level and every outstanding order. Exact solution is out of reach…

11 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Non-Strongly-Convex Smooth Stochastic Approximation with Convergence Rate O(1/n): Averaged Constant-Step-Size LMS Has Expected Excess Risk at Most (1/2n)[σ√d/(1−√(γR²)) + R‖θ₀−θ*‖/√(γR²)]²Research Paper

Least-squares regression fitted by stochastic gradient descent — the least-mean-square (LMS) algorithm — is the basic large-scale learning procedure: each observation is touched once, at a cost linear in the dimension. Classical analyses of stochastic approximation give the rate O(1/n)O(1/\sqrt n)O(1/n​) for non-strongly-convex objectives, and O(1/(μn))O(1/(\mu n))O(1/(μn)) when the…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Simultaneously Learning and Optimizing Using Controlled Variance Pricing 1: Controlled Variance Pricing Has Regret O(T^α + T^(1−α) log T)Research Paper

A firm that sets prices without knowing how demand responds to them has to learn the demand curve from its own sales. Each price it charges is both a revenue decision and an experiment. The natural policy, certainty equivalent pricing, re-estimates the demand parameters after every period and charges the price that would be optimal if the estimates were…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchReinforcement LearningStochastic Systems·Captain: mikedeng1

Learning in Structured MDPs with Convex Cost Functions: Improved Regret Bounds for Inventory Management: Base-Stock Values from Any Two Starting States Differ by at Most 36 max(h,p)LxResearch Paper

The lost-sales inventory problem with lead times is a basic model of operations management. A retailer reviews one product's stock each period and places an order that arrives LLL periods later. Demand that cannot be met from stock on hand is lost, and the retailer pays a holding cost hhh per unit left on the shelf and a penalty ppp per unit of lost demand. The…

9 thms2 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: mikedeng1

Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems 1: Finite-Sample Confidence Region for the Mean and CovarianceResearch Paper

An optimization model often needs a probability distribution for an uncertain cost or demand, while a practitioner has only a finite sample from that distribution. Replacing the distribution by the empirical one can hide uncertainty in its estimated mean and covariance. Delage and Ye use a finite-sample confidence region for these two moments to justify a…

7 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic Programming·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 6: A Canonical Policy Is Strong Average Optimal and Its Average Cost Is the Optimal OneResearch Paper

A controlled Markov process (CMP), or Markov decision process, models a system that moves randomly between states while a controller chooses actions that influence both the cost incurred and the next state. When the planning horizon is long and no discounting is natural (queueing control, inventory, communication networks, maintenance), the criterion of…

12 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningStatistics·Captain: mikedeng1

Kullback–Leibler Upper Confidence Bounds for Optimal Sequential Allocation I: kl-UCB Draws a Suboptimal Arm log(T)/d(μ_a, μ*) + O(√log T) Times in One-Parameter Exponential FamiliesResearch Paper

In a stochastic multi-armed bandit a player repeatedly chooses one of KKK distributions ("arms") and observes a reward drawn from it; the goal is to collect as much reward as possible, which amounts to pulling suboptimal arms as rarely as possible. Lai and Robbins (1985) showed that any reasonable strategy must pull a suboptimal arm aaa at least …

12 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Solving Linear Programs in the Current Matrix Multiplication Time: The Stochastic Central Path Falls Back to a Classical Step with Probability at Most 10/n² per IterationResearch Paper

Linear programming, min⁡{c⊤x:Ax=b, x≥0}\min\{c^\top x : Ax=b,\ x\ge0\}min{c⊤x:Ax=b, x≥0} with A∈Rd×nA\in\mathbb R^{d\times n}A∈Rd×n, is the basic model of operations research, and the complexity of solving it is a central question of algorithm theory. Interior-point methods follow the central path: primal–dual pairs (x,s)(x,s)(x,s) with x,s>0x,s>0x,s>0 and xisi=tx_is_i=txi​si​=t for every iii, as the path parameter ttt decreases to 000. A…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainOperations Research+1·Captain: mikedeng1

Reversibility and Stochastic Networks VI: The Ewens Sampling Distribution Is Consistent Under Sampling Without ReplacementTextbook

The neutral theory of molecular evolution holds that much of the genetic variation observed at the molecular level is caused by selectively neutral mutations rather than by selection. To test it against data one needs the distribution of allele frequencies that a neutral model predicts, and in practice that distribution has to be compared with a sample from…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Quantifying the Bullwhip Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and Information 2: Without Shared Demand Information the Bullwhip Bound Is MultiplicativeResearch Paper

The bullwhip effect is the observation that the variability of orders grows as one moves up a supply chain, from the retailer to the wholesaler, the distributor and the factory, even when customer demand is stable. It was documented in industry practice by Lee, Padmanabhan and Whang (Management Science, 1997), who identified demand forecasting as one of its…

5 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

On the Stochastic Matrices Associated with Certain Queuing Processes 1: The M/G/1 Imbedded Chain Is Ergodic iff ρ < 1 and Recurrent iff ρ ≤ 1Research Paper

Many queues observed at well-chosen instants are Markov chains on the nonnegative integers. For the single-server queue with Poisson arrivals and general service times (M/G/1), D. G. Kendall showed in 1951 that the number of customers left behind at successive departure epochs is such a chain, the imbedded Markov chain (Kendall 1951; Kendall 1953). Whether…

9 thms2 active usersReviewed
🏆Completed
Markov ChainReinforcement Learning·Captain: mikedeng1

Linear Least-Squares Algorithms for Temporal Difference Learning II: Probability-One Convergence of LS TD on Ergodic Markov ChainsResearch Paper

Temporal-difference (TD) learning estimates the value function of a Markov chain — the expected discounted sum of future rewards from each state — from a single stream of observed transitions, without knowing the transition probabilities. With a linear function approximator the value of state xxx is represented as ϕx′θ\phi_x'\thetaϕx′​θ for a feature vector ϕx\phi_xϕx​ and…

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

Discounted Dynamic Programming: An Optimal Stationary Plan Exists When the Action Set Is Essentially FiniteResearch Paper

Sequential decisions often change the distribution of future states. A planner choosing an action today must account for both its immediate reward and the later rewards made possible by the resulting state. The mathematical question is whether an optimal rule can be chosen once and reused at every stage, even when a competing plan may randomize and use the…

11 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performance I: Quadratic Potential Functions Bound Mean Response Times in Open NetworksResearch Paper

Scheduling in a multiclass queueing network asks which waiting job a server should work on next when jobs of several types share stations and revisit them along fixed routes. Such networks model semiconductor wafer fabs, job shops and communication switches. Optimal policies are rarely computable: the state space is countably infinite, and even deciding…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 5: The Maximum Likelihood Estimator Exists with Probability Tending to One and Is Consistent and Asymptotically NormalResearch Paper

The conditional logit model is the workhorse of discrete choice analysis in econometrics, transportation planning, marketing and revenue management. An individual facing a finite set of alternatives picks alternative iii with probability proportional to eziθe^{z_i\theta}ezi​θ, where ziz_izi​ is a vector of observed attributes and θ\thetaθ an unknown parameter vector. Daniel…

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

Certified Adversarial Robustness via Randomized Smoothing 2: The Certified ℓ2 Radius Cannot Be EnlargedResearch Paper

Neural-network classifiers can be made to change their output by perturbations of the input that are imperceptible to a person. A certified defense is a classifier together with a proof that its prediction at a point xxx does not change for any perturbation δ\deltaδ in a stated set, typically an ℓ2\ell_2ℓ2​ ball ∥δ∥2<R\|\delta\|_2<R∥δ∥2​<R. Randomized smoothing turns an…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Secretary Problems: Weights and Discounts 1: An (8+3e)-Competitive Algorithm for the Weighted Secretary ProblemResearch Paper

The classical secretary problem asks how to select one valuable candidate when candidates arrive in random order and a decision must be made when each candidate appears. Many allocation settings have several goods of unequal quality instead of a single position. An employer may have roles of different desirability, or a seller may have placements with…

7 thms2 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 3: Reversed Weighted Sums of Bounded Martingale Differences Obey a Strong LawResearch Paper

A martingale difference sequence is the standard model of a "fair" sequence of observations whose terms may depend on the past: each new term has conditional mean zero given everything observed before it. Laws of large numbers for such sequences underlie the analysis of stochastic approximation, sequential estimation and online learning, where the noise…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 1: Independence of Irrelevant Alternatives with a Universal Benchmark Yields Logit Selection ProbabilitiesResearch Paper

The conditional logit model is the workhorse of discrete choice analysis: it is used to forecast travel mode shares, to estimate demand for differentiated products, and, in operations research, as the multinomial logit (MNL) choice model behind assortment optimization and revenue management. Its selection probabilities have the form …

7 thms2 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 1: Weighted Sums of Bounded Multiplicative Systems Grow at Most Like √(2Bₙ² log n)Research Paper

Weighted sums of dependent random variables occur when the weights change with the observation horizon. Even if each random variable is bounded and centered, allowing the weights in row nnn to be chosen anew makes an almost-sure statement about all large nnn different from a bound on a single finite sum. Kazuo Azuma's 1967 paper treats this situation under a…

7 thms2 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning II: High-Probability Regret Bound for UCBVI with a Bernstein–Freedman BonusResearch Paper

An agent can learn to act in an unknown environment by repeatedly running a finite episode, observing the states reached after its actions, and updating its model of the environment. The agent must trade off rewards in the current episode against information that may improve later decisions. A regret bound measures the cumulative value lost relative to an…

13 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time 2: The Two-Phase Shadow-Vertex Simplex Method Has Polynomial Smoothed ComplexityResearch Paper

The simplex method solves linear programs by moving between vertices of a feasible polyhedron. Its worst-case number of moves can grow exponentially, yet it often performs well on ordinary inputs. Worst-case examples alone therefore give an incomplete account of the method’s behavior. Spielman and Teng introduced smoothed analysis to measure expected…

22 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Asymptotic Behavior of Statistical Estimators and of Optimal Solutions of Stochastic Optimization Problems: Optimal Solutions Under Estimated Distributions Are Strongly ConsistentResearch Paper

Many estimation procedures in statistics, and most stochastic optimization models in operations research, have the same shape: a decision or parameter x∈Rnx\in\mathbb R^nx∈Rn is chosen to minimize an expected loss Ef(x)=∫f(x,ξ) P(dξ)Ef(x)=\int f(x,\xi)\,P(d\xi)Ef(x)=∫f(x,ξ)P(dξ) under a distribution PPP that is not known. In practice PPP is replaced by an estimate PνP^\nuPν built from the information…

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

Multi-parameter Mechanism Design and Sequential Posted Pricing 4: A 6.75-Approximate Truthful Posted-Price Menu for Unit-Demand Buyers of Multiple ItemsResearch Paper

A hotel sells rooms of several types, in limited numbers, to guests who each want one room. The revenue-optimal way to sell is known only in special cases: for buyers with several private values, optimal mechanisms can be randomized, involve lotteries, and lack a closed form (Manelli–Vincent 2007; Chawla, Hartline, Kleinberg 2007). In practice sellers post…

15 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Variance-based Regularization with Convex Objectives I: The χ²-Robust Risk Equals Empirical Risk plus a Standard-Deviation PenaltyResearch Paper

Many statistical procedures minimize an average observed loss. This treats two candidates with the same average as equally attractive even when one has much more variable losses across the sample. Adding a multiple of the empirical standard deviation can distinguish them, but the resulting objective need not be convex even when each individual loss is…

8 thms2 active usersReviewed
PreviousPage 55 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