In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1:n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1:n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1:n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1:n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1:n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1:n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1:n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1:n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).
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 \geq 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.
The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0,1}n and the constant-dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: $\text{{\it RLS\/}}(\{0,1\}^n)=\Theta(2^{n/2}n^{1/2})$, $\text{{\it QLS\/}}(\{0,1\}^n)=\Theta(2^{n/3}n^{1/6})$, $\text{{\it RLS\/}}([n]^d)=\Theta(n^{d/2})$ for d≥4, $\text{{\it QLS\/}}([n]^d)=\Theta(n^{d/3})$ for d≥6. Here $\text{{\it RLS\/}}(G)$ and $\text{{\it QLS\/}}(G)$ are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494–501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(n(loglogn)1.5) queries is given. This improves the previously best known upper bound of O(n2/3) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474]), and implies that Local Search on grids exhibits different properties in low dimensions.
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality
Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.