論文の概要: Uniform convergence at optimal rate and scale

• arxiv url: http://arxiv.org/abs/2610.24336v1
• Date: Sat, 17 Oct 2026 00:04:51 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 11:52:34.850089
• Title: Uniform convergence at optimal rate and scale
• Title（参考訳）: 最適速度とスケールにおける均一収束
• Abstract要約: Vapnik--Chervonenkis の定理は、次元 VC の有限性による一様収束を特徴づける。 二値クラスに対しては、Vapnik--Chervonenkis定理はVCの有限性による一様収束を特徴づける。
• 参考スコア（独自算出の注目度）: 45.104496365252636
• License:
• Abstract: Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension $d$, the sharp worst-case sample complexity for additive error $\varepsilon$ is of order $d/\varepsilon^2$. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale $γ$. The challenge is to achieve error $γ+\varepsilon$ with order $d/\varepsilon^2$ samples, matching the sample bound for binary classes, where $d$ is now the fat-shattering dimension at scale $γ$. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns $\varepsilon$-nets with margin. A classical $\varepsilon$-net intersects every set of mass at least $\varepsilon$ in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain $\ell_2$ covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.
• Abstract（参考訳）: 一様収束は、経験的平均に対して何個のランダムサンプルが、関数のクラス全体に対する期待を同時に近似するのに十分であるかを問う。 確率の中心的な概念であり、統計的学習の基礎である。 二値クラスに対しては、Vapnik--Chervonenkis定理はVC次元の有限性による一様収束を特徴づける。 次元$d$の場合、加法誤差$\varepsilon$は階数$d/\varepsilon^2$である。 実数値関数の場合、類似の組合せパラメータは脂肪散乱次元であり、近似スケール$γ$に依存する。 問題は、次数$d/\varepsilon^2$サンプルでエラー$γ+\varepsilon$を達成することである。 これまでの結果は、最適なスケールか、最適なサンプルの複雑さを達成できたが、両方ではなかった。 我々の主な結果は、このギャップを埋め、最適なスケールで鋭いサンプルの複雑さを確立します。 途中では、独立した関心を持つかもしれないいくつかのツールを使用します。 最初の問題は、利益率で$\varepsilon$-netsだ。 古典的な$\varepsilon$-netは、所定の族において少なくとも$\varepsilon$のすべての質量集合を交わす。 興味深いことに、この緩和は自然幾何学的設定において周囲次元から独立な境界を許す。 第二に、離散値と実値の両方の設定における被覆境界の改善を導出する: ハウスラーの被覆補題を部分概念クラスに拡張し、この拡張を使用して実値の関数クラスに対して最適なスケールで$\ell_2$被覆を得る。 第三に、逐次近似が互いに近づくように被覆を整列することで、最適スケールで連鎖境界を得る。

関連論文リスト

• Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence [7.277122777390684]
  幅$m$のランダムに初期化されたニューラルネットワークはガウス過程に$m to infty$として収束し、この収束を特徴づける2種類の量的境界を持つ。 有限サンプル境界は、ネットワークを任意の領域上の固定有限標本集合におけるガウス極限と比較し、二次ワッサーシュタイン距離$mathcal W$で、明示定数を持つ$m-1/2$の収束率を達成する。 関数境界は、2つの関数を$mathcal W$またはより遅いレートよりも弱いランダムなメトリクスとして比較することによって、その依存を取り除く。
  論文  参考訳（メタデータ） (2026-10-13T11:10:44Z)
• Constrained Learning with Universally Learnable Concept Classes [2.5998827435861633]
  双対アルゴリズムの解の解の普遍的な PACC 学習性を確立する。 最適性は、凸性によって支配される普遍性と強ラグランジアン双対性の間に捕えられる。
  論文  参考訳（メタデータ） (2026-08-09T02:13:57Z)
• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
  ブールハイパーキューブ上でのサロゲートの学習問題について検討する。 通常の$L$型保証よりも、均一な$L_infty$-error保証が必要です。 本結果は,最適化セーフなサロゲートを学習する際のサンプルの複雑さの厳密な証明を提供する。
  論文  参考訳（メタデータ） (2026-06-15T22:00:03Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。 さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
  論文  参考訳（メタデータ） (2023-11-09T14:29:25Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)

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

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