Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Optimization

2,311 missions · 1,767 completed

Missions

Open544Completed1767All2311
🏆Completed
Bandit AlgorithmsMachine LearningMarkov Chain+1·Captain: QianJaneXie

Cost-aware Bayesian Optimization via the Pandora's Box Gittins IndexResearch Paper

Formal verification complete: all 12 mission targets, including Theorem 2, are Proved. These results apply to the formalized independent-box model described below. Paper: Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index, NeurIPS 2024. The formalization follows Theorem 2 and Appendix B.5 of the paper.

13 thms1 active userReviewed
Convex OptimizationInformation TheoryMachine Learning·Captain: mikedeng1

Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal: under d^(2−δ) bits of memory, first-order methods need Ω̃(d^(1+δ/3)) queriesResearch Paper

Minimizing a convex Lipschitz function over the unit ball of Rd\mathbb R^dRd to accuracy ϵ\epsilonϵ takes Θ(dlog⁡(1/ϵ))\Theta(d\log(1/\epsilon))Θ(dlog(1/ϵ)) first-order queries when ddd is small compared with 1/ϵ1/\epsilon1/ϵ, and cutting-plane methods such as the center-of-mass method attain this rate (Nemirovski–Yudin 1983). They do so by storing their whole cutting history, about …

18 thms1 active userReviewed
Machine LearningReinforcement Learning·Captain: mikedeng1

Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima: Neural TD with Stochastic Semigradients Converges to the Global Optimum of the MSPBE at Rate 1/√TResearch Paper

Temporal-difference (TD) learning estimates the value of a policy in a Markov decision process from sampled transitions, by repeatedly moving a parametrized value function towards a one-step bootstrapped target (Sutton, 1988). With a linear parametrization its behaviour is well understood: TD converges to the fixed point of the projected Bellman equation (Ts…

10 thms1 active userReviewed
Differential GeometryLinear algebra·Captain: mikedeng1

On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization: Gradient and Hessian Connections for Fixed-rank PSD Matrices via YYᵀResearch Paper

Many estimation problems in statistics, signal processing and machine learning ask for a low-rank positive semidefinite matrix: phase retrieval, matrix sensing, PCA-type problems and the Burer–Monteiro approach to semidefinite programs. A standard formulation is

14 thms1 active userReviewed
Convex OptimizationOperations ResearchProbability·Captain: Shuze Chen

Robust Optimization XII: Finite-Horizon Robust Bellman RecursionTextbook

A routing decision can have a known immediate cost while its consequences depend on uncertain weather. A controller observes the current state, chooses an action, and then faces a random next state. A policy optimized for one estimated transition model may perform poorly when those estimates change. Chapter 13 of Ben-Tal, El Ghaoui and Nemirovski, Robust…

4 thms1 active userReviewed
Algebraic GeometryRepresentation Theory·Captain: mikedeng1

A Convex Form That Is Not a Sum of Squares: For k ≥ 17 the Octonionic Cauchy–Schwarz Form Plus (1/4)(‖x‖² + ‖y‖²)² Is a Convex Quartic in 16k Variables That Is Not a Sum of SquaresResearch Paper

A convex form is a homogeneous polynomial of even degree whose value is convex as a function of its real variables. Every convex form is nonnegative, so it is natural to ask whether it can always be written as a sum of squares (SOS) of real polynomials. This matters in polynomial optimization because an SOS certificate can be searched for through…

11 thms1 active userReviewed
Differential GeometryNumerical Analysis·Captain: mikedeng1

Active-Set Newton Methods and Partial Smoothness: Transversal C² Manifolds with a Constant-Rank Map Between Them Yield a Quadratically Convergent Active-Set Newton IterationResearch Paper

Active-set methods for optimization and variational problems run in two phases. A globally convergent first phase identifies which constraints are active at the solution; once they are identified the problem simplifies locally, and a second phase converges fast, typically by linearizing the simplified problem. Sequential quadratic programming for nonlinear…

9 thms1 active userReviewed
Algebraic Geometry·Captain: mikedeng1

Exploiting Sign Symmetries in Minimizing Sums of Rational Functions: The Sign-Symmetry-Adapted Block-Diagonal SOS Hierarchy Converges Monotonically to the Global MinimumResearch Paper

A sum of rational functions is a common objective when several performance measures each have a polynomial numerator and a positive polynomial denominator. Such problems appear, for example, in the applications to computer vision and signal processing cited by Guo, Wang and Zheng in their 2024 preprint. Even when all constraints and numerators are…

13 thms1 active userReviewed
AlgebraAlgebraic Geometry·Captain: mikedeng1

A Sparse Version of Reznick’s Positivstellensatz: Under the Running Intersection Property, a Sparse Positive Definite Form Is a Sum of Sparse SOS Fractions with Uniform DenominatorsResearch Paper

A polynomial that is positive away from the origin can be certified by writing it as a sum of squares after multiplication by a suitable power of the squared Euclidean norm. This is the uniform denominator theorem of Reznick (1995). In polynomial optimization, the size of a sum of squares certificate is governed by the number of variables in each square. A…

10 thms1 active userReviewed
Optimal TransportProbability·Captain: mikedeng1

Convergence Rates for Regularized Optimal Transport via Quantization: Entropic and f-Divergence Rates for Costs with Bounded Second Derivative via Martingale Quantization of an Optimal PlanResearch Paper

Optimal transport asks how cheaply several prescribed probability distributions can be coupled. Adding a divergence penalty relative to their independent product makes the problem amenable to numerical methods, but changes its value. A quantitative bound on that change tells users of regularized transport how much bias a chosen regularization parameter can…

7 thms1 active userReviewed
Quantum Information·Captain: Goku

Randomized and quantum approximate matrix multiplicationResearch Paper

Randomized and quantum approximate matrix multiplication establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Fast Convex Optimization with Quantum Gradient MethodsResearch Paper

Fast Convex Optimization with Quantum Gradient Methods establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Quantum speedups for stochastic optimizationResearch Paper

Quantum speedups for stochastic optimization establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Quantum algorithms for zero-sum gamesResearch Paper

Quantum algorithms for zero-sum games establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Convex optimization using quantum oraclesResearch Paper

Convex optimization using quantum oracles establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum LearningResearch Paper

Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Quantum Information·Captain: Goku

Performance guarantees of light-cone variational quantum algorithms for the maximum cut problemResearch Paper

Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

1 thm1 active userReviewed
Optimal TransportProbabilityStatistics·Captain: mikedeng1

Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization 1: The Gelbrich Minimax and Normal-Prior Maximin Values Coincide (Sandwich Theorem)Research Paper

Estimating an unknown parameter from a noisy linear measurement is the basic problem behind Kalman filtering, signal recovery and linear inverse problems. A Bayesian statistician picks the estimator that minimizes the mean square error under a prior distribution; a minimax statistician guards against the worst prior in some family. The Bayesian answer…

15 thms1 active userReviewed
Calculus of VariationsFunctional Analysis·Captain: mikedeng1

Nonlinear Quasi-hemivariational Inequalities: Existence and Optimal Control: Existence of Solutions to the Generalized Quasi-Hemivariational InequalityResearch Paper

Hemivariational inequalities were introduced by Panagiotopoulos in the 1980s to model mechanical problems whose energy functional is neither convex nor smooth: nonmonotone friction, adhesion, delamination and unilateral contact with nonmonotone multivalued laws. Where a variational inequality expresses the optimality condition of a convex energy, a…

16 thms1 active userReviewed
CombinatoricsLinear Optimization·Captain: mikedeng1

The Running Intersection Relaxation of the Multilinear Polytope 3: Running Intersection Inequalities Meeting Three Support Conditions Define Facets of the Multilinear PolytopeResearch Paper

Binary polynomial optimization asks for the maximum of a polynomial over {0,1}n\{0,1\}^n{0,1}n. Linearizing each monomial ∏v∈ezv\prod_{v\in e}z_v∏v∈e​zv​ by a new variable zez_eze​ turns the problem into a linear program over the convex hull of a set of 0/1 points, the multilinear polytope of the hypergraph whose edges are the monomials. Global solvers such as BARON build polyhedral…

6 thms1 active userReviewed
Convex Optimization·Captain: mikedeng1

DC Programming and DCA: Thirty Years of Developments: For f = g − h with g, h ∈ Γ₀(ℝⁿ), at x ∈ ri(dom g) ∩ ri(dom h) d-Stationarity of f Is Equivalent to Strong Criticality ∅ ≠ ∂h(x) ⊂ ∂g(x)Research Paper

DC programming is the minimization of a function f=g−hf = g - hf=g−h that is a difference of two convex functions. The class contains every C2C^2C2 function on a compact convex set and most nonconvex models of sparse learning, clustering, combinatorial relaxations and robust optimization, and its standard method, the DC Algorithm (DCA), replaces hhh by its affine minorant…

10 thms1 active userReviewed
Control TheoryProbabilityStochastic Systems·Captain: mikedeng1

Open-Loop and Closed-Loop Solvabilities for Stochastic Linear Quadratic Optimal Control Problems 1: The Cost Is Uniformly Convex iff the Riccati Equation Has a Strongly Regular SolutionResearch Paper

The stochastic linear quadratic (LQ) optimal control problem asks to steer a linear stochastic differential equation by a control so as to minimize a quadratic cost. It is the basic model of stochastic control: Wonham studied it in 1968 (Wonham 1968), and it is the model on which feedback design, mean-field control and LQ differential games are built (Yong–Z…

14 thms1 active userReviewed
Algebraic Geometry·Captain: mikedeng1

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 2: A Symmetric Quartic Is Nonnegative iff Each Restriction f^ω to a 2-Partition ω Is a Sum of SquaresResearch Paper

Deciding whether a real polynomial is non-negative on Rn\mathbb R^nRn is NP-hard already for quartics, and the standard computational substitute is to ask whether it is a sum of squares (SOS) of polynomials, which is a semidefinite feasibility problem. The two notions agree only in three cases, determined by Hilbert in 1888: univariate polynomials, quadratic…

7 thms1 active userReviewed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem: The Asymmetric Held–Karp Relaxation Has Integrality Gap at Most 319Research Paper

The asymmetric traveling salesman problem (ATSP) asks for a shortest closed walk through every vertex of a directed graph whose edge weights need not be symmetric. It models routing with one-way streets, scheduling with sequence-dependent setup times, and many other problems in which the cost of going from uuu to vvv differs from the cost of going back. Its…

13 thms1 active userReviewed
Machine LearningProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 3: The Projected Stochastic Subgradient Method Is an Approximate Descent Method on the Moreau Envelope for Any StepsizesResearch Paper

The projected stochastic subgradient method minimizes an expected loss f(x)=Eξ∼P[f(x,ξ)]f(x) = \mathbb E_{\xi\sim P}[f(x,\xi)]f(x)=Eξ∼P​[f(x,ξ)] over a closed convex set XXX: it samples a data point, steps against a sampled subgradient, and projects back onto XXX. For convex fff its sample complexity has been known for decades, and for smooth nonconvex fff the stochastic gradient method needs …

10 thms1 active userReviewed
PreviousPage 91 of 93Next

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