Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908948022427648 |
|---|---|
| author | Fountoulakis, Kimon Martínez-Rubio, David |
| author_facet | Fountoulakis, Kimon Martínez-Rubio, David |
| contents | 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 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 $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We also provide graph-structural sufficient conditions that imply such confinement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21138 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank Fountoulakis, Kimon Martínez-Rubio, David Optimization and Control Data Structures and Algorithms Machine Learning 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 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 $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We also provide graph-structural sufficient conditions that imply such confinement. |
| title | Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank |
| topic | Optimization and Control Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2602.21138 |