Query Complexity of Local Search in Rounds: Grids, General Graphs, and AI-assisted Proofs

Abstract: Local search is a powerful heuristic for solving hard optimization problems, used for tasks ranging from training neural networks to finding Nash equilibria. In this talk, I will focus on the query complexity of local search on a graph under round constraints. This model captures tasks like neural network training, where each “query” is an expensive evaluation of the loss function and batching queries is crucial for efficiency.

We begin with the d-dimensional grid, establishing matching upper and lower bounds that quantify the trade-off between the number of rounds and total queries. We then generalize these results to arbitrary graphs, for which we obtain a geometric bound as a function of the separation number of the graph and randomized lower bounds.

A feature of the general graph results is the methodology used to obtain them. This work was developed through an interactive “scaffolded reasoning” process with AI models. I will discuss how the AI acted as a junior collaborator and our experience with them.
Joint work with Jiawei Li (UT Austin), and with Ioannis Panageas (UC Irvine) and Dimitris Paparas (Google Research).

Bio: I’m an associate professor of computer science at Purdue University. My research interests are in algorithmic game theory, theory of computation, artificial intelligence, algorithms, learning, computational complexity and their interface with dynamical systems and optimization. Example of topics I worked on include fair division, markets and auctions, games and learning dynamics, and the complexity of local search. My research is supported by an NSF CAREER Award.