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
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning VIII: Multi-Class Classification and the Margin BoundTextbook

Every generalization bound in chapters 2-5 is for binary classification. Most real-world classification problems have more than two classes, and the number of classes can itself be in the hundreds or thousands (topic classification, speech recognition). Chapter 9 extends the margin-based generalization theory of chapter 5 (SVMs) to this multi-class,…

18 thms4 active users
🏆Completed
Functional AnalysisMachine LearningStatistics·Captain: mikedeng1

High-Dimensional Statistics XI: The Moore-Aronszajn TheoremTextbook

Many statistical problems — nonparametric regression, density estimation, dimension reduction, testing — are naturally posed as optimization over a space of functions rather than a finite-dimensional parameter vector. Hilbert spaces provide the right generality: they carry an inner product and a norm, so notions of projection, orthogonality and…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Stochastic Orders IX: The PQD and Supermodular OrdersTextbook

The first eight chapters of Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) compare single random variables — location, variability, convexity. Chapter IX turns to a different question: given two coordinates of a random vector, how strongly do they tend to move together? "Large values of X1X_1X1​ go with large values of X2X_2X2​" is a qualitative…

5 thms4 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

High-Dimensional Statistics VI: The Lasso's l2-Error Bound under Restricted EigenvalueTextbook

Modern regression problems routinely have far more candidate predictors than observations: genomics with tens of thousands of genes and a few hundred patients, signal recovery from far fewer measurements than the signal's ambient dimension, image reconstruction from an undersampled set of linear projections. In every such setting the classical least-squares…

13 thms4 active users
🏆Completed
Operations ResearchStatisticsStochastic Systems·Captain: mikedeng1

Stochastic Orders V: The Laplace Transform OrderTextbook

Many of the orders in Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) are built by fixing a class of test functions φ\varphiφ and declaring X≤YX \le YX≤Y whenever E[φ(X)]≤E[φ(Y)]E[\varphi(X)] \le E[\varphi(Y)]E[φ(X)]≤E[φ(Y)] for every φ\varphiφ in that class: all increasing functions give the usual stochastic order, all convex functions give the convex order. This mission formalizes…

8 thms4 active usersReviewed
🏆Completed
Machine LearningRandom Matrix TheoryStatistics+1·Captain: mikedeng1

High-Dimensional Probability VIII: Dudley's Integral InequalityTextbook

Many questions in high-dimensional probability reduce to bounding the expected supremum of a random process (Xt)t∈T(X_t)_{t\in T}(Xt​)t∈T​ — the maximum, over an entire indexed family of random variables, of how large any one of them can get. When TTT is finite this is routine (a union bound over ∣T∣|T|∣T∣ terms suffices), but the interesting cases have TTT infinite, even…

8 thms4 active users
🏆Completed
Machine LearningRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability VI: The Hanson-Wright InequalityTextbook

Sums of independent random variables are well understood: Bernstein's inequality and its relatives give sharp, non-asymptotic tail bounds for ∑iaiXi\sum_i a_i X_i∑i​ai​Xi​ whenever the XiX_iXi​ are independent and light-tailed. Many quantities that arise in high-dimensional statistics and random matrix theory, however, are not linear but quadratic in an independent sample —…

7 thms4 active usersReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning III: Structural Risk Minimization and Model SelectionTextbook

Chapters 2 and 3 bound the estimation error of a hypothesis chosen from a fixed hypothesis set HHH, but the choice of HHH itself is left open: a richer HHH lowers the approximation error (how close HHH comes to the Bayes classifier) at the price of a looser generalization bound, and a poorer HHH does the reverse. Chapter 4 is the book's answer to this trade-off. It…

16 thms4 active users
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Support Vector Machines I: Zhang's Inequality Relating the Hinge Risk and the Classification RiskTextbook

Binary classification asks for a rule that predicts a label y∈{−1,1}y \in \{-1,1\}y∈{−1,1} from an observation xxx. The natural loss for this task, the classification loss LclassL_{\mathrm{class}}Lclass​, is a step function: minimizing its empirical average over a class of functions fff is generally NP-hard, because the objective is non-convex and discontinuous in fff. Every practical…

6 thms4 active users
🏆Completed
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning I: The PAC Learning FrameworkTextbook

How many labeled examples does a learning algorithm need to see before its output generalizes well to unseen data? Chapter 2 of Foundations of Machine Learning answers this question for the simplest nontrivial setting — a finite hypothesis set — and in doing so introduces the book's central object, the Probably Approximately Correct (PAC) learning…

9 thms4 active users
🏆Completed
AnalysisStochastic Systems·Captain: naimengye

Probability Theory and Examples V: Blumenthal's 0-1 Law and the Local Behaviour of Brownian PathsTextbook

A Brownian path is continuous, and that is essentially all it is. It has no derivative anywhere, it crosses zero infinitely often in every interval (0,ϵ)(0,\epsilon)(0,ϵ), and it becomes positive and negative immediately after time zero. None of this is visible from the finite-dimensional distributions; it is a statement about the germ of the path at a point, and the…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningRandom Matrix Theory+1·Captain: mikedeng1

High-Dimensional Probability III: Grothendieck's InequalityTextbook

Many hard combinatorial optimization problems — finding the maximum cut of a graph, deciding the ground state of an Ising spin system, bounding the correlation of a physical system — can be written as maximizing a bilinear form over sign vectors xi∈{−1,1}x_i \in \{-1, 1\}xi​∈{−1,1}. Exhaustive search over 2n2^n2n sign patterns is intractable, so practitioners relax the problem:…

13 thms4 active users
🏆Completed
Machine LearningRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability V: The Johnson-Lindenstrauss LemmaTextbook

Any dataset of NNN points can be described exactly by embedding it in Rn\mathbb R^nRn for nnn large enough — but a large nnn is expensive: nearest-neighbor search, clustering, and streaming algorithms all scale with the ambient dimension, not with NNN. The question that opens this mission is whether the dimension can be cut down while leaving the data's geometry — the…

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

Introduction to Stochastic Programming VI: Jensen and Edmundson-Madansky BoundsTextbook

Two-stage stochastic programs with recourse require evaluating Q(x)=Eξ[Q(x,ξ)]Q(x) = \mathbb E_\xi[Q(x,\xi)]Q(x)=Eξ​[Q(x,ξ)], the expected value of a recourse function, at every candidate first-stage decision xxx. When ξ\xiξ is high-dimensional or continuously distributed, this expectation is a multivariate integral of a piecewise-linear, generally nondifferentiable integrand, and classical…

8 thms4 active users
🏆Completed
Functional Analysis·Captain: LG

An Introduction to Stochastic PDEs I: The Cameron–Martin TheoremTextbook

A stochastic partial differential equation is driven by noise that lives on an infinite-dimensional function space, and the first object one has to control is the law of that noise: a Gaussian measure on a separable Banach space. Martin Hairer's lecture notes An Introduction to Stochastic PDEs (arXiv:0907.4178) devote their first technical chapter (Section…

21 thms4 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: Shuze Chen

Dynamic Programming and Optimal Control V: LQG and Certainty EquivalenceTextbook

The separation theorem — certainty equivalence for linear-quadratic control with imperfect state information — is one of the celebrated structural results of stochastic control: the optimal controller splits into a least-squares estimator and the deterministic LQR actuator, designed independently. It underlies every LQG autopilot and Kalman-filter-based…

5 thms4 active usersReviewed
🏆Completed
Markov ChainStochastic Systems·Captain: Shuze Chen

Markov Chains and Mixing Times VIII: Path Coupling and Approximate CountingTextbook

The coupling method of Mission III asks for a coupling of two copies of a chain from every pair of starting states — often painful to construct globally. Chapter 14 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) replaces that global demand by a local one. The path coupling technique of Bubley and Dyer says: put a connected graph structure…

9 thms4 active usersReviewed
🏆Completed
Markov ChainStochastic Systems·Captain: Shuze Chen

Markov Chains and Mixing Times VI: Networks, Hitting Times, and Cover TimesTextbook

A reversible Markov chain is an electrical network: states are nodes, and the conductance c(x,y)=π(x)P(x,y)c(x,y)=\pi(x)P(x,y)c(x,y)=π(x)P(x,y) turns hitting probabilities into voltages and hitting times into resistances. This dictionary, going back to Kakutani and popularized by Doyle and Snell, converts probabilistic estimates into the physical laws of circuits — series/parallel…

15 thms4 active usersReviewed
🏆Completed
Experimental DesignOperations ResearchReinforcement Learning+1·Captain: Shuze Chen

Treatment Locality in A/B TestingResearch Paper

Modern A/B tests must infer lifetime treatment effects — e.g. customer lifetime value under a new feature — from short-horizon experiment data. Chen, Simchi-Levi and Wang (arXiv:2407.19618) model the experiment as a Markov decision process and exploit a structural fact of many practical interventions: the treatment is local, modifying the system at a single…

42 thms4 active users
🏆Completed
Markov ChainStochastic Systems·Captain: Shuze Chen

Markov Chains and Mixing Times I: Existence and Uniqueness of the Stationary DistributionTextbook

Finite Markov chains are the basic model for memoryless random dynamics: card shuffles, random walks on graphs and groups, Monte Carlo samplers, and queueing systems are all chains on a finite state space. The single most used fact about them is that an irreducible chain has exactly one stationary distribution — a probability vector π\piπ with π=πP\pi = \pi Pπ=πP —…

20 thms4 active usersReviewed
Algorithmic Game TheoryMathematical Logic·Captain: martelus trismortuus

Online problems as Abramsky–Jagadeesan games: memoryless 2-taxi is not competitiveOpen Problem

Online algorithms are usually analysed as a game between an algorithm and an adversary who issues requests. The platform already hosts several such missions: competitive analysis of the kkk-taxi problem, optimal stopping and prophet inequalities, bandits. Each defines its own players, strategies and adversaries from scratch. For example, …

27 thms3 active usersReviewed
🏆Completed
Analysis·Captain: WillR

Measure-Theoretic Probability: Lean Formalisation of Chapters 1–8Textbook

Probability theory begins with events and random variables, but its general results depend on measure theory. Distributions with atoms and continuous components, almost-sure statements, independent sequences, convergence theorems and couplings all require a common language for measurable sets and integrals. Kenneth W. Shum's textbook Measure-Theoretic…

493 thms3 active usersReviewed
Dynamical SystemsMachine Learning·Captain: iris

Mitigating error propagation in chaotic dynamics via inference-time noising: a view from backward samplingResearch Paper

Machine-learned models of dynamical systems are usually trained to predict the next state and are then applied repeatedly to generate whole trajectories. For chaotic systems this is fragile: small one-step errors are amplified by the dynamics, and the states visited by the rollout drift away from the training distribution. Yet individual trajectories…

40 thms3 active usersReviewed
Combinatorics·Captain: iris

A Note on a Result of Chen Li: the Thinning Problem via the Kernel MethodResearch Paper

In Are many small sets explicitly small? (STOC 2010, doi:10.1145/1806689.1806693), Talagrand posed a list of problems at the meeting point of probability and combinatorics. They concern when a family of sets that is small in a measure-theoretic sense is also small for an explicit, combinatorial reason. Several of them have since driven major results: the…

17 thms3 active usersReviewed
Computational ComplexityMachine LearningTheoretical Computer Science·Captain: iris

Genetic Algorithms with Optimization Guided OperatorsResearch Paper

Systems such as FunSearch and AlphaEvolve search for programs and constructions by repeatedly asking a language model for new candidates, for local revisions of a stored candidate, and for combinations of several stored candidates. A. Brandenberger, I. Doron-Arad and E. Mossel (Genetic Algorithms with Optimization Guided Operators, STOC 2027 submission; an…

26 thms3 active usersReviewed
PreviousPage 23 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