In practical distributed systems, workers are typically not homogeneous, and due to differences in hardware configurations and network conditions, can have highly varying processing times. We consider smooth nonconvex finite-sum (empirical risk minimization) problems in this setup and introduce a new parallel method, Freya PAGE, designed to handle arbitrarily heterogeneous and asynchronous computations. By being robust to "stragglers" and adaptively ignoring slow computations, Freya PAGE offers significantly improved time complexity guarantees compared to all previous methods, including Asynchronous SGD, Rennala SGD, SPIDER, and PAGE, while requiring weaker assumptions. The algorithm relies on novel generic stochastic gradient collection strategies with theoretical guarantees that can be of interest on their own, and may be used in the design of future optimization methods. Furthermore, we establish a lower bound for smooth nonconvex finite-sum problems in the asynchronous setup, providing a fundamental time complexity limit. This lower bound is tight and demonstrates the optimality of Freya PAGE in the large-scale regime, i.e., when $\sqrt{m} \geq n$, where $n$ is # of workers, and $m$ is # of data samples.

该研究论文介绍了一种名为Freya PAGE的新的并行方法，用于处理异构和异步计算情况下的非凸有限和问题，该方法具有较强的鲁棒性，通过忽略慢速计算和对付异常值，相比之前的方法包括异步SGD、Rennala SGD、SPIDER和PAGE，具有显著改善的时间复杂度保证。它还提供了一种新颖的随机梯度收集策略，并建立了异步设置下平滑非凸有限和问题的时间复杂性下界，证明了Freya PAGE在大规模情况下的最优性。

Freya PAGE: 大规模非凸有限和优化中的首个最优时间复杂性与异步计算的异构