Generalized learnability of stochastic principles

Motivated by recent applications of proof theory in probability, we introduce a novel computational interpretation of probabilistic ∃∀-formulas, called dependent learnability. This encompasses several important notions of quantitative stochastic convergence, where it represents a generalized version of the property – widely studied in probability and ergodic theory – that a sequence of random variables has bounded fluctuations. We study both deterministic and stochastic variants of this notion and relate these to other computational interpretations of ∃∀-formulas from the literature. In particular, we prove dependent learnability to be primitive recursively equivalent to the influential notion of metastability, which in conjunction with results from applied proof theory highlights that dependently learnable rates can be extracted from large classes of nonconstructive proofs of ∃∀-formulas. Furthermore, we present a primitive recursive algorithm for joining two (and thus finitely many) dependently learnable rates, which in particular proves to be considerably more mathematically intuitive than the corresponding functional for joining rates of metastability. Finally, we discuss our results in the light of game semantics.