Stochastic Spectral and Conjugate Descent Methods

2018/02/11 by Dmitry Kovalev, Kovalev, Dmitry, Eduard Gorbunov +5 · 1 citation
Computer Science · Engineering · Mathematics · #Face and Expression Recognition #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1802.03703

arxiv created 2018/02/11 · arxiv updated 2018/02/13

Abstract

The state-of-the-art methods for solving optimization problems in big dimensions are variants of randomized coordinate descent (RCD). In this paper we introduce a fundamentally new type of acceleration strategy for RCD based on the augmentation of the set of coordinate directions by a few spectral or conjugate directions. As we increase the number of extra directions to be sampled from, the rate of the method improves, and interpolates between the linear rate of RCD and a linear rate independent of the condition number. We develop and analyze also inexact variants of these methods where the spectral and conjugate directions are allowed to be approximate only. We motivate the above development by proving several negative results which highlight the limitations of RCD with importance sampling.

Cited by

• Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions

Related

• Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
• About accelerated randomized methods
• Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
• Stability and Generalization for Randomized Coordinate Descent
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection