# L-SVRG and L-Katyusha with Arbitrary Sampling

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2019.

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

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling](https://mlsanity.com/paper/2206.02275/) (2022)
- [Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology](https://mlsanity.com/paper/2207.03730/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Personalized Federated Learning with Multiple Known Clusters](https://mlsanity.com/paper/2204.13619/) (2022)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)
- [Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient](https://mlsanity.com/paper/2405.17761/) (2024)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)

## Abstract (arXiv)

We develop and analyze a new family of em nonaccelerated and accelerated loopless variance-reduced methods for finite sum optimization problems. Our convergence analysis relies on a novel expected smoothness condition which upper bounds the variance of the stochastic gradient estimation by a constant times a distance-like function. This allows us to handle with ease em arbitrary sampling schemes as well as the nonconvex case. We perform an in-depth estimation of these expected smoothness parameters and propose new importance samplings which allow em linear speedup when the expected minibatch size is in a certain range. Furthermore, a connection between these expected smoothness parameters and expected separable overapproximation (ESO) is established, which allows us to exploit data sparsity as well. Our results recover as special cases the recently proposed loopless SVRG and loopless Katyusha.