Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.21138
curl -X POST /api/v1/records/arxiv/2602.21138/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.21138/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'