Research map / Learning theory and algorithms / Sample complexity
Iterative Methods via Locally Evolving Set Process
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.
Introduces a locally evolving set process framework that localizes standard iterative solvers (GS-SOR, gradient descent, Chebyshev, heavy-ball) for PPR linear systems, yielding new runtime bounds based on average active volume and residual ratio, with up to 100x speedups over standard solvers on real graphs.
Problem
Local approximation of personalized PageRank vectors requires runtime that is independent of graph size; existing local solvers (APPR, ISTA/FISTA, ASPR) have runtime bounds tied to 1/(alpha*eps) or rely on monotonicity properties, and it is open whether faster (accelerated) local solvers exist.
Approach
Model local solvers as a locally evolving set process, showing APPR is a local Gauss-Seidel SOR; this gives new runtime bounds in terms of running-average active volume and active residual ratio, and enables localized GD, SOR, Chebyshev and heavy-ball methods whose analysis does not need monotonicity.
Key results
- LocSOR, LocCH, LocHB achieve up to a hundredfold speedup over corresponding standard solvers on 17 real-world graphs (abstract).
- Localized Chebyshev and heavy-ball methods admit runtime bound O~(vol-bar/(sqrt(alpha)(2-c))) without monotonicity assumptions under geometric-mean residual reduction assumption.
- On ogbn-papers100M and com-friendster, the proposed local solvers are several times faster than current default local methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LocSOR instead of APPR | local clustering · G1 | operations: 6.9e+05 -> 6.5e+04 | Helped |
| Use LocSOR instead of APPR | local clustering · G2 | operations: 6.7e+05 -> 8.9e+04 | Helped |
| Use LocSOR instead of APPR | local clustering · G3 | operations: 4.3e+05 -> 3.5e+04 | Helped |
| Use LocSOR instead of APPR | local clustering · G4 | operations: 5.7e+05 -> 7.6e+04 | Helped |
| Use LocSOR instead of APPR | local clustering · G5 | operations: 5.4e+05 -> 9.0e+04 | Helped |
| Use LocSOR instead of APPR | local clustering · G1 | runtime (seconds): 0.127 -> 0.043 | Helped |
| Use LocSOR instead of APPR | local clustering · G2 | runtime (seconds): 0.362 -> 0.125 | Helped |
| Use LocSOR instead of APPR | local clustering · G3 | runtime (seconds): 0.069 -> 0.014 | Helped |
| Use LocSOR instead of APPR | local clustering · G4 | runtime (seconds): 0.357 -> 0.175 | Helped |
| Use LocSOR instead of APPR | local clustering · G5 | runtime (seconds): 0.072 -> 0.055 | Helped |
| Use LocSOR instead of FISTA | local clustering · G1–G5 | operations | Helped |
| Use LocSOR instead of FISTA | local clustering · G1–G5 | runtime (seconds) | Helped |
Limitations
- Accelerated bound for LocCH relies on an empirically motivated geometric-mean residual reduction assumption without theoretical justification.
- When alpha is small, the acceleration effect partially disappears.
Experimental setup
Baselines: APPR ISTA FISTA conjugate gradient method ASPR
Builds on: APPR (Andersen et al. 2006) evolving set process FISTA Chebyshev iteration
Closest papers by meaning
- Accelerated Evolving Set Processes for Local PageRank Computation (NeurIPS 2025 · similarity 0.89)
- Faster Local Solvers for Graph Diffusion Equations (NeurIPS 2024 · similarity 0.87)
- Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank (NeurIPS 2026 · similarity 0.85)
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.84)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.83)
- Accelerating Optimization via Differentiable Stopping Time (NeurIPS 2025 · 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.