Decentralized Riemannian Gradient Descent on the Stiefel Manifold
- URL: http://arxiv.org/abs/2102.07091v1
- Date: Sun, 14 Feb 2021 07:30:23 GMT
- Title: Decentralized Riemannian Gradient Descent on the Stiefel Manifold
- Authors: Shixiang Chen, Alfredo Garcia, Mingyi Hong, Shahin Shahrampour
- Abstract summary: We consider a distributed non-sensian optimization where a network of agents aims at minimizing a global function over the Stiefel manifold.
To have exact with constant use, we also propose a decentralized gradient (DRA) for the Stiefel manifold.
- Score: 39.750623187256735
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a distributed non-convex optimization where a network of agents
aims at minimizing a global function over the Stiefel manifold. The global
function is represented as a finite sum of smooth local functions, where each
local function is associated with one agent and agents communicate with each
other over an undirected connected graph. The problem is non-convex as local
functions are possibly non-convex (but smooth) and the Steifel manifold is a
non-convex set. We present a decentralized Riemannian stochastic gradient
method (DRSGD) with the convergence rate of $\mathcal{O}(1/\sqrt{K})$ to a
stationary point. To have exact convergence with constant stepsize, we also
propose a decentralized Riemannian gradient tracking algorithm (DRGTA) with the
convergence rate of $\mathcal{O}(1/K)$ to a stationary point. We use multi-step
consensus to preserve the iteration in the local (consensus) region. DRGTA is
the first decentralized algorithm with exact convergence for distributed
optimization on Stiefel manifold.
Related papers
- Decentralized Riemannian Conjugate Gradient Method on the Stiefel
Manifold [59.73080197971106]
This paper presents a first-order conjugate optimization method that converges faster than the steepest descent method.
It aims to achieve global convergence over the Stiefel manifold.
arXiv Detail & Related papers (2023-08-21T08:02:16Z) - Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
We focus on the Stiefel manifold in the decentralized setting, where a connected network of agents in $nMn log-1)$ are tested.
We propose an method called the decentralized subgradient method (DRSM)$ for forcing a natural station below $nMn log-1)$.
arXiv Detail & Related papers (2023-03-31T02:56:23Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
The minimax algorithms for neural networks have been developed to solve many problems.
In this paper, we propose two types of minimax algorithms.
For the setting, we propose DRSGDA and prove that our method achieves a gradient.
arXiv Detail & Related papers (2023-02-08T01:42:45Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
In this paper, we consider solving the distributed optimization problem under the communication restricted setting.
We show the method over com-pressed exact diffusion termed CEDAS"
In particular, when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when when
arXiv Detail & Related papers (2023-01-14T09:49:15Z) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
This paper investigates the distributed non optimization problem of minimizing a global cost function formed by the summation of $ZOn$ local cost functions.
Agents approximate their own ZO coordinate method to solve the problem.
arXiv Detail & Related papers (2021-03-24T03:07:46Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
The finite descent-ascent parameters (GDA) has been widely applied to solve minimax optimization problems.
This paper fills such a gap by studying the convergence of the KL-Lized geometry.
arXiv Detail & Related papers (2021-02-09T05:35:53Z) - A Multi-Agent Primal-Dual Strategy for Composite Optimization over
Distributed Features [52.856801164425086]
We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
arXiv Detail & Related papers (2020-06-15T19:40:24Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
Decentralized convex optimization is proposed to minimize a sum of smooth and strongly cost functions when the functions are distributed over a directed network nodes.
In particular, we propose thetextbftextttS-ADDOPT algorithm that assumes a first-order oracle at each node.
For decaying step-sizes$mathcalO (1/k)$, we show thattextbfttS-ADDOPT reaches the exact solution subly at$mathcalO (1/k)$ and its convergence is networkally-independent
arXiv Detail & Related papers (2020-05-15T21:14:22Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions.
In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
arXiv Detail & Related papers (2020-02-10T23:23:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.