![[2602.21138] Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.21138] Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
Summary
This paper investigates the efficiency of the FISTA method for computing $ ext{l}_1$-regularized PageRank, focusing on the trade-offs between acceleration and computational locality.
Why It Matters
Understanding the computational complexity of algorithms like FISTA is crucial for optimizing PageRank calculations, which are foundational in various machine learning and data analysis applications. The findings could enhance performance in real-world scenarios where large graphs are involved.
Key Takeaways
- FISTA can potentially improve the computational efficiency of $ ext{l}_1$-regularized PageRank.
- The study identifies conditions under which acceleration does not compromise locality.
- Results indicate both speedup and slowdown regimes depending on graph structure.
Mathematics > Optimization and Control arXiv:2602.21138 (math) [Submitted on 24 Feb 2026] Title:Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank Authors:Kimon Fountoulakis, David Martínez-Rubio View a PDF of the paper titled Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank, by Kimon Fountoulakis and 1 other authors View PDF HTML (experimental) Abstract: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} ((\alpha\rho)^{-1})$, where $\alpha$ is the teleportation parameter and $\rho$ is the $\ell_1$-regularization parameter. A natural question is whether FISTA can improve the dependence on $\alpha$ from $1/\alpha$ to $1/\sqrt{\alpha}$ while preserving the $1/\rho$ 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 $(\rho\sqrt{\alpha})^{-1}\log(\alpha/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(\rho\alpha^{3/2})$. We provide graph-struct...
