Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth PMLR Kögler, Kevin Shevchenko, Aleksandr Hassani, Hamed Mondelli, Marco ; https://orcid.org/0000-0002-3242-7020 ddc:000 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 Press 2024 info:eu-repo/semantics/conferenceObject doc-type:ConferenceObject ConferenceObject http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/17469 Kögler K, Shevchenko A, Hassani H, Mondelli M. Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:24964-25015. eng info:eu-repo/semantics/altIdentifier/arxiv/2402.05013 info:eu-repo/semantics/openAccess