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
Quantum Information·Captain: iris

Efficient Agnostic Learning of Tensor Network StatesResearch Paper

Quantum state tomography asks for a classical description of an unknown quantum state from measurements on independent copies of it. For general states on nnn subsystems the number of copies grows exponentially in nnn (O'Donnell–Wright 2016; Haah et al. 2017), so efficient reconstruction must exploit structure. Tensor network states — matrix product states…

90 thms5 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

Fast Quantum Algorithms for Learning Linear Threshold FunctionsResearch Paper

A linear threshold function (LTF), or halfspace, labels each point of Rn\mathbb R^nRn by the side of a hyperplane on which it lies. LTFs are the classifiers of the perceptron and of linear support vector machines, and learning them is one of the oldest problems in computational learning theory.

72 thms5 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and Learning AlgorithmsResearch Paper

Integer programming solvers expose parameters, and in practice they are run on many instances of one application. Data-driven algorithm configuration asks for parameters that perform well on a training set of instances. For cutting planes, Balcan, Prasad, Sandholm and Vitercik (2021) bound the sample complexity of tuning Chvátal–Gomory cuts: how many…

55 thms5 active usersReviewed
Bandit AlgorithmsGraph Theory·Captain: iris

The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback GraphsResearch Paper

Online learning algorithms randomize to hedge against an adversary, and independent resampling makes them change action often. When changing a route, a deployed model or a treatment has a cost of its own, the right benchmark charges one unit per change. With full information this charge leaves the minimax regret at order Tlog⁡K\sqrt{T\log K}TlogK​ (Kalai and Vempala,…

40 thms5 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

Approximately Stationary Bandits with Knapsacks: Algorithm 1 Earns ρ+σr(σc−ρ)+\rho + \sigma_r(\sigma_c - \rho)^+ρ+σr​(σc​−ρ)+ of OPTFD\mathrm{OPT}_{FD}OPTFD​ Against Adaptive (σr,σc)(\sigma_r, \sigma_c)(σr​,σc​)-Stationary AdversariesResearch Paper

In Bandits with Knapsacks (BwK) a player repeatedly picks one of KKK actions; each choice yields a reward and consumes ddd limited resources, and play stops as soon as a budget runs out. The model covers dynamic pricing with limited inventory, ad auctions with a spending cap and crowdsourcing with a payment budget (Badanidiyuru, Kleinberg, Slivkins 2018). Its…

17 thms5 active usersReviewed
Operations ResearchOptimization·Captain: iris

Global Convergence of Inexact Augmented Lagrangian Method for Zero-One Composite Optimization: Under Full Row Rank and Strong Convexity, the Whole IALM Sequence Converges to a Local MinimizerResearch Paper

Binary classification, multi-label classification and rank correlation estimation all score a model by counting the samples on which a linear score has the wrong sign. The natural penalty is the zero-one loss, which is 111 on positive numbers and 000 on the rest. Support vector machines, multi-label classification and the maximum rank correlation estimator are…

23 thms5 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: iris

Quantifying and Visualizing Attribute Interactions: interaction information satisfies McGill's recursion and decomposes total correlation, which vanishes exactly under mutual independenceResearch Paper

Mutual information measures how much two attributes of a data set depend on each other. A pair of numbers does not describe three attributes. In the exclusive or, C=A+B(mod2)C=A+B \pmod 2C=A+B(mod2), each pair is independent while the triple is fully determined. A triplicated attribute, A=B=CA=B=CA=B=C, is the opposite case: every pair is fully dependent, and given one attribute the other…

22 thms5 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

On the Impossibility of Convergence of Mixed Strategies with Optimal No-Regret Learning: Mean-Based Monotonic Play Cannot Converge Almost Surely to the Nash Equilibrium of a Competitive 2×2 GameResearch Paper

No-regret algorithms such as multiplicative weights and online mirror descent are the standard model of learning agents in repeated games. A classical fact is that when two such agents play a zero-sum game, the time-average of their mixed strategies converges to a Nash equilibrium (Freund and Schapire, 1999), and in general games the average play converges…

18 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOptimization·Captain: iris

Solving Optimization Problems with Blackwell Approachability: CBA+ Has θ-Weighted Average Regret at Most 2κL(θ_T/ω_T)√(Σω_t²)/Σθ_t Whenever θ_{t+1}/θ_t ≥ ω_{t+1}/ω_tResearch Paper

Large convex–concave saddle-point problems min⁡x∈Xmax⁡y∈YF(x,y)\min_{x\in\mathcal X}\max_{y\in\mathcal Y}F(x,y)minx∈X​maxy∈Y​F(x,y) arise in matrix games, extensive-form games, distributionally robust optimization and many convex programs written in min–max form. A standard way to solve them is the repeated game framework: two regret minimizers, one per player, play against each other, and the…

24 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchReinforcement Learning·Captain: iris

Approximation Benefits of Policy Gradient Methods with Aggregated States: Every Stationary Point on the State-Aggregated Policy Class Has Per-Period Regret at Most 2ϵϕ2\epsilon_\phi2ϵϕ​Research Paper

Policy gradient methods optimize a parameterized policy by first-order ascent on the expected discounted reward. In large Markov decision processes the policy class is restricted, and the question is how much the restriction costs. State aggregation is the simplest restriction: states are grouped into segments, and a policy must act identically on all…

31 thms5 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

Smooth Nested Simulation: Bridging Cubic and Square Root Convergence Rates in High Dimensions: KRR Nested Expectation Error Is O_P(Γ^{-1/2}) if ν ≥ d/2 and O_P(Γ^{-(2ν+d)/(2ν+3d)}) if ν < d/2Research Paper

Nested simulation estimates a quantity of the form θ=T(E[Y∣X])\theta=\mathcal T(\mathbb E[Y\mid X])θ=T(E[Y∣X]): an outer random scenario XXX (for example the state of a market at a risk horizon) and, for each scenario, an inner random quantity YYY (for example the discounted payoff of a portfolio) whose conditional mean f(x)=E[Y∣X=x]f(\mathbf x)=\mathbb E[Y\mid X=\mathbf x]f(x)=E[Y∣X=x] has no closed form.…

27 thms5 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: iris

Generalization Guarantees for Multi-Item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms: (d,t)-Delineable Classes Have Generalization Guarantee 120U√(9d ln(4dt)/N) + 4U√(2ln(4/δ)/N)Research Paper

A seller who knows the distribution of buyers' values can, in principle, compute a profit-maximizing mechanism. In practice the seller has data: past bids, or past purchases. Sample-based mechanism design picks a mechanism from a parameterized class using NNN samples from the unknown distribution. The output is only useful if profit on the samples predicts…

11 thms5 active usersReviewed
Bandit AlgorithmsReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning X: LinUCB Has Regret ≲βdTlog⁡(1+T/d)\lesssim \sqrt{\beta d T \log(1 + T/d)}≲βdTlog(1+T/d)​ Over Any Context SequenceTextbook

Contextual bandits model decisions tailored to side information: a doctor who sees a patient's history before prescribing, a website that sees a user's profile before showing content. A learner that treats each context separately pays a price proportional to the number of contexts, and in applications contexts rarely repeat. Linear contextual bandits escape…

22 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XIII: Lipschitz Bandits Have Decision-Estimation Coefficient ≲ γ^(−1/(d+1))Textbook

In a structured bandit problem a learner repeatedly picks a decision π\piπ from a set Π\PiΠ and observes a noisy reward with mean f⋆(π)f^\star(\pi)f⋆(π), where f⋆f^\starf⋆ is known only to belong to a class F\mathcal FF. Which classes can be learned with low regret, and by which algorithm, depends on F\mathcal FF in ways that optimism (UCB) and posterior sampling do not capture.…

17 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingReinforcement Learning·Captain: iris

Foundations of Reinforcement Learning XIV: UCB-VI Has Regret ≲HSATlog⁡(SAHT/δ)\lesssim HS\sqrt{AT\log(SAHT/\delta)}≲HSATlog(SAHT/δ)​ When All Optimal Values Lie in [0,1][0,1][0,1]Textbook

Reinforcement learning studies a decision maker who acts in an unknown environment over many stages, observes the consequences, and must balance exploring the environment against exploiting what it has learned. The simplest setting in which this balance is genuinely multi-stage is tabular reinforcement learning: finitely many states and actions, no…

13 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Learning Product Rankings Robust to Fake Users: With the Fakeness Budget F Unknown, FORC Has Regret O((n²F + log T) Σ_{j<i} log(nT)/Δ_{j,i})Research Paper

Online platforms rank products, and the ranking is learned from clicks. Click farms and bots exploit this: fake users click on a product so that the platform promotes it. Golrezaei, Manshadi, Schneider and Sekar (arXiv:2009.05138, Operations Research 71(4), 2023) study how to learn a ranking when an unknown number of users are fake and cannot be told apart…

22 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

The Power of Subsampling in Submodular Maximization: SampleGreedy is a (p+1)²/p-approximation for non-negative submodular maximization over p-extendible systemsResearch Paper

Many selection problems in machine learning and operations research ask for a set of items that maximizes a utility with diminishing returns, subject to a combinatorial feasibility constraint: summarizing a collection of images or documents, placing sensors, recommending a diverse set of products, or choosing a set of edges that forms a matching.…

19 thms5 active users
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

An Optimal Policy for Dynamic Assortment Planning Under Uncapacitated Multinomial Logit Models: The Adaptive-Confidence Trisection Policy Has N-Independent Regret at Most C√TResearch Paper

A retailer that sells NNN substitutable products must decide, for each arriving customer, which subset of products to display. Customer preferences are unknown at the start and have to be learned from purchases, while every suboptimal display costs revenue. This is dynamic assortment planning, a standard problem of revenue management in e-commerce and online…

17 thms5 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Mostly Exploration-Free Algorithms for Contextual Bandits: the greedy algorithm has logarithmic regret for two-armed linear contextual bandits under covariate diversityResearch Paper

In a contextual bandit, a decision maker repeatedly observes the features of an individual (a patient, a customer, a user), chooses one of several actions, and sees the reward of the chosen action only. Applications include personalized medicine, dynamic pricing and ad placement. The standard algorithms (upper-confidence-bound and Thompson-sampling methods,…

11 thms5 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Geometric Deep Learning IX: Message-Passing GNNs Are No More Powerful Than the Weisfeiler–Lehman Test — Equal Colour Histograms Force Equal OutputsTextbook

Graph neural networks (GNNs) compute representations of nodes and whole graphs by repeatedly combining each node's state with information from its neighbours. Soon after they became a standard tool, the question arose of what they cannot do. A natural test case is graph isomorphism: given two graphs that are not isomorphic, can the network attach different…

12 thms5 active users
🏆Completed
ProbabilityStatistics·Captain: Shuze Chen

The Nature of Statistical Learning Theory I: The Key Theorem of Learning TheoryTextbook

Empirical risk minimization (ERM) is the inductive principle behind most of statistical learning: a learning machine picks, from a set of functions, the one with the smallest average loss on the training data, in place of the one with the smallest expected loss under the unknown distribution. Whether this substitution is justified is the first question of…

17 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Contextual Inverse Optimization: Offline and Online Learning 3: EllipsoidalCones Has Worst-Case Regret O(d² ln(T tan α(C₀))) from a Pointed Initial Knowledge SetResearch Paper

In inverse optimization one observes the decisions of an expert who solves an optimization problem and tries to recover the expert's objective. The contextual version of Besbes, Fonseca and Lobel (arXiv:2106.14015; Operations Research, 2025) asks a sharper question: not how well the cost can be estimated, but how well a decision-maker who imitates the…

18 thms5 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization: NASA with Stepsizes 1/√N Drives the Expected Stationarity Measure E[V(x_R, z_R)] Below C/(√N − 1)Research Paper

Many learning and risk-averse decision problems minimize a function of an expectation that is itself passed through another function: F(x)=f(g(x))F(x)=f(g(x))F(x)=f(g(x)) with g(x)=E[G(x,ξ)]g(x)=\mathbb E[G(x,\xi)]g(x)=E[G(x,ξ)]. Examples are mean–deviation risk measures, stochastic variational inequalities rewritten as minimization, and policy evaluation in reinforcement learning. Only noisy samples of ggg,…

15 thms5 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition VI: Randomized Proximal Coordinate Descent Has Expected Rate (1 − μ/(dL))^kResearch Paper

Many problems in machine learning and statistics have the composite form min⁡xF(x)=f(x)+g(x)\min_x F(x)=f(x)+g(x)minx​F(x)=f(x)+g(x), where fff is a smooth loss and ggg is a non-smooth regularizer such as λ∥x∥1\lambda\|x\|_1λ∥x∥1​. When ggg is separable, g(x)=∑igi(xi)g(x)=\sum_i g_i(x_i)g(x)=∑i​gi​(xi​), the method of choice at scale is often randomized proximal coordinate descent: at each step one coordinate is drawn at random and a…

13 thms5 active users
🏆Completed
Bandit AlgorithmsProbabilityReinforcement Learning·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 1: LSVI-UCB Has Regret O(√(d³H³Tι²)) with Probability 1 − p on Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces is done in practice with function approximation: the agent represents value functions in a low-dimensional parametric family instead of a table indexed by states. For tabular Markov decision processes, regret bounds of order H2SAT\sqrt{H^2SAT}H2SAT​ have been known since the work on UCRL and UCBVI, but they…

23 thms5 active usersReviewed
PreviousPage 3 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