AMS Seminar: Frank Curtis (Lehigh University) @ Whitehead 304
Title: Characterizing the Worst-Case Performance of Algorithms for Nonconvex Optimization
Abstract: 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.