Average-Case Optimization Analysis for Distributed Consensus Algorithms on Regular Graphs

N. T. Nguyen ; A. V. Rogozin ; A. V. Gasnikov

Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 907-931.

Résumé

The consensus problem in distributed computing involves a network of agents aiming to compute the average of their initial vectors through local communication, represented by an undirected graph. This paper focuses on studying this problem using an average-case analysis approach, particularly over regular graphs. Traditional algorithms for solving the consensus problem often rely on worst-case performance evaluation scenarios, which may not reflect typical performance in real-world applications. Instead, we apply average-case analysis, focusing on the expected spectral distribution of eigenvalues to obtain a more realistic view of performance. Key contributions include deriving the optimal method for consensus on regular graphs, showing its relation to the Heavy Ball method, analyzing its asymptotic convergence rate, and comparing it to various first-order methods through numerical experiments.

Détail

Keywords: consensus problem, average-case analysis, regular graph

Bibliographie

[1] Berthier, R., Bach, F., and Gaillard, P., “Accelerated Gossip in Networks of Given Dimension Using Jacobi Polynomial Iterations”, SIAM J. Math. Data Sci., 2:1 (2020), 24–47 | DOI | MR | Zbl

[2] Hestenes, M. R. and Stiefel, E., “Methods of Conjugate Gradients for Solving Linear Systems”, J. Research Nat. Bur. Standards, 49:6 (1952), 409–436 | DOI | MR | Zbl

[3] Pedregosa, F., Residual Polynomials and the Chebyshev Method, , 2020 fa.bianp.net

[4] Pedregosa, F., Momentum: When Chebyshev Meets Chebyshev, , 2020 fa.bianp.net

[5] Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D., “Randomized Gossip Algorithms”, IEEE Trans. Inform. Theory, 52:6 (2006), 2508–2530 | DOI | MR | Zbl

[6] Cao, M., Spielman, D. A., and Yeh, E. M., “Accelerated Gossip Algorithms for Distributed Computation”, Proc. of the 44th Annual Allerton Conf. on Communication, Control, and Computation (Monticello, Ill., USA, Sep 2006), 952–959

[7] Rebeschini, P. and Tatikonda, S. C., “Accelerated Consensus via Min-Sum Splitting”, Proc. of the 31st Annual Conf. on Neural Information Processing Systems (NIPS, Long Beach, Calif., USA, Dec 2017), 11 pp.

[8] Pedregosa, F. and Scieur, D., “Acceleration through Spectral Density Estimation”, Proc. of the 37th Internat. Conf. on Machine Learning (PMLR, 2020), 7553–7562

[9] Li, W. W. and Solé, P., “Spectra of Regular Graphs and Hypergraphs and Orthogonal Polynomials”, Europ. J. Combinatorics, 17:5 (1996), 461–477 | DOI | MR | Zbl

[10] Scieur, D. and Pedregosa, F., “Universal Average-Case Optimality of Polyak Momentum”, Proc. of the 37th Internat. Conf. on Machine Learning (PMLR, 2020), 8565–8572

[11] Ding, X. and Jiang, T., “Spectral Distributions of Adjacency and Laplacian Matrices of Random Graphs”, Ann. Appl. Probab., 20:6 (2010), 2086–2117 | DOI | MR | Zbl

[12] Gorbunov, E., Rogozin, A., Beznosikov, A., Dvinskikh, D., and Gasnikov, A., “Recent Theoretical Advances in Decentralized Distributed Convex Optimization”, High-Dimensional Optimization and Probability: With a View towards Data Science, Springer Optimization and Its Applications, 191, eds. A. Nikeghbali, P. M. Pardalos, A. M. Raigorodskii, M. T. Rassias, Springer, Cham, 2022, 253–325 | DOI | MR | Zbl

[13] Rogozin, A., Gasnikov, A., Beznosikov, A., and Kovalev, D., “Decentralized Convex Optimization over Time-Varying Graphs”, Encyclopedia of Optimization, eds. P. M. Pardalos, O. A. Prokopyev, Springer, Cham, 2023, 1–17 | MR

[14] Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L., “Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks”, Proc. of the 34th Internat. Conf. on Machine Learning, Sydney, NSW, Australia, Aug 2017, 3027–3036 | MR

[15] Georgopoulos, L. and Hasler, M., “Distributed Machine Learning in Networks by Consensus”, Neurocomputing, 124 (2014), 2–12 | DOI

[16] Tsianos, K. I., Lawlor, S., and Rabbat, M. G., “Consensus-Based Distributed Optimization: Practical Issues and Applications in Large-Scale Machine Learning”, Proc. of the 50th Annual Allerton Conf. on Communication, Control, and Computing (Monticello, Ill., USA, Oct 2012), 1543–1550

[17] Nesterov, Yu., Lectures on Convex Optimization, Springer Optimization and Its Applications, 137, 2nd ed., Springer, Cham, 2018, xxiii, 589 pp. | DOI | MR | Zbl

[18] Nemirovski, A., Information-Based Complexity of Convex Programming: Lecture Notes (Fall Semester 1994/95), , 268 pp. isye.gatech.edu

[19] Knuth, D. E., The Art of Computer Programming: Vol. 3. Sorting and Searching, 2nd ed., Addison-Wesley, New York, 1998, xiv, 780 pp. | MR

[20] Hoare, C. A. R., “Quicksort”, Comput. J., 5:1 (1962), 10–16 | DOI | MR

[21] Borgwardt, K. H., “Probabilistic Analysis of the Simplex Method”, DGOR/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with NSOR, Operations Research Proceedings, eds. H. Schellhaas, P. Beek, H. Isermann, R. Schmidt, M. Zijlstra, Springer, Berlin, 1988, 564–575, 670 pp.

[22] Spielman, D. A. and Teng, S.-H., “Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time”, J. ACM, 51:3 (2004), 385–463 | DOI | MR | Zbl

[23] Katz, J. and Lindell, Y., “Private-Key Encryption”, Introduction to Modern Cryptography, 2nd ed., Chapman Hall/CRC, New York, 2014, 77–82 | MR

[24] Bogdanov, A. and Trevisan, L., “Average-Case Complexity”, Found. Trends Theor. Comput. Sci., 2:1 (2006), 1–106 | DOI | MR

[25] Paquette, C., van Merriënboer, B., Paquette, E., and Pedregosa, F., “Halting Time Is Predictable for Large Models: A Universality Property and Average-Case Analysis”, Found. Comput. Math., 23:2 (2023), 597–673 | DOI | MR | Zbl

[26] Cunha, L., Gidel, G., Pedregosa, F., Scieur, D., and Paquette, C., “Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime”, Proc. of the 39th Internat. Conf. on Machine Learning (Baltimore, Md., USA, Jul 2022), 4474–4491

[27] Nedic, A. and Ozdaglar, A., “Distributed Subgradient Methods for Multi-Agent Optimization”, IEEE Trans. Autom. Control, 54:1 (2009), 48–61 | DOI | MR | Zbl

[28] Duchi, J. C., Agarwal, A., and Wainwright, M. J., “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling”, IEEE Trans. Autom. Control, 57:3 (2012), 592–606 | DOI | MR | Zbl

[29] Metelev, D., Rogozin, A., Kovalev, D., and Gasnikov, A., Is Consensus Acceleration Possible in Decentralized Optimization over Slowly Time-Varying Networks?, Proc. of the 40th Internat. Conf. on Machine Learning (ICML'23, Honolulu, H.I., USA, Jul 2023), 24532–24554 | MR

[30] Dokl. RAN. Math. Inf. Proc. Upr., 514:2 (2023), 158–168 (Russian) | DOI | MR | Zbl

[31] Nesterov, Yu., Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, 87, Springer, New York, 2004, xviii, 236 pp. | DOI | MR

[32] Taylor, A. B., Hendrickx, J. M., and Glineur, F., “Smooth Strongly Convex Interpolation and Exact Worst-Case Performance of First-Order Methods”, Math. Program., 161:1–2 (2017), 307–345 | DOI | MR | Zbl

[33] d'Aspremont, A., Scieur, D., and Taylor, A., “Acceleration Methods”, Found. Trends Optimiz., 5:1–2 (2021), 1–245 | DOI

[34] Arioli, M. and Scott, J., “Chebyshev Acceleration of Iterative Refinement”, Numer. Algor., 66:3 (2014), 591–608 | DOI | MR | Zbl

[35] Kühn, R., “Spectra of Random Stochastic Matrices and Relaxation in Complex Systems”, Europhys. Lett., 109:6 (2015), Art. 60003, 5 pp. | DOI | MR

[36] Fischer, B., Polynomial Based Iteration Methods for Symmetric Linear Systems, Wiley-Teubner Ser. Adv. in Num. Math., Teubner, Stuttgart, 1996, 283 pp. | MR | Zbl

[37] Fischer, B., Polynomial Based Iteration Methods for Symmetric Linear Systems, Classics in Appl. Math., 68, SIAM, Philadelphia, Pa., 2011, 283 pp. | MR | Zbl

[38] Polyak, B., Introduction to Optimization, Optimization Software, Inc., New York, 1987 | MR

[39] Frankel, S. P., “Convergence Rates of Iterative Treatments of Partial Differential Equations”, Math. Tables Aids Comput., 4 (1950), 65–75 | DOI | MR

[40] Hochstrasser, U., Die Anwendung der Methode der konjugierten Gradienten und ihrer Modifikationen auf die Lösung linearer Randwertprobleme, PhD Thesis, Eidgenössische Technische Hochschule Zürich (ETHZ), Zürich, Schweiz, 1954, 48 pp. | MR

[41] Rutishauser, H., “Theory of Gradient Methods”, Refined Iterative Methods for Computation of the Solution and the Eigenvalues of Self-Adjoint Boundary Value Problems, Engeli, M., Ginsburg, Th., Rutishauser, H., and Stiefel, E., Mitteilungen aus dem Institut für Angewandte Mathematik, Birkhäuser, Basel, 1959, 24–49, 107 pp. | MR

[42] Zh. Vychisl. Mat. Mat. Fiz., 4:5 (1964), 791–803 (Russian) | DOI | MR

[43] Paquette, C., van Merriënboer, B., Paquette, E., and Pedregosa, F., “Halting Time Is Predictable for Large Models: A Universality Property and Average-Case Analysis”, Found. Comput. Math., 23:2 (2023), 597–673 | DOI | MR | Zbl

[44] Mirchev, M., “On the Spectra of Scale-Free and Small-World Networks”, Electronica + Electrotechnika, 54:1–2 (2019), 9–16

[45] Samukhin, A. N., Dorogovtsev, S. N., and Mendes, J. F. F., Laplacian Spectra of, and Random Walks on, Complex Networks: Are Scale-Free Architectures Really Important?, Phys. Rev. E (3), 77:3 (2008), Art. 036115, 19 pp. | DOI | MR

[46] Vershik, A. M. and Sporyshev, P. V., “Estimation of the Mean Number of Steps in the Simplex Method, and Problems of Asymptotic Integral Geometry”, Dokl. Akad. Nauk SSSR, 271:5 (1983), 1044–1048 (Russian) | MR | Zbl

[47] Smale, S., “On the Average Number of Steps of the Simplex Method of Linear Programming”, Math. Program., 27:3 (1983), 241–262 | DOI | MR | Zbl

[48] Goujaud, B., Scieur, D., Dieuleveut, A., Taylor, A. B., and Pedregosa, F., “Super-Acceleration with Cyclical Step-Sizes”, Proc. of the 25th Internat. Conf. on Artificial Intelligence and Statistics (AISTATS, Valencia, Spain, Apr 2022), 3028–3065

[49] Hagberg, A., Swart, P. J. and Schult, D. A., “Exploring Network Structure, Dynamics, and Function Using NetworkX”, SciPy 2008: Proc. of the 7th Python in Science Conf., eds. G. Varoquaux, T. Vaught, J. Millman, Los Alamos National Laboratory (LANL), Los Alamos, N.M., 2008, 11–15

[50] Braca, P., Marano, S., and Matta, V., “Running Consensus in Wireless Sensor Networks”, Proc. of the 11th Internat. Conf. on Information Fusion (Cologne, Germany, 2008), 6 pp.