Compression and Learning in Linear Regression

摘要

We introduce a linear regression regularization method based on the minimum description length principle, which aims at both sparsi-fication and over-fit avoidance. We begin by building compact prefix free encryption codes for both rational-valued parameters and integer-valued residuals, then build smooth approximations to their code lengths, as to provide an objective function whose minimization provides optimal lossless compression under certain assumptions. We compare the method against the LASSO on simulated datasets proposed by Tibshirani [14], examining generalization and accuracy in sparsity structure recovery.