# Complexity of Classical Acceleration for ℓ1-Regularized PageRank

arXiv: https://arxiv.org/abs/2602.21138 · HTML: https://mlsanity.com/paper/2602.21138/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 7 of 7)

- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- ["Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?](https://mlsanity.com/paper/1712.03577/) (2017)
- [Statistical guarantees for local graph clustering](https://mlsanity.com/paper/1906.04863/) (2019)
- [Iterative Methods via Locally Evolving Set Process](https://mlsanity.com/paper/2410.15020/) (2024)
- [Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond](https://mlsanity.com/paper/2303.12875/) (2023)
- [On the Interplay between Acceleration and Identification for the Proximal Gradient algorithm](https://mlsanity.com/paper/1909.08944/) (2019)

## Abstract (arXiv)

We study the degree-weighted work required to compute ℓ1-regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (ISTA), the best known worst-case work is widetildeO((αρ)-1), where α is the teleportation parameter and ρ is the ℓ1-regularization parameter. It is not known whether classical acceleration methods can improve 1/α to 1/√α while preserving the 1/ρ locality scaling, or whether they can be asymptotically worse. For FISTA, we show a negative result by constructing a family of instances for which standard FISTA is asymptotically worse than ISTA. On the positive side, we analyze FISTA on a slightly over-regularized objective and show that, under a confinement condition, all spurious activations remain inside a boundary set B. This yields a bound consisting of an accelerated (ρ√α)-1log(α/varepsilon) term plus a boundary overhead √vol(B)/(ρα3/2). We also provide graph-structural sufficient conditions that imply such confinement.