← All papers
First page of Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds

Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds

Xinyuan Guo, Andersen Ang

cs.LO Nov 13, 2026 · v1
Implements, in Lean 4 with Mathlib, a checker that consumes exact performance-estimation certificates, plus a reusable analytic theorem that turns them into verified bounds for optimization algorithms.
Performance-estimation certificates describe worst-case bounds for optimization algorithms. Turning a certificate into a formal theorem requires exact verification of its algebra and a connection between its coordinates, constraints and objective and the intended function-level problem. Lean-PEP provides a reusable interface for this task. It checks a submitted source and exact certificate against a supported canonical finite model, and a parameterized analytic theorem transfers the resulting finite bound to every admissible algorithm trajectory. Generated computation proofs discharge the obligations that depend on each certificate. An additional capture entry checks the numerical record and reconstruction policy. The implemented two-step proximal-gradient consumer verifies a new input with normalized bound 62500/499999, and a fixed eight-configuration batch yields seven distinct payloads with accepted certificates and executed Lean proofs. PG/GD cases and one-step attainment witnesses establish the corresponding algorithmic conclusions, and a fresh installation reproduces consumption of the supplied input. These results show how new certificate data can reuse a proved analytic interface to obtain function-level bounds within the supported models.

Performance-estimation (PEP) certificates give worst-case bounds for optimization algorithms. Turning one into a formal theorem requires checking its exact algebra and connecting its coordinates, constraints and objective to the intended function-level problem. Doing this should not require a new analytic proof for each certificate.

Lean-PEP accepts a submitted source and exact rational certificate and checks them against a supported canonical finite model, using a Boolean checker whose premises are discharged by generated computation proofs. A single parameterized analytic theorem maps any admissible proximal-gradient trajectory to a feasible datum in that model, transferring the finite bound to every trajectory. An optional capture interface also checks the certificate against its numerical record and reconstruction policy. Exact certificates are built from numerical PEP output by source-affine Gaussian elimination and a bounded search.

A two-step proximal-gradient input is verified with normalized bound 62500/499999. A fixed eight-configuration batch yields seven distinct payloads with accepted certificates and executed Lean proofs. Proximal-gradient and gradient-descent bounds are verified, exact one-step bounds are attained by analytic witnesses, and a fresh installation reproduces consumption of the supplied input.

CaseSelected BReferenceB - reference
PG11/41/40
PG2, original62497/4999741/81/1999896
PG341630/4995591/121/5994708
GD1, exact pair1/61/60
PG2, new frozen input62500/4999991/81/3999992
Normalized upper bounds vs. reference values