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
AnalysisFunctional Analysis·Captain: mikedeng1

Theory of Reproducing Kernels IV: The Kernels of a Decreasing Sequence of Reproducing Kernel Classes Converge to the Kernel of the Limit ClassResearch Paper

A reproducing kernel Hilbert space is a Hilbert space of functions on a set in which every point evaluation is continuous; the function K(x,y)K(x,y)K(x,y) that represents evaluation at yyy is its reproducing kernel. N. Aronszajn's Theory of Reproducing Kernels (Trans. Amer. Math. Soc. 68 (1950), 337–404, DOI 10.1090/S0002-9947-1950-0051437-7) gave the general theory of…

11 thms2 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: mikedeng1

Theory of Reproducing Kernels V: A Hermitian Kernel Represents a Bounded Symmetric Operator with Bounds m and M iff mK ≪ Λ ≪ MKResearch Paper

Reproducing kernel Hilbert spaces are the function spaces of kernel methods in statistics and machine learning (Gaussian-process regression, support vector machines, kernel mean embeddings), of the Bergman and Szegő spaces of complex analysis, and of the theory of positive-definite functions. In all of these, bounded operators on the space (covariance…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsFunctional Analysis·Captain: mikedeng1

The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network II: Fat-Shattering Bound for Bounded-Weight NetworksResearch Paper

In the mid-1990s, neural networks trained by gradient descent were observed to generalize well even when the number of weights far exceeded the number of training examples. The classical theory could not explain this: VC-dimension bounds for networks grow with the number of parameters, so for large networks they are vacuous. Bartlett's paper (IEEE Trans.…

11 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Certified Adversarial Robustness via Randomized Smoothing 2: The Certified ℓ2 Radius Cannot Be EnlargedResearch Paper

Neural-network classifiers can be made to change their output by perturbations of the input that are imperceptible to a person. A certified defense is a classifier together with a proof that its prediction at a point xxx does not change for any perturbation δ\deltaδ in a stated set, typically an ℓ2\ell_2ℓ2​ ball ∥δ∥2<R\|\delta\|_2<R∥δ∥2​<R. Randomized smoothing turns an…

11 thms2 active usersReviewed
🏆Completed
ProbabilityReinforcement Learning·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning II: High-Probability Regret Bound for UCBVI with a Bernstein–Freedman BonusResearch Paper

An agent can learn to act in an unknown environment by repeatedly running a finite episode, observing the states reached after its actions, and updating its model of the environment. The agent must trade off rewards in the current episode against information that may improve later decisions. A regret bound measures the cumulative value lost relative to an…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 2: A No-Regret Algorithm and a Valid Halfspace Oracle Approach a Compact Convex Set at Rate 2·Regret_T/TResearch Paper

Blackwell approachability is the vector-payoff analogue of von Neumann's minimax theorem. In a repeated game where each round's outcome is a vector u(xt,yt)∈Rdu(x_t, y_t) \in \mathbb R^du(xt​,yt​)∈Rd, a player wants the running average of these vectors to converge to a target set SSS, whatever the opponent does. Blackwell (1956) showed when this is possible, and approachability has…

6 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction VIII: The TD Fixed Point of Linear Semi-gradient TD(0) and Its Error BoundTextbook

Reinforcement learning methods estimate the value function vπv_\pivπ​ of a policy π\piπ: the expected discounted sum of future rewards from each state. When the state space is large, vπv_\pivπ​ cannot be stored as a table and is approximated by a parametrized function. The most studied case is linear function approximation, where each state sss carries a feature vector …

11 thms2 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Variance-based Regularization with Convex Objectives I: The χ²-Robust Risk Equals Empirical Risk plus a Standard-Deviation PenaltyResearch Paper

Many statistical procedures minimize an average observed loss. This treats two candidates with the same average as equally attractive even when one has much more variable losses across the sample. Adding a multiple of the empirical standard deviation can distinguish them, but the resulting objective need not be convex even when each individual loss is…

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

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems III: Contextual Bandits and the Banditron Mistake BoundTextbook

In many sequential decision problems the learner sees side information before acting. A news site chooses an article for a visitor whose history and location it knows; an ad server chooses an advertisement for a query. Only the reward of the chosen action is observed. These are contextual bandit problems, and Chapter 4 of Bubeck and Cesa-Bianchi's monograph …

11 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsConvex OptimizationOperations Research+1·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems V: Bandit Convex Optimization with One-Point FeedbackTextbook

In bandit convex optimization a forecaster repeatedly picks a point xtx_txt​ of a convex set K⊆Rd\mathcal K\subseteq\mathbb R^dK⊆Rd, and an adversary picks a convex loss ℓt\ell_tℓt​. The forecaster pays ℓt(xt)\ell_t(x_t)ℓt​(xt​) and observes only that number: it never sees the function, its gradient, or its value elsewhere. This is the model of online optimization with only function-value…

11 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsConvex OptimizationOperations Research+1·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems IV: Online Stochastic Mirror Descent for Combinatorial Semi-BanditsTextbook

Many sequential decision problems ask a learner to choose, round after round, a combination of items: a set of mmm ads out of ddd, a path in a network, a matching. After each choice the learner sees the loss of the items it used, not of those it did not. This is online combinatorial optimization with semi-bandit feedback. It contains the classical adversarial…

12 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Certified Adversarial Robustness via Randomized Smoothing 1: The Gaussian-Smoothed Classifier Is Constant on the ℓ2 Ball of Radius (σ/2)(Φ⁻¹(p_A) − Φ⁻¹(p_B))Research Paper

Classifiers trained on images, speech and text can be made to change their prediction by perturbations of the input that are tiny in norm (Szegedy et al., 2014). Empirical defences against such adversarial examples have repeatedly been broken by stronger attacks (Athalye, Carlini, Wagner, 2018), which motivates certified defences: classifiers that come with…

15 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems II: High-Probability and Expected Regret of Exp3.PTextbook

In the adversarial (non-stochastic) multi-armed bandit problem a forecaster repeatedly chooses one of KKK actions while an opponent sets the rewards, and only the reward of the chosen action is revealed. The model was proposed as a way of playing an unknown repeated game: Baños (1968) studied the repeated game in which the player observes only its own payoff,…

13 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Stability and Generalization 1: Polynomial Generalization Bounds from Hypothesis Stability for the Empirical and Leave-One-Out ErrorsResearch Paper

A learning algorithm is judged by its generalization error, its expected loss on a fresh example, which cannot be computed because the data distribution is unknown. Practitioners estimate it either by the empirical error on the training set or by the leave-one-out error, which retrains the algorithm once per example. Classical learning theory justifies…

13 thms2 active usersReviewed
🏆Completed
Convex OptimizationStatistics·Captain: mikedeng1

Stability and Generalization 3: Tikhonov Regularization in a Reproducing Kernel Hilbert Space Has Uniform Stability σ²κ²/(2λm)Research Paper

Learning from a finite sample is useful only if changing the sample has a controlled effect on the learned predictor. Uniform stability asks for a bound on the change in loss at every test point when one training example is removed. Bousquet and Elisseeff use this property to obtain generalization bounds for learning algorithms, and identify regularization…

9 thms2 active usersReviewed
🏆Completed
Linear algebraReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction XI: Dutch Traces and the Equivalence of Forward and Backward Views in Monte Carlo LearningTextbook

Eligibility traces are one of the basic mechanisms of reinforcement learning. A trace is a short-term memory vector ztz_tzt​ with one component per weight. It records which components contributed to recent value estimates, so that an error observed now can be credited to the right components without storing the past. Chapter 12 of Sutton and Barto's Reinforcement…

11 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network I: Fat-Shattering Margin Bound with d = fat_H(γ/16)Research Paper

Classical generalization bounds for classifiers, built on the VC dimension, grow with the number of adjustable parameters. For neural networks this is at odds with practice: networks with many more weights than training examples often generalize well. Bartlett's 1998 paper (IEEE Trans. Inform. Theory 44(2), 525–536) explains part of this by measuring a…

12 thms2 active usersReviewed
🏆Completed
ProbabilityReinforcement Learning·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning I: High-Probability Regret Bound for UCBVI with a Chernoff–Hoeffding BonusResearch Paper

An agent learning to control an unknown environment must balance rewards it can collect now against information that improves later decisions. In a finite Markov decision process (MDP), every action changes the distribution of the next state, so a mistaken transition estimate can affect decisions many steps later. Regret measures this loss against a policy…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 1: Any Approachability Algorithm Yields Online Linear Optimization with Regret/T at Most 2κ Times Its Approachability RateResearch Paper

Online decision makers often have to choose an action before seeing the cost assigned to it. A no-regret algorithm performs almost as well, in total, as the best single action that could have been chosen after the costs were known. In a related repeated-game problem, Blackwell approachability asks a player to keep the average of vector payoffs close to a…

6 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOptimizationReinforcement Learning·Captain: mikedeng1

Reinforcement Learning: An Introduction I: The Gradient Bandit Algorithm Is Stochastic Gradient AscentTextbook

The multi-armed bandit is the simplest setting in which a learner must trade off exploiting what it knows against exploring what it does not: one situation, kkk actions, and a reward drawn from an unknown distribution each time an action is taken. Chapter 2 of Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) uses it to…

11 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchReinforcement Learning·Captain: mikedeng1

Approximately Optimal Approximate Reinforcement Learning II: Near-Optimality of a Policy with Small Policy AdvantageResearch Paper

Approximate policy iteration and policy-gradient methods stop when they can no longer find a direction of improvement. Kakade and Langford (ICML 2002) asked what such a stopping point guarantees. Their algorithm, conservative policy iteration, halts at a policy π\piπ for which no policy can improve much on π\piπ as measured under a restart distribution μ\muμ; the…

10 thms2 active usersReviewed
🏆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
PreviousPage 30 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