Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
This work addresses computational efficiency for graph-based ranking problems, but it is incremental as it builds on existing methods with specific structural analyses.
The paper tackles the problem of computing ℓ1-regularized PageRank efficiently using an accelerated method (FISTA), showing that under certain conditions, it achieves a bound with an accelerated term scaling as (ρ√α)^{-1}log(α/ε) plus a boundary overhead, and experiments demonstrate speedup and slowdown regimes.
We study the degree-weighted work required to compute $\ell_1$-regularized PageRank using the standard one-gradient-per-iteration accelerated proximal-gradient method (FISTA). For non-accelerated local methods, the best known worst-case work scales as $\widetilde{O} ((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. A natural question is whether FISTA can improve the dependence on $α$ from $1/α$ to $1/\sqrtα$ while preserving the $1/ρ$ locality scaling. The challenge is that acceleration can break locality by transiently activating nodes that are zero at optimality, thereby increasing the cost of gradient evaluations. We analyze FISTA on a slightly over-regularized objective and show that, under a checkable confinement condition, all spurious activations remain inside a boundary set $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We provide graph-structural conditions that imply such confinement. Experiments on synthetic and real graphs show the resulting speedup and slowdown regimes under the degree-weighted work model.