On the Rate of Convergence and Byzantine Resilience of Decentralized Optimization Algorithms over Connected Networks

The present work concerns practical and theoretical aspects regarding decentralized optimization over distributed connected networks, specifically, their rate of convergence and resilience against byzantine attacks. These two aspects are discussed within the framework of common consensus strategies, such as the Relaxed Alternating Direction Method of Multipliers (R-ADMM) and Consensus Algorithms via Stochastic Matrices. Concerning the rate of convergence in the decentralized setting, we focus our attention to regular graphs holding functions of the same convexity, this allows for a simplification of the R-ADMM algorithm to linear form analysable with respect to the eigenvalues of the matrix dictating the convergence. The result of the analysis highlights heavily the importance of hyperparameters chosen beyond the classical values used in the ADMM, notably increasing the rate of convergence of the algorithm. Numerical simulations supporting the evidence of the theoretical analysis are provided. The second part of this work discusses Byzantine attacks, the general setup in which they are studied and common strategies used for dealing with this critical security issue. In this section the setting is restricted by limiting our attention towards problems in which the objective functions in each node are all equal. This section heads towards an improved strategy for identifying and filtering adversarial agents. From a theoretical perspective, this involves non-trivial challenges such as ensuring convergence, optimality of the solution, and correct synchronized distributed filtering. The proposed solution addresses these challenges with satisfactory results. To conclude this portion, numerical simulations were performed on popular machine learning datasets to showcase the effectiveness of the proposed strategy. This thesis aims to collaborate to the understanding and development of decentralized optimization due to its importance to the field of Control Systems. The results presented are important both practically and theoretically, having implications for areas such as multiagent coordination, security over networked components, and decentralized learning. It is in our hope that the present work encourages future work, especially regarding convergence and optimality analysis on consensus algorithms as well security of networked systems under byzantine attacks.