Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Numerical Analysis

254 missions · 180 completed

Missions

Open74Completed180All254
🏆Completed
Functional AnalysisMachine LearningProbability+1·Captain: Shuze Chen

The Nature of Statistical Learning Theory VII: Tikhonov Regularization of Ill-Posed ProblemsTextbook

Estimating a probability density, a conditional probability or a conditional density from data can be written as solving a linear operator equation Af=FAf = FAf=F whose right-hand side FFF is a distribution function. The true FFF is unknown; only its empirical estimate FℓF_\ellFℓ​ is available, built from ℓ\ellℓ observations. The Glivenko–Cantelli theorem and the…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling XI: First Passage Times by Reduction and BisectionTextbook

In a quasi-birth-and-death process (QBD) a queue length or buffer content (the level) moves up or down by at most one per step while an auxiliary Markov environment (the phase) modulates the rates. When buffers are bounded the level lives in {0,1,…,M}\{0,1,\dots,M\}{0,1,…,M}, and a basic performance question is how long it takes, on average, for an initially empty buffer to…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling VIII: The Logarithmic Reduction Series for GTextbook

Quasi-birth-and-death processes (QBDs) are Markov chains on pairs (level, phase) in which the level moves by at most one at each step. They model queues in random environments, priority queues, and many other systems treated by matrix-analytic methods (Latouche & Ramaswami 1999). Their stationary distribution, when it exists, is matrix-geometric, and…

8 thms2 active usersReviewed
🏆Completed
Linear algebraMarkov ChainOperations Research+2·Captain: Shuze Chen

Introduction to Matrix Analytic Methods in Stochastic Modeling X: Linear Level Reduction for Finite QBDsTextbook

In a queue with a finite buffer, a multi-server system with a capacity limit, or a communication link with a bounded number of packets in transit, the number of customers is a level that takes only finitely many values, and the rest of the state (service phase, arrival phase, environment) is a phase. The resulting Markov chain is a finite…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Lectures on Modern Convex Optimization X: Complexity of the Ellipsoid MethodTextbook

A convex program whose objective and feasible set are known only through oracles, routines that answer queries about one point at a time, can still be solved to any prescribed accuracy with a number of queries bounded in advance. The ellipsoid method is the classical algorithm that achieves this. It was introduced for convex minimization by Yudin and…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: Shuze Chen

Lectures on Modern Convex Optimization XI: Primal-Dual Path-Following for Semidefinite ProgrammingTextbook

Semidefinite programming (SDP), the optimization of a linear function over the intersection of an affine subspace with the cone of positive semidefinite matrices, is the workhorse behind relaxations in combinatorial optimization, robust optimization and control. Its practical and theoretical tractability rests on interior point methods: algorithms that…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs: Linear Splines of the Marginal Costs with Bounded Step Sizes Give an (α, β)-Approximate Minimum-Cost Flow FunctionResearch Paper

Flow networks model the movement of material, traffic, electricity, or gas through connected systems. In many such models, the required net flow at each vertex varies with a parameter, so the object of interest is a whole family of optimal flows rather than one solution. When edge costs are nonlinear, solving a new optimization problem for every parameter…

10 thms2 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 3: The Kurdyka–Łojasiewicz Property with Exponent 1/2 Implies the VP-EB Error BoundResearch Paper

Augmented Lagrangian methods are a standard tool for constrained optimization, and first-order primal-dual variants of them are used when the objective is large, nonsmooth or nonconvex and second-order information is too expensive. Zhu, Zhao and Zhang (arXiv:2007.12219v1, published in Mathematics of Operations Research, 2024) analyse such a method, NAPP-AL (…

14 thms2 active users
AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Generalized Newton Method for Subgradient Systems 2: Under Metric Regularity and Semismoothness*, the FBE-Based Newton Algorithm Converges Superlinearly in Quadratic Composite OptimizationResearch Paper

Many optimization models in statistics, signal processing and machine learning minimize a smooth loss plus a nonsmooth regularizer, min⁡xf(x)+g(x)\min_x f(x)+g(x)minx​f(x)+g(x). When fff is quadratic this is the quadratic composite problem, which also appears as the subproblem of sequential quadratic programming and of proximal Newton methods. First-order splitting methods (proximal…

22 thms2 active usersReviewed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Generalized Newton Method for Subgradient Systems 1: Under Metric Regularity and Semismoothness*, the Prox-Based Newton Algorithm Converges Superlinearly for Prox-Regular FunctionsResearch Paper

Many problems in optimization reduce to a subgradient inclusion 0∈∂φ(x)0\in\partial\varphi(x)0∈∂φ(x): for a smooth φ\varphiφ this is the gradient equation ∇φ(x)=0\nabla\varphi(x)=0∇φ(x)=0, and for an extended-real-valued φ=f+g\varphi=f+gφ=f+g (a smooth loss plus an indicator or a nonsmooth regularizer) it is the first-order optimality condition of a composite problem. Newton's method is the…

17 thms2 active usersReviewed
Markov ChainProbability·Captain: mikedeng1

Multilevel Langevin Pathwise Average for Gibbs Approximation I: Under (H₁)–(H₄) the Multilevel Occupation Measure Has L²-Error ≲ [f]₁ε at Cost 𝔠_𝔞γ₀⁻¹𝔱ε⁻², or ε⁻²R_ε³ When 𝔞 = 1Research Paper

Sampling from a Gibbs distribution π(dx)∝e−U(x)dx\pi(dx)\propto e^{-U(x)}dxπ(dx)∝e−U(x)dx on Rd\mathbb R^dRd, or computing integrals π(f)\pi(f)π(f) against it, is a basic task in Bayesian statistics and machine learning. A standard approach simulates an ergodic diffusion whose invariant distribution is π\piπ, such as the overdamped Langevin diffusion dXt=−∇U(Xt)dt+2 dBtdX_t=-\nabla U(X_t)dt+\sqrt2\,dB_tdXt​=−∇U(Xt​)dt+2​dBt​, discretizes…

12 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

An Approximation to the Invariant Measure of the Limiting Diffusion of G/Ph/n + GI Queues in the Halfin–Whitt Regime and Related Asymptotics 1: Euler–Maruyama Error C_ς η^{(1−ς)/2} in Wasserstein-1Research Paper

Many-server queues are the basic model of call centres and hospital wards, and the Halfin–Whitt regime (the number of servers nnn grows while the traffic intensity approaches one at rate n−1/2n^{-1/2}n−1/2) is where such systems operate efficiently and with short delays. In this regime the centred and scaled queue process of a G/Ph/n+GIG/Ph/n+GIG/Ph/n+GI queue (general arrivals,…

18 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results IV: The Image Function (Bg) Is Lsc on B dom g Exactly When Condition (5.5) HoldsResearch Paper

The alternating direction method of multipliers (ADMM) solves problems of the form min⁡x,zf(x)+g(z)\min_{x,z} f(x)+g(z)minx,z​f(x)+g(z) subject to Ax+Bz=bAx+Bz=bAx+Bz=b. Themelis and Patrinos (arXiv:1709.05747v4, SIAM J. Optim. 30(1):149–181, 2020) show that, for nonconvex fff and ggg, ADMM is the Douglas–Rachford splitting method applied to a reformulated problem whose second term is the image function …

7 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results I: Under the Tight Stepsize Bound, the Nonconvex DRS Residual Vanishes and Cluster Points Are StationaryResearch Paper

Douglas–Rachford splitting (DRS) minimizes a sum φ=φ1+φ2\varphi=\varphi_1+\varphi_2φ=φ1​+φ2​ by alternating the proximal mappings of the two terms. It goes back to the alternating-direction schemes for heat conduction of Douglas and Rachford (1956), was cast as a splitting method for monotone operators by Lions and Mercier (1979), and through its dual form, the alternating…

11 thms2 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 3: With Linesearch and Locally Lipschitz B the Method Converges to a Zero in Finite DimensionsResearch Paper

Many problems in optimization, variational inequalities and saddle-point computation can be written as a monotone inclusion: find xxx with 0∈A(x)+B(x)0 \in A(x) + B(x)0∈A(x)+B(x), where AAA is a set-valued maximally monotone operator (a subdifferential, a normal cone) and BBB is single-valued (a gradient, a skew saddle operator). Splitting methods treat AAA only through its resolvent…

9 thms2 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 1: The Forward-Reflected-Backward Method Converges Weakly to a Zero of A + BResearch Paper

Many problems in convex optimization, variational inequalities and saddle-point computation can be written as a monotone inclusion: find xxx in a real Hilbert space HHH with

11 thms2 active usersReviewed
Functional AnalysisOptimization·Captain: mikedeng1

Projected Reflected Gradient Methods for Monotone Variational Inequalities 3: The Adaptive-Step Method Converges Weakly to a Solution Without Knowing the Lipschitz ConstantResearch Paper

A variational inequality asks for a point of a convex set at which a vector field points "inward" against every feasible direction. It covers constrained convex minimization (with F=∇fF = \nabla fF=∇f), saddle-point problems, Nash equilibria of convex games and complementarity problems, which is why projection methods for it are a standard topic in optimization and…

11 thms2 active usersReviewed
🏆Completed
Linear algebraOptimizationTheoretical Computer Science·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 2: Sketched Multiple-Response Regression Is (1 + 4ε)-Optimal in Squared Error If the Sketch Embeds the Subspace and Approximates ProductsResearch Paper

Least-squares regression, min⁡X∥AX−B∥F\min_X\|AX-B\|_FminX​∥AX−B∥F​ for a tall matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d with n≫dn\gg dn≫d, is among the most frequently solved problems in numerical computation. Direct methods (QR or SVD) cost O(nd2)O(nd^2)O(nd2) time, which is prohibitive when nnn is in the millions. Sketching replaces the problem by a much smaller one: choose a matrix S∈Rt×nS\in\mathbb R^{t\times n}S∈Rt×n…

7 thms2 active usersReviewed
Linear algebraProbabilityTheoretical Computer Science·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper

Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…

9 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Conservative Set Valued Fields, Automatic Differentiation, Stochastic Gradient Methods and Deep Learning 2: Forward and Reverse Mode Automatic Differentiation Yield Conservative FieldsResearch Paper

Training a neural network means running a first-order method on a loss that is built from compositions of elementary operations, many of them nonsmooth: ReLU, max-pooling, absolute values, sorting, norms. The gradient the optimizer uses is not computed by hand. It is computed by automatic differentiation (autodiff), most often in its reverse mode, backpropag…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An Augmented Lagrangian Based Algorithm for Distributed Nonconvex Optimization 1: With ρ = 0, the ALADIN Dual Update Equals the Levenberg–Marquardt Dual Newton Step of Dual DecompositionResearch Paper

Large optimization problems often split into blocks owned by different agents (subsystems of a power grid, vehicles in a formation, scenarios of a stochastic program) that are coupled only through a few linear constraints. Distributed optimization methods solve such problems by letting each agent work on its own block and exchanging a small amount of…

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

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 3: ISTA for ℓ1-Regularized Least Squares Satisfies f(x_k) − min f ≤ (f(x_0) − min f)/q^k with q = 1 + 2aγ_R/b²Research Paper

The ℓ1-regularized least squares problem (the Lasso, or basis pursuit denoising) is the model problem of compressed sensing and sparse inverse problems: given a matrix A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n, data d∈Rmd\in\mathbb R^md∈Rm and a weight μ>0\mu>0μ>0, one seeks a vector xxx that fits Ax≈dAx\approx dAx≈d while having few nonzero entries. The standard first-order method for it is the i…

14 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 1: Bounded Iterates Converge to a KKT Point with Finite Length Under the KL PropertyResearch Paper

Many problems in signal processing, statistics and machine learning are of the form min⁡x{g(Ax)+h(x)}\min_x \{g(Ax)+h(x)\}minx​{g(Ax)+h(x)}: a smooth data-fitting term hhh, plus a possibly nonsmooth and nonconvex regularizer ggg applied to a linear image AxAxAx of the variable. Examples are total-variation-type penalties with nonconvex potentials, ℓ0\ell_0ℓ0​-type sparsity terms, and constraints Ax∈CAx\in CAx∈C…

16 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold: Every Limit Point of ManPG Is Stationary, and an ε-Stationary Point Is Reached Within ⌈2L(F(X₀)−F*)/(γᾱε²)⌉ IterationsResearch Paper

Many problems in statistics and signal processing ask for an orthonormal frame X∈Rn×rX\in\mathbb R^{n\times r}X∈Rn×r that is both a good fit to the data and sparse or otherwise structured. Sparse principal component analysis, compressed modes in physics, unsupervised feature selection and sparse blind deconvolution all take the form

12 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Adaptive Euler-Maruyama Method for SDEs with Nonglobally Lipschitz Drift II: Strong Convergence of Order 1/2 Uniformly in Time for Contractive SDEsResearch Paper

Many stochastic differential equations used in physics, biology and Bayesian sampling are ergodic: their law converges to an invariant measure π\piπ, and quantities of interest are averages π(φ)=∫φ dπ=lim⁡t→∞E[φ(Xt)]\pi(\varphi)=\int\varphi\,\mathrm d\pi=\lim_{t\to\infty}\mathbb E[\varphi(X_t)]π(φ)=∫φdπ=limt→∞​E[φ(Xt​)]. Estimating such averages by simulation requires a numerical method whose accuracy does not…

14 thms2 active usersReviewed
PreviousPage 7 of 11Next

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