Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation

Technical Summary: Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation

Problem Statement
The paper addresses the problem of computing the leading-$k$ eigenspace of a symmetric matrix $A \in \mathbb{S}^d$ in a heterogeneous distributed setting. The matrix is given in a finite-sum form $A = \frac{1}{n}\sum_{i=1}^n A_i$, where each $A_i$ is stored locally by a worker. The objective is to solve the trace minimization problem:
$$\min_{W \in \mathcal{S}_t(d,k)} F(W) := -\text{tr}(W^\top A W)$$
where $\mathcal{S}_t(d,k)$ is the Stiefel manifold. Due to the invariance of the objective under right orthogonal transformations, the decision variable represents a point on the Grassmannian manifold $\text{Gr}(d,k)$. The authors focus on asynchronous optimization, where updates occur immediately upon the arrival of worker results without waiting for global synchronization, thereby avoiding the "straggler" problem common in synchronous distributed methods.

Methodology: GRASSIA
The authors propose GRASSIA (GRASSmannian Incremental Aggregation), a method that adapts the Incremental Aggregated Gradient (IAG) framework to the geometry of the Grassmannian.

1. Transport-Free Aggregation: Unlike standard Riemannian optimization which requires parallel transport of gradients between tangent spaces (a costly operation), GRASSIA maintains a table of cached component gradients $G_i^t = \text{grad } F_i(W^{t-\tau_i(t)})$. These gradients are treated as ambient matrix quantities in $\mathbb{R}^{d \times k}$. The algorithm aggregates these stale gradients in the ambient space:
   $$G^t = \frac{1}{n} \sum_{i=1}^n G_i^t$$
   The update is performed via an extrinsic polar step:
   $$W^{t+1} = \text{Polar}(W^t - \eta G^t)$$
   where $\text{Polar}(\cdot)$ maps a full-column-rank matrix to the nearest point on the Stiefel manifold. The authors prove that despite the extrinsic nature of the update, the induced first-order motion on the Grassmannian is precisely the negative projection of the stale aggregate onto the current tangent space, avoiding the need for explicit vector transport.

2. Incremental Updates: The aggregate $G^t$ is updated incrementally. When a subset of workers $S_{t+1}$ returns new gradients, the aggregate is corrected by the difference between the new and old cached gradients, ensuring low per-update computational cost independent of the total number of components $n$.

Key Theoretical Contributions

1. Tight Angle-Dependent Gradient Dominance:
   The paper establishes that the eigenspace objective does not possess a uniform global gradient-dominance (Polyak-Łojasiewicz) constant. Instead, the authors derive a tight, angle-dependent inequality:
   $$\frac{1}{2}\|\text{grad } F(W)\|_F^2 \geq 2\delta \cos^2(\theta_k) (F(W) - F^*)$$
   where $\delta = \lambda_k(A) - \lambda_{k+1}(A)$ is the eigengap and $\theta_k$ is the largest principal angle between the current subspace and the target eigenspace. The coefficient $2\delta \cos^2(\theta_k)$ is shown to be pointwise tight, deteriorating to zero as $\theta_k \to \pi/2$. This provides a sharper spectral dependence than previous bounds.

2. Basin Invariance:
   A critical challenge in asynchronous analysis is proving that stale information does not drive the iterates out of the region where the gradient-dominance condition holds. The authors prove a basin-invariance property: under a specific stepsize condition, the iterates remain within a fixed angular neighborhood of the target eigenspace. This is achieved via a Lyapunov function that balances objective decrease against the potential increase in geodesic distance caused by stale gradients.

3. Two-Phase Linear Convergence:
   Combining the basin invariance with the angle-dependent gradient dominance, the paper establishes linear convergence rates:

   • Broad-Basin Regime: For initialization within a prescribed broad basin, the iteration complexity is $O(\tau \delta^{-3/2} \log(1/(\delta \varepsilon)))$.
   • Local Regime: Once iterates enter a sharper local region (defined by a stronger objective-gap condition), the complexity improves to $O((\tau + 1)\delta^{-1} \log(1/\varepsilon))$.
     Crucially, the constants depend on the spectral spreads ($\nu_i = \lambda_1(A_i) - \lambda_d(A_i)$) rather than absolute spectral norms, making the convergence guarantees shift-invariant (invariant under $A_i \to A_i + c_i I$).

Results and Experimental Validation

• Theoretical Comparison: The paper compares GRASSIA against Orthogonal Iteration, Riemannian Gradient Descent (RGD), Block Oja, VR-PCA, and the existing IARG method (restricted to $k=1$). GRASSIA is the first method to achieve linear convergence for asynchronous $k$-dimensional eigenspace computation on the Grassmannian with an eigengap dependence of $O(\delta^{-1})$ in the local regime, improving upon the $O(\delta^{-2})$ dependence of prior asynchronous or variance-reduced methods.
• Numerical Experiments:
  • Serial Setting: On real-world datasets (LIBSVM a1a, w1a), GRASSIA demonstrates superior sample efficiency compared to Block Oja, VR-PCA, and IARG with deflation. It achieves lower geodesic distances with fewer data passes.
  • Distributed Setting: On a heterogeneous CIFAR-10 setup with 20 workers of varying speeds, GRASSIA outperforms synchronous RGD (which suffers from stragglers) and non-aggregated delayed methods (Delayed-Oja) in wall-clock time. The results confirm that stale-gradient aggregation preserves the low latency of incremental updates while maintaining search direction accuracy.

Significance and Claims
The paper claims to fill a theoretical gap in asynchronous optimization on manifolds. Specifically, it provides the first convergence theory for asynchronous leading-$k$ subspace computation that:

1. Avoids the computational overhead of parallel transport.
2. Offers shift-invariant convergence guarantees.
3. Achieves linear convergence with optimal eigengap dependence ($O(\delta^{-1})$) without requiring full-gradient passes or synchronized rounds.

The authors position GRASSIA as a framework for asynchronous Riemannian optimization that tailors stale-update control and basin invariance to the specific geometry of the objective, suggesting applicability beyond eigenspace computation to a wider class of manifold optimization problems.