Distributed Online Optimization in Dynamic Environments Using Mirror Descent

By Shahin Shahrampour, Ali Jadbabaie. 2016

339 citations recorded by the source corpus.

This work addresses decentralized online optimization in nonstationary environments. A network of agents aim to track the minimizer of a global, time-varying, and convex function. The minimizer follows a known linear dynamics corrupted by unknown unstructured noise. At each time, the global function (which could be a tracking error) can be cast as a sum of a finite number of local functions, each of which is assigned to one agent in the network. Moreover, the local functions become available to agents sequentially, and agents do not have prior knowledge of the future cost functions. Therefore, agents must communicate with each other to build an online approximation of the global function. We propose a decentralized variation of the celebrated mirror descent algorithm, according to which agents perform a consensus step to follow the global function and take into account the dynamics of the global minimizer. In order to measure the performance of the proposed online algorithm, we compare it to its offline counterpart, where the global functions are available a priori. The gap between the two losses is defined as dynamic regret. We establish a regret bound that scales inversely in the spectral gap of the network and represents the deviation of minimizer sequence with respect to the given dynamics. We show that our framework subsumes a number of results in distributed optimization.

Subfields: Computational Mechanics, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Hanlin Tang
2. Ce Zhang
3. Ji Liu
4. Xiangru Lian
5. Ming Yan
6. Peilin Zhao
7. Amrit Singh Bedi
8. Conghui Tan

In Computer Networks and Communications

1. Hanlin Tang
2. Ji Liu
3. Ce Zhang
4. Xiangru Lian
5. Amrit Singh Bedi
6. Ketan Rajawat
7. Peilin Zhao
8. Kunlun He

In Management Science and Operations Research

1. Chaoyang He
2. Conghui Tan
3. Peilin Zhao
4. Kunlun He
5. Chenkai Yu
6. Ce Zhang
7. Ming Yan
8. Zongren Li

Citations in the corpus

• Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “Examples of these works include Kamp et al. (2014); Shahrampour and Jadbabaie (2017); Lee et al. (2016).”
• Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “Decentralized Online Learning (or, online learning in decentralized networks) receives extensive attentions in recent years [Shahrampour and Jadbabaie, 2018, Kamp et al., 2014, Koppel et al., 2018, Zhang et al., 2018a, 2017b, Xu et al., 2015, Akbari et al., 2017, Lee et al., 2016, Nedi et al.,…”
• D2: Decentralized Training over Decentralized Data (2018, background): “The decentralized stochastic gradient descent [Lian et al., 2017a, Shahrampour and Jadbabaie, 2017, Zhang et al., 2017] allows each worker (say worker i ) maintaining its own local variable x ( i ) .”
• Competing with Automata-based Expert Sequences (2018, background): “One perspective has been the design of algorithms that maintain a guarantee against sequences that do not vary too much [Mokhtari et al., 2016, Shahrampour and Jadbabaie, 2016, Jadbabaie et al., 2015, Besbes et al., 2015].”
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, background): “Recent year have witnessed the development of theoretical guarantees in form of dynamic regret, where the performance of the learner is measured against that of an adaptive and time-varying adversary [11], [17], [18].”
• Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “he dynamics? • How difficult to follow dynamics in online learning? Although the dynamic regret receives more and more attention recently [Mokhtari et al., 2016, Yang et al., 2016, Zhang et al., 2017a, Shahrampour and Jadbabaie, 2018, Hall and Willett, 2015, Jadbabaie et al., 2015] and some successive”
• Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, neutral): “[27] extends it to the decentrialized setting(1).”
• Asynchronous Decentralized Online Learning (2021, background): “Many different algorithms have been proposed [31, 32, 22, 15, 28, 16, 24] and successfully applied in various application scenarios, such as recommendation systems [29], energy management [5] and cooperative navigation [21].”