Emergence Dynamics: Optimization, Transformers and sparse Graphs
Abstract
Emergent behavior is encountered in collective dynamics of biological and ecological systems, in human activities and with other mechanical systems in which local interactions of self-driven particles or agents emerge into higher-order structures, so that "thewhole is greater than the sum of its parts . The last 20 years witnessed an intense activity in developing mathematical framework in this direction. The PI of this proposal was actively involved in leading such research activity. The overall goal of this proposal is to investigate applications of collective dynamics in four major directions.(i) Optimization # emergence of minimzers. The distinctive feature of our swarm-based approach is agents which are tagged by both their position and their mass. Mass is used as a communication platform between `lighter explorers# at high ground and #heavier leaders# at lower ground. Lighter explorers lead the swarm into improved position with large(r) time steps, randomly increasing orientation, or by increasing their temperature, or "annealing-rate of Brownian motion. We propose a general protocol of communication for swarm-based optimization which paves the way to a new class of mean-field description for such swarm-based dynamics. (ii) Emergent behavior of Transformers. Transformers play a central role in neural network architectures. The mathematical framework for analyzing transformers is based on their interpretation as interacting particle systems determined by the (Query, Key, Value) parameter matrices learned from data. The longtime dynamics results in emergence of clusters, dictated by the fine properties of these eigen-structure. We propose to develop a systematic approach to study the collective dynamics governed by such (Q,K,V) systems. The key feature is the double-exponential re-scaling which lends itself to alignment dynamics with local interactions. However, the interactions are not metric.(iii) The emergence of Ramanujan graphs. The (almost)-Ramanujan graphs are discrete objects which attracted much interest for their `"elasticity : these are sparse graphs which encode high-degree of connectivity. This part of our research points out to a remarkable discovery, that such (almost-)Ramanujan graphs emerge out of the longtime alignment dynamics, governed by highly oscillatory interactions. We propose to study this remarkable dynamics. Specifically --- one needs to trace the time behavior of spectral gap of the underlying graph dictated by first-order alignment dynamics.(iv) The distance problem. Emergence of time-line in noisy data. The distance problem seeks to recover the position of N points in R^d from their relative distances, {D_{ij}}_{i,j=1}^N. The case of $d=1$ is of particular interest:here one seeks to sort the time line in noisy data: the only access to the data is through their relative distances, D_{ij}, in thetime line of these `events . Ideally, these are `lined along the 1D time line, but the noisy time-line requires a different processing mechanism. We propose to continue our ongoing investigation of the "Wanderlust algorithm which was introduced as an ad-hoc algorithms in the early 2010s. Our approach recast the problem as a repulsion/attraction dynamics and we will study its optimal timeprotocol for reaching its large-time "consensus .In summary, our research plan is to investigate analyze applications of alignment dynamics and their large time behavior, offering a new paradigms of emergent phenomena in optimization, neural networks, sparse graphs and the noisy distance problem with incomplete data.This abstract is Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412659
Entities
People
- Eitan Tadmor
Organizations
- Office of Naval Research
- United States Navy
- University of Maryland