# Nonconvex Variance Reduced Optimization with Arbitrary Sampling

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2018.

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

- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling](https://mlsanity.com/paper/2206.02275/) (2022)
- [Fast-FedUL: A Training-Free Federated Unlearning with Provable Skew Resilience](https://mlsanity.com/paper/2405.18040/) (2024)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations](https://mlsanity.com/paper/2405.15545/) (2024)
- [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)
- [Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance](https://mlsanity.com/paper/2310.02698/) (2023)
- [Client Selection in Federated Learning with Data Heterogeneity and Network Latencies](https://mlsanity.com/paper/2504.01921/) (2025)

## Abstract (arXiv)

We provide the first importance sampling variants of variance reduced algorithms for empirical risk minimization with non-convex loss functions. In particular, we analyze non-convex versions of SVRG, SAGA and SARAH. Our methods have the capacity to speed up the training process by an order of magnitude compared to the state of the art on real datasets. Moreover, we also improve upon current mini-batch analysis of these methods by proposing importance sampling for minibatches in this setting. Surprisingly, our approach can in some regimes lead to superlinear speedup with respect to the minibatch size, which is not usually present in stochastic optimization. All the above results follow from a general analysis of the methods which works with arbitrary sampling, i.e., fully general randomized strategy for the selection of subsets of examples to be sampled in each iteration. Finally, we also perform a novel importance sampling analysis of SARAH in the convex setting.