---
_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
arxiv: 1
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: <i>Proceedings of 2023 IEEE International Symposium on Information
    Theory</i>. IEEE; 2023:400-405. doi:<a href="https://doi.org/10.1109/isit54713.2023.10206899">10.1109/isit54713.2023.10206899</a>'
  apa: 'Esposito, A. R., &#38; Mondelli, M. (2023). Concentration without independence
    via information measures. In <i>Proceedings of 2023 IEEE International Symposium
    on Information Theory</i> (pp. 400–405). Taipei, Taiwan: IEEE. <a href="https://doi.org/10.1109/isit54713.2023.10206899">https://doi.org/10.1109/isit54713.2023.10206899</a>'
  chicago: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
    via Information Measures.” In <i>Proceedings of 2023 IEEE International Symposium
    on Information Theory</i>, 400–405. IEEE, 2023. <a href="https://doi.org/10.1109/isit54713.2023.10206899">https://doi.org/10.1109/isit54713.2023.10206899</a>.
  ieee: A. R. Esposito and M. Mondelli, “Concentration without independence via information
    measures,” in <i>Proceedings of 2023 IEEE International Symposium on Information
    Theory</i>, Taipei, Taiwan, 2023, pp. 400–405.
  ista: 'Esposito AR, Mondelli M. 2023. Concentration without independence via information
    measures. Proceedings of 2023 IEEE International Symposium on Information Theory.
    ISIT: International Symposium on Information Theory, 400–405.'
  mla: Esposito, Amedeo Roberto, and Marco Mondelli. “Concentration without Independence
    via Information Measures.” <i>Proceedings of 2023 IEEE International Symposium
    on Information Theory</i>, IEEE, 2023, pp. 400–05, doi:<a href="https://doi.org/10.1109/isit54713.2023.10206899">10.1109/isit54713.2023.10206899</a>.
  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: International Symposium on Information Theory'
  start_date: 2023-06-25
corr_author: '1'
date_created: 2024-02-02T11:18:40Z
date_published: 2023-06-30T00:00:00Z
date_updated: 2025-09-04T13:06:52Z
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
scopus_import: '1'
status: public
title: Concentration without independence via information measures
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
arxiv: 1
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: <i>Proceedings
    of 2023 IEEE International Symposium on Information Theory</i>. IEEE; 2023:1178-1183.
    doi:<a href="https://doi.org/10.1109/isit54713.2023.10206671">10.1109/isit54713.2023.10206671</a>'
  apa: 'Fu, T., Liu, Y., Barbier, J., Mondelli, M., Liang, S., &#38; Hou, T. (2023).
    Mismatched estimation of non-symmetric rank-one matrices corrupted by structured
    noise. In <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>
    (pp. 1178–1183). Taipei, Taiwan: IEEE. <a href="https://doi.org/10.1109/isit54713.2023.10206671">https://doi.org/10.1109/isit54713.2023.10206671</a>'
  chicago: Fu, Teng, YuHao Liu, Jean Barbier, Marco Mondelli, ShanSuo Liang, and TianQi
    Hou. “Mismatched Estimation of Non-Symmetric Rank-One Matrices Corrupted by Structured
    Noise.” In <i>Proceedings of 2023 IEEE International Symposium on Information
    Theory</i>, 1178–83. IEEE, 2023. <a href="https://doi.org/10.1109/isit54713.2023.10206671">https://doi.org/10.1109/isit54713.2023.10206671</a>.
  ieee: T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, and T. Hou, “Mismatched
    estimation of non-symmetric rank-one matrices corrupted by structured noise,”
    in <i>Proceedings of 2023 IEEE International Symposium on Information Theory</i>,
    Taipei, Taiwan, 2023, pp. 1178–1183.
  ista: 'Fu T, Liu Y, Barbier J, Mondelli M, Liang S, Hou T. 2023. Mismatched estimation
    of non-symmetric rank-one matrices corrupted by structured noise. Proceedings
    of 2023 IEEE International Symposium on Information Theory. ISIT: International
    Symposium on Information Theory, 1178–1183.'
  mla: Fu, Teng, et al. “Mismatched Estimation of Non-Symmetric Rank-One Matrices
    Corrupted by Structured Noise.” <i>Proceedings of 2023 IEEE International Symposium
    on Information Theory</i>, IEEE, 2023, pp. 1178–83, doi:<a href="https://doi.org/10.1109/isit54713.2023.10206671">10.1109/isit54713.2023.10206671</a>.
  short: T. Fu, Y. Liu, J. Barbier, M. Mondelli, S. Liang, T. Hou, in:, Proceedings
    of 2023 IEEE International Symposium on Information Theory, IEEE, 2023, pp. 1178–1183.
conference:
  end_date: 2023-06-30
  location: Taipei, Taiwan
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2023-06-25
corr_author: '1'
date_created: 2024-02-02T11:20:39Z
date_published: 2023-06-30T00:00:00Z
date_updated: 2025-07-10T11:51:04Z
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
page: 1178-1183
publication: Proceedings of 2023 IEEE International Symposium on Information Theory
publication_identifier:
  eissn:
  - 2157-8117
  isbn:
  - '9781665475549'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '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: '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.'
arxiv: 1
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: <i>2018 IEEE International Symposium on Information Theory</i>.
    IEEE; 2018:351-355. doi:<a href="https://doi.org/10.1109/isit.2018.8437479">10.1109/isit.2018.8437479</a>'
  apa: 'Mondelli, M., Hassani, H., &#38; Urbanke, R. (2018). A new coding paradigm
    for the primitive relay channel. In <i>2018 IEEE International Symposium on Information
    Theory</i> (pp. 351–355). Vail, CO, United States: IEEE. <a href="https://doi.org/10.1109/isit.2018.8437479">https://doi.org/10.1109/isit.2018.8437479</a>'
  chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “A New Coding Paradigm
    for the Primitive Relay Channel.” In <i>2018 IEEE International Symposium on Information
    Theory</i>, 351–55. IEEE, 2018. <a href="https://doi.org/10.1109/isit.2018.8437479">https://doi.org/10.1109/isit.2018.8437479</a>.
  ieee: M. Mondelli, H. Hassani, and R. Urbanke, “A new coding paradigm for the primitive
    relay channel,” in <i>2018 IEEE International Symposium on Information Theory</i>,
    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.”
    <i>2018 IEEE International Symposium on Information Theory</i>, IEEE, 2018, pp.
    351–55, doi:<a href="https://doi.org/10.1109/isit.2018.8437479">10.1109/isit.2018.8437479</a>.
  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: 2024-10-09T20:59:04Z
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: '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.
arxiv: 1
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: <i>2017 IEEE International Symposium on Information Theory </i>.
    IEEE; 2017:1853-1857. doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>'
  apa: 'Mondelli, M., Hassani, S. H., &#38; Urbanke, R. (2017). Construction of polar
    codes with sublinear complexity. In <i>2017 IEEE International Symposium on Information
    Theory </i> (pp. 1853–1857). Aachen, Germany: IEEE. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>'
  chicago: Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of
    Polar Codes with Sublinear Complexity.” In <i>2017 IEEE International Symposium
    on Information Theory </i>, 1853–57. IEEE, 2017. <a href="https://doi.org/10.1109/isit.2017.8006850">https://doi.org/10.1109/isit.2017.8006850</a>.
  ieee: M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with
    sublinear complexity,” in <i>2017 IEEE International Symposium on Information
    Theory </i>, 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.”
    <i>2017 IEEE International Symposium on Information Theory </i>, IEEE, 2017, pp.
    1853–57, doi:<a href="https://doi.org/10.1109/isit.2017.8006850">10.1109/isit.2017.8006850</a>.
  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'
...