Dimension-Free Correlated Sampling for the Hypersimplex
Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, David Wajc · 2025
Read Dimension-Free Correlated Sampling for the Hypersimplex by Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, David Wajc (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13573.txt.
Introduction
Joseph Naor and five co-authors improve correlated sampling for the hypersimplex, a tool that lets separate parties draw sets that overlap as much as possible. Correlated sampling from the simplex has served theoretical computer science since the two thousands as a shared building block. The hypersimplex version asks for sets of bounded size whose expected gap stays within a factor of the input distance.
Earlier work reached a factor that grows with the full ambient dimension. The new algorithm brings that factor down to one that grows only with the set size, removing the dimension from the bound. It also samples fast on sparse inputs and supports quick updates. Uses include online paging, metric multi-labeling, and welfare reallocation problems.
Catalog record
| CREATOR | Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, David Wajc |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13573
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dimension-Free Correlated Sampling for the Hypersimplex Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, David Wajc Abstract 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 k in [ n ] [n] , while maximizing the sampled sets’ overlap. Specifically, the expected difference between two output sets should be at most α \alpha times their input vectors’ ℓ 1 \ell_{1} distance. A value of α = O ( log n ) \alpha=O(\log n) is known to be achievable, due to Chen et al. (ICALP’17). We improve this factor to O ( log k ) O(\log k) , independent of the ambient dimension n n . Our algorithm satisfies other desirable properties, including (up to a log ∗ n \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. 1 Introduction Consider the following natural correlated sampling problem: we wish to sample from numerous discrete distributions over [n] , or equivalently round numerous points in the n -dimensional probability simplex, \Delta_{n}\triangleq\{\mathbf{x}\in[0,1]^{n}\mathrel{\mathop{\mathchar 58\relax}}~\mathinner{\!\left\lVert\mathbf{x}\right\rVert}_{1}=1\} , in a consistent manner . In particular, for any two distributions with low total variation distance, i.e., points in \Delta_{n} with low \ell_{1} distance, \mathinner{\!\left\lVert\mathbf{x}-\mathbf{y}\right\rVert}_{1}\triangleq\sum_{i}|x_{i}-y_{i}| , we wish the sets drawn according to these points to be similar in expectation. This problem is well-understood [ 31 , 27 , 26 , 9 , 2 , 5 ] . Moreover, efficient correlated sampling algorithms have found numerous applications to disparate areas of computation, from approximation algorithms [ 31 , 26 , 9 , 40 ] , parallel repetition [ 27 , 4 ] , replicability and privacy [ 3 , 11 ] , parallel sampling [ 34 , 1 ] , cryptography [ 39 ] , locality sensitive hashing [ 7 , 14 ] , and more. Such correlated sampling is a special case of what statisticians refer to as coordinated sampling , and have been studying since the 1950s [ 29 ] . Here, the motivation of maximizing overlap is in minimizing overhead of initiation interviews for newly sampled interviewees or overhead of hiring new interviewers for new regions with sampled interviewees. Such rationale was used and adopted, for example in the U.S. Bureau of the Census household surveys. See discussion of such applications and nearly half a century of work on such questions in the survey by Ernst [ 23 ] . In this work we study the following correlated sampling problem, introduced by [ 16 ] , generalizing from the probability simplex to the convex hull of the hypersimplex and the origin, i.e., the polytope whose extreme points are vectors in \{0,1\}^{n} with at most k ones, \Delta_{n,k}\triangleq\{\mathbf{x}\in[0,1]^{n}\mathrel{\mathop{\mathchar 58\relax}}~\mathinner{\!\left\lVert\mathbf{x}\right\rVert}_{1}\leq k\}. We wish to round points in this set while preserving marginals, respecting the cardinality constraint of k , and guaranteeing that the expected distance of the output sets for any two points \mathbf{x},\mathbf{y}\in\Delta_{n,k} is bounded in terms of the points’ \ell_{1} distance. Formally, we study the following problem. Definition 1.1 . A distribution \mathcal{D} over deterministic algorithms \mathcal{A}\mathrel{\mathop{\mathchar 58\relax}}\Delta_{n,k}\to 2^{[n]} mapping points in \Delta_{n,k} to subsets of [n] of cardinality at most k is an \bm{\alpha} -stretch correlated sampling algorithm for \bm{\Delta_{n,k}} if it satisfies the following properties for all \mathbf{x},\mathbf{y}\in\Delta_{n,k} : (P1) (Cardinality) |\mathcal{A}(\mathbf{x})|\in\left\{\lfloor\|\mathbf{x}\|_{1}\rfloor,\lceil\|\mathbf{x}\|_{1}\rceil\right\} (hence |\mathcal{A}(\mathbf{x})|\leq k ) for all \mathcal{A} in the support of \mathcal{D} . (P2) (Marginals) \mathds{P}r_{\mathcal{A}\sim\mathcal{D}}[i\in\mathcal{A}(\mathbf{x})]=x_{i} for all i\in[n] . (P3) (Stretch) \mathbb{E}_{\mathcal{A}\sim\mathcal{D}}[\;|\mathcal{A}(\mathbf{x})\oplus\mathcal{A}(\mathbf{y})|\;]\leq\alpha\cdot\mathinner{\!\left\lVert\mathbf{x}-\mathbf{y}\right\rVert}_{1} . To clarify Property (P3) and its use: after a common initialization step where we draw an algorithm \mathcal{A}\sim\mathcal{D} , we guarantee that when rounding any two vectors \mathbf{x},\mathbf{y}\in\Delta_{n,k} , the output’s expected distance (over the random choice of \mathcal{A} ) is at most the vectors’ \ell_{1} distance times some \alpha . Naturally, we wish to keep \alpha as small as possible. For k=1 it is known that \alpha must be at least two [ 2 , 5 ] , 1 1 1 More precisely, some \mathbf{x},\mathbf{y} must have stretch at least 2/(1+\delta) , for \delta\triangleq\frac{1}{2}\mathinner{\!\left\lVert\mathbf{x}-\mathbf{y}\right\rVert}_{1} , though \delta may tend to zero. and this bound is attainable, provided \mathinner{\!\left\lVert x\right\rVert}_{1}=k=1 , i.e., for \Delta_{n}\subsetneq\Delta_{n,1} [ 31 , 27 , 26 , 9 , 2 , 34 ] . (As we show in Appendix B , a constant bound of \alpha=3 for \Delta_{n,1} more generally follows from the bound for \Delta_{n} .) For k>1 , in contrast, [ 16 ] show that an O(\log n) stretch is achievable, and use it for applications to metric multi-labelling, which we define later. The stark difference between the case k=1 and larger k>1 should be apparent. The natural question, which we study, is whether this logarithmic in n stretch is inherent to the problem. 1.1 Our Contribution Our main contribution is a correlated sampling algorithm for the hypersimplex with k>1 with stretch logarithmic in k , but independent of the input dimension, n . Theorem 1.2 . There exists an O(\log k) -stretch correlated sampling algorithm for \Delta_{n,k} for all n . Our algorithm is extremely fast, and can be implemented in O(nnz\cdot\log^{*}n) time, for nnz\leq n the number of nonzeros and \log^{*}n the (extremely slowly-growing) iterated logarithm function (see 2.1 ). Thus, the algorithm’s running time is also very nearly linear in the input sparsity, and dimension independent. Our algorithm can further be implemented in O(\log n\cdot\log^{*}n) parallel depth and O(\log(nnz)\cdot\log^{*}n) update time in dynamic settings. Property (P2) immediately implies preservation of linear objectives. We also prove that our algorithm preserves submodular objectives. (See Section 3.4 for some background, but for now suffice it to say that these functions capture the ubiquitous phenomenon of diminishing returns.) In particular, we prove that our correlated sampling algorithm’s output has at least as high a submodular value as independent rounding with marginals \mathbf{x} (the so-called multilinear extension ), while being oblivious to the objective submodular function, and also satisfying the cardinality constraint and desired low stretch guarantees. In Appendix C we extend this property to correlated sampling for partition matroids , where the ground set is partitioned into parts, with a cardinality constraint on each part. Due to the widespread uses of correlated sampling for the probability simplex, we anticipate numerous subsequent applications of our correlated sampling algorithm for the hypersimplex. To illustrate this, we provide several simple applications of our algorithm, to online paging, offline metric multi-labeling, and dynamic submodular welfare maximizing reallocation. As these applications only illustrate the variety of (potential) applications of our correlated sampling for the hypersimplex, we defer their description to Section 4 . However, for our last application, we note that our dimension-free stretch hints at further applications: combining it with a simple rounding algorithm for the case that k is large, we