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 proceedingConference 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 languageEnglish (US)
Title of host publication2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings
Pages5383-5387
Number of pages5
DOIs
StatePublished - Oct 18 2013
Event2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Vancouver, BC, Canada
Duration: May 26 2013May 31 2013

Other

Other2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013
Country/TerritoryCanada
CityVancouver, BC
Period5/26/135/31/13

Keywords

  • sensor networks
  • ski rental problem
  • sparsity
  • step size using adaptivity

ASJC Scopus subject areas

  • Signal Processing
  • Software
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Adaptive step size selection for optimization via the ski rental problem'. Together they form a unique fingerprint.

Cite this