Lean-PEP turns worst-case optimization bounds into formally verified Lean proofs
prof_grimmer · x · 2026-11-18
An undergrad CS project (now a paper, arXiv 2611.17618) presents Lean-PEP: a reusable interface that converts Performance-Estimation Problem (PEP) worst-case numerical bounds for optimization algorithms into Lean-verified, auto-generated proofs.
- Verified example: two-step proximal gradient achieving F(x)−F ≤ LR²·62500/499999 in Lean
- Mechanism: checks submitted source and exact certificate against canonical finite models; a parameterized analytic theorem transfers the finite bound to every reachable algorithm trajectory, with generated computation proofs discharging dependent obligations
- Includes a capture entry for numerical records and a fixed eight-configuration batch yielding seven distinct accepted certificates and executed Lean proofs
More from Research
- sokrypton shows models can reason about which beta sheets interact — sokrypton · 2026-11-18
- OpenAI study: persona-style CoT training drops monitorability from 0.94 to 0.22 — dair_ai · 2026-11-18
- LLM protein-folding test on fresh PDB entry lands near-random structures — MoAlQuraishi · 2026-11-18
- Two arms, two token streams, one shared vocabulary: new robot manipulation work open-sourced — DJiafei · 2026-11-18
- NUS's BiCAT action tokenizer for bimanual robots: 113/150 real-robot wins, 2.7x lower latency than OAT — DJiafei · 2026-11-18
- Roboflow: vision AI faces a long-tail problem — BNSF runs bespoke models on 32,500 miles of track — PTrubey · 2026-11-18