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
Convex OptimizationFunctional AnalysisOptimization·Captain: iris

When Do Gradients Suffice? A Characterization of First-Order Convex OptimizationResearch Paper

First-order methods (gradient descent, Mirror Descent, their stochastic and accelerated variants) are the default tools of large-scale convex optimization, and their guarantees are usually stated in a Euclidean or ℓp\ell_pℓp​ geometry. A basic question underlies all of them: in which normed spaces can a convex Lipschitz function on the unit ball be minimized to…

66 thms1 active userReviewed
Optimization·Captain: iris

Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower BoundsResearch Paper

Finding a point where the gradient of a smooth nonconvex function is small is the basic task of nonconvex optimization. In sufficiently high dimension, Carmon et al. proved an Ω(ε−2)\Omega(\varepsilon^{-2})Ω(ε−2) lower bound under Lipschitz-gradient assumptions, which matches gradient descent. Fixed dimension behaves differently. Bubeck and Mikulincer (COLT 2020)…

45 thms1 active userReviewed
Optimization·Captain: iris

0.4633-Approximation for Online and Offline Non-Monotone DR-Submodular MaximizationResearch Paper

Maximizing a nonnegative DR-submodular function over a down-closed convex set is the continuous counterpart of non-monotone submodular set-function maximization. It appears in MAP inference for determinantal point processes, revenue maximization, and the continuous relaxations used to round set-function problems. In the online version, an adversary chooses…

73 thms1 active userReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit FeedbackResearch Paper

Many sequential decisions under uncertainty share one shape: a decision maker inspects random quantities one at a time, decides after each inspection what to inspect next or whether to stop, and collects a reward that depends on what was seen. Stochastic Boolean function evaluation, the secretary problem, optimal stopping, Pandora's box, scheduling and…

21 thms1 active userReviewed
Bandit AlgorithmsLinear OptimizationOperations Research·Captain: iris

Blind Network Revenue Management and Bandits with Knapsacks Under Limited Switches: LS-2SLP and a Matching Lower Bound Pin the Optimal Regret at T^(1/(2-2^(-ν(s,d))))Research Paper

Network revenue management studies a firm that sells several products made from shared, limited resources over a finite season: airline seats on connected legs, hotel room nights, retail items that share inventory. In the blind version the firm does not know how demand responds to price and has to learn it while selling. Besbes and Zeevi (2012) posed this…

18 thms1 active userReviewed
Operations ResearchOptimizationStochastic Systems·Captain: iris

An Online Learning Approach to Dynamic Pricing and Capacity Sizing in Service Systems: GOLiQ Has Gradient Bias at Most K0/(8k)K_0/(8k)K0​/(8k) and Regret O((log⁡ML)2)O((\log M_L)^2)O((logML​)2) in a GI/GI/1GI/GI/1GI/GI/1 QueueResearch Paper

A service provider who runs a single-server queue chooses two numbers: the fee ppp charged to each customer, which determines the demand rate λ(p)\lambda(p)λ(p), and the service capacity μ\muμ, which costs c(μ)c(\mu)c(μ) per unit time. Waiting customers cost h0h_0h0​ per unit time. When the distributions of interarrival and service times are known, the profit-maximizing pair …

28 thms1 active userReviewed
Operations ResearchOptimizationStatistics·Captain: iris

An Asymptotically Tight Learning Algorithm for Mobile-Promotion Platforms: The Policy BidAlloc Has Regret at Most K2K12TTIK_2 K_1^{2T}\sqrt{T}\sqrt{I}K2​K12T​T​I​ Over III SeasonsResearch Paper

Mobile-promotion platforms sell advertisers a number of ad impressions to be delivered within a time window, and buy those impressions one at a time by bidding on an ad exchange. A bid that is too low misses a campaign's target, which costs a penalty; a bid that is too high overpays. The difficulty is that the platform does not know its win curves, the…

27 thms1 active userReviewed
Bandit AlgorithmsConvex OptimizationOperations Research+1·Captain: iris

Optimal Learning for Structured Bandits: DUSA Has Asymptotic Regret at Most (1+ε)(C(P)+ε(1+Σₓ∆(x,P))) log T, Matching the Lower Bound C(P) as ε → 0, with O(log T) Exploration RoundsResearch Paper

In a multi-armed bandit a learner repeatedly pulls one of finitely many arms and observes a random reward, trying to earn as much as an omniscient learner who knows the best arm. In many operations problems the arms are not unrelated: in dynamic pricing the probability of no sale is monotone in the price, in assortment or dosage problems mean rewards vary…

20 thms1 active userReviewed
Operations ResearchReinforcement LearningStatistics·Captain: iris

Optimal Oracle Inequalities for Projected Fixed-Point Equations, with Applications to Policy Evaluation: Averaged Stochastic Approximation Attains the Instance-Dependent Approximation FactorResearch Paper

Many estimation problems ask for the solution v∗v^*v∗ of a linear fixed-point equation v=Lv+bv=Lv+bv=Lv+b on a high- or infinite-dimensional space, when only noisy unbiased samples of LLL and bbb are available. The leading example is policy evaluation in reinforcement learning: the value function of a Markov reward process solves the Bellman equation v=r+γPvv=r+\gamma Pvv=r+γPv, and…

20 thms1 active userReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

Multiplayer Bandits Without Observing Collision Information: A Decentralized Algorithm Has Expected Regret O(mK log(T)/Δ²)Research Paper

In cognitive radio networks, several radios share a set of frequency channels. Each radio picks a channel in every time slot. The quality of a channel is random and unknown, and two radios that pick the same channel interfere and transmit nothing. This is the multiplayer multi-armed bandit problem: mmm players repeatedly choose among KKK arms, an arm pays a…

16 thms1 active userReviewed
Algorithmic Game TheoryBandit AlgorithmsMechanism Design+1·Captain: iris

Bilateral Trade: A Regret Minimization Perspective: Under Realistic Feedback and Independent Bounded-Density Valuations, Scouting Bandits Has Regret O(MT^{2/3}) via an Explicit Bound in T₀, K and αResearch Paper

In bilateral trade a seller and a buyer each hold a private valuation for one good, and an intermediary (a platform or broker) decides at which price the good changes hands. Myerson and Satterthwaite showed that no mechanism can be at once efficient, incentive compatible, individually rational and budget balanced (Myerson–Satterthwaite 1983). Among…

17 thms1 active userReviewed
Algorithmic Game TheoryReinforcement Learning·Captain: iris

A General Framework for Learning Mean-Field Games: GMF-V reaches the stationary mean-field equilibrium within C₀ε with probability 1 − 2δ, with an explicit sample-complexity boundResearch Paper

Mean-field games (MFGs) approximate stochastic games with many identical, interchangeable players by a single representative player who interacts with the distribution of the population (Huang, Malhamé, Caines 2006; Lasry, Lions 2007). In applications such as online ad auctions the reward and the dynamics are not known in closed form, and the equilibrium…

15 thms1 active userReviewed
🏆Completed
Bandit AlgorithmsMarkov ChainOptimization+1·Captain: QianJaneXie

Cost-aware Bayesian Optimization via the Pandora's Box Gittins IndexResearch Paper

Formal verification complete: all 12 mission targets, including Theorem 2, are Proved. These results apply to the formalized independent-box model described below. Paper: Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index, NeurIPS 2024. The formalization follows Theorem 2 and Appendix B.5 of the paper.

13 thms1 active userReviewed
Convex OptimizationInformation TheoryOptimization·Captain: mikedeng1

Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal: under d^(2−δ) bits of memory, first-order methods need Ω̃(d^(1+δ/3)) queriesResearch Paper

Minimizing a convex Lipschitz function over the unit ball of Rd\mathbb R^dRd to accuracy ϵ\epsilonϵ takes Θ(dlog⁡(1/ϵ))\Theta(d\log(1/\epsilon))Θ(dlog(1/ϵ)) first-order queries when ddd is small compared with 1/ϵ1/\epsilon1/ϵ, and cutting-plane methods such as the center-of-mass method attain this rate (Nemirovski–Yudin 1983). They do so by storing their whole cutting history, about …

18 thms1 active userReviewed
OptimizationReinforcement Learning·Captain: mikedeng1

Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima: Neural TD with Stochastic Semigradients Converges to the Global Optimum of the MSPBE at Rate 1/√TResearch Paper

Temporal-difference (TD) learning estimates the value of a policy in a Markov decision process from sampled transitions, by repeatedly moving a parametrized value function towards a one-step bootstrapped target (Sutton, 1988). With a linear parametrization its behaviour is well understood: TD converges to the fixed point of the projected Bellman equation (Ts…

10 thms1 active userReviewed
Bandit AlgorithmsProbabilityReinforcement Learning·Captain: mikedeng1

Nonasymptotic Analysis of Monte Carlo Tree Search: UCB with a Polynomial Bonus on a Non-Stationary Bandit Converges and Concentrates PolynomiallyResearch Paper

Monte Carlo tree search repeatedly chooses actions using estimates built from earlier simulations. The rewards attached to an action need not form an independent, identically distributed sequence: deeper parts of the search tree change as the search proceeds. Shah, Xie and Xu isolate this difficulty in a non-stationary multi-armed bandit and study a version…

9 thms1 active userReviewed
ProbabilityReinforcement LearningStochastic Systems·Captain: mikedeng1

Reusing Historical Trajectories in Natural Policy Gradient via Importance Sampling: Asymptotic Normality of the RNPG Error, with Reuse Shrinking the Joint-Noise Covariance by 1/KResearch Paper

In reinforcement learning, each policy update may require new interaction with an environment. When interaction is costly, an optimizer can retain past trajectories and use them again, provided it corrects for the different policy that generated them. Lin, Wang, and Zhou study this idea for natural policy gradient, using importance weights to reuse earlier…

10 thms1 active userReviewed
Bandit AlgorithmsStatistics·Captain: mikedeng1

Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes: The SmoothBandit Algorithm Has Regret Õ(T^((β+d−αβ)/(2β+d)) + 1) on Every Hölder-Smooth InstanceResearch Paper

In a contextual bandit a decision maker repeatedly observes a context XtX_tXt​, chooses one of two actions, and sees the reward of that action only. Personalised medicine, dynamic pricing and online advertising have this structure: the reward of the action not taken is never observed, so learning and earning must be balanced. Performance is measured by the regret…

11 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Mean Field Analysis of Deep Neural Networks: The SGD-Trained Two-Hidden-Layer Network Converges, as Its Layer Widths Grow in Turn, to the Unique Solution of a Limiting Integro-Differential SystemResearch Paper

A neural network can change its behavior substantially when both its width and its training duration grow. For a network with two hidden layers, the parameters of the layers interact during training, so a large-width description must account for the output of the actual optimization algorithm. Sirignano and Spiliopoulos study this question for online…

9 thms1 active userReviewed
ProbabilityReinforcement LearningStatistics·Captain: mikedeng1

Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning: Cross-Fitted DRL Is Asymptotically Linear and Normal at the MDP Efficiency BoundResearch Paper

Off-policy evaluation (OPE) asks for the long-run value of a target decision policy, using only data collected under a different policy. It arises wherever running the target policy is expensive or unsafe: a new treatment rule in medicine, a new recommendation or pricing rule, a candidate controller in reinforcement learning. Importance-sampling estimators…

13 thms1 active userReviewed
Quantum Information·Captain: Goku

Sample-optimal learning of stabilizer statesResearch Paper

Sample-optimal learning of stabilizer states establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Fast Estimation of Sparse Quantum NoiseResearch Paper

Fast Estimation of Sparse Quantum Noise establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Provably efficient machine learning for quantum many-body problemsResearch Paper

Provably efficient machine learning for quantum many-body problems establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Foundations for learning from noisy quantum experimentsResearch Paper

Foundations for learning from noisy quantum experiments establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Robust shadow estimationResearch Paper

Robust shadow estimation establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
PreviousPage 34 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