Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth

conference paper Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth PMLR published yes Kevin Kögler author 94ec913c-dc85-11ea-9058-e5051ab2428b Aleksandr Shevchenko author F2B06EC2-C99E-11E9-89F0-752EE6697425 Hamed Hassani author Marco Mondelli author 27EB676C-8706-11E9-9510-7717E66974250000-0002-3242-7020 DaAl department MaMo department ICML: International Conference on Machine Learning Prix Lopez-Loretta 2019 - Marco Mondelli project Autoencoders are a prominent model in many empirical branches of machine learning and lossy data compression. However, basic theoretical questions remain unanswered even in a shallow two-layer setting. In particular, to what degree does a shallow autoencoder capture the structure of the underlying data distribution? For the prototypical case of the 1-bit compression of sparse Gaussian data, we prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. Namely, the performance of the algorithm is the same as if it was compressing a Gaussian source - with no sparsity. For general data distributions, we give evidence of a phase transition phenomenon in the shape of the gradient descent minimizer, as a function of the data sparsity: below the critical sparsity level, the minimizer is a rotation taken uniformly at random (just like in the compression of non-sparse data); above the critical sparsity, the minimizer is the identity (up to a permutation). Finally, by exploiting a connection with approximate message passing algorithms, we show how to improve upon Gaussian performance for the compression of sparse data: adding a denoising function to a shallow architecture already reduces the loss provably, and a suitable multi-layer decoder leads to a further improvement. We validate our findings on image datasets, such as CIFAR-10 and MNIST. ML Research Press2024Vienna, Austria eng Proceedings of the 41st International Conference on Machine Learning 2402.05013 23524964-25015 https://research-explorer.ista.ac.at/record/23072 https://research-explorer.ista.ac.at/record/17465 K. Kögler, A. Shevchenko, H. Hassani, M. Mondelli, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 24964–25015. Kögler, K., Shevchenko, A., Hassani, H., & Mondelli, M. (2024). Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. In Proceedings of the 41st International Conference on Machine Learning (Vol. 235, pp. 24964–25015). Vienna, Austria: ML Research Press. K. Kögler, A. Shevchenko, H. Hassani, and M. Mondelli, “Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth,” in Proceedings of the 41st International Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 24964–25015. Kögler K, Shevchenko A, Hassani H, Mondelli M. 2024. Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 24964–25015. Kögler K, Shevchenko A, Hassani H, Mondelli M. Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. In: Proceedings of the 41st International Conference on Machine Learning. Vol 235. ML Research Press; 2024:24964-25015. Kögler, Kevin, et al. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” Proceedings of the 41st International Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 24964–5015. Kögler, Kevin, Alexander Shevchenko, Hamed Hassani, and Marco Mondelli. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” In Proceedings of the 41st International Conference on Machine Learning, 235:24964–15. ML Research Press, 2024. 174692024-08-29T11:47:57Z2026-10-10T22:31:20Z