IFML Seminar: 09/12/25 - Accelerating Nonconvex Optimization via Online Learning

Abstract: A fundamental problem in optimization is finding an ε-first-order stationary point of a smooth function using only gradient information. The best-known gradient query complexity for this task, assuming both the gradient and Hessian of the objective function are Lipschitz continuous, is O(ε^−7/4). In this talk, I present a method with a gradient complexity of O(d^1/4 ε^−13/8), where d is the problem dimension—yielding improved complexity when d= O(ε^−1/2). The proposed method builds on quasi-Newton ideas and operates by solving two online learning problems under the hood. This talk is based on the following STOC paper: https://dl.acm.org/doi/pdf/10.1145/3717823.3718308