Workshop on Distributed Learning and Multi-agent Learning:
Overview, Recent Results, and Open Problems

Abstract: We will overview the distributed optimization algorithms starting with the basic underlying idea illustrated on a prototype problem in machine learning. In particular, we will focus on convex minimization problem where the objective function is given as the sum of convex functions, each of which is known by an agent in a network. The agents communicate over the network with a task to jointly determine a minimum of the sum of their objective functions. The communication network can vary over time, which is modeled through a sequence of graphs over a static set of nodes (representing the agents in a system). In this setting, the distributed first-order methods will be discussed that make use of an agreement protocol, which is a mechanism replacing the role of a coordinator. We will discuss some refinements of the basic method and conclude with more recent developments of fast methods that can match the performance of centralized methods (up to a logarithmic factor).

Bio: Angelia Nedich has a Ph.D. from Moscow State University, Moscow, Russia, in Computational Mathematics and Mathematical Physics (1994), and a Ph.D. from Massachusetts Institute of Technology, Cambridge, USA in Electrical and Computer Science Engineering (2002). She has worked as a senior engineer in BAE Systems North America, Advanced Information Technology Division at Burlington, MA. Currently, she is a faculty member of the school of Electrical, Computer and Energy Engineering at Arizona State University at Tempe. Prior to joining Arizona State University, she has been a Willard Scholar faculty member at the University of Illinois at Urbana-Champaign. She is a recipient (jointly with her co-authors) of the Best Paper Award at the Winter Simulation Conference 2013 and the Best Paper Award at the International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) 2015. Her general research interest is in optimization, large scale complex systems dynamics, variational inequalities and games.

Abstract: We consider a standard federated learning architecture where a group of clients periodically coordinate with a central server to train a statistical model. We tackle two major challenges in federated learning:(i) objective heterogeneity, which stems from differences in the clients' local loss functions, and (ii) systems heterogeneity, which leads to slow and straggling client devices. Due to such client heterogeneity, we show that existing federated learning algorithms suffer from a fundamental speed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at a sub-linear rate, ie, fast convergence comes at the expense of accuracy. To address the above limitation, we propose FedLin-a simple, new algorithm that exploits past gradients and employs client-specific learning rates. When the clients' local loss functions are smooth and strongly convex, we show that FedLin guarantees linear convergence to the global minimum. We then establish matching upper and lower bounds on the convergence rate of FedLin that highlight the trade-offs associated with infrequent, periodic communication. Notably, FedLin is the only approach that is able to match centralized convergence rates (up to constants) for smooth strongly convex, convex, and non-convex loss functions despite arbitrary objective and systems heterogeneity. We further show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate.

Bio: Hamed Hassani is currently an assistant professor Electrical and Systems Engineering department at the University of Pennsylvania. Prior to that, he was a research fellow at Simons Institute for the Theory of Computing (UC Berkeley) affiliated with the program of Foundations of Machine Learning, and a post-doctoral researcher in the Institute of Machine Learning at ETH Zurich. He received a Ph.D. degree in Computer and Communication Sciences from EPFL, Lausanne. He is the recipient of the 2014 IEEE Information Theory Society Thomas M. Cover Dissertation Award, 2015 IEEE International Symposium on Information Theory Student Paper Award, 2017 Simons-Berkeley Fellowship, 2018 NSF-CRII Research Initiative Award, 2020 Air Force Office of Scientific Research (AFOSR) Young Investigator Award, 2020 National Science Foundation (NSF) CAREER Award, and 2020 Intel Rising Star Award

Abstract: The confluence of two powerful global trends - the rapid development of computational technology and the large amount of collected data - has enabled data-driven decision making in large-scale complex systems. Prominent examples include autonomous driving, robotics, data center, and manufacturing. The key challenge in these systems is in handling the vast quantities of information shared between the agents to find an optimal policy that maximizes or minimizes the agents’ objectives. This task needs to be done under computation and communication constraints. Among potential approaches, distributed algorithms, which is not only amenable to low-cost implementation but can also be implemented in real time, has been recognized as an important approach to address this challenge. In this talk, I will discuss about our recent work in developing distributed two-time-scale stochastic approximation for solving optimization problems over multi-agent systems under communication constraints. Two-time-scale stochastic approximation, a generalized version of the classic stochastic approximation, has broad applications in many areas, including stochastic optimization and reinforcement learning. We developed distributed two-time-scale stochastic gradient methods for solving networked optimization and show that our methods can handle both quantized communication and network latency. We provide an explicit formula to characterize the convergence rates of our methods as a function of network topology and communication capacity. I will conclude my talk with some discussion on the applications of two-time-scale methods in networked control and optimization.

Bio: Thinh T. Doan is an Assistant Professor in the Department of Electrical and Computer Engineering at Virginia Tech. Before joining Virginia Tech, he was a TRIAD postdoctoral fellow at Georgia Tech. He obtained his Ph.D. degree at the University of Illinois, Urbana-Champaign, his master degree at the University of Oklahoma, and his bachelor degree at Hanoi University of Science and Technology, Vietnam, all in Electrical Engineering. His research interests span on the intersection of control theory, optimization, machine learning, reinforcement learning, and applied probability theory.

Abstract: Recent years have witnessed significant advances in reinforcement learning (RL), which has registered tremendous success in solving various sequential decision-making problems in machine learning. Most of the successful RL applications today involve the participation of multiple agents, which naturally fall into the realm of multi-agent RL (MARL), a domain which has recently witnessed resurgence due to advances in single agent deep RL techniques. Even though empirically successful, theoretical foundations for MARL are relatively few in the literature, and their development constitutes exciting and promising avenues of research. This talk will provide a selective overview of decentralized MARL with networked agents, with focus on algorithms backed by theoretical analysis. In such a setting, multiple agents perform sequential decision-making in an environment common to them, and without the coordination of any central controller, while being allowed to exchange information with their neighbors over a communication network. Thus, each agent makes individual decisions based on both the information observed locally and the messages received from its neighbors over the underlying network, which could have a time-varying topology. In terms of the objectives of the agents, the presentation will cover fully cooperative and fully competitive behaviors, as well as a blend of the two, which captures a scenario where two teams of agents compete in a zero-sum game setting, while the agents within each team collaborate by exchanging information over the communication network. The general framework of decentralized MARL with networked agents has broad applications in diverse domains, such as control and operation of robots, unmanned vehicles, mobile sensor networks, and the smart grid.

Bio: Tamer Basar has been with the University of Illinois Urbana-Champaign since 1981, where he is currently Swanlund Endowed Chair Emeritus and Center for Advanced Study (CAS) Professor Emeritus of Electrical and Computer Engineering, with also affiliations with the Coordinated Science Laboratory, Information Trust Institute, and Mechanical Science and Engineering. At Illinois, he has also served as Director of CAS (2014-2020), Interim Dean of Engineering (2018), and Interim Director of the Beckman Institute (2008-2010). He received B.S.E.E. from Robert College, Istanbul, and M.S., M.Phil, and Ph.D. from Yale University, from which he received in 2021 the Wilbur Cross Medal. He is a member of the US National Academy of Engineering, and Fellow of IEEE, IFAC, and SIAM. He has served as president of IEEE CSS (Control Systems Society), ISDG (International Society of Dynamic Games), and AACC (American Automatic Control Council). He has received several awards and recognitions over the years, including the highest awards of IEEE CSS, IFAC, AACC, and ISDG, the IEEE Control Systems Award, and a number of international honorary doctorates and professorships. He has around 1000 publications in systems, control, communications, optimization, networks, and dynamic games, including books on non-cooperative dynamic game theory, robust control, network security, wireless and communication networks, and stochastic networked control. He was the Editor-in-Chief of Automatica between 2004 and 2014, and is currently editor of several book series. His current research interests include stochastic teams, games, and networks; multi-agent systems and learning; data-driven distributed optimization; epidemics modeling and control over networks; security and trust; energy systems; and cyber-physical systems.

Abstract: In this talk, we present some of our recent results in studying the performance of the gradient play algorithm for stochastic games (SGs), where each agent tries to maximize its own total discounted reward by making decisions independently based on current state information which is shared between agents. Policies are directly parameterized by the probability of choosing a certain action at a given state. We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting, and give a local convergence rate around strict NEs. Further, for a subclass of SGs called Markov potential games (which includes the cooperative setting with identical rewards among agents as an important special case), we design a sample-based reinforcement learning algorithm and give a non-asymptotic global convergence rate analysis for both exact gradient play and our sample-based learning algorithm. Local geometry and local stability are also considered, where we prove that strict NEs are local maxima of the total potential function and fully-mixed NEs are saddle points. Joint work with Runyu Zhang and Zhaolin Ren

Bio: Na Li is a Gordon McKay professor in Electrical Engineering and Applied Mathematics at Harvard University. She received her Bachelor degree in Mathematics from Zhejiang University in 2007 and Ph.D. degree in Control and Dynamical systems from California Institute of Technology in 2013. She was a postdoctoral associate at Massachusetts Institute of Technology 2013-2014. Her research lies in control, learning, and optimization of networked systems, including theory development, algorithm design, and applications to real-world cyber-physical societal system. She received NSF career award (2016), AFSOR Young Investigator Award (2017), ONR Young Investigator Award(2019), Donald P. Eckman Award (2019), McDonald Mentoring Award (2020), along with some other awards.

Abstract: The ability to learn is an essential aspect of autonomous systems facing uncertain and changing environments. However, the process of learning a new model or behavior often does not come for free, but involves a certain cost. For example, gathering informative data can be challenging due to physical limitations, or updating models can require substantial computation. Moreover, learning for autonomous agents often requires exploring new behavior and thus typically means deviating from nominal or desired behavior. Hence, the question of "when to learn?" is essential for the efficient and intelligent operation of autonomous systems. We have recently proposed the concept of event-triggered learning (ETL) for making principled decisions on when to learn new dynamics models. Building on the core idea of learning only when necessary, we haved developed concrete triggers and theory for different domains. In the context of networked and interconnected systems, ETL leads to superior communication savings over standard event-triggered control. For linear quadratic control, ETL automatically detects inaccurate models and yields improved control performance under changing dynamics. In this talk, we present the concept, theoretical results, and experimental applications of ETL.

Bio: Sebastian Trimpe is a Full Professor at RWTH Aachen University, where he heads the newly founded Institute for Data Science in Mechanical Engineering (DSME) since May 2020. Research as DSME focusses on fundamental questions at the intersection of control, machine learning, networks, and robotics. Before moving to RWTH, Sebastian was a Max Planck and Cyber Valley Research Group Leader at the Max Planck Institute (MPI) for Intelligent Systems in Stuttgart, Germany, where he keeps a side appointment at present. Sebastian obtained his Ph.D. degree in 2013 from ETH Zurich with Raffaello D’Andrea at the Institute for Dynamic Systems and Control. Before, he received a B.Sc. degree in General Engineering Science in 2005, a M.Sc. degree (Dipl.-Ing.) in Electrical Engineering in 2007, and an MBA degree in Technology Management in 2007, all from Hamburg University of Technology. In 2007, he was a research scholar at the University of California at Berkeley. Sebastian is recipient of the triennial IFAC World Congress Interactive Paper Prize (2011), the Klaus Tschira Award for achievements in public understanding of science (2014), the Best Demo Award of the International Conference on Information Processing in Sensor Networks (2019), and the Best Paper Award of the International Conference on Cyber-Physical Systems (2019).