論文の概要: Minimax Limits of k-Fold Cross-Validation via Majority

• arxiv url: http://arxiv.org/abs/2605.25859v1
• Date: Mon, 25 May 2026 13:50:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:20.231002
• Title: Minimax Limits of k-Fold Cross-Validation via Majority
• Title（参考訳）: 多数性によるk-Foldクロスバリデーションのミニマックス限界
• Authors: Ido Nachum, Rüdiger Urbanke, Thomas Weinberger,
• Abstract要約: リスク推定器としての$k$-foldクロスバリデーションの平均二乗誤差について検討し、その精度が$k$の折りたたみ数に依存するかに着目した。 本研究は,データ再利用戦略としてのクロスバリデーションの基本的限界を明らかにし,従来の理論的研究におけるギャップと不正確さを明らかにし,クロスバリデーションの厳密な分析が説明できるような自然なベンチマークとして,アルゴリズムを位置づけた。
• 参考スコア（独自算出の注目度）: 3.3008315224941978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the mean-squared error of $k$-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds $k$. Despite the widespread use of cross-validation, principled guidance for choosing $k$ is largely absent, mainly due to the complex dependence between fold-wise error estimates. To obtain sharp and interpretable results, we focus on the majority algorithm in binary classification, a minimal yet nontrivial empirical risk minimization procedure. We provide a fine-grained analysis of its cross-validation behavior, showing that even this simple algorithm exhibits subtle and delicate phenomena for which existing theory provides loose and even vacuous bounds. Leveraging this analysis, we introduce a minimax framework for cross-validation risk estimation and prove that no empirical risk minimization algorithm can achieve an $O(1/n)$ minimax mean-squared error when the number of folds grows with the number of samples $n$; instead, a lower bound of order $Ω(\sqrt{k}/n)$ is unavoidable. Our results reveal fundamental limitations of cross-validation as a data-reuse strategy, clarify gaps and inaccuracies in prior theoretical work, and position the majority algorithm as a natural benchmark that any tight analysis of cross-validation should be able to explain.
• Abstract（参考訳）: リスク推定器としての$k$-foldクロスバリデーションの平均二乗誤差について検討し、その精度が$k$の折りたたみ数に依存するかに着目した。 クロスバリデーションが広く使われているにもかかわらず、$k$を選択するための原則的なガイダンスは、主に折りたたみ誤差推定の複雑な依存のため、ほとんど欠落している。 シャープかつ解釈可能な結果を得るために、我々は二分分類における大多数のアルゴリズム、最小でも非自明な経験的リスク最小化手法に焦点を当てた。 この単純なアルゴリズムでさえ、既存の理論がゆるく、あるいは空白な境界を提供する微妙で微妙な現象を示すことを示す。 この分析を応用して、クロスバリデーションリスク推定のためのミニマックスフレームワークを導入し、実験的なリスク最小化アルゴリズムがサンプル数$n$で折りたたみ数が増加すると$O(1/n)$ minimax平均二乗誤差を達成できないことを証明し、代わりに、下位のオーダー$Ω(\sqrt{k}/n)$は避けられない。 本研究は,データ再利用戦略としてのクロスバリデーションの基本的限界を明らかにし,従来の理論的研究におけるギャップと不正確さを明らかにし,クロスバリデーションの厳密な分析が説明できるような自然なベンチマークとして,アルゴリズムを位置づけた。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits [3.3008315224941978]
  アルゴリズム分布対の性質が$k$-foldクロスバリデーションにおける折りたたみ数の選択にどのように影響するかを示す。 また、CVが$n$の検証セットによって1/n$達成可能なオーダーの最適値を得ることができないことも証明する。
  論文  参考訳（メタデータ） (2025-11-05T15:35:46Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Causality Pursuit from Heterogeneous Environments via Neural Adversarial Invariance Learning [12.947265104477237]
  データから因果関係を抽出することは、科学的発見、治療介入、伝達学習における根本的な問題である。 本稿では,複数の環境における回帰モデルにおける非パラメトリック不変性と因果学習に対処するアルゴリズムを提案する。 提案したFocused Adrial Invariant Regularizationフレームワークは、逆検定により回帰モデルを予測不変解へ向ける革新的なミニマックス最適化手法を利用する。
  論文  参考訳（メタデータ） (2024-05-07T23:37:40Z)
• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  半教師付き学習(SSL)のための最悪ケース整合正則化手法を提案する。 本稿では,ラベル付きトレーニングデータとラベル付きトレーニングデータとを別々に比較した経験的損失項からなるSSLの一般化について述べる。 この境界によって動機づけられたSSLの目的は、元のラベルのないサンプルと、その複数の拡張版との最大の矛盾を最小限に抑えるものである。
  論文  参考訳（メタデータ） (2022-09-26T12:04:49Z)
• Robust Unsupervised Learning via L-Statistic Minimization [38.49191945141759]
  教師なし学習に焦点をあて、この問題に対する一般的なアプローチを提示する。 重要な仮定は、摂動分布は、許容モデルの特定のクラスに対するより大きな損失によって特徴付けられることである。 教師なし学習におけるいくつかのポピュラーモデルに対する提案基準に関して,一様収束境界を証明した。
  論文  参考訳（メタデータ） (2020-12-14T10:36:06Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。 混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2020-06-19T22:49:42Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions [19.439945058410203]
  高次元状態におけるサンプル外リスク推定の問題について検討する。 広範囲にわたる経験的証拠は、アウト・ワン・アウト・クロス・バリデーションの正確さを裏付ける。 この理論の技術的利点の1つは、拡張可能な近似LOに関する最近の文献から得られたいくつかの結果を明確化し、接続することができることである。
  論文  参考訳（メタデータ） (2020-03-03T20:07:07Z)

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

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