Adaptive step size selection for optimization via the ski rental problem

Amirali Aghazadeh; Ali Ayremlou; Daniel D. Calderon; Tom Goldstein; Raajen Patel; Divyanshu Vats; Richard G. Baraniuk

doi:10.1109/ICASSP.2013.6638691

Adaptive step size selection for optimization via the ski rental problem

Amirali Aghazadeh, Ali Ayremlou, Daniel D. Calderon, Tom Goldstein, Raajen Patel, Divyanshu Vats, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.

Original language	English (US)
Title of host publication	2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings
Pages	5383-5387
Number of pages	5
DOIs	https://doi.org/10.1109/ICASSP.2013.6638691
State	Published - Oct 18 2013
Event	2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Vancouver, BC, Canada Duration: May 26 2013 → May 31 2013

Other

Other	2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013
Country/Territory	Canada
City	Vancouver, BC
Period	5/26/13 → 5/31/13

Keywords

sensor networks
ski rental problem
sparsity
step size using adaptivity

ASJC Scopus subject areas

Signal Processing
Software
Electrical and Electronic Engineering

Access to Document

10.1109/ICASSP.2013.6638691

Cite this

Aghazadeh, A, Ayremlou, A, Calderon, DD, Goldstein, T, Patel, R, Vats, D & Baraniuk, RG 2013, Adaptive step size selection for optimization via the ski rental problem. in 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings., 6638691, pp. 5383-5387, 2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, 5/26/13. https://doi.org/10.1109/ICASSP.2013.6638691

@inproceedings{2498c295240249629edbd26a938774e2,

title = "Adaptive step size selection for optimization via the ski rental problem",

abstract = "Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.",

keywords = "sensor networks, ski rental problem, sparsity, step size using adaptivity",

author = "Amirali Aghazadeh and Ali Ayremlou and Calderon, {Daniel D.} and Tom Goldstein and Raajen Patel and Divyanshu Vats and Baraniuk, {Richard G.}",

year = "2013",

month = oct,

day = "18",

doi = "10.1109/ICASSP.2013.6638691",

language = "English (US)",

isbn = "9781479903566",

pages = "5383--5387",

booktitle = "2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings",

note = "2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 ; Conference date: 26-05-2013 Through 31-05-2013",

}

TY - GEN

T1 - Adaptive step size selection for optimization via the ski rental problem

AU - Aghazadeh, Amirali

AU - Ayremlou, Ali

AU - Calderon, Daniel D.

AU - Goldstein, Tom

AU - Patel, Raajen

AU - Vats, Divyanshu

AU - Baraniuk, Richard G.

PY - 2013/10/18

Y1 - 2013/10/18

N2 - Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.

AB - Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.

KW - sensor networks

KW - ski rental problem

KW - sparsity

KW - step size using adaptivity

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

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

U2 - 10.1109/ICASSP.2013.6638691

DO - 10.1109/ICASSP.2013.6638691

M3 - Conference contribution

AN - SCOPUS:84890469527

SN - 9781479903566

SP - 5383

EP - 5387

BT - 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings

T2 - 2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013

Y2 - 26 May 2013 through 31 May 2013

ER -

Adaptive step size selection for optimization via the ski rental problem

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this