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

Improved Algorithms for Linear Stochastic Bandits II: Constant High-Probability Regret of UCB(δ)Research Paper

The stochastic multi-armed bandit is the basic model of sequential decision making under uncertainty: a learner repeatedly chooses one of ddd actions, observes a noisy reward for the chosen action only, and must balance exploring poorly known actions against exploiting the one that currently looks best. It underlies adaptive clinical trials, online…

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

Logarithmic Regret Algorithms for Online Convex Optimization 1: Logarithmic Regret of Online Gradient DescentResearch Paper

Online convex optimization is a repeated game between a learner and an adversary. In each round t=1,…,Tt=1,\dots,Tt=1,…,T the learner commits to a point xtx_txt​ of a convex set P⊆Rn\mathcal P\subseteq\mathbb R^nP⊆Rn; only then is a convex cost function ftf_tft​ revealed, and the learner pays ft(xt)f_t(x_t)ft​(xt​). The learner is judged by its regret: its total cost minus the total cost of the best…

5 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework I: Natarajan-Dimension Generalization Bound for Polyhedral Feasible RegionsResearch Paper

In many operational problems (shortest paths, assignment, planning) the decision solves a linear program whose cost vector is unknown at decision time and is predicted from contextual features. The predict-then-optimize pipeline fits a model fff that maps a feature vector xxx to a predicted cost vector c^=f(x)\hat c=f(x)c^=f(x), and then acts on the decision that is optimal…

9 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization I: Kantorovich Duality and Strong Duality for the Worst-Case RiskTextbook

Every data-driven decision problem faces the same trap. A decision-maker estimates a risk functional R(P,ℓ)=EP[ℓ(ξ)]R(P,\ell) = \mathbb{E}_P[\ell(\xi)]R(P,ℓ)=EP​[ℓ(ξ)] from a nominal distribution P^N\hat P_NP^N​ built from NNN training samples, then optimizes a loss function ℓ\ellℓ against P^N\hat P_NP^N​ instead of the unknown true distribution PPP. Because the optimizer adapts to the noise in P^N\hat P_NP^N​,…

23 thms5 active users
🏆Completed
ProbabilityStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning XII: Algorithmic StabilityTextbook

Every generalization bound in Chapters 2-11 depends only on the complexity of a fixed hypothesis set HHH — Rademacher complexity, VC-dimension, growth function — and holds regardless of which algorithm within HHH actually returns the hypothesis. This is both a strength (broad applicability) and a limitation: it throws away everything specific to how an…

12 thms5 active users
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Statistics V: Thresholding-Based Covariance EstimationTextbook

Estimating a d×dd\times dd×d covariance matrix Σ\SigmaΣ from nnn samples is a canonical high-dimensional problem: the natural estimator, the sample covariance Σ^\hat\SigmaΣ^, is consistent in operator norm only when n≳dn\gtrsim dn≳d, which fails outright in the regime d≫nd\gg nd≫n common to modern applications. When Σ\SigmaΣ is additionally known to be sparse — few nonzero entries per…

15 thms5 active users
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

High-Dimensional Statistics II: Talagrand's Convex Concentration InequalityTextbook

Chapter 2's tail bounds mostly rest on moment-generating-function control, obtained either directly (sub-Gaussianity) or through explicit combinatorial arguments (Hoeffding, bounded differences). The entropic method offers a different, more structural route: bound a specific information-theoretic quantity — the φ\varphiφ-entropy of eλXe^{\lambda X}eλX — and convert…

8 thms5 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

High-Dimensional Statistics VII: Eigenvector Perturbation for High-Dimensional PCATextbook

Principal component analysis (PCA) is one of the oldest and most widely used tools in multivariate statistics: given data with covariance matrix Σ\SigmaΣ, project onto the top eigenvector(s) of Σ\SigmaΣ to find the directions of maximal variance. In practice one never observes Σ\SigmaΣ itself, only a perturbed version — a sample covariance matrix …

18 thms5 active users
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Support Vector Machines VI: An Oracle Inequality for Classifying with Support Vector MachinesTextbook

A support vector machine for classification is trained by minimizing a regularized hinge-loss objective — never the classification loss itself, which is non-convex and computationally intractable to minimize. Every earlier mission in this series supplies one piece of the argument that this substitution is nonetheless justified: 01-loss-functions shows the…

10 thms5 active usersReviewed
🏆Completed
ProbabilityStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning V: Kernel Methods and the Representer TheoremTextbook

Linear methods like SVMs work only when the classes are linearly separable, but most real data is not. Chapter 6 shows how to get non-linear decision boundaries for free: replace the input space's inner product with a kernel KKK that implicitly computes an inner product in a (possibly very high- or infinite-dimensional) feature space, without ever explicitly…

7 thms5 active usersReviewed
🏆Completed
ProbabilityRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability IV: Norms of Random Matrices with Sub-gaussian EntriesTextbook

Random matrices with independent entries appear whenever a system is measured through many noisy, roughly independent channels: shot noise in a sensor array, edges in an Erdős–Rényi-type random graph, or the design matrix of a linear model with independent covariates. A basic question about any such matrix AAA is how far it can stretch a vector — its operator…

12 thms5 active users
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning VI: The Classic Conditional Gradient MethodTextbook

Every method in Chapters 2-4 of this series solves a projection or proximal subproblem at every step — a Euclidean projection, or a Bregman-divergence prox-mapping — which can itself be as hard as the original problem when XXX is a complicated feasible set (a spectrahedron, a flow polytope, a matroid base polytope). The conditional gradient method (Frank &…

4 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning V: Nonconvex Stochastic Mirror DescentTextbook

Most machine learning training objectives — deep network losses, matrix factorization, regularized empirical risk with a nonconvex loss — are not convex, yet the great majority of convergence theory available before Ghadimi and Lan's 2013 work applied only to convex problems or gave no non-asymptotic rate at all. Ghadimi and Lan (2013) established the first…

10 thms5 active users
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning IV: Variance-Reduced Mirror Descent for Finite-Sum ProblemsTextbook

Empirical-risk-minimization objectives in machine learning are finite sums: Ψ(x)=1m∑i=1mfi(x)+h(x)\Psi(x) = \frac{1}{m}\sum_{i=1}^m f_i(x) + h(x)Ψ(x)=m1​∑i=1m​fi​(x)+h(x), one smooth term fif_ifi​ per training example (or per worker, in a distributed setting), plus a simple nonsmooth regularizer hhh. Chapter 4's basic stochastic mirror descent handles this by sampling a single random component gradient …

10 thms5 active users
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning II: Subgradient Descent, Mirror Descent and Accelerated Gradient DescentTextbook

Gradient descent's convergence rate for a general smooth convex problem is O(1/k)O(1/k)O(1/k) in the function-value gap; Nemirovski and Yudin (1983) proved that no first-order method can do better than O(1/k2)O(1/k^2)O(1/k2) is achievable, and Nesterov (1983, 1988, 2004) constructed the first method attaining it — the accelerated (or "fast") gradient method. For thirty years this…

14 thms5 active users
🏆Completed
Algorithmic Game TheoryConvex OptimizationLinear Optimization+1·Captain: mikedeng1

Introduction to Online Convex Optimization VIII: Solving Zero-Sum Games and Linear Programs via Regret MinimizationTextbook

Two-player zero-sum games and linear programming are, on their surface, unrelated pieces of 20th-century mathematics: von Neumann's minimax theorem for games (1928) was proved with tools from topology, and linear programming duality (Dantzig, 1940s) with convexity and geometry. Yet the two are formally equivalent — Dantzig recounts von Neumann conjecturing…

8 thms5 active users
🏆Completed
Operations ResearchQuantum InformationStochastic Systems·Captain: tianyipeng

Markov Entanglement: Value Decomposition Error in Multi-agent MDPsResearch Paper

Value decomposition — approximating the value of a joint state by a sum of per-agent local values — is a staple of multi-agent dynamic programming and reinforcement learning, from index policies for restless bandits to modern MARL architectures, yet it is normally used without justification. Chen and Peng (arXiv:2506.02385) supply one. They show a…

25 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms XIII: Pure Exploration and Best-Arm IdentificationTextbook

Sometimes reward during learning is irrelevant — a pharmaceutical company running phase-II trials only cares about identifying the best treatment, as quickly and as reliably as possible. Chapter 33 of Lattimore–Szepesvári formalizes fixed-confidence best-arm identification: a policy together with a stopping time τ\tauτ and a recommendation must be sound (wrong…

50 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms IV: Bernoulli Bandits and KL-UCBTextbook

When rewards are binary — a click or no click, a cure or no cure — the subgaussian machinery of Missions I–III is not tight: the variance of a Bernoulli arm degrades near the boundary of [0,1][0,1][0,1], and the correct exponential rate is governed by the binary relative entropy d(p,q)=plog⁡pq+(1−p)log⁡1−p1−qd(p,q) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}d(p,q)=plogqp​+(1−p)log1−q1−p​ rather than a squared distance.…

28 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms VI: Information-Theoretic FoundationsTextbook

Every lower bound in bandit theory rests on one question: how hard is it to tell two probability measures apart from a sample? The answer is quantified by the relative entropy D(P,Q)D(P,Q)D(P,Q), and the sharpest elementary tool is the Bretagnolle–Huber inequality: for any event AAA, P(A)+Q(Ac)≥12exp⁡(−D(P,Q))P(A) + Q(A^c) \ge \frac{1}{2}\exp(-D(P,Q))P(A)+Q(Ac)≥21​exp(−D(P,Q)) — no test can distinguish PPP from QQQ with total…

5 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsConvex Optimization·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism: One-Bit Feedback Achieves O(T3/5log⁡5T)O(T^{3/5}\log^{5}T)O(T3/5log5T) Regret for Independent Regular ValuationsResearch Paper

A broker stands between a seller and a buyer. It posts a price to each, and the trade happens only if both accept. Posted prices are the standard mechanism when the parties cannot be asked to report their values: they are simple, strategy-proof and individually rational. When the trade repeats, the broker must learn profitable prices while observing only…

27 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsConvex Optimization·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism: One-Bit Feedback Achieves O(Tlog⁡5/2T)O(\sqrt{T}\log^{5/2}T)O(T​log5/2T) Regret for Independent MHR ValuationsResearch Paper

A broker stands between a seller who owns one item and a buyer who may want it. In every round t=1,…,Tt=1,\dots,Tt=1,…,T a fresh pair of private valuations (st,bt)∈[0,1]2(s_t,b_t)\in[0,1]^2(st​,bt​)∈[0,1]2 arrives, and the broker posts a price ptp_tpt​ to the seller and a price qtq_tqt​ to the buyer. Trade happens when both accept (st≤pts_t\le p_tst​≤pt​ and qt≤btq_t\le b_tqt​≤bt​), and the broker earns qt−ptq_t-p_tqt​−pt​. The broker sees only…

21 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit Algorithms·Captain: iris

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism: Every Algorithm Has Ω(T3/5)\Omega(T^{3/5})Ω(T3/5) Regret on Some Independent Regular ValuationsResearch Paper

A broker stands between a seller and a buyer with private valuations. It posts a price ppp to the seller and a price qqq to the buyer; trade happens if the seller accepts ppp and the buyer accepts qqq, and the broker keeps the spread q−pq-pq−p. When such trades repeat, the broker must learn good prices from experience. Brüstle, di Gregorio, Fusco and Leonardi determine…

14 thms4 active usersReviewed
Quantum Information·Captain: mikedeng1

Agnostic proper learning of stabilizer states from Pauli measurementsResearch Paper

A quantum experiment consumes copies of an unknown state to obtain classical observations. When the observables of interest commute, several outcomes can be obtained from one copy. This matters for predicting outcomes of Pauli measurements and for evaluating sums of Pauli terms in quantum algorithms. A prediction task asks for more than estimating one…

33 thms4 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Cryptographic Guarantees for Distributed Training Under Malicious AdversariesResearch Paper

Distributed training splits the computation of a gradient across many workers whose contributions are combined by an aggregation server. When some workers are malicious and the server is untrusted, protocols add three kinds of safeguard: cryptographic checks that a reported aggregate is consistent with committed local gradients, differential privacy noise…

9 thms4 active usersReviewed
PreviousPage 5 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