The classical dynamic Schrödinger Bridge (dSB) problem, which seeks the most likely stochastic evolution between two marginal probability distributions, has been extensively studied in optimal transport and statistical physics, and more recently in the machine learning community due to its connections with generative modeling. The dSB is equivalent to the static Schrödinger Bridge (sSB), which can be framed as a matrix optimization problem: it seeks a matrix with prescribed row and column sums that is closest to a given reference matrix. In the classical setting, this closeness is measured using the Kullback-Leibler (KL) divergence, but the framework can be generalized to allow any strictly increasing divergence functional.

This generalized sSB framework unifies a wide range of seemingly unrelated problems, including entropic optimal transport, matrix scaling, contingency table inference, and graph realization with prescribed degree sequences. Recent advances show that Sinkhorn-type algorithms for generalized sSB problems exhibit fast linear convergence—even in settings without closed-form updates, as in the KL divergence case. These developments open the door to tailoring divergence functionals adaptively for different problem domains.

The proposed REU program will explore both practical and theoretical aspects of the generalized Schrödinger Bridge problem. On the practical side, students will begin by implementing the Diffusion Schrödinger Bridge and applying it to image generation tasks, such as unpaired image translation. We will then extend the framework to incorporate general divergence functionals, investigating whether this added flexibility offers advantages for specific tasks. Additional experiments will include video generation in a multi-marginal Schrödinger Bridge framework.

On the theoretical side, while the generalized static SB framework connects many classical problems, their dynamic counterparts have so far been studied primarily within the original dSB setting. We will investigate the mathematical properties of dynamic generalizations of sSB in domains such as contingency tables and graphs with prescribed degree sequences.

• Dates June 15 – August 14, 2025
• Format In-person / online at UW–Madison
• Stipend $4,000
• Eligibility Current UW–Madison undergraduates

Across diverse scientific domains, networks are employed to illustrate interactions within complex systems. Examples abound in fields such as physics, biology, sociology, and information science. Many significant scientific inquiries involve processing data on networks, where the objective is to analyze a group of entities whose interactions are represented by large-scale, often sparse, network data. Tasks include community detection, subgraph approximation and classification, network comparison, link prediction, vertex nomination, crowd-sourced graph clustering, analysis of opinion dynamics, and prediction of synchronization in coupled oscillators and power networks. Consequently, there is a growing demand to devise methodologies and theoretical frameworks for analyzing large datasets with network structure, where each data point, often high-dimensional, represents a node in the network.

In this summer REU project, the team will take an interdisciplinary approach to investigate various machine learning techniques to analyze data sets on networks. The key point will be to sample a large number of small-sized instances of data with sub-network structure and learn patterns from them by using various machine learning methods. We will investigate ways to extract signatures from large networks and use them to predict the signature of an unknown network. For instance, we may ‘regress’ the SARS-Cov-2 protein-protein interaction (PPI) network as a ‘linear combination’ of known ones (e.g., SARS and MERS PPI networks) and infer unknown characteristics or functions of the new network.

• Dates July 1 – August 31, 2024
• Format In-person at UW–Madison
• Stipend $4,000
• Eligibility Current UW–Madison undergraduates

If a group of people is given local clocks with arbitrarily set times, and there is no global reference (for example GPS), is it possible for the group to synchronize all clocks by only communicating with nearby members? In order for a distributed system to be able to perform high-level tasks that may go beyond the capability of an individual agent, the system must first solve a “clock synchronization” problem to establish a shared notion of time. The study of clock synchronization (or coupled oscillators) has been an important subject of research in mathematics and various areas of science for decades, with fruitful applications in many areas including wildfire monitoring, electric power networks, robotic vehicle networks, large-scale information fusion, and wireless sensor networks. However, there has been a gap between our theoretical understanding of systems of coupled oscillators and practical requirements for clock synchronization algorithms in modern application contexts. This project will develop systematic approaches for bridging this gap based on combinatorial, probabilistic, and machine learning methods.

Suppose we are given a system of coupled oscillators on an unknown graph along with the trajectory of the system during some short period. Can we predict whether the system will eventually synchronize? Even with known underlying graph structure, this is an important but analytically intractable question in general. In a paper resulting from a past REU project (L2PSync), we take a novel approach that we call “learning to predict synchronization” (L2PSync), by viewing the synchronization prediction problem as a classification problem for sets of initial dynamics into two classes: ‘synchronizing’ or ‘non-synchronizing’. While a baseline predictor using concentration principle misses a large proportion of synchronizing examples, standard binary classification algorithms trained on large enough datasets of initial dynamics can successfully predict the unseen future of a system on highly heterogeneous sets of unknown graphs with surprising accuracy. In addition, we find that the full graph information gives only marginal improvements over what we can achieve by only using the initial dynamics.

In this REU project, we will investigate various open problems in related topics. One of the main open questions is why/how simple classification algorithms significantly outperform what oscillator theory predicts. What kind of separation between synchronizing and non-synchronizing examples do they see? Can we (humans) learn what machine learning algorithms learned from a massive amount of data and use it to advance our theoretical understanding of coupled oscillators? A possible approach is to use yet another class of machine learning methods of supervised feature extraction to let them tell us what they see.

• Dates July 1 – August 31, 2022
• Format In-person at UW–Madison
• Stipend $4,000
• Support NSF DMS-2010035

If a group of people is given local clocks with arbitrarily set times, and there is no global reference (for example GPS), is it possible for the group to synchronize all clocks by only communicating with nearby members? In order for a distributed system to be able to perform high-level tasks that may go beyond the capability of an individual agent, the system must first solve a “clock synchronization” problem to establish a shared notion of time. The study of clock synchronization (or coupled oscillators) has been an important subject of research in mathematics and various areas of science for decades, with fruitful applications in many areas including wildfire monitoring, electric power networks, robotic vehicle networks, large-scale information fusion, and wireless sensor networks. However, there has been a gap between our theoretical understanding of systems of coupled oscillators and practical requirements for clock synchronization algorithms in modern application contexts. This project will develop systematic approaches for bridging this gap based on combinatorial and probabilistic methods. The use of discrete oscillators will be a key thread in developing more robust and efficient clock synchronization algorithms, extending the current proof techniques for convergence guarantee, and providing a foundation for a data-driven approach to the clock synchronization problems.

During the 8-weeks long summer REU 2020 project, the team will take an interdisciplinary approach to the problem of oscillator and clock synchronization using some of the modern machine learning techniques and a family of discrete oscillators due to the PI (called the Firefly Cellular Automata).

• Dates June 1 – August 1, 2020
• Format Online (UCLA)
• Support NSF DMS-2010035