Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity

Dear reviewer, we thank you for your review and comments. We sincerely appreciate your reading and feedback, your engagement with our manuscript, and the recognition of our “quite interesting theoretical results about the developed algorithms” in the work. We will be sure to take your feedback into account in the presentation of our manuscript.

We would like to respond to the weakness and question you posed as follows. We believe this response will help clarify the results of our manuscript and we hope for a productive discussion. All the sources here are the same as in our manuscript.

We first would like to clarify Assumption 1.1. Our Assumption 1.1 is not that $||\nabla^2 F(w)|| \le \rho_1(||\nabla F(w)||)$, but rather $||\nabla^2 F(w)|| \le \rho_1(F(w))$ (the difference being an upper bound in terms of function value rather than gradient), and in fact our Assumption 1.1 is more general. Namely, the assumption $||\nabla^2 F(w)|| \le \rho_1(||\nabla F(w)||)$ for sub-quadratic $\rho_1(\cdot)$ (from Li et al 2023a, generalizing Zhang et al 2020) is subsumed by our assumption, see Proposition A.1. In particular when $\rho_1(x)=L_1 x + L_0$, the $(L_0, L_1)$-smoothness assumption pioneered in Zhang et al 2020 and followed up in many subsequent works, this implies Assumption 1.1 with $\rho_1(x) = \frac32 L_0 + 4 L_1^2 x$ (Proposition A.1). Moreover, there are natural univariate functions where our Assumption 1.1 holds but the $||\nabla^2 F(w)|| \le \rho_1(||\nabla F(w)||)$ condition does not hold for sub-quadratic $\rho_1(\cdot)$, see Example 1.

We respectfully disagree with the assessment that our algorithms are not practical in their current form. In our results, $\eta$ is a fixed step size which only depends on $\rho_1(F(w_0))$, a fixed value depending only on initialization. Moreover, the expressions depending on $\rho_1(F(w_0))$ are only an upper bound for working step sizes. We do not need to know these exact values. Therefore to implement our algorithms, all that is needed is an upper bound on fixed quantities such as $\rho_1(F(w_0))$. Thus a working step size for our algorithms can be found using cross validation or binary search. We will be sure to add this discussion to our manuscript and we thank the reviewer for bringing this point up.

Furthermore as mentioned above, $(L_0, L_1)$-smoothness implies our Assumption 1.1 with $\rho_1(x) = \frac32 L_0 + 4 L_1^2 x$. Thus under $(L_0, L_1)$ smoothness, it is simple to back out a range of working step sizes in terms of $L_0, L_1, F(w_0)$ for all of our Theorems. This dependence on $L_0, L_1, F(w_0)$ is similar to the dependence in the step sizes provided in Zhang et al 2020, Jin et al 2021b, Crawshaw et al 2022, Li et al 2023a, Li et al 2023b, and many other works.

On adaptivity: Indeed as the reviewer pointed out, it would be interesting to get a completely adaptive algorithm. That said, one can interpret cross validation or binary search over $\eta$ as adaptive algorithms in their own right. This leads to results for cross validation or binary search over $\eta$ that are analogous to our current results, and it is relatively straightforward to make these results formal. In the learning from data setting, one can make the cross validation result formal using classic techniques. Again, we will be sure to add this point to our manuscript and we thank the reviewer for bringing this point up.

Finally, we wish to clarify the goal of our manuscript. Our goal is not to propose new algorithms. Rather, we perform a theoretical analysis of existing, practical, and widely used first-order optimization algorithms. We systematically establish stronger theoretical results for these widely used algorithms – in particular, novel results on SOSPs – in the more realistic and challenging generalized smooth setting. Our manuscript is not focused on demonstrating the validity of new algorithms.

We note that finding SOSPs is a significant and difficult problem established in the literature for over a decade, which carries strong theoretical and practical implications in optimization for machine learning. We furthermore note that our work contains simulations. Our simulations show that the dependence on initialization via $\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior on which step sizes successfully optimize generalized smooth functions in practice.

Please let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!

Dear reviewer, we thank you for your review and comments. We sincerely appreciate your supportive review, careful reading and feedback, and belief that our main results seem compelling to a well-motivated problem and that our work “offers a systematic and fundamental view of how such arguments are structured, making it a valuable contribution to the literature”. We will be sure to improve the notation and presentation by taking your suggestions fully into account.

We would like to respond to the questions and weaknesses you raised as follows. All the sources here are the same as in our manuscript or your review.

Third-order self-bounding regularity: This is a good question, and we thank the reviewer for raising it. The third-order self-bounding regularity condition does carry further significance. Namely, Xie et al 2024 very interestingly demonstrates that under mild assumptions, the objective of Distributionally Robust Optimization (DRO) satisfies their Assumption 3 (see Theorem 3 in their paper), which is subsumed by our third-order self-bounding regularity condition as per our Example 2. Thus our results apply to DRO. DRO is a general optimization problem that has significant applications in fairness in machine learning and in learning under distribution shifts; see Xie et al 2024 for more discussion. We will be sure to add this discussion to our manuscript. We also demonstrate in Example 2 that this condition covers several natural growth rates of interest.

Notation for the framework: We thank you very much for the detailed comments on the presentation. We will be sure to clean it up as best we can. Regarding $\mathcal{R}(\mathcal{A}_2(\cdot))$, this was a presentation choice we made. We believe defining $\mathcal{R}$ separately is more natural when presenting high probability results for the algorithm returning exactly one candidate solution in $\mathcal{S}$ (which we did not present in our submission for simplicity). If the reviewer feels strongly that this notation is cumbersome, we are happy to change this in our manuscript.

That said, we believe some of the framework’s notation is both helpful and necessary. In particular, we define $\mathcal{R}$ for sequences of any length because for Restarted SGD, $\mathcal{R}$ takes in the average of $K_0$ points, which can be of arbitrary length. Likewise for SGD, $\mathcal{R}$ outputs a sequence of $K_0$ consecutive iterates, which also can be of arbitrary length.

Generality of assumption 3.1: We believe Assumption 3.1 is quite general; it allows for the variance of gradient noise to increase with function value, considered a more realistic setting for gradient noise studied in Wojtowytsch 2023, 2024 and De Sa et al 2022. We can also extend Theorem 3.3 to sub-Gaussian noise with sub-Gaussian parameter depending on function value as we discuss in Remark 4, which was also considered in De Sa et al 2022 as a more general assumption for gradient noise in SGD. As per your suggestion, we will be sure to add more comparisons of Assumption 3.1 to other works studying relaxed gradient noise assumptions, such as Gower et al 2019.

Re experiments/simulations: Indeed, they are not on phase retrieval or matrix PCA. Instead our experiments/simulations empirically verify that when optimizing natural generalized smooth functions with GD and SGD, the larger the loss $F(w_0)$ is at initialization, the smaller the largest working step size is (in contrast to optimizing smooth functions). These results show that the dependence on initialization via $\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior in practice. Thus our experiments/simulations validate the practical implications of our theoretical results. We thank you for the feedback and we will separate the last paragraph of Subsection 3.6 in our manuscript as per your suggestion.

Please let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!

Dear reviewer, we thank you for your review and comments. We sincerely appreciate your supportive review, thoughtful questions, and belief that we are solving an important problem in machine learning and that we “provide a thorough and unified convergence analysis for a wide variety of first-order algorithms”. We will be sure to add further discussion on our experiments/simulations in our manuscript as you suggested.

We would just like to respond to the questions and weaknesses you raised as follows. All the sources here are the same as in our manuscript.

Generality of self-bounding regularity: This is a good question, and we thank the reviewer for raising it. As discussed in Section 1.1 (see Proposition A.1), second-order self-bounding regularity is strictly more general than the $(L_0, L_1)$-smooth conditions which arise frequently in machine learning.

-The $(L_0, L_1)$ smoothness condition arises frequently in machine learning, and therefore by the following discussion, self-bounding regularity arises in the exact same situations as well. Namely $(L_0, L_1)$ smoothness was experimentally shown to hold for LSTMs in Zhang 2019 et al and transformers in Crawshaw et al 2022, and has been subject to extensive study in recent years as a more realistic set of regularity assumptions for optimization in machine learning.

-We demonstrate in Proposition A.1 that $(L_0, L_1)$-smoothness implies self-bounding regularity with $\rho_1(x) = \frac32 L_0 + 4 L_1^2 x$. Li et al. 2023a generalized $(L_0, L_1)$-smoothness and once more, our self-bounding regularity conditions subsumes the condition of Li et al 2023a; see our Proposition A.1. We also demonstrate in Example 1 that there are natural univariate functions which do not satisfy $(L_0, L_1)$ smoothness and do not satisfy the condition of Li et al 2023a, but do satisfy self-bounding regularity.

Thus we believe self-bounding regularity is quite general and arises frequently in modern machine learning. Moreover, there is growing evidence that conditions analogous to self-bounding regularity imposing quantitative control of the Hessian in terms of gradient or function value are necessary for optimization to succeed via first-order methods (even for finding stationary points). Namely, see Kornowski et al 2024 Theorem 2.1 and De Sa et al 2022 Theorem 3. That said, we emphasize that we work with self-bounding regularity not just because it is more general than $(L_0, L_1)$ smoothness, but because we believe it is a more natural way of analyzing ubiquitous first-order optimization algorithms under generalizations of smoothness.

For third-order self-bounding regularity, we demonstrate several theoretical examples in optimization for machine learning, namely phase retrieval and matrix PCA, satisfy this condition and also satisfy second-order self-bounding regularity. We also demonstrate in Example 2 that this condition covers several natural growth rates of interest. Moreover, Xie et al 2024 very interestingly demonstrates that under mild assumptions, the objective of Distributionally Robust Optimization (DRO) satisfies their Assumption 3 (see Theorem 3 in their paper), which is subsumed by our third-order self-bounding regularity condition as per our Example 2. Thus our results apply to DRO. DRO is a general optimization problem that has significant applications in fairness in machine learning and in learning under distribution shifts; see Xie et al 2024 for more discussion. We will be sure to add this discussion to our manuscript.

Dependence on initialization: It is true that the step size will depend on initialization. This holds true also for many works studying optimization with GD and SGD under generalizations of smoothness, such as Li et al 2023a. We also note that the step size provided is an upper bound on possible working step sizes. Thus, one can find a working step size with cross validation in the learning setting. We will add this point to our manuscript at the reviewer’s suggestion.

In fact, this dependence on initialization carries important practical implications, as we describe in Section 3.6 and detail fully in our experiments/simulations in Section 9. There, we empirically verify that when optimizing natural generalized smooth functions with GD and SGD, the larger the loss $F(w_0)$ is at initialization, the smaller the largest working step size is (in contrast to optimizing smooth functions). These results show that the dependence on initialization via $\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior in practice. Thus our experiments/simulations validate the practical implications of our theoretical results on which step sizes successfully optimize generalized smooth functions.

Please let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!

Dear reviewer, thank you for your constructive comments. We sincerely appreciate your reading and feedback, and your engagement with our manuscript. We will be sure to revise our manuscript to improve our exposition of a decrease procedure and to further emphasize central conceptual ideas in our work, particularly in Section 2, taking your feedback fully into account.

We would like to answer your questions as follows. All sources in the following are from our manuscript or your comments.

Motivation and related work: This is a good question, and we thank the reviewer for raising it. The results of Lee et al. 2016, 2019 show asymptotic guarantees. However, we are focused on nonasymptotic guarantees/efficient rates for the convergence of first order methods, which is very important in theory and practice where iterations are limited. (Indeed as reviewer er1q points out in their comment, many of our results are sharp in order of precision $\epsilon$.) For such nonasymptotic guarantees of finding SOSPs, the Hessian Lipschitz assumption appears ubiquitously in the literature (except for Xie et al. 2024, whose assumption is generalized by our work as per Example 2). This motivates our generalization of the Hessian Lipschitz assumption. At your suggestion, we will be sure to cite and add discussion r.e. Lee et al. 2016, 2019 to our manuscript, including on asymptotic almost sure guarantees under our regularity assumptions. We will also be sure to further emphasize our focus on efficient rates/nonasymptotic guarantees. Again, we thank you for bringing up this point.

We believe our generalization of the Hessian Lipschitz assumption, Assumption 1.2, is quite general: it is satisfied by phase retrieval and matrix PCA (Subsection 3.6), covers many growth rates of interest (Example 2), and furthermore under mild conditions, it is satisfied by Distributionally Robust Optimization (see our response to reviewer SgYJ, which we will add to our manuscript). Moreover, Kornowski et al. 2024 showed quantitative control of the Hessian is in fact necessary for nonasymptotic guarantees of finding first order stationary points. We also note our Assumption 1.1 generalizes the $(L_0, L_1)$ smoothness assumption which is a widely studied relaxation of gradient Lipschitzness, and our Assumption 1.2 generalizes the regularity assumptions of Xie et al. 2024; see our response to reviewer SgYJ and er1q for more details on this.

Step size clarification: Thank you for raising the question. Under Assumption 1.1, the standard choice of step size $\eta \le 1/L$ in smooth optimization where $L$ is a global upper bound on $||\nabla^2 F||$ does not work, since no finite bound $L<\infty$ exists (hence one would have to set $\eta=0$). This is what we meant by $\eta$ becoming vanishingly small. However, $1/L(w_0)$ in (4) is not vanishingly small as $L(w_0) < \infty$ is the ‘effective smoothness constant’ in the $F(w_0)$-sublevel set, where the iterates are guaranteed to lie (with high probability). Also note that any step size $\eta \le \frac1{L(w_0)}$ would work, see our response to reviewer er1q.

Assumptions and technical contributions, and main points of our paper: We wish to reiterate the core idea in our paper, which builds upon selecting an appropriate step size and generalizing the descent lemma to encompass the following. As discussed in Subsection 2.1 of our manuscript, the crucial idea to ‘chain together’ the descent lemma; to formalize this idea, we introduce the notion of a decrease procedure. In particular, the algorithm being a decrease procedure in the $F(w_0)$-sublevel set guarantees decrease (with high probability) when the step size is chosen appropriately in terms of initialization $w_0$, which guarantees the step size defined in terms of $w_0$ works at the next iterate, which guarantees decrease again, and so forth. Thus all the iterates lie in the $F(w_0)$-sublevel set (with high probability), and furthermore this decrease cannot occur too many times as $F$ is lower bounded, yielding bounds on iteration complexity. We believe this gives a systematic view of how these convergence proofs are structured under generalized smoothness, as reviewer SgYJ also points out. We will be sure to further emphasize this discussion and perspective in our manuscript, by emphasizing it further in Section 2 and adding it to the summary of our contributions in Section 1 and in the exposition in Sections 3 and 4. We thank the reviewer for the helpful suggestion.

Please let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!