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

 

Abstract:
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" [...]

 

  In particular, Payday Loans Texas can cater to the needs of its residents. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.