  In this paper, we consider a non-convex loss-minimization problem of learning
Supervised PageRank models, which can account for some properties not
considered by classical approaches such as the classical PageRank model. 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 state-of-the-art gradient-based method we manage to provide theoretically
the convergence rate guarantees for both of them. In particular, under the
assumption of local convexity of the loss function, our random gradient-free
algorithm guarantees decrease of the loss function value expectation. At the
same time, we theoretically justify that without convexity assumption for the
loss function our gradient-based algorithm allows to find a point where the
stationary condition is fulfilled with a given accuracy. For both proposed
optimization algorithms, we find the settings of hyperparameters which give the
lowest complexity (i.e., the number of arithmetic operations needed to achieve
the given accuracy of the solution of the loss-minimization problem). The
resulting estimates of the complexity are also provided. Finally, we apply
proposed optimization algorithms to the web page ranking problem and compare
proposed and state-of-the-art algorithms in terms of the considered loss
function.
