---
_id: '15172'
abstract:
- lang: eng
text: 'We propose a novel approach to concentration for non-independent random variables.
The main idea is to “pretend” that the random variables are independent and pay
a multiplicative price measuring how far they are from actually being independent.
This price is encapsulated in the Hellinger integral between the joint and the
product of the marginals, which is then upper bounded leveraging tensorisation
properties. Our bounds represent a natural generalisation of concentration inequalities
in the presence of dependence: we recover exactly the classical bounds (McDiarmid’s
inequality) when the random variables are independent. Furthermore, in a “large
deviations” regime, we obtain the same decay in the probability as for the independent
case, even when the random variables display non-trivial dependencies. To show
this, we consider a number of applications of interest. First, we provide a bound
for Markov chains with finite state space. Then, we consider the Simple Symmetric
Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting
in which the stochastic process depends on its entire past. To conclude, we propose
an application to Markov Chain Monte Carlo methods, where our approach leads to
an improved lower bound on the minimum burn-in period required to reach a certain
accuracy. In all of these settings, we provide a regime of parameters in which
our bound fares better than what the state of the art can provide.'
article_processing_charge: No
article_type: original
author:
- first_name: Amedeo Roberto
full_name: Esposito, Amedeo Roberto
id: 9583e921-e1ad-11ec-9862-cef099626dc9
last_name: Esposito
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Esposito AR, Mondelli M. Concentration without independence via information
measures. IEEE Transactions on Information Theory. doi:10.1109/TIT.2024.3367767
apa: Esposito, A. R., & Mondelli, M. (n.d.). Concentration without independence
via information measures. IEEE Transactions on Information Theory. IEEE.
https://doi.org/10.1109/TIT.2024.3367767
chicago: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
via Information Measures.” IEEE Transactions on Information Theory. IEEE,
n.d. https://doi.org/10.1109/TIT.2024.3367767.
ieee: A. R. Esposito and M. Mondelli, “Concentration without independence via information
measures,” IEEE Transactions on Information Theory. IEEE.
ista: Esposito AR, Mondelli M. Concentration without independence via information
measures. IEEE Transactions on Information Theory.
mla: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
via Information Measures.” IEEE Transactions on Information Theory, IEEE,
doi:10.1109/TIT.2024.3367767.
short: A.R. Esposito, M. Mondelli, IEEE Transactions on Information Theory (n.d.).
date_created: 2024-03-24T23:01:00Z
date_published: 2024-02-20T00:00:00Z
date_updated: 2024-03-25T07:15:51Z
day: '20'
department:
- _id: MaMo
doi: 10.1109/TIT.2024.3367767
external_id:
arxiv:
- '2303.07245'
language:
- iso: eng
month: '02'
oa_version: None
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: inpress
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '14922'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Concentration without independence via information measures
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
_id: '13315'
abstract:
- lang: eng
text: How do statistical dependencies in measurement noise influence high-dimensional
inference? To answer this, we study the paradigmatic spiked matrix model of principal
components analysis (PCA), where a rank-one matrix is corrupted by additive noise.
We go beyond the usual independence assumption on the noise entries, by drawing
the noise from a low-order polynomial orthogonal matrix ensemble. The resulting
noise correlations make the setting relevant for applications but analytically
challenging. We provide characterization of the Bayes optimal limits of inference
in this model. If the spike is rotation invariant, we show that standard spectral
PCA is optimal. However, for more general priors, both PCA and the existing approximate
message-passing algorithm (AMP) fall short of achieving the information-theoretic
limits, which we compute using the replica method from statistical physics. We
thus propose an AMP, inspired by the theory of adaptive Thouless–Anderson–Palmer
equations, which is empirically observed to saturate the conjectured theoretical
limit. This AMP comes with a rigorous state evolution analysis tracking its performance.
Although we focus on specific noise distributions, our methodology can be generalized
to a wide class of trace matrix ensembles at the cost of more involved expressions.
Finally, despite the seemingly strong assumption of rotation-invariant noise,
our theory empirically predicts algorithmic performance on real data, pointing
at strong universality properties.
acknowledgement: J.B. was funded by the European Union (ERC, CHORAL, project number
101039794). Views and opinions expressed are however those of the author(s) only
and do not necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held responsible
for them. M.M. was supported by the 2019 Lopez-Loreta Prize. We would like to thank
the reviewers for the insightful comments and, in particular, for suggesting the
BAMP-inspired denoisers leading to AMP-AP.
article_number: e2302028120
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Jean
full_name: Barbier, Jean
last_name: Barbier
- first_name: Francesco
full_name: Camilli, Francesco
last_name: Camilli
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Manuel
full_name: Sáenz, Manuel
last_name: Sáenz
citation:
ama: Barbier J, Camilli F, Mondelli M, Sáenz M. Fundamental limits in structured
principal component analysis and how to reach them. Proceedings of the National
Academy of Sciences of the United States of America. 2023;120(30). doi:10.1073/pnas.2302028120
apa: Barbier, J., Camilli, F., Mondelli, M., & Sáenz, M. (2023). Fundamental
limits in structured principal component analysis and how to reach them. Proceedings
of the National Academy of Sciences of the United States of America. National
Academy of Sciences. https://doi.org/10.1073/pnas.2302028120
chicago: Barbier, Jean, Francesco Camilli, Marco Mondelli, and Manuel Sáenz. “Fundamental
Limits in Structured Principal Component Analysis and How to Reach Them.” Proceedings
of the National Academy of Sciences of the United States of America. National
Academy of Sciences, 2023. https://doi.org/10.1073/pnas.2302028120.
ieee: J. Barbier, F. Camilli, M. Mondelli, and M. Sáenz, “Fundamental limits in
structured principal component analysis and how to reach them,” Proceedings
of the National Academy of Sciences of the United States of America, vol.
120, no. 30. National Academy of Sciences, 2023.
ista: Barbier J, Camilli F, Mondelli M, Sáenz M. 2023. Fundamental limits in structured
principal component analysis and how to reach them. Proceedings of the National
Academy of Sciences of the United States of America. 120(30), e2302028120.
mla: Barbier, Jean, et al. “Fundamental Limits in Structured Principal Component
Analysis and How to Reach Them.” Proceedings of the National Academy of Sciences
of the United States of America, vol. 120, no. 30, e2302028120, National Academy
of Sciences, 2023, doi:10.1073/pnas.2302028120.
short: J. Barbier, F. Camilli, M. Mondelli, M. Sáenz, Proceedings of the National
Academy of Sciences of the United States of America 120 (2023).
date_created: 2023-07-30T22:01:02Z
date_published: 2023-07-25T00:00:00Z
date_updated: 2023-10-17T11:44:55Z
day: '25'
ddc:
- '000'
department:
- _id: MaMo
doi: 10.1073/pnas.2302028120
external_id:
pmid:
- '37463204'
file:
- access_level: open_access
checksum: 1fc06228afdb3aa80cf8e7766bcf9dc5
content_type: application/pdf
creator: dernst
date_created: 2023-07-31T07:30:48Z
date_updated: 2023-07-31T07:30:48Z
file_id: '13323'
file_name: 2023_PNAS_Barbier.pdf
file_size: 995933
relation: main_file
success: 1
file_date_updated: 2023-07-31T07:30:48Z
has_accepted_license: '1'
intvolume: ' 120'
issue: '30'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the National Academy of Sciences of the United States
of America
publication_identifier:
eissn:
- 1091-6490
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/fcamilli95/Structured-PCA-
scopus_import: '1'
status: public
title: Fundamental limits in structured principal component analysis and how to reach
them
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 120
year: '2023'
...
---
_id: '14459'
abstract:
- lang: eng
text: Autoencoders are a popular model in many branches of machine learning and
lossy data compression. However, their fundamental limits, the performance of
gradient methods and the features learnt during optimization remain poorly understood,
even in the two-layer setting. In fact, earlier work has considered either linear
autoencoders or specific training regimes (leading to vanishing or diverging compression
rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders
trained in the challenging proportional regime in which the input dimension scales
linearly with the size of the representation. Our results characterize the minimizers
of the population risk, and show that such minimizers are achieved by gradient
methods; their structure is also unveiled, thus leading to a concise description
of the features obtained via training. For the special case of a sign activation
function, our analysis establishes the fundamental limits for the lossy compression
of Gaussian sources via (shallow) autoencoders. Finally, while the results are
proved for Gaussian data, numerical simulations on standard datasets display the
universality of the theoretical predictions.
acknowledgement: Aleksandr Shevchenko, Kevin Kogler and Marco Mondelli are supported
by the 2019 Lopez-Loreta Prize. Hamed Hassani acknowledges the support by the NSF
CIF award (1910056) and the NSF Institute for CORE Emerging Methods in Data Science
(EnCORE).
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. Fundamental limits of two-layer
autoencoders, and achieving them with gradient methods. In: Proceedings of
the 40th International Conference on Machine Learning. Vol 202. ML Research
Press; 2023:31151-31209.'
apa: 'Shevchenko, A., Kögler, K., Hassani, H., & Mondelli, M. (2023). Fundamental
limits of two-layer autoencoders, and achieving them with gradient methods. In
Proceedings of the 40th International Conference on Machine Learning (Vol.
202, pp. 31151–31209). Honolulu, Hawaii, HI, United States: ML Research Press.'
chicago: Shevchenko, Aleksandr, Kevin Kögler, Hamed Hassani, and Marco Mondelli.
“Fundamental Limits of Two-Layer Autoencoders, and Achieving Them with Gradient
Methods.” In Proceedings of the 40th International Conference on Machine Learning,
202:31151–209. ML Research Press, 2023.
ieee: A. Shevchenko, K. Kögler, H. Hassani, and M. Mondelli, “Fundamental limits
of two-layer autoencoders, and achieving them with gradient methods,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, Hawaii,
HI, United States, 2023, vol. 202, pp. 31151–31209.
ista: 'Shevchenko A, Kögler K, Hassani H, Mondelli M. 2023. Fundamental limits of
two-layer autoencoders, and achieving them with gradient methods. Proceedings
of the 40th International Conference on Machine Learning. ICML: International
Conference on Machine Learning, PMLR, vol. 202, 31151–31209.'
mla: Shevchenko, Aleksandr, et al. “Fundamental Limits of Two-Layer Autoencoders,
and Achieving Them with Gradient Methods.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 31151–209.
short: A. Shevchenko, K. Kögler, H. Hassani, M. Mondelli, in:, Proceedings of the
40th International Conference on Machine Learning, ML Research Press, 2023, pp.
31151–31209.
conference:
end_date: 2023-07-29
location: Honolulu, Hawaii, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
date_created: 2023-10-29T23:01:17Z
date_published: 2023-07-30T00:00:00Z
date_updated: 2023-10-31T08:52:28Z
day: '30'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2212.13468'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2212.13468
month: '07'
oa: 1
oa_version: Preprint
page: 31151-31209
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 40th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fundamental limits of two-layer autoencoders, and achieving them with gradient
methods
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '13321'
abstract:
- lang: eng
text: We consider the problem of reconstructing the signal and the hidden variables
from observations coming from a multi-layer network with rotationally invariant
weight matrices. The multi-layer structure models inference from deep generative
priors, and the rotational invariance imposed on the weights generalizes the i.i.d.
Gaussian assumption by allowing for a complex correlation structure, which is
typical in applications. In this work, we present a new class of approximate message
passing (AMP) algorithms and give a state evolution recursion which precisely
characterizes their performance in the large system limit. In contrast with the
existing multi-layer VAMP (ML-VAMP) approach, our proposed AMP – dubbed multilayer
rotationally invariant generalized AMP (ML-RI-GAMP) – provides a natural generalization
beyond Gaussian designs, in the sense that it recovers the existing Gaussian AMP
as a special case. Furthermore, ML-RI-GAMP exhibits a significantly lower complexity
than ML-VAMP, as the computationally intensive singular value decomposition is
replaced by an estimation of the moments of the design matrices. Finally, our
numerical results show that this complexity gain comes at little to no cost in
the performance of the algorithm.
acknowledgement: Marco Mondelli was partially supported by the 2019 Lopez-Loreta prize.
article_processing_charge: No
author:
- first_name: Yizhou
full_name: Xu, Yizhou
last_name: Xu
- first_name: Tian Qi
full_name: Hou, Tian Qi
last_name: Hou
- first_name: Shan Suo
full_name: Liang, Shan Suo
last_name: Liang
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Xu Y, Hou TQ, Liang SS, Mondelli M. Approximate message passing for multi-layer
estimation in rotationally invariant models. In: 2023 IEEE Information Theory
Workshop. Institute of Electrical and Electronics Engineers; 2023:294-298.
doi:10.1109/ITW55543.2023.10160238'
apa: 'Xu, Y., Hou, T. Q., Liang, S. S., & Mondelli, M. (2023). Approximate message
passing for multi-layer estimation in rotationally invariant models. In 2023
IEEE Information Theory Workshop (pp. 294–298). Saint-Malo, France: Institute
of Electrical and Electronics Engineers. https://doi.org/10.1109/ITW55543.2023.10160238'
chicago: Xu, Yizhou, Tian Qi Hou, Shan Suo Liang, and Marco Mondelli. “Approximate
Message Passing for Multi-Layer Estimation in Rotationally Invariant Models.”
In 2023 IEEE Information Theory Workshop, 294–98. Institute of Electrical
and Electronics Engineers, 2023. https://doi.org/10.1109/ITW55543.2023.10160238.
ieee: Y. Xu, T. Q. Hou, S. S. Liang, and M. Mondelli, “Approximate message passing
for multi-layer estimation in rotationally invariant models,” in 2023 IEEE
Information Theory Workshop, Saint-Malo, France, 2023, pp. 294–298.
ista: 'Xu Y, Hou TQ, Liang SS, Mondelli M. 2023. Approximate message passing for
multi-layer estimation in rotationally invariant models. 2023 IEEE Information
Theory Workshop. ITW: Information Theory Workshop, 294–298.'
mla: Xu, Yizhou, et al. “Approximate Message Passing for Multi-Layer Estimation
in Rotationally Invariant Models.” 2023 IEEE Information Theory Workshop,
Institute of Electrical and Electronics Engineers, 2023, pp. 294–98, doi:10.1109/ITW55543.2023.10160238.
short: Y. Xu, T.Q. Hou, S.S. Liang, M. Mondelli, in:, 2023 IEEE Information Theory
Workshop, Institute of Electrical and Electronics Engineers, 2023, pp. 294–298.
conference:
end_date: 2023-04-28
location: Saint-Malo, France
name: 'ITW: Information Theory Workshop'
start_date: 2023-04-23
date_created: 2023-07-30T22:01:04Z
date_published: 2023-05-01T00:00:00Z
date_updated: 2023-12-13T11:35:46Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/ITW55543.2023.10160238
external_id:
arxiv:
- '2212.01572'
isi:
- '001031733100053'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2212.01572
month: '05'
oa: 1
oa_version: Preprint
page: 294-298
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2023 IEEE Information Theory Workshop
publication_identifier:
eissn:
- 2475-4218
isbn:
- '9798350301496'
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximate message passing for multi-layer estimation in rotationally invariant
models
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '12859'
abstract:
- lang: eng
text: 'Machine learning models are vulnerable to adversarial perturbations, and
a thought-provoking paper by Bubeck and Sellke has analyzed this phenomenon through
the lens of over-parameterization: interpolating smoothly the data requires significantly
more parameters than simply memorizing it. However, this "universal" law provides
only a necessary condition for robustness, and it is unable to discriminate between
models. In this paper, we address these gaps by focusing on empirical risk minimization
in two prototypical settings, namely, random features and the neural tangent kernel
(NTK). We prove that, for random features, the model is not robust for any degree
of over-parameterization, even when the necessary condition coming from the universal
law of robustness is satisfied. In contrast, for even activations, the NTK model
meets the universal lower bound, and it is robust as soon as the necessary condition
on over-parameterization is fulfilled. This also addresses a conjecture in prior
work by Bubeck, Li and Nagaraj. Our analysis decouples the effect of the kernel
of the model from an "interaction matrix", which describes the interaction with
the test data and captures the effect of the activation. Our theoretical results
are corroborated by numerical evidence on both synthetic and standard datasets
(MNIST, CIFAR-10).'
acknowledgement: "Simone Bombari and Marco Mondelli were partially supported by the
2019 Lopez-Loreta prize, and\r\nthe authors would like to thank Hamed Hassani for
helpful discussions.\r\n"
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
- first_name: Shayan
full_name: Kiyani, Shayan
id: f5a2b424-e339-11ed-8435-ff3b4fe70cf8
last_name: Kiyani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Bombari S, Kiyani S, Mondelli M. Beyond the universal law of robustness: Sharper
laws for random features and neural tangent kernels. In: Proceedings of the
40th International Conference on Machine Learning. Vol 202. ML Research Press;
2023:2738-2776.'
apa: 'Bombari, S., Kiyani, S., & Mondelli, M. (2023). Beyond the universal law
of robustness: Sharper laws for random features and neural tangent kernels. In
Proceedings of the 40th International Conference on Machine Learning (Vol.
202, pp. 2738–2776). Honolulu, HI, United States: ML Research Press.'
chicago: 'Bombari, Simone, Shayan Kiyani, and Marco Mondelli. “Beyond the Universal
Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels.”
In Proceedings of the 40th International Conference on Machine Learning,
202:2738–76. ML Research Press, 2023.'
ieee: 'S. Bombari, S. Kiyani, and M. Mondelli, “Beyond the universal law of robustness:
Sharper laws for random features and neural tangent kernels,” in Proceedings
of the 40th International Conference on Machine Learning, Honolulu, HI, United
States, 2023, vol. 202, pp. 2738–2776.'
ista: 'Bombari S, Kiyani S, Mondelli M. 2023. Beyond the universal law of robustness:
Sharper laws for random features and neural tangent kernels. Proceedings of the
40th International Conference on Machine Learning. ICML: International Conference
on Machine Learning, PMLR, vol. 202, 2738–2776.'
mla: 'Bombari, Simone, et al. “Beyond the Universal Law of Robustness: Sharper Laws
for Random Features and Neural Tangent Kernels.” Proceedings of the 40th International
Conference on Machine Learning, vol. 202, ML Research Press, 2023, pp. 2738–76.'
short: S. Bombari, S. Kiyani, M. Mondelli, in:, Proceedings of the 40th International
Conference on Machine Learning, ML Research Press, 2023, pp. 2738–2776.
conference:
end_date: 2023-07-29
location: Honolulu, HI, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2023-07-23
date_created: 2023-04-23T16:11:03Z
date_published: 2023-10-27T00:00:00Z
date_updated: 2024-02-06T07:42:00Z
day: '27'
department:
- _id: GradSch
- _id: MaMo
external_id:
arxiv:
- '2302.01629'
intvolume: ' 202'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2302.01629
month: '10'
oa: 1
oa_version: Preprint
page: 2738-2776
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 40th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/simone-bombari/beyond-universal-robustness
status: public
title: 'Beyond the universal law of robustness: Sharper laws for random features and
neural tangent kernels'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 202
year: '2023'
...
---
_id: '14921'
abstract:
- lang: eng
text: Neural collapse (NC) refers to the surprising structure of the last layer
of deep neural networks in the terminal phase of gradient descent training. Recently,
an increasing amount of experimental evidence has pointed to the propagation of
NC to earlier layers of neural networks. However, while the NC in the last layer
is well studied theoretically, much less is known about its multi-layered counterpart
- deep neural collapse (DNC). In particular, existing work focuses either on linear
layers or only on the last two layers at the price of an extra assumption. Our
paper fills this gap by generalizing the established analytical framework for
NC - the unconstrained features model - to multiple non-linear layers. Our key
technical contribution is to show that, in a deep unconstrained features model,
the unique global optimum for binary classification exhibits all the properties
typical of DNC. This explains the existing experimental evidence of DNC. We also
empirically show that (i) by optimizing deep unconstrained features models via
gradient descent, the resulting solution agrees well with our theory, and (ii)
trained networks recover the unconstrained features suitable for the occurrence
of DNC, thus supporting the validity of this modeling principle.
acknowledgement: M. M. is partially supported by the 2019 Lopez-Loreta Prize. The
authors would like to thank Eugenia Iofinova, Bernd Prach and Simone Bombari for
valuable feedback on the manuscript.
alternative_title:
- NeurIPS
article_processing_charge: No
author:
- first_name: Peter
full_name: Súkeník, Peter
id: d64d6a8d-eb8e-11eb-b029-96fd216dec3c
last_name: Súkeník
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Súkeník P, Mondelli M, Lampert C. Deep neural collapse is provably optimal
for the deep unconstrained features model. In: 37th Annual Conference on Neural
Information Processing Systems.'
apa: Súkeník, P., Mondelli, M., & Lampert, C. (n.d.). Deep neural collapse is
provably optimal for the deep unconstrained features model. In 37th Annual
Conference on Neural Information Processing Systems. New Orleans, LA, United
States.
chicago: Súkeník, Peter, Marco Mondelli, and Christoph Lampert. “Deep Neural Collapse
Is Provably Optimal for the Deep Unconstrained Features Model.” In 37th Annual
Conference on Neural Information Processing Systems, n.d.
ieee: P. Súkeník, M. Mondelli, and C. Lampert, “Deep neural collapse is provably
optimal for the deep unconstrained features model,” in 37th Annual Conference
on Neural Information Processing Systems, New Orleans, LA, United States.
ista: 'Súkeník P, Mondelli M, Lampert C. Deep neural collapse is provably optimal
for the deep unconstrained features model. 37th Annual Conference on Neural Information
Processing Systems. NeurIPS: Neural Information Processing Systems, NeurIPS, .'
mla: Súkeník, Peter, et al. “Deep Neural Collapse Is Provably Optimal for the Deep
Unconstrained Features Model.” 37th Annual Conference on Neural Information
Processing Systems.
short: P. Súkeník, M. Mondelli, C. Lampert, in:, 37th Annual Conference on Neural
Information Processing Systems, n.d.
conference:
end_date: 2023-12-16
location: New Orleans, LA, United States
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2023-12-10
date_created: 2024-02-02T11:17:41Z
date_published: 2023-12-15T00:00:00Z
date_updated: 2024-02-06T07:53:26Z
day: '15'
department:
- _id: MaMo
- _id: ChLa
external_id:
arxiv:
- '2305.13165'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2305.13165'
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 37th Annual Conference on Neural Information Processing Systems
publication_status: inpress
quality_controlled: '1'
status: public
title: Deep neural collapse is provably optimal for the deep unconstrained features
model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14924'
abstract:
- lang: eng
text: "The stochastic heavy ball method (SHB), also known as stochastic gradient
descent (SGD) with Polyak's momentum, is widely used in training neural networks.
However, despite the remarkable success of such algorithm in practice, its theoretical
characterization remains limited. In this paper, we focus on neural networks with
two and three layers and provide a rigorous understanding of the properties of
the solutions found by SHB: \\emph{(i)} stability after dropping out part of the
neurons, \\emph{(ii)} connectivity along a low-loss path, and \\emph{(iii)} convergence
to the global optimum.\r\nTo achieve this goal, we take a mean-field view and
relate the SHB dynamics to a certain partial differential equation in the limit
of large network widths. This mean-field perspective has inspired a recent line
of work focusing on SGD while, in contrast, our paper considers an algorithm with
momentum. More specifically, after proving existence and uniqueness of the limit
differential equations, we show convergence to the global optimum and give a quantitative
bound between the mean-field limit and the SHB dynamics of a finite-width network.
Armed with this last bound, we are able to establish the dropout-stability and
connectivity of SHB solutions."
acknowledgement: D. Wu and M. Mondelli are partially supported by the 2019 Lopez-Loreta
Prize. V. Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16_019/0000765
"Research Center for Informatics".
alternative_title:
- TMLR
article_processing_charge: No
author:
- first_name: Diyuan
full_name: Wu, Diyuan
id: 1a5914c2-896a-11ed-bdf8-fb80621a0635
last_name: Wu
- first_name: Vyacheslav
full_name: Kungurtsev, Vyacheslav
last_name: Kungurtsev
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Wu D, Kungurtsev V, Mondelli M. Mean-field analysis for heavy ball methods:
Dropout-stability, connectivity, and global convergence. In: Transactions on
Machine Learning Research. ML Research Press; 2023.'
apa: 'Wu, D., Kungurtsev, V., & Mondelli, M. (2023). Mean-field analysis for
heavy ball methods: Dropout-stability, connectivity, and global convergence. In
Transactions on Machine Learning Research. ML Research Press.'
chicago: 'Wu, Diyuan, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field Analysis
for Heavy Ball Methods: Dropout-Stability, Connectivity, and Global Convergence.”
In Transactions on Machine Learning Research. ML Research Press, 2023.'
ieee: 'D. Wu, V. Kungurtsev, and M. Mondelli, “Mean-field analysis for heavy ball
methods: Dropout-stability, connectivity, and global convergence,” in Transactions
on Machine Learning Research, 2023.'
ista: 'Wu D, Kungurtsev V, Mondelli M. 2023. Mean-field analysis for heavy ball
methods: Dropout-stability, connectivity, and global convergence. Transactions
on Machine Learning Research. , TMLR, .'
mla: 'Wu, Diyuan, et al. “Mean-Field Analysis for Heavy Ball Methods: Dropout-Stability,
Connectivity, and Global Convergence.” Transactions on Machine Learning Research,
ML Research Press, 2023.'
short: D. Wu, V. Kungurtsev, M. Mondelli, in:, Transactions on Machine Learning
Research, ML Research Press, 2023.
date_created: 2024-02-02T11:21:56Z
date_published: 2023-02-28T00:00:00Z
date_updated: 2024-02-06T08:53:15Z
day: '28'
department:
- _id: MaMo
external_id:
arxiv:
- '2210.06819'
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2210.06819
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Transactions on Machine Learning Research
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: 'Mean-field analysis for heavy ball methods: Dropout-stability, connectivity,
and global convergence'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14923'
abstract:
- lang: eng
text: We study the performance of a Bayesian statistician who estimates a rank-one
signal corrupted by non-symmetric rotationally invariant noise with a generic
distribution of singular values. As the signal-to-noise ratio and the noise structure
are unknown, a Gaussian setup is incorrectly assumed. We derive the exact analytic
expression for the error of the mismatched Bayes estimator and also provide the
analysis of an approximate message passing (AMP) algorithm. The first result exploits
the asymptotic behavior of spherical integrals for rectangular matrices and of
low-rank matrix perturbations; the second one relies on the design and analysis
of an auxiliary AMP. The numerical experiments show that there is a performance
gap between the AMP and Bayes estimators, which is due to the incorrect estimation
of the signal norm.
article_processing_charge: No
author:
- first_name: Teng
full_name: Fu, Teng
last_name: Fu
- first_name: YuHao
full_name: Liu, YuHao
last_name: Liu
- first_name: Jean
full_name: Barbier, Jean
last_name: Barbier
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: ShanSuo
full_name: Liang, ShanSuo
last_name: Liang
- first_name: TianQi
full_name: Hou, TianQi
last_name: Hou
citation:
ama: 'Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. Mismatched estimation
of non-symmetric rank-one matrices corrupted by structured noise. In: Proceedings
of 2023 IEEE International Symposium on Information Theory. IEEE. doi:10.1109/isit54713.2023.10206671'
apa: 'Fu, T., Liu, Y., Barbier, J., Mondelli, M., Liang, S., & Hou, T. (n.d.).
Mismatched estimation of non-symmetric rank-one matrices corrupted by structured
noise. In Proceedings of 2023 IEEE International Symposium on Information Theory.
Taipei, Taiwan: IEEE. https://doi.org/10.1109/isit54713.2023.10206671'
chicago: Fu, Teng, YuHao Liu, Jean Barbier, Marco Mondelli, ShanSuo Liang, and TianQi
Hou. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured
Noise.” In Proceedings of 2023 IEEE International Symposium on Information
Theory. IEEE, n.d. https://doi.org/10.1109/isit54713.2023.10206671.
ieee: T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, and T. Hou, “Mismatched
estimation of non-symmetric rank-one matrices corrupted by structured noise,”
in Proceedings of 2023 IEEE International Symposium on Information Theory,
Taipei, Taiwan.
ista: 'Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. Mismatched estimation
of non-symmetric rank-one matrices corrupted by structured noise. Proceedings
of 2023 IEEE International Symposium on Information Theory. ISIT: IEEE International
Symposium on Information Theory.'
mla: Fu, Teng, et al. “Mismatched Estimation of Non-Symmetric Rank-One Matrices
Corrupted by Structured Noise.” Proceedings of 2023 IEEE International Symposium
on Information Theory, IEEE, doi:10.1109/isit54713.2023.10206671.
short: T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, T. Hou, in:, Proceedings
of 2023 IEEE International Symposium on Information Theory, IEEE, n.d.
conference:
end_date: 2023-06-30
location: Taipei, Taiwan
name: 'ISIT: IEEE International Symposium on Information Theory'
start_date: 2023-06-25
date_created: 2024-02-02T11:20:39Z
date_published: 2023-06-30T00:00:00Z
date_updated: 2024-02-14T14:34:03Z
day: '30'
department:
- _id: MaMo
doi: 10.1109/isit54713.2023.10206671
external_id:
arxiv:
- '2302.03306'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2302.03306
month: '06'
oa: 1
oa_version: Preprint
publication: Proceedings of 2023 IEEE International Symposium on Information Theory
publication_status: inpress
publisher: IEEE
quality_controlled: '1'
status: public
title: Mismatched estimation of non-symmetric rank-one matrices corrupted by structured
noise
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14922'
abstract:
- lang: eng
text: 'We propose a novel approach to concentration for non-independent random variables.
The main idea is to ``pretend'''' that the random variables are independent and
pay a multiplicative price measuring how far they are from actually being independent.
This price is encapsulated in the Hellinger integral between the joint and the
product of the marginals, which is then upper bounded leveraging tensorisation
properties. Our bounds represent a natural generalisation of concentration inequalities
in the presence of dependence: we recover exactly the classical bounds (McDiarmid''s
inequality) when the random variables are independent. Furthermore, in a ``large
deviations'''' regime, we obtain the same decay in the probability as for the
independent case, even when the random variables display non-trivial dependencies.
To show this, we consider a number of applications of interest. First, we provide
a bound for Markov chains with finite state space. Then, we consider the Simple
Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian
setting in which the stochastic process depends on its entire past. To conclude,
we propose an application to Markov Chain Monte Carlo methods, where our approach
leads to an improved lower bound on the minimum burn-in period required to reach
a certain accuracy. In all of these settings, we provide a regime of parameters
in which our bound fares better than what the state of the art can provide.'
acknowledgement: The authors are partially supported by the 2019 Lopez-Loreta Prize.
They would also like to thank Professor Jan Maas for providing valuable suggestions
and comments on an early version of the work.
article_processing_charge: No
author:
- first_name: Amedeo Roberto
full_name: Esposito, Amedeo Roberto
id: 9583e921-e1ad-11ec-9862-cef099626dc9
last_name: Esposito
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Esposito AR, Mondelli M. Concentration without independence via information
measures. In: Proceedings of 2023 IEEE International Symposium on Information
Theory. IEEE; 2023:400-405. doi:10.1109/isit54713.2023.10206899'
apa: 'Esposito, A. R., & Mondelli, M. (2023). Concentration without independence
via information measures. In Proceedings of 2023 IEEE International Symposium
on Information Theory (pp. 400–405). Taipei, Taiwan: IEEE. https://doi.org/10.1109/isit54713.2023.10206899'
chicago: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
via Information Measures.” In Proceedings of 2023 IEEE International Symposium
on Information Theory, 400–405. IEEE, 2023. https://doi.org/10.1109/isit54713.2023.10206899.
ieee: A. R. Esposito and M. Mondelli, “Concentration without independence via information
measures,” in Proceedings of 2023 IEEE International Symposium on Information
Theory, Taipei, Taiwan, 2023, pp. 400–405.
ista: 'Esposito AR, Mondelli M. 2023. Concentration without independence via information
measures. Proceedings of 2023 IEEE International Symposium on Information Theory.
ISIT: IEEE International Symposium on Information Theory, 400–405.'
mla: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
via Information Measures.” Proceedings of 2023 IEEE International Symposium
on Information Theory, IEEE, 2023, pp. 400–05, doi:10.1109/isit54713.2023.10206899.
short: A.R. Esposito, M. Mondelli, in:, Proceedings of 2023 IEEE International Symposium
on Information Theory, IEEE, 2023, pp. 400–405.
conference:
end_date: 2023-06-30
location: Taipei, Taiwan
name: 'ISIT: IEEE International Symposium on Information Theory'
start_date: 2023-06-25
date_created: 2024-02-02T11:18:40Z
date_published: 2023-06-30T00:00:00Z
date_updated: 2024-03-25T07:15:51Z
day: '30'
department:
- _id: MaMo
doi: 10.1109/isit54713.2023.10206899
external_id:
arxiv:
- '2303.07245'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2303.07245
month: '06'
oa: 1
oa_version: Preprint
page: 400-405
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of 2023 IEEE International Symposium on Information Theory
publication_identifier:
eisbn:
- '9781665475549'
eissn:
- 2157-8117
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '15172'
relation: later_version
status: public
status: public
title: Concentration without independence via information measures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '11420'
abstract:
- lang: eng
text: 'Understanding the properties of neural networks trained via stochastic gradient
descent (SGD) is at the heart of the theory of deep learning. In this work, we
take a mean-field view, and consider a two-layer ReLU network trained via noisy-SGD
for a univariate regularized regression problem. Our main result is that SGD with
vanishingly small noise injected in the gradients is biased towards a simple solution:
at convergence, the ReLU network implements a piecewise linear map of the inputs,
and the number of “knot” points -- i.e., points where the tangent of the ReLU
network estimator changes -- between two consecutive training inputs is at most
three. In particular, as the number of neurons of the network grows, the SGD dynamics
is captured by the solution of a gradient flow and, at convergence, the distribution
of the weights approaches the unique minimizer of a related free energy, which
has a Gibbs form. Our key technical contribution consists in the analysis of the
estimator resulting from this minimizer: we show that its second derivative vanishes
everywhere, except at some specific locations which represent the “knot” points.
We also provide empirical evidence that knots at locations distinct from the data
points might occur, as predicted by our theory.'
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"
article_processing_charge: No
article_type: original
author:
- first_name: Aleksandr
full_name: Shevchenko, Aleksandr
id: F2B06EC2-C99E-11E9-89F0-752EE6697425
last_name: Shevchenko
- first_name: Vyacheslav
full_name: Kungurtsev, Vyacheslav
last_name: Kungurtsev
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Shevchenko A, Kungurtsev V, Mondelli M. Mean-field analysis of piecewise linear
solutions for wide ReLU networks. Journal of Machine Learning Research.
2022;23(130):1-55.
apa: Shevchenko, A., Kungurtsev, V., & Mondelli, M. (2022). Mean-field analysis
of piecewise linear solutions for wide ReLU networks. Journal of Machine Learning
Research. Journal of Machine Learning Research.
chicago: Shevchenko, Aleksandr, Vyacheslav Kungurtsev, and Marco Mondelli. “Mean-Field
Analysis of Piecewise Linear Solutions for Wide ReLU Networks.” Journal of
Machine Learning Research. Journal of Machine Learning Research, 2022.
ieee: A. Shevchenko, V. Kungurtsev, and M. Mondelli, “Mean-field analysis of piecewise
linear solutions for wide ReLU networks,” Journal of Machine Learning Research,
vol. 23, no. 130. Journal of Machine Learning Research, pp. 1–55, 2022.
ista: Shevchenko A, Kungurtsev V, Mondelli M. 2022. Mean-field analysis of piecewise
linear solutions for wide ReLU networks. Journal of Machine Learning Research.
23(130), 1–55.
mla: Shevchenko, Aleksandr, et al. “Mean-Field Analysis of Piecewise Linear Solutions
for Wide ReLU Networks.” Journal of Machine Learning Research, vol. 23,
no. 130, Journal of Machine Learning Research, 2022, pp. 1–55.
short: A. Shevchenko, V. Kungurtsev, M. Mondelli, Journal of Machine Learning Research
23 (2022) 1–55.
date_created: 2022-05-29T22:01:54Z
date_published: 2022-04-01T00:00:00Z
date_updated: 2022-05-30T08:34:14Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
- _id: DaAl
external_id:
arxiv:
- '2111.02278'
file:
- access_level: open_access
checksum: d4ff5d1affb34848b5c5e4002483fc62
content_type: application/pdf
creator: cchlebak
date_created: 2022-05-30T08:22:55Z
date_updated: 2022-05-30T08:22:55Z
file_id: '11422'
file_name: 21-1365.pdf
file_size: 1521701
relation: main_file
success: 1
file_date_updated: 2022-05-30T08:22:55Z
has_accepted_license: '1'
intvolume: ' 23'
issue: '130'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 1-55
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Journal of Machine Learning Research
publication_identifier:
eissn:
- 1533-7928
issn:
- 1532-4435
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
related_material:
link:
- relation: other
url: https://www.jmlr.org/papers/v23/21-1365.html
scopus_import: '1'
status: public
title: Mean-field analysis of piecewise linear solutions for wide ReLU networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 23
year: '2022'
...
---
_id: '12016'
abstract:
- lang: eng
text: We consider the problem of coded distributed computing using polar codes.
The average execution time of a coded computing system is related to the error
probability for transmission over the binary erasure channel in recent work by
Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes
is investigated. In this paper, we focus on polar codes and unveil a connection
between the average execution time and the scaling exponent μ of the family of
codes. In the finite-length characterization of polar codes, the scaling exponent
is a key object capturing the speed of convergence to capacity. In particular,
we show that (i) the gap between the normalized average execution time of polar
codes and that of optimal MDS codes is O(n –1/μ ), and (ii) this upper bound can
be improved to roughly O(n –1/2 ) by considering polar codes with large kernels.
We conjecture that these bounds could be improved to O(n –2/μ ) and O(n –1 ),
respectively, and provide a heuristic argument as well as numerical evidence supporting
this view.
acknowledgement: D. Fathollahi and M. Mondelli were partially supported by the 2019
Lopez-Loreta Prize. The authors thank Hamed Hassani and Hessam Mahdavifar for helpful
discussions.
article_processing_charge: No
author:
- first_name: Dorsa
full_name: Fathollahi, Dorsa
last_name: Fathollahi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Fathollahi D, Mondelli M. Polar coded computing: The role of the scaling exponent.
In: 2022 IEEE International Symposium on Information Theory. Vol 2022.
IEEE; 2022:2154-2159. doi:10.1109/ISIT50566.2022.9834712'
apa: 'Fathollahi, D., & Mondelli, M. (2022). Polar coded computing: The role
of the scaling exponent. In 2022 IEEE International Symposium on Information
Theory (Vol. 2022, pp. 2154–2159). Espoo, Finland: IEEE. https://doi.org/10.1109/ISIT50566.2022.9834712'
chicago: 'Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role
of the Scaling Exponent.” In 2022 IEEE International Symposium on Information
Theory, 2022:2154–59. IEEE, 2022. https://doi.org/10.1109/ISIT50566.2022.9834712.'
ieee: 'D. Fathollahi and M. Mondelli, “Polar coded computing: The role of the scaling
exponent,” in 2022 IEEE International Symposium on Information Theory,
Espoo, Finland, 2022, vol. 2022, pp. 2154–2159.'
ista: 'Fathollahi D, Mondelli M. 2022. Polar coded computing: The role of the scaling
exponent. 2022 IEEE International Symposium on Information Theory. ISIT: Internation
Symposium on Information Theory vol. 2022, 2154–2159.'
mla: 'Fathollahi, Dorsa, and Marco Mondelli. “Polar Coded Computing: The Role of
the Scaling Exponent.” 2022 IEEE International Symposium on Information Theory,
vol. 2022, IEEE, 2022, pp. 2154–59, doi:10.1109/ISIT50566.2022.9834712.'
short: D. Fathollahi, M. Mondelli, in:, 2022 IEEE International Symposium on Information
Theory, IEEE, 2022, pp. 2154–2159.
conference:
end_date: 2022-07-01
location: Espoo, Finland
name: 'ISIT: Internation Symposium on Information Theory'
start_date: 2022-06-26
date_created: 2022-09-04T22:02:05Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2022-09-05T10:35:40Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834712
external_id:
arxiv:
- '2201.10082'
intvolume: ' 2022'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2201.10082
month: '08'
oa: 1
oa_version: Preprint
page: 2154-2159
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
isbn:
- '9781665421591'
issn:
- 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Polar coded computing: The role of the scaling exponent'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022
year: '2022'
...
---
_id: '12540'
abstract:
- lang: eng
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.
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.
article_number: '22'
article_processing_charge: No
author:
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
- first_name: Kevin
full_name: Kögler, Kevin
id: 94ec913c-dc85-11ea-9058-e5051ab2428b
last_name: Kögler
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Venkataramanan R, Kögler K, Mondelli M. Estimation in rotationally invariant
generalized linear models via approximate message passing. In: Proceedings
of the 39th International Conference on Machine Learning. Vol 162. ML Research
Press; 2022.'
apa: 'Venkataramanan, R., Kögler, K., & Mondelli, M. (2022). Estimation in rotationally
invariant generalized linear models via approximate message passing. In Proceedings
of the 39th International Conference on Machine Learning (Vol. 162). Baltimore,
MD, United States: ML Research Press.'
chicago: Venkataramanan, Ramji, Kevin Kögler, and Marco Mondelli. “Estimation in
Rotationally Invariant Generalized Linear Models via Approximate Message Passing.”
In Proceedings of the 39th International Conference on Machine Learning,
Vol. 162. 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 Proceedings
of the 39th International Conference on Machine Learning, Baltimore, MD, United
States, 2022, vol. 162.
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.'
mla: Venkataramanan, Ramji, et al. “Estimation in Rotationally Invariant Generalized
Linear Models via Approximate Message Passing.” Proceedings of the 39th International
Conference on Machine Learning, vol. 162, 22, ML Research Press, 2022.
short: R. Venkataramanan, K. Kögler, M. Mondelli, in:, Proceedings of the 39th International
Conference on Machine Learning, ML Research Press, 2022.
conference:
end_date: 2022-07-23
location: Baltimore, MD, United States
name: 'ICML: International Conference on Machine Learning'
start_date: 2022-07-17
date_created: 2023-02-10T13:49:04Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2023-02-13T10:54:58Z
ddc:
- '000'
department:
- _id: MaMo
file:
- access_level: open_access
checksum: 67436eb0a660789514cdf9db79e84683
content_type: application/pdf
creator: dernst
date_created: 2023-02-13T10:53:11Z
date_updated: 2023-02-13T10:53:11Z
file_id: '12547'
file_name: 2022_PMLR_Venkataramanan.pdf
file_size: 2341343
relation: main_file
success: 1
file_date_updated: 2023-02-13T10:53:11Z
has_accepted_license: '1'
intvolume: ' 162'
language:
- iso: eng
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 39th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: Estimation in rotationally invariant generalized linear models via approximate
message passing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 162
year: '2022'
...
---
_id: '12536'
abstract:
- lang: eng
text: 'We consider the problem of estimating a rank-1 signal corrupted by structured
rotationally invariant noise, and address the following question: how well do
inference algorithms perform when the noise statistics is unknown and hence Gaussian
noise is assumed? While the matched Bayes-optimal setting with unstructured noise
is well understood, the analysis of this mismatched problem is only at its premises.
In this paper, we make a step towards understanding the effect of the strong source
of mismatch which is the noise statistics. Our main technical contribution is
the rigorous analysis of a Bayes estimator and of an approximate message passing
(AMP) algorithm, both of which incorrectly assume a Gaussian setup. The first
result exploits the theory of spherical integrals and of low-rank matrix perturbations;
the idea behind the second one is to design and analyze an artificial AMP which,
by taking advantage of the flexibility in the denoisers, is able to "correct"
the mismatch. Armed with these sharp asymptotic characterizations, we unveil a
rich and often unexpected phenomenology. For example, despite AMP is in principle
designed to efficiently compute the Bayes estimator, the former is outperformed
by the latter in terms of mean-square error. We show that this performance gap
is due to an incorrect estimation of the signal norm. In fact, when the SNR is
large enough, the overlaps of the AMP and the Bayes estimator coincide, and they
even match those of optimal estimators taking into account the structure of the
noise.'
article_number: '2205.10009'
article_processing_charge: No
author:
- first_name: Jean
full_name: Barbier, Jean
last_name: Barbier
- first_name: TianQi
full_name: Hou, TianQi
last_name: Hou
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Manuel
full_name: Saenz, Manuel
last_name: Saenz
citation:
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? arXiv.
doi:10.48550/arXiv.2205.10009'
apa: 'Barbier, J., Hou, T., Mondelli, M., & Saenz, M. (n.d.). The price of ignorance:
How much does it cost to forget noise structure in low-rank matrix estimation?
arXiv. https://doi.org/10.48550/arXiv.2205.10009'
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?” ArXiv, n.d. https://doi.org/10.48550/arXiv.2205.10009.'
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?,” arXiv.
.'
ista: '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? arXiv, 2205.10009.'
mla: 'Barbier, Jean, et al. “The Price of Ignorance: How Much Does It Cost to Forget
Noise Structure in Low-Rank Matrix Estimation?” ArXiv, 2205.10009, doi:10.48550/arXiv.2205.10009.'
short: J. Barbier, T. Hou, M. Mondelli, M. Saenz, ArXiv (n.d.).
date_created: 2023-02-10T13:45:41Z
date_published: 2022-05-20T00:00:00Z
date_updated: 2023-02-16T09:41:25Z
day: '20'
department:
- _id: MaMo
doi: 10.48550/arXiv.2205.10009
external_id:
arxiv:
- '2205.10009'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2205.10009
month: '05'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: accepted
status: public
title: 'The price of ignorance: How much does it cost to forget noise structure in
low-rank matrix estimation?'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '12233'
abstract:
- lang: eng
text: A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes
based on successive permutations (SP) of the codeword is presented. A low-complexity
SP scheme applied to a subset of the symmetry group of RM codes is first proposed
to carefully select a good codeword permutation on the fly. Then, the proposed
SP technique is integrated into an improved RLD algorithm that initializes different
decoding paths with random codeword permutations, which are sampled from the full
symmetry group of RM codes. Finally, efficient latency and complexity reduction
schemes are introduced that virtually preserve the error-correction performance
of the proposed decoder. Simulation results demonstrate that at the target frame
error rate of 10−3 for the RM code of length 256 with 163 information bits, the
proposed decoder reduces 6% of the computational complexity and 22% of the decoding
latency of the state-of-the-art semi-parallel simplified successive-cancellation
decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from
the full symmetry group of RM codes, while relatively maintaining the error-correction
performance and memory consumption of the semi-parallel permuted SSC-FHT decoder.
article_processing_charge: No
article_type: original
author:
- first_name: Nghia
full_name: Doan, Nghia
last_name: Doan
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Warren J.
full_name: Gross, Warren J.
last_name: Gross
citation:
ama: Doan N, Hashemi SA, Mondelli M, Gross WJ. Decoding Reed-Muller codes with successive
codeword permutations. IEEE Transactions on Communications. 2022;70(11):7134-7145.
doi:10.1109/tcomm.2022.3211101
apa: Doan, N., Hashemi, S. A., Mondelli, M., & Gross, W. J. (2022). Decoding
Reed-Muller codes with successive codeword permutations. IEEE Transactions
on Communications. Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/tcomm.2022.3211101
chicago: Doan, Nghia, Seyyed Ali Hashemi, Marco Mondelli, and Warren J. Gross. “Decoding
Reed-Muller Codes with Successive Codeword Permutations.” IEEE Transactions
on Communications. Institute of Electrical and Electronics Engineers, 2022.
https://doi.org/10.1109/tcomm.2022.3211101.
ieee: N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross, “Decoding Reed-Muller
codes with successive codeword permutations,” IEEE Transactions on Communications,
vol. 70, no. 11. Institute of Electrical and Electronics Engineers, pp. 7134–7145,
2022.
ista: Doan N, Hashemi SA, Mondelli M, Gross WJ. 2022. Decoding Reed-Muller codes
with successive codeword permutations. IEEE Transactions on Communications. 70(11),
7134–7145.
mla: Doan, Nghia, et al. “Decoding Reed-Muller Codes with Successive Codeword Permutations.”
IEEE Transactions on Communications, vol. 70, no. 11, Institute of Electrical
and Electronics Engineers, 2022, pp. 7134–45, doi:10.1109/tcomm.2022.3211101.
short: N. Doan, S.A. Hashemi, M. Mondelli, W.J. Gross, IEEE Transactions on Communications
70 (2022) 7134–7145.
date_created: 2023-01-16T09:50:38Z
date_published: 2022-11-01T00:00:00Z
date_updated: 2023-08-04T09:34:43Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/tcomm.2022.3211101
external_id:
arxiv:
- '2109.02122'
isi:
- '000937284600006'
intvolume: ' 70'
isi: 1
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.02122'
month: '11'
oa: 1
oa_version: Preprint
page: 7134-7145
publication: IEEE Transactions on Communications
publication_identifier:
eissn:
- 1558-0857
issn:
- 0090-6778
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decoding Reed-Muller codes with successive codeword permutations
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 70
year: '2022'
...
---
_id: '10364'
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.'
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
article_type: original
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Arman
full_name: Fazeli, Arman
last_name: Fazeli
- first_name: Alexander
full_name: Vardy, Alexander
last_name: Vardy
- first_name: John
full_name: Cioffi, John
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
ama: Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism
versus latency in simplified successive-cancellation decoding of polar codes.
IEEE Transactions on Wireless Communications. 2022;21(6):3909-3920. doi:10.1109/TWC.2021.3125626
apa: Hashemi, S. A., 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. Institute
of Electrical and Electronics Engineers. https://doi.org/10.1109/TWC.2021.3125626
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.” IEEE Transactions on Wireless Communications.
Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/TWC.2021.3125626.
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,” IEEE Transactions on Wireless Communications, vol. 21, no.
6. Institute of Electrical and Electronics Engineers, pp. 3909–3920, 2022.
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.
mla: Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation
Decoding of Polar Codes.” IEEE Transactions on Wireless Communications,
vol. 21, no. 6, Institute of Electrical and Electronics Engineers, 2022, pp. 3909–20,
doi:10.1109/TWC.2021.3125626.
short: S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith,
IEEE Transactions on Wireless Communications 21 (2022) 3909–3920.
date_created: 2021-11-28T23:01:29Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-08-14T06:55:57Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TWC.2021.3125626
external_id:
arxiv:
- '2012.13378'
isi:
- '000809406400028'
intvolume: ' 21'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.13378
month: '06'
oa: 1
oa_version: Preprint
page: 3909-3920
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: IEEE Transactions on Wireless Communications
publication_identifier:
eissn:
- 1558-2248
issn:
- 1536-1276
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
record:
- id: '10053'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Parallelism versus latency in simplified successive-cancellation decoding of
polar codes
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 21
year: '2022'
...
---
_id: '12538'
abstract:
- lang: eng
text: In this paper, we study the compression of a target two-layer neural network
with N nodes into a compressed network with MIEEE Information Theory Workshop.
2022:588-593. doi:10.1109/ITW54588.2022.9965870
apa: 'Amani, M. H., Bombari, S., Mondelli, M., Pukdee, R., & Rini, S. (2022).
Sharp asymptotics on the compression of two-layer neural networks. IEEE Information
Theory Workshop. Mumbai, India: IEEE. https://doi.org/10.1109/ITW54588.2022.9965870'
chicago: Amani, Mohammad Hossein, Simone Bombari, Marco Mondelli, Rattana Pukdee,
and Stefano Rini. “Sharp Asymptotics on the Compression of Two-Layer Neural Networks.”
IEEE Information Theory Workshop. IEEE, 2022. https://doi.org/10.1109/ITW54588.2022.9965870.
ieee: M. H. Amani, S. Bombari, M. Mondelli, R. Pukdee, and S. Rini, “Sharp asymptotics
on the compression of two-layer neural networks,” IEEE Information Theory Workshop.
IEEE, pp. 588–593, 2022.
ista: Amani MH, Bombari S, Mondelli M, Pukdee R, Rini S. 2022. Sharp asymptotics
on the compression of two-layer neural networks. IEEE Information Theory Workshop.,
588–593.
mla: Amani, Mohammad Hossein, et al. “Sharp Asymptotics on the Compression of Two-Layer
Neural Networks.” IEEE Information Theory Workshop, IEEE, 2022, pp. 588–93,
doi:10.1109/ITW54588.2022.9965870.
short: M.H. Amani, S. Bombari, M. Mondelli, R. Pukdee, S. Rini, IEEE Information
Theory Workshop (2022) 588–593.
conference:
end_date: 2022-11-09
location: Mumbai, India
name: 'ITW: Information Theory Workshop'
start_date: 2022-11-01
date_created: 2023-02-10T13:47:56Z
date_published: 2022-11-16T00:00:00Z
date_updated: 2023-12-18T11:31:47Z
day: '16'
department:
- _id: MaMo
doi: 10.1109/ITW54588.2022.9965870
external_id:
arxiv:
- '2205.08199'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2205.08199'
month: '11'
oa: 1
oa_version: Preprint
page: 588-593
publication: IEEE Information Theory Workshop
publication_identifier:
isbn:
- '9781665483414'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sharp asymptotics on the compression of two-layer neural networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '12537'
abstract:
- lang: eng
text: 'The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide
memorization, optimization and generalization guarantees in deep neural networks.
A line of work has studied the NTK spectrum for two-layer and deep networks with
at least a layer with Ω(N) neurons, N being the number of training samples. Furthermore,
there is increasing evidence suggesting that deep networks with sub-linear layer
widths are powerful memorizers and optimizers, as long as the number of parameters
exceeds the number of samples. Thus, a natural open question is whether the NTK
is well conditioned in such a challenging sub-linear setup. In this paper, we
answer this question in the affirmative. Our key technical contribution is a lower
bound on the smallest NTK eigenvalue for deep networks with the minimum possible
over-parameterization: the number of parameters is roughly Ω(N) and, hence, the
number of neurons is as little as Ω(N−−√). To showcase the applicability of our
NTK bounds, we provide two results concerning memorization capacity and optimization
guarantees for gradient descent training.'
acknowledgement: "The authors were partially supported by the 2019 Lopez-Loreta prize,
and they would like to thank\r\nQuynh Nguyen, Mahdi Soltanolkotabi and Adel Javanmard
for helpful discussions.\r\n"
article_processing_charge: No
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
- first_name: Mohammad Hossein
full_name: Amani, Mohammad Hossein
last_name: Amani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Bombari S, Amani MH, Mondelli M. Memorization and optimization in deep neural
networks with minimum over-parameterization. In: 36th Conference on Neural
Information Processing Systems. Vol 35. Curran Associates; 2022:7628-7640.'
apa: Bombari, S., Amani, M. H., & Mondelli, M. (2022). Memorization and optimization
in deep neural networks with minimum over-parameterization. In 36th Conference
on Neural Information Processing Systems (Vol. 35, pp. 7628–7640). Curran
Associates.
chicago: Bombari, Simone, Mohammad Hossein Amani, and Marco Mondelli. “Memorization
and Optimization in Deep Neural Networks with Minimum Over-Parameterization.”
In 36th Conference on Neural Information Processing Systems, 35:7628–40.
Curran Associates, 2022.
ieee: S. Bombari, M. H. Amani, and M. Mondelli, “Memorization and optimization in
deep neural networks with minimum over-parameterization,” in 36th Conference
on Neural Information Processing Systems, 2022, vol. 35, pp. 7628–7640.
ista: Bombari S, Amani MH, Mondelli M. 2022. Memorization and optimization in deep
neural networks with minimum over-parameterization. 36th Conference on Neural
Information Processing Systems. vol. 35, 7628–7640.
mla: Bombari, Simone, et al. “Memorization and Optimization in Deep Neural Networks
with Minimum Over-Parameterization.” 36th Conference on Neural Information
Processing Systems, vol. 35, Curran Associates, 2022, pp. 7628–40.
short: S. Bombari, M.H. Amani, M. Mondelli, in:, 36th Conference on Neural Information
Processing Systems, Curran Associates, 2022, pp. 7628–7640.
date_created: 2023-02-10T13:46:37Z
date_published: 2022-07-24T00:00:00Z
date_updated: 2023-12-18T11:39:09Z
day: '24'
department:
- _id: MaMo
external_id:
arxiv:
- '2205.10217'
intvolume: ' 35'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2205.10217'
month: '07'
oa: 1
oa_version: Preprint
page: 7628-7640
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 36th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713871088'
publication_status: published
publisher: Curran Associates
quality_controlled: '1'
status: public
title: Memorization and optimization in deep neural networks with minimum over-parameterization
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2022'
...
---
_id: '12480'
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.'
acknowledgement: "The authors would like to thank Andrea Montanari for helpful discussions.\r\nM
Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R Venkataramanan
was partially supported by the Alan Turing Institute under the EPSRC Grant\r\nEP/N510129/1."
article_number: '114003'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: 'Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization
for generalized linear models. Journal of Statistical Mechanics: Theory and
Experiment. 2022;2022(11). doi:10.1088/1742-5468/ac9828'
apa: 'Mondelli, M., & Venkataramanan, R. (2022). Approximate message passing
with spectral initialization for generalized linear models. Journal of Statistical
Mechanics: Theory and Experiment. IOP Publishing. https://doi.org/10.1088/1742-5468/ac9828'
chicago: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing
with Spectral Initialization for Generalized Linear Models.” Journal of Statistical
Mechanics: Theory and Experiment. IOP Publishing, 2022. https://doi.org/10.1088/1742-5468/ac9828.'
ieee: 'M. Mondelli and R. Venkataramanan, “Approximate message passing with spectral
initialization for generalized linear models,” Journal of Statistical Mechanics:
Theory and Experiment, vol. 2022, no. 11. IOP Publishing, 2022.'
ista: 'Mondelli M, Venkataramanan R. 2022. Approximate message passing with spectral
initialization for generalized linear models. Journal of Statistical Mechanics:
Theory and Experiment. 2022(11), 114003.'
mla: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with
Spectral Initialization for Generalized Linear Models.” Journal of Statistical
Mechanics: Theory and Experiment, vol. 2022, no. 11, 114003, IOP Publishing,
2022, doi:10.1088/1742-5468/ac9828.'
short: 'M. Mondelli, R. Venkataramanan, Journal of Statistical Mechanics: Theory
and Experiment 2022 (2022).'
date_created: 2023-02-02T08:31:57Z
date_published: 2022-11-24T00:00:00Z
date_updated: 2024-03-07T10:36:52Z
day: '24'
ddc:
- '510'
- '530'
department:
- _id: MaMo
doi: 10.1088/1742-5468/ac9828
external_id:
isi:
- '000889589900001'
file:
- access_level: open_access
checksum: 01411ffa76d3e380a0446baeb89b1ef7
content_type: application/pdf
creator: dernst
date_created: 2023-02-02T08:35:52Z
date_updated: 2023-02-02T08:35:52Z
file_id: '12481'
file_name: 2022_JourStatisticalMechanics_Mondelli.pdf
file_size: 1729997
relation: main_file
success: 1
file_date_updated: 2023-02-02T08:35:52Z
has_accepted_license: '1'
intvolume: ' 2022'
isi: 1
issue: '11'
keyword:
- Statistics
- Probability and Uncertainty
- Statistics and Probability
- Statistical and Nonlinear Physics
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
issn:
- 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
record:
- id: '10598'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Approximate message passing with spectral initialization for generalized linear
models
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022
year: '2022'
...
---
_id: '10595'
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.'
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)."
alternative_title:
- Proceedings of Machine Learning Research
article_processing_charge: No
author:
- first_name: Quynh
full_name: Nguyen, Quynh
last_name: Nguyen
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Guido F
full_name: Montufar, Guido F
last_name: Montufar
citation:
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.
Proceedings of the 38th International Conference on Machine Learning. Vol
139. ML Research Press; 2021:8119-8129.'
apa: 'Nguyen, Q., Mondelli, M., & Montufar, G. F. (2021). Tight bounds on the
smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In M.
Meila & T. Zhang (Eds.), Proceedings of the 38th International Conference
on Machine Learning (Vol. 139, pp. 8119–8129). Virtual: ML Research Press.'
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 Proceedings
of the 38th International Conference on Machine Learning, edited by Marina
Meila and Tong Zhang, 139:8119–29. ML Research Press, 2021.
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 Proceedings
of the 38th International Conference on Machine Learning, Virtual, 2021, vol.
139, pp. 8119–8129.
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.'
mla: Nguyen, Quynh, et al. “Tight Bounds on the Smallest Eigenvalue of the Neural
Tangent Kernel for Deep ReLU Networks.” Proceedings of the 38th International
Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol.
139, ML Research Press, 2021, pp. 8119–29.
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.
conference:
end_date: 2021-07-24
location: Virtual
name: 'ICML: International Conference on Machine Learning'
start_date: 2021-07-18
date_created: 2022-01-03T10:57:49Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2022-01-04T09:59:21Z
department:
- _id: MaMo
editor:
- first_name: Marina
full_name: Meila, Marina
last_name: Meila
- first_name: Tong
full_name: Zhang, Tong
last_name: Zhang
external_id:
arxiv:
- '2012.11654'
intvolume: ' 139'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://proceedings.mlr.press/v139/nguyen21g.html
oa: 1
oa_version: Published Version
page: 8119-8129
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 38th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep
ReLU networks
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 139
year: '2021'
...
---
_id: '10599'
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.
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.
article_processing_charge: No
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: John
full_name: Cioffi, John
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
ama: 'Hashemi SA, Mondelli M, Cioffi J, Goldsmith A. Successive syndrome-check decoding
of polar codes. In: Proceedings of the 55th Asilomar Conference on Signals,
Systems, and Computers. Vol 2021-October. Institute of Electrical and Electronics
Engineers; 2021:943-947. doi:10.1109/IEEECONF53345.2021.9723394'
apa: 'Hashemi, S. A., Mondelli, M., Cioffi, J., & Goldsmith, A. (2021). Successive
syndrome-check decoding of polar codes. In Proceedings of the 55th Asilomar
Conference on Signals, Systems, and Computers (Vol. 2021–October, pp. 943–947).
Virtual, Pacific Grove, CA, United States: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/IEEECONF53345.2021.9723394'
chicago: Hashemi, Seyyed Ali, Marco Mondelli, John Cioffi, and Andrea Goldsmith.
“Successive Syndrome-Check Decoding of Polar Codes.” In Proceedings of the
55th Asilomar Conference on Signals, Systems, and Computers, 2021–October:943–47.
Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/IEEECONF53345.2021.9723394.
ieee: S. A. Hashemi, M. Mondelli, J. Cioffi, and A. Goldsmith, “Successive syndrome-check
decoding of polar codes,” in Proceedings of the 55th Asilomar Conference on
Signals, Systems, and Computers, Virtual, Pacific Grove, CA, United States,
2021, vol. 2021–October, pp. 943–947.
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.'
mla: Hashemi, Seyyed Ali, et al. “Successive Syndrome-Check Decoding of Polar Codes.”
Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers,
vol. 2021–October, Institute of Electrical and Electronics Engineers, 2021, pp.
943–47, doi:10.1109/IEEECONF53345.2021.9723394.
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.
conference:
end_date: 2021-11-03
location: Virtual, Pacific Grove, CA, United States
name: 'ACSSC: Asilomar Conference on Signals, Systems, and Computers'
start_date: 2021-10-31
date_created: 2022-01-03T11:39:51Z
date_published: 2021-11-01T00:00:00Z
date_updated: 2023-02-13T10:44:16Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/IEEECONF53345.2021.9723394
external_id:
arxiv:
- '2112.00057'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2112.00057'
month: '11'
oa: 1
oa_version: Preprint
page: 943-947
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 55th Asilomar Conference on Signals, Systems, and
Computers
publication_identifier:
isbn:
- '9781665458283'
issn:
- 1058-6393
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Successive syndrome-check decoding of polar codes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2021-October
year: '2021'
...
---
_id: '13146'
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.'
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
author:
- first_name: Quynh
full_name: Nguyen, Quynh
last_name: Nguyen
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Guido
full_name: Montufar, Guido
last_name: Montufar
citation:
ama: 'Nguyen Q, Mondelli M, Montufar G. Tight bounds on the smallest Eigenvalue
of the neural tangent kernel for deep ReLU networks. In: Proceedings of the
38th International Conference on Machine Learning. Vol 139. ML Research Press;
2021:8119-8129.'
apa: 'Nguyen, Q., Mondelli, M., & Montufar, G. (2021). Tight bounds on the smallest
Eigenvalue of the neural tangent kernel for deep ReLU networks. In Proceedings
of the 38th International Conference on Machine Learning (Vol. 139, pp. 8119–8129).
Virtual: ML Research Press.'
chicago: Nguyen, Quynh, Marco Mondelli, and Guido Montufar. “Tight Bounds on the
Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks.” In Proceedings
of the 38th International Conference on Machine Learning, 139:8119–29. ML
Research Press, 2021.
ieee: Q. Nguyen, M. Mondelli, and G. Montufar, “Tight bounds on the smallest Eigenvalue
of the neural tangent kernel for deep ReLU networks,” in Proceedings of the
38th International Conference on Machine Learning, Virtual, 2021, vol. 139,
pp. 8119–8129.
ista: Nguyen Q, Mondelli M, Montufar G. 2021. Tight bounds on the smallest Eigenvalue
of the neural tangent kernel for deep ReLU networks. Proceedings of the 38th International
Conference on Machine Learning. International Conference on Machine Learning vol.
139, 8119–8129.
mla: Nguyen, Quynh, et al. “Tight Bounds on the Smallest Eigenvalue of the Neural
Tangent Kernel for Deep ReLU Networks.” Proceedings of the 38th International
Conference on Machine Learning, vol. 139, ML Research Press, 2021, pp. 8119–29.
short: Q. Nguyen, M. Mondelli, G. Montufar, in:, Proceedings of the 38th International
Conference on Machine Learning, ML Research Press, 2021, pp. 8119–8129.
conference:
end_date: 2021-07-24
location: Virtual
name: International Conference on Machine Learning
start_date: 2021-07-18
date_created: 2023-06-18T22:00:48Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2023-06-19T10:52:51Z
day: '01'
ddc:
- '000'
department:
- _id: MaMo
external_id:
arxiv:
- '2012.11654'
file:
- access_level: open_access
checksum: 19489cf5e16a0596b1f92e317d97c9b0
content_type: application/pdf
creator: dernst
date_created: 2023-06-19T10:49:12Z
date_updated: 2023-06-19T10:49:12Z
file_id: '13155'
file_name: 2021_PMLR_Nguyen.pdf
file_size: 591332
relation: main_file
success: 1
file_date_updated: 2023-06-19T10:49:12Z
has_accepted_license: '1'
intvolume: ' 139'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 8119-8129
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 38th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
isbn:
- '9781713845065'
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep
ReLU networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 139
year: '2021'
...
---
_id: '9047'
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.
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.
article_processing_charge: No
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: John M.
full_name: Cioffi, John M.
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
ama: Mondelli M, Hashemi SA, Cioffi JM, Goldsmith A. Sublinear latency for simplified
successive cancellation decoding of polar codes. IEEE Transactions on Wireless
Communications. 2021;20(1):18-27. doi:10.1109/TWC.2020.3022922
apa: Mondelli, M., Hashemi, S. A., Cioffi, J. M., & Goldsmith, A. (2021). Sublinear
latency for simplified successive cancellation decoding of polar codes. IEEE
Transactions on Wireless Communications. IEEE. https://doi.org/10.1109/TWC.2020.3022922
chicago: Mondelli, Marco, Seyyed Ali Hashemi, John M. Cioffi, and Andrea Goldsmith.
“Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes.”
IEEE Transactions on Wireless Communications. IEEE, 2021. https://doi.org/10.1109/TWC.2020.3022922.
ieee: M. Mondelli, S. A. Hashemi, J. M. Cioffi, and A. Goldsmith, “Sublinear latency
for simplified successive cancellation decoding of polar codes,” IEEE Transactions
on Wireless Communications, vol. 20, no. 1. IEEE, pp. 18–27, 2021.
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.” IEEE Transactions on Wireless Communications,
vol. 20, no. 1, IEEE, 2021, pp. 18–27, doi:10.1109/TWC.2020.3022922.
short: M. Mondelli, S.A. Hashemi, J.M. Cioffi, A. Goldsmith, IEEE Transactions on
Wireless Communications 20 (2021) 18–27.
date_created: 2021-01-31T23:01:21Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2023-08-07T13:36:25Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TWC.2020.3022922
external_id:
arxiv:
- '1909.04892'
isi:
- '000607808800002'
intvolume: ' 20'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.04892
month: '01'
oa: 1
oa_version: Preprint
page: 18-27
publication: IEEE Transactions on Wireless Communications
publication_identifier:
eissn:
- '15582248'
issn:
- '15361276'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '8536'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Sublinear latency for simplified successive cancellation decoding of polar
codes
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 20
year: '2021'
...
---
_id: '10053'
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."
article_processing_charge: No
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Arman
full_name: Fazeli, Arman
last_name: Fazeli
- first_name: Alexander
full_name: Vardy, Alexander
last_name: Vardy
- first_name: John
full_name: Cioffi, John
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
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: 2021 IEEE International Symposium on Information Theory. Institute
of Electrical and Electronics Engineers; 2021:2369-2374. doi:10.1109/ISIT45174.2021.9518153'
apa: 'Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., & Goldsmith,
A. (2021). Parallelism versus latency in simplified successive-cancellation decoding
of polar codes. In 2021 IEEE International Symposium on Information Theory
(pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/ISIT45174.2021.9518153'
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 2021 IEEE International Symposium on Information
Theory, 2369–74. Institute of Electrical and Electronics Engineers, 2021.
https://doi.org/10.1109/ISIT45174.2021.9518153.
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 2021 IEEE International Symposium on Information Theory,
Melbourne, Australia, 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.'
mla: Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation
Decoding of Polar Codes.” 2021 IEEE International Symposium on Information
Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74,
doi:10.1109/ISIT45174.2021.9518153.
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.
conference:
end_date: 2021-07-20
location: Melbourne, Australia
name: 'ISIT: International Symposium on Information Theory'
start_date: 2021-07-12
date_created: 2021-09-27T14:33:14Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2023-08-14T06:55:58Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/ISIT45174.2021.9518153
external_id:
arxiv:
- '2012.13378'
isi:
- '000701502202078'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.13378
month: '09'
oa: 1
oa_version: Preprint
page: 2369-2374
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2021 IEEE International Symposium on Information Theory
publication_identifier:
eisbn:
- 978-1-5386-8209-8
isbn:
- 978-1-5386-8210-4
issn:
- 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
record:
- id: '10364'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Parallelism versus latency in simplified successive-cancellation decoding of
polar codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '10597'
abstract:
- lang: eng
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.
article_processing_charge: No
author:
- first_name: Dorsa
full_name: Fathollahi, Dorsa
last_name: Fathollahi
- first_name: Nariman
full_name: Farsad, Nariman
last_name: Farsad
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Fathollahi D, Farsad N, Hashemi SA, Mondelli M. Sparse multi-decoder recursive
projection aggregation for Reed-Muller codes. In: 2021 IEEE International Symposium
on Information Theory. Institute of Electrical and Electronics Engineers;
2021:1082-1087. doi:10.1109/isit45174.2021.9517887'
apa: 'Fathollahi, D., Farsad, N., Hashemi, S. A., & Mondelli, M. (2021). Sparse
multi-decoder recursive projection aggregation for Reed-Muller codes. In 2021
IEEE International Symposium on Information Theory (pp. 1082–1087). Virtual,
Melbourne, Australia: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/isit45174.2021.9517887'
chicago: Fathollahi, Dorsa, Nariman Farsad, Seyyed Ali Hashemi, and Marco Mondelli.
“Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes.”
In 2021 IEEE International Symposium on Information Theory, 1082–87. Institute
of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/isit45174.2021.9517887.
ieee: D. Fathollahi, N. Farsad, S. A. Hashemi, and M. Mondelli, “Sparse multi-decoder
recursive projection aggregation for Reed-Muller codes,” in 2021 IEEE International
Symposium on Information Theory, Virtual, Melbourne, Australia, 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.'
mla: Fathollahi, Dorsa, et al. “Sparse Multi-Decoder Recursive Projection Aggregation
for Reed-Muller Codes.” 2021 IEEE International Symposium on Information Theory,
Institute of Electrical and Electronics Engineers, 2021, pp. 1082–87, doi:10.1109/isit45174.2021.9517887.
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.
conference:
end_date: 2021-07-20
location: Virtual, Melbourne, Australia
name: 'ISIT: International Symposium on Information Theory'
start_date: 2021-07-12
date_created: 2022-01-03T11:31:26Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2023-08-17T06:32:06Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/isit45174.2021.9517887
external_id:
arxiv:
- '2011.12882'
isi:
- '000701502201029'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2011.12882
month: '09'
oa: 1
oa_version: Preprint
page: 1082-1087
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 2021 IEEE International Symposium on Information Theory
publication_identifier:
eisbn:
- 978-1-5386-8209-8
isbn:
- 978-1-5386-8210-4
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sparse multi-decoder recursive projection aggregation for Reed-Muller codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '10211'
abstract:
- lang: eng
text: "We study the problem of recovering an unknown signal \U0001D465\U0001D465
given measurements obtained from a generalized linear model with a Gaussian sensing
matrix. Two popular solutions are based on a linear estimator \U0001D465\U0001D465^L
and a spectral estimator \U0001D465\U0001D465^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 \U0001D465\U0001D465^L and \U0001D465\U0001D465^s. At
the heart of our analysis is the exact characterization of the empirical joint
distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s)
in the high-dimensional limit. This allows us to compute the Bayes-optimal combination
of \U0001D465\U0001D465^L and \U0001D465\U0001D465^s, given the limiting distribution
of the signal \U0001D465\U0001D465. When the distribution of the signal is Gaussian,
then the Bayes-optimal combination has the form \U0001D703\U0001D465\U0001D465^L+\U0001D465\U0001D465^s
and we derive the optimal combination coefficient. In order to establish the limiting
distribution of (\U0001D465\U0001D465,\U0001D465\U0001D465^L,\U0001D465\U0001D465^s),
we design and analyze an approximate message passing algorithm whose iterates
give \U0001D465\U0001D465^L and approach \U0001D465\U0001D465^s. Numerical simulations
demonstrate the improvement of the proposed combination with respect to the two
methods considered separately."
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.
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Christos
full_name: Thrampoulidis, Christos
last_name: Thrampoulidis
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: Mondelli M, Thrampoulidis C, Venkataramanan R. Optimal combination of linear
and spectral estimators for generalized linear models. Foundations of Computational
Mathematics. 2021. doi:10.1007/s10208-021-09531-x
apa: Mondelli, M., Thrampoulidis, C., & Venkataramanan, R. (2021). Optimal combination
of linear and spectral estimators for generalized linear models. Foundations
of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-021-09531-x
chicago: Mondelli, Marco, Christos Thrampoulidis, and Ramji Venkataramanan. “Optimal
Combination of Linear and Spectral Estimators for Generalized Linear Models.”
Foundations of Computational Mathematics. Springer, 2021. https://doi.org/10.1007/s10208-021-09531-x.
ieee: M. Mondelli, C. Thrampoulidis, and R. Venkataramanan, “Optimal combination
of linear and spectral estimators for generalized linear models,” Foundations
of Computational Mathematics. Springer, 2021.
ista: Mondelli M, Thrampoulidis C, Venkataramanan R. 2021. Optimal combination of
linear and spectral estimators for generalized linear models. Foundations of Computational
Mathematics.
mla: Mondelli, Marco, et al. “Optimal Combination of Linear and Spectral Estimators
for Generalized Linear Models.” Foundations of Computational Mathematics,
Springer, 2021, doi:10.1007/s10208-021-09531-x.
short: M. Mondelli, C. Thrampoulidis, R. Venkataramanan, Foundations of Computational
Mathematics (2021).
date_created: 2021-11-03T10:59:08Z
date_published: 2021-08-17T00:00:00Z
date_updated: 2023-09-05T14:13:57Z
day: '17'
ddc:
- '510'
department:
- _id: MaMo
doi: 10.1007/s10208-021-09531-x
external_id:
arxiv:
- '2008.03326'
isi:
- '000685721000001'
file:
- access_level: open_access
checksum: 9ea12dd8045a0678000a3a59295221cb
content_type: application/pdf
creator: alisjak
date_created: 2021-12-13T15:47:54Z
date_updated: 2021-12-13T15:47:54Z
file_id: '10542'
file_name: 2021_Springer_Mondelli.pdf
file_size: 2305731
relation: main_file
success: 1
file_date_updated: 2021-12-13T15:47:54Z
has_accepted_license: '1'
isi: 1
keyword:
- Applied Mathematics
- Computational Theory and Mathematics
- Computational Mathematics
- Analysis
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
issn:
- 1615-3375
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal combination of linear and spectral estimators for generalized linear
models
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2021'
...
---
_id: '10593'
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.'
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"
article_processing_charge: No
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: 'Mondelli M, Venkataramanan R. PCA initialization for approximate message passing
in rotationally invariant models. In: 35th Conference on Neural Information
Processing Systems. Vol 35. Neural Information Processing Systems Foundation;
2021:29616-29629.'
apa: 'Mondelli, M., & Venkataramanan, R. (2021). PCA initialization for approximate
message passing in rotationally invariant models. In 35th Conference on Neural
Information Processing Systems (Vol. 35, pp. 29616–29629). Virtual: Neural
Information Processing Systems Foundation.'
chicago: Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate
Message Passing in Rotationally Invariant Models.” In 35th Conference on Neural
Information Processing Systems, 35:29616–29. Neural Information Processing
Systems Foundation, 2021.
ieee: M. Mondelli and R. Venkataramanan, “PCA initialization for approximate message
passing in rotationally invariant models,” in 35th Conference on Neural Information
Processing Systems, 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.'
mla: Mondelli, Marco, and Ramji Venkataramanan. “PCA Initialization for Approximate
Message Passing in Rotationally Invariant Models.” 35th Conference on Neural
Information Processing Systems, vol. 35, Neural Information Processing Systems
Foundation, 2021, pp. 29616–29.
short: M. Mondelli, R. Venkataramanan, in:, 35th Conference on Neural Information
Processing Systems, Neural Information Processing Systems Foundation, 2021, pp.
29616–29629.
conference:
end_date: 2021-12-14
location: Virtual
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
date_created: 2022-01-03T10:50:02Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2023-10-17T11:48:23Z
day: '01'
department:
- _id: MaMo
external_id:
arxiv:
- '2106.02356'
intvolume: ' 35'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2106.02356
month: '12'
oa: 1
oa_version: Preprint
page: 29616-29629
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 35th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713845393'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: PCA initialization for approximate message passing in rotationally invariant
models
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2021'
...
---
_id: '10594'
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.'
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).
article_processing_charge: No
author:
- first_name: Quynh
full_name: Nguyen, Quynh
last_name: Nguyen
- first_name: Pierre
full_name: Bréchet, Pierre
last_name: Bréchet
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Nguyen Q, Bréchet P, Mondelli M. When are solutions connected in deep networks?
In: 35th Conference on Neural Information Processing Systems. Vol 35. Neural
Information Processing Systems Foundation; 2021.'
apa: 'Nguyen, Q., Bréchet, P., & Mondelli, M. (2021). When are solutions connected
in deep networks? In 35th Conference on Neural Information Processing Systems
(Vol. 35). Virtual: Neural Information Processing Systems Foundation.'
chicago: Nguyen, Quynh, Pierre Bréchet, and Marco Mondelli. “When Are Solutions
Connected in Deep Networks?” In 35th Conference on Neural Information Processing
Systems, 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 35th Conference on Neural Information Processing Systems,
Virtual, 2021, vol. 35.
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.
mla: Nguyen, Quynh, et al. “When Are Solutions Connected in Deep Networks?” 35th
Conference on Neural Information Processing Systems, 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.
conference:
end_date: 2021-12-14
location: Virtual
name: 35th Conference on Neural Information Processing Systems
start_date: 2021-12-06
date_created: 2022-01-03T10:56:20Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2023-10-17T11:48:40Z
day: '01'
department:
- _id: MaMo
external_id:
arxiv:
- '2102.09671'
intvolume: ' 35'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2102.09671
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 35th Conference on Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713845393'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
status: public
title: When are solutions connected in deep networks?
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2021'
...
---
_id: '10598'
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. '
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.
alternative_title:
- Proceedings of Machine Learning Research
article_processing_charge: Yes (via OA deal)
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Ramji
full_name: Venkataramanan, Ramji
last_name: Venkataramanan
citation:
ama: 'Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization
for generalized linear models. In: Banerjee A, Fukumizu K, eds. Proceedings
of The 24th International Conference on Artificial Intelligence and Statistics.
Vol 130. ML Research Press; 2021:397-405.'
apa: 'Mondelli, M., & Venkataramanan, R. (2021). Approximate message passing
with spectral initialization for generalized linear models. In A. Banerjee &
K. Fukumizu (Eds.), Proceedings of The 24th International Conference on Artificial
Intelligence and Statistics (Vol. 130, pp. 397–405). Virtual, San Diego, CA,
United States: ML Research Press.'
chicago: Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing
with Spectral Initialization for Generalized Linear Models.” In Proceedings
of The 24th International Conference on Artificial Intelligence and Statistics,
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 Proceedings of The 24th International
Conference on Artificial Intelligence and Statistics, Virtual, San Diego,
CA, United States, 2021, vol. 130, pp. 397–405.
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.'
mla: Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with
Spectral Initialization for Generalized Linear Models.” Proceedings of The
24th International Conference on Artificial Intelligence and Statistics, 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.
conference:
end_date: 2021-04-15
location: Virtual, San Diego, CA, United States
name: 'AISTATS: Artificial Intelligence and Statistics'
start_date: 2021-04-13
date_created: 2022-01-03T11:34:22Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2024-03-07T10:36:53Z
day: '01'
department:
- _id: MaMo
editor:
- first_name: Arindam
full_name: Banerjee, Arindam
last_name: Banerjee
- first_name: Kenji
full_name: Fukumizu, Kenji
last_name: Fukumizu
external_id:
arxiv:
- '2010.03460'
intvolume: ' 130'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.mlr.press/v130/mondelli21a.html
month: '04'
oa: 1
oa_version: Preprint
page: 397-405
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of The 24th International Conference on Artificial Intelligence
and Statistics
publication_identifier:
issn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
related_material:
record:
- id: '12480'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Approximate message passing with spectral initialization for generalized linear
models
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 130
year: '2021'
...
---
_id: '9002'
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).'
article_processing_charge: No
article_type: original
author:
- first_name: Arman
full_name: Fazeli, Arman
last_name: Fazeli
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Alexander
full_name: Vardy, Alexander
last_name: Vardy
citation:
ama: 'Fazeli A, Hassani H, Mondelli M, Vardy A. Binary linear codes with optimal
scaling: Polar codes with large kernels. IEEE Transactions on Information Theory.
2021;67(9):5693-5710. doi:10.1109/TIT.2020.3038806'
apa: '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. IEEE. https://doi.org/10.1109/TIT.2020.3038806'
chicago: 'Fazeli, Arman, Hamed Hassani, Marco Mondelli, and Alexander Vardy. “Binary
Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” IEEE Transactions
on Information Theory. IEEE, 2021. https://doi.org/10.1109/TIT.2020.3038806.'
ieee: 'A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary linear codes with
optimal scaling: Polar codes with large kernels,” IEEE Transactions on Information
Theory, vol. 67, no. 9. IEEE, pp. 5693–5710, 2021.'
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.'
mla: 'Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes
with Large Kernels.” IEEE Transactions on Information Theory, vol. 67,
no. 9, IEEE, 2021, pp. 5693–710, doi:10.1109/TIT.2020.3038806.'
short: A. Fazeli, H. Hassani, M. Mondelli, A. Vardy, IEEE Transactions on Information
Theory 67 (2021) 5693–5710.
date_created: 2021-01-10T23:01:18Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2024-03-07T12:18:50Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/TIT.2020.3038806
external_id:
arxiv:
- '1711.01339'
intvolume: ' 67'
issue: '9'
language:
- iso: eng
month: '09'
oa_version: Preprint
page: 5693-5710
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6665'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Binary linear codes with optimal scaling: Polar codes with large kernels'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2021'
...
---
_id: '9221'
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
author:
- first_name: Quynh
full_name: Nguyen, Quynh
last_name: Nguyen
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Nguyen Q, Mondelli M. Global convergence of deep networks with one wide layer
followed by pyramidal topology. In: 34th Conference on Neural Information Processing
Systems. Vol 33. Curran Associates; 2020:11961–11972.'
apa: 'Nguyen, Q., & Mondelli, M. (2020). Global convergence of deep networks
with one wide layer followed by pyramidal topology. In 34th Conference on Neural
Information Processing Systems (Vol. 33, pp. 11961–11972). Vancouver, Canada:
Curran Associates.'
chicago: Nguyen, Quynh, and Marco Mondelli. “Global Convergence of Deep Networks
with One Wide Layer Followed by Pyramidal Topology.” In 34th Conference on
Neural Information Processing Systems, 33:11961–11972. Curran Associates,
2020.
ieee: Q. Nguyen and M. Mondelli, “Global convergence of deep networks with one wide
layer followed by pyramidal topology,” in 34th Conference on Neural Information
Processing Systems, Vancouver, Canada, 2020, vol. 33, pp. 11961–11972.
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 vol. 33, 11961–11972.'
mla: Nguyen, Quynh, and Marco Mondelli. “Global Convergence of Deep Networks with
One Wide Layer Followed by Pyramidal Topology.” 34th Conference on Neural Information
Processing Systems, vol. 33, Curran Associates, 2020, pp. 11961–11972.
short: Q. Nguyen, M. Mondelli, in:, 34th Conference on Neural Information Processing
Systems, Curran Associates, 2020, pp. 11961–11972.
conference:
end_date: 2020-12-12
location: Vancouver, Canada
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2020-12-06
date_created: 2021-03-03T12:06:02Z
date_published: 2020-07-07T00:00:00Z
date_updated: 2022-01-04T09:24:41Z
day: '07'
department:
- _id: MaMo
external_id:
arxiv:
- '2002.07867'
intvolume: ' 33'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2002.07867
month: '07'
oa: 1
oa_version: Preprint
page: 11961–11972
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 34th Conference on Neural Information Processing Systems
publication_status: published
publisher: Curran Associates
quality_controlled: '1'
status: public
title: Global convergence of deep networks with one wide layer followed by pyramidal
topology
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 33
year: '2020'
...
---
_id: '8536'
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.
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_number: 401-406
article_processing_charge: No
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: John
full_name: Cioffi, John
last_name: Cioffi
- first_name: Andrea
full_name: Goldsmith, Andrea
last_name: Goldsmith
citation:
ama: 'Mondelli M, Hashemi SA, Cioffi J, Goldsmith A. Simplified successive cancellation
decoding of polar codes has sublinear latency. In: IEEE International Symposium
on Information Theory - Proceedings. Vol 2020-June. IEEE; 2020. doi:10.1109/ISIT44484.2020.9174141'
apa: 'Mondelli, M., Hashemi, S. A., Cioffi, J., & Goldsmith, A. (2020). Simplified
successive cancellation decoding of polar codes has sublinear latency. In IEEE
International Symposium on Information Theory - Proceedings (Vol. 2020–June).
Los Angeles, CA, United States: IEEE. https://doi.org/10.1109/ISIT44484.2020.9174141'
chicago: Mondelli, Marco, Seyyed Ali Hashemi, John Cioffi, and Andrea Goldsmith.
“Simplified Successive Cancellation Decoding of Polar Codes Has Sublinear Latency.”
In IEEE International Symposium on Information Theory - Proceedings, Vol.
2020–June. IEEE, 2020. https://doi.org/10.1109/ISIT44484.2020.9174141.
ieee: M. Mondelli, S. A. Hashemi, J. Cioffi, and A. Goldsmith, “Simplified successive
cancellation decoding of polar codes has sublinear latency,” in IEEE International
Symposium on Information Theory - Proceedings, Los Angeles, CA, United States,
2020, vol. 2020–June.
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: Internation Symposium on
Information Theory vol. 2020–June, 401–406.'
mla: Mondelli, Marco, et al. “Simplified Successive Cancellation Decoding of Polar
Codes Has Sublinear Latency.” IEEE International Symposium on Information Theory
- Proceedings, vol. 2020–June, 401–406, IEEE, 2020, doi:10.1109/ISIT44484.2020.9174141.
short: M. Mondelli, S.A. Hashemi, J. Cioffi, A. Goldsmith, in:, IEEE International
Symposium on Information Theory - Proceedings, IEEE, 2020.
conference:
end_date: 2020-06-26
location: Los Angeles, CA, United States
name: 'ISIT: Internation Symposium on Information Theory'
start_date: 2020-06-21
date_created: 2020-09-20T22:01:37Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-07T13:36:24Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/ISIT44484.2020.9174141
external_id:
arxiv:
- '1909.04892'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1909.04892
month: '06'
oa: 1
oa_version: Preprint
publication: IEEE International Symposium on Information Theory - Proceedings
publication_identifier:
isbn:
- '9781728164328'
issn:
- '21578095'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '9047'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Simplified successive cancellation decoding of polar codes has sublinear latency
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-June
year: '2020'
...
---
_id: '9198'
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."
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
author:
- first_name: Alexander
full_name: Shevchenko, Alexander
last_name: Shevchenko
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: 'Shevchenko A, Mondelli M. Landscape connectivity and dropout stability of
SGD solutions for over-parameterized neural networks. In: Proceedings of the
37th International Conference on Machine Learning. Vol 119. ML Research Press;
2020:8773-8784.'
apa: Shevchenko, A., & Mondelli, M. (2020). Landscape connectivity and dropout
stability of SGD solutions for over-parameterized neural networks. In Proceedings
of the 37th International Conference on Machine Learning (Vol. 119, pp. 8773–8784).
ML Research Press.
chicago: Shevchenko, Alexander, and Marco Mondelli. “Landscape Connectivity and
Dropout Stability of SGD Solutions for Over-Parameterized Neural Networks.” In
Proceedings of the 37th International Conference on Machine Learning, 119:8773–84.
ML Research Press, 2020.
ieee: A. Shevchenko and M. Mondelli, “Landscape connectivity and dropout stability
of SGD solutions for over-parameterized neural networks,” in Proceedings of
the 37th International Conference on Machine Learning, 2020, vol. 119, pp.
8773–8784.
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.
mla: Shevchenko, Alexander, and Marco Mondelli. “Landscape Connectivity and Dropout
Stability of SGD Solutions for Over-Parameterized Neural Networks.” Proceedings
of the 37th International Conference on Machine Learning, vol. 119, ML Research
Press, 2020, pp. 8773–84.
short: A. Shevchenko, M. Mondelli, in:, Proceedings of the 37th International Conference
on Machine Learning, ML Research Press, 2020, pp. 8773–8784.
date_created: 2021-02-25T09:36:22Z
date_published: 2020-07-13T00:00:00Z
date_updated: 2023-10-17T12:43:19Z
day: '13'
ddc:
- '000'
department:
- _id: MaMo
external_id:
arxiv:
- '1912.10095'
file:
- access_level: open_access
checksum: f042c8d4316bd87c6361aa76f1fbdbbe
content_type: application/pdf
creator: dernst
date_created: 2021-03-02T15:38:14Z
date_updated: 2021-03-02T15:38:14Z
file_id: '9217'
file_name: 2020_PMLR_Shevchenko.pdf
file_size: 5336380
relation: main_file
success: 1
file_date_updated: 2021-03-02T15:38:14Z
has_accepted_license: '1'
intvolume: ' 119'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 8773-8784
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: Proceedings of the 37th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: Landscape connectivity and dropout stability of SGD solutions for over-parameterized
neural networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 119
year: '2020'
...
---
_id: '6748'
abstract:
- lang: eng
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."
article_processing_charge: No
article_type: original
author:
- first_name: Adel
full_name: Javanmard, Adel
last_name: Javanmard
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Andrea
full_name: Montanari, Andrea
last_name: Montanari
citation:
ama: Javanmard A, Mondelli M, Montanari A. Analysis of a two-layer neural network
via displacement convexity. Annals of Statistics. 2020;48(6):3619-3642.
doi:10.1214/20-AOS1945
apa: Javanmard, A., Mondelli, M., & Montanari, A. (2020). Analysis of a two-layer
neural network via displacement convexity. Annals of Statistics. Institute
of Mathematical Statistics. https://doi.org/10.1214/20-AOS1945
chicago: Javanmard, Adel, Marco Mondelli, and Andrea Montanari. “Analysis of a Two-Layer
Neural Network via Displacement Convexity.” Annals of Statistics. Institute
of Mathematical Statistics, 2020. https://doi.org/10.1214/20-AOS1945.
ieee: A. Javanmard, M. Mondelli, and A. Montanari, “Analysis of a two-layer neural
network via displacement convexity,” Annals of Statistics, vol. 48, no.
6. Institute of Mathematical Statistics, pp. 3619–3642, 2020.
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.
mla: Javanmard, Adel, et al. “Analysis of a Two-Layer Neural Network via Displacement
Convexity.” Annals of Statistics, vol. 48, no. 6, Institute of Mathematical
Statistics, 2020, pp. 3619–42, doi:10.1214/20-AOS1945.
short: A. Javanmard, M. Mondelli, A. Montanari, Annals of Statistics 48 (2020) 3619–3642.
date_created: 2019-07-31T09:39:42Z
date_published: 2020-12-11T00:00:00Z
date_updated: 2024-03-06T08:28:50Z
day: '11'
department:
- _id: MaMo
doi: 10.1214/20-AOS1945
external_id:
arxiv:
- '1901.01375'
isi:
- '000598369200021'
intvolume: ' 48'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1901.01375
month: '12'
oa: 1
oa_version: Preprint
page: 3619-3642
publication: Annals of Statistics
publication_identifier:
eissn:
- 1941-7330
issn:
- 1932-6157
publication_status: published
publisher: Institute of Mathematical Statistics
quality_controlled: '1'
status: public
title: Analysis of a two-layer neural network via displacement convexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2020'
...
---
_id: '6662'
abstract:
- lang: eng
text: "In phase retrieval, we want to recover an unknown signal \U0001D465∈ℂ\U0001D451
from n quadratic measurements of the form \U0001D466\U0001D456=|⟨\U0001D44E\U0001D456,\U0001D465⟩|2+\U0001D464\U0001D456,
where \U0001D44E\U0001D456∈ℂ\U0001D451 are known sensing vectors and \U0001D464\U0001D456
is measurement noise. We ask the following weak recovery question: What is the
minimum number of measurements n needed to produce an estimator \U0001D465^(\U0001D466)
that is positively correlated with the signal \U0001D465? We consider the case
of Gaussian vectors \U0001D44E\U0001D44E\U0001D456. We prove that—in the high-dimensional
limit—a sharp phase transition takes place, and we locate the threshold in the
regime of vanishingly small noise. For \U0001D45B≤\U0001D451−\U0001D45C(\U0001D451),
no estimator can do significantly better than random and achieve a strictly positive
correlation. For \U0001D45B≥\U0001D451+\U0001D45C(\U0001D451), a simple spectral
estimator achieves a positive correlation. Surprisingly, numerical simulations
with the same spectral estimator demonstrate promising performance with realistic
sensing matrices. Spectral methods are used to initialize non-convex optimization
algorithms in phase retrieval, and our approach can boost the performance in this
setting as well. Our impossibility result is based on classical information-theoretic
arguments. The spectral algorithm computes the leading eigenvector of a weighted
empirical covariance matrix. We obtain a sharp characterization of the spectral
properties of this random matrix using tools from free probability and generalizing
a recent result by Lu and Li. Both the upper bound and lower bound generalize
beyond phase retrieval to measurements \U0001D466\U0001D456 produced according
to a generalized linear model. As a by-product of our analysis, we compare the
threshold of the proposed spectral method with that of a message passing algorithm."
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Andrea
full_name: Montanari, Andrea
last_name: Montanari
citation:
ama: Mondelli M, Montanari A. Fundamental limits of weak recovery with applications
to phase retrieval. Foundations of Computational Mathematics. 2019;19(3):703-773.
doi:10.1007/s10208-018-9395-y
apa: Mondelli, M., & Montanari, A. (2019). Fundamental limits of weak recovery
with applications to phase retrieval. Foundations of Computational Mathematics.
Springer. https://doi.org/10.1007/s10208-018-9395-y
chicago: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery
with Applications to Phase Retrieval.” Foundations of Computational Mathematics.
Springer, 2019. https://doi.org/10.1007/s10208-018-9395-y.
ieee: M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications
to phase retrieval,” Foundations of Computational Mathematics, vol. 19,
no. 3. Springer, pp. 703–773, 2019.
ista: Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications
to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773.
mla: Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery
with Applications to Phase Retrieval.” Foundations of Computational Mathematics,
vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:10.1007/s10208-018-9395-y.
short: M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019)
703–773.
date_created: 2019-07-22T13:23:48Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:08:28Z
day: '01'
doi: 10.1007/s10208-018-9395-y
extern: '1'
external_id:
arxiv:
- '1708.05932'
intvolume: ' 19'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.05932
month: '06'
oa: 1
oa_version: Preprint
page: 703-773
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- 1615-3383
publication_status: published
publisher: Springer
quality_controlled: '1'
status: public
title: Fundamental limits of weak recovery with applications to phase retrieval
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 19
year: '2019'
...
---
_id: '6663'
abstract:
- lang: eng
text: Consider the problem of constructing a polar code of block length N for a
given transmission channel W. Previous approaches require one to compute the reliability
of the N synthetic channels and then use only those that are sufficiently reliable.
However, we know from two independent works by Schürch and by Bardet et al. that
the synthetic channels are partially ordered with respect to degradation. Hence,
it is natural to ask whether the partial order can be exploited to reduce the
computational burden of the construction problem. We show that, if we take advantage
of the partial order, we can construct a polar code by computing the reliability
of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we
prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to
be considered and such a bound is tight up to a multiplicative factor log log
N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense
that it allows one to construct polar codes for any W, and it can be identified
by solving a maximum matching problem on a bipartite graph. Our proof technique
consists of reducing the construction problem to the problem of computing the
maximum cardinality of an antichain for a suitable partially ordered set. As such,
this method is general, and it can be used to further improve the complexity of
the construction problem, in case a refined partial order on the synthetic channels
of polar codes is discovered.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear
complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667
apa: Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar
codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar
Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with
sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019.
ista: Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear
complexity. IEEE. 65(5), 2782–2791.
mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.”
IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791.
date_created: 2019-07-23T07:32:57Z
date_published: 2019-05-01T00:00:00Z
date_updated: 2023-02-23T12:50:20Z
day: '01'
doi: 10.1109/tit.2018.2889667
extern: '1'
external_id:
arxiv:
- '1612.05295'
intvolume: ' 65'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1612.05295
month: '05'
oa: 1
oa_version: Preprint
page: 2782-2791
publication: IEEE
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6729'
relation: earlier_version
status: public
status: public
title: Construction of polar codes with sublinear complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 65
year: '2019'
...
---
_id: '6747'
abstract:
- lang: eng
text: "We establish connections between the problem of learning a two-layer neural
network and tensor decomposition. We consider a model with feature vectors x∈ℝd,
r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w\U0001D5B3ix),
with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3,
we prove that no polynomial-time learning algorithm can outperform the trivial
predictor that assigns to each example the response variable \U0001D53C(y), when
d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard
Gaussian feature vectors x, and output distributed according to a two-layer neural
network with random isotropic weights, and under a certain complexity-theoretic
assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time
algorithm can substantially outperform current methods for tensor decomposition
based on the sum-of-squares hierarchy. We also prove generalizations of this statement
for higher degree polynomial activations, and non-random weight vectors. Remarkably,
several existing algorithms for learning two-layer networks with rigorous guarantees
are based on tensor decomposition. Our results support the idea that this is indeed
the core computational difficulty in learning such networks, under the stated
generative model for the data. As a side result, we show that under this model
learning the network requires accurate learning of its weights, a property that
does not hold in a more general setting. "
article_processing_charge: No
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Andrea
full_name: Montanari, Andrea
last_name: Montanari
citation:
ama: 'Mondelli M, Montanari A. On the connection between learning two-layers neural
networks and tensor decomposition. In: Proceedings of the 22nd International
Conference on Artificial Intelligence and Statistics. Vol 89. Proceedings
of Machine Learning Research; 2019:1051-1060.'
apa: 'Mondelli, M., & Montanari, A. (2019). On the connection between learning
two-layers neural networks and tensor decomposition. In Proceedings of the
22nd International Conference on Artificial Intelligence and Statistics (Vol.
89, pp. 1051–1060). Naha, Okinawa, Japan: Proceedings of Machine Learning Research.'
chicago: Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning
Two-Layers Neural Networks and Tensor Decomposition.” In Proceedings of the
22nd International Conference on Artificial Intelligence and Statistics, 89:1051–60.
Proceedings of Machine Learning Research, 2019.
ieee: M. Mondelli and A. Montanari, “On the connection between learning two-layers
neural networks and tensor decomposition,” in Proceedings of the 22nd International
Conference on Artificial Intelligence and Statistics, Naha, Okinawa, Japan,
2019, vol. 89, pp. 1051–1060.
ista: 'Mondelli M, Montanari A. 2019. On the connection between learning two-layers
neural networks and tensor decomposition. Proceedings of the 22nd International
Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence
and Statistics vol. 89, 1051–1060.'
mla: Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning
Two-Layers Neural Networks and Tensor Decomposition.” Proceedings of the 22nd
International Conference on Artificial Intelligence and Statistics, vol. 89,
Proceedings of Machine Learning Research, 2019, pp. 1051–60.
short: M. Mondelli, A. Montanari, in:, Proceedings of the 22nd International Conference
on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research,
2019, pp. 1051–1060.
conference:
end_date: 2019-04-18
location: Naha, Okinawa, Japan
name: 'AISTATS: Artificial Intelligence and Statistics'
start_date: 2019-04-16
date_created: 2019-07-31T09:31:26Z
date_published: 2019-04-01T00:00:00Z
date_updated: 2021-01-12T08:08:49Z
day: '01'
extern: '1'
external_id:
arxiv:
- '1802.07301'
intvolume: ' 89'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1802.07301
month: '04'
oa: 1
oa_version: Preprint
page: 1051-1060
publication: Proceedings of the 22nd International Conference on Artificial Intelligence
and Statistics
publication_status: published
publisher: Proceedings of Machine Learning Research
quality_controlled: '1'
status: public
title: On the connection between learning two-layers neural networks and tensor decomposition
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 89
year: '2019'
...
---
_id: '6750'
abstract:
- lang: eng
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. '
article_number: '8854897'
article_processing_charge: No
article_type: original
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Carlo
full_name: Condo, Carlo
last_name: Condo
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Warren J
full_name: Gross, Warren J
last_name: Gross
citation:
ama: Hashemi SA, Condo C, Mondelli M, Gross WJ. Rate-flexible fast polar decoders.
IEEE Transactions on Signal Processing. 2019;67(22). doi:10.1109/TSP.2019.2944738
apa: Hashemi, S. A., Condo, C., Mondelli, M., & Gross, W. J. (2019). Rate-flexible
fast polar decoders. IEEE Transactions on Signal Processing. IEEE. https://doi.org/10.1109/TSP.2019.2944738
chicago: Hashemi, Seyyed Ali, Carlo Condo, Marco Mondelli, and Warren J Gross. “Rate-Flexible
Fast Polar Decoders.” IEEE Transactions on Signal Processing. IEEE, 2019.
https://doi.org/10.1109/TSP.2019.2944738.
ieee: S. A. Hashemi, C. Condo, M. Mondelli, and W. J. Gross, “Rate-flexible fast
polar decoders,” IEEE Transactions on Signal Processing, vol. 67, no. 22.
IEEE, 2019.
ista: Hashemi SA, Condo C, Mondelli M, Gross WJ. 2019. Rate-flexible fast polar
decoders. IEEE Transactions on Signal Processing. 67(22), 8854897.
mla: Hashemi, Seyyed Ali, et al. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions
on Signal Processing, vol. 67, no. 22, 8854897, IEEE, 2019, doi:10.1109/TSP.2019.2944738.
short: S.A. Hashemi, C. Condo, M. Mondelli, W.J. Gross, IEEE Transactions on Signal
Processing 67 (2019).
date_created: 2019-07-31T09:51:14Z
date_published: 2019-11-15T00:00:00Z
date_updated: 2021-01-12T08:08:51Z
day: '15'
department:
- _id: MaMo
doi: 10.1109/TSP.2019.2944738
external_id:
arxiv:
- '1903.09203'
intvolume: ' 67'
issue: '22'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.09203
month: '11'
oa: 1
oa_version: Preprint
publication: IEEE Transactions on Signal Processing
publication_identifier:
issn:
- 1053587X
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: 1
status: public
title: Rate-flexible fast polar decoders
type: journal_article
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 67
year: '2019'
...
---
_id: '7007'
abstract:
- lang: eng
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.'
article_number: '218'
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: S. Hamed
full_name: Hassani, S. Hamed
last_name: Hassani
- first_name: Rüdiger
full_name: Urbanke, Rüdiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani SH, Urbanke R. A new coding paradigm for the primitive
relay channel. Algorithms. 2019;12(10). doi:10.3390/a12100218
apa: Mondelli, M., Hassani, S. H., & Urbanke, R. (2019). A new coding paradigm
for the primitive relay channel. Algorithms. MDPI. https://doi.org/10.3390/a12100218
chicago: Mondelli, Marco, S. Hamed Hassani, and Rüdiger Urbanke. “A New Coding Paradigm
for the Primitive Relay Channel.” Algorithms. MDPI, 2019. https://doi.org/10.3390/a12100218.
ieee: M. Mondelli, S. H. Hassani, and R. Urbanke, “A new coding paradigm for the
primitive relay channel,” Algorithms, vol. 12, no. 10. MDPI, 2019.
ista: Mondelli M, Hassani SH, Urbanke R. 2019. A new coding paradigm for the primitive
relay channel. Algorithms. 12(10), 218.
mla: Mondelli, Marco, et al. “A New Coding Paradigm for the Primitive Relay Channel.”
Algorithms, vol. 12, no. 10, 218, MDPI, 2019, doi:10.3390/a12100218.
short: M. Mondelli, S.H. Hassani, R. Urbanke, Algorithms 12 (2019).
date_created: 2019-11-12T14:46:19Z
date_published: 2019-10-18T00:00:00Z
date_updated: 2023-02-23T12:49:28Z
day: '18'
ddc:
- '510'
department:
- _id: MaMo
doi: 10.3390/a12100218
external_id:
arxiv:
- '1801.03153'
file:
- access_level: open_access
checksum: 267756d8f9db572f496cd1663c89d59a
content_type: application/pdf
creator: dernst
date_created: 2019-11-12T14:48:45Z
date_updated: 2020-07-14T12:47:47Z
file_id: '7008'
file_name: 2019_Algorithms_Mondelli.pdf
file_size: 696791
relation: main_file
file_date_updated: 2020-07-14T12:47:47Z
has_accepted_license: '1'
intvolume: ' 12'
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: Algorithms
publication_identifier:
issn:
- 1999-4893
publication_status: published
publisher: MDPI
quality_controlled: '1'
related_material:
record:
- id: '6675'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: A new coding paradigm for the primitive relay channel
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2019'
...
---
_id: '6664'
abstract:
- lang: eng
text: Reed-Muller (RM) and polar codes are a class of capacity-achieving channel
coding schemes with the same factor graph representation. Low-complexity decoding
algorithms fall short in providing a good error-correction performance for RM
and polar codes. Using the symmetric group of RM and polar codes, the specific
decoding algorithm can be carried out on multiple permutations of the factor graph
to boost the error-correction performance. However, this approach results in high
decoding complexity. In this paper, we first derive the total number of factor
graph permutations on which the decoding can be performed. We further propose
a successive permutation (SP) scheme which finds the permutations on the fly,
thus the decoding always progresses on a single factor graph permutation. We show
that SP can be used to improve the error-correction performance of RM and polar
codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping
the memory requirements of the decoders unaltered. Our results for RM and polar
codes of length 128 and rate 0.5 show that when SP is used and at a target frame
error rate of 10 -4 , up to 0.5 dB and 0.1 dB improvement can be achieved for
RM and polar codes respectively.
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Nghia
full_name: Doan, Nghia
last_name: Doan
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: 'Warren '
full_name: 'Gross, Warren '
last_name: Gross
citation:
ama: 'Hashemi SA, Doan N, Mondelli M, Gross W. Decoding Reed-Muller and polar codes
by successive factor graph permutations. In: 2018 IEEE 10th International Symposium
on Turbo Codes & Iterative Information Processing. IEEE; 2018:1-5. doi:10.1109/istc.2018.8625281'
apa: 'Hashemi, S. A., Doan, N., Mondelli, M., & Gross, W. (2018). Decoding Reed-Muller
and polar codes by successive factor graph permutations. In 2018 IEEE 10th
International Symposium on Turbo Codes & Iterative Information Processing
(pp. 1–5). Hong Kong, China: IEEE. https://doi.org/10.1109/istc.2018.8625281'
chicago: Hashemi, Seyyed Ali, Nghia Doan, Marco Mondelli, and Warren Gross. “Decoding
Reed-Muller and Polar Codes by Successive Factor Graph Permutations.” In 2018
IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing,
1–5. IEEE, 2018. https://doi.org/10.1109/istc.2018.8625281.
ieee: S. A. Hashemi, N. Doan, M. Mondelli, and W. Gross, “Decoding Reed-Muller and
polar codes by successive factor graph permutations,” in 2018 IEEE 10th International
Symposium on Turbo Codes & Iterative Information Processing, Hong Kong,
China, 2018, pp. 1–5.
ista: 'Hashemi SA, Doan N, Mondelli M, Gross W. 2018. Decoding Reed-Muller and polar
codes by successive factor graph permutations. 2018 IEEE 10th International Symposium
on Turbo Codes & Iterative Information Processing. ISTC: Symposium on Turbo
Codes & Iterative Information Processing, 1–5.'
mla: Hashemi, Seyyed Ali, et al. “Decoding Reed-Muller and Polar Codes by Successive
Factor Graph Permutations.” 2018 IEEE 10th International Symposium on Turbo
Codes & Iterative Information Processing, IEEE, 2018, pp. 1–5, doi:10.1109/istc.2018.8625281.
short: S.A. Hashemi, N. Doan, M. Mondelli, W. Gross, in:, 2018 IEEE 10th International
Symposium on Turbo Codes & Iterative Information Processing, IEEE, 2018, pp.
1–5.
conference:
end_date: 2018-12-07
location: Hong Kong, China
name: 'ISTC: Symposium on Turbo Codes & Iterative Information Processing'
start_date: 2018-12-03
date_created: 2019-07-23T09:12:43Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2021-01-12T08:08:29Z
day: '01'
doi: 10.1109/istc.2018.8625281
extern: '1'
external_id:
arxiv:
- '1807.03912'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1807.03912
month: '12'
oa: 1
oa_version: Preprint
page: 1-5
publication: 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information
Processing
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Decoding Reed-Muller and polar codes by successive factor graph permutations
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6674'
abstract:
- lang: eng
text: Polar codes represent one of the major recent breakthroughs in coding theory
and, because of their attractive features, they have been selected for the incoming
5G standard. As such, a lot of attention has been devoted to the development of
decoding algorithms with good error performance and efficient hardware implementation.
One of the leading candidates in this regard is represented by successive-cancellation
list (SCL) decoding. However, its hardware implementation requires a large amount
of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly
reduce the memory consumption. In this paper, we consider the paradigm of PSCL
decoding from a practical standpoint, and we provide several improvements. First,
by changing the target signal-to-noise ratio and consequently modifying the construction
of the code, we are able to improve the performance at no additional computational,
latency, or memory cost. Second, we bridge the performance gap between SCL and
PSCL decoding by introducing a generalized PSCL decoder and a layered PSCL decoder.
In this way, we obtain almost the same performance of the SCL decoder with a significantly
lower memory requirement, as testified by hardware implementation results. Third,
we present an optimal scheme to allocate cyclic redundancy checks. Finally, we
provide a lower bound on the list size that guarantees optimal maximum a posteriori
performance for the binary erasure channel.
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: S. Hamed
full_name: Hassani, S. Hamed
last_name: Hassani
- first_name: Carlo
full_name: Condo, Carlo
last_name: Condo
- first_name: Rudiger L.
full_name: Urbanke, Rudiger L.
last_name: Urbanke
- first_name: Warren J.
full_name: Gross, Warren J.
last_name: Gross
citation:
ama: 'Hashemi SA, Mondelli M, Hassani SH, Condo C, Urbanke RL, Gross WJ. Decoder
partitioning: Towards practical list decoding of polar codes. IEEE Transactions
on Communications. 2018;66(9):3749-3759. doi:10.1109/tcomm.2018.2832207'
apa: 'Hashemi, S. A., Mondelli, M., Hassani, S. H., Condo, C., Urbanke, R. L., &
Gross, W. J. (2018). Decoder partitioning: Towards practical list decoding of
polar codes. IEEE Transactions on Communications. IEEE. https://doi.org/10.1109/tcomm.2018.2832207'
chicago: 'Hashemi, Seyyed Ali, Marco Mondelli, S. Hamed Hassani, Carlo Condo, Rudiger
L. Urbanke, and Warren J. Gross. “Decoder Partitioning: Towards Practical List
Decoding of Polar Codes.” IEEE Transactions on Communications. IEEE, 2018.
https://doi.org/10.1109/tcomm.2018.2832207.'
ieee: 'S. A. Hashemi, M. Mondelli, S. H. Hassani, C. Condo, R. L. Urbanke, and W.
J. Gross, “Decoder partitioning: Towards practical list decoding of polar codes,”
IEEE Transactions on Communications, vol. 66, no. 9. IEEE, pp. 3749–3759,
2018.'
ista: 'Hashemi SA, Mondelli M, Hassani SH, Condo C, Urbanke RL, Gross WJ. 2018.
Decoder partitioning: Towards practical list decoding of polar codes. IEEE Transactions
on Communications. 66(9), 3749–3759.'
mla: 'Hashemi, Seyyed Ali, et al. “Decoder Partitioning: Towards Practical List
Decoding of Polar Codes.” IEEE Transactions on Communications, vol. 66,
no. 9, IEEE, 2018, pp. 3749–59, doi:10.1109/tcomm.2018.2832207.'
short: S.A. Hashemi, M. Mondelli, S.H. Hassani, C. Condo, R.L. Urbanke, W.J. Gross,
IEEE Transactions on Communications 66 (2018) 3749–3759.
date_created: 2019-07-24T08:59:41Z
date_published: 2018-09-01T00:00:00Z
date_updated: 2021-01-12T08:08:31Z
day: '01'
doi: 10.1109/tcomm.2018.2832207
extern: '1'
intvolume: ' 66'
issue: '9'
language:
- iso: eng
month: '09'
oa_version: None
page: 3749-3759
publication: IEEE Transactions on Communications
publication_identifier:
eissn:
- 1558-0857
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'Decoder partitioning: Towards practical list decoding of polar codes'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2018'
...
---
_id: '6728'
abstract:
- lang: eng
text: Polar codes are a channel coding scheme for the next generation of wireless
communications standard (5G). The belief propagation (BP) decoder allows for parallel
decoding of polar codes, making it suitable for high throughput applications.
However, the error-correction performance of polar codes under BP decoding is
far from the requirements of 5G. It has been shown that the error-correction performance
of BP can be improved if the decoding is performed on multiple permuted factor
graphs of polar codes. However, a different BP decoding scheduling is required
for each factor graph permutation which results in the design of a different decoder
for each permutation. Moreover, the selection of the different factor graph permutations
is at random, which prevents the decoder to achieve a desirable error correction
performance with a small number of permutations. In this paper, we first show
that the permutations on the factor graph can be mapped into suitable permutations
on the codeword positions. As a result, we can make use of a single decoder for
all the permutations. In addition, we introduce a method to construct a set of
predetermined permutations which can provide the correct codeword if the decoding
fails on the original permutation. We show that for the 5G polar code of length
1024, the error-correction performance of the proposed decoder is more than 0.25
dB better than that of the BP decoder with the same number of random permutations
at the frame error rate of 10 -4 .
author:
- first_name: Nghia
full_name: Doan, Nghia
last_name: Doan
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Warren J.
full_name: Gross, Warren J.
last_name: Gross
citation:
ama: 'Doan N, Hashemi SA, Mondelli M, Gross WJ. On the decoding of polar codes on
permuted factor graphs. In: 2018 IEEE Global Communications Conference .
IEEE; 2018. doi:10.1109/glocom.2018.8647308'
apa: 'Doan, N., Hashemi, S. A., Mondelli, M., & Gross, W. J. (2018). On the
decoding of polar codes on permuted factor graphs. In 2018 IEEE Global Communications
Conference . Abu Dhabi, United Arab Emirates: IEEE. https://doi.org/10.1109/glocom.2018.8647308'
chicago: Doan, Nghia, Seyyed Ali Hashemi, Marco Mondelli, and Warren J. Gross. “On
the Decoding of Polar Codes on Permuted Factor Graphs.” In 2018 IEEE Global
Communications Conference . IEEE, 2018. https://doi.org/10.1109/glocom.2018.8647308.
ieee: N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross, “On the decoding of
polar codes on permuted factor graphs,” in 2018 IEEE Global Communications
Conference , Abu Dhabi, United Arab Emirates, 2018.
ista: 'Doan N, Hashemi SA, Mondelli M, Gross WJ. 2018. On the decoding of polar
codes on permuted factor graphs. 2018 IEEE Global Communications Conference .
GLOBECOM: Global Communications Conference.'
mla: Doan, Nghia, et al. “On the Decoding of Polar Codes on Permuted Factor Graphs.”
2018 IEEE Global Communications Conference , IEEE, 2018, doi:10.1109/glocom.2018.8647308.
short: N. Doan, S.A. Hashemi, M. Mondelli, W.J. Gross, in:, 2018 IEEE Global Communications
Conference , IEEE, 2018.
conference:
end_date: 2018-12-13
location: Abu Dhabi, United Arab Emirates
name: 'GLOBECOM: Global Communications Conference'
start_date: 2018-12-09
date_created: 2019-07-30T06:43:15Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2021-01-12T08:08:42Z
day: '01'
doi: 10.1109/glocom.2018.8647308
extern: '1'
external_id:
arxiv:
- '1806.11195'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1806.11195
month: '12'
oa: 1
oa_version: Preprint
publication: '2018 IEEE Global Communications Conference '
publication_identifier:
isbn:
- '9781538647271'
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: On the decoding of polar codes on permuted factor graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6678'
abstract:
- lang: eng
text: We survey coding techniques that enable reliable transmission at rates that
approach the capacity of an arbitrary discrete memoryless channel. In particular,
we take the point of view of modern coding theory and discuss how recent advances
in coding for symmetric channels help provide more efficient solutions for the
asymmetric case. We consider, in more detail, three basic coding paradigms. The
first one is Gallager's scheme that consists of concatenating a linear code with
a non-linear mapping so that the input distribution can be appropriately shaped.
We explicitly show that both polar codes and spatially coupled codes can be employed
in this scenario. Furthermore, we derive a scaling law between the gap to capacity,
the cardinality of the input and output alphabets, and the required size of the
mapper. The second one is an integrated scheme in which the code is used both
for source coding, in order to create codewords distributed according to the capacity-achieving
input distribution, and for channel coding, in order to provide error protection.
Such a technique has been recently introduced by Honda and Yamamoto in the context
of polar codes, and we show how to apply it also to the design of sparse graph
codes. The third paradigm is based on an idea of Böcherer and Mathar, and separates
the two tasks of source coding and channel coding by a chaining construction that
binds together several codewords. We present conditions for the source code and
the channel code, and we describe how to combine any source code with any channel
code that fulfill those conditions, in order to provide capacity-achieving schemes
for asymmetric channels. In particular, we show that polar codes, spatially coupled
codes, and homophonic codes are suitable as basic building blocks of the proposed
coding strategy. Rather than focusing on the exact details of the schemes, the
purpose of this tutorial is to present different coding techniques that can then
be implemented with many variants. There is no absolute winner and, in order to
understand the most suitable technique for a specific application scenario, we
provide a detailed comparison that takes into account several performance metrics.
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: 'Rudiger '
full_name: 'Urbanke, Rudiger '
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Urbanke R. How to achieve the capacity of asymmetric
channels. IEEE Transactions on Information Theory. 2018;64(5):3371-3393.
doi:10.1109/tit.2018.2789885
apa: Mondelli, M., Hassani, H., & Urbanke, R. (2018). How to achieve the capacity
of asymmetric channels. IEEE Transactions on Information Theory. IEEE.
https://doi.org/10.1109/tit.2018.2789885
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “How to Achieve the
Capacity of Asymmetric Channels.” IEEE Transactions on Information Theory.
IEEE, 2018. https://doi.org/10.1109/tit.2018.2789885.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “How to achieve the capacity of asymmetric
channels,” IEEE Transactions on Information Theory, vol. 64, no. 5. IEEE,
pp. 3371–3393, 2018.
ista: Mondelli M, Hassani H, Urbanke R. 2018. How to achieve the capacity of asymmetric
channels. IEEE Transactions on Information Theory. 64(5), 3371–3393.
mla: Mondelli, Marco, et al. “How to Achieve the Capacity of Asymmetric Channels.”
IEEE Transactions on Information Theory, vol. 64, no. 5, IEEE, 2018, pp.
3371–93, doi:10.1109/tit.2018.2789885.
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Information Theory
64 (2018) 3371–3393.
date_created: 2019-07-24T12:38:49Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2023-02-23T12:50:46Z
day: '01'
doi: 10.1109/tit.2018.2789885
extern: '1'
external_id:
arxiv:
- '1406.7373'
intvolume: ' 64'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1406.7373
month: '05'
oa: 1
oa_version: Preprint
page: 3371-3393
publication: IEEE Transactions on Information Theory
publication_identifier:
issn:
- 0018-9448
- 1557-9654
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6740'
relation: earlier_version
status: public
status: public
title: How to achieve the capacity of asymmetric channels
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 64
year: '2018'
...
---
_id: '6675'
abstract:
- lang: eng
text: 'We present a coding paradigm that provides a new achievable rate for the
primitive relay channel by combining compress-and-forward and decode-and-forward
with a chaining construction. In the primitive relay channel model, the source
broadcasts a message to the relay and to the destination; and the relay facilitates
this communication by sending an additional message to the destination through
a separate channel. Two well-known coding approaches for this setting are decode-and-forward
and compress-and-forward: in the former, the relay decodes the message and sends
some of the information to the destination; in the latter, the relay does not
attempt to decode, but it sends a compressed description of the received sequence
to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs
of blocks and we use compress-and-forward for the first block and decode-and-forward
for the second. In particular, in the first block, the relay does not attempt
to decode and it sends only a part of the compressed description of the received
sequence; in the second block, the relay decodes the message and sends this information
plus the remaining part of the compressed sequence relative to the first block.
As a result, we strictly outperform both compress-and- forward and decode-and-forward.
Furthermore, this paradigm can be implemented with a low-complexity polar coding
scheme that has the typical attractive features of polar codes, i.e., quasi-linear
encoding/decoding complexity and super-polynomial decay of the error probability.
Throughout the paper we consider as a running example the special case of the
erasure relay channel and we compare the rates achievable by our proposed scheme
with the existing upper and lower bounds.'
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: 'Mondelli M, Hassani H, Urbanke R. A new coding paradigm for the primitive
relay channel. In: 2018 IEEE International Symposium on Information Theory.
IEEE; 2018:351-355. doi:10.1109/isit.2018.8437479'
apa: 'Mondelli, M., Hassani, H., & Urbanke, R. (2018). A new coding paradigm
for the primitive relay channel. In 2018 IEEE International Symposium on Information
Theory (pp. 351–355). Vail, CO, United States: IEEE. https://doi.org/10.1109/isit.2018.8437479'
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “A New Coding Paradigm
for the Primitive Relay Channel.” In 2018 IEEE International Symposium on Information
Theory, 351–55. IEEE, 2018. https://doi.org/10.1109/isit.2018.8437479.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “A new coding paradigm for the primitive
relay channel,” in 2018 IEEE International Symposium on Information Theory,
Vail, CO, United States, 2018, pp. 351–355.
ista: 'Mondelli M, Hassani H, Urbanke R. 2018. A new coding paradigm for the primitive
relay channel. 2018 IEEE International Symposium on Information Theory. ISIT:
International Symposium on Information Theory , 351–355.'
mla: Mondelli, Marco, et al. “A New Coding Paradigm for the Primitive Relay Channel.”
2018 IEEE International Symposium on Information Theory, IEEE, 2018, pp.
351–55, doi:10.1109/isit.2018.8437479.
short: M. Mondelli, H. Hassani, R. Urbanke, in:, 2018 IEEE International Symposium
on Information Theory, IEEE, 2018, pp. 351–355.
conference:
end_date: 2018-06-22
location: Vail, CO, United States
name: 'ISIT: International Symposium on Information Theory '
start_date: 2018-06-17
date_created: 2019-07-24T09:10:38Z
date_published: 2018-06-16T00:00:00Z
date_updated: 2023-02-23T12:56:49Z
day: '16'
doi: 10.1109/isit.2018.8437479
extern: '1'
external_id:
arxiv:
- '1801.03153'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1801.03153
month: '06'
oa: 1
oa_version: Preprint
page: 351-355
publication: 2018 IEEE International Symposium on Information Theory
publication_identifier:
eissn:
- 2157-8117
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '7007'
relation: later_version
status: public
status: public
title: A new coding paradigm for the primitive relay channel
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6665'
abstract:
- lang: eng
text: We prove that, at least for the binary erasure channel, the polar-coding paradigm
gives rise to codes that not only approach the Shannon limit but, in fact, 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.
Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure
reliable communication at rates within ε > 0 of capacity with block length n =
O(1/ε 2+δ ), construction complexity Θ(n), and encoding/decoding complexity Θ(n
log n).
author:
- first_name: Arman
full_name: Fazeli, Arman
last_name: Fazeli
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Alexander
full_name: Vardy, Alexander
last_name: Vardy
citation:
ama: 'Fazeli A, Hassani H, Mondelli M, Vardy A. Binary linear codes with optimal
scaling: Polar codes with large kernels. In: 2018 IEEE Information Theory Workshop.
IEEE; 2018:1-5. doi:10.1109/itw.2018.8613428'
apa: 'Fazeli, A., Hassani, H., Mondelli, M., & Vardy, A. (2018). Binary linear
codes with optimal scaling: Polar codes with large kernels. In 2018 IEEE Information
Theory Workshop (pp. 1–5). Guangzhou, China: IEEE. https://doi.org/10.1109/itw.2018.8613428'
chicago: 'Fazeli, Arman, Hamed Hassani, Marco Mondelli, and Alexander Vardy. “Binary
Linear Codes with Optimal Scaling: Polar Codes with Large Kernels.” In 2018
IEEE Information Theory Workshop, 1–5. IEEE, 2018. https://doi.org/10.1109/itw.2018.8613428.'
ieee: 'A. Fazeli, H. Hassani, M. Mondelli, and A. Vardy, “Binary linear codes with
optimal scaling: Polar codes with large kernels,” in 2018 IEEE Information
Theory Workshop, Guangzhou, China, 2018, pp. 1–5.'
ista: 'Fazeli A, Hassani H, Mondelli M, Vardy A. 2018. Binary linear codes with
optimal scaling: Polar codes with large kernels. 2018 IEEE Information Theory
Workshop. ITW: Information Theory Workshop, 1–5.'
mla: 'Fazeli, Arman, et al. “Binary Linear Codes with Optimal Scaling: Polar Codes
with Large Kernels.” 2018 IEEE Information Theory Workshop, IEEE, 2018,
pp. 1–5, doi:10.1109/itw.2018.8613428.'
short: A. Fazeli, H. Hassani, M. Mondelli, A. Vardy, in:, 2018 IEEE Information
Theory Workshop, IEEE, 2018, pp. 1–5.
conference:
end_date: 2018-11-29
location: Guangzhou, China
name: 'ITW: Information Theory Workshop'
start_date: 2018-11-25
date_created: 2019-07-23T11:01:42Z
date_published: 2018-11-01T00:00:00Z
date_updated: 2024-03-07T12:18:50Z
day: '01'
doi: 10.1109/itw.2018.8613428
extern: '1'
external_id:
arxiv:
- '1711.01339'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1711.01339
month: '11'
oa: 1
oa_version: Preprint
page: 1-5
publication: 2018 IEEE Information Theory Workshop
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '9002'
relation: later_version
status: public
status: public
title: 'Binary linear codes with optimal scaling: Polar codes with large kernels'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '6679'
abstract:
- lang: eng
text: 'Polar codes represent one of the major recent breakthroughs in coding theory
and, because of their attractive features, they have been selected for the incoming
5G standard. As such, a lot of attention has been devoted to the development of
decoding algorithms with good error performance and efficient hardware implementation.
One of the leading candidates in this regard is represented by successive-cancellation
list (SCL) decoding. However, its hardware implementation requires a large amount
of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly
reduce the memory consumption [1]. In this paper, we examine the paradigm of PSCL
decoding from both theoretical and practical standpoints: (i) by changing the
construction of the code, we are able to improve the performance at no additional
computational, latency or memory cost, (ii) we present an optimal scheme to allocate
cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list
size that allows MAP performance.'
author:
- first_name: Seyyed Ali
full_name: Hashemi, Seyyed Ali
last_name: Hashemi
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Ruediger
full_name: Urbanke, Ruediger
last_name: Urbanke
- first_name: Warren
full_name: Gross, Warren
last_name: Gross
citation:
ama: 'Hashemi SA, Mondelli M, Hassani H, Urbanke R, Gross W. Partitioned list decoding
of polar codes: Analysis and improvement of finite length performance. In: 2017
IEEE Global Communications Conference. IEEE; 2017:1-7. doi:10.1109/glocom.2017.8254940'
apa: 'Hashemi, S. A., Mondelli, M., Hassani, H., Urbanke, R., & Gross, W. (2017).
Partitioned list decoding of polar codes: Analysis and improvement of finite length
performance. In 2017 IEEE Global Communications Conference (pp. 1–7). Singapore,
Singapore: IEEE. https://doi.org/10.1109/glocom.2017.8254940'
chicago: 'Hashemi, Seyyed Ali, Marco Mondelli, Hamed Hassani, Ruediger Urbanke,
and Warren Gross. “Partitioned List Decoding of Polar Codes: Analysis and Improvement
of Finite Length Performance.” In 2017 IEEE Global Communications Conference,
1–7. IEEE, 2017. https://doi.org/10.1109/glocom.2017.8254940.'
ieee: 'S. A. Hashemi, M. Mondelli, H. Hassani, R. Urbanke, and W. Gross, “Partitioned
list decoding of polar codes: Analysis and improvement of finite length performance,”
in 2017 IEEE Global Communications Conference, Singapore, Singapore, 2017,
pp. 1–7.'
ista: 'Hashemi SA, Mondelli M, Hassani H, Urbanke R, Gross W. 2017. Partitioned
list decoding of polar codes: Analysis and improvement of finite length performance.
2017 IEEE Global Communications Conference. GLOBECOM: Global Communications Conference,
1–7.'
mla: 'Hashemi, Seyyed Ali, et al. “Partitioned List Decoding of Polar Codes: Analysis
and Improvement of Finite Length Performance.” 2017 IEEE Global Communications
Conference, IEEE, 2017, pp. 1–7, doi:10.1109/glocom.2017.8254940.'
short: S.A. Hashemi, M. Mondelli, H. Hassani, R. Urbanke, W. Gross, in:, 2017 IEEE
Global Communications Conference, IEEE, 2017, pp. 1–7.
conference:
end_date: 2017-12-08
location: Singapore, Singapore
name: 'GLOBECOM: Global Communications Conference'
start_date: 2017-12-04
date_created: 2019-07-24T13:55:25Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2021-01-12T08:08:34Z
day: '01'
doi: 10.1109/glocom.2017.8254940
extern: '1'
external_id:
arxiv:
- '1705.05497'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.05497
month: '12'
oa: 1
oa_version: Preprint
page: 1-7
publication: 2017 IEEE Global Communications Conference
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'Partitioned list decoding of polar codes: Analysis and improvement of finite
length performance'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '6729'
abstract:
- lang: eng
text: Consider the problem of constructing a polar code of block length N for the
transmission over a given channel W. Typically this requires to compute the reliability
of all the N synthetic channels and then to include those that are sufficiently
reliable. However, we know from [1], [2] that there is a partial order among the
synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce
the computational burden of the construction problem. We show that, if we take
advantage of the partial order [1], [2], we can construct a polar code by computing
the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic
channels is universal, in the sense that it allows one to construct polar codes
for any W, and it can be identified by solving a maximum matching problem on a
bipartite graph. Our proof technique consists in reducing the construction problem
to the problem of computing the maximum cardinality of an antichain for a suitable
partially ordered set. As such, this method is general and it can be used to further
improve the complexity of the construction problem in case a new partial order
on the synthetic channels of polar codes is discovered.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: S. Hamed
full_name: Hassani, S. Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: 'Mondelli M, Hassani SH, Urbanke R. Construction of polar codes with sublinear
complexity. In: 2017 IEEE International Symposium on Information Theory .
IEEE; 2017:1853-1857. doi:10.1109/isit.2017.8006850'
apa: 'Mondelli, M., Hassani, S. H., & Urbanke, R. (2017). Construction of polar
codes with sublinear complexity. In 2017 IEEE International Symposium on Information
Theory (pp. 1853–1857). Aachen, Germany: IEEE. https://doi.org/10.1109/isit.2017.8006850'
chicago: Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of
Polar Codes with Sublinear Complexity.” In 2017 IEEE International Symposium
on Information Theory , 1853–57. IEEE, 2017. https://doi.org/10.1109/isit.2017.8006850.
ieee: M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with
sublinear complexity,” in 2017 IEEE International Symposium on Information
Theory , Aachen, Germany, 2017, pp. 1853–1857.
ista: 'Mondelli M, Hassani SH, Urbanke R. 2017. Construction of polar codes with
sublinear complexity. 2017 IEEE International Symposium on Information Theory
. ISIT: International Symposium on Information Theory, 1853–1857.'
mla: Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.”
2017 IEEE International Symposium on Information Theory , IEEE, 2017, pp.
1853–57, doi:10.1109/isit.2017.8006850.
short: M. Mondelli, S.H. Hassani, R. Urbanke, in:, 2017 IEEE International Symposium
on Information Theory , IEEE, 2017, pp. 1853–1857.
conference:
end_date: 2017-06-30
location: Aachen, Germany
name: 'ISIT: International Symposium on Information Theory'
start_date: 2017-06-25
date_created: 2019-07-30T07:14:18Z
date_published: 2017-06-15T00:00:00Z
date_updated: 2023-02-23T12:49:08Z
day: '15'
doi: 10.1109/isit.2017.8006850
extern: '1'
external_id:
arxiv:
- '1612.05295'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1612.05295
month: '06'
oa: 1
oa_version: Preprint
page: 1853-1857
publication: '2017 IEEE International Symposium on Information Theory '
publication_identifier:
eissn:
- 2157-8117
isbn:
- '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6663'
relation: later_version
status: public
status: public
title: Construction of polar codes with sublinear complexity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '6730'
abstract:
- lang: eng
text: We introduce a new approach to proving that a sequence of deterministic linear
codes achieves capacity on an erasure channel under maximum a posteriori decoding.
Rather than relying on the precise structure of the codes, our method exploits
code symmetry. In particular, the technique applies to any sequence of linear
codes where the blocklengths are strictly increasing, the code rates converge,
and the permutation group of each code is doubly transitive. In other words, we
show that symmetry alone implies near-optimal performance. An important consequence
of this result is that a sequence of Reed-Muller codes with increasing block length
and converging rate achieves capacity. This possibility has been suggested previously
in the literature but it has only been proven for cases where the limiting code
rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant
codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves,
in the affirmative, the existence question for capacity-achieving sequences of
binary cyclic codes. The primary tools used in the proof are the sharp threshold
property for symmetric monotone Boolean functions and the area theorem for extrinsic
information transfer functions.
author:
- first_name: Shrinivas
full_name: Kudekar, Shrinivas
last_name: Kudekar
- first_name: Santhosh
full_name: Kumar, Santhosh
last_name: Kumar
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Henry D.
full_name: Pfister, Henry D.
last_name: Pfister
- first_name: Eren
full_name: Sasoglu, Eren
last_name: Sasoglu
- first_name: Ridiger L.
full_name: Urbanke, Ridiger L.
last_name: Urbanke
citation:
ama: Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoglu E, Urbanke RL. Reed–Muller
codes achieve capacity on erasure channels. IEEE Transactions on Information
Theory. 2017;63(7):4298-4316. doi:10.1109/tit.2017.2673829
apa: Kudekar, S., Kumar, S., Mondelli, M., Pfister, H. D., Sasoglu, E., & Urbanke,
R. L. (2017). Reed–Muller codes achieve capacity on erasure channels. IEEE
Transactions on Information Theory. IEEE. https://doi.org/10.1109/tit.2017.2673829
chicago: Kudekar, Shrinivas, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren
Sasoglu, and Ridiger L. Urbanke. “Reed–Muller Codes Achieve Capacity on Erasure
Channels.” IEEE Transactions on Information Theory. IEEE, 2017. https://doi.org/10.1109/tit.2017.2673829.
ieee: S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Sasoglu, and R. L. Urbanke,
“Reed–Muller codes achieve capacity on erasure channels,” IEEE Transactions
on Information Theory, vol. 63, no. 7. IEEE, pp. 4298–4316, 2017.
ista: Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoglu E, Urbanke RL. 2017. Reed–Muller
codes achieve capacity on erasure channels. IEEE Transactions on Information Theory.
63(7), 4298–4316.
mla: Kudekar, Shrinivas, et al. “Reed–Muller Codes Achieve Capacity on Erasure Channels.”
IEEE Transactions on Information Theory, vol. 63, no. 7, IEEE, 2017, pp.
4298–316, doi:10.1109/tit.2017.2673829.
short: S. Kudekar, S. Kumar, M. Mondelli, H.D. Pfister, E. Sasoglu, R.L. Urbanke,
IEEE Transactions on Information Theory 63 (2017) 4298–4316.
date_created: 2019-07-30T07:18:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2021-01-12T08:08:43Z
day: '01'
doi: 10.1109/tit.2017.2673829
extern: '1'
external_id:
arxiv:
- '1601.04689'
intvolume: ' 63'
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1601.04689
month: '07'
oa: 1
oa_version: Preprint
page: 4298-4316
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Reed–Muller codes achieve capacity on erasure channels
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 63
year: '2017'
...
---
_id: '6731'
abstract:
- lang: eng
text: 'We present a rate-compatible polar coding scheme that achieves the capacity
of any family of channels. Our solution generalizes the previous results [1],
[2] that provide capacity-achieving rate-compatible polar codes for a degraded
family of channels. The motivation for our extension comes from the fact that
in many practical scenarios, e.g., MIMO systems and non-Gaussian interference,
the channels cannot be ordered by degradation. The main technical contribution
of this paper consists in removing the degradation condition. To do so, we exploit
the ideas coming from the construction of universal polar codes. Our scheme possesses
the usual attractive features of polar codes: low complexity code construction,
encoding, and decoding; super-polynomial scaling of the error probability with
the block length; and absence of error floors. On the negative side, the scaling
of the gap to capacity with the block length is slower than in standard polar
codes, and we prove an upper bound on the scaling exponent.'
article_number: '7919107'
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Ivana
full_name: Maric, Ivana
last_name: Maric
- first_name: Dennis
full_name: Hui, Dennis
last_name: Hui
- first_name: Song-Nam
full_name: Hong, Song-Nam
last_name: Hong
citation:
ama: 'Mondelli M, Hassani H, Maric I, Hui D, Hong S-N. Capacity-achieving rate-compatible
polar codes for general channels. In: 2017 IEEE Wireless Communications and
Networking Conference Workshops . IEEE; 2017. doi:10.1109/wcncw.2017.7919107'
apa: 'Mondelli, M., Hassani, H., Maric, I., Hui, D., & Hong, S.-N. (2017). Capacity-achieving
rate-compatible polar codes for general channels. In 2017 IEEE Wireless Communications
and Networking Conference Workshops . San Francisco, CA, USA: IEEE. https://doi.org/10.1109/wcncw.2017.7919107'
chicago: Mondelli, Marco, Hamed Hassani, Ivana Maric, Dennis Hui, and Song-Nam Hong.
“Capacity-Achieving Rate-Compatible Polar Codes for General Channels.” In 2017
IEEE Wireless Communications and Networking Conference Workshops . IEEE, 2017.
https://doi.org/10.1109/wcncw.2017.7919107.
ieee: M. Mondelli, H. Hassani, I. Maric, D. Hui, and S.-N. Hong, “Capacity-achieving
rate-compatible polar codes for general channels,” in 2017 IEEE Wireless Communications
and Networking Conference Workshops , San Francisco, CA, USA, 2017.
ista: 'Mondelli M, Hassani H, Maric I, Hui D, Hong S-N. 2017. Capacity-achieving
rate-compatible polar codes for general channels. 2017 IEEE Wireless Communications
and Networking Conference Workshops . WCNCW: Wireless communications and networking
conference workshops, 7919107.'
mla: Mondelli, Marco, et al. “Capacity-Achieving Rate-Compatible Polar Codes for
General Channels.” 2017 IEEE Wireless Communications and Networking Conference
Workshops , 7919107, IEEE, 2017, doi:10.1109/wcncw.2017.7919107.
short: M. Mondelli, H. Hassani, I. Maric, D. Hui, S.-N. Hong, in:, 2017 IEEE Wireless
Communications and Networking Conference Workshops , IEEE, 2017.
conference:
end_date: 2017-03-22
location: San Francisco, CA, USA
name: 'WCNCW: Wireless communications and networking conference workshops'
start_date: 2017-03-19
date_created: 2019-07-31T05:56:58Z
date_published: 2017-05-04T00:00:00Z
date_updated: 2021-01-12T08:08:43Z
day: '04'
doi: 10.1109/wcncw.2017.7919107
extern: '1'
external_id:
arxiv:
- '1611.01199'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.01199
month: '05'
oa: 1
oa_version: Preprint
publication: '2017 IEEE Wireless Communications and Networking Conference Workshops '
publication_identifier:
isbn:
- '9781509059089'
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Capacity-achieving rate-compatible polar codes for general channels
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '6732'
abstract:
- lang: eng
text: Consider the transmission of a polar code of block length N and rate R over
a binary memoryless symmetric channel W and let P e be the block error probability
under successive cancellation decoding. In this paper, we develop new bounds that
characterize the relationship of the parameters R, N, P e , and the quality of
the channel W quantified by its capacity I(W) and its Bhattacharyya parameter
Z(W). In previous work, two main regimes were studied. In the error exponent regime,
the channel W and the rate R <; I(W) are fixed, and it was proved that the error
probability Pe scales roughly as 2 -√N . In the scaling exponent approach, the
channel W and the error probability Pe are fixed and it was proved that the gap
to capacity I(W) - R scales as N -1/μ . Here, μ is called scaling exponent and
this scaling exponent depends on the channel W. A heuristic computation for the
binary erasure channel (BEC) gives μ = 3.627 and it was shown that, for any channel
W, 3.579 ≤ μ ≤ 5.702. Our contributions are as follows. First, we provide the
tighter upper bound μ <;≤ 4.714 valid for any W. With the same technique, we obtain
the upper bound μ ≤ 3.639 for the case of the BEC; this upper bound approaches
very closely the heuristically derived value for the scaling exponent of the erasure
channel. Second, we develop a trade-off between the gap to capacity I(W)- R and
the error probability Pe as the functions of the block length N. In other words,
we neither fix the gap to capacity (error exponent regime) nor the error probability
(scaling exponent regime), but we do consider a moderate deviations regime in
which we study how fast both quantities, as the functions of the block length
N, simultaneously go to 0. Third, we prove that polar codes are not affected by
error floors. To do so, we fix a polar code of block length N and rate R. Then,
we vary the channel W and study the impact of this variation on the error probability.
We show that the error probability Pe scales as the Bhattacharyya parameter Z(W)
raised to a power that scales roughly like VN. This agrees with the scaling in
the error exponent regime.
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: S. Hamed
full_name: Hassani, S. Hamed
last_name: Hassani
- first_name: Rudiger L.
full_name: Urbanke, Rudiger L.
last_name: Urbanke
citation:
ama: 'Mondelli M, Hassani SH, Urbanke RL. Unified scaling of polar codes: Error
exponent, scaling exponent, moderate deviations, and error floors. IEEE Transactions
on Information Theory. 2016;62(12):6698-6712. doi:10.1109/tit.2016.2616117'
apa: 'Mondelli, M., Hassani, S. H., & Urbanke, R. L. (2016). Unified scaling
of polar codes: Error exponent, scaling exponent, moderate deviations, and error
floors. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/tit.2016.2616117'
chicago: 'Mondelli, Marco, S. Hamed Hassani, and Rudiger L. Urbanke. “Unified Scaling
of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error
Floors.” IEEE Transactions on Information Theory. IEEE, 2016. https://doi.org/10.1109/tit.2016.2616117.'
ieee: 'M. Mondelli, S. H. Hassani, and R. L. Urbanke, “Unified scaling of polar
codes: Error exponent, scaling exponent, moderate deviations, and error floors,”
IEEE Transactions on Information Theory, vol. 62, no. 12. IEEE, pp. 6698–6712,
2016.'
ista: 'Mondelli M, Hassani SH, Urbanke RL. 2016. Unified scaling of polar codes:
Error exponent, scaling exponent, moderate deviations, and error floors. IEEE
Transactions on Information Theory. 62(12), 6698–6712.'
mla: 'Mondelli, Marco, et al. “Unified Scaling of Polar Codes: Error Exponent, Scaling
Exponent, Moderate Deviations, and Error Floors.” IEEE Transactions on Information
Theory, vol. 62, no. 12, IEEE, 2016, pp. 6698–712, doi:10.1109/tit.2016.2616117.'
short: M. Mondelli, S.H. Hassani, R.L. Urbanke, IEEE Transactions on Information
Theory 62 (2016) 6698–6712.
date_created: 2019-07-31T06:03:49Z
date_published: 2016-12-01T00:00:00Z
date_updated: 2021-01-12T08:08:44Z
day: '01'
doi: 10.1109/tit.2016.2616117
extern: '1'
external_id:
arxiv:
- '1501.02444'
intvolume: ' 62'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1501.02444
month: '12'
oa: 1
oa_version: Preprint
page: 6698-6712
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'Unified scaling of polar codes: Error exponent, scaling exponent, moderate
deviations, and error floors'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2016'
...
---
_id: '6733'
abstract:
- lang: eng
text: 'The question whether RM codes are capacity-achieving is a long-standing open
problem in coding theory that was recently answered in the affirmative for transmission
over erasure channels [1], [2]. Remarkably, the proof does not rely on specific
properties of RM codes, apart from their symmetry. Indeed, the main technical
result consists in showing that any sequence of linear codes, with doubly-transitive
permutation groups, achieves capacity on the memoryless erasure channel under
bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding.
In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold
was shown to be sharp enough so that the block erasure probability also converges
to 0. However, this technique relies heavily on the fact that the transmission
is over an erasure channel. We present an alternative approach to strengthen results
regarding the bit-MAP threshold to block-MAP thresholds. This approach is based
on a careful analysis of the weight distribution of RM codes. In particular, the
flavor of the main result is the following: assume that the bit-MAP error probability
decays as N -δ , for some δ > 0. Then, the block-MAP error probability also converges
to 0. This technique applies to transmission over any binary memoryless symmetric
channel. Thus, it can be thought of as a first step in extending the proof that
RM codes are capacity-achieving to the general case.'
author:
- first_name: Shrinivas
full_name: Kudekar, Shrinivas
last_name: Kudekar
- first_name: Santhosh
full_name: Kumar, Santhosh
last_name: Kumar
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Henry D.
full_name: Pfister, Henry D.
last_name: Pfister
- first_name: Rudiger
full_name: Urbankez, Rudiger
last_name: Urbankez
citation:
ama: 'Kudekar S, Kumar S, Mondelli M, Pfister HD, Urbankez R. Comparing the bit-MAP
and block-MAP decoding thresholds of Reed-Muller codes on BMS channels. In: 2016
IEEE International Symposium on Information Theory . IEEE; 2016:1755-1759.
doi:10.1109/isit.2016.7541600'
apa: 'Kudekar, S., Kumar, S., Mondelli, M., Pfister, H. D., & Urbankez, R. (2016).
Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on
BMS channels. In 2016 IEEE International Symposium on Information Theory
(pp. 1755–1759). Barcelona, Spain: IEEE. https://doi.org/10.1109/isit.2016.7541600'
chicago: Kudekar, Shrinivas, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, and
Rudiger Urbankez. “Comparing the Bit-MAP and Block-MAP Decoding Thresholds of
Reed-Muller Codes on BMS Channels.” In 2016 IEEE International Symposium on
Information Theory , 1755–59. IEEE, 2016. https://doi.org/10.1109/isit.2016.7541600.
ieee: S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, and R. Urbankez, “Comparing
the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels,”
in 2016 IEEE International Symposium on Information Theory , Barcelona,
Spain, 2016, pp. 1755–1759.
ista: 'Kudekar S, Kumar S, Mondelli M, Pfister HD, Urbankez R. 2016. Comparing the
bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels.
2016 IEEE International Symposium on Information Theory . ISIT: International
Symposium on Information Theory, 1755–1759.'
mla: Kudekar, Shrinivas, et al. “Comparing the Bit-MAP and Block-MAP Decoding Thresholds
of Reed-Muller Codes on BMS Channels.” 2016 IEEE International Symposium on
Information Theory , IEEE, 2016, pp. 1755–59, doi:10.1109/isit.2016.7541600.
short: S. Kudekar, S. Kumar, M. Mondelli, H.D. Pfister, R. Urbankez, in:, 2016 IEEE
International Symposium on Information Theory , IEEE, 2016, pp. 1755–1759.
conference:
end_date: 2016-07-15
location: Barcelona, Spain
name: 'ISIT: International Symposium on Information Theory'
start_date: 2016-07-10
date_created: 2019-07-31T06:36:16Z
date_published: 2016-08-11T00:00:00Z
date_updated: 2021-01-12T08:08:44Z
day: '11'
doi: 10.1109/isit.2016.7541600
extern: '1'
external_id:
arxiv:
- '1601.06048'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1601.06048
month: '08'
oa: 1
oa_version: Preprint
page: 1755-1759
publication: '2016 IEEE International Symposium on Information Theory '
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes
on BMS channels
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '6770'
abstract:
- lang: eng
text: "We describe a new method to compare the bit-MAP and block-MAP decoding thresholds
of Reed-Muller (RM) codes for transmission over a binary memoryless symmetric
channel. The question whether RM codes are capacity-achieving is a long-standing
open problem in coding theory and it has recently been answered in the affirmative
for transmission over\r\nerasure channels. Remarkably, the proof does not rely
on specific properties of RM codes, apart from their symmetry. Indeed, the main
technical result consists in showing that any sequence of linear codes, with doubly-transitive
permutation groups, achieves capacity on the memoryless erasure channel under
bit-MAP decoding. A natural question is what happens under block-MAP decoding.
If the minimum distance of the code family is close to linear (e.g., of order
N/ log(N)), then one can combine an upper bound on the bit-MAP error probability
with a lower bound on the minimum distance to show that the code family is also
capacity-achieving under block-MAP decoding. This strategy is successful for BCH
codes. Unfortunately, the minimum distance of RM codes scales only as √N, which
does not suffice to obtain the desired result. Then, one can exploit further symmetries
of RM codes to show that the bit-MAP threshold is sharp enough so that the block
erasure probability also tends to 0. However, this technique relies heavily on
the fact that the transmission is over an erasure channel.\r\nWe present an alternative
approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds.
This approach is based on a careful analysis of the weight distribution of RM
codes. In particular, the flavor of the main result is the following: assume that
the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP\r\nerror
probability also converges to 0. This technique applies to the transmission over
any binary memoryless symmetric channel. Thus, it can be thought of as a first
step in extending the proof that RM codes are capacity-achieving to the general
case."
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Shrinivas
full_name: Kudekar, Shrinivas
last_name: Kudekar
- first_name: Santosh
full_name: Kumar, Santosh
last_name: Kumar
- first_name: Henry D.
full_name: Pfister, Henry D.
last_name: Pfister
- first_name: Eren
full_name: Şaşoğlu, Eren
last_name: Şaşoğlu
- first_name: Rüdiger
full_name: Urbanke, Rüdiger
last_name: Urbanke
citation:
ama: 'Mondelli M, Kudekar S, Kumar S, Pfister HD, Şaşoğlu E, Urbanke R. Reed-Muller
codes: Thresholds and weight distribution. In: 24th International Zurich Seminar
on Communications. ETH Zürich; 2016:50. doi:10.3929/ETHZ-A-010646484'
apa: 'Mondelli, M., Kudekar, S., Kumar, S., Pfister, H. D., Şaşoğlu, E., & Urbanke,
R. (2016). Reed-Muller codes: Thresholds and weight distribution. In 24th International
Zurich Seminar on Communications (p. 50). Zurich, Switzerland: ETH Zürich.
https://doi.org/10.3929/ETHZ-A-010646484'
chicago: 'Mondelli, Marco, Shrinivas Kudekar, Santosh Kumar, Henry D. Pfister, Eren
Şaşoğlu, and Rüdiger Urbanke. “Reed-Muller Codes: Thresholds and Weight Distribution.”
In 24th International Zurich Seminar on Communications, 50. ETH Zürich,
2016. https://doi.org/10.3929/ETHZ-A-010646484.'
ieee: 'M. Mondelli, S. Kudekar, S. Kumar, H. D. Pfister, E. Şaşoğlu, and R. Urbanke,
“Reed-Muller codes: Thresholds and weight distribution,” in 24th International
Zurich Seminar on Communications, Zurich, Switzerland, 2016, p. 50.'
ista: 'Mondelli M, Kudekar S, Kumar S, Pfister HD, Şaşoğlu E, Urbanke R. 2016. Reed-Muller
codes: Thresholds and weight distribution. 24th International Zurich Seminar on
Communications. IZS: International Zurich Seminar on Communications, 50.'
mla: 'Mondelli, Marco, et al. “Reed-Muller Codes: Thresholds and Weight Distribution.”
24th International Zurich Seminar on Communications, ETH Zürich, 2016,
p. 50, doi:10.3929/ETHZ-A-010646484.'
short: M. Mondelli, S. Kudekar, S. Kumar, H.D. Pfister, E. Şaşoğlu, R. Urbanke,
in:, 24th International Zurich Seminar on Communications, ETH Zürich, 2016, p.
50.
conference:
end_date: 2016-03-04
location: Zurich, Switzerland
name: 'IZS: International Zurich Seminar on Communications'
start_date: 2016-03-02
date_created: 2019-08-05T12:43:48Z
date_published: 2016-03-01T00:00:00Z
date_updated: 2021-01-12T08:08:57Z
day: '01'
doi: 10.3929/ETHZ-A-010646484
extern: '1'
language:
- iso: eng
month: '03'
oa_version: None
page: '50'
publication: 24th International Zurich Seminar on Communications
publication_status: published
publisher: ETH Zürich
quality_controlled: '1'
status: public
title: 'Reed-Muller codes: Thresholds and weight distribution'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '6737'
abstract:
- lang: eng
text: This paper presents polar coding schemes for the two-user discrete memoryless
broadcast channel (DM-BC) which achieve Marton's region with both common and private
messages. This is the best achievable rate region known to date, and it is tight
for all classes of two-user DM-BCs whose capacity regions are known. To accomplish
this task, we first construct polar codes for both the superposition as well as
binning strategy. By combining these two schemes, we obtain Marton's region with
private messages only. Finally, we show how to handle the case of common information.
The proposed coding schemes possess the usual advantages of polar codes, i.e.,
they have low encoding and decoding complexity and a superpolynomial decay rate
of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who
recently introduced polar codes emulating the superposition and binning schemes.
To align the polar indices, for both schemes, their solution involves some degradedness
constraints that are assumed to hold between the auxiliary random variables and
channel outputs. To remove these constraints, we consider the transmission of
k blocks and employ a chaining construction that guarantees the proper alignment
of the polarized indices. The techniques described in this paper are quite general,
and they can be adopted to many other multiterminal scenarios whenever there polar
indices need to be aligned.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Igal
full_name: Sason, Igal
last_name: Sason
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Sason I, Urbanke R. Achieving Marton’s region for broadcast
channels using polar codes. IEEE Transactions on Information Theory. 2015;61(2):783-800.
doi:10.1109/tit.2014.2368555
apa: Mondelli, M., Hassani, H., Sason, I., & Urbanke, R. (2015). Achieving Marton’s
region for broadcast channels using polar codes. IEEE Transactions on Information
Theory. IEEE. https://doi.org/10.1109/tit.2014.2368555
chicago: Mondelli, Marco, Hamed Hassani, Igal Sason, and Rudiger Urbanke. “Achieving
Marton’s Region for Broadcast Channels Using Polar Codes.” IEEE Transactions
on Information Theory. IEEE, 2015. https://doi.org/10.1109/tit.2014.2368555.
ieee: M. Mondelli, H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton’s region
for broadcast channels using polar codes,” IEEE Transactions on Information
Theory, vol. 61, no. 2. IEEE, pp. 783–800, 2015.
ista: Mondelli M, Hassani H, Sason I, Urbanke R. 2015. Achieving Marton’s region
for broadcast channels using polar codes. IEEE Transactions on Information Theory.
61(2), 783–800.
mla: Mondelli, Marco, et al. “Achieving Marton’s Region for Broadcast Channels Using
Polar Codes.” IEEE Transactions on Information Theory, vol. 61, no. 2,
IEEE, 2015, pp. 783–800, doi:10.1109/tit.2014.2368555.
short: M. Mondelli, H. Hassani, I. Sason, R. Urbanke, IEEE Transactions on Information
Theory 61 (2015) 783–800.
date_created: 2019-07-31T07:03:38Z
date_published: 2015-02-01T00:00:00Z
date_updated: 2021-01-12T08:08:46Z
day: '01'
doi: 10.1109/tit.2014.2368555
extern: '1'
external_id:
arxiv:
- '1401.6060'
intvolume: ' 61'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1401.6060
month: '02'
oa: 1
oa_version: Preprint
page: 783-800
publication: IEEE Transactions on Information Theory
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Achieving Marton’s region for broadcast channels using polar codes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2015'
...
---
_id: '6736'
abstract:
- lang: eng
text: Motivated by the significant performance gains which polar codes experience
under successive cancellation list decoding, their scaling exponent is studied
as a function of the list size. In particular, the error probability is fixed,
and the tradeoff between the block length and back-off from capacity is analyzed.
A lower bound is provided on the error probability under MAP decoding with list
size L for any binary-input memoryless output-symmetric channel and for any class
of linear codes such that their minimum distance is unbounded as the block length
grows large. Then, it is shown that under MAP decoding, although the introduction
of a list can significantly improve the involved constants, the scaling exponent
itself, i.e., the speed at which capacity is approached, stays unaffected for
any finite list size. In particular, this result applies to polar codes, since
their minimum distance tends to infinity as the block length increases. A similar
result is proved for genie-aided successive cancellation decoding when transmission
takes place over the binary erasure channel, namely, the scaling exponent remains
constant for any fixed number of helps from the genie. Note that since genie-aided
successive cancellation decoding might be strictly worse than successive cancellation
list decoding, the problem of establishing the scaling exponent of the latter
remains open.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Urbanke R. Scaling exponent of list decoders with applications
to polar codes. IEEE Transactions on Information Theory. 2015;61(9):4838-4851.
doi:10.1109/tit.2015.2453315
apa: Mondelli, M., Hassani, H., & Urbanke, R. (2015). Scaling exponent of list
decoders with applications to polar codes. IEEE Transactions on Information
Theory. IEEE. https://doi.org/10.1109/tit.2015.2453315
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Scaling Exponent
of List Decoders with Applications to Polar Codes.” IEEE Transactions on Information
Theory. IEEE, 2015. https://doi.org/10.1109/tit.2015.2453315.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “Scaling exponent of list decoders
with applications to polar codes,” IEEE Transactions on Information Theory,
vol. 61, no. 9. IEEE, pp. 4838–4851, 2015.
ista: Mondelli M, Hassani H, Urbanke R. 2015. Scaling exponent of list decoders
with applications to polar codes. IEEE Transactions on Information Theory. 61(9),
4838–4851.
mla: Mondelli, Marco, et al. “Scaling Exponent of List Decoders with Applications
to Polar Codes.” IEEE Transactions on Information Theory, vol. 61, no.
9, IEEE, 2015, pp. 4838–51, doi:10.1109/tit.2015.2453315.
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Information Theory
61 (2015) 4838–4851.
date_created: 2019-07-31T06:50:34Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2021-01-12T08:08:45Z
day: '01'
doi: 10.1109/tit.2015.2453315
extern: '1'
external_id:
arxiv:
- '1304.5220'
intvolume: ' 61'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1304.5220
month: '09'
oa: 1
oa_version: Preprint
page: 4838-4851
publication: IEEE Transactions on Information Theory
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Scaling exponent of list decoders with applications to polar codes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2015'
...
---
_id: '6740'
abstract:
- lang: eng
text: We describe coding techniques that achieve the capacity of a discrete memoryless
asymmetric channel. To do so, we discuss how recent advances in coding for symmetric
channels yield more efficient solutions also for the asymmetric case. In more
detail, we consider three basic approaches. The first one is Gallager's scheme
that concatenates a linear code with a non-linear mapper, in order to bias the
input distribution. We explicitly show that both polar codes and spatially coupled
codes can be employed in this scenario. Further, we derive a scaling law between
the gap to capacity, the cardinality of channel input and output alphabets, and
the required size of the mapper. The second one is an integrated approach in which
the coding scheme is used both for source coding, in order to create codewords
with the capacity-achieving distribution, and for channel coding, in order to
provide error protection. Such a technique has been recently introduced by Honda
and Yamamoto in the context of polar codes, and we show how to apply it also to
the design of sparse graph codes. The third approach is based on an idea due to
Böcherer and Mathar and separates completely the two tasks of source coding and
channel coding by “chaining” together several codewords. We prove that we can
combine any suitable source code with any suitable channel code in order to provide
optimal schemes for asymmetric channels. In particular, polar codes and spatially
coupled codes fulfill the required conditions.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
citation:
ama: 'Mondelli M, Urbanke R, Hassani H. How to achieve the capacity of asymmetric
channels. In: 52nd Annual Allerton Conference on Communication, Control, and
Computing. IEEE; 2014:789-796. doi:10.1109/allerton.2014.7028535'
apa: 'Mondelli, M., Urbanke, R., & Hassani, H. (2014). How to achieve the capacity
of asymmetric channels. In 52nd Annual Allerton Conference on Communication,
Control, and Computing (pp. 789–796). Monticello, IL, United States: IEEE.
https://doi.org/10.1109/allerton.2014.7028535'
chicago: Mondelli, Marco, Rudiger Urbanke, and Hamed Hassani. “How to Achieve the
Capacity of Asymmetric Channels.” In 52nd Annual Allerton Conference on Communication,
Control, and Computing, 789–96. IEEE, 2014. https://doi.org/10.1109/allerton.2014.7028535.
ieee: M. Mondelli, R. Urbanke, and H. Hassani, “How to achieve the capacity of asymmetric
channels,” in 52nd Annual Allerton Conference on Communication, Control, and
Computing, Monticello, IL, United States, 2014, pp. 789–796.
ista: Mondelli M, Urbanke R, Hassani H. 2014. How to achieve the capacity of asymmetric
channels. 52nd Annual Allerton Conference on Communication, Control, and Computing.
Allerton Conference on Communication, Control, and Computing, 789–796.
mla: Mondelli, Marco, et al. “How to Achieve the Capacity of Asymmetric Channels.”
52nd Annual Allerton Conference on Communication, Control, and Computing,
IEEE, 2014, pp. 789–96, doi:10.1109/allerton.2014.7028535.
short: M. Mondelli, R. Urbanke, H. Hassani, in:, 52nd Annual Allerton Conference
on Communication, Control, and Computing, IEEE, 2014, pp. 789–796.
conference:
end_date: 2014-10-03
location: Monticello, IL, United States
name: Allerton Conference on Communication, Control, and Computing
start_date: 2014-09-30
date_created: 2019-07-31T07:24:23Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2023-02-23T12:49:36Z
day: '01'
doi: 10.1109/allerton.2014.7028535
extern: '1'
external_id:
arxiv:
- '1406.7373'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1406.7373
month: '10'
oa: 1
oa_version: Preprint
page: 789-796
publication: 52nd Annual Allerton Conference on Communication, Control, and Computing
publication_identifier:
eisbn:
- 978-1-4799-8009-3
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6678'
relation: later_version
status: public
status: public
title: How to achieve the capacity of asymmetric channels
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '6739'
abstract:
- lang: eng
text: 'We explore the relationship between polar and RM codes and we describe a
coding scheme which improves upon the performance of the standard polar code at
practical block lengths. Our starting point is the experimental observation that
RM codes have a smaller error probability than polar codes under MAP decoding.
This motivates us to introduce a family of codes that “interpolates” between RM
and polar codes, call this family C inter = {C α : α ∈ [0, 1j}, where C α|α=1
is the original polar code, and C α|α=0 is an RM code. Based on numerical observations,
we remark that the error probability under MAP decoding is an increasing function
of α. MAP decoding has in general exponential complexity, but empirically the
performance of polar codes at finite block lengths is boosted by moving along
the family Cinter even under low-complexity decoding schemes such as, for instance,
belief propagation or successive cancellation list decoder. We demonstrate the
performance gain via numerical simulations for transmission over the erasure channel
as well as the Gaussian channel.'
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: 'Mondelli M, Hassani H, Urbanke R. From polar to Reed-Muller codes: A technique
to improve the finite-length performance. IEEE Transactions on Communications.
2014;62(9):3084-3091. doi:10.1109/tcomm.2014.2345069'
apa: 'Mondelli, M., Hassani, H., & Urbanke, R. (2014). From polar to Reed-Muller
codes: A technique to improve the finite-length performance. IEEE Transactions
on Communications. IEEE. https://doi.org/10.1109/tcomm.2014.2345069'
chicago: 'Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “From Polar to Reed-Muller
Codes: A Technique to Improve the Finite-Length Performance.” IEEE Transactions
on Communications. IEEE, 2014. https://doi.org/10.1109/tcomm.2014.2345069.'
ieee: 'M. Mondelli, H. Hassani, and R. Urbanke, “From polar to Reed-Muller codes:
A technique to improve the finite-length performance,” IEEE Transactions on
Communications, vol. 62, no. 9. IEEE, pp. 3084–3091, 2014.'
ista: 'Mondelli M, Hassani H, Urbanke R. 2014. From polar to Reed-Muller codes:
A technique to improve the finite-length performance. IEEE Transactions on Communications.
62(9), 3084–3091.'
mla: 'Mondelli, Marco, et al. “From Polar to Reed-Muller Codes: A Technique to Improve
the Finite-Length Performance.” IEEE Transactions on Communications, vol.
62, no. 9, IEEE, 2014, pp. 3084–91, doi:10.1109/tcomm.2014.2345069.'
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Communications
62 (2014) 3084–3091.
date_created: 2019-07-31T07:20:21Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2021-01-12T08:08:46Z
day: '01'
doi: 10.1109/tcomm.2014.2345069
extern: '1'
external_id:
arxiv:
- '1401.3127'
intvolume: ' 62'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1401.3127
month: '09'
oa: 1
oa_version: Preprint
page: 3084-3091
publication: IEEE Transactions on Communications
publication_identifier:
issn:
- 0090-6778
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'From polar to Reed-Muller codes: A technique to improve the finite-length
performance'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2014'
...
---
_id: '6744'
abstract:
- lang: eng
text: With the aim of extending the coverage and improving the performance of impulse
radio ultra-wideband (UWB) systems, this paper focuses on developing a novel single
differential encoded decode and forward (DF) non-cooperative relaying scheme (NCR).
To favor simple receiver structures, differential noncoherent detection is employed
which enables effective energy capture without any channel estimation. Putting
emphasis on the general case of multi-hop relaying, we illustrate an original
algorithm for the joint power allocation and path selection (JPAPS), minimizing
an approximate expression of the overall bit error rate (BER). In particular,
after deriving a closed-form power allocation strategy, the optimal path selection
is reduced to a shortest path problem on a connected graph, which can be solved
without any topology information with complexity O(N 3 ), N being the number of
available relays of the network. An approximate scheme is also presented, which
reduces the complexity to O(N 2 ) while showing a negligible performance loss,
and for benchmarking purposes, an exhaustive-search based multi-hop DF cooperative
strategy is derived. Simulation results for various network setups corroborate
the effectiveness of the proposed low-complexity JPAPS algorithm, which favorably
compares to existing AF and DF relaying methods.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Qi
full_name: Zhou, Qi
last_name: Zhou
- first_name: Vincenzo
full_name: Lottici, Vincenzo
last_name: Lottici
- first_name: Xiaoli
full_name: Ma, Xiaoli
last_name: Ma
citation:
ama: Mondelli M, Zhou Q, Lottici V, Ma X. Joint power allocation and path selection
for multi-hop noncoherent decode and forward UWB communications. IEEE Transactions
on Wireless Communications. 2014;13(3):1397-1409. doi:10.1109/twc.2014.020914.130669
apa: Mondelli, M., Zhou, Q., Lottici, V., & Ma, X. (2014). Joint power allocation
and path selection for multi-hop noncoherent decode and forward UWB communications.
IEEE Transactions on Wireless Communications. IEEE. https://doi.org/10.1109/twc.2014.020914.130669
chicago: Mondelli, Marco, Qi Zhou, Vincenzo Lottici, and Xiaoli Ma. “Joint Power
Allocation and Path Selection for Multi-Hop Noncoherent Decode and Forward UWB
Communications.” IEEE Transactions on Wireless Communications. IEEE, 2014.
https://doi.org/10.1109/twc.2014.020914.130669.
ieee: M. Mondelli, Q. Zhou, V. Lottici, and X. Ma, “Joint power allocation and path
selection for multi-hop noncoherent decode and forward UWB communications,” IEEE
Transactions on Wireless Communications, vol. 13, no. 3. IEEE, pp. 1397–1409,
2014.
ista: Mondelli M, Zhou Q, Lottici V, Ma X. 2014. Joint power allocation and path
selection for multi-hop noncoherent decode and forward UWB communications. IEEE
Transactions on Wireless Communications. 13(3), 1397–1409.
mla: Mondelli, Marco, et al. “Joint Power Allocation and Path Selection for Multi-Hop
Noncoherent Decode and Forward UWB Communications.” IEEE Transactions on Wireless
Communications, vol. 13, no. 3, IEEE, 2014, pp. 1397–409, doi:10.1109/twc.2014.020914.130669.
short: M. Mondelli, Q. Zhou, V. Lottici, X. Ma, IEEE Transactions on Wireless Communications
13 (2014) 1397–1409.
date_created: 2019-07-31T09:05:07Z
date_published: 2014-03-20T00:00:00Z
date_updated: 2021-01-12T08:08:48Z
day: '20'
doi: 10.1109/twc.2014.020914.130669
extern: '1'
intvolume: ' 13'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 1397-1409
publication: IEEE Transactions on Wireless Communications
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Joint power allocation and path selection for multi-hop noncoherent decode
and forward UWB communications
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2014'
...
---
_id: '6768'
abstract:
- lang: eng
text: The paper presents an algorithm that applies a stack filter simulating the
Mean Curvature Motion equation via a finite difference scheme.
article_type: original
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
citation:
ama: Mondelli M. A finite difference scheme for the stack filter simulating the
MCM. Image Processing On Line. 2013;3:68-111. doi:10.5201/ipol.2013.53
apa: Mondelli, M. (2013). A finite difference scheme for the stack filter simulating
the MCM. Image Processing On Line. Image Processing On Line. https://doi.org/10.5201/ipol.2013.53
chicago: Mondelli, Marco. “A Finite Difference Scheme for the Stack Filter Simulating
the MCM.” Image Processing On Line. Image Processing On Line, 2013. https://doi.org/10.5201/ipol.2013.53.
ieee: M. Mondelli, “A finite difference scheme for the stack filter simulating the
MCM,” Image Processing On Line, vol. 3. Image Processing On Line, pp. 68–111,
2013.
ista: Mondelli M. 2013. A finite difference scheme for the stack filter simulating
the MCM. Image Processing On Line. 3, 68–111.
mla: Mondelli, Marco. “A Finite Difference Scheme for the Stack Filter Simulating
the MCM.” Image Processing On Line, vol. 3, Image Processing On Line, 2013,
pp. 68–111, doi:10.5201/ipol.2013.53.
short: M. Mondelli, Image Processing On Line 3 (2013) 68–111.
date_created: 2019-08-05T12:30:38Z
date_published: 2013-07-11T00:00:00Z
date_updated: 2021-01-12T08:08:56Z
day: '11'
ddc:
- '510'
doi: 10.5201/ipol.2013.53
extern: '1'
file:
- access_level: open_access
checksum: 83b7d429bc248c6c461229d3504fb139
content_type: application/pdf
creator: dernst
date_created: 2019-08-05T12:33:40Z
date_updated: 2020-07-14T12:47:40Z
file_id: '6769'
file_name: 2013_IPOL_Mondelli.pdf
file_size: 4306158
relation: main_file
file_date_updated: 2020-07-14T12:47:40Z
has_accepted_license: '1'
intvolume: ' 3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 68-111
publication: Image Processing On Line
publication_identifier:
issn:
- 2105-1232
publication_status: published
publisher: Image Processing On Line
quality_controlled: '1'
status: public
title: A finite difference scheme for the stack filter simulating the MCM
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3
year: '2013'
...
---
_id: '6746'
abstract:
- lang: eng
text: This paper proposes a novel cooperative approach for two-hop amplify-and-forward
(A&F) relaying that exploits both the signal forwarded by the relay and the one
directly transmitted by the source in impulse-radio ultra-wideband (IR-UWB) systems.
Specifically, we focus on a non-coherent setup employing a double-differential
encoding scheme at the source node and a single differential demodulation at the
relay and destination. The log-likelihood ratio based decision rule is derived
at the destination node. A semi-analytical power allocation strategy is presented
by evaluating a closed-form expression for the effective signal to noise ratio
(SNR) at the destination, which is maximized by exhaustive search. Numerical simulations
show that the proposed system outperforms both the direct transmission with single
differential encoding and the non-cooperative multi-hop approach in different
scenarios.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Qi
full_name: Zhou, Qi
last_name: Zhou
- first_name: Xiaoli
full_name: Ma, Xiaoli
last_name: Ma
- first_name: Vincenzo
full_name: Lottici, Vincenzo
last_name: Lottici
citation:
ama: 'Mondelli M, Zhou Q, Ma X, Lottici V. A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems. In: 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE; 2012:2905-2908.
doi:10.1109/icassp.2012.6288524'
apa: 'Mondelli, M., Zhou, Q., Ma, X., & Lottici, V. (2012). A cooperative approach
for amplify-and-forward differential transmitted reference IR-UWB relay systems.
In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP) (pp. 2905–2908). Kyoto, Japan: IEEE. https://doi.org/10.1109/icassp.2012.6288524'
chicago: Mondelli, Marco, Qi Zhou, Xiaoli Ma, and Vincenzo Lottici. “A Cooperative
Approach for Amplify-and-Forward Differential Transmitted Reference IR-UWB Relay
Systems.” In 2012 IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP), 2905–8. IEEE, 2012. https://doi.org/10.1109/icassp.2012.6288524.
ieee: M. Mondelli, Q. Zhou, X. Ma, and V. Lottici, “A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems,” in 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan,
2012, pp. 2905–2908.
ista: 'Mondelli M, Zhou Q, Ma X, Lottici V. 2012. A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems. 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP). ICASSP: International
Conference on Acoustics, Speech and Signal Processing, 2905–2908.'
mla: Mondelli, Marco, et al. “A Cooperative Approach for Amplify-and-Forward Differential
Transmitted Reference IR-UWB Relay Systems.” 2012 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–08,
doi:10.1109/icassp.2012.6288524.
short: M. Mondelli, Q. Zhou, X. Ma, V. Lottici, in:, 2012 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–2908.
conference:
end_date: 2012-03-30
location: Kyoto, Japan
name: 'ICASSP: International Conference on Acoustics, Speech and Signal Processing'
start_date: 2012-03-25
date_created: 2019-07-31T09:14:48Z
date_published: 2012-07-31T00:00:00Z
date_updated: 2021-01-12T08:08:49Z
day: '31'
doi: 10.1109/icassp.2012.6288524
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 2905-2908
publication: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP)
publication_identifier:
issn:
- 1520-6149
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: A cooperative approach for amplify-and-forward differential transmitted reference
IR-UWB relay systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '6749'
abstract:
- lang: eng
text: This article refers to algorithms based on finite difference schemes for computing
mean and affine curvature evolutions of digital images, introduced by Alvarez
and Morel [L. Alvarez, J.M. Morel, “Formalization and computational aspects of
image analysis”, Acta Numerica, pp. 159, 1994]. We discuss consistency, stability
and convergence. Our analysis focuses on some possible choices of the parameters,
choices that generate multiple variants in the implementations. Meaningful visual
examples on how the algorithms actually work are provided.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Adina
full_name: Ciomaga, Adina
last_name: Ciomaga
citation:
ama: Mondelli M, Ciomaga A. Finite difference schemes for MCM and AMSS. Image
Processing On Line. 2011;1:127-177. doi:10.5201/ipol.2011.cm_fds
apa: Mondelli, M., & Ciomaga, A. (2011). Finite difference schemes for MCM and
AMSS. Image Processing On Line. IPOL Image Processing On Line. https://doi.org/10.5201/ipol.2011.cm_fds
chicago: Mondelli, Marco, and Adina Ciomaga. “Finite Difference Schemes for MCM
and AMSS.” Image Processing On Line. IPOL Image Processing On Line, 2011.
https://doi.org/10.5201/ipol.2011.cm_fds.
ieee: M. Mondelli and A. Ciomaga, “Finite difference schemes for MCM and AMSS,”
Image Processing On Line, vol. 1. IPOL Image Processing On Line, pp. 127–177,
2011.
ista: Mondelli M, Ciomaga A. 2011. Finite difference schemes for MCM and AMSS. Image
Processing On Line. 1, 127–177.
mla: Mondelli, Marco, and Adina Ciomaga. “Finite Difference Schemes for MCM and
AMSS.” Image Processing On Line, vol. 1, IPOL Image Processing On Line,
2011, pp. 127–77, doi:10.5201/ipol.2011.cm_fds.
short: M. Mondelli, A. Ciomaga, Image Processing On Line 1 (2011) 127–177.
date_created: 2019-07-31T09:44:24Z
date_published: 2011-09-13T00:00:00Z
date_updated: 2021-01-12T08:08:50Z
day: '13'
ddc:
- '000'
doi: 10.5201/ipol.2011.cm_fds
extern: '1'
file:
- access_level: open_access
checksum: 910710811224c633202791e0c217d05d
content_type: application/pdf
creator: dernst
date_created: 2019-08-01T06:34:21Z
date_updated: 2020-07-14T12:47:39Z
file_id: '6751'
file_name: 2011_IPOL_Mondelli.pdf
file_size: 2793903
relation: main_file
file_date_updated: 2020-07-14T12:47:39Z
has_accepted_license: '1'
intvolume: ' 1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 127-177
publication: Image Processing On Line
publication_identifier:
issn:
- 2105-1232
publication_status: published
publisher: IPOL Image Processing On Line
quality_controlled: '1'
status: public
title: Finite difference schemes for MCM and AMSS
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1
year: '2011'
...
---
_id: '6767'
abstract:
- lang: eng
text: "In the present paper we give a thorough analysis of two finite difference
schemes for the Mean Curvature Motion and its affine variant, the Affine Morphological
Scale Space, schemes introduced in the Image Processing framework. This analysis
brings in a series of parameters that allow us to compute an accurate discrete
evolution of curvature motions.\r\nThe choice of these parameters is based on
intrinsic geometric properties of the evolution equations for linear, radial and
elliptical functions. In the last part we present several examples, underlining
the main advantages of the algorithms (the removal of pixelization effects and
JPEG artifacts) as well as their major drawbacks (absence of contrast invariance
and grid dependence). A detailed explanatory report, the ANSI C implementations
and an on-line demo can be found at http://www.ipol.im/."
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Adina
full_name: Ciomaga, Adina
last_name: Ciomaga
citation:
ama: 'Mondelli M, Ciomaga A. On finite difference schemes for curvature motions.
In: Proceedings of the International Student Conference on Pure and Applied
Mathematics. Editura Universitãtii „Alexandru Ioan Cuza” Iasi; 2011:137-156.
doi:10.13140/2.1.1862.4646'
apa: 'Mondelli, M., & Ciomaga, A. (2011). On finite difference schemes for curvature
motions. In Proceedings of the International Student Conference on Pure and
Applied Mathematics (pp. 137–156). Iasi, Romania: Editura Universitãtii „Alexandru
Ioan Cuza” Iasi. https://doi.org/10.13140/2.1.1862.4646'
chicago: Mondelli, Marco, and Adina Ciomaga. “On Finite Difference Schemes for Curvature
Motions.” In Proceedings of the International Student Conference on Pure and
Applied Mathematics, 137–56. Editura Universitãtii „Alexandru Ioan Cuza” Iasi,
2011. https://doi.org/10.13140/2.1.1862.4646.
ieee: M. Mondelli and A. Ciomaga, “On finite difference schemes for curvature motions,”
in Proceedings of the International Student Conference on Pure and Applied
Mathematics, Iasi, Romania, 2011, pp. 137–156.
ista: 'Mondelli M, Ciomaga A. 2011. On finite difference schemes for curvature motions.
Proceedings of the International Student Conference on Pure and Applied Mathematics.
ISCOPAM: International Student Conference on Pure and Applied Mathematics, 137–156.'
mla: Mondelli, Marco, and Adina Ciomaga. “On Finite Difference Schemes for Curvature
Motions.” Proceedings of the International Student Conference on Pure and Applied
Mathematics, Editura Universitãtii „Alexandru Ioan Cuza” Iasi, 2011, pp. 137–56,
doi:10.13140/2.1.1862.4646.
short: M. Mondelli, A. Ciomaga, in:, Proceedings of the International Student Conference
on Pure and Applied Mathematics, Editura Universitãtii „Alexandru Ioan Cuza” Iasi,
2011, pp. 137–156.
conference:
end_date: 2010-07-16
location: Iasi, Romania
name: 'ISCOPAM: International Student Conference on Pure and Applied Mathematics'
start_date: 2010-07-12
date_created: 2019-08-05T12:20:58Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T08:08:56Z
day: '01'
doi: 10.13140/2.1.1862.4646
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 137-156
publication: Proceedings of the International Student Conference on Pure and Applied
Mathematics
publication_identifier:
isbn:
- 978-973-703-602-5
publication_status: published
publisher: Editura Universitãtii „Alexandru Ioan Cuza” Iasi
quality_controlled: '1'
status: public
title: On finite difference schemes for curvature motions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...