Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Introduction

Stochastic gradient descent is one of the basic algorithms in optimization. It is often used to solve the following stochastic optimization problem

When the function $f(w)$ is convex, convergence of stochastic gradient descent is well-understood (Rakhlin et al.,, 2012; Shalev-Shwartz et al.,, 2009). However, stochastic gradient descent is not only limited to convex functions. Especially, in the context of neural networks, stochastic gradient descent is known as the “backpropagation” algorithm (Rumelhart et al.,, 1988), and has been the main algorithm that underlies the success of deep learning (Bengio,, 2009). However, the guarantees in the convex setting does not transfer to the non-convex settings.

Optimizing a non-convex function is NP-hard in general. The difficulty comes from two aspects. First, a non-convex function may have many local minima, and it might be hard to find the best one (global minimum) among them. Second, even finding a local minimum might be hard as there can be many saddle points which have -gradient but are not local minimaSee Section 3 for definition of saddle points.. In the most general case, there is no known algorithm that guarantees to find a local minimum in polynomial number of steps. The discrete analog (finding local minimum in domains like $\{0,1\}^{n}$) has been studied in complexity theory and is PLS-complete (Johnson et al.,, 1988).

In many cases, especially in those related to deep neural networks (Dauphin et al.,, 2014) (Choromanska et al.,, 2014), the main bottleneck in optimization is not due to local minima, but the existence of many saddle points. Gradient based algorithms are in particular susceptible to saddle point problems as they only rely on the gradient information. The saddle point problem is alleviated for second-order methods that also rely on the Hessian information (Dauphin et al.,, 2014).

However, using Hessian information usually increases the memory requirement and computation time per iteration. As a result many applications still use stochastic gradient and empirically get reasonable results. In this paper we investigate why stochastic gradient methods can be effective even in presence of saddle point, in particular we answer the following question:

Question: Given a non-convex function $f$ with many saddle points, what properties of $f$ will guarantee stochastic gradient descent to converge to a local minimum efficiently?

We identify a property of non-convex functions which we call strict saddle. Intuitively, this property guarantees local progress if we have access to the Hessian information. Surprisingly we show with only first order (gradient) information, stochastic gradient can escape the saddle points efficiently. We give a framework for analyzing stochastic gradient in both unconstrained and equality-constrained case using this property.

We apply our framework to orthogonal tensor decomposition, which is a core problem in learning many latent variable models (see discussion in 2.2). The tensor decomposition problem is inherently susceptible to the saddle point issues, as the problem asks to find $d$ different components and any permutation of the true components yields a valid solution. Such symmetry creates exponentially many local minima and saddle points in the optimization problem. Using our new analysis of stochastic gradient, we give the first online algorithm for orthogonal tensor decomposition with global convergence guarantee. This is a key step towards making tensor decomposition algorithms more scalable.

Given a function $f(w)$ that is twice differentiable, we call $w$ a stationary point if $\nabla f(w)=0$. A stationary point can either be a local minimum, a local maximum or a saddle point. We identify an interesting class of non-convex functions which we call strict saddle. For these functions the Hessian of every saddle point has a negative eigenvalue. In particular, this means that local second-order algorithms which are similar to the ones in (Dauphin et al.,, 2014) can always make some progress.

It may seem counter-intuitive why stochastic gradient can work in these cases: in particular if we run the basic gradient descent starting from a stationary point then it will not move. However, we show that the saddle points are not stable and that the randomness in stochastic gradient helps the algorithm to escape from the saddle points.

Suppose $f(w)$ is strict saddle (see Definition 5), Noisy Gradient Descent (Algorithm 1) outputs a point that is close to a local minimum in polynomial number of steps.

Online tensor decomposition

Requiring all saddle points to have a negative eigenvalue may seem strong, but it already allows non-trivial applications to natural non-convex optimization problems. As an example, we consider the orthogonal tensor decomposition problem. This problem is the key step in spectral learning for many latent variable models (see more discussions in Section 2.2).

We design a new objective function for tensor decomposition that is strict saddle.

Combining this new objective with our framework for analyzing stochastic gradient in non-convex setting, we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee.

2 Related Works

In optimization theory and economics, there are extensive works on understanding functions that behave similarly to convex functions (and in particular can be optimized efficiently). Such notions involve pseudo-convexity (Mangasarian,, 1965), quasi-convexity (Kiwiel,, 2001), invexity(Hanson,, 1999) and their variants. More recently there are also works that consider classes that admit more efficient optimization procedures like RSC (restricted strong convexity) (Agarwal et al.,, 2010). Although these classes involve functions that are non-convex, the function (or at least the function restricted to the region of analysis) still has a unique stationary point that is the desired local/global minimum. Therefore these works cannot be used to prove global convergence for problems like tensor decomposition, where by symmetry of the problem there are multiple local minima and saddle points.

Second-order algorithms

The most popular second-order method is the Newton’s method. Although Newton’s method converges fast near a local minimum, its global convergence properties are less understood in the more general case. For non-convex functions, (Frieze et al.,, 1996) gave a concrete example where second-order method converges to the desired local minimum in polynomial number of steps (interestingly the function of interest is trying to find one component in a $4$-th order orthogonal tensor, which is a simpler case of our application). As Newton’s method often converges also to saddle points, to avoid this behavior, different trusted-region algorithms are applied (Dauphin et al.,, 2014).

Stochastic gradient and symmetry

The tensor decomposition problem we consider in this paper has the following symmetry: the solution is a set of $d$ vectors $v_{1},...,v_{d}$. If $(v_{1},v_{2},...,v_{d})$ is a solution, then for any permutation $\pi$ and any sign flips $\kappa\in\{\pm 1\}^{d}$, $(..,\kappa_{i}v_{\pi(i)},...)$ is also a valid solution. In general, symmetry is known to generate saddle points, and variants of gradient descent often perform reasonably in these cases (see (Saad and Solla,, 1995), (Rattray et al.,, 1998), (Inoue et al.,, 2003)). The settings in these work are different from ours, and none of them give bounds on number of steps required for convergence.

There are many other problems that have the same symmetric structure as the tensor decomposition problem, including the sparse coding problem (Olshausen and Field,, 1997) and many deep learning applications (Bengio,, 2009). In these problems the goal is to learn multiple “features” where the solution is invariant under permutation. Note that there are many recent papers on iterative/gradient based algorithms for problems related to matrix factorization (Jain et al.,, 2013; Saxe et al.,, 2013). These problems often have very different symmetry, as if $Y=AX$ then for any invertible matrix $R$ we know $Y=(AR)(R^{-1}X)$. In this case all the equivalent solutions are in a connected low dimensional manifold and there need not be saddle points between them.

Preliminaries

1 Stochastic Gradient Descent

The stochastic gradient aims to solve the stochastic optimization problem (1), which we restate here:

Recall $\phi(w,x)$ denotes the loss function evaluated for sample $x$ at point $w$. The algorithm follows a stochastic gradient

where $x_{t}$ is a random sample drawn from distribution $\mathcal{D}$ and $\eta$ is the learning rate.

In the more general setting, stochastic gradient descent can be viewed as optimizing an arbitrary function $f(w)$ given a stochastic gradient oracle.

In this case the update step of the algorithm becomes $w_{t+1}=w_{t}-\eta SG(w_{t})$.

Traditional analysis for stochastic gradient often assumes the function is smooth and strongly convex. A function is $\beta$-smooth if for any two points $w_{1},w_{2}$,

When $f$ is twice differentiable this is equivalent to assuming that the spectral norm of the Hessian matrix is bounded by $\beta$. We say a function is $\alpha$-strongly convex if the Hessian at any point has smallest eigenvalue at least $\alpha$ ($\lambda_{min}(\nabla^{2}f(w))\geq\alpha$).

Using these two properties, previous work (Rakhlin et al.,, 2012) shows that stochastic gradient converges at a rate of $1/t$. In this paper we consider non-convex functions, which can still be $\beta$-smooth but cannot be strongly convex.

Smoothness of Hessians

We also require the Hessian of the function $f$ to be smooth. We say a function $f(w)$ has $\rho$-Lipschitz Hessian if for any two points $w_{1},w_{2}$ we have

This is a third order condition that is true if the third order derivative exists and is bounded.

2 Tensors decomposition

Tensors can be constructed from tensor products. We use $(u\otimes v)$ to denote a $2$nd order tensor where $(u\otimes v)_{i,j}=u_{i}v_{j}$. This generalizes to higher order and we use $u^{\otimes 4}$ to denote the $4$-th order tensor

where $a_{i}$’s are orthonormal vectors that satisfy $\|a_{i}\|=1$ and $a_{i}^{T}a_{j}=0$ for $i\neq j$. We call the vectors $a_{i}$’s the components of this decomposition. Such a decomposition is unique up to permutation of $a_{i}$’s and sign-flips.

Stochastic gradient descent for strict saddle function

In this section we discuss the properties of saddle points, and show if all the saddle points are well-behaved then stochastic gradient descent finds a local minimum for a non-convex function in polynomial time.

For a twice differentiable function $f(w)$, we call the points stationary points if their gradients are equal to . Stationary points could be local minima, local maxima or saddle points. By local optimality conditions (Wright and Nocedal,, 1999), in many cases we can tell what type a point $w$ is by looking at its Hessian: if $\nabla^{2}f(w)$ is positive definite then $w$ is a local minimum; if $\nabla^{2}f(w)$ is negative definite then $w$ is a local maximum; if $\nabla^{2}f(w)$ has both positive and negative eigenvalues then $w$ is a saddle point. These criteria do not cover all the cases as there could be degenerate scenarios: $\nabla^{2}f(w)$ can be positive semidefinite with an eigenvalue equal to 0, in which case the point could be a local minimum or a saddle point.

If a function does not have these degenerate cases, then we say the function is strict saddle:

A twice differentiable function $f(w)$ is strict saddle, if all its local minima have $\nabla^{2}f(w)\succ 0$ and all its other stationary points satisfy $\lambda_{min}(\nabla^{2}f(w))<0$.

Intuitively, if we are not at a stationary point, then we can always follow the gradient and reduce the value of the function. If we are at a saddle point, we need to consider a second order Taylor expansion:

Since the strict saddle property guarantees $\nabla^{2}f(w)$ to have a negative eigenvalue, there is always a point that is near $w$ and has strictly smaller function value. It is possible to make local improvements as long as we have access to second order information. However it is not clear whether the more efficient stochastic gradient updates can work in this setting.

To make sure the local improvements are significant, we use a robust version of the strict saddle property:

A twice differentiable function $f(w)$ is $(\alpha,\gamma,\epsilon,\delta)$-strict saddle, if for any point $w$ at least one of the following is true

$\lambda_{min}(\nabla^{2}f(w))\leq-\gamma$.

There is a local minimum $w^{\star}$ such that $\|w-w^{\star}\|\leq\delta$, and the function $f(w^{\prime})$ restricted to $2\delta$ neighborhood of $w^{\star}$ ($\|w^{\prime}-w^{\star}\|\leq 2\delta$) is $\alpha$-strongly convex.

Intuitively, this condition says for any point whose gradient is small, it is either close to a robust local minimum, or is a saddle point (or local maximum) with a significant negative eigenvalue.

We purpose a simple variant of stochastic gradient algorithm, where the only difference to the traditional algorithm is we add an extra noise term to the updates. The main benefit of this additional noise is that we can guarantee there is noise in every direction, which allows the algorithm to effectively explore the local neighborhood around saddle points. If the noise from stochastic gradient oracle already has nonnegligible variance in every direction, our analysis also applies without adding additional noise. We show noise can help the algorithm escape from saddle points and optimize strict saddle functions.

Often analysis of stochastic gradient descent uses decreasing learning rates and the algorithm converges to a local (or global) minimum. Since the function is strongly convex in the small region close to local minimum, we can use Theorem 6 to first find a point that is close to a local minimum, and then apply standard analysis of SGD in the strongly convex case (where we decrease the learning rate by $1/t$ and get $1/\sqrt{t}$ convergence in $\|w-w^{\star}\|$).

In the next part we sketch the proof of the main theorem. Details are deferred to Appendix A.

2 Proof sketch

In order to prove Theorem 6, we analyze the three cases in Definition 5. When the gradient is large, we show the function value decreases in one step (see Lemma 7); when the point is close to a local minimum, we show with high probability it cannot escape in the next polynomial number of iterations (see Lemma 8).

The proof of this lemma is a simple application of the smoothness property.

The proof of this lemma is similar to the standard analysis (Rakhlin et al.,, 2012) of stochastic gradient descent in the smooth and strongly convex setting, except we only have local strongly convexity. The proof appears in Appendix A.

The hardest case is when the point is “close” to a saddle point: it has gradient smaller than $\epsilon$ and smallest eigenvalue of the Hessian bounded by $-\gamma$. In this case we show the noise in our algorithm helps the algorithm to escape:

Intuitively, at point $w_{t}$ there is a good direction that is hiding in the Hessian. The hope of the algorithm is that the additional (or inherent) noise in the update step makes a small step towards the correct direction, and then the gradient information will reinforce this small perturbation and the future updates will “slide” down the correct direction.

3 Constrained Problems

In many cases, the problem we are facing are constrained optimization problems. In this part we briefly describe how to adapt the analysis to problems with equality constraints (which suffices for the tensor application). Dealing with general inequality constraint is left as future work.

in general we need to consider the set of points in a low dimensional manifold that is defined by the constraints. In particular, in the algorithm after every step we need to project back to this manifold (see Algorithm 2 where $\Pi_{\mathcal{W}}$ is the projection to this manifold).

For constrained optimization it is common to consider the Lagrangian:

Under common regularity conditions, it is possible to compute the value of the Lagrangian multipliers:

We can also define the tangent space, which contains all directions that are orthogonal to all the gradients of the constraints: $\mathcal{T}(w)=\{v:\nabla c_{i}(w)^{T}v=0;~{}i=1,\cdots,m\}$. In this case the corresponding gradient and Hessian we consider are the first-order and second-order partial derivative of Lagrangian $\mathcal{L}$ at point $(w,\lambda^{*}(w))$:

We replace the gradient and Hessian with $\chi(w)$ and $\mathfrak{M}(w)$, and when computing eigenvectors of $\mathfrak{M}(w)$ we focus on its projection on the tangent space. In this way, we can get a similar definition for strict saddle (see Appendix B), and the following theorem.

Detailed discussions and formal version of this theorem are deferred to Appendix B.

Online Tensor Decomposition

In this section we describe how to apply our stochastic gradient descent analysis to tensor decomposition problems. We first give a new formulation of tensor decomposition as an optimization problem, and show that it satisfies the strict saddle property. Then we explain how to compute stochastic gradient in a simple example of Independent Component Analysis (ICA) (Hyvärinen et al.,, 2004).

where the components $a_{i}$’s are orthonormal vectors ($\|a_{i}\|=1$, $a_{i}^{T}a_{j}=0$ for $i\neq j$), the goal of orthogonal tensor decomposition is to find the components $a_{i}$’s.

This problem has inherent symmetry: for any permutation $\pi$ and any set of $\kappa_{i}\in\{\pm 1\},i\in[d]$, we know $u_{i}=\kappa_{i}a_{\pi(i)}$ is also a valid solution. This symmetry property makes the natural optimization problems non-convex.

In this section we will give a new formulation of orthogonal tensor decomposition as an optimization problem, and show that this new problem satisfies the strict saddle property.

Previously, Frieze et al., (1996) solves the problem of finding one component, with the following objective function

In Appendix C.1, as a warm-up example we show this function is indeed strict saddle, and we can apply Theorem 10 to prove global convergence of stochastic gradient descent algorithm.

It is possible to find all components of a tensor by iteratively finding one component, and do careful deflation, as described in Anandkumar et al., (2014) or Arora et al., (2012). However, in practice the most popular approaches like Alternating Least Squares (Comon et al.,, 2009) or FastICA (Hyvarinen,, 1999) try to use a single optimization problem to find all the components. Empirically these algorithms are often more robust to noise and model misspecification.

The most straight-forward formulation of the problem aims to minimize the reconstruction error

We propose a new objective that aims to minimize the correlation between different components:

To understand this objective intuitively, we first expand vectors $u_{k}$ in the orthogonal basis formed by $\{a_{i}\}$’s. That is, we can write $u_{k}=\sum_{i=1}^{d}z_{k}(i)a_{i}$, where $z_{k}(i)$ are scalars that correspond to the coordinates in the $\{a_{i}\}$ basis. In this way we can rewrite $T(u_{k},u_{k},u_{l},u_{l})=\sum_{i=1}^{d}(z_{k}(i))^{2}(z_{l}(i))^{2}$. From this form it is clear that the $T(u_{k},u_{k},u_{l},u_{l})$ is always nonnegative, and is equal to only when the support of $z_{k}$ and $z_{l}$ do not intersect. For the objective function, we know in order for it to be equal to 0 the $z$’s must have disjoint support. Therefore, we claim that $\{u_{k}\},\forall k\in[d]$ is equivalent to $\{a_{i}\},\forall i\in[d]$ up to permutation and sign flips when the global minimum (which is 0) is achieved.

We further show that this optimization program satisfies the strict saddle property and all its local minima in fact achieves global minimum value. The proof is deferred to Appendix C.2.

The optimization problem (13) is $(\alpha,\gamma,\epsilon,\delta)$-strict saddle, for $\alpha=1$ and $\gamma,\epsilon,\delta=1/\mbox{poly}(d)$. Moreover, all its local minima have the form $u_{i}=\kappa_{i}a_{\pi(i)}$ for some $\kappa_{i}=\pm 1$ and permutation $\pi(i)$.

2 Implementing stochastic gradient oracle

To design an online algorithm based on objective function (13), we need to give an implementation for the stochastic gradient oracle.

where all other entries of $Z$ are equal to . The tensor $T$ can be written as a function of the auxiliary tensor $Z$ and multilinear form of the sample $y$.

Notice that computing this stochastic gradient does not require constructing the $4$-th order tensor $T-y^{\otimes 4}$. In particular, this stochastic gradient can be computed very efficiently:

The stochastic gradient (14) can be computed in $O(d^{3})$ time for one sample or $O(d^{3}+d^{2}k)$ for average of $k$ samples.

The proof is straight forward as the first two terms take $O(d^{3})$ and is shared by all samples. The third term can be efficiently computed once the inner-products between all the $y$’s and all the $u_{i}$’s are computed (which takes $O(kd^{2})$ time). ∎

Experiments

We run simulations for Projected Noisy Gradient Descent (Algorithm 2) applied to orthogonal tensor decomposition. The results show that the algorithm converges from random initial points efficiently (as predicted by the theorems), and our new formulation (13) performs better than reconstruction error (12) based formulation.

Samples and stochastic gradients

In the second case we consider the ICA example introduced in Section 4.2, and use Equation (14) to compute a stochastic gradient. In this case the stochastic gradient has a large variance, so we use mini-batch of size 100 to reduce the variance.

Comparison of objective functions

We use the simple way of generating samples for our new objective function (13) and reconstruction error objective (12). The result is shown in Figure 1. Our new objective function is empirically more stable (always converges within 10000 iterations); the reconstruction error do not always converge within the same number of iterations and often exhibits long periods with small improvement (which is likely to be caused by saddle points that do not have a significant negative eigenvalue).

Simple ICA example

As shown in Figure 2, our new algorithm also works in the ICA setting. When the learning rate is constant the error stays at a fixed small value. When we decrease the learning rate the error converges to 0.

Conclusion

In this paper we identify the strict saddle property and show stochastic gradient descent converges to a local minimum under this assumption. This leads to new online algorithm for orthogonal tensor decomposition. We hope this is a first step towards understanding stochastic gradient for more classes of non-convex functions. We believe strict saddle property can be extended to handle more functions, especially those functions that have similar symmetry properties.

References

Appendix A Detailed Analysis for Section 3 in Unconstrained Case

In this section we give detailed analysis for noisy gradient descent, under the assumption that the unconstrained problem satisfies $(\alpha,\gamma,\epsilon,\delta)$-strict saddle property.

The algorithm we investigate in Algorithm 1, we can combine the randomness in the stochastic gradient oracle and the artificial noise, and rewrite the update equation in form:

where $\eta$ is step size, $\xi=SG(w_{t-1})-\nabla f(w_{t-1})+n$ (recall $n$ is a random vector on unit sphere) is the combination of two source of noise.

We first restate the main theorem in the context of stochastic gradient descent.

As we discussed in the proof sketch in Section 3, we analyze the behavior of the algorithm in three different cases. The first case is when the gradient is large.

Under the assumptions of Theorem 13, for any point with $\|\nabla f(w_{0})\|\geq\sqrt{2\eta\sigma^{2}\beta d}$ where $\sqrt{2\eta\sigma^{2}\beta d}<\epsilon$, after one iteration we have:

Choose $\eta_{\max}<\frac{1}{\beta}$, then by update equation Eq.(15), we have:

where $w^{\star}$ is the locally optimal point.

We shall construct a supermartingale and use Azuma’s inequality (Azuma,, 1967) to prove this result.

By Definition 5 of $(\alpha,\gamma,\epsilon,\delta)$-strict saddle, we know $f$ is locally $\alpha$-strongly convex in the $2\delta$-neighborhood of $w^{\star}$. Since $\nabla f(w^{\star})=0$, we have

Furthermore, with $\eta_{\max}<\frac{\alpha}{\beta^{2}}$, using $\beta$-smoothness, we have:

Then, let $G_{t}=(1-\eta\alpha)^{-t}(\|w_{t}-w^{\star}\|^{2}-\frac{\eta}{\alpha})$, we have:

which means $G_{t}1_{\mathfrak{E}_{t-1}}$ is a supermartingale.

Under the assumptions of Theorem 13, for any initial point $w_{0}$ where $\|\nabla f(w_{0})\|\leq\sqrt{2\eta\sigma^{2}\beta d}<\epsilon$, and $\lambda_{\min}(\mathcal{H}(w_{0}))\leq-\gamma$, then there is a number of steps $T$ that depends on $w_{0}$ such that:

The number of steps $T$ has a fixed upper bound $T_{max}$ that is independent of $w_{0}$ where $T\leq T_{max}=O((\log d)/\gamma\eta)$.

As we described in the proof sketch, the main idea is to consider a coupled update sequence that correspond to the local second-order approximation of $f(x)$ around $w_{0}$. We characterize this sequence of update in the next lemma.

Substitute the update equation of SGD in Eq.(37), we have:

we can choose $\eta_{\max}<\min\{(\sqrt{2}-1)/L,2d/\gamma\}$ so that

then by summing over dimension $d$ and taking union bound over all $t\leq T$, we directly have:

Combine this fact with Eq.(A) and Eq.(A), we finish the proof.

Next we need to prove that the two sequences of updates are always close.

First, we have update function of gradient by:

Denote $\mathcal{H}=\mathcal{H}(w_{0})$, and $\mathcal{H}^{\prime}_{t-1}=\mathcal{H}(w_{t-1})-\mathcal{H}(w_{0})$. By Hessian smoothness, we immediately have:

Substitute the update equation of SGD (Eq.(15)) into Eq.(45), we have:

We first need to carefully bounded all terms in Eq.(50), conditioned on event $\mathfrak{K}_{t-1}\cap\mathfrak{E}_{t-1}$, by Eq.(47), Eq.(48)), and Eq.(51), with probability 1, for all $t\leq T\leq O(\log d/\gamma_{0}\eta)$, we have:

Since event $\mathfrak{K}_{t-1}\subset\mathfrak{F}_{t-1},\mathfrak{E}_{t-1}\subset\mathfrak{F}_{t-1}$ thus independent of $\xi_{t-1}$, we also have:

Then, when $\eta_{\max}$ is small enough, we have:

Once conditional on filtration $\mathfrak{F}_{t-1}$, the first two terms are deterministic, and only the third and fourth term are random. Therefore, we know, with probability 1:

Where the main contribution comes from the product of the first term and third term. Then, with probability 1, we have:

Therefore, combined with Lemma 17, we have:

Using the two lemmas above we are ready to prove Lemma 16

Let $\lambda_{1},\cdots,\lambda_{d}$ be the eigenvalues of $\mathcal{H}$. By the result of lemma 17 and simple linear algebra, we have:

The last inequality is directly implied by the choice of $T$ as in Eq.(35). Also, by Eq.(35), we also immediately have that $T=O(\log d/\gamma_{0}\eta)\leq O(\log d/\gamma\eta)$. Therefore, by choose $T_{max}=O(\log d/\gamma\eta)$ with large enough constant, we have $T\leq T_{max}=O(\log d/\gamma\eta)$.

For bounding the second term, by definition of $\mathfrak{E}_{t}$, we have:

Finally, substitute Eq.(68), Eq.(69) and Eq.(A) into Eq.(A), we finish the proof. ∎

Finally, we combine three cases to prove the main theorem.

Define stochastic process $\{\tau_{i}\}$ s.t. $\tau_{0}=0$, and

Therefore, combine above equation, we have:

Define event $\mathfrak{E}_{i}=\{\exists j\leq i,~{}w_{\tau_{j}}\in\mathcal{L}_{3}\}$, clearly $\mathfrak{E}_{i}\subset\mathfrak{E}_{i+1}$, thus $P(\mathfrak{E}_{i})\leq P(\mathfrak{E}_{i+1})$. Finally, consider $f(w_{\tau_{i+1}})1_{\mathfrak{E}_{i}}$, we have:

Therefore, by summing up over $i$, we have:

Appendix B Detailed Analysis for Section 3 in Constrained Case

So far, we have been discussed all about unconstrained problem. In this section we extend our result to equality constraint problems under some mild conditions.

Consider the equality constrained optimization problem:

Define the feasible set as the set of points that satisfy all the constraints $\mathcal{W}=\{w~{}|~{}c_{i}(w)=0;~{}i=1,\cdots,m\}$.

In this case, the algorithm we are running is Projected Noisy Gradient Descent. Let function $\Pi_{\mathcal{W}}(v)$ to be the projection to the feasible set， where the projection is defined as the global solution of $\min_{w\in\mathcal{W}}\|v-w\|^{2}$.

With same argument as in the unconstrained case, we could slightly simplify and convert it to standard projected stochastic gradient descent (PSGD) with update equation:

Often for constrained optimization problems we want the constraints to satisfy some regularity conditions. LICQ (linear independent constraint quantification) is a common assumption in this context.

In equality-constraint problem Eq.(77), given a point $w$, we say that the linear independence constraint qualification (LICQ) holds if the set of constraint gradients $\{\nabla c_{i}(x),i=1,\cdots,m\}$ is linearly independent.

In constrained optimization, we can locally transform it to an unconstrained problem by introducing Lagrangian multipliers. The Langrangian $\mathcal{L}$ can be written as

Then, if LICQ holds for all $w\in\mathcal{W}$, we can properly define function $\lambda^{*}(\cdot)$ to be:

where $\lambda^{*}(\cdot)$ can be calculated analytically: let matrix $C(w)=(\nabla c_{1}(w),\cdots,\nabla c_{m}(w))$, then we have:

where $(\cdot)^{\dagger}$ is Moore-Penrose pseudo-inverse.

In our setting we need a stronger regularity condition which we call robust LICQ (RLICQ).

In equality-constraint problem Eq.(77), given a point $w$, we say that $\alpha_{c}$-robust linear independence constraint qualification ( $\alpha_{c}$-RLICQ ) holds if the minimum singular value of matrix $C(w)=(\nabla c_{1}(w),\cdots,\nabla c_{m}(w))$ is greater or equal to $\alpha_{c}$, that is $\sigma_{\min}(C(w))\geq\alpha_{c}$.

Given a point $w\in\mathcal{W}$, $\alpha_{c}$-RLICQ implies LICQ. While LICQ holds for all $w\in\mathcal{W}$ is a necessary condition for $\lambda^{*}(w)$ to be well-defined; it’s easy to check that $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$ is a necessary condition for $\lambda^{*}(w)$ to be bounded. Later, we will also see $\alpha_{c}$-RLICQ combined with the smoothness of $\{c_{i}(w)\}_{i=1}^{m}$ guarantee the curvature of constraint manifold to be bounded everywhere.

Note that we require this condition in order to provide a quantitative bound, without this assumption there can be cases that are exponentially close to a function that does not satisfy LICQ.

We can also write down the first-order and second-order partial derivative of Lagrangian $\mathcal{L}$ at point $(w,\lambda^{*}(w))$:

Given a feasible point $w\in\mathcal{W}$, define its corresponding Tangent Space to be $\mathcal{T}(w)=\{v~{}|~{}\nabla c_{i}(w)^{T}v=0;~{}i=1,\cdots,m\}$, and Normal Space to be $\mathcal{T}^{c}(w)=\text{span}\{\nabla c_{1}(w)\cdots,\nabla c_{m}(w)\}$

If $w\in\mathcal{R}^{d}$, and we have $m$ constraint satisfying $\alpha_{c}$-RLICQ , the tangent space would be a linear subspace with dimension $d-m$; and the normal space would be a linear subspace with dimension $m$. We also know immediately that $\chi(w)$ defined in Eq.(83) has another interpretation: it’s the component of gradient $\nabla f(w)$ in tangent space.

Also, it’s easy to see the normal space $\mathcal{T}^{c}(w)$ is the orthogonal complement of $\mathcal{T}$. We can also define the projection matrix of any vector onto tangent space (or normal space) to be $P_{\mathcal{T}(w)}$ (or $P_{\mathcal{T}^{c}(w)}$). Then, clearly, both $P_{\mathcal{T}(w)}$ and $P_{\mathcal{T}^{c}(w)}$ are orthoprojector, thus symmetric. Also by Pythagorean theorem, we have:

Let $w,w_{0}\in\mathcal{W}$, and fix $\lambda^{*}=\lambda^{*}(w_{0})$ independent of $w$, assume $\nabla^{2}_{ww}\mathcal{L}(w,\lambda^{*})$ is $\rho_{L}$-Lipschitz, that is $\|\nabla^{2}_{ww}\mathcal{L}(w_{1},\lambda^{*})-\nabla^{2}_{ww}\mathcal{L}(w_{2},\lambda^{*})\|\leq\rho_{L}\|w_{1}-w_{2}\|$ By Taylor expansion, we have:

Since $w,w_{0}$ are feasible, we know: $\mathcal{L}(w,\lambda^{*})=f(w)$ and $\mathcal{L}(w_{0},\lambda^{*})=f(w_{0})$, this gives:

Derivative of χ​(w)𝜒𝑤\chi(w)

By taking derative of $\chi(w)$ again, we know the change of this tangent gradient can be characterized by:

We immediately know that $\nabla\chi(w)=\mathfrak{M}(w)+\mathfrak{N}(w)$.

Finally, for completeness, we state here the first/second-order necessary (or sufficient) conditions for optimality. Please refer to Wright and Nocedal, (1999) for the proof of those theorems.

In equality constraint problem Eq.(77), suppose that $w^{\dagger}$ is a local solution, and that the functions $f$ and $c_{i}$ are continuously differentiable, and that the LICQ holds at $w^{\dagger}$. Then there is a Lagrange multiplier vector $\lambda^{\dagger}$, such that:

These conditions are also usually referred as Karush-Kuhn-Tucker (KKT) conditions.

In equality constraint problem Eq.(77), suppose that $w^{\dagger}$ is a local solution, and that the LICQ holds at $w^{\dagger}$. Let $\lambda^{\dagger}$ Lagrange multiplier vector for which the KKT conditions are satisfied. Then:

Then $w^{\dagger}$ is a strict local solution.

By definition Eq.(82), we know immediately $\lambda^{*}(w^{\dagger})$ is one of valid Lagrange multipliers $\lambda^{\dagger}$ for which the KKT conditions are satisfied. This means $\chi(w^{\dagger})=\nabla_{w}\mathcal{L}(w^{\dagger},\lambda^{\dagger})$ and $\mathfrak{M}(w^{\dagger})=\mathcal{L}(w^{\dagger},\lambda^{\dagger})$.

Therefore, Theorem 22, 23, 24 gives strong implication that $\chi(w)$ and $\mathfrak{M}(w)$ are the right thing to look at, which are in some sense equivalent to $\nabla f(w)$ and $\nabla^{2}f(w)$ in unconstrained case.

B.2 Geometrical Lemmas Regarding Constraint Manifold

Since in equality constraint problem, at each step of PSGD, we are effectively considering the local manifold around feasible point $w_{t-1}$. In this section, we provide some technical lemmas relating to the geometry of constraint manifold in preparsion for the proof of main theorem in equality constraint case.

We first show if two points are close, then the projection in the normal space is much smaller than the projection in the tangent space.

Suppose the constraints $\{c_{i}\}_{i=1}^{m}$ are $\beta_{i}$-smooth, and $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$. Then, let $\sum_{i=1}^{m}\frac{\beta_{i}^{2}}{\alpha^{2}_{c}}=\frac{1}{R^{2}}$, for any $w,w_{0}\in\mathcal{W}$, let $\mathcal{T}_{0}=\mathcal{T}(w_{0})$, then

Furthermore, if $\|w-w_{0}\|<R$ holds, we additionally have:

First, since for any vector $\hat{v}\in\mathcal{T}_{0}$, we have $\|C(w_{0})^{T}\hat{v}\|=0$, then by simple linear algebra, it’s easy to show:

On the other hand, by $\beta_{i}$-smooth, we have:

Since $w,w_{0}$ are feasible points, we have $c_{i}(w)=c_{i}(w_{0})=0$, which gives:

Combining Eq.(B.2) and Eq.(98), and the definition of $R$, we have:

Solving this second-order inequality gives two solution

By assumption, we know $\|w-w_{0}\|<R$ (so the second case cannot be true), which finishes the proof. ∎

Here, we see the $\sqrt{\sum_{i=1}^{m}\frac{\beta_{i}^{2}}{\alpha^{2}_{c}}}=\frac{1}{R}$ serves as a upper bound of the curvatures on the constraint manifold, and equivalently, $R$ serves as a lower bound of the radius of curvature. $\alpha_{c}$-RLICQ and smoothness guarantee that the curvature is bounded.

Next we show the normal/tangent space of nearby points are close.

Suppose the constraints $\{c_{i}\}_{i=1}^{m}$ are $\beta_{i}$-smooth, and $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$. Let $\sum_{i=1}^{m}\frac{\beta_{i}^{2}}{\alpha^{2}_{c}}=\frac{1}{R^{2}}$, for any $w,w_{0}\in\mathcal{W}$, let $\mathcal{T}_{0}=\mathcal{T}(w_{0})$. Then for all $\hat{v}\in\mathcal{T}(w)$ so that $\|\hat{v}\|=1$, we have

With similar calculation as Eq.(B.2), we immediately have:

Since $\hat{v}\in\mathcal{T}(w)$ , we have $C(w)^{T}\hat{v}=0$, combined with the fact that $\hat{v}$ is a unit vector, we have:

Combining Eq.(102) and Eq.(103), and the definition of $R$, we concludes the proof. ∎

Suppose the constraints $\{c_{i}\}_{i=1}^{m}$ are $\beta_{i}$-smooth, and $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$. Let $\sum_{i=1}^{m}\frac{\beta_{i}^{2}}{\alpha^{2}_{c}}=\frac{1}{R^{2}}$, for any $w,w_{0}\in\mathcal{W}$, let $\mathcal{T}_{0}=\mathcal{T}(w_{0})$. Then for all $\hat{v}\in\mathcal{T}^{c}(w)$ so that $\|\hat{v}\|=1$, we have

On the other hand, let $\lambda=(\lambda_{1},\cdots,\lambda_{m})^{T}$, we know $C(w)\lambda=\hat{v}$, thus:

Therefore, by $\alpha_{c}$-RLICQ and the fact $\hat{v}$ is unit vector, we know: $\|\lambda\|\leq\frac{1}{\alpha_{c}}$. Combined with Eq.(B.2), we finished the proof. ∎

Using the previous lemmas, we can then prove that: starting from any point $w_{0}$ on constraint manifold, the result of adding any small vector $v$ and then projected back to feasible set, is not very different from the result of adding $P_{\mathcal{T}(w_{0})}v$.

Where projection $\Pi_{\mathcal{W}}(w)$ is defined as the closet point to $w$ on feasible set $\mathcal{W}$.

Denote $u_{1}=\Pi_{\mathcal{W}}(w_{1})$, and clearly $u_{1}\in\mathcal{W}$. we can formulate $u_{1}$ as the solution to following constrained optimization problems:

Since function $f(u)=\|w_{1}-u\|^{2}$ and $c_{i}(u)$ are continuously differentiable by assumption, and the condition $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$ implies that LICQ holds for $u_{1}$. Therefore, by Karush-Kuhn-Tucker necessary conditions, we immediately know $(w_{1}-u_{1})\in\mathcal{T}^{c}(u_{1})$.

Let $v_{1}=w_{0}+P_{\mathcal{T}_{0}}(u_{1}-w_{0})$, we have:

Combining Eq.(B.2) and Eq.(111), we finished the proof.

B.3 Main Theorem

Now we are ready to prove the main theorems. First we revise the definition of strict saddle in the constrained case.

A twice differentiable function $f(w)$ with constraints $c_{i}(w)$ is $(\alpha,\gamma,\epsilon,\delta)$-strict saddle, if for any point $w$ one of the following is true

$\hat{v}^{T}\mathfrak{M}(w)\hat{v}\leq-\gamma$ for some $\hat{v}\in\mathcal{T}(w)$, $\|\hat{v}\|=1$

There is a local minimum $w^{\star}$ such that $\|w-w^{\star}\|\leq\delta$, and for all $w^{\prime}$ in the $2\delta$ neighborhood of $w^{\star}$, we have $\hat{v}^{T}\mathfrak{M}(w^{\prime})\hat{v}\geq\alpha$ for all $\hat{v}\in\mathcal{T}(w^{\prime})$, $\|\hat{v}\|=1$

Next, we prove a equivalent formulation for PSGD.

Suppose the constraints $\{c_{i}\}_{i=1}^{m}$ are $\beta_{i}$-smooth, and $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$. Furthermore, if function $f$ is $L$-Lipschitz, and the noise $\xi$ is bounded, then running PSGD as in Eq.(78) is equivalent to running:

Lemma 30 is a direct corollary of Lemma 28. ∎

The intuition behind this lemma is that: when $\{c_{i}\}_{i=1}^{m}$ are smooth and $\alpha_{c}$-RLICQ holds for all $w\in\mathcal{W}$, then the constraint manifold has bounded curvature every where. Then, if we only care about first order behavior, it’s well-approximated by the local dynamic in tangent plane, up to some second-order correction.

Therefore, by Eq.(112), we see locally it’s not much different from the unconstrainted case Eq.(15) up to some negeligable correction. In the following analysis, we will always use formula Eq.(112) as the update equation for PSGD.

Since most of following proof bears a lot similarity as in unconstrained case, we only pointed out the essential steps in our following proof.

First, we proof the assumptions in main theorem implies the smoothness conditions for $\mathfrak{M}(w)$, $\mathfrak{N}(w)$ and $\nabla^{2}_{ww}\mathcal{L}(w,\lambda^{*}(w^{\prime}))$.

Under the assumptions of Theorem 31, there exists $\beta_{M},\beta_{N},\rho_{M},\rho_{N},\rho_{L}$ polynomial related to $B,L,\beta,\rho,\frac{1}{\alpha_{c}}$ and $\{L_{i},\beta_{i},\rho_{i}\}_{i=1}^{m}$ so that:

$\|\mathfrak{M}(w)\|\leq\beta_{M}$ and $\|\mathfrak{N}(w)\|\leq\beta_{N}$ for all $w\in\mathcal{W}$.

$\mathfrak{M}(w)$ is $\rho_{M}$-Lipschitz, and $\mathfrak{N}(w)$ is $\rho_{N}$-Lipschitz, and $\nabla^{2}_{ww}\mathcal{L}(w,\lambda^{*}(w^{\prime}))$ is $\rho_{L}$-Lipschitz for all $w^{\prime}\in\mathcal{W}$.

Since $\alpha_{c}$-RLICQ holds for all feasible points, we immediately have: $\|C(w)^{\dagger}\|\leq\frac{1}{\alpha_{c}}$, thus bounded. For simplicity, in the following context we use $C^{\dagger}$ to represent $C^{\dagger}(w)$ without ambiguity. By some calculation of linear algebra, we have the derivative of pseudo-inverse:

Define the transpose of a 3rd order tensor $E^{T}_{i,j,k}=E_{k,j,i}$, then we have

where by calculation $[E(w)](I,I,e_{i})=\nabla^{2}c_{i}(w)$.

From now on, we can use the same proof strategy as unconstraint case. Below we list the corresponding lemmas and the essential steps that require modifications.

Under the assumptions of Theorem 31, with notations in Lemma 32, for any point with $\|\chi(w_{0})\|\geq\sqrt{2\eta\sigma^{2}\beta_{M}(d-m)}$ where $\sqrt{2\eta\sigma^{2}\beta_{M}(d-m)}<\epsilon$, after one iteration we have:

Choose $\eta_{\max}<\frac{1}{\beta_{M}}$, and also small enough, then by update equation Eq.(112), we have:

where $w^{\star}$ is the locally optimal point.

Let filtration $\mathfrak{F}_{t}=\sigma\{\xi_{0},\cdots\xi_{t-1}\}$, and note $\sigma\{\Delta_{0},\cdots,\Delta_{t}\}\subset\mathfrak{F}_{t}$, where $\sigma\{\cdot\}$ denotes the sigma field. Let event $\mathfrak{E}_{t}=\{\forall\tau\leq t,\|w_{\tau}-w^{\star}\|\leq\mu\sqrt{\eta\log\frac{1}{\eta\zeta}}<\delta\}$, where $\mu$ is independent of $(\eta,\zeta)$, and will be specified later.

By Definition 29 of $(\alpha,\gamma,\epsilon,\delta)$-strict saddle, we know $\mathfrak{M}(w)$ is locally $\alpha$-strongly convex restricted to its tangent space $\mathcal{T}(w)$. in the $2\delta$-neighborhood of $w^{\star}$. If $\eta_{\max}$ is chosen small enough, by Remark Remark and Lemma 25, we have in addition:

Then, everything else follows almost the same as the proof of Lemma 15. ∎

The number of steps $T$ has a fixed upper bound $T_{max}$ that is independent of $w_{0}$ where $T\leq T_{max}=O((\log(d-m))/\gamma\eta)$.

Similar to the unconstrained case, we show this by a coupling sequence. Here the sequence we construct will only walk on the tangent space, by Lemmas in previous subsection, we know this is not very far from the actual sequence. We first define and characterize the coupled sequence in the following lemma:

This lemma is then proved by a direct application of Lemma 17. ∎

Then we show the sequence constructed is very close to the actual sequence.

First, we have update function of tangent gradient by:

Project it to tangent space $\mathcal{T}_{0}=\mathcal{T}(w_{0})$. Denote $\widetilde{\mathfrak{M}}=P_{\mathcal{T}_{0}}^{T}\mathfrak{M}(w_{0})P_{\mathcal{T}_{0}}$, and $\widetilde{\mathfrak{M}}^{\prime}_{t-1}=P_{\mathcal{T}_{0}}^{T}[~{}\mathfrak{M}(w_{t_{1}})-\mathfrak{M}(w_{0})~{}]P_{\mathcal{T}_{0}}$. Then, we have:

By Hessian smoothness, we immediately have:

Substitute the update equation of PSGD (Eq.(112)) into Eq.(133), we have:

By Lemma 25, we know if $\sum_{i=1}^{m}\frac{\beta_{i}^{2}}{\alpha_{c}^{2}}=\frac{1}{R^{2}}$, then we have:

Therefore, abstractly, conditioned on event $\mathfrak{K}_{t-1}\cap\mathfrak{E}_{t-1}$, we could write down the recursive equation as:

On the other hand, for $\Gamma_{t}=\eta\sum_{\tau=0}^{t-1}P_{\mathcal{T}_{0}}\cdot P_{\mathcal{T}^{c}(w_{\tau})}\xi_{\tau}$, we have:

We also know by Lemma 27, with probability 1:

Therefore, combined with Lemma 36, we have:

Finally, conditioned on event $\mathfrak{K}_{t-1}\cap\mathfrak{E}_{t-1}$, if we have $\|\Gamma_{t}\|\leq\mu_{2}\eta\log^{2}\frac{1}{\eta}$, then by Eq.(139):

These two lemmas allow us to prove the result when the initial point is very close to a saddle point.

Combine Talyor expansion Eq.87 with Lemma 36, Lemma 37, we prove this Lemma by the same argument as in the proof of Lemma 16. ∎

By Lemma 33, Lemma 35, and Lemma 34, with the same argument as in the proof Theorem 13, we easily concludes this proof. ∎

Appendix C Detailed Proofs for Section 4

In this section we show two optimization problems (11) and (13) satisfy the $(\alpha,\gamma,\epsilon,\delta)$-strict saddle propery.

Recall that we are trying to solve the optimization (11), which we restate here.

This is a constrained optimization, so we apply the framework developed in Section 3.3.

Let $c(x)=\|x\|_{2}^{2}-1$. We first compute the Lagrangian

Since there is only one constraint, and the gradient when $\|x\|=1$ always have norm $2$, we know the set of constraints satisfy $2$-RLICQ. In particular, we can compute the correct value of Lagrangian multiplier $\lambda$,

Therefore, the gradient in the tangent space is equal to

The second-order partial derivative of Lagrangian is equal to

Since the variable $x$ has bounded norm, and the function is a polynomial, it’s clear that the function itself is bounded and all its derivatives are bounded. Moreover, all the derivatives of the constraint are bounded. We summarize this in the following lemma.

The objective function (11) is bounded by $1$, its $p$-th order derivative is bounded by $O(\sqrt{d})$ for $p=1,2,3$. The constraint’s $p$-th order derivative is bounded by $2$, for $p=1,2,3$.

Therefore the function satisfy all the smoothness condition we need. Finally we show the gradient and Hessian of Lagrangian satisfy the $(\alpha,\gamma,\epsilon,\delta)$-strict saddle property. Note that we did not try to optimize the dependency with respect to $d$.

The only local minima of optimization problem (11) are $\pm a_{i}~{}(i\in[d])$. Further it satisfy $(\alpha,\gamma,\epsilon,\delta)$-strict saddle for $\gamma=7/d$, $\alpha=3$ and $\epsilon,\delta=1/\mbox{poly}(d)$.

In order to prove this theorem, we consider the transformed version Eq.155. We first need following two lemma for points around saddle point and local minimum respectively. We choose

Where by intuition, $\mathfrak{S}(x)$ is the set of coordinates whose value is relative large.

Under the choice of parameters in Eq.(160), suppose $\|\chi(x)\|\leq\epsilon$, and $|\mathfrak{S}(x)|\geq 2$. Then, there exists $\hat{v}\in\mathcal{T}(x)$ and $\|\hat{v}\|=1$, so that $\hat{v}^{T}\mathfrak{M}(x)\hat{v}\leq-7/d$.

Suppose $|\mathfrak{S}(x)|=p$, and $2\leq p\leq d$. Since $\|\chi(x)\|\leq\epsilon=4\epsilon_{0}^{2}$, by Eq.(C.1), we have for each $i\in[d]$, $|[\chi(x)]_{i}|=4|(x_{i}^{2}-\|x\|_{4}^{4})x_{i}|\leq 4\epsilon_{0}^{2}$. Therefore, we have:

Because of symmetry, WLOG we assume $\mathfrak{S}(x)=\{1,\cdots,p\}$. Since $|\mathfrak{S}(x)|\geq 2$, we can pick $\hat{v}=(a,b,0,\cdots,0)$. Here $a>0,b<0$, and $a^{2}+b^{2}=1$. We pick $a$ such that $ax_{1}+bx_{2}=0$. The solution is the intersection of a radius $1$ circle and a line which passes $(0,0)$, which always exists. For this $\hat{v}$, we know $\|\hat{v}\|=1$, and $\hat{v}^{T}x=0$ thus $\hat{v}\in\mathcal{T}(x)$. We have:

Under the choice of parameters in Eq.(160), suppose $\|\chi(x)\|\leq\epsilon$, and $|\mathfrak{S}(x)|=1$. Then, there is a local minimum $x^{\star}$ such that $\|x-x^{\star}\|\leq\delta$, and for all $x^{\prime}$ in the $2\delta$ neighborhood of $x^{\star}$, we have $\hat{v}^{T}\mathfrak{M}(x^{\prime})\hat{v}\geq 3$ for all $\hat{v}\in\mathcal{T}(x^{\prime})$, $\|\hat{v}\|=1$

WLOG, we assume $\mathfrak{S}(x)=\{1\}$. Then, we immediately have for all $i>1$, $|x_{i}|\leq\epsilon_{0}$, and thus:

Therefore $x_{1}\geq\sqrt{1-d\epsilon_{0}^{2}}$ or $x_{1}\leq-\sqrt{1-d\epsilon_{0}^{2}}$. Which means $x_{1}$ is either close to $1$ or close to $-1$. By symmetry, we know WLOG, we can assume the case $x_{1}\geq\sqrt{1-d\epsilon_{0}^{2}}$. Let $e_{1}=(1,0,\cdots,0)$, then we know:

Next, we show $e_{1}$ is a local minimum. According to Eq.C.1, we know $\mathfrak{M}(e_{1})$ is a diagonal matrix with $4$ on the diagonals except for the first diagonal entry (which is equal to $-8$), since $\mathcal{T}(e_{1})=\text{span}\{e_{2},\cdots,e_{d}\}$, we have:

Which by Theorem 24 means $e_{1}$ is a local minimum.

Finally, denote $\mathcal{T}_{1}=\mathcal{T}(e_{1})$ be the tangent space of constraint manifold at $e_{1}$. We know for all $x^{\prime}$ in the $2\delta$ neighborhood of $e_{1}$, and for all $\hat{v}\in\mathcal{T}(x^{\prime})$, $\|\hat{v}\|=1$:

By lemma 26, we know $\|P_{\mathcal{T}^{c}_{1}}\hat{v}\|^{2}\leq\|x^{\prime}-e_{1}\|^{2}\leq 4\delta^{2}$. By Eq.(C.1), we have:

In conclusion, we have $\hat{v}^{T}\mathfrak{M}(x^{\prime})\hat{v}\geq 4-48\delta^{2}-64d\delta\geq 3$ which finishs the proof. ∎

Finally, we are ready to prove Theorem 39.

According to Lemma 40 and Lemma 41, we immediately know the optimization problem satisfies $(\alpha,\gamma,\epsilon,\delta)$-strict saddle.

The only thing remains to show is that the only local minima of optimization problem (11) are $\pm a_{i}~{}(i\in[d])$. Which is equivalent to show that the only local minima of the transformed problem is $\pm e_{i}~{}(i\in[d])$, where $e_{i}=(0,\cdots,0,1,0,\cdots,0)$, where $1$ is on $i$-th coordinate.

By investigating the proof of Lemma 40 and Lemma 41, we know these two lemmas actually hold for any small enough choice of $\epsilon_{0}$ satisfying $\epsilon_{0}\leq(10d)^{-4}$, by pushing $\epsilon_{0}\rightarrow 0$, we know for any point satisfying $|\chi(x)|\leq\epsilon\rightarrow 0$, if it is close to some local minimum, it must satisfy $1=|\mathfrak{S}(x)|\rightarrow\operatorname{supp}(x)$. Therefore, we know the only possible local minima are $\pm e_{i}~{}(i\in[d])$. In Lemma 41, we proved $e_{1}$ is local minimum, by symmetry, we finishes the proof. ∎

C.2 New formulation

In this section we consider our new formulation (13). We first restate the optimization problem here:

Note that we changed the notation for the variables from $u_{i}$ to $u^{(i)}$, because in later proofs we will often refer to the particular coordinates of these vectors.

Similar to the previous section, we perform a change of basis. The effect is equivalent to making $a_{i}$’s equal to basis vectors $e_{i}$ (and hence the tensor is equal to $T=\sum_{i=1}^{d}e_{i}^{\otimes 4}$. After the transformation the equations become

Here $h(u^{(i)},u^{(j)})=\sum_{k=1}^{d}(u^{(i)}_{k}u^{(j)}_{k})^{2}$, $(i,j)\in[d]^{2}$. We divided the objective function by $2$ to simplify the calculation.

The gradients of $c_{i}(U)$’s are equal to $(0,\cdots,0,2u^{(i)},0,\cdots,0)^{T}$, all of these vectors are orthogonal to each other (because they have disjoint supports) and have norm $2$. Therefore the set of constraints satisfy $2$-RLICQ. We can then compute the Lagrangian multipiers $\lambda^{*}$ as follows

Therefore, gradient in the tangent space is equal to

The gradient is a $d^{2}$ dimensional vector (which can be viewed as a $d\times d$ matrix corresponding to entries of $U$), and we express this in a coordinate-by-coordinate way. For simplicity of later proof, denote:

Similarly we can compute the second-order partial derivative of Lagrangian as

The Hessian is a $d^{2}\times d^{2}$ matrix, we index it by $4$ indices in $[d]$. The entries are summarized below:

Similar to the previous case, it is easy to bound the function value and derivatives of the function and the constraints.

The objective function (13) and $p$-th order derivative are all bounded by $\mbox{poly}(d)$ for $p=1,2,3$. Each constraint’s $p$-th order derivative is bounded by $2$, for $p=1,2,3$.

Therefore the function satisfy all the smoothness condition we need. Finally we show the gradient and Hessian of Lagrangian satisfy the $(\alpha,\gamma,\epsilon,\delta)$-strict saddle property. Again we did not try to optimize the dependency with respect to $d$.

Optimization problem (13) has exactly $2^{d}\cdot d!$ local minimum that corresponds to permutation and sign flips of $a_{i}$’s. Further, it satisfy $(\alpha,\gamma,\epsilon,\delta)$-strict saddle for $\alpha=1$ and $\gamma,\epsilon,\delta=1/\mbox{poly}(d)$.

Again, in order to prove this theorem, we follow the same strategy: we consider the transformed version Eq.171. and first prove the following lemmas for points around saddle point and local minimum respectively. We choose

Where by intuition, $\mathfrak{S}(u)$ is the set of coordinates whose value is relative large.

Under the choice of parameters in Eq.(180), suppose $\|\chi(U)\|\leq\epsilon$, and there exists $(i,j)\in[d]^{2}$ so that $\mathfrak{S}(u^{(i)})\cap\mathfrak{S}(u^{(j)})\neq\emptyset$. Then, there exists $\hat{v}\in\mathcal{T}(U)$ and $\|\hat{v}\|=1$, so that $\hat{v}^{T}\mathfrak{M}(U)\hat{v}\leq-\gamma$.

Again, since $\|\chi(x)\|\leq\epsilon=2\epsilon_{0}^{6}$, by Eq.(177), we have for each $i\in[d]$, $|[\chi(x)]_{ik}|=2|U_{ik}\psi_{ik}(U)|\leq 2\epsilon_{0}^{6}$. Therefore, have:

Then, we prove this lemma by dividing it into three cases. Note in order to prove that there exists $\hat{v}\in\mathcal{T}(U)$ and $\|\hat{v}\|=1$, so that $\hat{v}^{T}\mathfrak{M}(U)\hat{v}\leq-\gamma$; it suffices to find a vector $v\in\mathcal{T}(U)$ and $\|v\|\leq 1$, so that $v^{T}\mathfrak{M}(U)v\leq-\gamma$.

: $|\mathfrak{S}(u^{(i)})|\geq 2$, $|\mathfrak{S}(u^{(j)})|\geq 2$, and $|\mathfrak{S}(u^{(i)})\cap\mathfrak{S}(u^{(j)})|\geq 2$.

WLOG, assume $\{1,2\}\in\mathfrak{S}(u^{(i)})\cap\mathfrak{S}(u^{(j)})$, choose $v$ to be $v_{i1}=\frac{U_{i2}}{4}$, $v_{i2}=-\frac{U_{i1}}{4}$, $v_{j1}=\frac{U_{j2}}{4}$ and $v_{j2}=-\frac{U_{j1}}{4}$. All other entries of $v$ are zero. Clearly $v\in\mathcal{T}(U)$, and $\|v\|\leq 1$. On the other hand, we know $\mathfrak{M}(U)$ restricted to these 4 coordinates $(i1,i2,j1,j2)$ is

By Eq.(181), we know all diagonal entries are $\leq 2\epsilon_{0}^{5}$.

If $U_{i1}U_{j1}U_{i2}U_{j2}$ is negative, we have the quadratic form:

If $U_{i1}U_{j1}U_{i2}U_{j2}$ is positive we just swap the sign of the first two coordinates $v_{i1}=-\frac{U_{i2}}{2}$, $v_{i2}=\frac{U_{i1}}{2}$ and the above argument would still holds.