TY - GEN

T1 - Sequential probability assignment via online convex programming using exponential families

AU - Raginsky, Maxim

AU - Marcia, Roummel F.

AU - Silva, Jorge

AU - Willett, Rebecca M.

PY - 2009

Y1 - 2009

N2 - This paper considers the problem of sequential assignment of probabilities (likelihoods) to elements of an individual sequence using an exponential family of probability distributions. We draw upon recent work on online convex programming to devise an algorithm that does not require computing posterior distributions given all current observations, involves simple primal-dual parameter updates, and achieves minimax per-round regret against slowly varying product distributions with marginals drawn from the same exponential family. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality.

AB - This paper considers the problem of sequential assignment of probabilities (likelihoods) to elements of an individual sequence using an exponential family of probability distributions. We draw upon recent work on online convex programming to devise an algorithm that does not require computing posterior distributions given all current observations, involves simple primal-dual parameter updates, and achieves minimax per-round regret against slowly varying product distributions with marginals drawn from the same exponential family. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality.

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

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

U2 - 10.1109/ISIT.2009.5205929

DO - 10.1109/ISIT.2009.5205929

M3 - Conference contribution

AN - SCOPUS:70449503911

SN - 9781424443130

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1338

EP - 1342

BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009

T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009

Y2 - 28 June 2009 through 3 July 2009

ER -