Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning

Dear Reviewer,

Thank you for your review.

Comment: A discussion regarding the `tightness' of the sufficient condition (Assumption 2.8) is missing.

Response: Assumption 2.8 is a sufficient condition that is significantly easier to verify than the second-order characterization of anisotropic smoothness (3), which in turn is equivalent to a matrix inequality involving $\nabla^2 f$ [32, Lemma 2.5]. The merits of this condition are two-fold: On the one hand, it is practical and was used it to establish generalized smoothness of the examples in section 2.3. On the other hand, it reveals the close connection between anisotropic smoothness and $(L_0, L_1)$-smoothness.

For $(L_0, L_1)$-smoothness, some tightness is lost by requiring global polynomial upper and lower bounds to the Hessian and gradient norms, respectively. In principle, a bounded ratio of these two quantities suffices, in which case the definition of $(L_0, L_1)$-smoothness can be used directly.

For anisotropic smoothness, more tightness is lost: the matrix inequality [32, Lemma 2.5]

only imposes an upper bound to the Hessian's eigenvalues, whereas a bound on $\Vert\nabla^2 f(x)\Vert$ -- as in Assumption 2.8 or in $(L_0, L_1)$-smoothness -- imposes both a lower and an upper bound to the Hessian's eigenvalues. This makes anisotropic smoothness (at least for certain reference functions $\phi$) more general than $(L_0, L_1)$-smoothness (see also Example 2.6), but significantly harder to verify.

As we have illustrated through the applications in section 2.3, the Assumption 2.8 entails a practically verifiable sufficient condition, whereas, e.g., the matrix inequality [32, Lemma 2.5] would be far more difficult to establish for specific applications.

We thank the reviewer for posing this question, and agree that a discussion regarding the tightness of Assumption 2.8 would be valuable. We will include it after introducing Assumption 2.8.

Comment: The applications in section 2.3 have specialized algorithms that are efficient. It is not clear why a nonlinearly preconditioned gradient method is a good choice for those problems.

Response: Section 2.3 does not claim that nonlinearly preconditioned gradient methods are efficient methods for the applications in section 2.3 -- although [32, Fig 3] indicates that they perform very well for phase retrieval, and this also agrees with our personal experience. Rather, we wanted to illustrate that this theoretical framework for generalized smoothness is truly relevant by showing that it applies to certain key applications where classical Lipschitz smoothness fails. As acknowledged by one of the other reviewers, this is a crucial step which many theoretical papers fail to take.

Comment: There are no numerical experiments.

Response: To address this comment, we have conducted two experiments:

(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\phi(x) = \cosh(\Vert x \Vert) - 1$. As suggested by Reviewer M3Bk, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\bar L = 1$)

In this case, large gradients are damped -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\gamma$ that are often orders of magnitudes larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.

(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\bar L = 1$. We compare against classical GD, and vary the constant $L \in \\{1, 1.5, 2, 3\\}$ and dimension $n \in \\{5, 10\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD. The resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\bar L^{-1}$.

We believe these experiments significantly improve our manuscript and therefore plan to include them.

We hope that we have adequately addressed any concerns that you may have had, and that you are willing to re-evaluate your rating of our work.

Dear Reviewer,

We thank you for your thorough and encouraging feedback.

Comment: A visualization of the P-GD dynamics and an illustration of the convergence of Algorithm 1 in comparison to standard GD could provide valuable intuition.

Response: Thank you for this suggestion! We have conducted the following two experiments:

(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\phi(x) = \cosh(\Vert x \Vert) - 1$. As you suggested, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\bar L = 1$)

In this case, large gradients are damped -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\gamma$ that are often orders of magnitudes larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.

(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\bar L = 1$. We compare against classical GD, and vary the constant $L \in \\{1, 1.5, 2, 3\\}$ and dimension $n \in \\{5, 10\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD. The resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\bar L^{-1}$.

We believe these experiments significantly improve our manuscript and therefore plan to include them.

Question: Provide more intuition regarding Assumption 3.3. How does the choice of $\phi$ affect whether this assumption holds? Are there natural choices of $\phi$ for which the assumption fails, and what would be the consequences?

Response: Thank you for raising this interesting question.

We believe Assumption 3.3 constitutes a meaningful generalization of the Hessian Lipschitz continuity assumption that is often used in complexity analyses. In an attempt to provide some more intuition, we highlight that under the conditions in Assumption 2.10 $\Vert \nabla^2 \phi^\*(y) \Vert \to 0$ as $\Vert y \Vert \to \infty$. The rough idea is that this counteracts the growth of $\nabla^2 f(x)$ as $\Vert x \Vert \to \infty$ in a way that ensures Lipschitz continuity of $H_\lambda(x) = \nabla^2 \phi^\*(\lambda \nabla f(x)) \nabla^2 f(x)$.

We stress that even if Assumption 3.3 is violated, then the asymptotic result of Theorem 3.1 still holds. Only regarding the required number of iterations, we can no longer give a formal guarantee.

Finally, we refer to our answer to Question 3 of Reviewer ZsPD for a discussion about sufficient conditions on $f$ and $\phi$ for Assumption 3.3 to hold.

Question: In Theorem 3.6, how do $L, \bar L$ and $\rho$ scale with the dimension $n$ and other problem parameters for key applications? Is the overall complexity truly polylogarithmic?

Response: This is an interesting question. From a theoretical point of view, we mention that the proofs in Section 2.3 do not explicitly construct the constants $L, \bar L$, so that we cannot formally rule out a dependence on the dimension. However, we strongly believe this is not the case, and this for the following reasons:

(i) By Example 2.6, $(L_0, L_1)$-smoothness implies anisotropic smoothness with $L = L_1$ and $\bar L = L_0 / L_1$. Thus, if $L_0, L_1$ are independent of $n$, then so are $L, \bar L$. Judging from the experiments in [38], the empirical estimates for $L_0, L_1$ remain very moderate, even for high-dimensional neural networks.

(ii) This is in line with with our own experiments on e.g. matrix factorization, in which the method converges for large step sizes, also when the dimension is increased.

(iii) Likewise, we mention that for $L_H$-Lipschitz continuous Hessians $\nabla^2 f$, the constant $\rho$ reduces to $L_H$ when $\phi = \frac{1}{2}\Vert \cdot \Vert^2$. To further rule out hidden dependencies on $n$, we carefully investigated the scaling of the number of iterations of Algorithm 1 with the dimension $n$ (cf. Comment 1: Experiment (ii)). We found the scaling to closely match the one reported in [11, Figs 3 and 4], thus further validating the complexity of Theorem 3.6.

Question: The analysis for hard clipping in Theorem 3.2 requires the set $U := \{x \mid \Vert \nabla f(x) \Vert \neq \bar L\}$ to have measure one. Can you provide a justification or an example where this assumption holds for the problems of interest?

Response: Let us define the function $F(x) := \Vert \nabla f(x) \Vert^2$, which is $\mathcal{C}^1$ whenever $f \in \mathcal{C}^2$.

If $\bar L^2$ is a regular value of $F$, i.e., if there exists no $x \in \mathbb{R}^n$ for which $F(x) = \bar L^2$ with $\nabla F(x) = 0$, then by the preimage theorem the level set $F^{-1}(\bar L^2) \equiv \\{x \mid F(x) = \bar L^2 \\} \equiv \mathbb{R}^n \setminus U$ is a smooth manifold of dimension $n - 1$, and therefore has measure zero in $\mathbb{R}^n$.

On the other hand, the set of critical values ($\bar L^2$ is a critical value of $F$ if it is not a regular value of $F$) is small for generic functions. To be more precise, by Sard's theorem the set of critical values has measure $0$ if $F$ is $k$ times continuously differentiable for some $k$ large enough ($k$ depends on $n$).

In conclusion, if $f$ is $k$ times continuously differentiable for some $k$ large enough, then for almost every $\bar L$ the set $U$ has measure one.

Question: Could you elaborate on the significance of the regularization term ($\kappa > 0$) in the asymmetric matrix factorization case (Theorem 2.14)? Does this imply that the unregularized problem ($\kappa = 0$) does not satisfy $(L_0, L_1)$-smoothness, and if so, does this have implications for the analysis of unregularized matrix factorization?

Response: Indeed, if $\kappa = 0$, then asymmetric matrix factorization does not satisfy $(L_0, L_1)$-smoothness. Let $m = n = r = 1$ such that $f(w, h) = \frac{1}{2} (w h - y)^2$ is minimized w.r.t. $w, h \in \mathbb{R}$ for some given $y \in \mathbb{R}$. Clearly, any $w, h$ on the curve $h(w) = \frac{y}{w}$ are (global) minimizers. The Hessian for global minimizers reduces to

This matrix has eigenvalues $0$ and $\frac{y^2}{w^2} + w^2$, and hence $\Vert \nabla^2 f(w, h(w)) \Vert = \frac{y^2}{w^2} + w^2$. Clearly, as $w \to \infty$, this Hessian norm grows unbounded, whereas the gradient norm $\Vert \nabla f(w, h(w)) \Vert = 0$ remains zero. This clearly violates $(L_0, L_1)$-smoothness.

Consequently, also Assumption 2.8 is violated. However, it remains unclear whether anisotropic smoothness may nevertheless hold for some reference function $\phi$; this is a question we are further exploring. In this regard, we also highlight that anisotropic smoothness generalizes $(L_0, L_1)$-smoothness, since the equivalent matrix inequality [32, Lemma 2.5] only imposes an upper bound to the eigenvalues of $\nabla^2 f(x)$. We refer to our answer of Reviewer F5tt's first comment for more details.

A possible implication for unregularized matrix factorization is that regularization actually helps satisfy (generalized) smoothness assumptions, which in turn may make the optimizer more efficient. We believe that this hypothesis deserves further investigation.

We thank you for your valuable suggestions, and hope that we have accurately addressed your questions.

Dear Reviewer,

We thank you for your time and effort in reviewing our work.

Comment: Lack of numerical experiments.

Response: To address this comment, we have conducted two experiments:

(i) For the symmetric matrix factorization problem (6) with $n = 2$ and $r = 1$, we have created a 2D visualization of the level curves of the objective, along with the iterates of both classical gradient descent (GD) and nonlinearly preconditioned gradient descent (P-GD) with $\phi(x) = \cosh(\Vert x \Vert) - 1$. As suggested by Reviewer M3Bk, this provides the reader with some intuition regarding the (P-GD) behavior. In particular it reveals that unless (GD) is initialized close to a stationary point, the stepsize must be chosen (very) small to prevent the iterates from diverging -- as expected, because the objective is not Lipschitz smooth. In contrast, the (P-GD) iterations take the form (for $\bar L = 1$)

In this case, large gradients are damped -- recall the close resemblance to clipping methods, cf. Fig 1b -- resulting in the convergence of (P-GD) for stepsizes $\gamma$ that are often orders of magnitudes larger than the maximum stepsize of (GD). In turn, this causes (P-GD) to often require significantly fewer iterations, and overall outperform (GD) for fixed stepsize.

(ii) We illustrate the fast escape of saddle points by Algorithm 1, by reproducing the experiment of [11, Section 5] for Algorithm 1. In particular, we consider the `octopus' objective from [11] which was precisely constructed to ensure that (GD) takes exponential time to find a local minimizer. We also select all hyperparameters as in the experiment of [11], and set the only additional hyperparameter $\bar L = 1$. We compare against classical GD, and vary the constant $L \in \\{1, 1.5, 2, 3\\}$ and dimension $n \in \\{5, 10\\}$, thus recreating the plots [11, Figs 3 and 4] for Algorithm 1 and classical GD. The resulting plots look very similar to [11, Figs 3 and 4] and validate Theorem 3.6. For example, they confirm that the number of iterations scales proportionally with $L$. In this way, we also confirmed that the number of iterations scales proportionally with $\bar L^{-1}$.

We believe these experiments significantly improve our manuscript and therefore plan to include them.

Comment: Lack of analysis for parameter $r$ in Assumption 2.8.

Response: The meaning of this comment is not entirely clear to us, so please let us know if it is not properly addressed by the statements below.

In case you are wondering how to obtain $r$ in Assumption 2.8 for specific applications, the degree of the polynomial bound to the Hessian norm is typically quite clear, especially for polynomial objectives. Given this polynomial upper bound of degree $r$ the main difficulty in showing that Assumption 2.8 holds, is establishing the polynomial lower bound to the gradient norm.

In case this comment relates to us using the same symbol $r$ for the polynomial degree in Assumption 2.8 and the perturbation radius $r$ in Algorithm 1 (which are unrelated, see also Question 2), we apologize. We will update the notation.

Question: Does requiring gradient growth $r+1$ to strictly exceed Hessian growth $r$ limit application scenarios?

Response: We are not aware of practical applications in which this is the limiting factor, although toy examples can of course be constructed.

Nevertheless, we highlight that in cases where the gradient norm is lower bounded by a polynomial of degree $r$ rather than $r+1$, Theorem 2.9 still holds, as noted in the footnote on page 4. Likewise, the proof of Theorem 2.11 still holds for reference functions $\phi(x) = h(\Vert x \Vert)$ for which ${h^*}'(y)$ is uniformly lower and upper bounded. This is the case, e.g., for $h(x)= - \vert x \vert - \ln(1 - \vert x \vert)$, but not, e.g., for $h(x) = \cosh(x) - 1$.

For simplicity of exposition, and because we believe this entails no significant limitation, we formulated Assumption 2.8 with the gradient growth strictly exceeding the Hessian growth.

Question: What relationship exists between the polynomial degree $r$ and the function $f$ in Algorithm 1? Is there any theoretical or empirical analysis on how to select the appropriate $r$ for different function $f$?

Response: The polynomial degree $r$ in Assumption 2.8 is unrelated to the perturbation radius $r$ in Algorithm 1: the former bounds the gradient and Hessian growth of $f$, whereas the latter is a hyperparameter in Algorithm 1, which we fix (cf. (13)) in the analysis of Theorem 3.6.

We acknowledge that using the same symbol for both is confusing, and will update the notation to have separate symbols for both; our apologies for any confusion caused because of this.

Question: It is not entirely clear under what practical conditions Assumption 3.3 is guaranteed to hold. Are there natural or verifiable sufficient conditions on the function $f$ and the reference function $\phi$ that ensure Assumption 3.3 holds?

Response: Thank you for raising this interesting question. First, we would like to point out that the reasoning in Example 3.4 with $\phi = \cosh(\vert \cdot \vert) - 1$ actually holds for any univariate polynomial, regardless of its degree. We will also explicitly mention this in the manuscript. This result provides a strong indication that Assumption 3.3 is relatively mild, although verifable sufficient conditions on $f$ and $\phi$ remain difficult to obtain.

Nevertheless, it appears that polynomial bounds can also be used as a sufficient condition in this case. We further explored this idea under the conditions of Theorem 2.11 and the additional assumption that $h^* \in \mathcal{C}^3$, which we mention only holds for $h = \cosh(\cdot) - 1$, but not for the other kernel functions in (2).

Lipschitz continuity of $H_\lambda(x)$ can be established through boundedness of $\Vert \nabla H_\lambda(x) \Vert$, which in turn can be bounded by an expression of the form

After careful examination of the structure of $\Vert \nabla^3 \phi^*(\nabla f(x)) \Vert$, a similar reasoning as in the proof of Theorem 2.11 indicates that the following two conditions on $f$ and $h$ would be sufficient:

(i) $\Vert \nabla^3 f(x) \Vert$ is upper bounded by a polynomial of degree $r$ in the variable $\Vert x \Vert$ (similar to the Hessian bound in Assumption 2.8).

(ii) $\vert {h^*}'''(y) \vert$ decreases fast enough as $y \to \infty$, i.e.,

We note that this condition holds for $h = \cosh(\cdot) - 1$.

It would be interesting to further investigate the approach outlined above. In particular, we believe that the assumption $h^* \in \mathcal{C}^3$ can be relaxed to accomodate for both $h(x) = \exp(\vert x \vert) - \vert x \vert - 1$ and $h(x) = - \vert x \vert - \ln(1 - \vert x \vert)$, in which case the corresponding ${h^*}''(y)$ is differentiable everywhere except at $0$.

We hope that we have accurately addressed any concerns that you may have had.

Dear Reviewer,

We thank you for your encouraging feedback.

Suggestion: Another relevant reference.

Response: Thank you for bringing this relevant reference to our attention. We include it accordingly.

Suggestion: Guide readers to [32] for a geometric intuition behind $(L, \bar L)$-anisotropic smoothness.

Response: Thank you for this suggestion. We will add an explicit pointer to [32, p2], which links anisotropic smoothness to the related concept of $\Phi$-convexity and provides a visualization of the latter. For a deeper geometric intuition, we believe it is also worth pointing the interested reader to the related works [23, 31] on $\Phi$-convexity.

Question: Theorem 3.2: Why does $U$ need to be measure one, and why are $\Vert \nabla f(x) \Vert$ and $\bar L$ related?

Response: The recent extension of the stable-center manifold theorem to nonsmooth iteration maps [8, Prop. 2.5] requires the iteration map $T_{\gamma, \lambda}$ to be continuously differentiable on a set of measure one. This is the case if $\nabla \phi^*(\bar L^{-1}\nabla f(\cdot))$ is continuously differentiable almost everywhere.

For $\phi = h(\Vert \cdot \Vert)$ with $h = \frac{1}{2} \Vert \cdot \Vert^2 + \delta_{[-1, 1]}$ we have that

which is potentially non-differentiable at points $x$ for which $\Vert \bar L^{-1} \nabla f(x) \Vert = 1$. If $U$ has measure one, then $\nabla \phi^*(\bar L^{-1}\nabla f(\cdot))$ is continuously differentiable almost everywhere, as required by [8, Prop. 2.5]. We also refer to Question 3 of Reviewer M3Bk for more details on when this assumption holds.

We thank you again for your suggestions and hope this response adequately addresses your question.