Seonglae ChoPPR
The current fastest method is proximal gradient, with time complexity
O~((αρ)^(-1)), which is independent of graph size.Key idea: Using acceleration (proximal gradient acceleration) could potentially reduce complexity to
O~((√α·ρ)^(-1)), theoretically achieving a 1/√α-fold improvement.While experiments show promising speedups, there is currently no theoretical guarantee that this approach is faster in the worst case—it might even be slower in some scenarios.
Proof
Kimon Fountoulakis on Twitter / X
GPT-5.2 solves our COLT 2022 open problem: “Running Time Complexity of Accelerated L1-Regularized PageRank” using a standard accelerated gradient algorithm and a complementarity margin assumption. Link to the open problem: https://t.co/JcdTbhnLkyAll proofs were generated by… pic.twitter.com/U7TNafIn83— Kimon Fountoulakis (@kfountou) December 16, 2025
https://x.com/kfountou/status/2000957773584974298
Open Problem: Running time complexity of accelerated $\ell_1$-regularized PageRank
The results in Google Search, Twitter and other popular search engines traditionally utilize the Personalized PageRank (PPR) vector to rank the results in th...
https://proceedings.mlr.press/v178/open-problem-fountoulakis22a