Probabilistic Variance-Reduced Shuffling Gradient Descent Algorithm for Nonconvex Optimization

Nonconvex finite-sum optimization finds wide applications in various signal processing and machine learning tasks. The well-known stochastic gradient algorithms generate unbiased stochastic gradient estimates by taking the uniform sampling mechanism with replacement, which can be difficult to implement in practice. This paper explores a sampling-without-replacement shuffling scheme to generate stochastic gradients. Additionally, to handle the variance of gradients, this paper develops a novel variance reduction step in the shuffling gradient descent algorithm. Specifically, this paper proposes a probabilistic variance-reduced shuffling gradient descent algorithm, which reduces the number of gradient oracle calls in the variance reduction step. The proposed algorithm owns a better convergence rate compared to existing stochastic gradient algorithms for nonconvex optimization. Finally, numerical results are presented to demonstrate the efficiency of the proposed algorithm.