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
CombinatoricsProbabilityStatistics·Captain: Shuze Chen

The Nature of Statistical Learning Theory III: The Growth Function Is Linear or LogarithmicTextbook

Statistical learning theory asks when minimizing the error on a finite sample also controls the error on unseen data. For a set of classifiers, the answer given by Vapnik and Chervonenkis is governed by a single combinatorial quantity: how many different ways the set can label ℓ\ellℓ points. Bounds on the generalization error of empirical risk minimization…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes: The Sparse Multinomial Relaxation Bound Is Tight up to Four Features, ψ(k − 4) ≤ ϕ(k) ≤ ψ(k) ≤ ϕ(k + 4)Research Paper

Naive Bayes is one of the oldest and cheapest classifiers for text and count data: given word counts for documents in two classes, it fits one multinomial distribution per class by maximum likelihood and classifies by the likelihood ratio. Its cost is a single pass over the data. In high-dimensional applications (text, genomics) one also wants the…

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

Risk Guarantees for End-to-End Prediction and Optimization Processes: The Excess Squared-Loss Risk Bounds the Squared Excess Optimality-Gap Risk, Scaled by the Squared Diameter of the Feasible SetResearch Paper

Many operational decisions are optimization problems whose cost vector is unknown when the decision is made but can be predicted from observed features: shortest paths under predicted travel times, portfolios under predicted returns, production plans under predicted prices. The common practice, predict-then-optimize, first fits a regression model ggg mapping…

10 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

“Un”Fair Machine Learning Algorithms: With Endogenous Learning Effort, Equal Treatment Accepts a Larger Share of the Protected Group's Good Candidates than Equal Opportunity in a Risky MarketResearch Paper

Lenders, employers and insurers increasingly screen applicants with learned scores, and regulators and the fair machine learning literature ask that such screening be fair across demographic groups. Two notions are standard. Equal treatment (ET) asks that the same decision rule be applied to everyone, regardless of group; the paper notes that it is what the…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Interpretable Optimal Stopping: For Trees of Bounded Depth, the Optimal SAA Value of Tree Policies Converges Almost Surely to the Optimal Tree-Policy ValueResearch Paper

Optimal stopping asks when to halt a stochastic process so as to maximize an expected reward. Examples are exercising an American option, selling an asset, or ending a clinical trial. The optimal policy is the solution of a dynamic program over the whole state space. In high dimension it cannot be computed exactly, and the usual approximations (regression…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Optimal Decision Making Under Strategic Behavior 3: A Three-Value Instance with General Costs Where No Optimal Policy Is Outcome MonotonicResearch Paper

When a decision rule is announced in advance, people may change the features on which the rule acts. A lender, for example, may offer loans with different probabilities to applicants with different reported characteristics. An applicant then weighs the greater chance of receiving a loan against the cost of changing those characteristics. The decision maker…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Optimal Decision Making Under Strategic Behavior 1: Under Additive Outcome Monotonic Costs Some Outcome Monotonic Binary Policy Is OptimalResearch Paper

A lender or other decision maker may publish a rule that assigns a positive decision to an individual with some probability. Once the rule is visible, individuals can change the features on which it acts. The decision maker must therefore evaluate a rule under the distribution it induces after individuals respond, rather than only under the original…

6 thms2 active usersReviewed
🏆Completed
Linear algebraStatistics·Captain: mikedeng1

A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers 2: Spectral Rounding Without Outliers Gives Σ|S_k|/n_k ≤ 64(2+ε)‖X⁰ − X̂‖₁/n²minResearch Paper

Spectral clustering recovers group labels from a similarity matrix: compute its leading eigenvectors, embed each point as a row of the eigenvector matrix, and cluster the rows with k-means. It is a standard last step of convex-relaxation methods for clustering, which first estimate a clustering matrix XXX (with Xij=1X_{ij} = 1Xij​=1 when iii and jjj belong to the same…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 3: Even with Full Information and v_t ≡ 1, Every Bidding Policy Has Worst-Case Expected Regret at Least c√TResearch Paper

Most online advertising inventory is sold one impression at a time in automated auctions, and since about 2019 the major ad exchanges have moved from second-price to first-price rules: the highest bidder wins and pays its own bid. A bidder in a first-price auction must trade off winning probability against the price paid, and that trade-off depends on the…

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

Optimal No-regret Learning in Repeated First-price Auctions 5: With Adversarial Contexts and K = (α+1)M ≤ T^(1/3), Every Policy for Partially Ordered Contextual Bandits Has Regret ≥ √(KT)/(32e³)Research Paper

A bidder in repeated first-price auctions faces a learning problem with two kinds of side information. Their private value is a context that changes every round, and the outcome of one bid reveals something about other bids (graph feedback across actions) and about other values (cross learning across contexts). Han, Zhou and Weissman (arXiv:2003.09795v7)…

12 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 6: If the HOB Law Switches at an Unknown Value Threshold, Every Bidding Policy Has Regret Ω(T)Research Paper

In a first-price auction the highest bidder wins and pays her own bid. Display advertising moved to first-price auctions around 2019, and a bidder who participates in millions of them faces a learning problem: at each round ttt she sees a private value vt∈[0,1]v_t\in[0,1]vt​∈[0,1] for the item, bids bt∈[0,1]b_t\in[0,1]bt​∈[0,1], and wins when btb_tbt​ is at least the highest other bid (HOB) mtm_tmt​,…

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

Thompson Sampling with Information Relaxation Penalties III: As T → ∞ the Action Laws of IRS.FH and IRS.V-Zero Converge to That of Thompson SamplingResearch Paper

Thompson sampling (TS) is the standard randomized heuristic for the Bayesian multi-armed bandit: at each decision it samples a parameter vector from the current posterior and pulls the arm that would be best if the sample were true. It ignores the remaining horizon. Min, Maglaras and Moallemi (arXiv:1902.04251, Management Science, 2025) obtain horizon-aware…

9 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchReinforcement Learning·Captain: mikedeng1

Corruption-Robust Exploration in Episodic Reinforcement Learning I: Regret of SuperVIsed.C Is Bounded by the Bonus Sums of Its Critically Tolerant and Robust Base LearnersResearch Paper

Reinforcement-learning algorithms with regret guarantees, such as UCBVI (Azar, Osband & Munos 2017), assume that every episode is generated by the same Markov decision process. In practice a fraction of episodes can be generated by something else: fraudulent users of a recommender, sensor faults, a strategic participant. Corruption-robust learning asks for…

14 thms2 active usersReviewed
🏆Completed
Quantum Information·Captain: Goku

A Survey of Quantum Learning Theory 5: Atıcı–Servedio: time-efficient quantum learning of k-juntas (corrected)Textbook

This mission develops Chapter 5 of A Survey of Quantum Learning Theory by Srinivasan Arunachalam and Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.

5 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning XII: Coordinate-Wise Krichevsky–Trofimov Betting Has Parameter-Free Regret ‖u‖₁L∞√(2T ln(1 + e‖u‖∞T/ε)) + dεL∞Textbook

In online convex optimization, a learner makes a prediction before seeing the next loss. A standard regret guarantee often depends on a learning rate chosen using the size of the comparator that will be assessed later. That comparator is unknown during play. Chapter 13 of Orabona's textbook uses coin betting to obtain a bound that adapts to every comparator…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 5: Under μ-Strong Convexity, Model-Based Minimization with β_t = μ(t+1)/2 Reaches Expected Function Gap O(1/(μT))Research Paper

Many problems in statistical learning and signal processing minimize an expectation f(x)=Eξ[F(x,ξ)]f(x)=\mathbb E_\xi[F(x,\xi)]f(x)=Eξ​[F(x,ξ)] plus a regularizer or constraint r(x)r(x)r(x), with access to fff only through samples ξ∼P\xi\sim Pξ∼P. The standard tool is the stochastic (proximal) subgradient method, which replaces fff at the current point by a random linear function. Two other methods use…

6 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Certifying Some Distributional Robustness with Principled Adversarial Training 3: The Softmax Loss of a Smooth Deep Network Has a (√2·β_L(θ)+α_L(θ)²)-Lipschitz Input GradientResearch Paper

Sinha, Namkoong, Volpi and Duchi (arXiv:1710.10571, ICLR 2018) train classifiers against adversarial perturbations by solving a Lagrangian relaxation of a Wasserstein distributionally robust problem. The inner problem, sup⁡z{ℓ(θ;z)−γ c(z,z0)}\sup_z \{\ell(\theta;z)-\gamma\, c(z,z_0)\}supz​{ℓ(θ;z)−γc(z,z0​)}, is strongly concave, and hence solvable by gradient ascent with the paper's certificates,…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Incremental Proximal Methods for Large Scale Convex Optimization II: With a Randomized Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge Almost Surely to an OptimumResearch Paper

Many problems in statistical learning, signal processing and distributed optimization minimize a sum of a large number mmm of convex components over a convex set: a data-fit term per sample plus a regularizer or constraint per sample. When mmm is large, a method that processes one component per iteration is often far cheaper per step than one that evaluates the…

7 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Distribution-Free, Risk-Controlling Prediction Sets III: Thresholding the Conditional Expected Loss Gives the Smallest Sets Among Predictors of No Larger Risk (Theorem 8)Research Paper

A set-valued predictor returns, for each input xxx, a set of plausible responses rather than a single guess. Such sets are used wherever a model's output feeds a decision with asymmetric costs: a medical classifier that lists every diagnosis it cannot rule out, a segmentation model that marks every pixel that may belong to a tumour, a protein-structure…

6 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Distribution-Free, Risk-Controlling Prediction Sets I: Upper Confidence Bound Calibration Selects a λ̂ Whose Risk Is at Most α with Probability at Least 1 − δ (Theorem 1)Research Paper

A trained classifier or regressor returns a point prediction, but many uses of machine learning need a prediction set: a set of plausible labels together with a guarantee about how often, or how badly, it misses the truth. Medical imaging, protein structure prediction and multi-label classification are examples where a user wants a set whose expected loss…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 2: Under Strict Activity Every Inequality of the Exponential Family (6b) Is Facet-DefiningResearch Paper

Trained neural networks are increasingly embedded inside optimization models: to verify that a classifier is robust to small input perturbations, to optimize over a learned surrogate of an expensive system, or to choose decisions whose outcome is predicted by a network. When the network uses rectified linear units (ReLU), each neuron y=max⁡{0, w⋅x+b}y=\max\{0,\,w\cdot x+b\}y=max{0,w⋅x+b}…

5 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 1: A ReLU Neuron over a Box Has an Ideal Formulation with One Binary Variable and the Exponential Family (6b)Research Paper

A trained feed-forward neural network with ReLU activations, ReLU(v)=max⁡{0,v}\mathrm{ReLU}(v)=\max\{0,v\}ReLU(v)=max{0,v}, is a piecewise linear function of its input. Many tasks ask for an optimization over such a network with its weights held fixed: verifying that no small perturbation of an image changes its classification, finding adversarial examples, or embedding a learned model of…

7 thms2 active usersReviewed
🏆Completed
Information TheoryProbabilityStatistics·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms II: n ≥ (8σ²/α²)(ε/β + log(2/β)) Samples Give |L_μ(W) − L_S(W)| ≤ α with Probability at Least 1 − β (Theorem 3)Research Paper

A learning algorithm picks a hypothesis WWW from a dataset SSS; its generalization error Lμ(W)−LS(W)L_\mu(W) - L_S(W)Lμ​(W)−LS​(W) measures how far the empirical risk the algorithm sees is from the population risk it is judged by. Classical bounds control this error through the complexity of the hypothesis space (VC dimension, Rademacher complexity) or through the algorithm's…

9 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsProbability·Captain: mikedeng1

A Tutorial on Thompson Sampling III: In the Known-Standard Problem, Every Stationary Deterministic Strategy Has Linearly Growing Expected Regret Under Some PriorResearch Paper

Thompson sampling (TS) selects each action by sampling a parameter from the current posterior and playing the action that is optimal for the sample. It is a stationary randomized strategy: the distribution of the action is a fixed function of the posterior, the same in every period, and the action is drawn at random from it. Its Bayesian regret bounds,…

4 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization 2: For f = ‖x‖², Every k-Sparse Point of the Simplex Has Duality Gap ≥ 2/kResearch Paper

The Frank–Wolfe algorithm minimizes a smooth convex objective over a compact convex domain by choosing an atom through a linear optimization problem and moving toward it. On a domain that is the convex hull of atoms, each ordinary iteration introduces at most one new atom. That makes the method useful when a solution represented with few atoms is valuable,…

5 thms2 active usersReviewed
PreviousPage 17 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