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
Bandit AlgorithmsOperations Research·Captain: Shuze Chen

Bandit Algorithms IX: Self-Normalized Concentration and Optimal DesignTextbook

Least-squares estimation from adaptively collected data is the statistical heart of linear bandits: the actions AtA_tAt​ depend on past noise, so classical fixed-design theory does not apply. Chapter 20 of Lattimore–Szepesvári resolves this with the method of mixtures: the process Mt(x)=exp⁡(⟨x,St⟩−12∥x∥Vt(λ)2)M_t(x) = \exp(\langle x, S_t\rangle - \frac{1}{2}\|x\|^2_{V_t(\lambda)})Mt​(x)=exp(⟨x,St​⟩−21​∥x∥Vt​(λ)2​) is a…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper

In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…

11 thms3 active usersReviewed
🏆Completed
Probability·Captain: Shuze Chen

Sample Complexity of Multiclass OmnipredictionResearch Paper

Omniprediction, introduced by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389), asks for one predictor that serves every downstream decision maker at once. Each decision maker has their own loss, best-responds to the predicted label distribution, and should do as well as the best benchmark in a fixed class FFF. For binary labels, randomized…

15 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Is Randomness Necessary for Adaptive Data Analysis?Research Paper

A dataset is often reused to answer questions chosen after seeing earlier answers. Each answer can influence the next question, so the usual guarantee for one question fixed in advance does not automatically extend to the resulting interaction. Adaptive data analysis asks what a mechanism can reliably reveal about a population from a single finite sample in…

14 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Ramsey Obstructions to DisambiguationResearch Paper

A partial binary classifier may leave a point unlabeled. For a separating hyperplane with a prescribed margin, this represents points too close to the boundary to receive a prescribed label. A class of such classifiers can have bounded VC-dimension, even when the ambient Euclidean dimension grows. Completing all missing labels asks whether this simplicity…

30 thms3 active usersReviewed
🏆Completed
Group TheoryRepresentation Theory·Captain: iris

The State Complexity of Block-Diagonal State Space ModelsResearch Paper

Given a sequence x1,…,xTx_1,\dots,x_Tx1​,…,xT​ of elements of a fixed finite group GGG, a state-tracking model must report the running product xT⋯x1x_T\cdots x_1xT​⋯x1​ after every prefix. The task tests structured memory: the model has to preserve order, retain information for arbitrary sequence lengths, and implement the multiplication law. It also has complexity-theoretic content,…

26 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: iris

On the VC Dimension of Autoregressive Linear Threshold FunctionsResearch Paper

An autoregressive model applies one fixed next-token rule to the current sequence, appends the produced token, and repeats. Intermediate tokens act as computation steps, which is one explanation of why chain-of-thought generation increases the power of language models. Joshi et al. introduced a learning framework for this process: a fixed generator runs for …

22 thms3 active usersReviewed
🏆Completed
Statistics·Captain: iris

Omniprediction for All Mixable Proper Losses and BeyondResearch Paper

A forecaster that outputs probabilities is usually trained against one loss function, yet its forecasts are often consumed by several downstream decision makers, each with its own loss, some of them unknown at training time. Omniprediction, introduced in the batch setting by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389) and in the online…

49 thms3 active usersReviewed
🏆Completed
Linear algebraStatistics·Captain: mikedeng1

SYN-DIGITS: A Synthetic Control Framework for Calibrated Digital Twin Simulation: Error Bound for Ridge Fit-and-Transfer on a New QuestionResearch Paper

Large language models are increasingly used as digital twins of survey respondents: a model is prompted with a persona and asked to answer the same questionnaire a human would. The appeal is cost and speed, since a new question can be "fielded" to thousands of simulated respondents in minutes. The obstacle is fidelity. Large language models exhibit…

8 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability+1·Captain: mikedeng1

The Fragility of Optimized Bandit Algorithms: Optimized Bandit Algorithms Have Truncated Cauchy Regret TailsResearch Paper

The stochastic multi-armed bandit is the basic model of sequential decision-making under uncertainty: in each round an algorithm chooses one of KKK arms, observes a random reward from that arm's distribution, and tries to play the best arm as often as possible. Since Lai and Robbins (1985) the standard of quality has been the expected regret, and an algorithm…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Stochastic Optimization Forests: the approximate risk criterion consistently approximates the oracle splitting criterion as the region to split shrinksResearch Paper

In contextual stochastic optimization a decision z∈Rdz\in\mathbb R^dz∈Rd is chosen after observing features X∈RpX\in\mathbb R^pX∈Rp, and the ideal policy solves, for each feature value,

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

Contextual Bandits with Cross-Learning: UCB1.CL Has Expected Regret O(Kκ̄ log T/Δ*) and O(√(κ̄KT log T)) with Stochastic Rewards and Adversarial ContextsResearch Paper

In a contextual bandit a learner plays TTT rounds; in round ttt it observes a context ctc_tct​, pulls one of KKK arms and receives the reward of that arm in that context. In many applications the learner also learns what the pulled arm would have paid in other contexts. The motivating example of Balseiro, Golrezaei, Mahdian, Mirrokni and Schneider (arXiv:1809.09582)…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributed Stochastic Optimization with Large Delays: Under Polynomially Growing Delays, Asynchronous SGD with Tuned Step-Sizes Drives the Mean-Square Gradient Norm to ZeroResearch Paper

Large-scale learning problems, such as empirical risk minimization over millions of samples, are solved in practice by stochastic gradient descent (SGD) run on many processors at once. In a master–worker system, or in a multi-processor system with shared memory, a worker reads the current parameter, computes a stochastic gradient and writes its update back.…

13 thms3 active usersReviewed
🏆Completed
Dynamical Systems·Captain: mikedeng1

Geometric Deep Learning VIII: An RNN Seeded at a Fixed Point h⁽⁰⁾ = R(0, h⁽⁰⁾) Is Equivariant to Left Shifts of a Zero-Padded Input SequenceTextbook

A recurrent neural network (RNN) processes an ordered stream while retaining a summary of earlier inputs. The same update rule is applied at every time step, so it is natural to ask whether shifting the input stream simply shifts the resulting sequence of summaries. The answer depends on how the run begins. The first summary is supplied as an initial state,…

5 thms3 active usersReviewed
🏆Completed
Harmonic AnalysisLinear algebra·Captain: mikedeng1

Geometric Deep Learning III: An n × n Matrix Commutes with the Cyclic Shift S if and only if It Is Circulant, So Convolution Is Shift EquivarianceTextbook

Convolutional neural networks process images, audio and time series with layers whose weights are shared across positions. The Geometric Deep Learning programme of Bronstein, Bruna, Cohen and Veličković (arXiv:2104.13478v2) explains this architecture by symmetry: on a grid the relevant symmetry is translation, and a linear layer that respects translations…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Accelerated MM Algorithms for Ranking Scores Inference from Comparison Data: Rescaled MM for Bradley–Terry MAP Estimation Contracts the Log-Posterior Gap at a Rate Set by Algebraic ConnectivityResearch Paper

Paired-comparison data (which of two items a user clicked, which of two players won a game, which of two products a respondent preferred) are summarised by ranking scores, one real number per item. The Bradley–Terry model (Bradley and Terry, 1952) is the standard statistical model for such scores, and its parameters are estimated by maximum likelihood or by…

14 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach: The Optimal Accuracy-Length Tradeoff Solves the Questions of Smallest Token Complexity FirstResearch Paper

Large language models answer reasoning questions better when they are allowed to write out a chain of thought (CoT) before the final answer, but every generated token costs time and money. A large body of recent work therefore asks models to "think less": prompts such as "be concise" or "use at most 10 words", and training methods that shorten the reasoning…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms: The Optimal Central-Privacy Mechanism Sets Privacy Losses to the Minimizer of a Virtual-Cost ProgramResearch Paper

Platforms that estimate a population quantity from individual data, such as a health service estimating the mean response to a treatment, must compensate users for the privacy they give up. Users differ in how much they value privacy, and that value is private information. Differential privacy (Dwork, McSherry, Nissim, Smith, 2006) supplies a quantitative…

11 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchReinforcement Learning·Captain: mikedeng1

A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation: Projected TD(0) Under Markov Chain Sampling Converges at Mixing-Time-Scaled RatesResearch Paper

Temporal-difference (TD) learning is the basic algorithm of reinforcement learning for estimating the value function of a fixed policy from a single stream of experience. With a linear function approximation Vθ(s)=ϕ(s)⊤θV_\theta(s)=\phi(s)^\top\thetaVθ​(s)=ϕ(s)⊤θ, TD(0) is the evaluation step inside many policy-iteration and actor–critic methods, and its behaviour governs how much…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Private Sequential Learning: The Query Complexity of an (ϵ, δ, L)-Private Learner Lies Between max{log(1/ϵ), log(δ/ϵ) + 2L − 4} and log(1/(Lϵ)) + 2LResearch Paper

A learner wants to locate an unknown number, the true value v∗∈[0,1)v^* \in [0,1)v∗∈[0,1), by asking threshold questions of a database: each query qqq is answered by the single bit I(v∗≥q)\mathbb I(v^* \ge q)I(v∗≥q). Bisection finds v∗v^*v∗ to within ϵ/2\epsilon/2ϵ/2 with ⌈log⁡2(1/ϵ)⌉\lceil \log_2(1/\epsilon) \rceil⌈log2​(1/ϵ)⌉ queries, and no strategy does better (Waeber, Frazier and Henderson, 2013). Bisection, however,…

15 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Optimal Decision Making Under Strategic Behavior 2: A Three-Value Instance with Outcome Monotonic Costs Whose Optimal Policies Are All StochasticResearch Paper

Many consequential decisions, such as lending, hiring or admissions, are made by policies that map an individual's features to a probability of a positive decision. When the policy is published, individuals respond to it: they change their features, at a cost, to raise their chance of a positive decision. Tsirtsis, Tabibian, Khajehnejad, Singla, Schölkopf…

7 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchReinforcement Learning·Captain: mikedeng1

Nonstationary Reinforcement Learning: The Blessing of (More) Optimism II: Per-Step Dynamic Regret of SWUCRL2-CW When the Widened Confidence Region Contains an MDP of Diameter at Most DResearch Paper

A reinforcement-learning agent chooses actions while learning how those actions affect future states. In a stationary model, observations collected long ago remain relevant to the current transition law. In a nonstationary Markov decision process, rewards and transition probabilities may change at each round. Old observations can then bias an estimate even…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low IV: ℓ1-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper

Best subset selection fits a linear predictor using at most kkk of ppp available columns. Its explicit limit on the number of selected variables makes the model easy to interpret, but the search can still fit noise: among many subsets of the same size, one can align unusually well with a noisy response. Mazumder, Radchenko and Dedieu study this effect in Subset…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low III: ℓ2-Regularized Best Subset Selection Satisfies Slow-Rate and Fast-Rate Oracle InequalitiesResearch Paper

Best subset selection fits a linear model using at most kkk of ppp available predictors, choosing the kkk that minimize the residual sum of squares. Mixed-integer optimization made it computable at moderate scale (Bertsimas, King & Mazumder, 2016), which reopened the statistical question of when it should be used. Empirical comparisons (Hastie, Tibshirani &…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Offline Multi-Action Policy Learning: Generalization and Optimization 2: Depth-L Decision Trees Satisfy log N_H(ε,Π_L) ≤ (2^L−1)log p + 2^L log d + (2^L−1)log(L/ε+1)Research Paper

Offline policy learning chooses a treatment rule from logged data: given nnn observations of features XiX_iXi​, the action AiA_iAi​ taken and the reward obtained, pick a policy π:X→{1,…,d}\pi:\mathcal X\to\{1,\dots,d\}π:X→{1,…,d} from a class Π\PiΠ whose expected reward is close to the best in the class. Zhou, Athey and Wager (arXiv:1810.04778v2) bound the regret of their cross-fitted…

6 thms3 active usersReviewed
PreviousPage 9 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