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

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

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.