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
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Analysis of Thompson Sampling for the Multi-armed Bandit Problem 2: Logarithmic Regret for N ArmsResearch Paper

Thompson Sampling is the oldest heuristic for the multi-armed bandit problem: proposed by Thompson in 1933, it plays each arm with the posterior probability that the arm is the best one. It is simple to implement, performs well empirically (Chapelle and Li, NIPS 2011), and has been used in production systems such as click-through-rate prediction for search…

11 thms4 active usersReviewed
🏆Completed
Linear algebraOptimizationReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction X: Off-policy Divergence and the Gradient of the Projected Bellman ErrorTextbook

Off-policy learning estimates the value function of a target policy π\piπ from data generated by a different behavior policy bbb. It is how an agent learns about a greedy policy while exploring, and how many policies can be evaluated from one stream of experience. Combined with linear function approximation and bootstrapping (updating an estimate toward other…

14 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 3: An Efficient Forecaster Whose (ℓ1, ε)-Calibration Rate Is at Most √(2/(εT))Research Paper

A forecaster announces, each day, a probability that it will rain; afterwards nature reveals whether it did. The forecaster is calibrated if, on the days on which it announced roughly 30%, it rained roughly 30% of the time, and likewise for every other announced value. Calibration is a minimal consistency requirement for probabilistic forecasts, used in…

11 thms4 active usersReviewed
🏆Completed
ProbabilityReinforcement LearningStatistics·Captain: mikedeng1

Reinforcement Learning: An Introduction V: Off-policy Prediction by Importance SamplingTextbook

Reinforcement learning methods must explore in order to find good behaviour, yet the quantity they usually want to evaluate is the value of a different, often deterministic, policy. Off-policy prediction separates the two roles: episodes are generated by a behaviour policy bbb, and the goal is the value function vπv_\pivπ​ of a target policy π\piπ. Almost every…

14 thms4 active usersReviewed
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Shadow Tomography of Quantum States 1: Polylogarithmically Many Copies Suffice to Estimate Every Acceptance Probability to Within εResearch Paper

Learning an unknown quantum state is expensive. Full quantum state tomography of a DDD-dimensional mixed state ρ\rhoρ to accuracy ε\varepsilonε in trace distance needs on the order of D2/ε2D^2/\varepsilon^2D2/ε2 copies of ρ\rhoρ (O'Donnell–Wright 2016; Haah et al. 2017), and this is optimal. For a system of nnn qubits, D=2nD = 2^nD=2n, so full tomography is out of reach beyond a few…

17 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Competitive Caching with Machine Learned Advice: The Competitive Ratio of Predictive MarkerResearch Paper

Caching (online paging) is one of the oldest problems in online algorithms: a fast memory of kkk slots serves a sequence of requests, and every request for an element not in the fast memory is a cache miss that forces the element to be loaded, possibly evicting another one. With the whole request sequence known in advance, evicting the element whose next…

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

Optimal Best Arm Identification with Fixed Confidence III: δ-PAC Guarantee of Chernoff's Stopping Rule for Bernoulli BanditsResearch Paper

In best arm identification with fixed confidence, a learner samples KKK unknown distributions ("arms") one at a time, and must eventually stop and name the arm with the largest mean, with an error probability at most a prescribed risk δ\deltaδ, while using as few samples as possible. The problem goes back to the sequential design of experiments (Chernoff, 1959;…

10 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities II: The Uniform Deviation BoundResearch Paper

Bernoulli's law of large numbers says that the relative frequency of a single event AAA in lll independent trials converges in probability to P(A)P(A)P(A). Statistics and learning theory need more: the probabilities of a whole class SSS of events are judged from one and the same sample, so the frequencies must converge uniformly over the class. Uniform convergence can…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

A Distributional Interpretation of Robust Optimization II: Box-Robust Sample Average Optimization Is ConsistentResearch Paper

Many decision problems under uncertainty take the form of a stochastic program: choose a decision vvv from a feasible set F\mathcal FF to maximise the expected utility Ex∼μ[f(v,x)]\mathbb E_{x\sim\mu}[f(v,x)]Ex∼μ​[f(v,x)], where the distribution μ\muμ of the uncertain parameter x∈Rmx\in\mathbb R^mx∈Rm is known only through i.i.d. samples x1,…,xnx_1,\dots,x_nx1​,…,xn​. The standard remedy, sample average…

7 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Learnability, Stability and Uniform Convergence III: For an ERM, Leave-One-Out Stability, Universal Consistency and Universal Generalization Are EquivalentResearch Paper

Algorithmic stability asks how much the output of a learning algorithm changes when its training sample is perturbed. Since Devroye and Wagner (IEEE Trans. Inf. Theory 1979) it has served as a route to generalization bounds that does not go through the complexity of the hypothesis class. Bousquet and Elisseeff (JMLR 2002) popularised uniform stability, and…

11 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability+1·Captain: mikedeng1

Learnability, Stability and Uniform Convergence II: Tikhonov-Regularized ERM Learns Convex Lipschitz Stochastic Optimization in Hilbert Space with High ProbabilityResearch Paper

Statistical learning theory asks when a rule that sees only an i.i.d. sample z1,…,zmz_1,\dots,z_mz1​,…,zm​ from an unknown distribution DDD can return a hypothesis whose expected loss is close to the best possible. In supervised classification the classical answer is uniform convergence: learnability holds exactly when empirical risks converge to expected risks uniformly…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimizationStatistics·Captain: mikedeng1

A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers: Error Bounds under Decomposability and Restricted Strong ConvexityResearch Paper

High-dimensional statistics studies estimation when the number of parameters ppp is comparable to, or larger than, the number of observations nnn. The standard estimators in this regime are regularized M-estimators: minimise an empirical loss plus a penalty that encodes structure, such as the Lasso (ℓ1\ell_1ℓ1​ penalty, sparse vectors), the group Lasso (block norms,…

5 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Adversarially Robust Generalization Requires More Data 1: A Robust-Error Lower Bound in the Gaussian ModelResearch Paper

Classifiers trained to high standard accuracy on image benchmarks can be made to fail by perturbations of the input that are small in the ℓ∞\ell_\inftyℓ∞​ norm (Szegedy et al., 2014; Goodfellow et al., 2015). Adversarial training reaches high robust accuracy on the training set, but on CIFAR10 the robust accuracy on held-out data is much lower than on the…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbabilityStatistics·Captain: mikedeng1

Calibrated Learning and Correlated Equilibrium III: A Randomized Forecast Calibrated against Every OpponentResearch Paper

A forecaster who announces "70% chance of rain" is calibrated if, among the days on which that number was announced, it rained on about 70% of them. Dawid (The well-calibrated Bayesian, JASA 1982) proposed calibration as the minimal requirement of an honest probability forecaster. Oakes (Self-calibrating priors do not exist, JASA 1985) showed that no…

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

Calibrated Learning and Correlated Equilibrium I: Calibrated Forecasts with Best Responses Converge to the Set of Correlated EquilibriaResearch Paper

A correlated equilibrium (Aumann 1974) is a joint distribution over the players' strategy profiles such that no player gains by deviating from the strategy the distribution recommends to them. It is the equilibrium notion that learning dynamics in repeated games most naturally reach, and a basic question in learning in games is which simple rules, played…

15 thms4 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector V: Estimation, Prediction and Sparsity Bounds for the LassoResearch Paper

In a linear regression with many more candidate variables than observations, least squares is not defined uniquely and does not estimate anything useful. The Lasso (Tibshirani, 1996) replaces it by an ℓ1\ell_1ℓ1​-penalised least-squares problem, which is convex, can be solved at scale, and returns sparse coefficient vectors. The question that a statistician, a…

10 thms4 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector IV: Estimation and Prediction Error Bounds for the Dantzig SelectorResearch Paper

In high-dimensional linear regression the number of unknown coefficients MMM may be much larger than the number of observations nnn, and the coefficient vector can only be recovered because it is assumed to be sparse: few of its entries are non-zero. Two convex estimators dominate this setting: the Lasso of Tibshirani (1996), an ℓ1\ell_1ℓ1​-penalized least-squares…

10 thms4 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Simultaneous Analysis of Lasso and Dantzig Selector II: Approximate Equivalence of the Lasso and Dantzig Prediction LossesResearch Paper

Two estimators dominate sparse high-dimensional regression, where the number MMM of candidate regressors can far exceed the sample size nnn. The Lasso (Tibshirani, 1996) minimises a least-squares criterion plus an ℓ1\ell_1ℓ1​ penalty. The Dantzig selector (Candès and Tao, 2007) minimises the ℓ1\ell_1ℓ1​ norm of the coefficients subject to a bound on the correlation…

9 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion III: No Method Recovers Incoherent Rank-r Matrices below the Sampling Rate (I.20)Research Paper

Matrix completion asks to recover a matrix from a small random subset of its entries. It models collaborative filtering (a ratings table with most entries missing), sensor-network localisation from partial distance data, and system identification. With no structure the task is hopeless, so one assumes the matrix has low rank rrr and that its information is…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework II: Margin-Based Generalization Bound for the SPO Loss under the Strength PropertyResearch Paper

In the predict-then-optimize paradigm a model first predicts the cost vector of a linear optimization problem from contextual features, and the prediction is then fed to an optimization solver that returns a decision. Examples include routing with predicted travel times and portfolio choice with predicted returns. The quality of a prediction is judged by…

9 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XXV: PAC-BayesTextbook

The MDL and Occam principles of Chapter 7 rank hypotheses by description length and pay for a hypothesis according to its rank. Chapter 31 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), generalizes this to the PAC-Bayesian approach of McAllester: prior knowledge is a prior…

6 thms4 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: naimengye

Understanding Machine Learning XV: Neural NetworksTextbook

A feedforward neural network is a directed acyclic graph of neurons, each computing a fixed scalar activation of a weighted sum of its inputs; fixing the graph and the activation and letting the weights vary gives a hypothesis class. Chapter 20 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO97811072…

8 thms4 active usersReviewed
🏆Completed
Probability·Captain: LG

The Principles of Deep Learning Theory I: Wick's Theorem for Gaussian IntegralsTextbook

The book The Principles of Deep Learning Theory by D. A. Roberts and S. Yaida (arXiv:2106.10165) develops a perturbative, physics-style theory of wide deep neural networks. Every later computation in the book, from the statistics of preactivations at initialization to the neural tangent kernel, reduces to Gaussian expectations of polynomials. The single…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory III: The Vapnik-Chervonenkis Dimension, ε-Nets and Sample ComplexityTextbook

Chapter 3 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks how many random examples suffice to learn a concept from an infinite class. The cardinality bound of Occam's Razor is useless there, yet the rectangle game of Chapter 1 shows that some infinite classes are learnable…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization IV: Regularization by Robustification in Classification and RegressionTextbook

Regularization — adding a penalty on model complexity to an empirical risk minimization objective — is one of the oldest and most reliably effective tools in statistical learning: ridge regression, LASSO, and margin-based support vector machines all fit this template. For decades the regularization weight and penalty function were chosen heuristically or by…

15 thms4 active users
PreviousPage 7 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