Stochastic Spectral and Conjugate Descent Methods

Dmitry Kovalev; Eduard Gorbunov; Elnur Gasanov; Peter Richtarik

Stochastic Spectral and Conjugate Descent Methods

Dmitry Kovalev, Eduard Gorbunov, Elnur Gasanov, Peter Richtarik

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems, 2018
Publisher	NIPS Proceedingsβ
State	Published - Feb 11 2018

Access to Document

https://repository.kaust.edu.sa/bitstream/10754/627183/1/1802.03703v1.pdf

Cite this

@inproceedings{2c043d059cae43beaf53da8fac3a16c4,

title = "Stochastic Spectral and Conjugate Descent Methods",

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.",

author = "Dmitry Kovalev and Eduard Gorbunov and Elnur Gasanov and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2018",

month = feb,

day = "11",

language = "English (US)",

booktitle = "Advances in Neural Information Processing Systems, 2018",

publisher = "NIPS Proceedingsβ",

}

TY - GEN

T1 - Stochastic Spectral and Conjugate Descent Methods

AU - Kovalev, Dmitry

AU - Gorbunov, Eduard

AU - Gasanov, Elnur

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2018/2/11

Y1 - 2018/2/11

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/627183

UR - https://papers.nips.cc/paper/7596-stochastic-spectral-and-conjugate-descent-methods

M3 - Conference contribution

BT - Advances in Neural Information Processing Systems, 2018

PB - NIPS Proceedingsβ

ER -

Stochastic Spectral and Conjugate Descent Methods

Abstract

Access to Document

Other files and links

Fingerprint

Cite this