Complexity of Classical Acceleration for ℓ1-Regularized PageRank

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.