Abstract: An algorithm to learn optimal actions in convex distributed online problems is developed. Learning is online because cost functions are revealed sequentially and distributed because they are revealed to agents of a network that can exchange information with neighboring nodes only. Learning is measured in terms of the global network regret, which is defined here as the accumulated loss of causal prediction with respect to a centralized clairvoyant agent to which the information of all times and agents is revealed at the initial time. A variant of the Arrow-Hurwicz saddle point algorithm is proposed to control the growth of global network regret. This algorithm uses Lagrange multipliers to penalize the discrepancies between agents and leads to an implementation that relies on local operations and exchange of variables between neighbors. We show that decisions made with this saddle point algorithm lead to regret whose order is not larger than O(sqrt(T)), where T is the total operating time. Numerical behavior is illustrated for the particular case of distributed recursive least squares. An application to computer network security in which service providers cooperate to detect the signature of malicious users is developed to illustrate the practical value of the proposed algorithm.
We then consider an extension of this problem class to the case where agents aim to learn a common discriminative signal representation for a particular learning task, which makes the program non-convex. Nonetheless, we are able to establish the convergence in expectation of a block-stochastic saddle point algorithm for this setting. We apply the proposed method to the problem of a mobile robotic team seeking to collaboratively incorporate visual information into navigability assessment in an unknown environment, demonstrating the proposed algorithm's utility in a field setting.
Bio: Alec Koppel is a doctoral student in the Department of Electrical and Systems Engineering at the University of Pennsylvania and a participant in the Science, Mathematics, and Research for Transformation (SMART) Scholarship Program sponsored by the American Society of Engineering Education. His sponsoring facility is the U.S. Army Research Laboratory in Adelphi, MD, where he works during doctoral summers. Before coming to Penn, he completed his M.S. degree in Systems Science and Mathematics and B.A. degree in Mathematics at Washington University in St. Louis, MO. His research interests are in the areas of signal processing, optimization, and learning theory. His current work focuses on designing new large-scale or dynamic optimization methods for multi-agent systems with a focus on robotic and computer networks.