PaperlayerView exact revision on arXiv

Source-linked AI summary

The Query Complexity of Local Search in Rounds on General Graphs

Simina Brânzei, Ioannis Panageas, Dimitris Paparas

arXiv:2601.13266v2cs.CCcs.DS

TL;DR

The paper studies finding a local minimum through value queries when interaction is limited to t rounds. It develops round-limited algorithms for general graphs and establishes deterministic upper bounds and randomized lower bounds.

  • Problem

    The task is to find a local minimum of an unknown vertex function using oracle queries, with interaction limited to t rounds.

    Source: §1 · p. 2, §1.3 · p. 4

  • Method

    The paper uses hierarchical graph decomposition for a deterministic algorithm and a parallelized warm-start steepest-descent approach for a randomized algorithm.

    Source: §3.1 · p. 7, §3.2 · p. 11

  • Results

    For connected graphs, deterministic t-round query complexity is bounded in terms of graph size, maximum degree, and separation number, while randomized complexity is at least Ω(tn^1/t − t).

    Source: §1.4 · p. 5

  • Takeaways & Limitations

    Parallel warm-start steepest descent offers an alternative that can give better bounds when the separation number is large.

    Source: §3.2 · p. 11

    The lower-bound construction assumes a unique local minimum chosen uniformly at random from the vertices.

    Source: §4.2 · p. 17, §4.3 · p. 19

Abstract

from arXiv · show

We analyze the query complexity of finding a local minimum in $t$ rounds on general graphs. More precisely, given a graph $G = (V,E)$ and oracle access to an unknown function $f : V \to \mathbb{R}$, the goal is to find a local minimum--a vertex $v$ such that $f(v) \leq f(u)$ for all $(u,v) \in E$--using at most $t$ rounds of interaction with the oracle. The query complexity is well understood on grids, but much less is known beyond. This abstract problem captures many optimization tasks, such as finding a local minimum of a loss function during neural network training. For each graph with $n$ vertices, we prove a deterministic upper bound of $O(t n^{1/t} (s\Delta)^{1-1/t})$, where $s$ is the separation number and $\Delta$ is the maximum degree of the graph. We complement this result with a randomized lower bound of $\Omega(t n^{1/t}-t)$ that holds for any connected graph. We also find that parallel steepest descent with a warm start provides improved bounds for graphs with high separation number and bounded degree. To obtain our results, we utilized an advanced version of Gemini at various stages of our research. We discuss our experience in a methodology section.

1 Introduction

The paper studies black-box local search on general graphs when oracle interaction is limited to t rounds, extending the round-complexity question beyond grids. It relates query bounds to graph structure and gives both deterministic upper bounds and randomized lower bounds.

1.1 Examples

  • Examples include regression on a grid of coefficient candidates and low-rank matrix search, where a single factor-entry change modifies an entire matrix row.The matrix-search graph is topologically distinct from a grid and contains triangles.Source: §1.1 · pp. 2–3

1 Introduction

  • Expensive neural-network loss evaluations motivate parallel query rounds, where each batch is chosen using answers from earlier rounds.Training a configuration to convergence may take hours or days, making sequential search difficult.Source: §1.1 · p. 2, §1 · p. 2

1.2 Graph Features and Complexity of Local Search

  • A minimum vertex cover C yields a two-round local-search algorithm using |C| + Δ queries, illustrating how graph structure can prune the search.The algorithm queries C first, then the neighbors of its lowest-valued vertex if needed.Source: §1.2 · pp. 3–4

1.3 Model

  • The model asks for a vertex whose function value is no greater than its neighbors’ values, using value queries and at most t adaptive rounds.The separation number is defined through separators across all subgraphs and is within a constant factor of treewidth.Source: §1.3 · p. 4

1.4 Our Results

  • Theorem 1 bounds deterministic t-round query complexity using the graph’s size, maximum degree, and separation number.The result applies to connected undirected graphs with t ≥ 2.Source: §1.4 · p. 5
  • For graphs with large separation number, parallel steepest descent with a warm start can provide better bounds.The randomized approach parallelizes the classical warm-start method.Source: §1.4 · p. 5
  • Theorem 2 gives a randomized lower bound of Ω(tn^1/t − t) for connected graphs.The lower-bound analysis uses a hard distribution in which each round reduces the search to a smaller subtree.Source: §1.4 · p. 5

2 Related Work

Prior work studies local-search query complexity on hypercubes and grids, then relates general-graph complexity to structural features. Research also examines parallel rounds, distributed settings, and connections to continuous optimization.

The Boolean Hypercube and Grids

  • On the Boolean hypercube, Aldous's warm-start steepest descent uses O(√n·2^(n/2)) queries, Zhang proves Θ(√n·2^(n/2)), and deterministic divide-and-conquer gives O(2^n log n/√n).The passage also reports an earlier nearly matching lower bound of Ω(2^(n/2−o(n))).Source: §2 · p. 5
  • For [n]^d, Zhang proves a tight Ω(n^(d/2)) randomized lower bound for constant d ≥4, while Sun and Yao resolve remaining gaps for d=2,3 and quantum settings.Source: §2 · p. 5

General Graphs

  • For general graphs, prior work uses separation number and links query complexity to genus, diameter, congestion, and mixing time.The cited passage also reports a deterministic O((s + ∆) log n) upper bound.Source: §2 · pp. 5–6

Local Search in Rounds and Distributed Settings

  • Parallel query rounds have been analyzed for grid graphs, while distributed local search studies communication when data is held by different parties.Source: §2 · p. 6

Stationary Points and Adaptive Complexity

  • Discrete local search is related to approximate stationary-point computation; Zhou et al. report dimension-dependent parallelization results and reduce constant-dimensional lower bounds to grid local search.In high dimensions, their passage says parallelization offers no asymptotic benefit; for constant dimensions, they give a near-optimal constant-round algorithm.Source: §2 · p. 6

3 Algorithms

Section 3 studies local-search query complexity through separator-based deterministic algorithms and randomized parallel steepest descent with a warm start. It gives query bounds for bounded-degree graphs and describes where the randomized algorithm is effective relative to specialized algorithms.

3.1 Deterministic Algorithm

  • The t-round algorithm recursively applies the shattering lemma to build nested separators, querying separators and components adjacent to the running minimum.The lemma gives a separator S with |S| < 3sn/K whose removal leaves components of size at most K; components without neighbors of the running minimum are not explored.Source: §3.1 · pp. 6, 7, 8, 11
  • For connected graphs and t ≥ 2, the deterministic query complexity is at most min(n, 4t n^(1/t)(s∆)^(1−1/t)).Here s is the separation number and ∆ is the maximum degree.Source: §3.1 · pp. 7, 10

3.2 Randomized Algorithm

  • The randomized approach parallelizes classical steepest descent with a warm start [Ald83], sampling q vertices and querying radius-(r+1) balls to simulate r descent steps per search round.It uses one sampling round followed by t−1 parallel-search rounds.Source: §3.2 · p. 11
  • For the minimum of q uniformly sampled vertices, the expected steepest-descent path length is less than n/(q+1).The path uses a strict vertex order that breaks equal-value ties lexicographically.Source: §3.2 · p. 11
  • O(√n + t) randomized queries suffice for graphs with maximum degree at most 2 and t ≥ 2.Source: §3.2 · p. 12
  • O(n / log n) randomized queries suffice in two rounds when maximum degree and t are constants and maximum degree is at least 3.Source: §3.2 · p. 12
  • Algorithm 3 is effective for bounded-degree graphs with high expansion, such as expanders, whereas specialized algorithms perform better on slowly expanding graphs such as grids.For expanders with separation number s = Θ(n), Theorem 1's deterministic bound is O(n).Source: §3.2 · p. 12

4 Lower Bounds

The section proves randomized query lower bounds for connected graphs by analyzing how query batches distinguish candidate sets across rounds. It constructs inputs with uniformly random unique local minima and shows that algorithms succeeding with probability at least c require Ω(t·c·n^(1/t)−t) queries for t≥2.

4 Lower Bounds

  • The construction assigns each vertex v a function f_v for which v is the unique local minimum, and chooses the target uniformly from V.This distribution is used in the lower-bound arguments for connected graphs.Source: §4 · p. 13, §4.2 · p. 17

4.1 Properties of the Construction

  • For any query set Q, at most |Q|+1 distinct signatures arise; after each round, candidate sets partition V and contain at most the queried root.The signature bound follows by associating each non-empty signature with its deepest queried vertex.Source: §4.1 · pp. 13–15

4.2 Lower Bound for Two Rounds

  • For connected undirected graphs with n > 1 vertices, randomized local-minimum search in two rounds requires Ω(√n) queries.More generally, for success probability at least c, the proof lower-bounds expected query cost by 2c√n − 2.Source: §4.2 · p. 17

4.3 Lower Bound for t Rounds

  • For connected undirected graphs with n vertices, randomized local-minimum search in t rounds requires Ω(t n^1/t − t) queries.The proof uses Yao’s principle on a uniform target distribution, partitions candidates by round, and relates expected branching to shrinkage; a query batch creates at most |Q|+1 distinct signatures.Source: §4.1 · p. 13, §4.3 · p. 19
  • Success probability at least c requires at least ⌈cn⌉ final candidate sets, since an algorithm cannot succeed on both vertices in any set containing distinct vertices.Source: §4.3 · p. 21
  • For t=1, the expected query complexity is at least ⌈cn⌉−1, giving an Ω(cn) lower bound.Source: §4.3 · p. 21
  • For fixed L, the minimum objective has L−1 singleton sets and one set of size n−L+1; the objective is minimized at L=⌈cn⌉.Source: §4.3 · p. 22
  • For t≥2, the randomized query complexity is Ω(t·c·n^(1/t)−t) as n→∞.The derived expected-query bound is at least c·t·n^(1/t) + t·(1−c)^(1−1/t) − t; the stated asymptotic follows as n grows.Source: §4.3 · p. 22

Methodology

The authors describe an interactive collaboration with Gemini models in which they supplied high-level directions and lemma statements, then verified and refined model-generated proofs. The models contributed strategies for both the deterministic upper bound and randomized lower bounds, while the authors corrected errors and used the model to check hypotheses.

Methodology

  • The authors supplied high-level conceptual direction and lemma statements; Gemini synthesized initial proofs that the authors rigorously verified and refined.The collaboration used Gemini Deep Think and advanced Google-internal variants.Source: Methodology · pp. 22–23
  • For the deterministic upper bound, Gemini found a separation-based strategy for two rounds and generalized it to t rounds using recursive decomposition and the Shattering Lemma.Source: Methodology · p. 23
  • For randomized lower bounds, Gemini proposed a distance-based function family for trees and a spanning-tree reduction that the authors generalized to t rounds.The authors supplied prior-work examples.Source: Methodology · p. 23
  • The authors corrected a circular argument in the histories-to-candidate-sets proof, and Gemini also proposed parallel steepest descent as an adversarial check on a hypothesis.That algorithm showed linear lower bounds do not hold for two-round local search on constant-degree expanders.Source: Methodology · p. 23

A Appendix: Algorithms

The appendix begins by introducing proofs of several lemmas from Section 3.

A Appendix: Algorithms

A.1 Deterministic Algorithm

The appendix proves a separator-based decomposition result and develops its recursive construction and size bound. It also establishes a pruning property for the deterministic algorithm: a candidate component with no neighbor of the current running minimum is never queried.

A.1 Deterministic Algorithm

  • For any K in [1,n], a set S of size less than 3sn/K leaves every connected component of G[V \ S] with at most K vertices.Source: §A.1 · p. 25
  • FindSeparator recursively removes an (s, 2/3)-separator, then processes the two disconnected remaining parts until their components have size at most K.At each recursive step, the two parts have size at most 2/3 of the current subgraph and no edges between them.Source: §A.1 · p. 26
  • The proof bounds the accumulated separator size by charging each separator across its subgraph's vertices; geometric shrinkage controls the total charge.The recursion ensures components remain of size at most K, and the accumulated separator satisfies the bound in the separator lemma.Source: §A.1 · pp. 26–27
  • If the running minimum has no neighbors in a candidate component C, the algorithm never queries any vertex in C in later rounds.The induction uses that selected components are adjacent to the running minimum and distinct components in the decomposition are disconnected.Source: §A.1 · pp. 27–28

A.2 Randomized Algorithm

For maximum degree at most 2, the randomized query complexity is O(√n + t). The proof analyzes an initial sample followed by parallel search, with graph-ball sizes used to bound search cost.

A.2 Randomized Algorithm

  • For ∆=2, every radius-ρ ball has at most 1+2ρ vertices.Source: §A.2 · p. 29
  • O(√n + t): the randomized query complexity is bounded by this amount when ∆≤2.Source: §A.2 · p. 29
  • The analysis uses T=t−1 parallel search rounds after sampling q1 vertices, and treats sampling and search as the two components of query cost.Source: §A.2 · p. 29
  • 10n: failure probability is below 1/10 when (q1 + 1)Tr ≥ 10n.Source: §A.2 · p. 29
  • The search cost is O(t∆^2√n) under the stated choice of r.Source: §A.2 · p. 29
Loading 2601.13266v2…