[{"author":[{"first_name":"Mohammad Hossein","last_name":"Amani","full_name":"Amani, Mohammad Hossein"},{"full_name":"Bombari, Simone","id":"ca726dda-de17-11ea-bc14-f9da834f63aa","first_name":"Simone","last_name":"Bombari"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"full_name":"Pukdee, Rattana","last_name":"Pukdee","first_name":"Rattana"},{"last_name":"Rini","first_name":"Stefano","full_name":"Rini, Stefano"}],"oa_version":"Preprint","conference":{"location":"Mumbai, India","start_date":"2022-11-01","end_date":"2022-11-09","name":"ITW: Information Theory Workshop"},"abstract":[{"text":"In this paper, we study the compression of a target two-layer neural network with N nodes into a compressed network with M<N nodes. More precisely, we consider the setting in which the weights of the target network are i.i.d. sub-Gaussian, and we minimize the population L_2 loss between the outputs of the target and of the compressed network, under the assumption of Gaussian inputs. By using tools from high-dimensional probability, we show that this non-convex problem can be simplified when the target network is sufficiently over-parameterized, and provide the error rate of this approximation as a function of the input dimension and N. In this mean-field limit, the simplified objective, as well as the optimal weights of the compressed network, does not depend on the realization of the target network, but only on expected scaling factors. Furthermore, for networks with ReLU activation, we conjecture that the optimum of the simplified optimization problem is achieved by taking weights on the Equiangular Tight Frame (ETF), while the scaling of the weights and the orientation of the ETF depend on the parameters of the target network. Numerical evidence is provided to support this conjecture.","lang":"eng"}],"citation":{"ista":"Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. 2022. Sharp asymptotics on the compression of two-layer neural networks. IEEE Information Theory Workshop., 588–593.","chicago":"Amani, Mohammad Hossein, Simone Bombari, Marco Mondelli, Rattana Pukdee, and Stefano Rini. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.” <i>IEEE Information Theory Workshop</i>. IEEE, 2022. <a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">https://doi.org/10.1109/ITW54588.2022.9965870</a>.","mla":"Amani, Mohammad Hossein, et al. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.” <i>IEEE Information Theory Workshop</i>, IEEE, 2022, pp. 588–93, doi:<a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">10.1109/ITW54588.2022.9965870</a>.","ieee":"M. H. Amani, S. Bombari, M. Mondelli, R. Pukdee, and S. Rini, “Sharp asymptotics on the compression of two-layer neural networks,” <i>IEEE Information Theory Workshop</i>. IEEE, pp. 588–593, 2022.","short":"M.H. Amani, S. Bombari, M. Mondelli, R. Pukdee, S. Rini, IEEE Information Theory Workshop (2022) 588–593.","apa":"Amani, M. H., Bombari, S., Mondelli, M., Pukdee, R., &#38; Rini, S. (2022). Sharp asymptotics on the compression of two-layer neural networks. <i>IEEE Information Theory Workshop</i>. Mumbai, India: IEEE. <a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">https://doi.org/10.1109/ITW54588.2022.9965870</a>","ama":"Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. Sharp asymptotics on the compression of two-layer neural networks. <i>IEEE Information Theory Workshop</i>. 2022:588-593. doi:<a href=\"https://doi.org/10.1109/ITW54588.2022.9965870\">10.1109/ITW54588.2022.9965870</a>"},"publication_identifier":{"isbn":["9781665483414"]},"type":"journal_article","arxiv":1,"date_updated":"2025-09-10T09:53:31Z","year":"2022","title":"Sharp asymptotics on the compression of two-layer neural networks","date_published":"2022-11-16T00:00:00Z","article_type":"original","language":[{"iso":"eng"}],"scopus_import":"1","month":"11","doi":"10.1109/ITW54588.2022.9965870","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2205.08199"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2023-02-10T13:47:56Z","day":"16","publication_status":"published","publisher":"IEEE","department":[{"_id":"MaMo"}],"page":"588-593","oa":1,"publication":"IEEE Information Theory Workshop","status":"public","quality_controlled":"1","external_id":{"arxiv":["2205.08199"],"isi":["000904341100099"]},"article_processing_charge":"No","_id":"12538","isi":1},{"quality_controlled":"1","ddc":["000"],"article_processing_charge":"No","_id":"12540","acknowledgement":"The authors would like to thank the anonymous reviewers for their helpful comments. KK and MM were partially supported by the 2019 Lopez-Loreta Prize.","department":[{"_id":"MaMo"}],"publisher":"ML Research Press","oa":1,"file":[{"checksum":"67436eb0a660789514cdf9db79e84683","file_size":2341343,"date_created":"2023-02-13T10:53:11Z","file_name":"2022_PMLR_Venkataramanan.pdf","success":1,"file_id":"12547","relation":"main_file","creator":"dernst","date_updated":"2023-02-13T10:53:11Z","content_type":"application/pdf","access_level":"open_access"}],"status":"public","publication":"Proceedings of the 39th International Conference on Machine Learning","publication_status":"published","intvolume":"       162","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2023-02-10T13:49:04Z","corr_author":"1","has_accepted_license":"1","file_date_updated":"2023-02-13T10:53:11Z","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"volume":162,"date_published":"2022-01-01T00:00:00Z","language":[{"iso":"eng"}],"type":"conference","date_updated":"2025-04-15T07:50:16Z","year":"2022","title":"Estimation in rotationally invariant generalized linear models via approximate message passing","author":[{"full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan","first_name":"Ramji"},{"last_name":"Kögler","first_name":"Kevin","id":"94ec913c-dc85-11ea-9058-e5051ab2428b","full_name":"Kögler, Kevin"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"conference":{"name":"ICML: International Conference on Machine Learning","end_date":"2022-07-23","location":"Baltimore, MD, United States","start_date":"2022-07-17"},"oa_version":"Published Version","citation":{"short":"R. Venkataramanan, K. Kögler, M. Mondelli, in:, Proceedings of the 39th International Conference on Machine Learning, ML Research Press, 2022.","ista":"Venkataramanan R, Kögler K, Mondelli M. 2022. Estimation in rotationally invariant generalized linear models via approximate message passing. Proceedings of the 39th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 162, 22.","chicago":"Venkataramanan, Ramji, Kevin Kögler, and Marco Mondelli. “Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing.” In <i>Proceedings of the 39th International Conference on Machine Learning</i>, Vol. 162. ML Research Press, 2022.","mla":"Venkataramanan, Ramji, et al. “Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing.” <i>Proceedings of the 39th International Conference on Machine Learning</i>, vol. 162, 22, ML Research Press, 2022.","ieee":"R. Venkataramanan, K. Kögler, and M. Mondelli, “Estimation in rotationally invariant generalized linear models via approximate message passing,” in <i>Proceedings of the 39th International Conference on Machine Learning</i>, Baltimore, MD, United States, 2022, vol. 162.","ama":"Venkataramanan R, Kögler K, Mondelli M. Estimation in rotationally invariant generalized linear models via approximate message passing. In: <i>Proceedings of the 39th International Conference on Machine Learning</i>. Vol 162. ML Research Press; 2022.","apa":"Venkataramanan, R., Kögler, K., &#38; Mondelli, M. (2022). Estimation in rotationally invariant generalized linear models via approximate message passing. In <i>Proceedings of the 39th International Conference on Machine Learning</i> (Vol. 162). Baltimore, MD, United States: ML Research Press."},"article_number":"22","abstract":[{"text":"We consider the problem of signal estimation in generalized linear models defined via rotationally invariant design matrices. Since these matrices can have an arbitrary spectral distribution, this model is well suited for capturing complex correlation structures which often arise in applications. We propose a novel family of approximate message passing (AMP) algorithms for signal estimation, and rigorously characterize their performance in the high-dimensional limit via a state evolution recursion. Our rotationally invariant AMP has complexity of the same order as the existing AMP derived under the restrictive assumption of a Gaussian design; our algorithm also recovers this existing AMP as a special case. Numerical results showcase a performance close to Vector AMP (which is conjectured to be Bayes-optimal in some settings), but obtained with a much lower complexity, as the proposed algorithm does not require a computationally expensive singular value decomposition.","lang":"eng"}]},{"publication":"arXiv","language":[{"iso":"eng"}],"status":"public","date_published":"2022-03-30T00:00:00Z","oa":1,"department":[{"_id":"GradSch"},{"_id":"MaMo"}],"_id":"12860","doi":"10.48550/arXiv.2203.16701","month":"03","article_processing_charge":"No","external_id":{"arxiv":["2203.16701"]},"date_created":"2023-04-23T16:11:48Z","day":"30","abstract":[{"lang":"eng","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."}],"citation":{"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>","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>","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>.","ieee":"S. Bombari <i>et al.</i>, “Towards differential relational privacy and its use in question answering,” <i>arXiv</i>. .","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>.","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.","short":"S. Bombari, A. Achille, Z. Wang, Y.-X. Wang, Y. Xie, K.Y. Singh, S. Appalaraju, V. Mahadevan, S. Soatto, ArXiv (n.d.)."},"article_number":"2203.16701","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","last_name":"Bombari","first_name":"Simone"},{"full_name":"Achille, Alessandro","first_name":"Alessandro","last_name":"Achille"},{"full_name":"Wang, Zijian","last_name":"Wang","first_name":"Zijian"},{"last_name":"Wang","first_name":"Yu-Xiang","full_name":"Wang, Yu-Xiang"},{"full_name":"Xie, Yusheng","last_name":"Xie","first_name":"Yusheng"},{"full_name":"Singh, Kunwar Yashraj","last_name":"Singh","first_name":"Kunwar Yashraj"},{"full_name":"Appalaraju, Srikar","first_name":"Srikar","last_name":"Appalaraju"},{"full_name":"Mahadevan, Vijay","first_name":"Vijay","last_name":"Mahadevan"},{"full_name":"Soatto, Stefano","first_name":"Stefano","last_name":"Soatto"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2203.16701"}],"title":"Towards differential relational privacy and its use in question answering","publication_status":"submitted","year":"2022","date_updated":"2023-04-25T07:34:49Z","arxiv":1,"type":"preprint"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2024-05-29T06:37:16Z","day":"01","publication_status":"published","intvolume":"        35","department":[{"_id":"MaMo"}],"publisher":"ML Research Press","file":[{"date_created":"2024-08-05T09:44:49Z","file_size":476307,"checksum":"05f6f9f8fc34e224e0cad045b9489030","file_name":"2022_NeurIPS_Zhang.pdf","success":1,"creator":"dernst","relation":"main_file","file_id":"17392","date_updated":"2024-08-05T09:44:49Z","content_type":"application/pdf","access_level":"open_access"}],"oa":1,"status":"public","alternative_title":["NeurIPS"],"publication":"36th Conference on Neural Information Processing Systems","quality_controlled":"1","external_id":{"arxiv":["2206.02455"]},"ddc":["000"],"article_processing_charge":"No","_id":"17086","acknowledgement":"Part of this work was done when YZ was a postdoc at Technion where he received funding from\r\nthe European Union’s Horizon 2020 research and innovation programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]. The work of of NW was supported in part by the Israel Science Foundation (ISF) under Grant 1782/22. NW is grateful to Guy Bresler for introducing him to this problem, for the initial ideas that led to this research, and for many helpful discussions on the topic.","author":[{"full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","first_name":"Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang"},{"full_name":"Weinberger, Nir","last_name":"Weinberger","first_name":"Nir"}],"conference":{"name":"NeurIPS: Neural Information Processing Systems","start_date":"2022-11-28","location":"New Orleans, LA, United States","end_date":"2022-12-09"},"oa_version":"Published Version","citation":{"apa":"Zhang, Y., &#38; Weinberger, N. (2022). Mean estimation in high-dimensional binary Markov Gaussian mixture models. In <i>36th Conference on Neural Information Processing Systems</i> (Vol. 35). New Orleans, LA, United States: ML Research Press.","ama":"Zhang Y, Weinberger N. Mean estimation in high-dimensional binary Markov Gaussian mixture models. In: <i>36th Conference on Neural Information Processing Systems</i>. Vol 35. ML Research Press; 2022.","chicago":"Zhang, Yihan, and Nir Weinberger. “Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models.” In <i>36th Conference on Neural Information Processing Systems</i>, Vol. 35. ML Research Press, 2022.","ista":"Zhang Y, Weinberger N. 2022. Mean estimation in high-dimensional binary Markov Gaussian mixture models. 36th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, NeurIPS, vol. 35.","ieee":"Y. Zhang and N. Weinberger, “Mean estimation in high-dimensional binary Markov Gaussian mixture models,” in <i>36th Conference on Neural Information Processing Systems</i>, New Orleans, LA, United States, 2022, vol. 35.","mla":"Zhang, Yihan, and Nir Weinberger. “Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models.” <i>36th Conference on Neural Information Processing Systems</i>, vol. 35, ML Research Press, 2022.","short":"Y. Zhang, N. Weinberger, in:, 36th Conference on Neural Information Processing Systems, ML Research Press, 2022."},"abstract":[{"text":"We consider a high-dimensional mean estimation problem over a binary hidden Markov model, which illuminates the interplay between memory in data, sample size, dimension, and signal strength in statistical inference. In this model, an estimator observes n samples of a d-dimensional parameter vector θ∗∈Rd, multiplied by a random sign Si (1≤i≤n), and corrupted by isotropic standard Gaussian noise. The sequence of signs {Si}i∈[n]∈{−1,1}n is drawn from a stationary homogeneous Markov chain with flip probability δ∈[0,1/2]. As δ varies, this model smoothly interpolates two well-studied models: the Gaussian Location Model for which δ=0 and the Gaussian Mixture Model for which δ=1/2. Assuming that the estimator knows δ, we establish a nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of ∥θ∗∥,δ,d,n. We then provide an upper bound to the case of estimating δ, assuming a (possibly inaccurate) knowledge of θ∗. The bound is proved to be tight when θ∗ is an accurately known constant. These results are then combined to an algorithm which estimates θ∗ with δ unknown a priori, and theoretical guarantees on its error are stated.","lang":"eng"}],"arxiv":1,"type":"conference","publication_identifier":{"isbn":["9781713871088"]},"date_updated":"2024-08-05T09:48:58Z","year":"2022","title":"Mean estimation in high-dimensional binary Markov Gaussian mixture models","corr_author":"1","has_accepted_license":"1","file_date_updated":"2024-08-05T09:44:49Z","date_published":"2022-12-01T00:00:00Z","volume":35,"language":[{"iso":"eng"}],"scopus_import":"1","month":"12"},{"language":[{"iso":"eng"}],"article_type":"original","date_published":"2022-10-01T00:00:00Z","volume":22,"file_date_updated":"2021-12-13T15:47:54Z","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"has_accepted_license":"1","doi":"10.1007/s10208-021-09531-x","month":"10","scopus_import":"1","citation":{"short":"M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational Mathematics 22 (2022) 1513–1566.","ista":"Mondelli M, Thrampoulidis C, Venkataramanan R. 2022. Optimal combination of linear and spectral estimators for generalized linear models. Foundations of Computational Mathematics. 22(5), 1513–1566.","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, 2022. <a href=\"https://doi.org/10.1007/s10208-021-09531-x\">https://doi.org/10.1007/s10208-021-09531-x</a>.","mla":"Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models.” <i>Foundations of Computational Mathematics</i>, vol. 22, no. 5, Springer, 2022, pp. 1513–66, doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">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>, vol. 22, no. 5. Springer, pp. 1513–1566, 2022.","ama":"Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear and spectral estimators for generalized linear models. <i>Foundations of Computational Mathematics</i>. 2022;22(5):1513-1566. doi:<a href=\"https://doi.org/10.1007/s10208-021-09531-x\">10.1007/s10208-021-09531-x</a>","apa":"Mondelli, M., Thrampoulidis, C., &#38; Venkataramanan, R. (2022). 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>"},"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"}],"oa_version":"Published Version","author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli"},{"first_name":"Christos","last_name":"Thrampoulidis","full_name":"Thrampoulidis, Christos"},{"full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan","first_name":"Ramji"}],"title":"Optimal combination of linear and spectral estimators for generalized linear models","year":"2022","date_updated":"2025-04-15T06:53:08Z","type":"journal_article","arxiv":1,"publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"status":"public","publication":"Foundations of Computational Mathematics","file":[{"file_name":"2021_Springer_Mondelli.pdf","file_size":2305731,"date_created":"2021-12-13T15:47:54Z","checksum":"9ea12dd8045a0678000a3a59295221cb","success":1,"creator":"alisjak","file_id":"10542","relation":"main_file","access_level":"open_access","date_updated":"2021-12-13T15:47:54Z","content_type":"application/pdf"}],"oa":1,"department":[{"_id":"MaMo"}],"page":"1513-1566","publisher":"Springer","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.","isi":1,"article_processing_charge":"Yes (via OA deal)","_id":"10211","quality_controlled":"1","external_id":{"arxiv":["2008.03326"],"isi":["000685721000001"]},"ddc":["510"],"date_created":"2021-11-03T10:59:08Z","day":"01","issue":"5","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","intvolume":"        22","keyword":["Applied Mathematics","Computational Theory and Mathematics","Computational Mathematics","Analysis"],"publication_status":"published"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"url":"https://arxiv.org/abs/2012.13378","open_access":"1"}],"date_created":"2021-11-28T23:01:29Z","day":"01","issue":"6","intvolume":"        21","publication_status":"published","oa":1,"publisher":"Institute of Electrical and Electronics Engineers","page":"3909-3920","department":[{"_id":"MaMo"}],"publication":"IEEE Transactions on Wireless Communications","status":"public","external_id":{"arxiv":["2012.13378"],"isi":["000809406400028"]},"quality_controlled":"1","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.","article_processing_charge":"No","_id":"10364","isi":1,"oa_version":"Preprint","author":[{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"},{"full_name":"Fazeli, Arman","first_name":"Arman","last_name":"Fazeli"},{"last_name":"Vardy","first_name":"Alexander","full_name":"Vardy, Alexander"},{"first_name":"John","last_name":"Cioffi","full_name":"Cioffi, John"},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"abstract":[{"lang":"eng","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."}],"citation":{"short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, IEEE Transactions on Wireless Communications 21 (2022) 3909–3920.","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.","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>","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>"},"date_updated":"2025-04-15T07:50:11Z","publication_identifier":{"issn":["1536-1276"],"eissn":["1558-2248"]},"type":"journal_article","arxiv":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10053"}]},"title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","year":"2022","volume":21,"date_published":"2022-06-01T00:00:00Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"language":[{"iso":"eng"}],"article_type":"original","scopus_import":"1","doi":"10.1109/TWC.2021.3125626","month":"06"},{"volume":35,"date_published":"2022-11-20T00:00:00Z","corr_author":"1","language":[{"iso":"eng"}],"scopus_import":"1","month":"11","oa_version":"Preprint","conference":{"location":"New Orleans, LA, United States","start_date":"2022-11-28","end_date":"2022-12-09","name":"NeurIPS: Neural Information Processing Systems"},"author":[{"first_name":"Jean","last_name":"Barbier","full_name":"Barbier, Jean"},{"last_name":"Hou","first_name":"TianQi","full_name":"Hou, TianQi"},{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Saenz, Manuel","first_name":"Manuel","last_name":"Saenz"}],"abstract":[{"text":"We consider the problem of estimating a rank-1 signal corrupted by structured rotationally invariant noise, and address the following question: how well do inference algorithms perform when the noise statistics is unknown and hence Gaussian noise is assumed? While the matched Bayes-optimal setting with unstructured noise is well understood, the analysis of this mismatched problem is only at its premises. In this paper, we make a step towards understanding the effect of the strong source of mismatch which is the noise statistics. Our main technical contribution is the rigorous analysis of a Bayes estimator and of an approximate message passing (AMP) algorithm, both of which incorrectly assume a Gaussian setup. The first result exploits the theory of spherical integrals and of low-rank matrix perturbations; the idea behind the second one is to design and analyze an artificial AMP which, by taking advantage of the flexibility in the denoisers, is able to \"correct\" the mismatch. Armed with these sharp asymptotic characterizations, we unveil a rich and often unexpected phenomenology. For example, despite AMP is in principle designed to efficiently compute the Bayes estimator, the former is outperformed by the latter in terms of mean-square error. We show that this performance gap is due to an incorrect estimation of the signal norm. In fact, when the SNR is large enough, the overlaps of the AMP and the Bayes estimator coincide, and they even match those of optimal estimators taking into account the structure of the noise.","lang":"eng"}],"citation":{"ista":"Barbier J, Hou T, Mondelli M, Saenz M. 2022. The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? 36th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 35.","chicago":"Barbier, Jean, TianQi Hou, Marco Mondelli, and Manuel Saenz. “The Price of Ignorance: How Much Does It Cost to Forget Noise Structure in Low-Rank Matrix Estimation?” In <i>36th Conference on Neural Information Processing Systems</i>, Vol. 35. Neural Information Processing Systems Foundation, 2022.","mla":"Barbier, Jean, et al. “The Price of Ignorance: How Much Does It Cost to Forget Noise Structure in Low-Rank Matrix Estimation?” <i>36th Conference on Neural Information Processing Systems</i>, vol. 35, Neural Information Processing Systems Foundation, 2022.","ieee":"J. Barbier, T. Hou, M. Mondelli, and M. Saenz, “The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation?,” in <i>36th Conference on Neural Information Processing Systems</i>, New Orleans, LA, United States, 2022, vol. 35.","short":"J. Barbier, T. Hou, M. Mondelli, M. Saenz, in:, 36th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2022.","apa":"Barbier, J., Hou, T., Mondelli, M., &#38; Saenz, M. (2022). The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? In <i>36th Conference on Neural Information Processing Systems</i> (Vol. 35). New Orleans, LA, United States: Neural Information Processing Systems Foundation.","ama":"Barbier J, Hou T, Mondelli M, Saenz M. The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation? In: <i>36th Conference on Neural Information Processing Systems</i>. Vol 35. Neural Information Processing Systems Foundation; 2022."},"date_updated":"2026-07-07T06:38:45Z","publication_identifier":{"issn":["1049-5258"],"isbn":["9781713871088"]},"type":"conference","arxiv":1,"title":"The price of ignorance: How much does it cost to forget noise structure in low-rank matrix estimation?","year":"2022","oa":1,"publisher":"Neural Information Processing Systems Foundation","department":[{"_id":"MaMo"}],"publication":"36th Conference on Neural Information Processing Systems","alternative_title":["Advances in Neural Information Processing Systems"],"status":"public","quality_controlled":"1","external_id":{"arxiv":["2205.10009"]},"das_tickbox":"1","acknowledgement":"M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. The authors acknowledge\r\ndiscussions with A. Krajenbrink, M. Robinson, A. Depope, N. Macris and F. Pourkamali.\r\n","_id":"12536","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2205.10009"}],"day":"20","date_created":"2023-02-10T13:45:41Z","intvolume":"        35","publication_status":"published"},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"issue":"130","day":"01","date_created":"2022-05-29T22:01:54Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_status":"published","intvolume":"        23","publication":"Journal of Machine Learning Research","status":"public","publisher":"Journal of Machine Learning Research","department":[{"_id":"MaMo"},{"_id":"DaAl"}],"page":"1-55","oa":1,"file":[{"access_level":"open_access","date_updated":"2022-05-30T08:22:55Z","content_type":"application/pdf","relation":"main_file","file_id":"11422","creator":"cchlebak","success":1,"file_name":"21-1365.pdf","checksum":"d4ff5d1affb34848b5c5e4002483fc62","date_created":"2022-05-30T08:22:55Z","file_size":1521701}],"_id":"11420","article_processing_charge":"No","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","ddc":["000"],"quality_controlled":"1","external_id":{"arxiv":["2111.02278"]},"abstract":[{"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.","lang":"eng"}],"citation":{"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.","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.","mla":"Shevchenko, Alexander, 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.","chicago":"Shevchenko, Alexander, 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.","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.","short":"A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research 23 (2022) 1–55."},"author":[{"last_name":"Shevchenko","first_name":"Aleksandr","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","full_name":"Shevchenko, Aleksandr"},{"full_name":"Kungurtsev, Vyacheslav","last_name":"Kungurtsev","first_name":"Vyacheslav"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"oa_version":"Published Version","year":"2022","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"17465"}],"link":[{"url":"https://www.jmlr.org/papers/v23/21-1365.html","relation":"other"}]},"title":"Mean-field analysis of piecewise linear solutions for wide ReLU networks","publication_identifier":{"eissn":["1533-7928"],"issn":["1532-4435"]},"type":"journal_article","arxiv":1,"date_updated":"2026-08-11T22:30:16Z","article_type":"original","language":[{"iso":"eng"}],"has_accepted_license":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"file_date_updated":"2022-05-30T08:22:55Z","corr_author":"1","date_published":"2022-04-01T00:00:00Z","volume":23,"month":"04","scopus_import":"1"},{"volume":139,"date_published":"2021-07-01T00:00:00Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"has_accepted_license":"1","file_date_updated":"2023-06-19T10:49:12Z","language":[{"iso":"eng"}],"scopus_import":"1","month":"07","oa_version":"Published Version","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2021-07-18","location":"Virtual","end_date":"2021-07-24"},"author":[{"full_name":"Nguyen, Quynh","first_name":"Quynh","last_name":"Nguyen"},{"last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"first_name":"Guido","last_name":"Montufar","full_name":"Montufar, Guido"}],"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."}],"citation":{"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.","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.","short":"Q. Nguyen, M. Mondelli, G. Montufar, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 8119–8129.","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.","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.","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.","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. ICML: International Conference on Machine Learning vol. 139, 8119–8129."},"date_updated":"2025-07-10T11:50:36Z","publication_identifier":{"isbn":["9781713845065"],"eissn":["2640-3498"]},"type":"conference","arxiv":1,"title":"Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks","year":"2021","oa":1,"file":[{"access_level":"open_access","content_type":"application/pdf","date_updated":"2023-06-19T10:49:12Z","creator":"dernst","file_id":"13155","relation":"main_file","success":1,"file_name":"2021_PMLR_Nguyen.pdf","date_created":"2023-06-19T10:49:12Z","file_size":591332,"checksum":"19489cf5e16a0596b1f92e317d97c9b0"}],"publisher":"ML Research Press","page":"8119-8129","department":[{"_id":"MaMo"}],"publication":"Proceedings of the 38th International Conference on Machine Learning","status":"public","ddc":["000"],"quality_controlled":"1","external_id":{"arxiv":["2012.11654"]},"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).","article_processing_charge":"No","_id":"13146","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","date_created":"2023-06-18T22:00:48Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"       139","publication_status":"published"},{"publisher":"IEEE","page":"1108-1119","department":[{"_id":"MaMo"}],"oa":1,"publication":"IEEE Journal on Selected Areas in Information Theory","status":"public","external_id":{"arxiv":["2102.09885"]},"quality_controlled":"1","_id":"15254","article_processing_charge":"No","acknowledgement":"The work of Rawad Bitar was supported in part by the Technical University of Munich—Institute for Advanced Studies, funded by the German Excellence Initiative and European Union Seventh Framework Programme under Grant 291763. The work of Sidharth Jaggi was supported by the Hong Kong UGC GRF under Grant 14304418, Grant 14300617, and Grant 14313116. The work of Yihan Zhang was supported by the European Union’s Horizon 2020 Research and Innovation Programme under Grant 682203-ERC-[Inf-Speed-Tradeoff]. Preliminary results were presented at IEEE International Symposium on information Theory (ISIT).","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2102.09885"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"4","date_created":"2024-03-31T22:01:13Z","day":"01","publication_status":"published","intvolume":"         2","date_published":"2021-12-01T00:00:00Z","volume":2,"article_type":"original","language":[{"iso":"eng"}],"scopus_import":"1","month":"12","doi":"10.1109/JSAIT.2021.3126474","author":[{"full_name":"Li, Sijie","last_name":"Li","first_name":"Sijie"},{"first_name":"Rawad","last_name":"Bitar","full_name":"Bitar, Rawad"},{"first_name":"Sidharth","last_name":"Jaggi","full_name":"Jaggi, Sidharth"},{"orcid":"0000-0002-6465-6258","first_name":"Yihan","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider the problem of reliable communication over a network containing a hidden myopic adversary who can eavesdrop on some zro links, jam some zwo links, and do both on some zrw links. We provide the first information-theoretically tight characterization of the optimal rate of communication possible under all possible settings of the tuple (zro,zwo,zrw) by providing a novel coding scheme/analysis for a subset of parameter regimes. In particular, our vanishing-error schemes bypass the Network Singleton Bound (which requires a zero-error recovery criteria) in a certain parameter regime where the capacity had been heretofore open. As a direct corollary we also obtain the capacity of the corresponding problem where information-theoretic secrecy against eavesdropping is required in addition to reliable communication."}],"citation":{"ama":"Li S, Bitar R, Jaggi S, Zhang Y. Network coding with myopic adversaries. <i>IEEE Journal on Selected Areas in Information Theory</i>. 2021;2(4):1108-1119. doi:<a href=\"https://doi.org/10.1109/JSAIT.2021.3126474\">10.1109/JSAIT.2021.3126474</a>","apa":"Li, S., Bitar, R., Jaggi, S., &#38; Zhang, Y. (2021). Network coding with myopic adversaries. <i>IEEE Journal on Selected Areas in Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/JSAIT.2021.3126474\">https://doi.org/10.1109/JSAIT.2021.3126474</a>","short":"S. Li, R. Bitar, S. Jaggi, Y. Zhang, IEEE Journal on Selected Areas in Information Theory 2 (2021) 1108–1119.","mla":"Li, Sijie, et al. “Network Coding with Myopic Adversaries.” <i>IEEE Journal on Selected Areas in Information Theory</i>, vol. 2, no. 4, IEEE, 2021, pp. 1108–19, doi:<a href=\"https://doi.org/10.1109/JSAIT.2021.3126474\">10.1109/JSAIT.2021.3126474</a>.","ieee":"S. Li, R. Bitar, S. Jaggi, and Y. Zhang, “Network coding with myopic adversaries,” <i>IEEE Journal on Selected Areas in Information Theory</i>, vol. 2, no. 4. IEEE, pp. 1108–1119, 2021.","ista":"Li S, Bitar R, Jaggi S, Zhang Y. 2021. Network coding with myopic adversaries. IEEE Journal on Selected Areas in Information Theory. 2(4), 1108–1119.","chicago":"Li, Sijie, Rawad Bitar, Sidharth Jaggi, and Yihan Zhang. “Network Coding with Myopic Adversaries.” <i>IEEE Journal on Selected Areas in Information Theory</i>. IEEE, 2021. <a href=\"https://doi.org/10.1109/JSAIT.2021.3126474\">https://doi.org/10.1109/JSAIT.2021.3126474</a>."},"publication_identifier":{"eissn":["2641-8770"]},"type":"journal_article","arxiv":1,"date_updated":"2024-04-02T08:31:59Z","year":"2021","title":"Network coding with myopic adversaries"},{"date_updated":"2025-04-15T07:50:11Z","arxiv":1,"type":"conference","publication_identifier":{"eisbn":["978-1-5386-8209-8"],"isbn":["978-1-5386-8210-4"],"issn":["2157-8095"]},"title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","related_material":{"record":[{"relation":"later_version","status":"public","id":"10364"}]},"year":"2021","conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2021-07-20","start_date":"2021-07-12","location":"Melbourne, Australia"},"oa_version":"Preprint","author":[{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"},{"full_name":"Fazeli, Arman","first_name":"Arman","last_name":"Fazeli"},{"first_name":"Alexander","last_name":"Vardy","full_name":"Vardy, Alexander"},{"last_name":"Cioffi","first_name":"John","full_name":"Cioffi, John"},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"citation":{"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.","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>.","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>.","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.","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>","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>"},"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"}],"scopus_import":"1","month":"09","doi":"10.1109/ISIT45174.2021.9518153","date_published":"2021-09-01T00:00:00Z","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"language":[{"iso":"eng"}],"publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.13378"}],"date_created":"2021-09-27T14:33:14Z","day":"01","external_id":{"arxiv":["2012.13378"],"isi":["000701502202078"]},"quality_controlled":"1","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.","isi":1,"_id":"10053","article_processing_charge":"No","oa":1,"page":"2369-2374","department":[{"_id":"MaMo"}],"publisher":"Institute of Electrical and Electronics Engineers","status":"public","publication":"2021 IEEE International Symposium on Information Theory"},{"language":[{"iso":"eng"}],"project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"corr_author":"1","date_published":"2021-12-01T00:00:00Z","volume":35,"month":"12","scopus_import":"1","abstract":[{"lang":"eng","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."}],"citation":{"short":"M. Mondelli, R. Venkataramanan, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 29616–29629.","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.","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.","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.","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."},"author":[{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Venkataramanan, Ramji","last_name":"Venkataramanan","first_name":"Ramji"}],"conference":{"name":"NeurIPS: Neural Information Processing Systems","location":"Virtual","start_date":"2021-12-06","end_date":"2021-12-14"},"oa_version":"Preprint","year":"2021","title":"PCA initialization for approximate message passing in rotationally invariant models","publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"arxiv":1,"type":"conference","date_updated":"2025-04-15T07:50:11Z","publication":"35th Conference on Neural Information Processing Systems","status":"public","publisher":"Neural Information Processing Systems Foundation","department":[{"_id":"MaMo"}],"page":"29616-29629","oa":1,"article_processing_charge":"No","_id":"10593","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","external_id":{"arxiv":["2106.02356"]},"quality_controlled":"1","date_created":"2022-01-03T10:50:02Z","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/2106.02356","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","intvolume":"        35"},{"quality_controlled":"1","external_id":{"arxiv":["2102.09671"]},"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).","_id":"10594","article_processing_charge":"No","oa":1,"publisher":"Neural Information Processing Systems Foundation","department":[{"_id":"MaMo"}],"publication":"35th Conference on Neural Information Processing Systems","status":"public","intvolume":"        35","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.09671"}],"day":"01","date_created":"2022-01-03T10:56:20Z","month":"12","volume":35,"date_published":"2021-12-01T00:00:00Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"corr_author":"1","language":[{"iso":"eng"}],"date_updated":"2025-04-15T07:50:11Z","publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"arxiv":1,"type":"conference","title":"When are solutions connected in deep networks?","year":"2021","conference":{"name":"35th Conference on Neural Information Processing Systems","location":"Virtual","start_date":"2021-12-06","end_date":"2021-12-14"},"oa_version":"Preprint","author":[{"full_name":"Nguyen, Quynh","last_name":"Nguyen","first_name":"Quynh"},{"full_name":"Bréchet, Pierre","first_name":"Pierre","last_name":"Bréchet"},{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"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."}],"citation":{"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.","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.","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.","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.","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.","short":"Q. Nguyen, P. Bréchet, M. Mondelli, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021."}},{"language":[{"iso":"eng"}],"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"volume":139,"date_published":"2021-01-01T00:00:00Z","month":"01","abstract":[{"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.","lang":"eng"}],"citation":{"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>, edited by Marina Meila and Tong Zhang, vol. 139, ML Research Press, 2021, pp. 8119–29.","ieee":"Q. Nguyen, M. Mondelli, and G. F. 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.","chicago":"Nguyen, Quynh, Marco Mondelli, and Guido F 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>, edited by Marina Meila and Tong Zhang, 139:8119–29. ML Research Press, 2021.","ista":"Nguyen Q, Mondelli M, Montufar GF. 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. ICML: International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 139, 8119–8129.","short":"Q. Nguyen, M. Mondelli, G.F. Montufar, in:, M. Meila, T. Zhang (Eds.), Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 8119–8129.","apa":"Nguyen, Q., Mondelli, M., &#38; Montufar, G. F. (2021). Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In M. Meila &#38; T. Zhang (Eds.), <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 8119–8129). Virtual: ML Research Press.","ama":"Nguyen Q, Mondelli M, Montufar GF. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In: Meila M, Zhang T, eds. <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:8119-8129."},"author":[{"full_name":"Nguyen, Quynh","first_name":"Quynh","last_name":"Nguyen"},{"last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Montufar, Guido F","first_name":"Guido F","last_name":"Montufar"}],"editor":[{"full_name":"Meila, Marina","first_name":"Marina","last_name":"Meila"},{"first_name":"Tong","last_name":"Zhang","full_name":"Zhang, Tong"}],"conference":{"end_date":"2021-07-24","start_date":"2021-07-18","location":"Virtual","name":"ICML: International Conference on Machine Learning"},"oa_version":"Published Version","year":"2021","title":"Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks","type":"conference","arxiv":1,"date_updated":"2026-06-18T08:43:54Z","publication":"Proceedings of the 38th International Conference on Machine Learning","alternative_title":["Proceedings of Machine Learning Research"],"status":"public","publisher":"ML Research Press","page":"8119-8129","department":[{"_id":"MaMo"}],"oa":1,"article_processing_charge":"No","_id":"10595","acknowledgement":"The authors would like to thank the anonymous reviewers for their helpful comments. MM was partially supported\r\nby the 2019 Lopez-Loreta Prize. QN and GM acknowledge support from the European Research Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme (grant agreement no 757983).","ddc":["000"],"external_id":{"arxiv":["2012.11654"]},"quality_controlled":"1","date_created":"2022-01-03T10:57:49Z","day":"01","main_file_link":[{"open_access":"1","url":"http://proceedings.mlr.press/v139/nguyen21g.html"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","intvolume":"       139"},{"scopus_import":"1","month":"04","volume":130,"date_published":"2021-04-01T00:00:00Z","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"language":[{"iso":"eng"}],"date_updated":"2025-04-15T07:50:16Z","type":"conference","arxiv":1,"publication_identifier":{"issn":["2640-3498"]},"title":"Approximate message passing with spectral initialization for generalized linear models","related_material":{"record":[{"id":"12480","relation":"later_version","status":"public"}]},"year":"2021","oa_version":"Preprint","conference":{"name":"AISTATS: Artificial Intelligence and Statistics","start_date":"2021-04-13","location":"Virtual, San Diego, CA, United States","end_date":"2021-04-15"},"editor":[{"last_name":"Banerjee","first_name":"Arindam","full_name":"Banerjee, Arindam"},{"first_name":"Kenji","last_name":"Fukumizu","full_name":"Fukumizu, Kenji"}],"author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli"},{"last_name":"Venkataramanan","first_name":"Ramji","full_name":"Venkataramanan, Ramji"}],"citation":{"ista":"Mondelli M, Venkataramanan R. 2021. Approximate message passing with spectral initialization for generalized linear models. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 130, 397–405.","chicago":"Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” In <i>Proceedings of The 24th International Conference on Artificial Intelligence and Statistics</i>, edited by Arindam Banerjee and Kenji Fukumizu, 130:397–405. ML Research Press, 2021.","ieee":"M. Mondelli and R. Venkataramanan, “Approximate message passing with spectral initialization for generalized linear models,” in <i>Proceedings of The 24th International Conference on Artificial Intelligence and Statistics</i>, Virtual, San Diego, CA, United States, 2021, vol. 130, pp. 397–405.","mla":"Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” <i>Proceedings of The 24th International Conference on Artificial Intelligence and Statistics</i>, edited by Arindam Banerjee and Kenji Fukumizu, vol. 130, ML Research Press, 2021, pp. 397–405.","short":"M. Mondelli, R. Venkataramanan, in:, A. Banerjee, K. Fukumizu (Eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2021, pp. 397–405.","apa":"Mondelli, M., &#38; Venkataramanan, R. (2021). Approximate message passing with spectral initialization for generalized linear models. In A. Banerjee &#38; K. Fukumizu (Eds.), <i>Proceedings of The 24th International Conference on Artificial Intelligence and Statistics</i> (Vol. 130, pp. 397–405). Virtual, San Diego, CA, United States: ML Research Press.","ama":"Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization for generalized linear models. In: Banerjee A, Fukumizu K, eds. <i>Proceedings of The 24th International Conference on Artificial Intelligence and Statistics</i>. Vol 130. ML Research Press; 2021:397-405."},"abstract":[{"lang":"eng","text":" We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach. "}],"quality_controlled":"1","external_id":{"arxiv":["2010.03460"]},"acknowledgement":"The authors would like to thank Andrea Montanari 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.","_id":"10598","article_processing_charge":"Yes (via OA deal)","oa":1,"department":[{"_id":"MaMo"}],"page":"397-405","publisher":"ML Research Press","status":"public","alternative_title":["Proceedings of Machine Learning Research"],"publication":"Proceedings of The 24th International Conference on Artificial Intelligence and Statistics","intvolume":"       130","publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://proceedings.mlr.press/v130/mondelli21a.html","open_access":"1"}],"date_created":"2022-01-03T11:34:22Z","day":"01"},{"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2112.00057","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","date_created":"2022-01-03T11:39:51Z","publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","page":"943-947","department":[{"_id":"MaMo"}],"oa":1,"publication":"Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers","status":"public","external_id":{"arxiv":["2112.00057"]},"quality_controlled":"1","_id":"10599","article_processing_charge":"No","acknowledgement":"This work is supported in part by ONR grant N00014-18-1-2191. S. A. Hashemi was supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and by Huawei. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize.","author":[{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"last_name":"Cioffi","first_name":"John","full_name":"Cioffi, John"},{"full_name":"Goldsmith, Andrea","first_name":"Andrea","last_name":"Goldsmith"}],"oa_version":"Preprint","conference":{"name":"ACSSC: Asilomar Conference on Signals, Systems, and Computers","location":"Virtual, Pacific Grove, CA, United States","start_date":"2021-10-31","end_date":"2021-11-03"},"abstract":[{"lang":"eng","text":"A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios."}],"citation":{"apa":"Hashemi, S. A., Mondelli, M., Cioffi, J., &#38; Goldsmith, A. (2021). Successive syndrome-check decoding of polar codes. In <i>Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers</i> (Vol. 2021–October, pp. 943–947). Virtual, Pacific Grove, CA, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/IEEECONF53345.2021.9723394\">https://doi.org/10.1109/IEEECONF53345.2021.9723394</a>","ama":"Hashemi SA, Mondelli M, Cioffi J, Goldsmith A. Successive syndrome-check decoding of polar codes. In: <i>Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers</i>. Vol 2021-October. Institute of Electrical and Electronics Engineers; 2021:943-947. doi:<a href=\"https://doi.org/10.1109/IEEECONF53345.2021.9723394\">10.1109/IEEECONF53345.2021.9723394</a>","ieee":"S. A. Hashemi, M. Mondelli, J. Cioffi, and A. Goldsmith, “Successive syndrome-check decoding of polar codes,” in <i>Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers</i>, Virtual, Pacific Grove, CA, United States, 2021, vol. 2021–October, pp. 943–947.","mla":"Hashemi, Seyyed Ali, et al. “Successive Syndrome-Check Decoding of Polar Codes.” <i>Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers</i>, vol. 2021–October, Institute of Electrical and Electronics Engineers, 2021, pp. 943–47, doi:<a href=\"https://doi.org/10.1109/IEEECONF53345.2021.9723394\">10.1109/IEEECONF53345.2021.9723394</a>.","ista":"Hashemi SA, Mondelli M, Cioffi J, Goldsmith A. 2021. Successive syndrome-check decoding of polar codes. Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers. ACSSC: Asilomar Conference on Signals, Systems, and Computers vol. 2021–October, 943–947.","chicago":"Hashemi, Seyyed Ali, Marco Mondelli, John Cioffi, and Andrea Goldsmith. “Successive Syndrome-Check Decoding of Polar Codes.” In <i>Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers</i>, 2021–October:943–47. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/IEEECONF53345.2021.9723394\">https://doi.org/10.1109/IEEECONF53345.2021.9723394</a>.","short":"S.A. Hashemi, M. Mondelli, J. Cioffi, A. Goldsmith, in:, Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers, Institute of Electrical and Electronics Engineers, 2021, pp. 943–947."},"publication_identifier":{"isbn":["9781665458283"],"issn":["1058-6393"]},"arxiv":1,"type":"conference","date_updated":"2025-04-15T07:50:12Z","year":"2021","title":"Successive syndrome-check decoding of polar codes","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"volume":"2021-October","date_published":"2021-11-01T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":"1","month":"11","doi":"10.1109/IEEECONF53345.2021.9723394"},{"oa":1,"publisher":"IEEE","page":"5693-5710","department":[{"_id":"MaMo"}],"publication":"IEEE Transactions on Information Theory","status":"public","OA_place":"repository","quality_controlled":"1","external_id":{"isi":["000690440100007"],"arxiv":["1711.01339"]},"OA_type":"green","_id":"9002","article_processing_charge":"No","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1711.01339"}],"date_created":"2021-01-10T23:01:18Z","day":"01","issue":"9","intvolume":"        67","publication_status":"published","volume":67,"date_published":"2021-09-01T00:00:00Z","language":[{"iso":"eng"}],"article_type":"original","scopus_import":"1","doi":"10.1109/TIT.2020.3038806","month":"09","oa_version":"Preprint","author":[{"full_name":"Fazeli, Arman","last_name":"Fazeli","first_name":"Arman"},{"full_name":"Hassani, Hamed","last_name":"Hassani","first_name":"Hamed"},{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"last_name":"Vardy","first_name":"Alexander","full_name":"Vardy, Alexander"}],"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)."}],"citation":{"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>","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>","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>.","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.","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."},"date_updated":"2025-09-10T09:59:12Z","publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"arxiv":1,"type":"journal_article","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"6665"}]},"title":"Binary linear codes with optimal scaling: Polar codes with large kernels","year":"2021"},{"scopus_import":"1","month":"01","doi":"10.1109/TWC.2020.3022922","corr_author":"1","volume":20,"date_published":"2021-01-01T00:00:00Z","article_type":"original","language":[{"iso":"eng"}],"type":"journal_article","arxiv":1,"publication_identifier":{"issn":["1536-1276"],"eissn":["1558-2248"]},"date_updated":"2025-09-10T10:27:04Z","year":"2021","title":"Sublinear latency for simplified successive cancellation decoding of polar codes","related_material":{"record":[{"id":"8536","relation":"earlier_version","status":"public"}]},"author":[{"last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"last_name":"Hashemi","first_name":"Seyyed Ali","full_name":"Hashemi, Seyyed Ali"},{"first_name":"John M.","last_name":"Cioffi","full_name":"Cioffi, John M."},{"full_name":"Goldsmith, Andrea","first_name":"Andrea","last_name":"Goldsmith"}],"oa_version":"Preprint","citation":{"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>","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>","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>.","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.","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."},"abstract":[{"lang":"eng","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."}],"quality_controlled":"1","external_id":{"arxiv":["1909.04892"],"isi":["000607808800002"]},"isi":1,"_id":"9047","article_processing_charge":"No","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.","page":"18-27","department":[{"_id":"MaMo"}],"publisher":"IEEE","oa":1,"status":"public","publication":"IEEE Transactions on Wireless Communications","publication_status":"published","intvolume":"        20","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1909.04892"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"1","date_created":"2021-01-31T23:01:21Z","day":"01"},{"publication":"2021 IEEE International Symposium on Information Theory","status":"public","OA_place":"repository","oa":1,"publisher":"Institute of Electrical and Electronics Engineers","page":"1082-1087","department":[{"_id":"MaMo"}],"_id":"10597","OA_type":"green","article_processing_charge":"No","isi":1,"quality_controlled":"1","external_id":{"isi":["000701502201029"],"arxiv":["2011.12882"]},"date_created":"2022-01-03T11:31:26Z","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/2011.12882","open_access":"1"}],"publication_status":"published","language":[{"iso":"eng"}],"date_published":"2021-09-01T00:00:00Z","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"month":"09","doi":"10.1109/isit45174.2021.9517887","scopus_import":"1","abstract":[{"text":"We thank Emmanuel Abbe and Min Ye for providing us the implementation of RPA decoding. D. Fathollahi and M. Mondelli are partially supported by the 2019 Lopez-Loreta Prize. N. Farsad is supported by Discovery Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) and Canada Foundation for Innovation (CFI), John R. Evans Leader Fund. S. A. Hashemi is supported by a Postdoctoral Fellowship from NSERC.","lang":"eng"}],"citation":{"ama":"Fathollahi D, Farsad N, Hashemi SA, Mondelli M. Sparse multi-decoder recursive projection aggregation for Reed-Muller codes. In: <i>2021 IEEE International Symposium on Information Theory</i>. Institute of Electrical and Electronics Engineers; 2021:1082-1087. doi:<a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">10.1109/isit45174.2021.9517887</a>","apa":"Fathollahi, D., Farsad, N., Hashemi, S. A., &#38; Mondelli, M. (2021). Sparse multi-decoder recursive projection aggregation for Reed-Muller codes. In <i>2021 IEEE International Symposium on Information Theory</i> (pp. 1082–1087). Virtual, Melbourne, Australia: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">https://doi.org/10.1109/isit45174.2021.9517887</a>","short":"D. Fathollahi, N. Farsad, S.A. Hashemi, M. Mondelli, in:, 2021 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 1082–1087.","ista":"Fathollahi D, Farsad N, Hashemi SA, Mondelli M. 2021. Sparse multi-decoder recursive projection aggregation for Reed-Muller codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 1082–1087.","chicago":"Fathollahi, Dorsa, Nariman Farsad, Seyyed Ali Hashemi, and Marco Mondelli. “Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes.” In <i>2021 IEEE International Symposium on Information Theory</i>, 1082–87. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">https://doi.org/10.1109/isit45174.2021.9517887</a>.","ieee":"D. Fathollahi, N. Farsad, S. A. Hashemi, and M. Mondelli, “Sparse multi-decoder recursive projection aggregation for Reed-Muller codes,” in <i>2021 IEEE International Symposium on Information Theory</i>, Virtual, Melbourne, Australia, 2021, pp. 1082–1087.","mla":"Fathollahi, Dorsa, et al. “Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 1082–87, doi:<a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">10.1109/isit45174.2021.9517887</a>."},"conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2021-07-20","location":"Virtual, Melbourne, Australia","start_date":"2021-07-12"},"oa_version":"Preprint","author":[{"first_name":"Dorsa","last_name":"Fathollahi","full_name":"Fathollahi, Dorsa","id":"712472af-8a7e-11f1-848f-9768b0c2fdf8"},{"last_name":"Farsad","first_name":"Nariman","full_name":"Farsad, Nariman"},{"full_name":"Hashemi, Seyyed Ali","first_name":"Seyyed Ali","last_name":"Hashemi"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","first_name":"Marco"}],"title":"Sparse multi-decoder recursive projection aggregation for Reed-Muller codes","year":"2021","date_updated":"2026-07-28T12:19:34Z","publication_identifier":{"eisbn":["978-1-5386-8209-8"],"isbn":["978-1-5386-8210-4"]},"type":"conference","arxiv":1},{"oa":1,"publisher":"IEEE","department":[{"_id":"MaMo"}],"publication":"IEEE International Symposium on Information Theory - Proceedings","status":"public","quality_controlled":"1","external_id":{"arxiv":["1909.04892"],"isi":["000714963400069"]},"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.","article_processing_charge":"No","_id":"8536","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1909.04892"}],"day":"01","date_created":"2020-09-20T22:01:37Z","publication_status":"published","volume":"2020-June","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":"1","doi":"10.1109/ISIT44484.2020.9174141","month":"06","oa_version":"Preprint","conference":{"location":"Los Angeles, CA, United States","start_date":"2020-06-21","end_date":"2020-06-26","name":"ISIT: International Symposium on Information Theory"},"author":[{"first_name":"Marco","orcid":"0000-0002-3242-7020","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"full_name":"Cioffi, John","first_name":"John","last_name":"Cioffi"},{"full_name":"Goldsmith, Andrea","first_name":"Andrea","last_name":"Goldsmith"}],"abstract":[{"lang":"eng","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(N 1−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 and 1."}],"citation":{"ama":"Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. Simplified successive cancellation decoding of polar codes has sublinear latency. In: <i>IEEE International Symposium on Information Theory - Proceedings</i>. Vol 2020-June. IEEE; 2020. doi:<a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">10.1109/ISIT44484.2020.9174141</a>","apa":"Mondelli, M., Hashemi, S. A., Cioffi, J., &#38; Goldsmith, A. (2020). Simplified successive cancellation decoding of polar codes has sublinear latency. In <i>IEEE International Symposium on Information Theory - Proceedings</i> (Vol. 2020–June). Los Angeles, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">https://doi.org/10.1109/ISIT44484.2020.9174141</a>","short":"M. Mondelli, S.A. Hashemi, J. Cioffi, A. Goldsmith, in:, IEEE International Symposium on Information Theory - Proceedings, IEEE, 2020.","chicago":"Mondelli, Marco, Seyyed Ali Hashemi, John Cioffi, and Andrea Goldsmith. “Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.” In <i>IEEE International Symposium on Information Theory - Proceedings</i>, Vol. 2020–June. IEEE, 2020. <a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">https://doi.org/10.1109/ISIT44484.2020.9174141</a>.","ista":"Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. 2020. Simplified successive cancellation decoding of polar codes has sublinear latency. IEEE International Symposium on Information Theory - Proceedings. ISIT: International Symposium on Information Theory vol. 2020–June, 401–406.","ieee":"M. Mondelli, S. A. Hashemi, J. Cioffi, and A. Goldsmith, “Simplified successive cancellation decoding of polar codes has sublinear latency,” in <i>IEEE International Symposium on Information Theory - Proceedings</i>, Los Angeles, CA, United States, 2020, vol. 2020–June.","mla":"Mondelli, Marco, et al. “Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.” <i>IEEE International Symposium on Information Theory - Proceedings</i>, vol. 2020–June, 401–406, IEEE, 2020, doi:<a href=\"https://doi.org/10.1109/ISIT44484.2020.9174141\">10.1109/ISIT44484.2020.9174141</a>."},"article_number":"401-406","date_updated":"2025-09-10T10:27:05Z","publication_identifier":{"issn":["2157-8095"],"isbn":["9781728164328"]},"arxiv":1,"type":"conference","related_material":{"record":[{"id":"9047","status":"public","relation":"later_version"}]},"title":"Simplified successive cancellation decoding of polar codes has sublinear latency","year":"2020"}]