Learning Supervised PageRank with Gradient-Free Optimization Methods

In this paper, we consider a problem of learning supervised PageRank models, which can account for some properties not considered by classical approaches such as the classical PageRank algorithm. Due to huge hidden dimension of the optimization problem we use random gradient-free methods to solve it. We prove a convergence theorem and estimate the number of arithmetic operations needed to solve it with a given accuracy. We find the best settings of the gradient-free optimization method in terms of the number of arithmetic operations needed to achieve given accuracy of the objective. In the paper, we apply our algorithm to the web page ranking problem. We consider a parametric graph model of users' behavior and evaluate web pages' relevance to queries by our algorithm. The experiments show that our optimization method outperforms the untuned gradient-free method in the ranking quality.