Decentralized Riemannian Gradient Descent on the Stiefel Manifold

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.

References in corpus (11)

• Constrained Consensus
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Global rates of convergence for nonconvex optimization on manifolds
• Stochastic Gradient Push for Distributed Deep Learning
• Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data
• Orthogonal Weight Normalization: Solution to Optimization over Multiple Dependent Stiefel Manifolds in Deep Neural Networks
• A Linearly Convergent Algorithm for Distributed Principal Component Analysis
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Distributed Optimization on Riemannian Manifolds for multi-agent networks