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

点击翻译按钮获取中文摘要

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.