Sample Efficient Graph-Based Optimization with Noisy Observations

Thanh Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori, Anup Rao, Branislav Kveton

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).

Performance and runtime comparison on synthetic data. The left plot shows the sub-optimal gap, while the right plot highlights the significant runtime advantage of our local search methods over global bandit approaches like SpectralBandit.

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.

Evaluation on real-world noisy data. The plots demonstrate the robustness of EXPLORE-DESCEND in identifying near-optimal solutions even under significant noise and limited budget compared to standard baselines.

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

Abstract

We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of best-arm identification can find a near-optimal solution after a small number of queries that is independent of the size of the graph. For functions that have local minima and are nearly convex, we show a sample complexity for the classical simulated annealing under noisy observations. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification as well as a web document re-ranking application.
BibTeX
@inproceedings{nguyen2019sample,
  author = {Thanh Tan Nguyen and Ali Shameli and Yasin Abbasi-Yadkori and Anup Rao and Branislav Kveton},
  title = {{Sample Efficient Graph-Based Optimization with Noisy Observations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=obaIz4mwoGf},
}
Figure