Combinatorial Aspects of Continuous Optimization: Graph Polynomials and Neural Networks

In this thesis, we study how combinatorial structures and symmetries emerge from analytic properties of graph polynomials and neural networks. Graph polynomials encode combinatorial aspects of the underlying graph in their coefficients and are remarkably useful in revealing information about the graph through inspection of their analytic properties. One such property, which we refer to as pre-Lorentzian, enables us to make progress on the following question of Alavi, Malde, Schwenk and Erdős: Is the independence sequence of trees or forest so-called unimodal? We show that all graphs that can be build by replacing the edges with a caterpillar of size $4$ are pre-Lorentzian, that is, their multivariate independence polynomial becomes Lorentzian after appropriate manipulations. Since pre-Lorentzian graphs have log-concave (and hence unimodal) independence sequences, we give an affirmative answer for all trees and forests that are attained by applying the edge replacement to arbitrary trees or forests.

In the context of neural networks, we show that analytic properties of student-teacher networks imply the emergence of symmetries in the set of critical points of the associated loss functions. In the under-parameterized setting, this allows us to understand under which conditions the student weights either copy or align with a group of teacher weights. Finally, we turn our attention to the gradient flow dynamics of the correlation loss for which we give tight time complexity bounds for teachers in arbitrary positions, show convergence to the nearest teacher vector for orthogonal teachers, and prove a saddle-to-minimum transition when the teacher weights form an equiangular frame.