Learning for Optimization

Recently, neural approaches have shown promise in tackling (combinatorial) optimization problems in a data-driven manner. On the other hand, for many problems, especially geometric optimization problems, many beautiful geometric ideas and algorithmic insights have been developed in fields such as theoretical computer science and computational geometry. Our goal is to infuse geometric and algorithmic ideas to the design of neural frameworks so that they can be more effective and generalize better. One line of work in PI Wang’s team is to explore (a) how to design better neural models suitable to a given problem with certain guarantees, and (b) how to use algorithmic ideas to guide the design of neural models.

In particular, for (a) Wang and her team considered the problem of approximating Wasserstein distance between point sets in a metric space (e.g., the Euclidean space). The Wasserstein distance, a special case of the optimal transport distance, is widely used in machine learning, e.g., in GANs. Their goal is to have a neural model of bounded size independent of input size, yet with the guarantee to have the capacity to approximately solve the problem. To this end, in [Chen & Wang, NeurIPS 2023] they designed a Siamese network based neural model, combining ideas from generating specific types of symmetric functions over product spaces, as well as a geometric sketching idea. In related work ([Chen, Tabaghi & Wang, AAAI 2024]), they show how to learn a tree-metric to efficiently approximate optimal transport distance.

For (b), in [Kahng et al., AAAI 2024] we propose using a mixed-algorithmic neural framework to tackle the hard combinatorial optimization problem, such as the minimal Steiner Tree problem in the Euclidean setting. This problem is motivated by applications in Chip Design. One of the key ideas is to use a high-level algorithmic framework, where a constant number of components within this framework are replaced by neural networks of bounded size (again, independently of input size!). The advantage is that no matter how big the input instances are, those neural components will always operate on problems of bounded sizes and therefore are fixed. Note that these neural components could be called by the outer-algorithm multiple times (depending on input size potentially). Once these neural components are learned, this mixed neural-algorithmic framework can be applied to input of arbitrary size. Indeed, in practice, they generalize well.