UC Berkeley

Within the realm of computational methods, there has been a long-standing trade-off between the scalability of different techniques and their optimality guarantees. However, most of today’s systems—such as transportation, power, and brain networks—are large-scale and safety-critical, thereby requiring both scalability and optimality guarantees. To address these challenges, in this dissertation we develop structure-aware, scalable, and guaranteed computational methods for the learning, optimization, and control of safety-critical systems.

In the first part of the dissertation, we consider two classes of machine learning problems, namely graphical model inference and robust matrix recovery. First, we provide a massively-scalable algorithm for the graphical model inference, where the goal is to reveal hidden correlation structures of high-dimensional datasets. We introduce a graph-based method that is capable of solving instances with billions of variables in less than an hour, significantly outperforming other state-of-the-art methods. Next, we consider a class of nonconvex and nonsmooth optimization problems in safe machine learning. We show that, despite their nonconvexity, a large class of problems in robust matrix recovery is devoid of spurious and sub-optimal solutions, thereby leading to the guaranteed success of fast local-search algorithms.

The second part of the dissertation is devoted to different classes of network optimization problems. In particular, we consider a class of generalized network flow problems that are at the backbone of many modern interconnected systems, such as power, water, and gas networks. Unlike many of its classical counterparts, the generalized network flow problem is highly nonconvex due to the incorporation of nonlinear losses in its formulation. To address this issue, we propose an efficient convex relaxation of the problem, and provide conditions under which the proposed relaxation is exact. Next, we focus on a specialized network optimization problem in power systems, namely optimal transmission switching, where the goal is to find the optimal topology of a power grid to minimize its cost of operation, while satisfying operational and security constraints in the network. The optimal transmission switching is a NP-hard optimization problem with mixed-integer variables. However, by exploiting the tree-like structure of realistic power grids, we introduce an strengthened formulation of the problem that can be solved efficiently in practice.

The third part of the dissertation is concerned with the design of robust and distributed control policies for dynamical systems with uncertain models. To this end, first we propose a sparsity-exploiting technique for the efficient learning of a structured dynamical system, based on a limited number of collected input-output sample trajectories from the system. In particular, we quantify the sample complexity of the sparse system identification problem in a high-dimensional setting, where the dimension of the system is significantly greater than the number of available data samples. Given the estimated dynamics, our next goal is to design a robust and distributed control policy for the system by taking into account the uncertainty of its estimated model. We show that near-optimal distributed controllers can be learned with logarithmic sample complexity and computed with near-linear time complexity.