First-order methods with optimal worst-case iteration complexities for various classes of convex optimization problems have been known for decades. However, their standard analysis bears little intuition, which makes their generalization to new problems arising in modern data analysis challenging. In this talk, I will present a novel general and unifying framework for the analysis of first-order methods. The framework relies on the construction of a primal-dual gap and can be likened to Lagrangian mechanics: continuous-time methods and their convergence analyses follow directly from enforcing a certain invariance. The discrete-time methods can then be obtained by using different methods of discretization. This stands in contrast with standard approaches, which can be thought of as being analogous to Newtonian mechanics, where an action (i.e., a predetermined optimization method) is applied to a system and then its behavior (convergence) analyzed. In the remainder of the talk, I will describe some of the generalizations and applications of this framework. I will also discuss how this invariance-based view can be generalized to the setting of convergence to stationary points in convex and non-convex optimization through a connection between the framework and Hamiltonian systems.

Recently, there has been an increasing interest in using tools from dynamical systems to analyze the behavior of simple optimization algorithms such as gradient descent and its accelerated variants. This talk will present differential equations and inclusions associated with various optimization algorithms (ADMM, Heavy ball, proximal splitting, and their accelerated variants) that are commonly used for solving unconstrained/constrained and smooth/non-smooth optimization problems. We use the direct method of Lyapunov to analyze the stability of critical points of the dynamical systems and to obtain associated convergence rates. We also derive new conformal, symplectic and relativistic algorithms emerging from conformal Hamiltonian systems. Joint work with Gui Franca and Daniel Robinson.

Stochastic optimization methods have been widely used in machine learning. However, the convergence analyses of many stochastic optimization methods for both convex and nonconvex optimization remain elusive. In this talk, I will show that continuous time dynamics can help us better understand stochastic optimization, derive new discrete-time algorithms based on various discretization schemes, and provide a unified and simple proof of convergence rates. More specifically, I will introduce a new framework based on stochastic differential equations to analyze accelerated stochastic mirror descent algorithms. Under this framework, we provide a Lyapunov function based analysis for continuous-time stochastic dynamics, as well as several new discrete-time algorithms derived from continuous time dynamics.

Many algorithms in machine learning are essentially just stochastic approximation methods, which are typically developed in a case-by-case manner. In this talk, we will present a unified control perspective on a large family of stochastic algorithms in machine learning. In the first half of the talk, we will focus on various algorithms used in supervised learning. Specifically, we will present an analysis routine for the so-called stochastic finite-sum methods including stochastic gradient descent (SGD), stochastic average gradient (SAG), SAGA, Finito, stochastic dual coordinate ascent (SDCA), stochastic variance reduction gradient (SVRG), and Katyusha momentum. In the second half of the talk, we will borrow the Markov jump linear system theory from the controls literature to analyze stochastic approximation algorithms in reinforcement learning. Specifically, we will tailor control tools to provide an exact analysis for temporal difference learning and its variants. We will conclude the talk with a few comments on future directions.

Most complicated optimization problems, in particular those involving a large number of variables, are solved in practice using iterative algorithms. The problem of selecting a suitable algorithm is currently more of an art than a science; a great deal of expertise is required to know which algorithms to try and how to properly tune them. Moreover, there are seldom performance guarantees. In this talk, I will show how the problem of algorithm selection can be approached using tools from robust control theory. By solving simple semidefinite programs (that are small, independent of problem size), we can derive robust bounds on convergence rates for popular algorithms such as the gradient method, proximal methods, fast/accelerated methods, and operator-splitting methods such as ADMM. The bounds derived in this manner either match or improve upon the best known bounds from the literature. The bounds also lead to a natural energy dissipation interpretation and an associated Lyapunov function. Finally, our framework can be used to search for algorithms that meet desired performance specifications, thus establishing a principled methodology for designing new algorithms.

In this talk, we study online linear quadratic regulators with a finite prediction window of the future cost functions and focus on regret analysis. Firstly, we provide a fundamental lower bound of dynamic regrets for any online algorithm. The lower bound decays exponentially with the prediction window’s length and increases linearly with the total variation of the tracking trajectory. In addition, we design an online algorithm and provide an upper bound of its dynamic regret. The upper bound almost matches the fundamental lower bound, implying that our algorithm achieves a near-optimal performance with respect to dynamic regrets. Finally, we conduct numerical experiments to demonstrate our results. Joint work with Yingying Li.

In robotics and complex systems, machine learning techniques have been instrumental for both improving estimates of unknown dynamics and for distilling information from high dimensional sensors such as cameras. This talk aims to provide rigorous guarantees for control systems with such learning-based components in closed loop. We show how to design robust controllers with the recently developed system level synthesis approach, which allows for handing uncertainties in a transparent way while e.g. satisfying safety constraints. With this framework, we are able to provide finite sample learning and performance guarantees for data-driven control, and use them to investigate trade-offs between safety and exploration in a principled way. Joint work with Nikolai Matni, Ben Recht, Stephen Tu, and Vickie Ye.

Among algorithmic techniques to design intelligent sequential decision making agents, learning-based approaches, such as reinforcement learning and imitation learning, have made rapid progress. These approaches have achieved impressive empirical successes in high-dimensional settings, especially those that can leverage low simulation cost and fast computation. Yet the path from these recent successes to many real-world applications remains elusive. Part of the disconnect stems from additional requirements introduced by real-world problems: data efficiency, safety, verifiability, etc. Looking ahead towards increasingly complex problem domains, it is important for new classes of methods to emerge that accommodate real-world constraints. In this talk, I will discuss methods that integrate policy learning with side constraints. Our framework largely takes a reduction-style approach that can naturally combine structural constraints with imitation learning, reinforcement learning and robust control techniques. Theoretically, a principled combination of structure and policy learning can yield better policy performance, faster learning, and certifiable properties. Empirically, I will also discuss several realistic applications of constrained policy learning.