論文の概要: 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ルールに匹敵するパフォーマンスを持つ。
関連論文リスト
- Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳(メタデータ) (2024-07-05T18:37:09Z) - Diversity-aware clustering: Computational Complexity and Approximation
Algorithms [19.67390261007849]
本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。
クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。
近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-01-10T19:01:05Z) - Clustering Mixtures of Bounded Covariance Distributions Under Optimal
Separation [44.25945344950543]
境界共分散分布の混合に対するクラスタリング問題について検討する。
このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。
我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
論文 参考訳(メタデータ) (2023-12-19T01:01:53Z) - Are Easy Data Easy (for K-Means) [0.0]
本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。
シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
論文 参考訳(メタデータ) (2023-08-02T09:40:19Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - 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) - Coresets for the Nearest-Neighbor Rule [78.15296214629433]
最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。
本稿では,最寄りの分類のためのコアセットの概念を紹介する。
そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-16T19:00:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。