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.

熵在世界上扮演着重要的角色。热力学第二定律告诉我们，在封闭系统中，熵总是增加的；它在热力学平衡时达到最大值。给定一组数据，“最大熵原理”断言，在所有与数据一致的假设概率分布中，最大熵的概率分布最能代表当前的知识状态。此外，如果考虑概率分布的凸集，则在此集上最大化强凹函数（如香农熵）的问题在计算上是可处理的，并且具有唯一的最优解。该项目关注的是算法设计、机器学习、复杂性理论和离散数学相关领域中熵最大化器的结构和计算效用。特别是，该项目将研究熵最大化在鼓励最优解决方案的简单性方面的作用。这个属性是有道理的：熵最大化器应该直观地只包含约束所暗示的信息，而不是其他信息。该项目的范围不仅包括经典熵函数，如香农熵和Kullback-Leibler散度，还包括量子态的类似概念（冯·诺伊曼熵）。量子熵最大化器的研究在半确定规划和通信复杂性方面具有深远的应用。此外，许多理论延伸到其他布雷格曼分歧，这是特别相关的应用在在线算法中，某些平滑的熵函数变得相关。项目的一部分涉及路径空间上的熵最优性。这一观点为离散和连续空间上的马尔可夫过程提供了一种新的观点。PI将采用这一观点来研究马尔可夫链的快速混合，以及离散超立方体上噪声算子的平滑特性（这是一个在复杂性理论和近似硬度方面具有显著应用的主题）。最后，应该提到的是，寻找熵最大值的迭代算法可以在熵正则化梯度下降的框架中看待；这些算法是机器学习（增强）和在线凸优化（乘法权重更新）的基础。这为大量工作提供了强大的联系，项目的主要动机是在两种观点之间建立思想和技术的桥梁。该项目的更广泛影响包括培养下一代科学家，包括在本科水平。该项目为本科生研究人员提供了许多机会，以有意义和实质性的方式做出贡献，同时获得作为发展中的科学家的宝贵指导和经验。