A Stochastic Recursive Gradient Algorithm with Random Barzilai-Borwein Step Size for Convex Optimization

Abstract

The stochastic recursive gradient algorithm (SARAH) has garnered considerable attention owing to its implementation of a straightforward recursive framework for stochastic gradient updates. Motivated by this, we propose to integrate the importance sampling strategy with mini-batch techniques into the SARAH framework, developing a variant termed SARAH-MI-RBB. During each inner iteration of SARAH-MI-RBB, the mini-batch technique and importance sampling method are employed to dynamically adjust the Barzilai-Borwein (BB) step size and update the iterates. We establish the linear convergence in expectation of the outer iterates to the unique optimal solution for strongly convex problems. Furthermore, we establish the complexity analysis of the algorithm. Numerical experiments demonstrate that the proposed algorithm outperforms existing state-of-the-art methods in its class.