Numerical Analysis and Scientific Computing Seminar

How to Characterize the Worst-Case Performance of Algorithms for Nonconvex Optimization

Speaker: Frank E. Curtis, Lehigh University

Location: Warren Weaver Hall 1302

Date: May 4, 2018, 10 a.m.

Synopsis:

Motivated by various applications, e.g., in data science, there has been increasing interest in numerical methods for minimizing nonconvex functions. Users of such methods often choose one algorithm versus another due to worst-case complexity guarantees, which in contemporary analyses bound the number of iterations required until a first- or second-order stationarity condition is approximately satisfied. In this talk, we question whether this is indeed the best manner in which to compare algorithms, especially since the worst-case behavior of an algorithm is often only seen when it is employed to minimize pedagogical examples which are quite distinct from functions seen in normal practice. We propose a new strategy for characterizing algorithms that attempts to better represent algorithmic behavior in real-world settings.