Minimax redundancy through accumulated estimation error

摘要

Minimax expected redundancies over memoryless source classes ofsmooth densities are studied, through their connections with accumulatedprediction errors and using available techniques from nonparametricstatistics. To derive lower bounds on the minimax expected redundancyrates, two methods are used and compared. One is the Assouad's techniquefrom statistical density estimation and the other is theinformation-theoretic (generalized) Fano's inequality. Both methods areapplied to hypercube sub-classes and a connection between Assouad's andFano's is established using a packing number result fromerror-correcting coding theory. Finally, optimal (rate) codes, whichachieve the minimax rate lower bounds on expected redundancy, are formedbased on optimal density estimators