Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$30,000.00

Entropy Optimization and Lorentzian Polynomials

EF 2024-25

Résumé
The recent breakthrough approximation technique for the traveling salesperson problem, the groundbreaking work of 2022 Fields medalist June Huh, and new powerful generative language models like OpenAI's GPT-3: what do they have in common? The answer is entropy optimization, and my goal is to study it and understand its role in such a diverse set of contexts. Entropy is a fundamental concept in the way that we think about the world today. The notion of entropy is used to describe the "randomness" of something - the more unstructured or random something is, the higher the entropy. Thus when approaching a situation where we have limited knowledge, we can model what we do not know by assuming that the entropy is high. Many fields that attempt to model phenomena in the world - finance, physics, engineering, statistics, and beyond - use this strategy when dealing with error terms in their models. Modeling error in this way is a centuries-old practice, and it has been crucial to our understanding of the universe. Entropy then also appears in an important way in mathematics and computer science (CS). One goal of these fields, put simply, is to count things which are difficult to count. We categorize structures based upon their different features, and we hope to count or approximate the number of structures which have certain properties. This connects to famous CS problems such as the traveling salesperson problem, to pure math problems such as computing volume and counting network/graph structures, and to applied problems such as guaranteeing privacy of data sampling and measuring quality of language models in machine learning. Entropy factors into these problems as it does in error modeling: where we assume less structure, we assume higher entropy. To obtain provable bounds and approximations, we then maximize the entropy using optimization techniques. This leads to approximation algorithms, and sometimes even to explicit bounds for hard counting problems. This technique utilizes the theory of Lorentzian polynomials (recently developed in the work of Fields medalist June Huh), which turns counting problems into calculus problems where optimization techniques can be used. My goal then is to study these techniques via three main objectives. First I will utilize these techniques to improve and generalize current CS applications, including improving the entropy optimization bounds used for the traveling salesperson problem. Second I will further develop these techniques for Lorentzian polynomials and generalizations, including applications to computing volumes, counting integer points of geometric objects, and beyond. Third I will explore applications to applied/industry problems, including the use of entropy maximization in machine learning applications like generative language and image models. Through these objectives, I hope to more fully understand the underlying importance of the concept of entropy in math and CS, and in our world more generally.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2023-03726
Name nom
Leake, Jonathan
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
30000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Entropy Optimization and Lorentzian Polynomials
Keywords
maximum entropy; lorentzian polynomials; combinatorial optimization; discrete approximation; log-concavity; traveling salesperson problem; optimal transport; matroids; stable polynomials; polynomial capacity
Application summary
The recent breakthrough approximation technique for the traveling salesperson problem, the groundbreaking work of 2022 Fields medalist June Huh, and new powerful generative language models like OpenAI's GPT-3: what do they have in common? The answer is entropy optimization, and my goal is to study it and understand its role in such a diverse set of contexts. Entropy is a fundamental concept in the way that we think about the world today. The notion of entropy is used to describe the "randomness" of something - the more unstructured or random something is, the higher the entropy. Thus when approaching a situation where we have limited knowledge, we can model what we do not know by assuming that the entropy is high. Many fields that attempt to model phenomena in the world - finance, physics, engineering, statistics, and beyond - use this strategy when dealing with error terms in their models. Modeling error in this way is a centuries-old practice, and it has been crucial to our understanding of the universe. Entropy then also appears in an important way in mathematics and computer science (CS). One goal of these fields, put simply, is to count things which are difficult to count. We categorize structures based upon their different features, and we hope to count or approximate the number of structures which have certain properties. This connects to famous CS problems such as the traveling salesperson problem, to pure math problems such as computing volume and counting network/graph structures, and to applied problems such as guaranteeing privacy of data sampling and measuring quality of language models in machine learning. Entropy factors into these problems as it does in error modeling: where we assume less structure, we assume higher entropy. To obtain provable bounds and approximations, we then maximize the entropy using optimization techniques. This leads to approximation algorithms, and sometimes even to explicit bounds for hard counting problems. This technique utilizes the theory of Lorentzian polynomials (recently developed in the work of Fields medalist June Huh), which turns counting problems into calculus problems where optimization techniques can be used. My goal then is to study these techniques via three main objectives. First I will utilize these techniques to improve and generalize current CS applications, including improving the entropy optimization bounds used for the traveling salesperson problem. Second I will further develop these techniques for Lorentzian polynomials and generalizations, including applications to computing volumes, counting integer points of geometric objects, and beyond. Third I will explore applications to applied/industry problems, including the use of entropy maximization in machine learning applications like generative language and image models. Through these objectives, I hope to more fully understand the underlying importance of the concept of entropy in math and CS, and in our world more generally.