Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods
In this paper, we consider a non-convex loss-minimization problem of learning Supervised PageRank models, which can account for features of nodes and edges. We propose gradient-based and random gradient-free methods to solve this problem. Our algorithms are based on the concept of an inexact oracle and unlike the state-ofthe-art gradient-based method we manage to provide theoretically the convergence rate guarantees for both of them. Finally, we compare the performance of the proposed optimization methods with the state of the art applied to a ranking task.
The authors motivate pagerank and then bring up a framework which has node and edge weights from a feature model. They pointed out that a previous algorithm for learning the parameters of the model had no performance guarantees. They plan to solve the methods by combining a previous method for approximating the stationary distribution of a Markov random walk with an adaptation of a gradient free method used for optimization when the loss function can only be estimated. They reproduce a framework under a different name and notation from [21]. They discuss a number of technical assumptions and a loss function and explain why the problem is hard to solve. Some lemma bounding the approximate gradient are stated. A general gradient free method is discussed, using a biased gradient-free oracle, and state a theorem on its performance. They make some more assumptions and construct an algorithm for the learning problem and adapt the gradient free methods to their problem, stating some more bounds. They outline some details of experimental results on a web graph used in related work, but detailed reporting of results and analysis are relegated to the appendix. Some parameters are not reported, and the novel algorithm is proclaimed to have outperformed other algorithms, but there is no discussion of the extent or implication of the improvement. It is unclear whether a diverse set of graphs were considered for testing.  
The writing is littered with grammatical errors. Citations are sloppy, the problem is called Supervised PageRank with a cite to [21], but only semi-supervised page rank appears there. I am not convinced that the problem solved is impactful.    Your bounds are strong, but I have doubts about whether the technical assumptions stated will hold in emprical data. Some assumptions seem limiting, e.g. your constriction of the search space of phi to an R-ball around some chosen phi_0may greatly restrict the efficacy/applicability of your algorithm, which should be discussed.   My biggest issue with the paper is that it all the meat appears in the appendix. You neither provide proof outlines nor full empirical results. How did you choose phi_0 and R in the empirical results section? Did you run tests on more than one graph? You do not report any tables or specific results in the main body of the paper. What are the practical consequences of your improvements?  Your bounds and analysis and algorithm may be powerful, but the content in the paper itself fails to convince me.