Escaping Saddle Points Faster on Manifolds via Perturbed Riemannian Stochastic Recursive Gradient

Consider the following finite-sum and online optimization problem defined on Riemannian manifold $\mathcal{M}$:

where $F:\mathcal{M}\xrightarrow[]{}\mathbb{R}$ is a non-convex function. Finite-sum optimization setting is a special case of online setting where $\omega$ can be finitely sampled. For simplicity of analysis, we only consider finite-sum formulation $\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ and refer to it as online optimization when $n$ approaches infinity. Solving problem (1) globally on Euclidean space (i.e when $\mathcal{M}\equiv\mathbb{R}^{d}$) is NP-hard in general, letting alone for any Riemannian manifold. Thus many algorithms set out to find only approximate first-order critical points with small gradients. But this is usually insufficient because for non-convex problems, a point with small gradient can be either around a local minima, a local maxima or a saddle point. Therefore, to avoid being trapped by saddle points (and possibly local maxima), we need to find approximate second-order critical points (see Definition 1) with small gradients as well as nearly positive semi-definite Hessians.

Second-order algorithms can explore curvature information via Hessian and thus escape saddle points by construction. However, it is always desired that simpler algorithms using only gradient information are designed for this purpose, because access to Hessian can be costly and sometimes unavailable in real applications. It turns out that gradient descent (GD) can inherently escape saddle points, yet requiring exponential time (Du et al., 2017). Instead, Jin et al. (2017) showed that by injecting isotropic Gaussian noise to iterates, the perturbed gradient descent (PGD) can reach approximate $\epsilon$-second-order stationarity within $\widetilde{\mathcal{O}}(n\epsilon^{-2})$ stochastic gradient queries with high probability. Similarly, a perturbed variant of stochastic gradient algorithm (PSGD) requires a complexity of $\widetilde{\mathcal{O}}(\epsilon^{-4})$ (Jin et al., 2019). The complexities match that of vanilla GD and SGD to find approximate first-order stationary points up to some poly-logarithmic factors.

When considering problem (1) on any arbitrary manifold, we require Riemannian gradient $\text{grad}F(x)\in T_{x}\mathcal{M}$ as well as a retraction $R_{x}:T_{x}\mathcal{M}\xrightarrow[]{}\mathbb{R}$ that allows iterates to be updated on the manifold with direction determined by Riemannian gradient. Defining a ‘pullback’ function $\hat{F}_{x}:=F\circ R_{x}:T_{x}\mathcal{M}\xrightarrow{}\mathbb{R}$, Criscitiello and Boumal (2019) extended the idea of perturbed gradient descent (referred to as PRGD) by executing perturbations and the following gradient steps on the tangent space. Given that $\hat{F}_{x}$ is naturally defined on a vector space, the analysis can be largely drawn from (Jin et al., 2017), with similar convergence guarantees. Recently, Criscitiello and Boumal (2020) also proposed perturbed Riemannian accelerated gradient descent (PRAGD), a direct generalization of its Euclidean counterpart originally proposed in (Jin et al., 2018). It achieves an even lower complexity of $\widetilde{\mathcal{O}}(n\epsilon^{-7/4})$ compared to perturbed GD. However, these algorithms are sub-optimal under finite-sum settings and even fail to work for online problems where full gradient is inaccessible.

When objective can be decomposed into component functions as in problem (1), variance reduction techniques can improve gradient complexity of both GD and SGD (Reddi et al., 2016; Nguyen et al., 2017b; Fang et al., 2018). The main idea is to exploit past gradient information to correct for deviation of current stochastic gradients, by comparing either to a fixed snapshot point (SVRG, Reddi et al. (2016)) or recursively to previous iterates (SRG/SPIDER, Nguyen et al. (2017a); Fang et al. (2018)). Notably, the gradient complexities $\mathcal{O}(\sqrt{n}\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-3})$ achieved by SRG and SPIDER are optimal to achieve first-order guarantees under finite-sum and online settings respectively (Fang et al., 2018; Arjevani et al., 2019). Motivated by the success of variance reduction and the simplicity of adding perturbation to ensure second-order convergence, Li (2019) proposed perturbed stochastic recursive gradient method (PSRG), which can escape saddle points faster than perturbed GD and SGD. In this paper, we generalize PSRG to optimization problems defined on Riemannian manifolds with the following contributions:

• •

  Our proposed method PRSRG is the first simple stochastic algorithm that achieves second-order guarantees on Riemannian manifold using only first-order information. That is, the algorithm only requires simple perturbations and does not involve any negative curvature exploitation as in PRAGD. Our algorithm adopts the idea of tangent space steps as in (Criscitiello and Boumal, 2019), which results in simple analysis for convergence.

• •

  Our complexity is measured against $(\epsilon,\delta)$-second-order stationarity, which is more general than $\epsilon$-second-order stationarity where $\delta=\mathcal{O}(\sqrt{\epsilon})$. Under finite-sum setting, PRSRG strictly improves the complexity of PRGD by $\widetilde{\mathcal{O}}(\min\{n/\epsilon^{1/2},$ $\sqrt{n}/\epsilon^{2}\})$ and is superior to PRAGD when $n\geq\epsilon^{-1/2}$. We also provide a complexity of PRSRG under online setting, which is novel for Riemannian optimization.

Following the work by (Jin et al., 2017), except for the perturbed SGD (Jin et al., 2019) and perturbed accelerated gradient method (Jin et al., 2018), Ge et al. (2019) showed that SVRG with perturbation (PSVRG) is sufficient to escape saddle points and a stabilized version is also developed to further improve the dependency on the Hessian Lipschitz constant. However, its complexity is strictly worse than PSRG (Li, 2019). We suspect that, with similar tangent space trick, PSVRG can be generalized to Riemannian manifolds with little efforts.

Another line of research is to incorporate negative curvature search subroutines (Xu et al., 2018; Allen-Zhu and Li, 2018) in some classic first-order algorithms, such as GD and SGD and also variance-reduction algorithms including SVRG (Allen-Zhu and Li, 2018), SNVRG (Zhou et al., 2018) and SPIDER (Fang et al., 2018). It usually requires access to Hessian-vector products when searching for the smallest eigenvector direction (Xu et al., 2018). Even though Allen-Zhu and Li (2018) managed to only use first-order information for the same goal, it still involves an iterative process that can be difficult to implement in practice.

To solve general optimization problems on Riemannian manifold, gradient descent and stochastic gradient descent have been generalized with provable guarantees (Boumal et al., 2019; Bonnabel, 2013; Hosseini and Sra, 2020). Some acceleration and variance reduction techniques have also been considered for speeding up the convergence of GD and SGD (Zhang and Sra, 2018; Ahn and Sra, 2020; Zhang et al., 2016; Kasai et al., 2018). These first-order methods however can only guarantee first-order convergence. To find second-order critical points, Newton’s methods, particularly the famous globalization variants, trust region and cubic regularization have been extended to manifold optimization, achieving similar second-order guarantees (Boumal et al., 2019; Agarwal et al., 2018).

Finally, we note that Sun et al. (2019) also proposed perturbed gradient descent on manifold. The perturbations and the following updates are performed directly on manifold, which is contrastly different to tangent space steps in this paper. The preference of tangent space steps over manifold steps is mainly due to the complexity of analysis. That is, Sun et al. (2019) requires more complicated geometric results as well as the use of exponential map given its natural connection to geodesics and Riemannian distance. By executing all the steps on tangent space, we can bypass these results while some regularity conditions should be carefully managed.

Here we start with a short review of some preliminary definitions. Readers can refer to (Absil et al., 2009) for more detailed discussions on manifold geometry. We consider $\mathcal{M}$ to be a $d$-dimensional Riemannian manifold. The tangent space $T_{x}\mathcal{M}$ for $x\in\mathcal{M}$ is a $d$-dimensional vector space. $\mathcal{M}$ is equipped with an inner product $\langle\cdot,\cdot\rangle_{x}$ and a corresponding norm $\|\cdot\|_{x}$ on each tangent space $T_{x}\mathcal{M}$, $\forall\,x\in\mathcal{M}$. Tangent bundle is the union of tangent spaces defined as $T\mathcal{M}:=\{(x,u):x\in\mathcal{M},u\in T_{x}\mathcal{M}\}$. Riemannian gradient of a function $F:\mathcal{M}\xrightarrow[]{}\mathbb{R}$ is the vector field $\text{grad}F$ that uniquely satisfies $\text{D}F(x)[u]=\langle\text{grad}F(x),u\rangle_{x}$, for all $(x,u)\in T\mathcal{M}$ where D$F(x)[u]$ is the directional derivative of $F(x)$ along $u$. Riemannian Hessian of $F$ is the covariant derivative of grad$F$ defined as that for all $(x,u)\in T\mathcal{M}$, it satisfies $\text{Hess}F(x)[u]=\nabla_{u}\text{grad}F(x)$, where $\nabla$ is the Riemannian connection (also known as Levi-Civita connection). Note that we also use $\nabla$ to represent differentiation on vector space, which is a special case of covariant derivative.

Retraction $R_{x}:T_{x}\mathcal{M}\xrightarrow{}\mathcal{M}$ maps a tangent vector to manifold surface by satisfying (i) $R_{x}(0)=x$, and (ii) $\text{D}R_{x}(0)$ is the identity map. $\text{D}R_{x}(u)$ represents the differential of retraction, denoted as $T_{u}:T_{x}\mathcal{M}\xrightarrow{}T_{R_{x}(u)}\mathcal{M}$. Exponential map is a special instance of retraction and hence our results in this paper can be trivially generalized to this particular retraction. Define the pullback function $\hat{F}_{x}:=F\circ R_{x}:T_{x}\mathcal{M}\xrightarrow{}\mathbb{R}$. That is, $\hat{F}_{x}(u)=\frac{1}{n}\sum_{i=1}^{n}\hat{f}_{i,x}(u)$ $=\frac{1}{n}\sum_{i=1}^{n}{f}_{i}(R_{x}(u))$, where we also define the pullback components as $\hat{f}_{i,x}:=f_{i}\circ R_{x}$. Given that the domain of pullback function is a vector space, we can represent its gradient $\nabla\hat{F}_{x}$ and Hessian $\nabla^{2}\hat{F}_{x}$ in terms of Riemannian gradient and Hessian as well as the differentiated retraction $T_{u}$ in the following Lemma (see Lemma 2.5 in Criscitiello and Boumal (2020)).

If the retraction $R_{x}$ is a second-order retraction, $\nabla\hat{F}_{x}(0)$ and $\nabla^{2}\hat{F}_{x}(0)$ match the Riemannian gradient and Hessian at $x$. See Lemma 8 (Appendix B) for more details. Vector transport $\mathcal{T}$ with respect to retraction $R_{x}$ is a linear map that $\mathcal{T}:T\mathcal{M}\,\oplus\,T\mathcal{M}\xrightarrow[]{}T\mathcal{M}$ satisfies (i) $\mathcal{T}_{u}[\xi]\in T_{R_{x}(u)}\mathcal{M}$; (ii) $\mathcal{T}_{0_{x}}[\xi]=\xi$. In this paper, we only consider isometric vector transport, which satisfies $\langle\xi,v\rangle_{x}=\langle\mathcal{T}_{u}\xi,\mathcal{T}_{u}v\rangle_{R_{x}(u)}$. Below are some common notations used throughout this paper.

Notation. Denote $\lambda_{\min}(H)$ as the minimum eigenvalue of a symmetric operator $H$ and use $\|\cdot\|$ to represent either the vector norm or the spectral norm for a matrix. We claim $h(t)=\mathcal{O}(g(t))$ if there exists a positive constant $M$ and $t_{0}$ such that $h(t)\leq Mg(t)$ for all $t\geq t_{0}$ and use $\widetilde{\mathcal{O}}(\cdot)$ to hide poly-logarithmic factors. Let $\mathbb{B}_{x}(r)$ be the Euclidean ball with radius $r$ to the origin of the tangent space $T_{x}\mathcal{M}$. That is, $\mathbb{B}_{x}(r):=\{u\in T_{x}\mathcal{M}:\|u\|_{x}\leq r\}$. We use $\text{Unif}(\mathbb{B}_{x}(r))$ to denote the uniform distribution on the set $\mathbb{B}_{x}(r)$. Denote $[n]:=\{1,2,..,n\}$ and let $\nabla\hat{f}_{\mathcal{I},x}(u)=\frac{1}{|\mathcal{I}|}\sum_{i\in\mathcal{I}}\nabla\hat{f}_{i,x}(u)$ be a mini-batch gradient of the pullback component function where $\mathcal{I}\subseteq[n]$ with cardinality $|\mathcal{I}|$. Similarly, $\text{grad}f_{\mathcal{I}}(x)$ represents a mini-batch Riemannian gradient. Finally, we denote $\log(x)$ as the natural logarithm and $\log_{\alpha}(x)$ as logarithm with base $\alpha$.

In this section, we introduce perturbed Riemannian stochastic recursive gradient method (PRSRG) in Algorithm 1 where the main updates are performed by tangent space stochastic recursive gradient (TSSRG) in Algorithm 2. The key idea is simple: when gradient is large, we repeatedly execute $m$ standard recursive gradient iterations (i.e. an epoch) on tangent space before retracting back to the manifold. Essentially, we are minimizing the pullback function $\hat{F}_{x}$ within the constraint ball by SRG updates, which translates to minimizing $F$ within a neighbourhood of $x$.

This process repeats until gradient is small. Then we perform the same SRG updates but at most $\mathscr{T}$ times, from a perturbed iterate with isotropic noise added on the tangent space. Notice that the small gradient condition in Line 3 in Algorithm 1 is examined against $\text{grad}f_{\mathcal{B}}(x)$, where $\mathcal{B}$ contains $B$ samples drawn without replacement from $[n]$. This is to ensure that full batch gradient is computed under finite-sum setting where we choose $B=n$. Under online setting when $n$ approaches infinity, access to full gradient is unavailable and therefore we can only rely on the large-batch gradient.

TSSRG is mainly based on stochastic recursive gradient algorithm in (Nguyen et al., 2017b). The algorithm adopts a double-loop structure. At the start of each outer loop (called an epoch), a full gradient (or a large-batch gradient for online optimization) is evaluated. Within each inner loop, mini-batch gradients are computed for current iterate $u_{t}$ and its last iterate $u_{t-1}$. Then a modified gradient $v_{t}$ at $u_{t}$ is constructed recursively based on the difference between $v_{t-1}$ and mini-batch gradient at $u_{t-1}$. That is,

Note that we do not require any vector transporter since all gradients (of the pullback) are defined on the same tangent space. Hence, TSSRG is very similar to Euclidean SRG with only differences in stopping criteria, discussed as follows. When gradient is large, we perform at most $m$ updates and break the loop with probability $\frac{1}{m-k+1}$ where $k$ is the index of inner iteration (Line 12, Algorithm 2). This stopping rule is equivalent to uniformly selecting from iterates within this epoch at random as the output. This is to ensure that either small gradient condition is triggered or sufficient decrease is achieved. More details can be found in Section 6. When gradient is small (i.e. around saddle point), we only break until max iteration has been reached.

Finally, we note that the Lipschitzness conditions are only guaranteed within a constraint ball of radius $D$ while taking $\mathscr{T}$ updates on tangent space can violate this requirement. Therefore, in Line 9 (Algorithm 2), we explicitly control the deviation of iterates from the origin and break the loop as soon as one iterate leaves the ball. Then we return some points on the boundary of the ball. By carefully balancing the parameters, we can show that whenever iterates escape the constraint ball, function value already has a large decrease.

To simplify notations, for the most time, we refer to Algorithm 2 as TSSRG($x,u_{0},\mathscr{T}$).

In this section, we present the main complexity results of PRSRG in finding second-order stationary points.

Under finite-sum setting, we choose $B=n$ and thus $\text{grad}f_{\mathcal{B}}\equiv\text{grad}F$. We set the parameters as in (3) while we also require first-order tolerance $\epsilon\leq\widetilde{\mathcal{O}}(\frac{D\sqrt{L}}{m\sqrt{\eta}})$. This is not a strict condition given step size $\eta$ can be chosen arbitrarily small. The second-order tolerance $\delta$ needs to be smaller than the Lipschitz constant $\ell$ in Assumption 2. Otherwise when $\delta>\ell$, any $x\in\mathcal{M}$ with small gradient $\|\text{grad}F(x)\|\leq\epsilon$ is already a $(\epsilon,\delta)$-second-order stationary point because by $\|\lambda_{\min}(\nabla\hat{F}_{x}(0))\|\leq\ell$ from Assumption 2, we have $\lambda_{\min}(\text{Hess}F(x))=\lambda_{\min}(\nabla\hat{F}_{x}(0))\geq-\ell\geq-\delta$.

Up to some constants and poly-log factors, the complexity in Theorem 1 is exactly the same as that when optimization domain is a vector space (i.e. $\mathcal{M}\equiv\mathbb{R}^{d}$). Indeed, our result is a direct generalization of the Euclidean counterpart where retraction $R_{x}(u)=x+u$ and the Lipschitzness conditions are made with respect to $F:\mathbb{R}^{d}\xrightarrow[]{}\mathbb{R}$. Set the same parameters as in (3) except that we do not require $\epsilon$ to be small since $D=+\infty$ and require $\delta\leq L$ given $\ell=L$. Then we can recover the Euclidean perturbed stochastic recursive gradient algorithm (Li, 2019).

Under online setting, the complexities of stochastic gradient queries are presented below.

Note the complexities in this paper are analysed in terms of achieving $(\epsilon,\delta)$-second-order stationarity. Some literature prefers to choose $\delta=\sqrt{\rho\epsilon}$ to match the units of gradient and Hessian, following the work in (Nesterov and Polyak, 2006). In this case, our complexities reduce to $\widetilde{\mathcal{O}}(\frac{n}{\epsilon^{3/2}}+\frac{\sqrt{n}}{\epsilon^{2}})$ for finite-sum problems and $\widetilde{\mathcal{O}}(\frac{1}{\epsilon^{7/2}})$ for online problems. Compared to the optimal rate of $\mathcal{O}(\frac{\sqrt{n}}{\epsilon^{2}})$ and $\mathcal{O}(\frac{1}{\epsilon^{3}})$ in finding first-order stationary points, our rates are sub-optimal even if we ignore the poly-log factors. This nevertheless appears to be a problem for all stochastic variance reduction methods (Ge et al., 2019; Li, 2019).

Now we provide a high-level proof road map of our proposed method in achieving second-order convergence guarantees. The main proof strategies are similar as in (Li, 2019). However, we need to carefully handle the particularity of manifold geometry as well as manage the unique regularity conditions. We focus on finite-sum problems and only highlight the key differences under online setting.

In this paper, we generalize perturbed stochastic recursive gradient method to Riemannian manifold by adopting the idea of tangent space steps introduced in (Criscitiello and Boumal, 2019). This avoids using any complicated geometric result as in (Sun et al., 2019) and thus largely simplifies the analysis. We show that up to some constants and poly-log factors, our generalization achieves the same stochastic gradient complexities as the Euclidean version (Li, 2019). Under finite-sum setting, our result is strictly superior to PRGD by Criscitiello and Boumal (2019) and to PRAGD by Criscitiello and Boumal (2020) for large-scale problems. We also prove an online complexity, which is, to the best of our knowledge, the first result in finding second-order stationary points only using first-order information.

This section presents some useful concentration bounds on vector space, which is used to derive high probability bounds for sequences defined on tangent space of the manifold.