Dear Reviewer RYzW,
Thank you so much for your positive feedback and thoughtful suggestions! We sincerely appreciate your recognition and support. We are glad to hear that our clarifications are very helpful. We will add our clarifications above in the writing to make our paper clearer. We would like to address your remaining concerns below.
---
### Questions #2
We totally agree with you that sample averaging applied to standard SGD can achieve similar complexity as our OptEx, without the overhead of managing the GP. As we have justified above, these two speedup approaches stem from different principles:
- OptEx Speedup: This comes from reduced sequential iterations (first term on the RHS in Equation 45).
- Sample Averaging Speedup: This is derived from reduced gradient variance (second term on the RHS in Equation 45).
So, when gradient noise $\sigma$ is already decreased to a small value through sample averaging with parallelism $N'$ (not $N$), increasing $N'$ further (i.e., $N'+N$) provides diminishing returns due to the sublinear rate of $O(1/\sqrt{N'+N})$. For example, the benefit of reducing from $1/\sqrt{10}$ to $1/\sqrt{15}$ is less significant compared to reducing from $1/\sqrt{1}$ to $1/\sqrt{6}$ with an additional parallelism $N=5$.
However, in this scenario of a small gradient noise $\sigma$, our OptEx can still achieve noticeable speedup (e.g., from $1/\sqrt{1}$ to $1/\sqrt{6}$ with the same additional parallelism $N=5$) by leveraging additional parallel computing to reduce the sequential iterations. This reduction in sequential iterations is however unattainable by mini-batch SGD itself.
In light of this, Equation 45, leading to our Theorem 2, in fact, will provide valuable insights into when OptEx is preferable to simple sample averaging. Overall, OptEx complements rather than replaces existing parallelization methods, including sample averaging, to accelerate first-order optimization. This is particularly effective when other methods are **inapplicable** or **underperforming**, i.e., further noticeable improvements cannot be achieved merely by increasing parallel computing resources in those methods, as we have justified above.
### Weaknesses #2
We apologize for the confusion caused by our notation $\tau$. Our intention was to use $\tau$ to denote all gradients evaluated during the optimization process more easily, including those in parallel processes, as mentioned in line 260. In Theorems 2 and 3, the expression $\min_{\tau \leq NT} \left|\nabla F(\theta_{\tau})\right|$ is exactly meant to represent $\min_{t \leq T, s \leq N} \left|\nabla F(\theta_{t,s})\right|$. Thank you for bringing this to our attention. We will correct this notation in our revised paper.
---
We want to thank Reviewer RYzW for your positive feedback and recognition again! We sincerely hope our response has addressed your remaining concerns and can increase your opinions of our work. If you have any other questions, we would like to address them.
Sincerely, Authors