論文の概要: Minimum discrepancy principle strategy for choosing $k$ in $k$-NN
regression
- arxiv url: http://arxiv.org/abs/2008.08718v4
- Date: Wed, 5 May 2021 11:33:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 03:15:28.967869
- Title: Minimum discrepancy principle strategy for choosing $k$ in $k$-NN
regression
- Title(参考訳): $k$-NNレグレッションにおける$k$の選択のための最小不一致原理戦略
- Authors: Yaroslav Averyanov and Alain Celisse
- Abstract要約: 我々は、$k$-NN回帰推定器において、ハイパーパラメータ$k$を選択するための新しいデータ駆動戦略を示す。
本稿では,早期停止と最小一致原理に基づく実践的戦略を実践的に容易に導入することを提案する。
この戦略は、一般化されたクロスバリデーションまたはAkaikeのAIC基準の計算時間を$mathcalOleft(n3 right)$から$mathcalOleft(n2 (n - k) right)$に短縮する。
- 参考スコア(独自算出の注目度): 2.132096006921048
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a novel data-driven strategy to choose the hyperparameter $k$ in
the $k$-NN regression estimator. We treat the problem of choosing the
hyperparameter as an iterative procedure (over $k$) and propose using an easily
implemented in practice strategy based on the idea of early stopping and the
minimum discrepancy principle. This model selection strategy is proven to be
minimax-optimal, under the fixed-design assumption on covariates, over some
smoothness function classes, for instance, the Lipschitz functions class on a
bounded domain. The novel method often improves statistical performance on
artificial and real-world data sets in comparison to other model selection
strategies, such as the Hold-out method and 5-fold cross-validation. The
novelty of the strategy comes from reducing the computational time of the model
selection procedure while preserving the statistical (minimax) optimality of
the resulting estimator. More precisely, given a sample of size $n$, assuming
that the nearest neighbors are already precomputed, if one should choose $k$
among $\left\{ 1, \ldots, n \right\}$, the strategy reduces the computational
time of the generalized cross-validation or Akaike's AIC criteria from
$\mathcal{O}\left( n^3 \right)$ to $\mathcal{O}\left( n^2 (n - k) \right)$,
where $k$ is the proposed (minimum discrepancy principle) value of the nearest
neighbors. Code for the simulations is provided at
https://github.com/YaroslavAveryanov/Minimum-discrepancy-principle-for-choosing-k.
- Abstract(参考訳): 我々は,$k$-nn回帰推定器のハイパーパラメータ$k$を選択するための新しいデータ駆動戦略を提案する。
我々は,ハイパーパラメータを反復的手順 ($k$以上) として選択する問題を扱い,早期停止の考え方と最小差分原理に基づく実践的戦略を用いて提案する。
このモデル選択戦略は、いくつかの滑らかな函数クラス、例えば有界領域上のリプシッツ函数クラスに対する共変量に対する固定設計仮定の下で、ミニマックス最適であることが証明されている。
この新しい手法は、ホールドアウト法や5倍クロスバリデーション法といった他のモデル選択戦略と比較して、人工および実世界のデータセットの統計性能をしばしば改善する。
戦略の新規性は、モデル選択手順の計算時間を短縮し、結果の推定器の統計的(極小)最適性を保ちながら得られる。
より正確には、サイズ n$ のサンプルが与えられたとき、最寄りの近傍が既に事前計算されていると仮定し、もし$\left\{ 1, \ldots, n \right\}$ の中から $k$ を選ぶと、戦略は、一般のクロスバリデーションまたはアカイケの aic 基準の計算時間を$\mathcal{o}\left(n^3 \right)$ to $\mathcal{o}\left(n^2 (n - k) \right)$ から減少させる。
シミュレーションのコードはhttps://github.com/yaroslavaveryanov/minimum-discrepancy-principle-for-choosing-kで提供されている。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Bayes beats Cross Validation: Efficient and Accurate Ridge Regression
via Expectation Maximization [3.061662434597098]
本稿では,正規化ハイパーパラメータである$lambda$について,LOOCV(Left-out-out Cross-validation)よりも高速に計算できる手法を提案する。
提案手法は,比較的穏やかな条件下で,十分大きな$n$に対して,一意の最適解を求めることが保証されている。
論文 参考訳(メタデータ) (2023-10-29T01:13:55Z) - Settling the Sample Complexity of Online Reinforcement Learning [100.52613756483589]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳(メタデータ) (2023-06-28T17:43:19Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳(メタデータ) (2022-11-29T18:38:40Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Regression via Implicit Models and Optimal Transport Cost Minimization [5.144809478361603]
条件付きGAN (CGAN) が回帰に適用されている。
現在のCGAN実装では、古典的なジェネレータ-ディスクリミネータアーキテクチャを使用している。
実確率分布$p(y|x)$と推定分布$hatp(y|x)$との間の最適輸送コストを直接最適化する解を提案する。
論文 参考訳(メタデータ) (2020-03-03T02:26:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。