論文の概要: The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits

• arxiv url: http://arxiv.org/abs/2511.03554v1
• Date: Wed, 05 Nov 2025 15:35:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 18:19:32.466861
• Title: The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits
• Title（参考訳）: クロスバリデーション誤差の構造:安定性、共分散およびミニマックス限界
• Authors: Ido Nachum, Rüdiger Urbanke, Thomas Weinberger,
• Abstract要約: アルゴリズム分布対の性質が$k$-foldクロスバリデーションにおける折りたたみ数の選択にどのように影響するかを示す。 また、CVが$n$の検証セットによって1/n$達成可能なオーダーの最適値を得ることができないことも証明する。
• 参考スコア（独自算出の注目度）: 3.3008315224941978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite ongoing theoretical research on cross-validation (CV), many theoretical questions about CV remain widely open. This motivates our investigation into how properties of algorithm-distribution pairs can affect the choice for the number of folds in $k$-fold cross-validation. Our results consist of a novel decomposition of the mean-squared error of cross-validation for risk estimation, which explicitly captures the correlations of error estimates across overlapping folds and includes a novel algorithmic stability notion, squared loss stability, that is considerably weaker than the typically required hypothesis stability in other comparable works. Furthermore, we prove: 1. For every learning algorithm that minimizes empirical error, a minimax lower bound on the mean-squared error of $k$-fold CV estimating the population risk $L_\mathcal{D}$: \[ \min_{k \mid n}\; \max_{\mathcal{D}}\; \mathbb{E}\!\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{\mathcal{D}}\big)^{2}\right] \;=\; \Omega\!\big(\sqrt{k}/n\big), \] where $n$ is the sample size and $k$ the number of folds. This shows that even under idealized conditions, for large values of $k$, CV cannot attain the optimum of order $1/n$ achievable by a validation set of size $n$, reflecting an inherent penalty caused by dependence between folds. 2. Complementing this, we exhibit learning rules for which \[ \max_{\mathcal{D}}\; \mathbb{E}\!\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{\mathcal{D}}\big)^{2}\right] \;=\; \Omega(k/n), \] matching (up to constants) the accuracy of a hold-out estimator of a single fold of size $n/k$. Together these results delineate the fundamental trade-off in resampling-based risk estimation: CV cannot fully exploit all $n$ samples for unbiased risk evaluation, and its minimax performance is pinned between the $k/n$ and $\sqrt{k}/n$ regimes.
• Abstract（参考訳）: CV (cross-validation) に関する理論的研究が進行中であるにもかかわらず、CVに関する多くの理論的疑問が広く開かれている。 このことは、アルゴリズム分布対の性質が$k$-foldクロスバリデーションにおける折りたたみ数の選択にどのように影響するかを調査する動機となっている。 この結果は、重なり合う折り畳みの誤差推定の相関を明示的に捉え、新しいアルゴリズム的安定性の概念である2乗損失安定性を含む、リスク推定における平均二乗誤差の新たな分解から成り立っている。 さらに, 経験的誤差を最小限に抑える学習アルゴリズムについて, 平均二乗誤差の最小値が$k$-fold CVで, 集団リスクを推定する最小値が$L_\mathcal{D}$: \[ \min_{k \mid n}\; \max_{\mathcal{D}}\; \mathbb{E}\! \left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{\mathcal{D}}\big)^{2}\right] \;=\; \Omega\! \big(\sqrt{k}/n\big), \] ここで$n$はサンプルサイズ、$k$は折りたたみ数である。 これは、理想化された条件の下でも、大きな値が$k$であっても、CVは、折り畳み間の依存によって引き起こされる固有のペナルティを反映して、$n$の検証セットによって1/n$の最適値を得ることができないことを示している。 2.これを補完して, \[ \max_{\mathcal{D}}\; \mathbb{E}\! \left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{\mathcal{D}}\big)^{2}\right] \;=\; \Omega(k/n), \] マッチング(定数まで) サイズ$n/k$のホールドアウト推定子の精度。 CVは非バイアスリスク評価のためにすべての$n$サンプルをフルに活用することができず、そのミニマックス性能は$k/n$と$\sqrt{k}/n$レジームの間で固定される。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model [13.582475656749775]
  リスクに敏感な強化学習(RL)のサンプル複雑性問題を生成モデルを用いて検討する。 この問題のサンプル複雑性に基づいて,上界と下界にほぼ一致する境界を定めている。
  論文  参考訳（メタデータ） (2025-03-11T22:31:03Z)
• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
  楕円分布の共分散/散乱行列の計算効率の良いロバスト推定問題について検討する。 ガウスのケースを超えて拡張される、計算可能で、ほぼ最適な、ほぼ最適な共分散推定器を初めて得る。
  論文  参考訳（メタデータ） (2025-02-10T15:31:57Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Rademacher upper bounds for cross-validation errors with an application to the lasso [6.837167110907022]
  我々は、K$-foldクロスバリデーション(K$-CV)エラーに対する一般的な上限を確立する。 CV誤差上限は軽テール分布と重テール誤差分布の両方に適用される。 CVエラー上限を$K$-CVベースのアルゴリズムで計算するためのPythonパッケージを提供する。
  論文  参考訳（メタデータ） (2020-07-30T17:13:03Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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