Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Machine Learning

886 missions · 536 completed

The science of systems that learn from data and experience. Its scope runs from the statistical and mathematical foundations of learning, including generalization, expressivity, and computational limits, through the design of learning algorithms, deep learning, reinforcement learning, and probabilistic methods, to the empirical study of large models and the trustworthiness, interpretability, and societal impact of learned systems.

Missions

Open350Completed536All886
🏆Completed
Statistics·Captain: Shuze Chen

Exact Matrix CompletionResearch Paper

Every time a streaming service guesses what you would rate a film you have never seen, it is solving a matrix completion problem: fill in the missing entries of a vast user-by-item table from the few that are observed. The question became famous during the Netflix Prize (2006-2009), and it looks hopeless - infinitely many matrices fit the observed entries -…

602 thms13 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms III: Asymptotic and Minimax Optimality of UCBTextbook

The basic UCB regret bound of Mission II is logarithmic but not tight: its leading constant 16/Δi16/\Delta_i16/Δi​ is eight times the information-theoretic limit, and its worst-case rate carries a spurious log⁡n\sqrt{\log n}logn​. Chapters 8–9 of Lattimore–Szepesvári close both gaps. A refined confidence schedule f(t)=1+tlog⁡2tf(t) = 1 + t\log^2 tf(t)=1+tlog2t yields the asymptotically optimal …

25 thms10 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Privacy for Free in Efficient Agnostic Halfspace LearningResearch Paper

A classifier trained on individual records can reveal information about those records through its output. Differential privacy bounds how much the output distribution changes when one labeled example is replaced. For halfspace learning, the statistical question is whether this protection requires substantially more examples than learning without privacy.…

33 thms9 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms II: Stochastic Bandits and the UCB AlgorithmTextbook

A learner repeatedly chooses one of kkk slot machines, observes only the reward of the chosen arm, and wants to earn almost as much as the best arm in hindsight. This is the stochastic multi-armed bandit, the canonical model of the exploration–exploitation dilemma. This mission formalizes the model (environments, policies, regret, and the regret decomposition …

27 thms9 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit Algorithms·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price MechanismResearch Paper

A broker stands between a seller and a buyer who hold private valuations. It posts a price to each side, and trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their valuations: they are simple, strategy-proof, and individually rational. When the same kind of trade repeats, the broker must…

28 thms8 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand 1: AIM's Average Expected Cost Is Within O(1/√T) of the Newsvendor Cost, Perishable and Non-PerishableResearch Paper

A retailer who restocks a product every period must choose an order-up-to level without knowing the demand distribution, and in most retail settings it observes only sales, the minimum of demand and stock. Demand above the stock is lost and never recorded. This is censored demand: the data needed to estimate the distribution are truncated exactly at the…

17 thms8 active usersReviewed
🏆Completed
Bandit AlgorithmsInformation TheoryOperations Research·Captain: mikedeng1

Phase Transitions in Bandits with Switching Constraints: every policy with at most S switches has regret at least the phase-dependent rate up to a logarithmic factorResearch Paper

In many sequential decision problems, changing the action is costly or administratively limited: a retailer can revise a posted price only a few times per season, a clinical trial can change its treatment allocation only a few times, and a firm can reconfigure its production line only so often. The multi-armed bandit with switching constraints (BwSC)…

31 thms7 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization 1: Diagonal AdaGrad's Regret Is Bounded by the Per-Coordinate Gradient Norms Σᵢ‖g_{1:T,i}‖₂Research Paper

Stochastic and online subgradient methods are the workhorse of large-scale learning: each step touches one example, costs time linear in the dimension, and needs no line search. Their weak point is the step size. A single global step size treats every coordinate alike, while in high-dimensional, sparse problems (text, click-through data, bag-of-words…

22 thms7 active users
🏆Completed
ProbabilityStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning VII: On-Line Learning and On-Line-to-Batch ConversionTextbook

Every guarantee in the preceding chapters assumes a fixed distribution and i.i.d. sampling. On-line learning drops both assumptions: an algorithm processes one example at a time, in an adversarial (worst-case) sequence, and is judged by regret against the best fixed comparator in hindsight rather than by generalization error. This chapter develops the…

28 thms7 active users
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability IX: The Matrix Deviation InequalityTextbook

Random matrices with independent rows are the workhorse of high-dimensional statistics and compressed sensing: sample covariance matrices, sub-sampled measurement operators, and randomized sketches are all of this form. A basic question about such a matrix AAA is how close ∥Ax∥2\|Ax\|_2∥Ax∥2​ stays to its typical size E∥Ax∥2≈m∥x∥2\mathbb E\|Ax\|_2\approx\sqrt m\|x\|_2E∥Ax∥2​≈m​∥x∥2​ — not just…

13 thms7 active users
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms XIV: Bayesian Bandits, the Gittins Index and Thompson SamplingTextbook

The oldest bandit algorithm (Thompson, 1933) is also the most modern: sample a parameter from the posterior and act greedily. Chapters 34–36 of Lattimore–Szepesvári develop the Bayesian view in two crowning results. The Gittins index theorem: for infinite-horizon discounted Markov bandits, the seemingly intractable dynamic program is solved exactly by an…

89 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms XI: Lower Bounds for Stochastic Linear BanditsTextbook

Is the dnd\sqrt{n}dn​ regret of LinUCB (Mission X) an artifact of the algorithm or a law of nature? Chapters 24–25 of Lattimore–Szepesvári prove it is essentially unimprovable. On the unit ball there is a parameter θ\thetaθ with ∥θ∥22=d2/(48n)\|\theta\|_2^2 = d^2/(48n)∥θ∥22​=d2/(48n) forcing Rn≥dn163R_n \ge \frac{d\sqrt{n}}{16\sqrt{3}}Rn​≥163​dn​​ — the goal theorem — and the hypercube gives the same …

14 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms V: Adversarial Bandits and Exp3Textbook

What if the rewards are not random at all, but chosen by an adversary who knows your algorithm? Remarkably, a randomized learner can still compete with the best fixed arm in hindsight. Chapters 11–12 of Lattimore–Szepesvári develop the adversarial kkk-armed bandit: rewards xti∈[0,1]x_{ti} \in [0,1]xti​∈[0,1] are an arbitrary fixed matrix, the learner samples At∼PtA_t \sim P_tAt​∼Pt​, and…

12 thms7 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Dynamic Pricing with Unknown Non-Parametric Demand and Limited Price Changes: The SLPE Policy Has Regret O(√T log T log log T) on Its Concentration Event and Makes O(log log T) Price ChangesResearch Paper

A retailer selling one product over TTT periods must choose a price each period without knowing how demand responds to price. Charging different prices reveals the demand curve but costs revenue, and in practice every price change has its own cost: relabelling, customer goodwill, contractual limits on repricing. Dynamic pricing with learning asks for policies…

10 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 2: Regret Lower Bound for Periodic Multi-Armed Bandits with Known PeriodsResearch Paper

Demand, prices and click-through rates often follow seasonal cycles: weekly, monthly, yearly. A decision maker who repeatedly chooses among options whose expected payoffs repeat in time faces a non-stationary multi-armed bandit. Chen, Wang and Wang (arXiv:2005.08088v4, Operations Research, 2025) study the model in which each arm's mean reward is periodic…

15 thms6 active usersReviewed
🏆Completed
Quantum Information·Captain: Goku

Quantum Algorithms and Learning Theory — Part II 6: Shadow tomography with poly(log m, log d, 1/ε, log(1/δ)) copiesTextbook

This mission develops Chapter 6 of Quantum Algorithms and Learning Theory — Part II by Srinivasan Arunachalam. The chapter's selected results describe the mathematical guarantees below.

13 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Distribution-Free Contextual Dynamic Pricing 1: The DIP Policy Has Expected Regret at Most C T^(2/3) log T Plus 4 p_max L Times the Episode-Weighted ℓ₁ Estimation ErrorsResearch Paper

In contextual dynamic pricing a seller posts a price for each arriving customer, observes only whether the customer buys, and must learn the demand from these binary responses while selling. The problem arises in e-commerce, insurance and consumer lending, where every customer comes with features (product attributes, customer characteristics) that shift the…

18 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games II: If Every Player Runs Optimistic FTRL with Step Size (n−1)^{−1/2}T^{−1/4}, Each Player's Regret Is at Most (R+4)√(n−1)·T^{1/4}Research Paper

When every participant in a repeated game runs a no-regret learning algorithm, the time-averaged play converges to a coarse correlated equilibrium, and in smooth games the average welfare approaches the price-of-anarchy guarantee. These facts are a standard justification for equilibrium predictions in auctions, routing and markets, where agents learn rather…

15 thms6 active users
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning I: Projected Online Gradient Descent Has Regret D²/(2η_T) + Σ_t η_t‖g_t‖²/2Textbook

In online learning, a decision is made before the loss for that round is revealed. The learner cannot optimize a known objective once and use its minimizer forever: the sequence of objectives may be arbitrary. A basic performance measure is regret, the learner's total loss minus the loss of one fixed decision chosen with hindsight. A regret bound that grows…

9 thms6 active users
🏆Completed
Bandit AlgorithmsProbabilityReinforcement Learning·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 2: LSVI-UCB Has Regret O(√(d³H³Tι²) + ζdHT√ι) on ζ-Approximately Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces relies on function approximation: value functions are represented as functions of a ddd-dimensional feature map instead of tables indexed by states. Before 2019, regret guarantees for exploration with function approximation either needed strong assumptions (deterministic dynamics, a generative…

17 thms6 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition V: Under the Proximal-PL Inequality, Proximal-Gradient Converges at Rate (1 − μ/L)^kResearch Paper

Many problems in machine learning and signal processing minimize a smooth loss plus a simple non-smooth regularizer: ℓ1\ell_1ℓ1​-regularized least squares, group-sparse regression, and constrained problems written with an indicator function. The standard algorithm for this composite form is the proximal-gradient method, a gradient step on the smooth part…

11 thms6 active users
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems V: Symmetric Monotonic Strategies Draw the Suboptimal Arms Collectively a Linear Number of TimesResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of KKK arms and receives a random reward drawn from the chosen arm's unknown distribution. The classical lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996) describe the regret of good strategies when the horizon TTT tends to infinity: it grows like ln⁡T\ln TlnT, with a constant…

15 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems VI: Uniformly Super-Fast Convergent Strategies Draw Each Suboptimal Arm ln T / K_inf Times up to Explicit Lower-Order TermsResearch Paper

In a stochastic multi-armed bandit, a decision maker repeatedly chooses one of several unknown reward sources. Sampling an arm reveals its reward but uses a round that could have been spent on a better arm. A good strategy must therefore reduce sampling of inferior arms, yet it cannot stop sampling them too early: it must still distinguish the current…

14 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems IV: Under Pairwise Symmetry a Suboptimal Arm Is Drawn T/K Times or Almost as Often as an Optimal ArmResearch Paper

Lower bounds for stochastic multi-armed bandits are usually stated for a large horizon: Lai and Robbins (1985) and Burnetas and Katehakis (1996) show that a consistent strategy pulls a suboptimal arm at least about ln⁡T/Kinf⁡\ln T / \mathcal{K}_{\inf}lnT/Kinf​ times. These bounds say nothing about the small-horizon regime, the first rounds in which a strategy has not yet had…

11 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems II: Uniformly Fast Convergent Strategies Draw Every Suboptimal Arm at Least ln T / K_inf Times AsymptoticallyResearch Paper

In a stochastic multi-armed bandit, a player repeatedly chooses one of finitely many arms and sees only the reward from the chosen arm. To earn a high reward, the player must favor arms that appear best. Yet an arm that currently appears inferior might be best under another plausible reward law. That uncertainty forces any strategy with uniformly strong…

11 thms6 active usersReviewed
PreviousPage 1 of 22Next

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