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.
