Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness

We appreciate your valuable input and considerate questions!

Weakness 1 : “ Though the text has a good flow in terms of the context, there is still room for improvements: e.g. (a) In page 2 there are two loose sentences in the middle of the page. They can be integrated with the previous paragraph or just in a new independent paragraph; (b) Below assumption 1.2: E[g(x,ξ)] or E[F(x,ξ)]; (c) \citet was used wrongly in many places. Please consider replacing the wrong ones with \citep; (d) function ψt(x) above algorithm 1 is not defined (I think it is in the algorithm so you should refer to that or simply introduce it); (e) The definition of f in section 7 page 8 is an abuse of notation: f(x)=E[f(x,ξ)]; (f) I suggest larger font size on Figures 1,2; (g) Large gap in the appendix after (26); ”

Response: Thank you for suggestions and pointing out several inaccuracies. We agree with comments (a, c, d, e, f , g) and will change it in the revised version. Regarding comment (b), we maintain the expression "E[g(x,ξ)]" exactly as it is below Assumption 1.2

Weakness 2: "I think contributions 3 & 1 should be integrated."

Response: Contribution 1 signifies an enhanced convergence rate, whereas Contribution 3 underscores the successful integration of an inexact subproblem solution—a novel aspect not previously addressed in inexact second-order and high-order convex methods. We appreciate your thoughtful input and will consider how best to integrate these contributions for an improved presentation of our research.

Weakness 3: "Table 1 might lead to misunderstanding. Your result is based on the asssumption of unbiased gradients. The rate by Agafonov does not have this assumption. Thus, it seems like an unfair comparison."

Response: Certainly, we acknowledge that a direct comparison of the convergence of these methods is not feasible, as elucidated in the paragraph following Assumption 2.3. To provide a comprehensive overview of the current landscape in the realm of inexact/stochastic second-order methods, we present Table 1. This table includes a column outlining assumptions related to inexactness, explicitly noting that the unbiasedness of the gradient was not assumed in the work [1]. We believe that Table 1's clear articulation of assumptions minimizes any potential misunderstandings regarding the comparative context.

Weakness 4: "The title of the section “Lower Bound” is very generic and also the description is vague. For example, the first sentence of this section is vague."

Response: Could you kindly offer additional insights on why the title and the first sentence might be considered vague? We value your perspective and would appreciate any suggestions you may have for improvement. While the current wording seems acceptable to us, we are open to refining it based on your feedback. Thank you.

Question 1: " Is the $\Phi_x$ defined at the beginning of Section 2 used? Same question holds for $\Phi_x$ defined under Assumption 5.1."

Response: Formally, its utilization is confined to the Appendix. Nevertheless, we believe it is crucial to introduce the exact Taylor polynomial $\Phi_x(y)$, as it provides valuable insights into the construction of high-order methods.

Question 2: "Lemma 2.1 seems like a special case of a similar lemma in Agafonov et al 2020. Is there a reason you did not cite their work when you present the Lemma? Same question holds for Lemma 5.2."

Response: Thank you, we agree with your comment, and we will add a direct citation near Lemmas 2.1 and 5.1 in revised version.

Question 3: "How did you find the dynamic strategy for the precision level $\tau_t = c / t^{3/2}$?"

Response: Thank you for this question. We have a typo here, it should be $\tau = \frac{c}{t^{5/2}}$, we will fill it in the revised version.

From the convergence, we have for any $t \geq 1$

$f(x_{t}) - f(x^*) \leq O(\frac{\sigma_1 R}{\sqrt{t}} + \frac{\sigma_2 R^2}{t^2} + \frac{L_2 R^3}{t^3} + \frac{\sigma_1 R}{\sqrt{t}})$

By choosing $\tau = \frac{c}{t^{5/2}}$, we get for any $t \geq 1$

$f(x_{t}) - f(x^*) \leq O(\frac{\sigma_1 R}{\sqrt{t}} + \frac{\sigma_2 R^2}{t^2} + \frac{L_2 R^3}{t^3} + \frac{c R}{t^3})$

References

[1] Agafonov, Artem, et al. "Inexact tensor methods and their application to stochastic convex optimization." arXiv preprint arXiv:2012.15636 (2020)."*

Thank you for your helpful feedback and thoughtful inquiries!

Question 1: “The paper lacks an intuitive explanation of the proposed algorithm. It is suggested to explain the motivation and impact of parameters such as αt, the choice of the model $\omega_{x, M}^{\bar \delta}$ and the technique of estimating sequence on the algorithm's performance and convergence.”

Response: Kindly examine the common commentary titled "On intuition behind the algorithm."

Question 2: “When comparing computational time, is the proposed algorithm better than existing methods?”

Response: In computational time comparisons, the efficiency is often contingent on the implementation rather than solely on the algorithms themselves. The relative speed of the proposed algorithm compared to existing methods can vary depending on the specific implementation and the characteristics of the minimization problem. To ensure a fair evaluation, we have presented our results in terms of iteration complexity.

When comparing our implementations of SGD, ExtraNewton (EN), and Accelerated Stochastic Cubic Newton (ASCN), all implemented using PyTorch 2.0, in terms of computation time, we observe a slight advantage of ASCN over EN. Notably, both ASCN and EN outperform SGD in scenarios with small Hessian batch sizes ranging from 150 to 1000. We are open to incorporating these additional experiments into the revised version of the paper.

Question 3: “The figures in the paper are too small, making it difficult for readers to interpret the results.”

Response: Thank you for your feedback regarding the figures in our paper. We acknowledge your concern about their size impacting the ease of interpretation for readers. In the revised version, we will try to address this by resizing the figures for better visibility and comprehension. However, it's essential to note that we are constrained to 9 pages, and any adjustments to figure sizes may necessitate the removal of other elements from the work to maintain brevity. Alternatively, we are open to adding figures from Section 7 to the Appendix, presenting them with increased size as shown in Figures 3 and 4. Your further suggestions on this ma tter are appreciated.

Dear Reviewer 2pJU,

We have submitted a revised version of our work. In this iteration, we have made several enhancements to address your feedback.

Firstly, we have included running time experiments in Appendix C (Figures 7 and 8). Our findings indicate that. in a setup with a gradient batch size of 10,000, and Hessian batch sizes of 150 and 450, Accelerated Stochastic Cubic Newton outperforms both Extra-Newton and SGD.

Additionally, we have increased the font size for Figures 1 and 2. To provide further clarity and accessibility, we have added a larger version of these graphics to Appendix C (Figures 5 and 6).

Furthermore, we have included a discussion on the intuition behind our method to Appendix B.

We appreciate your valuable insights. Thank you for your time and consideration.

Weaknesses : "The algorithm of step 4 also includes another optimization problem."

Questions: "How does the algorithm work in step 4 of the proposed algorithm? Does it work in practice?"

The subproblem in line 4 of Algorithm 1 admits a closed form solution, so it cannot be considered as a separate optimization problem. We apologize for not presenting it explicitly in the paper. Allow us to rectify that here.

First, note that the problem in line 4 is convex. Let us write optimality condition $0 = \nabla \psi_t(y_t) = (\lambda_{t} + \kappa_2^{t} + \kappa_3^{t} ||y_{t} - x_0||)(y_{t} - x_0) + \sum \limits_{j=0}^{t-1} \frac{\alpha_j}{A_j} g(x_{j+1}).$ Thus, $(\lambda_{t} + \kappa_2^{t} + \kappa_3^{t} ||y_{t} - x_0||)||y_{t} - x_0|| = || \sum \limits_{j=0}^{t-1}\frac{\alpha_j}{A_j} g(x_{j+1})||.$ Let us denote $r_{t} = ||y_{t} - x_0||$ and $S_t = || \sum \limits_{j=0}^{t-1}\frac{\alpha_j}{A_j} g(x_{j+1})||$. Then, we get $\kappa_3^{t} r_{t}^2 + (\lambda_{t} + \kappa_2^{t})r_{t} - S_t = 0.$ Next, we get the solution of quadratic equation $r_{t} = \frac{\sqrt{(\lambda_{t} + \kappa_2^{t})^2 + 4 \kappa_3^{t}S_t } - (\lambda_{t} + \kappa_2^{t} )}{2\kappa_3^{t}}.$ Finally, we get explicit solution

$y_{t} = x_0 - \frac{\sum \limits_{j=0}^{t-1}\frac{\alpha_j}{A_j} g(x_{j+1}) }{\lambda_t + \bar{\kappa}_2^t + \bar{\kappa}_3^t r_t}.$

We will add this derivation to the revised version of the paper.

Furthermore, we would like to point out that solving minimization subproblems are in the heart of algorithm design. For example, even the iconic gradient descent scheme stems directly from minimizing quadratically regularized 1st order Taylor approximation sub-problem: $x_{k+1} = \arg \min_x (f(x_k) + \langle \nabla f(x_k), x- x_k\rangle + \frac{1}{2\gamma}||x - x_k||^2).$ Gradient descent allows for closed form solution as a subproblem in line 4 in Algorithm 1 . Subproblems like line 4 in Algorithm 1 naturally arise from acceleration techniques. See line 1 of (4.8) from [1], lines 6-7 of Algorithm 1 from [2]. Furthermore, the absence of a closed-form solution for a subproblem should not be viewed as a deterrent when considering a specific optimization method, such as Mirror-Prox [3], Frank-Wolfe methods [4, 5], or Trust-Region methods [5].

Practical performance

As we have established, the practical performance of subproblem 4 is not an issue. We use the explicit solution in our implementation of the algorithm. We provide numerical evidence for the overall algorithm in section 7. The proposed method works well in practice, one can see the behavior on Figures 1, 2.

Having outlined the specifics of the subproblem in line 4 of Algorithm 1 along with its explicit solution, we wonder whether this might be the reason for the pronounced strong rejection.

[1] Nesterov, Yu. "Accelerating the cubic regularization of Newton’s method on convex problems." Mathematical Programming 112.1 (2008): 159-181.

[2] Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent." arXiv preprint arXiv:1407.1537 (2014).

[3] Nemirovskij, Arkadij Semenovič, and David Borisovich Yudin. "Problem complexity and method efficiency in optimization." (1983).

[4] Jaggi, Martin. "Revisiting Frank-Wolfe: Projection-free sparse convex optimization." International conference on machine learning. PMLR, 2013.

[5] Nocedal, Jorge, and Stephen J. Wright, eds. Numerical optimization. New York, NY: Springer New York, 1999.

Thank you for your insightful feedback and valuable questions!

Weakness 1: “While I grasp the overarching concept of the algorithm and the principal steps in the proof, the exposition doesn't offer much in the way of intuitive understanding. Could the authors elucidate the rationale behind the algorithm's design and the parameter choices? Enhancing the exposition with additional intuitive insights into the algorithm would be highly beneficial.”

Response: Please review the common commentary “On the intuition behind the algorithm”.

Weakness 2: “The assumptions (2.2 and 2.3) of stochacity and inexactness differ but seem highly related, as they lead to two quite similar convergence rates and proof for your algorithm. In this paper the way of discussing the stochasticity and inexactness settings seems a bit nesting. Maybe it could be better if their highlevel relations are set forth in a proper manner.”

Response: We appreciate your observation regarding the nesting of Assumptions (2.2 and 2.3) and their apparent similarities in leading to analogous convergence rates and proof for our algorithms. While we recognize their close relationship, it's crucial to emphasize a fundamental distinction between the two. Assumption 2.2 imposes a bound on the expected norm of the difference between the Hessian and the stochastic Hessian, whereas Assumption 2.3 pertains to the difference along the direction $y - x$. Consequently, 2.3 is necessary only for iterations of the Algorithm, and the value of $\delta_2^{x, y}$ can be significantly smaller than the norm of the difference between the Hessian and its approximation. This delineation underscores why we present both assumptions and provide separate theoretical results for each. If you believe that presenting both assumptions is unnecessary, we welcome further discussion on this matter.

Weakness 3: “Clarification: O(1/T^2) ->\Omega(1/T^2) in P2 line 2; bounded variance stochastic Hessian ->stochastic Hessian with bounded variance; formatting issues such as sequence numbers in the algorithm list.”

Response: Thank you for bringing that to our attention; we will make the necessary changes to the paper in the revised version.

Question 1: “In section 3, the subproblem you defined is $ω_{x, M}^{\bar δ}(y)=f(x)+⟨g(x),y−x⟩+\frac{1}{2}⟨y−x,H(x)(y−x)⟩+\frac{\bar δ}{2}‖x−y‖^2+\frac{M}{6}‖x−y‖^3$. Compared to the original cubic regularized subproblem, in addition to the modification of the inexactness and stochasticity, your formulation has an additional quadratic term $\frac{\bar \delta}{2}‖x−y‖^2$. Are there any reason or intuition for this term?.”

Response: Please have a look at the part A of common commentary “On the intuition behind the algorithm”.

Question 2: “Could you bring more insights for the aggregation of stochastic linear models above algorithm 1?”

Response: Please have a look at the part B of common commentary “On the intuition behind the algorithm”.

Question 3: “The gloabal convergent (accelerated, cubic newton type) second-order methods, while they have accelerated global convergence, they usually can be proven to have superlinear local convergence rate. Is the parallel local characteristic worth to be mentioned and investigated in your stochastic/inexact setting?”

Response: Thank you for your insightful commentary.

While local convergence seems to be an interesting theoretical direction, it lies beyond the scope of this paper, which primarily concentrates on global convergence without assumptions on initial point. Local convergence normally requires some very restrictive assumptions on starting point and batch size (gradient accuracy) which are hard to satisfy in practice.

Illustratively, consider the local superlinear convergence from [1], which requires $f(x_0) - f(x^*) \leq \frac{\mu^3}{L_2^2}$. In most practical scenarios desired accuracy $\varepsilon \lesssim \frac{\mu^3}{L_2^2}$.

In summary, while the local convergence of stochastic/inexact accelerated second-order/high-order methods remains an open question, we believe that exploring this aspect may not make the proposed scheme much more practical. Consequently, we maintain our focus on global performance within the defined scope of this work.

Question 4: “The open question mentioned, "what's the optimal trade-off between inexactness in gradients and the Hessian?", where in the article is intuitively investigated? ”

Response: We establish the lower bound $\Omega(\frac{\sigma_1 R}{\sqrt{T}} + \frac{\sigma_2 R^2}{T^2} + \frac{L_2 R^{3}}{T^{7/2}})$, which shows that the best possible tradeoff between inexactness is $\Omega(\frac{\sigma_1 R}{\sqrt{T}} + \frac{\sigma_2 R^2}{T^2})$, which is achieved by proposed algorithm.

[1] Kovalev, Dmitry, Konstantin Mishchenko, and Peter Richtárik. "Stochastic Newton and cubic Newton methods with simple local linear-quadratic rates." arXiv preprint arXiv:1912.01597 (2019).