2022-06-28-branzei22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
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, where at most $k$ rounds of interaction (aka adaptivity) with the oracle are allowed. Adaptivity is a fundamental concept studied due to the need to parallelize computation and understand the speedups attainable. The query complexity of local search is tightly related to the complexity of computing stationary points of a function, thus bounds for local search can give insights into the performance of algorithms such as gradient descent. We focus on the $d$-dimensional grid $\{1, 2, \ldots, n \}^d$, where the dimension $d \geq 2$ is a constant. Our main contribution is to give algorithms and lower bounds that characterize the trade-off between the number of rounds of adaptivity and the query complexity of local search, when the number of rounds is constant and polynomial in $n$, respectively. The local search analysis also enables us to characterize the query complexity of computing a Brouwer fixed point in rounds. 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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	branzei22a	0	The Query Complexity of Local Search and Brouwer in Rounds	5128	5145	5128-5145	5128	false	Branzei, Simina and Li, Jiawei	given family Simina Branzei given family Jiawei Li	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/branzei22a/branzei22a.pdf