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
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

High Precision Multiplicative-Error Approximation of #SAC¹ Functions in Logspace Uniform AC¹Research Paper

Counting computations can produce integers whose binary expansions are much longer than their inputs. A short arithmetic circuit may repeatedly multiply values, making exact output expensive even when the circuit itself has a compact description. An approximation can have a short floating-point representation, but a small absolute error does not by itself…

26 thms2 active usersReviewed
Linear algebraRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Dimension-Free ℓ22\ell_2^2ℓ22​-Sampling Algorithms for Eigenvalue EstimationResearch Paper

Computing the eigenvalues of a symmetric matrix is a basic primitive of numerical linear algebra, data analysis and spectral algorithms. Classical methods read every entry, which costs Ω(n2)\Omega(n^2)Ω(n2) for a dense n×nn\times nn×n matrix. Bhattacharjee, Dexter, Drineas, Musco and Ray ([BDD+24], Algorithmica 2024) asked whether a sublinear number of entry queries…

33 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Delegating Computation with Approximate Arithmetic: Interactive Proofs for WizardsResearch Paper

Interactive proofs let a computationally weak verifier check a computation carried out by an untrusted prover (Goldwasser–Micali–Rackoff 1989, Babai 1985). The protocol of Goldwasser, Kalai and Rothblum (GKR, JACM 2015) makes this efficient for both parties for arithmetic circuits over a finite field: the prover runs in time polynomial in the circuit size,…

26 thms2 active usersReviewed
Differential GeometryOptimization·Captain: iris

A Riemannian Smoothing Steepest Descent Method for Non-Lipschitz Optimization on Submanifolds: RSSD Accumulation Points Are Stationary, and Limiting Stationary under Gradient Sub-ConsistencyResearch Paper

Many estimation problems in signal processing and statistics ask for a sparse or robust solution under an orthogonality or normalization constraint: finding the sparsest vector in a linear subspace over the unit sphere, or learning an orthogonal dictionary over the orthogonal group. Sparsity is promoted by penalties such as ∥x∥pp\|x\|_p^p∥x∥pp​ with 0<p<10<p<10<p<1, which are no…

15 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints: Trust-IPM Reaches an Approximate Second-Order SIP in O(1 + (ψµ(x⁰) − ψ*µ)/µ · (L₁/(µτₗ²))^{3/4}) IterationsResearch Paper

Interior point methods (IPMs) are the basis of widely used nonlinear optimization solvers, and in practice they are applied to problems whose constraints are nonconvex. For linear and conic programs the theory is complete: self-concordance gives an O(clog⁡(1/ϵ))O(\sqrt{c}\log(1/\epsilon))O(c​log(1/ϵ)) iteration bound. For nonconvex constraints, the analyses of practical IPMs show…

16 thms2 active usersReviewed
Machine LearningOptimization·Captain: iris

Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence: RISRO Converges Quadratic-Linearly to a Rank-rrr Stationary Point under 2r2r2r-RIPResearch Paper

Many estimation problems ask for a low-rank matrix that fits linear measurements: matrix sensing, matrix completion, phase retrieval, blind deconvolution, and system identification among them. The common core is rank constrained least squares, a non-convex problem that also underlies low-rank recovery theory (Recht, Fazel and Parrilo, 2010). The problem is…

30 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold: ManIAL Reaches an ε-KKT Point Within Õ(ε⁻³) / O(ε⁻³) Oracle CallsResearch Paper

Many estimation problems are posed over a manifold and carry a nonsmooth regularizer: sparse principal component analysis over the Stiefel manifold, nonnegative PCA, low-rank semidefinite programs in factored form. They share the composite form

27 thms2 active usersReviewed
Operations ResearchOptimization·Captain: iris

Ghost Penalties in Nonconvex Constrained Optimization: Diminishing-Stepsize SQP-Type Iterates Have a Generalized Stationary Limit Point, All KKT under eMFCQResearch Paper

Diminishing stepsizes, γν→0\gamma^\nu\to 0γν→0 with ∑νγν=∞\sum_\nu\gamma^\nu=\infty∑ν​γν=∞, are the standard device of stochastic and distributed optimization: they need no line search, no function evaluations and no global information. For unconstrained or convex problems their convergence theory is classical. For nonconvex problems with nonconvex constraints it was missing:…

38 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
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
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
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
ProbabilityStochastic Systems·Captain: mikedeng1

Adaptive Euler-Maruyama Method for SDEs with Nonglobally Lipschitz Drift I: Strong Convergence of Order 1/2 on a Finite Time IntervalResearch Paper

The explicit Euler–Maruyama scheme is the standard way to simulate a stochastic differential equation

16 thms2 active usersReviewed
Optimization·Captain: mikedeng1

Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms IV: Accumulation Points of the Partial Sparse-Simplex Method Are L2(f)-Stationary PointsResearch Paper

Many problems in signal processing, statistics and machine learning ask for a minimizer of a smooth loss among vectors with few nonzero entries: compressed sensing with a nonlinear measurement model, sparse regression with a non-quadratic loss, sparse phase retrieval. The common abstraction is the sparsity constrained problem

8 thms2 active usersReviewed
Dynamical SystemsOptimization·Captain: mikedeng1

Differential Variational Inequalities 3: For a Cone K and a Strongly Monotone Composite F, the Time-Stepping Iterates Exist, Are Unique and Are Uniformly BoundedResearch Paper

A differential variational inequality (DVI) couples an ordinary differential equation with a finite-dimensional variational inequality whose solution enters the dynamics as a control. Contact mechanics with friction, electrical circuits with diodes, dynamic traffic equilibria, hybrid engineering systems and the continuous-time limits of Nash games all have…

10 thms2 active usersReviewed
Dynamical SystemsOptimization·Captain: mikedeng1

Differential Variational Inequalities 2: Uniformly Bounded Euler Time-Stepping Iterates Converge Along a Subsequence, and Every Limit Is a Weak Solution of the Initial-Value DVIResearch Paper

A differential variational inequality (DVI) couples an ordinary differential equation with a finite-dimensional variational inequality whose solution acts as an algebraic input to the dynamics. The class contains linear complementarity systems, mechanical systems with unilateral contact and friction, dynamic Nash games and many hybrid engineering models.…

9 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Strong Convergence of an Explicit Numerical Method for SDEs with Nonglobally Lipschitz Continuous Coefficients: The Tamed Euler Scheme Converges to the SDE Solution in Uniform Lp with Order 1/2Research Paper

Stochastic differential equations (SDEs) are simulated almost always by time-stepping schemes, and the cheapest and most widely used is the explicit Euler (Euler–Maruyama) scheme. Its strong convergence with order 12\tfrac1221​ is classical when the coefficients are globally Lipschitz. Many models in applications are not: Langevin dynamics with confining…

18 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

A Regression-Based Monte Carlo Method to Solve Backward Stochastic Differential Equations I: Projection Errors of the Picard–Regression Scheme Accumulate AdditivelyResearch Paper

A backward stochastic differential equation (BSDE) prescribes the value of a process at a terminal time and asks for an adapted process that reaches it while following a given drift. In mathematical finance the price of a contingent claim, and its hedging strategy, solve such an equation; when the market has frictions (different borrowing and lending rates,…

9 thms2 active usersReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

A Regression-Based Monte Carlo Method to Solve Backward Stochastic Differential Equations II: Simulation Error of the Empirical Regression Scheme in the Number of PathsResearch Paper

Backward stochastic differential equations (BSDEs) describe the price and the hedge of a contingent claim in models with nonlinear pricing rules (differential interest rates, funding costs, reflected or constrained claims), and give probabilistic representations of semilinear parabolic PDEs (El Karoui, Peng and Quenez, 1997). Their numerical solution in…

9 thms2 active usersReviewed
OptimizationProbability·Captain: mikedeng1

A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization: With Fixed Sampling Radius ε, Gradient Sampling Almost Surely Stops at or Clusters at a Clarke ε-Stationary PointResearch Paper

Many objective functions in engineering and statistics are nonsmooth and nonconvex: the spectral abscissa of a parametrized matrix, the largest eigenvalue of a symmetric matrix function, the H∞H_\inftyH∞​ norm of a closed-loop system, or a maximum of finitely many smooth functions. Such functions are typically differentiable almost everywhere, yet their…

14 thms2 active usersReviewed
PreviousPage 2 of 3Next

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