  Unsupervised speech recognition (ASR-U) is the problem of learning automatic
speech recognition (ASR) systems from unpaired speech-only and text-only
corpora. While various algorithms exist to solve this problem, a theoretical
framework is missing from studying their properties and addressing such issues
as sensitivity to hyperparameters and training instability. In this paper, we
proposed a general theoretical framework to study the properties of ASR-U
systems based on random matrix theory and the theory of neural tangent kernels.
Such a framework allows us to prove various learnability conditions and sample
complexity bounds of ASR-U. Extensive ASR-U experiments on synthetic languages
with three classes of transition graphs provide strong empirical evidence for
our theory (code available at cactuswiththoughts/UnsupASRTheory.git).
