We would like to thank you again for your answer. We will try to address reservations and hope our answers are satisfying.
- Regarding **(a)**, estimating $m$ is not problematic; it serves as a hyperparameter in our algorithm that we can determine using methods like grid search. In our article, we demonstrate that we can choose $m$ in a way that minimizes the total number of gradient calls. This number depends entirely on the knowledge of the count of gradients and Hessians utilized during each step. Surprisingly, this requirement only involves knowing the number of samples $n$ and the dimension $d$. To illustrate this, let's consider the case of the lazy Newton algorithm. In this scenario, we have $\delta_1=0$ and $\delta_2=L$, leading to $E[|\nabla f(x_{\text{out}})|^{3/2}]=\mathcal{O}( \frac{\sqrt{L}F_0}{S\sqrt{m}})$. To determine the optimal $m$ based on this rate, let's calculate the total number of gradient calls. It's evident that this count equals $n d S + n Sm = nS (d + m)$ because we used $S$ Hessians and $mS$ gradients. For a given precision $\varepsilon$, we have $S\sim \frac{\sqrt{L}F_0}{\varepsilon^{3/2}\sqrt{m}}$. Consequently, when minimizing $nS (d + m)$ with respect to $m$, we obtain $m=\sqrt{d}$. While this example is the simplest in the paper, the general idea is the same.
- In response to **(b)**, to underscore the practical significance of our convergence guarantees hinging on parameters $\delta_1$ and $\delta_2$, we highlight instances (as discussed in the paper) where these parameters are precisely known. To be specific, Equation (10) in the paper presents the bound $\mathcal{O}\big(\frac{\sqrt{L}F_0}{Sm} + \frac{\sqrt{\delta_2}F_0}{S\sqrt{m}} + \frac{\sqrt{\delta_1}F_0}{S}\big)$, allowing for the direct substitution of known similarity parameter values. For example, in the case of cubic Newton's method, we have $\delta_1=\delta_2=0$. For Lazy-Newton, the values are $\delta_1=0$ and $\delta_2=L$. In the context of VRCN, $\delta_1=\mathcal{O}(\frac{L}{\sqrt{b_g}})$ and $\delta_2=\mathcal{O}(\frac{L}{\sqrt{b_h}})$, while for Lazy-VRCN, $\delta_1=\mathcal{O}(\frac{L}{\sqrt{b_g}})$ and $\delta_2=0$. This consolidated formulation encompasses all of these rates within a single formula.
An insightful observation is that random batch sampling (performed in previous works), can be understood as an attempt to reduce similarity, and aligns with the objective of finding helpers with small similarities. However, it's worth noting that alternative methods might exist to achieve similar outcomes.