Adaptation, Learning, and Optimization over Networks

A. H. Sayed, Adaptation, Learning, and Optimization over Networks, NOW Publishers, 2014.


Adaptation, Learning, and Optimization over Networks deals with the topic of information processing over graphs. The presentation is largely self-contained and covers results that relate to the analysis and design of multi-agent networks for the distributed solution of optimization, adaptation, and learning problems from streaming data through localized interactions among agents. The results derived in this monograph are useful in comparing network topologies against each other, and in comparing networked solutions against centralized or batch implementations.

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, 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, Adaptation, Learning, and Optimization over Networks examines the limits of performance of distributed solutions and discusses procedures that help bring forth their potential more fully.

Adaptation, Learning, and Optimization over Networks adopts a useful statistical framework and derives performance results that elucidate the mean-square stability, convergence, and steady-state behavior of the learning networks. At the same time, the monograph illustrates how distributed processing over graphs gives rise to some revealing phenomena due to the coupling effect among the agents. These phenomena are discussed in the context of adaptive networks, along with examples from a variety of areas including distributed sensing, intrusion detection, distributed estimation, online adaptation, network system theory, and machine learning.

About the Author

Ali H. Sayed is a professor and former chairman of electrical engineering at the University of California, Los Angeles, where he directs the UCLA Adaptive Systems Laboratory. An author of over 440 scholarly publications and six books, his research involves several areas including adaptation and learning, network science, information processing theories, and biologically-inspired designs. His work has been recognized with several awards including the 2014 Athanasios Papoulis Award from the European Association of Signal Processing, the 2013 Meritorious Service Award and the 2012 Technical Achievement Award from the IEEE Signal Processing Society, the 2005 Terman Award from the American Society for Engineering Education, the 2003 Kuwait Prize, and the 1996 IEEE Donald G. Fink Prize. He served as a 2005 Distinguished Lecturer for the IEEE Signal Processing Society in 2005. His articles received best paper awards from the IEEE Signal Processing Society in 2002, 2005, and 2012. He is a Fellow of both the IEEE and the American Association for the Advancement of Science (AAAS). He is also a Highly Cited Researcher by Thomson Reuters.

Table of Contents

1. Motivation and Introduction: 1.1 Introduction, 1.2 Biological Networks, 1.3 Distributed Processing, 1.4 Adaptive Networks, 1.5 Organization, 1.6 Notation and Symbols

2. Optimization by Single Agents: 2.1 Risk and Loss Functions, 2.2 Conditions on Risk Function, 2.3 Optimization via Gradient Descent, 2.4 Decaying Step-Size Sequences, 2.5 Optimization in the Complex Domain

3. Stochastic Optimization by Single Agents: 3.1 Adaptation and Learning, 3.2 Gradient Noise Process, 3.3 Stability of Second-Order Error Moment, 3.4 Stability of Fourth-Order Error Moment, 3.5 Decaying Step-Size Sequences, 3.6 Optimization in the Complex Domain

4. Performance of Single Agents: 4.1 Conditions on Risk Function and Noise, 4.2 Stability of First-Order Error Moment, 4.3 Long-Term Error Dynamics, 4.4 Size of Approximation Error, 4.5 Performance Metrics, 4.6 Performance in the Complex Domain

5. Centralized Adaptation and Learning:  5.1 Non-Cooperative Processing, 5.2 Centralized Processing, 5.3 Stochastic-Gradient Centralized Solution, 5.4 Gradient Noise Model, 5.5 Performance of Centralized Solution, 5.6 Comparison with Single Agents, 5.7 Decaying Step-Size Sequences

6. Multi-Agent Network Model: 6.1 Connected Networks, 6.2 Strongly-Connected Networks, 6.3 Network Objective

7. Multi-Agent Distributed Strategies: 7.1 Incremental Strategy, 7.2 Consensus Strategy, 7.3 Diffusion Strategy

8. Evolution of Multi-Agent Networks: 8.1 State Recursion for Network Errors, 8.2 Network Limit Point and Pareto Optimality, 8.3 Gradient Noise Model, 8.4 Extended Network Error Dynamics

9. Stability of Multi-Agent Networks: 9.1 Stability of Second-Order Error Moment, 9.2 Stability of Fourth-Order Error Moment, 9.3 Stability of First-Order Error Moment

10. Long-Term Network Dynamics: 10.1 Long-Term Error Model, 10.2 Size of Approximation Error, 10.3 Stability of Second-Order Error Moment, 10.4 Stability of Fourth-Order Error Moment, 10.5 Stability of First-Order Error Moment, 10.6 Comparing Consensus and Diffusion Strategies

11. Performance of Multi-Agent Networks: 11.1 Conditions on Costs and Noise, 11.2 Performance Metrics, 11.3 Mean-Square-Error Performance, 11.4 Excess-Risk Performance, 11.5 Comparing Consensus and Diffusion Strategies

12. Benefits of Cooperation: 12.1 Doubly-Stochastic Combination Policies, 12.2 Left-Stochastic Combination Policies, 12.3 Comparison with Centralized Solutions, 12.4 Excess-Risk Performance

13. Role of Informed Agents: 13.1 Informed and Uninformed Agents, 13.2 Conditions on Cost Functions, 13.3 Mean-Square-Error Performance, 13.4 Controlling Degradation in Performance, 13.5 Excess-Risk Performance

14. Combination Policies: 14.1 Static Combination Policies, 14.2 Need for Adaptive Policies, 14.3 Hastings Policy, 14.4 Relative-Variance Policy, 14.5 Adaptive Combination Policy

15. Extensions and Conclusions: 15.1 Gossip and Asynchronous Strategies, 15.2 Noisy Exchanges of Information, 15.3 Exploiting Temporal Diversity, 15.4 Incorporating Sparsity Constraints, 15.5 Distributed Constrained Optimization, 15.6 Distributed Recursive Least-Squares, 15.7 Distributed State-Space Estimation



A. Complex Gradient Vectors: A.1 Cauchy-Riemann Conditions, A.2 Scalar Arguments, A.3 Vector Arguments, A.4 Real Arguments

B. Complex Hessian Matrices: B.1 Hessian Matrices for Real Arguments, B.2 Hessian Matrices for Complex Arguments

C. Convex Functions: C.1 Convexity in the Real Domain, C.2 Convexity in the Complex Domain

D. Mean-Value Theorems: D.1 Increment Formulae for Real Arguments, D.2 Increment Formulae for Complex Arguments

E. Lipschitz Conditions: E.1 Perturbation Bounds in the Real Domain, E.2 Lipschitz Conditions in the Real Domain, E.3 Perturbation Bounds in the Complex Domain, E.4 Lipschitz Conditions in the Complex Domain

F. Useful Matrix and Convergence Results: F.1 Kronecker Products, F.2 Vector and Matrix Norms, F.3 Perturbation Bounds on Eigenvalues,  F.4 Lyapunov Equations, F.5 Stochastic Matrices, F.6 Convergence of Inequality Recursions

G. Logistic Regression: G.1 Logistic Function, G.2 Odds Function, G.3 Kullback-Leibler Divergence