<p>In the other situation when in your notation $k&gt;&gt;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, <a href="https://arxiv.org/pdf/1708.03735.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1708.03735.pdf</a> help? It took us about 15 pages of laborious calculation to get this - hopefully its helpful! :D  </p>

<p>The "??" in the statement is a LaTeX error. It was meant to refer to the previous Theorem 3.1.</p>

CC BY-SA 4.0
2018-05-27T21:53:36.877Z
It does look relevant, indeed!
Clement C.
CC BY-SA 4.0
2018-05-23T16:18:05.183Z
2018-05-23T16:23:37.550Z
2018-05-23T16:23:37.550Z
Student
<p><em>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.</em></p>

<p>If I understood correctly the concept, an <a href="https://en.wikipedia.org/wiki/Autoencoder" rel="nofollow noreferrer">autoencoder</a> is a specific case of neural networks with as many input nodes than output nodes (say $d$), whose goal is to approximate the <em>identity</em> 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.</p>

<p>This struck me as begging the question:</p>

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

<p>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?</p>

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

CC BY-SA 3.0
2017-10-11T05:37:20.063Z
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.
CC BY-SA 3.0
2017-10-11T22:13:42.990Z
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: https://arxiv.org/abs/1310.6343.
user43170
CC BY-SA 3.0
2017-10-12T19:19:25.417Z
@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.
CC BY-SA 3.0
2017-10-12T21:10:31.853Z
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.
CC BY-SA 3.0
2017-10-13T09:25:19.163Z
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_Here_There
CC BY-SA 3.0
2017-10-14T01:01:49.103Z
@D.W. Mmh. I guess the question should become "what is the most interesting theoretical paradigm/model under which to study this question so that we can still get non-trivial answers", then. I had the impression that learning the identity function and see what these learning algorithms did under the hood would be a good start -- but now that gets too hazy and vague to be even considered as a well-formulated question.
Clement C.
<machine-learning><it.information-theory>
Autoencoders and information compression
Clement C.
# Autoencoders and information compression

(Asked by: username_0 on 2017-10-10)

*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](https://en.wikipedia.org/wiki/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?

**Tags:** machine-learning, it.information-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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: https://arxiv.org/abs/1310.6343.  
> **username_0**: @username_1 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)?  
> **username_1**: 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.  
> **username_3**: 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.  
> **username_0**: @username_1 Mmh. I guess the question should become "what is the most interesting theoretical paradigm/model under which to study this question so that we can still get non-trivial answers", then. I had the impression that learning the identity function and see what these learning algorithms did under the hood would be a good start -- but now that gets too hazy and vague to be even considered as a well-formulated question.  

---

## 1 answers

### Answer by username_4 on 2018-05-23. Score: 2 | Accepted answer

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

The "??" in the statement is a LaTeX error. It was meant to refer to the previous Theorem 3.1.

> **Comments:**
> **username_0**: It does look relevant, indeed!  

---

