On The Average Block Coordinate Descent Methods And Its Preconditioning

The Coordinate Descent(CD)method is a simple but efficient non-gradient optimization algorithm,which is equivalent to the classical Gauss-Seidel method directly applied to normal equations.It can be used to solve large-scale linear least square problems.To reduce the iteration steps of CD method,some scholars have proposed Randomized Coordinate Descent method,Greedy Randomized Coordinate Descent method,and Randomized Block Gauss-Seidel method,and so on.To further improve the efficiency of the algorithms,in this paper,we constructs an Average Block Coordinate Descent method.By using random partition strategies and residual-based greedy criteria,we propose two specific Average Block Coordinate Descent methods: Greedy Average Randomized Block Coordinate Descent method and Greedy Average Block Coordinate Descent method.Theoretical analysis shows that the convergence rates of the two methods are both related to the singular values of the coefficient matrix and the selected partitioned matrices.Therefore,we further propose a preconditioned method based on sketching to improve the singular value distribution and accelerate the convergence of the new algorithms.The specific content of this paper is as follows:(1)By weighting and averaging multiple search directions simultaneously to obtain a new search direction,and defining appropriate step size and weights,we propose the Average Block Coordinate Descent method.Compared with the Block Coordinate Descent method,the new method has lower computational complexity and is more suitable for distributed computing.(2)By using random partition strategies and the residual-based greedy criteria,we propose the Greedy Average Randomized Block Coordinate Descent method and Greedy Average Block Coordinate Descent method.The convergence analysis of the two methods is given,and we prove that the two methods converge linearly to the unique minimum norm solution of the least square problem.Numerical results show that the performance of new methods are better than the existing classical methods.(3)Through theoretical analysis,we find that the convergence rates of the two methods are both related to the minimum singular value of the coefficient matrix and the maximum singular values of the partitioned matrices selected at each iteration step.Therefore,in order to further accelerate the convergence of the two methods,we investigate the sketching preconditioners and proposes the Preconditioned Greedy Average Randomized Block Coordinate Descent method and Preconditioned Greedy Average Block Coordinate Descent method.Numerical results show that both the iteration steps and CPU time are significantly reduced by utilizing the Count Sketch preconditioner,which means that the preconditioner constructed by sketching is practical and effective.