A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees

We thank reviewer cCif for the valuable comments.

Weakness 1. Some of the symbols in the paper need clearer explanations. For example, the meaning of the symbol  is not explained. Although line 87 mentions "The notations... are used in their standard sense to represent asymptotic behavior," a more detailed explanation would help readers who are not familiar with complexity theory.

Thanks for your suggestions, we will add these explanations in revision.

Weakness 2. On line 260, "lemma" should be "proposition". Additionally, on line 272, the definition of  should be provided. On line 303, there is a missing space before the final "and" in the sentence. Lastly, on lines 951 and 956, the formulae should end with a comma instead of a period.

Thanks for your suggestions, we will fix them in revision.

Weakness 3. The paper is somewhat lengthy. Although this is done for theoretical completeness, it makes the review process for a conference submission more difficult.

Thank you for the feedback. While we acknowledge that the paper is somewhat lengthy due to the theoretical completeness, we have made an effort to highlight the main ideas and intuitions in the main text. The technical details and extended discussions are deferred to the appendix to maintain the flow of the core narrative. We believe this structure strikes a balance between accessibility and rigor. We are also open to reorganizing or condensing the material further in the final version to improve readability. For example, moving the key ingradient LipEstimation of the algorithm to the main text.

Q1: Clarification about Tab 1.

1. In their method, the Lipschitz constant estimator $M_k$ is determined through an inner iteration. However, in Table 1, we report only the number of outer iterations of their algorithm, which is why the $\tilde{O}(1)$ term is omitted. Each inner iteration involves solving a regularized Newton equation, and as shown in their Theorem 4 (specifically Eq. (29)), this introduces an additive $O(\log L_H)$ factor due to the constant $T = O(\log L_H)$ (see their Eq. (25)). In contrast, each iteration of the other compared methods solves only one regularized Newton equation.

2. As an example, in Royer's method they choose the regularizer to be fixed $\sqrt{\epsilon}$, which directly gives a sufficient descent $O(\epsilon^{1.5})$ at every iteration, but such a choice is not adaptive and may degrade empirical performance when the tolerance parameter $\epsilon$ is small (as shown in the "fixed \omega$ case of our experiemnt). The advantage of this choice is that it may simplify the theoretical analysis and give an iteration complexity without a multiplicative log factor. On the other hand, "ME" represents the algorithm needs to compute the minimal eigenvalue to determine some parameters, e.g., the regularizer. We will clarify them in the table.

Q2: The choice of $\alpha$ in Alg 1, L13.

It is based on a observation that in Lem D.3(1), choosing the stepsize as the r.h.s. of (D.9) would lead to a linesearch accepted, and the choice of $\alpha$ is designed to track this stepsize, and leave the unknown part $C_M$ in the r.h.s. determined by the linesearch.

Q3: Whether $\theta$ can be adaptively chosen？

This is an interesting question. However, adaptively choosing $\theta$ would require a principled selection rule. We suspect that relaxing the Lipschitz continuity assumption on the Hessian to a $\nu$-Hölder condition may offer insights into such a rule, as in this case, setting $\theta > \nu$ yields the best possible local convergence rate.

Q4: It appears that ARCqK shows excellent time efficiency in most experiments. However, while the authors mention using slightly fewer Hessian evaluations in line 306, it does not seem to result in a better time efficiency. Could the authors further emphasize the practical advantages of the proposed algorithm compared to other methods, particularly in real-world applications? Highlighting these advantages will help readers understand the practical utility of the algorithm better.

Thanks for your suggestion. The differences of ARCqK and our methods in the CUTest benchmark are not quiet significant. ARCqK is a cubic regularization method, but their implementation also solves a regularized Newton equation but they need to search the corresponding regularization coefficient to make the solution satisifies the optimal condition of the cubic regularized subproblem. In contrast, our method can give the descent direction directly and may be helpful when solving the equation is expensive as in the PINN example.

We thank reviewer 9yAV for the valuable comments.

Q1: When training deep neural networks, how to handle the Hessian matrix? In general, the exact computation of Hessian on the full batch is difficult. Do you use Hessian-free (Hessian-vector products) methods or quasi-Newton methods that does not use the exact Hessian? Or do you adopt lazy Hessian?

Our algorithm only relies on the Hessian-vector products (HVPs), which makes the computational and memory costs relatively modest (see Tab 2). Besides, PyTorch supports HVP computation well, so it does not introduce many implementation overhead. We do not adopt the lazy Hessian, but it may be a promising direction for future work.

Q2: Can the algorithm be extended to be stochastic? Most of machine learning problems may require mini-batch sampling. What is the theoretical convergence guarantees?

Thanks for your questions. We think it can be applied to stochastic settings empirically without theoretically guarantees. The main challenge lies in the estimation of the Lipschitz constant and the line search procedure, both of which require evaluations of the full objective function. It is not immediately clear how the method behaves when these are replaced with their stochastic counterparts. As discussed in Sec 5, we leave it as a future work.

Q3: ARC and ARNCG, and Jiang's TR (2311.11489)

1. Relationship to ARC: ARC is an adaptive CR, but there are important differences to our method. The core step of ARC is to minimize a cubically regularized subproblem, which can also be viewed as solving a regularized Newton equation $(\nabla^2\varphi(x) + \rho I)d = -\nabla \varphi(x)$, where $\rho \propto \sigma \| d \|$ depends on the solution $\|d\|$. A key step of ARC is to search an appropriate value of $\rho$, while our method uses a prescribed coefficient $\rho$ that does not depends on the solution $d$, which avoids the search step.

2. Relation to Jiang's trust-region method: Jiang's method is a trust-region type algorithm with a quadratic regularization parameter $\sigma_k$ and an additional free parameter: the trust-region radius $r_k$.

   • For the local convergence rate, as shown in their Tab 2, they first check whether the scale of the minimum eigenvalue of the Hessian is sufficiently large. If so, they set $\sigma_k = 0$ and use the trust-region constraint purely as a globalization mechanism. Under a local convexity assumption, this effectively reduces to the classical Newton method near the solution, allowing for a quadratic convergence rate. However, this strategy requires an additional eigenvalue check and is not directly applicable to regularized Newton methods (RNMs), which rely solely on a regularization parameter. As a result, achieving a quadratic rate is more challenging for RNMs.
   • For the global convergence rate, their global analysis relies on partitioning iterations into successful and unsuccessful sets, similar to the approach described in our Sec 2. This leads to an extra multiplicative $\log(1/\epsilon)$ factor in the complexity bound. In contrast, our new partitioning technique introduced in Sec 3, along with the second choice of regularization coefficients in Thm 2.2, eliminates this additional factor. We believe our new partitioning rule can also improve their log factor to $\log \log (1/\epsilon)$.

Q4: What are the theoretical convergence results if without Lipschitz smoothness? Is it possible?

It may be possible to relax the assumption to $\nu$-Holder continuous one. Under this assumption our Lem 3.7 and its refined version in App F.2 guarantees that $\theta > \nu$ gives a best possible local rate $1 + \nu$. However, to obtain an optimal global rate we may need to modify the Lipschitz estimation rule and dynamically estimate the Holder exponent $\nu$, which needs further efforts and we leave it as the future work.

We thank reviewer hnj5 for the valuable comments.

Q1: the clarity of this article.

Thank you for the valuable suggestions. If the paper is accepted, an additional page becomes available. We plan to include the LipEstimation procedure in the main text. The CappedCG component is a slight modification of the method by Royer et al., so we can present a brief (informal) version to convey its main idea. We believe these changes, along with the intuitive explanations and high-level overview in Sec 2.1, would improve clarity and make the algorithm easier to follow.

Q2: the comparsion with the shifted Steihaug-Toint variant in the CUTest benchmark

Thank you for the suggestion. In our experiments, we selected recent methods from the categories of trust-region methods (CAT), cubic regularization methods (ARCqK), and quadratic regularization methods (AN2CER). According to the results reported in ARCqK, it is “more efficient than a classic Steihaug–Toint trust-region method.” We believe this comparison is representative, and we will clarify it in the revised version.

Q3: The method seems similar in nature to papers like this: https://arxiv.org/pdf/2311.11489

There are some notable differences. Jiang's method is a trust-region type algorithm with a quadratic regularization parameter $\sigma_k$ and an additional free parameter: the trust-region radius $r_k$.

• For the local convergence rate, as shown in their Tab 2, they first check whether the scale of the minimum eigenvalue of the Hessian is sufficiently large. If so, they set $\sigma_k = 0$ and use the trust-region constraint purely as a globalization mechanism. Under a local convexity assumption, this effectively reduces to the classical Newton method near the solution, allowing for a quadratic convergence rate. However, this strategy requires an additional eigenvalue check and is not directly applicable to regularized Newton methods (RNMs), which rely solely on a regularization parameter. As a result, achieving a quadratic rate is more challenging for RNMs.
• For the global convergence rate, their global analysis relies on partitioning iterations into successful and unsuccessful sets, similar to the approach described in our Sec 2. This leads to an extra multiplicative $\log(1/\epsilon)$ factor in the complexity bound. In contrast, our new partitioning technique introduced in Sec 3, along with the second choice of regularization coefficients in Thm 2.2, eliminates this additional factor. We believe our new partitioning rule can also improve their log factor to $\log \log (1/\epsilon)$.

We thank reviewer MUHH for the valuable comments.

Weakness 1: the computational complexity and oracle complexity

Thank you for the helpful suggestions. The overall computational complexity can be viewed as the product of the number of HVP evaluations (Thm 2.3) and the cost of each HVP evaluation, which is typically fixed and does not vary across iterations. We will clarify this point and move the discussion of oracle complexity accordingly in revision.

Weakness 2: the exact version of local convergence and the size of the neighborhood

The non-asymptotic statement of the local convergence is presented in Prop E.4 in appendix. We will move it to the main text. For the size of the local convergence neighborhood, some discussions are presented before Lem 3.7. Its size depends on two factors: (1). the assumption of the solution, i.e., $L_H I \succeq \nabla^2 \varphi(x^*) \succeq \alpha I$. Since our regularizer is at most $g_k^{0.5}$, the local convergence rate is at least 1.5 and its neighborhood does not depend on $\theta$; (2). the parameter $\theta$. When entering the neighborhood with 1.5 local rate, it can be boosted to 2 within $O(\log\log poly(L^\theta_H, U_\varphi^\theta))+ 2\log \frac{2\theta-1}{2\theta-2}$ steps.

Weakness 3 and Question: the comparsion with simper problems and quasi-Newton type methods.

Thanks for your suggestions. The CUTest benchmark also includes a subset of simple functions, e.g., the Rosenbrock's banana function $f(x, y) = (a - x)^2 + b(y - x^2)^2$. There is an illustrative figure in Fig. 4 in p.42. We will clarify this point in the text surrounding the figure.

We note that in prior work on Newton-type methods evaluated on the CUTEst benchmark, quasi-Newton methods such as BFGS, DFP, and SR1 are typically not included for comparison, as they represent a different class of algorithms with distinct convergence properties and design goals. In our case, the focus is on methods that explicitly leverage second-order information.

Nevertheless, we do compare against L-BFGS in the PINN experiment, where it is commonly used in practice. Other quasi-Newton methods such as BFGS and SR1 are less applicable in this setting due to their high memory requirements, as they need to store dense matrices of the same size as the Hessian, which becomes impractical for large-scale problems like PINNs.