Mini-batch Block Coordinate Descent Method Based On Gauss-Southwell Rule

Optimization is an important branch of operational research.It is widely applied in many different fields such as economy,finance,engineering,management,military and national defense.In particular,it is a key technology of machine learning and artificial intelligence.With the coming of the big data era,the scale and dimention of data grow tremendously,and optimization methods nowadays face the challenge of low speed and high computational cost.How to design fast and effective algorithms remains a hot research topic.In this paper,we focus on stochastic optimization algorithms in machine learning and propose a novel fast algorithm.First we introduce the background and significance of the algorithm,then we give an overview of two kinds of algorithms for large-scale optimization problems proposed by researchers.After comparing and summarizing these algorithms,we propose the mini-batch block coordinate descent method based on Gauss-Southwell rule.This algorithm has the following characteristics:(1)We give GS rule under the condition of block coordinates and select a block that leads to the optimum descent for objective function.(2)It also has the idea of stochastic gradient descent method,which uses only part of the samples to obtain a local gradient as an approximation for the whole gradient.In order to reduce the amount of computation,we also apply the variance reduction technique,thus the variance introduced by random sampling asymptotically converges to zero.(3)At each step of iteration we only select a single block of coordinates to update the parameter,thus further reducing the amount of computation.Based on 4 real datasets,we carry out numerical experiments to compare different algorithms in terms of time,computation and sparsity.The results show that the algorithm we propose is highly efficient and fast for solving Lasso problems,sparse logistic regression and multi-class sparse logistic regression in large-scale and high-dimensional optimization problems.Meanwhile,this paper also gives an algorithm software package written in Python.