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

Junqi Tang, Mohammad Golbabaee, Mike E. Davies
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3377-3386, 2017.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares %A Junqi Tang %A Mohammad Golbabaee %A Mike E. Davies %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-tang17a %I PMLR %P 3377--3386 %U https://proceedings.mlr.press/v70/tang17a.html %V 70 %X 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.
APA
Tang, J., Golbabaee, M. & Davies, M.E.. (2017). Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3377-3386 Available from https://proceedings.mlr.press/v70/tang17a.html.

Related Material