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’ 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
Text
Tang et al. "Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares." International Conference on Machine Learning, 2017.Markdown
[Tang et al. "Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/tang2017icml-gradient/)BibTeX
@inproceedings{tang2017icml-gradient,
title = {{Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares}},
author = {Tang, Junqi and Golbabaee, Mohammad and Davies, Mike E.},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {3377-3386},
volume = {70},
url = {https://mlanthology.org/icml/2017/tang2017icml-gradient/}
}