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

AF：小：度量信息论、在线学习和竞争分析

• 批准号: 2007079
• 负责人: James Lee
• 金额: $ 40万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007079&HistoricalAwards=false
• 关键词: AF; Small; Metric; Information; Theory

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.

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

项目成果

Chemical Subdiffusivity of Critical 2D Percolation

临界二维渗流的化学子扩散率

• DOI: 10.1007/s00220-021-04222-8
• 发表时间: 2020-05-18
• 期刊: Communications in Mathematical Physics
• 影响因子: 2.4
• 作者: S. Ganguly;James R. Lee
• 通讯作者: James R. Lee

Spectral dimension, Euclidean embeddings, and the metric growth exponent

谱维数、欧几里德嵌入和度量增长指数

• DOI: 10.1007/s11856-023-2520-x
• 发表时间: 2023-09
• 期刊: Israel Journal of Mathematics
• 影响因子: 1
• 作者: Lee; James R.
• 通讯作者: James R.

Relations between scaling exponents in unimodular random graphs

幺模随机图中标度指数之间的关系

• DOI: 10.1007/s00039-023-00654-7
• 发表时间: 2020-07-13
• 期刊: Geometric and Functional Analysis
• 影响因子: 2.2
• 作者: James R. Lee

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

高温吉布斯态量子哈密顿量的优化学习

• DOI: 10.1109/focs54457.2022.00020
• 发表时间: 2022-10
• 期刊: IEEE
• 作者: Haah, Jeongwan;Kothari, Robin;Tang, Ewin
• 通讯作者: Tang, Ewin

Non-Existence of Annular Separators in Geometric Graphs

几何图中不存在环形分隔符

• DOI: 10.1007/s00454-023-00519-8
• 发表时间: 2023-06
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Ebrahimnejad, Farzam;Lee, James R.
• 通讯作者: Lee, James R.