Research map / Optimization / Nonconvex and smooth optimization
Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows standard FISTA can be asymptotically worse than ISTA for l1-regularized PageRank via a star-graph lower bound, and gives a conditional FISTA work bound on an over-regularized objective under boundary confinement.
Problem
Whether accelerated proximal gradient (FISTA) can reduce the degree-weighted work of l1-regularized PageRank from O~(1/(alpha rho)) to O~(1/(rho sqrt(alpha))) while preserving locality, or whether acceleration can hurt.
Approach
Gives a seed-at-leaf star instance where FISTA activates a high-degree center and incurs Omega(m) work while ISTA stays local; for FISTA on a slightly over-regularized objective, bounds spurious work via KKT slack and a boundary set B, with a no-percolation graph condition guaranteeing confinement.
Key results
- Star-graph lower bound: standard FISTA needs at least 2m total work to reach any accuracy eps <= eps_0(alpha), while ISTA needs O((1/alpha) log(1/eps)) independent of m.
- Conditional FISTA work bound on over-regularized objective: O((rho sqrt(alpha))^-1 log(alpha/eps) + sqrt(vol(B))/(rho alpha^{3/2})).
- On real SNAP graphs, FISTA typically reduces work vs ISTA for com-Amazon, com-DBLP, com-Youtube, while com-Orkut shows FISTA slower for small alpha.
Surprising findings
- Standard FISTA can be asymptotically worse than ISTA in degree-weighted work on star instances.
- On com-Orkut, FISTA can be slower than ISTA for small alpha due to costly transient exploration of high-degree nodes.
Limitations
- Upper bound is conditional on an explicit confinement assumption on spurious activations.
- Analysis applies to over-regularized objective F_{2rho} rather than the original problem.
- Lower bound is worst-case on specific star instances; real-graph results mixed.
Experimental setup
Datasets: com-Amazon com-DBLP com-Youtube com-Orkut
Benchmarks: SNAP com-Amazon SNAP com-DBLP SNAP com-Youtube SNAP com-Orkut synthetic core-boundary-exterior graphs
Metrics: degree-weighted work
Baselines: ISTA ASPR
Builds on: FISTA ISTA ASPR l1-regularized PageRank
Closest papers by meaning
- Accelerated Evolving Set Processes for Local PageRank Computation (NeurIPS 2025 · similarity 0.89)
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.85)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.84)
- Faster Local Solvers for Graph Diffusion Equations (NeurIPS 2024 · similarity 0.84)
- Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning (ICML 2024 · similarity 0.83)
- Finding Koopman Invariant Subspaces via Personalized PageRank (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.