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
Bandit AlgorithmsOperations ResearchStatistics·Captain: iris

A Simple and Optimal Policy Design with Safety Against Heavy-Tailed Risk for Stochastic Bandits: SE and UCB Have O(KTln⁡T)O(\sqrt{KT\ln T})O(KTlnT​) Regret and an e−Ω(x/KT)e^{-\Omega(x/\sqrt{KT})}e−Ω(x/KT​) Regret TailResearch Paper

Stochastic multi-armed bandit policies are judged almost always by their expected regret. In operations settings such as dynamic pricing, assortment testing or clinical allocation, a decision maker also cares about the probability of a bad outcome: a policy whose regret is small on average can still incur regret linear in the horizon TTT with non-negligible…

21 thms2 active usersReviewed
Bandit AlgorithmsOperations Research·Captain: iris

Shrinking the Upper Confidence Bound: A Dynamic Product Selection Problem for Urban Warehouses: ConsUCB Has Regret at Most K + αK + 10α√(dKT log(KT)) with Probability at Least 1 − δResearch Paper

An online retailer choosing which low-demand products to display, and to stock in its urban warehouses, faces an unusual learning problem. Thousands of products must be chosen at once, the selection can change only a few times per season, and sales data arrive only for the products that were offered. Jin, Simchi-Levi, Wang, Wang and Yang (arXiv:1903.07844v2)…

19 thms2 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes: Some Posted Price Mechanism Has Regret O(T^{(1+CW/(CW+1))/2}·√log|Γ|) on Every DRACC InstanceResearch Paper

A seller who allocates resources that appear and expire over time (machine slots in a cloud, rooms on given nights, edges of a matching market that change from round to round) often cannot run an auction for every user. A posted price mechanism announces prices before the user arrives and lets the user buy her preferred bundle; it is truthful for myopic…

20 thms2 active usersReviewed
Bandit AlgorithmsGraph TheoryProbability·Captain: iris

Small-Loss Bounds for Online Learning with Partial Information: Double-Threshold Freezing has ϵ\epsilonϵ-approximate regret ≤300α(A(d,T)+3log⁡d+2δ)/ϵ2\le 300\alpha(A(d,T)+3\log\frac{d+2}{\delta})/\epsilon^2≤300α(A(d,T)+3logδd+2​)/ϵ2 w.p. 1−δ1-\delta1−δResearch Paper

In adversarial online learning a learner chooses one of ddd actions (arms) in each of TTT rounds and suffers a loss in [0,1][0,1][0,1]. Classical regret bounds grow with the horizon, O(Tlog⁡d)O(\sqrt{T\log d})O(Tlogd​). A small-loss bound replaces TTT by the loss L⋆L^\starL⋆ of the best arm, which matters whenever good actions exist: routing traffic, choosing treatments, recommending items.…

12 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: iris

Learning to Persuade on the Fly: Robustness Against Ignorance: The Rai Algorithm Has O(√(T log T)) Regret with High ProbabilityResearch Paper

In Bayesian persuasion a sender who observes a random state commits to a rule that maps states to recommendations, and a receiver who knows the state distribution follows a recommendation only when it is optimal given what it reveals (Kamenica and Gentzkow 2011; Bergemann and Morris 2019). When the distribution is known, the sender's best rule solves a…

33 thms2 active usersReviewed
Bandit AlgorithmsInformation Theory·Captain: iris

Satisficing in Time-Sensitive Bandit Learning: Every Policy's Discounted Satisficing Regret Is at Most Γ(A~,ψ) I(A~;θ)/(1−α2)\sqrt{\Gamma(\tilde A,\psi)\,I(\tilde A;\theta)/(1-\alpha^2)}Γ(A~,ψ)I(A~;θ)/(1−α2)​Research Paper

Bayesian bandit algorithms such as Thompson sampling are analyzed through the information ratio: the squared expected shortfall of a period divided by the information the period's observation reveals about the optimal action A∗A^*A∗ (Russo & Van Roy 2016). That analysis bounds regret by Γ H(A∗) T\sqrt{\Gamma\, H(A^*)\, T}ΓH(A∗)T​, where H(A∗)H(A^*)H(A∗) is the entropy of the optimal…

18 thms2 active usersReviewed
StatisticsTheoretical Computer Science·Captain: iris

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization: ℓ_q Mean Estimation for 1 < q < 2 to Error ε with 2d log d Queries to VSTAT((16 log d/ε)^p)Research Paper

The statistical query (SQ) model describes algorithms that never see individual samples of a distribution DDD; they only ask for approximate expectations Ew∼D[ϕ(w)]\mathbf E_{w\sim D}[\phi(w)]Ew∼D​[ϕ(w)] of functions ϕ\phiϕ of their choice. It was introduced by Kearns for noise-tolerant learning (Kearns 1998), and it has since become the standard abstraction for algorithms that can…

24 thms2 active usersReviewed
Operations ResearchOptimizationProbability+1·Captain: iris

Scalable Reinforcement Learning for Multi-Agent Networked Systems: High-Probability Stationarity Bound for Scalable Actor Critic with κ\kappaκ-Hop Truncated Q-FunctionsResearch Paper

Many control problems are posed on networks of agents that each see only a local state and take a local action: traffic signals at intersections, wireless transmitters sharing a channel, nodes of an epidemic or a power grid. Treated as one Markov decision process, such a system has a state space whose size is exponential in the number of agents nnn, so…

22 thms2 active usersReviewed
Dynamic ProgrammingReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XVII: LSVI-UCB Has Regret ≲Hd3Tlog⁡(HT/δ)log⁡(1+T/d)\lesssim H\sqrt{d^3 T\log(HT/\delta)\log(1+T/d)}≲Hd3Tlog(HT/δ)log(1+T/d)​ in Low-Rank MDPsTextbook

In episodic reinforcement learning a learner interacts with an unknown Markov decision process for TTT episodes of HHH steps and is measured by its regret: the total shortfall of the value of the policies it plays against the value of an optimal policy. For tabular problems, where states and actions are few, optimism-based algorithms such as UCB-VI reach regret…

10 thms2 active usersReviewed
Bandit AlgorithmsReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XI: Generalized UCB Has Regret Controlled by the Eluder DimensionTextbook

A structured bandit is a repeated decision problem in which a learner picks a decision πt\pi^tπt from a set Π\PiΠ and observes a noisy reward. The set Π\PiΠ can be large or continuous: a dosage, a price vector, a path in a graph. Treating each decision separately costs regret of order ∣Π∣T\sqrt{|\Pi|T}∣Π∣T​, which is useless when Π\PiΠ is large relative to the horizon TTT. The…

22 thms2 active usersReviewed
Bandit AlgorithmsReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XV: A Family Embedding the Multi-Armed Bandit Forces the Constrained DEC to Be ≳ αTextbook

In interactive decision making a learner repeatedly picks a decision π\piπ from a decision space Π\PiΠ, receives a reward and an observation drawn from an unknown model M⋆M^\starM⋆, and is judged by its regret against the best decision of M⋆M^\starM⋆. Foster and Rakhlin's lecture notes (arXiv:2312.16730) organize the whole theory around one complexity measure, the Decis…

14 thms2 active usersReviewed
Computational Complexity·Captain: Shuze Chen

Training a 3-node neural network is NP-complete: NP-completeness of exact training on Boolean inputsResearch Paper

Training a classifier asks for parameters that fit observed examples. Even when the data can be classified perfectly, the task of finding suitable parameters can have substantial computational cost. The question here concerns exact training: deciding whether any parameter choice makes zero mistakes on the entire supplied data set. It concerns computation on…

7 thms2 active usersReviewed
ProbabilityStatistics·Captain: Shuze Chen

Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory: Variance-dependent generalization for moment penalizationResearch Paper

A learning procedure chooses a hypothesis from observed data, but its quality is determined by performance on future observations. A uniform bound based only on the largest possible loss can obscure a useful feature of a problem: a population-optimal hypothesis may have much smaller loss variance than the worst-case envelope suggests. Variance-dependent…

13 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Robust Dynamic Assortment Optimization in the Presence of Outlier Customers: Active Elimination Has TOTE Regret O(ε̄K²T log T + (K²√ε̄ + √K)√(NT log³T) + K²N log²T) Under ε-ContaminationResearch Paper

A retailer that learns customer preferences online, for example an e-commerce platform choosing which products to display, observes purchases that are not all generated by the population it is trying to learn. Some arrivals are bots, fraudulent accounts or atypical buyers, and their choices can be arbitrary or deliberately misleading. Standard learning…

10 thms2 active usersReviewed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex–Nonconcave Min-Max Optimization: Every Bounded Function with Lipschitz Hessian Has a Greedy Adversarial EquilibriumResearch Paper

Min-max problems min⁡xmax⁡yf(x,y)\min_x\max_y f(x,y)minx​maxy​f(x,y) model two-player zero-sum games and appear across machine learning and operations research: adversarial training of classifiers, generative adversarial networks, and robust optimization against an adversarial perturbation. When fff is convex in xxx and concave in yyy, von Neumann's minimax theorem gives a saddle point, and…

9 thms2 active usersReviewed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

Hedging the Drift: Learning to Optimize under Non-Stationarity: the Bandit-over-Bandit algorithm has dynamic regret Õ(d^{2/3}B_T^{1/3}T^{2/3} + d^{1/2}T^{3/4}) without knowing B_TResearch Paper

Many sequential decision problems in operations research are learned online while the environment changes: demand responds to prices differently from week to week, click-through rates drift, and the value of an action in a recommendation or auto-loan pricing system decays as conditions move. The stochastic linear bandit is the standard model for such…

10 thms2 active usersReviewed
OptimizationProbabilityStatistics·Captain: mikedeng1

Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model: The SDP Clustering Error Is at Most Twice the Oracle Integer Program ErrorResearch Paper

Clustering methods must infer a partition from noisy observations, while the quality of a partition is usually judged against labels that the method cannot see. Fei and Chen study a balanced sub-Gaussian mixture model in which a semidefinite program (SDP) estimates a cluster matrix from pairwise distances. Their Theorem 1 relates its error to a simpler…

13 thms2 active usersReviewed
Bandit AlgorithmsLinear algebraProbability·Captain: mikedeng1

The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Sampling: For Any Prior and Noise, E[Σ Aₜᵀ Γₜ Aₜ] ≤ 2 max(σ², 1) log det(I + T Γ₁)Research Paper

In a linear bandit problem, a learner chooses a vector and observes a noisy scalar response that carries information about an unknown parameter. Regret analyses often need to control the sum of the learner's uncertainty in the directions it chooses. The familiar elliptical potential lemma does this when uncertainty is represented by the inverse of a…

7 thms2 active usersReviewed
ProbabilityStatistics·Captain: Shuze Chen

The Nature of Statistical Learning Theory II: The Basic Inequalities of the Theory of BoundsTextbook

Every guarantee that a learning machine trained by empirical risk minimization will perform well on unseen data rests on one kind of statement: a bound on the probability that, simultaneously over a whole set of functions, observed frequencies stray far from the probabilities they estimate. Vapnik and Chervonenkis proved the first such bounds for sets of…

11 thms2 active usersReviewed
OptimizationProbability·Captain: mikedeng1

Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Explicit Population Risk Bound for Euler SGHMCResearch Paper

Many learning problems are instances of the stochastic program

14 thms2 active usersReviewed
OptimizationStatistics·Captain: mikedeng1

High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks: Excess-Risk Bounds at S3ONC Solutions of MCP-Regularized M-EstimationResearch Paper

High-dimensional statistical learning (HDSL) fits a model with ppp parameters from nnn samples when ppp may far exceed nnn. The standard guarantees for sparse estimators, such as the Lasso, rest on restricted strong convexity (RSC) or restricted eigenvalue conditions on the empirical risk (Negahban et al., 2012; Loh & Wainwright, 2015). These conditions fail or are…

11 thms2 active usersReviewed
OptimizationRandom Matrix TheoryStatistics·Captain: mikedeng1

Nonconvex Low-Rank Tensor Completion from Noisy Data: Spectrally Initialized Vanilla Gradient Descent Recovers the Tensor Factors at a Linear Rate to Near-Optimal ℓ2 and ℓ2,∞ AccuracyResearch Paper

A partially observed array with three indices appears when data record relationships among triples of objects. If its entries have a low-rank structure, one can hope to recover the full array from far fewer than d3d^3d3 measurements. Cai, Li, Poor and Chen study this problem when the measurements are noisy and only a random subset of entries is seen. Their…

8 thms2 active usersReviewed
Markov ChainOperations ResearchStatistics·Captain: mikedeng1

Learning Markov Models Via Low-Rank Optimization: KL Error Bound for the Rank-Constrained Maximum Likelihood Estimator of a Low-Rank Markov ChainResearch Paper

Many systems studied in operations research and reinforcement learning are modelled as finite Markov chains with a large number of states ppp: the stops of a taxi in a city, a random walk on a network, the conformations of a molecule. Estimating the p×pp\times pp×p transition matrix from one observed trajectory needs, in general, a trajectory long compared with the …

13 thms2 active usersReviewed
Operations ResearchStatistics·Captain: mikedeng1

Minimax-Optimal Policy Learning Under Unobserved Confounding: Minimizing the Worst-Case Empirical Regret Attains the Population Minimax Regret up to an Explicit n^(-1/2) TermResearch Paper

Personalized decisions in medicine, marketing and public policy are increasingly learned from observational data: records of who received which treatment and how it turned out. Standard policy-learning methods assume unconfoundedness, that treatment assignment depends only on observed covariates. When an unobserved factor influences both the treatment and…

10 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers 1: Robust-LP Inlier Error ≤ Cn²·max{exp(−Δ²min/64σ²max), log nmin/nmin} with Probability ≥ 1 − 2r/nminResearch Paper

Clustering points drawn from a mixture of well-separated distributions is a basic problem of unsupervised learning. Practical data sets also contain outliers, points that belong to no cluster and may be placed anywhere. Srivastava, Sarkar and Hanasusanto (arXiv:1912.07546v3; Operations Research 71(1), 2023) propose a robust spectral clustering algorithm. It…

16 thms2 active usersReviewed
PreviousPage 9 of 14Next

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