論文の概要: Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank

• arxiv url: http://arxiv.org/abs/2602.21138v1
• Date: Tue, 24 Feb 2026 17:35:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.866631
• Title: Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
• Title（参考訳）: $\ell_1$-regularized PageRank の古典的加速の複雑さ
• Authors: Kimon Fountoulakis, David Martínez-Rubio,
• Abstract要約: FISTAは1/$ローカリティスケーリングを保ちながら$$への依存を改善することができることを示す。 我々はFISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件下では、全ての刺激活性化が境界集合内に存在することを示す。 これにより、加速された$(sqrt)-1log(/varepsilon)$項と境界オーバーヘッド$sqrtvol(mathcalB)/(3/2)$からなるバウンダリが得られる。
• 参考スコア（独自算出の注目度）: 14.919427330415608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: FISTA法を用いて,$\ell_1$-regularized PageRank計算に必要な次数重み付け作業について検討した。 非加速ローカルメソッドの場合、最もよく知られた最悪の作業スケールは$\widetilde{O} ((αρ)^{-1})$、$α$はテレポーテーションパラメータ、$ρ$は$\ell_1$-regularizationパラメータである。 自然な問題は、FISTAが1/ρ$の局所性スケーリングを保ちながら、1/α$から1/\sqrtα$への依存を改善することができるかどうかである。 問題は、加速が最適でゼロのノードを過度に活性化することで局所性を壊し、勾配評価のコストを増大させることである。 我々は、FISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件の下では、全ての刺激的な活性化が境界集合$\mathcal{B}$内に残っていることを示す。 これにより、加速された$(ρ\sqrtα)^{-1}\log(α/\varepsilon)$項と境界オーバーヘッド$\sqrt{vol(\mathcal{B})}/(ρα^{3/2})$からなる境界が得られる。 このような閉じ込めを暗示するグラフ構造条件を提供する。 合成グラフと実グラフの実験は、次級重み付けされた作業モデルの下で、結果として生じるスピードアップと減速のレギュレーションを示している。

関連論文リスト

• Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization [27.377966916440432]
  上層問題と下層問題とが凸である場合、二レベル最適化のための$epsilon-gradient pointを求める複雑性を示す。 最近の研究は、一階スムーズな問題に対して$tildemathcalO(epsilon-4)$ lower boundを達成した、一階近似 F$2$SA を提案した。
  論文  参考訳（メタデータ） (2025-09-03T02:02:52Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification [19.32160757444549]
  非函数 $f(X)=phi(XXT)$ を$ntimes r$ factor matrix $X$ で最小化するために勾配降下を考える。 本稿では,勾配降下の収束率を線形に戻すための安価なプレコンディショナーを提案する。
  論文  参考訳（メタデータ） (2022-06-07T14:26:49Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。