Random block-coordinate gradient projection algorithms

Chandramani Singh; Angelia Nedic; R. Srikant

doi:10.1109/CDC.2014.7039379

Random block-coordinate gradient projection algorithms

Chandramani Singh, Angelia Nedic, R. Srikant

Research output: Contribution to journal › Conference article

Abstract

In this paper, we study gradient projection algorithms based on random partial updates of decision variables. These algorithms generalize random coordinate descent methods. We analyze these algorithms with and without assuming strong convexity of the objective functions. We also present an accelerated version of the algorithm based on Nesterov's two-step gradient method [1]. In each case, we prove convergence and provide a bound on the rate of convergence. We see that the randomized algorithms exhibit similar rates of convergence as their full gradient based deterministic counterparts.

Original language	English (US)
Article number	7039379
Pages (from-to)	185-190
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
Volume	2015-February
Issue number	February
DOIs	https://doi.org/10.1109/CDC.2014.7039379
State	Published - Jan 1 2014
Externally published	Yes
Event	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States Duration: Dec 15 2014 → Dec 17 2014

Fingerprint

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Cite this

Singh, C., Nedic, A., & Srikant, R. (2014). Random block-coordinate gradient projection algorithms. Proceedings of the IEEE Conference on Decision and Control, 2015-February(February), 185-190. [7039379]. https://doi.org/10.1109/CDC.2014.7039379

@article{a6ad62d2dacd45a5a5aac2040f73fb21,

title = "Random block-coordinate gradient projection algorithms",

abstract = "In this paper, we study gradient projection algorithms based on random partial updates of decision variables. These algorithms generalize random coordinate descent methods. We analyze these algorithms with and without assuming strong convexity of the objective functions. We also present an accelerated version of the algorithm based on Nesterov's two-step gradient method [1]. In each case, we prove convergence and provide a bound on the rate of convergence. We see that the randomized algorithms exhibit similar rates of convergence as their full gradient based deterministic counterparts.",

author = "Chandramani Singh and Angelia Nedic and R. Srikant",

year = "2014",

month = jan,

day = "1",

doi = "10.1109/CDC.2014.7039379",

language = "English (US)",

volume = "2015-February",

pages = "185--190",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "February",

note = "2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

}

TY - JOUR

T1 - Random block-coordinate gradient projection algorithms

AU - Singh, Chandramani

AU - Nedic, Angelia

AU - Srikant, R.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - In this paper, we study gradient projection algorithms based on random partial updates of decision variables. These algorithms generalize random coordinate descent methods. We analyze these algorithms with and without assuming strong convexity of the objective functions. We also present an accelerated version of the algorithm based on Nesterov's two-step gradient method [1]. In each case, we prove convergence and provide a bound on the rate of convergence. We see that the randomized algorithms exhibit similar rates of convergence as their full gradient based deterministic counterparts.

AB - In this paper, we study gradient projection algorithms based on random partial updates of decision variables. These algorithms generalize random coordinate descent methods. We analyze these algorithms with and without assuming strong convexity of the objective functions. We also present an accelerated version of the algorithm based on Nesterov's two-step gradient method [1]. In each case, we prove convergence and provide a bound on the rate of convergence. We see that the randomized algorithms exhibit similar rates of convergence as their full gradient based deterministic counterparts.

UR - http://www.scopus.com/inward/record.url?scp=84988227804&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988227804&partnerID=8YFLogxK

U2 - 10.1109/CDC.2014.7039379

DO - 10.1109/CDC.2014.7039379

M3 - Conference article

AN - SCOPUS:84988227804

VL - 2015-February

SP - 185

EP - 190

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

IS - February

M1 - 7039379

T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -

Access to Document

10.1109/CDC.2014.7039379