Speaker: Zheng Qu

Title: Randomized Coordinate Descent for Composite optimization: algorithm and complexity

Abstract: In this talk we present a randomized coordinate descent method for solving the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. In special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent both in non-accelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a unified complexity analysis, from which we deduce as direct corollary complexity bounds for its many variants, all matching or improving best known bounds.