[{"date_updated":"2026-05-23T22:30:05Z","publication_status":"published","department":[{"_id":"DaAl"},{"_id":"MaMo"}],"quality_controlled":"1","author":[{"full_name":"Kögler, Kevin","first_name":"Kevin","id":"94ec913c-dc85-11ea-9058-e5051ab2428b","last_name":"Kögler"},{"id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","first_name":"Aleksandr","last_name":"Shevchenko","full_name":"Shevchenko, Aleksandr"},{"last_name":"Hassani","first_name":"Hamed","full_name":"Hassani, Hamed"},{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","full_name":"Mondelli, Marco","last_name":"Mondelli"}],"main_file_link":[{"url":"https://proceedings.mlr.press/v235/kogler24a.html","open_access":"1"}],"_id":"17469","citation":{"apa":"Kögler, K., Shevchenko, A., Hassani, H., &#38; Mondelli, M. (2024). 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, pp. 24964–25015). Vienna, Austria: ML Research Press.","short":"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.","ieee":"K. Kögler, A. Shevchenko, H. Hassani, and M. Mondelli, “Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 24964–25015.","ista":"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.","chicago":"Kögler, Kevin, Alexander Shevchenko, Hamed Hassani, and Marco Mondelli. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:24964–15. ML Research Press, 2024.","mla":"Kögler, Kevin, et al. “Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 24964–5015.","ama":"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."},"conference":{"location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21","end_date":"2024-07-27"},"publisher":"ML Research Press","title":"Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth","related_material":{"record":[{"id":"17465","relation":"dissertation_contains","status":"public"}]},"date_created":"2024-08-29T11:47:57Z","arxiv":1,"page":"24964-25015","article_processing_charge":"No","external_id":{"arxiv":["2402.05013"]},"type":"conference","acknowledgement":"Kevin Kogler, Alexander Shevchenko and Marco Mondelli are supported by the 2019 Lopez-Loreta Prize. Hamed\r\nHassani acknowledges the support by the NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science (EnCORE).","year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication":"Proceedings of the 41st International Conference on Machine Learning","month":"07","abstract":[{"lang":"eng","text":"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."}],"oa_version":"Published Version","scopus_import":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"date_published":"2024-07-01T00:00:00Z","volume":235,"day":"01","corr_author":"1","status":"public","oa":1,"alternative_title":["PMLR"],"intvolume":"       235"},{"date_created":"2023-10-29T23:01:17Z","related_material":{"record":[{"id":"17465","relation":"dissertation_contains","status":"public"}]},"arxiv":1,"conference":{"location":"Honolulu, Hawaii, HI, United States","end_date":"2023-07-29","name":"ICML: International Conference on Machine Learning","start_date":"2023-07-23"},"publisher":"ML Research Press","title":"Fundamental limits of two-layer autoencoders, and achieving them with gradient methods","external_id":{"arxiv":["2212.13468"]},"type":"conference","page":"31151-31209","article_processing_charge":"No","publication_status":"published","date_updated":"2026-05-23T22:30:06Z","_id":"14459","citation":{"ama":"Shevchenko A, Kögler K, Hassani H, Mondelli M. Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. In: <i>Proceedings of the 40th International Conference on Machine Learning</i>. Vol 202. ML Research Press; 2023:31151-31209.","mla":"Shevchenko, Alexander, et al. “Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient Methods.” <i>Proceedings of the 40th International Conference on Machine Learning</i>, vol. 202, ML Research Press, 2023, pp. 31151–209.","chicago":"Shevchenko, Alexander, Kevin Kögler, Hamed Hassani, and Marco Mondelli. “Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient Methods.” In <i>Proceedings of the 40th International Conference on Machine Learning</i>, 202:31151–209. ML Research Press, 2023.","ista":"Shevchenko A, Kögler K, Hassani H, Mondelli M. 2023. Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. Proceedings of the 40th International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 202, 31151–31209.","ieee":"A. Shevchenko, K. Kögler, H. Hassani, and M. Mondelli, “Fundamental limits of two-layer autoencoders, and achieving them with gradient methods,” in <i>Proceedings of the 40th International Conference on Machine Learning</i>, Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 31151–31209.","short":"A. Shevchenko, K. Kögler, H. Hassani, M. Mondelli, in:, Proceedings of the 40th International Conference on Machine Learning, ML Research Press, 2023, pp. 31151–31209.","apa":"Shevchenko, A., Kögler, K., Hassani, H., &#38; Mondelli, M. (2023). Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. In <i>Proceedings of the 40th International Conference on Machine Learning</i> (Vol. 202, pp. 31151–31209). Honolulu, Hawaii, HI, United States: ML Research Press."},"department":[{"_id":"MaMo"},{"_id":"DaAl"}],"quality_controlled":"1","author":[{"id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","full_name":"Shevchenko, Aleksandr","first_name":"Aleksandr","last_name":"Shevchenko"},{"first_name":"Kevin","full_name":"Kögler, Kevin","last_name":"Kögler","id":"94ec913c-dc85-11ea-9058-e5051ab2428b"},{"last_name":"Hassani","first_name":"Hamed","full_name":"Hassani, Hamed"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2212.13468"}],"corr_author":"1","oa":1,"alternative_title":["PMLR"],"status":"public","volume":202,"publication_identifier":{"eissn":["2640-3498"]},"day":"30","intvolume":"       202","language":[{"iso":"eng"}],"year":"2023","acknowledgement":"Aleksandr Shevchenko, Kevin Kogler and Marco Mondelli are supported by the 2019 Lopez-Loreta Prize. Hamed Hassani acknowledges the support by the NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science (EnCORE).","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","date_published":"2023-07-30T00:00:00Z","scopus_import":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"month":"07","publication":"Proceedings of the 40th International Conference on Machine Learning","abstract":[{"lang":"eng","text":"Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions."}]},{"publication":"Proceedings of the 39th International Conference on Machine Learning","ddc":["000"],"abstract":[{"lang":"eng","text":"We consider the problem of signal estimation in generalized linear models defined via rotationally invariant design matrices. Since these matrices can have an arbitrary spectral distribution, this model is well suited for capturing complex correlation structures which often arise in applications. We propose a novel family of approximate message passing (AMP) algorithms for signal estimation, and rigorously characterize their performance in the high-dimensional limit via a state evolution recursion. Our rotationally invariant AMP has complexity of the same order as the existing AMP derived under the restrictive assumption of a Gaussian design; our algorithm also recovers this existing AMP as a special case. Numerical results showcase a performance close to Vector AMP (which is conjectured to be Bayes-optimal in some settings), but obtained with a much lower complexity, as the proposed algorithm does not require a computationally expensive singular value decomposition."}],"oa_version":"Published Version","date_published":"2022-01-01T00:00:00Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"year":"2022","acknowledgement":"The authors would like to thank the anonymous reviewers for their helpful comments. KK and MM were partially supported by the 2019 Lopez-Loreta Prize.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"intvolume":"       162","volume":162,"corr_author":"1","status":"public","oa":1,"department":[{"_id":"MaMo"}],"quality_controlled":"1","author":[{"first_name":"Ramji","full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan"},{"id":"94ec913c-dc85-11ea-9058-e5051ab2428b","last_name":"Kögler","first_name":"Kevin","full_name":"Kögler, Kevin"},{"orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco"}],"_id":"12540","citation":{"ista":"Venkataramanan R, Kögler K, Mondelli M. 2022. Estimation in rotationally invariant generalized linear models via approximate message passing. Proceedings of the 39th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 162, 22.","apa":"Venkataramanan, R., Kögler, K., &#38; Mondelli, M. (2022). Estimation in rotationally invariant generalized linear models via approximate message passing. In <i>Proceedings of the 39th International Conference on Machine Learning</i> (Vol. 162). Baltimore, MD, United States: ML Research Press.","ieee":"R. Venkataramanan, K. Kögler, and M. Mondelli, “Estimation in rotationally invariant generalized linear models via approximate message passing,” in <i>Proceedings of the 39th International Conference on Machine Learning</i>, Baltimore, MD, United States, 2022, vol. 162.","short":"R. Venkataramanan, K. Kögler, M. Mondelli, in:, Proceedings of the 39th International Conference on Machine Learning, ML Research Press, 2022.","mla":"Venkataramanan, Ramji, et al. “Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing.” <i>Proceedings of the 39th International Conference on Machine Learning</i>, vol. 162, 22, ML Research Press, 2022.","ama":"Venkataramanan R, Kögler K, Mondelli M. Estimation in rotationally invariant generalized linear models via approximate message passing. In: <i>Proceedings of the 39th International Conference on Machine Learning</i>. Vol 162. ML Research Press; 2022.","chicago":"Venkataramanan, Ramji, Kevin Kögler, and Marco Mondelli. “Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing.” In <i>Proceedings of the 39th International Conference on Machine Learning</i>, Vol. 162. ML Research Press, 2022."},"date_updated":"2025-04-15T07:50:16Z","article_number":"22","file_date_updated":"2023-02-13T10:53:11Z","publication_status":"published","article_processing_charge":"No","type":"conference","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2022-07-17","end_date":"2022-07-23","location":"Baltimore, MD, United States"},"file":[{"date_updated":"2023-02-13T10:53:11Z","content_type":"application/pdf","file_size":2341343,"access_level":"open_access","date_created":"2023-02-13T10:53:11Z","success":1,"relation":"main_file","checksum":"67436eb0a660789514cdf9db79e84683","file_name":"2022_PMLR_Venkataramanan.pdf","creator":"dernst","file_id":"12547"}],"title":"Estimation in rotationally invariant generalized linear models via approximate message passing","publisher":"ML Research Press","date_created":"2023-02-10T13:49:04Z","has_accepted_license":"1"}]