論文の概要: 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で提供されている。

関連論文リスト

• Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization [55.98760097296213]
  iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。 本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
  論文  参考訳（メタデータ） (2023-11-03T13:20:11Z)
• 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)
• Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
  オフライン強化学習(RL)は、他のポリシによって収集されたトランジションの固定データセットから、ほぼ最適なポリシを学ぶことを目的としている。 本稿では,RLの線形プログラミング定式化に基づく原始双対最適化手法を提案する。
  論文  参考訳（メタデータ） (2023-05-22T11:45:23Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Streaming Sparse Linear Regression [1.8707139489039097]
  本稿では,データポイントが逐次到着したときのストリーミングデータを解析する新しいオンライン疎線形回帰フレームワークを提案する。 提案手法はメモリ効率が高く,厳密な制約付き凸性仮定を必要とする。
  論文  参考訳（メタデータ） (2022-11-11T07:31:55Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation [49.502277468627035]
  本稿では,関数近似を用いたバッチデータ強化学習の統計的理論について検討する。 記録履歴から新たな対象政策の累積値を推定するオフ・ポリティクス評価問題を考察する。
  論文  参考訳（メタデータ） (2020-02-21T19:20:57Z)

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

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