N. Alon, D. Vitali, and . Milman, ? 1 , isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, series B, vol.38, pp.73-88, 1985.

M. Arioli and J. Scott, Chebyshev acceleration of iterative refinement, Numerical Algorithms, vol.66, issue.3, pp.591-608, 2014.

Y. Arjevani and O. Shamir, Communication complexity of distributed convex learning and optimization, Advances in Neural Information Processing Systems (NeurIPS), pp.1756-1764, 2015.

Q. Ling-aryan, W. Mokhtari, A. Shi, and . Ribeiro, A decentralized second-order method with exact linear convergence rate for consensus optimization, IEEE Transactions on Signal and Information Processing over Networks, vol.2, issue.4, pp.507-522, 2016.

W. Auzinger, Iterative Solution of Large Linear Systems. Lecture notes, 2011.

S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), vol.14, issue.SI, pp.2508-2530, 2006.

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, vol.3, pp.1-122, 2011.

S. Bubeck, Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, vol.8, pp.231-357, 2015.

S. Bubeck, Q. Jiang, Y. Lee, Y. Li, and A. Sidford, Complexity of highly parallel non-smooth convex optimization, 2019.

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, vol.40, issue.1, pp.120-145, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00490826

, Convex Distributed Optimization in Networks

J. C. Duchi, A. Agarwal, and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Transactions on Automatic Control, vol.57, issue.3, pp.592-606, 2012.

J. C. Duchi, P. L. Bartlett, and M. J. Wainwright, Randomized smoothing for stochastic optimization, SIAM Journal on Optimization, vol.22, issue.2, pp.674-701, 2012.

D. Dvinskikh and A. Gasnikov, Decentralized and Parallelized Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems, 2019.

L. He, A. Bian, and M. Jaggi, Cola: Decentralized linear learning, Advances in Neural Information Processing Systems (NeurIPS), pp.4536-4546, 2018.

N. He, A. Juditsky, and A. Nemirovski, Mirror prox algorithm for multi-term composite minimization and semi-separable problems, Computational Optimization and Applications, vol.61, issue.2, pp.275-319, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01335905

H. Hendrikx, F. Bach, and L. Massoulié, An accelerated decentralized stochastic proximal algorithm for finite sums, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02280763

H. Hendrikx, L. Massoulié, and F. Bach, Accelerated decentralized optimization with local updates for smooth and strongly convex objectives, International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
URL : https://hal.archives-ouvertes.fr/hal-01893568

M. Jaggi, V. Smith, M. Takác, J. Terhorst, S. Krishnan et al., Communication-efficient distributed dual coordinate ascent, Advances in Neural Information Processing Systems (NeurIPS), pp.3068-3076, 2014.

D. Jakoveti?, A unification and generalization of exact distributed first-order methods, IEEE Transactions on Signal and Information Processing over Networks, vol.5, issue.1, pp.31-46, 2019.

D. Jakoveti?, J. Xavier, and J. M. Moura, Fast distributed gradient methods, IEEE Transactions on Automatic Control, vol.59, issue.5, pp.1131-1146, 2014.

D. Jakoveti?, M. F. José, J. Moura, and . Xavier, Linear convergence rate of a class of distributed augmented lagrangian algorithms, IEEE Transactions on Automatic Control, vol.60, issue.4, pp.922-936, 2015.

E. Arroyo, Efficient distributed estimation of inverse covariance matrices, IEEE Statistical Signal Processing Workshop (SSP), pp.1-5, 2016.

Z. Jiang, A. Balu, C. Hegde, and S. Sarkar, Collaborative deep learning in fixed topology networks, Advances in Neural Information Processing Systems (NeurIPS), pp.5904-5914, 2017.

A. Koloskova, S. Stich, and M. Jaggi, Decentralized stochastic optimization and gossip algorithms with compressed communication, International Conference on Machine Learning (ICML), pp.3478-3487, 2019.

S. Lacoste-julien, M. Schmidt, and F. Bach, A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00768187

G. Lan, S. Lee, and Y. Zhou, Communication-efficient algorithms for decentralized and stochastic optimization, 2017.

J. D. Lee, Q. Liu, Y. Sun, and J. E. Taylor, Communication-efficient sparse regression, Journal of Machine Learning Research, vol.18, issue.5, pp.1-30, 2017.

A. Mokhtari and A. Ribeiro, DSA: Decentralized double stochastic averaging gradient algorithm, Journal of Machine Learning Research, vol.17, issue.1, pp.2165-2199, 2016.

J. Moreau, Proximité et dualité dans un espace Hilbertien. Bulletin de la Société Mathématique de France, vol.93, pp.273-299, 1965.

A. Nedic and A. Olshevsky, Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control, vol.60, issue.3, pp.601-615, 2015.

A. Nedic and A. Olshevsky, Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Transactions on Automatic Control, vol.61, issue.12, pp.3936-3947, 2016.

A. Nedic and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, vol.54, issue.1, pp.48-61, 2009.

A. Nedic, A. Olshevsky, and W. Shi, Linearly convergent decentralized consensus optimization over directed networks, IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp.485-489, 2016.

A. Nedic, A. Olshevsky, and W. Shi, Achieving geometric convergence for distributed optimization over time-varying graphs, SIAM Journal on Optimization, vol.27, issue.4, pp.2597-2633, 2017.

Y. Nesterov, Introductory Lectures on Convex Optimization : a Basic Course, 2004.

S. Pu, W. Shi, J. Xu, and A. Nedic, A push-pull gradient method for distributed optimization in networks, IEEE Conference on Decision and Control (CDC), pp.3385-3390, 2018.

G. Qu and N. Li, Accelerated distributed nesterov gradient descent for smooth and strongly convex functions, Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.209-216, 2016.

K. Scaman, F. Bach, S. Bubeck, Y. Lee, and L. Massoulié, Optimal algorithms for smooth and strongly convex distributed optimization in networks, International Conference on Machine Learning (ICML), pp.3027-3036, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01478317

K. Scaman, F. Bach, S. Bubeck, L. Massoulié, and Y. Lee, Optimal algorithms for non-smooth distributed optimization in networks, Advances in Neural Information Processing Systems (NeurIPS), pp.2740-2749, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01957013

A. Necdet-serhat-aybat, M. Fallah, A. Gurbuzbalaban, and . Ozdaglar, A Universally Optimal Multistage Accelerated Stochastic Gradient Method, 2019.

O. Shamir, Fundamental limits of online and distributed algorithms for statistical learning and estimation, Advances in Neural Information Processing Systems (NeurIPS), pp.163-171, 2014.

W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Transactions on Signal Processing, vol.62, issue.7, pp.1750-1761, 2014.

W. Shi, Q. Ling, G. Wu, and W. Yin, EXTRA: An exact first-order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, vol.25, issue.2, pp.944-966, 2015.

U. Sebastian and . Stich, Local SGD converges fast and communicates little. arXiv e-prints, 2018.

L. Tian and Q. Gu, Communication-efficient Distributed Sparse Linear Discriminant Analysis, International Conference on Artificial Intelligence and Statistics (AIS-TATS), pp.1178-1187, 2017.

A. César, S. Uribe, A. Lee, A. Gasnikov, and . Nedic, A dual approach for optimal algorithms in distributed optimization over networks, 2018.

S. Vaswani, F. Bach, and M. Schmidt, Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron, International Conference on Artificial Intelligence and Statistics (AISTATS), pp.1195-1204, 2019.

E. Wei and A. Ozdaglar, Distributed alternating direction method of multipliers, IEEE Conference on Decision and Control (CDC), pp.5445-5450, 2012.

C. Xi and U. A. Khan, Dextra: A fast algorithm for optimization over directed graphs, IEEE Transactions on Automatic Control, vol.62, issue.10, pp.4980-4993, 2017.

R. Xin, D. Jakoveti?, and U. A. Khan, Distributed nesterov gradient methods over arbitrary graphs, IEEE Signal Processing Letters, vol.26, issue.8, pp.1247-1251, 2019.