Fully Distributed And Mixed Symmetric Diagonal Dominant Solvers For Large Scale Optimization

Over the past twenty years, we have witnessed an unprecedented growth in data, inaugurating the so-called Big Data Epoch. Throughout these years, the exponential growth in the power of computer chips forecasted by Moore\u27s Law has allowed us to increasingly handle such growing data progression. However, due to the physical limitations on the size of transistors we have already reached the computational limits of traditional microprocessors\u27 architecture.Therefore, we either need conceptually new computers or distributed models of computation to allow processors to solve Big Data problems in a collaborative manner. The purpose of this thesis is to show that decentralized optimization is capable of addressing our growing computational demands by exploiting the power of coordinated data processing. In particular, we propose an exact distributed Newton method for two important challenges in large-scale optimization: Network Flow and Empirical Risk Minimization. The key observation behind our method is related to the symmetric diagonal dominant structure of the Hessian of dual functions correspondent to the aforementioned problems. Consequently, one can calculate the Newton direction by solving symmetric diagonal dominant (SDD) systems in a decentralized fashion. We first propose a fully distributed SDD solver based on a recursive approximation of SDD matrix inverses with a collection of specifically structured distributed matrices. To improve the precision of the algorithm, we then apply Richardson Preconditioners arriving at an efficient algorithm capable of approximating the solution of SDD system with any arbitrary precision. vi Our second fully distributed SDD solver significantly improves the computational performance of the rst algorithm by utilizing Chebyshev polynomials for an approximation of the SDD matrix inverse. The particular choice of Chebyshev polynomials is motivated by their extremal properties and their recursive relation. We then explore mixed strategies for solving SDD systems by slightly relaxing the decentralization requirements. Roughly speaking, by allowing for one computer to aggregate some particular information from all others, one can gain quite surprising computational benefits. The key idea is to construct a spectral sparsifier of the underlying graph of computers by using local communication between them. Finally, we apply these solvers for calculating the Newton direction for the dual function of Network Flow and Empirical Risk Minimization. On the theoretical side, we establish quadratic convergence rate for our algorithms surpassing all existing techniques. On the empirical side, we verify our superior performance in a set of extensive numerical simulations