← 研踪 PaperTrailarXiv:2610.36970 · v1
On the VC Dimension of Autoregressive Linear Threshold Functions
首次提交 2026-10-27 18:26
版本更新 2026-10-27 18:26
雷达观测 2026-10-29 00:35
摘要
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$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-27 18:26 · 最新观测版本
On the VC Dimension of Autoregressive Linear Threshold Functions
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$.
查看此版本解读 →查看此版本原文 ↗