論文の概要: 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ルールに匹敵するパフォーマンスを持つ。
分析では, 改良された集約法による代替ルールを提案し, 最適な最小値が得られることを示した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。