Almost Tune-Free Variance Reduction

Bingcong Li, Lingda Wang, Georgios B. Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The variance reduction class of algorithms including the representative ones, SVRG and SARAH, have well documented merits for empirical risk minimization problems. However, they require grid search to tune parameters (step size and the number of iterations per inner loop) for optimal performance. This work introduces 'almost tune-free' SVRG and SARAH schemes equipped with i) Barzilai-Borwein (BB) step sizes; ii) averaging; and, iii) the inner loop length adjusted to the BB step sizes. In particular, SVRG, SARAH, and their BB variants are first reexamined through an 'estimate sequence' lens to enable new averaging methods that tighten their convergence rates theoretically, and improve their performance empirically when the step size or the inner loop length is chosen large. Then a simple yet effective means to adjust the number of iterations per inner loop is developed to enhance the merits of the proposed averaging schemes and BB step sizes. Numerical tests corroborate the proposed methods.

Original languageEnglish (US)
Title of host publication37th International Conference on Machine Learning, ICML 2020
EditorsHal Daume, Aarti Singh
PublisherInternational Machine Learning Society (IMLS)
Pages5925-5934
Number of pages10
ISBN (Electronic)9781713821120
StatePublished - 2020
Event37th International Conference on Machine Learning, ICML 2020 - Virtual, Online
Duration: Jul 13 2020Jul 18 2020

Publication series

Name37th International Conference on Machine Learning, ICML 2020
VolumePartF168147-8

Conference

Conference37th International Conference on Machine Learning, ICML 2020
CityVirtual, Online
Period7/13/207/18/20

Bibliographical note

Funding Information:
The authors would like to thank anonymous reviewers for their constructive feedback. We also gratefully acknowledge the support from NSF grants 1711471, and 1901134.

Publisher Copyright:
© International Conference on Machine Learning, ICML 2020. All rights reserved.

Fingerprint Dive into the research topics of 'Almost Tune-Free Variance Reduction'. Together they form a unique fingerprint.

Cite this