License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.18
URN: urn:nbn:de:0030-drops-173037
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17303/
Go to the corresponding LIPIcs Volume Portal

Skorski, Maciej

Entropy Matters: Understanding Performance of Sparse Random Embeddings

pdf-format:
LIPIcs-ISAAC-2022-18.pdf (0.7 MB)

Abstract

This work shows how the performance of sparse random embeddings depends on the Renyi entropy-like property of data, improving upon recent works from NIPS'18 and NIPS'19.
While the prior works relied on involved combinatorics, the novel approach is simpler and modular. As the building blocks, it develops the following probabilistic facts of general interest:
b) a comparison inequality between the linear and quadratic chaos
c) a comparison inequality between heterogenic and homogenic linear chaos
d) a simpler proof of Latala’s strong result on estimating distributions of IID sums
e) sharp bounds for binomial moments in all parameter regimes.

BibTeX - Entry

@InProceedings{skorski:LIPIcs.ISAAC.2022.18,
  author =	{Skorski, Maciej},
  title =	{{Entropy Matters: Understanding Performance of Sparse Random Embeddings}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17303},
  URN =		{urn:nbn:de:0030-drops-173037},
  doi =		{10.4230/LIPIcs.ISAAC.2022.18},
  annote =	{Keywords: Random Embeddings, Sparse Projections, Renyi Entropy}
}

Keywords: Random Embeddings, Sparse Projections, Renyi Entropy
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI