論文の概要: On the VC Dimension of Autoregressive Linear Threshold Functions

• arxiv url: http://arxiv.org/abs/2610.36970v1
• Date: Tue, 27 Oct 2026 10:26:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.565659
• Title: On the VC Dimension of Autoregressive Linear Threshold Functions
• Title（参考訳）: 自己回帰線形閾値関数のVC次元について
• Abstract要約: 我々は、VC次元がすべての$Tge d2$に対して$(d2)$であることを証明する。 次に、決定論的モデルと自己回帰モデルとの指数的分離を示すために、同じ手法を適用する。
• 参考スコア（独自算出の注目度）: 14.292982828097465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear threshold functions (LTFs) are a canonical class of Boolean predictors. In the autoregressive setting, the same LTF reads the most recent $d$ bits, generates the next bit, and returns the bit produced after $T$ steps. While the one-step class has VC dimension $d$, for general $T$ the counting upper bound is $O(d^2)$. We prove that the VC dimension is $Θ(d^2)$ for every $T\ge d^2$, resolving the quadratic gap for deterministic autoregressive LTFs. We then adapt the same technique to show an exponential separation between deterministic and stochastic autoregressive models: replacing the sign of LTFs by logistic sampling can increase the VC dimension of the final majority prediction class from quadratic to exponential in $d$.
• Abstract（参考訳）: 線形しきい値関数 (LTF) はブール予測器の標準クラスである。 自己回帰設定では、同じLTFが最新の$d$ビットを読み出し、次のビットを生成し、$T$ステップ後に生成されたビットを返す。 一段階のクラスはVC次元$d$を持つが、一般の$T$の場合、カウントの上界は$O(d^2)$である。 我々は、VC次元がすべての$T\ge d^2$に対して$(d^2)$であることを証明する。 次に、決定論的・確率的自己回帰モデルの指数関数的分離を示すために同じ手法を適用し、ロジスティックサンプリングによりLTFの符号を置き換えることで、最終多数予想クラスのVC次元を2次から指数的に$d$に増やすことができる。

関連論文リスト

• Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression [1.376408511310322]
  ステップサイズ$$の勾配降下は、多クラスロジスティック回帰損失に対して$varepsilon$Optimity gapを達成できることを示す。 そのために、ステップサイズ$$は、$varepsilon$の関数として十分に大きく選ばなければならない。
  論文  参考訳（メタデータ） (2026-10-19T17:14:12Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Linear RNN Scaling Laws: When Longer Sequences Beat More Sequences [17.927451930317197]
  自己回帰言語モデルの実証的なスケーリング法則は、予測損失をモデルサイズ、データサイズ、最適化計算に関連付ける。 本研究では,安定な潜在線形RNNが軌道を発生し,スケッチされた線形リカレント学習者は,次の予測に基づいて,安全でフルバッチなWSD勾配勾配で学習する,学習可能な教師-学生モデルを用いて検討する。
  論文  参考訳（メタデータ） (2026-08-23T13:37:15Z)
• Data Predictability Shapes Weibull Weight-Scale Growth in Transformer Training [0.0]
  学習条件付き法則を定める前に計算した学習自由統計法則が得られた。 トレーニングの前に$D$が計算されるので、この法則はフォワード予測器である。 クロスコーパス予測 オーバー予測コード、冗長性はより広い$(D,R,A,H)$データ・ツー・ウェイト・フレームワークの第2軸を意味する。
  論文  参考訳（メタデータ） (2026-06-27T12:26:39Z)
• Linear-Readout Floors and Threshold Recovery in Computation in Superposition [0.0]
  重ね合わせにおける計算に対する最近の2つのアプローチは、異なるキャパシティレジームに到達している。 これらの結果は異なるインターフェース不変性を維持するため矛盾しない。 Hnniテンプレート以外のロバストな非線形リセットは開のままである。
  論文  参考訳（メタデータ） (2026-05-02T02:11:31Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSMは$textitnon-linear$リカレントモデルで、現在の線形状態空間層と同じくらい高速に長いシーケンスを処理する。 ヤコビ行列を対角線に強制することにより、全列を並列に解くことができる。 LrcSSMは、Liquid-S4のような他の入力変化系が提供しないことを保証する形式的な勾配安定性を提供する。
  論文  参考訳（メタデータ） (2025-05-27T20:02:59Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)

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

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