# Autoencoders and information compression

Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions.

If I understood correctly the concept, an autoencoder is a specific case of neural networks with as many input nodes than output nodes (say $d$), whose goal is to approximate the identity function $$\operatorname{id}\colon \mathbb{R}^d \to \mathbb{R}^d\,.$$ The trick is that this net can be broken into two parts, "encoder" and "decoder" of the form $\Phi\colon \mathbb{R}^d \to \mathbb{R}^k$ and $\Psi\colon \mathbb{R}^k \to \mathbb{R}^d$, such that $k\ll d$. Therefore, there has to be something non-trivial going on for $\Psi\circ \Phi$ to approximate the identity, given the restricted width of the middle layers.

This struck me as begging the question:

Can one (and has one already?) formalize and analyze this rigorously in terms of information theory, and specifically compression?

I realize the problem itself would need a more thorough and precise formulation to be tackled, as in the above we deal with full real numbers (so "hiding" information in a single real number, say the weight of a node in the middle layer, would give a very easy way out). But with this dealt with appropriately, hopefully there are non-trivial statements to be made with regard to what compression can be achieved, with respect to some distribution over the inputs?

Has this type of question been looked at from a theoretical viewpoint, in our community or another?

• What would it mean, for you, to formalize and analyze this rigorously? What would you want to know about it? What would you want such a theory to give you? I suspect information theory might not be very helpful here, because intuitively we expect that (for tasks where we'd use an autoencoder) the input probably comes approximately from a low-dimensional space so information-theoretically such a pair of functions $\Phi,\Psi$ probably exists. Not sure what that teaches us, though. – D.W. Oct 11 '17 at 5:37
• The interesting cases are when the input is recovered only approximately. For example PCA is a simple form of autoencoder. I am not aware of any lower bounds. Upper bound for random autoencoders have been studied by Arora er al: arxiv.org/abs/1310.6343. – user43170 Oct 11 '17 at 22:13
• @D.W. Well, that itself would be interesting per se (wouldn't it?). Under some restrictions of the magnitudes of the weights (can be encoded with say $m$ bits), under what assumptions on the underlying distribution (supported on a $k$-dimensional manifold?) can we prove convergence of an autoencoder net in time and sample complexity $\mathrm{poly}(m,k,\varepsilon)$ to give an $\varepsilon$-approximation of the identity function (in which metric/sense)? – Clement C. Oct 12 '17 at 19:19
• I don't see how information theory will let you get at questions like convergence of gradient descent at training an autoencoder net. At best it seems like it might help you demonstrate that such functions exist, but not convergence time for training. Anyway, in general, for deep neural networks, we can prove approximately nothing about training (convergence time, success at converging to something near a global optimum, etc.); I don't see any reason why that would be any easier for autoencoders than other neural nets. – D.W. Oct 12 '17 at 21:10
• Actually, Kolmogorov Complexity is non-computable, but the autoencoders somehow is like an appoximate compression, but I am not sure what we will get having formulated and analyzed the net rigorously. – XL _at_China Oct 13 '17 at 9:25

In the other situation when in your notation $k>>d$, in one of our papers we did analyze one such autoencoder in details to be able to say something about what you are asking. Does our Theorem 3.2 here, https://arxiv.org/pdf/1708.03735.pdf help? It took us about 15 pages of laborious calculation to get this - hopefully its helpful! :D