Source-linked AI summary
On the VC Dimension of Autoregressive Linear Threshold Functions
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
TL;DR
The paper asks how autoregressive steps affect the statistical complexity of LTFs, where the known VC-dimension bounds left a linear-to-quadratic gap. It proves a quadratic deterministic bound is tight and adapts its construction to show exponential VC dimension for a stochastic logistic model.
Problem
The VC dimension of autoregressive LTFs was known to lie between linear and quadratic order, leaving the end-to-end statistical complexity unresolved.
Source: §1 · pp. 1–2Method
The paper encodes labels in weights and constructs autoregressive processes that recover them, using repeated threshold tests deterministically and logistic sampling stochastically.
Source: Theorem 1: deterministic generators · p. 3, Theorem 2: stochastic generators · p. 4Results
For T ≥ d^2, autoregressive LTFs have VC dimension at least d^2/30242, while for some T the stochastic logistic class has VC dimension at least 2^(cd).
Source: §1 · p. 2Takeaways & Limitations
At fixed accuracy and confidence, end-to-end learning requires Θ(d^2) examples, compared with Θ(d) for the analogous CoT-supervision bound.
Source: §1 · p. 2The construction assumes the initial block x is independent of the labels.
Source: Block Construction · p. 15
Abstract
from arXiv · showhide
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 $\Theta(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$.
1 Introduction
The paper studies how repeated use of one fixed LTF changes statistical complexity, closing the deterministic VC-dimension gap and showing exponential VC dimension for a stochastic logistic model. Its constructions encode labels in weights and recover them through autoregressive steps.
1 Introduction
- The open question was whether autoregressive LTFs have VC dimension of order d or d^2, a gap tied to end-to-end sample complexity.The same LTF reads the most recent d bits at every step with fixed weights and threshold, and the output is the bit after T steps.Source: §1 · pp. 1–2
- For T ≥ d^2, autoregressive LTFs have VC dimension at least d^2/30242, matching the O(d^2) counting upper bound in quadratic order.The proof uses rational weights of polynomial bit length, and the result yields Θ(d^2) end-to-end sample complexity at fixed accuracy and confidence.Source: §1 · p. 2
Theorem 2: stochastic generators
- For some T, the stochastic logistic model's final majority prediction class has VC dimension at least 2^(cd), an exponential separation from the deterministic O(d^2) bound.The theorem gives such a T no larger than 2^(2Cd) for every sufficiently large d; the construction has small margin.Source: §1 · p. 2
Theorem 1: deterministic generators
- The deterministic construction stores each row's labels in an integer encoded in weights, then recovers its binary digits through repeated threshold tests.The multi-LTF recursion uses row, test, output, and pointer bits, recovering digits from largest to smallest in O(m) rounds.Source: Theorem 1: deterministic generators · p. 3
- A carefully placed O(m)-bit block lets one fixed LTF perform each update, while label-independent inputs select the desired outputs at a common time T.The construction uses Θ(m) blocks and Θ(m^2)=Θ(d^2) steps; the selected input windows are fixed before labels are chosen.Source: Theorem 1: deterministic generators · p. 3
Theorem 2: stochastic generators
- The stochastic construction stores exponentially many labels in base-4 digits of one real number and uses logistic sampling to read a selected digit.The probability that the sampled-one count is 0 or 1 modulo 4 oscillates around 1/2, allowing its sign to reveal the selected label.Source: Theorem 2: stochastic generators · p. 4
2 Shattering with Several LTFs
A recursive procedure uses row, test, output, and pointer bits to recover arbitrary encoded labels. Its outputs recover every entry of the labeling after m+1 rounds, yielding a quadratic shattering construction using O(m) LTFs per round.
2 Shattering with Several LTFs
- Θ(m²) inputs are shattered with O(m) LTFs per round; by t≥m+1, outputs recover every λ_i,j.The lemma states that each output bit equals its corresponding label for all t≥m+1.Source: §2 · pp. 4–5
- The recursion encodes each row’s labels in θ_i and recovers its binary digits from largest to smallest.It initializes 3m+2 bits for each selected row.Source: §2 · p. 4
- Row bits select i, the test compares θ_i with current output and pointer values, output bits store recovered digits, and pointer bits select the next digit.The update equations can all be implemented as LTF computations.Source: §2 · p. 4
- In the illustrated round, 21−16≥4 sets output digit 3 to 1, then the pointer shifts from position 3 to position 2.The other output bits remain unchanged.Source: Figure 1 · p. 5
3 Implementing the Recursion with One LTF
The section encodes the multi-bit recursion’s state in blocks so one fixed LTF can generate the next block bit by bit. A coefficient construction makes this recurrence reproduce the intended updates for every row and round.
3 Implementing the Recursion with One LTF
- Each state is encoded as a p-bit block, and the same LTF generates the next block from left to right, one bit at a time.The test bit is generated before output bits so they can depend on the new test and previous block.Source: §3 · p. 6, Figure 2 · p. 6
- Blocks reserve a fixed initial 1 and designated positions for row, test, output, and pointer bits; other positions are zero.Each block ends in zero.Source: §3 · pp. 6–7
- Row bits are stored once, while test, output, and pointer bits are duplicated in adjacent positions.The figure’s example shows the test setting output digit 3 before the pointer changes to j=2.Source: §3 · p. 6, Figure 2 · p. 6
- Integer coefficients B>0 and a_1,...,a_p+1 let the recurrence generate E_t+1 from (0,E_t) for every row and round.For d≥p+1, the recurrence is an instance of the autoregressive LTF with weights a_ℓ/B and zero weights beyond p+1.Source: §3 · p. 7
- The coefficient construction makes scores nonnegative at designated update positions and negative at all remaining positions.The claims establish the encoded next block at the designated positions and negative scores elsewhere.Source: §3 · pp. 9–10
4 Choosing the Inputs
The construction selects fixed, label-independent prompts whose final bits retrieve designated outputs from recursively generated blocks. Under the stated dimension and horizon conditions, it shatters m^2 prompts.
4 Choosing the Inputs
- Each prompt is a d-bit window from a label-independent initial string, shifted so time T lands on its designated output position.The shifts align the target output position modulo the block length, while the selected inputs remain independent of the labels.Source: §4 · pp. 10, 12
- For d ≥ p + 1 and T ≥ (m + 3)p, Lemma 3 states that the m² prompts in (35) are distinct and shattered by Fd,T.Source: §4 · p. 11
- Distinct index pairs yield distinct prompts, since identical prompts assigned different labels would contradict the construction's output guarantee.The proof establishes distinctness by assigning opposite labels to a hypothetical duplicate pair.Source: §4 · p. 12
- The construction's weights have polynomial bit length in d.For m ≥ 2, the coefficient magnitudes are bounded using B, with log2 B = m + 5 + log2(m + 2).Source: §4 · p. 12
5 Stochastic Digit Extraction
The stochastic construction encodes labels in a real number and uses repeated logistic samples with modulo-4 state tracking to recover them. It implements this process with one logistic generator and constructs fixed prompts whose output probabilities realize the labels at a shared horizon.
5.1 Reusing the Deterministic Simulation
- The recursion stores the address, sampled test bit, and modulo-4 counter in a state vector, whose updates are computed using linear threshold functions.A sampled 1 advances the counter through a four-state cycle; a sampled 0 leaves it unchanged.Source: §5.1 · p. 14
5 Stochastic Digit Extraction
- The modulo-4 counter makes its second coordinate 1 exactly when the number of sampled ones is 0 or 1 modulo 4, yielding a probability gap according to the selected label.Lemma 4 states that the final output probability lies on the label's side of 1/2 by at least δN.Source: §5 · p. 13, §5.1 · p. 14
Block Construction
- Lemma 5 provides weights and bias for one logistic process to generate the encoded blocks from every input with its stated probability guarantee.The construction defines block positions and coefficients, then analyzes the logistic scores at each position.Source: Block Construction · pp. 15, 17
5.2 Choosing the Stochastic Inputs
- For m = Θ(d), the construction shatters 2^m prompts, and zero-padding extends it to dimension d without changing output probabilities.The proof chooses m as a function of d and states that the horizon depends only on d.Source: §5.2 · p. 17