論文の概要: Faster Maximum Inner Product Search in High Dimensions

• arxiv url: http://arxiv.org/abs/2212.07551v1
• Date: Wed, 14 Dec 2022 23:46:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-16 16:06:27.621852
• Title: Faster Maximum Inner Product Search in High Dimensions
• Title（参考訳）: 高次元における最大内積探索の高速化
• Authors: Mo Tiwari, Ryan Kang, Je-Yong Lee, Luke Lee, Chris Piech, Sebastian Thrun, Ilan Shomorony, Martin Jinye Zhang
• Abstract要約: 本稿では,BanditMIPSと呼ばれる高次元の内積探索問題に対する最先端のアルゴリズムを提案する。 BanditMIPSは、マルチアームバンディットからテクニックを借りてMIPS問題をベストアーム識別問題に還元するランダム化アルゴリズムである。 実世界の高次元データセットでは、BanditMIPSは既存のアプローチの約12倍の速度で動作し、同じソリューションを返す。
• 参考スコア（独自算出の注目度）: 13.951262463110455
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximum Inner Product Search (MIPS) is a popular problem in the machine learning literature due to its applicability in a wide array of applications, such as recommender systems. In high-dimensional settings, however, MIPS queries can become computationally expensive as most existing solutions do not scale well with data dimensionality. In this work, we present a state-of-the-art algorithm for the MIPS problem in high dimensions, dubbed BanditMIPS. BanditMIPS is a randomized algorithm that borrows techniques from multi-armed bandits to reduce the MIPS problem to a best-arm identification problem. BanditMIPS reduces the complexity of state-of-the-art algorithms from $O(\sqrt{d})$ to $O(\text{log}d)$, where $d$ is the dimension of the problem data vectors. On high-dimensional real-world datasets, BanditMIPS runs approximately 12 times faster than existing approaches and returns the same solution. BanditMIPS requires no preprocessing of the data and includes a hyperparameter that practitioners may use to trade off accuracy and runtime. We also propose a variant of our algorithm, named BanditMIPS-$\alpha$, which employs non-uniform sampling across the data dimensions to provide further speedups.
• Abstract（参考訳）: 最大内積探索(maximum inner product search, mips)は、レコメンダシステムなど、幅広いアプリケーションに適用可能なため、機械学習文献において一般的な問題である。 しかし、高次元設定では、既存のほとんどのソリューションがデータ次元に合わないため、MIPSクエリは計算コストが高くなる可能性がある。 本研究では,BanditMIPSと呼ばれる高次元のMIPS問題に対する最先端のアルゴリズムを提案する。 BanditMIPSは、マルチアームバンディットからテクニックを借りてMIPS問題をベストアーム識別問題に還元するランダム化アルゴリズムである。 BanditMIPSは、最先端アルゴリズムの複雑さを$O(\sqrt{d})$から$O(\text{log}d)$に還元する。 実世界の高次元データセットでは、BanditMIPSは既存のアプローチの約12倍高速に動作し、同じソリューションを返す。 BanditMIPSはデータの事前処理を必要とせず、実践者が正確性と実行をトレードオフするために使用するハイパーパラメータを含んでいる。 また、データ次元をまたいだ一様サンプリングを用いてさらなる高速化を実現するBanditMIPS-$\alpha$というアルゴリズムの変種を提案する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
  決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-01T15:22:12Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat\'ern Correlations [23.560067934682294]
  マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。 提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
  論文  参考訳（メタデータ） (2022-03-07T03:30:35Z)
• Quantum Algorithms for Reinforcement Learning with a Generative Model [16.168901236223117]
  強化学習は、エージェントがその累積報酬を最大化するために環境とどのように相互作用するかを研究する。 最適ポリシー(pi*$)、最適値関数(v*$)、最適値関数(q*$)を近似する量子アルゴリズムを設計する。 一致する量子下界を証明して、q*$を計算するための量子アルゴリズムが最適であることを示す。
  論文  参考訳（メタデータ） (2021-12-15T19:51:49Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits [16.1767275655842]
  現在の$k$-medoidsクラスタリングアルゴリズム、例えば、PAM(Partitioning Around Medoids)は反復的であり、各イテレーションで$n$のデータセットサイズであり、大規模なデータセットでは極めて高価である。 マルチアームバンディットの技法にインスパイアされたランダム化アルゴリズムであるBanditPAMを提案する。これは、PAMの繰り返しの複雑さを$O(n2)$から$O(n log n)$に減らし、実際に保持されるデータに対する仮定の下で、高い確率で同じ結果を返す。 我々は、コーディングを含むいくつかの大規模な実世界のデータセットで実験的に結果を検証する。
  論文  参考訳（メタデータ） (2020-06-11T22:17:16Z)
• Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
  本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。 アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。 新規検索戦略として$dyaPM$と$hiePM$が提案されている。
  論文  参考訳（メタデータ） (2020-05-15T22:40:18Z)

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

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