swMATH ID: 20864
Software Authors: Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, F.
Description: Code of the Performance Estimation Toolbox (PESTO) whose aim is to ease the access to the PEP methodology. The numerical worst-case analyses from PEP can be performed just by writting the algorithms just as you would implement them: Exact worst-case performance of first-order methods for composite convex optimization. We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2]
Homepage: https://github.com/AdrienTaylor/Performance-Estimation-Toolbox
Source Code: https://github.com/AdrienTaylor/Performance-Estimation-Toolbox
Keywords: convex optimization; composite convex optimization; first-order methods; worst-case analysis; performance estimation; semidefinite programming; convex interpolation
Related Software: YALMIP; CVX; SeDuMi; UNLocBoX; Mosek; Wasserstein GAN; GitHub; Saga; TensorFlow; DFO; Wirtinger Flow; Eigtool; SDPT3; Mathematica; IQC-Game; AlexNet; SBEED; ImageNet; CVXPY; Macaulay2
Cited in: 40 Publications

Citations by Year