論文の概要: One-Nearest-Neighbor Search is All You Need for Minimax Optimal Regression and Classification

• arxiv url: http://arxiv.org/abs/2202.02464v1
• Date: Sat, 5 Feb 2022 01:59:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-08 18:41:47.864929
• Title: One-Nearest-Neighbor Search is All You Need for Minimax Optimal Regression and Classification
• Title（参考訳）: 最小限の回帰と分類に必要なのは一番近い検索
• Authors: J. Jon Ryu and Young-Han Kim
• Abstract要約: 本稿では, 十分多数のグループに対する$k=1$の分散アルゴリズムが, ある正規性条件下での乗算対数係数までの最小誤差率を達成することを示す。 分析では, 改良された集約法による代替ルールを提案し, 正確な最小値の最適値が得られることを示した。
• 参考スコア（独自算出の注目度）: 22.98602552223454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Qiao, Duan, and Cheng~(2019) proposed a distributed nearest-neighbor classification method, in which a massive dataset is split into smaller groups, each processed with a $k$-nearest-neighbor classifier, and the final class label is predicted by a majority vote among these groupwise class labels. This paper shows that the distributed algorithm with $k=1$ over a sufficiently large number of groups attains a minimax optimal error rate up to a multiplicative logarithmic factor under some regularity conditions, for both regression and classification problems. Roughly speaking, distributed 1-nearest-neighbor rules with $M$ groups has a performance comparable to standard $\Theta(M)$-nearest-neighbor rules. In the analysis, alternative rules with a refined aggregation method are proposed and shown to attain exact minimax optimal rates.
• Abstract（参考訳）: 近年,Qiao,Duan,Cheng~(2019) は,大規模データセットを小さなグループに分割し,それぞれが$k$-nearest-neighbor分類器で処理し,最終クラスラベルをこれらのグループワイドクラスラベルの多数投票によって予測する分散近傍分類法を提案した。 本稿では,ある正規性条件下での乗算対数係数までの最小誤差率を,回帰問題と分類問題の両方に対して,十分な数のグループに対して$k=1$の分散アルゴリズムが達成可能であることを示す。 大まかに言えば、分散1-nearest-neighborルールは$m$グループで、標準の$\theta(m)$-nearest-neighborルールに匹敵するパフォーマンスを持つ。 分析では, 改良された集約法による代替ルールを提案し, 最適な最小値が得られることを示した。

関連論文リスト

• 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)

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

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