The Query Complexity of Local Search and Brouwer in Rounds

We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a local minimum of the loss function when training deep neural networks. In such applications, each query is an expensive loss evaluation, making it crucial to parallelize computations. This motivates our study of local search where at most k rounds of interaction (aka adaptivity) with the oracle are allowed. We focus on the d-dimensional grid 1, 2, ldots, n d, where the dimension d ≥ 2 is a constant. Our main contribution is to give algorithms and lower bounds that characterize the query complexity of finding a local minimum in k rounds, when k is constant and polynomial in n, respectively. Our proof technique for lower bounding the query complexity in rounds may be of independent interest as an alternative to the classical relational adversary method of Aaronson from the fully adaptive setting. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds.