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
Captain: Minghui

Certified Federated Unlearning for Linearized ModelsResearch Paper

Federated learning combines information from several clients without pooling their raw training records. A client may later request removal of its contribution. Retraining on the retained records supplies a natural comparison model, but repeating the training process can be costly. Jin, Chen, Zhang, and Li introduce a linearized learning pipeline and a…

7 thms2 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: mikedeng1

Robustness and Generalization IV: Robustness of the Lasso on a Compact Sample SpaceResearch Paper

The Lasso (Tibshirani 1996, doi:10.1111/j.2517-6161.1996.tb02080.x) is ℓ1\ell_1ℓ1​-penalized least squares regression, one of the standard estimators of statistics and machine learning because it selects sparse coefficient vectors. Explaining why a learned Lasso predictor generalizes is less routine than it looks. The two classical routes are uniform convergence…

7 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Robustness and Generalization III: Quantile-Value and Truncated-Mean Generalization Bounds for Pseudo-Robust AlgorithmsResearch Paper

Classical generalization bounds control the gap between the expected loss of a learned hypothesis and its average loss on the training sample. The average is sensitive to outliers: when a non-negligible fraction of the sample is corrupted, the mean loss stops describing the quality of a solution, and quantile-type summaries such as the median become the…

7 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Robustness and Generalization II: A Learning Method Generalizes w.r.t. a Training Sequence If and Only If It Is Weakly Robust w.r.t. ItResearch Paper

Most generalization guarantees in statistical learning theory bound the gap between training error and expected error through a complexity measure of the hypothesis class: VC dimension, Rademacher complexity, covering numbers. Such bounds are sufficient conditions, and they say little about why a particular algorithm, run on a particular data stream, does…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Robustness and Generalization I: A Generalization Bound for Robust AlgorithmsResearch Paper

A learning algorithm maps a training set to a hypothesis. It generalizes when the loss it incurs on the training set is close to its expected loss on fresh data. The classical way to certify this bounds the complexity of the whole hypothesis class the algorithm may output, through its VC dimension, covering numbers or Rademacher complexity. A second…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: mikedeng1

Approximately Optimal Approximate Reinforcement Learning I: Conservative Policy Iteration Improves Monotonically and Returns a Near-Greedy PolicyResearch Paper

Approximate policy iteration and policy gradient methods are the two classical families of reinforcement learning algorithms that work with approximate, sampled information instead of an exact model. Kakade and Langford (ICML 2002) observed that neither family answers three basic questions: is there a performance measure that is guaranteed to improve at…

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

Optimal Best Arm Identification with Fixed Confidence II: Characterization of the Optimal Proportions of Arm DrawsResearch Paper

In best arm identification with fixed confidence, a learner samples KKK unknown distributions ("arms") sequentially and must name the arm with the largest mean, with error probability at most a prescribed δ\deltaδ, using as few samples as possible. Garivier and Kaufmann (arXiv:1602.04589, COLT 2016) showed that every δ\deltaδ-PAC strategy needs, in expectation,…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Stochastic Quasi-Newton Method for Large-Scale Optimization: The Expected Suboptimality Bound of the SQN MethodResearch Paper

Training a statistical model by empirical risk minimization means minimizing an average of NNN losses over a parameter vector w∈Rnw\in\mathbb R^nw∈Rn, where both NNN and nnn can be in the millions. Stochastic gradient descent (SGD) is the standard method: each step uses the gradient of a small random batch of losses. It is cheap per step but sensitive to the scaling of…

13 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities I: The Growth Function DichotomyResearch Paper

Statistical learning theory asks when the empirical frequencies of a whole class of events converge to their probabilities uniformly over the class. Vapnik and Chervonenkis answered this question in 1971 (Theory Probab. Appl. 16 (1971) 264–280) by attaching to every class of sets a single combinatorial quantity, the growth function, and bounding the…

9 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimal Transport+2·Captain: mikedeng1

Distributionally Robust Logistic Regression II: Worst- and Best-Case Misclassification Risks over a Wasserstein Ball Are Linear ProgramsResearch Paper

A logistic regression model is fitted on finitely many samples, and the quantity a practitioner cares about is the misclassification risk of the fitted classifier on new data. Its empirical counterpart, the training error, is biased downwards, and classical generalization bounds give it an additive margin that depends on a complexity measure of the model…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Distributionally Robust Logistic Regression I: The Worst-Case Expected Logloss over a Wasserstein Ball Is a Tractable Convex ProgramResearch Paper

Logistic regression is among the most widely used classification methods in statistics and machine learning. Its maximum-likelihood estimator minimizes the average logloss on the training data and is known to overfit when data are scarce; practitioners respond with ad hoc regularization, typically a norm penalty on the weight vector. Shafieezadeh-Abadeh,…

9 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Adversarially Robust Generalization Requires More Data 3: Robust Learning in the Gaussian Model with Enough SamplesResearch Paper

Classifiers trained by standard methods can be fooled by small, carefully chosen perturbations of their inputs. Adversarial training reduces this vulnerability on the training set, but on image benchmarks such as CIFAR10 the robust accuracy on held-out data remains far below the training accuracy. Schmidt, Santurkar, Tsipras, Talwar and Mądry (arXiv:1804.112…

10 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOptimization·Captain: mikedeng1

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits II: The Iteration Bound of Coordinate DescentResearch Paper

In the contextual bandit problem a learner repeatedly observes a context, picks one of KKK actions, and sees the reward of that action only. Against a finite class Π\PiΠ of policies, statistically optimal regret of order KTln⁡∣Π∣\sqrt{KT\ln|\Pi|}KTln∣Π∣​ has been known since EXP4 (Auer et al., 2002), but EXP4 maintains a weight per policy and costs Ω(∣Π∣)\Omega(|\Pi|)Ω(∣Π∣) time per…

7 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Stochastic Linear Optimization under Bandit Feedback 2: A Regret Lower Bound on the CircleResearch Paper

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a point xtx_txt​ from a compact decision set D⊂RnD\subset\mathbb R^nD⊂Rn and observes only the random cost ℓt\ell_tℓt​ of that point, whose mean is μ⋅xt\mu\cdot x_tμ⋅xt​ for an unknown vector μ\muμ. The problem models online routing, ad placement and other sequential decisions with linearly structured…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: naimengye

Understanding Machine Learning XXIV: Compression BoundsTextbook

The book has characterized learnability through uniform convergence and through stability; Chapter 30 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), gives a third sufficient condition, compression: if a learning algorithm's output can be reconstructed from a small subsequence of kkk tr…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: naimengye

Understanding Machine Learning XXIII: Multiclass LearnabilityTextbook

Chapter 17 introduced multiclass prediction; Chapter 29 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), asks the two questions the fundamental theorem answered for binary classes: which classes of multiclass predictors are PAC learnable with respect to the 0–1 loss, and with what…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: naimengye

Understanding Machine Learning XXII: Proof of the Fundamental TheoremTextbook

Chapter 6 stated the fundamental theorem of statistical learning: a binary class is learnable if and only if its VC dimension is finite, with sample complexity Θ((d+ln⁡(1/δ))/ϵ2)\Theta((d + \ln(1/\delta))/\epsilon^2)Θ((d+ln(1/δ))/ϵ2) in the agnostic case and Θ((dln⁡(1/ϵ)+ln⁡(1/δ))/ϵ)\Theta((d\ln(1/\epsilon) + \ln(1/\delta))/\epsilon)Θ((dln(1/ϵ)+ln(1/δ))/ϵ) in the realizable case. Chapter 28 of Shalev-Shwartz and Ben-David, Understanding…

11 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XX: Rademacher ComplexitiesTextbook

Chapter 4 showed that uniform convergence suffices for learnability; Chapter 26 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), measures its rate. The representativeness of a sample, sup⁡h∈H(LD(h)−LS(h))\sup_{h \in H}(L_D(h) - L_S(h))suph∈H​(LD​(h)−LS​(h)), is the quantity that controls the excess risk of ERM, and the…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: naimengye

Understanding Machine Learning XVI: Online LearningTextbook

In PAC learning the learner receives a batch of examples, learns, and only then predicts. Online learning has no such separation: on each round the learner receives an instance, predicts its label, and then sees the true label, and the goal is to make few mistakes over the whole sequence, with no statistical assumption whatsoever on how the sequence is…

10 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: naimengye

Understanding Machine Learning XIV: Nearest NeighborTextbook

Every learning paradigm of the book so far, ERM, SRM, MDL, RLM, is defined by a hypothesis class: the learner searches a predefined set of functions. Nearest Neighbor is the first method that is not. It memorizes the training set and labels a new point by the labels of its closest neighbors, on the assumption that the features are relevant to the labels in…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOptimization·Captain: naimengye

Understanding Machine Learning XIII: Multiclass Prediction and RankingTextbook

Binary classification is the exception in practice; most prediction tasks have many labels, a structured label space, or ask for a ranking. Chapter 17 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) extends linear predictors to these settings through one idea: a class-sensitive…

12 thms2 active usersReviewed
🏆Completed
Optimization·Captain: naimengye

Understanding Machine Learning XII: Kernel Methods and the Representer TheoremTextbook

Chapter 15 bounded the sample complexity of large-margin halfspaces by the norms of the data and of the separator, independently of the dimension. Chapter 16 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) removes the remaining obstacle to using halfspaces in very high-dimensional…

8 thms2 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: naimengye

Understanding Machine Learning XI: Support Vector Machines and MarginTextbook

The sample complexity of learning halfspaces in Rd\mathbb{R}^dRd grows with ddd, which is bad news when features are many or infinite. Chapter 15 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) introduces the support vector machine, the learning rule that replaces dimension by geometry.…

15 thms2 active usersReviewed
🏆Completed
Probability·Captain: LG

The Principles of Deep Learning Theory II: Deep Linear Networks at InitializationTextbook

Chapter 3 of The Principles of Deep Learning Theory by D. A. Roberts and S. Yaida (arXiv:2106.10165) is the book's first complete example of its effective-theory method. For deep linear networks at initialization, the two- and four-point correlators of the network outputs can be computed exactly at any width and depth. The resulting formulas exhibit, in the…

11 thms2 active usersReviewed
🏆Completed
Probability·Captain: LG

The Principles of Deep Learning Theory III: Preactivation Statistics in the First Two LayersTextbook

Chapter 4 of The Principles of Deep Learning Theory by D. A. Roberts and S. Yaida (arXiv:2106.10165) begins the analysis of general multilayer perceptrons (MLPs) with a nonlinear activation function σ\sigmaσ at initialization. The first layer is exactly Gaussian; the second layer is the first place where non-Gaussianity appears, as a connected four-point…

12 thms2 active usersReviewed
PreviousPage 20 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