論文の概要: Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

• arxiv url: http://arxiv.org/abs/2611.00788v1
• Date: Sat, 31 Oct 2026 10:00:44 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:20:52.96625
• Title: Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features
• Title（参考訳）: 未知のi.i.d.特徴を持つ一般VCクラスに対するTight Stochastic Sequential Covers
• Abstract要約: 本研究では,特徴分布が不明な場合に,特徴とラベルを併用したハイブリッドオンライン学習について検討する。 有限VC次元だけでは、VC次元のすべてのバイナリクラス$d$に対して十分であることを示す。 また、二項現象がVCから擬似次元に拡張されないことも示している。
• 参考スコア（独自算出の注目度）: 18.39862174147355
• License:
• Abstract: We study hybrid online learning with stochastic features and adversarial labels when the feature distribution is unknown. Prior work gave stochastic sequential covers of log-size $O(d\log^2 T)$ for a general VC class and logarithmic bounds only under stronger star-type structure. We show that finite VC dimension alone is enough: every binary class of VC dimension $d$ admits a distribution-blind exact cover with log-size $O(d\log T+\log(1/δ))$, matching the worst-case $Ω(d\log(T/d))$ dependence on the horizon. The key ingredient is a new local cube weight that counts Boolean subcubes incident to each realizable trace. Unlike the equal splits used in earlier constructions, we split mass unevenly according to these cube weights; a coordinate-deletion inequality shows that VC dimension controls the total cost of these splits. This yields, to our knowledge, the first tight $O((d+1)\log T)$ expected worst-case log-loss regret for general VC partitions with unknown i.i.d. features, and an exact polynomial-time implementation for planar affine halfspaces. We also show that the binary phenomenon does not extend from VC dimension to pseudo-dimension: a fixed pseudo-dimension-one sigmoid class requires $Ω(\log^2 T)$ bits for uniform sequential approximation at accuracy $1/T$.
• Abstract（参考訳）: 特徴分布が不明な場合,確率的特徴と逆ラベルを併用したハイブリッドオンライン学習について検討した。 以前の研究は、一般的なVCクラスに対して、対数サイズ$O(d\log^2 T)$の確率的逐次被覆を与え、対数境界はより強い星型構造の下でのみ与えられる。 有限VC次元だけで十分であることを示す: すべてのVC次元のバイナリクラス$d$は、ログサイズ$O(d\log T+\log(1/δ))$で、水平線に依存する最悪の$Ω(d\log(T/d))$である。 鍵となる要素は、Boolean subcubesインシデントをそれぞれの実現可能なトレースにカウントする新しい局所立方体ウェイトである。 初期の構成で使われる等分割とは異なり、これらの立方体重みに応じて質量を不均一に分割する; 座標削除の不等式は、VC次元がこれらの分割の総コストを制御することを示している。 このことは、我々の知る限り、最初の厳密な$O((d+1)\log T)$予想最悪ケースのログロス後悔は、未知のi.d.特徴を持つ一般VCパーティションに対するものであり、平面アフィン半空間に対する正確な多項式時間実装である。 固定擬次元 1 のシグモノイド類は、精度1/T$で一様逐次近似を行うために$Ω(\log^2T)$ビットを必要とする。

関連論文リスト

• Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
  本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。 決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
  論文  参考訳（メタデータ） (2026-10-18T05:17:14Z)
• Adversarial Online Classification with a Preview [17.495168716195476]
  最悪のオンライン分類は、リトルストーン次元のようなシーケンシャルな複雑さによって管理されている。 オンラインの順序をランダムにすることなく、古典的な統計次元によって、ランダムなプレビューが最悪ケースのシーケンシャルな複雑さを置き換えることができることを示す。
  論文  参考訳（メタデータ） (2026-08-30T01:38:49Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• A Fine-Grained Understanding of Uniform Convergence for Halfspaces [31.579168044707462]
  最悪のVC境界を超えたハーフスペースの微細な均一収束挙動について検討する。 $dge 2$ の $mathbbRd$ の非同次半空間に対して、標準一階VC境界は本質的に強であることを示す。 対照的に$mathbbR2$の同質半空間は明らかに異なる振る舞いを示す。
  論文  参考訳（メタデータ） (2026-05-07T10:53:49Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
  ヒルシュベルクのアルゴリズムは、格子動的プログラム(DP)上の中点二項による$O(N2)$から$O(N)$へ、最も長い共通部分列問題の空間複雑性を減少させる。 我々は、その基礎となるアイデアが、有向非巡回グラフ(DP DAG)に局所的依存を持つ広範な動的プログラムのクラスに一般化されることを示す。 前方シングルパスモデルでは$()$空間項は避けられないことを示し、ストリーミング設定における推測される$sqrtT$-type障壁について議論する。
  論文  参考訳（メタデータ） (2025-12-10T22:26:22Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• 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)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
  論文  参考訳（メタデータ） (2022-10-11T13:54:41Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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