Subsampled cubic regularization method for finite-sum minimization

Abstract

This paper proposes and analyses a subsampled Cubic Regularization Method (CRM) for solving finite-sum optimization problems. The new method uses random subsampling techniques to approximate the functions, gradients and Hessians in order to reduce the overall computational cost of the CRM. Under suitable hypotheses, first- and second-order iteration-complexity bounds and global convergence analyses are presented. We also discuss the local convergence properties of the method. Numerical experiments are presented to illustrate the performance of the proposed scheme.