Adaptation, Learning, and Optimization over Networks

There are many good reasons for the peaked interest in distributed implementations, especially in this day and age when the word “network” has become commonplace whether one is referring to social networks, power networks, transportation networks, data networks, biological networks or other types of networks. Some of these reasons have to do with the benefits of cooperation in terms of improved performance and improved resilience to failure. Other reasons deal with privacy and secrecy considerations where agents may not be comfortable sharing their data with remote fusion centers. In other situations, the data may already be available in dispersed locations, as happens with cloud computing. One may also be interested in learning through data mining from Big Data sets.

Motivated by these considerations, this tutorial deals with the topic of information processing over graphs and how collaboration among agents in a network can lead to superior adaptation and learning performance. The presentation covers results and tools that relate to the analysis and design of networks that are able to solve optimization, adaptation and learning problems in an online and distributed manner from streaming data through localized interactions among their agents. The results discussed in this tutorial are useful in comparing network topologies against each other and in comparing networked solutions against centralized or batch implementations. The results are also useful in elucidating how cooperation among unsophisticated agents can lead to powerful network behavior.

It is not difficult to envision that future engineering systems will benefit from similar bottom?up design approaches involving coordination among less powerful units to achieve higher levels of cognition and performance. Robotic swarms are one notable example where agents can work together through an evolving topology, and adjust their locations and exploration space in response to environmental conditions, malfunctioning of neighbors or even suspicious behavior by intruders. Another example is the use of networked learners to mine information from Big Data sets, such as those related to health informatics, transportation networks, power grids, social networks, or surveillance applications. In these scenarios, it is often the case that information is already spread across dispersed locations and decentralized learning and adaptation offers an attractive approach to information processing.

The tutorial will discuss at length how families of networked agents can be made to adapt and learn continually from streaming data and from limited interactions among neighboring agents, and how by tapping into the “wisdom” of the group, networks are able to complement the limitations of their individual agents. The presentation will also explain how such networks can be used to solve optimization problems in a decentralized manner. The tutorial will further clarify the limits of performance of distributed solutions and discuss procedures that help bring forth their potential more fully. The presentation adopts a useful statistical framework and discusses performance results that elucidate the stability, convergence, and performance behavior of the learning networks. The work also illustrates how distributed processing over graphs gives rise to some revealing phenomena due to the coupling effect among agents. These phenomena are discussed in the context of several applications including distributed sensing, intrusion detection, dictionary learning, distributed estimation, distributed optimization, online learning, network system theory, biological networks and machine learning.

Outline:

1. Motivation & Examples: Distributed processing. Biological networks. Adaptive networks. Graphs.
2. Optimization by Single Agents: Risks and loss functions. Convergence. Limitations.
3. Stochastic Optimization by Single Agents: Learning. Adaptation. Convergence. Limitations.
4. Performance of Single Agents: Analysis. MSE design. Logistic regression. Pattern classification.
5. Centralized Adaptation and Learning: Comparison with non-cooperative schemes.
6. Multi-Agent Networks: Graph models and properties. Pareto optimality. Limits points.
7. Multi-Agent Distributed Strategies: Incremental, consensus, diffusion, primal-dual techniques.
8. Evolution of Multi-Agent Networks: Coupling among agents. Stochastic models. Implications.
9. Stability of Multi-Agent Networks: Bounded moments. Convergence. Cooperation matters.
10. Long-Term Network Dynamics: Slow adaptation regime. Network evolution.
11. Performance of Multi-Agent Networks: Performance expressions. Influence of topology.
12. Benefits of Cooperation: Doubly vs. left-stochastic policies. Social benefit vs. individual benefit.
13. Combination Policies: Optimal policies. Adaptive policies. Clustering.
14. Extensions: Gossip & asynchronous strategies, constrained optimization, sparse optimization.
15. Applications: distributed optimization, adaptation and learning, dictionary learning, biological networks, intrusion detection, target tracking, machine learning and online learning.