[{"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2203.16701","open_access":"1"}],"citation":{"short":"S. Bombari, A. Achille, Z. Wang, Y.-X. Wang, Y. Xie, K.Y. Singh, S. Appalaraju, V. Mahadevan, S. Soatto, ArXiv (n.d.).","ama":"Bombari S, Achille A, Wang Z, et al. Towards differential relational privacy and its use in question answering. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2203.16701\">10.48550/arXiv.2203.16701</a>","apa":"Bombari, S., Achille, A., Wang, Z., Wang, Y.-X., Xie, Y., Singh, K. Y., … Soatto, S. (n.d.). Towards differential relational privacy and its use in question answering. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2203.16701\">https://doi.org/10.48550/arXiv.2203.16701</a>","ista":"Bombari S, Achille A, Wang Z, Wang Y-X, Xie Y, Singh KY, Appalaraju S, Mahadevan V, Soatto S. Towards differential relational privacy and its use in question answering. arXiv, 2203.16701.","chicago":"Bombari, Simone, Alessandro Achille, Zijian Wang, Yu-Xiang Wang, Yusheng Xie, Kunwar Yashraj Singh, Srikar Appalaraju, Vijay Mahadevan, and Stefano Soatto. “Towards Differential Relational Privacy and Its Use in Question Answering.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2203.16701\">https://doi.org/10.48550/arXiv.2203.16701</a>.","ieee":"S. Bombari <i>et al.</i>, “Towards differential relational privacy and its use in question answering,” <i>arXiv</i>. .","mla":"Bombari, Simone, et al. “Towards Differential Relational Privacy and Its Use in Question Answering.” <i>ArXiv</i>, 2203.16701, doi:<a href=\"https://doi.org/10.48550/arXiv.2203.16701\">10.48550/arXiv.2203.16701</a>."},"day":"30","article_processing_charge":"No","article_number":"2203.16701","status":"public","abstract":[{"text":"Memorization of the relation between entities in a dataset can lead to privacy issues when using a trained model for question answering. We introduce Relational Memorization (RM) to understand, quantify and control this phenomenon. While bounding general memorization can have detrimental effects on the performance of a trained model, bounding RM does not prevent effective learning. The difference is most pronounced when the data distribution is long-tailed, with many queries having only few training examples: Impeding general memorization prevents effective learning, while impeding only relational memorization still allows learning general properties of the underlying concepts. We formalize the notion of Relational Privacy (RP) and, inspired by Differential Privacy (DP), we provide a possible definition of Differential Relational Privacy (DrP). These notions can be used to describe and compute bounds on the amount of RM in a trained model. We illustrate Relational Privacy concepts in experiments with large-scale models for Question Answering.","lang":"eng"}],"year":"2022","date_created":"2023-04-23T16:11:48Z","date_updated":"2023-04-25T07:34:49Z","publication":"arXiv","author":[{"id":"ca726dda-de17-11ea-bc14-f9da834f63aa","last_name":"Bombari","full_name":"Bombari, Simone","first_name":"Simone"},{"last_name":"Achille","full_name":"Achille, Alessandro","first_name":"Alessandro"},{"last_name":"Wang","full_name":"Wang, Zijian","first_name":"Zijian"},{"full_name":"Wang, Yu-Xiang","first_name":"Yu-Xiang","last_name":"Wang"},{"first_name":"Yusheng","full_name":"Xie, Yusheng","last_name":"Xie"},{"first_name":"Kunwar Yashraj","full_name":"Singh, Kunwar Yashraj","last_name":"Singh"},{"last_name":"Appalaraju","first_name":"Srikar","full_name":"Appalaraju, Srikar"},{"first_name":"Vijay","full_name":"Mahadevan, Vijay","last_name":"Mahadevan"},{"last_name":"Soatto","full_name":"Soatto, Stefano","first_name":"Stefano"}],"oa_version":"Preprint","external_id":{"arxiv":["2203.16701"]},"date_published":"2022-03-30T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"MaMo"}],"title":"Towards differential relational privacy and its use in question answering","oa":1,"language":[{"iso":"eng"}],"publication_status":"submitted","arxiv":1,"type":"preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12860","month":"03","doi":"10.48550/arXiv.2203.16701"},{"publication_status":"published","oa":1,"related_material":{"record":[{"id":"10053","relation":"earlier_version","status":"public"}]},"title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","article_type":"original","month":"06","_id":"10364","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"MaMo"}],"acknowledgement":"S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and\r\nEngineering Research Council of Canada (NSERC) and by Huawei. M. Mondelli is partially\r\nsupported by the 2019 Lopez-Loreta Prize. A. Fazeli and A. Vardy were supported in part by\r\nthe National Science Foundation under Grant CCF-1764104.","status":"public","abstract":[{"text":"This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1-1/μ + N/P log2 log2 N/P), where N is the block length of the code and μ is the scaling exponent of the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P = N/2, the latency of SSC decoding is O(N1-1/μ), which is sublinear in the block length. This recovers a result from our earlier work. Second, in a fully-serial implementation where P = 1, the latency of SSC decoding scales as O(N log2 log2 N). The multiplicative constant is also calculated: we show that the latency of SSC decoding when P = 1 is given by (2 + o(1))N log2 log2 N. Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P = N1/μ. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.","lang":"eng"}],"intvolume":"        21","citation":{"ieee":"S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith, “Parallelism versus latency in simplified successive-cancellation decoding of polar codes,” <i>IEEE Transactions on Wireless Communications</i>, vol. 21, no. 6. Institute of Electrical and Electronics Engineers, pp. 3909–3920, 2022.","mla":"Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>IEEE Transactions on Wireless Communications</i>, vol. 21, no. 6, Institute of Electrical and Electronics Engineers, 2022, pp. 3909–20, doi:<a href=\"https://doi.org/10.1109/TWC.2021.3125626\">10.1109/TWC.2021.3125626</a>.","chicago":"Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>IEEE Transactions on Wireless Communications</i>. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/TWC.2021.3125626\">https://doi.org/10.1109/TWC.2021.3125626</a>.","ista":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2022. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. IEEE Transactions on Wireless Communications. 21(6), 3909–3920.","apa":"Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., &#38; Goldsmith, A. (2022). Parallelism versus latency in simplified successive-cancellation decoding of polar codes. <i>IEEE Transactions on Wireless Communications</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/TWC.2021.3125626\">https://doi.org/10.1109/TWC.2021.3125626</a>","ama":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. <i>IEEE Transactions on Wireless Communications</i>. 2022;21(6):3909-3920. doi:<a href=\"https://doi.org/10.1109/TWC.2021.3125626\">10.1109/TWC.2021.3125626</a>","short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, IEEE Transactions on Wireless Communications 21 (2022) 3909–3920."},"day":"01","language":[{"iso":"eng"}],"arxiv":1,"type":"journal_article","doi":"10.1109/TWC.2021.3125626","publisher":"Institute of Electrical and Electronics Engineers","publication":"IEEE Transactions on Wireless Communications","issue":"6","author":[{"last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali","first_name":"Seyyed Ali"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","first_name":"Marco"},{"full_name":"Fazeli, Arman","first_name":"Arman","last_name":"Fazeli"},{"last_name":"Vardy","first_name":"Alexander","full_name":"Vardy, Alexander"},{"last_name":"Cioffi","first_name":"John","full_name":"Cioffi, John"},{"last_name":"Goldsmith","full_name":"Goldsmith, Andrea","first_name":"Andrea"}],"oa_version":"Preprint","external_id":{"isi":["000809406400028"],"arxiv":["2012.13378"]},"date_published":"2022-06-01T00:00:00Z","isi":1,"volume":21,"year":"2022","date_created":"2021-11-28T23:01:29Z","quality_controlled":"1","page":"3909-3920","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"date_updated":"2024-09-10T13:03:18Z","publication_identifier":{"eissn":["1558-2248"],"issn":["1536-1276"]},"main_file_link":[{"url":"https://arxiv.org/abs/2012.13378","open_access":"1"}],"scopus_import":"1","article_processing_charge":"No"},{"ddc":["000"],"author":[{"id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","last_name":"Shevchenko","full_name":"Shevchenko, Aleksandr","first_name":"Aleksandr"},{"first_name":"Vyacheslav","full_name":"Kungurtsev, Vyacheslav","last_name":"Kungurtsev"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","first_name":"Marco"}],"publication":"Journal of Machine Learning Research","issue":"130","date_published":"2022-04-01T00:00:00Z","external_id":{"arxiv":["2111.02278"]},"oa_version":"Published Version","file_date_updated":"2022-05-30T08:22:55Z","type":"journal_article","language":[{"iso":"eng"}],"arxiv":1,"publisher":"Journal of Machine Learning Research","scopus_import":"1","publication_identifier":{"issn":["1532-4435"],"eissn":["1533-7928"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"article_processing_charge":"No","volume":23,"file":[{"date_updated":"2022-05-30T08:22:55Z","access_level":"open_access","success":1,"content_type":"application/pdf","date_created":"2022-05-30T08:22:55Z","file_id":"11422","file_name":"21-1365.pdf","creator":"cchlebak","file_size":1521701,"checksum":"d4ff5d1affb34848b5c5e4002483fc62","relation":"main_file"}],"date_updated":"2024-09-10T13:03:17Z","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"quality_controlled":"1","page":"1-55","date_created":"2022-05-29T22:01:54Z","year":"2022","acknowledgement":"We would like to thank Mert Pilanci for several exploratory discussions in the early stage\r\nof the project, Jan Maas for clarifications about Jordan et al. (1998), and Max Zimmer for\r\nsuggestive numerical experiments. A. Shevchenko and M. Mondelli are partially supported\r\nby the 2019 Lopez-Loreta Prize. V. Kungurtsev acknowledges support to the OP VVV\r\nproject CZ.02.1.01/0.0/0.0/16 019/0000765 Research Center for Informatics.\r\n","department":[{"_id":"MaMo"},{"_id":"DaAl"}],"article_type":"original","title":"Mean-field analysis of piecewise linear solutions for wide ReLU networks","oa":1,"related_material":{"link":[{"url":"https://www.jmlr.org/papers/v23/21-1365.html","relation":"other"}]},"publication_status":"published","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"11420","month":"04","intvolume":"        23","citation":{"ama":"Shevchenko A, Kungurtsev V, Mondelli M. Mean-field analysis of piecewise linear solutions for wide ReLU networks. <i>Journal of Machine Learning Research</i>. 2022;23(130):1-55.","short":"A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research 23 (2022) 1–55.","mla":"Shevchenko, Aleksandr, et al. “Mean-Field Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” <i>Journal of Machine Learning Research</i>, vol. 23, no. 130, Journal of Machine Learning Research, 2022, pp. 1–55.","ieee":"A. Shevchenko, V. Kungurtsev, and M. Mondelli, “Mean-field analysis of piecewise linear solutions for wide ReLU networks,” <i>Journal of Machine Learning Research</i>, vol. 23, no. 130. Journal of Machine Learning Research, pp. 1–55, 2022.","ista":"Shevchenko A, Kungurtsev V, Mondelli M. 2022. Mean-field analysis of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning Research. 23(130), 1–55.","chicago":"Shevchenko, Aleksandr, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research, 2022.","apa":"Shevchenko, A., Kungurtsev, V., &#38; Mondelli, M. (2022). Mean-field analysis of piecewise linear solutions for wide ReLU networks. <i>Journal of Machine Learning Research</i>. Journal of Machine Learning Research."},"has_accepted_license":"1","day":"01","abstract":[{"lang":"eng","text":"Understanding the properties of neural networks trained via stochastic gradient descent (SGD) is at the heart of the theory of deep learning. In this work, we take a mean-field view, and consider a two-layer ReLU network trained via noisy-SGD for a univariate regularized regression problem. Our main result is that SGD with vanishingly small noise injected in the gradients is biased towards a simple solution: at convergence, the ReLU network implements a piecewise linear map of the inputs, and the number of “knot” points -- i.e., points where the tangent of the ReLU network estimator changes -- between two consecutive training inputs is at most three. In particular, as the number of neurons of the network grows, the SGD dynamics is captured by the solution of a gradient flow and, at convergence, the distribution of the weights approaches the unique minimizer of a related free energy, which has a Gibbs form. Our key technical contribution consists in the analysis of the estimator resulting from this minimizer: we show that its second derivative vanishes everywhere, except at some specific locations which represent the “knot” points. We also provide empirical evidence that knots at locations distinct from the data points might occur, as predicted by our theory."}],"status":"public"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"11639","month":"12","article_type":"original","title":"List decoding random Euclidean codes and Infinite constellations","oa":1,"publication_status":"published","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].","department":[{"_id":"MaMo"}],"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."}],"status":"public","day":"01","intvolume":"        68","citation":{"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>","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>","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>.","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>.","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."},"publisher":"IEEE","doi":"10.1109/TIT.2022.3189542","type":"journal_article","language":[{"iso":"eng"}],"arxiv":1,"date_published":"2022-12-01T00:00:00Z","oa_version":"Preprint","external_id":{"isi":["000891796100007"],"arxiv":["1901.03790"]},"author":[{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","first_name":"Yihan","last_name":"Zhang"},{"full_name":"Vatedka, Shashank","first_name":"Shashank","last_name":"Vatedka"}],"issue":"12","publication":"IEEE Transactions on Information Theory","date_updated":"2023-08-03T12:12:19Z","quality_controlled":"1","page":"7753-7786","date_created":"2022-07-24T22:01:42Z","year":"2022","volume":68,"isi":1,"article_processing_charge":"No","scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1901.03790","open_access":"1"}],"publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]}},{"publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"scopus_import":"1","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2205.06708","open_access":"1"}],"article_processing_charge":"No","volume":2022,"quality_controlled":"1","page":"2523-2528","date_created":"2022-09-04T22:02:03Z","year":"2022","date_updated":"2022-09-05T09:09:15Z","publication":"2022 IEEE International Symposium on Information Theory","author":[{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","first_name":"Yihan","last_name":"Zhang"},{"last_name":"Jaggi","full_name":"Jaggi, Sidharth","first_name":"Sidharth"},{"last_name":"Langberg","first_name":"Michael","full_name":"Langberg, Michael"},{"first_name":"Anand D.","full_name":"Sarwate, Anand D.","last_name":"Sarwate"}],"conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: Internation Symposium on Information Theory","start_date":"2022-06-26"},"oa_version":"Preprint","external_id":{"arxiv":["2205.06708"]},"date_published":"2022-08-03T00:00:00Z","language":[{"iso":"eng"}],"arxiv":1,"type":"conference","doi":"10.1109/ISIT50566.2022.9834709","publisher":"IEEE","intvolume":"      2022","citation":{"short":"Y. Zhang, S. Jaggi, M. Langberg, A.D. Sarwate, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 2523–2528.","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>","ista":"Zhang Y, Jaggi S, Langberg M, Sarwate AD. 2022. The capacity of causal adversarial channels. 2022 IEEE International Symposium on Information Theory. ISIT: Internation 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>","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>.","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>.","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."},"day":"03","status":"public","abstract":[{"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.","lang":"eng"}],"acknowledgement":"The work of ADS and ML was supported in part by the US National Science Foundation under awards CCF-1909468 and CCF-1909451.","department":[{"_id":"MaMo"}],"oa":1,"title":"The capacity of causal adversarial channels","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","_id":"12011"},{"arxiv":1,"language":[{"iso":"eng"}],"type":"conference","doi":"10.1109/ISIT50566.2022.9834711","publisher":"IEEE","publication":"2022 IEEE International Symposium on Information Theory","author":[{"last_name":"Torkamani","first_name":"Sahel","full_name":"Torkamani, Sahel","id":"0503e7f8-2d05-11ed-aa17-db0640c720fc"},{"full_name":"Ebrahimi, Javad B.","first_name":"Javad B.","last_name":"Ebrahimi"},{"last_name":"Sadeghi","full_name":"Sadeghi, Parastoo","first_name":"Parastoo"},{"last_name":"D'Oliveira","first_name":"Rafael G.L.","full_name":"D'Oliveira, Rafael G.L."},{"first_name":"Muriel","full_name":"Médard, Muriel","last_name":"Médard"}],"oa_version":"Preprint","conference":{"start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"external_id":{"arxiv":["2203.15429"]},"date_published":"2022-08-03T00:00:00Z","volume":2022,"quality_controlled":"1","page":"1623-1628","date_created":"2022-09-04T22:02:04Z","year":"2022","date_updated":"2022-09-05T10:28:35Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2203.15429"}],"article_processing_charge":"No","oa":1,"title":"Heterogeneous differential privacy via graphs","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12012","month":"08","department":[{"_id":"MaMo"}],"status":"public","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)."}],"intvolume":"      2022","citation":{"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>","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: Internation 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>","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."},"day":"03"},{"scopus_import":"1","intvolume":"      2022","citation":{"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: Internation Symposium on Information Theory vol. 2022, 504–509.","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>","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>.","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.","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>"},"publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"article_processing_charge":"No","day":"03","volume":2022,"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."}],"status":"public","date_updated":"2022-09-05T10:23:35Z","page":"504-509","quality_controlled":"1","year":"2022","date_created":"2022-09-04T22:02:04Z","author":[{"full_name":"Joshi, Pranav","first_name":"Pranav","last_name":"Joshi"},{"last_name":"Purkayastha","full_name":"Purkayastha, Amritakshya","first_name":"Amritakshya"},{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang","first_name":"Yihan","full_name":"Zhang, Yihan"},{"first_name":"Amitalok J.","full_name":"Budkuley, Amitalok J.","last_name":"Budkuley"},{"first_name":"Sidharth","full_name":"Jaggi, Sidharth","last_name":"Jaggi"}],"publication":"2022 IEEE International Symposium on Information Theory","date_published":"2022-08-03T00:00:00Z","department":[{"_id":"MaMo"}],"oa_version":"None","conference":{"location":"Espoo, Finland","end_date":"2022-07-01","name":"ISIT: Internation Symposium on Information Theory","start_date":"2022-06-26"},"type":"conference","title":"On the capacity of additive AVCs with feedback","publication_status":"published","language":[{"iso":"eng"}],"publisher":"IEEE","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"08","_id":"12013","doi":"10.1109/ISIT50566.2022.9834850"},{"article_processing_charge":"No","day":"03","citation":{"ista":"Zhang Y, Vatedka S. 2022. List-decodability of Poisson Point Processes. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 2559–2564.","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>.","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>","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>.","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.","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 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>"},"intvolume":"      2022","scopus_import":"1","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"date_updated":"2022-09-05T09:23:04Z","year":"2022","date_created":"2022-09-04T22:02:04Z","quality_controlled":"1","page":"2559-2564","volume":2022,"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]."}],"status":"public","department":[{"_id":"MaMo"}],"date_published":"2022-08-03T00:00:00Z","conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory"},"oa_version":"None","author":[{"last_name":"Zhang","full_name":"Zhang, Yihan","first_name":"Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"first_name":"Shashank","full_name":"Vatedka, Shashank","last_name":"Vatedka"}],"publication":"2022 IEEE International Symposium on Information Theory","publisher":"IEEE","month":"08","_id":"12014","doi":"10.1109/ISIT50566.2022.9834512","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","language":[{"iso":"eng"}],"publication_status":"published","title":"List-decodability of Poisson Point Processes"},{"type":"conference","title":"Lower bounds for multiple packing","publication_status":"published","language":[{"iso":"eng"}],"publisher":"IEEE","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12015","month":"08","doi":"10.1109/ISIT50566.2022.9834443","author":[{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang","full_name":"Zhang, Yihan","first_name":"Yihan"},{"full_name":"Vatedka, Shashank","first_name":"Shashank","last_name":"Vatedka"}],"publication":"2022 IEEE International Symposium on Information Theory","date_published":"2022-08-03T00:00:00Z","department":[{"_id":"MaMo"}],"oa_version":"None","conference":{"start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"abstract":[{"text":"We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let 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.","lang":"eng"}],"volume":2022,"status":"public","date_updated":"2022-09-05T10:39:04Z","page":"3085-3090","quality_controlled":"1","year":"2022","date_created":"2022-09-04T22:02:05Z","scopus_import":"1","intvolume":"      2022","citation":{"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>.","ista":"Zhang Y, Vatedka S. 2022. Lower bounds for multiple packing. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 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>","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>.","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.","short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 3085–3090.","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>"},"publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"article_processing_charge":"No","day":"03"},{"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.","department":[{"_id":"MaMo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12016","month":"08","oa":1,"title":"Polar coded computing: The role of the scaling exponent","publication_status":"published","day":"03","citation":{"short":"D. Fathollahi, M. Mondelli, in:, 2022 IEEE International Symposium on Information Theory, IEEE, 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>","ista":"Fathollahi D, Mondelli M. 2022. Polar coded computing: The role of the scaling exponent. 2022 IEEE International Symposium on Information Theory. ISIT: Internation 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>","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.","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>."},"intvolume":"      2022","status":"public","abstract":[{"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.","lang":"eng"}],"external_id":{"arxiv":["2201.10082"]},"oa_version":"Preprint","conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory"},"date_published":"2022-08-03T00:00:00Z","publication":"2022 IEEE International Symposium on Information Theory","author":[{"full_name":"Fathollahi, Dorsa","first_name":"Dorsa","last_name":"Fathollahi"},{"last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020"}],"doi":"10.1109/ISIT50566.2022.9834712","publisher":"IEEE","language":[{"iso":"eng"}],"arxiv":1,"type":"conference","article_processing_charge":"No","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2201.10082","open_access":"1"}],"quality_controlled":"1","page":"2154-2159","year":"2022","date_created":"2022-09-04T22:02:05Z","date_updated":"2024-09-10T13:03:17Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"volume":2022},{"scopus_import":"1","citation":{"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>","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>.","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.","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.","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>.","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>"},"intvolume":"      2022","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"article_processing_charge":"No","day":"03","abstract":[{"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.","lang":"eng"}],"volume":2022,"status":"public","date_updated":"2023-02-13T09:00:14Z","page":"2535-2540","quality_controlled":"1","year":"2022","date_created":"2022-09-04T22:02:06Z","author":[{"last_name":"Yadav","full_name":"Yadav, Anuj Kumar","first_name":"Anuj Kumar"},{"last_name":"Alimohammadi","first_name":"Mohammadreza","full_name":"Alimohammadi, Mohammadreza"},{"last_name":"Zhang","first_name":"Yihan","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"first_name":"Amitalok J.","full_name":"Budkuley, Amitalok J.","last_name":"Budkuley"},{"full_name":"Jaggi, Sidharth","first_name":"Sidharth","last_name":"Jaggi"}],"publication":"2022 IEEE International Symposium on Information Theory","date_published":"2022-08-03T00:00:00Z","department":[{"_id":"MaMo"}],"oa_version":"None","conference":{"end_date":"2022-07-01","location":"Espoo, Finland","start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory"},"type":"conference","title":"New results on AVCs with omniscient and myopic adversaries","language":[{"iso":"eng"}],"publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12017","doi":"10.1109/ISIT50566.2022.9834632","month":"08"},{"date_updated":"2023-02-13T09:02:06Z","date_created":"2022-09-04T22:02:06Z","year":"2022","quality_controlled":"1","page":"1324-1329","volume":2022,"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"}],"status":"public","article_processing_charge":"No","day":"03","intvolume":"      2022","citation":{"short":"Y. Zhang, S. Vatedka, in:, 2022 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2022, pp. 1324–1329.","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>.","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>","ista":"Zhang Y, Vatedka S. 2022. Lower bounds on list decoding capacity using error exponents. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 1324–1329.","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."},"scopus_import":"1","publication_identifier":{"isbn":["9781665421591"],"issn":["2157-8095"]},"publisher":"Institute of Electrical and Electronics Engineers","doi":"10.1109/ISIT50566.2022.9834815","_id":"12018","month":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","language":[{"iso":"eng"}],"publication_status":"published","title":"Lower bounds on list decoding capacity using error exponents","department":[{"_id":"MaMo"}],"date_published":"2022-08-03T00:00:00Z","oa_version":"None","conference":{"start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"author":[{"first_name":"Yihan","full_name":"Zhang, Yihan","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"},{"first_name":"Shashank","full_name":"Vatedka, Shashank","last_name":"Vatedka"}],"publication":"2022 IEEE International Symposium on Information Theory"},{"abstract":[{"lang":"eng","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."}],"volume":2022,"status":"public","date_updated":"2023-02-13T09:02:18Z","year":"2022","date_created":"2022-09-04T22:02:07Z","quality_controlled":"1","page":"2553-2558","intvolume":"      2022","citation":{"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>","ista":"Polyanskii N, Zhang Y. 2022. List-decodable zero-rate codes for the Z-channel. 2022 IEEE International Symposium on Information Theory. ISIT: Internation Symposium on Information Theory vol. 2022, 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>.","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>","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>.","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."},"scopus_import":"1","publication_identifier":{"issn":["2157-8095"],"isbn":["9781665421591"]},"article_processing_charge":"No","day":"03","type":"conference","language":[{"iso":"eng"}],"publication_status":"published","title":"List-decodable zero-rate codes for the Z-channel","publisher":"Institute of Electrical and Electronics Engineers","doi":"10.1109/ISIT50566.2022.9834829","_id":"12019","month":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Nikita","full_name":"Polyanskii, Nikita","last_name":"Polyanskii"},{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","first_name":"Yihan","full_name":"Zhang, Yihan","last_name":"Zhang"}],"publication":"2022 IEEE International Symposium on Information Theory","department":[{"_id":"MaMo"}],"date_published":"2022-08-03T00:00:00Z","conference":{"start_date":"2022-06-26","name":"ISIT: Internation Symposium on Information Theory","end_date":"2022-07-01","location":"Espoo, Finland"},"oa_version":"None"},{"_id":"13146","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","oa":1,"title":"Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks","department":[{"_id":"MaMo"}],"acknowledgement":"The authors would like to thank the anonymous reviewers for their helpful comments. MM was partially supported by the 2019 Lopez-Loreta Prize. QN and GM acknowledge support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no 757983).","status":"public","abstract":[{"lang":"eng","text":"A recent line of work has analyzed the theoretical properties of deep neural networks via the Neural Tangent Kernel (NTK). In particular, the smallest eigenvalue of the NTK has been related to the memorization capacity, the global convergence of gradient descent algorithms and the generalization of deep nets. However, existing results either provide bounds in the two-layer setting or assume that the spectrum of the NTK matrices is bounded away from 0 for multi-layer networks. In this paper, we provide tight bounds on the smallest eigenvalue of NTK matrices for deep ReLU nets, both in the limiting case of infinite widths and for finite widths. In the finite-width setting, the network architectures we consider are fairly general: we require the existence of a wide layer with roughly order of N neurons, N being the number of data samples; and the scaling of the remaining layer widths is arbitrary (up to logarithmic factors). To obtain our results, we analyze various quantities of independent interest: we give lower bounds on the smallest singular value of hidden feature matrices, and upper bounds on the Lipschitz constant of input-output feature maps."}],"day":"01","has_accepted_license":"1","intvolume":"       139","citation":{"ista":"Nguyen Q, Mondelli M, Montufar G. 2021. Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning vol. 139, 8119–8129.","apa":"Nguyen, Q., Mondelli, M., &#38; Montufar, G. (2021). Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 8119–8129). Virtual: ML Research Press.","chicago":"Nguyen, Quynh, Marco Mondelli, and Guido Montufar. “Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:8119–29. ML Research Press, 2021.","mla":"Nguyen, Quynh, et al. “Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 8119–29.","ieee":"Q. Nguyen, M. Mondelli, and G. Montufar, “Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 8119–8129.","short":"Q. Nguyen, M. Mondelli, G. Montufar, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 8119–8129.","ama":"Nguyen Q, Mondelli M, Montufar G. Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:8119-8129."},"publisher":"ML Research Press","language":[{"iso":"eng"}],"arxiv":1,"type":"conference","file_date_updated":"2023-06-19T10:49:12Z","oa_version":"Published Version","external_id":{"arxiv":["2012.11654"]},"conference":{"name":"International Conference on Machine Learning","start_date":"2021-07-18","location":"Virtual","end_date":"2021-07-24"},"date_published":"2021-07-01T00:00:00Z","publication":"Proceedings of the 38th International Conference on Machine Learning","author":[{"first_name":"Quynh","full_name":"Nguyen, Quynh","last_name":"Nguyen"},{"full_name":"Mondelli, Marco","first_name":"Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Montufar, Guido","first_name":"Guido","last_name":"Montufar"}],"ddc":["000"],"year":"2021","date_created":"2023-06-18T22:00:48Z","page":"8119-8129","quality_controlled":"1","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"date_updated":"2024-09-10T13:03:17Z","file":[{"file_name":"2021_PMLR_Nguyen.pdf","file_id":"13155","content_type":"application/pdf","date_created":"2023-06-19T10:49:12Z","date_updated":"2023-06-19T10:49:12Z","access_level":"open_access","success":1,"relation":"main_file","checksum":"19489cf5e16a0596b1f92e317d97c9b0","file_size":591332,"creator":"dernst"}],"volume":139,"article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_identifier":{"isbn":["9781713845065"],"eissn":["2640-3498"]},"scopus_import":"1"},{"publisher":"IEEE","doi":"10.1109/TIT.2020.3038806","type":"journal_article","language":[{"iso":"eng"}],"arxiv":1,"date_published":"2021-09-01T00:00:00Z","external_id":{"arxiv":["1711.01339"]},"oa_version":"Preprint","author":[{"full_name":"Fazeli, Arman","first_name":"Arman","last_name":"Fazeli"},{"last_name":"Hassani","full_name":"Hassani, Hamed","first_name":"Hamed"},{"last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020"},{"full_name":"Vardy, Alexander","first_name":"Alexander","last_name":"Vardy"}],"publication":"IEEE Transactions on Information Theory","issue":"9","date_updated":"2024-03-07T12:18:50Z","quality_controlled":"1","page":"5693-5710","year":"2021","date_created":"2021-01-10T23:01:18Z","volume":67,"article_processing_charge":"No","scopus_import":"1","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"9002","month":"09","article_type":"original","title":"Binary linear codes with optimal scaling: Polar codes with large kernels","related_material":{"record":[{"id":"6665","relation":"earlier_version","status":"public"}]},"publication_status":"published","department":[{"_id":"MaMo"}],"abstract":[{"lang":"eng","text":" We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε>0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ=2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2×2 kernel) on the BEC is μ=3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ×ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ(ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ(ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(nlogn)."}],"status":"public","day":"01","intvolume":"        67","citation":{"ista":"Fazeli A, Hassani H, Mondelli M, Vardy A. 2021. Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory. 67(9), 5693–5710.","chicago":"Fazeli, Arman, Hamed Hassani, Marco Mondelli, and Alexander Vardy. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2021. <a href=\"https://doi.org/10.1109/TIT.2020.3038806\">https://doi.org/10.1109/TIT.2020.3038806</a>.","apa":"Fazeli, A., Hassani, H., Mondelli, M., &#38; Vardy, A. (2021). Binary linear codes with optimal scaling: Polar codes with large kernels. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2020.3038806\">https://doi.org/10.1109/TIT.2020.3038806</a>","ieee":"A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary linear codes with optimal scaling: Polar codes with large kernels,” <i>IEEE Transactions on Information Theory</i>, vol. 67, no. 9. IEEE, pp. 5693–5710, 2021.","mla":"Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” <i>IEEE Transactions on Information Theory</i>, vol. 67, no. 9, IEEE, 2021, pp. 5693–710, doi:<a href=\"https://doi.org/10.1109/TIT.2020.3038806\">10.1109/TIT.2020.3038806</a>.","short":"A. Fazeli, H. Hassani, M. Mondelli, A. Vardy, IEEE Transactions on Information Theory 67 (2021) 5693–5710.","ama":"Fazeli A, Hassani H, Mondelli M, Vardy A. Binary linear codes with optimal scaling: Polar codes with large kernels. <i>IEEE Transactions on Information Theory</i>. 2021;67(9):5693-5710. doi:<a href=\"https://doi.org/10.1109/TIT.2020.3038806\">10.1109/TIT.2020.3038806</a>"}},{"publication_identifier":{"eissn":["15582248"],"issn":["15361276"]},"main_file_link":[{"url":"https://arxiv.org/abs/1909.04892","open_access":"1"}],"scopus_import":"1","article_processing_charge":"No","isi":1,"volume":20,"date_created":"2021-01-31T23:01:21Z","year":"2021","quality_controlled":"1","page":"18-27","date_updated":"2023-08-07T13:36:25Z","publication":"IEEE Transactions on Wireless Communications","issue":"1","author":[{"last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020"},{"last_name":"Hashemi","first_name":"Seyyed Ali","full_name":"Hashemi, Seyyed Ali"},{"last_name":"Cioffi","first_name":"John M.","full_name":"Cioffi, John M."},{"first_name":"Andrea","full_name":"Goldsmith, Andrea","last_name":"Goldsmith"}],"external_id":{"arxiv":["1909.04892"],"isi":["000607808800002"]},"oa_version":"Preprint","date_published":"2021-01-01T00:00:00Z","arxiv":1,"language":[{"iso":"eng"}],"type":"journal_article","doi":"10.1109/TWC.2020.3022922","publisher":"IEEE","citation":{"ista":"Mondelli M, Hashemi SA, Cioffi JM, Goldsmith A. 2021. Sublinear latency for simplified successive cancellation decoding of polar codes. IEEE Transactions on Wireless Communications. 20(1), 18–27.","chicago":"Mondelli, Marco, Seyyed Ali Hashemi, John M. Cioffi, and Andrea Goldsmith. “Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes.” <i>IEEE Transactions on Wireless Communications</i>. IEEE, 2021. <a href=\"https://doi.org/10.1109/TWC.2020.3022922\">https://doi.org/10.1109/TWC.2020.3022922</a>.","apa":"Mondelli, M., Hashemi, S. A., Cioffi, J. M., &#38; Goldsmith, A. (2021). Sublinear latency for simplified successive cancellation decoding of polar codes. <i>IEEE Transactions on Wireless Communications</i>. IEEE. <a href=\"https://doi.org/10.1109/TWC.2020.3022922\">https://doi.org/10.1109/TWC.2020.3022922</a>","mla":"Mondelli, Marco, et al. “Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes.” <i>IEEE Transactions on Wireless Communications</i>, vol. 20, no. 1, IEEE, 2021, pp. 18–27, doi:<a href=\"https://doi.org/10.1109/TWC.2020.3022922\">10.1109/TWC.2020.3022922</a>.","ieee":"M. Mondelli, S. A. Hashemi, J. M. Cioffi, and A. Goldsmith, “Sublinear latency for simplified successive cancellation decoding of polar codes,” <i>IEEE Transactions on Wireless Communications</i>, vol. 20, no. 1. IEEE, pp. 18–27, 2021.","short":"M. Mondelli, S.A. Hashemi, J.M. Cioffi, A. Goldsmith, IEEE Transactions on Wireless Communications 20 (2021) 18–27.","ama":"Mondelli M, Hashemi SA, Cioffi JM, Goldsmith A. Sublinear latency for simplified successive cancellation decoding of polar codes. <i>IEEE Transactions on Wireless Communications</i>. 2021;20(1):18-27. doi:<a href=\"https://doi.org/10.1109/TWC.2020.3022922\">10.1109/TWC.2020.3022922</a>"},"intvolume":"        20","day":"01","status":"public","abstract":[{"text":"This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1−1/μ) , where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 or 1.","lang":"eng"}],"department":[{"_id":"MaMo"}],"acknowledgement":"M. Mondelli was partially supported by grants NSF DMS-1613091, CCF-1714305, IIS-1741162, and ONR N00014-18-1-2729. S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and by Huawei. The authors would like to thank the anonymous reviewers for their comments that helped improving the quality of the manuscript.","publication_status":"published","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"8536"}]},"title":"Sublinear latency for simplified successive cancellation decoding of polar codes","oa":1,"article_type":"original","month":"01","_id":"9047","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"article_processing_charge":"No","publication_identifier":{"issn":["2157-8095"],"isbn":["978-1-5386-8210-4"],"eisbn":["978-1-5386-8209-8"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.13378"}],"scopus_import":"1","year":"2021","date_created":"2021-09-27T14:33:14Z","quality_controlled":"1","page":"2369-2374","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"date_updated":"2024-09-10T13:03:18Z","isi":1,"oa_version":"Preprint","external_id":{"isi":["000701502202078"],"arxiv":["2012.13378"]},"conference":{"end_date":"2021-07-20","location":"Melbourne, Australia","start_date":"2021-07-12","name":"ISIT: International Symposium on Information Theory"},"date_published":"2021-09-01T00:00:00Z","publication":"2021 IEEE International Symposium on Information Theory","author":[{"last_name":"Hashemi","first_name":"Seyyed Ali","full_name":"Hashemi, Seyyed Ali"},{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco"},{"last_name":"Fazeli","first_name":"Arman","full_name":"Fazeli, Arman"},{"last_name":"Vardy","first_name":"Alexander","full_name":"Vardy, Alexander"},{"full_name":"Cioffi, John","first_name":"John","last_name":"Cioffi"},{"last_name":"Goldsmith","full_name":"Goldsmith, Andrea","first_name":"Andrea"}],"doi":"10.1109/ISIT45174.2021.9518153","publisher":"Institute of Electrical and Electronics Engineers","arxiv":1,"language":[{"iso":"eng"}],"type":"conference","day":"01","citation":{"ista":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 2369–2374.","chicago":"Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” In <i>2021 IEEE International Symposium on Information Theory</i>, 2369–74. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>.","apa":"Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., &#38; Goldsmith, A. (2021). Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In <i>2021 IEEE International Symposium on Information Theory</i> (pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>","ieee":"S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith, “Parallelism versus latency in simplified successive-cancellation decoding of polar codes,” in <i>2021 IEEE International Symposium on Information Theory</i>, Melbourne, Australia, 2021, pp. 2369–2374.","mla":"Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74, doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>.","short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, in:, 2021 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–2374.","ama":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In: <i>2021 IEEE International Symposium on Information Theory</i>. Institute of Electrical and Electronics Engineers; 2021:2369-2374. doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>"},"status":"public","abstract":[{"text":"This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.","lang":"eng"}],"department":[{"_id":"MaMo"}],"acknowledgement":"S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council\r\nof Canada (NSERC) and by Huawei. M. Mondelli is partially supported by the 2019 Lopez-Loreta Prize. A. Fazeli and A. Vardy were supported in part by the National Science Foundation under Grant CCF-1764104.","_id":"10053","month":"09","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","oa":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"10364"}]},"title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes"},{"day":"17","has_accepted_license":"1","keyword":["Applied Mathematics","Computational Theory and Mathematics","Computational Mathematics","Analysis"],"citation":{"short":"M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational Mathematics (2021).","ama":"Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear and spectral estimators for generalized linear models. <i>Foundations of Computational Mathematics</i>. 2021. doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">10.1007/s10208-021-09531-x</a>","ista":"Mondelli M, Thrampoulidis C, Venkataramanan R. 2021. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics.","apa":"Mondelli, M., Thrampoulidis, C., &#38; Venkataramanan, R. (2021). Optimal combination of linear and spectral estimators for generalized linear models. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-021-09531-x\">https://doi.org/10.1007/s10208-021-09531-x</a>","chicago":"Mondelli, Marco, Christos Thrampoulidis, and Ramji Venkataramanan. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” <i>Foundations of Computational Mathematics</i>. Springer, 2021. <a href=\"https://doi.org/10.1007/s10208-021-09531-x\">https://doi.org/10.1007/s10208-021-09531-x</a>.","ieee":"M. Mondelli, C. Thrampoulidis, and R. Venkataramanan, “Optimal combination of linear and spectral estimators for generalized linear models,” <i>Foundations of Computational Mathematics</i>. Springer, 2021.","mla":"Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” <i>Foundations of Computational Mathematics</i>, Springer, 2021, doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">10.1007/s10208-021-09531-x</a>."},"status":"public","abstract":[{"text":"We study the problem of recovering an unknown signal 𝑥𝑥 given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator 𝑥𝑥^L and a spectral estimator 𝑥𝑥^s. The former is a data-dependent linear combination of the columns of the measurement matrix, and its analysis is quite simple. The latter is the principal eigenvector of a data-dependent matrix, and a recent line of work has studied its performance. In this paper, we show how to optimally combine 𝑥𝑥^L and 𝑥𝑥^s. At the heart of our analysis is the exact characterization of the empirical joint distribution of (𝑥𝑥,𝑥𝑥^L,𝑥𝑥^s) in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of 𝑥𝑥^L and 𝑥𝑥^s, given the limiting distribution of the signal 𝑥𝑥. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form 𝜃𝑥𝑥^L+𝑥𝑥^s and we derive the optimal combination coefficient. In order to establish the limiting distribution of (𝑥𝑥,𝑥𝑥^L,𝑥𝑥^s), we design and analyze an approximate message passing algorithm whose iterates give 𝑥𝑥^L and approach 𝑥𝑥^s. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately.","lang":"eng"}],"department":[{"_id":"MaMo"}],"acknowledgement":"M. Mondelli would like to thank Andrea Montanari for helpful discussions. All the authors would like to thank the anonymous reviewers for their helpful comments.","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"10211","month":"08","oa":1,"title":"Optimal combination of linear and spectral estimators for generalized linear models","publication_status":"published","article_type":"original","article_processing_charge":"Yes (via OA deal)","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"scopus_import":"1","quality_controlled":"1","date_created":"2021-11-03T10:59:08Z","year":"2021","date_updated":"2023-09-05T14:13:57Z","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"isi":1,"file":[{"file_size":2305731,"creator":"alisjak","relation":"main_file","checksum":"9ea12dd8045a0678000a3a59295221cb","content_type":"application/pdf","file_id":"10542","date_created":"2021-12-13T15:47:54Z","success":1,"date_updated":"2021-12-13T15:47:54Z","access_level":"open_access","file_name":"2021_Springer_Mondelli.pdf"}],"oa_version":"Published Version","external_id":{"isi":["000685721000001"],"arxiv":["2008.03326"]},"date_published":"2021-08-17T00:00:00Z","publication":"Foundations of Computational Mathematics","ddc":["510"],"author":[{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","full_name":"Mondelli, Marco","last_name":"Mondelli"},{"first_name":"Christos","full_name":"Thrampoulidis, Christos","last_name":"Thrampoulidis"},{"first_name":"Ramji","full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan"}],"doi":"10.1007/s10208-021-09531-x","publisher":"Springer","language":[{"iso":"eng"}],"arxiv":1,"file_date_updated":"2021-12-13T15:47:54Z","type":"journal_article"},{"oa_version":"Preprint","conference":{"end_date":"2021-12-14","location":"Virtual","start_date":"2021-12-06","name":"NeurIPS: Neural Information Processing Systems"},"external_id":{"arxiv":["2106.02356"]},"date_published":"2021-12-01T00:00:00Z","publication":"35th Conference on Neural Information Processing Systems","author":[{"first_name":"Marco","full_name":"Mondelli, Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Venkataramanan, Ramji","first_name":"Ramji","last_name":"Venkataramanan"}],"publisher":"Neural Information Processing Systems Foundation","arxiv":1,"language":[{"iso":"eng"}],"type":"conference","article_processing_charge":"No","publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2106.02356"}],"page":"29616-29629","quality_controlled":"1","date_created":"2022-01-03T10:50:02Z","year":"2021","date_updated":"2024-09-10T13:03:19Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"volume":35,"department":[{"_id":"MaMo"}],"acknowledgement":"M. Mondelli would like to thank László Erdős for helpful discussions. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R. Venkataramanan was partially supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1.\r\n","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"12","_id":"10593","title":"PCA initialization for approximate message passing in rotationally invariant models","oa":1,"publication_status":"published","day":"01","citation":{"short":"M. Mondelli, R. Venkataramanan, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 29616–29629.","ama":"Mondelli M, Venkataramanan R. PCA initialization for approximate message passing in rotationally invariant models. In: <i>35th Conference on Neural Information Processing Systems</i>. Vol 35. Neural Information Processing Systems Foundation; 2021:29616-29629.","ista":"Mondelli M, Venkataramanan R. 2021. PCA initialization for approximate message passing in rotationally invariant models. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems vol. 35, 29616–29629.","chicago":"Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate Message Passing in Rotationally Invariant Models.” In <i>35th Conference on Neural Information Processing Systems</i>, 35:29616–29. Neural Information Processing Systems Foundation, 2021.","apa":"Mondelli, M., &#38; Venkataramanan, R. (2021). PCA initialization for approximate message passing in rotationally invariant models. In <i>35th Conference on Neural Information Processing Systems</i> (Vol. 35, pp. 29616–29629). Virtual: Neural Information Processing Systems Foundation.","mla":"Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate Message Passing in Rotationally Invariant Models.” <i>35th Conference on Neural Information Processing Systems</i>, vol. 35, Neural Information Processing Systems Foundation, 2021, pp. 29616–29.","ieee":"M. Mondelli and R. Venkataramanan, “PCA initialization for approximate message passing in rotationally invariant models,” in <i>35th Conference on Neural Information Processing Systems</i>, Virtual, 2021, vol. 35, pp. 29616–29629."},"intvolume":"        35","status":"public","abstract":[{"text":"We study the problem of estimating a rank-$1$ signal in the presence of rotationally invariant noise-a class of perturbations more general than Gaussian noise. Principal Component Analysis (PCA) provides a natural estimator, and sharp results on its performance have been obtained in the high-dimensional regime. Recently, an Approximate Message Passing (AMP) algorithm has been proposed as an alternative estimator with the potential to improve the accuracy of PCA. However, the existing analysis of AMP requires an initialization that is both correlated with the signal and independent of the noise, which is often unrealistic in practice. In this work, we combine the two methods, and propose to initialize AMP with PCA. Our main result is a rigorous asymptotic characterization of the performance of this estimator. Both the AMP algorithm and its analysis differ from those previously derived in the Gaussian setting: at every iteration, our AMP algorithm requires a specific term to account for PCA initialization, while in the Gaussian case, PCA initialization affects only the first iteration of AMP. The proof is based on a two-phase artificial AMP that first approximates the PCA estimator and then mimics the true AMP. Our numerical simulations show an excellent agreement between AMP results and theoretical predictions, and suggest an interesting open direction on achieving Bayes-optimal performance.","lang":"eng"}]},{"volume":35,"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"date_updated":"2024-09-10T13:03:19Z","year":"2021","date_created":"2022-01-03T10:56:20Z","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.09671"}],"publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"article_processing_charge":"No","type":"conference","language":[{"iso":"eng"}],"arxiv":1,"publisher":"Neural Information Processing Systems Foundation","author":[{"first_name":"Quynh","full_name":"Nguyen, Quynh","last_name":"Nguyen"},{"full_name":"Bréchet, Pierre","first_name":"Pierre","last_name":"Bréchet"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","full_name":"Mondelli, Marco","first_name":"Marco","last_name":"Mondelli"}],"publication":"35th Conference on Neural Information Processing Systems","date_published":"2021-12-01T00:00:00Z","conference":{"location":"Virtual","end_date":"2021-12-14","name":"35th Conference on Neural Information Processing Systems","start_date":"2021-12-06"},"oa_version":"Preprint","external_id":{"arxiv":["2102.09671"]},"abstract":[{"lang":"eng","text":"The question of how and why the phenomenon of mode connectivity occurs in training deep neural networks has gained remarkable attention in the research community. From a theoretical perspective, two possible explanations have been proposed: (i) the loss function has connected sublevel sets, and (ii) the solutions found by stochastic gradient descent are dropout stable. While these explanations provide insights into the phenomenon, their assumptions are not always satisfied in practice. In particular, the first approach requires the network to have one layer with order of N neurons (N being the number of training samples), while the second one requires the loss to be almost invariant after removing half of the neurons at each layer (up to some rescaling of the remaining ones). In this work, we improve both conditions by exploiting the quality of the features at every intermediate layer together with a milder over-parameterization condition. More specifically, we show that: (i) under generic assumptions on the features of intermediate layers, it suffices that the last two hidden layers have order of N−−√ neurons, and (ii) if subsets of features at each layer are linearly separable, then no over-parameterization is needed to show the connectivity. Our experiments confirm that the proposed condition ensures the connectivity of solutions found by stochastic gradient descent, even in settings where the previous requirements do not hold."}],"status":"public","intvolume":"        35","citation":{"ieee":"Q. Nguyen, P. Bréchet, and M. Mondelli, “When are solutions connected in deep networks?,” in <i>35th Conference on Neural Information Processing Systems</i>, Virtual, 2021, vol. 35.","mla":"Nguyen, Quynh, et al. “When Are Solutions Connected in Deep Networks?” <i>35th Conference on Neural Information Processing Systems</i>, vol. 35, Neural Information Processing Systems Foundation, 2021.","chicago":"Nguyen, Quynh, Pierre Bréchet, and Marco Mondelli. “When Are Solutions Connected in Deep Networks?” In <i>35th Conference on Neural Information Processing Systems</i>, Vol. 35. Neural Information Processing Systems Foundation, 2021.","apa":"Nguyen, Q., Bréchet, P., &#38; Mondelli, M. (2021). When are solutions connected in deep networks? In <i>35th Conference on Neural Information Processing Systems</i> (Vol. 35). Virtual: Neural Information Processing Systems Foundation.","ista":"Nguyen Q, Bréchet P, Mondelli M. 2021. When are solutions connected in deep networks? 35th Conference on Neural Information Processing Systems. 35th Conference on Neural Information Processing Systems vol. 35.","ama":"Nguyen Q, Bréchet P, Mondelli M. When are solutions connected in deep networks? In: <i>35th Conference on Neural Information Processing Systems</i>. Vol 35. Neural Information Processing Systems Foundation; 2021.","short":"Q. Nguyen, P. Bréchet, M. Mondelli, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021."},"day":"01","publication_status":"published","title":"When are solutions connected in deep networks?","oa":1,"_id":"10594","month":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"MaMo"}],"acknowledgement":"MM was partially supported by the 2019 Lopez-Loreta Prize. QN and PB acknowledge support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no 757983)."}]