Approximate Steepest Coordinate Descent

2017/06/26 by Sebastian U. Stich, Stich, Sebastian U., Anant Raj +3
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Robotics and Sensor-Based Localization

paper · pdf · doi:10.48550/arxiv.1706.08427

Abstract

We propose a new selection rule for the coordinate selection in coordinate descent methods for huge-scale optimization. The efficiency of this novel scheme is provably better than the efficiency of uniformly random selection, and can reach the efficiency of steepest coordinate descent (SCD), enabling an acceleration of a factor of up to n, the number of coordinates. In many practical applications, our scheme can be implemented at no extra cost and computational efficiency very close to the faster uniform selection. Numerical experiments with Lasso and Ridge regression show promising improvements, in line with our theoretical guarantees.

Related

• A Primer on Coordinate Descent Algorithms
• Towards Solving Large-scale Expensive Optimization Problems Efficiently\n Using Coordinate Descent Algorithm
• Coordinate Descent with Bandit Sampling
• Coordinate Descent Algorithms
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling