Complexity of Classical Acceleration for ${\ell }_1$-Regularized PageRank

Kimon Fountoulakis, David Martínez-Rubio

We study the degree-weighted work required to compute ${\ell }_1$-regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (IS…