Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma

Authors: jason vander woude
peter  dixon
a  pavan
jamie  radcliffe
n v vinodchandran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:09:27

Abstract: This paper studies replicability in machine learning tasks from a geometric viewpoint. Recent works have revealed the role of geometric partitions and  Sperner's lemma (and its variations) in designing replicable learning algorithms and in establishing impossibility results.  

A partition $\mathcal{P}$ of $\mathbb{R}^d$ is called a $(k,\epsilon)$-secluded partition if for every $\vec{p}\in\mathbb{R}^d$, an $\varepsilon$-radius ball (with respect to the $\ell_{\infty}$ norm) centered at $\vec{p}$ intersects at most $k$ members of $\mathcal{P}$.  In relation to replicable learning, the parameter $k$ is closely related to the $\textit{list complexity}$, and the parameter $\varepsilon$ is related to the sample complexity of the replicable learner. Construction of secluded partitions with better parameters (small $k$ and large $\varepsilon$) will lead to replicable learning algorithms with small list and sample complexities. 

Motivated by this connection, we undertake a comprehensive study of secluded partitions and establish near-optimal relationships between $k$ and $\varepsilon$. 

1.  We show that for any $(k,\epsilon)$-secluded partition where each member has at most unit measure, it must be that $k \geq(1+2\varepsilon)^d$, and consequently, for the interesting regime $k\in[2^d]$ it must be that $\epsilon\leq\frac{\log_4(k)}{d}$. 

2. To complement this upper bound on $\epsilon$, we show that for each $d\in\mathbb{N}$ and each viable $k\in[2^d]$, a construction of a $(k,\epsilon)$-secluded (unit cube) partition with $\epsilon\geq\frac{\log_4(k)}{d}\cdot\frac{1}{8\log_4(d+1)}$. This establishes the optimality of $\epsilon$ within a logarithmic factor.

3.  Finally, we adapt our proof techniques to obtain a new ``neighborhood'' variant of the cubical KKM lemma (or cubical Sperner's lemma): For any coloring of $[0,1]^d$ in which no color is used on opposing faces, it holds for each $\epsilon\in(0,\frac12]$ that there is a point where the open $\epsilon$-radius $\ell_\infty$-ball intersects at least $(1+\frac23\epsilon)^d$ colors. While the classical Sperner/KKM lemma guarantees the existence of a point that is "adjacent" to points with $(d+1)$ distinct colors, the neighborhood version guarantees the existence of a small neighborhood with  exponentially many points with distinct colors.

Main paper: 
 introduction: 
 Can we design learning algorithms that are replicable? Typically, learning algorithms observe samples from an unknown distribution and output a hypothesis. Since different runs of a learning algorithm may observe different samples, the algorithm may output different hypotheses on different runs, making standard learning algorithms non-replicable. Several recent works have been investigating various notions of replicability in learning algorithms. Intuitively, a replicable learning algorithm should output the same canonical hypothesis, on multiple runs (with high probability). However, it has been observed that such an ideal notion of replicability may not be achievable even in simple learning tasks such as learning one-dimensional thresholds. This led to relaxed definitions of replicability including ρ-replicability [31] , stability [10] , global-stability [24] , and list-replicability [17] .A significant insight that emerged form these works is the profound connection between geometry and algorithmic replicability [17, 13, 31, 12] . These works use geometric partitions to design replicable algorithms and employ (variants of) Sperner/KKM lemma, including Poincare-Miranda and Borsuk-Ulam theorems, to obtain lower bound results. In particular, in [17] , the authors use the notion of secluded partitions of R d [44] to design replicable learning algorithms with small list complexity. The works of [13, 12, 17] used Sperner/KKM, Poincare-Miranda and Borsuk-Ulam theorems to obtain lower bounds on list complexity and stability parameters for various learning tasks.Motivated by these connections we undertake an in-depth investigation into secluded partitions. Our first contribution is a comprehensive understanding of the optimality of secluded partition constructions. Our second contribution is the discovery of a new neighborhood variant of the Sperner/KKM lemma.Secluded partitions have found applications beyond replicable learning including deterministic rounding, pseudodeterministic algorithms, and quantum computaion [44, 7] . Moreover, the notion of secluded partitions is simple and natural and is rooted in the works of Lebesgue and Brouwer [36, 8] . Thus, our investigation of secluded partitions should be seen as a fundamental endeavor.The applicability of the Sperner/KKM lemma, and other equivalent results such as Brouwer's fixed point theorem, the Poincaré-Miranda theorem, and the Lebesgue covering theorem is not just limited to the area of replicable algorithms. These lemmas and their variants have found numerous applications in various contexts: distributed and parallel computing [2, 4, 39, 28, 42, 6] , communication complexity [21, 11] , computational complexity [25, 35, 40, 16] , algorithmic game theory [14, 15] , and fair-division [37, 38, 5] . We expect that the neighborhood variant we established will also be useful in computer science applications. 
preliminaries: 
 A learning algorithm is k-list replicable if the output of the learning algorithm belongs to a list L consisting of at most k good hypotheses with high probability. Below is a more formal definition from [17] .Let X be a domain over which a family of distributions D are defined, let H be a set (representing hypotheses), and err : D × H → [0, ∞) be an error function. A learning algorithm on input ε, δ observes m samples from a distribution D ∈ D and learns a hypothesis h ∈ H with a small error err(D, h) ≤ ε. Definition 2.1 (List Replicability). Let k ∈ N, ε ∈ (0, ∞), and δ ∈ [0, 1]. A learning algorithm A is (k, ε, δ)-list replicable if there exists n ∈ N such that for every D ∈ D, there exists a list L ⊆ H of size at most k such that for all h ∈ L, err(D, h) ≤ ε, andPr s∼D n [A(s, ε, δ) ∈ L] ≥ 1 -δ.For k ∈ N, we call A k-list replicable if for all ε ∈ (0, ∞) and δ ∈ (0, 1], A is (k, ε, δ)-list replicable. We say that n is the sample complexity of A and k is the list complexity of A.The above definition captures the ideas over multiple runs of the learning algorithm, we may see at most k different hypotheses. Note that the ideal scenario is when k = 1. A generic goal is to design list replicable algorithms with small list and sample complexities. The work of [17] designed list-replicable algorithms for various learning tasks including a general theorem that any concept class that is learnable with k non-adaptive statistical queries has a k + 1-list replicable algorithm.A key ingredient in their list replicable algorithms is the geometric notion of secluded partitions that we define next. Given a point ⃗ p ∈ R d , let B ∞ (ε, ⃗ p) (B • ∞ (ε, ⃗ p)) denote the closed (respectively, open) ε-ball around ⃗ p in the ℓ ∞ norm.). A partition P of R d is called a (k, ε)-secluded partition if for every ⃗ p ∈ R d , the ball B ∞ (ε, ⃗ p) intersects at most k members of P. The parameters k and ε are called the degree and tolerance respectively. Remark. To avoid trivial partitions where each point is a partition member or the entire R d is a single partition member, all the partitions considered in this work have non-zero, bounded measure partition members.It is easy to see that the standard grid partition of R d with unit cubes is (2 d , 1 2 )-secluded. The following result [44, 30] improves the degree parameter substantially. Theorem 2.3. There is a (d + 1, 1 2d )-secluded partition where each partition member is a unit cube. Sperner/KKM Lemma, Poincaré-Miranda Theorem, and Borsuk-Ulam Theorem can be viewed as fixed point theorems and are known to be equivalent to each other (in the sense that any of these theorems can be derived from the other theorem). We state the Sperner/KKM Lemma below. First we introduce the necessary definitions and notation.Recall that a d-dimensional cube is the set [0, 1] d . For a set of colors C, a coloring is a mapping χ : [0, 1] d → C. For a color c ∈ C, let X c denote the set of points assigned color c by χ. That is, X c = χ -1 (c). A coloring χ is a Sperner/KKM coloring if no two points from opposite faces of the cube gets the same color. That is, for every c ∈ C the set X c has the property that for each coordinate i ∈ [d], the projection π i (X c ) = {x i : ⃗ x ∈ X c } does not contain both 0 and 1.Theorem 2.4 (Sperner/KKM). Given a valid Sperner/KKM coloring of [0, 1] d by finitely many colors, there exists a point in the closure of at least d + 1 different colors.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [NA] .Justification: This is a theoretical paper. The open problems and future research directions are discussed.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
our contributions: 
 This section provides an overview of the results established in this work.Secluded Partitions and replicability. The relationship between replicability and partitions can be best abstracted by considering d-coin bias estimation problem [17] : given d coins with unknown biases, estimate the biases of each coin within an additive error of ν. The work of [17] showed that a (k, ε)-partition of R d yields a k-list replicable algorithm for this task. They used a known construction of (d + 1, 1 2d )-secluded partition of R d from Theorem 2.3to obtain a d + 1-list replicable algorithm for this task. However, there is a cost to replicability. The sample complexity of the replicable algorithm blows up by a factor of O(d 2 ) (compared to the sample complexity of the non-replicable algorithm). In general a (k, ε)-secluded partition gives rise to a k-list replicable algorithm whose sample complexity blows up by a factor of O( 1 ε 2 ) (compared to the "non-replicable" algorithms). Thus constructions of secluded partitions with low-degree (k) and high tolerance (ε), will lead to list replicable algorithms with low list and sample complexities. It is also known that the degree parameter k must be at least d + 1 [44] . This leads to the following fundamental questions: Can we design secluded partitions that substantially improve the tolerance with little or no degradation of the degree? For example, consider the (d + 1, 1 2d )-secluded partition from Theorem 2.3. Can we improve this and construct a (d + 1, ω( 1 d ))-secluded partition? Or can we loosen the degree requirement fromk = d + 1 to k ∈ poly(d) in favor of improving the tolerance from ε ∈ Θ( 1 d ) to ε ∈ ω( 1 d )?Our first contribution is the following upper bound result on the tolerance parameter. Theorem 3.1. Let d ∈ N, ε ∈ [0, ∞), and P a partition of R d such that every member has outer Lebesgue measure at most 1. Then there exists some ⃗p ∈ R d such that B • ∞ (ε, ⃗ p) intersects at least (1 + 2ε) d members of P. Thus, if P is a (k, ε)-secluded partition, then k ≥ (1 + 2ε) d . Consequently, if k ≤ 2 d , then it must be that ε ≤ log 4 (k) d .This result shows that even if one relaxes k ∈ poly(d), ε ∈ O( log d d ). This shows that the (d + 1, 1 2d )secluded partition construction is near optimal in terms of the tolerance parameter, for degree d + 1. Stated in terms of replicability, this result implies one can not hope to design list-replicable algorithms with improved sample complexity using a secluded partitions approach.Our second result is a construction of secluded partitions for various choices of the degree parameter k with tolerance parameter ε almost matching the bound from Theorem 3.1. Until this work, we knew of secluded partitions for only two choices of the degree parameter k: the standard grid partition ofR d that is (2 d , 12 )-secluded and the (d + 1, 1 2d ) partition from Theorem 2.3. We did not know secluded partition constructions for other choices of k. Our second main contribution is the construction of near-optimal secluded partitions for all choices of k.Theorem 3.2. Let d ∈ N and k ∈ [2 d ] \ [d].Then there exists a (k, ε)-secluded unit cube partition ofR d with ε ≥ log 4 (k)8d log 4 (d+1) .Note that by Theorem 3.1, ε ≤ log 4 k d and the above construction achieves ε ≥ log 4 (k) 8d log 4 (d+1) . Thus this construction is optimal up to log factors. As a corollary of this construction, we obtain a smooth tradeoff between list and sample complexities for the problem of estimating the bias of d-coins Corollary 3.3. For the d-coin bias estimation problem, there exists a k-list replicable algorithm with sample complexity Õ(d 2 log 2 d ν 2 log 2 k ), for any k ∈ [2 d ] \ [d], per coin.For example, if we allow k = 2 √ d , then the sample complexity is Õ( d ν 2 ), per coin.Sperner/KKM Lemma and replicability. While the geometric tool of secluded partitions has been used to design list replicable algorithms, interestingly works that establish lower bounds on the list complexity of replicable algorithms [17, 13, 12] employ geometric/topological tools such as Sperner/KKM Lemma, Poincaré-Miranda Theorem, and Borsuk-Ulam Theorem. For example, the work [17] used Sperner/KKM lemma to establish a lower bound of d + 1 on the list complexity for the problem of estimating the bias of d coins as well as for the d-dimensional threshold learning problem. The work of [13] used Poincaré-Miranda Theorem to establish a lower bound on the list complexity of classes with VC-Dimension d. As our third contribution, we generalize the Sperner/KKM Lemma and obtain a neighborhood variant. Theorem 3.4 (Neighborhood Sperner/KKM Lemma). Given a Sperner/KKM coloring of [0, 1] d , for any ε ∈ (0, 1 2 ], there exists a point⃗ p ∈ [0, 1] d such that B • ∞ (ε, ⃗ p) contains at least 1 + 2 3 ε d points with distinct colors.Sperner/KKM Lemma(Lemma 2.4) states that in valid coloring of the d-dimensional hypercube, there is a point ⃗ p whose closure has at least d + 1 colors. That is, for every ε > 0, the ε-ball around ⃗ p intersects at least d + 1 colors. Our theorem is a quantitative generalization of this result. It states that the ε-ball around ⃗ p intersects exponentially many colors-at least (1 + 2 3 ε) d many colors.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
related work: 
 One of the first works that studied replicability in the context of learning algorithms is the seminal work of Bun, Livny, and Moran [10] ; they used the term global stability to capture this notion. A learning algorithm A to be (n, η)-globally stable with respect to a distribution D if there is a hypothesis h such that Pr S∼D n (A(S) = h) ≥ η, here η is called the stability parameter. They used the notion of stability, combined with the work of [3] , to obtain the equivalence between online learnability and differentially private PAC learnability. Ghazi, Kumar and Manurangsi [24] generalized the notion of stability to pseudo-global stability and list-global stability. Impagliazzo, Lei, Pitassi, and Sorrell [31] introduced the notion of ρ-replicabililty and designed replicable algorithms for various learning tasks. One of their replicable algorithms uses a partition/tiling known as "foams tiling" [34] . Dixon, Pavan, Vander Woude and Vinodchandran [17] studied the notions of list replicability and certificate replicability as a measure of the degree of (non)-replicability. Chase, Moran and Yehudayof [13] related the notions list complexity and stability. They established that a learning task has list complexity k if and only if its stability parameter is 1/k. They also established lower bounds the list-complexity (upper bound on the stability) on the PAC-learnability of classes with bounded VC-dimension. In [12] , the authors use Borsuk-Ulam theorem to establish impossibility results for replicable agnostic PAC learning.In the context of randomized algorithms, the notion of replicability is studied under the terminology pseudodeterminism. This notion was introduced by Gat and Goldwasser [23] and has been extended to notions called multi-pseudodeterminism [26] and influential-bit algorithms [27] . The study of replicability in the context of learning has been receiving growing attention over the past few years and researchers have been investigating this notion under various scenarios. The notion of replicability in the context of stochastic bandits and reinforcement learning has been studied in [19, 33, 18] , and the work of [1] studies replicability for optimization problems. Other very recent works include those reported in [9, 29, 32] . A notion that is related to replicability is that of reproducibility. The article by [41] distinguishes these two notions. 
proof sketches of main results: 
 The main technical tools that we use come from measure theory and the geometry of numbers and include generalized Brunn-Minkowski Inequality and ideas from the standard proof of Blichfeldt's theorem. The generalized Brunn-Minkowski inequality gives a lower bound on the measure of a Minkowski sum of sets (A + B = ⃗ a + ⃗ b : ⃗ a ∈ A, ⃗ b ∈ B ) basedm(A + B) ≥ m(A) 1 d + m(B) 1 d d .A common technique in the proof of Blichfeldt's theorem is to use an averaging argument to show that if a set A is covered by a large family of other sets, then some point in A is covered many times.We present the high-level ideas and the intuition behind the proof of Theorem 3.1. In the appendix, we provide a complete proof. Figure 1 serves as a visual.The goal is to find some point ⃗ p ∈ R d such that B • ∞ (ε, ⃗ p) intersects at least (1 + 2ε) d members of the partition. Instead of directly trying to establish this, we take a critical change of perspective: for any ⃗ p ∈ R d and X ∈ P (or really anyX ⊆ R d ), it holds that B • ∞ (ε, ⃗ p) ∩ X ̸ = ∅ if and only if ⃗ p ∈ ⃗ x∈X B • ∞ (ε, ⃗ x).Thus, what we do is to "replace" every member X of the partition with the enlarged set ⃗ x∈X B • ∞ (ε, ⃗ x) and try to find a point ⃗ p that belongs to at least (1 + 2ε) d of these enlarged sets. To achieve this, we take inspiration from a common proof of Blichfeldt's theoremspecifically, the following result which says that if we have a collection of sets A 1 , A 2 , A 3 , . . . which are subsets of another set S, then there is a point in S occurring in multiple A i s provided together the A i s have enough volume/measure. We can in fact give a lower bound on the number of A i s to which such a point belongs to. The following is the formal claim of this known result. . Then if k < ∞, there exists ⃗ p ∈ S such that ⃗ p belongs to at least k members of A. (And if k = ∞, then for any n ∈ N there exists ⃗ p (n) ∈ S such that ⃗ p (n) belongs to at least n members of A.)There is an immediate issue we have to deal with to be able to use Proposition 5.1 for our application. We would like to take A to be the indexed collection of enlarged partition members:A = ⃗ x∈X B • ∞ (ε, ⃗ x) X∈P, but then all we know is that each of these is a subset of S = R d which is not bounded. This is a simple enough issue to deal with using a standard measure theory technique of considering instead a sequence S 1 , S 2 , S 3 , . . . of sets which are bounded and get larger and larger so that ∞ n=1 S n = R d ; we work with each of these sets individually and then try to use a limiting argument to pass the result back to S = R d . Specifically, we will take S n = [-n, n] d as illustrated in the first two panes of Figure 1 . The third pane of Figure 1 illustrates that we will specifically consider the partition of S n induced by P which we denote by S n . That is, the induced partition S n is the set {X ∩ S n : X ∈ P and X ∩ S n ̸ = ∅}. Then for each S n we consider a collection A n of the enlarged members of the induced partition: However, there remains one other issue to deal with to utilize Proposition 5.1-for each n, we have to have some lower bound on the expressionA n = {A Y } Y ∈Sn where A Y def = ⃗ y∈Y B • ∞ (ε, ⃗ y). Note that each A Y is a subset of S ′ n def = [-(n + ε), n + ε]A Y ∈An m(A Y ) m(S ′ n ). We know that m(S ′ n ) = (2(n + ε)) d , and using the fact that S n is a partition of S n = [-n, n] d , we have the following if S n is countable 1 (meaning finite or countably infinite):A Y ∈An m(A Y ) ≥ Y ∈Sn m(Y ) = m Y ∈Sn Y = m(S n ),A Y ∈An m(A) m(S ′ n ) ≥ m(S n ) m(S ′ n ) ≥ (2n) d (2(n + ε)) d = n n + ε d = 1whereas we want it ≥ (1 + 2ε) d . Basically, this lower bound is not good because we did not account for the fact that each A Y ∈ A n is enlarged from Y ∈ S n . Thus, we want some way to give for each Y ∈ S n , a lower bound on the measure of the enlarged set A Y . One might observe that enlarging with an ε-ball looks something like scaling by a factor of 1 + ε, and since the Lebesgue measure (i.e. typical notion of volume/measure in R d ) has the property that scaling by (1 + ε) increases the measure by a factor of (1 + ε) d , we might be able to show that the enlarged version of each member increases by a factor of (1 + ε) d (which is basically what we are looking to get). 1 If Sn is uncountable, one of the equalities in the chain becomes the wrong inequality as we get thatY ∈Sn m(Y ) ≤ m Y ∈Sn Y by B.2 in B.This intuition holds, though the actual reason is not related to scaling, and is dependent on the members having measure at most 1. Rather, we use a specialized adaption of Theorem 5.1 to show that m(A Y ) ≥ m(Y ) • (1 + 2ε) d(1) holds. Now that we have dealt with both issues that arise with trying to apply Proposition 5.1, we can consider a fixed n and can continue. We proceed in two cases: (1) the interesting case in which S n has only countably many members, and (2) the nearly trivial case in which the partition S n contains uncountably many members. In case (1) we haveA Y ∈An m(A Y ) m(S ′ n ) = Y ∈Sn m(A Y ) m(S ′ n ) (Re-index) ≥ Y ∈Sn m(Y ) • (1 + 2ε) d m(S ′ n )( Equation 1)= (1 + 2ε) d • Y ∈Sn m(Y ) m(S ′ n ) (Linearity of summation) = (1 + 2ε) d • m Y ∈Sn Y m(S ′ n ) (Countable additivity of measures) = (1 + 2ε) d • m(S n ) m(S ′ n ) (S n = Y ∈Sn Y ) = (1 + 2ε) d • n n + ε d ( m(Sn) m(S ′ n ) = ( n n+ε ) d as above)Since (for fixed d and ε) we have lim n→∞n n+ε d = 1, then lim n→∞ (1 + 2ε) d • n n+ε d = (1 + 2ε) d ,so because there is a ceiling involved, we can take N ∈ N to be large enough that In case (2) where some S N contains uncountably many members, then we completely ignore the lower bound for m(A Y ) in Equation 1 because it might be that lots of members Y (possibly all of them) have measure 0, and so that bound only tells us that m(A Y ) ≥ 0. Instead, we note that Y is at least non-empty, so contains at least one point ⃗ y, and thus(1 + 2ε) d • N N +ε d = (1 + 2ε) d ,A Y ⊇ B • ∞ (ε, ⃗ y) = d i=1 [y i -ε, y i + ε], and so m(A Y ) ≥ (2ε) d . Thus, A Y ∈A N m(A Y ) m(S ′ N )= ∞, so by Proposition 5.1, there is a point⃗ p ∈ S ′ N that is contained in at least (1 + 2ε) d many sets in A N ,and by our change of perspective, this point ⃗ p has the property that B • ∞ (ε, ⃗ p) intersects at least (1 + 2ε) d many members of P.The partitions that we construct, to establish Theorem 3.2, are of a very natural form: we build a partition of a large dimension d space, by splitting up the coordinates into smaller sets, and separately partitioning each set of coordinates. In the end, the smaller partitions will be known partition constructions from Theorem 2.3. We will define the construction very generically. We need the observation that if a partition is (k, ε)-secluded, then we can increase k to k ′ and decrease ε to ε ′ and the partition is trivially (k ′ , ε ′ )-secluded. We refer to this property as the "monotonicity" property. P i def = n i=1 X i : X i ∈ P i where n i=1 X i is viewed as a subset of R d .We specifically stated thatn i=1 X i is viewed as a subset of R d , because technically it is a subset of n i=1 R di , but this is naturally isomorphic to R d = R n i=1 di . For example, technically, if d 1 = d 2 = d 3 = 2, then the elements of n i=1 R di are of the form ⟨⟨x 1 , x 2 ⟩, ⟨x 3 , x 4 ⟩, ⟨x 5 , x 6 ⟩⟩, butthis is trivially isomorphic to R 6 by instead considering the element as ⟨x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ⟩.We can now show that if we take a product of partitions, and we have a guarantee for each P i that it is (k i , ε i )-secluded, then we can guarantee the product partition is (k, ε)-secluded where k is the product of the k i 's and ε is the minimum of the ε i 's.Proposition 5.2 (Product Partition Seclusion Guarantees). Let n ∈ N. For each index i ∈ [n], let d i , k i ∈ N, ε i ∈ (0, ∞) and P i be a (k i , ε i )-secluded partition of R di . Then the product partition P = n i=1 P i is a (k, ε)-secluded partition of R d where d = n i=1 d i , and k = n i=1 k i , and ε = min i∈[n] ε i .Proof Sketch. The basic idea is that for any point ⃗ p ∈ R d , we consider how many members of P intersect B ε (⃗ p). Conceptually we think of ⃗ p as a sequence ⟨⃗ p (i) ⟩ n i=1 of n points where the ith point ⃗ p (i) belongs to R di . Because we are working with the ℓ ∞ norm (that is the norm used by the definition of secluded), the ε ball around ⃗ p is the product of the ε balls around each ⃗ p (i) which is smaller than the product of ε i balls around each ⃗ p (i) because we chose ε as the minimum size. Thus, if the ε ball around ⃗ p intersects a member X of the partition P, then conceptually viewing X as a sequence ⟨X i ⟩ n i=1 where X i is a member of P i , it must be for each i ∈ [n] that the ε ball around ⃗ p (i) intersects X i (and thus so does the ε i ball sinceε i ≥ ε). This means (for each i ∈ [n]) that X i is one of at most k i members of P i because at most k i members of P i intersect the ε i ball around ⃗ p (i) (by definition of P i being (k i , ε i )-secluded). Thus X is one of at most n i=1 k i = k members of P.That is, there are at most k members of P that intersect the ε ball around ⃗ p which is the definition of P being (k, ε)-secluded.Utilizing the construction above, we will now take the unit cube partition from Theorem 2.3 for each R di and take their product to obtain a new partition. Since the dimension of each d i is smaller than the dimension d, this allows us to get a larger value of ε i for each partition, and thus a larger value of ε for the partition of R d than if we had used one of the original partitions. The price we pay for this is that the value of k also increases.We establish the following lemma. In the case that⌈ d d ′ ⌉ and ε = 1 2d ′ . Proof. Let n = ⌈ d d ′ ⌉. By [44], let P ′ be a (d ′ + 1, 1/2d ′ )-secluded unit cube partition of R d ′ . By Proposition 5.2 P = n i=1 P ′ is a (k, ε)-secluded unit cube partition of R n•d ′ where k = (d ′ + 1) n and ε = 1 2d ′ . Since n • d ′ = ⌈ d d ′ ⌉ • d ′ ≥ d,d ′ = 1, then ε = 1 2 and k ≥ (d ′ + 1) ⌈ d d ′ ⌉ = 2 dand by hypothesis k ≤ 2 d , so we have equality and we conclude thatlog 4 (k) 4d log 4 (d + 1) = d/2 4d log 4 (d + 1) = 1 8 log 4 (d + 1) ≤ 1 8 • 1 2 ≤ 1 2 = εwhich proves the bound on ε in the first case.In the other case, we have d≥ d ′ ≥ 2. Let d ′′ = d ′ -1 > 0 and δ = 1 2d ′′ . Note that ε δ = 2d ′′ 2d ′ = d ′ -1 d ′ = 1 - 1 d ′ ≥ 1 - 1 2 = 1 2 so ε ≥ 1 2 δ. By our choice of d ′ and because d ′′ < d ′ , it must be that k ≤ (d ′′ + 1) ⌈ d d ′′ ⌉ . Noting that ⌈ d d ′′ ⌉ ≤ d d ′′ + 1 = d+d ′′ d ′′ ≤ 2d d ′′ , we have k ≤ (d ′′ + 1) ⌈ d d ′′ ⌉ ≤ (d ′′ + 1) 2d d ′′ = (d ′′ + 1) 4dδ ≤ (d ′′ + 1) 8dε ≤ (d + 1) 8dεBy taking the logarithm of each side and solving for ε, we obtain the desired result that ε ≥log 4 (k)8d log 4 (d+1) .Interestingly, the proof of the neighborhood Sperner/KKM lemma relies on the techniques developed to prove Theorem 3.1: for each color c ∈ C, let X c be the set of points that are colored c. We union an ε-ball at each point in X c , to obtain an enlarged version A Xc of X c . Now, as before, by the Continuous Pigeonhole Principle (Corollary 5.1 ), there is a point that belongs to many of the enlarged sets (and so the ball located at that point intersects many of the original color sets). However, there are some additional issues that arise on the unit cube that don't arise in R d .In the discussion in the proof sketch of Theorem 3.1, the enlarged set was not contained in the original region (denoted S n ) and we needed to consider a larger region (denote S ′ n ) to contain them. In R d we could deal with this via a limiting argument so that the ratio of the volume change m(S n )/m(S ′ n ) tends to 1 (i.e. it became negligible when ceilings were involved). If one enlarges every color in a unit cube [- 1 2 , 1 2 ] d in the same way, the measure of each color is guaranteed to increase by a factor of (1 + 2ε) d as before, but also the smallest set that contains all of these enlargements is the unit cube [-1 2 -ε, 1 2 + ε] d which increased in measure by a factor of (1 + 2ε) d compared to the original cube, so nothing has been gained! Obviously, there will be an overlap of the enlargements, but the bounds given by the generalized Brunn-Minkowsi inequality tell us no additional information.We resolve this by employing a trick of first extending the coloring directly to [-1 2 -ε, 1 2 + ε] d in a natural way that ensures each color is bounded away from the boundary so that we can perform an enlargement which is non-uniform (it enlarges only toward one of the 2 d orthants) and still have the enlarged color set contained in [- 1 2 -ε, 1 2 + ε] d . This means we end up knowing that each modified color has increased in measure by at least a factor of (1 + 2 3 ε) d and that the modified containing region has not changed in measure at all. 
conclusion and open questions: 
 This work is a comprehensive study of secluded partitions. Prior to this work, it was known that the [30, 44] were optimal in regards to the degree parameter (k = d + 1). However, it was unknown if they were optimal in the tolerance parameter ε for this choice of k. The present work showed that these constructions are optimal in ε up to a logarithmic factors. Furthermore, they remain optimal within a logarithmic factor even if we allow the degree k to be polynomial in the dimension d. We also constructed secluded partitions, optimal up to logarithmic factors, for all k between d + 1 and 2 d . This work raises a few open problems. At first glance, it might seem to complete the study of secluded partitions; however, it only establishes near-matching bounds for the ℓ ∞ norm. In Appendix A.8, we present upper bounds on ε in terms of k for ℓ p norms, but no known constructions approach these bounds. Developing near-optimal partitions for other norms and exploring their applications to replicability would be an intriguing direction for future research In replicable algorithm design, there appears to be a cost to achieve replicability-sample complexity blow-up. This work showed that this blow-up in sample complexity is unavoidable in list replicability if one uses secluded partitions method. Can we establish a generic lower bound on the sample complexity of list replicable learning algorithms? While Theorem 3.4 gives a new "neighborhood" variant of the Sperner/KKM lemma, the color bound of (1 + 2 3 ε) d is not tight for small ε because the standard cubical Sperner/KKM lemma (2.4) shows that even for arbitrarily small ε, the color bound is at least d + 1. A compelling research goal is to improve on Theorem 3.4 so that the standard cubical Sperner/KKM lemma follows as a special case. Finally, finding applications of the neighborhood Sperner/KKM lemma is an interesting research direction.(d + 1, O( 1 d ))-secluded partitions of 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: Our paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our paper has no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
: 
 1. We show that for any (k, ε)-secluded partition where each member has at most unit measure, it must be that k ≥ (1 + 2ε) d , and consequently, for the interesting regime k ∈ [2 d ] it must be that ε ≤ log 4 (k) d . 2. To complement this upper bound on ε, we show that for each d ∈ N and for each viable k ∈ [2 d ], a construction of a (k, ε)-secluded (unit cube) partition with ε ≥ log 4 (k)EQUATION8 log 4 (d+1) . This establishes the optimality of ε within a logarithmic factor. 3. Finally, we adapt our proof techniques to obtain a new "neighborhood" variant of the cubical KKM lemma (or cubical Sperner's lemma): For any coloring of [0, 1] d in which no color is used on opposing faces, it holds for each ε ∈ (0, 1 2 ] that there is a point where the open ε-radius ℓ ∞ -ball intersects at least (1 + 2 3 ε) d colors. While the classical Sperner/KKM lemma guarantees the existence of a point that is "adjacent" to points with (d + 1) distinct colors, the neighborhood version guarantees the existence of a small neighborhood with exponentially many points with distinct colors. 
 
 Appendix: The following is a list of some of the notation we will use in this paper.• We use N to denote the natural numbers starting with 1. A.2 Proof Theorem 3.1• We continue to use B ∥•∥ (ε, ⃗ p), B • ∥•∥ (ε, ⃗ p), B ∞ (ε, ⃗ p),In this section, we present a complete proof of 3.1. We begin with some prerequisite results in A.2.1. Then, in A.2.2 we establish a more generic theorem that can handle any norm. Theorem 3.1 follows as immediate corollary this generic result.In this section, we will deal with arbitrary norms of R d . We point out the well-known fact that all norms on R d are equivalent in the sense that they all generate the same topology onR d . Given two norms ∥•∥ a and ∥•∥ b on R d , there exists fixed constants c d , C d ∈ (0, ∞) such that for all vectors ⃗ x ∈ R d , it holds that c d ∥⃗ x∥ a ≤ ∥⃗ x∥ b ≤ C d ∥⃗ x∥ a .Thus the collection of open sets in R d is the same no matter which norm we are using. This also means that the Borel and Lebesgue σ-algebras on R d are the same no matter which norm is used, and thus balls with respect to any norm on R d are measurable.We begin with four simple facts. The first fact will later allow us to pass a result through a limit since the answer will be an integer. Fact A.1. For any α ∈ R, there exists γ ∈ R such that γ < α and ⌈γ⌉ = ⌈α⌉.The next fact says that the Minkowski sum of a set X and an open ball at the origin can be viewed as a union of open balls positioned at each point of X. Fact A.2. For any normed vector space, given a set X and ε ∈ [0, ∞), thenX + B • ∥•∥ (ε, ⃗ 0) = ⃗ x∈X B • ∥•∥ (ε, ⃗ x).The same can be said replacing open balls with closed balls.The third fact says that we can decompose a ball into a Minkowski sum of two smaller balls.Fact A.3. For any normed vector space, and any α, β ∈ (0, ∞), it holds thatEQUATION). The fourth fact, while also very simple, is the key change of perspective that allowed us to prove the main results of this section. It says that if we are checking which sets X in our partition intersect an ε-ball located at ⃗ p (in order to see how many there are), we can instead enlarge each member of the partition by taking its Minkowski sum with the origin-centered ε-ball, and check which of these enlarged members contain the point ⃗ p. Fact A.4. For any normed vector space, for any set X, for any vector ⃗ p, and any ε > 0, the following are equivalent:1. B • ∥•∥ (ε, ⃗ p) ∩ X ̸ = ∅ 2. ⃗ p ∈ X + B • ∥•∥ (ε, ⃗ 0)The same can be said replacing both open balls with closed balls. Now we introduce the result which is the connection to the above-mentioned key change of perspective.The result says to consider a bounded, (measurable) subset S ⊆ R d (so it has finite measure) and a collection A of (measurable) subsets of S. If we compute the sum of measures of all members in the collection A (i.e. intuitively the total volume that they take up), and compare this to the measure/volume of S, then whatever this ratio is, we can find a point in S covered by that many members of the collection A. For example, in the simplest case that the total measure of members of A is larger than the measure of S, then there is no way for all of the members of A to be disjoint, so there has to be some point covered by two members. This simple case can be viewed as a continuous version of the pigeonhole principle.In the more generic case, this result should be intuitively true by an averaging argument: if every point of S is covered only n times, then the total measure of members in A is at most n • m(S), so if the ratio of total measure in A to the measure of S is large, then n must also be large. This more general version is a sort of continuous multi-pigeonhole principle. . Then if k < ∞, there exists ⃗ p ∈ S such that ⃗ p belongs to at least k members of A. (And if k = ∞, then for any n ∈ N there exists ⃗ p (n) ∈ S such that ⃗ p (n) belongs to at least n members of A.)We first encountered this result as the main ingredient in the standard proof of Blichfeldt's theorem (which was the source of motivation for our main technique), but many of the sources we found where proofs of Blichfeldt's theorem are presented did not prove the result above except in special cases, so for convenience and completion, we provide a proof in B in two parts: B.4, and B.5.The next ingredient that we need is a way to measure how large the Minkowski sum in Fact A.4 is. In order to utilize Proposition A.1 we need a lower bound on the measures, and we can obtain one using the generalized Brunn-Minkowski inequality stated below. This version of the statement can be obtained from [22, Equation 11] ; in that survey, Gardner states this theorem with a requirement that the sets be bounded, but in the following paragraph notes that this is not necessary and the requirement is only stated for convenience of the presentation in that survey.In the theorem, the requirement that A + B is Lebesgue measurable is not a triviality; Gardner discusses that there exist known Lebesgue measurable sets A and B such that the Minkowski sum A + B is not Lebesgue measurable as shown in [43] . The next result gives us a way to circumvent this issue in our application even if the members of our partition are not measurable by taking B to be an open set so that the sum A + B is open (and thus measurable), and using the outer measure of A so that we don't need the assumption that A is measurable.Lemma A.6. Let d ∈ N and let R d be equipped with any norm∥•∥. Let Y ⊆ R d , and ε ∈ (0, ∞). Then Y + B • ∥•∥ (ε, ⃗ 0)is open (and thus Borel measurable), and m(Y+ B • (ε, ⃗ 0)) ≥ m out (Y ) 1 d + ε • (v ∥•∥,d ) 1 d d . Proof. By Fact A.2, for any ε ′′ ∈ (0, ∞), Y + B • ∥•∥ (ε ′′ , ⃗ 0) = ⃗ y∈Y B • ∥•∥ (ε ′′ , ⃗ y)which is a union of open sets, so is itself open and thus Borel measurable. Now, for any ε ′ ∈ (0, ε), observe that by FactA.3, B • ∥•∥ (ε, ⃗ 0) = B • ∥•∥ (ε -ε ′ , ⃗ 0) + B • ∥•∥ (ε ′ , ⃗ 0)and thus, this sum is measurable because it is an open ball. Using this equality and the associativity of the Minkowski sum, we haveY + B • ∥•∥ (ε, ⃗ 0) = Y + B • ∥•∥ (ε -ε ′ , ⃗ 0) + B • ∥•∥ (ε ′ , ⃗ 0) = Y + B • ∥•∥ (ε -ε ′ , ⃗ 0) + B • ∥•∥ (ε ′ , ⃗ 0).Thus, we have the following chain of inequalities (each justified after it is stated):m Y + B • ∥•∥ (ε, ⃗ 0) = m Y + B • ∥•∥ (ε -ε ′ , ⃗ 0) + B • ∥•∥ (ε ′ , ⃗ 0) (Open, measurable, equality above) ≥ m Y + B • ∥•∥ (ε -ε ′ , ⃗ 0) 1 d + m B • ∥•∥ (ε ′ , ⃗ 0) 1 d dThe above comes from the Theorem A.5 noting that as demonstrated above, terms of the sumY + B • ∥•∥ (ε -ε ′ , ⃗ 0) and B • ∥•∥ (ε ′ , ⃗ 0)are open and thus measurable, and the same holds for the sum itself Y + B • ∥•∥ (ε, ⃗ 0) . We continue.≥ m out (Y )1 d + m B • ∥•∥ (ε ′ , ⃗ 0) 1 d dThe above inequality comes from the definition of the outer measure of Y being the infimum of the measures of all measurable supersets of Y . Since Y ⊆ Y + B • ∥•∥ (ε ′ , ⃗ 0), we get the inequality above. Continuing, we have the following:EQUATION) ) Since the inequality above holds for all ε ′ ∈ (0, ε), it must also hold in the limit (keeping d and Y fixed):m Y + B • ∥•∥ (ε, ⃗ 0) ≥ lim ε ′ →ε m out (Y ) 1 d + ε ′ • (v ∥•∥,d ) 1 d d = m out (Y ) 1 d + ε • (v ∥•∥,d ) 1 d dwhich concludes the proof.At this point, we are nearly in a position to prove the main result of this section, but we need one last result which gives an inequality that we will compose with the Theorem A.5. The result below can be interpreted as saying that for appropriate parameters, we can essentially factor our the "x" in (x 1/d + α) d to get the no larger expression x(1 + α) d .Lemma A.7.For d ∈ [1, ∞), x ∈ [0, 1], and α ∈ [0, ∞), it holds that (x 1/d + α) d ≥ x(1 + α) d . Proof. If x = 0, then the result is trivial. Otherwise x ∈ (0, 1], so x 1/d ∈ (0, 1]. Because α ≥ 0, α x 1/d ≥ α, so (x 1/d + α) d = x 1/d 1 + α x 1/d d = x 1 + α x 1/d d ≥ x(1 + α) d .We establish Theorem 3.1, by proving the following result. Theorem A.8 (ε-Neighborhoods for Measure Bounded Partitions and Arbitrary Norm). theorem Let d ∈ N, M ∈ (0, ∞), and P a partition of R d such that every member has outer Lebesgue measure at most M . Let R d be equipped with any norm ∥•∥. For every ε ∈ (0, ∞), there exists⃗ p ∈ R d such that B • ∥•∥ (ε, ⃗ p) intersects at least k = 1 + ε v ∥•∥,d M 1/d dmembers of the partition wherev ∥•∥,d def = m B • ∥•∥ (1, ⃗ 0) is the Lebesgue measure of the ∥•∥ unit ball.Proof. Throughout the proof, all lengths will be with respect to ∥•∥, so we will eliminate the clutter by neglecting to use the ∥•∥ subscript anywhere in the proof. We will also be working in a single dimension d throughout the proof, so we also drop the d subscript from v throughout.Consider the following for each n ∈ N. Let S n = B • (n, ⃗ 0) and S ′ n = B • (n + ε, ⃗ 0) = S n + B • (ε, ⃗ 0) and S be the partition of S n induced2 by P.For each Y ∈ S n , let C Y = Y + B • (ε, ⃗ 0). By Lemma A.6, C Y is measurable, and m(C Y ) ≥ m out (Y ) 1 d + ε • v 1 d d . Also observe that C Y ⊆ S ′n . Now consider the following inequalities:m(C Y ) ≥ m out (Y ) 1 d + ε • v 1 d d (Above) = M 1/d m out (Y ) 1 d M 1/d + ε • v 1 d M 1/d d (Algebra) = M m out (Y ) M 1 d + ε • v 1 d M 1/d d (Algebra) ≥ M • m out (Y ) M • 1 + ε • v 1 d M 1/d d (A.7 since mout(Y ) M ∈ [0, 1]) = m out (Y ) • 1 + ε • v 1 d M 1/d d (Simplify)Informally, the above shows that for each Y ∈ S n , the set Y + B • (ε, ⃗ 0) has substantially more (outer) measure than Y does-specifically a factor of 1 + ε•v1 d M 1/d d. We will extend this to unsurprisingly show that this implies that Y + B • (ε, ⃗ 0)Y ∈Sn also has this same factor more (outer) measure than S n does, observing that S n has total (outer) measure of about m(S n ) since S n is a partition of S n (any discrepancy is due to non-measurable members in S n )Formally, we claim that there exists a finite subfamilyF n ⊆ S n such that Y ∈Fn m Y + B • (ε, ⃗ 0) ≥ 1 + ε • v 1 d M 1/d d • m(S n ).To see this, first consider the case that S n has infinite cardinality. Let F n ⊂ S n be any subfamily of finite cardinality at least1 + ε•v 1 d M 1/d d • m(S n ) • 1 ε d v . This gives Y ∈Fn m Y + B • (ε, ⃗ 0) ≥ Y ∈Fn m B • (ε, ⃗ 0)where this inequality is because Y +B• (ε, ⃗ 0) is a superset of some translation of B • (ε, ⃗ 0) since Y ̸ = ∅.Continuing, we use the standard fact that m BEQUATIONNow consider the other (more interesting) case where S n has finite cardinality 3 . Take F n = S n so thatY ∈Fn m Y + B • (ε, ⃗ 0) = Y ∈Sn m Y + B • (ε, ⃗ 0) (F n = S n ) ≥ Y ∈Sn m out (Y ) • 1 + ε • v 1 d M 1/d d (Above) = 1 + ε • v 1 d M 1/d d • Y ∈Sn m out (Y ) (Linearity of summation) ≥ 1 + ε • v 1 d M 1/d d • m out Y ∈Sn Ywhere the above inequality is due the the countable subaddativity property of outer measures which states that a countable sum of outer measures of sets is at least as large as the outer measure of the union of the sets. In the last step we get= 1 + ε • v 1 d M 1/d d • m (S n ) ( Y ∈Fn Y = S n is measurable)Thus, regardless of whether S n has infinite or finite cardinality, there exists a finite subfamilyF n ⊆ S n such that Y ∈Fn m Y + B • (ε, ⃗ 0) ≥ 1 + ε • v 1 d M 1/d d • m(S n ).Fix such a subfamily F n , and letA n = Y + B • (ε, ⃗ 0)Y ∈Fn be a family indexed4 by F n . Note thatfor each A Y def = Y +B • (ε, ⃗ 0) ∈ A n , since Y ⊆ S n = B • (n, ⃗ 0), we have A Y ⊆ S n +B • (ε, ⃗ 0) = S ′ n .Thus, by B.5 5 , there is a point ⃗ p (n) ∈ S ′ n which belongs to at least k n -many sets in A n wherek n def =     Y ∈Fn m Y + B • (ε, ⃗ 0) m(S ′ n )     ≥ 1 + ε•v 1 d M 1/d d • m (S n ) m(S ′ n ) (Above) = 1 + ε • v 1 d M 1/d d • m B • (n, ⃗ 0) m B • (n + ε, ⃗ 0) (Def'n of S n and S ′ n ) = 1 + ε • v 1 d M 1/d d • n d • v (n + ε) d • v (Standard scaling fact) = 1 + ε • v 1 d M 1/d d • n n + ε d .(Simplify)Since ⃗ p (n) belongs to at least k n -many sets in A n , this by definition means that there are at leastk n -many sets Y ∈ F n such that ⃗ p (n) ∈ Y + B • (ε, ⃗ 0), so by Fact A.4, we have Y ∩ B • (ε, ⃗ p (n) ) ̸ = ∅. For each such Y (since Y ∈ F n ⊆ S n ), there is a distinct 6 X Y ∈ P such that Y ⊆ X Y and thus X Y ∩ B • (ε, ⃗ 0) ̸ = ∅showing that there are at least k n -many sets in P which intersect B • (ε, ⃗ 0).For the last step of the proof, we perform a limiting process on n. By Fact A.1, let γ ∈ R such thatγ < 1 + ε•v 1 d M 1/d d and ⌈γ⌉ = 1 + ε•v 1 d M 1/d d . Then, because lim n→∞ k n ≥ lim n→∞ 1 + ε • v 1 d M 1/d d • n n + ε d = 1 + ε • v 1 d M 1/d d > γ,we can take N ∈ N sufficiently large so thatk N ≥ 1 + ε • v 1 d M 1/d d • N N + ε d > γ.Then considering the point ⃗ p (N ) , we have by the choice of γ and the fact that k N is an integer that Then by A.8, there is a pointk N = ⌈k N ⌉ ≥ ⌈γ⌉ =     1 + ε • v 1 d M 1/d d     showing that B • (ε, ⃗ p (N ) ) intersects at least k N ≥ 1 + ε•v 1 d M 1/⃗ p ∈ R d such that B • ∞ (ε, ⃗ p) intersects at least 1 + ε v ∥•∥∞,d M 1/d d = 1 + ε 2 d 1 1/d d = (1 + 2ε) dmembers of P, and thus trivially the closed ball B ∞ (ε, ⃗ p) does as well. Thus, if P is (k, ε)-secluded (meaning by definition that for every ⃗ p ∈ R d it holds that B ∞ (ε, ⃗ p) intersects at most k members of P) then it must be that k ≥ (1 + 2ε) d .For the consequence, if k ≤ 2 d , then this implies ε ≤ 1 2 . Then taking the logarithm of both sides of our inequality and using the fact that log 4 (1 + 2x) ≥ x for x ∈ [0, 1 2 ] (see footnote 7 ), we have log ε(d) ≤ ln(k(d)) d ≤ n ln(Cd) d ∈ O ln(d) d .More specifically, for any n ′ > n we have for large enough d that (n ′ -n) ln(d) ≥ n ln(C), so for large enough d we haveε(d) ≤ n ln(Cd) d = n[ln(C) + ln(d)] d ≤ (n ′ -n) ln(d) + n ln(d) d = n ′ ln(d) dshowing that the hidden constant can be taken to be any n ′ larger than the degree n of k.The partitions that we construct in this section are of a very natural form: we build a partition of a large dimension d space, by splitting up the coordinates into smaller sets, and separately partitioning each set of coordinates. In the end, the smaller partitions will be known partition constructions [44] . We will define the construction very generically. We need two basic results. The following observation notes that if a partition is (k, ε)-secluded, then we can increase k to k ′ and decrease ε to ε ′ and the partition is trivially (k ′ , ε ′ )-secluded. Observation A.10 (Monotonicity in k and ε).Let d ∈ N, k, k ′ ∈ N with k ′ ≥ k, ε, ε ′ ∈ [0, ∞) with ε ′ ≤ ε, and P a (k, ε)-secluded partition of R d . Then P is also a (k ′ , ε ′ )-secluded partition of R d .Proof. Since P is (k, ε)-secluded, by definition every ε-ball intersects at most k members of P, so trivially every (no larger) ε ′ -ball intersects at most k ′ ≥ k members of P.We will frequently refer to the above observation just using the phrase "by monotonicity, P is(k ′ , ε ′ )-secluded" Fact A.11 (Trivial k for Unit Cube Partitions). Let d ∈ N, ε ∈ [0, ∞), and P be any unit cube partition of R d . Then P is (k, ε)-secluded for k = (2 + 2ε) d . Proof. Consider any point ⃗ p ∈ R d . Observe that for any X ∈ P, X is a unit cube, so diam ∞ (X) = 1, so if X intersects B ∞ (ε, ⃗ p), then X ⊆ B ∞ (1 + ε, ⃗ p).Because (1) each X ∈ P has measure 1, and (2) every pair of members are disjoint (because P is a partition), and (3) the measure ofB ∞ (1 + ε, ⃗ p) = ⃗ p + [-1 -ε, 1 + ε] d is (2 + 2ε) d , it follows that at most (2 + 2ε) d members of P are a subset of B ∞ (1 + ε, ⃗ p) and thus at most (2 + 2ε) d members of P intersect B ∞ (ε, ⃗ p) which shows that P is (k, ε)-secluded for k = (2 + 2ε) d as claimed.Utilizing the construction above, we will now take a unit cube partition of [44] for each R di and take the product to obtain a new partition. Since the dimension of each d i is smaller than the dimension d, this allows us to get a larger value of ε i for each partition, and thus a larger value of ε for the partition of R d than if we had used one of the original partitions. The price we pay for this is that the value of k also increases.We establish the following theorem stated as Theorem 5.3 in the main body of the paper. ⌈ d d ′ ⌉ and ε = 1 2d ′ . Proof. Let n = ⌈ d d ′ ⌉. By [44] , let P ′ be a(d ′ + 1, 1 2d ′ )-secluded unit cube partition of R d ′ .By Proposition A.2 and Fact A.13, P =n i=1 P ′ is a (k, ε)-secluded unit cube partition of R n•d ′ where k = (d ′ + 1) n and ε = 1 2d ′ . Since n • d ′ = ⌈ d d ′ ⌉ • d ′ ≥ d,this trivially (by ignoring extra coordinates) gives a partition of R d with these same properties (alternatively, see footnote 9 ) which completes the proof. This construction is sufficiently general that for any dimension d ∈ N and any tolerance parameter in the domain of interest (k ∈ [2 d ]), we can construct a (k, ε)-secluded unit cube partition of R d such that ε which is within a factor of 8 log 4 (d + 1) of the maximum possible tolerance for this choice of dimension and degree.Finally, we are ready to prove Theorem 3.2. 10 ), and let ε = 1 2d ′ . By Theorem A.14 and monotonicity, let P be a (k, ε)-secluded unit cube partition of R d . Now we prove the bound on ε in two cases: eitherProof. Let d ′ ∈ [d] be the minimum integer such that (d ′ + 1) ⌈ d d ′ ⌉ ≤ k (see justificationd ′ = 1 or d ′ ≥ 2.In the case thatd ′ = 1, then ε = 1 2 and k ≥ (d ′ + 1) ⌈ d d ′ ⌉ = 2 dand by hypothesis k ≤ 2 d , so we have equality and we conclude thatlog 4 (k) 4d log 4 (d + 1) = d/2 4d log 4 (d + 1) = 1 8 log 4 (d + 1) ≤ 1 8 • 1 2 ≤ 1 2 = εwhich proves the bound on ε in the first case.In the other case, we have d≥ d ′ ≥ 2. Let d ′′ = d ′ -1 > 0 and δ = 1 2d ′′ . Note that ε δ = 2d ′′ 2d ′ = d ′ -1 d ′ = 1 - 1 d ′ ≥ 1 - 1 2 = 1 2 so ε ≥ 1 2 δ. By our choice of d ′ and because d ′′ < d ′ , it must be that k ≤ (d ′′ + 1) ⌈ d d ′′ ⌉ . Noting that ⌈ d d ′′ ⌉ ≤ d d ′′ + 1 = d+d ′′ d ′′ ≤ 2d d ′′ , we have k ≤ (d ′′ + 1) ⌈ d d ′′ ⌉ ≤ (d ′′ + 1) 2d d ′′ = (d ′′ + 1) 4dδ ≤ (d ′′ + 1) 8dε ≤ (d + 1) 8dεBy taking the logarithm 11 , of each side and solving for ε, we obtain the desired result:ε ≥ log 4 (k) 8d log 4 (d + 1). 9 An alternate perspective is to let d1, . . . , dn be such that n i=1 di = d and the first portion of the list di = d ′ , and the second portion of the list di= d ′′ def = d ′ -1. Then let P ′ a (d ′ + 1, 1 2d ′ )-secluded partition of R d ′as before, and letP ′′ a (d ′′ + 1, 1 2d ′′ )-secluded partition of R d ′′ . Since d ′′ < d ′ , P ′′ is (by monotonicity) a (d ′ + 1, 1 2d ′ )-secluded partition.Then take Pi = P ′ when di = d ′ and Pi = P ′′ when di = d ′′ . Again, we get that P is (k, ε)-secluded for k = (d ′ + 1) n and ε = 1 2d ′ . 10 A minimum exists by finiteness and the fact that some d ′ satisfies the condition-in particular d ′ = d satisfies the requirement because k ≥ d + 1 by hypothesis. 11 We choose the base 4 logarithm since that is what appears in our upper bound on ε.The first step in the proof is to extend the coloring χ to the larger cube [-1 2 -ε, 1 2 + ε] d in a natural way. Consider the following function f which truncates points in the larger interval to be in the smaller interval:f : [-1 2 -ε, 1 2 + ε] → [-1 2 , 1 2 ] f (y) def =    -1 2 y ≤ -1 2 y y ∈ (-1 2 , 1 2 ) 1 2 y ≥ 1 2 Let ⃗ f : [-1 2 -ε, 1 2 +ε] d → [-1 2 , 1 2 ] d be the function which is f in each coordinate: ⃗ f (⃗ y) def = ⟨f (y i )⟩ d i=1 . Now extend the coloring χ to the coloring γ : [-1 2 -ε, 1 2 + ε] d → C defined by γ(⃗ x) def = χ ⃗ f (⃗ x) .For each color c ∈ C, let Y c = γ -1 (c) denote the points assigned color c by γ and note that Y c ⊇ X c . Consistent with this notation, we will typically refer to a point in the unit cube as ⃗ x and a point in the extended cube as ⃗ y.We make the following claim which implies that for each color c ∈ C, the set Y c of points of that color in the extended coloring are contained in a set bounded away from one side of the extended cube[-1 2 -ε, 1 2 + ε] d in each coordinate. Subclaim A.16. For each color c ∈ C there exists an orientation ⃗ v ∈ {-1, 1} d such that Y c ⊆ d i=1 v i • (-1 2 , 1 2 + ε].Proof of Claim. Fix an arbitrary coordinate i ∈ [d]. Note that for every ⃗ y ∈ Y c we have f (⃗ y ∈ X c which is to say that the ⃗ y has the same color in the extended coloring as f (⃗ y) does in the original coloring (see justification 12 ).Note that if there is some ⃗ y ∈ Y c with y i ≤ -1 2 , then f(y i ) = -1 2 so π i (X c ) ∋ f (y i ) = -1 2 . Similarly, if there is some ⃗ y ∈ Y c with y i ≥ 1 2 , then π i (X c ) ∋ 1 2 .Recall that by hypothesis, π i (X c ) does not contain both -1 2 and 1 2 which means it is either the case that for all ⃗ y ∈ Y c we havey i > -1 2 (so π i (Y c ) ⊆ (-1 2 , 1 2 + ε])or it is the case that for all ⃗ y ∈ Y c we havey i < 1 2 (so π i (Y c ) ⊆ [-1 2 -ε, 1 2 )). Thus we can choose v i ∈ {-1, 1} such that π i (Y c ) ⊆ v i • (-1 2 , 1 2 + ε]. Since this is true for each coordinate i ∈ [d] we can select ⃗ v ∈ {-1, 1} d such that Y c ⊆ d i=1 π i (Y c ) ⊆ d i=1 v i • (- 1 2 , 1 2 + ε] as claimed. ■ For an orientation ⃗ v ∈ {-1, 1} d , let B ⃗ c denote the set B ⃗ v def = d i=1 -v i • (0, ε)which should be interpreted as an open orthant of the ℓ ∞ ε-ball centered at the origin-specifically the orthant opposite the orientation ⃗ v. Building on A.16, we get the following: Subclaim A.17. For each color c ∈ C, there exists an orientation⃗ v ∈ {-1, 1} d such that Y c + B ⃗ v ⊆ [-1 2 -ε, 1 2 + ε] d .sum of measures of sets in A, we have the following:A∈A m(A) = c∈C m Y c + B ⃗ v(c)(Def'n of A; measurability was shown above) 18 and linearity of summation)≥ 1 + ε 1 + ε d • c∈C m out (Y c ) (A.≥ 1 + ε 1 + ε d • m out c∈C Y c(Countable/finite subaddativity of outer measures) What we really want, though, is a point in the unit cube that has this property rather than a point in the extended cube, and we want it with respect to the original coloring χ rather than the extended coloring γ. We will show that the point ⃗ f (⃗ p) suffices.= 1 + ε 1 + ε d • m out [-1 2 -ε, 1 2 + ε] d (The Y c 's partition [-1 2 -ε, 1 2 + ε] d ) = 1 + ε 1 + ε d • (1 + 2ε) d (Evaluate outer measure) By A.17, each member of A is a subset of [-1 2 -ε, 1 2 + ε] d , so by 5.1, there exists a point ⃗ p ∈ [-1 2 -ε, 1 2 + ε] d that belongs to at least      1 + ε 1+ε d • (1 + 2ε) d (1 + 2ε) d      = 1 + ε 1 + ε d sets in A. That is, ⃗ p belongs to Y c + B ⃗ v(c) for at least 1 + ε 1+ε d colors c ∈ C. For each such color c, it follows that ⃗ p + (-ε, ε) d intersects Y c (see justification 14 ). Note that with respect to the ℓ ∞ norm, ⃗ p + (-ε, ε) d = B • ∞ (ε, ⃗ p) showing that B • ∞ (ε, ⃗ p)Subclaim A.19. If c ∈ C is a color for which B • ∞ (ε, ⃗ p) ∩ Y c ̸ = ∅, then also B • ∞ (ε, ⃗ f (⃗ p)) ∩ X c ̸ = ∅. Proof of Claim. Let ⃗ y ∈ B • ∞ (ε, ⃗ p) ∩ Y ⃗ c . Then because ⃗ y ∈ B • ∞ (ε, ⃗ p), we have ∥⃗ y -⃗ p∥ ∞ < ε, so for each coordinate i ∈ [d], |y i -p i | < ε.It is easy to analyze the 9 cases (or 3 by symmetries) arising in the definition of f to see that this implies |f (y i ) -f (p i )| < ε as well (i.e. f maps pairs of values in its domain so that they are no farther apart), thus∥ ⃗ f (⃗ y) -⃗ f (⃗ p)∥ ∞ < ε and thus ⃗ f (⃗ y) ∈ B • ∞ (ε, ⃗ f (⃗ p)).Also, as justified in a prior footnote 12 , for any unique color since any pair of corners belong to an opposite pair of faces on the cube. For this reason it is trivial that for ε > 1 2 there is a point ⃗ p such that B • ∞ (ε, ⃗ p) intersects at least 2 d colors: just let ⃗ p be the midpoint of the unit cube. Thus, the only interesting case is ε ∈ (0, 1 2 ], and for such ε we have⃗ y ∈ Y c we have ⃗ f (⃗ y) ∈ X c so that ⃗ f (⃗ y) ∈ B • ∞ (ε, ⃗ f (⃗ p)) ∩ X c which1 + ε ≤ 3 2 and thus ε 1+ε ≥ 2 3 ε showing that 1 + ε 1+ε d ≥ (1 + 2 3 ε) d .This completes the proof of the theorem.Throughout this section, we use the word "countable" to mean finite or countably infinite. Thus µ( A∈A A) is an upper bound for the set A∈F µ(A) : F ⊆ A, F finite and thus greater than or equal to the supremum. Fact B.3 (Interchange of Countable Sums with Non-negative Terms). If I, J are countable sets, and a i,j ≥ 0 for all (i, j) ∈ I × J, then i∈I j∈J, ⃗ z ∈ X such that |π i (⃗ z)-π i (⃗ y)| > D which means ∥⃗ z -⃗ y∥ ∞ > D. Thus taking ⃗ p = ⟨ inf(Xi)+sup(Xi) 2 ⟩ d i=1 we have X ⊆ d i=1 [inf(X i ), sup(X i )] ⊆ ⃗ p + [-D 2 , D 2 ] d = B(D/2, ⃗ p).a i,j = j∈J i∈I a i,jProof. This can be proved directly via basic analysis methods if I and J are assumed to be N and the definition of the infinite sum as a limit of finite sums is used. Alternatively, viewing the summation as an integral over a countable measure space, this can be viewed as a corollary to Tonelli's theorem.Lemma B.4 (Upper Bound Measure of Multiplicity). Let n ∈ N. Let X be a measurable set in some measure space (the measure being denoted by µ) and let A be a countable family of measurable subsets of X such that for each x ∈ X, x belongs to at most n members of A.Then A∈A µ(A) ≤ n • µ(X).Proof. 15 For ease of indexing, assume A = {A i } ∞ i=1 . Let I Ai denote the indicator function for A i , and note that by hypothesis, for any k ∈ N, the function k i=1 I Ai is bounded above by the constant 15 We thank an anonymous researcher who pointed out that our original proof was overcomplicating things and pointing us to this elementary proof. function n. Thus, recalling that µ(A i ) = X I Ai dµ (because A i ⊆ X) we have the following for any k ∈ N:k i=1 µ(A i ) = k i=1 X I Ai dµ = X k i=1 I Ai dµ ≤ X n dµ = n • µ(X).Since this holds for all k, it also holds in the limit:A∈A µ(A) = ∞ i=1 µ(A i ) = lim k→∞ k i=1 µ(A i ) ≤ n • µ(X).Corollary B.5 (Lower Bound Cover Number). Let X be a measurable set in some measure space (the measure being denoted by µ) such that 0 < µ(X) < ∞. Let A be a countable family of measurable subsets of X such that A∈A µ(A) < ∞. Then there exists x ∈ X such that x belongs to at leastA∈A µ(A) µ(X)-many members of A.Proof. First observe that by hypothesis,A∈A µ(A) µ(X)is finite. Suppose for contradiction that eachx ∈ X belongs to strictly less thanEQUATION(noting that n < A∈A µ(A) µ(X)). Then each x ∈ X belongs to at most n-many members of A, so we haveA∈A µ(A) ≤ n • µ(X) (Lemma B.4) < A∈A µ(A) µ(X) µ(X) (0 < µ(X) < ∞ and n < A∈A µ(A) µ(X) ) = A∈A µ(A)which is a contradiction.Remark B.6. In Corollary B.5 above, it was important that we required A∈A µ(A) to be finite. If we allowed it to be infinite, then the claim would have been that there was some x ∈ X belonging to infinitely many members of A, but this is in general not true (see B.7 below). Nonetheless, it is true (and a straightforward corollary of the above) that if A∈A µ(A) = ∞, then for any n ∈ N 0 , there exists a point x n ∈ X that is contained in at least n-many sets of A. The distinction is that this point might have to depend on the choice of n. Example B.7 (Harmonic Cover of Open Unit Interval). Let X = (0, 1) be equipped with the Borel or Lebesgue measure µ.Let A = (0, 1 i ) : i ∈ N . Then A∈A µ(A) = i∈N 1 i = ∞.For any n ∈ N, we can consider the point x n = 1 n+1 which is contained in (0, 1 i ) for i ∈ [n] and not for any other i, so it belongs to exactly n sets in A.However, no point in X belongs to infinitely many sets in A. To see this, consider an arbitrary point x ∈ X = (0, 1). Then for sufficiently large i ∈ N, x ̸ ∈ (0, 1 i ) so x belongs to only finitely many members of A. Justification: Rigorous proofs of all results stated in the abstract and introduction are provided in the main body/appendix.• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: There are no potential harms caused by this research work.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024).I.e. S = {X ∩ Sn : X ∈ P and X ∩ Sn ̸ = ∅}. That is, S is the partition of Sn obtained by intersecting every member of P with the new domain Sn and keeping those that have non-empty intersections.In fact this case also works if Sn is countable even though we have already dealt with that case.We require this to be an indexed family rather than just a set, because it is possible that there are distinctY, Y ′ ∈ Sn such that Y + B • (ε, ⃗ 0) = Y ′ + B • (ε, ⃗ 0).We are taking X in B.5 to be S ′ n in this proof, and taking µ to be m and taking A to be An. We have that A∈An m(A) < ∞ because |An| = |Fn| is finite, and each A ∈ An is a subset of S ′ n , so has finite measure.I.e. for Y ̸ = Y ′ ∈ Sn we have that XY , X Y ′ ∈ P and XY ̸ = X Y ′ so this mapping of Y 's to X's is injective, so we have at least the same cardinality of X's with the desired property as Y 's with the desired property.One can verify that the function log 4 (1 + 2x) -x is concave on its domain (-1 2 , ∞) using the second derivative and note that it is 0 at x = 0 and x = 1 2 (which is why the base 4 logarithm was chosen) so it is non-negative on [0,1 2 ].In other words we identify the setR d with R d 1 × R d 2 × • • • × R d n-1 × R dnFor every ⃗ y ∈ Yc we have (by definition of Yc) that γ(⃗ y) = c and (by definition of γ) that γ(⃗ y) = χ(f (⃗ y)) showing that χ(f (⃗ y)) = c and thus (by definition of Xc) that f (⃗ y) ∈ Xc. 


Decision: The reviewers enjoyed reading the paper and appreciated its content. The only concern raised was that the main technical results seem somewhat loosely connected to the computational notion of replicability. Despite this, the reviewers found the results both interesting and inspiring.

Reviews: review: paper_summary: paper_summary: In this work the authors study various connections between geometric constructions in $R^d$, in particular various $(k,\varepsilon)$-secluded partitions, and its applications to list-replicable learnability. This connection was originally observed in prior work, and the authors provide stronger quantitative results. More specifically, their first main results shows an upper bound on the $\varepsilon$ for every (non-trivial) choice of the parameter $k$ of the secluded partition. This implies a lower bound on the number of samples needed to design a $k$-list-replicable algorithm for the problem of coin estimation through secluded partitions, and can be interpreted as a negative result: if $k = poly(d)$, then one needs $d^2$ samples per coin to design a $k$-list-replicable algorithm (through secluded partitions). This improves upon prior work which shows an upper bound on $\varepsilon$ only for $k = d+1$
Their next main provides a construction of $(k,\varepsilon)$-secluded partitions for all the (non-trivial) values of $k$ that is optimal w.r.t. $\varepsilon$ up to polylogarithmic factors. Due to the previous connection, this implies the existence of $k$-list-replicable algorithms whose sample complexity is determined by $\varepsilon$.
Lastly, the authors use the techniques they have developed to prove a "neighborhood" version of the cubical Sperner's/KKM lemma.
strength_weakness: strength_weakness: I am a bit worried that the results are a bit incremental. In particular, the connection between secluded partitions and list-replicability was already observed in prior work. Moreover, I view the result regarding secluded partitions as a negative result, in the sense that in order to get reasonable list complexity through secluded partitions, one needs a significant blow-up in the sample complexity, and this cannot be improved using this approach. Had the lower bound on the sample complexity been against all algorithms (or at least a broader class) I would have found the result more interesting. Similarly, the extension of cubical Sperner's lemma to its neighborhood variant is interesting on its own, but if the main focus of the paper is list-replicability, I am not too sure how much it adds to the story.

Some minor points/typos:
-Line 53: double full-stop.
-Line 56: "the replicable algorithm" -> replicable algorithms.
-Theorem 2.4: it would be better for a broader audience to define face/closure.
-Line 109: the degree parameter -> it.
-Line 339: know -> known.
-In many places: lowerbound -> lower bound
-Line 156: global stability.
-Line 172: extend -> extended.
-Line 112: a ) is missing.
-Line 114: drop result.
questions: questions: -Do you have a conjecture about the lower bound on the sample complexity of $k$-list replicable learning for algorithms that are not based on secluded partitions?

-Can you explain a bit more about the adaptation of Theorem 5.1 you talk about in Line 231?
limitations: limitations: Adequately addressed.
paper_summary: paper_summary: This work studies secluded partitions, which appear in the context of list-replicable learning (among other geometric/TCS applications). The complement known bounds on list complexity, the authors present new upper-bounds on the tolerance parameter as a function of the list complexity k and the ambient dimension d. They show a construction of a secluded partition that roughly achieves these bounds, showing the optimality of their bounds. The secluded partition results are then applied to give a "neighborhood" version of Sperner's lemma, for $\ell_\infty$ neighborhoods.
strength_weakness: strength_weakness: As written, I don’t think this work is a good fit for NeurIPS. This work  studies secluded partitions, which have connections to list-replicable algorithms for, e.g., the d-coin bias estimation problem as mentioned by the authors. In this sense the results have applications to replicable learning, but the actual application of the secluded partitions results give somewhat marginal replicable learning results. Theorem 3.1 essentially shows that one cannot meaningfully tradeoff list complexity for better secluded partition tolerance, and therefore cannot hope to improve sample complexity for the d-coin bias problem via the secluded partition approach, but says nothing of other approaches or other problems. 

If I try to read this as a learning paper where the focus is improving sample complexity of list-replicable d-coin bias estimation algorithms, it seems like there should be more attention paid in related work to replicable (in the sense of ILPS22) algorithms for the d-coin bias estimation problem as well, as this has been studied in [1], [2], and recently (posted after NeurIPS submission deadline) [3]. 

[1] “Stability is Stable” Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, Sorrell
[2] “Replicability in Reinforcement Learning” Karbasi, Velegkas, Yang, Zhou ’23
[3] “Replicability in High Dimensional Statistics” Hopkins, Impagliazzo, Kane, Liu, Ye ‘24

Typos/suggested edits:

Abstract

“We show that for each d” -> “we show for each d”

Section 1 pg 2
Brower -> Brouwer
should be seen as a fundamental endeavor. . 

Section 2 page 2
“belongs to a list L consisting of almost k good hypotheses”

“over which a family of distribution” -> “over which a family of distributions”

page 3

“the partitions considered in this work have a non-zero” -> “the partitions considered in this work have non-zero

Theorem 2.4 could be written a little more clearly. It would be good to define the mapping implicit in the term “coloring” and clarify that opposite faces mean faces of the hypercube

Section 3

“in general a $(k, \varepsilon)$-secluded partitions” 

“Can we improve this and construct a (d+1, \omega(1/d)-secluded partition?”

“is the following result upper bound result”

“Till this work we know”

“There exist a k-list replicable algorithm”

“Spener/KKM Lemma”

Section 4
“A learning algorithm A to be $(n, \eta)$-globally stable”

Section 5.1

Need a period before Thus/ what we do is to “replace”

I found the proof sketch for Theorem 3.1 had a few seemingly unnecessary detours that were a bit distracting. For instance, deriving the lower bound of 1 before deriving the desired bound. The footnote could be more precise (what does “becomes the wrong inequality” mean?)

Need a period before “Now that we have dealt with both issues” on page 6.

“So because there is a ceiling involved” could be made more precise, as could “by our change of perspective.”

Section 5.2

There’s a $d_n$ that should be $d_i$ in Definition 5.2

Section 6

“We also constructed secluded partitions for a wide all $k$”

The second paragraph of Section 6 is very vague, and doesn’t mention that the similar upper bounds are for general lp norms.
questions: questions: What direct implications do these results have for list-replicable learning?

How do these implications compare to what is known for $\rho$-replicable learning for similar problems?
limitations: limitations: Yes, the authors have addressed all limitations.
paper_summary: paper_summary: This paper studies connections between (i) list-replicability, a well-studied relaxation of the standard replicable learning framework and (ii) the design of partitions of the Euclidean space, in particular $(k,\epsilon)$-secluded partitions. A partition $P$ will be called $(k, \epsilon)$-secluded if for any $d$-dimensional vector $x$, a box centered at $x$ with side-length $2\epsilon$ intersects with at most $k$ members of  $P$. Crucially, the lis size of a list replicable learner is closely related to $k$. 

The main results of the paper are near-optimal trade-offs between $k$ and $\epsilon$ for secluded partitions. These imply some limitations on the design of list-replicable algorithms based on such partitions of the space.
strength_weakness: strength_weakness: Some suggestions in terms of presentation:

1) Between line 91-95, I would add some more discussion about Sperner's lemma and the terminology used.
questions: questions: 1) Do you have any intuition on what would happen if we replaced the $L_\infty$ norm with some other norm in terms of list-replicability?

2) There is a series of works that establish connections between replicability and approximate DP. Is there some similar connection to list-replicability?

3) Returning to the geometric connections to list replicability, is there some similar geometric intuition for DP?
limitations: limitations: No limitations.
paper_summary: paper_summary: The authors study the list-replicable coin problem and a closely related underlying geometric problem of constructing ($k,\varepsilon$)-secluded partitions of $\mathbb{R}^d$. The authors resolve the optimal trade-off between $k,\varepsilon$, and $d$ in the latter, and as a corollary give a new set of upper bounds for the list-replicable coin problem trading off list-size and sample complexity for the former.

The coin problem asks, given coins with biases $p_1,\ldots , p_d$, estimate the biases of each coin up to accuracy $\nu$. An algorithm for the coin problem is called *L-list-replicable* if with high probability over samples, it’s output (for any fixed set of biases) is one of $L$ possible ($\nu$-correct) bias vectors. List replicability is closely related to other core notions of stability in learning such as differential privacy, global stability, and replicability.

Prior work established that it is possible the list-replicable solve the coin problem with list size $d+1$ and $d^2$ samples per coin. The former parameter, the list size, was known to be optimal, but it was open whether the number of samples could be improved. The main "learning" result of this paper is an upper and conditional lower bound for the list-replicable coin problem giving a trade-off between list size and samples. The upper bound states for any list size $L \in [2^d] \setminus [d]$, there is an $L$-list-replicable algorithm using $\tilde{O}(\frac{d^2}{\nu^2\log^2(L)})$ samples per coin. The lower bound states that this trade-off is tight for any algorithm based on `secluded partitions’.

The true main result of the paper is a near-tight bound on the construction of ($k,\varepsilon$)-secluded partitions of $\mathbb{R}^d$. A ($k,\varepsilon$)-secluded partition is a partition of $\mathbb{R}^d$ such that for any point $p \in \mathbb{R}^d$, the $\ell_\infty$ $\varepsilon$-ball around $p$ touches at most $k$ members of the partition. It is known that any  ($k,\varepsilon$)-secluded partition leads to a $k$-list replicable algorithm with roughly $1/\varepsilon^2$ blow-up in samples per coin over the non-list-replicable coin problem.

Prior works established the existence of $(d+1,\frac{1}{2d})$-secluded partitions. The authors roughly show for any $\varepsilon$ one can construct a $((1+2\varepsilon)^d,\varepsilon)$-secluded partition and that this is tight.

The authors also establish a related "neighborhood" variant of the KKM/Sperner Lemma, stating that any coloring of [0,1]^d where no color touches opposite faces must have a point $p$ such that the $\ell_\infty-\varepsilon$-ball around $p$ touches $(1+O(\varepsilon))^d$ many colors. This is in some sense a `quantified/robust’ version of KKM, which states there is a point where every $\varepsilon$-ball sees at least $d+1$ colors, though it is actually incomparable.
strength_weakness: strength_weakness: This work’s only substantial weakness lies in its scope for NeurIPS: while the geometric results proved are indeed fundamental, the resulting implications within replicable learning are, at the moment, a bit lack-luster.

In particular, while the upper bound result itself mentioned above is nice, it is fairly close to being a corollary of the previous work “List and Certificate Complexities in Replicable Learning". All that is needed over the original work is the new secluded partition construction, which is just a product of the construction used in the original paper. Based on the definition itself (namely working in $\ell_\infty$), it is elementary to see such a construction will work, and while not formally stated in the original paper (which just focused on achieving $d+1$ list complexity), it was already pretty clear this was possible.

Thus in terms of novelty, the core contribution of this paper is really the *lower bound* on secluded partitions. This is a beautiful result geometrically, but because we do not know secluded partitions are necessary for list-replicable learning, it does not actually give a lower bound on the coin problem, nor do the authors yet have another use for the bound or related neighborhood KKM Lemma. I believe these notions will indeed prove useful, which is why I am still recommending this paper be accepted, but at the moment the learning results are a bit too weak for a stronger recommendation.
questions: questions: N/A
limitations: limitations: The authors have appropriately discussed the limitations of their work.

Comments: title: Rebuttal Acknowledgement
comment: Thank you for reviewing the rebuttal and your positive response.
Thank you for reviewing the rebuttal and your response and being positive about the work.
Thank you for reviewing the rebuttal and your positive response.
Thank you to the authors for addressing my concerns regarding fit and for committing to expanding the related work section. I still believe that this paper would be better-appreciated in another venue, but given that I enjoyed the work and the overall positive scores of other reviewers, it seems like I might be wrong and there will be enough of an interested audience at NeurIPS that I will revise my score.
I would like to thank the authors for their thorough response. Just a clarification on my comment; I didn't imply that the technical contribution of the lower bound is incremental, I do think it's an elegant construction. I meant to say that the result on its own is a bit incremental, since it implies a hardness only for a particular technique/approach for constructing list-replicable algorithms. I also agree that the new variant of the Sperner/KKM lemma is interesting, it just feels a bit disconnected from the main message/story of the rest of the paper. 

I agree with some of the points the other reviewers have mentioned, but I am still on the positive side about the paper.
We acknowledge the authors' rebuttal. We agree with the authors that the material arose in the context of replicability, has some implications therein, and may be of use in algorithmic stability in the future. I think the results are important, and will be of interest to a specialized subset of the NeurIPS community (including, e.g., myself). Nevertheless, my general opinion as stated in the review stands: the paper should be accepted, but is held back from a stronger recommendation by its scope with respect to learning.