Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel fast exact subproblem solver for stochastic Quasi-Newton cubic regularized optimization.
The solver can much reduce the computation cost and is easy to implement.
I believe this method has potential applications in non-convex optimization.
strength_and_weaknesses: The solver proposed in this paper can much reduce the computation cost and is easy to implement.
I believe this method has potential applications in non-convex optimization.
clarity,_quality,_novelty_and_reproducibility: It is easy to read to paper.
The idea is new.
summary_of_the_review: The solver proposed in this paper can much reduce the computation cost and is easy to implement.
I believe this method has potential applications in non-convex optimization.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work studies using L-BFGS method to solve the cubic subproblem in the second-order optimization. The authors provide theoretical analysis to suggest their method converges. Experiment results show their algorithm is empirically better than existing approaches. 
strength_and_weaknesses: Pros:

- The algorithm design is clear.

Cons:

- This work may lack importance. Although making an efficient cubic-subproblem solver is a very important task in second-order optimization research, the main contribution of this work seems only to be providing an efficient implementation of solving a Newton method by adapting the low-rank structure, which does not contribute a lot of new knowledge to the optimization community. 

- The presentation of this paper is very confusing. For instance, 

-- Page 5, the authors keep mentioning matrices $S$ and $Y$. What are their definitions? 

-- Page 5, the matrix $\Phi$ is defined in (10), which serves as one component from the decomposition of $B$. However, later in Assumption 1, the authors mention 'replace columns in $\Phi$), which confuses me since $\Phi$ should be some fixed matrix. 

- I suggest the authors compare their L-BFGS algorithms with some Krylov subspace-based algorithms for solving the cubic subproblems, such as [1]. It is interesting to see how their computational complexity differs from each other, given the fact that the approximate Krylov subspace-based algorithms actually perform very well in practice.

[1] Kohler, Jonas Moritz, and Aurelien Lucchi. "Sub-sampled cubic regularization for non-convex optimization." International Conference on Machine Learning. PMLR, 2017.

- The experiments need more demonstration. For instance, 

-- In Table 3, I do not understand why SGD achieves the highest cost, compared with other algorithms. Are they supposed to run the same 25 epochs? If so, it is strange because SGD should enjoy the lowest cost since any other algorithms need additional computation besides the computation of gradients.



clarity,_quality,_novelty_and_reproducibility: The novelty of this work is limited since it provides nothing new but efficient implementation of an existing algorithm. 
summary_of_the_review: This paper studies how to efficiently solve the cubic sub-problem given the limited-memory limit. However, the contribution of this work is somehow limited, and its presentation also needs to be further improved. Thus I recommend a reject to this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors provide to their knowledge the first matrix-free Newton's method in reduced subspace to obtain exact solution of cubic-regularization (CR), which is much faster than the previous CR solvers. Then, the previous ARC algorithm is expanded to ARCLQN algorithm using LQN matrices, to incorporate SGD and the proposed exact cubic-regularization solver. ARCLQN is proved to converge to stationary point and empirically demonstrated more efficient than existing CR-based algorithms.
strength_and_weaknesses: Pros: The ideas of matrix-free exact CR solver and incorporating SGD when the update of $B_k~$fails look novel. Lit review looks very comprehensive. Experimental results look good. 

Cons: There is lack of clarity, non-asymptotic convergence rate results and objective functions for experiments, as listed in "Clarity, Quality, Novelty And Reproducibility". 
clarity,_quality,_novelty_and_reproducibility: Clarity: Many details need to be clarified. I list the ones I found as follows. 

(1) (My major concern) It is still hard for readers to find out how to update $||\hat{g}_1||$ and $\hat{g}_2$ incrementally, and hard to see the whole procedure of the proposed exact cubic solver. I suggest to add an algorithm box either in main text or appendix to list all procedures of the proposed exact cubic solver, including the formulas for updating $||\hat{g}_1||$ and $\hat{g}_2$ incrementally. 

(2) You could explain "ARCLQN" at its first appearance at the beginning of Section 3. For instance, "ARCLQN (Algorithm 3)".

(3) If convenient, right after eq. (11), you could write the definition of $\hat{\Lambda}$ or roughly how it is obtained. 

(4) What are the sizes of $U_1$ and $U_2$ in eq. (12)? You could write them.

(5) Is $\hat{\Lambda}=\text{diag}(\hat{\lambda}_1,\ldots,\hat{\lambda}_m)$ correct? If yes, then you could mention that, and it seems that $k=m$ as $\hat{\Lambda}\in\mathbb{R}^{k\times k}$, yes? 

(6) Does Algorithm 1 give the exact solution to the CR problem (1) within finitely many iterations? If yes, you could mention that and give iteration complexity.  

(6) In step 4 of Algorithm 2, do we randomly select $\sigma_{k+1}$ in the correct interval? 

(7) What equations are used to update $B_k$ in lines 12 and 20 of Algorithm 3? 

(8) What does hard case mean in Table 1? 

(9) What is the function $H$ in Assumptions 6 and 9 in Appendix E? Make sure every new terminologies and notations are defined upon their first appearance.

(10) In Theorem 2 in Appendix D, the generalized eigenvalue problem seems could be written as $MV=\Lambda TV$ to obtain $(V,\Lambda)$. Also, what is $\overline{u}$? 

Quality: The claimed advantages of the proposed CR solver and ARCLQN algorithm look strong, but are not well supported due to the following reasons. 

(1) (My another major concern) It seems that the authors claim Algorithm 1 to give exact CR solution, while Theorem 5 only converges to the exact solution. Could you explain that? Also non-asymptotic convergence rates or computation/sample complexity of Algorithms 1 and 3 are lacking, which have been obtained in previous cubic-regularization works. Therefore, the claimed higher efficiency of Algorithms 1 and 3 are not well supported unless faster convergence rate or computation/sample complexity can be proved. 

(2) Assumption 8 implies that the objective function $f$ is Lipschitz continuous, which is rarely satisfied in many applications. Even quadratic function is not Lipschitz continuous. 

(3) At the end of Section 2, the 4th item of "Our Contributions" could mention the advantage of the proposed ARCLQN demonstrated by the experiments. 

Novelty: The ideas of matrix-free exact CR solver and incorporating SGD when the update of $B_k$ fails look novel. 

Reproducibility: In the experiments, objective functions and some other hyperparameter choices such as $\sigma_0$, $\epsilon$, $\delta$, etc. could be provided to ensure reproducibility. 

Minor comments: 

(1) In Section 2, "Ranganath et al. (2022) solve a modified version", use "solves". There are other similar typos. 

(2) Use $y_k, s_k$ instead of $y, s$ right after eq. (2). 

(3) Change "remain" to remains and "paperd" to "paper" right after eq. (3). 

(4) At the end of Theorem 1, should $g$ and $B$ be $g_k$ and $B_k$ respectively?

(5) In Algorithm 1, you could use "solve $-\lambda_1=\sigma\|s(-\lambda_1)+\alpha u_1\|$ to obtain $\alpha$" so that we know which variable to get. Similarly for eq. (7). 

(6) Should $\alpha_1 s$ be $\alpha_1 s_k^*$ in line 12 of Algorithm 3? Also, "update and" seems could be removed. 

(7) In the first line of Algorithm 2, $\gamma_2>\gamma_1>1$, yes?
summary_of_the_review: Based on "Strength And Weaknesses" above, I currently recommend borderline reject for this paper. If the authors can solve the above listed problems, especially my two major concerns (item 1 of clarity and quality), I would like to raise my rating.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work mainly proposes a method to solve the subproblems of the cubic regularized Quasi-Newton method, where L-BFGS method is used to approximate Hessian matrix.  A few related asymptotic convergence results are provided to support the method. 

From the reviewers, the main complaint is that the novelty of this paper does not meet the standard of ICLR. That is, the paper only focuses on a very specific aspect of the CRN method. The paper describes a way to make the CRN subproblem with L-BFGS style approximate Hessian matrix. More specifically, using L-BFGS style Hessian approximation is also known, the authors only propose a way to make update for the subproblem. 

Another issue is that, due to the use of inexact Hessian matrix, the $const\cdot\|x_k-x_{k+1}\|^3$ sufficient descent of the original CRN method is missing. In order to guarantee the convergence, an EXACT function evaluation is needed to certify descent, see Eqn. (17). This is OK for deterministic optimization. However, this is fatal for the stochastic case. Evaluating the function and certifying a sufficient descent exactly is very hard for stochastic optimization. When we look at the neural network ERM example considered in this paper, making a function evaluation (forward pass) is already half the cost of the full gradient evaluation (backward pass). This makes the stochastic sampling meaningless. 

Moreover, the theoretical contribution is also weak, only asymptotic convergence is obtained.
Decision: Reject