[{"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."}],"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2303.07245"}],"oa":1,"publication_status":"published","page":"400-405","title":"Concentration without independence via information measures","_id":"14922","doi":"10.1109/isit54713.2023.10206899","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2024-02-02T11:18:40Z","language":[{"iso":"eng"}],"publication":"Proceedings of 2023 IEEE International Symposium on Information Theory","acknowledgement":"The authors are partially supported by the 2019 Lopez-Loreta Prize. They would also like to thank Professor Jan Maas for providing valuable suggestions and comments on an early version of the work.","type":"conference","arxiv":1,"scopus_import":"1","oa_version":"Preprint","conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2023-06-25","location":"Taipei, Taiwan","end_date":"2023-06-30"},"quality_controlled":"1","day":"30","month":"06","article_processing_charge":"No","external_id":{"arxiv":["2303.07245"]},"author":[{"first_name":"Amedeo Roberto","last_name":"Esposito","id":"9583e921-e1ad-11ec-9862-cef099626dc9","full_name":"Esposito, Amedeo Roberto"},{"first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"related_material":{"record":[{"relation":"later_version","id":"15172","status":"public"}]},"date_published":"2023-06-30T00:00:00Z","corr_author":"1","department":[{"_id":"MaMo"}],"citation":{"short":"A.R. Esposito, M. Mondelli, in:, Proceedings of 2023 IEEE International Symposium on Information Theory, IEEE, 2023, pp. 400–405.","ista":"Esposito AR, Mondelli M. 2023. Concentration without independence via information measures. Proceedings of 2023 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 400–405.","apa":"Esposito, A. R., &#38; Mondelli, M. (2023). Concentration without independence via information measures. In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i> (pp. 400–405). Taipei, Taiwan: IEEE. <a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">https://doi.org/10.1109/isit54713.2023.10206899</a>","chicago":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, 400–405. IEEE, 2023. <a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">https://doi.org/10.1109/isit54713.2023.10206899</a>.","mla":"Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence via Information Measures.” <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, IEEE, 2023, pp. 400–05, doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">10.1109/isit54713.2023.10206899</a>.","ieee":"A. R. Esposito and M. Mondelli, “Concentration without independence via information measures,” in <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, Taipei, Taiwan, 2023, pp. 400–405.","ama":"Esposito AR, Mondelli M. Concentration without independence via information measures. In: <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>. IEEE; 2023:400-405. doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206899\">10.1109/isit54713.2023.10206899</a>"},"publisher":"IEEE","date_updated":"2025-09-04T13:06:52Z","status":"public","publication_identifier":{"eisbn":["9781665475549"],"eissn":["2157-8117"]}},{"day":"30","month":"06","arxiv":1,"scopus_import":"1","oa_version":"Preprint","conference":{"start_date":"2023-06-25","name":"ISIT: International Symposium on Information Theory","end_date":"2023-06-30","location":"Taipei, Taiwan"},"quality_controlled":"1","corr_author":"1","department":[{"_id":"MaMo"}],"publisher":"IEEE","citation":{"ista":"Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. 2023. Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. Proceedings of 2023 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 1178–1183.","apa":"Fu, T., Liu, Y., Barbier, J., Mondelli, M., Liang, S., &#38; Hou, T. (2023). Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i> (pp. 1178–1183). Taipei, Taiwan: IEEE. <a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">https://doi.org/10.1109/isit54713.2023.10206671</a>","short":"T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, T. Hou, in:, Proceedings of 2023 IEEE International Symposium on Information Theory, IEEE, 2023, pp. 1178–1183.","ama":"Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise. In: <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>. IEEE; 2023:1178-1183. doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">10.1109/isit54713.2023.10206671</a>","mla":"Fu, Teng, et al. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured Noise.” <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, IEEE, 2023, pp. 1178–83, doi:<a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">10.1109/isit54713.2023.10206671</a>.","chicago":"Fu, Teng, YuHao Liu, Jean Barbier, Marco Mondelli, ShanSuo Liang, and TianQi Hou. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured Noise.” In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, 1178–83. IEEE, 2023. <a href=\"https://doi.org/10.1109/isit54713.2023.10206671\">https://doi.org/10.1109/isit54713.2023.10206671</a>.","ieee":"T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, and T. Hou, “Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise,” in <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>, Taipei, Taiwan, 2023, pp. 1178–1183."},"date_updated":"2025-07-10T11:51:04Z","status":"public","publication_identifier":{"eissn":["2157-8117"],"isbn":["9781665475549"]},"article_processing_charge":"No","external_id":{"arxiv":["2302.03306"]},"author":[{"first_name":"Teng","last_name":"Fu","full_name":"Fu, Teng"},{"first_name":"YuHao","full_name":"Liu, YuHao","last_name":"Liu"},{"first_name":"Jean","full_name":"Barbier, Jean","last_name":"Barbier"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Liang, ShanSuo","last_name":"Liang","first_name":"ShanSuo"},{"last_name":"Hou","full_name":"Hou, TianQi","first_name":"TianQi"}],"date_published":"2023-06-30T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2302.03306"}],"oa":1,"publication_status":"published","page":"1178-1183","title":"Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise","abstract":[{"lang":"eng","text":"We study the performance of a Bayesian statistician who estimates a rank-one signal corrupted by non-symmetric rotationally invariant noise with a generic distribution of singular values. As the signal-to-noise ratio and the noise structure are unknown, a Gaussian setup is incorrectly assumed. We derive the exact analytic expression for the error of the mismatched Bayes estimator and also provide the analysis of an approximate message passing (AMP) algorithm. The first result exploits the asymptotic behavior of spherical integrals for rectangular matrices and of low-rank matrix perturbations; the second one relies on the design and analysis of an auxiliary AMP. The numerical experiments show that there is a performance gap between the AMP and Bayes estimators, which is due to the incorrect estimation of the signal norm."}],"publication":"Proceedings of 2023 IEEE International Symposium on Information Theory","type":"conference","_id":"14923","doi":"10.1109/isit54713.2023.10206671","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","date_created":"2024-02-02T11:20:39Z","language":[{"iso":"eng"}]},{"_id":"14924","date_created":"2024-02-02T11:21:56Z","language":[{"iso":"eng"}],"year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"D. Wu and M. Mondelli are partially supported by the 2019 Lopez-Loreta Prize. V. Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16_019/0000765 \"Research Center for Informatics\".","type":"conference","publication":"Transactions on Machine Learning Research","abstract":[{"text":"The stochastic heavy ball method (SHB), also known as stochastic gradient descent (SGD) with Polyak's momentum, is widely used in training neural networks. However, despite the remarkable success of such algorithm in practice, its theoretical characterization remains limited. In this paper, we focus on neural networks with two and three layers and provide a rigorous understanding of the properties of the solutions found by SHB: \\emph{(i)} stability after dropping out part of the neurons, \\emph{(ii)} connectivity along a low-loss path, and \\emph{(iii)} convergence to the global optimum.\r\nTo achieve this goal, we take a mean-field view and relate the SHB dynamics to a certain partial differential equation in the limit of large network widths. This mean-field perspective has inspired a recent line of work focusing on SGD while, in contrast, our paper considers an algorithm with momentum. More specifically, after proving existence and uniqueness of the limit differential equations, we show convergence to the global optimum and give a quantitative bound between the mean-field limit and the SHB dynamics of a finite-width network. Armed with this last bound, we are able to establish the dropout-stability and connectivity of SHB solutions.","lang":"eng"}],"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2210.06819"}],"oa":1,"title":"Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence","alternative_title":["TMLR"],"author":[{"first_name":"Diyuan","last_name":"Wu","id":"1a5914c2-896a-11ed-bdf8-fb80621a0635","full_name":"Wu, Diyuan"},{"first_name":"Vyacheslav","full_name":"Kungurtsev, Vyacheslav","last_name":"Kungurtsev"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","first_name":"Marco"}],"article_processing_charge":"No","has_accepted_license":"1","external_id":{"arxiv":["2210.06819"]},"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2023-02-28T00:00:00Z","date_updated":"2025-04-15T07:50:17Z","publisher":"ML Research Press","citation":{"ieee":"D. Wu, V. Kungurtsev, and M. Mondelli, “Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence,” in <i>Transactions on Machine Learning Research</i>, 2023.","chicago":"Wu, Diyuan, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field Analysis for Heavy Ball Methods: Dropout-Stability, Connectivity, and Global Convergence.” In <i>Transactions on Machine Learning Research</i>. ML Research Press, 2023.","mla":"Wu, Diyuan, et al. “Mean-Field Analysis for Heavy Ball Methods: Dropout-Stability, Connectivity, and Global Convergence.” <i>Transactions on Machine Learning Research</i>, ML Research Press, 2023.","ama":"Wu D, Kungurtsev V, Mondelli M. Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence. In: <i>Transactions on Machine Learning Research</i>. ML Research Press; 2023.","short":"D. Wu, V. Kungurtsev, M. Mondelli, in:, Transactions on Machine Learning Research, ML Research Press, 2023.","apa":"Wu, D., Kungurtsev, V., &#38; Mondelli, M. (2023). Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence. In <i>Transactions on Machine Learning Research</i>. ML Research Press.","ista":"Wu D, Kungurtsev V, Mondelli M. 2023. Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence. Transactions on Machine Learning Research. , TMLR, ."},"department":[{"_id":"MaMo"}],"corr_author":"1","status":"public","quality_controlled":"1","oa_version":"Published Version","arxiv":1,"day":"28","month":"02"},{"oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2212.13468","open_access":"1"}],"publication_status":"published","alternative_title":["PMLR"],"page":"31151-31209","title":"Fundamental limits of two-layer autoencoders, and achieving them with gradient methods","abstract":[{"text":"Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.","lang":"eng"}],"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"acknowledgement":"Aleksandr Shevchenko, Kevin Kogler and Marco Mondelli are supported by the 2019 Lopez-Loreta Prize. Hamed Hassani acknowledges the support by the NSF CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science (EnCORE).","type":"conference","publication":"Proceedings of the 40th International Conference on Machine Learning","intvolume":"       202","_id":"14459","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2023-10-29T23:01:17Z","language":[{"iso":"eng"}],"day":"30","month":"07","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2023-07-23","location":"Honolulu, Hawaii, HI, United States","end_date":"2023-07-29"},"quality_controlled":"1","arxiv":1,"oa_version":"Preprint","scopus_import":"1","publisher":"ML Research Press","citation":{"short":"A. Shevchenko, K. Kögler, H. Hassani, M. Mondelli, in:, Proceedings of the 40th International Conference on Machine Learning, ML Research Press, 2023, pp. 31151–31209.","apa":"Shevchenko, A., Kögler, K., Hassani, H., &#38; Mondelli, M. (2023). Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. In <i>Proceedings of the 40th International Conference on Machine Learning</i> (Vol. 202, pp. 31151–31209). Honolulu, Hawaii, HI, United States: ML Research Press.","ista":"Shevchenko A, Kögler K, Hassani H, Mondelli M. 2023. Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. Proceedings of the 40th International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 202, 31151–31209.","ieee":"A. Shevchenko, K. Kögler, H. Hassani, and M. Mondelli, “Fundamental limits of two-layer autoencoders, and achieving them with gradient methods,” in <i>Proceedings of the 40th International Conference on Machine Learning</i>, Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 31151–31209.","mla":"Shevchenko, Alexander, et al. “Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient Methods.” <i>Proceedings of the 40th International Conference on Machine Learning</i>, vol. 202, ML Research Press, 2023, pp. 31151–209.","chicago":"Shevchenko, Alexander, Kevin Kögler, Hamed Hassani, and Marco Mondelli. “Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient Methods.” In <i>Proceedings of the 40th International Conference on Machine Learning</i>, 202:31151–209. ML Research Press, 2023.","ama":"Shevchenko A, Kögler K, Hassani H, Mondelli M. Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. In: <i>Proceedings of the 40th International Conference on Machine Learning</i>. Vol 202. ML Research Press; 2023:31151-31209."},"date_updated":"2026-06-13T22:30:06Z","corr_author":"1","department":[{"_id":"MaMo"},{"_id":"DaAl"}],"publication_identifier":{"eissn":["2640-3498"]},"status":"public","author":[{"last_name":"Shevchenko","full_name":"Shevchenko, Aleksandr","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","first_name":"Aleksandr"},{"id":"94ec913c-dc85-11ea-9058-e5051ab2428b","full_name":"Kögler, Kevin","last_name":"Kögler","first_name":"Kevin"},{"first_name":"Hamed","full_name":"Hassani, Hamed","last_name":"Hassani"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"external_id":{"arxiv":["2212.13468"]},"article_processing_charge":"No","volume":202,"date_published":"2023-07-30T00:00:00Z","related_material":{"record":[{"id":"17465","relation":"dissertation_contains","status":"public"}]}},{"scopus_import":"1","oa_version":"Preprint","arxiv":1,"quality_controlled":"1","issue":"12","day":"01","month":"12","external_id":{"arxiv":["1901.03790"],"isi":["000891796100007"]},"article_processing_charge":"No","author":[{"orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","first_name":"Yihan"},{"first_name":"Shashank","last_name":"Vatedka","full_name":"Vatedka, Shashank"}],"date_published":"2022-12-01T00:00:00Z","volume":68,"department":[{"_id":"MaMo"}],"corr_author":"1","date_updated":"2024-10-09T21:02:55Z","publisher":"IEEE","citation":{"ista":"Zhang Y, Vatedka S. 2022. List decoding random Euclidean codes and Infinite constellations. IEEE Transactions on Information Theory. 68(12), 7753–7786.","apa":"Zhang, Y., &#38; Vatedka, S. (2022). List decoding random Euclidean codes and Infinite constellations. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2022.3189542\">https://doi.org/10.1109/TIT.2022.3189542</a>","short":"Y. Zhang, S. Vatedka, IEEE Transactions on Information Theory 68 (2022) 7753–7786.","ama":"Zhang Y, Vatedka S. List decoding random Euclidean codes and Infinite constellations. <i>IEEE Transactions on Information Theory</i>. 2022;68(12):7753-7786. doi:<a href=\"https://doi.org/10.1109/TIT.2022.3189542\">10.1109/TIT.2022.3189542</a>","mla":"Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes and Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 12, IEEE, 2022, pp. 7753–86, doi:<a href=\"https://doi.org/10.1109/TIT.2022.3189542\">10.1109/TIT.2022.3189542</a>.","chicago":"Zhang, Yihan, and Shashank Vatedka. “List Decoding Random Euclidean Codes and Infinite Constellations.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2022. <a href=\"https://doi.org/10.1109/TIT.2022.3189542\">https://doi.org/10.1109/TIT.2022.3189542</a>.","ieee":"Y. Zhang and S. Vatedka, “List decoding random Euclidean codes and Infinite constellations,” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 12. IEEE, pp. 7753–7786, 2022."},"status":"public","publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"isi":1,"abstract":[{"lang":"eng","text":"We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints P and N respectively, the list decoding capacity is equal to 1/2logP/N. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity."}],"publication_status":"published","article_type":"original","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1901.03790"}],"oa":1,"title":"List decoding random Euclidean codes and Infinite constellations","page":"7753-7786","_id":"11639","doi":"10.1109/TIT.2022.3189542","intvolume":"        68","language":[{"iso":"eng"}],"date_created":"2022-07-24T22:01:42Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","year":"2022","publication":"IEEE Transactions on Information Theory","type":"journal_article","acknowledgement":"This work was done when Shashank Vatedka was at the Chinese University of Hong Kong, where he was supported in part by CUHK Direct Grants 4055039 and 4055077. He would like to acknowledge funding from a seed grant offered by IIT Hyderabad and the Start-up Research Grant (SRG/2020/000910) from the Science and Engineering Board, India. Yihan Zhang has received funding from the European Union’s Horizon 2020 research and innovation programme\r\nunder grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]."},{"publication":"2022 IEEE International Symposium on Information Theory","acknowledgement":"The work of ADS and ML was supported in part by the US National Science Foundation under awards CCF-1909468 and CCF-1909451.","type":"conference","date_created":"2022-09-04T22:02:03Z","language":[{"iso":"eng"}],"year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"12011","doi":"10.1109/ISIT50566.2022.9834709","intvolume":"      2022","title":"The capacity of causal adversarial channels","page":"2523-2528","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2205.06708"}],"abstract":[{"lang":"eng","text":"We characterize the capacity for the discrete-time arbitrarily varying channel with discrete inputs, outputs, and states when (a) the encoder and decoder do not share common randomness, (b) the input and state are subject to cost constraints, (c) the transition matrix of the channel is deterministic given the state, and (d) at each time step the adversary can only observe the current and past channel inputs when choosing the state at that time. The achievable strategy involves stochastic encoding together with list decoding and a disambiguation step. The converse uses a two-phase \"babble-and-push\" strategy where the adversary chooses the state randomly in the first phase, list decodes the output, and then chooses state inputs to symmetrize the channel in the second phase. These results generalize prior work on specific channels models (additive, erasure) to general discrete alphabets and models."}],"status":"public","isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:40:42Z","publisher":"IEEE","citation":{"ama":"Zhang Y, Jaggi S, Langberg M, Sarwate AD. The capacity of causal adversarial channels. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2523-2528. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">10.1109/ISIT50566.2022.9834709</a>","mla":"Zhang, Yihan, et al. “The Capacity of Causal Adversarial Channels.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2523–28, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">10.1109/ISIT50566.2022.9834709</a>.","chicago":"Zhang, Yihan, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. “The Capacity of Causal Adversarial Channels.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2523–28. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">https://doi.org/10.1109/ISIT50566.2022.9834709</a>.","ieee":"Y. Zhang, S. Jaggi, M. Langberg, and A. D. Sarwate, “The capacity of causal adversarial channels,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2523–2528.","ista":"Zhang Y, Jaggi S, Langberg M, Sarwate AD. 2022. The capacity of causal adversarial channels. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2523–2528.","apa":"Zhang, Y., Jaggi, S., Langberg, M., &#38; Sarwate, A. D. (2022). The capacity of causal adversarial channels. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2523–2528). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834709\">https://doi.org/10.1109/ISIT50566.2022.9834709</a>","short":"Y. Zhang, S. Jaggi, M. Langberg, A.D. Sarwate, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2523–2528."},"date_published":"2022-08-03T00:00:00Z","volume":2022,"article_processing_charge":"No","external_id":{"isi":["001254261902114"],"arxiv":["2205.06708"]},"author":[{"first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang"},{"full_name":"Jaggi, Sidharth","last_name":"Jaggi","first_name":"Sidharth"},{"last_name":"Langberg","full_name":"Langberg, Michael","first_name":"Michael"},{"last_name":"Sarwate","full_name":"Sarwate, Anand D.","first_name":"Anand D."}],"month":"08","day":"03","oa_version":"Preprint","scopus_import":"1","arxiv":1,"quality_controlled":"1","conference":{"start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"}},{"author":[{"first_name":"Sahel","full_name":"Torkamani, Sahel","id":"0503e7f8-2d05-11ed-aa17-db0640c720fc","last_name":"Torkamani"},{"full_name":"Ebrahimi, Javad B.","last_name":"Ebrahimi","first_name":"Javad B."},{"last_name":"Sadeghi","full_name":"Sadeghi, Parastoo","first_name":"Parastoo"},{"first_name":"Rafael G.L.","full_name":"D'Oliveira, Rafael G.L.","last_name":"D'Oliveira"},{"first_name":"Muriel","last_name":"Médard","full_name":"Médard, Muriel"}],"external_id":{"isi":["001254261901131"],"arxiv":["2203.15429"]},"article_processing_charge":"No","date_published":"2022-08-03T00:00:00Z","volume":2022,"date_updated":"2025-09-10T09:42:41Z","citation":{"ista":"Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. 2022. Heterogeneous differential privacy via graphs. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 1623–1628.","apa":"Torkamani, S., Ebrahimi, J. B., Sadeghi, P., D’Oliveira, R. G. L., &#38; Médard, M. (2022). Heterogeneous differential privacy via graphs. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 1623–1628). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">https://doi.org/10.1109/ISIT50566.2022.9834711</a>","short":"S. Torkamani, J.B. Ebrahimi, P. Sadeghi, R.G.L. D’Oliveira, M. Médard, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 1623–1628.","ama":"Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. Heterogeneous differential privacy via graphs. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:1623-1628. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">10.1109/ISIT50566.2022.9834711</a>","chicago":"Torkamani, Sahel, Javad B. Ebrahimi, Parastoo Sadeghi, Rafael G.L. D’Oliveira, and Muriel Médard. “Heterogeneous Differential Privacy via Graphs.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:1623–28. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">https://doi.org/10.1109/ISIT50566.2022.9834711</a>.","mla":"Torkamani, Sahel, et al. “Heterogeneous Differential Privacy via Graphs.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 1623–28, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834711\">10.1109/ISIT50566.2022.9834711</a>.","ieee":"S. Torkamani, J. B. Ebrahimi, P. Sadeghi, R. G. L. D’Oliveira, and M. Médard, “Heterogeneous differential privacy via graphs,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 1623–1628."},"publisher":"IEEE","department":[{"_id":"MaMo"}],"isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"status":"public","quality_controlled":"1","conference":{"start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"oa_version":"Preprint","scopus_import":"1","arxiv":1,"day":"03","month":"08","intvolume":"      2022","doi":"10.1109/ISIT50566.2022.9834711","_id":"12012","language":[{"iso":"eng"}],"date_created":"2022-09-04T22:02:04Z","year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","publication":"2022 IEEE International Symposium on Information Theory","abstract":[{"lang":"eng","text":"This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual’s response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter ε across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter ε is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph)."}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2203.15429"}],"oa":1,"title":"Heterogeneous differential privacy via graphs","page":"1623-1628"},{"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:42:04Z","publisher":"IEEE","citation":{"ama":"Joshi P, Purkayastha A, Zhang Y, Budkuley AJ, Jaggi S. On the capacity of additive AVCs with feedback. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:504-509. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">10.1109/ISIT50566.2022.9834850</a>","ieee":"P. Joshi, A. Purkayastha, Y. Zhang, A. J. Budkuley, and S. Jaggi, “On the capacity of additive AVCs with feedback,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 504–509.","mla":"Joshi, Pranav, et al. “On the Capacity of Additive AVCs with Feedback.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 504–09, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">10.1109/ISIT50566.2022.9834850</a>.","chicago":"Joshi, Pranav, Amritakshya Purkayastha, Yihan Zhang, Amitalok J. Budkuley, and Sidharth Jaggi. “On the Capacity of Additive AVCs with Feedback.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:504–9. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">https://doi.org/10.1109/ISIT50566.2022.9834850</a>.","apa":"Joshi, P., Purkayastha, A., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S. (2022). On the capacity of additive AVCs with feedback. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 504–509). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834850\">https://doi.org/10.1109/ISIT50566.2022.9834850</a>","ista":"Joshi P, Purkayastha A, Zhang Y, Budkuley AJ, Jaggi S. 2022. On the capacity of additive AVCs with feedback. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 504–509.","short":"P. Joshi, A. Purkayastha, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 504–509."},"status":"public","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"isi":1,"external_id":{"isi":["001254261900085"]},"article_processing_charge":"No","author":[{"first_name":"Pranav","last_name":"Joshi","full_name":"Joshi, Pranav"},{"first_name":"Amritakshya","full_name":"Purkayastha, Amritakshya","last_name":"Purkayastha"},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"first_name":"Amitalok J.","full_name":"Budkuley, Amitalok J.","last_name":"Budkuley"},{"first_name":"Sidharth","last_name":"Jaggi","full_name":"Jaggi, Sidharth"}],"volume":2022,"date_published":"2022-08-03T00:00:00Z","day":"03","month":"08","scopus_import":"1","oa_version":"None","quality_controlled":"1","conference":{"location":"Espoo, Finland","end_date":"2022-07-01","start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory"},"publication":"2022 IEEE International Symposium on Information Theory","type":"conference","_id":"12013","intvolume":"      2022","doi":"10.1109/ISIT50566.2022.9834850","language":[{"iso":"eng"}],"date_created":"2022-09-04T22:02:04Z","year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","title":"On the capacity of additive AVCs with feedback","page":"504-509","abstract":[{"lang":"eng","text":"We consider the problem of communication over adversarial channels with feedback. Two parties comprising sender Alice and receiver Bob seek to communicate reliably. An adversary James observes Alice's channel transmission entirely and chooses, maliciously, its additive channel input or jamming state thereby corrupting Bob's observation. Bob can communicate over a one-way reverse link with Alice; we assume that transmissions over this feedback link cannot be corrupted by James. Our goal in this work is to study the optimum throughput or capacity over such channels with feedback. We first present results for the quadratically-constrained additive channel where communication is known to be impossible when the noise-to-signal (power) ratio (NSR) is at least 1. We present a novel achievability scheme to establish that positive rate communication is possible even when the NSR is as high as 8/9. We also present new converse upper bounds on the capacity of this channel under potentially stochastic encoders and decoders. We also study feedback communication over the more widely studied q-ary alphabet channel under additive noise. For the q -ary channel, where q > 2, it is well known that capacity is positive under full feedback if and only if the adversary can corrupt strictly less than half the transmitted symbols. We generalize this result and show that the same threshold holds for positive rate communication when the noiseless feedback may only be partial; our scheme employs a stochastic decoder. We extend this characterization, albeit partially, to fully deterministic schemes under partial noiseless feedback. We also present new converse upper bounds for q-ary channels under full feedback, where the encoder and/or decoder may privately randomize. Our converse results bring to the fore an interesting alternate expression for the well known converse bound for the q—ary channel under full feedback which, when specialized to the binary channel, also equals its known capacity."}]},{"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:41:24Z","citation":{"mla":"Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2559–64, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">10.1109/ISIT50566.2022.9834512</a>.","chicago":"Zhang, Yihan, and Shashank Vatedka. “List-Decodability of Poisson Point Processes.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2559–64. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">https://doi.org/10.1109/ISIT50566.2022.9834512</a>.","ieee":"Y. Zhang and S. Vatedka, “List-decodability of Poisson Point Processes,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2559–2564.","ama":"Zhang Y, Vatedka S. List-decodability of Poisson Point Processes. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2559-2564. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">10.1109/ISIT50566.2022.9834512</a>","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2559–2564.","ista":"Zhang Y, Vatedka S. 2022. List-decodability of Poisson Point Processes. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2559–2564.","apa":"Zhang, Y., &#38; Vatedka, S. (2022). List-decodability of Poisson Point Processes. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2559–2564). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834512\">https://doi.org/10.1109/ISIT50566.2022.9834512</a>"},"publisher":"IEEE","status":"public","isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"article_processing_charge":"No","external_id":{"isi":["001254261902120"]},"author":[{"first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang"},{"first_name":"Shashank","last_name":"Vatedka","full_name":"Vatedka, Shashank"}],"date_published":"2022-08-03T00:00:00Z","volume":2022,"day":"03","month":"08","scopus_import":"1","oa_version":"None","quality_controlled":"1","conference":{"start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"publication":"2022 IEEE International Symposium on Information Theory","type":"conference","_id":"12014","doi":"10.1109/ISIT50566.2022.9834512","intvolume":"      2022","date_created":"2022-09-04T22:02:04Z","language":[{"iso":"eng"}],"year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","title":"List-decodability of Poisson Point Processes","page":"2559-2564","abstract":[{"lang":"eng","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 Rn such that any point in Rn 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 exactly pin down the asymptotic density of (expurgated) Poisson Point Processes under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. This gives rise to the best known lower bound on the largest multiple packing density. Our result corrects a mistake in a previous paper by Blinovsky [Bli05]."}]},{"scopus_import":"1","oa_version":"None","quality_controlled":"1","conference":{"name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26","location":"Espoo, Finland","end_date":"2022-07-01"},"month":"08","day":"03","volume":2022,"date_published":"2022-08-03T00:00:00Z","article_processing_charge":"No","external_id":{"isi":["001254261903042"]},"author":[{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"full_name":"Vatedka, Shashank","last_name":"Vatedka","first_name":"Shashank"}],"status":"public","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"isi":1,"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:44:24Z","citation":{"short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 3085–3090.","apa":"Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds for multiple packing. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 3085–3090). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">https://doi.org/10.1109/ISIT50566.2022.9834443</a>","ista":"Zhang Y, Vatedka S. 2022. Lower bounds for multiple packing. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 3085–3090.","ieee":"Y. Zhang and S. Vatedka, “Lower bounds for multiple packing,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 3085–3090.","chicago":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:3085–90. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">https://doi.org/10.1109/ISIT50566.2022.9834443</a>.","mla":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds for Multiple Packing.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 3085–90, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">10.1109/ISIT50566.2022.9834443</a>.","ama":"Zhang Y, Vatedka S. Lower bounds for multiple packing. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:3085-3090. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834443\">10.1109/ISIT50566.2022.9834443</a>"},"publisher":"IEEE","abstract":[{"lang":"eng","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 P, N > 0 and L∈Z≥2. A multiple packing is a set C of points in Bn(0–,nP−−−√) such that any point in ℝ n lies in the intersection of at most L – 1 balls of radius nN−−−√ around points in C. 1 In this paper, we derive two lower bounds on the largest possible density of a multiple packing. These bounds are obtained through a stronger notion called average-radius multiple packing. Specifically, we exactly pin down the asymptotics of (expurgated) Gaussian codes and (expurgated) spherical codes under average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. The bound for spherical codes matches the previous best known bound which was obtained for the standard (weaker) notion of multiple packing through a curious connection with error exponents [Bli99], [ZV21]. The bound for Gaussian codes suggests that they are strictly inferior to spherical codes."}],"title":"Lower bounds for multiple packing","page":"3085-3090","publication_status":"published","date_created":"2022-09-04T22:02:05Z","language":[{"iso":"eng"}],"year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"12015","intvolume":"      2022","doi":"10.1109/ISIT50566.2022.9834443","publication":"2022 IEEE International Symposium on Information Theory","type":"conference"},{"day":"03","month":"08","scopus_import":"1","oa_version":"Preprint","arxiv":1,"quality_controlled":"1","conference":{"start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:43:32Z","publisher":"IEEE","citation":{"mla":"Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of the Scaling Exponent.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022, pp. 2154–59, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">10.1109/ISIT50566.2022.9834712</a>.","chicago":"Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of the Scaling Exponent.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2154–59. IEEE, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">https://doi.org/10.1109/ISIT50566.2022.9834712</a>.","ieee":"D. Fathollahi and M. Mondelli, “Polar coded computing: The role of the scaling exponent,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2154–2159.","ama":"Fathollahi D, Mondelli M. Polar coded computing: The role of the scaling exponent. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. IEEE; 2022:2154-2159. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">10.1109/ISIT50566.2022.9834712</a>","short":"D. Fathollahi, M. Mondelli, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2154–2159.","ista":"Fathollahi D, Mondelli M. 2022. Polar coded computing: The role of the scaling exponent. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2154–2159.","apa":"Fathollahi, D., &#38; Mondelli, M. (2022). Polar coded computing: The role of the scaling exponent. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2154–2159). Espoo, Finland: IEEE. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834712\">https://doi.org/10.1109/ISIT50566.2022.9834712</a>"},"status":"public","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"isi":1,"external_id":{"arxiv":["2201.10082"],"isi":["001254261902052"]},"article_processing_charge":"No","author":[{"last_name":"Fathollahi","full_name":"Fathollahi, Dorsa","first_name":"Dorsa"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"volume":2022,"date_published":"2022-08-03T00:00:00Z","publication_status":"published","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2201.10082","open_access":"1"}],"oa":1,"title":"Polar coded computing: The role of the scaling exponent","page":"2154-2159","abstract":[{"lang":"eng","text":"We consider the problem of coded distributed computing using polar codes. The average execution time of a coded computing system is related to the error probability for transmission over the binary erasure channel in recent work by Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes is investigated. In this paper, we focus on polar codes and unveil a connection between the average execution time and the scaling exponent μ of the family of codes. In the finite-length characterization of polar codes, the scaling exponent is a key object capturing the speed of convergence to capacity. In particular, we show that (i) the gap between the normalized average execution time of polar codes and that of optimal MDS codes is O(n –1/μ ), and (ii) this upper bound can be improved to roughly O(n –1/2 ) by considering polar codes with large kernels. We conjecture that these bounds could be improved to O(n –2/μ ) and O(n –1 ), respectively, and provide a heuristic argument as well as numerical evidence supporting this view."}],"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"publication":"2022 IEEE International Symposium on Information Theory","type":"conference","acknowledgement":"D. Fathollahi and M. Mondelli were partially supported by the 2019 Lopez-Loreta Prize. The authors thank Hamed Hassani and Hessam Mahdavifar for helpful discussions.","_id":"12016","doi":"10.1109/ISIT50566.2022.9834712","intvolume":"      2022","date_created":"2022-09-04T22:02:05Z","language":[{"iso":"eng"}],"year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"publication":"2022 IEEE International Symposium on Information Theory","type":"conference","date_created":"2022-09-04T22:02:06Z","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2022","_id":"12017","doi":"10.1109/ISIT50566.2022.9834632","intvolume":"      2022","title":"New results on AVCs with omniscient and myopic adversaries","page":"2535-2540","publication_status":"published","abstract":[{"lang":"eng","text":"In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget."}],"status":"public","isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"department":[{"_id":"MaMo"}],"date_updated":"2025-09-10T09:45:03Z","citation":{"ista":"Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. 2022. New results on AVCs with omniscient and myopic adversaries. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 2535–2540.","apa":"Yadav, A. K., Alimohammadi, M., Zhang, Y., Budkuley, A. J., &#38; Jaggi, S. (2022). New results on AVCs with omniscient and myopic adversaries. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2535–2540). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">https://doi.org/10.1109/ISIT50566.2022.9834632</a>","short":"A.K. Yadav, M. Alimohammadi, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 2535–2540.","ama":"Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. New results on AVCs with omniscient and myopic adversaries. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:2535-2540. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">10.1109/ISIT50566.2022.9834632</a>","chicago":"Yadav, Anuj Kumar, Mohammadreza Alimohammadi, Yihan Zhang, Amitalok J. Budkuley, and Sidharth Jaggi. “New Results on AVCs with Omniscient and Myopic Adversaries.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2535–40. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">https://doi.org/10.1109/ISIT50566.2022.9834632</a>.","mla":"Yadav, Anuj Kumar, et al. “New Results on AVCs with Omniscient and Myopic Adversaries.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2535–40, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834632\">10.1109/ISIT50566.2022.9834632</a>.","ieee":"A. K. Yadav, M. Alimohammadi, Y. Zhang, A. J. Budkuley, and S. Jaggi, “New results on AVCs with omniscient and myopic adversaries,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2535–2540."},"publisher":"Institute of Electrical and Electronics Engineers","date_published":"2022-08-03T00:00:00Z","volume":2022,"article_processing_charge":"No","external_id":{"isi":["001254261902116"]},"author":[{"first_name":"Anuj Kumar","last_name":"Yadav","full_name":"Yadav, Anuj Kumar"},{"first_name":"Mohammadreza","last_name":"Alimohammadi","full_name":"Alimohammadi, Mohammadreza"},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"full_name":"Budkuley, Amitalok J.","last_name":"Budkuley","first_name":"Amitalok J."},{"last_name":"Jaggi","full_name":"Jaggi, Sidharth","first_name":"Sidharth"}],"month":"08","day":"03","scopus_import":"1","oa_version":"None","conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: Internation Symposium on Information Theory","start_date":"2022-06-26"},"quality_controlled":"1"},{"scopus_import":"1","oa_version":"None","conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: International Symposium on Information Theory"},"quality_controlled":"1","month":"08","day":"03","volume":2022,"date_published":"2022-08-03T00:00:00Z","external_id":{"isi":["001254261901080"]},"article_processing_charge":"No","author":[{"orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","first_name":"Yihan"},{"last_name":"Vatedka","full_name":"Vatedka, Shashank","first_name":"Shashank"}],"status":"public","isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"department":[{"_id":"MaMo"}],"publisher":"Institute of Electrical and Electronics Engineers","citation":{"ama":"Zhang Y, Vatedka S. Lower bounds on list decoding capacity using error exponents. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:1324-1329. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">10.1109/ISIT50566.2022.9834815</a>","chicago":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity Using Error Exponents.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:1324–29. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">https://doi.org/10.1109/ISIT50566.2022.9834815</a>.","mla":"Zhang, Yihan, and Shashank Vatedka. “Lower Bounds on List Decoding Capacity Using Error Exponents.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–29, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">10.1109/ISIT50566.2022.9834815</a>.","ieee":"Y. Zhang and S. Vatedka, “Lower bounds on list decoding capacity using error exponents,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 1324–1329.","ista":"Zhang Y, Vatedka S. 2022. Lower bounds on list decoding capacity using error exponents. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 1324–1329.","apa":"Zhang, Y., &#38; Vatedka, S. (2022). Lower bounds on list decoding capacity using error exponents. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 1324–1329). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834815\">https://doi.org/10.1109/ISIT50566.2022.9834815</a>","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–1329."},"date_updated":"2025-09-10T09:45:40Z","abstract":[{"text":"We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset C⊂Rn is an (N,L – 1)-multiple packing or an (N,L– 1)-list decodable code if every Euclidean ball of radius nN−−−√ in ℝ n contains no more than L − 1 points of C. We study this problem with and without ℓ 2 norm constraints on C, and derive the best-known lower bounds on the maximal rate for (N,L−1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing.","lang":"eng"}],"page":"1324-1329","title":"Lower bounds on list decoding capacity using error exponents","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2022","date_created":"2022-09-04T22:02:06Z","language":[{"iso":"eng"}],"_id":"12018","doi":"10.1109/ISIT50566.2022.9834815","intvolume":"      2022","publication":"2022 IEEE International Symposium on Information Theory","type":"conference"},{"isi":1,"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"status":"public","date_updated":"2025-09-10T09:46:15Z","publisher":"Institute of Electrical and Electronics Engineers","citation":{"apa":"Polyanskii, N., &#38; Zhang, Y. (2022). List-decodable zero-rate codes for the Z-channel. In <i>2022 IEEE International Symposium on Information Theory</i> (Vol. 2022, pp. 2553–2558). Espoo, Finland: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">https://doi.org/10.1109/ISIT50566.2022.9834829</a>","ista":"Polyanskii N, Zhang Y. 2022. List-decodable zero-rate codes for the Z-channel. 2022 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory vol. 2022, 2553–2558.","short":"N. Polyanskii, Y. Zhang, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–2558.","ama":"Polyanskii N, Zhang Y. List-decodable zero-rate codes for the Z-channel. In: <i>2022 IEEE International Symposium on Information Theory</i>. Vol 2022. Institute of Electrical and Electronics Engineers; 2022:2553-2558. doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">10.1109/ISIT50566.2022.9834829</a>","ieee":"N. Polyanskii and Y. Zhang, “List-decodable zero-rate codes for the Z-channel,” in <i>2022 IEEE International Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 2553–2558.","chicago":"Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the Z-Channel.” In <i>2022 IEEE International Symposium on Information Theory</i>, 2022:2553–58. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">https://doi.org/10.1109/ISIT50566.2022.9834829</a>.","mla":"Polyanskii, Nikita, and Yihan Zhang. “List-Decodable Zero-Rate Codes for the Z-Channel.” <i>2022 IEEE International Symposium on Information Theory</i>, vol. 2022, Institute of Electrical and Electronics Engineers, 2022, pp. 2553–58, doi:<a href=\"https://doi.org/10.1109/ISIT50566.2022.9834829\">10.1109/ISIT50566.2022.9834829</a>."},"department":[{"_id":"MaMo"}],"date_published":"2022-08-03T00:00:00Z","volume":2022,"author":[{"first_name":"Nikita","last_name":"Polyanskii","full_name":"Polyanskii, Nikita"},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"}],"external_id":{"isi":["001254261902119"]},"article_processing_charge":"No","month":"08","day":"03","conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: International Symposium on Information Theory","start_date":"2022-06-26"},"quality_controlled":"1","oa_version":"None","scopus_import":"1","type":"conference","publication":"2022 IEEE International Symposium on Information Theory","date_created":"2022-09-04T22:02:07Z","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2022","intvolume":"      2022","doi":"10.1109/ISIT50566.2022.9834829","_id":"12019","title":"List-decodable zero-rate codes for the Z-channel","page":"2553-2558","publication_status":"published","abstract":[{"text":"This paper studies combinatorial properties of codes for the Z-channel. A Z-channel with error fraction τ takes as input a length-n binary codeword and injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L − 1)-list-decodable code for the Z-channel with error fraction τ has exponential (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be L−1L−1−L−LL−1. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size Θ L (ε −3/2 ) for any L − 1 ≥ 1.","lang":"eng"}]},{"abstract":[{"text":"A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. A low-complexity SP scheme applied to a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is integrated into an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, efficient latency and complexity reduction schemes are introduced that virtually preserve the error-correction performance of the proposed decoder. Simulation results demonstrate that at the target frame error rate of 10−3 for the RM code of length 256 with 163 information bits, the proposed decoder reduces 6% of the computational complexity and 22% of the decoding latency of the state-of-the-art semi-parallel simplified successive-cancellation decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from the full symmetry group of RM codes, while relatively maintaining the error-correction performance and memory consumption of the semi-parallel permuted SSC-FHT decoder.","lang":"eng"}],"title":"Decoding Reed-Muller codes with successive codeword permutations","page":"7134-7145","publication_status":"published","article_type":"original","oa":1,"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2109.02122","open_access":"1"}],"date_created":"2023-01-16T09:50:38Z","language":[{"iso":"eng"}],"year":"2022","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12233","doi":"10.1109/tcomm.2022.3211101","intvolume":"        70","publication":"IEEE Transactions on Communications","type":"journal_article","issue":"11","scopus_import":"1","oa_version":"Preprint","arxiv":1,"quality_controlled":"1","month":"11","day":"01","volume":70,"date_published":"2022-11-01T00:00:00Z","article_processing_charge":"No","external_id":{"isi":["000937284600006"],"arxiv":["2109.02122"]},"author":[{"first_name":"Nghia","last_name":"Doan","full_name":"Doan, Nghia"},{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","orcid":"0000-0002-3242-7020"},{"last_name":"Gross","full_name":"Gross, Warren J.","first_name":"Warren J."}],"status":"public","isi":1,"publication_identifier":{"eissn":["1558-0857"],"issn":["0090-6778"]},"department":[{"_id":"MaMo"}],"date_updated":"2023-08-04T09:34:43Z","publisher":"Institute of Electrical and Electronics Engineers","citation":{"chicago":"Doan, Nghia, Seyyed Ali Hashemi, Marco Mondelli, and Warren J. Gross. “Decoding Reed-Muller Codes with Successive Codeword Permutations.” <i>IEEE Transactions on Communications</i>. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/tcomm.2022.3211101\">https://doi.org/10.1109/tcomm.2022.3211101</a>.","mla":"Doan, Nghia, et al. “Decoding Reed-Muller Codes with Successive Codeword Permutations.” <i>IEEE Transactions on Communications</i>, vol. 70, no. 11, Institute of Electrical and Electronics Engineers, 2022, pp. 7134–45, doi:<a href=\"https://doi.org/10.1109/tcomm.2022.3211101\">10.1109/tcomm.2022.3211101</a>.","ieee":"N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross, “Decoding Reed-Muller codes with successive codeword permutations,” <i>IEEE Transactions on Communications</i>, vol. 70, no. 11. Institute of Electrical and Electronics Engineers, pp. 7134–7145, 2022.","ama":"Doan N, Hashemi SA, Mondelli M, Gross WJ. Decoding Reed-Muller codes with successive codeword permutations. <i>IEEE Transactions on Communications</i>. 2022;70(11):7134-7145. doi:<a href=\"https://doi.org/10.1109/tcomm.2022.3211101\">10.1109/tcomm.2022.3211101</a>","short":"N. Doan, S.A. Hashemi, M. Mondelli, W.J. Gross, IEEE Transactions on Communications 70 (2022) 7134–7145.","ista":"Doan N, Hashemi SA, Mondelli M, Gross WJ. 2022. Decoding Reed-Muller codes with successive codeword permutations. IEEE Transactions on Communications. 70(11), 7134–7145.","apa":"Doan, N., Hashemi, S. A., Mondelli, M., &#38; Gross, W. J. (2022). Decoding Reed-Muller codes with successive codeword permutations. <i>IEEE Transactions on Communications</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/tcomm.2022.3211101\">https://doi.org/10.1109/tcomm.2022.3211101</a>"}},{"type":"journal_article","publication":"IEEE Transactions on Information Theory","doi":"10.1109/tit.2022.3167554","intvolume":"        68","_id":"12273","language":[{"iso":"eng"}],"date_created":"2023-01-16T10:01:19Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","year":"2022","article_type":"original","publication_status":"published","oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1801.05951","open_access":"1"}],"title":"Quadratically constrained myopic adversarial channels","page":"4901-4948","abstract":[{"text":"We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most 2log(n) bits in one sub-regime, and at most Ω(n) bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.","lang":"eng"}],"date_updated":"2024-10-09T21:03:54Z","citation":{"apa":"Zhang, Y., Vatedka, S., Jaggi, S., &#38; Sarwate, A. D. (2022). Quadratically constrained myopic adversarial channels. <i>IEEE Transactions on Information Theory</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/tit.2022.3167554\">https://doi.org/10.1109/tit.2022.3167554</a>","ista":"Zhang Y, Vatedka S, Jaggi S, Sarwate AD. 2022. Quadratically constrained myopic adversarial channels. IEEE Transactions on Information Theory. 68(8), 4901–4948.","short":"Y. Zhang, S. Vatedka, S. Jaggi, A.D. Sarwate, IEEE Transactions on Information Theory 68 (2022) 4901–4948.","ama":"Zhang Y, Vatedka S, Jaggi S, Sarwate AD. Quadratically constrained myopic adversarial channels. <i>IEEE Transactions on Information Theory</i>. 2022;68(8):4901-4948. doi:<a href=\"https://doi.org/10.1109/tit.2022.3167554\">10.1109/tit.2022.3167554</a>","ieee":"Y. Zhang, S. Vatedka, S. Jaggi, and A. D. Sarwate, “Quadratically constrained myopic adversarial channels,” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 8. Institute of Electrical and Electronics Engineers, pp. 4901–4948, 2022.","mla":"Zhang, Yihan, et al. “Quadratically Constrained Myopic Adversarial Channels.” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 8, Institute of Electrical and Electronics Engineers, 2022, pp. 4901–48, doi:<a href=\"https://doi.org/10.1109/tit.2022.3167554\">10.1109/tit.2022.3167554</a>.","chicago":"Zhang, Yihan, Shashank Vatedka, Sidharth Jaggi, and Anand D. Sarwate. “Quadratically Constrained Myopic Adversarial Channels.” <i>IEEE Transactions on Information Theory</i>. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/tit.2022.3167554\">https://doi.org/10.1109/tit.2022.3167554</a>."},"publisher":"Institute of Electrical and Electronics Engineers","department":[{"_id":"MaMo"}],"corr_author":"1","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"isi":1,"status":"public","author":[{"first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang"},{"last_name":"Vatedka","full_name":"Vatedka, Shashank","first_name":"Shashank"},{"full_name":"Jaggi, Sidharth","last_name":"Jaggi","first_name":"Sidharth"},{"full_name":"Sarwate, Anand D.","last_name":"Sarwate","first_name":"Anand D."}],"external_id":{"arxiv":["1801.05951"],"isi":["000838527100004"]},"article_processing_charge":"No","date_published":"2022-08-01T00:00:00Z","volume":68,"day":"01","month":"08","quality_controlled":"1","scopus_import":"1","oa_version":"Preprint","arxiv":1,"issue":"8"},{"article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","external_id":{"isi":["000889589900001"]},"author":[{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"first_name":"Ramji","full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan"}],"related_material":{"record":[{"relation":"earlier_version","id":"10598","status":"public"}]},"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2022-11-24T00:00:00Z","volume":2022,"department":[{"_id":"MaMo"}],"corr_author":"1","date_updated":"2025-04-15T07:50:16Z","publisher":"IOP Publishing","citation":{"short":"M. Mondelli, R. Venkataramanan, Journal of Statistical Mechanics: Theory and Experiment 2022 (2022).","ista":"Mondelli M, Venkataramanan R. 2022. Approximate message passing with spectral initialization for generalized linear models. Journal of Statistical Mechanics: Theory and Experiment. 2022(11), 114003.","apa":"Mondelli, M., &#38; Venkataramanan, R. (2022). Approximate message passing with spectral initialization for generalized linear models. <i>Journal of Statistical Mechanics: Theory and Experiment</i>. IOP Publishing. <a href=\"https://doi.org/10.1088/1742-5468/ac9828\">https://doi.org/10.1088/1742-5468/ac9828</a>","mla":"Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” <i>Journal of Statistical Mechanics: Theory and Experiment</i>, vol. 2022, no. 11, 114003, IOP Publishing, 2022, doi:<a href=\"https://doi.org/10.1088/1742-5468/ac9828\">10.1088/1742-5468/ac9828</a>.","chicago":"Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” <i>Journal of Statistical Mechanics: Theory and Experiment</i>. IOP Publishing, 2022. <a href=\"https://doi.org/10.1088/1742-5468/ac9828\">https://doi.org/10.1088/1742-5468/ac9828</a>.","ieee":"M. Mondelli and R. Venkataramanan, “Approximate message passing with spectral initialization for generalized linear models,” <i>Journal of Statistical Mechanics: Theory and Experiment</i>, vol. 2022, no. 11. IOP Publishing, 2022.","ama":"Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization for generalized linear models. <i>Journal of Statistical Mechanics: Theory and Experiment</i>. 2022;2022(11). doi:<a href=\"https://doi.org/10.1088/1742-5468/ac9828\">10.1088/1742-5468/ac9828</a>"},"status":"public","publication_identifier":{"issn":["1742-5468"]},"isi":1,"scopus_import":"1","oa_version":"Published Version","quality_controlled":"1","issue":"11","day":"24","keyword":["Statistics","Probability and Uncertainty","Statistics and Probability","Statistical and Nonlinear Physics"],"month":"11","_id":"12480","doi":"10.1088/1742-5468/ac9828","ddc":["510","530"],"intvolume":"      2022","language":[{"iso":"eng"}],"date_created":"2023-02-02T08:31:57Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","year":"2022","file_date_updated":"2023-02-02T08:35:52Z","publication":"Journal of Statistical Mechanics: Theory and Experiment","type":"journal_article","acknowledgement":"The authors would like to thank Andrea Montanari for helpful discussions.\r\nM Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R Venkataramanan was partially supported by the Alan Turing Institute under the EPSRC Grant\r\nEP/N510129/1.","abstract":[{"lang":"eng","text":"We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach."}],"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"article_type":"original","publication_status":"published","oa":1,"article_number":"114003","file":[{"date_updated":"2023-02-02T08:35:52Z","creator":"dernst","file_id":"12481","success":1,"relation":"main_file","file_size":1729997,"access_level":"open_access","file_name":"2022_JourStatisticalMechanics_Mondelli.pdf","content_type":"application/pdf","checksum":"01411ffa76d3e380a0446baeb89b1ef7","date_created":"2023-02-02T08:35:52Z"}],"title":"Approximate message passing with spectral initialization for generalized linear models"},{"status":"public","publication_identifier":{"isbn":["9781713871088"]},"department":[{"_id":"MaMo"}],"corr_author":"1","date_updated":"2024-10-09T21:04:25Z","citation":{"short":"J. Barbier, T. Hou, M. Mondelli, M. Saenz, in:, 36th Annual Conference on Neural Information Processing Systems, 2022.","ista":"Barbier J, Hou T, Mondelli M, Saenz M. 2022. The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? 36th Annual Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, NeurIPS, vol. 35.","apa":"Barbier, J., Hou, T., Mondelli, M., &#38; Saenz, M. (2022). The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? In <i>36th Annual Conference on Neural Information Processing Systems</i> (Vol. 35). New Orleans, LA, United States.","chicago":"Barbier, Jean, TianQi Hou, Marco Mondelli, and Manuel Saenz. “The Price of Ignorance: How Much Does It Cost to Forget Noise Structure in Low-Rank Matrix Estimation?” In <i>36th Annual Conference on Neural Information Processing Systems</i>, Vol. 35, 2022.","mla":"Barbier, Jean, et al. “The Price of Ignorance: How Much Does It Cost to Forget Noise Structure in Low-Rank Matrix Estimation?” <i>36th Annual Conference on Neural Information Processing Systems</i>, vol. 35, 2022.","ieee":"J. Barbier, T. Hou, M. Mondelli, and M. Saenz, “The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation?,” in <i>36th Annual Conference on Neural Information Processing Systems</i>, New Orleans, LA, United States, 2022, vol. 35.","ama":"Barbier J, Hou T, Mondelli M, Saenz M. The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? In: <i>36th Annual Conference on Neural Information Processing Systems</i>. Vol 35. ; 2022."},"volume":35,"date_published":"2022-11-20T00:00:00Z","article_processing_charge":"No","external_id":{"arxiv":["2205.10009"]},"author":[{"last_name":"Barbier","full_name":"Barbier, Jean","first_name":"Jean"},{"last_name":"Hou","full_name":"Hou, TianQi","first_name":"TianQi"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"first_name":"Manuel","last_name":"Saenz","full_name":"Saenz, Manuel"}],"month":"11","day":"20","oa_version":"Preprint","scopus_import":"1","arxiv":1,"conference":{"name":"NeurIPS: Neural Information Processing Systems","start_date":"2022-11-28","location":"New Orleans, LA, United States","end_date":"2022-12-09"},"quality_controlled":"1","publication":"36th Annual Conference on Neural Information Processing Systems","type":"conference","acknowledgement":"M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. The authors acknowledge\r\ndiscussions with A. Krajenbrink, M. Robinson, A. Depope, N. Macris and F. Pourkamali.\r\n","language":[{"iso":"eng"}],"date_created":"2023-02-10T13:45:41Z","year":"2022","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12536","intvolume":"        35","title":"The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation?","alternative_title":["NeurIPS"],"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2205.10009"}],"abstract":[{"lang":"eng","text":"We consider the problem of estimating a rank-1 signal corrupted by structured rotationally invariant noise, and address the following question: how well do inference algorithms perform when the noise statistics is unknown and hence Gaussian noise is assumed? While the matched Bayes-optimal setting with unstructured noise is well understood, the analysis of this mismatched problem is only at its premises. In this paper, we make a step towards understanding the effect of the strong source of mismatch which is the noise statistics. Our main technical contribution is the rigorous analysis of a Bayes estimator and of an approximate message passing (AMP) algorithm, both of which incorrectly assume a Gaussian setup. The first result exploits the theory of spherical integrals and of low-rank matrix perturbations; the idea behind the second one is to design and analyze an artificial AMP which, by taking advantage of the flexibility in the denoisers, is able to \"correct\" the mismatch. Armed with these sharp asymptotic characterizations, we unveil a rich and often unexpected phenomenology. For example, despite AMP is in principle designed to efficiently compute the Bayes estimator, the former is outperformed by the latter in terms of mean-square error. We show that this performance gap is due to an incorrect estimation of the signal norm. In fact, when the SNR is large enough, the overlaps of the AMP and the Bayes estimator coincide, and they even match those of optimal estimators taking into account the structure of the noise."}]},{"publication":"36th Conference on Neural Information Processing Systems","acknowledgement":"The authors were partially supported by the 2019 Lopez-Loreta prize, and they would like to thank\r\nQuynh Nguyen, Mahdi Soltanolkotabi and Adel Javanmard for helpful discussions.\r\n","type":"conference","date_created":"2023-02-10T13:46:37Z","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2022","_id":"12537","intvolume":"        35","title":"Memorization and optimization in deep neural networks with minimum over-parameterization","alternative_title":["Advances in Neural Information Processing Systems"],"page":"7628-7640","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2205.10217"}],"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"abstract":[{"lang":"eng","text":"The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide memorization, optimization and generalization guarantees in deep neural networks. A line of work has studied the NTK spectrum for two-layer and deep networks with at least a layer with Ω(N) neurons, N being the number of training samples. Furthermore, there is increasing evidence suggesting that deep networks with sub-linear layer widths are powerful memorizers and optimizers, as long as the number of parameters exceeds the number of samples. Thus, a natural open question is whether the NTK is well conditioned in such a challenging sub-linear setup. In this paper, we answer this question in the affirmative. Our key technical contribution is a lower bound on the smallest NTK eigenvalue for deep networks with the minimum possible over-parameterization: the number of parameters is roughly Ω(N) and, hence, the number of neurons is as little as Ω(N−−√). To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training."}],"status":"public","publication_identifier":{"isbn":["9781713871088"],"eissn":["1049-5258"]},"department":[{"_id":"MaMo"}],"corr_author":"1","date_updated":"2025-05-14T11:28:22Z","citation":{"ista":"Bombari S, Amani MH, Mondelli M. 2022. Memorization and optimization in deep neural networks with minimum over-parameterization. 36th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 35, 7628–7640.","apa":"Bombari, S., Amani, M. H., &#38; Mondelli, M. (2022). Memorization and optimization in deep neural networks with minimum over-parameterization. In <i>36th Conference on Neural Information Processing Systems</i> (Vol. 35, pp. 7628–7640). New Orleans, LA, United States: Neural Information Processing Systems Foundation.","short":"S. Bombari, M.H. Amani, M. Mondelli, in:, 36th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2022, pp. 7628–7640.","ama":"Bombari S, Amani MH, Mondelli M. Memorization and optimization in deep neural networks with minimum over-parameterization. In: <i>36th Conference on Neural Information Processing Systems</i>. Vol 35. Neural Information Processing Systems Foundation; 2022:7628-7640.","chicago":"Bombari, Simone, Mohammad Hossein Amani, and Marco Mondelli. “Memorization and Optimization in Deep Neural Networks with Minimum Over-Parameterization.” In <i>36th Conference on Neural Information Processing Systems</i>, 35:7628–40. Neural Information Processing Systems Foundation, 2022.","mla":"Bombari, Simone, et al. “Memorization and Optimization in Deep Neural Networks with Minimum Over-Parameterization.” <i>36th Conference on Neural Information Processing Systems</i>, vol. 35, Neural Information Processing Systems Foundation, 2022, pp. 7628–40.","ieee":"S. Bombari, M. H. Amani, and M. Mondelli, “Memorization and optimization in deep neural networks with minimum over-parameterization,” in <i>36th Conference on Neural Information Processing Systems</i>, New Orleans, LA, United States, 2022, vol. 35, pp. 7628–7640."},"publisher":"Neural Information Processing Systems Foundation","OA_place":"repository","date_published":"2022-07-24T00:00:00Z","volume":35,"external_id":{"arxiv":["2205.10217"]},"article_processing_charge":"No","author":[{"first_name":"Simone","id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","last_name":"Bombari"},{"first_name":"Mohammad Hossein","last_name":"Amani","full_name":"Amani, Mohammad Hossein"},{"first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"month":"07","day":"24","OA_type":"green","oa_version":"Preprint","arxiv":1,"conference":{"start_date":"2022-11-28","name":"NeurIPS: Neural Information Processing Systems","location":"New Orleans, LA, United States","end_date":"2022-12-09"},"quality_controlled":"1"},{"month":"11","day":"16","conference":{"location":"Mumbai, India","end_date":"2022-11-09","start_date":"2022-11-01","name":"ITW: Information Theory Workshop"},"quality_controlled":"1","arxiv":1,"scopus_import":"1","oa_version":"Preprint","isi":1,"publication_identifier":{"isbn":["9781665483414"]},"status":"public","citation":{"ama":"Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. Sharp asymptotics on the compression of two-layer neural networks. <i>IEEE Information Theory Workshop</i>. 2022:588-593. doi:<a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">10.1109/ITW54588.2022.9965870</a>","mla":"Amani, Mohammad Hossein, et al. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.” <i>IEEE Information Theory Workshop</i>, IEEE, 2022, pp. 588–93, doi:<a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">10.1109/ITW54588.2022.9965870</a>.","chicago":"Amani, Mohammad Hossein, Simone Bombari, Marco Mondelli, Rattana Pukdee, and Stefano Rini. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.” <i>IEEE Information Theory Workshop</i>. IEEE, 2022. <a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">https://doi.org/10.1109/ITW54588.2022.9965870</a>.","ieee":"M. H. Amani, S. Bombari, M. Mondelli, R. Pukdee, and S. Rini, “Sharp asymptotics on the compression of two-layer neural networks,” <i>IEEE Information Theory Workshop</i>. IEEE, pp. 588–593, 2022.","ista":"Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. 2022. Sharp asymptotics on the compression of two-layer neural networks. IEEE Information Theory Workshop., 588–593.","apa":"Amani, M. H., Bombari, S., Mondelli, M., Pukdee, R., &#38; Rini, S. (2022). Sharp asymptotics on the compression of two-layer neural networks. <i>IEEE Information Theory Workshop</i>. Mumbai, India: IEEE. <a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">https://doi.org/10.1109/ITW54588.2022.9965870</a>","short":"M.H. Amani, S. Bombari, M. Mondelli, R. Pukdee, S. Rini, IEEE Information Theory Workshop (2022) 588–593."},"publisher":"IEEE","date_updated":"2025-09-10T09:53:31Z","department":[{"_id":"MaMo"}],"date_published":"2022-11-16T00:00:00Z","author":[{"last_name":"Amani","full_name":"Amani, Mohammad Hossein","first_name":"Mohammad Hossein"},{"first_name":"Simone","id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","last_name":"Bombari"},{"last_name":"Mondelli","orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco"},{"first_name":"Rattana","last_name":"Pukdee","full_name":"Pukdee, Rattana"},{"first_name":"Stefano","last_name":"Rini","full_name":"Rini, Stefano"}],"article_processing_charge":"No","external_id":{"arxiv":["2205.08199"],"isi":["000904341100099"]},"page":"588-593","title":"Sharp asymptotics on the compression of two-layer neural networks","oa":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2205.08199"}],"article_type":"original","publication_status":"published","abstract":[{"lang":"eng","text":"In this paper, we study the compression of a target two-layer neural network with N nodes into a compressed network with M<N nodes. More precisely, we consider the setting in which the weights of the target network are i.i.d. sub-Gaussian, and we minimize the population L_2 loss between the outputs of the target and of the compressed network, under the assumption of Gaussian inputs. By using tools from high-dimensional probability, we show that this non-convex problem can be simplified when the target network is sufficiently over-parameterized, and provide the error rate of this approximation as a function of the input dimension and N. In this mean-field limit, the simplified objective, as well as the optimal weights of the compressed network, does not depend on the realization of the target network, but only on expected scaling factors. Furthermore, for networks with ReLU activation, we conjecture that the optimum of the simplified optimization problem is achieved by taking weights on the Equiangular Tight Frame (ETF), while the scaling of the weights and the orientation of the ETF depend on the parameters of the target network. Numerical evidence is provided to support this conjecture."}],"type":"journal_article","publication":"IEEE Information Theory Workshop","year":"2022","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"date_created":"2023-02-10T13:47:56Z","doi":"10.1109/ITW54588.2022.9965870","_id":"12538"}]