論文の概要: Iterative Methods via Locally Evolving Set Process

• arxiv url: http://arxiv.org/abs/2410.15020v1
• Date: Sat, 19 Oct 2024 07:28:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:17:39.920109
• Title: Iterative Methods via Locally Evolving Set Process
• Title（参考訳）: 局所進化的集合過程による反復的手法
• Authors: Baojian Zhou, Yifan Sun, Reza Babanezhad Harikandeh, Xingzhi Guo, Deqing Yang, Yanghua Xiao,
• Abstract要約: Approximate Personalized PageRank (APPR)はGauss-Seidelのローカル版である。 我々はAPPRが新しいランタイム境界である$tildeO(overlineoperatornamevol(S_t)/overlinegamma_t leq 1/epsilon$を認めたことを示す。 計算結果は,本フレームワークの効率を確認し,実世界のグラフ上で対応する標準解法よりも100倍の高速化を示す。
• 参考スコア（独自算出の注目度）: 43.405427507066065
• License:
• Abstract: Given the damping factor $\alpha$ and precision tolerance $\epsilon$, \citet{andersen2006local} introduced Approximate Personalized PageRank (APPR), the \textit{de facto local method} for approximating the PPR vector, with runtime bounded by $\Theta(1/(\alpha\epsilon))$ independent of the graph size. Recently, \citet{fountoulakis2022open} asked whether faster local algorithms could be developed using $\tilde{O}(1/(\sqrt{\alpha}\epsilon))$ operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of \textit{whether standard iterative solvers can be effectively localized}. We propose to use the \textit{locally evolving set process}, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let $\overline{\operatorname{vol}}{ (S_t)}$ and $\overline{\gamma}_{t}$ be the running average of volume and the residual ratio of active nodes $\textstyle S_{t}$ during the process. We show $\overline{\operatorname{vol}}{ (S_t)}/\overline{\gamma}_{t} \leq 1/\epsilon$ and prove APPR admits a new runtime bound $\tilde{O}(\overline{\operatorname{vol}}(S_t)/(\alpha\overline{\gamma}_{t}))$ mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is $\Theta(\sqrt{\alpha})$, then there exists $c \in (0,2)$ such that the local Chebyshev method has runtime $\tilde{O}(\overline{\operatorname{vol}}(S_{t})/(\sqrt{\alpha}(2-c)))$ without the monotonicity assumption. Numerical results confirm the efficiency of this novel framework and show up to a hundredfold speedup over corresponding standard solvers on real-world graphs.
• Abstract（参考訳）: 減衰係数 $\alpha$ と精度耐性 $\epsilon$, \citet{andersen2006local} が与えられたとき、PPRベクトルを近似する Approximate Personalized PageRank (APPR) が導入された。 最近 \citet{fountoulakis2022open} は $\tilde{O}(1/(\sqrt{\alpha}\epsilon))$ 演算を用いて高速な局所アルゴリズムを開発できるかどうかを尋ねた。 本稿では,APPRがGauss-Seidelの局所変種であることに気付き,標準反復解法を効果的に局所化できるかどうかを問う。 本稿では,アルゴリズムの局所性を特徴付ける新しいフレームワークである‘textit{locally evolution set process} を用い,多くの標準解法を効果的に局所化できることを実証する。 ここで、$\overline{\operatorname{vol}}{ (S_t)}$ と $\overline{\gamma}_{t}$ を、その過程でアクティブノード $\textstyle S_{t}$ のランニング平均と残余比とする。 我々は$\overline{\operatorname{vol}}{ (S_t)}/\overline{\gamma}_{t} \leq 1/\epsilon$を示し、APPRが新しいランタイム境界である$\tilde{O}(\overline{\operatorname{vol}}(S_t)/(\alpha\overline{\gamma}_{t})を許容することを証明している。 さらに、残留還元の幾何平均が $\Theta(\sqrt{\alpha})$ であるとき、局所チェビシェフ法が単調性仮定なしで、ランタイム $\tilde{O}(\overline{\operatorname{vol}}(S_{t})/(\sqrt{\alpha}(2-c))$ を持つような$c \in (0,2)$ が存在する。 計算結果は,本フレームワークの効率を確認し,実世界のグラフ上で対応する標準解法よりも100倍の高速化を示す。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。 本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
  論文  参考訳（メタデータ） (2023-05-25T17:13:08Z)
• On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning [37.63373979256335]
  協調的な$N$エージェントネットワークでは、エージェントに対してローカルに実行可能なポリシーを設計できることを示す。 また,ローカルポリシーを明示的に構築するアルゴリズムも考案した。
  論文  参考訳（メタデータ） (2022-09-07T23:15:08Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
  我々は、ほとんどの方向において$bfu$と$nu=mathrmpoly(k)$に対して、$n=mathrmpoly(k)$測定を用いて、高い精度で$bfu$を推定するアルゴリズムを開発し、分析する。 数値実験により,非漸近的条件下でも良好な性能が得られた。
  論文  参考訳（メタデータ） (2021-10-04T02:10:47Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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