Is there a formal relation between weight regularization and compression? In my understanding, compression, strictly speaking, means that we diminish the amount of data required to describe something, such as a model. E.g. compressing an image file means to create a file that is literally smaller in terms of bits but contains (almost) the same information.
In the context of machine learning, it seems to me that compression literally means that we decrease the amount of bits required to describe a model. For example:


*

*L1 weight regularization of a statistical model results in a subset of parameters being $0$, so that we require less information to describe it. (We can just remove those variables for example)


However, other regularization techniques have a similar effect in terms of making the model "simpler". E.g. L2 regularization also makes the model "simpler" and generally less overfitty, but it doesnt tend to set the parameters literally to $0$, only to "small". So we aren't actually literally compressing the model.
Yet there intuitively is a sense in which $L2$ also "compresses" the model: it intuitively causes the distribution of parameters to be tighter around "simple" models. 
Is there a way that this intuition can be formalized, so that we can see even methods like L2 as compression?


*

*it seems like this is more of a "probabilistic" notion of compression, as we are not literally getting a smaller data file for the resulting parameters of the model, but there is nevertheless less information (in the sense of information theory) in the distribution over models (prior to observing the data).

*if we round the parameters to the nearest nth decimal digit (as is necessary in any computer implementation), we may in some cases literally get a smaller set of possible parameters for a given problem distribution
 A: If you assume some gaussian prior on weights, and are willing to accept some small quantization error, then you can do the following:


*

*Quantize your weights/prior to some very fine tolerance

*Encode them with the optimal code corresponding to your prior. This should take $-\log P(\theta)$ bits where $P$ is your prior and $\theta$ are your parameters
Of course negative log density of the standard gaussian is proportional to $||\theta||_2^2$, so the number of bits it takes to express your model is proportional to the L2 regularization term.
Regarding the quantization part: while this may at first seem like an ugly workaround to the impossibility of encoding real numbers in a finite amount of bits, you can take a more bayesian approach and say that you have a posterior distribution over the model weights. 
In that case, a wider posterior corresponds to a lower coding cost and a narrower posterior corresponds to a higher cost. Hinton and Camp show via the "bits back" argument that you can actually quantize as finely as you want in this case without spending any bits at all (technically you still have to spend them, you just get a refund)!
