Iterative pre-conditioning for expediting the distributed gradient-descent method: the case of linear least-squares problem
From MaRDI portal
Publication:2071934
Abstract: This paper considers the multi-agent linear least-squares problem in a server-agent network. In this problem, the system comprises multiple agents, each having a set of local data points, that are connected to a server. The goal for the agents is to compute a linear mathematical model that optimally fits the collective data points held by all the agents, without sharing their individual local data points. This goal can be achieved, in principle, using the server-agent variant of the traditional iterative gradient-descent method. The gradient-descent method converges linearly to a solution, and its rate of convergence is lower bounded by the conditioning of the agents' collective data points. If the data points are ill-conditioned, the gradient-descent method may require a large number of iterations to converge. We propose an iterative pre-conditioning technique that mitigates the deleterious effect of the conditioning of data points on the rate of convergence of the gradient-descent method. We rigorously show that the resulting pre-conditioned gradient-descent method, with the proposed iterative pre-conditioning, achieves superlinear convergence when the least-squares problem has a unique solution. In general, the convergence is linear with improved rate of convergence in comparison to the traditional gradient-descent method and the state-of-the-art accelerated gradient-descent methods. We further illustrate the improved rate of convergence of our proposed algorithm through experiments on different real-world least-squares problems in both noise-free and noisy computation environment.
Recommendations
- A Distributed Normalized Explicit Preconditioned Conjugate Gradient Method
- A preconditioner for least-squares distributed parameter estimation
- On the convergence of the conditional gradient method in distributed optimization problems
- Distributed iteratively reweighted least squares and applications
- A preconditioned conjugate gradient method on a distributed memory multiprocessor
- Linear convergence of primal-dual gradient methods and their performance in distributed optimization
- Exact spectral-like gradient method for distributed optimization
- Fast Distributed Gradient Methods
- Scalable distributed least square algorithms for large-scale linear equations via an optimization approach
- Gradient-free distributed optimization with exact convergence
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 1274356 (Why is no real title available?)
- scientific article; zbMATH DE number 1460605 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- Analysis and design of optimization algorithms via integral quadratic constraints
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- Application of machine learning techniques for supply chain demand forecasting
- Distributed Solution of Large-Scale Linear Systems via Accelerated Projection-Based Consensus
- Linear hypothesis testing in dense high-dimensional linear models
- Some methods of speeding up the convergence of iteration methods
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
Cited in
(4)- A control theoretic framework for adaptive gradient optimizers
- A Distributed Normalized Explicit Preconditioned Conjugate Gradient Method
- Scalable distributed least square algorithms for large-scale linear equations via an optimization approach
- Reduced-order identification methods: hierarchical algorithm or variable elimination algorithm
This page was built for publication: Iterative pre-conditioning for expediting the distributed gradient-descent method: the case of linear least-squares problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2071934)
