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
Linear algebraOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers VII: Factor Model Fitting — the ADMM X-Update in Closed Form, Entry by EntryTextbook

Alternating direction methods are used when one part of an optimization problem is easy to minimize and another part has a simple projection. Chapter 9 of Boyd, Parikh, Chu, Peleato and Eckstein (2011) examines this idea with nonconvex constraints. Its examples include sparse vectors, Boolean vectors and low-rank matrices. The chapter says explicitly that…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

From Predictive to Prescriptive Analytics 2: For Costs in [0, c̄] That Are L-Lipschitz, w.p. ≥ 1 − δ Every Decision Rule in F Costs ≤ Its Empirical Cost + c̄√(log(1/δ)/2N) + L·ℜ_N(F)Research Paper

Many operations decisions are made after observing side information: an inventory manager sees weather, search trends and calendar effects before ordering; a supply-chain planner sees market signals before shipping. Bertsimas and Kallus, in From Predictive to Prescriptive Analytics (arXiv:1402.5481v4, Management Science 2020), study how to turn such data…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XVI: Random Coordinate Descent RCD(γ) on a Strongly Convex Coordinate-Smooth Function Has Rate (1 − 1/κ_γ)^tTextbook

When a problem has millions of variables, even one full gradient can be too expensive to compute, while a single partial derivative ∂f/∂xi\partial f/\partial x_i∂f/∂xi​ is often cheap: in regularized regression, support vector machines and many structured problems, updating one coordinate costs a small fraction of a full gradient step. Coordinate descent methods exploit…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XIV: Stochastic Mirror Descent on a β-Smooth Function with Noise σ Has Rate Rσ√(2/t) + βR²/tTextbook

Many optimization problems in statistics and machine learning ask to minimize an expected loss f(x)=Eξ ℓ(x,ξ)f(x)=\mathbb E_\xi\,\ell(x,\xi)f(x)=Eξ​ℓ(x,ξ), or an average f(x)=1m∑i=1mfi(x)f(x)=\frac1m\sum_{i=1}^m f_i(x)f(x)=m1​∑i=1m​fi​(x) over a large data set. Exact gradients of such an fff are unavailable or too expensive, but unbiased random estimates are cheap: the gradient of the loss at one sample, or of one randomly…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XII: Mirror Prox on a Convex β-Smooth Function Has Rate βR²/(ρt)Textbook

First-order methods for constrained convex optimization are usually analysed in the Euclidean norm, where gradient descent and its projected and accelerated variants have well-understood rates. Many constraint sets of practical interest, such as the probability simplex, the ℓ1\ell_1ℓ1​ ball and the spectrahedron, are poorly adapted to the Euclidean geometry: the…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XI: Mirror Descent with a ρ-Strongly Convex Mirror Map Has Rate RL√(2/(ρt))Textbook

The projected subgradient method of Chapter 3 measures distances in the Euclidean norm, and its rate RL/tRL/\sqrt tRL/t​ depends on the geometry only through a Euclidean radius RRR and a Euclidean bound LLL on the subgradients. For many constraint sets that occur in practice this is the wrong geometry. On the probability simplex Δn\Delta_nΔn​ with subgradients bounded in …

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity X: Nesterov's Accelerated Gradient Descent on a β-Smooth α-Strongly Convex Function Has Rate ((α + β)/2)‖x₁ − x*‖² exp(−(t − 1)/√κ)Textbook

First-order methods, which query only function values and gradients, are the workhorse of large-scale optimization in machine learning, signal processing and operations research, because each step costs little more than one gradient evaluation. For a function that is both strongly convex and smooth, plain gradient descent converges geometrically, but the…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity IX: Nesterov's Accelerated Gradient Descent on a Convex β-Smooth Function Has Rate 2β‖x₁ − x*‖²/t²Textbook

Minimizing a convex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R whose gradient is Lipschitz is the basic problem of first-order optimization, and it is the regime in which most large-scale methods of machine learning, signal processing and operations research are analysed. The natural method, gradient descent, reaches accuracy ε\varepsilonε after O(1/ε)O(1/\varepsilon)O(1/ε) gradi…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity VIII: No Black-Box Method Beats 3β‖x₁ − x*‖²/(32(t + 1)²) on β-Smooth Convex FunctionsTextbook

Upper bounds for an optimization method say how fast it converges; oracle complexity lower bounds say how fast any method of a given kind can possibly converge. Chapter 3 of S. Bubeck, Convex Optimization: Algorithms and Complexity (Foundations and Trends in Machine Learning 8(3–4), 2015, arXiv:1405.4980) proves upper bounds for subgradient descent on…

8 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 6: The Expected Maximum Discrepancy Lies Between R_n(F)/2 − 2√(2/n) and R_n(F) + 4√(2/n)Research Paper

Data-dependent risk bounds in statistical learning theory control the gap between the expected loss of a learned function and its empirical loss by a complexity penalty that is computed from the training data. The first such penalties were the maximum discrepancy of a function class (Bartlett, Boucheron and Lugosi, Model selection and error estimation,…

10 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 5: Kernel Expansions with α′Kα ≤ B² Have Rademacher and Gaussian Complexity at Most 2B√(E k(X,X)/n)Research Paper

Kernel methods, such as support vector machines, predict with functions of the form x↦∑iαik(x,xi)x \mapsto \sum_i \alpha_i k(x, x_i)x↦∑i​αi​k(x,xi​): finite expansions of a fixed similarity function kkk centred at data points. Their statistical behaviour is governed by the size of the class of such expansions that the method searches. Bartlett and Mendelson, in Rademacher and Gaussian…

8 thms3 active usersReviewed
🏆Completed
OptimizationReinforcement Learning·Captain: mikedeng1

On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift 1: Projected Gradient Ascent on the Simplex Is ε-Optimal After 64γ|S||A|D∞²/((1−γ)⁶ε²) IterationsResearch Paper

Policy gradient methods optimize a parameterized policy of a Markov decision process by gradient ascent on its expected discounted return. They are among the most widely used methods in reinforcement learning, from REINFORCE (Williams 1992) and the policy gradient theorem to natural policy gradient and trust-region methods. The objective is not concave in…

18 thms3 active usersReviewed
🏆Completed
Optimal TransportOptimizationStatistics·Captain: mikedeng1

Robust Wasserstein Profile Inference and Applications to Machine Learning 1: Square-Root LASSO Is Wasserstein DRO — the Worst-Case Squared Loss over D_c(P, P_n) ≤ δ Equals (√MSE_n(β) + √δ‖β‖_p)²Research Paper

Regularized least squares is the standard tool of high-dimensional linear regression. The square-root LASSO of Belloni, Chernozhukov and Wang (Biometrika, 2011) minimizes MSEn(β)+λ∥β∥1\sqrt{\mathrm{MSE}_n(\beta)} + \lambda\|\beta\|_1MSEn​(β)​+λ∥β∥1​. Unlike the LASSO, its optimal regularization parameter does not depend on the unknown noise level. Regularization is usually justified…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Oracle-Based Robust Optimization via Online Learning 1: The Dual-Subgradient Meta-Algorithm Returns a 2ε-Approximate Robust Solution or Certifies Infeasibility within ⌈G²D²/ε²⌉ Oracle CallsResearch Paper

Robust optimization protects a decision against every realization of uncertain data in a prescribed uncertainty set. The standard approach replaces the uncertain constraints by a deterministic robust counterpart and solves that counterpart directly (Ben-Tal, El Ghaoui, Nemirovski, Robust Optimization, 2009). The counterpart is often a harder problem than…

8 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results 4: A Fixed Boolean Combination of k Classes Has Gaussian Complexity at Most 2 Σ_j G_n(F_j)Research Paper

Data-dependent risk bounds in statistical learning replace combinatorial quantities such as the VC dimension with averages of how well a function class can fit random noise on the observed sample. Bartlett and Mendelson's article (JMLR 3, 2002) established these averages, the Rademacher and Gaussian complexities, as a general tool: a risk bound (their…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationReinforcement Learning·Captain: mikedeng1

Twice Regularized MDPs and the Equivalence Between Robustness and Regularization 2: The Greedy Policy of the R2 Optimal Value Is the Unique Optimal R2 PolicyResearch Paper

A robust Markov decision process (robust MDP) evaluates a policy against the worst transition kernel and reward in an uncertainty set around a nominal model (P0,r0)(P_0, r_0)(P0​,r0​). It is the standard model for planning when the dynamics are estimated from data (Iyengar 2005; Nilim and El Ghaoui 2005; Wiesemann, Kuhn and Rustem 2013). Its Bellman update contains an…

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

The Best of Both Worlds: Stochastic and Adversarial Bandits: SAO Has Pseudo-Regret O(K log K log²β/Δ) on Stochastic Rewards and Regret Õ(√(nK)) Against Adaptive AdversariesResearch Paper

In a multi-armed bandit problem a learner chooses one of KKK actions in each of nnn rounds and observes only the reward of the chosen action. Two models of the rewards have separate theories. In the stochastic model, each arm pays independent draws from a fixed distribution; algorithms such as UCB1 (Auer, Cesa-Bianchi & Fischer 2002) have regret of order …

20 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems I: Pseudo-Regret of (α, ψ)-UCBTextbook

The stochastic multi-armed bandit is the basic model of sequential decisions under uncertainty with partial feedback: a forecaster repeatedly picks one of KKK options and observes only the reward of the option it picked. It models clinical trials, ad placement, routing and dynamic pricing, and is the building block of many reinforcement-learning algorithms.…

12 thms3 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network III: Sigmoid Networks with Small Weights GeneralizeResearch Paper

A classifier built from a neural network produces a real score and predicts a binary label from its sign. A network can have many hidden units, so a guarantee based only on the number of parameters can be uninformative even when its output weights are small. Bartlett's 1998 paper asks whether a classifier's margin on training examples and the total…

20 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability+1·Captain: mikedeng1

Variance-based Regularization with Convex Objectives IV: Fast Rates for Approximate Robust Minimizers under a Growth ConditionResearch Paper

In stochastic optimization and statistical learning one chooses a parameter θ\thetaθ from a set Θ⊆Rd\Theta\subseteq\mathbb R^dΘ⊆Rd to make the risk R(θ)=EP[ℓ(θ;X)]R(\theta)=\mathbb E_P[\ell(\theta;X)]R(θ)=EP​[ℓ(θ;X)] small, having seen only a sample X1,…,XnX_1,\dots,X_nX1​,…,Xn​ from PPP. Generalization bounds suggest trading empirical risk against its standard deviation, but the variance-penalized objective is…

12 thms3 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

Variance-based Regularization with Convex Objectives II: A Covering-Number Certificate and Oracle Inequality for the Robust MinimizerResearch Paper

Empirical risk minimization (ERM) chooses, from a class F\mathcal FF of loss functions, the one with the smallest average loss on a sample X1,…,XnX_1,\dots,X_nX1​,…,Xn​. Its standard guarantees bound the excess population risk by a term of order 1/n1/\sqrt n1/n​, whatever the variance of the losses. When good functions in F\mathcal FF have small variance, a better trade-off is…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationProbabilityStatistics·Captain: mikedeng1

The Dantzig Selector: Statistical Estimation When p Is Much Larger than n 2: Oracle Inequality within a Logarithmic Factor of the Ideal Mean Squared ErrorResearch Paper

Many regression problems have far more unknown coefficients ppp than observations nnn: gene expression studies with tens of samples and thousands of genes, imaging from few measurements, nonparametric curve recovery from a finite number of noisy samples. Estimation is hopeless in general, but becomes possible when the parameter is sparse, that is, has few…

11 thms3 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: mikedeng1

Theory of Reproducing Kernels II: One Reproducing Kernel Class Contains Another iff a Multiple of Its Kernel Dominates the Other KernelResearch Paper

A reproducing kernel Hilbert space (RKHS) is a Hilbert space of functions in which evaluation at each point is a continuous functional. Each such space is determined by its kernel, and in practice spaces are usually given by their kernels: Gaussian or Sobolev kernels in kernel methods and Gaussian-process regression, the Bergman and Szegő kernels in complex…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationProbabilityStatistics·Captain: mikedeng1

Stability and Generalization 4: Relative-Entropy Regularization of Mixtures Has Uniform Stability M²/(λm)Research Paper

A learning algorithm generalizes when its error on fresh data is close to its error on the training sample. Bousquet and Elisseeff (JMLR 2, 2002) showed that a single property of the algorithm, uniform stability, controls this gap with exponential concentration: if removing any one example from a training set of size mmm changes the loss of the output at…

18 thms3 active users
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Stability and Generalization 2: Exponential Generalization Bounds for Uniformly Stable AlgorithmsResearch Paper

A learning algorithm is judged by its generalization error: the expected loss of the hypothesis it outputs on a fresh example. That quantity depends on an unknown distribution, so it is estimated from the training data, by the empirical error (the average loss on the training set) or the leave-one-out error (the average loss on each training point of the…

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