ICML 2017poster43 citations
Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares
Junqi Tang, Mohammad Golbabaee, Mike E. Davies
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.
BibTeX
@InProceedings{pmlr-v70-tang17a,
title = {Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares},
author = {Junqi Tang and Mohammad Golbabaee and Mike E. Davies},
booktitle = {Proceedings of the 34th International Conference on Machine Learning},
pages = {3377--3386},
year = {2017},
editor = {Precup, Doina and Teh, Yee Whye},
volume = {70},
series = {Proceedings of Machine Learning Research},
month = {06--11 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v70/tang17a/tang17a.pdf},
url = {https://proceedings.mlr.press/v70/tang17a.html},
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.}
}