Id: arxiv/2602.21138 Url: https://arxiv.org/abs/2602.21138 Tags: math.OC, cs.DS, cs.LG Score: 0 Title: Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank Domain: math.OC Source: arxiv Authors: Kimon Fountoulakis, David Martínez-Rubio Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-24 Page: https://delphi.science/r/arxiv/2602.21138 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 (ISTA), the best known worst-case work is $\widetilde{O}((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. It is not known whether classical acceleration methods can improve $1/α$ to $1/\sqrtα$ 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…