权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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
通讯作者：
James R. Lee

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.
通讯作者：
Lee, James R.

Spectral Hypergraph Sparsification via Chaining

通过链接进行光谱超图稀疏化

DOI：
10.1145/3564246.3585165
发表时间：
2023
期刊：
ACM
影响因子：
0
作者：
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

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

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