Graph-Based Ascent Algorithms for Function Maximization
This work addresses function maximization on graphs, which is relevant for optimization in network-based applications, but it is incremental as it builds on existing random walk methods with specific parameterizations.
The paper tackles the problem of maximizing a function defined on graph nodes by proposing two local iterative algorithms based on Metropolis-Hastings random walks with different transition kernels, deriving convergence rates in terms of total variation distance and hitting times, and showing through simulations that these algorithms outperform an unbiased random walk depending on graph function smoothness.
We study the problem of finding the maximum of a function defined on the nodes of a connected graph. The goal is to identify a node where the function obtains its maximum. We focus on local iterative algorithms, which traverse the nodes of the graph along a path, and the next iterate is chosen from the neighbors of the current iterate with probability distribution determined by the function values at the current iterate and its neighbors. We study two algorithms corresponding to a Metropolis-Hastings random walk with different transition kernels: (i) The first algorithm is an exponentially weighted random walk governed by a parameter $γ$. (ii) The second algorithm is defined with respect to the graph Laplacian and a smoothness parameter $k$. We derive convergence rates for the two algorithms in terms of total variation distance and hitting times. We also provide simulations showing the relative convergence rates of our algorithms in comparison to an unbiased random walk, as a function of the smoothness of the graph function. Our algorithms may be categorized as a new class of "descent-based" methods for function maximization on the nodes of a graph.