Distributed Online Optimization in Dynamic Environments Using Mirror Descent
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/117724 |
| _version_ | 1826214061092634624 |
|---|---|
| author | Shahrampour, Shahin |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Shahrampour, Shahin |
| author_sort | Shahrampour, Shahin |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:58:51Z |
| format | Article |
| id | mit-1721.1/117724 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:58:51Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1177242022-09-29T17:28:19Z Distributed Online Optimization in Dynamic Environments Using Mirror Descent Shahrampour, Shahin Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society 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. 2018-09-11T19:40:25Z 2018-09-11T19:40:25Z 2017-08 2018-08-16T16:35:44Z Article http://purl.org/eprint/type/JournalArticle 0018-9286 1558-2523 http://hdl.handle.net/1721.1/117724 Shahrampour, Shahin, and Ali Jadbabaie. “Distributed Online Optimization in Dynamic Environments Using Mirror Descent.” IEEE Transactions on Automatic Control, vol. 63, no. 3, Mar. 2018, pp. 714–25. http://dx.doi.org/10.1109/TAC.2017.2743462 IEEE Transactions on Automatic Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Shahrampour, Shahin Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title | Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title_full | Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title_fullStr | Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title_full_unstemmed | Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title_short | Distributed Online Optimization in Dynamic Environments Using Mirror Descent |
| title_sort | distributed online optimization in dynamic environments using mirror descent |
| url | http://hdl.handle.net/1721.1/117724 |
| work_keys_str_mv | AT shahrampourshahin distributedonlineoptimizationindynamicenvironmentsusingmirrordescent |