{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-24","reactions":{}}