論文の概要: Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

• arxiv url: http://arxiv.org/abs/2605.13684v1
• Date: Wed, 13 May 2026 15:41:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:28.146043
• Title: Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
• Title（参考訳）: スケール・センシティブ・シャッター:最適スケールでの学習可能性と評価性
• Authors: Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine,
• Abstract要約: 実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
• 参考スコア（独自算出の注目度）: 54.65053906803857
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every $γ>0$, uniform convergence at scale $γ$, agnostic learnability at scale $γ/2$, and finiteness of the fat-shattering dimension at every scale $γ'>γ$ are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical $\ell_\infty$ covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale $γ$: an $O(\log^2 n)$ bound holds already at scale $γ/2$, while an $O(\log n)$ bound holds at scale $2γ$. We further show that the $O(\log^2 n)$ bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor $c<3$, while $3$-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.
• Abstract（参考訳）: 実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 我々の主な結果は、すべての有界実数値類とすべての$γ>0$に対して、スケール$γ$における一様収束、スケール$γ/2$における無知学習性、スケール$γ'>γ$における脂肪散乱次元の有限性である。 これは、Anthony and Bartlett (Cambridge Univ. Press 1999) による学習可能性の正確な尺度に関する質問を解決し、フィル・ロング(Phil Long)による、乗法的2要素ギャップは避けられないという予想に反論し、そのような損失をもたらすBartlett and Long (JCSS 1998) の上界を改善する。 鍵となる技術的要素は、数値を包含する経験的な$\ell_\infty$の直接束縛であり、パッキング数による標準の振れを避けることである。 その結果、脂肪散乱スケール$γ$: a $O(\log^2 n)$bound は既にスケール$γ/2$ であり、$O(\log n)$ bound はスケール$2γ$ である。 さらに、$O(\log^2 n)$バウンドが時としてタイトであることを示す。 これらの結果は、Alon et al (JACM 1997) と Rudelson and Vershynin (Ann. of Math. 2006) によって解決された。 応用として、有界積分確率測度に対する鋭い二分法を確立する:そのようなIMMは任意の乗算係数$c<3$で評価できないが、$3$-弱評価は常に成り立ち、Aiyer et al (ICML 2026) からオープンな質問を解く。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions [39.97534972432276]
  本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。 このアルゴリズムの絶対誤差の一般上界を証明した。 本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
  論文  参考訳（メタデータ） (2023-04-21T15:51:35Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks [0.0]
  ニューラルネットワークの表現力に対する基本的な限界について検討する。 まず最初に、$F$ の函数が $Lp(mu)$ ノルムでどれだけよく近似できるかの一般的な下界を証明します。 すると、これを$G$が多項式フィードフォワードニューラルネットワークに対応するケースに初期化する。
  論文  参考訳（メタデータ） (2022-06-09T09:01:05Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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