AF: Small: Metric Information Theory, Online Learning, and Competitive Analysis

点击翻译按钮获取中文摘要

There will always be limitations on human ability to collect and process dataabout systems, environments, and populations. Algorithmic agents act in realtime based on partial, noisy information about the world, and the eliminationof uncertainty through "learning" must often be balanced against theoptimization of some objective. The cost of choices made in the present mustbe weighed against the risk that those choices might incur further costs inthe future. Information theory provides a rich and fertile framework for quantifying andmanaging uncertainty. The situation becomes more subtle when distinct piecesof information carry differing costs. Consider one's 401(k) balance atretirement. While the least significant digit is most uncertain, there issubstantially more cost associated with incorrectly predicting the value of themost significant digit.This project concerns probability spaces endowed with a metric that describesthe associated cost of uncertainty. Designing algorithms to optimize in such aframework is intimately connected to having a robust theory of metricinformation. Moreover, the settings of online optimization and competitiveanalysis provide a deep and varied set of formal models in which to apply thesemethods and test their efficacy. In an area where algorithm design and analysis have often been seen as ad-hoc and unstructured, the framework underlying this work contends that both algorithms and their analysis can bederived readily from the right set of underlying definitions. Indeed, many problems in this area have been researched for 30-40 years, andyet preliminary application of algorithms and analysis tools from online convexoptimization--in the context of metric probability spaces--has already achieveda sequence of breakthroughs. The team of researchers will develop the corresponding theory, guided by a collection of prominent open problems, withthe ultimate goal of understanding in what circumstances, and to what extent, one can limit the detrimental effects of uncertainty on optimization.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.