Official Comment by Authors
Thank you for the question.
Indeed, in Line 304, we say that Freya SGD is closely related to Rennala SGD [1]. We consider Freya SGD to get the time complexity of the finite-sum optimization with a *non-variance reduced method.* Why is it important? First, such a method can be crucial and has a better convergence rate in the interpolation regime [2,3]. Second, while the dependence of Freya SGD on $\varepsilon$ is worse compared to Freya PAGE, the former method does not *explicitly* depend on $m$ (compare (10) vs the last formula in Theorem 25), which can be beneficial in some regimes. In total, Freya SGD provides a new time complexity that was not considered in the literature, which we believe is important for future work and for a general understanding of asynchronous methods.
Let us explain the main differences between Freya SGD and Rennala SGD. The time complexity of Freya SGD is equal to
$$\frac{\delta^0 L_-}{\varepsilon} \min_{j \in [n]} \left(\left(\sum_{i=1}^j \frac{1}{\tau_i}\right)^{-1} \left(\frac{L_{\max}}{\varepsilon} \left(\delta^0 + \Delta^*\right) + j \right)\right).$$
Unlike Rennala SGD, this complexity does not depend on the noise $\sigma^2$ of stochastic gradients, which is a major advantage of Freya SGD. Another important difference between Rennala SGD and Freya SGD is the choice of the number of stochastic gradients that methods calculate in every iteration. In [1], the authors choose $S \approx \frac{\sigma^2}{\varepsilon},$ while we prove that the optimal choice of $S$ that minimizes the upper bound in Theorem 25 is $\approx \frac{L_{\max}}{\varepsilon} \left(\delta^0 + \Delta^*\right).$ Moreover, the convergence rate of Rennala SGD relies on the theory from [4], while Freya SGD uses the analysis with a different proof technique from [5].
Beyond the main contributions related to Freya PAGE and the lower bound, we think that the analysis of Freya SGD is the cherry on top, offering deeper insights into time complexities in the finite-sum setting with heterogeneous asynchronous computations.
We hope we have answered the question. If you need more information, we'd be happy to provide further details.
[1] Tyurin and Richtárik, “Optimal Time Complexities of Parallel Stochastic Optimization Methods under a Fixed Computation Model”, in NeurIPS 2023.
[2] M. Schmidt and N. L. Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370, 2013.
[3] S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern overparametrized learning. In International Conference on Machine Learning, pages 3325–3334. PMLR, 2018.
[4] Ghadimi, S. and Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368.
[5] A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2022.