Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In the cubic regularization method, a key step is to solve the so called secular equation which may costs O(n^3) time.
In this paper, the authors consider two faster approximation to the secular equation which reduce the computing time to O(n^2 m).
The authors give some theoretical analysis of the proposed methods.

strengths_and_weaknesses: The proposed method reduces the computing time of secular equation, which may be novel.
The paper is relatively well-written and clear.
This paper is mostly a theoretical paper.
In my opinion, however, the theoretical results are not significant enough.
In fact, from the authors' theoretical results (Proposition 3 for example), the proposed method has an irreducible error.
From the authors' experiments, it may be the case that the obtained theoretical bound is too loose.

questions: line 41: Proposition 2. Is this proposition adapted from Claim 2.1 in [1]? Why A + rho ||x^*|| > 0? Can you provide a proof of Proposition 2?
line 45: "and hence the gradient norm serves as an optimality measure" I do not understand this.
line 49: "lambda_1 + simga > 0" Should it be >= 0?
line 90: "for any mu". Should it be "for any mu > lambda_m"?
line 109: What does the symbol big O mean in your context? From line 113, it seems tht ||tuilde x - x*|| has no absolute upper bound, for example, suppose |lmabda_i| and simga* are very small.
line 122 -- 126: These discussions lack mathematical rigor.

From the theoretical view, is it possible to improve the bound?
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the cubic regularization technique and proposes two methods for approximating the secular equation based on the first-order and second-order Taylar expansions. Theoretical discussions including uniqueness and existence of the solution together with error analysis are provided. Five numerical experiments are conducted with comparable performance with the state of the art. However, the trade-off between accuracy improvement and computational reduction for these truncation-based approaches is not clear. Overall, the paper looks interesting with a variety of applications but with limited novelty. 
strengths_and_weaknesses: Strengths: The paper proposes to use simple Taylor approximations to approximate the secular equation, which intends to simplify the computation. Implementation details are provided, together with various numerical comparisons with the state of the art. 

Weaknesses: The Taylor expansion-based truncation seems intuitive and standard, which will bring inaccuracy for the approximation. It is not fully clear how this type of approximation will affect the accuracy and reduce the computational cost. The general high-order approximation could be discussed as well. In addition, in the numerical results, say Table 1, ARC-Krylov seems to outperform the proposed method in terms of running time. A comparison of computational complexity in the big-O notation could be given with theoretical discussions. 
questions: 1. In line 212, what does the "computational waste" mean here?
2. In Table 1, it may not be fair to simply compare the overall running time. The running time per iteration could be compared as well. In addition, does the number of iterations depend on the selection of certain parameters in all methods being compared? If yes, please discuss which parameters are sensitive and provide guidelines for tuning if available. 
3. In Section 5, it would be better to describe the computing platform and computer configurations at the very beginning of the section rather than in an unnoticeable place in Experiment 5. 
limitations: Regularization techniques have been widely used in solving a lot of application problems, such as inverse problems and machine learning. But the paper does not show any such application experiment, which would limit the practical use and attraction.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes an efficient and general scheme for finding approximate solutions to the cubic regularization subproblem (CRS) used in the classic cubic regualization method in nonconvex optimization. The main advantage of the scheme lies in the efficient computation of the unique root in a given truncated approximate secular equation (ABE) that scales as $O(mn^2)$ where $n$ is the dimension of the underlying problem and $m < n$ is a parameter that balances the accuracy of the scheme with the overall computational cost. Numerical experiments are given to demonstrate the behavior of the scheme on different parameter choices, different kinds of problem instances, and a subset of the well-known CUTEst optimization problem dataset.  
strengths_and_weaknesses: **Disclaimer**: My review is limited to the material presented in the 9-page body of the paper, and does not consider the materials in the supplement.

*Strengths*

1. The numerical experiments are significant in their scope and quality. Specifically, they test the behavior of the proposed scheme (ASEM) with respect to its key parameter $\mu$ and the distribution of eigenvalues in the CR subproblem. I also appreciate the inclusion of other well-known algorithms in the benchmarks, such as gradient descent, the Cauchy-point method, and the Krylov subspace method.

2. The error bounds in Theorem 1 and 2 are highly appreciated, as they encapsulate the expected behavior of the scheme and do abuse asymptotic notation to hide any universal constants.

3. The complexity improvement from $O(n^3)$ to $O(mn^2)$ is impactful both from a theoretical and practical point-of-view.

4. The writing of the paper is both clear and concise. Moreover, the remarks following some of the more important results, e.g., Proposition 3, are both welcome and informative.

*(Minor) Weaknesses*

1. There are few places that could better with additional clarifying statements (see the *Questions* section below).

2. There are few minor typos (see the *Questions* section below).
questions: 1. Line 36: Do you mean $V\Lambda V^T$?

2. Proposition 2: Make this slightly more self-contained, by re-iterating what $v_1$ and $x^*$ are.

3. End of Section 1: A topic that might arouse more interest in the paper early on is a discussion on the choice of $m$ (which is discussed later, starting on line 211). Hence, it would be helpful to add 1-2 sentences at the end of Section 1 to say that this is a topic that will be discussed later in the paper.

4. The choice of $\mu$ in Theorem 2 does not seem to be immediately implementable, since it relies on $\lambda_{m+1},\ldots,\lambda_{n}$. However, equation (13) later on gives a tractable form for $\mu$. Perhaps a remark in (or after) the Theorem should be made to direct the reader to (13).

5. Line 197: "...if with imperfect initialization." Missing word?

6. Line 183: Return <- Returning

7. Line 289: "The rest of the parameter..." <- "The remaining parameter..."

8. The words "Krylov" and "Krylob" are used interchangeably throughout. I would suggest picking only one of these spellings.
limitations: The authors have sufficiently addressed all limitations (assumptions) in this paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The well-known cubic regularization of Newton's method proposed by Nesterov (2006) requires solving a "cubic subproblem" at each iteration:
$
\min_{\mathbf{x} \in \mathbb{R}^{n}} =\mathbf{b}^{\mathrm{T}} \mathbf{x}+\frac{1}{2} \mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}+\frac{\rho}{3}\|\mathbf{x}\|^{3}.
$ 
The cubic subproblem is equivalent to solving a "secular equation", which is a nonlinear equation that depends explicitly on the eigenvalues of $A \in \mathbb{R}^{n\times n}$. Solvers for this secular equation run in $O(n^3)$.  

In this work the authors propose two "approximate" secular equations. Essentially the approximate secular equations are obtained by setting a parameter $m$ and replace all eigenvalues larger than $\lambda_m(A)$ in the secular equation with a constant $\mu\geq \lambda_m(A)$.  The advantage is that now we only need to compute the first $m$ eigenvalues of $A$, reducing the computational cost to $O(mn^2)$. The authors provide error analysis on the difference between the exact solution of the secular equation and the approximate solution. Furthermore, they provide numerical experiments to gauge the error of the approximate secular equation in a number of different scenarios. It is observed that the error depends on the distribution of the eigenvalues of $A$. 
strengths_and_weaknesses: ### Strengths
The ability to solve cubic subproblems efficiently is very important for the success of cubic regularization. The idea of solving an approximate cubic subproblem instead of an exact one can be useful in specific cases where the large eigenvalues of $A$ is concentrated in a small interval. The error bounds in this paper also become tighter in this regime. 

### Weaknesses
- The main contribution of this paper is proposing two approximate secular equations and analyzing their errors. However, both the proposed equations and the error analysis are quite obvious and unsurprising. It basically boils down to the following idea: in the equation
$
w(\sigma)=\sum_{i=1}^{n} \frac{c_{i}^{2}}{\left(\lambda_{i}+\sigma\right)^{2}}-\frac{\sigma^{2}}{\rho^{2}} = 0,
$
we can pick an index $m$ and replace all eigenvalues greater or equal to $\lambda_m(A)$ with a constant $\mu$, resulting in an approximate equation. The larger $m$ is, the smaller the approximation error. When $m=n$, the method is exact. The error analysis is also based on this idea. The overall theoretical contribution is weak because the tradeoff between $m$ and the accuracy is quite obvious. It is also clear that the resulting error will depend on $m$, $\mu$ and the distribution of the eigenvalues. Using a small $m$, of course, will increase the error and reduce the running time, which is the gist of this paper. 
- The motivation for this work is that the approximate secular equations can be used to solve the cubic subproblem, resulting in more efficient iterates for cubic regularization of Newton's method. However the experimental section does not contain such an experiment where an actual optimization problem is solved with cubic regularization and the running time is compared with other methods for solving the cubic subproblem, either exactly or approximately. 
- In the end, there is neither a theoretical proof nor a convincing experimental section that demonstrate the advantage of the proposed method when it is actually used in cubic regularization. 

questions: The paper is clear and easy to understand. My only question is how does the approximate solver work in practice when used in cubic regularization? If the authors can implement their method and compared to state of art algorithms such as Carmon and Duchi 2018, or Cartis et al. 2011 and demonstrate a clear advantage, I would consider increasing my overall evaluation. 
limitations: Yes. There is no direct negative societal impact.
review_title: null

Meta-review: metareview: This paper proposes a new method for solving the cubic subproblem in the cubic regularized Newton method. The propose method is simple, but works very well in practice. The numerical experiments demonstrated that the ARC algorithm combined with the proposed new subproblem solver significantly outperforms ARC with different subproblem solvers. Moreover, the accuracy of the solution generated by the proposed method can be several orders better than the one generated by other methods. Error analysis of the proposed method is also provided. Overall, this is a very nice contribution to the cubic regularized Newton method, which has the potential to accelerate this important method. 
confidence: Certain
Decision: Accept