Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Statistics

598 missions · 354 completed

The mathematical discipline of drawing inferences from data under uncertainty: estimation, hypothesis testing, prediction, and the quantification of confidence. Grounded in probability, it spans classical and Bayesian inference, experimental design, and modern high-dimensional and nonparametric theory, asking what data can reveal and with what guarantees.

Missions

Open244Completed354All598
🏆Completed
Information TheoryQuantum Information·Captain: mikedeng1

Shadow Tomography of Quantum States 2: Even the Classical Special Case Needs Ω(min{D, log M}/ε²) CopiesResearch Paper

Shadow tomography asks for predictions of many specified measurements of an unknown quantum state, while using as few prepared copies of that state as possible. The requested output is a list of acceptance probabilities, not a full description of the state. A procedure might exploit the fact that these are only MMM numbers, even when the state has dimension DDD.…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability·Captain: mikedeng1

Stability and Generalization 4: Relative-Entropy Regularization of Mixtures Has Uniform Stability M²/(λm)Research Paper

A learning algorithm generalizes when its error on fresh data is close to its error on the training sample. Bousquet and Elisseeff (JMLR 2, 2002) showed that a single property of the algorithm, uniform stability, controls this gap with exponential concentration: if removing any one example from a training set of size mmm changes the loss of the output at…

18 thms3 active users
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Stability and Generalization 2: Exponential Generalization Bounds for Uniformly Stable AlgorithmsResearch Paper

A learning algorithm is judged by its generalization error: the expected loss of the hypothesis it outputs on a fresh example. That quantity depends on an unknown distribution, so it is estimated from the training data, by the empirical error (the average loss on the training set) or the leave-one-out error (the average loss on each training point of the…

13 thms3 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningProbability·Captain: mikedeng1

The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 1: ℓ2 Error Bound for Sparse Parameters under the Uniform Uncertainty PrincipleResearch Paper

In many statistical applications the number of unknown parameters ppp is far larger than the number of observations nnn: gene-expression studies with tens of samples and thousands of genes, imaging problems with fewer measurements than pixels, and nonparametric curve estimation from finitely many noisy samples. Least squares is useless in this regime, since the…

9 thms3 active usersReviewed
🏆Completed
Machine LearningMarkov ChainReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction VI: Batch TD(0) Converges to the Certainty-Equivalence EstimateTextbook

Temporal-difference (TD) learning estimates the value of each state of a Markov reward process from observed experience, updating an estimate toward a target built from the next reward and the current estimate of the next state. Monte Carlo (MC) methods instead update toward the full observed return. Both are standard prediction methods in reinforcement…

9 thms3 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 2: An Iterated-Logarithm Upper Bound for Weighted Conditionally Sub-Gaussian Martingale DifferencesResearch Paper

The law of the iterated logarithm (LIL) gives the exact almost-sure size of the fluctuations of a sum of random variables. For independent fair ±1\pm1±1 increments x1,x2,…x_1,x_2,\dotsx1​,x2​,… with partial sums SnS_nSn​, Khinchin (1924) showed that lim sup⁡n∣Sn∣/2nlog⁡log⁡n=1\limsup_n |S_n|/\sqrt{2n\log\log n}=1limsupn​∣Sn​∣/2nloglogn​=1 almost surely; Kolmogorov (1929) extended this to bounded independent increments, and Hartman…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Fundamentals of Queueing Theory VIII: Lindley's Integral Equation for the G/G/1 QueueTextbook

The single-server queue with general interarrival times and general service times, written G/G/1 in Kendall's notation, is the model left when every distributional assumption is removed from the classical single-server queue. Customers arrive one at a time, wait in line in first-come, first-served order, and are served one at a time. Almost nothing about it…

12 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies IV: Sufficient Conditions for Logarithmic Regret with a Known Incumbent PriceResearch Paper

A seller who does not know how demand responds to price must learn the demand curve from its own sales while also earning revenue. This is the learn-and-earn problem of dynamic pricing. Every price it charges both earns and informs, and a policy that only earns can stop learning. Keskin and Zeevi (Operations Research 62(5), 2014) study the problem for a…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Elements of Queueing Theory V: Strassen's Theorems and the Stochastic Ordering of QueuesTextbook

Chapters 1–3 of Baccelli and Brémaud's Elements of Queueing Theory compute exact quantities: Palm identities, stability criteria, PASTA, Pollaczek–Khinchin. Chapter 4 asks a different question. When you cannot compute a queue, can you at least say it is better than another one?

15 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Learnability, Stability and Uniform Convergence I: A Problem Is Learnable if and only if It Admits a Uniform-RO Stable Universal AERMResearch Paper

In supervised binary classification, a hypothesis class is learnable if and only if it has uniform convergence, meaning that empirical risks converge to true risks uniformly over the class. When that holds, empirical risk minimisation (ERM) learns. This equivalence, due to Vapnik and Chervonenkis and extended to real-valued losses by Alon, Ben-David,…

12 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Adversarially Robust Generalization Requires More Data 4: Robust Learning from One Thresholded Sample in the Bernoulli ModelResearch Paper

Classifiers trained to high standard accuracy can be fooled by small, deliberately chosen perturbations of their inputs, so-called adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015). Training methods that aim at robustness against perturbations bounded in the ℓ∞\ell_\inftyℓ∞​ norm reach high robust accuracy on the training set while robust test…

8 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Adversarially Robust Generalization Requires More Data 2: A Robust-Error Lower Bound for Linear Classifiers in the Bernoulli ModelResearch Paper

Classifiers trained by standard methods reach high accuracy on image benchmarks and yet change their prediction under perturbations of each pixel that are invisible to a human. Training against such perturbations (adversarial training) improves robustness, but on CIFAR10 and SVHN the robust test accuracy stays far below the robust training accuracy: robust…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Are Call Center and Hospital Arrivals Well Modeled by Nonhomogeneous Poisson Processes?: Combining k Equal Subintervals of a Linear Arrival Rate Bounds the Degree of Nonhomogeneity by C/kResearch Paper

Arrival processes to call centers and hospital emergency departments are routinely modeled as nonhomogeneous Poisson processes (NHPPs): Poisson processes whose arrival rate varies over the day. Staffing and queueing models built on this assumption are only as good as the assumption itself, so practitioners test it on data. The standard test, going back to…

8 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector III: A Sparsity Oracle Inequality for the LassoResearch Paper

In high-dimensional regression the number of candidate predictors MMM can far exceed the number of observations nnn. A regression function can then be estimated only if it is well approximated by a combination of a few elements of a large dictionary. The Lasso is the most widely used estimator in this regime. The question this mission formalizes is how well the…

9 thms3 active usersReviewed
🏆Completed
Linear algebraMachine LearningOptimization·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector I: Sparse Eigenvalue and Correlation Conditions Imply the Restricted Eigenvalue ConditionResearch Paper

In high-dimensional linear regression one observes y=Xβ∗+w∈Rny = X\beta^* + w \in \mathbb R^ny=Xβ∗+w∈Rn with a design matrix X∈Rn×MX\in\mathbb R^{n\times M}X∈Rn×M whose number of columns MMM may far exceed the sample size nnn. The two standard estimators of a sparse β∗\beta^*β∗, the Lasso (Tibshirani, 1996) and the Dantzig selector (Candès and Tao, 2007), both come with error bounds of order …

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Markovian Decision Processes with Uncertain Transition Probabilities II: Max-Max and Max-Min Optimal Returns Bound the Bayesian Optimal ReturnResearch Paper

A Markovian decision process (Howard, 1960) models a controller who, in each of finitely many states, picks a decision, earns a reward and moves to a random next state according to known transition probabilities. In applications (inventory control, equipment replacement, quality control) those probabilities are estimated, not known. Satia and Lave (Operation…

7 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

The Optimal Sample Complexity of PAC Learning: The Optimal Realizable Sample Complexity BoundResearch Paper

The sample complexity of a learning problem is the number of labelled examples needed to learn to a prescribed accuracy with a prescribed confidence. In Valiant's probably approximately correct (PAC) model it is the basic quantity of statistical learning theory: it says how much data is necessary and sufficient, as a function of the complexity of the…

12 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: naimengye

Understanding Machine Learning XIX: Generative ModelsTextbook

The book is discriminative almost throughout: it learns predictors, not distributions, following Vapnik's advice not to solve a more general problem as an intermediate step. Chapter 24 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), presents the generative alternative: assume a…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

An Introduction to Computational Learning Theory V: Classification Noise and Statistical QueriesTextbook

Chapter 5 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks what happens to PAC learning when the labels are unreliable. In the classification noise model of Angluin and Laird, each label returned by the oracle is flipped independently with a fixed probability η<1/2\eta < 1/2η<1/2. The…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: naimengye

An Introduction to Computational Learning Theory IV: Weak and Strong Learning, Boosting and Chernoff BoundsTextbook

Chapter 4 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks whether the PAC model's demand for arbitrarily small error and confidence is essential. A weak learning algorithm need only, with some fixed positive probability, output a hypothesis that beats random guessing by a…

7 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchOptimization+1·Captain: naimengye

Multi-armed Bandit Allocation Indices VI: Bandit Sampling Processes, Favourable Priors and Invariance of the IndexTextbook

The bandit processes that motivated the index theorem are sampling processes: an arm is a population from which one draws i.i.d. observations whose distribution has an unknown parameter, and each draw both earns something and teaches something. Chapter 7 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/97804709800…

9 thms3 active usersReviewed
🏆Completed
AnalysisMathematical Physics·Captain: LG

CODATA 2022: exactly known constants of the revised SI and the least-squares adjustmentResearch Paper

Since the 2019 revision of the SI, seven constants of nature have fixed, exact numerical values: the caesium hyperfine frequency ΔνCs\Delta\nu_{\mathrm{Cs}}ΔνCs​, the speed of light ccc, the Planck constant hhh, the elementary charge eee, the Boltzmann constant kkk, the Avogadro constant NAN_ANA​ and the luminous efficacy KcdK_{\mathrm{cd}}Kcd​. Every other constant is either measured,…

18 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

Reinforcement learning formalizes a scenario supervised learning cannot: an agent that actively interacts with an environment, choosing actions that change both the state it observes next and the reward it receives, rather than passively receiving an i.i.d. labeled sample. Every practical treatment of this scenario — from classical dynamic programming to…

13 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityRandom Matrix Theory·Captain: mikedeng1

High-Dimensional Probability XI: Dvoretzky-Milman's TheoremTextbook

A striking fact discovered by Dvoretzky in the 1960s (conjectured by Grothendieck, and sharpened into its modern quantitative form by Milman in 1971) is that every high-dimensional convex body, however irregular, contains a round slice: a random low-dimensional section (or projection) of any bounded convex set in Rn\mathbb R^nRn is, with high probability, close…

9 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

Support Vector Machines V: Bernstein's Inequality for Independent Hilbert-Space-Valued Random VariablesTextbook

Every statistical guarantee for a learning algorithm ultimately rests on a concentration inequality: a bound on how far an empirical average can stray from its expectation. For real-valued averages, Bernstein's inequality (1924, refined through the 20th century) is the classical tool — sharper than Hoeffding's inequality whenever the summands' variance is…

5 thms3 active usersReviewed
PreviousPage 9 of 15Next

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