Fast Distributed Coordinate Descent for Non-Strongly Convex Losses

2014/05/21 by Olivier Fercoq, Zheng Qu, Fercoq, Olivier +5
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.1405.5300

arxiv created 2014/07/27 · arxiv updated 2014/07/29

Abstract

We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k²) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest supercomputer in the UK - and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.

Related

• Parallel Coordinate Descent Methods for Big Data Optimization
• Distributed Coordinate Descent Method for Learning with Big Data
• Pathwise coordinate optimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Accelerated, Parallel and Proximal Coordinate Descent