Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem

This paper considers the multi-agent linear least-squares problem in a server-agent network architecture. The system comprises multiple agents, each with a set of local data points. The agents are connected to a server, and there is no inter-agent communication. The agents' goal is to compute a linear model that optimally fits the collective data. The agents, however, cannot share their data points. In principle, the agents can solve this problem by collaborating with the server using the server-agent network variant of the classical gradient-descent method. However, when the data points are ill-conditioned, the gradient-descent method requires a large number of iterations to converge. We propose an iterative pre-conditioning technique to mitigate the deleterious impact of the data points' conditioning on the convergence rate of the gradient-descent method. Unlike the conventional preconditioning techniques, the pre-conditioner matrix used in our proposed technique evolves iteratively. We show that our proposed algorithm converges linearly with an improved rate of convergence in comparison to both the classical and the accelerated gradient-descent methods. For the special case, when the solution of the least-squares problem is unique, our algorithm converges to the solution superlinearly. Through numerical experiments on benchmark least-squares problems, we validate our theoretical findings, and also demonstrate our algorithm's improved robustness against process noise. (C) 2021 Elsevier Ltd. All rights reserved.

On Preconditioning of Decentralized Gradient-Descent When Solving a System of Linear Equations

Nirupam Gupta

This article considers solving an overdetermined system of linear equations in peer-to-peer multiagent networks. The network is assumed to be synchronous and strongly connected. Each agent has a set of local data points, and their goal is to compute a linear model that fits the collective data points. In principle, the agents can apply the decentralized gradient-descent method (DGD). However, when the data matrix is ill-conditioned, DGD requires many iterations to converge and is unstable against system noise. We propose a decentralized preconditioning technique to mitigate the deleterious effects of the data points' conditioning on the convergence rate of DGD. The proposed algorithm converges linearly, with an improved convergence rate than DGD. Considering the practical scenario where the computations performed by the agents are corrupted, we study the robustness guarantee of the proposed algorithm. In addition, we apply the proposed algorithm for solving decentralized state estimation problems. The empirical results show our proposed state predictor's favorable convergence rate and robustness against system noise compared to prominent decentralized algorithms.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

OrthoNet: Multilayer Network Data Clustering

Giovanni Chierchia, Mireille El Gheche, Pascal Frossard

Network data appears in very diverse applications, like biological, social, or sensor networks. Clustering of network nodes into categories or communities has thus become a very common task in machine learning and data mining. Network data comes with some information about the network edges. In some cases, this network information can even be given with multiple views or layers, each one representing a different type of relationship between the network nodes. Increasingly often, network nodes also carry a feature vector. We propose in this paper to extend the node clustering problem, that commonly considers only the network information, to a problem where both the network information and the node features are considered together for learning a clustering-friendly representation of the feature space. Specifically, we design a generic two-step algorithm for multilayer network data clustering. The first step aggregates the different layers of network information into a graph representation given by the geometric mean of the network Laplacian matrices. The second step uses a neural net to learn a feature embedding that is consistent with the structure given by the network layers. We propose a novel algorithm for efficiently training the neural net via gradient descent, which encourages the neural net outputs to span the leading eigenvectors of the aggregated Laplacian matrix, in order to capture the pairwise interactions on the network, and provide a clustering-friendly representation of the feature space. We demonstrate with an extensive set of experiments on synthetic and real datasets that our method leads to a significant improvement w.r.t. state-of-the-art multilayer graph clustering algorithms, as it judiciously combines nodes features and network information in the node embedding algorithms.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Accelerated SGD for Non-Strongly-Convex Least Squares

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre

We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, as

O(d/t)

while accelerating the forgetting of the initial conditions to

O(d/t^2)

. Our new algorithm is based on a simple modification of the accelerated gradient descent. We provide convergence results for both the averaged and the last iterate of the algorithm. In order to describe the tightness of these new bounds, we present a matching lower bound in the noiseless setting and thus show the optimality of our algorithm.

2022

Accelerated SGD for Non-Strongly-Convex Least Squares

Nicolas Henri Bernard Flammarion, Aditya Vardhan Varre

O(d/t)

while accelerating the forgetting of the initial conditions to

O(d/t^2)

2022