# MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 50 references that are in the map.
- First posted on arXiv 6 Jun 2021.

## Builds on (most cited first, 30 of 33)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Optimal Gradient Compression for Distributed and Federated Learning](https://mlsanity.com/paper/2010.03246/) (2020)
- [Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization](https://mlsanity.com/paper/2006.11573/) (2020)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning](https://mlsanity.com/paper/1911.08250/) (2019)
- [A Double Residual Compression Algorithm for Efficient Distributed Learning](https://mlsanity.com/paper/1910.07561/) (2019)
- [Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists](https://mlsanity.com/paper/1912.00137/) (2019)
- [Fixed Point Strategies in Data Science](https://mlsanity.com/paper/2008.02260/) (2020)
- [L-SVRG and L-Katyusha with Arbitrary Sampling](https://mlsanity.com/paper/1906.01481/) (2019)
- [Optimal mini-batch and step sizes for SAGA](https://mlsanity.com/paper/1902.00071/) (2019)

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

- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [Shifted Compression Framework: Generalizations and Improvements](https://mlsanity.com/paper/2206.10452/) (2022)
- [TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation](https://mlsanity.com/paper/2302.09832/) (2023)
- [A Stochastic Variance-Reduced Coordinate Descent Algorithm for Learning Sparse Bayesian Network from Discrete High-Dimensional Data](https://mlsanity.com/paper/2108.09501/) (2021)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)
- [Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2511.05593/) (2025)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

We propose a generic variance-reduced algorithm, which we call MUltiple RANdomized Algorithm (MURANA), for minimizing a sum of several smooth functions plus a regularizer, in a sequential or distributed manner. Our method is formulated with general stochastic operators, which allow us to model various strategies for reducing the computational complexity. For example, MURANA supports sparse activation of the gradients, and also reduction of the communication load via compression of the update vectors. This versatility allows MURANA to cover many existing randomization mechanisms within a unified framework, which also makes it possible to design new methods as special cases.