Distributed Online Optimization on time-varying networks
Akbari Varnousfaderani, Mohammad Jr
MetadataShow full item record
This thesis introduces two classes of discrete-time distributed online optimization algorithms, with a group of agents which communicate over a network. At each time, a private convex objective function is revealed to each agent. In the next time step, each agent updates its state using its own objective function and the information gathered from its immediate in-neighbours at that time. We design algorithms distributed over the network topologies, which guarantee that the individual regret, the diﬀerence between the network cost incurred by the agent’s states estimation and the cost incurred by the best ﬁxed choice, grows only sublinearly. One algorithm is based on gradient-ﬂow, which provably works for a sequence of time-varying uniformly strongly connected graphs. The other one is based on Alternating Direction Method of Multipliers, which works on ﬁxed undirected graphs and gives an explicit regret bound in terms of the size of the network. We implement the proposed algorithms on a sensor network and the results demonstrate the good performance for both algorithms.