Jorge Cortés

Professor

Cymer Corporation Endowed Chair





Distributed online convex optimization over jointly connected digraphs
D. Mateos-Nuñez, J. Cortés
IEEE Transactions on Network Science and Engineering 1 (1) (2014), 23-37


Abstract

This paper considers networked online convex optimization scenarios from a regret analysis perspective. At each round, each agent in the network commits to a decision and incurs in a local cost given by functions that are revealed over time and whose unknown evolution model might be adversarially adaptive to the agent's behavior. The goal of each agent is to incur a cumulative cost over time with respect to the sum of local functions across the network that is competitive with the best fixed and centralized decision in hindsight. To achieve this, agents cooperate with each other using local averaging over time-varying, weight-balanced digraphs as well as subgradient descent on the local cost functions revealed in the previous round. We propose a class of coordination algorithms that generalize distributed online subgradient descent and saddle-point dynamics, allowing proportional-integral (and higher-order) feedback on the disagreement among neighboring agents. We show that our algorithm design achieves logarithmic agent regret (when local objectives are strongly convex), or square-root agent regret (when local objectives are convex) in scenarios where the communication graphs are jointly connected. Simulations in a medical diagnosis application illustrate our results.

pdf   |   ps.gz

Mechanical and Aerospace Engineering, University of California, San Diego
9500 Gilman Dr, La Jolla, California, 92093-0411

Ph: 1-858-822-7930
Fax: 1-858-822-3107

cortes at ucsd.edu
Skype id: jorgilliyo