The project aims to develop novel mathematical and computational tools for the design of algorithms learning the structure, the dynamics, and the control of large-scale networks.
Many complex systems, whether biological, physical, social, or economical, are structured in networks consisting of a large collection of interacting entities. Some of these networks, such as social networks on the Internet emerge without our control or intervention. As a consequence, their structure, the way their entities interact and evolve are a priori unknown. Some are de signed and deployed by engineers, but their scale may become so large (this is for instance the case of future mobile networks) that their individual entities cannot be finely tuned when deployed, and again the structure of the network and the interactions between its entities can not be predicted. Our ability to optimize the operation of a network however strongly relies on an accurate knowledge of its characteristics.
In this project, we will develop novel mathemat ical and computational tools to devise efficient algorithms learning the network structure and dynamics, as well as efficient ways to control it. This vast and ambitious objective calls for a multidisciplinary effort, and we envision to reach it leveraging and combining techniques from probability theory, statistical machine learning, and control theory.
Two application domains play an important role in the NEST, and provide the scientific questions driving our research. The first domain explored together with Ericsson is that of radio communication systems. The second application domain is that of intermediation platforms (e.g., e-commerce systems, search engines, recommender systems).
Long-term Impact
The project will enhance our fundamental understanding of learning and control tasks in networks. Such tasks are key enablers for future technologies deployed on largescale networks such as communication networks, social networks, power grids, and transportation systems. The project will hence be hopefully of great benefit for Swedish industry and society at large.
Research efforts in the domain of networked systems tend to focus on either structural and topological properties of networks, or on identifying and defining dynamical system properties without accounting for topological structures. This project focuses on inference of both structure and dynamics will enable novel fundamental insights to systems, such communication networks and intermediation platforms, where structure and dynamics are inherently intertwined.
The grand challenge of the project is to develop a comprehensive theory of learning in networks that identifies fundamental limits to this learning and devises efficient algorithms approaching these limits. We distinguish learning problems depending on the initially hidden network component, its structure, its dynamics, or its control, and formulate and address these problems in our two applicative domains.
This project involves renowned researchers, actively collaborating with stron academic and industrial partners. Proutiere and Skerman are parts of an active network of researchers in both the machine learning and mathematics communities involving Prof. Massoulie’s joint INRIA/Microsoft research center, and Prof. McDiarmind at Oxford University. Skerman is a research fellow at Simons Institute. Rantzer has maintained strong ties to California Institute of Technology for over thirty years, and the MIT Institute for Data, Systems, and Society. Tegling has an existing collaborations with MIT.
Scientific presentation
Background
Our society increasingly relies on controlled complex networks. These include communication networks and social networks resulting from the interactions of users on online platforms. Our ability to reap all the benefits of these networks and to optimize their operation strongly depends on an accurate knowledge of their structure and of the way their entities in teract. This knowledge is however most often lacking when the network is deployed or started, and rather needs to be acquired by testing and learning from observations.
For example, future mobile networks (5G and beyond) will consist of possibly millions of base stations (BSs) deployed in the field without precise or optimized configuration. This unprecedented scale calls for a radical paradigm shift in the way the network is operated. Today’s network operations require repeated and tedious human interventions to adapt BS configurations to changing traffic demand and evolving services, but this simply becomes impossible in larger networks. There, network management schemes will be automated and decentralized, and rely on algorithms able to quickly learn the network structure (e.g., the way BSs interact through interference), its dynamics, and optimal tuning parameters.
Purpose
The project aims to develop novel mathematical and computational tools for the de sign of algorithms learning the structure, the dynamics, and the control of largescale networks. Our objectives are twofold: (i) to develop a comprehensive theory of learning in networks, and (ii) to apply our results to two application domains, namely decentralized and automated network management of future radio communication networks, and online intermediation platforms.
Methods/ chosen approach
The project is articulated around three complementary research tracks. The first track is devoted to network structure inference, and to learning tasks dealing with recovering the structure of graphs and more general networks from random observations. For these tasks, we adopt a two-step fundamental approach: (i) we first attempt to identify fundamental learning limits (i.e., the most accurate estimators of the network structure we can get given the data available and accounting for potentially limited computational capabilities); (ii) in parallel, we want to devise algorithms that efficiently extract the network structure and whose performance approaches the fundamental statistical and computational limits.
The second research track is devoted to the design of computationally and statistically efficient algorithms learning the network dynamics. To feed these algorithms, we typically have access to data corresponding to trajectories of the network states and controlled actions, only. We will mainly focus on the cases where the dynamics are Markovian or described as a linear system. We will further investigate dynamic causality patterns, namely how information propagates through the network.
Finally, equipped with tools to estimate the structure and dynamics of the network, we aim to devise, in the last research track, decentralized robust and scalable control and RL algorithms. In terms of robustness, it is essential to keep in mind that stochastic models are always idealized, and our approach here is to consider adversarial disturbances instead. A particular challenge in learning control algorithms is to limit the need for information exchange. This is particularly important when the network is very large and learning should be done in realtime. Control signals have a dual purpose: The shortterm purpose is to mitigate the effect of disturbances. A more longterm purpose is to excite the system to enable a more rapid learning process. There is a conflict between the two objectives, known as the exploration/exploitation tradeoff. We will analyze this trade-off in a distributed setting, since scalable solutions for networks require localized learning.
NEST environment description
Proutiere is a professor at the Division of Decision and Control Systems at KTH and he is currently supervises two WASP industrial students at Ericsson Research working on topics related to the NEST-project. Proutiere acts as the PI of an SSF project on the security and robustness of learning and control systems. He is also coPI of the research project ”Data Limited Learning of Complex Dynamical Systems” at Digital Futures, KTH Royal Institute of Technology. Rantzer is a professor at the Department of Automatic Control at Lund University. He is a coPI (together with Hansson) of the ELLIIT project ”Scalable Optimization for Learning in Control”, and holds an ERC advanced grant. Tegling is a WASP associate professor in the Department of Automatic Control, Lund University. She is a coPI (together with Altafini, Como, and Larsson) of the ELLIIT project ”Dynamics of Complex SocioTechnological Network Systems”, tightly related to this NEST. Skerman is a WASP assistant professor in the Department of Mathematics in Uppsala University. The research environment at Uppsala University contributes with world-class mathematics expertise with collaborators such as Prof. Svante Jansson and Dr. Cecilia Holmgren.