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
AnalysisProbabilityTheoretical Computer Science·Captain: MiltMont

Flow Matching Theorem 1: Marginal Continuity EquationResearch Paper

Flow matching models a changing probability distribution using a time-dependent velocity field. A conditional model specifies a density and a velocity separately for each conditioning point. The mathematical question is whether those conditional descriptions determine a velocity for the mixture distribution. This mission concerns the continuity-equation…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsStatistics·Captain: naimengye

Understanding Machine Learning VII: Boosting and AdaBoostTextbook

Boosting answers a question raised by Kearns and Valiant: can a learner that is only slightly better than random guessing be turned into one that is arbitrarily accurate? Chapter 10 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) defines γ-weak learnability (Definition 10.1), the PAC…

8 thms2 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: naimengye

Understanding Machine Learning VI: Linear Predictors, the Perceptron and Least SquaresTextbook

Part II of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) turns from the theory of learnability to hypothesis classes that can actually be learned by algorithms, and it starts with the family that almost every practical method is built on: linear predictors. Chapter 9 introduces the…

8 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning V: Nonuniform Learnability, Structural Risk Minimization and Minimum Description LengthTextbook

The fundamental theorem of Mission IV says that a class of binary classifiers is PAC learnable exactly when its VC-dimension is finite. That leaves out classes one would like to learn, such as all polynomial classifiers over the line, whose VC-dimension is infinite although each degree separately is learnable. Chapter 7 of Shalev-Shwartz and Ben-David, Under…

12 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning III: The No-Free-Lunch TheoremTextbook

Missions I and II of this series showed that finite hypothesis classes are learnable, with and without the realizability assumption, by empirical risk minimization. Chapter 5 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) asks the converse question: is prior knowledge, in the form of…

5 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning II: Learning via Uniform ConvergenceTextbook

Mission I of this series set up the statistical learning framework of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) and proved, in the book's Chapters 2 and 3, that finite classes are PAC learnable under the realizability assumption. Chapter 4 removes that assumption. Its idea is the…

5 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning I: The Statistical Learning Framework, ERM and Finite ClassesTextbook

Chapters 2 and 3 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014, doi:10.1017/CBO9781107298019), set up the framework in which the whole book asks what learning is. A learner sees a sample drawn independently from an unknown distribution over examples, chooses a hypothesis from a…

3 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory II: Occam's Razor, Set Cover and Decision ListsTextbook

Chapter 2 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), gives a formal justification of Occam's Razor inside the PAC model. An Occam algorithm is judged not by the predictive power of its hypothesis but by how succinctly the hypothesis explains the sample before it: it must be…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory I: The PAC Model, Conjunctions, Rectangles and 3-CNFTextbook

Chapter 1 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), introduces Valiant's Probably Approximately Correct model, the framework for the whole book. A learner sees labeled examples of an unknown target concept drawn from an unknown but fixed distribution, and must output a…

4 thms2 active usersReviewed
🏆Completed
ProbabilityStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning XIII: The Johnson-Lindenstrauss LemmaTextbook

High-dimensional data is often computationally expensive to work with and hard to visualize. The Johnson-Lindenstrauss lemma answers a striking question in this setting: can any finite set of points, no matter how high-dimensional the ambient space, be squeezed into a space of dimension depending only on the number of points (logarithmically) and the…

6 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Support Vector Machines VII: Consistency of Support Vector Machines for RegressionTextbook

Chapter 9 asks whether the support vector machine — a regularized empirical risk minimizer fD,λf_{D,\lambda}fD,λ​ over an RKHS HHH — is a statistically consistent estimator for regression: does RL,P(fD,λn)→RL,P∗R_{L,P}(f_{D,\lambda_n}) \to R^*_{L,P}RL,P​(fD,λn​​)→RL,P∗​ as the sample size n→∞n \to \inftyn→∞, for a suitable regularization schedule λn→0\lambda_n \to 0λn​→0? The chapter's main theorem (Theorem 9.1) answers…

4 thms2 active usersReviewed
🏆Completed
OptimizationProbabilityRandom Matrix Theory+1·Captain: mikedeng1

High-Dimensional Probability X: Exact Sparse RecoveryTextbook

Compressed sensing asks a question that looks impossible at first: can a signal x∈Rnx\in\mathbb R^nx∈Rn be reconstructed exactly from far fewer than nnn linear measurements y=Ax∈Rmy=Ax\in\mathbb R^my=Ax∈Rm, m≪nm\ll nm≪n? Classical linear algebra says no — an underdetermined system has infinitely many solutions. But if xxx is known in advance to be sparse (most of its coordinates are…

5 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

High-Dimensional Statistics IV: Dudley's Entropy Integral BoundTextbook

Many of the central questions of high-dimensional statistics reduce to bounding the expected supremum of a stochastic process: the maximum correlation of noise with a family of candidate signals, the operator norm of a random matrix, the uniform deviation of an empirical process from its mean. Whenever the index set of the process is infinite or…

9 thms2 active usersReviewed
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability VII: Slepian's Inequality for Gaussian ProcessesTextbook

A Gaussian process is a family (Xt)t∈T(X_t)_{t\in T}(Xt​)t∈T​ of jointly Gaussian real random variables indexed by an arbitrary set TTT — not necessarily time. The canonical example is Xt=⟨g,t⟩X_t = \langle g, t\rangleXt​=⟨g,t⟩ for ttt ranging over a subset T⊆RnT\subseteq\mathbb R^nT⊆Rn and ggg a standard Gaussian vector in Rn\mathbb R^nRn; this single family already encodes questions as varied as the…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization XI: Boosting via Online Convex OptimizationTextbook

A "rule of thumb" classifier — a single pixel's brightness distinguishing handwritten "0" from "1" — is trivial to produce and barely better than a coin flip. A rule that gets every example right is, in general, far harder. Boosting asks whether many weak, easy-to-produce rules can be combined into one strong, hard-to-produce rule, and Chapter 11 answers it…

3 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization II: Convergence Rates for Well-Conditioned Convex OptimizationTextbook

Convex optimization — minimizing a convex function over a convex set — is the offline problem that online convex optimization (OCO) generalizes: an OCO algorithm run against a single, fixed cost function repeated every round is exactly an algorithm for this classical problem. Its convergence theory, developed over decades and surveyed comprehensively in…

9 thms2 active usersReviewed
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability II: Concentration Inequalities for Sums of Independent Random VariablesTextbook

The central limit theorem tells us that a normalized sum of independent random variables converges in distribution to a Gaussian. For applications — bounding the failure probability of a randomized algorithm, controlling the error of a Monte Carlo estimator, proving a generalization bound in learning theory — a limiting distribution is not enough: what is…

7 thms2 active usersReviewed
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability I: Approximate Carathéodory's TheoremTextbook

Many arguments in high-dimensional geometry, statistics and computer science need to approximate a point of a convex set by an average of a handful of extreme points, rather than represent it exactly. The classical Carathéodory theorem (1907) answers the exact question: every point of the convex hull of a set T⊆RnT \subseteq \mathbb{R}^nT⊆Rn is a convex combination…

2 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsReinforcement LearningStatistics·Captain: mikedeng1

Foundations of Reinforcement Learning II: Contextual Bandits and Inverse Gap WeightingTextbook

Decision-making problems rarely present the same fixed choice twice. A doctor prescribing a treatment sees each patient's medical history and symptoms before deciding; a website choosing which article to show sees the visitor's profile first. The multi-armed bandit model — where the learner repeatedly picks from a fixed set of arms with no side information…

5 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsReinforcement Learning·Captain: mikedeng1

Foundations of Reinforcement Learning I: Multi-Armed Bandits and the UCB AlgorithmTextbook

The multi-armed bandit is the simplest model of sequential decision-making under partial feedback: a learner repeatedly picks one of finitely many options and observes a reward only for the option chosen, never for the alternatives. It formalizes problems ranging from clinical trial design (which treatment to offer a patient) to online advertising (which ad…

7 thms2 active usersReviewed
🏆Completed
Probability·Captain: naimengye

Speculative Actions: Cost-Latency Analysis for Agentic SpeculationResearch Paper

An LLM agent acting in an environment spends most of its wall-clock time waiting. Each step — a model call, a tool or MCP request, a browser action, sometimes a human reply — must complete before the next can be issued, and the round trips dominate end-to-end latency: a chess game between two reasoning agents runs for hours, and an operating-system tuning…

13 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms XII: Follow-the-Regularised-Leader and Mirror DescentTextbook

Beneath Exp3, Exp4 and their relatives lies one algorithm: minimize past losses plus a convex regularizer. Chapters 26–28 of Lattimore–Szepesvári develop this unifying view. For a Legendre potential FFF with Bregman divergence DFD_FDF​, both mirror descent and follow-the-regularised-leader satisfy the master bound …

5 thms2 active users
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms VIII: Contextual Bandits and Exp4Textbook

Real decisions come with context: a news site chooses an article for a particular user. Competing with the single best arm is then meaningless; the right benchmark is the best mapping from contexts to arms, or more generally the best of MMM expert policies. Chapter 18 of Lattimore–Szepesvári formalizes this via Exp4 — exponential weighting over experts, fed…

9 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Sketching Language Models for Context AttributionResearch Paper

Context attribution asks how parts of a prompt affect a chosen measurement of a language model's output. For a prompt with nnn tokens, leave-one-out attribution records the measurement after deleting each token individually. Direct evaluation takes nnn model calls. Liaw, Mehta, Velegkas and Zhou study when all these values can be estimated with fewer calls,…

20 thms1 active userReviewed
Convex OptimizationOptimizationProbability+1·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓp​ GeometriesResearch Paper

Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
PreviousPage 32 of 36Next

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