Gradient Projection Iterative Sketch for Large Scale Constrained Least-Squares

Junqi Tang; Mohammad Golbabaee; Michael Davies

Gradient Projection Iterative Sketch for Large Scale Constrained Least-Squares

Junqi Tang, Mohammad Golbabaee, Michael Davies

School of Engineering

Research output: Contribution to conference › Paper › peer-review

Abstract

We propose a randomized first order optimization algorithm GradientProjection Iterative Sketch (GPIS) and an accelerated variant forefficiently solving large scale constrained Least Squares (LS). Weprovide theoretical convergence analysis for both proposed algorithmsand demonstrate our methods' computational efficiency compared toclassical accelerated gradient method, and the state of the artvariance-reduced stochastic gradient methods through numericalexperiments in various large synthetic/real data sets.

Original language	English
Publication status	Published - Aug 2017
Event	34th International Conference on Machine Learning (ICML), 2017 - Sydney, Australia Duration: 6 Aug 2017 → 11 Aug 2017

Conference

Conference	34th International Conference on Machine Learning (ICML), 2017
Country/Territory	Australia
City	Sydney
Period	6/08/17 → 11/08/17

Access to Document

arXiv version 1609.09419Accepted author manuscript, 333 KB
tang17aFinal published version, 370 KB

http://proceedings.mlr.press/v70/tang17a.htmlLicence: All Rights Reserved

Exploiting low dimensional models in sensing, computation and signal processing
Davies, M.
EU government bodies
1/09/16 → 31/08/22
Project: Research
CQ-MRI: Compressed Quantitative MRI
Marshall, I. & Davies, M.
EPSRC
1/07/15 → 31/12/18
Project: Research
MacSeNet: MacSeNet: Machine Sensing Training Network
Davies, M.
EU government bodies
1/01/15 → 31/12/18
Project: Research

Structure-Adaptive Large-Scale Convex Optimization Toolbox v1.0
Tang, J. (Creator), Edinburgh DataShare, 28 Jan 2019
DOI: 10.7488/ds/2489
Dataset

Cite this

@conference{25a6261b1bb9468397cd0af773e34700,

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

abstract = "We propose a randomized first order optimization algorithm GradientProjection Iterative Sketch (GPIS) and an accelerated variant forefficiently solving large scale constrained Least Squares (LS). Weprovide theoretical convergence analysis for both proposed algorithmsand demonstrate our methods' computational efficiency compared toclassical accelerated gradient method, and the state of the artvariance-reduced stochastic gradient methods through numericalexperiments in various large synthetic/real data sets.",

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

year = "2017",

month = aug,

language = "English",

note = "34th International Conference on Machine Learning (ICML), 2017 ; Conference date: 06-08-2017 Through 11-08-2017",

}

TY - CONF

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

AU - Tang, Junqi

AU - Golbabaee, Mohammad

AU - Davies, Michael

PY - 2017/8

Y1 - 2017/8

N2 - We propose a randomized first order optimization algorithm GradientProjection Iterative Sketch (GPIS) and an accelerated variant forefficiently solving large scale constrained Least Squares (LS). Weprovide theoretical convergence analysis for both proposed algorithmsand demonstrate our methods' computational efficiency compared toclassical accelerated gradient method, and the state of the artvariance-reduced stochastic gradient methods through numericalexperiments in various large synthetic/real data sets.

AB - We propose a randomized first order optimization algorithm GradientProjection Iterative Sketch (GPIS) and an accelerated variant forefficiently solving large scale constrained Least Squares (LS). Weprovide theoretical convergence analysis for both proposed algorithmsand demonstrate our methods' computational efficiency compared toclassical accelerated gradient method, and the state of the artvariance-reduced stochastic gradient methods through numericalexperiments in various large synthetic/real data sets.

M3 - Paper

T2 - 34th International Conference on Machine Learning (ICML), 2017

Y2 - 6 August 2017 through 11 August 2017

ER -

Gradient Projection Iterative Sketch for Large Scale Constrained Least-Squares

Abstract

Conference

Access to Document

Fingerprint

Projects

Exploiting low dimensional models in sensing, computation and signal processing

CQ-MRI: Compressed Quantitative MRI

MacSeNet: MacSeNet: Machine Sensing Training Network

Datasets

Structure-Adaptive Large-Scale Convex Optimization Toolbox v1.0

Cite this