AF: Small: Entropy Maximization in Approximation, Learning, and Complexity

AF：小：近似、学习和复杂性中的熵最大化

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

Entropy plays a distinguished role in the world. The second law of thermodynamics tell us that, in closed systems, entropy always increases; it is maximized at thermodynamic equilibrium. Given a collection of data, the "principle of maximum entropy" asserts that, among all hypothetical probability distributions that agree with the data, the one of maximum entropy best represents the current state of knowledge.Moreover, if one considers a convex set of probability distributions, the problem of maximizing a strongly concave function (like the Shannon entropy) over this set is computationally tractable and has a unique optimal solution. This project is concerned with the structure and computational utility of entropy maximizers in algorithm design, machine learning, complexity theory, and related areas of discrete mathematics. In particular, the project will study the role of entropy maximization in encouraging simplicity in the optimum solution. This property stands to reason: The entropy maximizer should intuitively contain only the information implied by the constraints and nothing more.The scope of the project includes not only classical entropy functionals like the Shannon entropy and Kullback-Leibler divergence, but also the analogous notions for quantum states (von Neumann entropy). The study of quantum entropy maximizers has far-reaching applications in semi-definite programming and communication complexity. Moreover, much of the theory extends to other Bregman divergences, and this is particularly relevant for applications in online algorithms where certain smoothed entropy functionals become relevant. A portion of the project concerns entropy optimality on path spaces. This perspective provides a novel view of Markov processes on discrete and continuous spaces. The PI will employ this viewpoint to study rapid mixing of Markov chains, as well smoothing properties of the noise operator on the discrete hypercube (a topic with remarkable applications in complexity theory and hardness of approximation).Finally, it should be mentioned that iterative algorithms for finding entropy maximizers can be viewed in the framework of entropy-regularized gradient descent; such algorithms are fundamental in machine learning (boosting) and online convex optimization (multiplicative weights update). This provides a powerful connection to large bodies of work, and a substantial motivation for the project is to create a bridge of ideas and techniques between the two perspectives.Broader impact of the project includes training of the next generation of scientists, including at the undergraduate level. This project presents a number of opportunities for undergraduate researchers to contribute in a meaningful and substantial way, while at the same time receiving valuable mentoring and experience as developing scientists.

熵在世界上起着杰出的作用。 热力学的第二定律告诉我们，在封闭的系统中，熵总是增加。它在热力学平衡时最大化。 Given a collection of data, the "principle of maximum entropy" asserts that, among all hypothetical probability distributions that agree with the data, the one of maximum entropy best represents the current state of knowledge.Moreover, if one considers a convex set of probability distributions, the problem of maximizing a strongly concave function (like the Shannon entropy) over this set is computationally tractable and has a unique optimal solution. 该项目与算法设计，机器学习，复杂性理论以及离散数学相关领域中熵最大化器的结构和计算实用性有关。 特别是，该项目将研究熵最大化在鼓励最佳解决方案中的简单性中的作用。 该属性是理性的：熵最大化器应直观地包含约束所隐含的信息，而仅此而已。该项目的范围不仅包括Shannon Entrody和Kullback-Lebler Divergence等经典熵功能，还包括量子状态的类似概念（VonNeumann Entropy）。 量子熵最大化器的研究在半准编程和通信复杂性中具有深远的应用。 此外，许多理论都扩展到其他布雷格曼的分歧，这与某些平滑熵功能变得相关的在线算法中的应用尤其重要。 该项目的一部分涉及路径空间上的熵最优性。 这种观点为离散和连续空间的马尔可夫过程提供了一种新颖的看法。 PI将采用该观点来研究马尔可夫链的快速混合，以及噪声操作员在离散超立方体上的平滑特性（在复杂性理论中具有显着应用的主题和近似值的硬度）。在本质上，应提到，迭代算法可以在寻找入围性最大化的框架中查看框架的框架。这种算法在机器学习（增强）和在线凸优化（乘法权重更新）中至关重要。 这为大型工作机构提供了有力的联系，该项目的实质性动机是在两个观点之间建立思想和技术的桥梁。该项目的影响包括对下一代科学家的培训，包括在本科层面。 该项目为本科研究人员提供了许多以有意义和实质性的方式做出贡献的机会，同时也获得了作为发展科学家的宝贵指导和经验。