Online Estimation via Offline Estimation: An Information-Theoretic Framework

$ $Theclassicaltheoryofstatisticalestimationaimstoestimateaparameterofinterestunderdatageneratedfromafixeddesign(\mathrm{"}offlineestimation\mathrm{"}),whilethecontemporarytheoryofonlinelearningprovidesalgorithmsforestimationunderadaptivelychosencovariates(\mathrm{"}onlineestimation\mathrm{"})\mathrm{.}Motivatedbyconnectionsbetweenestimationandinteractivedecisionmaking,weask:isitpossibletoconvertofflineestimationalgorithmsintoonlineestimationalgorithmsinablack-boxfashion?Weinvestigatethisquestionfromaninformation-theoreticperspectivebyintroducinganewframework,Oracle-EfficientOnlineEstimation(OEOE),wherethelearnercanonlyinteractwiththedatastreamindirectlythroughasequenceofofflineestimatorsproducedbyablack-boxalgorithmoperatingonthestream\mathrm{.}Ourmainresultssettlethestatisticalandcomputationalcomplexityofonlineestimationinthisframework\mathrm{.}$\bullet$Statisticalcomplexity\mathrm{.}Weshowthatinformation-theoretically,thereexistalgorithmsthatachievenear-optimalonlineestimationerrorviablack-boxofflineestimationoracles,andgiveanearly-tightcharacterizationforminimaxratesintheOEOEframework\mathrm{.}$\bullet$ Computational complexity. We show that the guarantees above cannot be achieved in a computationally efficient fashion in general, but give a refined characterization for the special case of conditional density estimation: computationally efficient online estimation via black-box offline estimation is possible whenever it is possible via unrestricted algorithms. Finally, we apply our results to give offline oracle-efficient algorithms for interactive decision making.