[{"conference":{"name":"ISIT: International Symposium on Information Theory","end_date":"2021-07-20","start_date":"2021-07-12","location":"Virtual, Melbourne, Australia"},"language":[{"iso":"eng"}],"citation":{"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.","mla":"Fathollahi, Dorsa, et al. “Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, IEEE, 2021, pp. 1082–87, doi:<a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">10.1109/isit45174.2021.9517887</a>.","short":"D. Fathollahi, N. Farsad, S.A. Hashemi, M. Mondelli, in:, 2021 IEEE International Symposium on Information Theory, IEEE, 2021, pp. 1082–1087.","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: IEEE. <a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">https://doi.org/10.1109/isit45174.2021.9517887</a>","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>. IEEE; 2021:1082-1087. doi:<a href=\"https://doi.org/10.1109/isit45174.2021.9517887\">10.1109/isit45174.2021.9517887</a>","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. IEEE, 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."},"day":"01","oa_version":"Preprint","publication_identifier":{"isbn":["978-1-5386-8210-4"],"eisbn":["978-1-5386-8209-8"]},"OA_type":"green","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"}],"title":"Sparse multi-decoder recursive projection aggregation for Reed-Muller codes","article_processing_charge":"No","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2011.12882"}],"publisher":"IEEE","external_id":{"isi":["000701502201029"],"arxiv":["2011.12882"]},"doi":"10.1109/isit45174.2021.9517887","quality_controlled":"1","department":[{"_id":"MaMo"}],"OA_place":"repository","date_updated":"2026-08-12T06:36:19Z","author":[{"first_name":"Dorsa","last_name":"Fathollahi","full_name":"Fathollahi, Dorsa","id":"712472af-8a7e-11f1-848f-9768b0c2fdf8"},{"first_name":"Nariman","full_name":"Farsad, Nariman","last_name":"Farsad"},{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020"}],"date_created":"2022-01-03T11:31:26Z","_id":"10597","year":"2021","isi":1,"month":"09","scopus_import":"1","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"publication":"2021 IEEE International Symposium on Information Theory","arxiv":1,"page":"1082-1087","type":"conference","publication_status":"published","date_published":"2021-09-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1109/isit45174.2021.9517887","oa":1},{"article_processing_charge":"No","title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","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 μ+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."}],"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.","related_material":{"record":[{"id":"10364","status":"public","relation":"later_version"}]},"publication_identifier":{"isbn":["978-1-5386-8210-4"],"issn":["2157-8095"],"eisbn":["978-1-5386-8209-8"]},"oa_version":"Preprint","day":"01","citation":{"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: IEEE. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>","short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, in:, 2021 IEEE International Symposium on Information Theory, IEEE, 2021, pp. 2369–2374.","mla":"Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, IEEE, 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.","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. IEEE, 2021. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>.","ama":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In: <i>2021 IEEE International Symposium on Information Theory</i>. IEEE; 2021:2369-2374. doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>","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."},"language":[{"iso":"eng"}],"conference":{"end_date":"2021-07-20","name":"ISIT: International Symposium on Information Theory","start_date":"2021-07-12","location":"Melbourne, Australia"},"author":[{"last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali","first_name":"Seyyed Ali"},{"full_name":"Mondelli, Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"last_name":"Fazeli","full_name":"Fazeli, Arman","first_name":"Arman"},{"last_name":"Vardy","full_name":"Vardy, Alexander","first_name":"Alexander"},{"first_name":"John","full_name":"Cioffi, John","last_name":"Cioffi"},{"full_name":"Goldsmith, Andrea","last_name":"Goldsmith","first_name":"Andrea"}],"date_created":"2021-09-27T14:33:14Z","date_updated":"2026-08-12T06:43:01Z","department":[{"_id":"MaMo"}],"doi":"10.1109/ISIT45174.2021.9518153","quality_controlled":"1","external_id":{"arxiv":["2012.13378"],"isi":["000701502202078"]},"publisher":"IEEE","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.13378"}],"status":"public","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"scopus_import":"1","isi":1,"month":"09","year":"2021","_id":"10053","oa":1,"fulldoi":"https://doi.org/10.1109/ISIT45174.2021.9518153","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2021-09-01T00:00:00Z","publication_status":"published","type":"conference","page":"2369-2374","arxiv":1,"publication":"2021 IEEE International Symposium on Information Theory"},{"publisher":"IEEE","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1909.04892"}],"author":[{"first_name":"Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020"},{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"full_name":"Cioffi, John M.","last_name":"Cioffi","first_name":"John M."},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"date_created":"2021-01-31T23:01:21Z","date_updated":"2026-08-12T11:12:22Z","external_id":{"isi":["000607808800002"],"arxiv":["1909.04892"]},"doi":"10.1109/TWC.2020.3022922","quality_controlled":"1","corr_author":"1","department":[{"_id":"MaMo"}],"intvolume":"        20","day":"01","oa_version":"Preprint","publication_identifier":{"eissn":["1558-2248"],"issn":["1536-1276"]},"language":[{"iso":"eng"}],"volume":20,"citation":{"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>.","short":"M. Mondelli, S.A. Hashemi, J.M. Cioffi, A. Goldsmith, IEEE Transactions on Wireless Communications 20 (2021) 18–27.","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>","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.","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."},"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.","related_material":{"record":[{"id":"8536","status":"public","relation":"earlier_version"}]},"abstract":[{"text":"This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1−1/μ) , where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 or 1.","lang":"eng"}],"title":"Sublinear latency for simplified successive cancellation decoding of polar codes","page":"18-27","type":"journal_article","publication_status":"published","date_published":"2021-01-01T00:00:00Z","publication":"IEEE Transactions on Wireless Communications","arxiv":1,"oa":1,"fulldoi":"https://doi.org/10.1109/TWC.2020.3022922","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","_id":"9047","issue":"1","month":"01","isi":1,"article_type":"original","scopus_import":"1"},{"intvolume":"        33","department":[{"_id":"MaMo"}],"quality_controlled":"1","external_id":{"arxiv":["2002.07867"]},"date_created":"2021-03-03T12:06:02Z","date_updated":"2025-05-14T11:27:13Z","author":[{"full_name":"Nguyen, Quynh","last_name":"Nguyen","first_name":"Quynh"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2002.07867"}],"status":"public","publisher":"Neural Information Processing Systems Foundation","title":"Global convergence of deep networks with one wide layer followed by pyramidal topology","abstract":[{"lang":"eng","text":"Recent works have shown that gradient descent can find a global minimum for over-parameterized neural networks where the widths of all the hidden layers scale polynomially with N (N being the number of training samples). In this paper, we prove that, for deep networks, a single layer of width N following the input layer suffices to ensure a similar guarantee. In particular, all the remaining layers are allowed to have constant widths, and form a pyramidal topology. We show an application of our result to the widely used LeCun’s initialization and obtain an over-parameterization requirement for the single wide layer of order N2.\r\n"}],"acknowledgement":"The authors would like to thank Jan Maas, Mahdi Soltanolkotabi, and Daniel Soudry for the helpful discussions, Marius Kloft, Matthias Hein and Quoc Dinh Tran for proofreading portions of a prior version of this paper, and James Martens for a clarification concerning LeCun’s initialization. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. Q. Nguyen was partially supported by the German Research Foundation (DFG) award KL 2698/2-1.","article_processing_charge":"No","citation":{"ama":"Nguyen Q, Mondelli M. Global convergence of deep networks with one wide layer followed by pyramidal topology. In: <i>34th Conference on Neural Information Processing Systems</i>. Vol 33. Neural Information Processing Systems Foundation; 2020:11961–11972.","ieee":"Q. Nguyen and M. Mondelli, “Global convergence of deep networks with one wide layer followed by pyramidal topology,” in <i>34th Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2020, vol. 33, pp. 11961–11972.","chicago":"Nguyen, Quynh, and Marco Mondelli. “Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology.” In <i>34th Conference on Neural Information Processing Systems</i>, 33:11961–11972. Neural Information Processing Systems Foundation, 2020.","mla":"Nguyen, Quynh, and Marco Mondelli. “Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology.” <i>34th Conference on Neural Information Processing Systems</i>, vol. 33, Neural Information Processing Systems Foundation, 2020, pp. 11961–11972.","short":"Q. Nguyen, M. Mondelli, in:, 34th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2020, pp. 11961–11972.","apa":"Nguyen, Q., &#38; Mondelli, M. (2020). Global convergence of deep networks with one wide layer followed by pyramidal topology. In <i>34th Conference on Neural Information Processing Systems</i> (Vol. 33, pp. 11961–11972). Vancouver, Canada: Neural Information Processing Systems Foundation.","ista":"Nguyen Q, Mondelli M. 2020. Global convergence of deep networks with one wide layer followed by pyramidal topology. 34th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 33, 11961–11972."},"volume":33,"language":[{"iso":"eng"}],"conference":{"location":"Vancouver, Canada","start_date":"2020-12-06","name":"NeurIPS: Neural Information Processing Systems","end_date":"2020-12-12"},"alternative_title":["Advances in Neural Information Processing Systems"],"oa_version":"Preprint","day":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"arxiv":1,"publication":"34th Conference on Neural Information Processing Systems","date_published":"2020-07-07T00:00:00Z","publication_status":"published","type":"conference","page":"11961–11972","month":"07","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"_id":"9221","year":"2020"},{"publication":"Annals of Statistics","arxiv":1,"publication_status":"published","date_published":"2020-12-11T00:00:00Z","page":"3619-3642","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"fulldoi":"https://doi.org/10.1214/20-AOS1945","issue":"6","_id":"6748","year":"2020","article_type":"original","scopus_import":"1","isi":1,"month":"12","main_file_link":[{"url":"https://arxiv.org/abs/1901.01375","open_access":"1"}],"status":"public","publisher":"Institute of Mathematical Statistics","department":[{"_id":"MaMo"}],"intvolume":"        48","external_id":{"isi":["000598369200021"],"arxiv":["1901.01375"]},"quality_controlled":"1","doi":"10.1214/20-AOS1945","date_created":"2019-07-31T09:39:42Z","date_updated":"2024-10-21T06:02:33Z","author":[{"first_name":"Adel","last_name":"Javanmard","full_name":"Javanmard, Adel"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"full_name":"Montanari, Andrea","last_name":"Montanari","first_name":"Andrea"}],"volume":48,"citation":{"mla":"Javanmard, Adel, et al. “Analysis of a Two-Layer Neural Network via Displacement Convexity.” <i>Annals of Statistics</i>, vol. 48, no. 6, Institute of Mathematical Statistics, 2020, pp. 3619–42, doi:<a href=\"https://doi.org/10.1214/20-AOS1945\">10.1214/20-AOS1945</a>.","short":"A. Javanmard, M. Mondelli, A. Montanari, Annals of Statistics 48 (2020) 3619–3642.","apa":"Javanmard, A., Mondelli, M., &#38; Montanari, A. (2020). Analysis of a two-layer neural network via displacement convexity. <i>Annals of Statistics</i>. Institute of Mathematical Statistics. <a href=\"https://doi.org/10.1214/20-AOS1945\">https://doi.org/10.1214/20-AOS1945</a>","ama":"Javanmard A, Mondelli M, Montanari A. Analysis of a two-layer neural network via displacement convexity. <i>Annals of Statistics</i>. 2020;48(6):3619-3642. doi:<a href=\"https://doi.org/10.1214/20-AOS1945\">10.1214/20-AOS1945</a>","ieee":"A. Javanmard, M. Mondelli, and A. Montanari, “Analysis of a two-layer neural network via displacement convexity,” <i>Annals of Statistics</i>, vol. 48, no. 6. Institute of Mathematical Statistics, pp. 3619–3642, 2020.","chicago":"Javanmard, Adel, Marco Mondelli, and Andrea Montanari. “Analysis of a Two-Layer Neural Network via Displacement Convexity.” <i>Annals of Statistics</i>. Institute of Mathematical Statistics, 2020. <a href=\"https://doi.org/10.1214/20-AOS1945\">https://doi.org/10.1214/20-AOS1945</a>.","ista":"Javanmard A, Mondelli M, Montanari A. 2020. Analysis of a two-layer neural network via displacement convexity. Annals of Statistics. 48(6), 3619–3642."},"language":[{"iso":"eng"}],"day":"11","oa_version":"Preprint","publication_identifier":{"issn":["1932-6157"],"eissn":["1941-7330"]},"abstract":[{"text":"Fitting a function by using linear combinations of a large number N of `simple' components is one of the most fruitful ideas in statistical learning. This idea lies at the core of a variety of methods, from two-layer neural networks to kernel regression, to boosting. In general, the resulting risk minimization problem is non-convex and is solved by gradient descent or its variants. Unfortunately, little is known about global convergence properties of these approaches.\r\nHere we consider the problem of learning a concave function f on a compact convex domain Ω⊆ℝd, using linear combinations of `bump-like' components (neurons). The parameters to be fitted are the centers of N bumps, and the resulting empirical risk minimization problem is highly non-convex. We prove that, in the limit in which the number of neurons diverges, the evolution of gradient descent converges to a Wasserstein gradient flow in the space of probability distributions over Ω. Further, when the bump width δ tends to 0, this gradient flow has a limit which is a viscous porous medium equation. Remarkably, the cost function optimized by this gradient flow exhibits a special property known as displacement convexity, which implies exponential convergence rates for N→∞, δ→0. Surprisingly, this asymptotic theory appears to capture well the behavior for moderate values of δ,N. Explaining this phenomenon, and understanding the dependence on δ,N in a quantitative manner remains an outstanding challenge.","lang":"eng"}],"title":"Analysis of a two-layer neural network via displacement convexity","article_processing_charge":"No"},{"conference":{"end_date":"2020-06-26","name":"ISIT: International Symposium on Information Theory","location":"Los Angeles, CA, United States","start_date":"2020-06-21"},"language":[{"iso":"eng"}],"volume":"2020-June","citation":{"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. ISIT: International Symposium on Information Theory vol. 2020–June, 401–406.","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</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>.","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</i>, Los Angeles, CA, United States, 2020, vol. 2020–June.","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</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</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>","mla":"Mondelli, Marco, et al. “Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.” <i>IEEE International Symposium on Information Theory</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>.","short":"M. Mondelli, S.A. Hashemi, J. Cioffi, A. Goldsmith, in:, IEEE International Symposium on Information Theory, IEEE, 2020."},"day":"01","publication_identifier":{"issn":["2157-8095"],"isbn":["9781728164328"]},"oa_version":"Preprint","related_material":{"record":[{"relation":"later_version","status":"public","id":"9047"}]},"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.","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."}],"title":"Simplified successive cancellation decoding of polar codes has sublinear latency","article_processing_charge":"No","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1909.04892","open_access":"1"}],"publisher":"IEEE","external_id":{"isi":["000714963400069"],"arxiv":["1909.04892"]},"quality_controlled":"1","doi":"10.1109/ISIT44484.2020.9174141","department":[{"_id":"MaMo"}],"date_created":"2020-09-20T22:01:37Z","author":[{"orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","last_name":"Mondelli","full_name":"Mondelli, Marco","first_name":"Marco"},{"last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali","first_name":"Seyyed Ali"},{"first_name":"John","last_name":"Cioffi","full_name":"Cioffi, John"},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"date_updated":"2026-08-12T11:12:23Z","_id":"8536","year":"2020","article_number":"401-406","month":"06","isi":1,"scopus_import":"1","publication":"IEEE International Symposium on Information Theory","arxiv":1,"type":"conference","publication_status":"published","date_published":"2020-06-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1109/ISIT44484.2020.9174141","oa":1},{"arxiv":1,"has_accepted_license":"1","publication":"Proceedings of the 37th International Conference on Machine Learning","date_published":"2020-07-13T00:00:00Z","publication_status":"published","type":"conference","ddc":["000"],"page":"8773-8784","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","oa":1,"_id":"9198","year":"2020","month":"07","project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"status":"public","publisher":"ML Research Press","intvolume":"       119","department":[{"_id":"MaMo"},{"_id":"DaAl"}],"quality_controlled":"1","external_id":{"arxiv":["1912.10095"]},"author":[{"first_name":"Aleksandr","full_name":"Shevchenko, Aleksandr","id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","last_name":"Shevchenko"},{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"date_created":"2021-02-25T09:36:22Z","date_updated":"2026-11-05T23:31:06Z","citation":{"short":"A. Shevchenko, M. Mondelli, in:, Proceedings of the 37th International Conference on Machine Learning, ML Research Press, 2020, pp. 8773–8784.","mla":"Shevchenko, Aleksandr, and Marco Mondelli. “Landscape Connectivity and Dropout Stability of SGD Solutions for Over-Parameterized Neural Networks.” <i>Proceedings of the 37th International Conference on Machine Learning</i>, vol. 119, ML Research Press, 2020, pp. 8773–84.","apa":"Shevchenko, A., &#38; Mondelli, M. (2020). Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. In <i>Proceedings of the 37th International Conference on Machine Learning</i> (Vol. 119, pp. 8773–8784). ML Research Press.","ama":"Shevchenko A, Mondelli M. Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. In: <i>Proceedings of the 37th International Conference on Machine Learning</i>. Vol 119. ML Research Press; 2020:8773-8784.","ieee":"A. Shevchenko and M. Mondelli, “Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks,” in <i>Proceedings of the 37th International Conference on Machine Learning</i>, 2020, vol. 119, pp. 8773–8784.","chicago":"Shevchenko, Aleksandr, and Marco Mondelli. “Landscape Connectivity and Dropout Stability of SGD Solutions for Over-Parameterized Neural Networks.” In <i>Proceedings of the 37th International Conference on Machine Learning</i>, 119:8773–84. ML Research Press, 2020.","ista":"Shevchenko A, Mondelli M. 2020. Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. Proceedings of the 37th International Conference on Machine Learning. vol. 119, 8773–8784."},"volume":119,"language":[{"iso":"eng"}],"file_date_updated":"2021-03-02T15:38:14Z","oa_version":"Published Version","day":"13","title":"Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks","abstract":[{"lang":"eng","text":"The optimization of multilayer neural networks typically leads to a solution\r\nwith zero training error, yet the landscape can exhibit spurious local minima\r\nand the minima can be disconnected. In this paper, we shed light on this\r\nphenomenon: we show that the combination of stochastic gradient descent (SGD)\r\nand over-parameterization makes the landscape of multilayer neural networks\r\napproximately connected and thus more favorable to optimization. More\r\nspecifically, we prove that SGD solutions are connected via a piecewise linear\r\npath, and the increase in loss along this path vanishes as the number of\r\nneurons grows large. This result is a consequence of the fact that the\r\nparameters found by SGD are increasingly dropout stable as the network becomes\r\nwider. We show that, if we remove part of the neurons (and suitably rescale the\r\nremaining ones), the change in loss is independent of the total number of\r\nneurons, and it depends only on how many neurons are left. Our results exhibit\r\na mild dependence on the input dimension: they are dimension-free for two-layer\r\nnetworks and depend linearly on the dimension for multilayer networks. We\r\nvalidate our theoretical findings with numerical experiments for different\r\narchitectures and classification tasks."}],"file":[{"access_level":"open_access","date_updated":"2021-03-02T15:38:14Z","creator":"dernst","date_created":"2021-03-02T15:38:14Z","file_name":"2020_PMLR_Shevchenko.pdf","relation":"main_file","file_size":5336380,"content_type":"application/pdf","success":1,"checksum":"f042c8d4316bd87c6361aa76f1fbdbbe","file_id":"9217"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"17465"}]},"acknowledgement":"M. Mondelli was partially supported by the 2019 LopezLoreta Prize. The authors thank Phan-Minh Nguyen for helpful discussions and the IST Distributed Algorithms and Systems Lab for providing computational resources.","article_processing_charge":"No"},{"issue":"22","_id":"6750","article_number":"8854897","year":"2019","article_type":"original","scopus_import":"1","month":"11","arxiv":1,"publication":"IEEE Transactions on Signal Processing","date_published":"2019-11-15T00:00:00Z","publication_status":"published","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"fulldoi":"https://doi.org/10.1109/TSP.2019.2944738","citation":{"ama":"Hashemi SA, Condo C, Mondelli M, Gross WJ. Rate-flexible fast polar decoders. <i>IEEE Transactions on Signal Processing</i>. 2019;67(22). doi:<a href=\"https://doi.org/10.1109/TSP.2019.2944738\">10.1109/TSP.2019.2944738</a>","chicago":"Hashemi, Seyyed Ali, Carlo Condo, Marco Mondelli, and Warren J Gross. “Rate-Flexible Fast Polar Decoders.” <i>IEEE Transactions on Signal Processing</i>. IEEE, 2019. <a href=\"https://doi.org/10.1109/TSP.2019.2944738\">https://doi.org/10.1109/TSP.2019.2944738</a>.","ieee":"S. A. Hashemi, C. Condo, M. Mondelli, and W. J. Gross, “Rate-flexible fast polar decoders,” <i>IEEE Transactions on Signal Processing</i>, vol. 67, no. 22. IEEE, 2019.","mla":"Hashemi, Seyyed Ali, et al. “Rate-Flexible Fast Polar Decoders.” <i>IEEE Transactions on Signal Processing</i>, vol. 67, no. 22, 8854897, IEEE, 2019, doi:<a href=\"https://doi.org/10.1109/TSP.2019.2944738\">10.1109/TSP.2019.2944738</a>.","short":"S.A. Hashemi, C. Condo, M. Mondelli, W.J. Gross, IEEE Transactions on Signal Processing 67 (2019).","apa":"Hashemi, S. A., Condo, C., Mondelli, M., &#38; Gross, W. J. (2019). Rate-flexible fast polar decoders. <i>IEEE Transactions on Signal Processing</i>. IEEE. <a href=\"https://doi.org/10.1109/TSP.2019.2944738\">https://doi.org/10.1109/TSP.2019.2944738</a>","ista":"Hashemi SA, Condo C, Mondelli M, Gross WJ. 2019. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 67(22), 8854897."},"volume":67,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1053-587X"]},"oa_version":"Preprint","day":"15","title":"Rate-flexible fast polar decoders","abstract":[{"text":"Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. ","lang":"eng"}],"article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/1903.09203","open_access":"1"}],"status":"public","publisher":"IEEE","intvolume":"        67","department":[{"_id":"MaMo"}],"quality_controlled":"1","doi":"10.1109/TSP.2019.2944738","external_id":{"arxiv":["1903.09203"]},"date_updated":"2025-01-14T14:34:26Z","date_created":"2019-07-31T09:51:14Z","author":[{"last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali","first_name":"Seyyed Ali"},{"first_name":"Carlo","full_name":"Condo, Carlo","last_name":"Condo"},{"last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"first_name":"Warren J","full_name":"Gross, Warren J","last_name":"Gross"}]},{"publication_identifier":{"issn":["1999-4893"]},"oa_version":"Published Version","day":"18","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:47Z","citation":{"ista":"Mondelli M, Hassani SH, Urbanke R. 2019. A new coding paradigm for the primitive relay channel. Algorithms. 12(10), 218.","apa":"Mondelli, M., Hassani, S. H., &#38; Urbanke, R. (2019). A new coding paradigm for the primitive relay channel. <i>Algorithms</i>. MDPI. <a href=\"https://doi.org/10.3390/a12100218\">https://doi.org/10.3390/a12100218</a>","mla":"Mondelli, Marco, et al. “A New Coding Paradigm for the Primitive Relay Channel.” <i>Algorithms</i>, vol. 12, no. 10, 218, MDPI, 2019, doi:<a href=\"https://doi.org/10.3390/a12100218\">10.3390/a12100218</a>.","short":"M. Mondelli, S.H. Hassani, R. Urbanke, Algorithms 12 (2019).","ieee":"M. Mondelli, S. H. Hassani, and R. Urbanke, “A new coding paradigm for the primitive relay channel,” <i>Algorithms</i>, vol. 12, no. 10. MDPI, 2019.","chicago":"Mondelli, Marco, S. Hamed Hassani, and Rüdiger Urbanke. “A New Coding Paradigm for the Primitive Relay Channel.” <i>Algorithms</i>. MDPI, 2019. <a href=\"https://doi.org/10.3390/a12100218\">https://doi.org/10.3390/a12100218</a>.","ama":"Mondelli M, Hassani SH, Urbanke R. A new coding paradigm for the primitive relay channel. <i>Algorithms</i>. 2019;12(10). doi:<a href=\"https://doi.org/10.3390/a12100218\">10.3390/a12100218</a>"},"volume":12,"related_material":{"record":[{"id":"6675","status":"public","relation":"earlier_version"}]},"title":"A new coding paradigm for the primitive relay channel","abstract":[{"text":"We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner–Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner–Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds.","lang":"eng"}],"file":[{"access_level":"open_access","creator":"dernst","date_created":"2019-11-12T14:48:45Z","date_updated":"2020-07-14T12:47:47Z","file_name":"2019_Algorithms_Mondelli.pdf","file_size":696791,"relation":"main_file","content_type":"application/pdf","file_id":"7008","checksum":"267756d8f9db572f496cd1663c89d59a"}],"publisher":"MDPI","status":"public","date_created":"2019-11-12T14:46:19Z","date_updated":"2024-10-09T20:59:05Z","author":[{"full_name":"Mondelli, Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"first_name":"S. Hamed","last_name":"Hassani","full_name":"Hassani, S. Hamed"},{"last_name":"Urbanke","full_name":"Urbanke, Rüdiger","first_name":"Rüdiger"}],"doi":"10.3390/a12100218","quality_controlled":"1","external_id":{"arxiv":["1801.03153"]},"intvolume":"        12","department":[{"_id":"MaMo"}],"corr_author":"1","article_number":"218","year":"2019","_id":"7007","issue":"10","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"month":"10","article_type":"original","scopus_import":1,"type":"journal_article","ddc":["510"],"date_published":"2019-10-18T00:00:00Z","publication_status":"published","arxiv":1,"has_accepted_license":"1","publication":"Algorithms","fulldoi":"https://doi.org/10.3390/a12100218","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]