Efficient Computational Methods for Large-Scale Safety-critical Systems

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 investigate the above issue for some canonical data-driven problems with connections to optimization and control theory. We consider the graphical Lasso which is a popular optimization method for learning graphical models from data. By analyzing the properties of this problem, we show that its true computational complexity is indeed linear for sparse graphical models, which enables designing new algorithms for this problem to be able to solve large-scale learning problems efficiently. Second, we study the problem of solving nonlinear optimization problems efficiently using low-complexity methods. Nonlinearity is ubiquitous in control theory and more recently has played a major role in deep learning and artificial intelligence. We discuss the recent advances in this area and in particular study the low-rank matrix recovery problems which arise in various complex systems.