KELLY SPENDLOVE
Montana

About.

Kelly

I currently work at Google on search ads auction mechanisms. Previously, I was a postdoctoral researcher at the Mathematical Institute of the University of Oxford in the Centre for Topological Data Analysis, mentored by Ulrike Tillmann FRS and Heather Harrington.

I completed my PhD in mathematics at Rutgers University under the direction of Konstantin Mischaikow, with the support of an NSF Graduate Fellowship. During my PhD, I was an NSF GROW Fellow at VU Amsterdam working with Rob Vandervorst, a long term visitor at the Mathematical Biosciences Institute, a visiting researcher at INRIA with Fred Chazal, and an NSF EAPSI Fellow at Kyoto University with Hiroshi Kokubu. Here is an (academic) CV (2021).

Research Interests.


My current research interests lie in the intersection of dynamical systems, (algorithmic) game theory, and mechanism/auction design. My background is in the development of mathematical theory and computational tools for the analysis of nonlinear and/or high-dimensional systems, primarily using applied topology or computational dynamics. In particular, computational Conley theory, connection matrix theory, and topological data analysis. For more details, see my google scholar page, papers or slides from my talks below.

preprints

With Rob Vandervorst.
Abstract: To capture the global structure of a dynamical system we reformulate dynamics in terms of appropriately constructed topologies, which we call flow topologies; we call this process topologization. This yields a description of a semi-flow in terms of a bi-topological space, with the first topology corresponding to the (phase) space and the second to the flow topology. A study of topology is facilitated through discretization, i.e. defining and examining appropriate finite sub-structures. Topologizing the dynamics provides an elegant solution to their discretization by discretizing the associated flow topologies. We introduce Morse pre-orders, an instance of a more general bi-topological discretization, which synthesize the space and flow topologies, and encode the directionality of dynamics. We describe how Morse pre-orders can be augmented with appropriate (co)homological information in order to describe invariance of the dynamics; this ensemble provides an algebraization of the semi-flow. An illustration of the main ingredients of the paper is provided by an application to the theory of discrete parabolic flows. Algebraization yields a new invariant for positive braids in terms of a bi-graded differential module which contains Morse theoretic information of parabolic flows.
Here is the arxiv preprint (2022).

With Shaun Harker and Konstantin Mischaikow.
Abstract: We introduce the notion of a template for discrete Morse theory. Templates provide a memory efficient approach to the computation of homological invariants (e.g., homology, persistent homology, Conley complexes) of cell complexes. We demonstrate the effectiveness of templates in two settings: first, by computing the homology of certain cubical complexes which are homotopy equivalent to Sd for 1 ≤ d ≤ 20, and second, by computing Conley complexes and connection matrices for a collection of examples arising from a Conley-Morse theory on spaces of braids diagrams.
Submitted. Here is the arxiv preprint (2021). A five minute presentation of the paper is available here.

publications

With Jason Milionis, Christos Papadimitriou and Georgios Piliouras.
Abstract: The Nash equilibrium - a combination of choices by the players of a game from which no self-interested player would deviate - is the predominant solution concept in game theory. Even though every game has a Nash equilibrium, it is not known whether there are deterministic behaviors of the players who play a game repeatedly that are guaranteed to converge to a Nash equilibrium of the game from all starting points. If one assumes that the players' behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this question becomes a problem in the theory of dynamical systems. We apply this theory, and in particular Conley index theory, to prove a general impossibility result: there exist games, for which all game dynamics fail to converge to Nash equilibria from all starting points. The games which help prove this impossibility result are degenerate, but we conjecture that the same result holds, under computational complexity assumptions, for nondegenerate games. We also prove a stronger impossibility result for the solution concept of approximate Nash equilibria: for a set of games of positive measure no game dynamics can converge to the set of approximate Nash equilibria for a sufficiently small yet substantial approximation bound. Our results establish that, although the notions of Nash equilibrium and its computation-inspired approximations are universally applicable in all games, they are fundamentally incomplete as predictors of long term player behavior.
Final version in the Proceedings of the National Academy of Sciences (PNAS) (2023). A conference version appeared in SAGT 2022. Here is the arxiv preprint (2022).

With Hannah Alpert, Uli Bauer, Matt Kahle, and Bob MacPherson.
Abstract: We study the configuration spaces C(n;p,q) of n labeled hard squares in a p by q rectangle, a generalization of the well-known "15 Puzzle". Our main interest is in the topology of these spaces. Our first result is to describe a cubical cell complex and prove that is homotopy equivalent to the configuration space. We then focus on determining for which n, j, p, and q the homology group Hj[C(n;p,q)] is nontrivial. We prove three homology-vanishing theorems, based on discrete Morse theory on the cell complex. Then we describe several explicit families of nontrivial cycles, and a method for interpolating between parameters to fill in most of the picture for "large-scale" nontrivial homology.
Final version in Algebraic and Geometric Topology (2023). arxiv (2022).

With Stefanos Leonardos and Georgios Piliouras.
Abstract: The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a prototypical learning model that explicitly captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality, in weighted zero-sum polymatrix games with heterogeneous learning agents using positive exploration rates. Complementing recent results about convergence in weighted potential games, we show that fast convergence of Q-learning in competitive settings is obtained regardless of the number of agents and without any need for parameter fine-tuning. As showcased by our experiments in network zero-sum games, these theoretical results provide the necessary guarantees for an algorithmic approach to the currently open problem of equilibrium selection in competitive multi-agent settings.
Spotlight at NeurIPS-21. Final version in the NeurIPS conference proceedings and the arxiv (2021).

With Shaun Harker and Konstantin Mischaikow.
Abstract: The connection matrix is a powerful algebraic topological tool from Conley index theory, a subfield of topological dynamics. Conley index theory is a purely topological generalization of Morse theory in which the connection matrix subsumes the role of the Morse boundary operator. Over the last few decades, Conley’s approach to dynamics has been cast into a purely computational form. In this paper we introduce a computational and categorical framework for connection matrix theory. Broadly speaking, this contribution promotes the computational Conley theory to a computational, homological theory for dynamical systems. More specifically, within this paper we have three specific aims:
1. We cast connection matrix theory in an appropriate categorical, homotopy-theoretic language. We demonstrate the relationship to the previous definitions of connection matrix. Lastly, the homotopy-theoretic language allows us to formulate connection matrix theory categorically.
2. We describe an algorithm for the computation of connection matrices based on algebraic-discrete Morse theory and formalized with the notion of reductions. We advertise an open-source implementation of our algorithm.
3. We show that the connection matrix can be used to compute persistent homology. Ultimately, we believe that connection matrix theory has the potential to be an important tool within topological data analysis.
Final version in the Journal of Applied and Computational Topology (2021) and the arxiv (2021).

With Bree Cummins and Tomas Gedeon.
Abstract: We present a theoretical framework for inferring dynamical interactions between weakly or moderately coupled variables in systems where deterministic dynamics plays a dominating role. The variables in such a system can be arranged into an interaction graph, which is a set of nodes connected by directed edges wherever one variable directly drives another. In a system of ordinary differential equations, a variable x directly drives y if it appears nontrivially on the right-hand side of the equation for the derivative of y. Ideally, given time series measurements of the variables in a system, we would like to recover the interaction graph. We introduce a comprehensive theory showing that the transitive closure of the interaction graph is the best outcome that can be obtained from state space reconstructions in a purely deterministic system. Our work depends on extensions of Takens' theorem and the results of Sauer et al. [J. Stat. Phys., 65 (1991), pp. 579--616] that characterize the properties of time-delay reconstructions of invariant manifolds and attractors. Along with the theory, we discuss practical implementations of our results. One method for empirical recovery of the interaction graph is presented by Sugihara et al. [Science, 338 (2012), pp. 496--500], called convergent cross-mapping. We show that the continuity detection algorithm of Pecora et al. [Phys. Rev. E, 52 (1995), pp. 3420--3439] is a viable alternative to convergent cross-mapping that is more consistent with the underlying theory. We examine two examples of dynamical systems for which we can recover the transitive closure of the interaction graph using the continuity detection technique. The strongly connected components of the recovered graph represent distinct dynamical subsystems coupled through one-way driving relationships that may correspond to causal relationships in the underlying physical scenario.
Final version in the SIAM Journal on Applied Dynamical Systems (2015).

With Jesse Berwald and Tomas Gedeon.
Abstract: Complex dynamical systems, from those appearing in physiology and ecology to Earth system modelling, often experience critical transitions in their behaviour due to potentially minute changes in their parameters. While the focus of much recent work, predicting such bifurcations is still notoriously difficult. We propoåse an active learning approach to the classification of parameter space of dynamical systems for which the codimension of bifurcations is high. Using elementary notions regarding the dynamics, in combination with the nearest-neighbour algorithm and Conley index theory to classify the dynamics at a predefined scale, we are able to predict with high accuracy the boundaries between regions in parameter space that produce critical transitions.
Final version in Mathematical and Computer Modelling of Dynamical Systems (2013).

talks

slides | video for an introductory talk on Conley-Morse theory for maps, with an application to game theory given at the Fields Institute Symposium on Machine Learning and Dynamical Systems and the Oxford Applied Topology Seminar.

slides for a talk given at the Jagiellonian Computational Mathematics Seminar, the CRM 2019 Workshop on Data Driven Dynamics, the SUNY Albany Algebra/Topology Seminar, the Fall 2018 IAS-Penn-Rutgers joint workshop Identifying Order in Complex Systems, and the UPenn Applied Topology seminar.

slides for a talk given at DyToComp2018, ATMCS8 and ATDD18 over the summer of 2018.

slides for a talk at the Applied Algebraic Topology Conference in August 2017.

slides for a talk at the MBI Visitor Seminar in December 2016.

other writings

My Ph.D. dissertation is available here. Roughly one third of the thesis is the material contained in A computational framework for connection matrix theory, and another third is the material contained in Morse theoretic templates for high dimensional homology computation.

Available here is a User's Guide for the Conley-Morse database that I wrote during my time as an NSF EAPSI Fellow at Kyoto University. The intended audience is potential users of the Conley-Morse database who have had little exposure to dynamics or even mathematics.

other projects

Over the summer of 2015 I worked with Fred Chazal at INRIA Geometrica (now INRIA Datashape) on detecting periodicity in data. A white paper from the 2015 NSF Data Science Workshop is here and a poster here.

Courses.


Rutgers University

In Spring 2019 I was a TA at Large for Math 252: Elementary Differential Equations.

In Fall 2018 I was a TA for Math 151: Calculus I for the Mathematical and Physical Sciences Sections 25-27.

In Fall 2017 I was a TA for Math 244: Differential Equations for Engineering and Physics at Rutgers.

Over summer 2017 I was the instructor for the introductory algebra course (Math 351) at Rutgers University. The textbook we used was baby Hungerford. Here are some lecture notes I wrote for the course, which were popular among the students.

VU Amsterdam

In Spring 2018 I was TA for both Calculus II and Linear Algebra for Business Analytics at VU University in Amsterdam.

Contact.

Email:
my last name at google dot com