Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes

Junqi Tang; Mohammad Golbabaee; Francis Bach; Mike Davies

Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes

Junqi Tang, Mohammad Golbabaee, Francis Bach, Mike Davies

Research output: Contribution to journal › Conference article › peer-review

5 Citations (SciVal)

Abstract

We propose a structure-adaptive variant of a state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity (RSC) constants. We also propose an adaptive-restart variant which is able to estimate the RSC on the fly and adjust the restart period automatically. We demonstrate the effectiveness of our approach via numerical experiments.

Original language	English
Pages (from-to)	429-440
Number of pages	12
Journal	Advances in Neural Information Processing Systems
Publication status	Published - 1 Jan 2018
Event	32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada Duration: 2 Dec 2018 → 8 Dec 2018

Funding

JT, FB, MG and MD would like to acknowledge the support from H2020-MSCA-ITN Machine Sensing Training Network (MacSeNet), project 642685; ERC grant SEQUOIA, project 724063; EPSRC Compressed Quantitative MRI grant, number EP/M019802/1; and ERC Advanced grant, project 694888, C-SENSE, respectively. MD is also supported by a Royal Society Wolfson Research Merit Award. JT would like to thank Damien Scieur and Vincent Roulet for helpful discussions during his research visit in SIERRA team.

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{a096dc5823b64165b1d53d5d7d7d2bdf,

title = "Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes",

abstract = "We propose a structure-adaptive variant of a state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity (RSC) constants. We also propose an adaptive-restart variant which is able to estimate the RSC on the fly and adjust the restart period automatically. We demonstrate the effectiveness of our approach via numerical experiments.",

author = "Junqi Tang and Mohammad Golbabaee and Francis Bach and Mike Davies",

year = "2018",

month = jan,

day = "1",

language = "English",

pages = "429--440",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

note = "32nd Conference on Neural Information Processing Systems, NeurIPS 2018 ; Conference date: 02-12-2018 Through 08-12-2018",

}

TY - JOUR

T1 - Rest-Katyusha

T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018

AU - Tang, Junqi

AU - Golbabaee, Mohammad

AU - Bach, Francis

AU - Davies, Mike

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We propose a structure-adaptive variant of a state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity (RSC) constants. We also propose an adaptive-restart variant which is able to estimate the RSC on the fly and adjust the restart period automatically. We demonstrate the effectiveness of our approach via numerical experiments.

AB - We propose a structure-adaptive variant of a state-of-the-art stochastic variance-reduced gradient algorithm Katyusha for regularized empirical risk minimization. The proposed method is able to exploit the intrinsic low-dimensional structure of the solution, such as sparsity or low rank which is enforced by a non-smooth regularization, to achieve even faster convergence rate. This provable algorithmic improvement is done by restarting the Katyusha algorithm according to restricted strong-convexity (RSC) constants. We also propose an adaptive-restart variant which is able to estimate the RSC on the fly and adjust the restart period automatically. We demonstrate the effectiveness of our approach via numerical experiments.

UR - http://www.scopus.com/inward/record.url?scp=85064836500&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85064836500

SN - 1049-5258

SP - 429

EP - 440

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

Y2 - 2 December 2018 through 8 December 2018

ER -

Rest-Katyusha: Exploiting the solution's structure via scheduled restart schemes

Abstract

Funding

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this