spacer search

UCLA Adaptive Systems Laboratory

Home arrow Books Descriptions arrow Adaptation, Learning, and Optimization over Networks

Adaptation, Learning, and Optimization over Networks
Foundations and Trends in Machine Learning, vol. 7, issue 4-5, NOW Publishers, 2014.

Adaptation, Learning, and Optimization over Networks

Printed book, 518pp
ISBN 978-1-60198-850-8
DOI 10.1561/2200000051

Author: Ali H. Sayed, UCLA

Published July 2014

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 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