Stochastic Steepest Descent Methods for Linear Systems: Greedy Sampling & Momentum
Md Sarowar Morshed,
Sabbir Ahmad
August, 2021
Abstract
Recently proposed adaptive (SP) methods connect several well-known projection methods such as (RK), (RBK), (MR), (RCD), (CCD) etc. into one framework for solving linear systems. In this work, we first propose a (SSD) framework that connects SP methods with the well-known (SD) method for solving positive-definite linear system of equations. We then introduce two greedy sampling strategies in the SSD framework that allow us to obtain algorithms such as (SKM), (SBK), (SCD), etc. In doing so, we generalize the existing sampling rules into one framework and develop an efficient version of SP methods. Furthermore, we incorporated the Polyak momentum technique into the SSD method to accelerate the resulting algorithms. We provide global convergence results for both the SSD method and the momentum induced SSD method. Moreover, we prove convergence rate for the Cesaro average of iterates generated by both methods. By varying parameters in the SSD method, we obtain classical convergence results of the SD method as well as the SP methods as special cases. We design computational experiments to demonstrate the performance of the proposed greedy sampling methods as well as the momentum methods. The proposed greedy methods significantly outperform the existing methods for a wide variety of datasets such as random test instances as well as real-world datasets (LIBSVM, sparse datasets from matrix market collection). Finally, the momentum algorithms designed in this work accelerate the algorithmic performance of the SSD methods.
Operations Research Engineer
My research interests include mathematical optimization, operations research and machine learning.