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

Non-Strongly-Convex Smooth Stochastic Approximation with Convergence Rate O(1/n): Averaged Constant-Step-Size LMS Has Expected Excess Risk at Most (1/2n)[σ√d/(1−√(γR²)) + R‖θ₀−θ*‖/√(γR²)]²Research Paper

Least-squares regression fitted by stochastic gradient descent — the least-mean-square (LMS) algorithm — is the basic large-scale learning procedure: each observation is touched once, at a cost linear in the dimension. Classical analyses of stochastic approximation give the rate O(1/n)O(1/\sqrt n)O(1/n​) for non-strongly-convex objectives, and O(1/(μn))O(1/(\mu n))O(1/(μn)) when the…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Oracle-Based Robust Optimization via Online Learning 2: Follow the Perturbed Leader with an ε-Approximate Linear Oracle Has Expected Regret at Most 2√(DRAT) + 2εTResearch Paper

Many decision problems are solved repeatedly against data that arrive over time: routing traffic, allocating budgets, choosing portfolios or combinatorial structures. Online linear optimization models this. At each round t=1,…,Tt = 1, \ldots, Tt=1,…,T a learner picks a decision xtx_txt​ from a fixed domain K⊆Rn\mathcal K\subseteq\mathbb R^nK⊆Rn, then a reward vector ftf_tft​ is revealed…

7 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsConvex Optimization·Captain: mikedeng1

Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient: Bandit Gradient Descent Has Expected Regret ≤ 3Cn^{5/6}∛(12dR/r)Research Paper

In online convex optimization a decision maker picks points x1,x2,…,xnx_1,x_2,\dots,x_nx1​,x2​,…,xn​ in a convex set S⊆RdS\subseteq\mathbb R^dS⊆Rd, and after each choice pays ct(xt)c_t(x_t)ct​(xt​) for a convex cost function ctc_tct​ chosen in advance by an adversary. Performance is measured by regret: the total cost paid minus the cost of the best fixed point in hindsight. Zinkevich (ICML 2003) showed…

12 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsProbabilityStatistics·Captain: mikedeng1

Kullback–Leibler Upper Confidence Bounds for Optimal Sequential Allocation I: kl-UCB Draws a Suboptimal Arm log(T)/d(μ_a, μ*) + O(√log T) Times in One-Parameter Exponential FamiliesResearch Paper

In a stochastic multi-armed bandit a player repeatedly chooses one of KKK distributions ("arms") and observes a reward drawn from it; the goal is to collect as much reward as possible, which amounts to pulling suboptimal arms as rarely as possible. Lai and Robbins (1985) showed that any reasonable strategy must pull a suboptimal arm aaa at least …

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