論文の概要: Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors

• arxiv url: http://arxiv.org/abs/2202.02464v3
• Date: Fri, 6 Sep 2024 05:33:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-09 21:24:12.285043
• Title: Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors
• Title（参考訳）: 固定k$-Nearest Neighbors を用いたminimax Optimal Algorithms
• Authors: J. Jon Ryu, Young-Han Kim,
• Abstract要約: 大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。 分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。 十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
• 参考スコア（独自算出の注目度）: 13.231906521852718
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents how to perform minimax optimal classification, regression, and density estimation based on fixed-$k$ nearest neighbor (NN) searches. We consider a distributed learning scenario, in which a massive dataset is split into smaller groups, where the $k$-NNs are found for a query point with respect to each subset of data. We propose \emph{optimal} rules to aggregate the fixed-$k$-NN information for classification, regression, and density estimation that achieve minimax optimal rates for the respective problems. We show that the distributed algorithm with a fixed $k$ over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions. Roughly speaking, distributed $k$-NN rules with $M$ groups has a performance comparable to the standard $\Theta(kM)$-NN rules even for fixed $k$.
• Abstract（参考訳）: 本稿では,固定k$近辺(NN)探索に基づいて,最小値の分類,回帰,密度推定を行う方法を提案する。 大規模データセットを小さなグループに分割し,各サブセットに対するクエリポイントに対して$k$-NNを求める分散学習シナリオを検討する。 本稿では,各問題に対する最小値の最適値を達成するための分類,回帰,密度推定のために,固定k$-NN情報を集約する「emph{optimal}ルール」を提案する。 十分多数のグループに対して固定された$k$の分散アルゴリズムは、ある正規性条件下での乗算対数係数までの最小誤差率を達成することを示す。 大まかに言えば、$M$グループによる分散$k$-NNルールは、固定$k$であっても標準$\Theta(kM)$-NNルールに匹敵するパフォーマンスを持つ。

関連論文リスト

• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Bagged $k$-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets [7.208515071018781]
  モードベースのクラスタリング(textitBDMBC)のためのtextitbagged $k$-distance というアンサンブル学習アルゴリズムを提案する。 理論的には、bagged $k$-distance, sub-sample size $s$, bagging rounds $B$, and the number of neighbors $k_L$ for the localized level set, BDMBC can achieve optimal convergence rate for mode estimation。
  論文  参考訳（メタデータ） (2022-10-18T11:58:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  我々は、$k$-means問題に対する急激な局所解の構造について検討する。 分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
  論文  参考訳（メタデータ） (2020-02-16T22:15:03Z)

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

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