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

• URL: http://arxiv.org/abs/2410.04285v2
• Date: Fri, 13 Jun 2025 17:24:41 GMT
• Title: MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times
• Authors: Artavazd Maranjyan, Omar Shaikh Omar, Peter Richtárik,
• Abstract summary: We investigate the problem of minimizing the expectation of smooth non functions in a setting with multiple parallel workers that are able to compute optimal gradients.<n>A challenge in this context is the presence of arbitrarily heterogeneous and distributed compute times.<n>We introduce MindFlayer SGD, a novel parallel SGD method specifically designed to handle this gap.
• Score: 49.1574468325115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the problem of minimizing the expectation of smooth nonconvex functions in a distributed setting with multiple parallel workers that are able to compute stochastic gradients. A significant challenge in this context is the presence of arbitrarily heterogeneous and stochastic compute times among workers, which can severely degrade the performance of existing parallel stochastic gradient descent (SGD) methods. While some parallel SGD algorithms achieve optimal performance under deterministic but heterogeneous delays, their effectiveness diminishes when compute times are random - a scenario not explicitly addressed in their design. To bridge this gap, we introduce MindFlayer SGD, a novel parallel SGD method specifically designed to handle stochastic and heterogeneous compute times. Through theoretical analysis and empirical evaluation, we demonstrate that MindFlayer SGD consistently outperforms existing baselines, particularly in environments with heavy-tailed noise. Our results highlight its robustness and scalability, making it a compelling choice for large-scale distributed learning tasks.

Related papers

• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
  arXiv  Detail & Related papers  (2025-01-27T16:07:26Z)
• Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework [56.82432591933544]
  Distributed gradient descent (SGD) has attracted considerable recent attention due to its potential for scaling computational resources, reducing training time, and helping protect user privacy in machine learning. This paper presents the run time and staleness of distributed SGD based on delay differential equations (SDDEs) and the approximation of gradient arrivals. It is interestingly shown that increasing the number of activated workers does not necessarily accelerate distributed SGD due to staleness.
  arXiv  Detail & Related papers  (2024-06-17T02:56:55Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  In practical distributed systems, workers typically not homogeneous, and can have highly varying processing times. We introduce a new parallel method Freya to handle arbitrarily slow computations. We show that Freya offers significantly improved complexity guarantees compared to all previous methods.
  arXiv  Detail & Related papers  (2024-05-24T13:33:30Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  We analyze asynchronous-type algorithms for distributed SGD in the heterogeneous setting. As a by-product of our analysis, we also demonstrate guarantees for gradient-type algorithms such as SGD with random tightness.
  arXiv  Detail & Related papers  (2023-10-31T13:44:53Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  A gradient descent performed in an asynchronous manner plays a crucial role in training large-scale machine learning models. Existing generalization error bounds are rather pessimistic and cannot reveal the correlation between asynchronous delays and generalization. Our theoretical results indicate that asynchronous delays reduce the generalization error of the delayed SGD algorithm.
  arXiv  Detail & Related papers  (2023-08-18T10:00:27Z)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  We propose a novel approach to the problem of shared parallel computation. By combining two strategies into a unified framework, DPSGD is a better trade computation framework. The potential gains can be achieved by DPSGD on a deep learning (DRL) problem (Latent Diletrichal inference) and on a deep learning (DRL) problem (advantage actor - A2C)
  arXiv  Detail & Related papers  (2022-10-06T13:06:08Z)
• Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays [8.46491234455848]
  We prove much better guarantees for the same asynchronous gradient regardless of the delays in steps, depending instead just on the number of steps. For our analysis, we introduce a novel based on "virtual steps" and delay iterations, which allow us to derive state-of-the-art guarantees for both convex non-adaptive gradients.
  arXiv  Detail & Related papers  (2022-06-15T16:28:37Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Convergence Analysis of Homotopy-SGD for non-convex optimization [43.71213126039448]
  We present a first-order algorithm based on a combination of homotopy methods and SGD, called Gradienty-Stoch Descent (H-SGD) Under some assumptions, we conduct a theoretical analysis of the proposed problem. Experimental results show that H-SGD can outperform SGD.
  arXiv  Detail & Related papers  (2020-11-20T09:50:40Z)
• Slow and Stale Gradients Can Win the Race [39.750046808758526]
  Distributed Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in runtime as it waits for the slowest workers (stragglers) Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect the convergence error. We present a novel theoretical characterization of the speedup offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime.
  arXiv  Detail & Related papers  (2020-03-23T23:27:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.