832 citations · 1.3k across the 79 of their papers we have counts for
91 papers
Polyhedral Geometry of Time-to-First-Spike Neural Networks
Manjot Singh, Guido Montúfar, Gitta Kutyniok
We study the expressivity of spiking neural networks, which provide a natural framework for asynchronous, event-driven computation complementary to conventional feedforward neural…
The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes
Ryan A. Anderson, Guido Montufar
We study the geometry of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless stochastic policies. Our main contrib…
TriSearch: Learning to Optimize Triangulations via Bistellar Flips
Yiran Wang, Guido Montúfar
We introduce TriSearch, a reinforcement learning framework for optimizing objectives over triangulations of a polytope via bistellar flips. The key idea is a circuit-supported subt…
Implicit Bias of Mirror Flow in Homogeneous Neural Networks: Sparse and Dense Feature Learning
Tom Jacobs, Guido Montufar
We study the max-margin solutions reached by mirror flow in deep neural networks with homogeneous activation functions. Extending classical results on gradient flow, we derive a no…
Most ReLU Networks Admit Identifiable Parameters
Moritz Grillo, Guido Montúfar
We study the realization map of deep ReLU networks, focusing on when a function determines its parameters up to scaling and permutation. To analyze hidden redundancies beyond these…
The Symmetries of Three-Layer ReLU Networks
Johanna Marie Gegenfurtner, Moritz Grillo, Guido Montúfar
We develop a framework for analyzing parameter symmetries in deep ReLU networks and obtain a complete characterization of the generic parameter fibers for three-layer bottleneck ar…
Stress-Testing Neural Network Verifiers with Provably Robust Instances
David Troxell, Yulia Alexandr, Sofia Hunt +2
Neural network verifiers aim to provide formal guarantees on model behavior, but existing verification benchmarks are fundamentally limited by their lack of ground-truth labels. As…
Differentiable Optimization Layers for Guaranteed Fairness in Deep Learning
David Troxell, Noah Roemer, Guido Montúfar
Differentiable optimization layers are traditionally integrated in predict-then-optimize frameworks where a neural model estimates parameters that subsequently serve as fixed input…
Algebraic Invariants of Lightning Self-Attention
Yulia Alexandr, Hao Duan, Guido Montúfar
We study the polynomial coefficients of lightning self-attention as coordinates of an algebraic variety. In the single-token case, we characterize the coefficient variety as a rank…
Robustness Verification of Polynomial Neural Networks
Yulia Alexandr, Hao Duan, Guido Montúfar
We study robustness verification of neural networks via metric algebraic geometry. For polynomial neural networks, certifying a robustness radius amounts to computing the distance…
Harmful Overfitting in Sobolev Spaces
Kedar Karhadkar, Alexander Sietsema, Deanna Needell +1
Motivated by recent work on benign overfitting in overparameterized machine learning, we study the generalization behavior of functions in Sobolev spaces t…
Hadamard ranks of algebraic varieties
Dario Antolini, Guido Montúfar, Alessandro Oneto
Motivated by the study of decompositions of tensors as Hadamard products (i.e., coefficient-wise products) of low-rank tensors, we introduce the notion of Hadamard rank of a given…
Low Rank Gradients and Where to Find Them
Rishi Sonthalia, Michael Murray, Guido Montúfar
This paper investigates low-rank structure in the gradients of the training loss for two-layer neural networks while relaxing the usual isotropy assumptions on the training data an…
Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region
Shuang Liang, Guido Montúfar
We examine gradient descent in matrix factorization and show that under large step sizes the parameter space develops a fractal structure. We derive the exact critical step size fo…
Constraining the outputs of ReLU neural networks
Yulia Alexandr, Guido Montúfar
We introduce a class of algebraic varieties naturally associated with ReLU neural networks, arising from the piecewise linear structure of their outputs across activation regions i…
Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contexts
James Chapman, Kedar Karhadkar, Guido Montufar
Deep reinforcement learning (DRL) has achieved remarkable success across multiple domains, including competitive games, natural language processing, and robotics. Despite these adv…
Understanding Learning Invariance in Deep Linear Networks
Hao Duan, Guido Montúfar
Equivariant and invariant machine learning models exploit symmetries and structural patterns in data to improve sample efficiency. While empirical studies suggest that data-driven…
Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing
Diaaeldin Taha, James Chapman, Marzieh Eidi +2
Topological deep learning (TDL) has emerged as a powerful tool for modeling higher-order interactions in relational data. However, phenomena such as oversquashing in topological me…
On the Local Complexity of Linear Regions in Deep ReLU Networks
Niket Patel, Guido Montufar
We define the local complexity of a neural network with continuous piecewise linear activations as a measure of the density of linear regions over an input data distribution. We sh…
Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension
Kedar Karhadkar, Michael Murray, Guido Montúfar
Bounds on the smallest eigenvalue of the neural tangent kernel (NTK) are a key ingredient in the analysis of neural network optimization and memorization. However, existing results…
Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients
Johannes Müller, Semih Çaycı, Guido Montúfar
Kakade's natural policy gradient method has been studied extensively in recent years, showing linear convergence with and without regularization. We study another natural gradient…
Supermodular Rank: Set Function Decomposition and Optimization
Rishi Sonthalia, Anna Seigal, Guido Montufar
We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summa…
Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape
Kedar Karhadkar, Michael Murray, Hanna Tseran +1
We study the loss landscape of both shallow and deep, mildly overparameterized ReLU neural networks on a generic finite input dataset for the squared error loss. We show both by co…
Function Space and Critical Points of Linear Convolutional Networks
Kathlén Kohn, Guido Montúfar, Vahid Shahverdi +1
We study the geometry of linear networks with one-dimensional convolutional layers. The function spaces of these networks can be identified with semi-algebraic families of polynomi…