New preprint: Robust stabilization!

I’m excited to share our new preprint on robust stabilization, by Saman Cyrus and myself. The title is “Generalized necessary and sufficient robust boundedness results for feedback systems”, and it is now available on arXiv. This work is the culmination of Saman’s PhD and formed the core of his thesis, which he recently successfully defended (!).

Robust stabilization is an old problem, dating back at least 70 years to the seminal work of Lur’e, Zames, and Willems. The basic idea is that a known system G is in feedback with an unknown nonlinearity H constrained to lie in some known set, and we seek sufficient conditions on G that ensure stability of the interconnection. In this work, we looked at the case where the nonlinearity is constrained to lie in a cone (also known as “sector-bounded”). Results of this type include: small-gain, circle, passivity, and extended conicity. It may be possible to extend our ideas to dynamic versions of robust stability (multiplier theory, dissipativity, or integral quadratic constraints), but this is an area for future work.

Robust stabilization results are typically formulated in the extended space L2e and can be expressed in a variety of ways, depending how which assumptions are made (causality, stability, linearity, time-invariance, etc.). Moreover, most of these results are only sufficient while some others are “necessary and sufficient”. Necessity can also mean two different things; when the conditions fail, can we construct worst-case signals only? Or can we also construct worst-case nonlinearities?

Our aim in this work was to disentangle the different formulations of these results and distill them into a single unified result that makes as few assumptions as possible. We worked with relations in an arbitrary semi-inner product space, which allowed us to avoid the notions of “causality”, “stability”, “time-invariance”, and “well-posedness”. In fact, we don’t even assume a notion of “time”! In this setting, we prove a very general necessary and sufficient condition for robust boundedness that requires essentially no assumptions. When our condition fails to hold, we show how to explicitly construct worst-case signals, and an associated worst-case nonlinearity. Moreover, our construction produces a nonlinearity that happens to be linear, which is nice.

Specializing our result to causal operators on L2e, this is what happens:

  1. When our condition fails, we can still construct worst-case signals. This works even when the plant G is nonlinear. Note: although the S-procedure can be used to prove this result, it would require assuming G is linear and would be non-constructive. We provide a direct construction and no linearity assumption is needed.
  2. The second step of our construction (constructing a worst-case nonlinearity) does not work in the L2e case because it typically produces a non-causal nonlinearity.
  3. By making additional assumptions, namely that G is LTI, we can construct worst-case nonlinearities that are causal. Our construction produces an LTI nonlinearity (in fact, a pure delay).
These results coincide with what was found in the literature. For example, the necessary-and-sufficient circle criterion of Vidyasagar assumes an LTI plant and constructs a worst-case nonlinearity using a pure delay. Also, the necessary-and-sufficient small gain theorem of Zhou, Doyle, and Glover assumes an LTI plant and constructs a worst-case LTI nonlinearity. In the case where G is LTI, we also provide frequency-domain and LMI flavors of our result.

Our work unifies existing results from the literature in the following way:

  1. Existing necessary-and-sufficient results are special cases of our general result.
  2. Existing sufficient-only results follow directly from our general necessary-and-sufficient condition once we apply the appropriate relaxations. We give examples in the text of how this works.

This turned out to be a very educational research project for both Saman and myself, on a rich and interesting topic, and I hope were able to do it justice! I also posted a Twitter thread summarizing the paper.

ACC’20 in Denver (online)

I attended the 2020 American Control Conference, which was supposed to take place in Denver, Colorado, but moved to a 100% online format as a precaution against COVID-19. I normally include a photo of the conference venue with these blog posts, but I don’t think anybody would be interested in seeing my home office setup so I’ll go with no photo this time!

At ACC, I presented a paper with Peter Seiler on the topic of using IQCs for algorithm synthesis. Iterative algorithms like gradient descent can be viewed as robust controllers. In robust control, we have an uncertain dynamical system we would like to control, and we assume the uncertainty is bounded. For example, we could have a mechanical or electrical system consisting of components that are subject to manufacturing tolerances and so we can’t know their exact parameters. Or perhaps their parameters change slowly over time as wear and tear sets in. The goal is to design a feedback controller that works for all systems in this bounded set. This robustness is desirable because if we build 100 identical robots, they won’t actually be identical. Using a robust controller means that we can design a single controller to use in all robots, and it will work even though the robots are not exactly identical. Optimization algorithms are very similar: we want to design an iterative optimization algorithm that works on a variety of different objective functions. The optimization algorithm plays the role of the controller and the objective function plays the role of the uncertain plant. In this paper, we showed how IQC synthesis tools from robust control theory can be used to design robust iterative algorithms.

This year, ACC experimented with a new type of presentation. Rather than the standard 20-minute talk, presenters were given the option to do 3-minute “rapid interactive” talks. I opted for this new format, and since all talks had to be pre-recorded, I’m happy to share with you my 3-minute talk explaining our paper! Here is a link to the video. My short talk was also awarded one of the inaugural “Rapid Interactive People’s Choice Awards”!

Overall, I the conference was very well run and I commend the organizers and staff for getting everything together under such difficult circumstances. I definitely miss the ability to meet with people face-to-face and the spontaneous encounters and discussions that happen at large conferences, but there are also advantages to an online format. There are no logistical/scheduling issues that arise from two talks happening at the same time. And the ability to pause a talk or watch it again later is very nice!

CDC’19 in Nice

I attended the 2019 Conference on Decision and Control in Nice, France. The photo above is a panoramic view of Nice taken from the top of Castle Hill. My research group had a solid showing at this year’s CDC with 3 papers. In no particular order, here are short summaries of each paper and a links to the slides for each talk.

  • “Integral quadratic constraints: Exact convergence rates and worst-case trajectories” with my postdoc Bryan Van Scoy. This paper considers the problem of robust stability; in a feedback interconnection where one of the components is uncertain (but the uncertainty is bounded), when can we guarantee that the interconnection will be stable? The most general robust stability result available is the IQC theorem of Megretski and Rantzer [[LINK]], which roughly states that robust stability can be established by checking the feasiblity of a particular linear matrix inequality (LMI). It is known that the result goes both ways: if the LMI is not feasible, then (at least in theory), there should exist some admissible choice of the uncertainty that will lead to instability. Bryan’s paper provides an explicit way of constructing such worst-case realizations by leveraging a theorem of strong alternatives for LMIs. This result is useful because it allows us to go beyond “could this system fail?”, and address the question “how could this system fail?”. Here are links to the paper and the slides from Bryan’s talk.
  • “Explicit agent-level optimal cooperative controllers for dynamically decoupled systems with output feedback” with my student Mruganka Kashyap. This paper considers a cooperative control problem where a group of agents (these could be robots, drones, etc.) attempt to solve a cooperative task under limited communication. In general, problems of this type are difficult to solve. However, solving simpler cases can provide useful intuition for what might work well in more general scenarios. In this work, we assumed the agents were “dynamically decoupled” and have linear dynamics. We also assume all disturbances are Gaussian and the global objective (which may couple the agents’ states and inputs) is quadratic. Previous work has shown that these assumptions ensure that the optimal strategy is a linear one and can be computed efficiently. Our contribution takes this a step further and elucidates the exact structure (down to the level of individual agents) that is used for optimal control. The optimal structure is reminiscent of the classical LQG structure: there is an “estimator”, a “compensator”, and a separation principle too! Here are links to the paper and the slides from Mruganka’s talk. Incidentally, this was Mruganka’s first talk at an international conference! See the photo on the right!
  • “Unified necessary and sufficient conditions for the robust stability of interconnected sector-bounded systems” with my student Saman Cyrus. The Lur’e problem is perhaps one of the most fundamental and well-studied examples of a robust control problem: assessing the stability properties of a known linear time-invariant plant in feedback with an unknown sector-bounded nonlinearity. This problem is is fundamental because many electrical, mechanical, and chemical systems (read: engineering systems!) are close to being linear. The departures from linearity often involve phenomena such as model errors, saturations, friction/stiction, or other hysteresis effects, which can often be well-modeled as sector-bounded nonlinearities. In the 60+ years of literature on this topic, various results have emerged: passivity theory, the small-gain theorem, the circle criterion, and more. Our paper presents an effort to unify these results (and their various incarnations) by using a very general mathematical framework. The benefit of our approach is that we can write a single robustness theorem that makes minimal assumptions yet can be specialized to recover many existing results. The advantage of having a single general theorem is that it allows us to derive new specializations! In our paper, we present one such new result: a necessary and sufficient condition for robust exponentially-weighted stability of Lur’e systems. Here are links to the paper and the slides from the talk.

One final highlight: I ran into my former PhD advisor, Sanjay Lall! Here is a photo of a small subset of my academic family: From left-to-right: Sanjay (my advisor), me, Bryan (my postdoc), and Mruganka (my student).

INFORMS’19 in Seattle

I attended the 2019 INFORMS Annual Meeting in Seattle, WA on Oct 20-23, 2019. INFORMS is the leading international association for Operations Research & Analytics professionals. It’s outside my wheelhouse, but I thought it would be nice to attend since Operations Research does touch on optimization, modeling, and data-driven decision-making, which are topics that interest me.

This was my first time attending an INFORMS conference and I was blown away by the sheer size and scope. There were well over 6,000 attendees and the conference had 100 simultaneous tracks over 4 full days. Compare this to CDC (the flagship annual controls conference), which is about 1/4 of the size.

At INFORMS, I gave two invited talks. The first was in a session organized by Jelena Diakonikolas, who will be my colleague at UW–Madison starting in Spring 2020! My talk was about the similarities and differences between discrete-time and continuous-time dynamical systems and how it relates to algorithm analysis. For example, notions of controllability/observability, stability regions, Lyapunov results, and more have direct analogs in discrete and continuous time. However, notions such as interval stability (e.g. Kharitonov’s theorem) or robust stability (e.g. Aizerman’s conjecture) are notably different in discrete and continuous time! My slides can be found here.

My second talk was in a session organized by Alireza Fallah, a PhD student in Asu Ozdaglar’s group at MIT. This talk was a short version of my talk on unified algorithm analysis and how small semidefinite programs can be used to automate the analysis and design of iterative optimization algorithms. For slides from a similar (but longer) version of this talk, see here.

Overall, I’m happy that I finally got to experience INFORMS. The two sessions I participated in were great (thanks Jelena and Alireza!). I think it’s a particularly nice conference to meet with industry contacts, since there is a substantial industry presence at this conference. That being said, I found it quite overwhelming at times because there were so many talks happening all at once. There is something to be said about smaller venues (see my recent NecSys and Allerton posts!) because the conferences tend to be more cohesive and it’s easier to find your friends when the venue isn’t the size of an airport!


I attended the 57th annual Allerton Conference on Communication, Control, and Computing in Monticello, IL. At the conference, I presented an invited talk in a session organized by Bin Hu, my former postdoc who is now at UIUC — so it was nice to see Bin again!

My talk was largely about the following recent paper (arxiv link) by my student Akhil Sundararajan, my postdoc Bryan Van Scoy, and me. The manuscript should get published at some point in 2020 once we make our final revisions. The paper describes how gradient-based distributed optimization algorithms can be parameterized and analyzed (in terms of their worst-case convergence rate) using simple semidefinite programs. In the paper, we study the case where the underlying graph is possibly time-varying (with uniformly bounded spectral gap), and we characterize the worst-case performance under any adversarially-varying graph. The benefit of this approach is that it enables rapid analysis, which means it also enables efficient design! Our paper also presents an “optimal” algorithm design (optimal in the sense that it has the fastest worst-case convergence rate) and a comparison between this algorithm and existing algorithms from the literature. Finally, we show that our approach likely produces tight bounds because we can construct worst-case sequences of graphs and functions that achieve the bound.

NecSys’19 in Chicago

I attended the 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems (NecSys) in Chicago on September 16-17, 2019. NecSys is a small international single-track conference that tends to attract optimization/controls/distributed systems researchers. The last time I attended NecSys was in 2012 (in Santa Barbara) while I was still a postdoc, and I have fond memories of it. It was nice for NecSys to be local again this year, as it meant that I could bring most of my research group along!

At the conference, Bryan presented a poster on his recent distributed optimization work (arxiv link). In this work, Bryan showed that near-optimal gradient-based distributed optimization algorithms can be designed by alternating between simple gradient steps and gossip steps. In the paper, Bryan shows how to tune the ratio of gradient to gossip steps based on the spectral gap of the adjacency matrix of the underlying communication graph (a measure of how “connected” the graph is) in order to achieve the fastest possible convergence rate.

On a personal note, I had the opportunity at NecSys to reconnect with my former PhD advisor Sanjay Lall and my former postdoc advisor Ben Recht (first photo). The fact that NecSys was local also led to a little road trip back to Madison with my students Mruganka, Saman, and Akhil! We stopped for dinner in “Little India”, which is a neighborhood filled with Indian and Pakistani restaurants and shops in a suburb north of Chicago. Akhil guided us to some traditional Chaat (second photo) and it was delicious!

ACC’19 in Philadelphia

I attended the 2019 American Control Conference in Philadelphia, Pennsylvania. The conference was held in downtown Philadelphia, which is filled with beautiful historical buildings, such as the Union League building, pictured on the right.

This was a conference of firsts. Together with my former postdoc Bin Hu, who is now faculty at UIUC, I co-organized my first ACC workshop! Here is a link to the workshop website. It was a full-day workshop on the interplay between optimization, control, and machine learning. Our morning session focused on how tools from controls, differential equations, and dynamical systems could be used to better analyze and design first-order optimization algorithms, which are a key tool in machine learning. Our afternoon session focused on how ideas from machine learning, reinforcement learning, and complexity theory could be used to address large-scale and computationally challenging control problems. We were lucky to have many great speakers, and our workshop was the most popular one at ACC this year — check out the full room on the right! If you’re interested in these topics, the workshop website linked contains info for all the talks that took place (authors, titles, and slides!).

In addition to the workshop, my student Akhil Sundararajan and postdoc Bryan Van Scoy joined me at ACC and Akhil presented a paper by the three of us titled: “A canonical form for first-order distributed optimization algorithms”. In distributed optimization, the goal is for a number of agents (computer servers, robots, mobile phones, etc.) to jointly solve an optimization problem. The problem is global, but the data collection and processing happens locally. The challenge is to design an algorithm that mediates how each agent processes its local data and what is communicated with the other agents so that each agent eventually learns the solution to the global problem. There have been many such algorithms proposed in recent years, but little insight on what makes one algorithm better than another, or how to go about actually designing such an algorithm. To make matters more confusing, there are many equivalent sets of equations that can be used to describe the same algorithm. So it might happen (and it has!) that two researchers invent the same algorithm without realizing it. Our paper makes an effort to classify distributed algorithms, by providing a canonical form that uses as few parameters as possible yet parameterizes a broad class of algorithms (including many existing published algorithms). Our unifying parameterization is a first step toward a more systematic and principled analysis and design of distributed optimization algorithms.

My student Akhil, who is also first author on the paper, presented our work. As a side note, this was Akhil’s first conference presentation, and he did a fantastic job! (see photo on the right). If you’re interested in seeing Akhil’s slides, you can download them here.

L4DC’19 at MIT

I had the pleasure to attend the inaugural Conference on Learning for Dynamics and Control at MIT. The goal of this new conference is to bring together researchers at the interface between machine learning, control, optimization, and related areas, with a focus on addressing scientific and application challenges in real-time physical processes modeled by dynamical or control systems. The conference format is still in flux, but this year’s version was a single-track format with diverse high-profile speakers presenting on a range of topics including: model-predictive control, deep learning, simulating dynamical systems, robotics, traffic systems, and more. There was also two excellent poster sessions. Overall, the conference was a huge success. Over 400 people attended, and all on very short notice! Only about 3 months elapsed between when the idea of this conference was conceived and when the conference actually occurred.

My two highlights of the conference were: (1) Getting to see all the Berkeley folks I knew through my postdoc but haven’t had much of a chance to interact with since then. Many any of them are now moving on to exciting careers in academia and industry. (2) Having the opportunity to meet Alexandre Megretski for the first time and chat about robust control and IQCs. Megretski wrote some of the seminal work in these areas and it was an honor to meet him in person.

Kudos to the organizers (Ali Jadbabaie, George Pappas, Pablo Parrilo, Ben Recht, and Melanie Zellinger) for putting together such an amazing conference on such short notice! I’m looking forward to attending again next year!

8th Midwest Workshop on Control and Game Theory

I recently attended the 8th Midwest Workshop on Control and Game Theory hosted by the University of Washington in St. Louis. The two-day workshop brought together faculty, postdocs, and grad students in the fields of controls, optimization, game theory, and economics. This was my first time visiting Wash U, and it’s a beautiful campus! The buildings are all built of sandstone, and it reminds me of Queen’s University in Kingston, Canada.

I quite like smaller workshop formats such as this one, so much less hectic than the large conferences I attend like CDC or ICML. It’s also nice to meet and network with other researchers in the Midwest!

At the workshop, I have a 30-minute talk on using a robust controls perspective to analyzing and designing optimization algorithms. The video of my talk is available on YouTube.

CDC’18 in Miami Beach

I attended the 2018 Conference on Decision and Control in Miami Beach, Florida. A welcome change of weather from the looming winter in Madison! The photo above was taken from the terrace of the conference venue.

At the conference, I took part in the Workshop on the Intersections of Machine Learning and Parameter Estimation in Control organized by Travis Gibson, Joseph Gaudio, and Anuradha Annaswamy of MIT. This general field at the intersection of machine learning, optimization, and control seems to be gaining momentum. Indeed, there was another workshop on very similar topics that was held concurrently and it was a shame I couldn’t attend both!

I’ll point out two highlights of the conference. Besides attending sessions on robust control, distributed optimization, decentralized control, and machine learning, I also strayed outside my comfort zone and attended a tutorial session on “Control-Theoretic Methods for Biological Networks”. A growing group of controls researchers have taken interest in biological systems, and I have to say I was both impressed at the progress in this field and humbled at how much there is left to do. Biological systems are incredibly complex and it seems the only way to advance the ball (and to be taken seriously) in this area is to work at the problem from both sides: performing biological experiments in a wet-lab environment and doing some serious mathematical modeling and analysis. I thought Hana El-Samad (UCSF) and Eduardo Sontag (Northeastern) both gave very insightful presentations.

The second highlight was a special session commemorating the life and contributions of Bruce Francis to the field of robust control. Bruce passed away in March of this year and it was nice to see so many people (standing room only) come to celebrate his life and accomplishments at CDC. Bruce’s (arguably) biggest contribution was in developing a state-space solution for the H-infinity control problem. The famous “DGKF” paper is among the most highly-cited papers in the field. The other three co-authors (Doyle, Glover, and Khargonekar) were all in attendance and shared some heartfelt words. The first photo on the right was taken during the CDC special session; John Doyle was recounting some of the initial (mixed) reactions to the DGKF paper, including some choice quotes (see the slide!). The first (and last) time I met Bruce Francis was at the Caltech CDS20 workshop five years ago. Incidentally, all four authors of DGKF were present at that event (see second photo on the right — authors are in the DGKF order!). Although Bruce and I had just met, we bonded over the fact that we are both Canadian, and we both enjoy playing Frisbee! Bruce was also a Professor at the University of Toronto, which is where I did my undergrad. Bruce was soft-spoken, kind, and humble — sentiments echoed by many of his colleagues at CDC this year. He will be missed.

This year’s Bode lecture was delivered by Mark Spong of UT Dallas. The topic was robotics, an area that is not really in my wheelhouse, but I thought Mark did a wonderful job of explaining some basic tools and challenges from the field. What amazed me from the presentation was how simple passivity-based control can be used to create very natural-looking movement patterns that are robust to disturbances. Mark showed examples of a self-righting inverted pendulum and various walking robots, all of which were designed using energy conservation principles. If you’re looking for a well-delivered introductory lecture on robotics, I highly recommend this one! The lecture was recorded and should be posted online here soon.