Nonlinearity appears in many areas of machine learning (ML), such as deep learning, reinforcement learning, graphical models, and adversarial ML. Given the large-scale nature and complexity of ML problems, nonlinearity has often been handled by heuristic techniques. These methods are behind the major successes of artificial intelligence in the past decade, but they lack mathematical guarantees. This has limited the applications of these methods to safety-critical systems, such as power systems and transportation systems. In this talk, we develop a set of computational tools with mathematical guarantees for various nonlinear problems, with applications to ML and energy. First, we work through the notions of restricted isometry property (RIP) and spurious solutions to understand when the best (global) solution of a nonlinear learning or optimization problem can be found via local search techniques. We discuss the limitations of RIP and introduce a variant of this notion that can be applied to a much broader set of problems, formulated as matrix sensing over graphs. We demonstrate the results on the state estimation problem for power systems and show how much data should be collected to break down the complexity of the underlying learning problem in power systems. We then study the problem of learning a model under adversarial attacks on the data using the notion of graphical mutual incoherence, and as an example we use our results to design the first vulnerability map of the U.S. power grid.
