NEXT: In-Network Nonconvex Optimization
The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
Abstract
We study nonconvex distributed optimization in multiagent networks with time-varying (nonsymmetric) connectivity. We introduce the first algorithmic framework for the distributed minimization of the sum of a smooth (possibly nonconvex and nonseparable) function-the agents' sum-utility-plus a convex (possibly nonsmooth and nonseparable) regularizer. The latter is usually employed to enforce some structure in the solution, typically sparsity. The proposed method hinges on successive convex approximation techniques while leveraging dynamic consensus as a mechanism to distribute the computation among the agents: each agent first solves (possibly inexactly) a local convex approximation of the nonconvex original problem, and then performs local averaging operations. Asymptotic convergence to (stationary) solutions of the nonconvex problem is established. Our algorithmic framework is then customized to a variety of convex and nonconvex problems in several fields, including signal processing, communications, networking, and machine learning. Numerical results show that the new method compares favorably to existing distributed algorithms on both convex and nonconvex problems.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The algorithm we will study in this paper crucially relies on tracking differences of gradients and is a minor variation of algorithms that have appeared in [73,74] and [15-17].”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [17]
In the citing paper
“However, none of the papers mentioned in this paragraph provide a theoretical analysis for strongly convex optimization problems over time-varying graphs , which is the goal of this paper.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [17]
Citations
Cites
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
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
Finite-Dimensional Variational Inequalities and Complementarity Problems
(2004) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/b97544 · Cited by 3,521
Constrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086
Optimization flow control. I. Basic algorithm and convergence
Low, S. H., & Lapsely, D. E. (1999) · IEEE/ACM Transactions on Networking · doi:10.1109/90.811451 · Cited by 1,972
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
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
Distributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187 · cited 1×
“Algorithms belonging to the former class include: i) consensus-based (sub)gradient schemes [1]–[4] along with their accelerated and asynchronous versions [5]–[7]; ii) the (sub)gradient push-method [8], [9]; iii) the dual-average method [10], [11]; and iv) distributed secondorder-based schemes [12], [13].”
MethodDiffusion LMS Strategies for Distributed Estimation
Cattivelli, F. S., & Sayed, A. H. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2033729 · Cited by 1,174
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
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
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Convergence in Multiagent Coordination, Consensus, and Flocking
Blondel, V. D., Hendrickx, J. M., Olshevsky, A., & Tsitsiklis, J. N. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1582620 · Cited by 859
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820
Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
Schizas, I. D., Ribeiro, A., & Giannakis, G. B. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.906734 · Cited by 685
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
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
Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2038417 · Cited by 510
Discrete-time dynamic average consensus
Zhu, M., & Martínez, S. (2010) · Automatica · doi:10.1016/j.automatica.2009.10.021 · Cited by 488
Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Chang, T.-H., Hong, M., & Wang, X. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2367458 · Cited by 444 · cited 1×
“Consider a network composed of I autonomous agents aiming to cooperatively and distributively solve Problem (1).”
Gradient Convergence in Gradient methods with Errors
Bertsekas, D. P., & Tsitsiklis, J. N. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497331063 · Cited by 437
Adaptation, Learning, and Optimization over Networks
Sayed, A. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781601988515 · Cited by 415
Consensus-based distributed support vector machines
Forero, P. A., Caño, A., & Giannakis, G. B. (2010) · Cited by 364
D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization
Mota, J. F. C., Xavier, J. M. F., Aguiar, P. M. Q., & Puschel, M. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2254478 · Cited by 363
Distributed 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
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers
Wei, E., & Ozdaglar, A. (2013) · 2013 IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6736937 · Cited by 342
Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
Scutari, G., Facchinei, F., Song, P., Palomar, D. P., & Pang, J.-S. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2293126 · Cited by 338
Self-citationPush-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 1×
“Algorithms belonging to the former class include: i) consensus-based (sub)gradien t schemes [1]–[4] along with their accelerated and asynchron ous versions [5]–[7]; ii) the (sub)gradient push-method [8], [ 9]; iii) the dual-average method [10], [11]; and iv) distributed sec ondorder-based schemes [12], [13].”
MethodProblems in Decentralized Decision making and Computation.
Tsitsiklis, J. N. (1984) · Defense Technical Information Center (DTIC) · Cited by 288
Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
Bianchi, P., & Jakubowicz, J. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2209984 · Cited by 245
Distributed optimization for cooperative agents: application to formation flight
Raffard, R. L., Tomlin, C. J., & Boyd, S. P. (2004) · 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601) · doi:10.1109/cdc.2004.1428778 · Cited by 245
Sparse Distributed Learning Based on Diffusion Adaptation
Di Lorenzo, P., & Sayed, A. H. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2232663 · Cited by 224
Self-citationNewton-Raphson Consensus for Distributed Convex Optimization
Varagnolo, D., Zanella, F., Cenedese, A., Pillonetto, G., & Schenato, L. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2449811 · Cited by 219
Schizas, I. D., Giannakis, G. B., Roumeliotis, S. I., & Ribeiro, A. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.908943 · Cited by 192
Asynchronous distributed optimization using a randomized alternating direction method of multipliers
Iutzeler, F., Bianchi, P., Ciblat, P., & Hachem, W. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760448 · Cited by 182
Distributed Maximum Likelihood Sensor Network Localization
Simonetto, A., & Leus, G. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2302746 · Cited by 176
Consensus-based distributed linear support vector machines
Forero, P. A., Cano, A., & Giannakis, G. B. (2010) · Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks · doi:10.1145/1791212.1791218 · Cited by 171
Parallel Selective Algorithms for Nonconvex Big Data Optimization
Facchinei, F., Scutari, G., & Sagratella, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2399858 · Cited by 162
Self-citationA fast distributed proximal-gradient method
Chen, A. I., & Ozdaglar, A. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483273 · Cited by 154
An Approximate Dual Subgradient Algorithm for Multi-Agent Non-Convex Optimization
Zhu, M., & Martínez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2228038 · Cited by 144
Locally constructed algorithms for distributed computations in ad-hoc networks
Scherber, D. S., & Papadopoulos, H. (2004) · International Symposium on Information Processing in Sensor Networks (IPSN) · doi:10.1145/984622.984625 · Cited by 112
Distributed Compressed Sensing for Static and Time-Varying Networks
Patterson, S., Eldar, Y. C., & Keidar, I. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2340812 · Cited by 97
Distributed Detection and Estimation in Wireless Sensor Networks
Barbarossa, S., Sardellitti, S., & Lorenzo, P. D. (2014) · Academic press library in signal processing · doi:10.1016/b978-0-12-396500-4.00007-7 · Cited by 96
Self-citationNewton-Raphson consensus for distributed convex optimization
Zanella, F., Varagnolo, D., Cenedese, A., Pillonetto, G., & Schenato, L. (2011) · IEEE Conference on Decision and Control and European Control Conference · doi:10.1109/cdc.2011.6160605 · Cited by 96
Distributed 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
Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data Optimization
Daneshmand, A., Facchinei, F., Kungurtsev, V., & Scutari, G. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2436357 · Cited by 78
Self-citationDistributed iterative thresholding for ℓ0/ℓ1-regularized linear inverse problems
Ravazzi, C., Fosson, S. M., & Magli, E. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2403263 · Cited by 51
Convergence and Applications of a Gossip-Based Gauss-Newton Algorithm
Li, X., & Scaglione, A. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2276440 · Cited by 41
Bianchi, P., Hachem, W., & Iutzeler, F. (2014) · arXiv (Cornell University) · Cited by 36
Diffusion Adaptation Strategies for Distributed Estimation Over Gaussian Markov Random Fields
Lorenzo, P. D. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2356433 · Cited by 25
Self-citationAn approximate dual subgradient algorithm for distributed non-convex constrained optimization
Zhu, M., & Martínez, S. (2010) · Cited by 20
Distributed average consensus for wireless sensor networks
Bénézit, F. (2009) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-4509 · Cited by 20
Mokhtari, A., Ling, Q. H., & Ribeiro, A. (2014) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2014.7094740 · Cited by 18
Mokhtari, A., Ling, Q. H., & Ribeiro, A. (2014) · Cited by 12
Utility Proportional Optimization Flow Control for Overlay Multicast
Jafari, A., Shafiei, H., Mirzasoleiman, B., & Sepidnam, G. (2009) · IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA) · doi:10.1109/ispa.2009.108 · Cited by 2
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
“The algorithm we will study in this paper crucially relies on tracking differences of gradients and is a minor variation of algorithms that have appeared in [73,74] and [15–17].”
MethodA survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Harnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
A review of cooperative multi-agent deep reinforcement learning
Oroojlooy, A., & Hajinezhad, D. (2023) · Applied Intelligence · doi:10.1007/s10489-022-04105-y · Cited by 482
Metadata
- Authors
- Lorenzo, P. D., & Scutari, G.
- Affiliations
- University of Perugia (IT)
- Purdue University West Lafayette (US)
- Venue
- IEEE Transactions on Signal and Information Processing over Networks
- Published
- 2016-06
- Volume
- 2
- Issue
- 2
- Pages
- 120-136
- ISSN
- 2373-776X (ISSN-L)
- 2373-7778
- OpenAlex
- W2266148951
- Cited by
- 473
- References
- 57
- Citations by year
- 2026: 12 · 2025: 43 · 2024: 45 · 2023: 55 · 2022: 45 · 2021: 63 · 2020: 68 · 2019: 62 · 2018: 45 · 2017: 21 · 2016: 13
- FWCI
- 44.34
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Signal and Information Processing over Networks (publishedVersion)
- IRIS Research product catalog (Sapienza University of Rome) (submittedVersion)
- Funders
- USA NSF (CIF 1564044)
- CAREER (1555850)
- ONR (N00014-16-1-2244)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Sensor Networks and Detection Algorithms
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Keywords
- multi-agent systems, time-varying connectedness, successive convex approximation, dynamic consensus, regularized optimization, sparsity, asymptotic convergence, in-network processing
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.