We study the problem of minimizing the expectation of smooth nonconvex functions with the help of several parallel workers whose role is to compute stochastic gradients. In particular, we focus on the challenging situation where the workers' compute times are arbitrarily heterogeneous and random. In the simpler regime characterized by arbitrarily heterogeneous but deterministic compute times, Tyurin and Richt\'arik (NeurIPS 2023) recently designed the first theoretically optimal asynchronous SGD method, called Rennala SGD, in terms of a novel complexity notion called time complexity. The starting point of our work is the observation that Rennala SGD can have arbitrarily bad performance in the presence of random compute times -- a setting it was not designed to handle. To advance our understanding of stochastic optimization in this challenging regime, we propose a new asynchronous SGD method, for which we coin the name MindFlayer SGD. Our theory and empirical results demonstrate the superiority of MindFlayer SGD over existing baselines, including Rennala SGD, in cases when the noise is heavy tailed.

本研究解决了在异构和随机计算时间条件下，最小化平滑非凸函数的期望问题。我们提出了一种新的异步随机梯度下降方法MindFlayer SGD，能有效应对随机计算时间的挑战，其理论与实证结果表明MindFlayer SGD在处理重尾噪声时优于现有方法，包括Rennala SGD。

MindFlayer：异构和随机工作计算时间下高效的异步并行随机梯度下降