Memory and precision in noiseless Gaussian regression
For every fixed finite , there are constants and such that for , integer , and , any learner in Definition 1.1 that draws independently of the rows and data-independent randomness and achieves must have prescribed horizon .
The proof on page 19 rigorously combines Proposition 5.3 for fine accuracy and the reflection bound (32) for constant accuracy, with all constants and dimension thresholds properly tracked.
“For every fixed finite A > 0, there are constants cA > 0 and dA such that the following holds. Let d ≥ dA, let 0 ≤ M ≤ Ad2 be an integer, and let 0 < ϵ ≤ 1/10. For any learner in Definition 1.1, draw S ∼ σd independently of the rows and the learner’s data-independent randomness. If P{arccos⟨sb, S⟩ ≤ ϵ} ≥ 2/3, then its prescribed horizon satisfies T ≥ cAd log(1/ϵ).” · Show in paper