論文の概要: Efficient and Local Parallel Random Walks

• arxiv url: http://arxiv.org/abs/2112.00655v1
• Date: Wed, 1 Dec 2021 17:06:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-02 15:56:40.830366
• Title: Efficient and Local Parallel Random Walks
• Title（参考訳）: 効率的かつ局所的なランダムウォーク
• Authors: Michael Kapralov, Silvio Lattanzi, Navid Nouri, Jakab Tardos
• Abstract要約: ランダムウォークは、多くの機械学習アルゴリズムで使用される基本的なプリミティブである。 ランダムウォークを効率的に局所的に構築することで,この制限を克服するアルゴリズムを提案する。 本手法はメモリとラウンド効率の両方で,特に並列局所クラスタリングアルゴリズムを効率よく実現している。
• 参考スコア（独自算出の注目度）: 21.29022677162416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random walks are a fundamental primitive used in many machine learning algorithms with several applications in clustering and semi-supervised learning. Despite their relevance, the first efficient parallel algorithm to compute random walks has been introduced very recently (Lacki et al.). Unfortunately their method has a fundamental shortcoming: their algorithm is non-local in that it heavily relies on computing random walks out of all nodes in the input graph, even though in many practical applications one is interested in computing random walks only from a small subset of nodes in the graph. In this paper, we present a new algorithm that overcomes this limitation by building random walk efficiently and locally at the same time. We show that our technique is both memory and round efficient, and in particular yields an efficient parallel local clustering algorithm. Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches.
• Abstract（参考訳）: ランダムウォークは、クラスタリングと半教師付き学習にいくつかの応用がある多くの機械学習アルゴリズムで使用される基本的なプリミティブである。 その関連性にもかかわらず、ランダムウォークを計算するための最初の効率的な並列アルゴリズムが最近導入された(Lacki et al.)。 彼らのアルゴリズムは、多くの実用的なアプリケーションにおいて、グラフの小さなサブセットからのみランダムウォークを計算することに関心があるにもかかわらず、入力グラフのすべてのノードからランダムウォークの計算に大きく依存しているため、非ローカルである。 本稿では,ランダムウォークを効率的かつ局所的に構築することにより,この制限を克服する新しいアルゴリズムを提案する。 提案手法はメモリ効率とラウンド効率の両方であり,特に効率的な並列局所クラスタリングアルゴリズムを実現する。 最後に,提案アルゴリズムが従来の手法よりもはるかにスケーラブルであることを示す実験結果と理論解析を補完する。

関連論文リスト

• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。 我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
  論文  参考訳（メタデータ） (2024-05-08T09:25:39Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
  論文  参考訳（メタデータ） (2021-10-21T19:16:16Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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