The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Distributed Online Optimization in Dynamic Environments Using Mirror Descent
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Horn, R. A., & Johnson, C. R. (2012) · doi:10.1017/cbo9781139020411 · Cited by 4,642
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719
Bar‐Shalom, Y. (1988) · Medical Entomology and Zoology · Cited by 3,157
(2003) · Cited by 1,733
Distributed Kalman filtering for sensor networks
Olfati-Saber, R. (2007) · 2007 46th IEEE Conference on Decision and Control · doi:10.1109/cdc.2007.4434303 · Cited by 1,586
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261
Online Learning and Online Convex Optimization
Shalev-Shwartz, S. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000018 · Cited by 1,246
Distributed average consensus with least-mean-square deviation
Xiao, L., Boyd, S., & Kim, S.-J. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2006.08.010 · Cited by 1,107
Online Learning and Online Convex Optimization
Shalev-Shwartz, S. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985477 · Cited by 1,095
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A., & Teboulle, M. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00231-6 · Cited by 1,060
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947
Detection, classification, and tracking of targets
Li, D., Wong, K. D., Hu, Y. H., & Sayeed, A. M. (2002) · IEEE Signal Processing Magazine · doi:10.1109/79.985674 · Cited by 932
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814 · cited 1×
“The effect of stochastic gradients is then considered in [9].”
BackgroundOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759
Fast Distributed Gradient Methods
Jakovetic, D., Xavier, J., & Moura, J. M. F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2298712 · Cited by 624
Kar, S., Moura, J. M. F., & Ramanan, K. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2191450 · Cited by 476
Stochastic Event-Triggered Sensor Schedule for Remote State Estimation
Han, D., Mo, Y., Wu, J., Weerakkody, S., Sinopoli, B., & Shi, L. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2406975 · Cited by 393
Non-stationary stochastic optimization
Besbes, O., Gur, Y., & Zeevi, A. (2015) · Operations Research · doi:10.1287/opre.2015.1408 · Cited by 337
A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
Johansson, B., Rabi, M., & Johansson, M. (2010) · SIAM Journal on Optimization · doi:10.1137/08073038x · Cited by 336
Distributed Sensor Networks: A Multiagent Perspective
Lesser, V., Tambe, M., & Ortiz, C. L. (2003) · Kluwer Academic Publishers eBooks · Cited by 289
Problems in Decentralized Decision making and Computation.
Tsitsiklis, J. N. (1984) · Defense Technical Information Center (DTIC) · Cited by 288
Online Convex Optimization in Dynamic Environments
Hall, E. C., & Willett, R. M. (2015) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2404790 · Cited by 219
Likelihood Consensus and Its Application to Distributed Particle Filtering
Hlinka, O., Sluciak, O., Hlawatsch, F., Djuric, P. M., & Rupp, M. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2196697 · Cited by 218
Fast Convergence Rates for Distributed Non-Bayesian Learning
Nedic, A., Olshevsky, A., & Uribe, C. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2690401 · Cited by 212
Distributed Online Convex Optimization on Time-Varying Directed Graphs
Akbari, M., Gharesifard, B., & Linder, T. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2505149 · Cited by 190
Online optimization in dynamic environments: Improved regret rates for strongly convex problems
Mokhtari, A., Shahrampour, S., Jadbabaie, A., & Ribeiro, A. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7799379 · Cited by 186
Self-citationOnline Optimization : Competing with Dynamic ComparatorsPreprint
Jadbabaie, A., Rakhlin, A., Shahrampour, S., & Sridharan, K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.06225 · Cited by 175
Self-citationA Class of Prediction-Correction Methods for Time-Varying Convex Optimization
Simonetto, A., Mokhtari, A., Koppel, A., Leus, G., & Ribeiro, A. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2568161 · Cited by 166
Distributed Online Convex Optimization Over Jointly Connected Digraphs
Mateos‐Núñez, D., & Cortés, J. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2014.2363554 · Cited by 149
Online distributed optimization via dual averaging
Hosseini, S., Chapman, A., & Mesbahi, M. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760092 · Cited by 130
Distributed Detection: Finite-Time Analysis and Impact of Network Topology
Shahrampour, S., Rakhlin, A., & Jadbabaie, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2506903 · Cited by 112
Self-citationDistributed Particle Filter for Target Tracking
Gu, D. (2007) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2007.364070 · Cited by 101
On connectivity, observability, and stability in distributed estimation
Khan, U. A., Kar, S., Jadbabaie, A., & Moura, J. M. F. (2010) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5717479 · Cited by 95
Self-citationDistributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms
Tsitsiklis, J. N., Bertsekas, D. P., & Athans, M. (1984) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.1984.4788427 · Cited by 89
Distributed mirror descent method for multi-agent optimization with delay
Li, J., Chen, G., Dong, Z. Y., & Wu, Z. (2015) · Neurocomputing · doi:10.1016/j.neucom.2015.12.017 · Cited by 66
Continuous-time stochastic Mirror Descent on a network: Variance reduction, consensus, convergence
Raginsky, M., & Bouvrie, J. (2012) · doi:10.1109/cdc.2012.6426639 · Cited by 54
Convergence of rule-of-thumb learning rules in social networks
Acemoğlu, D., Nedić, A., & Ozdaglar, A. (2008) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2008.4739167 · Cited by 46
Multi-agent mirror descent for decentralized stochastic optimization
Rabbat, M. (2015) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2015.7383850 · Cited by 43
Decentralized online optimization with global objectives and local communication
Nedić, A., Lee, S., & Raginsky, M. (2015) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2015.7172037 · Cited by 38
Shahrampour, S., & Jadbabaie, A. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7963457 · Cited by 23
Self-citationDistributed detection via Bayesian updates and consensus
Liu, Q., Zhao, J., & Xiao-fan, W. (2015) · Chinese Control Conference (CCC) · doi:10.1109/chicc.2015.7260745 · Cited by 17
Distributed estimation of dynamic parameters: Regret analysis
Shahrampour, S., Rakhlin, A., & Jadbabaie, A. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7525056 · Cited by 11
Self-citation
Cited by
Central Server Free Federated Learning over Single-sided Trust Social Networks
He, C., Tan, C., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1910.04956 · Cited by 60
Zhao, Y., Yu, C., Zhao, P., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1901.10593 · Cited by 16
Metadata
- Authors
- Shahrampour, S., & Jadbabaie, A.
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2018-03
- Volume
- 63
- Issue
- 3
- Pages
- 714-725
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- OpenAlex
- W2520863159
- Cited by
- 331
- References
- 46
- FWCI
- 16.33
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.