Are there connections between the theory of computation and machine learning?
Yes, check out Computational learning theory (Algorithmic learning theory) and conferences COLT and ALT although the connection with machine learning is arguably limited.