Wednesday, 15:15 - 15:40 h, Room: H 2036


Yoel Drori
Performance of first-order methods for smooth convex minimization: A novel approach

Coauthor: Marc Teboulle


We introduce a novel approach for analyzing the performance of first-order black-box optimization methods. Following the seminal work of Nemirovski and Yudin (1983) in the complexity analysis of convex optimization methods, we measure the computational cost based on the oracle model of optimization. Building on this model, our approach relies on the observation that by definition, the worst case behavior of a black-box optimization method is by itself an optimization problem, which we call the Performance Estimation Problem (PEP). We analyze the properties of the resulting PEP for various black-box first order schemes. This allows us to prove a new tight analytical bound for the classical gradient method, as well as to derive numerical bounds that can be efficiency computed for a broad class of first order schemes. Moreover, we derive an efficient procedure for finding step sizes which produces a first-order black-box method that achieves best performance.


Talk 1 of the invited session Wed.3.H 2036
"First-derivative methods in convex optimization" [...]
Cluster 4
"Conic programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.