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):183–202, 2009; Scheinberg et al. in Found Comput Math 14(3):389–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:1109.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):337-375, 2018) to the proximal gradient framework as well as to the accelerated first order methods.