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