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

University Of Washington, Seattle WA

Investigators

Abstract

There will always be limitations on human ability to collect and process data about systems, environments, and populations. Algorithmic agents act in real time based on partial, noisy information about the world, and the elimination of uncertainty through "learning" must often be balanced against the optimization of some objective. The cost of choices made in the present must be weighed against the risk that those choices might incur further costs in the future. Information theory provides a rich and fertile framework for quantifying and managing uncertainty. The situation becomes more subtle when distinct pieces of information carry differing costs. Consider one's 401(k) balance at retirement. While the least significant digit is most uncertain, there is substantially more cost associated with incorrectly predicting the value of the most significant digit. This project concerns probability spaces endowed with a metric that describes the associated cost of uncertainty. Designing algorithms to optimize in such a framework is intimately connected to having a robust theory of metric information. Moreover, the settings of online optimization and competitive analysis provide a deep and varied set of formal models in which to apply these methods 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 be derived readily from the right set of underlying definitions. Indeed, many problems in this area have been researched for 30-40 years, and yet preliminary application of algorithms and analysis tools from online convex optimization--in the context of metric probability spaces--has already achieved a sequence of breakthroughs. The team of researchers will develop the corresponding theory, guided by a collection of prominent open problems, with the 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.