Stochastic ISTA/FISTA Adaptive Step Search Algorithms for Convex Composite Optimization

We develop and analyze stochastic variants of ISTA and a full backtracking FISTA algorithms (Beck and Teboulle in SIAM J Imag Sci 2(1)–202, 2009; Scheinberg et al. in Found Comput Math 14(3)–417, 2014) for composite optimization without the assumption that stochastic gradient is an unbiased estimator. This work extends analysis of inexact fixed step ISTA/FISTA in Schmidt et al. (Convergence rates of inexact proximal-gradient methods for convex optimization, 2022. arXiv.2415) to the case of stochastic gradient estimates and adaptive step-size parameter chosen by backtracking. It also extends the framework for analyzing stochastic line-search method in Cartis and Scheinberg (Math Program 169(2), 2018) to the proximal gradient framework as well as to the accelerated first order methods.