证明经典加速方法在ℓ₁正则化PageRank中可能比普通方法更差，但稍强正则化下可实现加速。
Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
- 构造反例证明FISTA在某些场景下比ISTA更慢
- 在略强正则化下，得到加速项(ρ√α)⁻¹log(α/ε)与边界开销项√vol(B)/(ρα³⁄²)
- 给出图结构条件保证边界约束，适合关注优化理论的读者
我们研究使用标准加速近端梯度法（FISTA）计算ℓ₁-正则化PageRank所需的度加权工作量。对于非加速方法（ISTA），已知最坏情况下的工作量为$ ilde{O}((αρ)^{-1})$，其中$α$是随机跳转参数，$ρ$是ℓ₁正则化参数。目前尚不清楚经典加速方法是否能在保持$1/ρ$局部性的同时将$1/α$提升至$1/\sqrt{α}$，或是否会渐近更差。针对FISTA，我们通过构造一类实例，证明其在某些情况下渐近比ISTA更差。另一方面，我们分析了在稍强正则化目标上的FISTA，并证明在特定约束条件下，所有虚假激活均保留在边界集$\mathcal{B}$内。由此得到一个包含加速项$(ρ\sqrt{α})^{-1}\log(α/\varepsilon)$和边界开销项$\sqrt{\text{vol}(\mathcal{B})}/(ρα^{3/2})$的上界。同时提供了图结构的充分条件以确保该约束成立。
原文摘要 · Abstract (English)
We study the degree-weighted work required to compute $\ell_1$-regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (ISTA), the best known worst-case work is $\widetilde{O}((αρ)^{-1})$, where $α$ is the teleportation parameter and $ρ$ is the $\ell_1$-regularization parameter. It is not known whether classical acceleration methods can improve $1/α$ to $1/\sqrtα$ while preserving the $1/ρ$ locality scaling, or whether they can be asymptotically worse. For FISTA, we show a negative result by constructing a family of instances for which standard FISTA is asymptotically worse than ISTA. On the positive side, we analyze FISTA on a slightly over-regularized objective and show that, under a 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 also provide graph-structural sufficient conditions that imply such confinement.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。