# Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 61 references that are in the map.
- First posted on arXiv 6 Nov 2021.

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

- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling](https://mlsanity.com/paper/1709.10432/) (2017)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization](https://mlsanity.com/paper/2006.04340/) (2020)
- [Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications](https://mlsanity.com/paper/2010.00848/) (2020)
- [Improving Deep Learning by Inverse Square Root Linear Units (ISRLUs)](https://mlsanity.com/paper/1710.09967/) (2017)
- [Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs](https://mlsanity.com/paper/2008.06082/) (2020)
- [Communication-Censored Distributed Stochastic Gradient Descent](https://mlsanity.com/paper/1909.03631/) (2019)
- [Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks](https://mlsanity.com/paper/1607.06623/) (2016)
- [Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1703.00439/) (2017)
- [Distributed Proximal Algorithms for Multi-Agent Optimization with Coupled Inequality Constraints](https://mlsanity.com/paper/1907.03245/) (2019)
- [Distributed proximal gradient algorithm for non-smooth non-convex optimization over time-varying networks](https://mlsanity.com/paper/2103.02271/) (2021)

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

- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)

## Abstract (arXiv)

The non-smooth finite-sum minimization is a fundamental problem in machine learning. This paper develops a distributed stochastic proximal-gradient algorithm with random reshuffling to solve the finite-sum minimization over time-varying multi-agent networks. The objective function is a sum of differentiable convex functions and non-smooth regularization. Each agent in the network updates local variables with a constant step-size by local information and cooperates to seek an optimal solution. We prove that local variable estimates generated by the proposed algorithm achieve consensus and are attracted to a neighborhood of the optimal solution in expectation with an O(frac1T+frac1√T) convergence rate, where T is the total number of iterations. Finally, some comparative simulations are provided to verify the convergence performance of the proposed algorithm.