Technical Reports

HPL-2012-114

Click here for full text: PDF

Piecewise Constant Prediction

Ordentlich, Erik; Weinberger, Marcelo J.; Wu, Yihong
HP Laboratories

HPL-2012-114

Keyword(s): prediction; data compression; minimax strategies; universal schemes

Abstract: Minimax prediction of binary sequences is investigated for cases in which the predictor is forced to issue a piecewise constant prediction. The minimax strategy is characterized for Hamming loss whereas, for logarithmic loss, an asymptotically minimax strategy which achieves the leading term of the asymptotic minimax redundancy, is proposed. The average redundancy case is also analyzed for i.i.d. distributions. The piecewise constant prediction paradigm may be of relevance to resource constrained settings.

5 Pages

External Posting Date: May 21, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: May 21, 2012 [Fulltext]

Back to Index