  Various forms of regularization in learning tasks strive for different
notions of simplicity. This paper presents a spectral regularization technique,
which attaches a unique inductive bias to sequence modeling based on an
intuitive concept of simplicity defined in the Chomsky hierarchy. From
fundamental connections between Hankel matrices and regular grammars, we
propose to use the trace norm of the Hankel matrix, the tightest convex
relaxation of its rank, as the spectral regularizer. To cope with the fact that
the Hankel matrix is bi-infinite, we propose an unbiased stochastic estimator
for its trace norm. Ultimately, we demonstrate experimental results on Tomita
grammars, which exhibit the potential benefits of spectral regularization and
validate the proposed stochastic estimator.
