Dimension-Free Correlated Sampling for the Hypersimplex
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918206290001920 |
|---|---|
| author | Joseph Naor Raju, Nitya Shetty, Abhishek Srinivasan, Aravind Valieva, Renata Wajc, David |
| author_facet | Joseph Naor Raju, Nitya Shetty, Abhishek Srinivasan, Aravind Valieva, Renata Wajc, David |
| contents | Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) some $k$ in $[n]$, while maximizing the sampled sets' overlap. Specifically, the expected difference between two output sets should be at most $α$ times their input vectors' $\ell_1$ distance. A value of $α=O(\log n)$ is known to be achievable, due to Chen et al.~(ICALP'17). We improve this factor to $O(\log k)$, independent of the ambient dimension~$n$. Our algorithm satisfies other desirable properties, including (up to a $\log^* n$ factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling and swift multi-scenario submodular welfare approximating reallocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13573 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dimension-Free Correlated Sampling for the Hypersimplex Joseph Naor Raju, Nitya Shetty, Abhishek Srinivasan, Aravind Valieva, Renata Wajc, David Data Structures and Algorithms Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) some $k$ in $[n]$, while maximizing the sampled sets' overlap. Specifically, the expected difference between two output sets should be at most $α$ times their input vectors' $\ell_1$ distance. A value of $α=O(\log n)$ is known to be achievable, due to Chen et al.~(ICALP'17). We improve this factor to $O(\log k)$, independent of the ambient dimension~$n$. Our algorithm satisfies other desirable properties, including (up to a $\log^* n$ factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling and swift multi-scenario submodular welfare approximating reallocation. |
| title | Dimension-Free Correlated Sampling for the Hypersimplex |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.13573 |