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.

人类收集和处理DataAbout系统，环境和人群的能力总是会有局限性。 算法代理基于有关世界的部分嘈杂信息实时行动，而通过“学习”消除不确定性通常必须与某些目标的态度进行平衡。 目前做出的选择成本必须使这些选择可能在未来进一步产生成本的风险。 信息理论提供了一个丰富而肥沃的框架，用于量化和管理不确定性。 当信息的不同成本不同时，情况就会变得更加微妙。考虑一个人的401（k）平衡。 尽管最不重要的数字是最不确定的，但与错误地预测themost数字值的价值相关的成本更高。此项目涉及概率空间，并具有描述与不确定性相关的成本的度量。 设计算法以在此类Aframework中进行优化，这与具有强大的度量理论密切相关。 此外，在线优化和竞争分析的设置提供了一套深厚而多样的正式模型，在其中应用这些方法并测试其功效。 在一个算法设计和分析通常被视为临时和非结构化的领域中，这项工作的框架认为，算法及其分析都可以从正确的基本定义集中依赖。 实际上，该领域的许多问题已经研究了30 - 40年，在在线凸的算法和分析工具的Andyet初步应用 - 在指标概率空间的背景下 - 已经达到了突破的序列。 研究人员团队将发展相应的理论，并以突出的开放问题集合为指导，其最终目标是在什么情况下理解，并且在何种程度上，人们可以限制不确定性对优化的有害影响。这项奖项反映了NSF的法定任务，并通过使用该基金会的知识分子优点和广泛的影响来评估NSF的法定任务，并被视为值得进行的支持。

项目成果

Spectral dimension, Euclidean embeddings, and the metric growth exponent

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

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

Relations between scaling exponents in unimodular random graphs

• DOI: 10.1007/s00039-023-00654-7
• 发表时间: 2020-07
• 期刊: 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-01-01
• 期刊: 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS)
• 作者: Haah, Jeongwan;Kothari, Robin;Tang, Ewin
• 通讯作者: Tang, Ewin

Leibniz International Proceedings in Informatics (LIPIcs):13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

莱布尼茨国际信息学会议录 (LIPIcs)：第 13 届理论计算机科学创新会议 (ITCS 2022)

• DOI: 10.4230/lipics.itcs.2022.60
• 发表时间: 2022
• 期刊: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• 作者: Ebrahimnejad, Farzam;Lee, James R.
• 通讯作者: Lee, James R.

Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

基于采样的次线性低秩矩阵算术框架用于反量化量子机器学习

• DOI: 10.1145/3549524
• 发表时间: 2022
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Chia, Nai-Hui;Gilyén, András Pal;Li, Tongyang;Lin, Han-Hsuan;Tang, Ewin;Wang, Chunhao
• 通讯作者: Wang, Chunhao