Finding Simple Proofs for First-Order Optimization

Progress in mathematics often depends not only on proving that a result is true, but on finding a proof that is simple enough to understand, verify, and adapt. Automated systems can now independently discover proofs, but the certificates they produce tend to be dense and difficult to interpret, even when simpler arguments exist. Recent work on performance estimation problems has shown that proofs of convergence for first-order optimization methods can be discovered by searching over a structured space of Lagrangian dual certificates. This paper studies the simplification of such proofs as an optimization problem. Starting from dual certificates, we develop post-processing procedures using tools from sparse optimization and statistical learning. We measure complexity through features such as active hypotheses and residual structure, and introduce methods based on exhaustive sparsification, (weighted) $\ell_1$ heuristics, and semidefinite programming (SDP) formulations for discovering simple proofs and intermediate lemmas. Examples on gradient descent, proximal methods, and fast-gradient methods show that these procedures can autonomously prune redundant inequalities, reveal structured proof patterns, and, in the proximal setting, recover standard intermediate lemmas that lead to streamlined proofs. By distilling dense machine-generated certificates into compact proof structures, this workflow acts as a pre-processing step for the final proof, reducing the complexity that must be managed during human interpretation, reuse, and formalization.