A Unifying Theory of First-Order Methods and Applications

Опубликовано 13 марта 2018, 16:19

First-order methods in optimization have become the workhorse tool in modern data-driven applications. Although various general methods with optimal iteration complexities have been known for decades, their standard analysis often appears unintuitive. In this talk, I will present a simple unifying framework based on the numerical discretization of a continuous-time dynamics. Further, I will present a novel accelerated method that is naturally obtained from this framework. The method matches the iteration complexity of the well-known Nesterov’s method, and is, in some cases, more stable under noise-corrupted gradients. Time permitting, I will talk about other applications of the framework, such as in obtaining width-independent parallel algorithms for problems with positive linear constraints, and the extensions of the framework to various settings, including that of block coordinate descent.

See more at microsoft.com/en-us/research/v...