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
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low V: When the SNR Is Low, Best Subset Selection Has Prediction Error at Least of Order σ²γ²k log(ep/k)Research Paper

Best subset selection fits a linear model by least squares using at most kkk of ppp available predictors. It is the classical ℓ0\ell_0ℓ0​-constrained estimator of sparse regression. Mixed-integer optimization now computes it for problems with thousands of variables (Bertsimas, King & Mazumder 2016), so its statistical behaviour matters in practice. Simulations in Has…

8 thms2 active usersReviewed
Reinforcement LearningStatistics·Captain: mikedeng1

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model 3: Plug-In Policy Evaluation Is ε-Accurate w.p. 1−δ Once N ≥ c₀log(|S|log(e/(1−γ))/δ)/((1−γ)³ε²)Research Paper

Policy evaluation asks for the value of a fixed decision rule in a Markov decision process whose transition probabilities are unknown. It is the inner loop of policy iteration, the subroutine behind actor-critic methods, and the question an operator faces before deploying a policy in an inventory, queueing or routing system that can only be simulated. The…

17 thms2 active usersReviewed
Reinforcement LearningStatistics·Captain: mikedeng1

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model 1: The Perturbed Model-Based Planner Is ε-Optimal w.p. 1−δ Once N ≥ c₀log(|S||A|/((1−γ)εδ))/((1−γ)³ε²)Research Paper

A generative model lets a planner request independent next-state samples for any state-action pair. This is a useful idealization for studying how many simulator calls are needed before a policy computed from an estimated model performs well in the true environment. Li, Wei, Chi, and Chen show that a small independent perturbation of the rewards lets a…

15 thms2 active usersReviewed
Reinforcement LearningStatistics·Captain: mikedeng1

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model 4: Finite-Horizon Model-Based Planning Is ε-Optimal w.p. 1−δ Once N ≥ c₀H³log(H|S||A|/δ)/ε²Research Paper

Reinforcement learning with a generative model (a simulator) is a basic way to measure how many samples planning needs. A learner may query, for any state sss, action aaa and step hhh, a fresh next state drawn from the unknown transition law Ph(⋅∣s,a)P_h(\cdot\mid s,a)Ph​(⋅∣s,a), and must output a near-optimal policy. Model-based planning is the simplest approach: estimate each…

10 thms2 active usersReviewed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

Optimal No-regret Learning in Repeated First-price Auctions 4: Arm Elimination with Graph Feedback and Cross Learning Has Regret Õ(T ∧ √(αMT) ∧ √(KT)) with High ProbabilityResearch Paper

In many sequential decision problems, playing one action reveals the outcome of other actions too. A bidder in a first-price auction who bids bbb and sees the winning price learns whether every bid at or above that price would have won. A recommender that shows one item learns something about related items. Two kinds of side information recur. Graph feedback a…

8 thms2 active usersReviewed
Bandit AlgorithmsHarmonic AnalysisOperations Research+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 1: Regret Upper Bound for the Two-Stage Period-Estimation and Confidence-Bound PolicyResearch Paper

Many demand, traffic and click-through series are seasonal: their mean repeats after a fixed number of periods (a week of days, a year of months), while the length of that cycle is not known in advance. A retailer choosing among KKK promotions, or a platform choosing among KKK recommendations, then faces a multi-armed bandit whose arms have time-varying but…

17 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data: The G-MCP-Bandit Algorithm Has Expected Cumulative Regret at Most Rmax(T0 + |K|) + C log(T + 1)Research Paper

Personalized decisions — which drug to prescribe, which product to recommend, which price to quote — are made one user at a time, from user features observed on arrival, and the effect of each decision is learned only from the users it was applied to. This is the contextual (covariate) bandit. In electronic records and online platforms the feature vector is…

10 thms2 active usersReviewed
Bandit AlgorithmsProbabilityReinforcement Learning·Captain: mikedeng1

(More) Efficient Reinforcement Learning via Posterior Sampling: PSRL Has Bayesian Regret O(τS√(AT log(SAT))) in Episodic Finite MDPsResearch Paper

An agent that interacts repeatedly with an unknown Markov decision process must trade exploration against exploitation. The dominant design principle for provably efficient reinforcement learning has been optimism in the face of uncertainty: UCRL2 (Jaksch, Ortner & Auer, 2010) and REGAL (Bartlett & Tewari, 2009) build confidence sets around the unknown…

14 thms2 active usersReviewed
Bandit AlgorithmsProbabilityStatistics·Captain: mikedeng1

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability: FALCON+ Has Regret ≤ 14.3·Σₘ√(K𝓔(τₘ₋₁−τₘ₋₂))(τₘ−τₘ₋₁) + τ₁ + √(8T log(2/δ)) w.p. 1−δResearch Paper

A contextual bandit is a sequential decision problem: in each round a learner sees a context (a user's features, a patient's covariates), picks one of KKK actions, and observes the reward of that action only. Applications include recommendation, dynamic pricing and adaptive clinical decisions. The difficulty is statistical and computational at once: the…

14 thms2 active usersReviewed
OptimizationProbabilityReinforcement Learning·Captain: mikedeng1

Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies: Random-Horizon Policy Gradient with Robbins–Monro Stepsizes Drives the Policy Gradient to Zero Almost SurelyResearch Paper

Policy gradient methods are the main family of reinforcement learning algorithms that search directly over a parameterized class of stochastic policies πθ\pi_\thetaπθ​, θ∈Rd\theta\in\mathbb R^dθ∈Rd, by stochastic gradient ascent on the expected discounted return. They underlie REINFORCE, actor-critic methods and their deep-learning descendants. The return is a nonconvex…

17 thms2 active usersReviewed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Distributed Stochastic Gradient Tracking Methods I: With a Constant Stepsize, DSGT's Limiting Mean-Square Error Is at Most (Γ+1)ασ²/(Γμn) Plus a Network TermResearch Paper

Many learning and estimation problems are solved by a network of agents: each agent holds part of the data, can talk only to its neighbours, and wants to compute the minimizer of the average of all agents' objectives. Examples are sensor networks, multi-robot systems, and data-parallel training without a central server (Nedić and Ozdaglar 2009; Lian et al.…

18 thms2 active usersReviewed
Complexity TheoryConvex OptimizationOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives II: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(m√(γB²/ε)) Queries on Sums of m Convex γ-Smooth FunctionsResearch Paper

Many problems in machine learning and statistics minimize an average of mmm convex losses, one per data point or per block of data. Incremental methods such as SAG, SVRG, SAGA, SDCA, Finito and Katyusha exploit this finite-sum structure: each step touches one component fif_ifi​ instead of the whole average, and for smooth components the best of them reach accuracy …

12 thms2 active usersReviewed
OptimizationProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 2: Perturbed GD (Variant) Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f/ε²) IterationsResearch Paper

Training a model in machine learning usually means minimizing a nonconvex function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R with first-order methods. Finding a global minimum of a general nonconvex function is NP-hard, so the classical guarantee for gradient descent (GD), xt+1=xt−η∇f(xt)x_{t+1}=x_t-\eta\nabla f(x_t)xt+1​=xt​−η∇f(xt​), is weaker: with step size η=1/ℓ\eta=1/\ellη=1/ℓ it reaches a point with …

9 thms2 active usersReviewed
OptimizationProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 1: Perturbed SGD Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f·𝔑/ε²) IterationsResearch Paper

Most training objectives in machine learning are smooth and nonconvex, and they are minimized by stochastic gradient descent (SGD) and its variants. For nonconvex fff the classical guarantee is convergence to an ϵ\epsilonϵ-first-order stationary point, ∥∇f(x)∥≤ϵ\|\nabla f(x)\|\le\epsilon∥∇f(x)∥≤ϵ: Ghadimi and Lan (arXiv:1309.5549) showed that SGD reaches one in …

17 thms2 active usersReviewed
OptimizationProbabilityStatistics·Captain: mikedeng1

Robustness May Be at Odds with Accuracy 2: The Unit-Norm Soft-Margin SVM Is >99% Accurate but <1% Robust at ε ≥ 2η, While Adversarial Training Gives Accuracy pResearch Paper

Adversarial training asks a classifier to work even after an input has been changed within a prescribed perturbation budget. Tsipras, Santurkar, Engstrom, Turner, and Mądry studied why the classifier that performs best on ordinary inputs can behave very differently under these changes. Their explicit model separates one reliably predictive feature from many…

10 thms2 active usersReviewed
OptimizationProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 2: The Proximal Stochastic Subgradient Method Drives E‖∇φ_{1/ρ̄}(x_{t*})‖² to Zero at Rate O(1/√T)Research Paper

The proximal stochastic subgradient method is the workhorse of large-scale learning: to minimize a regularized population risk φ(x)=f(x)+r(x)\varphi(x) = f(x) + r(x)φ(x)=f(x)+r(x) with f(x)=Eξ∼P[f(x,ξ)]f(x) = \mathbb E_{\xi \sim P}[f(x,\xi)]f(x)=Eξ∼P​[f(x,ξ)], it samples a data point, takes a step against a sampled subgradient of fff, and applies the proximal map of the regularizer rrr. Its sample complexity is classical…

12 thms2 active usersReviewed
Dynamical SystemsHarmonic AnalysisProbability·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems II: Echo State Networks with Random Weights Approximate Regular Functionals with an Explicit L² Error Bound (Theorem 2)Research Paper

Reservoir computing learns an input/output system from data in two stages. A dynamical system, the reservoir, is driven by the input sequence and its state is recorded; then only a linear readout of that state is trained, by least squares. The echo state network (ESN) is the most widely used reservoir: its state evolves by …

11 thms2 active usersReviewed
Convex OptimizationOptimization·Captain: mikedeng1

A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic: Explicit Error Bounds for TTSA with a Strongly Convex Outer ObjectiveResearch Paper

Bilevel optimization asks for an outer decision while an inner optimization problem responds to that decision. In hyperparameter selection, for example, the outer objective evaluates a model whose parameters are chosen by a training problem. A two-timescale algorithm updates both levels in one stochastic loop, so its outer step uses an inner solution that…

10 thms2 active usersReviewed
Reinforcement LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making III: E2D with Hellinger Confidence Sets Has Regret at Most Σ_t sup dec_γ(M_εt(M̄), M̄) + γ·Est_H(T,δ)Research Paper

Interactive decision making covers bandits, contextual bandits and reinforcement learning: a learner repeatedly chooses a decision, observes a reward and an observation drawn from an unknown model, and tries to accumulate nearly as much reward as the best decision for that model. Foster, Kakade, Qian and Rakhlin (arXiv:2112.13487) introduced the Decision-Est…

13 thms2 active usersReviewed
Harmonic AnalysisProbability·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems I: Random ReLU Networks with Sampled Inner Weights Approximate Fourier-Represented Functions on a Hilbert Space (Theorem 1)Research Paper

In random-feature models, also called extreme learning machines or random neural networks, the inner weights of a one-hidden-layer network are drawn at random and only the linear readout is trained. Training is then a least-squares problem, which is why such models, and their dynamic counterparts reservoir computing and echo state networks, are used in…

8 thms2 active usersReviewed
Dynamical SystemsProbability·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems III: Echo State Networks with Output Feedback and Random Weights Approximate Contracting Reservoirs (Theorem 4)Research Paper

An echo state network with output feedback is a recurrent model whose previous output is fed back into its next hidden-state update. In reservoir computing only the linear output weights are trained, while the internal weights are fixed, typically after being drawn at random. This raises a quantitative question: if the internal rows are sampled from a fixed…

8 thms2 active usersReviewed
Reinforcement LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making II: Every Algorithm Has Expected Regret at Least (1/6)·dec_γ(M^∞_ε̄γ(M̄), M̄)·T, the Localized DEC Lower BoundResearch Paper

In interactive decision making, an algorithm chooses actions while learning which model governs its observations. A low-regret guarantee for one algorithm does not by itself say whether every algorithm could do better. The Decision-Estimation Coefficient (DEC) was introduced to express the cost of choosing useful decisions while distinguishing plausible…

12 thms2 active usersReviewed
Computational GeometryLinear algebra·Captain: mikedeng1

Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering I: The Rank-m SVD Truncation Plus Its Residual Preserves the Cost of Every j-Dimensional ShapeResearch Paper

Large data sets make clustering and subspace fitting expensive because a candidate solution must be evaluated against every input point. A dimensionality reduction replaces the data by a lower-rank matrix whose costs approximate those of the original input for an entire class of candidate solutions. Feldman, Schmidt, and Sohler study reductions that retain…

11 thms2 active usersReviewed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Personalized Dynamic Pricing with Machine Learning: High-Dimensional Features and Heterogeneous Elasticity 2: Under Unknown Sparsity, Lasso-Based ILQX Pricing Has Regret at Most Cs√T(log d + log T)Research Paper

Online sellers of loans, insurance, travel and retail goods observe data about each arriving customer before quoting a price. Using that data to price individually is attractive only if the seller can learn, from its own sales, how demand responds to price for customers with given characteristics. Two features make this hard in practice. The number of…

6 thms2 active usersReviewed
Optimal TransportProbabilityStatistics·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization and Variation Regularization III: With Probability 1 − e^(−t), E_Pn[(ρ − d(z, D_f))₊] ≤ Cρ² + 2ρ·E[Rademacher] + ρ√(t/2n) for Every fResearch Paper

Wasserstein distributionally robust optimization (DRO) replaces the empirical risk EPn[f]\mathbb E_{P_n}[f]EPn​​[f] of a loss fff by its worst case over all distributions within Wasserstein distance ρ\rhoρ of the empirical law PnP_nPn​. Gao, Chen and Kleywegt (arXiv:1712.06050; Operations Research, 2024, doi:10.1287/opre.2022.2383) show that, for small radii, this worst-case risk…

8 thms2 active usersReviewed
PreviousPage 10 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