Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds
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.
| Case | Selected B | Reference | B - reference |
|---|---|---|---|
| PG1 | 1/4 | 1/4 | 0 |
| PG2, original | 62497/499974 | 1/8 | 1/1999896 |
| PG3 | 41630/499559 | 1/12 | 1/5994708 |
| GD1, exact pair | 1/6 | 1/6 | 0 |
| PG2, new frozen input | 62500/499999 | 1/8 | 1/3999992 |
