Abstract: The area of data science lacks efficient computational methods with provable guarantees that can cope with the large-scale nature and the high nonlinearity of many real-world systems. Practitioners often design heuristic algorithms tailored to specific applications, but the theoretical underpinnings of these methods remain a mystery and this limits their usage in safety-critical systems. In this talk, we aim to address the above issue for some canonical data-driven problems.
First, we consider the graphical Lasso (GL), which is a popular optimization method for learning graphical models from data. GL is a conic optimization problem, which is perceived to be computationally challenging and there are numerous numerical methods in the literature but their computational complexities are at least cubic. By analyzing the properties of this conic problem, we show that its true complexity is indeed linear (both in time and in memory) for sparse graphical models. We solve instances with as many as 200,000 variables to 7-9 digits of accuracy in less than an hour on a standard laptop computer, while the existing solvers all stop working even for much smaller problems. We then study the related problem of finding the model of an unknown, but sparse, dynamical system from measurements and derive sharp bounds on the amount of data required to reliably identify the system (or design an optimal control policy).
In order to accelerate the computation, there is a major effort in the machine learning community to understand when simple local search algorithms could solve nonlinear problems to global optimality. A key proof technique relies on the notion of Restricted Isometry Property, whose conservatism is not well understood and cannot be applied to nonsmooth problems either (such as those involving 1-norm). We discuss our recent results on addressing these problems. In particular, we introduce the notion of “global functions”, as a major generalization of convex functions, which allows us to study the non-existence of spurious local minima for nonconvex and nonsmooth learning problems. We demonstrate the results on the tensor decomposition problem with outliers using 1-norm and local search algorithms. The talk is concluded by mentioning our participation in the ARPA-E $4M cash prize competition on Grid Optimization and how different techniques from optimization theory, numerical algorithms, graph theory, control theory, and machine learning could be used for this purpose.
Bio: Somayeh Sojoudi is an Assistant Professor in residence of the Departments of Electrical Engineering & Computer Sciences and Mechanical Engineering at the University of California, Berkeley. She is also on the faculty of the Tsinghua-Berkeley Shenzhen Institute (TBSI). She received her PhD degree in Control & Dynamical Systems from California Institute of Technology in 2013. She has worked on several interdisciplinary problems in optimization theory, control theory, machine learning, data analytics, and power systems. Somayeh Sojoudi is an Associate Editor of the journals of IEEE Transactions on Smart Grid, IEEE Access, and Systems & Control Letters. She is also a member of the conference editorial board of the IEEE Control Systems Society. She is a recipient of the 2015 INFORMS Optimization Society Prize for Young Researchers and a recipient of the 2016 INFORMS ENRE Energy Best Publication Award. She was a finalist (as advisor) for the Best Student Paper Award at the 2018 American Control Conference and a finalist (as a co-author) for the best student paper award at the 53rd IEEE Conference on Decision and Control 2014. Her paper on graphical models has received the INFORMS 2018 Data Mining Best Paper Award.
