MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times

1. The proposed method seems theoretically intuitive but may have practical limitations. Algorithm 1 and Algorithm 2 look more like an experiment setup instead of a true practical algorithm. For example, distribution of $\eta_i$ and thus also $p_i$ are hard to evaluate in practice. Compared to ASGD and Rennala SGD, Algorithm 1 involves more parameters such as $B_i, p_i$ that users need to decide on. Experiments are carried out where $\eta_i$ is of certain ideal theoretic distribution, which is rarely encountered in practice. Therefore, empirically estimation of good choices of $B_i, p_i$ and even $\mathcal{J}_i$ remain a problem.

To address these concerns, we have included a new section titled "Simplifying MindFlayer for Practical Use" in the appendix, which introduces Mod MindFlayer SGD, a more practical variant. This simplified version reduces the reliance on precise distribution knowledge by replacing $t_i$​ with the inverse cumulative distribution function (CDF) at a probabilistic threshold $p$. The parameter $t_i$​ can be estimated using historical data or dynamically updated via the Robbins-Monro stochastic approximation, making the approach feasible even when exact distributions are unavailable. Additionally, global parameters $p$ and $B$ replace per-worker parameters $t_i$​ and $B_i$​, significantly reducing the tuning burden for users.

While the original algorithms aim to provide theoretical insights, Mod MindFlayer SGD bridges the gap between theory and practice, addressing concerns about parameter estimation and real-world applicability without sacrificing performance, as demonstrated by our empirical results.

2. The setting being considered is interesting but may rise other practical issues. For example, the proposed method chooses to initialize another query whenever the current gradient computation takes too lone (quantified by >t), I feel this would significantly increase number of communication rounds between server and workers compared to baseline ASGD and Rennala SGD, which may form bottleneck in certain settings.

It depends on how the method is implemented. The most efficient approach would be to avoid adding extra communication steps by sending the value of tit_iti​ to each worker at the start. Since each worker knows the time they are allotted to compute a gradient, they can restart the computation themselves if it takes too long, without needing to communicate with the server.

Even if communication were necessary, it could be as minimal as a single bit of information, making it unlikely to form a significant bottleneck.

3. Figure 3 is hard to read, legends should be added to demonstrate what are dashed green line/ dotted purple line/ solid yellow line/ shaded grey region. The title includes no such information as well.

Sorry about that, a figure with a legend is included in the revision.

---

Thank you for pointing out the typos, they have been addressed in the revision.

Implicit Assumption of Utilizing Privileged Information in Algorithm Design. In the real world, the distributions of compute time for different works are usually unknown. The proposed algorithms implicitly leverage this information to get the expected batch size $B$. I am not sure if this is required in the proof. The paper fails to discuss this limitation and provide a workaround without using information $p_i$

We acknowledge the implicit assumption of leveraging privileged information, such as worker compute time distributions, in the proposed algorithms. To address this, we added a section titled "Simplifying MindFlayer for Practical Use" in the appendix, introducing Mod MindFlayer SGD, which reduces reliance on precise distribution knowledge.

Mod MindFlayer SGD replaces $t_i$​ with the inverse cumulative distribution function (CDF) at a probabilistic threshold $p$, estimated using historical data or online updates via the Robbins-Monro stochastic approximation. This reformulation simplifies implementation by dynamically adapting $t_i$​​ based on observed compute times, aligning it with the desired reliability $p$.

Experimental results show that Mod MindFlayer SGD achieves comparable performance to the original algorithm while addressing this limitation and enhancing practicality for real-world scenarios.

1. As described in Algortihms 1 and 2, a client needs to wait for other clients even after completing all of its trials, and each server’s update (Algorithm 1 Line 12) must aggregates gradients from all clients. Given these characteristics, MindFlayer SGD seems to function more like a synchronous algorithm rather than an asynchronous one.

You are right; our algorithm is not fully asynchronous but instead partially synchronous, as each client performs a varying number of gradient steps. This isn't a drawback—in fact, it's an advantage. Just like the optimal Rennala algorithm in deterministic time scenarios, ours is not fully asynchronous either. We have even benchmarked it against the fully asynchronous ASGD algorithm and found that our MindFlayer algorithm performs better.

We agree that the word "asynchronous" in the title may sound confusing, and we are considering removing it during the revision.

The issue with ASGD is that its workers operate independently, completing their calculations of stochastic gradients with potentially large and unpredictable delays. They apply their results as soon as they are ready, without waiting for other workers. This approach is problematic, as it slows down convergence when the stochastic gradient is calculated based on an outdated or irrelevant point. When the computation times of workers are random, these points can become very outdated and chaotic, which only exacerbates the problem.

2. The generalized computation model modestly extends the fixed computation model used in Rennala SGD, which may not present significant technical challenges.

To the best of our knowledge, we are the first to consider this generalized computation model, where deterministic computation times are replaced with random ones. While this may appear to be a modest extension, it represents a significant technical step forward. Unlike previous work, we make no assumptions about the distributions governing this randomness, allowing for a much broader applicability of the model.

Furthermore, we developed a method that not only recovers Rennala SGD in the deterministic setting but also outperforms it in scenarios where the random computation times exhibit heavy-tailed behavior. This demonstrates the robustness and adaptability of our approach to more complex and realistic settings.

3. The impact of various hyperparameters involved in MindFlayer SGD is not deeply discussed. Particularly, the parameters $t_i$ and $B_i$ are difficult to choose in practice, which plays a central role in MindFlayer SGD and could be crucial for practitioners aiming to adapt the method to specific applications.

We have added a section titled "Simplifying MindFlayer for Practical Use" to the appendix, introducing Mod MindFlayer SGD, a streamlined variant that replaces $t_i$ and $B_i$​ with two global parameters: a probabilistic threshold $p$ and a global batch size $B$. This reformulation simplifies implementation while retaining the core principles and robustness of the original algorithm.

To facilitate $t_i$​ selection, we propose a dynamic adjustment using the Robbins-Monro stochastic approximation, aligning $t_i$​ with the desired completion probability $p$. Experimental results in the appendix demonstrate that Mod MindFlayer SGD performs comparably to the original algorithm, highlighting that this simplification preserves the essential behavior of MindFlayer SGD while making it more practical for real-world applications.

4. The experiments compare MindFlayer SGD solely with Rennala SGD and vanilla ASGD, and the test problems may be overly simple. Including comparisons with a wider array of contemporary asynchronous methods on more complex machine learning problems could enhance the argument for MindFlayer SGD's superiority.

The algorithms included in our comparisons were chosen for their theoretical significance. ASGD serves as a well-established baseline, and Rennala is optimal under fixed compute time, making them particularly relevant for evaluating MindFlayer SGD. For this reason, our analysis focuses on these algorithms to provide a clear and theoretically grounded comparison.

Major issues:

1. For the algorithm itself, the contribution of MindFlayer SGD is incremental since it's mostly based on Rennala SGD, as the authors stated in this paper by themselves: "For MindFlayer SGD, each iteration, on average, receives only Bp gradients, making it effectively a scaled-down version of Rennala SGD." (Lin 241-242)

While we acknowledge that MindFlayer SGD builds upon Rennala SGD, we respectfully emphasize that this advancement carries significant theoretical and practical implications.

First, the transition from fixed times to general random times is a substantial theoretical leap. The fact that a method, that generalizes Rennala in the fixed-time setting, performs robustly in the random-time setting highlights the strength and utility of our approach. This generalization is not merely an adaptation; it is a meaningful extension that advances the understanding of stochastic optimization under broader assumptions.

Second, science inherently progresses through incremental improvements that stand on the foundation of previous work. The true measure of a contribution lies in the value of these refinements. Our work demonstrates that even small changes to Rennala SGD can lead to significant, measurable, and theoretically grounded performance gains. Importantly, as we illustrate in Figures 1, 3, 4, and 5, any improvement factor is, in principle, possible with our method. This highlights that MindFlayer SGD can, under the right conditions, outperform Rennala SGD arbitrarily.

2. Although it is stated that MindFlayer SGD is designed for dealing with the complexities/challenges of real-world distributed learning environments and applications, the experiment settings are far from those for real-world applications (especially in 2024). The only non-convex problem used in the experiment is an extremely simple two-layer neural network on the MNSIT dataset, which is far from convincing if the authors want to show that the proposed algorithm could be used in real-world distributed training and applications. Regardless of the real-world settings, most of the experiments are on convex problems, which cannot even be used to verify the theoretical results, since the theoretical analysis is based on smooth but non-convex settings.

Our primary goal is to validate and illustrate the theoretical contributions of MindFlayer SGD, not to address specific real-world problems. The simplicity of our experimental setup is intentional and aligns with the theoretical focus of our work. Following Occam's razor, we believe that simpler experiments often provide clearer insights than unnecessarily complex setups. Our experiments are carefully designed to demonstrate the behavior of our method and its theoretical guarantees in a controlled and interpretable manner.

Conducting experiments on large-scale problems requires significant computational resources. Given the theoretical nature of this work, we see no need to simulate artificially large-scale systems. Our main contributions stand independently of such experiments.

Do you agree that our experiments effectively corroborate our theoretical findings?

3. I cannot find the hyperparameters (basically just learning rates) used in the experiments, or in what range the hyperparameters are tuned. Actually, it is known whether the baselines are fairly tuned. For example, in Figure 5, the curve of ASGD seems to be a flat line (or it simply gets worse from the very beginning). However, if the learning rate is well tuned, a small enough learning rate should make the grad norm or loss of ASGD going down even a little bit. Thus, the overall experiment settings and the hyperparameter tuning is questionable.

Thank you for your observation regarding the absence of step size details in the original submission. We apologize for this omission and appreciate your diligence in bringing it to our attention. For most of the experiments, we followed the same step size and hyperparameter tuning approach as described in the Rennala paper. This has now been clarified in the revised version of our manuscript.

Regarding the performance of ASGD, as depicted in Figure 5, the flat or worsening trend in the grad norm is an artifact of the timescale used for visualization. The scale of random times essentially stretches out the curve which explains the upward trend observed in ASGD values.

---

Minor issues:

We have resolved the issue with the algorithm numbering; please see the updated version on OpenReview.
We also acknowledge the concern that separating the experiment descriptions in the main paper from the corresponding figures in the appendix is not reader-friendly. This decision was made to save space, but we will address this issue in the camera-ready version of the paper.