Inexact SARAH algorithm for stochastic optimization. (2nd January 2021)

• Record Type: Journal Article
• Authors: Nguyen, Lam M.; Scheinberg, Katya; Takáč, Martin
• Is Part Of: Optimization methods and software. Volume 36:Number 1(2021)
• Page Start: 237
• Page End: 258
• Publication Date: 2021-01-02
• Subjects: Stochastic gradient algorithms -- variance reduction -- stochastic optimization -- smooth convex; 90C15 -- 90C25 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1818081
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We develop and analyse a variant of the SARAH algorithm, which does not require computation of the exact gradient. Thus this new method can be applied to general expectation minimization problems rather than only finite sum problems. While the original SARAH algorithm, as well as its predecessor, SVRG, requires an exact gradient computation on each outer iteration, the inexact variant of SARAH (iSARAH), which we develop here, requires only stochastic gradient computed on a mini-batch of sufficient size. The proposed method combines variance reduction via sample size selection and iterative stochastic gradient updates. We analyse the convergence rate of the algorithms for strongly convex and non-strongly convex cases, under smooth assumption with appropriate mini-batch size selected for each case. We show that with an additional, reasonable, assumption iSARAH achieves the best-known complexity among stochastic methods in the case of non-strongly convex stochastic functions.