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

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 provide a linear convergence in expectation of the outer iterates to the unique optimal solution for strongly convex problems. Furthermore, we provide a complexity analysis of the algorithm. Numerical experiments demonstrate that the proposed algorithm outperforms existing state-of-the-art methods in its class.