PESTO
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]
Keywords for this software
References in zbMATH (referenced in 22 articles )
Showing results 1 to 20 of 22.
Sorted by year (- Asl, Azam; Overton, Michael L.: Analysis of the gradient method with an Armijo-Wolfe line search on a class of non-smooth convex functions (2020)
- Banert, Sebastian; Ringh, Axel; Adler, Jonas; Karlsson, Johan; Öktem, Ozan: Data-driven nonsmooth optimization (2020)
- De Klerk, Etienne; Glineur, François; Taylor, Adrien B.: Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation (2020)
- Drori, Yoel; Taylor, Adrien B.: Efficient first-order methods for convex minimization: a constructive approach (2020)
- Gu, Guoyong; Yang, Junfeng: Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems (2020)
- Rieger, Janosch; Tam, Matthew K.: Backward-forward-reflected-backward splitting for three operator monotone inclusions (2020)
- Ryu, Ernest K.; Taylor, Adrien B.; Bergeling, Carolina; Giselsson, Pontus: Operator splitting performance estimation: tight contraction factors and optimal parameter selection (2020)
- Ryu, Ernest K.; Vũ, Bằng Công: Finding the forward-Douglas-Rachford-forward method (2020)
- Zhang, Hui: New analysis of linear convergence of gradient-type methods via unifying error bound conditions (2020)
- Arridge, Simon; Maass, Peter; Öktem, Ozan; Schönlieb, Carola-Bibiane: Solving inverse problems using data-driven models (2019)
- Gasnikov, A. V.; Tyurin, A. I.: Fast gradient descent for convex minimization problems with an oracle producing a (( \delta, L))-model of function at the requested point (2019)
- Iutzeler, Franck; Hendrickx, J. M.: A generic online acceleration scheme for optimization algorithms via relaxation and inertia (2019)
- Fazlyab, Mahyar; Ribeiro, Alejandro; Morari, Manfred; Preciado, Victor M.: Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems (2018)
- Kim, Donghwan; Fessler, Jeffrey A.: Another look at the fast iterative shrinkage/thresholding algorithm (FISTA) (2018)
- Kim, Donghwan; Fessler, Jeffrey A.: Generalizing the optimized gradient method for smooth convex minimization (2018)
- Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, François: Exact worst-case convergence rates of the proximal gradient method for composite convex minimization (2018)
- de Klerk, Etienne; Glineur, François; Taylor, Adrien B.: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions (2017)
- Drori, Yoel: The exact information-based complexity of smooth convex minimization (2017)
- Kim, Donghwan; Fessler, Jeffrey A.: On the convergence analysis of the optimized gradient method (2017)
- Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, François: Exact worst-case performance of first-order methods for composite convex optimization (2017)