Universal randomized switching

Suleyman S. Kozat, Andrew C. Singer

Research output: Contribution to journalArticlepeer-review


In this paper, we consider a competitive approach to sequential decision problems, suitable for a variety of signal processing applications where at each of a succession of times, a selection must be made from among a fixed set of strategies (or outcomes). For each such decision and outcome pair, loss is incurred, and it is the time-accumulation of these losses that is sought to be minimized. Rather than using a statistical performance measure, our goal in this pursuit is to sequentially accumulate loss that is no larger than that of the best loss that could be obtained through a partitioning of the sequence of observations into an arbitrary fixed number of segments and independently selecting a different strategy for each segment. For this purpose, we introduce a randomized sequential algorithm built upon that of Kozat and Singer that asymptotically achieves the performance of a noncausal algorithm thatwould be able to choose the number of segments and the best algorithm for each segment, based on observing the whole observation process a priori. In addition to improving upon the bounds of Kozat and Singer as well as Gyorgy et al., the results we provide hold formore general loss functions than the square-error loss studied therein.

Original languageEnglish (US)
Pages (from-to)1922-1927
Number of pages6
JournalIEEE Transactions on Signal Processing
Issue number3 PART 2
StatePublished - Mar 2010


  • Prediction
  • Quantization
  • Randomized
  • Sequential decisions
  • Switching
  • Universal

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Universal randomized switching'. Together they form a unique fingerprint.

Cite this