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

人类收集和处理系统、环境和人口数据的能力总是有限的。 智能体根据关于世界的部分、嘈杂的信息实时行动，通过“学习”消除不确定性往往必须与某些目标的优化相平衡。 现在所做选择的成本必须与这些选择在未来可能带来进一步成本的风险相权衡。 信息论为量化和管理不确定性提供了一个丰富而肥沃的框架。 当不同的信息片段承担不同的成本时，情况变得更加微妙。想想一个人退休后的401（k）计划。 虽然最低有效位是最不确定的，但错误地预测最高有效位的值会带来更多的成本。本项目涉及概率空间，该空间具有描述不确定性相关成本的度量。 在这种情况下，设计优化算法与拥有强大的度量信息理论密切相关。 此外，在线优化和竞争分析的设置提供了一套深入而多样的正式模型，在其中应用这些方法并测试其有效性。 在一个算法设计和分析经常被视为特别和非结构化的领域，这项工作的基础框架认为，算法和它们的分析都可以很容易地从正确的基础定义中推导出来。 事实上，这一领域的许多问题已经研究了30-40年，但在线凸优化算法和分析工具的初步应用-在度量概率空间的背景下-已经取得了一系列突破。 该研究小组将开发相应的理论，由一系列突出的开放性问题的指导下，与理解在什么情况下，并在何种程度上，一个可以限制优化的不确定性的有害影响的最终目标。这个奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

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.