[{"month":"07","project":[{"_id":"911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf","name":"Inference in High Dimensions: Light-speed Algorithms and Information Limits","grant_number":"101161364"},{"name":"Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust LLMs","_id":"92099302-16d5-11f0-9cad-f9a785f54fbd"}],"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"_id":"21324","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"arxiv":1,"publication":"Proceedings of the 42nd International Conference on Machine Learning","has_accepted_license":"1","date_published":"2025-07-30T00:00:00Z","publication_status":"published","ddc":["000"],"type":"conference","page":"4839-4873","title":"Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterization","abstract":[{"lang":"eng","text":"Learning models have been shown to rely on spurious correlations between non-predictive features and the associated labels in the training data, with negative implications on robustness, bias and fairness. In this work, we provide a statistical characterization of this phenomenon for high-dimensional regression, when the data contains a predictive core feature x and a spurious feature y. Specifically, we quantify the amount of spurious correlations C learned via linear regression, in terms of the data covariance and the strength λ of the ridge regularization. As a consequence, we first capture the simplicity of y through the spectrum of its covariance, and its correlation with x through the Schur complement of the full data covariance. Next, we prove a trade-off between C and the in-distribution test loss L, by showing that the value of λ that minimizes L lies in an interval where C is increasing. Finally, we investigate the effects of over-parameterization via the random features model, by showing its equivalence to regularized linear regression. Our theoretical results are supported by numerical experiments on Gaussian, Color-MNIST, and CIFAR-10 datasets."}],"file":[{"content_type":"application/pdf","success":1,"file_id":"21335","checksum":"d4ba4f7717b362ca38878f45e57bd643","access_level":"open_access","creator":"dernst","file_name":"2025_ICML_Bombari.pdf","date_created":"2026-02-19T08:04:38Z","date_updated":"2026-02-19T08:04:38Z","relation":"main_file","file_size":887526}],"acknowledgement":"Marco Mondelli is funded by the European Union (ERC, INF2, project number 101161364). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Simone Bombari is supported by a Google PhD fellowship. The authors would like to thank GuanWen Qiu for helpful discussions.","OA_type":"gold","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"22857"}]},"article_processing_charge":"No","citation":{"ieee":"S. Bombari and M. Mondelli, “Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterization,” in <i>Proceedings of the 42nd International Conference on Machine Learning</i>, Vancouver, Canada, 2025, vol. 267, pp. 4839–4873.","chicago":"Bombari, Simone, and Marco Mondelli. “Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and over-Parameterization.” In <i>Proceedings of the 42nd International Conference on Machine Learning</i>, 267:4839–73. ML Research Press, 2025.","ama":"Bombari S, Mondelli M. Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterization. In: <i>Proceedings of the 42nd International Conference on Machine Learning</i>. Vol 267. ML Research Press; 2025:4839-4873.","apa":"Bombari, S., &#38; Mondelli, M. (2025). Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterization. In <i>Proceedings of the 42nd International Conference on Machine Learning</i> (Vol. 267, pp. 4839–4873). Vancouver, Canada: ML Research Press.","short":"S. Bombari, M. Mondelli, in:, Proceedings of the 42nd International Conference on Machine Learning, ML Research Press, 2025, pp. 4839–4873.","mla":"Bombari, Simone, and Marco Mondelli. “Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and over-Parameterization.” <i>Proceedings of the 42nd International Conference on Machine Learning</i>, vol. 267, ML Research Press, 2025, pp. 4839–73.","ista":"Bombari S, Mondelli M. 2025. Spurious correlations in high dimensional regression: The roles of regularization, simplicity bias and over-parameterization. Proceedings of the 42nd International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 267, 4839–4873."},"volume":267,"file_date_updated":"2026-02-19T08:04:38Z","language":[{"iso":"eng"}],"alternative_title":["PMLR"],"conference":{"start_date":"2025-07-13","location":"Vancouver, Canada","end_date":"2025-07-19","name":"ICML: International Conference on Machine Learning"},"publication_identifier":{"eissn":["2640-3498"]},"oa_version":"Published Version","day":"30","intvolume":"       267","OA_place":"publisher","corr_author":"1","department":[{"_id":"MaMo"}],"quality_controlled":"1","external_id":{"arxiv":["2502.01347"]},"date_updated":"2026-09-21T13:07:01Z","date_created":"2026-02-18T11:58:00Z","author":[{"first_name":"Simone","last_name":"Bombari","full_name":"Bombari, Simone","id":"ca726dda-de17-11ea-bc14-f9da834f63aa"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","full_name":"Mondelli, Marco"}],"status":"public","publisher":"ML Research Press"},{"month":"12","scopus_import":"1","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"_id":"19518","year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication":"38th Conference on Neural Information Processing Systems","arxiv":1,"type":"conference","publication_status":"published","date_published":"2024-12-20T00:00:00Z","OA_type":"green","acknowledgement":"The authors thank the anonymous NeurIPS reviewers for their useful comments and feedback, the IT department from the Institute of Science and Technology Austria for the hardware support, and Weights and Biases for the infrastructure to track all our experiments. Mher Safaryan has received funding from the European Union’s Horizon 2020 research and innovation program under the Maria Skłodowska-Curie grant agreement No 101034413.","abstract":[{"text":"The rising footprint of machine learning has led to a focus on imposing model\r\nsparsity as a means of reducing computational and memory costs. For deep neural\r\nnetworks (DNNs), the state-of-the-art accuracy-vs-sparsity is achieved by heuristics\r\ninspired by the classical Optimal Brain Surgeon (OBS) framework [LeCun et al.,\r\n1989, Hassibi and Stork, 1992, Hassibi et al., 1993], which leverages loss curvature\r\ninformation to make better pruning decisions. Yet, these results still lack a solid\r\ntheoretical understanding, and it is unclear whether they can be improved by\r\nleveraging connections to the wealth of work on sparse recovery algorithms. In this\r\npaper, we draw new connections between these two areas and present new sparse\r\nrecovery algorithms inspired by the OBS framework that comes with theoretical\r\nguarantees under reasonable assumptions and have strong practical performance.\r\nSpecifically, our work starts from the observation that we can leverage curvature\r\ninformation in OBS-like fashion upon the projection step of classic iterative sparse\r\nrecovery algorithms such as IHT. We show for the first time that this leads both\r\nto improved convergence bounds under standard assumptions. Furthermore, we\r\npresent extensions of this approach to the practical task of obtaining accurate sparse\r\nDNNs, and validate it experimentally at scale for Transformer-based models on\r\nvision and language tasks.","lang":"eng"}],"title":"The iterative optimal brain surgeon: Faster sparse recovery by leveraging second-order information","article_processing_charge":"No","alternative_title":["Advances in Neural Information Processing Systems"],"conference":{"name":"NeurIPS: Neural Information Processing Systems","end_date":"2024-12-15","location":"Vancouver, Canada","start_date":"2024-12-09"},"language":[{"iso":"eng"}],"volume":37,"citation":{"ista":"Wu D, Modoranu I-V, Safaryan M, Kuznedelev D, Alistarh D-A. 2024. The iterative optimal brain surgeon: Faster sparse recovery by leveraging second-order information. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.","short":"D. Wu, I.-V. Modoranu, M. Safaryan, D. Kuznedelev, D.-A. Alistarh, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.","mla":"Wu, Diyuan, et al. “The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information.” <i>38th Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024.","apa":"Wu, D., Modoranu, I.-V., Safaryan, M., Kuznedelev, D., &#38; Alistarh, D.-A. (2024). The iterative optimal brain surgeon: Faster sparse recovery by leveraging second-order information. In <i>38th Conference on Neural Information Processing Systems</i> (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation.","ama":"Wu D, Modoranu I-V, Safaryan M, Kuznedelev D, Alistarh D-A. The iterative optimal brain surgeon: Faster sparse recovery by leveraging second-order information. In: <i>38th Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024.","ieee":"D. Wu, I.-V. Modoranu, M. Safaryan, D. Kuznedelev, and D.-A. Alistarh, “The iterative optimal brain surgeon: Faster sparse recovery by leveraging second-order information,” in <i>38th Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2024, vol. 37.","chicago":"Wu, Diyuan, Ionut-Vlad Modoranu, Mher Safaryan, Denis Kuznedelev, and Dan-Adrian Alistarh. “The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information.” In <i>38th Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024."},"day":"20","publication_identifier":{"issn":["1049-5258"]},"oa_version":"Preprint","external_id":{"arxiv":["2408.17163"]},"acknowledged_ssus":[{"_id":"CampIT"}],"quality_controlled":"1","corr_author":"1","department":[{"_id":"DaAl"},{"_id":"MaMo"}],"intvolume":"        37","OA_place":"repository","author":[{"first_name":"Diyuan","full_name":"Wu, Diyuan","last_name":"Wu","id":"1a5914c2-896a-11ed-bdf8-fb80621a0635"},{"last_name":"Modoranu","id":"449f7a18-f128-11eb-9611-9b430c0c6333","full_name":"Modoranu, Ionut-Vlad","first_name":"Ionut-Vlad"},{"first_name":"Mher","last_name":"Safaryan","id":"dd546b39-0804-11ed-9c55-ef075c39778d","full_name":"Safaryan, Mher"},{"full_name":"Kuznedelev, Denis","last_name":"Kuznedelev","first_name":"Denis"},{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X"}],"ec_funded":1,"date_created":"2025-04-06T22:01:32Z","date_updated":"2025-05-14T11:37:10Z","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2408.17163","open_access":"1"}],"publisher":"Neural Information Processing Systems Foundation"},{"day":"01","oa_version":"Published Version","conference":{"location":"Vancouver, Canada","start_date":"2024-12-16","name":"NeurIPS: Neural Information Processing Systems","end_date":"2024-12-16"},"alternative_title":["Advances in Neural Information Processing Systems"],"language":[{"iso":"eng"}],"file_date_updated":"2025-02-04T08:11:25Z","volume":37,"citation":{"ista":"Súkeník P, Lampert C, Mondelli M. 2024. Neural collapse versus low-rank bias: Is deep neural collapse really optimal? 38th Annual Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.","ieee":"P. Súkeník, C. Lampert, and M. Mondelli, “Neural collapse versus low-rank bias: Is deep neural collapse really optimal?,” in <i>38th Annual Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2024, vol. 37.","chicago":"Súkeník, Peter, Christoph Lampert, and Marco Mondelli. “Neural Collapse versus Low-Rank Bias: Is Deep Neural Collapse Really Optimal?” In <i>38th Annual Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024.","ama":"Súkeník P, Lampert C, Mondelli M. Neural collapse versus low-rank bias: Is deep neural collapse really optimal? In: <i>38th Annual Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024.","apa":"Súkeník, P., Lampert, C., &#38; Mondelli, M. (2024). Neural collapse versus low-rank bias: Is deep neural collapse really optimal? In <i>38th Annual Conference on Neural Information Processing Systems</i> (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation.","mla":"Súkeník, Peter, et al. “Neural Collapse versus Low-Rank Bias: Is Deep Neural Collapse Really Optimal?” <i>38th Annual Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024.","short":"P. Súkeník, C. Lampert, M. Mondelli, in:, 38th Annual Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024."},"article_processing_charge":"No","das_tickbox":"0","supplementarymaterial":"no","OA_type":"gold","acknowledgement":"Marco Mondelli is partially supported by the 2019 Lopez-Loreta prize. This research was supported by the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).","file":[{"checksum":"b7b79f1ea3ac1e9e11b3d91faaeb0780","file_id":"18989","content_type":"application/pdf","success":1,"file_size":1784118,"relation":"main_file","access_level":"open_access","creator":"dernst","date_created":"2025-02-04T08:11:25Z","date_updated":"2025-02-04T08:11:25Z","file_name":"2024_NeurIPS_Sukenik.pdf"}],"abstract":[{"lang":"eng","text":"Deep neural networks (DNNs) exhibit a surprising structure in their final layer\r\nknown as neural collapse (NC), and a growing body of works has currently investigated the propagation of neural collapse to earlier layers of DNNs – a phenomenon\r\ncalled deep neural collapse (DNC). However, existing theoretical results are restricted to special cases: linear models, only two layers or binary classification.\r\nIn contrast, we focus on non-linear models of arbitrary depth in multi-class classification and reveal a surprising qualitative shift. As soon as we go beyond two\r\nlayers or two classes, DNC stops being optimal for the deep unconstrained features\r\nmodel (DUFM) – the standard theoretical framework for the analysis of collapse.\r\nThe main culprit is a low-rank bias of multi-layer regularization schemes: this bias\r\nleads to optimal solutions of even lower rank than the neural collapse. We support\r\nour theoretical findings with experiments on both DUFM and real data, which show\r\nthe emergence of the low-rank structure in the solution found by gradient descent."}],"title":"Neural collapse versus low-rank bias: Is deep neural collapse really optimal?","researchdata_availability":"no","publisher":"Neural Information Processing Systems Foundation","status":"public","author":[{"full_name":"Súkeník, Peter","id":"d64d6a8d-eb8e-11eb-b029-96fd216dec3c","last_name":"Súkeník","first_name":"Peter"},{"orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli"}],"date_created":"2025-01-27T11:15:18Z","date_updated":"2026-10-02T11:34:35Z","external_id":{"arxiv":["2405.14468"]},"acknowledged_ssus":[{"_id":"ScienComp"}],"quality_controlled":"1","corr_author":"1","department":[{"_id":"GradSch"},{"_id":"MaMo"},{"_id":"ChLa"}],"intvolume":"        37","OA_place":"publisher","year":"2024","_id":"18891","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"month":"12","type":"conference","ddc":["000"],"publication_status":"published","date_published":"2024-12-01T00:00:00Z","publication":"38th Annual Conference on Neural Information Processing Systems","has_accepted_license":"1","arxiv":1,"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"year":"2024","_id":"18897","project":[{"_id":"fc31cba2-9c52-11eb-aca3-ff467d239cd2","name":"Taming Complexity in Partial Differential Systems","grant_number":"F6504"},{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"month":"06","scopus_import":"1","type":"conference","ddc":["000"],"date_published":"2024-06-01T00:00:00Z","publication_status":"published","arxiv":1,"has_accepted_license":"1","publication":"Transactions on Machine Learning Research","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_identifier":{"issn":["2835-8856"]},"oa_version":"Published Version","day":"01","file_date_updated":"2025-01-27T12:19:44Z","language":[{"iso":"eng"}],"alternative_title":["TMLR"],"citation":{"ista":"Pedrotti F, Maas J, Mondelli M. 2024. Improved convergence of score-based diffusion models via prediction-correction. Transactions on Machine Learning Research. , TMLR, .","short":"F. Pedrotti, J. Maas, M. Mondelli, in:, Transactions on Machine Learning Research, 2024.","mla":"Pedrotti, Francesco, et al. “Improved Convergence of Score-Based Diffusion Models via Prediction-Correction.” <i>Transactions on Machine Learning Research</i>, 2024.","apa":"Pedrotti, F., Maas, J., &#38; Mondelli, M. (2024). Improved convergence of score-based diffusion models via prediction-correction. In <i>Transactions on Machine Learning Research</i>.","ama":"Pedrotti F, Maas J, Mondelli M. Improved convergence of score-based diffusion models via prediction-correction. In: <i>Transactions on Machine Learning Research</i>. ; 2024.","chicago":"Pedrotti, Francesco, Jan Maas, and Marco Mondelli. “Improved Convergence of Score-Based Diffusion Models via Prediction-Correction.” In <i>Transactions on Machine Learning Research</i>, 2024.","ieee":"F. Pedrotti, J. Maas, and M. Mondelli, “Improved convergence of score-based diffusion models via prediction-correction,” in <i>Transactions on Machine Learning Research</i>, 2024."},"article_processing_charge":"No","das_tickbox":"0","OA_type":"gold","related_material":{"record":[{"id":"17350","status":"public","relation":"earlier_version"}]},"acknowledgement":"Francesco Pedrotti and Jan Maas acknowledge support by the Austrian Science Fund (FWF) project 10.55776/F65. Marco Mondelli acknowledges support by the 2019 Lopez-Loreta prize.\r\n","supplementarymaterial":"no","title":"Improved convergence of score-based diffusion models via prediction-correction","file":[{"checksum":"76a1fd5afd8ee6f7ae0e5912d7dbf6b4","file_id":"18898","content_type":"application/pdf","success":1,"file_size":780315,"relation":"main_file","access_level":"open_access","file_name":"2024_TMLR_Pedrotti.pdf","date_updated":"2025-01-27T12:19:44Z","date_created":"2025-01-27T12:19:44Z","creator":"dernst"}],"abstract":[{"text":"Score-based generative models (SGMs) are powerful tools to sample from complex data distributions. Their underlying idea is to (i) run a forward process for time T1 by adding noise to the data, (ii) estimate its score function, and (iii) use such estimate to run a reverse process. As the reverse process is initialized with the stationary distribution of the forward one, the existing analysis paradigm requires T1→∞. This is however problematic: from a theoretical viewpoint, for a given precision of the score approximation, the convergence guarantee fails as T1 diverges; from a practical viewpoint, a large T1 increases computational costs and leads to error propagation. This paper addresses the issue by considering a version of the popular predictor-corrector scheme: after running the forward process, we first estimate the final distribution via an inexact Langevin dynamics and then revert the process. Our key technical contribution is to provide convergence guarantees which require to run the forward process only for a fixed finite time T1. Our bounds exhibit a mild logarithmic dependence on the input dimension and the subgaussian norm of the target distribution, have minimal assumptions on the data, and require only to control the L2 loss on the score approximation, which is the quantity minimized in practice.","lang":"eng"}],"researchdata_availability":"no","status":"public","date_updated":"2026-10-02T12:22:41Z","date_created":"2025-01-27T12:18:05Z","author":[{"first_name":"Francesco","full_name":"Pedrotti, Francesco","id":"d3ac8ac6-dc8d-11ea-abe3-e2a9628c4c3c","last_name":"Pedrotti"},{"orcid":"0000-0002-0845-1338","id":"4C5696CE-F248-11E8-B48F-1D18A9856A87","last_name":"Maas","full_name":"Maas, Jan","first_name":"Jan"},{"orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco"}],"quality_controlled":"1","external_id":{"arxiv":["2305.14164"]},"OA_place":"publisher","corr_author":"1","department":[{"_id":"JaMa"},{"_id":"MaMo"}]},{"project":[{"grant_number":"F6504","name":"Taming Complexity in Partial Differential Systems","_id":"fc31cba2-9c52-11eb-aca3-ff467d239cd2"},{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"month":"06","year":"2024","_id":"17350","fulldoi":"https://doi.org/10.48550/arXiv.2305.14164","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2024-06-06T00:00:00Z","publication_status":"draft","type":"preprint","arxiv":1,"publication":"arXiv","das_tickbox":"0","article_processing_charge":"No","title":"Improved convergence of score-based diffusion models via prediction-correction","abstract":[{"text":"Score-based generative models (SGMs) are powerful tools to sample from\r\ncomplex data distributions. Their underlying idea is to (i) run a forward\r\nprocess for time $T_1$ by adding noise to the data, (ii) estimate its score\r\nfunction, and (iii) use such estimate to run a reverse process. As the reverse\r\nprocess is initialized with the stationary distribution of the forward one, the\r\nexisting analysis paradigm requires $T_1\\to\\infty$. This is however\r\nproblematic: from a theoretical viewpoint, for a given precision of the score\r\napproximation, the convergence guarantee fails as $T_1$ diverges; from a\r\npractical viewpoint, a large $T_1$ increases computational costs and leads to\r\nerror propagation. This paper addresses the issue by considering a version of\r\nthe popular predictor-corrector scheme: after running the forward process, we\r\nfirst estimate the final distribution via an inexact Langevin dynamics and then\r\nrevert the process. Our key technical contribution is to provide convergence\r\nguarantees which require to run the forward process only for a fixed finite\r\ntime $T_1$. Our bounds exhibit a mild logarithmic dependence on the input\r\ndimension and the subgaussian norm of the target distribution, have minimal\r\nassumptions on the data, and require only to control the $L^2$ loss on the\r\nscore approximation, which is the quantity minimized in practice.","lang":"eng"}],"related_material":{"record":[{"status":"public","id":"17336","relation":"dissertation_contains"},{"relation":"later_version","id":"18897","status":"public"}]},"supplementarymaterial":"no","oa_version":"Preprint","day":"06","citation":{"ista":"Pedrotti F, Maas J, Mondelli M. Improved convergence of score-based diffusion models via prediction-correction. arXiv, <a href=\"https://doi.org/10.48550/arXiv.2305.14164\">10.48550/arXiv.2305.14164</a>.","chicago":"Pedrotti, Francesco, Jan Maas, and Marco Mondelli. “Improved Convergence of Score-Based Diffusion Models via Prediction-Correction.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2305.14164\">https://doi.org/10.48550/arXiv.2305.14164</a>.","ieee":"F. Pedrotti, J. Maas, and M. Mondelli, “Improved convergence of score-based diffusion models via prediction-correction,” <i>arXiv</i>. .","ama":"Pedrotti F, Maas J, Mondelli M. Improved convergence of score-based diffusion models via prediction-correction. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2305.14164\">10.48550/arXiv.2305.14164</a>","apa":"Pedrotti, F., Maas, J., &#38; Mondelli, M. (n.d.). Improved convergence of score-based diffusion models via prediction-correction. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2305.14164\">https://doi.org/10.48550/arXiv.2305.14164</a>","short":"F. Pedrotti, J. Maas, M. Mondelli, ArXiv (n.d.).","mla":"Pedrotti, Francesco, et al. “Improved Convergence of Score-Based Diffusion Models via Prediction-Correction.” <i>ArXiv</i>, doi:<a href=\"https://doi.org/10.48550/arXiv.2305.14164\">10.48550/arXiv.2305.14164</a>."},"language":[{"iso":"eng"}],"date_created":"2024-07-31T07:56:40Z","date_updated":"2026-10-02T12:22:41Z","author":[{"full_name":"Pedrotti, Francesco","last_name":"Pedrotti","id":"d3ac8ac6-dc8d-11ea-abe3-e2a9628c4c3c","first_name":"Francesco"},{"id":"4C5696CE-F248-11E8-B48F-1D18A9856A87","last_name":"Maas","full_name":"Maas, Jan","first_name":"Jan","orcid":"0000-0002-0845-1338"},{"last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","first_name":"Marco","orcid":"0000-0002-3242-7020"}],"OA_place":"repository","department":[{"_id":"JaMa"},{"_id":"MaMo"}],"corr_author":"1","doi":"10.48550/arXiv.2305.14164","external_id":{"arxiv":["2305.14164"]},"researchdata_availability":"no","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2305.14164","open_access":"1"}],"status":"public"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"fulldoi":"https://doi.org/10.52202/079017-4156","publication":"38th Annual Conference on Neural Information Processing Systems","arxiv":1,"type":"conference","publication_status":"published","date_published":"2024-12-01T00:00:00Z","month":"12","scopus_import":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"_id":"18890","year":"2024","external_id":{"arxiv":["2402.13728"]},"doi":"10.52202/079017-4156","quality_controlled":"1","department":[{"_id":"GradSch"},{"_id":"MaMo"}],"corr_author":"1","intvolume":"        37","OA_place":"publisher","author":[{"first_name":"Daniel","last_name":"Beaglehole","full_name":"Beaglehole, Daniel"},{"full_name":"Súkeník, Peter","id":"d64d6a8d-eb8e-11eb-b029-96fd216dec3c","last_name":"Súkeník","first_name":"Peter"},{"orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","first_name":"Marco"},{"last_name":"Belkin","full_name":"Belkin, Mikhail","first_name":"Mikhail"}],"date_created":"2025-01-27T11:11:40Z","date_updated":"2026-10-15T09:39:46Z","status":"public","main_file_link":[{"url":"https://doi.org/10.52202/079017-4156","open_access":"1"}],"publisher":"Neural Information Processing Systems Foundation","researchdata_availability":"no","supplementarymaterial":"no","acknowledgement":"We acknowledge support from the National Science Foundation (NSF) and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031883 and #814639 as well as the TILOS institute (NSF CCF-2112665). This work used the programs (1) XSEDE (Extreme science and engineering discovery environment) which is supported by NSF grant numbers ACI-1548562, and (2) ACCESS (Advanced cyberinfrastructure coordination ecosystem: services & support) which is supported by NSF grants numbers #2138259, #2138286, #2138307, #2137603, and #2138296. Specifically, we used the resources from SDSC Expanse GPU compute nodes, and NCSA Delta system, via allocations TG-CIS220009. Marco Mondelli is supported by the 2019 Lopez-Loreta prize. We also acknowledge useful feedback from anonymous reviewers. ","OA_type":"free access","abstract":[{"text":"Deep Neural Collapse (DNC) refers to the surprisingly rigid structure of the data representations in the final layers of Deep Neural Networks (DNNs). Though the phenomenon has been measured in a variety of settings, its emergence is typically explained via data-agnostic approaches, such as the unconstrained features model. In this work, we introduce a data-dependent setting where DNC forms due to feature learning through the average gradient outer product (AGOP). The AGOP is defined with respect to a learned predictor and is equal to the uncentered covariance matrix of its input-output gradients averaged over the training dataset. The Deep Recursive Feature Machine (Deep RFM) is a method that constructs a neural network by iteratively mapping the data with the AGOP and applying an untrained random feature map. We demonstrate empirically that DNC occurs in Deep RFM across standard settings as a consequence of the projection with the AGOP matrix computed at each layer. Further, we theoretically explain DNC in Deep RFM in an asymptotic setting and as a result of kernel learning. We then provide evidence that this mechanism holds for neural networks more generally. In particular, we show that the right singular vectors and values of the weights can be responsible for the majority of within-class variability collapse for DNNs trained in the feature learning regime. As observed in recent work, this singular structure is highly correlated with that of the AGOP.","lang":"eng"}],"title":"Average gradient outer product as a mechanism for deep neural collapse","article_processing_charge":"No","das_tickbox":"0","conference":{"location":"Vancouver, Canada","start_date":"2024-12-16","end_date":"2024-12-16","name":"NeurIPS: Neural Information Processing Systems"},"alternative_title":["Advances in Neural Information Processing Systems"],"language":[{"iso":"eng"}],"volume":37,"citation":{"ista":"Beaglehole D, Súkeník P, Mondelli M, Belkin M. 2024. Average gradient outer product as a mechanism for deep neural collapse. 38th Annual Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37.","ama":"Beaglehole D, Súkeník P, Mondelli M, Belkin M. Average gradient outer product as a mechanism for deep neural collapse. In: <i>38th Annual Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024. doi:<a href=\"https://doi.org/10.52202/079017-4156\">10.52202/079017-4156</a>","chicago":"Beaglehole, Daniel, Peter Súkeník, Marco Mondelli, and Mikhail Belkin. “Average Gradient Outer Product as a Mechanism for Deep Neural Collapse.” In <i>38th Annual Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024. <a href=\"https://doi.org/10.52202/079017-4156\">https://doi.org/10.52202/079017-4156</a>.","ieee":"D. Beaglehole, P. Súkeník, M. Mondelli, and M. Belkin, “Average gradient outer product as a mechanism for deep neural collapse,” in <i>38th Annual Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2024, vol. 37.","short":"D. Beaglehole, P. Súkeník, M. Mondelli, M. Belkin, in:, 38th Annual Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.","mla":"Beaglehole, Daniel, et al. “Average Gradient Outer Product as a Mechanism for Deep Neural Collapse.” <i>38th Annual Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024, doi:<a href=\"https://doi.org/10.52202/079017-4156\">10.52202/079017-4156</a>.","apa":"Beaglehole, D., Súkeník, P., Mondelli, M., &#38; Belkin, M. (2024). Average gradient outer product as a mechanism for deep neural collapse. In <i>38th Annual Conference on Neural Information Processing Systems</i> (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/079017-4156\">https://doi.org/10.52202/079017-4156</a>"},"day":"01","oa_version":"Published Version","publication_identifier":{"eissn":["1049-5258"]}},{"abstract":[{"lang":"eng","text":"We propose a novel approach to concentration for non-independent random variables. The main idea is to “pretend” that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper bounded leveraging tensorisation properties. Our bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid’s inequality) when the random variables are independent. Furthermore, in a “large deviations” regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies. To show this, we consider a number of applications of interest. First, we provide a bound for Markov chains with finite state space. Then, we consider the Simple Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting in which the stochastic process depends on its entire past. To conclude, we propose an application to Markov Chain Monte Carlo methods, where our approach leads to an improved lower bound on the minimum burn-in period required to reach a certain accuracy. In all of these settings, we provide a regime of parameters in which our bound fares better than what the state of the art can provide."}],"title":"Concentration without independence via information measures","supplementarymaterial":"yes","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"14922"}]},"das_tickbox":"0","article_processing_charge":"No","volume":70,"citation":{"ista":"Esposito AR, Mondelli M. 2024. Concentration without independence via information measures. IEEE Transactions on Information Theory. 70(6), 3823–3839.","ama":"Esposito AR, Mondelli M. Concentration without independence via information measures. <i>IEEE Transactions on Information Theory</i>. 2024;70(6):3823-3839. doi:<a href=\"https://doi.org/10.1109/TIT.2024.3367767\">10.1109/TIT.2024.3367767</a>","ieee":"A. R. Esposito and M. Mondelli, “Concentration without independence via information measures,” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 6. IEEE, pp. 3823–3839, 2024.","chicago":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/TIT.2024.3367767\">https://doi.org/10.1109/TIT.2024.3367767</a>.","short":"A.R. Esposito, M. Mondelli, IEEE Transactions on Information Theory 70 (2024) 3823–3839.","mla":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 6, IEEE, 2024, pp. 3823–39, doi:<a href=\"https://doi.org/10.1109/TIT.2024.3367767\">10.1109/TIT.2024.3367767</a>.","apa":"Esposito, A. R., &#38; Mondelli, M. (2024). Concentration without independence via information measures. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2024.3367767\">https://doi.org/10.1109/TIT.2024.3367767</a>"},"language":[{"iso":"eng"}],"day":"01","publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"oa_version":"Preprint","department":[{"_id":"MaMo"}],"corr_author":"1","intvolume":"        70","external_id":{"arxiv":["2303.07245"],"isi":["001230181100001"]},"quality_controlled":"1","doi":"10.1109/TIT.2024.3367767","date_updated":"2026-10-16T10:39:43Z","author":[{"last_name":"Esposito","full_name":"Esposito, Amedeo Roberto","id":"9583e921-e1ad-11ec-9862-cef099626dc9","first_name":"Amedeo Roberto"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli"}],"date_created":"2024-03-24T23:01:00Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2303.07245","open_access":"1"}],"status":"public","publisher":"IEEE","researchdata_availability":"no","article_type":"original","scopus_import":"1","month":"06","isi":1,"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"issue":"6","_id":"15172","year":"2024","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1109/TIT.2024.3367767","oa":1,"publication":"IEEE Transactions on Information Theory","arxiv":1,"publication_status":"published","date_published":"2024-06-01T00:00:00Z","page":"3823-3839","type":"journal_article"},{"citation":{"short":"L. Jin, A.R. Esposito, M. Gastpar, in:, Proceedings of the 2024 IEEE International Symposium on Information Theory, IEEE, 2024, pp. 3178–3183.","mla":"Jin, Lifu, et al. “Properties of the Strong Data Processing Constant for Rényi Divergence.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, IEEE, 2024, pp. 3178–83, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">10.1109/ISIT57864.2024.10619367</a>.","apa":"Jin, L., Esposito, A. R., &#38; Gastpar, M. (2024). Properties of the strong data processing constant for Rényi divergence. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i> (pp. 3178–3183). Athens, Greece: IEEE. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">https://doi.org/10.1109/ISIT57864.2024.10619367</a>","ama":"Jin L, Esposito AR, Gastpar M. Properties of the strong data processing constant for Rényi divergence. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>. IEEE; 2024:3178-3183. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">10.1109/ISIT57864.2024.10619367</a>","ieee":"L. Jin, A. R. Esposito, and M. Gastpar, “Properties of the strong data processing constant for Rényi divergence,” in <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, Athens, Greece, 2024, pp. 3178–3183.","chicago":"Jin, Lifu, Amedeo Roberto Esposito, and Michael Gastpar. “Properties of the Strong Data Processing Constant for Rényi Divergence.” In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory</i>, 3178–83. IEEE, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619367\">https://doi.org/10.1109/ISIT57864.2024.10619367</a>.","ista":"Jin L, Esposito AR, Gastpar M. 2024. Properties of the strong data processing constant for Rényi divergence. Proceedings of the 2024 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 3178–3183."},"language":[{"iso":"eng"}],"conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2024-07-12","location":"Athens, Greece","start_date":"2024-07-07"},"oa_version":"Preprint","publication_identifier":{"issn":["2157-8095"],"isbn":["9798350382846"]},"day":"19","title":"Properties of the strong data processing constant for Rényi divergence","abstract":[{"text":"Strong data processing inequalities (SDPI) are an important object of study in Information Theory and have been well studied for f -divergences. Universal upper and lower bounds have been provided along with several applications, connecting them to impossibility (converse) results, concentration of measure, hypercontractivity, and so on. In this paper, we study Renyi divergence and the corresponding SDPI constant whose behavior seems to deviate from that of ordinary <1>-divergences. In particular, one can find examples showing that the universal upper bound relating its SDPI constant to the one of Total Variation does not hold in general. In this work, we prove, however, that the universal lower bound involving the SDPI constant of the Chi-square divergence does indeed hold. Furthermore, we also provide a characterization of the distribution that achieves the supremum when is equal to 2 and consequently compute the SDPI constant for Renyi divergence of the general binary channel.","lang":"eng"}],"acknowledgement":"The work in this paper was supported in part by the Swiss National Science Foundation under Grant 200364.\r\n","supplementarymaterial":"no","das_tickbox":"0","article_processing_charge":"No","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2403.10656 ","open_access":"1"}],"status":"public","publisher":"IEEE","researchdata_availability":"no","corr_author":"1","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT57864.2024.10619367","quality_controlled":"1","external_id":{"isi":["001304426903055"],"arxiv":["2403.10656"]},"date_updated":"2026-10-16T10:38:29Z","date_created":"2024-09-08T22:01:12Z","author":[{"first_name":"Lifu","full_name":"Jin, Lifu","last_name":"Jin"},{"full_name":"Esposito, Amedeo Roberto","last_name":"Esposito","id":"9583e921-e1ad-11ec-9862-cef099626dc9","first_name":"Amedeo Roberto"},{"full_name":"Gastpar, Michael","last_name":"Gastpar","first_name":"Michael"}],"_id":"17893","year":"2024","scopus_import":"1","month":"08","isi":1,"arxiv":1,"publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory","date_published":"2024-08-19T00:00:00Z","publication_status":"published","type":"conference","page":"3178-3183","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1109/ISIT57864.2024.10619367","oa":1},{"oa":1,"fulldoi":"https://doi.org/10.1109/TIT.2023.3334032","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2024-02-01T00:00:00Z","publication_status":"published","type":"journal_article","page":"1008-1039","arxiv":1,"publication":"IEEE Transactions on Information Theory","scopus_import":"1","article_type":"original","month":"02","isi":1,"year":"2024","issue":"2","_id":"14665","date_created":"2023-12-10T23:01:00Z","date_updated":"2026-10-16T10:39:20Z","author":[{"first_name":"Yihan","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","orcid":"0000-0002-6465-6258"},{"full_name":"Vatedka, Shashank","last_name":"Vatedka","first_name":"Shashank"}],"intvolume":"        70","corr_author":"1","department":[{"_id":"MaMo"}],"quality_controlled":"1","doi":"10.1109/TIT.2023.3334032","external_id":{"isi":["001166812100008"],"arxiv":["2211.04408"]},"publisher":"IEEE","researchdata_availability":"no","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2211.04408"}],"status":"public","das_tickbox":"0","article_processing_charge":"No","title":"Multiple packing: Lower bounds via error exponents","abstract":[{"lang":"eng","text":"We derive lower bounds on the maximal rates for multiple packings in high-dimensional Euclidean spaces. For any N > 0 and L ∈ Z ≥2 , a multiple packing is a set C of points in R n such that any point in R n lies in the intersection of at most L - 1 balls of radius √ nN around points in C . This is a natural generalization of the sphere packing problem. We study the multiple packing problem for both bounded point sets whose points have norm at most √ nP for some constant P > 0, and unbounded point sets whose points are allowed to be anywhere in R n . Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied over finite fields. We derive the best known lower bounds on the optimal multiple packing density. This is accomplished by establishing an inequality which relates the list-decoding error exponent for additive white Gaussian noise channels, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We also derive novel bounds on the list-decoding error exponent for infinite constellations and closed-form expressions for the list-decoding error exponents for the power-constrained AWGN channel, which may be of independent interest beyond multiple packing."}],"acknowledgement":"The work of Yihan Zhang was supported by the European Union’s Horizon 2020 Research and Innovation Programme under Grant 682203-ERC-[Inf-Speed-Tradeoff]. The work of Shashank Vatedka was supported in part by the Core Research Grant from the Science and\r\nEngineering Research Board, India, under Grant CRG/2022/004464; and in\r\npart by the Department of Science and Technology (DST), India, under Grant\r\nDST/INT/RUS/RSF/P-41/2020 (TPN No. 65025).","supplementarymaterial":"yes","oa_version":"Preprint","publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"day":"01","citation":{"ista":"Zhang Y, Vatedka S. 2024. Multiple packing: Lower bounds via error exponents. IEEE Transactions on Information Theory. 70(2), 1008–1039.","apa":"Zhang, Y., &#38; Vatedka, S. (2024). Multiple packing: Lower bounds via error exponents. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2023.3334032\">https://doi.org/10.1109/TIT.2023.3334032</a>","short":"Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 70 (2024) 1008–1039.","mla":"Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Error Exponents.” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 2, IEEE, 2024, pp. 1008–39, doi:<a href=\"https://doi.org/10.1109/TIT.2023.3334032\">10.1109/TIT.2023.3334032</a>.","chicago":"Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Error Exponents.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/TIT.2023.3334032\">https://doi.org/10.1109/TIT.2023.3334032</a>.","ieee":"Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via error exponents,” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 2. IEEE, pp. 1008–1039, 2024.","ama":"Zhang Y, Vatedka S. Multiple packing: Lower bounds via error exponents. <i>IEEE Transactions on Information Theory</i>. 2024;70(2):1008-1039. doi:<a href=\"https://doi.org/10.1109/TIT.2023.3334032\">10.1109/TIT.2023.3334032</a>"},"volume":70,"language":[{"iso":"eng"}]},{"supplementarymaterial":"no","acknowledgement":"The work of M. Langberg and A. D. Sarwate was supported in part by the US NSF under awards CCF-1909451 and CCF1909468. B. K. Dey was supported in part by the Bharti Centre\r\nfor Communication in IIT Bombay. ","abstract":[{"text":"We propose a concatenated code construction for a class of discrete-alphabet oblivious arbitrarily varying channels (AVCs) with cost constraints. The code has time and space complexity polynomial in the blocklength n . It uses a Reed-Solomon outer code, logarithmic blocklength random inner codes, and stochastic encoding by permuting the codeword before transmission. When the channel satisfies a condition called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability originally due to Dobrushin and Stambler), we show that the code achieves a rate that for a variety of oblivious AVCs (such as classically studied error/erasure channels) match the known capacities.","lang":"eng"}],"title":"Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs","article_processing_charge":"No","das_tickbox":"0","conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2024-07-12","start_date":"2024-07-07","location":"Athens, Greece"},"language":[{"iso":"eng"}],"citation":{"ama":"Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>. IEEE; 2024:1586-1591. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">10.1109/ISIT57864.2024.10619362</a>","chicago":"Dey, B. K., S. Jaggi, M. Langberg, A. D. Sarwate, and Yihan Zhang. “Computationally Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.” In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, 1586–91. IEEE, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">https://doi.org/10.1109/ISIT57864.2024.10619362</a>.","ieee":"B. K. Dey, S. Jaggi, M. Langberg, A. D. Sarwate, and Y. Zhang, “Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs,” in <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Athens, Greece, 2024, pp. 1586–1591.","short":"B.K. Dey, S. Jaggi, M. Langberg, A.D. Sarwate, Y. Zhang, in:, Proceedings of the 2024 IEEE International Symposium on Information Theory , IEEE, 2024, pp. 1586–1591.","mla":"Dey, B. K., et al. “Computationally Efficient Codes for Strongly Dobrushin-Stambler Nonsymmetrizable Oblivious AVCs.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, IEEE, 2024, pp. 1586–91, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">10.1109/ISIT57864.2024.10619362</a>.","apa":"Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., &#38; Zhang, Y. (2024). Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i> (pp. 1586–1591). Athens, Greece: IEEE. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619362\">https://doi.org/10.1109/ISIT57864.2024.10619362</a>","ista":"Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Computationally efficient codes for strongly Dobrushin-Stambler nonsymmetrizable oblivious AVCs. Proceedings of the 2024 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 1586–1591."},"day":"19","publication_identifier":{"issn":["2157-8095"],"isbn":["9798350382846"]},"oa_version":"None","external_id":{"isi":["001304426901091"]},"doi":"10.1109/ISIT57864.2024.10619362","quality_controlled":"1","department":[{"_id":"MaMo"}],"date_created":"2024-09-08T22:01:12Z","author":[{"first_name":"B. K.","last_name":"Dey","full_name":"Dey, B. K."},{"first_name":"S.","last_name":"Jaggi","full_name":"Jaggi, S."},{"last_name":"Langberg","full_name":"Langberg, M.","first_name":"M."},{"last_name":"Sarwate","full_name":"Sarwate, A. D.","first_name":"A. D."},{"orcid":"0000-0002-6465-6258","first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang","full_name":"Zhang, Yihan"}],"date_updated":"2026-10-16T10:39:03Z","status":"public","researchdata_availability":"no","publisher":"IEEE","isi":1,"month":"08","scopus_import":"1","_id":"17895","year":"2024","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1109/ISIT57864.2024.10619362","publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory ","page":"1586-1591","type":"conference","publication_status":"published","date_published":"2024-08-19T00:00:00Z"},{"_id":"17894","year":"2024","isi":1,"month":"08","scopus_import":"1","publication":"Proceedings of the 2024 IEEE International Symposium on Information Theory ","type":"conference","page":"2110-2115","date_published":"2024-08-19T00:00:00Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1109/ISIT57864.2024.10619378","language":[{"iso":"eng"}],"conference":{"end_date":"2024-07-12","name":"ISIT: International Symposium on Information Theory","location":"Athens, Greece","start_date":"2024-07-07"},"citation":{"apa":"Esposito, A. R., Gastpar, M., &#38; Issa, I. (2024). Variational characterizations of Sibson’s α-mutual information. In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i> (pp. 2110–2115). Athens, Greece: IEEE. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">https://doi.org/10.1109/ISIT57864.2024.10619378</a>","short":"A.R. Esposito, M. Gastpar, I. Issa, in:, Proceedings of the 2024 IEEE International Symposium on Information Theory , IEEE, 2024, pp. 2110–2115.","mla":"Esposito, Amedeo Roberto, et al. “Variational Characterizations of Sibson’s α-Mutual Information.” <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, IEEE, 2024, pp. 2110–15, doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">10.1109/ISIT57864.2024.10619378</a>.","ieee":"A. R. Esposito, M. Gastpar, and I. Issa, “Variational characterizations of Sibson’s α-mutual information,” in <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, Athens, Greece, 2024, pp. 2110–2115.","chicago":"Esposito, Amedeo Roberto, Michael Gastpar, and Ibrahim Issa. “Variational Characterizations of Sibson’s α-Mutual Information.” In <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>, 2110–15. IEEE, 2024. <a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">https://doi.org/10.1109/ISIT57864.2024.10619378</a>.","ama":"Esposito AR, Gastpar M, Issa I. Variational characterizations of Sibson’s α-mutual information. In: <i>Proceedings of the 2024 IEEE International Symposium on Information Theory </i>. IEEE; 2024:2110-2115. doi:<a href=\"https://doi.org/10.1109/ISIT57864.2024.10619378\">10.1109/ISIT57864.2024.10619378</a>","ista":"Esposito AR, Gastpar M, Issa I. 2024. Variational characterizations of Sibson’s α-mutual information. Proceedings of the 2024 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory, 2110–2115."},"oa_version":"None","publication_identifier":{"isbn":["9798350382846"],"issn":["2157-8095"]},"day":"19","acknowledgement":"The work in this paper was supported in part by the Swiss National Science Foundation under Grant 200364.","supplementarymaterial":"no","title":"Variational characterizations of Sibson's α-mutual information","abstract":[{"text":"Sibson's α -mutual information has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this work, we introduce several variational representations of Sibson's α -mutual information: 1) as a supremum over joint distributions of (a combination of) KL divergences; and 2) as a supremum over functions of opportune expected values. Leveraging them, we produce a variety of novel and known results, including a generalization of transportation-cost inequalities and Fano's inequality.","lang":"eng"}],"article_processing_charge":"No","das_tickbox":"0","status":"public","publisher":"IEEE","researchdata_availability":"no","quality_controlled":"1","doi":"10.1109/ISIT57864.2024.10619378","external_id":{"isi":["001304426902023"]},"department":[{"_id":"MaMo"}],"corr_author":"1","author":[{"first_name":"Amedeo Roberto","id":"9583e921-e1ad-11ec-9862-cef099626dc9","last_name":"Esposito","full_name":"Esposito, Amedeo Roberto"},{"last_name":"Gastpar","full_name":"Gastpar, Michael","first_name":"Michael"},{"last_name":"Issa","full_name":"Issa, Ibrahim","first_name":"Ibrahim"}],"date_updated":"2026-10-16T10:38:46Z","date_created":"2024-09-08T22:01:12Z"},{"type":"conference","page":"13151-13155","date_published":"2024-04-19T00:00:00Z","publication_status":"published","publication":"2024 IEEE International Conference on Acoustics, Speech, and Signal Processing","fulldoi":"https://doi.org/10.1109/ICASSP48485.2024.10447198","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2024","_id":"17147","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"},{"_id":"9B8D11D6-BA93-11EA-9121-9846C619BF3A","name":"Improving estimation and prediction of common complex disease risk","grant_number":"PCEGP3_181181"}],"month":"04","isi":1,"scopus_import":"1","researchdata_availability":"no","publisher":"IEEE","status":"public","main_file_link":[{"url":"https://openreview.net/forum?id=aQYCDxfZV0","open_access":"1"}],"date_created":"2024-06-16T22:01:07Z","author":[{"first_name":"Al","last_name":"Depope","full_name":"Depope, Al","id":"0b77531d-dbcd-11ea-9d1d-a8eee0bf3830"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli"},{"full_name":"Robinson, Matthew Richard","id":"E5D42276-F5DA-11E9-8E24-6303E6697425","last_name":"Robinson","first_name":"Matthew Richard","orcid":"0000-0001-8982-8813"}],"date_updated":"2026-10-16T10:42:55Z","doi":"10.1109/ICASSP48485.2024.10447198","quality_controlled":"1","acknowledged_ssus":[{"_id":"ScienComp"}],"external_id":{"isi":["001396233806078"]},"OA_place":"repository","corr_author":"1","department":[{"_id":"MaMo"},{"_id":"MaRo"}],"oa_version":"Submitted Version","publication_identifier":{"issn":["1520-6149"],"isbn":["9798350344851"]},"day":"19","language":[{"iso":"eng"}],"conference":{"location":"Seoul, Korea","start_date":"2024-04-14","name":"ICASSP: International Conference on Acoustics, Speech and Signal Processing","end_date":"2024-04-19"},"citation":{"mla":"Depope, Al, et al. “Inference of Genetic Effects via Approximate Message Passing.” <i>2024 IEEE International Conference on Acoustics, Speech, and Signal Processing</i>, IEEE, 2024, pp. 13151–55, doi:<a href=\"https://doi.org/10.1109/ICASSP48485.2024.10447198\">10.1109/ICASSP48485.2024.10447198</a>.","short":"A. Depope, M. Mondelli, M.R. Robinson, in:, 2024 IEEE International Conference on Acoustics, Speech, and Signal Processing, IEEE, 2024, pp. 13151–13155.","apa":"Depope, A., Mondelli, M., &#38; Robinson, M. R. (2024). Inference of genetic effects via approximate message passing. In <i>2024 IEEE International Conference on Acoustics, Speech, and Signal Processing</i> (pp. 13151–13155). Seoul, Korea: IEEE. <a href=\"https://doi.org/10.1109/ICASSP48485.2024.10447198\">https://doi.org/10.1109/ICASSP48485.2024.10447198</a>","ama":"Depope A, Mondelli M, Robinson MR. Inference of genetic effects via approximate message passing. In: <i>2024 IEEE International Conference on Acoustics, Speech, and Signal Processing</i>. IEEE; 2024:13151-13155. doi:<a href=\"https://doi.org/10.1109/ICASSP48485.2024.10447198\">10.1109/ICASSP48485.2024.10447198</a>","ieee":"A. Depope, M. Mondelli, and M. R. Robinson, “Inference of genetic effects via approximate message passing,” in <i>2024 IEEE International Conference on Acoustics, Speech, and Signal Processing</i>, Seoul, Korea, 2024, pp. 13151–13155.","chicago":"Depope, Al, Marco Mondelli, and Matthew Richard Robinson. “Inference of Genetic Effects via Approximate Message Passing.” In <i>2024 IEEE International Conference on Acoustics, Speech, and Signal Processing</i>, 13151–55. IEEE, 2024. <a href=\"https://doi.org/10.1109/ICASSP48485.2024.10447198\">https://doi.org/10.1109/ICASSP48485.2024.10447198</a>.","ista":"Depope A, Mondelli M, Robinson MR. 2024. Inference of genetic effects via approximate message passing. 2024 IEEE International Conference on Acoustics, Speech, and Signal Processing. ICASSP: International Conference on Acoustics, Speech and Signal Processing, 13151–13155."},"article_processing_charge":"No","das_tickbox":"0","OA_type":"green","acknowledgement":"This work was supported by a Lopez-Loreta Prize to MM, an SNSF Eccellenza Grant to MRR (PCEGP3-181181), and core funding from ISTA. The authors thank Philip Schniter, Matthew Stephens and Pragya Sur for valuable suggestions on an early version of the work. The authors acknowledge the participants and investigators of the UK Biobank study. High-performance\r\ncomputing was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing (SciComp).","supplementarymaterial":"no","title":"Inference of genetic effects via approximate message passing","abstract":[{"lang":"eng","text":"Efficient utilization of large-scale biobank data is crucial for inferring the genetic basis of disease and predicting health outcomes from the DNA. Yet we lack efficient, accurate methods that scale to data where electronic health records are linked to whole genome sequence information. To address this issue, our paper develops a new algorithmic paradigm based on Approximate Message Passing (AMP), which is specifically tailored for genomic prediction and association testing. Our method yields comparable out-of-sample prediction accuracy to the state of the art on UK Biobank traits, whilst dramatically improving computational complexity, with a 8x-speed up in the run time. In addition, AMP theory provides a joint association testing framework, which outperforms the currently used REGENIE method, in roughly a third of the compute time. This first, truly large-scale application of the AMP framework lays the foundations for a far wider range of statistical analyses for hundreds of millions of variables measured on millions of people."}]},{"_id":"18973","year":"2024","scopus_import":"1","month":"07","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"publication":"41st International Conference on Machine Learning","arxiv":1,"publication_status":"published","date_published":"2024-07-30T00:00:00Z","page":"4300-4328","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"volume":235,"citation":{"apa":"Bombari, S., &#38; Mondelli, M. (2024). Towards understanding the word sensitivity of attention layers: A study via random features. In <i>41st International Conference on Machine Learning</i> (Vol. 235, pp. 4300–4328). Vienna, Austria: ML Research Press.","mla":"Bombari, Simone, and Marco Mondelli. “Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Features.” <i>41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 4300–28.","short":"S. Bombari, M. Mondelli, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 4300–4328.","chicago":"Bombari, Simone, and Marco Mondelli. “Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Features.” In <i>41st International Conference on Machine Learning</i>, 235:4300–4328. ML Research Press, 2024.","ieee":"S. Bombari and M. Mondelli, “Towards understanding the word sensitivity of attention layers: A study via random features,” in <i>41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 4300–4328.","ama":"Bombari S, Mondelli M. Towards understanding the word sensitivity of attention layers: A study via random features. In: <i>41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:4300-4328.","ista":"Bombari S, Mondelli M. 2024. Towards understanding the word sensitivity of attention layers: A study via random features. 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 4300–4328."},"conference":{"end_date":"2024-07-27","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21","location":"Vienna, Austria"},"alternative_title":["PMLR"],"language":[{"iso":"eng"}],"day":"30","publication_identifier":{"eissn":["2640-3498"]},"oa_version":"Preprint","abstract":[{"text":"Understanding the reasons behind the exceptional success of transformers requires a better analysis of why attention layers are suitable for NLP tasks. In particular, such tasks require predictive models to capture contextual meaning which often depends on one or few words, even if the sentence is long. Our work studies this key property, dubbed word sensitivity (WS), in the prototypical setting of random features. We show that attention layers enjoy high WS, namely, there exists a vector in the space of embeddings that largely perturbs the random attention features map. The argument critically exploits the role of the softmax in the attention layer, highlighting its benefit compared to other activations (e.g., ReLU). In contrast, the WS of standard random features is of order 1/n−−√, n being the number of words in the textual sample, and thus it decays with the length of the context. We then translate these results on the word sensitivity into generalization bounds: due to their low WS, random features provably cannot learn to distinguish between two sentences that differ only in a single word; in contrast, due to their high WS, random attention features have higher generalization capabilities. We validate our theoretical results with experimental evidence over the BERT-Base word embeddings of the imdb review dataset.","lang":"eng"}],"title":"Towards understanding the word sensitivity of attention layers: A study via random features","supplementarymaterial":"no","acknowledgement":"The authors were partially supported by the 2019 LopezLoreta prize, and they would like to thank Mohammad Hossein Amani, Lorenzo Beretta, and Clement Rebuffel for helpful discussions.","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"22857"}]},"OA_type":"green","das_tickbox":"0","article_processing_charge":"No","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2402.02969","open_access":"1"}],"status":"public","publisher":"ML Research Press","researchdata_availability":"no","corr_author":"1","department":[{"_id":"MaMo"}],"intvolume":"       235","OA_place":"repository","external_id":{"arxiv":["2402.02969"]},"quality_controlled":"1","date_updated":"2026-10-16T10:42:17Z","author":[{"id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","last_name":"Bombari","first_name":"Simone"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","full_name":"Mondelli, Marco"}],"date_created":"2025-01-30T07:35:49Z"},{"arxiv":1,"publication":"41st International Conference on Machine Learning","type":"conference","page":"4267-4299","date_published":"2024-07-30T00:00:00Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"_id":"18972","year":"2024","month":"07","scopus_import":"1","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2305.12100","open_access":"1"}],"researchdata_availability":"no","publisher":"ML Research Press","quality_controlled":"1","external_id":{"arxiv":["2305.12100"]},"intvolume":"       235","OA_place":"repository","department":[{"_id":"MaMo"}],"corr_author":"1","date_updated":"2026-10-16T10:42:37Z","date_created":"2025-01-30T07:29:47Z","author":[{"first_name":"Simone","id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","last_name":"Bombari"},{"first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020"}],"language":[{"iso":"eng"}],"alternative_title":["PMLR"],"conference":{"location":"Vienna, Austria","start_date":"2024-07-21","name":"ICML: International Conference on Machine Learning","end_date":"2024-07-27"},"citation":{"ista":"Bombari S, Mondelli M. 2024. How spurious features are memorized: Precise analysis for random and NTK features. 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 4267–4299.","short":"S. Bombari, M. Mondelli, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 4267–4299.","mla":"Bombari, Simone, and Marco Mondelli. “How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features.” <i>41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 4267–99.","apa":"Bombari, S., &#38; Mondelli, M. (2024). How spurious features are memorized: Precise analysis for random and NTK features. In <i>41st International Conference on Machine Learning</i> (Vol. 235, pp. 4267–4299). Vienna, Austria: ML Research Press.","ama":"Bombari S, Mondelli M. How spurious features are memorized: Precise analysis for random and NTK features. In: <i>41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:4267-4299.","chicago":"Bombari, Simone, and Marco Mondelli. “How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features.” In <i>41st International Conference on Machine Learning</i>, 235:4267–99. ML Research Press, 2024.","ieee":"S. Bombari and M. Mondelli, “How spurious features are memorized: Precise analysis for random and NTK features,” in <i>41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 4267–4299."},"volume":235,"publication_identifier":{"eissn":["2640-3498"]},"oa_version":"Preprint","day":"30","OA_type":"green","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"22857"}]},"acknowledgement":"The authors were partially supported by the 2019 LopezLoreta prize, and they would like to thank (in alphabetical order) Grigorios Chrysos, Simone Maria Giancola, Mahyar\r\nJafari Nodeh, Christoph Lampert, Marco Miani, GuanWen Qiu, and Peter Sukenık for helpful discussions.","supplementarymaterial":"yes","title":"How spurious features are memorized: Precise analysis for random and NTK features","abstract":[{"text":"Deep learning models are known to overfit and memorize spurious features in the training dataset. While numerous empirical studies have aimed at understanding this phenomenon, a rigorous theoretical framework to quantify it is still missing. In this paper, we consider spurious features that are uncorrelated with the learning task, and we provide a precise characterization of how they are memorized via two separate terms: (i) the stability of the model with respect to individual training samples, and (ii) the feature alignment between the spurious pattern and the full sample. While the first term is well established in learning theory and it is connected to the generalization error in classical work, the second one is, to the best of our knowledge, novel. Our key technical result gives a precise characterization of the feature alignment for the two prototypical settings of random features (RF) and neural tangent kernel (NTK) regression. We prove that the memorization of spurious features weakens as the generalization capability increases and, through the analysis of the feature alignment, we unveil the role of the model and of its activation function. Numerical experiments show the predictive power of our theory on standard datasets (MNIST, CIFAR-10).","lang":"eng"}],"article_processing_charge":"No","das_tickbox":"0"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1109/TIT.2024.3430842","oa":1,"arxiv":1,"publication":"IEEE Transactions on Information Theory","type":"journal_article","page":"6211-6238","date_published":"2024-09-01T00:00:00Z","publication_status":"published","month":"09","isi":1,"article_type":"original","scopus_import":"1","_id":"17330","issue":"9","year":"2024","doi":"10.1109/TIT.2024.3430842","quality_controlled":"1","external_id":{"arxiv":["2210.07754"],"isi":["001299623600019"]},"OA_place":"repository","intvolume":"        70","corr_author":"1","department":[{"_id":"MaMo"}],"date_updated":"2026-10-16T10:41:59Z","author":[{"last_name":"Resch","full_name":"Resch, Nicolas","first_name":"Nicolas"},{"first_name":"Chen","full_name":"Yuan, Chen","last_name":"Yuan"},{"last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","first_name":"Yihan","orcid":"0000-0002-6465-6258"}],"date_created":"2024-07-28T22:01:10Z","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/2210.07754","open_access":"1"}],"publisher":"IEEE","researchdata_availability":"no","OA_type":"green","related_material":{"record":[{"status":"public","id":"14083","relation":"earlier_version"}]},"acknowledgement":"Part of this work was done while Nicolas Resch was affiliated with the Centrum Wiskunde & Informatica and supported in part by ERC H2020 grant No.74079 (ALGSTRONGCRYPTO). Chen Yuan is supported in part by the National Key Research and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.","supplementarymaterial":"no","title":"Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery","abstract":[{"lang":"eng","text":"In this work we consider the list-decodability and list-recoverability of arbitrary q -ary codes, for all integer values of q ⩾ 2. A code is called ( p , L ) q -list-decodable if every radius pn Hamming ball contains less than L codewords; ( p , ℓ, L ) q -recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length ℓ and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate ( p , ℓ, L ) q -list-recoverable codes, the quantity we call the zero-rate threshold . Denoting this value by p *, we in fact show that codes correcting a p * + ε fraction of errors must have size O ε (1), i.e., independent of n . Such a result is typically referred to as a “Plotkin bound.” To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p * − ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demon-strating the Schur convexity of a certain function defined on the q -simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q -ary list-decoding; however, we point out that this earlier proof is flawed."}],"article_processing_charge":"No","das_tickbox":"0","language":[{"iso":"eng"}],"citation":{"ista":"Resch N, Yuan C, Zhang Y. 2024. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. IEEE Transactions on Information Theory. 70(9), 6211–6238.","ama":"Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. <i>IEEE Transactions on Information Theory</i>. 2024;70(9):6211-6238. doi:<a href=\"https://doi.org/10.1109/TIT.2024.3430842\">10.1109/TIT.2024.3430842</a>","chicago":"Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/TIT.2024.3430842\">https://doi.org/10.1109/TIT.2024.3430842</a>.","ieee":"N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery,” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 9. IEEE, pp. 6211–6238, 2024.","short":"N. Resch, C. Yuan, Y. Zhang, IEEE Transactions on Information Theory 70 (2024) 6211–6238.","mla":"Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” <i>IEEE Transactions on Information Theory</i>, vol. 70, no. 9, IEEE, 2024, pp. 6211–38, doi:<a href=\"https://doi.org/10.1109/TIT.2024.3430842\">10.1109/TIT.2024.3430842</a>.","apa":"Resch, N., Yuan, C., &#38; Zhang, Y. (2024). Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2024.3430842\">https://doi.org/10.1109/TIT.2024.3430842</a>"},"volume":70,"oa_version":"Preprint","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"day":"01"},{"corr_author":"1","department":[{"_id":"MaMo"}],"intvolume":"        21","quality_controlled":"1","doi":"10.1561/0100000112","date_updated":"2026-10-16T10:40:55Z","date_created":"2024-12-15T23:01:50Z","author":[{"full_name":"Dey, Bikash Kumar","last_name":"Dey","first_name":"Bikash Kumar"},{"last_name":"Jaggi","full_name":"Jaggi, Sidharth","first_name":"Sidharth"},{"first_name":"Michael","last_name":"Langberg","full_name":"Langberg, Michael"},{"first_name":"Anand D.","full_name":"Sarwate, Anand D.","last_name":"Sarwate"},{"full_name":"Zhang, Yihan","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","first_name":"Yihan","orcid":"0000-0002-6465-6258"}],"status":"public","publisher":"Now Publishers","researchdata_availability":"unclear","abstract":[{"text":"Over the last 70 years, information theory and coding has enabled communication technologies that have had an astounding impact on our lives. This is possible due to the match between encoding/decoding strategies and corresponding channel models. Traditional studies of channels have taken one of two extremes: Shannon-theoretic models are inherently average-case in which channel noise is governed by a memoryless stochastic process, whereas coding-theoretic (referred to as “Hamming”) models take a worst-case, adversarial, view of the noise. However, for several existing and emerging communication systems the Shannon/average-case view may be too optimistic, whereas the Hamming/worstcase view may be too pessimistic. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes.","lang":"eng"}],"title":"Codes for adversaries: Between worst-case and average-case jamming","supplementarymaterial":"unclear","OA_type":"closed access","article_processing_charge":"No","volume":21,"citation":{"mla":"Dey, Bikash Kumar, et al. “Codes for Adversaries: Between Worst-Case and Average-Case Jamming.” <i>Foundations and Trends in Communications and Information Theory</i>, vol. 21, no. 3–4, Now Publishers, 2024, pp. 300–588, doi:<a href=\"https://doi.org/10.1561/0100000112\">10.1561/0100000112</a>.","short":"B.K. Dey, S. Jaggi, M. Langberg, A.D. Sarwate, Y. Zhang, Foundations and Trends in Communications and Information Theory 21 (2024) 300–588.","apa":"Dey, B. K., Jaggi, S., Langberg, M., Sarwate, A. D., &#38; Zhang, Y. (2024). Codes for adversaries: Between worst-case and average-case jamming. <i>Foundations and Trends in Communications and Information Theory</i>. Now Publishers. <a href=\"https://doi.org/10.1561/0100000112\">https://doi.org/10.1561/0100000112</a>","ama":"Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. Codes for adversaries: Between worst-case and average-case jamming. <i>Foundations and Trends in Communications and Information Theory</i>. 2024;21(3-4):300-588. doi:<a href=\"https://doi.org/10.1561/0100000112\">10.1561/0100000112</a>","ieee":"B. K. Dey, S. Jaggi, M. Langberg, A. D. Sarwate, and Y. Zhang, “Codes for adversaries: Between worst-case and average-case jamming,” <i>Foundations and Trends in Communications and Information Theory</i>, vol. 21, no. 3–4. Now Publishers, pp. 300–588, 2024.","chicago":"Dey, Bikash Kumar, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate, and Yihan Zhang. “Codes for Adversaries: Between Worst-Case and Average-Case Jamming.” <i>Foundations and Trends in Communications and Information Theory</i>. Now Publishers, 2024. <a href=\"https://doi.org/10.1561/0100000112\">https://doi.org/10.1561/0100000112</a>.","ista":"Dey BK, Jaggi S, Langberg M, Sarwate AD, Zhang Y. 2024. Codes for adversaries: Between worst-case and average-case jamming. Foundations and Trends in Communications and Information Theory. 21(3–4), 300–588."},"language":[{"iso":"eng"}],"day":"03","publication_identifier":{"issn":["1567-2190"],"eissn":["1567-2328"]},"oa_version":"None","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.1561/0100000112","publication":"Foundations and Trends in Communications and Information Theory","publication_status":"published","date_published":"2024-12-03T00:00:00Z","page":"300-588","type":"journal_article","article_type":"original","scopus_import":"1","month":"12","issue":"3-4","_id":"18652","year":"2024"},{"alternative_title":["ISTA Thesis"],"language":[{"iso":"eng"}],"file_date_updated":"2024-10-05T22:30:05Z","citation":{"ama":"Shevchenko A. High-dimensional limits in artificial neural networks. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:17465\">10.15479/at:ista:17465</a>","chicago":"Shevchenko, Alexander. “High-Dimensional Limits in Artificial Neural Networks.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:17465\">https://doi.org/10.15479/at:ista:17465</a>.","ieee":"A. Shevchenko, “High-dimensional limits in artificial neural networks,” Institute of Science and Technology Austria, 2024.","short":"A. Shevchenko, High-Dimensional Limits in Artificial Neural Networks, Institute of Science and Technology Austria, 2024.","mla":"Shevchenko, Alexander. <i>High-Dimensional Limits in Artificial Neural Networks</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:17465\">10.15479/at:ista:17465</a>.","apa":"Shevchenko, A. (2024). <i>High-dimensional limits in artificial neural networks</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:17465\">https://doi.org/10.15479/at:ista:17465</a>","ista":"Shevchenko A. 2024. High-dimensional limits in artificial neural networks. Institute of Science and Technology Austria."},"day":"29","oa_version":"Published Version","publication_identifier":{"issn":["2663-337X"]},"supplementarymaterial":"no","related_material":{"record":[{"relation":"part_of_dissertation","id":"11420","status":"public"},{"id":"14459","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"9198"},{"relation":"part_of_dissertation","status":"public","id":"17469"}]},"file":[{"checksum":"da6dd3166078934577f6af93d27000e2","file_id":"17482","content_type":"application/pdf","file_size":4468610,"relation":"main_file","date_updated":"2024-10-05T22:30:05Z","embargo":"2024-10-04","file_name":"thesis_a2b.pdf","date_created":"2024-09-02T09:23:32Z","creator":"ashevche","access_level":"open_access"},{"file_size":15930999,"relation":"source_file","access_level":"closed","file_name":"Thesis Alex - ISTA.zip","date_updated":"2024-10-05T22:30:05Z","date_created":"2024-09-02T09:23:46Z","creator":"ashevche","file_id":"17483","checksum":"76a39ef252239560923cdda4ce0a31a4","content_type":"application/zip","embargo_to":"open_access"}],"abstract":[{"text":"In the modern age of machine learning, artificial neural networks have become an integral part\r\nof many practical systems. One of the key ingredients of the success of the deep learning\r\napproach is recent computational advances which allowed the training of models with billions\r\nof parameters on large-scale data. Such over-parameterized and data-hungry regimes pose a\r\nchallenge for the theoretical analysis of modern models since “classical” statistical wisdom\r\nis no longer applicable. In this view, it is paramount to extend or develop new machinery\r\nthat will allow tackling the neural network analysis under new challenging asymptotic regimes,\r\nwhich is the focus of this thesis.\r\nLarge neural network systems are usually optimized via “local” search algorithms, such\r\nas stochastic gradient descent (SGD). However, given the high-dimensional nature of the\r\nparameter space, it is a priori not clear why such a crude “local” approach works so remarkably\r\nwell in practice. We take a step towards demystifying this phenomenon by showing that\r\nthe landscape of the SGD training dynamics exhibits a few beneficial properties for the\r\noptimization. First, we show that along the SGD trajectory an over-parameterized network\r\nis dropout stable. The emergence of dropout stability allows to conclude that the minima\r\nfound by SGD are connected via a continuous path of small loss. This in turn means that\r\nthe high-dimensional landscape of the neural network optimization problem is provably not so\r\nunfavourable to gradient-based training, due to mode connectivity. Next, we show that SGD\r\nfor an over-parameterized network tends to find solutions that are functionally more “simple”.\r\nThis in turn means that the SGD minima are more robust, since a less complicated solution\r\nwill less likely overfit the data. More formally, for a prototypical example of a wide two-layer\r\nReLU network on a 1d regression task we show that the SGD algorithm is implicitly selective in\r\nits choice of an interpolating solution. Namely, at convergence the neural network implements\r\na piece-wise linear function with the number of linear regions depending only on the amount\r\nof training data. This is in contrast to a “smooth”-like behaviour which one would expect\r\ngiven such a severe over-parameterization of the model.\r\nDiverging from the generic supervised setting of classification and regression problems, we\r\nanalyze an auto-encoder model that is commonly used for representation learning and data\r\ncompression. Despite the wide applicability of the auto-encoding paradigm, the theoretical\r\nunderstanding of their behaviour is limited even in the simplistic shallow case. The related\r\nwork is restricted to extreme asymptotic regimes in which the auto-encoder is either severely\r\nover-parameterized or under-parameterized. In contrast, we provide a tight characterization\r\nfor the 1-bit compression of Gaussian signals in the challenging proportional regime, i.e., the\r\ninput dimension and the size of the compressed representation obey the same asymptotics.\r\nWe also show that gradient-based methods are able to find a globally optimal solution and\r\nthat the predictions made for Gaussian data extrapolate beyond - to the case of compression\r\nof natural images. Next, we relax the Gaussian assumption and study more structured input\r\nsources. We show that the shallow model is sometimes agnostic to the structure of the data\r\nvii\r\nwhich results in a Gaussian-like behaviour. We prove that making the decoding component\r\nslightly less shallow is already enough to escape the “curse” of Gaussian performance.\r\n","lang":"eng"}],"title":"High-dimensional limits in artificial neural networks","doi_confirm":"1","supervisor":[{"last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian"}],"article_processing_charge":"No","das_tickbox":"0","status":"public","researchdata_availability":"no","publisher":"Institute of Science and Technology Austria","acknowledged_ssus":[{"_id":"ScienComp"}],"doi":"10.15479/at:ista:17465","department":[{"_id":"GradSch"},{"_id":"DaAl"},{"_id":"MaMo"}],"corr_author":"1","OA_place":"repository","author":[{"last_name":"Shevchenko","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","full_name":"Shevchenko, Aleksandr","first_name":"Aleksandr"}],"date_updated":"2026-10-02T11:20:32Z","date_created":"2024-08-28T15:14:25Z","_id":"17465","year":"2024","degree_awarded":"PhD","month":"08","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"},{"grant_number":"W1260-N35","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","name":"Vienna Graduate School on Computational Optimization"}],"has_accepted_license":"1","page":"232","type":"dissertation","ddc":["519"],"publication_status":"published","date_published":"2024-08-29T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","fulldoi":"https://doi.org/10.15479/at:ista:17465","oa":1},{"publisher":"ML Research Press","researchdata_availability":"no","status":"public","main_file_link":[{"url":"https://proceedings.mlr.press/v235/kogler24a.html","open_access":"1"}],"date_updated":"2026-11-05T23:31:06Z","author":[{"first_name":"Kevin","full_name":"Kögler, Kevin","id":"94ec913c-dc85-11ea-9058-e5051ab2428b","last_name":"Kögler"},{"first_name":"Aleksandr","last_name":"Shevchenko","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","full_name":"Shevchenko, Aleksandr"},{"first_name":"Hamed","full_name":"Hassani, Hamed","last_name":"Hassani"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli"}],"date_created":"2024-08-29T11:47:57Z","quality_controlled":"1","external_id":{"arxiv":["2402.05013"]},"intvolume":"       235","department":[{"_id":"DaAl"},{"_id":"MaMo"}],"corr_author":"1","oa_version":"Published Version","day":"01","language":[{"iso":"eng"}],"conference":{"end_date":"2024-07-27","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21","location":"Vienna, Austria"},"alternative_title":["PMLR"],"citation":{"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.","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.","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.","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.","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.","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.","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."},"volume":235,"article_processing_charge":"No","das_tickbox":"0","related_material":{"record":[{"relation":"dissertation_contains","id":"23072","status":"public"},{"status":"public","id":"17465","relation":"dissertation_contains"}]},"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).","supplementarymaterial":"no","title":"Compression of structured data with autoencoders: Provable benefit of nonlinearities and depth","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."}],"ddc":["000"],"type":"conference","page":"24964-25015","date_published":"2024-07-01T00:00:00Z","publication_status":"published","arxiv":1,"publication":"Proceedings of the 41st International Conference on Machine Learning","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2024","_id":"17469","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"month":"07","scopus_import":"1"},{"_id":"12838","issue":"7","year":"2023","isi":1,"month":"07","article_type":"original","scopus_import":"1","publication":"IEEE Transactions on Information Theory","arxiv":1,"page":"4513-4527","type":"journal_article","publication_status":"published","date_published":"2023-07-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"fulldoi":"https://doi.org/10.1109/TIT.2023.3260950","language":[{"iso":"eng"}],"volume":69,"citation":{"ista":"Zhang Y, Vatedka S. 2023. Multiple packing: Lower bounds via infinite constellations. IEEE Transactions on Information Theory. 69(7), 4513–4527.","ieee":"Y. Zhang and S. Vatedka, “Multiple packing: Lower bounds via infinite constellations,” <i>IEEE Transactions on Information Theory</i>, vol. 69, no. 7. IEEE, pp. 4513–4527, 2023.","chicago":"Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2023. <a href=\"https://doi.org/10.1109/TIT.2023.3260950\">https://doi.org/10.1109/TIT.2023.3260950</a>.","ama":"Zhang Y, Vatedka S. Multiple packing: Lower bounds via infinite constellations. <i>IEEE Transactions on Information Theory</i>. 2023;69(7):4513-4527. doi:<a href=\"https://doi.org/10.1109/TIT.2023.3260950\">10.1109/TIT.2023.3260950</a>","apa":"Zhang, Y., &#38; Vatedka, S. (2023). Multiple packing: Lower bounds via infinite constellations. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2023.3260950\">https://doi.org/10.1109/TIT.2023.3260950</a>","short":"Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 69 (2023) 4513–4527.","mla":"Zhang, Yihan, and Shashank Vatedka. “Multiple Packing: Lower Bounds via Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>, vol. 69, no. 7, IEEE, 2023, pp. 4513–27, doi:<a href=\"https://doi.org/10.1109/TIT.2023.3260950\">10.1109/TIT.2023.3260950</a>."},"day":"01","publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"oa_version":"Preprint","acknowledgement":"YZ thanks Jiajin Li for making the observation given by Equation (23). He also would like to thank Nir Ailon and Ely Porat for several helpful conversations throughout this project, and Alexander Barg for insightful comments on the manuscript.\r\nYZ has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]. The work of SV was supported by a seed grant from IIT Hyderabad and the start-up research grant from the Science and Engineering Research Board, India (SRG/2020/000910).","abstract":[{"text":"We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let N > 0 and L ∈ Z ≽2 . A multiple packing is a set C of points in R n such that any point in R n lies in the intersection of at most L – 1 balls of radius √ nN around points in C . Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we derive the best known lower bounds on the optimal density of list-decodable infinite constellations for constant L under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory.","lang":"eng"}],"title":"Multiple packing: Lower bounds via infinite constellations","article_processing_charge":"No","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2211.04407","open_access":"1"}],"publisher":"IEEE","external_id":{"isi":["001017307000023"],"arxiv":["2211.04407"]},"quality_controlled":"1","doi":"10.1109/TIT.2023.3260950","department":[{"_id":"MaMo"}],"intvolume":"        69","author":[{"orcid":"0000-0002-6465-6258","first_name":"Yihan","full_name":"Zhang, Yihan","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"full_name":"Vatedka, Shashank","last_name":"Vatedka","first_name":"Shashank"}],"date_created":"2023-04-16T22:01:09Z","date_updated":"2023-12-13T11:16:46Z"},{"status":"public","publisher":"National Academy of Sciences","external_id":{"pmid":["37463204"],"isi":["001121663500001"]},"quality_controlled":"1","doi":"10.1073/pnas.2302028120","department":[{"_id":"MaMo"}],"intvolume":"       120","author":[{"last_name":"Barbier","full_name":"Barbier, Jean","first_name":"Jean"},{"first_name":"Francesco","last_name":"Camilli","full_name":"Camilli, Francesco"},{"orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco"},{"first_name":"Manuel","last_name":"Sáenz","full_name":"Sáenz, Manuel"}],"date_updated":"2025-09-09T12:41:50Z","date_created":"2023-07-30T22:01:02Z","language":[{"iso":"eng"}],"file_date_updated":"2023-07-31T07:30:48Z","volume":120,"citation":{"ama":"Barbier J, Camilli F, Mondelli M, Sáenz M. Fundamental limits in structured principal component analysis and how to reach them. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. 2023;120(30). doi:<a href=\"https://doi.org/10.1073/pnas.2302028120\">10.1073/pnas.2302028120</a>","ieee":"J. Barbier, F. Camilli, M. Mondelli, and M. Sáenz, “Fundamental limits in structured principal component analysis and how to reach them,” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 120, no. 30. National Academy of Sciences, 2023.","chicago":"Barbier, Jean, Francesco Camilli, Marco Mondelli, and Manuel Sáenz. “Fundamental Limits in Structured Principal Component Analysis and How to Reach Them.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences, 2023. <a href=\"https://doi.org/10.1073/pnas.2302028120\">https://doi.org/10.1073/pnas.2302028120</a>.","short":"J. Barbier, F. Camilli, M. Mondelli, M. Sáenz, Proceedings of the National Academy of Sciences of the United States of America 120 (2023).","mla":"Barbier, Jean, et al. “Fundamental Limits in Structured Principal Component Analysis and How to Reach Them.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 120, no. 30, e2302028120, National Academy of Sciences, 2023, doi:<a href=\"https://doi.org/10.1073/pnas.2302028120\">10.1073/pnas.2302028120</a>.","apa":"Barbier, J., Camilli, F., Mondelli, M., &#38; Sáenz, M. (2023). Fundamental limits in structured principal component analysis and how to reach them. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.2302028120\">https://doi.org/10.1073/pnas.2302028120</a>","ista":"Barbier J, Camilli F, Mondelli M, Sáenz M. 2023. Fundamental limits in structured principal component analysis and how to reach them. Proceedings of the National Academy of Sciences of the United States of America. 120(30), e2302028120."},"day":"25","publication_identifier":{"eissn":["1091-6490"]},"oa_version":"Published Version","related_material":{"link":[{"relation":"software","url":"https://github.com/fcamilli95/Structured-PCA-"}]},"acknowledgement":"J.B. was funded by the European Union (ERC, CHORAL, project number 101039794). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. M.M. was supported by the 2019 Lopez-Loreta Prize. We would like to thank the reviewers for the insightful comments and, in particular, for suggesting the BAMP-inspired denoisers leading to AMP-AP.","file":[{"success":1,"content_type":"application/pdf","file_id":"13323","checksum":"1fc06228afdb3aa80cf8e7766bcf9dc5","date_updated":"2023-07-31T07:30:48Z","creator":"dernst","file_name":"2023_PNAS_Barbier.pdf","date_created":"2023-07-31T07:30:48Z","access_level":"open_access","file_size":995933,"relation":"main_file"}],"abstract":[{"lang":"eng","text":"How do statistical dependencies in measurement noise influence high-dimensional inference? To answer this, we study the paradigmatic spiked matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We go beyond the usual independence assumption on the noise entries, by drawing the noise from a low-order polynomial orthogonal matrix ensemble. The resulting noise correlations make the setting relevant for applications but analytically challenging. We provide characterization of the Bayes optimal limits of inference in this model. If the spike is rotation invariant, we show that standard spectral PCA is optimal. However, for more general priors, both PCA and the existing approximate message-passing algorithm (AMP) fall short of achieving the information-theoretic limits, which we compute using the replica method from statistical physics. We thus propose an AMP, inspired by the theory of adaptive Thouless–Anderson–Palmer equations, which is empirically observed to saturate the conjectured theoretical limit. This AMP comes with a rigorous state evolution analysis tracking its performance. Although we focus on specific noise distributions, our methodology can be generalized to a wide class of trace matrix ensembles at the cost of more involved expressions. Finally, despite the seemingly strong assumption of rotation-invariant noise, our theory empirically predicts algorithmic performance on real data, pointing at strong universality properties."}],"title":"Fundamental limits in structured principal component analysis and how to reach them","article_processing_charge":"Yes (in subscription journal)","publication":"Proceedings of the National Academy of Sciences of the United States of America","has_accepted_license":"1","type":"journal_article","ddc":["000"],"publication_status":"published","date_published":"2023-07-25T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"fulldoi":"https://doi.org/10.1073/pnas.2302028120","_id":"13315","pmid":1,"issue":"30","year":"2023","article_number":"e2302028120","isi":1,"month":"07","article_type":"original","scopus_import":"1","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}]}]