Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares

Junqi Tang; Mohammad Golbabaee; Mike Davies

Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares

Junqi Tang, Mohammad Golbabaee, Mike Davies

Mathematics

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

Abstract

We propose a randomized first order optimization algorithm Gradient Projection Iterative Sketch (GPIS) and an accelerated variant for efficiently solving large scale constrained Least Squares (LS). We provide the first theoretical convergence analysis for both algorithms. An efficient implementation using a tailored line-search scheme is also proposed. We demonstrate our methods’ computational efficiency compared to the classical accelerated gradient method, and the variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.

Original language	English
Title of host publication	Proceedings of the 34th International Conference on Machine Learning
Publication status	Published - 6 Aug 2017

Access to Document

http://proceedings.mlr.press/v70/tang17a/tang17a.pdf

Cite this

@inproceedings{7db06ad55e484e92b5c2b7c08cd9fb52,

title = "Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares",

abstract = "We propose a randomized first order optimization algorithm Gradient Projection Iterative Sketch (GPIS) and an accelerated variant for efficiently solving large scale constrained Least Squares (LS). We provide the first theoretical convergence analysis for both algorithms. An efficient implementation using a tailored line-search scheme is also proposed. We demonstrate our methods{\textquoteright} computational efficiency compared to the classical accelerated gradient method, and the variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.",

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

year = "2017",

month = aug,

day = "6",

language = "English",

booktitle = "Proceedings of the 34th International Conference on Machine Learning",

}

TY - GEN

T1 - Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares

AU - Tang, Junqi

AU - Golbabaee, Mohammad

AU - Davies, Mike

PY - 2017/8/6

Y1 - 2017/8/6

N2 - We propose a randomized first order optimization algorithm Gradient Projection Iterative Sketch (GPIS) and an accelerated variant for efficiently solving large scale constrained Least Squares (LS). We provide the first theoretical convergence analysis for both algorithms. An efficient implementation using a tailored line-search scheme is also proposed. We demonstrate our methods’ computational efficiency compared to the classical accelerated gradient method, and the variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.

AB - We propose a randomized first order optimization algorithm Gradient Projection Iterative Sketch (GPIS) and an accelerated variant for efficiently solving large scale constrained Least Squares (LS). We provide the first theoretical convergence analysis for both algorithms. An efficient implementation using a tailored line-search scheme is also proposed. We demonstrate our methods’ computational efficiency compared to the classical accelerated gradient method, and the variance-reduced stochastic gradient methods through numerical experiments in various large synthetic/real data sets.

M3 - Conference contribution

BT - Proceedings of the 34th International Conference on Machine Learning

ER -

Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares

Abstract

Access to Document

Fingerprint

Cite this