Scalable Distributed Least Squares Algorithm for Linear Algebraic Equations via Scheduling
In this work, we propose a novel discrete-time distributed algorithm for finding least squares solutions of linear algebraic equations with a scheduling protocol to further enhance its scalability. Each agent in the network is assumed to know some rows of the coefficient matrix and the corresponding entries in the observation vector. Unlike typical distributed algorithms, our approach considers communication bandwidth limits, allowing agents to transmit only a portion of their `guessed" solution, independent of its dimension. A periodic scheduling protocol determines which portion is transmitted at each iteration. Assuming a small fixed step size and a diagonalizable algorithm matrix, we prove that agents' `guessed" solutions converge exponentially to a least squares solution. For cases where the observation vectors are time-varying, a modified algorithm guarantees practical convergence, with tracking error bounded by the single-step variation in the observation vector. Simulations on both small-scale and medium-scale examples validate the feasibility of our algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingSimilar Papers 제목 키워드 기반
Scalable Reinforcement Learning for Linear-Quadratic Control of Networks
Distributed optimal control is known to be challenging and can become intractable even for linear-quadratic regulator problems. In this work, we study a special class of such problems where distributed state feedback con…
reinforcement-learningReinforcement LearningDeepLM: Large-Scale Nonlinear Least Squares on Deep Learning Frameworks Using Stochastic Domain Decomposition
We propose a novel approach for large-scale nonlinear least squares problems based on deep learning frameworks. Nonlinear least squares are commonly solved with the Levenberg-Marquardt (LM) algorithm for fast converg…
Deep LearningDistributed OptimizationA Resilient Distributed Algorithm for Solving Linear Equations
This paper presents a resilient distributed algorithm for solving a system of linear algebraic equations over a multi-agent network in the presence of Byzantine agents capable of arbitrarily introducing untrustworthy inf…
Accelerating Distributed SGD for Linear Regression using Iterative Pre-Conditioning
This paper considers the multi-agent distributed linear least-squares problem. The system comprises multiple agents, each agent with a locally observed set of data points, and a common server with whom the agents can int…
regressionDistributed learning with regularized least squares
We study distributed learning with the least squares regularization scheme in a reproducing kernel Hilbert space (RKHS). By a divide-and-conquer approach, the algorithm partitions a data set into disjoint data subsets, a…