Summer 2022 REU program on “Machine learning approaches to oscillator and clock synchronization”
- PI: Hanbaek Lyu (Department of Mathematics, UW-Madison; hlyu@math.wisc.edu)
- Program support: NSF Grant DMS-2010035
- Program duration: Jul. 1, 2022 – Aug. 31, 2022 (Full time)
- Location: UW-Madison (In person)
- Participants: Bella Wu (Stats), Agam Goyal (CS), Binhao Chen (Math), Bryan Xu (Math)
- Project Report REU2022
- Slides: Interpretable_ML_for_Synchronization
Program Description:
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 resulted from a past REU project (in 2022 virtually at UCLA, see https://arxiv.org/pdf/2012.14048.pdf), 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 the upcoming REU project that will be held in summer 2022 at UW-Madison (in person), we will investigate various open problems in related topics. One of the main open questions is why/how simple classification algorithms significantly outperforms what oscillator theory predicts. What kind of separation between synchornizing and non-synchronizing examples do they see? Can we (human) 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.
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) as well as the standard continuous model called the Kuramoto oscillators.
Minimum experience in python programming and dynamical systems is required.
==================================================
- PI: Hanbaek Lyu (Department of Mathematics, UCLA; hlyu@math.ucla.edu)
- Program support: NSF Grant DMS-2010035
- Program duration: June 1, 2020 – Aug. 1, 2020 (Full time)
- Location: Online
- Participants: Hardeep Bassi, Richard Yim, Rohith Kodukula, Joshua Vendrow, Cherlin Zhu
- Hardeep Bassi*, Richard Yim*, Rohith Kodukula*, Joshua Vendrow*, Cherlin Zhu*, Hanbaek Lyu, “Learning to predict synchronization of coupled oscillators on randomly generated graphs.” To appear in Scientific Reports [Preprint, GitHub] (2020)
PI: Hanbaek Lyu
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).
Minimum experience in python programming and dynamical systems is required.
Hanbaek Lyu 