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
Information TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Lower Bounds for Memorization, Privacy and Replicability from Not-So-Strong Data Processing InequalitiesResearch Paper

Top-kkk selection asks an algorithm to look at nnn data records and name kkk of mmm candidate coordinates whose means are nearly the largest. It is a basic subroutine of private and reproducible data analysis: choosing features, hypotheses, or queries before answering them. Two stability requirements are central for it. Differential privacy (Dwork, McSherry,…

25 thms4 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Intractability of Continual Learning using Parametric Models with Unlimited Replay BufferResearch Paper

In continual learning a model is trained on a stream of tasks t=1,…,Tt = 1, \dots, Tt=1,…,T and must keep performing well on every task seen so far; losing accuracy on earlier tasks is called catastrophic forgetting. A common remedy is a replay buffer that stores past data. With an unlimited buffer every earlier dataset remains available, so forgetting can no longer be…

18 thms4 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Robust Mean Estimation Under Strong Double Corruption: Near-Linear Time and Sub-Gaussian RateResearch Paper

Data for a statistical task often arrive in batches from many sources: phones in federated learning, sensors in a network, contributors to a pooled dataset. Some sources are entirely unreliable, and even reliable sources contain a few bad points. Aliakbarpour, Liu and Yin study the most basic task in this setting, estimating the mean of a high-dimensional…

27 thms4 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: Shuze Chen

Provably Distilling from Modern Language Models via Low Logit RankResearch Paper

Modern language models compute, at every position, a vector of logits and sample the next token from its softmax. Commercial interfaces often expose these logits: a user submits a prefix and receives the next-token logit vector. Distillation asks how much query access of this kind is needed to build a small model that samples almost the same distribution as…

20 thms4 active usersReviewed
Algorithmic Game TheoryComputational Complexity·Captain: iris

On the Complexity of Infinite Zero-Sum GamesResearch Paper

Zero-sum games whose players choose among infinitely many strategies arise when the strategies are learning machines: each player may train any model, and the natural way to access such a game is through best responses, computed by training against a mixture of the opponent's models (empirical risk minimization), as in the double-oracle method of McMahan,…

46 thms4 active usersReviewed
🏆Completed
Captain: mikedeng1

Two ReLU layers is all you needResearch Paper

The architecture of a neural network limits which functions it can compute. For a rectified linear unit, or ReLU, the scalar activation is t↦max⁡(0,t)t\mapsto\max(0,t)t↦max(0,t). A question about exact expressivity asks whether additional hidden layers permit new functions when each layer may have arbitrary finite width. This question differs from approximation on a compact…

35 thms4 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's AlgorithmResearch Paper

An unknown Boolean formula can be observed through examples that satisfy it. The question here is how many such examples suffice to describe approximately the same distribution of solutions. This matters in learning structured distributions: the requested hypothesis is an explicit formula whose uniformly sampled solutions resemble the observations'…

29 thms4 active usersReviewed
Probability·Captain: mikedeng1

Nearly Linear Private Learning of Littlestone ClassesResearch Paper

Learning from personal records raises two distinct requirements: predictions should remain accurate on new records, and changing one person's contribution should have limited effect on the released predictor. Private PAC learning combines these requirements. Its sample complexity measures how many independent labeled examples suffice, without requiring the…

37 thms4 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Pure Differentially Private Query Release via Laplace Input SmoothingResearch Paper

Statistical query release asks a curator holding a database of NNN records to publish answers to kkk public counting queries while protecting every individual record. Differential privacy (Dwork, McSherry, Nissim, Smith 2006) is the standard formal guarantee, and its pure form, with no additive slack δ\deltaδ, is the strongest and the easiest to compose. The…

23 thms4 active usersReviewed
Probability·Captain: iris

Private Online Learning of Littlestone Classes and Matroid FlatsResearch Paper

In online classification a learner releases a classifier gt:X→{0,1}g_t : X \to \{0,1\}gt​:X→{0,1} at every round, then sees a labeled example (xt,yt)(x_t, y_t)(xt​,yt​) and errs if gt(xt)≠ytg_t(x_t) \neq y_tgt​(xt​)=yt​. Without privacy, a class of Littlestone dimension ddd can be learned with at most ddd mistakes on every realizable sequence (Littlestone, 1988), and Littlestone dimension characterizes online…

89 thms4 active usersReviewed
StatisticsTheoretical Computer Science·Captain: iris

Efficient Robust Learning at the Information-Theoretic LimitResearch Paper

In bounded contamination, the model of Bshouty, Eiron and Kushilevitz (Theoretical Computer Science 2002), an adversary may replace an η\etaη-fraction of a training set arbitrarily, in features and labels alike. Running empirical risk minimization on the corrupted data gives error 2η+ε2\eta+\varepsilon2η+ε, and no deterministic hypothesis does better. Whether a…

44 thms4 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private FilteringResearch Paper

A differentially private release adds noise calibrated to how much one record can move the output. Worst-case (global) sensitivity is often far larger than the influence of a record in typical data: a single outlier can force noise that is out of proportion to every other record. Several lines of work scale noise to the data instead, including smooth…

31 thms4 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Gaussian Partitioning for Reliable Learning of Multi-Index ModelsResearch Paper

Many learning algorithms for Boolean functions on Rd\mathbb R^dRd rest on properties of the standard Gaussian: low-degree polynomial approximation, moment bounds, Hermite analysis. In several settings the examples a learner sees are not Gaussian even when the original input distribution is. Boosting reweights the examples during its run; a learner given only…

47 thms4 active usersReviewed
Bandit AlgorithmsProbabilityReinforcement Learning·Captain: iris

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPsResearch Paper

An episodic adversarial Markov decision process (AMDP) models a learner who repeats an HHH-step task for KKK episodes while an adversary fixes the loss function of every episode in advance. The learner sees only the losses of the state-action pairs it visits (bandit feedback), and it does not know the transition law. The standard measure of performance is the re…

82 thms4 active usersReviewed
Algorithmic Game TheoryOptimization·Captain: iris

Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial OpponentsResearch Paper

Two players repeatedly playing a zero-sum game with no-regret learning algorithms approach a Nash equilibrium: a social regret of RTR_TRT​ makes the averaged strategies an (RT/T)(R_T/T)(RT​/T)-approximate equilibrium (Freund–Schapire 1999). Standard algorithms have regret O(T)O(\sqrt T)O(T​), but optimistic algorithms, which predict the next gradient, reach constant regret, and hence…

53 thms4 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-WiseResearch Paper

A seller with an unlimited supply of one product meets TTT customers in sequence. Each customer's value is drawn independently from a distribution FFF on [0,1][0,1][0,1] that the seller does not know, and the seller wants to earn, over the TTT rounds, nearly as much as the monopoly price pF∗p^*_FpF∗​ would earn if FFF were known. This dynamic pricing problem is a basic model of…

37 thms4 active usersReviewed
🏆Completed
Bandit Algorithms·Captain: iris

Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and GeometryResearch Paper

In a linear bandit a learner repeatedly picks an action AtA_tAt​ from a known set A⊂Rd\mathcal A\subset\mathbb R^dA⊂Rd and observes only a noisy scalar loss YtY_tYt​ with mean At⊤θtA_t^\top\theta_tAt⊤​θt​. Linear bandits model sequential decisions with structured feedback: routing, recommendation, pricing, and experimental design. Two benchmarks are classical. Against an adversarial envi…

68 thms4 active usersReviewed
Algorithmic Game TheoryInformation TheoryMechanism Design·Captain: iris

Query-Sample Tradeoffs for Revenue MaximizationResearch Paper

A seller posting a price for a single item to a buyer with an unknown value distribution FFF wants a price whose revenue is close to optimal. Two kinds of data are available. A value sample reveals a buyer's value v∼Fv\sim Fv∼F exactly, as in historical bid data or surveys. A pricing query posts a price ppp and reveals only whether a fresh buyer buys, the bit …

36 thms4 active usersReviewed
OptimizationProbability·Captain: iris

Memory-efficient Finite-sum Optimization without Full Gradient RefreshesResearch Paper

Training a model by empirical risk minimization means minimizing an average f(x)=1n∑i=1nfi(x)f(x)=\frac1n\sum_{i=1}^n f_i(x)f(x)=n1​∑i=1n​fi​(x) of nnn component losses over x∈Rdx\in\mathbb R^dx∈Rd, where nnn is the number of data points and is often very large. A full gradient ∇f\nabla f∇f costs nnn component-gradient queries; a stochastic gradient costs one query but its noise prevents convergence with a…

21 thms4 active usersReviewed
Convex OptimizationOptimization·Captain: iris

On the Relation Between Interval Regret and Dynamic RegretResearch Paper

Online convex optimization measures a learner against a benchmark chosen in hindsight. When the environment drifts, a single fixed benchmark says little, and two stronger measures have been studied. Interval regret (Daniely, Gonen and Shalev-Shwartz 2015) asks for small static regret simultaneously on every time interval. Dynamic regret (Zinkevich 2003; Zhan…

46 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

No-Regret Revenue Maximization in Sequential Market Making Under Inventory ConstraintsResearch Paper

A market maker quotes two prices for an asset: a bid, at which it buys, and an ask, at which it sells. It earns the spread when both sides trade, and it carries inventory risk when they do not balance: a maker that buys much more than it sells is exposed to the price of the asset itself, which defeats the purpose of quoting. Classical market-making models…

29 thms4 active usersReviewed
Optimization·Captain: iris

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

In many allocation problems adding resources helps less as the allocation grows, and eventually hurts: more active wireless transmitters create interference, oversupplying a saturated component wastes budget, and spreading probability mass over competing actions can lower the expected reward (Aggarwal and Lu, arXiv:2610.00545, p.3). A differentiable…

40 thms4 active usersReviewed
Algorithmic Game TheoryProbability·Captain: iris

Non-manipulability and Approachability Beyond Two-Player GamesResearch Paper

Online learning algorithms are routinely deployed against a single strategic party that sees how they behave: buyers bidding through autobidders on an ad platform, sellers pricing against a marketplace's matching rule, agents trained by self-play. The learners are usually asked for a worst-case guarantee, no regret, which protects each of them whatever the…

15 thms4 active usersReviewed
Quantum Information·Captain: iris

Learning quantum many-body systems from a few copies: Gibbs states with a transportation cost inequality are learned to ε√n‖O‖_Lip from O(4^k α⁻¹ε⁻²β log(m/δ) min{mβ/(Ln), m²/(αn²ε²)}) copiesResearch Paper

Thermal states of local Hamiltonians are the basic objects of quantum many-body physics, and estimating such a state from experimental data is the problem of Gibbs state learning (also called Hamiltonian learning from thermal states). It matters for the certification of quantum simulators and for characterizing quantum devices. A generic state of nnn qubits…

18 thms4 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: iris

Optimal Policies for Dynamic Pricing and Inventory Control with Nonparametric Censored Demands: Trisection Search with a Difference Estimator Has √T·ln²T Regret for Strongly Concave RewardsResearch Paper

A retailer that sets both a price and a stock level each period, without knowing how demand responds to price or how demand fluctuates, has to learn while selling. In the lost-sales setting the learning problem is harder than in pure pricing: when a period ends with empty shelves, the firm sees only its sales, not the demand that went unmet. Joint pricing…

13 thms4 active usersReviewed
PreviousPage 6 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