Kabir Verchand, USC

Title: The dynamics of iterative algorithms with random data: Beyond first-order methods

Abstract: In this talk, I will present a toolbox to analyze a broad class of iterative algorithms for high-dimensional (non)-convex optimization with random data. This class is rich enough to include general first-order methods with non-separable, Lipschitz updates (such as gradient descent and approximate message passing) as well as commonly used higher-order updates such as the proximal point method, prox-linear methods, as well as variants of alternating minimization and expectation maximization. For this class of algorithms, I will provide an exact, deterministic description of their dynamics as well as finite-sample guarantees bounding the deviation of the empirical iterates from their deterministic counterparts. Our techniques are based on a sequential variant of Gordon’s Gaussian comparison inequalities applied in conjunction with Bolthausen’s Gaussian conditioning technique. Joint work with Michael Celentano, Chen Cheng, and Ashwin Pananjady.