Finite-sum smooth optimization with SARAH

Lam M. Nguyen (), Marten Dijk (), Dzung T. Phan (), Phuong Ha Nguyen (), Tsui-Wei Weng () and Jayant R. Kalagnanam ()
Additional contact information
Lam M. Nguyen: IBM Research, Thomas J. Watson Research Center
Marten Dijk: Computer Security Group
Dzung T. Phan: IBM Research, Thomas J. Watson Research Center
Phuong Ha Nguyen: eBay Inc.
Tsui-Wei Weng: University of California San Diego
Jayant R. Kalagnanam: IBM Research, Thomas J. Watson Research Center

Computational Optimization and Applications, 2022, vol. 82, issue 3, No 1, 593 pages

Abstract: Abstract We introduce NC-SARAH for non-convex optimization as a practical modified version of the original SARAH algorithm that was developed for convex optimization. NC-SARAH is the first to achieve two crucial performance properties at the same time—allowing flexible minibatch sizes and large step sizes to achieve fast convergence in practice as verified by experiments. NC-SARAH has a close to optimal asymptotic convergence rate equal to existing prior variants of SARAH called SPIDER and SpiderBoost that either use an order of magnitude smaller step size or a fixed minibatch size. For convex optimization, we propose SARAH++ with sublinear convergence for general convex and linear convergence for strongly convex problems; and we provide a practical version for which numerical experiments on various datasets show an improved performance.

Keywords: Finite-sum; Smooth; Non-convex; Convex; Stochastic algorithm; Variance reduction (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00375-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:82:y:2022:i:3:d:10.1007_s10589-022-00375-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00375-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().