CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision

Awni Altabaa; John Lafferty; Omar Montasser

REVIEW 2 major objections 5 minor 9 references

CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that chain-of-thought supervision is never worse than input-output learning—and can be far better—with the gain set by a new quantity, the CoT information.

desk verdict Genuinely new sample-complexity rates for CoT supervision, correct under exact realizability; the practical robustness story is thinner than the abstract suggests, but the paper deserves a serious referee. read the letter →

arxiv 2505.15927 v1 pith:SXJKX4O6 submitted 2025-05-21 stat.ML cs.LG

Awni Altabaa , Omar Montasser , John Lafferty This is my paper · ORCID

classification stat.MLcs.LG MSC 68Q3268T05

keywords chain-of-thoughtsupervisionCoTinformationsamplecomplexitystatisticallearningtheoryPAChypothesistestinglowerboundsend-to-endriskVCdimension

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper develops a statistical theory for learning from chain-of-thought supervision—training examples that include intermediate reasoning steps alongside the final answer. It introduces a quantity, the CoT information, that measures how much extra discriminative power the reasoning trace provides beyond the input-output pair. The central result is that the sample complexity to reach a target end-to-end error $\varepsilon$ scales like $d$ divided by the CoT information, instead of the standard $d/\varepsilon$, and the CoT information is always at least $\varepsilon$. So CoT supervision is never information-theoretically worse than end-to-end supervision, and can be much better when traces reveal the underlying computation. Matching lower bounds argue that the CoT information is the right measure of this advantage.

What carries the argument

The CoT information $\mathcal{I}_{\mathcal{D},h_\star}^{\mathrm{CoT}}(\varepsilon;\mathcal{H})$ is the minimum, over hypotheses $h$ that disagree with the ground truth $h_\star$ on at least an $\varepsilon$ fraction of inputs, of the negative log probability that $h$ and $h_\star$ produce the same output and the same chain-of-thought on a random input. It quantifies how easily reasoning traces separate hypotheses that differ in end-to-end behavior. The main upper bounds flow from a lemma that converts CoT error into end-to-end error: any proper CoT learner that reaches CoT error $\gamma$ also reaches end-to-end error $\varepsilon$, with $\gamma$ tied to $\mathcal{I}$ by the identity $\mathcal{I} = -\log(1-\gamma)$. Applying this lemma to CoT consistency and CoT-ERM turns standard VC-dimension bounds into sample-complexity bounds with $1/\mathcal{I}$ in place of $1/\varepsilon$. The lower bounds reduce learning to binary and multi-way hypothesis testing (LeCam and Fano methods), relating total-variation and KL distances to the CoT information.

What would settle it

For a concrete CoT hypothesis class and input distribution, compute $\mathcal{I}_{\mathcal{D},h_\star}^{\mathrm{CoT}}(\varepsilon;\mathcal{H})$; if any learning algorithm achieves end-to-end error $\varepsilon$ with fewer than about $\log|\mathcal{H}|/\mathcal{I}_{\mathcal{D},h_\star}^{\mathrm{CoT}}(\varepsilon;\mathcal{H})$ samples, the claim that this measure governs the $\varepsilon$-dependence would be falsified.

Watch

Extended reading notes

Core claim

The paper's central claim is that the statistical cost of learning with chain-of-thought supervision is governed by a new measure, the CoT information $\mathcal{I}_{\mathcal{D},h_\star}^{\mathrm{CoT}}(\varepsilon;\mathcal{H})$. For a finite CoT hypothesis class, the CoT consistency rule reaches end-to-end error $\varepsilon$ with $m = (\log|\mathcal{H}| + \log(1/\delta)) / \mathcal{I}_{\mathcal{D},h_\star}^{\mathrm{CoT}}(\varepsilon;\mathcal{H})$, and since the measure is always at least $\varepsilon$, this rate is never worse—and can be much better—than the standard $\log|\mathcal{H}|/\varepsilon$. The $\varepsilon$-dependence of the rate carries over to infinite classes via the VC dimension of the CoT loss class, and information-theoretic lower bounds show that the same $\mathcal{I}$ controls the number of samples any algorithm must see. The paper therefore asserts that CoT information, not just the complexity of the CoT loss class, is the fundamental measure of the value of CoT supervision.

Load-bearing premise

The main rates assume the chain-of-thought traces in the data are exact deterministic outputs of the ground-truth hypothesis in the class, with the paper's own agnostic example showing the guarantee can vanish when that fails.

Editorial extensions

If this is right

In the realizable setting, CoT supervision is information-theoretically never worse than end-to-end supervision because the CoT information is always at least $\varepsilon$.
The speed-up can be dramatic: in the paper's deterministic-finite-automaton simulations the CoT information predicts roughly a 600-fold reduction in samples for zero error, and the experiments match.
The bound extends to infinite hypothesis classes through the VC dimension of the CoT loss class, so the improvement in $\varepsilon$-dependence is not an artifact of finite hypothesis spaces.
In the agnostic setting the guarantee depends on an agnostic CoT information measuring how well the data distribution aligns with the class; misaligned CoT annotations can actually destroy the guarantee.
Noise in the observed traces enters the lower bound through a channel capacity factor, giving a quantitative price for imperfect CoT annotations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A practical diagnostic that follows implicitly: estimate the CoT information from a trace dataset and use it to decide whether collecting more CoT annotations is worth more than collecting plain input-output pairs.
The coding-theoretic viewpoint of CoT traces as redundant codewords suggests a testable design principle: maximize the diversity of traces among hypotheses that give different answers, since that is exactly what raises the CoT information.
The transfer-learning variant of the measure gives a quantitative, testable condition for length generalization in automaton-like reasoning: traces on short inputs should already distinguish hypotheses that behave differently on long inputs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper delivers something real: a CoT information measure I that controls the epsilon-dependence of sample complexity in the realizable setting, with upper bounds of order log|H|/I and VC(LCoT)/I that beat the previous 1/epsilon rates whenever I >> epsilon. The risk-linking lemma (Lemma 2) is the key step and it is clean. The agnostic extension (Result 3) is also honest, with its own excess-risk-based information measure that can be zero when CoT is misaligned. This is a genuine advance over Joshi et al., not a repackaging.

The lower bounds are a mixed bag. The Le Cam bound (Result 4) is, as the reader notes, partly a restatement of the definition of I: the probability that a bad hypothesis is indistinguishable decays as exp(-mI) by construction. That is not a fatal flaw, since the matching upper bounds are the main contribution and the Fano bound (Result 5) is a real theorem. But calling Result 4 a lower bound that 'validates' I is overselling it slightly. The Fano bound with the noisy channel is a nice addition, and the channel-capacity calculation in the appendix is careful.

The soft spots are concentrated in what the abstract promises versus what is proven. The headline claim that CoT supervision is 'never worse' and that the gains are robust only holds under exact realizability: CoT labels are assumed to be deterministic outputs of the ground-truth h* in H. The paper is explicit about this, and Section 4.2 gives a sharp example where CoT-ERM has zero guarantee while E2E-ERM works. That is a real limitation for human-annotated traces, which are noisy and often out-of-class. Result 5 models noise but only as a lower bound; there is no matching upper bound showing CoT still helps under noise. The simulations are illustrative but thin: a single target automaton, no error bars, no code. They match the theory, which is good, but they would not convince a skeptic about practical impact.

The citation pattern is appropriate, and the related-work discussion correctly identifies the difference from Joshi et al. The writing is clear, the proofs are standard and appear correct, and the paper does not overclaim the practical implications in the body (the abstract pushes a bit harder). Overall, the central theoretical contribution holds up. The realizability caveat is real but standard for first theory, and the paper acknowledges it.

This is a paper for statistical learning theorists, and maybe for LLM practitioners who want a formal sense of when CoT traces help. It deserves a serious referee and, with revisions that strengthen the noisy-setting discussion and simulations, it would be a solid accept. I would bring it to a reading group and would cite it in my own work.

Referee Report

2 major / 5 minor

Summary. The paper develops a statistical theory for learning from chain-of-thought (CoT) supervision. It models a CoT hypothesis as a function h: X → Y×Z, defines end-to-end and CoT risks, and introduces the CoT information measure I^CoT_{D,h*}(ε;H) = inf_{h: e2e-error>ε} −log P_D[h_CoT(x)=h*_CoT(x), h_e2e(x)=h*_e2e(x)]. The main results are: Result 1 gives a sample complexity bound (log|H|+log(1/δ))/I^CoT for finite classes under CoT-consistency; Result 2 extends this to infinite classes with VC(LCoT(H)); Result 3 treats the agnostic setting with CoT-ERM at rate VC(LCoT(H))/tilde-I^2; Results 4 and 5 give Le Cam and Fano lower bounds in terms of I; and Section 6 presents simulations on deterministic finite automata and iterated linear thresholds that match the predicted gains. The paper carefully distinguishes realizable and agnostic settings and includes an example showing that CoT-ERM can fail when the CoT component is not realizable.

Significance. If the results hold, the CoT information measure is a valuable new quantity for CoT learning: it is always at least ε, it is monotone in ε and anti-monotone in H, and it appears in both upper bounds and information-theoretic lower bounds. The proofs are based on standard PAC, Le Cam, and Fano arguments and largely appear correct. The paper improves on prior work (notably Joshi et al.) by directly linking CoT risk to end-to-end risk instead of bounding CoT risk and then using the crude inequality R^e2e ≤ R^CoT. The simulations are a strength: they compute I for nontrivial classes and empirically confirm the predicted order-of-magnitude gains. The main caveat, explicitly acknowledged in Sections 4.2 and 7.3, is that the improved rates are proved only for exactly realizable CoT labels; with noisy or out-of-class CoT, CoT-ERM can have zero guarantee and the noisy-channel lower bound (Result 5) has no matching upper bound.

major comments (2)

[Abstract; Section 4.2; Result 5] The central improvement rates are proved only under exact realizability of the CoT labels (Definition 1). Section 4.2 shows that when the CoT component is not realizable, CoT-ERM can have inf_{h} R^CoT_D(h)=1 while inf_{h} R^e2e_D(h)=0, so the 'never worse' message does not extend to noisy or out-of-class CoT. The paper already acknowledges this in Section 4.2 and Section 7.3, and Result 5 provides only a lower bound under a noisy channel with no matching upper bound. Please make the realizable-setting scope explicit in the abstract and introduction, and state the missing noisy-channel upper bound as an open problem in Section 7.3.
[Appendix D.2 (proof of Result 5)] The proof states I(h*;S) = E_{h~π}[DKL(P_h^⊗m || \bar P^⊗m)] with \bar P = E_{h~π}P_h. This equality is not correct: the marginal of S under the prior is the mixture E_{h~π}P_h^⊗m, not the product \bar P^⊗m. The desired bound still follows by applying convexity of KL in the second argument to write I(h*;S) ≤ E_{h1,h2~π}[DKL(P_h1^⊗m||P_h2^⊗m)] = m E_{h1,h2~π}[DKL(P_h1||P_h2)], so the theorem remains correct, but the displayed line must be corrected. In addition, the 'in particular' implication that the stated m bound yields failure probability at least 1/2 holds only when log M(ε;H,d^e2e_D) ≥ 2 log 2; please state this condition or retain the exact Fano bound.

minor comments (5)

[Abstract; Section 3.2] The abstract compares 'd/I' with 'd/ε' informally; I is a function of h*, D, ε, and H, and Result 2 has an additive +1 term and logarithmic factors. Please phrase the comparison as 'up to logarithmic factors' and note that it applies in the realizable setting.
[Section 6, Figures 3-4] The simulations use a single target hypothesis (e.g., the DFA in Figure 5) and report no error bars or standard errors; reporting averages over multiple targets and providing code would strengthen the empirical claims.
[Appendix D.1 (proof of Result 4)] The proof introduces h0 without defining it, and the displayed triangle inequality contains repeated and ambiguous terms such as d(A(S),h1) on both sides; please clean up the notation for clarity.
[Result 5] When any pair of hypotheses has infinite CoT information, sup_π E[I] = ∞ and the displayed implication is vacuous; please add a remark explaining this boundary case and noting that in the fully informative CoT regime (Example 2) one sample can suffice, so a vacuous lower bound is expected.
[Section 7.3] The paper correctly lists missing agnostic lower bounds as an open problem; the missing upper bound under annotation noise should also be listed there, since Result 5 is only a lower bound.

Circularity Check

1 steps flagged · score 4.0 of 10

Result 4's lower bound restates the definition of CoT information; the upper bound and Fano bound retain independent content.

self definitional [Section 5, Result 4 and proof in Appendix D.1]
"Fix h⋆∈H and ε∈[0,1]. Let ¯h∈ arg min_{h∈∆^{e2e}_D(ε;H,h⋆)} I^{CoT}_D(h⋆,h). Then, by definition, we have that ¯h has end-to-end error at least ε and I^{CoT}_{D,h⋆}(ε;H)=I^{CoT}_D(h⋆,¯h). Thus, the probability that h⋆ and ¯h agree on a random input x with respect to both the CoT and E2E behavior can be expressed as ... = exp(−I^{CoT}_{D,h⋆}(ε;H))."

Definition 3 defines I^{CoT}_{D,h⋆}(ε;H) as the infimum over end-to-end-bad hypotheses of -log P[h and h⋆ agree on both CoT and E2E output]. Therefore the probability that any fixed bad hypothesis agrees with h⋆ on all m i.i.d. samples is exp(-m I) by construction. The first statement of Result 4 is exactly this definitional identity rewritten as a threshold on m, and the later Le Cam expected-error bound substitutes the same identity through TV(P_{h1},P_{h2}) = 1 - exp(-m I). Calling this a lower bound that 'validates' I as the fundamental rate is thus a restatement of the definition rather than an independent confirmation. The Fano-based Result 5 and the realizable upper-bound proof do contain genuine additional arguments, so the circularity is partial.

full rationale

The paper's realizable upper bound (Result 1) is a genuine union-bound argument; it uses Definition 3 as the exponent for the probability that a bad hypothesis is CoT-consistent, but that is a legitimate analytical step. The Fano lower bound (Result 5) is also independent, though it can become vacuous when pairwise CoT information is infinite. The main circularity is in Section 5: Result 4's lower bound is essentially the definition of CoT information exponentiated. Since I is defined as -log P[agreement on CoT and E2E], the statement that m < log(1/δ)/I leaves an indistinguishable bad hypothesis with probability at least δ is a direct restatement of that definition, not a new lower-bound phenomenon. There is no self-citation load-bearing and no fitted-parameter-as-prediction issue; the simulations provide an external check. Overall, the central quantity is partly self-justifying through the matching lower bound, but the upper-bound theorem and the Fano bound give the framework independent content, so the circularity is moderate rather than total.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical entities or fitted free parameters; the CoT information is a mathematical quantity defined from the data-generating model. The assumptions are standard PAC modeling choices plus a deterministic, realizable CoT signal in the main upper bounds.

assumptions (6)

standard math PAC learning and VC dimension uniform convergence bounds are valid for the CoT loss class L_CoT(H).
Used in the proofs of Results 2 and 3 (Sections 4.1 and C.1-C.2) for the consistency and ERM sample complexity of the CoT loss.
standard math Le Cam's method and Fano's inequality are applicable to the CoT observation model.
Used in Appendix D for lower bounds; requires the observation distributions P_h to be defined and finite packing numbers.
domain assumption Each hypothesis h in H is a deterministic map from X to (Y,Z), and the observed CoT is exactly h*_CoT(x) in the realizable upper bounds.
Section 2 defines H subset (Y x Z)^X and Definitions 1-2 assume samples are h*(x_i); this excludes stochastic or noisy CoT in the main upper bounds.
domain assumption The data distribution over X is fixed and samples are i.i.d.; loss is 0/1.
Standard PAC framework in Definitions 1-2; the risk mismatch between CoT training and end-to-end test is the paper's object of study.
domain assumption For the agnostic result, the CoT loss class L_CoT(H) has finite VC dimension and the CoT-ERM rule is proper (returns a hypothesis in H).
Result 3 and Lemma 3 rely on standard ERM guarantees for L_CoT(H); improper rules are explicitly set aside in the footnote of Section 2.
domain assumption The noisy channel Q in Result 5 is memoryless and has bounded capacity factor C_Q.
Introduced to model annotation noise in lower bounds; not required for upper bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision." pith.science (2026). https://pith.science/paper/SXJKX4O6

@misc{pith2026250515927,
  author       = {Pith},
  title        = {Pith review of: CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SXJKX4O6}},
  note         = {Machine review of arXiv:2505.15927}
}

abstract

Learning complex functions that involve multi-step reasoning poses a significant challenge for standard supervised learning from input-output examples. Chain-of-thought (CoT) supervision, which provides intermediate reasoning steps together with the final output, has emerged as a powerful empirical technique, underpinning much of the recent progress in the reasoning capabilities of large language models. This paper develops a statistical theory of learning under CoT supervision. A key characteristic of the CoT setting, in contrast to standard supervision, is the mismatch between the training objective (CoT risk) and the test objective (end-to-end risk). A central part of our analysis, distinguished from prior work, is explicitly linking those two types of risk to achieve sharper sample complexity bounds. This is achieved via the *CoT information measure* $\mathcal{I}_{\mathcal{D}, h_\star}^{\mathrm{CoT}}(\epsilon; \calH)$, which quantifies the additional discriminative power gained from observing the reasoning process. The main theoretical results demonstrate how CoT supervision can yield significantly faster learning rates compared to standard E2E supervision. Specifically, it is shown that the sample complexity required to achieve a target E2E error $\epsilon$ scales as $d/\mathcal{I}_{\mathcal{D}, h_\star}^{\mathrm{CoT}}(\epsilon; \calH)$, where $d$ is a measure of hypothesis class complexity, which can be much faster than standard $d/\epsilon$ rates. Information-theoretic lower bounds in terms of the CoT information are also obtained. Together, these results suggest that CoT information is a fundamental measure of statistical complexity for learning under chain-of-thought supervision.

Figures

Figures reproduced from arXiv: 2505.15927 by the authors.

**Figure 1.** An illustration of standard end-to-end supervision and CoT supervision. Our theoretical framework is aimed at understanding tradeoffs between end-to-end supervision and CoT supervision, and in particular, how the potentially richer information in the CoT signal can result in faster learning rates. 1. Introduction “Chain-of-thought” (CoT) reasoning has been a driving force behind recent advances in the capabilities … view at source ↗

**Figure 2.** Illustration of the statistical advantage of CoT supervision in terms of the geometry of the [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Numerical experiments for deterministic finite automata CoT hypothesis class. [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Numerical experiments for iterated linear thresholds CoT hypothesis class. [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]

**Figure 5.** Figure 5: The state transition graph of the DFA corresponding to the target hypothesis h⋆. CoT learning is often used as a means of providing supervision on the intermediate computation of a reference algorithm to be learned. In the following experiments, we use deterministic fi…

**Figure 6.** Figure 6: Capacity factor of Q as a function of error level for |Y × Z| = 1, 000 rule when applied to me2e end-to-end examples and mCoT CoT examples. Result 6 (Learning with Mixed Datasets). Let H ⊂ (Z × Y) X be a finite CoT hypothesis class, and let D be a distribution over X .…

**Figure 7.** Figure 7: Simulations exploring I CoT Dtr→Dtest (ε; H, h⋆) distribution over inputs of length n ≥ ℓ. In fact, the same line of reasoning shows that min ε>0 I CoT Dtr→Dtest (ε; H, h⋆) ≥ |Σ| −(ℓ+1) for any distribution Dtest (i.e., of arbitrary length). The chain-of-thought annota…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references · 7 canonical work pages

[1]

Some Local Measures of Complexity of Convex Hulls and Generalization Bounds

Angluin, Dana (Oct. 1981). “A Note on the Number of Queries Needed to Identify Regular Languages”. In: Information and Control (cited on page 27). – (Nov. 1, 1987). “Learning Regular Sets from Queries and Counterexamples”. In:Information and Computation (cited on page 27). Angluin, Dana, James Aspnes, Sarah Eisenstat, and Aryeh Kontorovich (2013). “On the...

work page Pith review arXiv 2013
[2]

={(s,x )∈S× Σ :δ1(s,x )̸=δ2(s,x )} be the set of state-symbol pairs on which 26 h1 andh2’s transition functions differ. Then, we have 1− P x∼D [ hCoT ⋆ (x) =hCoT(x),h e2e ⋆ (x) =he2e(x) ] ≥ P x∼D [ hCoT ⋆ (x)̸=hCoT(x) ] = P x∼D [∃t∈ [n] :zt̸=z∗ t ] = P x∼D [h⋆ visits any (s,a )∈ ∆(h,h⋆)] Suppose that h⋆’s transition graph is ℓ-connected in the sense that ...

work page 1981
[4]

Letx1,...,x m∼D be an i.i.d sample fromD

LetH⊂ (Y×Z )X be a CoT hypothesis class and let D be a distribution onX . Letx1,...,x m∼D be an i.i.d sample fromD. For anyh⋆∈H andε> 0, we have that m< log(1/δ) ICoT D,h⋆(ε;H) implies that with probability at leastδ, there existsh∈H with end-to-end error at leastε which is indistinguishable fromh⋆ on this sample. Proof. Fixh⋆∈H andε∈ [0, 1]. Let ¯h∈ arg ...

work page 1973
[8]

2 · ( 1− TV ( P⊗m h1 ,P⊗m h2 )) , where the last inequality follows from the minimum average probability of error in binary hypothesis testing (or, equivalently, the supremum representation of the total variation distance). Now, using 35 the previous calculation of the total variation distance in terms of the CoT information, we have sup h⋆∈H E S∼P⊗m h⋆ [...

work page 2006
[9]

Fore = 1/100 and|Y×Z| = 1, 000, the capacity factor is approximatelyCQ≈ 11.39

This corresponds to the fact that it is harder to distinguish between hypotheses when the observations are more noisy. Fore = 1/100 and|Y×Z| = 1, 000, the capacity factor is approximatelyCQ≈ 11.39. Appendix E: Other Topics E.1. Learning with Mixed Supervision In many situations, CoT training examples may be difficult or expensive to obtain, for example, b...

work page 1965
[1975]

A formal theory of inductive inference. Part I

Springer (cited on page 27). Solomonoff, Ray J (1964). “A formal theory of inductive inference. Part I”. In: Information and control (cited on page 43). Vapnik, V . (1982). “Estimation of Dependencies Based on Empirical Data”. Springer-Verlag, New York (cited on pages 6, 7). Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N...

work page 1964
[1987]

Piecewise testable events

28th Annual Symposium on Foundations of Computer Science. Los Angeles, CA, USA: IEEE (cited on page 27). Simon, Imre (1975). “Piecewise testable events”. In: Automata Theory and Formal Languages: 2nd GI Conference Kaiserslautern, May 20–23,

work page 1975
[2210]

Training Verifiers to Solve Math Word Problems

11416 [cs.LG] (cited on pages 3, 19). Cobbe, Karl et al. (2021). “Training Verifiers to Solve Math Word Problems”. arXiv:2110.14168 [cs.LG] (cited on pages 3, 19). Cover, T. M. and Joy A. Thomas (2006). “Elements of Information Theory”. 2nd ed. Hoboken, N.J: Wiley-Interscience. 748 pp. (cited on page 36). Feng, Guhao, Bohang Zhang, Yuntian Gu, Haotian Ye,...

arXiv 2021

Show all 9 references

[2305]

Efficient Learning of Typical Finite Automata from Random Walks

15408 [cs.LG] (cited on page 19). Freund, Yoav, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie (1993). “Efficient Learning of Typical Finite Automata from Random Walks”. In:Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Comp...

1993 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Some Local Measures of Complexity of Convex Hulls and Generalization Bounds

Angluin, Dana (Oct. 1981). “A Note on the Number of Queries Needed to Identify Regular Languages”. In: Information and Control (cited on page 27). – (Nov. 1, 1987). “Learning Regular Sets from Queries and Counterexamples”. In:Information and Computation (cited on page 27). Angluin, Dana, James Aspnes, Sarah Eisenstat, and Aryeh Kontorovich (2013). “On the...

work page Pith review arXiv 2013

[2] [2]

={(s,x )∈S× Σ :δ1(s,x )̸=δ2(s,x )} be the set of state-symbol pairs on which 26 h1 andh2’s transition functions differ. Then, we have 1− P x∼D [ hCoT ⋆ (x) =hCoT(x),h e2e ⋆ (x) =he2e(x) ] ≥ P x∼D [ hCoT ⋆ (x)̸=hCoT(x) ] = P x∼D [∃t∈ [n] :zt̸=z∗ t ] = P x∼D [h⋆ visits any (s,a )∈ ∆(h,h⋆)] Suppose that h⋆’s transition graph is ℓ-connected in the sense that ...

work page 1981

[3] [4]

Letx1,...,x m∼D be an i.i.d sample fromD

LetH⊂ (Y×Z )X be a CoT hypothesis class and let D be a distribution onX . Letx1,...,x m∼D be an i.i.d sample fromD. For anyh⋆∈H andε> 0, we have that m< log(1/δ) ICoT D,h⋆(ε;H) implies that with probability at leastδ, there existsh∈H with end-to-end error at leastε which is indistinguishable fromh⋆ on this sample. Proof. Fixh⋆∈H andε∈ [0, 1]. Let ¯h∈ arg ...

work page 1973

[4] [8]

2 · ( 1− TV ( P⊗m h1 ,P⊗m h2 )) , where the last inequality follows from the minimum average probability of error in binary hypothesis testing (or, equivalently, the supremum representation of the total variation distance). Now, using 35 the previous calculation of the total variation distance in terms of the CoT information, we have sup h⋆∈H E S∼P⊗m h⋆ [...

work page 2006

[5] [9]

Fore = 1/100 and|Y×Z| = 1, 000, the capacity factor is approximatelyCQ≈ 11.39

This corresponds to the fact that it is harder to distinguish between hypotheses when the observations are more noisy. Fore = 1/100 and|Y×Z| = 1, 000, the capacity factor is approximatelyCQ≈ 11.39. Appendix E: Other Topics E.1. Learning with Mixed Supervision In many situations, CoT training examples may be difficult or expensive to obtain, for example, b...

work page 1965

[6] [1975]

A formal theory of inductive inference. Part I

Springer (cited on page 27). Solomonoff, Ray J (1964). “A formal theory of inductive inference. Part I”. In: Information and control (cited on page 43). Vapnik, V . (1982). “Estimation of Dependencies Based on Empirical Data”. Springer-Verlag, New York (cited on pages 6, 7). Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N...

work page 1964

[7] [1987]

Piecewise testable events

28th Annual Symposium on Foundations of Computer Science. Los Angeles, CA, USA: IEEE (cited on page 27). Simon, Imre (1975). “Piecewise testable events”. In: Automata Theory and Formal Languages: 2nd GI Conference Kaiserslautern, May 20–23,

work page 1975

[8] [2210]

Training Verifiers to Solve Math Word Problems

11416 [cs.LG] (cited on pages 3, 19). Cobbe, Karl et al. (2021). “Training Verifiers to Solve Math Word Problems”. arXiv:2110.14168 [cs.LG] (cited on pages 3, 19). Cover, T. M. and Joy A. Thomas (2006). “Elements of Information Theory”. 2nd ed. Hoboken, N.J: Wiley-Interscience. 748 pp. (cited on page 36). Feng, Guhao, Bohang Zhang, Yuntian Gu, Haotian Ye,...

arXiv 2021