Workshop "Vistas in Control" September 10-11, 2018

Seminar: Event-driven and Data-driven Control and Optimization in Cyber-physical Systems 

Abstract:
This presentation will focus on two new major directions in the evolution of systems and control theory. The first is the emergence of the event-driven paradigm as an alternative viewpoint, complementary to the time-driven approach, for modeling, sampling, estimation, control, and optimization of dynamic systems that can provide dramatic energy savings in networked settings among other advantages. The second is the ubiquitous availability of data for both off-line and on-line processing. This opens up new opportunities for data-driven control and optimization methods that combine analytical system models with data. We will describe a general framework for event-driven and data-driven optimization that applies to Cyber-Physical Systems (CPS) with applications to cooperative multi-agent systems and to "smart cities".

Seminar: Least Squares Optimal Identification of LTI SISO Dynamical Models is an Eigenvalue Problem

Abstract:
The last 50 years, we have witnessed tremendous progress in model-based control design and applications. Both the solution to the steady state LQR problem and the Kalman filter, ultimately reduce to an eigenvalue problem (which is hidden in the matrix Riccati equations involved). The same observation applies to the H-infty framework, with different Riccati equations. 

But what about the models? Are they optimal in any sense, as often they are obtained from some non-linear optimization method? We will show how least squares optimal models for LTI SISO systems, derive from an eigenvalue problem, hence achieving an important landmark on optimal identification for this type of models. We focus on LTI SISO models, with at most one observed input and/or output data record, and at most one "unobserved" (typically assumed to be white) noise input (called "latency"). In the most general case, also the inputs and outputs are corrupted by additive measurement noise (called ‘misfit’). This class of models covers a lot of special cases, like AR, MA, ARMA, ARMAX, OE (Output-Error), Box-Jenkins, EIV (Errors-in-Variables), dynamic total least squares, and also includes models that up to now have not been described in the literature.

The results we will elaborate on, are the following:

• Firstly, we show that, using Lagrange multipliers, the least squares optimal model parameters, and the estimated latency and noise sequences, constitute a stationary point of the derivatives of the Lagrangean, which is equivalent to a (potentially large) set of multivariate polynomials. One (or some) of these stationary points provide the global minimum.
• We show that all stationary points of such multivariate polynomial optimization problems, correspond to the eigenvalues of a multi-dimensional (possibly singular) autonomous (nD-)shift invariant dynamical system.
• These eigenvalues can be obtained numerically by applying nD-realization theory in the null space calculated from a so-called Macaulay matrix. This matrix is built from the data, is a highly structured, quasi-Toeplitz matrix and in addition sparse. Revealing the number of stationary points that are finite, their structure and the solutions at infinity, requires a series of rank tests (SVDs) and eigenvalue calculations.
• We show how the parameters of the models are the eigenvalues of a multi-valued eigenvalue problem, and the estimated misfit and latency sequences are (parts) of corresponding eigenvectors. The implication is a serious reduction in computational complexity.
• Finally, we show how also this multi-valued eigenvalue problem ultimately reduces to an ‘ordinary’ (generalized) eigenvalue problem (i.e. in one variable, which is e.g. the minimal value of the least squares objective function).
  
  Our results put many identification methods that have been described in the signal processing and identification literature, in a new perspective (think of VARPRO, IQML, "noisy" realization, PEM (Prediction-Error-Methods), Riemannian SVD, ….): all of them generate (often very good) "heuristic" algorithms, but here for the first time, we will show how all of them in fact are heuristic attempts to find the minimal eigenvalue of a large matrix.
  
  The algorithms we come up with are guaranteed to find the global minima, using the well understood machinery of eigenvalue solvers and singular value decomposition algorithms. We will elaborate on the computational challenges (e.g. the fact that we only need to compute one eigenvalue-eigenvector pair of a large matrix, namely the one corresponding to the global optimum).
  
  We will also elaborate on some preliminary system theoretic interpretations of these results (e.g. that misfit and latency error sequences are also highly structured in a system theoretic sense), and on some ideas on how to incorporate a priori information (e.g. power spectra) into these methods.
  

Seminar: Brain-inspired non-von Neumann Computing

Abstract: 
In today’s computing systems based on the conventional von Neumann architecture, there are distinct memory and processing units. Performing computations results in a significant amount of data being moved back and forth between the physically separated memory and processing units. This costs time and energy, and constitutes an inherent performance bottleneck. This has triggered research efforts to unravel and understand the highly efficient computational paradigm of the human brain, with the aim of creating brain-inspired computing systems. IBM with its fully digital TrueNorth chip architecture reached a key milestone in mimicking neural networks “in silico”. Besides fully digital approaches, also analog and hybrid architectures are being investigated.

Most recently, post-silicon nanoelectronic devices with memristive properties are also finding applications beyond the realm of memory. It is becoming increasingly clear that for application areas such as cognitive computing, we need to transition to computing architectures in which memory and logic coexist in some form. Brain-inspired neuromorphic computing and the fascinating new area of in-memory computing or computational memory are two key non-von Neumann approaches being researched. A critical requirement in these novel computing paradigms is a very-high-density, low-power, variable-state, programmable and non-volatile nanoscale memory device. Phase-change-memory (PCM) devices based on chalcogenide phase-change materials, such as Ge2Sb2Te5, are well suited to address this need owing to their multi-level storage capability and potential scalability.

Spiking neural networks (SNNs) are considered by many as the third-generation neural networks. It is widely believed that SNNs are computationally more powerful because of the added temporal dimension. PCM devices could emulate neuronal and synaptic dynamics. Such phase-change neurons also exhibit an intrinsic stochasticity and can thus be used for the representation of high-frequency signals via population coding. In general, such phase-change neurons and synapses can be used to realize SNNs and associated learning rules in a highly efficient manner. I will present some recent theoretical results and experimental demonstrations of large-scale spiking neural networks realized using PCM-based neurons and synapses.

In-memory computing is another brain-inspired non-Neumann approach. In in-memory computing, the physics of nanoscale memory devices as well as the organization of PCM devices in crossbar arrays are exploited to perform certain computational tasks within the memory unit. I will present large-scale experimental demonstrations using about one million PCM devices organized to perform high-level computational primitives, such as compressed sensing, linear solvers and temporal correlation detection. Moreover, I will discuss the efficacy of this approach to efficiently address the training and inference of deep neural networks. The results show that this co-existence of computation and storage at the nanometer scale could be the enabler for new, ultra-dense, low-power, and massively parallel computing systems.

Seminar: Temporal Logics for Multi-Agent Systems

Abstract:
Temporal logic formalizes reasoning about the possible behaviors of a system over time. For example, a temporal formula may stipulate that an occurrence of event A may be, or must be, followed by an occurrence of event B. Traditional temporal logics, however, are insufficient for reasoning about multi-agent systems such as control systems. In order to stipulate, for example, that a controller can ensure that A is followed by B, references to agents, their capabilities, and their intentions must be added to the logic, yielding Alternating-time Temporal Logic (ATL). ATL is a temporal logic that is interpreted over multi-player games, whose players correspond to agents that pursue temporal objectives. The hardness of the model-checking problem -whether a given formula is true for a given multi-agent system- depends on how the players decide on the next move in the game (for example, whether they take turns, or make independent concurrent decisions, or bid for the next move), how the outcome of a move is computed (deterministically or stochastically), how much memory the players have available for making decisions, and which kind of objectives they pursue (qualitative or quantitative). The expressiveness of ATL is still insufficient for reasoning about equilibria and related phenomena in non-zero-sum games, where the players may have interfering but not necessarily complementary objectives. For this purpose, the behavioral strategies (a.k.a. policies) of individual players can been added to the logic as quantifiable first-order entities, yielding Strategy Logic. We survey several known results about these multi-player game logics and point out some open problems.

Seminar: Understanding Acceleration and Escape from Saddle Points in first-order Optimization
 

Abstract:
In the first part of the talk, I focus on studying gradient-based optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) corresponding to gradient dynamics with mass and friction. When the function is smooth enough, we show that acceleration can be achieved by a stable discretization of this ODE using standard Runge-Kutta integrators. Specifically, we show under Lipschitz-gradient and convexity the sequence of iterates generated by discretizing the proposed second-order ODE achieves acceleration, without any need for specialized integration schemes.
Furthermore, we introduce a new local flatness condition on the objective, under which rates even faster than O(1/N^2) can be achieved with low-order integrators and only gradient information. Notably, this flatness condition is satisfied by several standard loss functions used in machine learning.

In the second part of the talk, I focus on escaping from saddle points in smooth nonconvex optimization problems subject to a convex constraint. We propose a generic framework that yields convergence to a second-order stationary point (SOSP) of the problem if the constraint set $C$ is simple for a quadratic objective function. To be more precise, our results hold if one can solve a quadratic program over the set $C$ up to a constant factor. Under this condition, we show that the sequence of iterates generated by the proposed method reaches an SOSP in poly-time. We further characterize the overall arithmetic operations to reach an SOSP when the convex set $C$ can be written as a set of quadratic constraints. Finally, we extend our results to the stochastic setting and characterize the number of stochastic gradient and Hessian evaluations required to reach an SOSP.

Seminar: Reinforcement Learning for Unknown Autonomous Systems
 

Abstract:
System Identification followed by control synthesis has long been the dominant paradigm for control engineers. And yet, many autonomous systems must learn and control at the same time. Adaptive Control Theory has indeed been motivated by this need. But it has focused on asymptotic stability while many contemporary applications demand finite time (non-asymptotic) performance optimality. Results in stochastic adaptive control theory are sparse with any such algorithms being impractical for real-world implementation. We propose Reinforcement Learning algorithms inspired by recent developments in Online (bandit) Learning.

Two settings will be considered: Markov decision processes (MDPs) and Linear stochastic systems. We will introduce a posterior-sampling based regret-minimization learning algorithm that optimally trades off exploration v. exploitation and achieves order optimal regret. This is a practical algorithm that obviates the need for expensive computation and achieves non-asymptotic regret optimality. I will then talk about a general non-parametric stochastic system model on continuous state spaces. Designing universal control algorithms (that work for any problem) for such settings (even with known model) that are provably (approximately) optimal has long been a very challenging problem in both Stochastic Control and Reinforcement Learning. I will propose a simple algorithm that combines randomized function approximation in universal function approximation spaces with Empirical Q-Value Learning which is not only universal but also approximately optimal with high probability. In closing, I would like to argue that the problems of Reinforcement Learning present a new opportunity for Controls and some interesting future directions.  

Seminar: Fastest Convergence for Reinforcement Learning

Abstract:
There are two well known Stochastic Approximation techniques that are known to have optimal rate of convergence (measured in terms of asymptotic variance): the Stochastic Newton-Raphson (SNR) algorithm [a matrix gain algorithm that resembles the deterministic Newton-Raphson method], and the Ruppert-Polyak averaging technique. This talk will present new applications of these concepts for reinforcement learning.

1. Introducing Zap Q-Learning. In recent work, first presented at NIPS 2017, it is shown that a new formulation of SNR provides a new approach to Q-learning that has provably optimal rate of convergence under general assumptions, and astonishingly quick convergence in numerical examples. In particular, the standard Q-learning algorithm of Watkins typically has infinite asymptotic covariance, and in simulations the Zap Q-Learning algorithm exhibits much faster convergence than the Ruppert-Polyak averaging method. The only difficulty is the matrix inversion required in the SNR recursion.

2. A remedy is proposed based on a variant of Polyak’s heavy-ball method. For a special choice of the “momentum" gain sequence, it is shown that the parameter estimates obtained from the algorithm are essentially identical to those obtained using SNR. This new algorithm does not require matrix inversion. In simulations it is found that the sample paths of the two algorithms couple. A theoretical explanation for coupling is established for linear recursions.

Along with these new results, the talk will survey and unify popular approaches to deterministic optimization that form the foundation of this work. 

Seminar: Exploiting Sparsity in Semidefinite and Sum of Squares Programming

Abstract:
Semidefinite and sum of squares optimization have found a wide range of applications, including control theory, fluid dynamics, machine learning, and power systems. In theory they can be solved in polynomial time using interior-point methods. However, these methods are only practical for small- to medium- sized problem instances.

For large instances, it is essential to exploit or even impose sparsity and structure within the problem in order to solve the associated programs efficiently. In this talk I will present recent results on the analysis and design of networked systems, where chordal sparsity can be used to decompose the resulting SDPs, and solve an equivalent set of smaller semidefinite constraints. I will also discuss how sparsity and operator-splitting methods can be used to speed up computation of large SDPs and introduce our open-source solver CDCS. Lastly, I will extend the decomposition result on SDPs to SOS optimization with polynomial constraints, revealing a practical way to connect SOS optimization and DSOS/SDSOS optimization for sparse problem instances.

Seminar: Multi-agent distributed optimization over networks and its application to energy systems

Abstract:

The well-functioning of our modern society rests on the reliable and uninterrupted operation of large scale complex infrastructures, which are more and more exhibiting a network structure with a high number of interacting components/agents. Energy and transportation systems, communication and social networks are a few, yet prominent, examples of such large scale multi-agent networked systems. Depending on the specific case, agents may act cooperatively to optimize the overall system performance or compete for shared resources. Based on the underlying communication architecture, and the presence or not of a central regulation authority, either decentralized
or distributed decision making paradigms are adopted.

In this talk, we address the interacting and distributed nature of cooperative multi-agent systems arising in the energy application domain. More specifically, we present our recent results on the development of a unifying distributed optimization framework to cope with the main complexity features that are prominent in such systems, i.e.: heterogeneity, as we allow the agents to have different objectives and physical/technological constraints; privacy, as we do not require agents to disclose their local information; uncertainty, as we take into account uncertainty affecting the agents locally and/or globally; and combinatorial complexity, as we address the case of discrete decision variables.

This is a joint work with Alessandro Falsone, Simone Garatti, and Kostas Margellos.

Seminar: Time Series As A Matrix

Abstract:
We consider the task of interpolating and forecasting a time series in the presence of noise and missing data. As the main contribution of this work, we introduce an algorithm that transforms the observed time series into a matrix, utilizes matrix estimation as a black-box to simultaneously recover missing values and de-noise observed entries, and performs linear regression to make predictions. We argue that this method provides meaningful imputation and forecasting for a large class of models: finite sum of harmonics (which approximate stationary processes), non-stationary sub-linear trends, Linear-Time-Invariant (LTI) systems, and their additive mixtures. In general, our algorithm recovers the hidden state of dynamics based on its noisy observations, like that of a Hidden Markov Model (HMM), provided the dynamics obey the above stated models. As an important application, it provides a robust algorithm for "synthetic control'' for causal inference.

This is based on joint works with Anish Agarwal, Muhammad Amjad and Dennis Shen (all at MIT).

Seminar: The Information Knot Tying Sensing and Control and the Emergence Theory of Deep Representation Learning

Abstract:
Internal representations of the physical environment, inferred from sensory data, are believed to be crucial for interaction with it, but until recently lacked sound theoretical foundations. Indeed, some of the practices for high-dimensional sensor streams like imagery seemed to contravene basic principles of Information Theory: Are there non-trivial functions of past data that ‘summarize’ the ‘information’ it contains that is relevant to decision and control tasks? What ‘state’ of the world should an autonomous system maintain? How would such a state be inferred? What properties should it have? Is there some kind of ‘separation principle’, whereby a statistic (the state) of all past data is sufficient for control and decision tasks? I will start from defining an optimal representation as a (stochastic) function of past data that is sufficient (as good as the data) for a given task, has minimal (information) complexity, and is invariant to nuisance factors affecting the data but irrelevant for a task. Such minimal sufficient invariants, if computable, would be an ideal representation of the given data for the given task. I will then show that these criteria can be formalized into a variational optimization problem via the Information Bottleneck Lagrangian, and minimized with respect to a universal approximating class of function realized by deep neural networks. I will then specialize this program for control tasks, and show that it is possible to define and compute a ‘state’ that separates past data from future tasks, and has all the desirable properties that generalize the state of dynamical models customary in linear control systems, except for being highly non-linear and having high-dimension (in the millions).

References:
external page https://arxiv.org/pdf/1706.01350.pdf (JMLR 2018) and external page https://arxiv.org/abs/1710.11029 (ICLR 2018). external page https://www.annualreviews.org/doi/pdf/10.1146/annurev-control-060117-105140 (Annual Reviews 2018)

Joint work with Alessandro Achille and Pratik Chaudhari.

Seminar: Approximate MPC for Feedback Control through Contact
 

Abstract:  

For robots governed by smooth, controllable (possibly nonlinear) ODEs, linear MPC provides an extremely powerful tool for local stabilization of a fixed point or trajectory. The state of the art in multi-contact feedback control is much worse — we mostly rely on one-step lookahead (e.g. QP inverse dynamics) and or hand-designed state machines — the major missing piece is a systematic design procedure that can reason about stabilization “across contact modes”. As a result, legged robots struggle to recover from deviations from their pre-planned hybrid mode sequence, and there is an embarrassing paucity of feedback control theory to be found in the field of robot manipulation.

In this talk, I will argue that piecewise-affine (PWA) approximations of the system dynamics in floating-base coordinates are the natural and reasonable analog to linearization when locally stabilizing fixed-points or trajectories that lie on or near contact-mode boundaries. For these models, well-known results from explicit MPC tell us quite a bit about the feedback controller that optimizes a quadratic regulator objective (although it is not as nice as the affine case). The problem is primarily that the number of pieces quickly becomes too large for even moderately-sized problems. I will present a number of algorithms that we have been developing to efficiently compute the mixed-integer convex optimization problems that result from formulations like the piecewise-affine quadratic regulator (PWAQR), including some new tightness results leveraging disjunctive programming. I will also algorithms that approximate the explicit MPC solution, and discuss the prospects of actually having a turnkey solution that is anywhere near as powerful as LQR for smooth systems.

Seminar: Cyber-physical Manufacturing Systems: Improving Productivity with Advanced Control

Abstract:
High-performance computing technologies, including high-speed networks, high-performance simulations, high-speed networks, and cloud computing, are revolutionizing manufacturing systems operations. Using existing hardware (robots, CNC machines, conveyors), but taking advantage of the vast amounts of data being collected in real-time, advanced control techniques can result in reduced downtime, improved quality, and overall improved productivity. This talk will describe how the integration of simulation and plant-floor data can enable new control approaches that are able to optimize the overall performance of manufacturing system operations. Both hierarchical and distributed control approaches will be discussed, and implementations on a testbed at the University of Michigan will be described. Collaborations with industry will be highlighted.

Seminar: Global Optimality in Matrix Factorization, Tensor Factorization and Deep Learning
 

Abstract:
The past few years have seen a dramatic increase in the performance of recognition systems thanks to the introduction of deep networks for representation learning. However, the mathematical reasons for this success remain elusive. A key issue is that the neural network training problem is non-convex, hence optimization algorithms may not return a global minima. In addition, the regularization properties of algorithms such as dropout remain poorly understood. Building on ideas from convex relaxations of matrix factorizations, this work proposes a general framework which allows for the analysis of a wide range of non-convex factorization problems – including matrix factorization, tensor factorization, and deep neural network training. The talk will describe sufficient conditions under which a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a local descent algorithm. The talk will also present an analysis of the optimization and regularization properties of dropout in the case of matrix factorization.