← 研踪 PaperTrailarXiv:2611.17618 · v1
Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds
首次提交 2026-11-13 08:38
版本更新 2026-11-13 08:38
雷达观测 2026-11-17 04:58
摘要
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.
作者备注:26 pages, 2 figures, 8 tables
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-13 08:38 · 最新观测版本
Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds
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.
查看此版本解读 →查看此版本原文 ↗