Introduction
Optimizing functions over massive sets of items is a cornerstone of modern machine learning, appearing in tasks ranging from webpage layout optimization to nearest-neighbor search. However, when evaluations are noisy and the number of items ($n$) reaches the millions, standard multi-armed bandit algorithms become computationally and sample-prohibitive, as their complexity typically scales with $n$. This paper introduces a framework to achieve sublinear sample complexity by exploiting the underlying graph structure of the search space.
Exploiting Graph Structure through Convexity
The core theoretical contribution of this work is a new definition of "convexity" for functions defined on graphs. A function is considered "strongly convex" on a graph if, from any given node, there exists a path to the global minimum along which the function value decreases with a specific minimum steepness at each step.
This definition bridges the gap between continuous optimization and discrete graph search. The authors prove that for such well-behaved functions, the number of samples required to find the global optimum depends only on the function's steepness and the graph's degree, remaining independent of the total number of nodes ($n$).
Proposed Algorithms
The researchers propose two primary algorithms to navigate these noisy graph landscapes:
- Explore-Descend (E&D): A greedy local search algorithm. At each step, E&D treats the current node's neighbors as "arms" in a best-arm identification problem. It uses a variant of the Successive Rejects algorithm to identify the best neighbor despite noisy observations, then moves to that neighbor and repeats the process until it reaches the optimum.
- Simulated Annealing (SA): A classic optimization technique adapted for the noisy, graph-based setting. While generally slower than E&D, SA provides a robust alternative for "nearly convex" functions that may contain shallow local minima, offering a finite-time analysis for convergence.
Experimental Results
The effectiveness of these methods was tested on synthetic 2D grid graphs, web document re-ranking data from the Yandex Personalized Web Search Challenge, and image classification tasks using MNIST and COIL-100.
As shown in Figure 1, Explore-Descend maintains a low sub-optimal gap while requiring significantly less runtime than global approaches. Specifically, "Spectral Bandit" methods, which require calculating eigenvectors for the entire graph, become computationally expensive as the budget increases, whereas E&D's runtime remains nearly constant and negligible.
In real-world scenarios like document re-ranking (Figure 5), E&D demonstrates superior sample efficiency. It achieves a low sub-optimal gap even with a very small sampling budget, whereas global methods like Successive Reject require a much larger budget to identify the optimal region. Furthermore, in nearest-neighbor search for MNIST, the authors' graph-based approach achieved accuracy comparable to standard KD-Trees but was over 5x faster, utilizing less than 20% of the standard runtime.
Conclusion and Future Work
By formalizing "hill-climbing friendly" landscapes through graph convexity, this research provides a scalable path for optimization in massive, noisy domains. Unlike previous spectral methods, Explore-Descend relies only on local neighbor information, making it highly efficient. Future research directions include extending this framework to minimize "cumulative regret" (the loss incurred during the search process) and developing methods to automatically construct optimal graphs for specific datasets.
Summary updated