Aarhus University Seal / Aarhus Universitets segl

Specil talk by Zhao Song on Faster Optimization: from linear programming, to semidefinite programming and beyond to deep learning

22.02.2021 | Søs Küster Markussen

Date Tue 23 Feb
Time 15:00 16:00
Location Online - Zoom meeting

Specil talk by Zhao Song on Faster Optimization: from linear programming, to semidefinite programming and beyond to deep learning

Abstract : Many important real-life problems, in both convex and non-convex settings, can be solved using path-following optimization methods. The running time of optimization algorithms is typically governed by two components -- the number of iterations and the cost-per-iteration. For decades, the vast majority of research effort was dedicated to improving the number of iterations required for convergence. A recent line of work of ours shows that the cost-per-iteration can be dramatically improved using a careful combination of dynamic data structures with `robust' variants of the optimization method. A central ingredient is the use of randomized linear algebra for dimensionality reduction (e.g., linear sketching) for fast maintenance of dynamic matrix problems. This framework recently led to many breakthroughs on decade-old optimization problems.

In this talk, I will present the framework underlying these breakthroughs, focusing on faster algorithms for linear programming, semidefinite programming and deep learning. We will first present how to use the above idea to speed up general LP solvers by providing an n^omega + n^{2+1/18} time algorithm. We then show how to apply similar ideas to SDP solvers by providing an n^omega + n^{2+1/4} time algorithm. We finally show how to apply similar ideas in the *non-convex* setting of deep learning. We provide both a theoretical result of a near-linear training algorithm for (overparametrized) neural networks, and an experimental application of LP techniques to speed up neural network training in practice.

CS frontpage, Public/media, Featured