Abstract
We investigate the sample complexity of optimizing functions defined on graphs under noisy observations, specifically focusing on "hill-climbing friendly" objectives. We introduce a novel notion of graph convexity and demonstrate that a variant of best-arm identification can identify near-optimal solutions with a query budget independent of the graph's size. For functions exhibiting local minima but maintaining near-convexity, we analyze the performance of simulated annealing under noise. Our empirical evaluations on graph-based nearest neighbor classification and web document re-ranking demonstrate the effectiveness and efficiency of our proposed greedy-with-restarts and simulated annealing approaches compared to traditional bandit methods.
Introduction
Optimization on large-scale graphs is a fundamental challenge in applications ranging from social network analysis to web search re-ranking. Two primary obstacles hinder practical implementation: the presence of noise in observations and the prohibitive scale of modern graphs. Traditional multi-armed bandit algorithms often suffer from performance degradation as the number of nodes ($N$) increases, making them unsuitable for massive search spaces. This paper addresses these issues by developing sample-efficient algorithms whose performance is decoupled from the total number of nodes, provided the objective function satisfies certain "hill-climbing friendly" properties.
Methods
The core of our approach lies in the definition of Graph Convexity. We define a function as convex on a graph if there exists a "strongly convex path" from any node to the global minimum. This property ensures that local search strategies can reliably progress toward the optimum. Crucially, we prove that for such functions, the sample complexity required to find a near-optimal solution depends on the function's "steepness" rather than the graph's cardinality.
We propose two primary algorithmic approaches:
- EXPLORE-DESCEND: A sophisticated greedy search strategy that treats a node's neighborhood as a mini-bandit problem. It utilizes a SuccessiveReject subroutine to identify the most promising neighbor for the next step, effectively navigating noise while moving towards the local optimum.
- Noisy Simulated Annealing: Designed for functions with shallow local minima, this method employs a Metropolis-Hastings framework. Node values are estimated through multiple noisy samples, and transitions are governed by exponential weights to avoid getting stuck in minor local optima.
Key Results and Insights
Our methods were evaluated on synthetic grids, Yandex web search data, and image classification datasets (MNIST, COIL-100).
As illustrated in Figure 4, EXPLORE-DESCEND and Simulated Annealing significantly outperform standard bandit methods in both accuracy and computational efficiency when the sampling budget is small relative to the graph size. Notably, global methods like SpectralBandit require expensive computations involving the graph Laplacian, leading to runtimes that scale poorly. In contrast, our proposed methods rely solely on local neighborhood information, maintaining high efficiency.
In the context of nearest-neighbor search, we introduced "Smoothed Graph-based Nearest Neighbor" (SGNN), which uses short random walks to average noisy observations. This smoothing acts as a regularizer, preventing the search from being trapped in local noise. On the MNIST dataset, SGNN achieved state-of-the-art accuracy with a runtime less than 20% of traditional KDTree methods. Furthermore, as shown in Figure 2, EXPLORE-DESCEND remains robust across different budget scales, consistently finding better solutions than standalone Successive Reject or simulated annealing variants in noisy environments.
Conclusion
By leveraging local graph structure and the assumption of near-convexity, we have developed algorithms that break the dependency on graph size for noisy optimization. This makes them ideal for "big data" applications where global graph knowledge is unavailable or too expensive to compute. Future work will explore relaxing the convexity assumption to handle deeper local minima and extending these techniques to cumulative regret minimization.
Summary updated