Timeline for Autoencoders and information compression
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 27, 2018 at 21:53 | vote | accept | Clement C. | ||
| May 23, 2018 at 22:32 | history | tweeted | twitter.com/StackCSTheory/status/999417716061753345 | ||
| May 23, 2018 at 16:18 | answer | added | Student | timeline score: 2 | |
| Oct 14, 2017 at 1:01 | comment | added | Clement C. | @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. | |
| Oct 13, 2017 at 9:25 | comment | added | XL _At_Here_There | 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. | |
| Oct 12, 2017 at 21:10 | comment | added | D.W. | 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. | |
| Oct 12, 2017 at 19:19 | comment | added | Clement C. | @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)? | |
| Oct 11, 2017 at 22:13 | comment | added | user43170 | 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. | |
| Oct 11, 2017 at 5:37 | comment | added | D.W. | 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. | |
| Oct 10, 2017 at 11:54 | history | asked | Clement C. | CC BY-SA 3.0 |