Distributed optimization over time-varying directed graphs
The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O (ln t/√t), where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Coordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
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 · cited 2×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
Stability of multiagent systems with time-dependent communication links
Moreau, L. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.841888 · Cited by 2,706
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480
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
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 · cited 2×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
BackgroundDual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs
Gharesifard, B., & Cortes, J. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2278132 · Cited by 833
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 2×
“Finally, we remark that previous research [13], [17], [4] has studied the case when the matrices A(t) (defined in the statement of Theorem 2) are doubly stochastic; this occurs when the directed graph sequence {G(t)} is regular, and in that case our polynomial bounds essentially match previously known results.”
MethodResultSelf-citationIncremental Adaptive Strategies Over Distributed Networks
Lopes, C. G., & Sayed, A. H. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.896034 · Cited by 732
Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
Chen, J., & Sayed, A. H. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2198470 · Cited by 680
On Distributed Averaging Algorithms and Quantization Effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031203 · Cited by 557
Self-citationDistributed Subgradient Methods for Convex Optimization Over Random Networks
Lobel, I., & Ozdaglar, A. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2091295 · Cited by 351 · cited 1×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
BackgroundDistributed Asynchronous Constrained Stochastic Optimization
Srivastava, K., & Nedic, A. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2118740 · Cited by 350
Self-citationAsynchronous Broadcast-Based Convex Optimization Over a Network
Nedic, A. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2079650 · Cited by 310 · cited 1×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
Push-Sum Distributed Dual Averaging for convex optimization
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426375 · Cited by 304 · cited 3×
“The papers [20], [21] proved the convergence of a subgradient algorithm in a directed but fixed topology; implementation of the protocol appears to require knowledge of the graph or of the number of agents.”
BackgroundResultWeighted Gossip: Distributed Averaging using non-doubly stochastic matrices
Benezit, F., Blondel, V., Thiran, P., Tsitsiklis, J., & Vetterli, M. (2010) · 2010 IEEE International Symposium on Information Theory · doi:10.1109/isit.2010.5513273 · Cited by 224
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483403 · Cited by 223
Convergence rate for consensus with delays
Nedić, A., & Ozdaglar, A. (2010) · Journal of Global Optimization · doi:10.1007/s10898-008-9370-2 · Cited by 198
Self-citationDistributed multi-agent optimization with state-dependent communication
Lobel, I., Ozdaglar, A., & Feijer, D. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0467-x · Cited by 162 · cited 1×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
BackgroundA new class of distributed optimization algorithms: Application to regression of distributed data
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2012) · Optimization Methods and Software · doi:10.1080/10556788.2010.511669 · Cited by 123
On Distributed Optimization in Networked Systems
Johansson, B. (2008) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 114
Distributed Non-Autonomous Power Control through Distributed Convex Optimization
Ram, S. S., Veeravalli, V. V., & Nedic, A. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062275 · Cited by 99
Self-citationDistributed consensus and optimization under communication delays
Tsianos, K. I., & Rabbat, M. G. (2011) · 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2011.6120272 · Cited by 92
Distributed strategies for average consensus in directed graphs
Domínguez-García, A. D., & Hadjicostis, C. N. (2011) · 2011 50th IEEE Conference on Decision and Control and European Control Conference · doi:10.1109/cdc.2011.6160462 · Cited by 75
Competitive Spectrum Access in Cognitive Radio Networks: Graphical Game and Learning
Li, H., & Han, Z. (2010) · 2010 IEEE Wireless Communication and Networking Conference · doi:10.1109/wcnc.2010.5506285 · Cited by 67
Continuous-time distributed convex optimization on weight-balanced digraphs
Gharesifard, B., & Cortes, J. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426897 · Cited by 32
Distributed gradient optimization for epidemic routing: A preliminary evaluation
Neglia, G., Reina, G., & Alouf, S. (2009) · IFIP Wireless Days · doi:10.1109/wd.2009.5449659 · Cited by 27
Distributed continuous-time convex optimization on weight-balanced digraphsPreprint
Gharesifard, B., & Cortés, J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1204.0304 · Cited by 2
Research works printed but not linked: 1
- gharesifard, 2012, Distributed Continuoustime Convex Optimization on Weight-balanced Digraphs
Cited by
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
“To overcome this issue, reference [40] is the first to propose a different distributed approach, namely a subgradient-push algorithm that combines the distributed subgradient method [47] with the push-sum protocol [27].”
MethodSelf-citationA Distributed Algorithm for Solving a Linear Algebraic Equation
Mou, S., Liu, J., & Morse, A. S. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2414771 · Cited by 284
Metadata
- Authors
- Nedic, A., & Olshevsky, A.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- ORCID
- Olshevsky, Alex
- Venue
- 52nd IEEE Conference on Decision and Control
- Publisher
- IEEE
- Published
- 2013-12
- Pages
- 6855-6860
- ISSN
- 0191-2216 (ISSN-L)
- OpenAlex
- W2952931788
- Cited by
- 72
- References
- 31
- Citations by year
- 2026: 4 · 2024: 2 · 2023: 3 · 2021: 10 · 2020: 8 · 2019: 2 · 2018: 4 · 2017: 7 · 2016: 7 · 2015: 14 · 2014: 10 · 2013: 1
- FWCI
- 8.17
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Conference on Decision and Control (CDC) (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Engineering › Control and Systems Engineering › Advanced Control Systems Optimization
- Keywords
- distributed optimization, time-varying directed graphs, convex optimization, consensus, convergence rate
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.