Search papers, labs, and topics across Lattice.
This paper analyzes the complexity of using FISTA to compute $\ell_1$-regularized PageRank, focusing on whether acceleration can improve the dependence on the teleportation parameter α from $1/α$ to $1/\sqrtα$ without losing locality. They show that under a confinement condition, spurious activations remain within a boundary set, leading to a complexity bound with an accelerated term and a boundary overhead. The paper provides graph-structural conditions for this confinement and validates the theoretical findings with experiments on synthetic and real graphs.
FISTA's acceleration benefits for $\ell_1$-regularized PageRank are not guaranteed, with performance hinging on a confinement condition that dictates whether spurious node activations remain within a manageable boundary set.
We study the degree-weighted work required to compute $\ell_1$-regularized PageRank using the standard one-gradient-per-iteration accelerated proximal-gradient method (FISTA). For non-accelerated local methods, the best known worst-case work scales as $\widetilde{O} ((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. A natural question is whether FISTA can improve the dependence on $α$ from $1/α$ to $1/\sqrtα$ while preserving the $1/ρ$ locality scaling. The challenge is that acceleration can break locality by transiently activating nodes that are zero at optimality, thereby increasing the cost of gradient evaluations. We analyze FISTA on a slightly over-regularized objective and show that, under a checkable confinement condition, all spurious activations remain inside a boundary set $\mathcal{B}$. This yields a bound consisting of an accelerated $(ρ\sqrtα)^{-1}\log(α/\varepsilon)$ term plus a boundary overhead $\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$. We provide graph-structural conditions that imply such confinement. Experiments on synthetic and real graphs show the resulting speedup and slowdown regimes under the degree-weighted work model.
