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
Bandit Algorithms·Captain: iris

Follow the Perturbed Leader for Linear Bandits: T\sqrt{T}T​ Regret over General Action SetsResearch Paper

In an adversarial linear bandit a learner repeatedly picks an action ata_tat​ from a set A⊂RdA\subset\mathbb R^dA⊂Rd, an adversary picks a reward function, and the learner sees only the reward of the action it played. The problem models online routing, ranking and combinatorial decision making with partial feedback, and its minimax regret over general action sets is …

47 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

A Few Experts Suffice: Near-Optimal (Private) Online Learning with Limited SubscriptionsResearch Paper

In prediction with expert advice, a learner faces NNN experts over TTT rounds. Each round every expert iii earns a gain gti∈[0,1]g_t^i\in[0,1]gti​∈[0,1], the learner follows one expert, and its regret is the gap between the best expert's total gain and its own. Multiplicative weights achieves regret O(Tlog⁡N)O(\sqrt{T\log N})O(TlogN​), which is optimal (Freund–Schapire 1997; Cesa-Bianchi–Lugosi 2006)…

23 thms3 active usersReviewed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: iris

The Online Saddle Point Problem and Online Convex Optimization with Knapsacks: Saddle-Point Follow-the-Leader Has SP-Regret at Most 8G2/H⋅(1+log⁡T)8G^2/H\cdot(1+\log T)8G2/H⋅(1+logT) on Strongly Convex-Concave Lipschitz GamesResearch Paper

Many decisions are made by two parties with opposed interests who interact repeatedly while the game between them changes: a seller and a buyer facing shifting demand, a planner and an adversarial environment, or the primal and dual players of a constrained online optimization problem. Rivera Cardoso, Wang and Xu (arXiv:1806.08301v3) formalize this as the on…

13 thms3 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

Maximal Objectives in the Multi-armed Bandit with Applications: ADA-ETC Has an Explicit Instance-Dependent Regret Bound and Worst-Case Regret O(K^{1/3}T^{2/3}√log K) for the Max ObjectiveResearch Paper

In the classical stochastic multi-armed bandit, a decision-maker pulls one of KKK arms at each of TTT times and is judged by the sum of all rewards collected. Ozbay and Kamble (arXiv:2006.06853v6, later in Management Science, 2024) study a different objective: the decision-maker is judged by the largest cumulative reward of a single arm at the end of the…

11 thms3 active usersReviewed
OptimizationProbability·Captain: iris

Efficiency of Stochastic Coordinate Proximal Gradient Methods on Nonseparable Composite Optimization: With Probability ≥ 1 − e^{−β²(1−δ)(K+1)/2}, min_{i≤K} ‖∇F(xᵢ)‖² ≤ (F(x₀) − F*)/(C(1−β)(1−δ)(K+1))Research Paper

Many problems in machine learning, signal processing and control minimize a composite objective F(x)=f(x)+ψ(x)F(x)=f(x)+\psi(x)F(x)=f(x)+ψ(x) over x∈Rnx\in\mathbb R^nx∈Rn. Here fff is smooth and ψ\psiψ is a regularizer or penalty. When nnn is large, a full gradient or a full proximal step costs too much, and coordinate descent methods update only a few coordinates or a low-dimensional subspace per…

21 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Langevin Dynamics Based Algorithm e-THεO POULA for Stochastic Optimization Problems with Discontinuous Stochastic Gradient: Non-Asymptotic Bound on the Expected Excess RiskResearch Paper

Many stochastic optimization problems in machine learning, finance and insurance minimize an expectation u(θ)=E[U(θ,X)]u(\theta)=E[U(\theta,X)]u(θ)=E[U(θ,X)] whose stochastic gradient is discontinuous in the parameter: quantile estimation, vector quantization, CVaR minimization and networks with ReLU activation all have this form. The objective may also be non-convex, and its gradient…

28 thms3 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: iris

Delay-Adaptive Learning in Generalized Linear Contextual Bandits: Under Independent Delays with a Tail Envelope, DUCB-GLCB Satisfies the Regret Bound (16) with Probability at Least 1 − 5δResearch Paper

In many sequential decision problems the outcome of a decision arrives late. A recommendation's conversion, a clinical response or a sale is observed hours or weeks after the action, and in the meantime the decision maker has to keep acting. Contextual bandits model the decision side: at each round a learner sees side information, chooses one of KKK actions…

18 thms3 active usersReviewed
Bandit AlgorithmsOperations ResearchStatistics·Captain: iris

Rate-Optimal Bayesian Simple Regret in Best Arm Identification: Two-Stage Exploration Has Bayesian Simple Regret at Most Copt/T′+o(1/T)C_{\mathrm{opt}}/T' + o(1/T)Copt​/T′+o(1/T)Research Paper

A clinical trial, an A/B test or a simulation study often ends with one decision: which treatment to adopt. Multi-armed bandit theory calls this best arm identification. When the arm means are fixed, the frequentist simple regret after TTT pulls decays exponentially at each instance, with a rate that degenerates as the gap closes. A practitioner who has a…

39 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchReinforcement Learning·Captain: iris

Adaptive Discretization in Online Reinforcement Learning: AdaMB and AdaQL Have Regret Scaling with the Zooming DimensionResearch Paper

Reinforcement learning in operations problems (inventory control, ambulance routing, pricing, queue admission) often has continuous state and action spaces. A fixed grid of mesh ϵ\epsilonϵ wastes samples on regions where nothing is learned, and its regret grows with the ambient dimension of S×A\mathcal S\times\mathcal AS×A. Adaptive discretization refines a…

37 thms3 active usersReviewed
OptimizationProbability·Captain: iris

Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions: The Iterates Almost Surely Avoid Active Strict Saddles Satisfying the Verdier and Angle ConditionsResearch Paper

Training a neural network or fitting a nonsmooth statistical model usually means running the stochastic subgradient method on a function that is neither smooth nor convex. Convergence theory gives limit points that are Clarke critical (Davis et al., 2020; Bolte and Pauwels, 2021), but Clarke critical points include points that no one wants, and a…

27 thms3 active usersReviewed
ProbabilityStatistics·Captain: iris

Adversarial Robustness for Latent Models: Revisiting the Robust-Standard Accuracies Tradeoff: The Bayes-Optimal Classifier's Boundary Risk Vanishes in the Latent Gaussian Mixture ModelResearch Paper

Classifiers that reach high accuracy on test data can often be fooled by perturbations of the input that are small in some norm. Training a classifier to resist such perturbations (adversarial training) typically lowers its accuracy on unperturbed data, and part of the literature argues that this robust–standard accuracy tradeoff is unavoidable: for some…

21 thms3 active usersReviewed
ProbabilityStatistics·Captain: iris

Finite-Time High-Probability Bounds for Polyak–Ruppert Averaged Iterates of Linear Stochastic Approximation: Under i.i.d. Noise the p-th Moment Error Is ≲ √(p Tr Σε/n) + ‖ε‖∞(p/n^{3/4} + p²/n)Research Paper

Linear stochastic approximation (LSA) solves a linear system Aˉθ=bˉ\bar{\mathbf A}\theta=\bar{\mathbf b}Aˉθ=bˉ when only noisy observations of the matrix and of the right-hand side are available. It is the linear core of temporal-difference learning with linear function approximation, of stochastic gradient descent on least squares, and of many online estimation…

15 thms3 active usersReviewed
Bandit AlgorithmsProbability·Captain: iris

A General Framework for Bandit Problems Beyond Cumulative Objectives: U-UCB has regret O(log T / T) for every stable, smooth EDPM with a linear gapResearch Paper

In the classical stochastic multi-armed bandit a decision maker is scored by the sum of the rewards it collects. Many applications score the collected rewards differently: a portfolio manager cares about the conditional value at risk (CVaR) or the Sharpe ratio of the returns, a clinical trial about a quantile, a risk-averse controller about mean–variance.…

16 thms3 active usersReviewed
Bandit AlgorithmsReinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning XII: E2D Regret Is at Most the Decision-Estimation Coefficient Times T Plus γ·EstSqTextbook

In a structured bandit a learner repeatedly picks a decision πt\pi^tπt from a possibly huge or continuous set Π\PiΠ and observes a noisy reward with mean f⋆(πt)f^\star(\pi^t)f⋆(πt), where f⋆f^\starf⋆ belongs to a known class F\mathcal FF of functions Π→R\Pi\to\mathbb RΠ→R. The optimal regret depends on F\mathcal FF in ways that are hard to predict: optimism (UCB) and posterior sampling…

27 thms3 active usersReviewed
Reinforcement LearningStatistics·Captain: iris

Foundations of Reinforcement Learning VII: Empirical Risk Minimization over a Finite Class Has Expected Excess Risk ≲ √(log|F|/T), and ≲ log|F|/T for Well-Specified Square LossTextbook

Interactive decision making rests on estimation: an agent that acts well must fit a model to past data and rely on it for data not yet seen. The lecture notes of Foster and Rakhlin (arXiv:2312.16730) therefore open with statistical learning, the passive problem in which the learner does not influence the data. It isolates generalization and function…

20 thms3 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

The Secretary Problem with Predictions: Learned Dynkin Is max{0.215, (1−ε)/(1+ε)}-CompetitiveResearch Paper

The secretary problem asks how to hire the best of nnn candidates who are interviewed one at a time in random order, when every hiring decision must be made irrevocably at the interview. It is the standard model of online selection under uncertainty, and its answer, Dynkin's rule, hires the maximum with probability 1/e1/e1/e (Dynkin 1963; see the survey of Ferguson…

12 thms3 active usersReviewed
Operations ResearchStatistics·Captain: mikedeng1

A Statistical Learning Approach to Personalization in Revenue Management: High-Probability Revenue Gap Bound for Decisions from the ℓ1-Constrained Logit Maximum Likelihood EstimateResearch Paper

Retailers and platforms increasingly set prices and choose which products to display per customer, using observed customer attributes (location, device, purchase history). The decision rule is usually built in two steps: fit a choice model to historical transactions, then optimize prices and assortments as if the fitted model were the truth. Chen, Owen,…

10 thms3 active usersReviewed
Optimization·Captain: mikedeng1

Suboptimal Local Minima Exist for Wide Neural Networks with Smooth Activations: For Generic Inputs and Any Depth and Width, Some Output Data Gives the Squared Loss a Sub-Optimal Local MinimumResearch Paper

Training a neural network means minimizing a non-convex loss over its weights. Local search methods can only certify local optimality, so a recurring question in the theory of neural network optimization is whether every local minimum of the training loss is a global minimum. A local minimum that is not global is called a sub-optimal (or bad) local minimum.

8 thms3 active usersReviewed
Bandit AlgorithmsProbability·Captain: mikedeng1

Online Learning over a Finite Action Set with Limited Switching: An Algorithm for Prediction From Experts Whose Regret and Number of Switches Are Both O(√(T log n log(1/δ))) with Probability 1 − δResearch Paper

In prediction from experts (PFE), an online learner chooses one of nnn actions in each of TTT rounds, and an adversary assigns each action a loss in [0,1][0,1][0,1]. Performance is measured by regret, the learner's total loss minus that of the best single action in hindsight. In many applications changing the action is itself costly: re-routing traffic, re-balancing a…

10 thms3 active usersReviewed
Differential GeometryOptimizationProbability·Captain: mikedeng1

Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 2: ZO-RSGD Has Average Expected Squared Riemannian Gradient Norm at Most 4L(f(x₀) − f(x*))/(N+1) + 2μ²L²(d+6)³ + 16(d+4)σ²/mResearch Paper

Many optimization problems are posed over a manifold rather than a vector space: orthogonality constraints (the Stiefel manifold), unit-norm constraints (the sphere), fixed-rank matrices. In some of them the objective can only be evaluated, not differentiated. Black-box adversarial attacks on a neural network with a norm-constrained perturbation,…

13 thms3 active usersReviewed
Differential GeometryOptimizationProbability·Captain: mikedeng1

Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 1: ZO-RGD Has Average Expected Squared Riemannian Gradient Norm at Most 8(d+4)L(f(x₀) − f(x*))/(N+1) + 8(d+4)L·C(μ)Research Paper

Many optimization problems in statistics and machine learning constrain the variable to a smooth manifold: orthonormal frames in sparse PCA and dictionary learning (the Stiefel manifold), unit vectors in phase retrieval (the sphere), fixed-rank matrices in matrix completion. Riemannian optimization handles these problems directly on the manifold. A step is…

13 thms3 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Offline Multi-Action Policy Learning: Generalization and Optimization 1: Cross-Fitted AIPW Policy Learning Has Regret O_p(κ(Π)√(V*/n)) Even with Slowly Converging Nuisance EstimatesResearch Paper

Many decisions are made by assigning one of several actions to an individual on the basis of observed features: which of ddd drugs to prescribe, which of several promotions to show, which job-training programme to offer. Experimentation is often costly or unethical, while historical records of past assignments and their outcomes are plentiful. Offline policy…

9 thms3 active usersReviewed
OptimizationReinforcement Learning·Captain: mikedeng1

Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees: Single-Loop ML-IRL Policy and Reward Iterates Converge at Explicit Finite-Time RatesResearch Paper

Structural estimation of Markov decision processes recovers the parameters of an agent's reward from observed behavior, under the hypothesis that the agent acts optimally in a known dynamic environment. In econometrics this is the dynamic discrete choice model of Rust (Rust 1987); in artificial intelligence it is maximum-likelihood inverse reinforcement…

18 thms3 active usersReviewed
Quantum Information·Captain: Goku

A Survey of Quantum Learning Theory 4: Quantum states are PAC-learnable from n·poly(1/ε, 1/γ, log(1/δ)) measurement resultsTextbook

This mission develops Chapter 4 of A Survey of Quantum Learning Theory by Srinivasan Arunachalam and Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.

14 thms3 active usersReviewed
Operations ResearchOptimal TransportStatistics·Captain: mikedeng1

Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality 3: Under T₂(τ), W₂-Robust Loss at Radius ρ̃ₙ Bounds True Loss up to 4r⋆+2εₙ+ħρ̃ₙ²Research Paper

Wasserstein distributionally robust optimization (Wasserstein DRO) replaces the empirical loss EPn[f]\mathbb E_{\mathbb P_n}[f]EPn​​[f] of a decision by its worst case over all distributions within Wasserstein distance ρ\rhoρ of the empirical distribution Pn\mathbb P_nPn​. It is used in operations research (newsvendor, portfolio selection) and machine learning (adversarially…

15 thms3 active usersReviewed
PreviousPage 5 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