Graph-Based Ascent Algorithms for Function Maximization
Graph-Based Ascent Algorithms for Function Maximization
复制标题
DOI：
10.1109/allerton.2018.8636074
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Muni Sreenivas Pydi;Varun Jog;Po-Ling Loh
中科院分区：
文献类型：
--
作者：
Muni Sreenivas Pydi;Varun Jog;Po-Ling Loh
本文研究了求连通图中定义在节点上的函数的最大值的问题。目标是确定函数获得最大值的节点。我们专注于局部迭代算法，它沿着沿着路径遍历图的节点，并且下一个节点是从当前节点的邻居中选择的，其概率分布由当前节点及其邻居的函数值确定。研究了具有不同转移核的Metropolis-Hastings随机游动的两种算法：（i）第一种算法是由参数γ控制的指数加权随机游动。(ii)第二种算法是相对于图拉普拉斯算子和平滑度参数k定义的。我们推导出这两个算法的总变异距离和命中时间方面的收敛速度。我们还提供了模拟显示我们的算法的相对收敛速度相比，一个无偏的随机游走，作为一个函数的图函数的平滑度。我们的算法可以被归类为一类新的“基于下降”的方法函数最大化的节点上的图。
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 gamma. (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.