# L-SVRG and L-Katyusha with Adaptive Sampling

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

## Key facts

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

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [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)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (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)
- [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015)
- [On Optimal Probabilities in Stochastic Coordinate Descent Methods](https://mlsanity.com/paper/1310.3438/) (2013)
- [L-SVRG and L-Katyusha with Arbitrary Sampling](https://mlsanity.com/paper/1906.01481/) (2019)
- [Online Variance Reduction for Stochastic Optimization](https://mlsanity.com/paper/1802.04715/) (2018)
- [Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches](https://mlsanity.com/paper/1809.09354/) (2018)
- [SAGA with Arbitrary Sampling](https://mlsanity.com/paper/1901.08669/) (2019)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Stochastic Optimization with Bandit Sampling](https://mlsanity.com/paper/1708.02544/) (2017)
- [Online Variance Reduction with Mixtures](https://mlsanity.com/paper/1903.12416/) (2019)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)

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

- [Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm](https://mlsanity.com/paper/2306.02543/) (2023)

## Abstract (arXiv)

Stochastic gradient-based optimization methods, such as L-SVRG and its accelerated variant L-Katyusha (Kovalev et al., 2020), are widely used to train machine learning models.The theoretical and empirical performance of L-SVRG and L-Katyusha can be improved by sampling observations from a non-uniform distribution (Qian et al., 2021). However,designing a desired sampling distribution requires prior knowledge of smoothness constants, which can be computationally intractable to obtain in practice when the dimension of the model parameter is high. To address this issue, we propose an adaptive sampling strategy for L-SVRG and L-Katyusha that can learn the sampling distribution with little computational overhead, while allowing it to change with iterates, and at the same time does not require any prior knowledge of the problem parameters. We prove convergence guarantees for L-SVRG and L-Katyusha for convex objectives when the sampling distribution changes with iterates. Our results show that even without prior information, the proposed adaptive sampling strategy matches, and in some cases even surpasses, the performance of the sampling scheme in Qian et al. (2021). Extensive simulations support our theory and the practical utility of the proposed sampling scheme on real data.