# SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters

arXiv: https://arxiv.org/abs/2208.08425 · HTML: https://mlsanity.com/paper/2208.08425/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 17 Aug 2022.

## Builds on (most cited first, 17 of 17)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms](https://mlsanity.com/paper/1810.10690/) (2018)
- [Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning](https://mlsanity.com/paper/1805.09470/) (2018)
- [Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization](https://mlsanity.com/paper/1604.03584/) (2016)
- [Scalable Robust Matrix Factorization with Nonconvex Loss](https://mlsanity.com/paper/1710.07205/) (2017)

## Built on by (most cited first, 1 of 1)

- [Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations](https://mlsanity.com/paper/2405.15545/) (2024)

## Abstract (arXiv)

To increase the training speed of distributed learning, recent years have witnessed a significant amount of interest in developing both synchronous and asynchronous distributed stochastic variance-reduced optimization methods. However, all existing synchronous and asynchronous distributed training algorithms suffer from various limitations in either convergence speed or implementation complexity. This motivates us to propose an algorithm called STNTHESIS (semi-asynchronous path-integrated stochastic gradient search), which leverages the special structure of the variance-reduction framework to overcome the limitations of both synchronous and asynchronous distributed learning algorithms while retaining their salient features. We consider two implementations of STNTHESIS under distributed and shared memory architectures. We show that our STNTHESIS algorithms have O(√Nε-2(Delta+1)+N) and O(√Nε-2(Delta+1) d+N) computational complexities for achieving an ε-stationary point in non-convex learning under distributed and shared memory architectures, respectively, where N denotes the total number of training samples and Delta represents the maximum delay of the workers. Moreover, we investigate the generalization performance of algname by establishing algorithmic stability bounds for quadratic strongly convex and non-convex optimization. We further conduct extensive numerical experiments to verify our theoretical findings