Unverified

Running Time Complexity of Accelerated _1 -Regularized PageRank

Let $\alpha\in(0,1]$ , $\rho>0$ , and $\varepsilon>0$ . For the $\ell_1$ -regularized personalized PageRank objective

F(x)=\rho\alpha\|D^{1/2}x\|_1+\frac12x^TQx-\alpha x^TD^{-1/2}s, \qquad Q=\alpha I+\frac{1-\alpha}{2}L,

determine the worst-case running time of an accelerated proximal-gradient method for finding an $\varepsilon$ -accurate solution. In particular, can one prove that each accelerated iteration updates only $O(1/\rho)$ coordinates, or otherwise obtain the graph-size-independent bound

\widetilde O\!\left(\frac{1}{\sqrt\alpha\,\rho}\right)?

Download

Abstract

Small probabilities in a personalized PageRank vector can be thresholded automatically through $\ell_1$ -regularization or early termination. The fastest known method for $\ell_1$ -regularized personalized PageRank uses proximal gradient descent and has graph-size-independent running time $\widetilde O((\alpha\rho)^{-1})$ , where $\alpha$ is the teleportation parameter and $\rho$ controls sparsity. Accelerating the proximal method reduces its iteration complexity, but no corresponding sparsity bound is known. The open question is whether acceleration yields running time $\widetilde O((\sqrt\alpha\rho)^{-1})$ .

Background and progress

For an undirected graph with adjacency matrix $A$ , degree matrix $D$ , and seed indicator $s$ , define the symmetric normalized Laplacian $L=I-D^{-1/2}AD^{-1/2}$ ,

Q=\alpha I+\frac{1-\alpha}{2}L, \qquad f(x)=\frac12x^TQx-\alpha x^TD^{-1/2}s.

The gradient of $f$ is $1$ -Lipschitz and $f$ is $\alpha$ -strongly convex. The $\ell_1$ -regularized PageRank problem is

\min_x\ \rho\alpha\|D^{1/2}x\|_1+f(x).

Proximal gradient descent solves this problem in $\widetilde O((\alpha\rho)^{-1})$ time because it updates at most $1/\rho$ coordinates per iteration [Fountoulakis et al., 2019]. Accelerated methods such as FISTA have $O(\alpha^{-1/2}\log(1/\varepsilon))$ iteration complexity [Beck and Teboulle, 2009], but no known upper bound controls the number of coordinates updated per accelerated iteration. The resulting pessimistic running-time bound depends on the number $n$ of graph vertices. Numerical experiments reported in the source suggest that accelerated iterations update only a constant multiple of $1/\rho$ coordinates.

Reference papers

A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsA. Beck, M. TeboulleSIAM Journal on Imaging Sciences · 2009
Variational Perspective on Local Graph ClusteringKimon Fountoulakis, Farbod Roosta-Khorasani, Julian Shun, Xiang Cheng, Michael W. MahoneyMathematical Programming · 2019

Running Time Complexity of Accelerated _1 -Regularized PageRank

Coming soon

Organizer