OPTAMI: Global Superlinear Convergence of High-order Methods

Dear Reviewer TJTR,

Thank you for your valuable feedback! We appreciate your recognition of the strengths of our work, including the established superlinear convergence of second-order methods and our open-source library. We also value your constructive suggestions for areas requiring further discussion and improvement. Below, we address your questions. We have also uploaded a revised version of the paper and kindly invite you to review it.

Weakness 1. Structure of the paper

We realize that our initial presentation may have created the impression that NATA and the superlinear convergence results are separate topics. However, these two components are closely linked, as both address open challenges we faced during the development of the OPTAMI library. For further details, we invite you to review the common commentary, "Modified Structure of the Work," where we explain the narrative behind our approach and the relationship between these elements. The paper has been updated to reflect these clarifications.

Weakness 2. Questions 1 and 2. Subproblem.

Following the classical literature, we prove theoretical convergence results under the assumption of exact computations and exact subproblem solution. Introducing inexactness at this stage could overcomplicate the paper with technical details that might obscure the main ideas and results. We believe that analyzing various types of inexactness in the method could form the basis of a separate, technically focused paper more suited for an optimization journal [1],[2]. From a practical point of view, subproblems can often be solved inexactly, for example, Basic Tensor Method implemented in OPTAMI with inexact iterative subsolver. Our experiments demonstrate that this inexactness does not compromise global superlinear convergence. Efficiently solving cubic regularization and tensor subproblems remains an active area of research, with numerous dedicated papers [3], [4], [5], [6]. For this reason, we have chosen to leave this topic outside the scope of our current work.

[1] Nesterov, Yurii. "Inexact basic tensor methods for some classes of convex optimization problems." Optimization Methods and Software 37.3 (2022): 878-906.

[2] Grapiglia, Geovani Nunes, and Yu Nesterov. "On inexact solution of auxiliary problems in tensor methods for convex optimization." Optimization Methods and Software 36.1 (2021): 145-170.

[3] Carmon, Yair, and John Duchi. "Gradient descent finds the cubic-regularized nonconvex Newton step." SIAM Journal on Optimization 29.3 (2019): 2146-2178.

[4] Thomsen, Daniel Berg, and Nikita Doikov. "Complexity of Minimizing Regularized Convex Quadratic Functions." arXiv preprint arXiv:2404.17543 (2024).

[5] Jiang, Rujun, Man-Chung Yue, and Zhishuo Zhou. "An accelerated first-order method with complexity analysis for solving cubic regularization subproblems." Computational Optimization and Applications 79 (2021): 471-506.

[6] Gao, Yihang, Man-Chung Yue, and Michael Ng. "Approximate secular equations for the cubic regularization subproblem." Advances in Neural Information Processing Systems 35 (2022): 14250-14260.

Weakness 3. Question 3 and 4. Strong star-convexity

Thank you for the insightful questions and suggestions. In response, we have added experiments for various accelerated methods on strongly convex functions, as shown in Figure 5. Interestingly, most of these methods appear to exhibit global superlinear convergence without any specific theoretical adaptation for strongly convex functions, which is quite surprising.

Regarding the proofs, we can derive classical theoretical results for the restarted version of NATA, similar to existing methods. However, we currently do not have a way to prove global superlinear convergence for either classical Nesterov Acceleration or NATA. As such, we have highlighted this as an open problem and a potential direction for future research in the Conclusion section.

Weakness 4. Various unclear descriptions

Thank you for highlighting the unclear descriptions and minor errors. We have addressed these issues during the reorganization of the paper. The specific changes are as follows:

1. We now begin the paper by focusing on convex functions, ensuring that the rates presented in the introduction are valid.
2. We have corrected the “upperbound” and removed NPE. Matrix $B$ and corresponding norm have been introduced to align with the more general notation used by Yurii Nesterov in his papers [7], [1], [2]. However, if you believe this adds unnecessary complexity, we are open to removing it.

[7] Nesterov, Yurii. "Implementable tensor methods in unconstrained convex optimization." Mathematical Programming 186 (2021): 157-183.

Weakness 5. Insufficient reference.

As part of the reorganization, we entirely removed the discussion regarding the “poor global convergence” rate of the quasi-Newton method. Instead, we introduced a concise paragraph on Hessian approximations to motivate the exploration of second-order methods. Additionally, we incorporated more citations to strengthen the section on Quasi-Newton methods and Hessian approximations.

Dear Reviewer TJTR,

Thank you for the clarification!

Allow us to explain our perspective on this matter. Our theoretical results are derived under the standard assumptions of exact computations and exact subproblem solutions. It is a common and acknowledged practice in optimization community. To support this perspective, we highlight several influential optimization papers from well-known research groups accepted at major conferences or journals which assume exact computations and exact subproblem solution [1, 2, 3, 4, 5]. We believe that theoretical improvements within this exact regime is both normal and valuable, and it should not be considered a reason for rejection.

From the practical perspective, our Cubic Regularised Newton is implemented as it was introduced in the original paper with the same computational complexity. So, there is no overhead computation to get the provided experiments. As we mentioned in limitations, all second-order methods with exact Hessian “have computational and memory limitations in high-dimensional spaces, due to the need for Hessian calculations. There are, however, approaches to overcome this, such as using first-order subsolvers or inexact Hessian approximations like Quasi-Newton approximations (BFGS, L-SR1). In this paper, we focus on the exact Hessian to analyze methods’ peak performance.” We view our results as fundamental discovery for second-order methods which explains their practical properties. Next, in future research, they can be smartly coupled with inexact Hessian approximations or first-order subsolvers to make them dominant in both low and high-dimension settings.

We hope this explanation clarifies our perspective and addresses your concerns.

Best regards, Authors

[1] Doikov, N., Mishchenko, K. and Nesterov, Y., 2024. Super-universal regularized newton method. SIAM Journal on Optimization, 34(1), pp.27-56.

[2] Bubeck, S., Jiang, Q., Lee, Y.T., Li, Y. and Sidford, A., 2019, June. Near-optimal method for highly smooth convex optimization. In Conference on Learning Theory (pp. 492-507). PMLR.

[3] Antonakopoulos, K., Kavis, A. and Cevher, V., 2022. Extra-newton: A first approach to noise-adaptive accelerated second-order methods. Advances in Neural Information Processing Systems, 35, pp.29859-29872.

[4] Gower, R., Goldfarb, D. and Richtárik, P., 2016, June. Stochastic block BFGS: Squeezing more curvature out of data. In International Conference on Machine Learning (pp. 1869-1878). PMLR

[5] Jiang, R., Raman, P., Sabach, S., Mokhtari, A., Hong, M. and Cevher, V., 2024, April. Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate. In International Conference on Artificial Intelligence and Statistics (pp. 4411-4419). PMLR.

Dear Reviewer Pnwc, Thank you for your valuable feedback. We are grateful for your recognition of the strengths of our work and for your thoughtful and constructive suggestions, including the presentation style and the perceived logical disconnect between the two parts of our work in the initial version. We have uploaded a revised version in which we have tried to address your suggestions. We kindly ask you to review the updated manuscript along with the common commentary "Modified Structure of the Work."

Major comments:

• We regret that our initial presentation style gave the impression that NATA and the superlinear convergence rate are two independent topics. NATA and the theoretical proof of superlinear convergence address open problems we encountered during the development of the OPTAMI library. For more details, please review the common commentary "Modified Structure of the Work", where we outline the narrative behind our approach and the connection between these components. We have updated the paper accordingly.

• We refined the Introduction section by moving technical details to a specific subsection in Section 2, which focuses on the contents of the library. The paper has been updated accordingly.

• As you recommended, we have added NATA with tuned $\nu^t$ for every figure in the main paper. We will also include them in the experiments presented in the Appendix later. The main difference between the tuned and adaptive versions lies in the number of main parameters: adaptive NATA has one primary parameter, $L$, while NATA with tuned $\nu^t$ involves two parameters, $L$ and $\nu$. The additional parameter is a limitation of the tuned method compared to other acceleration techniques, which typically require only one main parameter. In the paper, we emphasize that the method with tuned $\nu$ generally outperforms the adaptive version in terms of efficiency, as it avoids the need for additional computations associated with adaptive search. However, this advantage depends on proper tuning of $\nu^t$ — without accurate tuning, the method may diverge. From our perspective, both adaptive and tuned NATA have their applications. If the adaptive search is available, the adaptive NATA is useful as has less parameters. On the other hand, while the tuned version can significantly accelerate the method (compared to classical Nesterov acceleration) in scenarios where exact function values are not accessible.

• We believe that using "Hessian computations" as the comparison axis is the fairest metric. All cubic methods solve the same type of subproblem and require nearly the same computational effort per iteration. Specifically, one Hessian computation corresponds to solving a single cubic subproblem. Furthermore, like adaptive NATA, other near-optimal and optimal acceleration methods perform line searches and may compute multiple Hessians per iteration. For example, Prox Point Segment Search methods typically involve around three Hessian computations per iteration. This consistency makes "Hessian computations" a fair and reliable axis for comparing acceleration methods.

Questions

1. Thank you. We fixed the misprint.

2. Thank you. We rephrased this line. Please let us know, if it is more clear now.

3. No, the CRN converges globally superlinearly only for strongly star-convex functions, not for uniformly star-convex functions. On the other hand, the $p$-th order Basic Tensor method achieves global superlinear convergence for $\mu_q$-uniformly star-convex functions when $p \geq q-1$.

Dear Reviewer WM8N, We sincerely appreciate your comprehensive and insightful review of our paper and your recognition of the strengths of our work. Below, we try to address your questions and comments.

Weakness 1. Questions 1 and 2

The existing results about the convergence rate of second-order methods for strongly-convex functions primarily address the regime where $\varepsilon < \frac{\mu^3}{L_2^2}$, as seen in both the lower-bounds (Theorem 1, Arjevani et al. 2019) and upper-bounds (Formula 1.14, Song et al. 2021). For instance, in Formula 1.14 from Song et al. 2021, if $\varepsilon > \frac{\mu^3}{L_2^2}$, the term $\log( \log(\frac{\mu^3}{L_2^2 \varepsilon}))$ becomes undefined. This implies that the method from Song et al. 2021 is optimal for the setting of optimizing strongly convex functions with second-order methods when $\varepsilon < \frac{\mu^3}{L_2^2}$.

In our work, we focus on the less-explored regime where $\varepsilon > \frac{\mu^3}{L_2^2}$, which corresponds to scenarios where a solution can be less precise. To visualize this regime better, consider a function $f(x)$ with $L_2=1$ and $\mu=10^{-4}$. In this case, Formula 1.14 imposes $\varepsilon < 10^{-12}$, a value far smaller than practical needs. In some applications, achieving an approximate solution with accuracy around $\varepsilon = 10^{-6}$ may be sufficient, which is the focus of our results. Furthermore, once the method with a global superlinear rate enters the quadratic convergence region, it transitions to classical convergence rates. Thus, our results complement the existing literature by addressing a different regime rather than introducing a trade-off. Additionally, our results provide valuable insights into the practical performance of second-order methods. In summary, we address the less-explored setting where $\varepsilon > \frac{\mu^3}{L_2^2}$, complementing and extending the existing literature rather than contradicting it. We have also corrected all the typos you highlighted. Thank you for pointing them out!

Dear Reviewer BoHs,

Thank you for your detailed and thoughtful review of our paper! We are pleased to hear that you found our theoretical analysis and practical developments compelling. We appreciate your constructive comments on the presentation style and organization of the paper, and we have made adjustments in the revised version to address them. For a detailed overview of the changes, please refer to the common response and revised version of the paper. Below, we specifically address your comments and the improvements we have made.

Major Comments on Structure:

Revised Introduction

We have significantly shortened and reorganized the Introduction section, removing many of the equations that were initially included. These equations have been relocated to Section 2, as you suggested, for better high-level structure and readability.

Expanded Methods Section

The second section has been enriched with content previously found in the Introduction. We have added further details and descriptions, particularly regarding the OPTAMI library, to provide a more comprehensive and logically structured presentation of the methods.

Novelty

Our results, to the best of our knowledge, are novel and somewhat unexpected. Initially, we found it surprising that in the experiments, Cubic Regularized Newton methods exhibited superlinear convergence even when far from the solution. Upon further research, we identified a loophole in existing lower bounds that does not cover the convergence of second-order methods before reaching the quadratic convergence area. Building on this observation, we developed and presented a new convergence theory demonstrating global superlinear convergence. Additionally, we relaxed the strong convexity assumptions to the more general strongly star-convexity, which allows for non-convex cases. We have added Table 1 at the end of the manuscript to emphasize the novelty of our results compared to the current state of the literature. The lower bound for convergence of second-order methods for any precision is still an open question.

Revised Fourth Section

We reorganized Section 4, incorporating the recommended connections and enhancing clarity. Specifically, we added a comparison with vanilla NATM. For clarity, we note that the theoretical convergence rates of NATA and NATM are the same, differing only in the additional iterations required for the adaptive search of $\nu^t$ in NATA. Merged Sections and Additional Experiments: Following your recommendation, we merged Sections 4 and 5. Furthermore, we have introduced additional experiments on acceleration methods for regularized logistic regression (strongly convex case) in Figure 5. These experiments demonstrate global superlinear convergence for many methods, naturally leading to the theoretical proofs of superlinear convergence presented in the subsequent section.

Minor comments/typos

We also carefully reviewed the manuscript and corrected all the typos you identified. Thank you for bringing them to our attention, as this helped us improve the overall quality of the paper.

We hope these revisions address your concerns and improve the clarity and quality of the manuscript. Thank you again for your insightful comments, which have been instrumental in refining our work. Please do not hesitate to let us know if there are further areas requiring clarification or improvement.