Learning in Complex Dynamic Systems : with Applications to Perpetual Flight, Energy Management, Distributed Decision Making, and Social Networks

Thesis (Ph.D.)--University of Washington, 2016-03This dissertation addresses learning in complex dynamic systems with applications to perpetual flight, energy management, collaborative decision making, and social networks. By increasing the size and complexity of network systems, decentralized optimization schemes or machine learning algorithms are desired for scaling up the automated learning process, reducing data transmission, and ensuring robustness in the presence of local failures. This work approaches these challenges from two fronts: complex dynamics associated with individual agents in the network; and protocols which are run on individual agents in the network. In this direction, energy management for aerial vehicles and small smart grids have been studied . With the objective to develop smart autonomous distributed systems performing in a highly uncertain environment, online distributed learning algorithms have been proposed. These algorithms allow the network topology to adapt and each agent learns the model based on its local data and the information it receives from its neighboring agents. Central to our analysis of the performance of such online distributed algorithms is the examination of the role of the network structure in the so-called social regret. In addition, this dissertation provides analysis of large scale time-varying and state-dependent networks to develop scalable distributed learning algorithms for online network estimation. In this problem, the state of the nodes are affected by their neighboring nodes, inspired by the opinion dynamics. A sampling approach is then applied to scale up the algorithm for massive networks. Our theoretical results demonstrate a good (sub-linear) regret bound for the topology estimation problem with limited and online observations of the underlying communication links