論文の概要: Learning to Hash Robustly, with Guarantees

• arxiv url: http://arxiv.org/abs/2108.05433v1
• Date: Wed, 11 Aug 2021 20:21:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-13 14:23:31.592803
• Title: Learning to Hash Robustly, with Guarantees
• Title（参考訳）: 保証付きでロバストにハッシュを学習する
• Authors: Alexandr Andoni, Daniel Beaglehole
• Abstract要約: 本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
• 参考スコア（独自算出の注目度）: 79.68057056103014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The indexing algorithms for the high-dimensional nearest neighbor search (NNS) with the best worst-case guarantees are based on the randomized Locality Sensitive Hashing (LSH), and its derivatives. In practice, many heuristic approaches exist to "learn" the best indexing method in order to speed-up NNS, crucially adapting to the structure of the given dataset. Oftentimes, these heuristics outperform the LSH-based algorithms on real datasets, but, almost always, come at the cost of losing the guarantees of either correctness or robust performance on adversarial queries, or apply to datasets with an assumed extra structure/model. In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms, while optimizing the hashing to the structure of the dataset (think instance-optimal algorithms) for performance on the minimum-performing query. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. On the theoretical side, we exhibit a natural setting (dataset model) where our algorithm is much better than the standard theoretical one. On the practical side, we run experiments that show that our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.
• Abstract（参考訳）: 高次元近傍探索 (nns) の最大値保証付きインデックス化アルゴリズムは、ランダム化局所性センシティブハッシュ (lsh) とその導関数に基づいている。 実際、多くのヒューリスティックなアプローチは、与えられたデータセットの構造に決定的に適応するNNSを高速化するために、最良のインデックス法を「学習」するために存在する。 多くの場合、これらのヒューリスティックスは実際のデータセット上でLSHベースのアルゴリズムよりも優れていますが、ほとんどの場合、敵クエリにおける正確性または堅牢なパフォーマンスの保証を失うか、仮定された余分な構造/モデルを持つデータセットに適用するコストがかかります。 本稿では,Hamming 空間に対する NNS アルゴリズムを設計し,理論的アルゴリズムと本質的に一致することを保証し,最小性能のクエリの性能向上のために,ハッシュをデータセットの構造(インスタンス最適化アルゴリズムなど)に最適化する。 アルゴリズムが与えられたデータセットに対して理論的かつ実際的に最適化する能力を評価する。 理論的には、我々のアルゴリズムが標準的な理論よりもずっと優れている自然設定(データセットモデル)を示す。 実用面では、我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリに対して、1.8倍と2.1倍のリコールがあることを示す実験を行っている。

関連論文リスト

• Adversarially robust clustering with optimality guarantees [7.0830450321883935]
  我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。 ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。 本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-16T17:17:07Z)
• Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
  我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。 提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
  論文  参考訳（メタデータ） (2023-03-01T18:49:10Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Streaming Algorithms for High-Dimensional Robust Statistics [43.106438224356175]
  ほぼ最適なメモリ要件を持つ高次元ロバスト統計のための,最初の効率的なストリーミングアルゴリズムを開発した。 本研究の主な成果は,ハマー汚染モデルにおける高次元ロバスト平均推定の課題である。
  論文  参考訳（メタデータ） (2022-04-26T15:57:07Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Benchmarking Simulation-Based Inference [5.3898004059026325]
  確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。 推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。 性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
  論文  参考訳（メタデータ） (2021-01-12T18:31:22Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Sampling for Predictor-Based Neural Architecture Search [3.287802528135173]
  ニューラルネットワーク探索のための予測器に基づくNASアルゴリズムについて検討する。 探索空間のサブセットに対してのみプロキシが計算されると,予測アルゴリズムのサンプル効率が劇的に低下することを示す。 これは、実際に予測器ベースのNASアルゴリズムを有用にするための重要なステップである。
  論文  参考訳（メタデータ） (2020-11-24T11:36:36Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)

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

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