Transportation Cost Spaces and Group Actions on Banach Spaces

In machine learning and AI applications such as image recognition, document retrieval, and classification tasks, it is essential to have a good measure of similarity between the objects of interest, such as images or text documents. The ability to compare objects and evaluate the efficiency of compression schemes enables the design of smarter systems that achieve better performance using less information. Often these objects are represented as distributions over a set of points in a metric space. For instance, an image maybe viewed as a distribution of pixel colors, and a text document as a distribution of words. The most natural measure of similarity between distributions is the Wasserstein -- or earth mover -- metric, and this metric has become part of the standard toolkit in machine learning and AI. The main goals of this project are centered around theoretical foundations to improve AI systems with more efficient computational approximations of the Wasserstein metric: sharpening and finding new techniques for approximations and proving impossibility results for certain classes of approximations. Additional project objectives include student mentorship and integration and dissemination of results between functional analysis and computer science/computational mathematics communities through seminar and conference organization. One of the fundamental ways in which the Wasserstein metric is studied is through its linear counterpart, the transportation cost space. The efficient approximations sought are low-distortion embeddings of the transportation cost space into the Banach space L1. The current method by which these embeddings are obtained is through stochastic embeddings into dominating tree metrics. The PI works to clarify the precise relationship between embeddability of the transportation cost space into L1, stochastic embeddability into trees of the underlying metric space, and intrinsic geometric properties of the underlying metric space, such as its isoperimetric profile. Potential contributions of this theory include development of techniques to stochastically approximate a given metric by tree metrics. In addition to the aforementioned applications in transportation cost theory, this will have implications for a variety of other algorithmic problems that are metric in nature. A second goal of the project concerns applications to analytic group theory. Some of the most important concepts in this field, such as Property (T) and the Haagerup property, can be formulated in terms of linear actions on Banach spaces. The PI adapts constructions arising in transportation cost theory in order to attack problems in group actions on Banach spaces, such as whether every hyperbolic group satisfies a weak version of the Haagerup property. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.