An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise
This paper addresses tracking of a moving target in a multi-agent network. The target follows a linear dynamics corrupted by an adversarial noise, i.e., the noise is not generated from a statistical distribution. The location of the target at each time induces a global time-varying loss function, an...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/117776 |
| _version_ | 1811079419341570048 |
|---|---|
| author | Shahrampour, Shahin Jadbabaie-Moghadam, Ali |
| 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 Jadbabaie-Moghadam, Ali |
| author_sort | Shahrampour, Shahin |
| collection | MIT |
| description | This paper addresses tracking of a moving target in a multi-agent network. The target follows a linear dynamics corrupted by an adversarial noise, i.e., the noise is not generated from a statistical distribution. The location of the target at each time induces a global time-varying loss function, and the global loss is a sum of local losses, each of which is associated to one agent. Agents noisy observations could be nonlinear. We for- mulate this problem as a distributed online optimization where agents communicate with each other to track the minimizer of the global loss. We then propose a decentralized version of the Mirror Descent algorithm and provide the non-asymptotic analysis of the problem. Using the notion of dynamic regret, we measure the performance of our algorithm versus its offline counterpart in the centralized setting. We prove that the bound on dynamic regret scales inversely in the network spectral gap, and it represents the adversarial noise causing deviation with respect to the linear dynamics. Our result subsumes a number of results in the distributed optimization literature. Finally, in a numerical experiment, we verify that our algorithm can be simply implemented for multi-agent tracking with nonlinear observations. |
| first_indexed | 2024-09-23T11:14:43Z |
| format | Article |
| id | mit-1721.1/117776 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:14:43Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1177762022-09-27T18:09:03Z An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise Shahrampour, Shahin Jadbabaie-Moghadam, Ali Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Jadbabaie-Moghadam, Ali This paper addresses tracking of a moving target in a multi-agent network. The target follows a linear dynamics corrupted by an adversarial noise, i.e., the noise is not generated from a statistical distribution. The location of the target at each time induces a global time-varying loss function, and the global loss is a sum of local losses, each of which is associated to one agent. Agents noisy observations could be nonlinear. We for- mulate this problem as a distributed online optimization where agents communicate with each other to track the minimizer of the global loss. We then propose a decentralized version of the Mirror Descent algorithm and provide the non-asymptotic analysis of the problem. Using the notion of dynamic regret, we measure the performance of our algorithm versus its offline counterpart in the centralized setting. We prove that the bound on dynamic regret scales inversely in the network spectral gap, and it represents the adversarial noise causing deviation with respect to the linear dynamics. Our result subsumes a number of results in the distributed optimization literature. Finally, in a numerical experiment, we verify that our algorithm can be simply implemented for multi-agent tracking with nonlinear observations. United States. Office of Naval Research. Basic Research Challenge. Program of Decentralized Online Optimization 2018-09-17T14:38:55Z 2018-09-17T14:38:55Z 2017-05 2018-08-16T17:20:01Z Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-5992-8 http://hdl.handle.net/1721.1/117776 Shahrampour, Shahin, and Ali Jadbabaie. “An Online Optimization Approach for Multi-Agent Tracking of Dynamic Parameters in the Presence of Adversarial Noise.” 2017 American Control Conference (ACC) (May 2017). http://dx.doi.org/10.23919/ACC.2017.7963457 2017 American Control Conference (ACC) 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 Jadbabaie-Moghadam, Ali An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title | An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title_full | An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title_fullStr | An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title_full_unstemmed | An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title_short | An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise |
| title_sort | online optimization approach for multi agent tracking of dynamic parameters in the presence of adversarial noise |
| url | http://hdl.handle.net/1721.1/117776 |
| work_keys_str_mv | AT shahrampourshahin anonlineoptimizationapproachformultiagenttrackingofdynamicparametersinthepresenceofadversarialnoise AT jadbabaiemoghadamali anonlineoptimizationapproachformultiagenttrackingofdynamicparametersinthepresenceofadversarialnoise AT shahrampourshahin onlineoptimizationapproachformultiagenttrackingofdynamicparametersinthepresenceofadversarialnoise AT jadbabaiemoghadamali onlineoptimizationapproachformultiagenttrackingofdynamicparametersinthepresenceofadversarialnoise |