Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma
Authors: Jason Vander Woude
Peter Dixon
A. Pavan
Jamie Radcliffe
N. V. Vinodchandran
Venue: NeurIPS 2024 poster (2024)
Keywords: replicability
learning
geometric partitions
sperner lemma
KKM lemma
sample complexity
list complexity
Primary area: learning_theory
TL;DR: This paper studies replicability in machine learning tasks from a geometric viewpoint.

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.

Replicability in Learning: Geometric Partitions and Sperner-KKM Lemma
Jason Vander Woude Sandia National Laboratories j jasonvooude@gmai..c. com com
Peter Dixon
University of Toronto, Mississauga tooplark@gmail.co com
A. Pavan Iowa State University pavanEcs. iastate. edu
Jamie Radcliffe
N. V. Vinodchandran University of Nebraska- vinodSunl. edu
University of Nebraska-Lineoln j jamie radcliffe@unl edu
Abstract
This paper studies replicability in machine learning tasks from a geometric view- point. Recent works have revealed the role of geometric partitions and Spererr' s lemma (and its variations) in designing replicable learning algorithms and in estab- lishing impossibility results.
A partition of Rd is called (k, -)-scludde partition if for every p E Rd,, an e-radius ball (with respect to the foo norm) centered at p intersects at most k members of P. relation replicable learning, the parameter i closely related to the list complexity, and the parameter is related to the sample complexity of the replicable learner. Construction of secluded partitions with better parameters (small & and large e) 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
1. We show that for any (ks, (b,,)c)clludd) partition where each member has at most unit measure, it must be that A 2 (1 + 2c)d. and consequently, for the interesting regime
[2d] it must be that < (kg,
To complement this upper bound on E, we show that for each E and for each viable & [2"], construction of a (eecuudd (unit cube) partition with = (kg,(k) (d-1, This establishes the optimality of E within a
d
logarithmic factor.
3. Finally, we adapt our proof techniques obtain 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 opposing faces, it holds for each
e E (0, 11 2. that there is a point where the open s-radius &oo -ball intersects
least (1 + 3d colors. While the elassical Sperner/KKM lemma guarantees the existence of point that is "adjacent" to points with (d distinct colors, the neighborhood version guarantees the existence of a small neighborhood with exponentially many points with distinct colors.
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 learning algorithm
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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, replicable learning algorithm should output the same canonical hypothesis, on multiple runs (with high probability). However, 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 p-replicability [31], stability [1O,, global-stability [24], and list-replicability [17.
significant insight that emerged form these works is the profound connection between geometry and algorithmic replicability [17 31 [2]. These works use geometric partitions to design replicable algorithms and employ (variants of) SpererrKKKM lemma, including Sbincare-Mirande and Borsuk- Ulam theorems, to obtain lower bound results. In particular, in [77]. the authors use the notion of to design replicable learning algorithms with small list complexity. used Operner/KKM, Poincare-Miranda and Borsuk-Ulam theorems to obtain lower bounds on list complexity and stability parameters for various learning tasks.
secluded partitions of RRd
44
The works of 13 12 17
Motivated by these connections we undertake an in-depth investigation into secluded partitions. Our first contribution is comprehensive understanding of the optimality of secluded partition constructions. Our second contribution is the discovery of a new neighborhood variant of the Spemer/KKM lemma.
Secluded partitions have found applications beyond replicable learning including deterministic rounding, Iseudodeterministicc 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 Thus, investigation of secluded partitions should be seen fundamental endeavor.
The applicability of the Spemner/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] computational complexity [25 40 16], algorithmic game
theory 44 and fair-division 37 38 5). We expect that the neighborhood variant 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 list L consisting of at most & good hypotheses with high probability. Below is a more formal definition from 177
Let X be a domain over which a family of distributions D are defined, let be a set (representing hypotheses), and err DD x H > [0, oo) be error function. A learning algorithm input e, observes m samples from a distribution D e D and learns a hypothesis err(D, h) S
H with small error
Definition 2.1 (List Replicability). Let k E N, E (0, co), and ò E [0, 1]. A learning algorithm A is (k, s, ---s replicable if there exists n E N such that for every D É D, there exists list L S H of size at most k such that for all h E L, err(D, h) S E, and
Pr. 8, E 1 *ND"
For ls E we call A k-list replicable for all E E (0, 2o) and 8 (0, 1], A is (k, 61-ssst replicable. We say that is the sample complexity of A and k is the list complexity of A.
The above definition captures the ideas over multiple at most k different hypotheses. Note that the ideal scenario is when A = 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 & non-adaptive statistical queries has a 1-list replicable algorithm.
of the learning algorithm, we may see
key ingredient in their list replicable algorithms is the geometric notion of secluded partitions that we define next. Given point ÿ E Rdd, let Bec P)) (B% (e, ()) denote the closed (respectively, open) e-ball around 5 in the fo norm.

---

Definition 2.2 ((44)) A partition P If is called a (k, seechuddd partition for every P E R", the ball (s, intersects at most k members of P. The parameters k and & are called the degree and toleancce respectively.
Remark, To avoid trivial partitions where each point is partition member or the entire IR:4 is 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 I with unit cubes is following result [4 30] improves the degree parameter substantially.
, }--slludded The
Theorem 2.3. There is (d+ 1, 2a )-scclude partition where each partition member is unit cube.
Sperner/KKM Lemma, Poincaré- Miranda Theorem, and Borsuk- 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 d-dimensional cube is the set [o, 1] For a set of colors C, a coloring a mapping X: [0, 11 + C. For color e E C, let X. denote the set of points assigned color by X- That is, X = xc) 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 has the property that for each coordinate i E [d]. the projection Ty (X.) = {xa E E X.e does not contain both 0 and 1.
Theorem 2.4 (Sperner/KKM), Given a valid Sperner/KKN KM coloring of (0, 1]4 by finitely many colors, there exists point in the closure of at least d + different colors.
3 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 v. The work of [17 showed that (ki, -paattitio of d yields k-list replicable algorithm for this task. They used a known construction of (d + 1, 3 "secluded partition of IRd from Theorem 2.3 obtain a d + 1-list replicable algorithm for this task. However, there is cost to replicability. The sample complexity of the replicable algorithm blows up by a factor of Odd) (compared to the sample complexity of the non-replicable algorithm). In general (ki, -)-selldded partition gives rise to a k--ist replicable algorithm whose sample complexity blows up by a factor of ( (compared to the "non-replicable" algorithms).
Thus constructions of secluded partitions with low-degree (k) and high tolerance (e), 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, 2/)) )sscluded partition from Theorem 2.3 Can we improve this and construct (d (d+1 1, 1, ()))
partition? Or can we loosen the degree requirement from k d 1 to k poly(d) in favor of improving the tolerance from E E (()) to E w(})) ) Our first. contribution is the following upper bound result on the tolerance parameter.
Theorem 3.1. Let N, E [0, xo), and partition of &R& such that every member has outer Lebesgue measure most 1. Then there exists some E Rdd such that B (s, p) intersects at least (1 + 2d members of P. Thus, if P is (k,,)) seecluudd partition, then k 2 (1 2e)d Consequently, if k < 2d, then it must be that E < logg(k)
This result shows that even if one relaxes & E poly(d), e E O This shows that the (d + 1, 2d secluded partition construction is near optimal in terms of the tolerance parameter, for degree dl + 1. Stated in terms of replicability, this result implies one can not hope to design list-replicable algorithms with improved sample complexity using secluded partitions approach.
Our second result is a construction of secluded partitions for various choices of the degree parameter A with tolerance parameter almost matching the bound from Theorem 3.1 Until this work, we knew
3

---

of secluded partitions for only two choices of the degree parameter k: the standard grid partition of
Fd that (2", -secluded and the (d+1, 27 partition from Theorem 2.3 We did not know secluded partition constructions for other choices of kt Our second main contribution is the construction of near-optimal secluded partitions for all choices of k.
Theorem 3.2. Let d E N and E [24)
\. [d.
Then there exists a (ki, --sccudedd unit cube partition of
R with e 2 Idg, (d41))
(N)
Note that by Theorem 3.1 E I Tog, and the above construction achieves
8dg (d+1) Thus
log, (A)
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 k-list replicable algorithm with sample complexity Ö d log"
) for any ks E [24) \ [d], per coin.
82 log"
For example, if we allow k _24, then the sample complexity is (( (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 [2] employ geometricftopologiaal tools such as Sperner/KKM KMM Lemma, Spincaré-Mirande Theorem, and Borsuk-Ulan Theorem. For example, the work 117 used Sperner/KKM lemma to establish a lower bound of d 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é-Mirande 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 neighborhood variant.
Theorem 3.4 (Neighborhood Sperner/K KKM Lemma). Given a Sperner/KKM coloring of [0, 1Js, for any & E (0, there exists a point ş E [0, 1]d such that B% (e,P) contains least (1 + 3e) points with distinct colors.
SPemne/KKM Lemma(Lemma 2.4 states that in valid coloring of the d-dimensional hypercube, there is point ÿ whose closure has at least dl + colors. That is, for every > 0, the s-ball around p intersects at least d + 1 colors. Our theorem is a quantitative generalization of this result. It states that the s-ball around ş" intersects exponentially many colors-at least (1 + }e)d many colors.
Related Work
One of the first works that studied replicability in the context of learning algorithms the seminal work of Bun, Livny, and Moran [10); they used the term global stability to capture this notion. learning algorithm A to be (n, gglobblyy stable with respect to distribution D if there is a hypothesis h such that PrswD" (A(S) f) 2 1) here 7 is called the stability parameter. They used the notion of stability, combined with the work of B. to obtain the equivalence between online learnability and differentially private PAC learnability. Ghazi, Kumar and Manurangsi [24] generalized the notion of stability to pseudo- pseudo-global stability and list- list-global stability. Impagliazzo. Lei, Pitassi, and Sorrell 33 introduced the notion of p-replicabilitty 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) replicablia Chase, Moran and Ychudayof (13] related the notions list complexity and stability. They established that learning task has list complexity 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-Iearnability of classes with bounded VC-dimension. In [1] the authors use Borsuk- -lam 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 pxeudlodeterminiso.. This notion was introduced by Gat and Goldwasser (23 and has been extended to notions called multi -eepdddttemmmiiiinnn (66 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 [9 33 18,, and the work of [ studies replicability for optimization problems. Other very recent works include those reported in 29 32 A notion that related to replicability is that of reproducibility. The article by distinguishes these two notions.
41
5
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-Minkowss Inequality and ideas from the standard proof of Blichfeldt's theorem. The generalized Minkowski sum of sets (A+ + B f a b: ā A, B))
inequality gives a lower bound on the measure of
based on the measures of those sets.
We use the following version of the statement from [22 Equation 11]. Here m(A) is the Lebesgue measure of set A [ IR
Theorem 5.1 (Generalized Mounn-Minkowski Inequality). Let E N and A, B C Rd be Lebesgue measurable such that A + B is also Lebesgue measurable. Then
m(A ( + B) 2 m(A)² m())
A common technique in the proof of Blichfeldt's theorem is to use an averaging argument to show that if set is covered by a large family of other sets, then some point in A is covered many times.
5.1 Proof Sketch of Theorem 3.1
We present the high-level ideas and the intuition behind the proof of Theorem 3.1 In the appendix, we provide complete proof. Figure D serves as visual.
The goal is to find some point p E Rd such that B (c. intersects least (1 + 2=)4 members of the partition. Instead of directly trying to establish this, we take critical change of perspective: for any F E Rd and X P (or really any X S Rd), it holds that B% (e, p) n X * if and only if p Uzex (E, H). Thus, what we do is to "replace" every member X of the partition with the enlarged set UsEx B% (s, T) and try to find point that belongs to at least (1 2 of these enlarged sets. To achieve this, we take inspiration from a common proof of Blichfeldt's theorem- specifically, the following result which says that if we have collection of sets A1. A2, Ag,.. which are subsets of another set S, then there is point in S occurring in multiple A,S provided together the As have enough volume/measure. We in fact give a lower bound on the number of A&s which such a point belongs to. The following is the formal claim of this known result.
Proposition 5.1 (Continuous Multi- Pagti-Pigeenhole Principle). Let d E N and S C Rd be bounded and [E m(A)] Then if
measurable. Let A be a family of measurable subsets of S. and let k
m(()
k < oc, there exists ő E S such that p belongs to at least k members of A. (And if k = oc, then for any n E N there exists (m)) S such that p(") belongs to least n members of A.)
There is an immediate issue we have to deal with to be able to use Proposition 5.1 for ap- plication. We would like to take A to be the indexed collection of enlarged partition members: A {Usex B% (E, } XEP: but then all we know is that each of these is subset of S = Rd which is not bounded. This is simple enough issue to deal with using a standard measure theory technique of considering instead a sequence S, S2, Sy.... of sets which are bounded and get larger and larger limiting
so that U S, Rd, work with each of these sets individually and then try argument pass the result back to S = Rdd. Specifically, we will take S, [-n, mx] illustrated in the first two panes of Figure [ The third pane of Figure Tillustrat that we will specifically consider the partition of Sn, induced by P which (X O nA: X < P and X n S., + 0}. Then for each S, we consider collection A, of the enlarged
denote by S... That is, the induced partition S,, is the set
members of the induced partition: An {Ay Jyes, where Ay def Uger B% (E. 17). Note that each
Ay is subset of Sy def, [I (n= + E), c]d as in the fourth pane of Figure
5

---

70000
Figure 1: Pane 1: A partition of RR2 Pane 2: We consider only members of the partition which intersect [-n, n)]2. Pane 3: The partition that induces on [-n, n]2. Pane We enlarge each member by placing an e-ball each point of the member. These enlarged elements still contained within [-(n + e), + e]2. Pane The sum of areas of the expanded members is "significantly" more than the area of [-(n (n E), e)?.
However, there remains one other issue to deal with to utilize Proposition 5.1 for each we have to have some lower bound on the expression LAyeA, m(Ay) We know that m(S)))) = (2(n + =))²
m(S)) and using the fact that S, is partition of S, [-n,, nj]d we have the following if S,, is countable (meaning finite or countably infinite):
Σ m(Ay)
Σ m(Y)
m(S,),
AAe
YES.
YES
but this is not nearly good enough, because it just gives
ΣAYEA, m(A) m(S))
(Sw) ((,))
(2n) (2(n + E))d
d' 12 n
=1
whereas we want it 2 (1 + 2d)d. Basically, this lower bound is not good because we did not account for the fact that each Ay A, is enlarged from Y S,. Thus, we want some way give for each Y E Sn, lower bound on the measure of the enlarged set Ay. One might observe that enlarging with an E-ball looks something like scaling by a factor of + E, and since the Lebesgue measure (i.e. typical notion of volume/measure in R has the property that scaling by (1 + E) increases the measure by factor of (1 + e)d, we might be able to show that the enlarged version of each member increases by factor of (1 + e)d (which is basically what we are looking to get).
Iff S. is uncountable, one of the equalities Eyes, m(Y) S m (Lyres, y) by B.2 in B
chain becomes the wrong inequality we get that

---

This intuition holds, though the actual reason is not related to scaling, and is dependent on the members having measure most 1. Rather, we use specialized adaption of Theorem 5.1 show that
(1) holds. Now that have dealt with both issues that arise with trying to apply Proposition 5.1 can consider a fixed n and can continue. We proceed in two cases: (1) the interesting case in which S has only countably many members, and (2) the nearly trivial case in which the partition S, contains uncountably many members. In case (1) we have
m(Ay) 2 m(Y) (1+ 28)d
EAYEA, m(Ax)
Eves, m(Ar)
(Re-index)
m(5))
m((h)
Eves, [m (1+ 2
2
[Equation] I
m((k))
(1 + 22)d ExES, m(r)
(Linearity of summation)
m(Sh)
(1+ + 25)d (UYEEs, Y)
(Countable additivity of measures)
m((h) (1 + 2e)" (m(S))
(S, Lyyss, Y)
m(S))
(1 22)a
n
mi (
)a as above)
11 E
(5
m+t
Since (for fixed d and E) we have lim
n = 1. then lim + 2z)d n++
n+s
(1 + 25)4, so because there is a ceiling involved, we can take N E N to be large enough that [(1+22) so by Proposition 5.1 there is point ş E Sy that is contained in at least (1 + 2s)d many sets in AN, and by our change of perspective, this point has the property that 0 (e, p)) intersects at least (1 + 2s)d many members of P.
(1 (1+
N
N+E
In case (2) where some Sx contains uncountably many members, then completely ignore the
lower bound for m(Ay) ) in Equation I because it might be that lots of members (possibly all of them) have measure 0, and so that bound only tells us that m m(Ay) 2 0. Instead, note that Y is at least non-empty, so contains at least one point y, and thus Ay 2 B (c.
[y: c, y1 + e].
and so m(Ay) 2 (2e)d. Thus, EAyyeyy m(Av) = co, so by Proposition 5.1 there is a point m(S))
F E 5ky that is contained in at least (1+ (1+22s) 2s) many sets in Ay. and by our change of perspective, this point ş has the property that B% () intersects at least (1 + 2e) many members of P.
5.2 Proof of Theorem 3.2
The partitions that construct, establish Theorem 3.2 of very natural form: build 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 partition is (k, eeecuudde then the partition is trivially (K', e'ecuuedd We refer to this property as the "monotonicity" property.
increase k' and decrease e' and
Definition 5.2 (Partition Product). Let di,..... dn E N and Pi...., Pn be partitions of IR.1 .R.,,. respectively. Letting d = Σ dn, we define the product partition of Rd as
m
1
P def
II
Xx: X, EP,
7

---

where IT:= X; is viewed as subset of R
We specifically stated that I X; is viewed as subset of IR because technically it is subset of IT. Rd, but this is naturally isomorphic to R RE d. For example, technically, if di d2 d3 2, then the elements of I[= Rd: are of the form (2)) (ara: ra), (1r, sa)), but this is trivially isomorphic to R by instead considering the element as (21 22 2 24 25, 46)
We can now show that if we take a product of partitions, and we have a guarantee for each P; that it is (kg, Ej --ecluudd then we can guarantee the product partition is (ke, )--selluded where ls is the product the k;'s 's's and ε is the minimum of the E,'s.
Proposition 5.2 (Product Partition Seclusion Guarantees). Let N. For each index i [n], let da kig N, E (0, oo) and Ps be (Ki,, ESeeuuudd partition of IRo, Then the product partition p -==1 P. is (k, seelluddddd partition of I2 where d = Ei= di and k II Ky, and E min Ei.
m
Proof Sketch. The basic idea is that for any point ø E R., we consider how many members of P intersect (p). Conceptually we think of sequence (p of points where the ith point p belongs to Rd: Because we are working with the fo norm (that is the norm used by the definition of secluded), the ball around pis is the product of the balls around each pt which is smaller than the product of E, balls around each p() because we chose ε as the minimum size. Thus, if the ball around p inteersects a member X of the partition P. then conceptually viewing as a sequence (X,)== where X; is member of Pr it must be for each E [n] that the ball around p( intersects X; (and thus so does the E; ball since E; 2 E). This means (for each E [nl) that X, is one of at most k; members of P. because at most k; members of Pi intersect the s; ball around p(0) (by definition of P, being (ki, &a )ee-ceedddd) Thus X one of most II k; members of P. That is, there are at most k members of P that intersect the e ball around p which is the definition of P being (k, ssseeluddd
Utilizing the construction above, we will now take the unit cube partition from Theorem 2.3 for each Rd and take their product to obtain a new partition. Since the dimension of each de is smaller than the dimension d, this allows us get a larger value of E; for each partition, and thus larger value of e for the partition of IR than if we had used one of the original partitions. The price we pay for this that the value of l also increases.
We establish the following lemma.
Lemma 5.3. Let d E N and d' E [d], There exists a (keeluue unit cube partition of Ed where == (d' + 1) $1 and 28
Proof. Let 11 By 44 let P' be (d' + ) unit cube partition of Rdd, By
Proposition 5.2 P - II P' is (k, 8) secluddd unit cube partition of Rn-d' where k: = (d' + 1)" and & zσ Since n d' I d' 2 d, this trivially (by ignoring extra coordinates) gives partition of Rd with these same properties which completes the proof.
Finally, we are ready to prove Theorem 3.2
Proof. Let d' E [d] be the minimum integer such that (d' - 1)1 S k and let e = 1
2 By
Lemma 5.3 and monotonicity, let P be a (k, e-secluddd unit cube partition of Idd Now we prove the bound on E in two cases: either d' 1 or d' 2 2.
In the case that d' = 1, then 1/2 and 1: > (d' + 1) 11 2d and by hypothesis & < 24, so we have equality and we conclude that
log,
d/2
8 lloga (d <
< =
4d 4d loga (d +11 4dlog, (d +
8. 2
which proves the bound in the first case.
8

---

In the other case, we have 2 2'
122, 2. = d' - >>> 0 and ò =
Let d"
1>>
1 2d
Note that
2d d' -1
2d
d'
2
so 2 26. By our choice of d' and because d' < d', it must be that & (d" + 1) # Noting that
d d
I d" + 1 d'
d+d"
2d we have
d"
k 5 (d" + 1) * - (d" + 1 (d" + 1)4dd S (d" + 1)dds S (d 1)8de
By taking the logarithm of each side and solving for e, obtain the desired result that > log, (k)
8d log, (d+1)
5.3 Proof Discussion of Theorem 3.4
Interestingly, the proof of the neighborhood Sperner/KKM lemma relies on the techniques developed to prove Theorem 3.1 for each color C. let X. be the set of points that are colored c. We union an s-ball at each point in X., to obtain an enlarged version Ax, of X... Now, as before, by the Continuous Pigeonhole Principle (Corollary 5.1 ) there is point that belongs 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 't arise in R
In the discussion in the proof sketch of Theorem 3.1 the enlarged set was not contained in the original region (denoted S,,) and we needed to consider larger region (denote S²,) to contain them. In Re we could deal with this via a limiting argument so that the ratio of the volume change m (Sx5)/m) (S.) tends to (i.e. it became negligible when ceilings were involved). If one enlarges every color in unit cube 1-2 2' 11d in the same way, the measure of each color is guaranteed to increase by a factor of 21) as before, but also the smallest set that contains all of these enlargements is the unit cube - =]" which increased in measure by a factor of (1 + 2s)² 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-Minkowe inequality tell us no additional information.
We resolve this by employing a trick of first extending the coloring directly to 1 -,,-,,,, =] in 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 orthants) and still have the enlarged color set contained in [-] E, + e)d This means we end up knowing that each modified color has increased in measure by at least a factor of (1 + ze)d and that the modified containing region has not changed in measure at all.
6 Conclusion and Open Questions
This work is a comprehensive study of secluded partitions. Prior to this work, it was known that the (d + 1, ()))))))sclluee) partitions of 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 kt The present work showed that these constructions 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 l between + and 2d
optimal in up to a logarithmic
This work raises few open problems. At first glance, it might seem to complete the study of secluded partitions; however, it only establishes mear-matching bounds for the foo norm. In Appendix (A.8) we present upper bounds on in terms of k for f, norms, but no known constructions approach these bounds. Developing nptr-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 eplicabillty--anmen complexity blow-up. This work showed that this blow-up in sample complexity is unavoidable in list replicability one uses secluded partitions method. Can we establish generic lower bound on the sample complexity of list replicable learning algorithms?

---

While Theorem 3.4 gives new "neighborhood" variant of the Sperner/KKM lemma, the color bound of (1 + fe) is not tight for small because the standard cubical Spemer/KKK 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 special case. Finally, finding applications of the neighborhood Spemner/KKM lemma is an interesting research direction.
7 Acknowledgements
We thank the anonymous reviewers for their valuable suggestions, which improved the presentation of this paper. Vinodchandran's 's work is partly supported by NSF grants 21 2130608, 2342244, and UNL Grand Challenges Grant. Pavan's work is supported in part by NSF grants 2130536 and 2342245. Jason Vander Woude's s contributions were made during his time at University of Nebraska, Lincoln and was partly supported by NSF grant 21 2130608.
References
[1] Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil I. Shamir. Re- producibility in optimization: Theoretical framework and limits. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022,
NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[2] Dan Alistarh, Faith Ellen, and Joel Rybicki. Wait-free approximate agreement on graphs, March 2021. MXXKv:2103.0894 [cs].
[3] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Anmual ACM SIGACT' Symposium Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860. ACM, 2019.
[4] Martin Biely, Peter Robinson, and Uirich Schmid. Easy Impossibility Proofs for k-Set Agree- ment in Message Passing Systems, March 2011. arXiv: 103.3671 [es].
[5] Vittorio Bilò, Ioannis Caragiannis. Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Do- minik Peters, Cosimo Vinci, and William S. Zwicker. Almost Envy-Free Allocations with Con- nected Bundles. Games and Economic Behavior, 131:197-2211 [cs, econ].
January 2022. arXiv:1808.0944 09940
[6] Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asyn- chronous computations. S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Awenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego CA, USA, pages 91-100. ACM, 1993.
[7] Sergey Bravyi, Natalie Parham, and Minh Tran. Identity check problem for shallow quantum circuits, 2024.
[8] L. J. Brouwer. Über den natürlichen dimensionsbeerrfff. Journal für die reine und angewandte Mathematik (Crelles Journal), pages 146 152, 1913.
[9] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 520-527. ACM, 2023.
[10] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Sandy Irani, editor, 61 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 389-402. IEEE, 2020.
10

---

[11] J. Y. Cai, R. Lipton, L. Longpré, M. Ogihara, K. Regan, and D. Sivakumar. Communication complexity of key agreement on small ranges. In STACS, pages 38 38-49, 1995.
[12] Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff. Local borsuk-ulam, stability, and replicability, 2023.
[13] Zachary Chase, Shay Moran, and Amir Yehudayoff. Replicability and stability in learning. CoRR, abs/2304.03757, 2023. 2023.
[14] Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci., 410(44):4448 44568,444666444 2009.
[15] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing nash equilibrium. SIAM J. Comput,, (9(1): 39(1):195-259 2009.
[16] Peter Dixon, A Pavan, Jason Vander Woude, and N.V. Vinodchandran. Pscudodeterminism: promises and lowerbounds. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1565. ACM, 2022.
[17] Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran. List and certificate complexities in replicable learning. CoRR, http//304.02240, 2023.
[18] Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[19] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[20] Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, April 1999. Google-Books-ID: N8iVDWAAQBAJ.
[21] Anat Ganor, Karthik C. S., and Dömötör Pálvölgyi. On Communication Complexity of Fixed Point Computation, May 2022. arXiv:1909.1000 10958 [cs].
[22] R. J. Gardner. The Brunn-Minkowski inequality. Bulletin of the American Mathematical Society, 39(03):355 406, April 2002.
[23] E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC), 18:136, 2011.
[24] Badih Ghazi, Ravi Kumnr, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pages 20172-20188 20144, 2021.
[25] Paul W. Goldberg. The Complexity of the Path-following Solutions of Two-dimensionall Sperner/rrouwer Functions, June 2015. arXiv:1506.0455 048880 [cs].
[26] Oded Goldreich. Mutti-pseeuooleermmnniiicc algorithms. Electronic Colloquium on Computa-
tional Complexity (ECCC), 26:12 2019.
[27] Ofer Grossman and Yang P. Liu. Reproducibility and pscudo-determinismn in log-space. In Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego California, USA, January 6-9, 2019, pages 606 620. SIAM, 2019.
[28] Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. ACM, 46(6):858-922 1999.
11

---

[29] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in high dimensional statistics. CoRR, 022222406.02628, 2024.
[30] William M. Hoza and Adam R. Klivans. Preserving Randomness for Adaptive Algorithms. 1r11.01611.0078, [cs], June 2018, arXiv: 1611.00783.
[31] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in Learning. arXiv:2201.084400 [cs], January 2022. arXiv: 2201.0843..
[32] Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Replicable learning of large-margin halfspaces. In Forty-first International Conference on Machine Learning, ICML 2024, Viemna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[33] Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[34] Guy Kindler, Ryan O' D'Dnnlll,, Anup Rao, and Avi Wigderson. Spherical Cubes and Rounding in High Dimensions. 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 189-198, 198, Philadelphia, PA, USA, October 2008. IEEE.
[35] Shiva Kintali. Scarf is Ppad-Complete, May 2009. arXiv:0812.160) [es].
[36] Henri Lebesgue. Sur non-applicabilité de deux domaines appartenant respectivement des espaces än etm+p dimensions. Mathematische Annalen, 70(2):166-155 168,666668, June 1911.
[37] Frédéric Meunier and Francis Edward Su. Multilabeled versions of Sperer'' and Fan's 's lemmas and applications, May 2019. arXiv:1801.02044 [cs, math].
[38] Frédéric Mcunier and Shira Zerbib. Envy-free cake division without assuming the players prefer nonempty pieces, January 2019. arXiv:1804.004:: [cs, math].
[39] Susumu Nishimura. Proving Unsolvability of Set Agreement Task with Epistemic ma-CCaluluus May 2022. arXiv:2205.0644 05642 [cs].
[40] Christos H. Papadimitriou. On graph-theoretic theoretic lemmata and complexity classes (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume 1I, pages 794 801. IEEE Computer Society, 1990.
[41] Joelle Pineau, Philippe Vincent-Lamarre, Koustuv Sinha, Vincent Lariviere, Alina Beygelzimer, Florence Alche Buc, Emily Fox, and Hugo Larochelle, Improving reproducibility machine learning research(a report from the neurips 2019 reproducibility program). Journal of Machine Learning Research, 22(164):1-20, 2021.
[42] Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449 14811144449114,,,,, 2000.
[43] Waclaw Sierpiáski. Sur question de mesurabilité de la base de M. Hamel. Fundamenta Mathematicae, 1:105-111, 1920. Publisher: Instytut Matematyezny Polskicj Akademii Nauk.
[44] Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Geometry of rounding, 2022. 10.48550/arXiv.22 1..66444.
12

---

A Complete Proofs
A.1 Notation
The following is a list of some of the notation we will use in this paper.
We use N denote the natural numbers starting with
We continue to use B1-1 (e.p), ( p). Bax (e, p). and (e, as before.
For two sets A, B [ Rd we write A + B to represent the Minkowski sum A +
def aa A, B.B). We also may write ā + B to mean {a {a be (a+b:bE B) for
some fixed vector a.
We will use 2p 1.d represent the Borel/Lebesgue measure of the unit radius ball in R with respect to a general norm ||-||. This is normalization factor that appears in some results.
A.2 Proof Theorem
In this section, we present a complete proof of 331 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.
A.2.1 Prerequisite Results
In this section, will deal with arbitrary norms of Rd We point out the well-known fact that all norms on Rd are equivalent in the sense that they all generate the same topology on R4. Given two norms ||-||* and I1-11% on Ted there exists fixed constants Cd, Ca E (0, oo) such that for all vectors 7 E [Rd, holds that cal| S || < Cal Thus the collection of open sets in g is the same no matter which norm we are using. This also means that the Borel and Lebesgue r-algebras on Rd are the same no matter which norm used, and thus balls with respect to any norm on R2 measurable.
We begin with four simple facts. The first fact will later allow to pass result through limit since the answer will be an integer.
Fact A.1. For any a R, there exists 7 IR such that y a and [T] [a]].
The next fact says that the Minkowski sum of set X and an open ball at the origin can be viewed as union of open balls positioned each point of X.
Fact A.2. For any normed vector space, given a set X and & E [0, oo), then
X Bi (c, 0)
U Bd (e.
FEX
The same be said replacing open balls with closed balls.
The third fact says that we can decompose ball into a Minkowski sum of two smaller balls. Fact A.3. For any normed vector space, and any B (0, oo), it holds that B (a, 0) (8,0) Bi (a 8)
The fourth fact, while also very simple, 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 e-ball located at ÿ (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 e e-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 O, the following are equivalent:
1. Bi Bi, (E. 7X nx
2. pe X + +,,,,
13

---

The same can be said replacing both open balls with closed balls.
Now we introduce the result which is the connection to the mentionentin key change of perspective. The result says to consider a bounded, (measurable) subset S S Rd (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 (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 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: every point of S is covered only n times, then the total measure of members in A is at most n m(S), so the ratio of total measure in A the measure of S large, then n must also large. This more general version is sort of continuous multi-pigeonhen principle.
Proposition A.1 (Continuous Milti-Pige Principle). Let d E N and S C C be bounded and measurable. Let A be a family of measurable subsets of S, and let k = EASA (MA) Then if
mIs)
oc, there exists Tī E such that p belongs to at least k members of A. (And if k = 00, then for any E N there exists n S such that pT)) belongs to least members of A..
We first encountered this result 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 '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.. we need lower bound on the measures, and we can obtain one using the generalized Brunn-Minkowe
inequality stated below.
Theorem A.5 (Generalized Brumn- Mrunn-Miikkowsii Inequality). Let d E N and A, B,BC C Rd be Lebesgue measurable such that A + is also Lebesgue measurable. Then
ml A + B) > m(AA} + m(B)3]
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 Lebesgue measurable not 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 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 It need the assumption that A is measurable.
Lemma A.6. Let d E N and let Id be equipped with any norm I1-Il- Let Y C Rd. and (0, Then Y Bi,, 0) is open (and thus Borel measurable), and m(Y + (c,, 2
(Monc(Y) ( + (v)),a)a)
Proof. By Fact A.2 for any e" 00), Y + (E, USer B (E"
(e".g) which is union of open sets, is itself open and thus Borel measurable. Now, for any E' E (0, observe that by Fact
A.3 B (e, 0) Bi (s s' o) ( o) and thus, this sum is measurable because it an open
ball. Using this equality and the associativity of the Minkowski sum, we have
Y + B (e, + [i (s- - 8' B B (e',0) = =[Y Bi c',))] B (E'00'
14

---

Thus, we have the following chain of inequalities (each justified after it is stated):
m (Y Be, m ([ Bi (5 e0, Big (s', 0)
(Open, measurable, equality above)
Bi Bi 60)) + BP (E,))))))))
The above comes from the Theorem A.5 noting that as demonstrated above, terms of the sum Y ( =0) and Bi (E', 0) are open and thus measurable, and the same holds for the sum itself (y (e. We continue.
Mout ( + m (Bi, (s', 0)) #) )
The 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 S Y Bi. Bi,,(E', (e',0), 0), we get the inequality above. Continuing, we have the following:
Mout (Y) m (6' Bi B1,((1,)) (..0))))))))))))))))
(Scaling of norm-based balls)
Mous (Y) ((E//d 11yy..m. m BB (1, (1.
(Scaling for Lebesgue measure)
-mont (Y) + (
(Algebra and o 1-i.d = m (B, (1, (),
def
Since the inequality above holds for all s' E (0, it must also hold in the limit (keeping d and Y fixed):
m (i, z lim c' (mone (Y) +e' (v)n))))) ( = (moue (X) + ()))))))))
which 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 inequality that 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-/d add to get the no larger expression x(1 + ar)..
Lemma A.7. For d E [1, xo), æ E [o, 11, and a [0, 2o), it holds that (x + aa 2 x(1 + aa)
Proof. If x 0, then the result is trivial. Otherwise x E (0, 1), so l/dd E (0, 1]. Because 2
2:/4 a.
= (so// (1+ αK 1/d + a:)==(10
1//d ) = x x2/d
2 x01 + a)
A.2.2 A generic result for all Norms, and Theorem 3.1
We establish Theorem 3.1 by proving the following result.
Theorem A.8 (e-Neighborhoods for Measure Bounded Partitions and Arbitrary Norm), theorem Let E N. M E (0, oo), and P partition of Rd such that every member has outer Lebesgue measure at most M. Let TRd be equipped with any norm ||-1]- For every & E (0,oo), there exists Φ E TRd
such that Bo (E. intersects at least k = (1+ ("Lna) 1/d d' members of the partition where
def m Br (1, (1, is the Lebesgue measure of the ||-II unit ball.
"p
15

---

Proof. Throughout the proof, all lengths will be with respect to ||-I|, so we will eliminate the clutter by neglecting use the |1-I| subscript anywhere the proof. We will also be working in a single dimension throughout the proof, so we also drop the d subscript from e throughout.
Consider the following for each n E N. Let Sn. = (n, 0) and S. = (n = S, + B (e, 0) and S be the partition of S, induced 2 by P. For each Y E Sn, let Cy = Y + (s, 0). By
Lemma A.6 Cy is measurable, and m(y)) 2 Mout (V) + e ..) Also observe that Cy 3 S.
Now consider the following inequalities:
m(Cr)= 2 Mout (Y) + vd
(Above)
Midd
Mout (Y)
E va MI/d
d
(Algebra)
Mi/d
((maus (Y)
M
(Algebra)
M
Midd
Mout (Y)
u
M
A.7
since
Mous (Y)
E
[0, 1))
M
Mi/d
e vž
Moat (Y)
1
(Simplify)
M1/a
Informally, the above shows that for each Y Sn, the set Y + (E, ()
has substantially more (outer) We will extend this to unsurprisingly
measure than does- specifiaell a factor of 171
show that this implies that {r (s, YES.,
also has this same factor more (outer) measure than S,, does, observing that S₁ has total (outer) measure of about mn(S) since S, is partition of S, (any discrepancy due to moa-ueasurable members S,) Formally, we claim that there exists a finite subfamily F, S S, such that
8 v. mmSs))
Σ m MY+ ((e,))))))) 1+ YEA.
Mija
To see this, first consider the case that Sn has infinite cardinality. Let Fn C. Sn be any subfamily of finite cardinality at least
[
a.rd Mira
-m(S)) -ेे This gives
Σ m mr BB(,))))) YEF.
Σ (B))),0)
YEF.
LL. s = 1. : X and X S, * 0}. That is. S is the partition of S,, obtained by intersecting every member of P with the domain S, and keeping those that have non-empty intersections.
16

---

where this inequality is because Y B+, is a superset some translation of 8 (E. 0) since Y Y 0. Continuing, we use standard fact that m (e, - m (e (1,, ea. m [ (1, =
Σ EXU
YET
E. vá d
1
((()))
(Cardinality of F,))
M1/d
d
vå M1/a
1
-m(S..)
(Simplify)
Now consider the other (more interesting) case where S,, has finite cardinality 2 Take F, = Sn so that
Σ m (V+
Σ m ( (e,,
i = S.))
YEF
YES
e v
Σ YESK
Mout (Y)
+
(Above)
Mifa
+ e nn
Σ
Mout (Y)
(Linearity of summation)
Mija
YES.
e va
Ur
1
Mija
Mont
YES,
where the above inequality is due the the countable subaddativity property of outer measures which states that a countable sum of outer measures of sets at least as large as the outer measure of the union of the sets, In the last step we get
e vå )a -(1+
MI/a m (Sw)
drer, Y = S, is measurable)
Thus, regardless of whether S, has infinite or finite cardinality, there exists finite subfamily Fn C Sn such that
.. (v+++ (Y+BB (c, 2 1+ Mi/a m(S)).
Σ m YEF.
Fix such subfamily Fu. and let An = {Y (2, ()) J
YEEF. be family indexed by F... Note that
for each Ay def Y Be, 0) E An, since y
S S, = (n, 0), we have Ay S S, + B", Ū) = S
In fact this case also works if S., is countable even though we have already dealt with that case. *e require this an indexed family rather than just a set, because possible that there are distinct Y, y E Sn, such that Y + (e, Y' + (e,
17

---

Thus, by B. there is point p(a) E Sh which belongs to at least ky -may sets in A,, where
c.và Mi/d
Ever, m (Y+
1 +
m (S.))
kn m(S))
(Above)
m(S))
d
BP (n, (n,
va
1//a
Ba n + &, 0)
m
(Def'n of S, and S),)
vd M
nd
(Standard scaling fact)
(n + B)d
E uu +
n
(Simplify)
MI/a
Since p(a) belongs to at least ki -mny sets in An, this by definition means that there are at least k, -any sets Y E Fa such that p(a) Y (e, 0), by F.ct we have B (s, pfm) o For each such Y (since Y E Fn S S,). there is disting Xy E EP such that Y C Xy and thus Xy n (E, 0) * 0 showing that there are at least kn -any sets in P which intersect 83 (E,
For the last step of the proof, we perform limiting process on n. By Fact A.1 y E such that
1 +
s-ud M1yd
and [>]
s.0.
Then, because
Mr
E vu 1
n
8 Vd 1+
lim kn
lim
Mi/d
Mi/d
7/
we can take Ne e N sufficiently large so that
d
g. M1/d
N
kN 2
1
N
+
Then considering the point NNN) we have by the choice of y and the fact that kw is an integer that
E va
AN = KN 2 h
(1
Mifd
(1+
showing that (s, intersects at least AiN 2
cnd M7ra
members of P as claimed which
completes the proof.
Now Theorem 3.1 follows as simple corollary of A.8
Proof. Consider the loo norm and M noting that for each d E N. V boodd 2d (i.e. the volume of the fx unit ball in dR is 2d).
Then by A.8 there a point ş E IRd such that (E, intersects at least
1/d d
I ++e
U ("l M
1/d
1 1
2d T
= 2s)
'ee are taking X in B.5 to be S" in this proof, and taking μ to be m and taking A to be An. We have that E AEa m(A) < so because [Aml [F,] is finite, and each A A., is subset of S so has finite measure. 'Le. for Y * Y S. we have that Xy,Xy= E P and Xy * Xy so this mapping Y's to X's is injective, so we have at least the same cardinality of X with the desired property as Y's with the desired property.
18

---

members of P, and thus trivially the closed ball (e, p) does as well. Thus, if P is (k, e--seludeed (meaning by definition that for every p E IR it holds that 3x intersects at most & members of P) then it must be that & 2 (1+ + 28)".
For the consequence. ls - 2 then this implies ε I 3. Then taking the logarithm of both sides of our inequality and using the fact that log, (1 + 2x) 2 æ for x E [O, 2 (see footnote p we have
loga(k) (k) 2 d dllog + 2e) de
showing that E (R) d
We state the following interesting corollary when k(d) is polynomial.
Corollary A.9. Let (Pa) be sequence of (k(d), s(d) -secluded partitions of R2 such that every member of each Pa has outer Lebesgue measure at most 1. If k(d) E poly(d) then E(d) E O (and) (where the hidden constant can be taken to be anything exceeding the polynomial degree of k).
Proof. Since k(d) E poly(d), then there are constants C, n such that for sufficiently large d, we have k(d) & Cd which for sufficiently large d is less than 2d so by 3.1 for sufficiently large we have
E(d) - In(k((d) n Cn())
E In(d)
d
More specifically, for any n' have for large enough d that (n' n) In(d) 2 mln(C), for large enough d we have
n In(dd) n n[ln(C) + In(d) (n' (n' In(d) + n' In(c)
<(d) S
d
d
showing that the hidden constant can be taken to be any n' larger than the degree n of k.
A.3 A Family of Near Optimal Constructions
The partitions that we construct in this section are of a very natural form: we build a partition of a large dimension 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: -seccldee then we can increase k to k' and decrease & to e' and the partition is trivially (k', ( -scc-uddd
Observation A.10 (Monotonicity in k and E). Let d E N, k W' E N with 2 k, e, E [0, oo) with S E, and P a (k, e) -ecluded partition of R.d. Then also (K, ('eee'-selluded partition of Rid.
Proof. Since P is (..ee)eseludee by definition every e-ball intersects at most k members of P, so trivially every (no larger) gx ebbll intersects at most k 2 i members P.
We will frequently refer to the above observation just using the phrase "by monotonicity, P is (K', e') "secluddd
Fact A.11 (Trivial l for Unit Cube Partitions). Let d E N, E [0, oo), and P be any unit cube partition of Rd. Then P is (k, e)-seluuded for k = (2 + 2=)dd.
Proof. Consider any point 7 E Rd, Observe that for any X E S, X is a unit cube, so diamie (X)
so if intersects B.c (e. p). then C Bax + +)
Because (1) each X E P has measure 1, and (2) every pair of members are disjoint (because P is e, +
= p [-1 1,,1-,,1: 1 =]d is (2 + 2z)d it follows that at most [2 + 2 members of P are a subset of B (1 + +. and thus at most [(2 + 2=
partition), and (3) the measure of B +
members of P intersect (E, which shows that P is (k, -secluded for k [(2 + 2=) as claimed.
1 'One can verify that the function log, (1 + 2x) - x concave on its domain (- oo) using the second derivative and note that it at and x (which is why the base 4 logarithm was chosen) it non-negative [0, 1
19

---

A.3.1 Construction
Definition A.12 (Partition Product). Let di,...,dh dn E N and Pi...., ......P,. Pn be partitions of R4 , Rd respectively. Letting Ei=1 dn we define the product partition of [ as
P. def II 1=1
i=1
where IT= X; is viewed as subset of R2..
We specifically stated that IIm X; is viewed as subset of IRd because technically it is subset of I Rd, but this is naturally isomorphic to R R_:..d; d: For example, technically, if d1 d2 d3 2, then the elements of IT= Rdd are of the form (2), (2a, sr4,, (1s, za)), but this is trivially isomorphic to R by instead considering the element as (21, 22, 2a 24 25, T66-
Also observe (shown below) that if the original partitions were unit cube partitions, then the product partition is also a unit cube partition.
Fact A.13 (Unit Cube Preservation). Ifd..... dn E N and Pi...., Pn are unit cube partitions of Rd ................................ Fdd respectively. then IT= P, is also a unit cube partition.
Proof. Each member of II Ps is of the form II X; where X; E P.. Since P; is unit cube partition, each X; is product of translates of [0, 1), and thus I[= X; is also a product of translates of [0, 1), so the member is a unit cube.
If all partitions Pi...., Pn "efficiently computable" in the sense that given arbitrary point, E e R4 there is an efficient algorithm that computes representation of the member of P. containing I then the product partition also "efficiently computable" because given some point the member that it is contained in can be found by determining which member of Pi the point ( is in, and independently determining which member of P2 the point (Wli=dd +d2 +11 is in, etc.
Rd
The member I P. that contains ÿ is just the product members. This is an important property for using partitions the basis of rounding schemes because algorithm must determine which member/equivalence class point is in (even if just implicitly). Because the partitions of drl are "efficiently computable" so are the partitions constructed here.
We can now show that if we take a product of partitions, and we have a guarantee for each P, that it is (k,, e --)selduddd, then can guarantee the product partition is (k, -scclluee where k is the product the k,'s 's and E is the minimum of the E s.
Proposition A.2 (Product Partition Seclusion Guarantecs). Let n E N. For each index E [n], let d, h; N, E E (0, oo) and P; be (ke, -e)-uuddd partition of Rd., Then the product partition P -==1 Pe is (eee)_ee partition of Rdd where d Ei=1 di, and k II k. and 8 min Sz.
Proof Sketch. The basic idea is that for any point ø E Rd, we consider how many members of P intersect (p). Conceptually we think of P as sequence (5()) of points where the ith point 9 belongs to R Because we are working with the for norm (that is the norm used by the definition of secluded), the ball around is the product of the e balls around each pto) which is smaller than the product e, balls around each gt because we chose e as the minimum size. Thus, if the ball around p intersects member X of the partition P. then conceptually viewing X sequence (X+) where X, is member of P,, it must be for each i [ni] that the ball around p( intersects X; (and thus so does the E, ball since E; 2 E). This means (for each E [r)) that X; is one of at most k; members of P. because at most k; members of P. intersect the e; ball around () (by definition of P. being (ke, (x secluded). Thus X is one of at most I[ k; = k members of P. That is, there are at most l members of P that intersect the ball around p which is the definition of P being (k, E) secludeed.
In other words we identify the set 1ed with di x dada ... [gda-1 x dd
20

---

Utilizing the construction above, we will now take a unit cube partition of [44] for each R4: and take the product to obtain new partition. Since the dimension of each d, smaller than the dimension this allows us to get larger value of for each partition, and thus a larger value of g for the partition of Rd than if 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. Theorem A.14. Let d E N and d' E [d]. There exists (k, where & = (d' + 1) $1 and E 22
unit cube partition of TR.
Proof. Let n
d' 1. By 44 let P' be (d' + 1, 2d -secllded unit cube partition of Rd
P I P' (k:, e -secluded unit cube partition of R 22' Since n d' a 1- d' d, this trivially (by ignoring extra coordinates) gives a partition of R with these same properties (alternatively, see footnote which completes the proof.
By Proposition A.2 and Fact A.13
where k (d' + 1) and &
This construction is sufficiently general that for any dimension E N and any tolerance parameter in the domain of interest (k (2 we can construct (k, -eecluuddd unit cube partition of IRd such that E which is within factor of (d + 1) of the maximum possible tolerance for this choice of dimension and degree.
Finally, we are ready to prove Theorem 3.2
Proof. Let d' E [d] be the minimum integer such that (d' + +1)[ < (see justificatior 10 and let
1. E E= 22 By Theorem A. 14 and monotonicity, let P be a (k, e)-selluded unit cube partition of I
Now we prove the bound on in two cases: either d' or d' 2
In the case that d' = 1, then e = and & 2 (d' + 1) [1 2d and by hypothesis I 24, so we have equality and we conclude that
1kg,(k)
d/2
1
$ =
4d log. (d +11 4d log. (d+ + 1)
8 blog.(d +
8
which proves the bound in the first case.
In the other case, we have d' 2 Let d" d' > and 2d"
Note that
2d" d' -
1
6 2x
d'
so E 2 4o. By our choice of d' and because d" < d', it must be that k S (d" + 1) ( Noting that
d S ni + d+d"
<
d we have
2d
d"
& (d"
+ 1) < (d" + +1
(d" + +1)1de s (d" + 11) < (d + 1)
By taking the logarithm | of each side and solving for we obtain the desired result: (k) 8d (d+1) 1)
9 An alternate perspective to let di,..., such that Er. d: and the first portion of the list
d, d', and the second portion of the list d' def d' Then P' (d' + 1, 22 )-sellueed partition of Rd as before, and let pM a (d" L, zd secluded partition of Rd", Since d' d', P" is (by monotonicity) (a" 1, 24 )-sccluded partition. Then take P. p' when d, d' and P. pd when d, d". Again, get that P is ssccluudl for & = (d' + 1)" and = 20
that some d' satisties condition particular d' satisfics the requirement because à 2 + by hypothesis.
10 minimum exists by finiteness and
We choose the base 4 logarithm since that is what appears in upper bound E.
21

---

A.4 A Neighborhood Sperner/KKM Lemma: Theorem 3.4
In this section, we restate and prove our neighborhood variant of the Spener/KKM/Lcbesguee result on the cube. The proof idea is illustrated in Figure
(a) Initial coloring
(b) Extended coloring 7
(c) Red points (Yrua)
(e) Purple points (Xpurple)
(g) Gray points (Ygny)
(d) added (Yea Bg)
Ball added (Yparpao + Bg) (b) added (Ygry Bg)
Figure 2: (a) shows (finite) coloring x of the unit cube [- 2. such that no color includes points on opposite edges. (b) shows the natural extension of that coloring to [- E, + e]²² The extension is obtained by mapping each point ÿ to the point for which each coordinate value y: is restricted to be within [- 1-2. 2). and then z is given whatever color z had. (c), (e), and (g) show three of the five colors and demonstrate that there at least one quadrant of the s-ball that can be Minkowski summed with the color that the sum remains subset of the extended cube. For red it is the lower right quadrant, for purple it is the upper right, and for gray it could be the upper left (shown) or the upper right. (d), (f), and (h) show the resulting Minkowski sum for each color. Utilizing the Brunn-Mine Brunn-Minkowske inequality, this set will have substantially greater area by a factor of at least (1 + 14.)²
Theorem A.15 (Neighborhood Sperner/KKM Lemma). Given a Sperner/KKM coloring of [0, 1]d for any (0, }), there exists point [0, 1]d such that B (E. contains least (1 + "=) points with distinct colors.
2: 11d rather than [0, 1]d. Let C be finite set (of colors) and x: [- 1 ptt - C' be Spemer/KKK coloring of the unit cube [- 1, 1
Proof. For convenience, we will assume that the cube is [-]
22

---

The first step in the proof is to extend the coloring, X to the larger cube [- - E: + + in a natural way. Consider the following function which truncates points in the larger interval be in the smaller interval:
f: [
6,2
+ - [- 2:
y S -
[w)
def
y
y/ (-
2
y/ VZ
Let f: 1-2 + 2 1 be the function which is f in each coordinate: f(() def (f()))
Now extend the coloring X to the coloring 7: 1-2 E, +e C' defined by
7 def
(f())
For each color e E let (e- denote the points assigned color e by 7 and note that Y. 2 X Consistent with this notation, we will typically refer to point in the unit cube as F and point in the extended cube as y.
We make the following claim which implies that for each color e E C, the set Ye of points of that color in the extended coloring are contained in bounded away from one side of the extended cube E, + =] in each coordinate.
Subclaim A.16. For each color e e C there exists an orientation T 13 such that Ye S Il U. (- te].
Proof of Claim. Fix an arbitrary coordinate E [d]. Note that for every ÿ E Y. we have f X which is to say that the i7 has the same color in the extended coloring as (ī] does in the original coloring (see justification 12..
= Note that if there is some z E Y, with yi < - - then ((n) = - so Te(X.) 3 f(x)=
Similarly, if there is some ÿ E Y. with
2. then (X.)) 9 2. Recall that by hypothesis,
T, (X.) does not contain both -1 and } which means it is either the case that for all ÿ E Y. have yi (so n; (Y.) C (- 2 + e)) or it is the that for all ÿ E Y. we have y/ < (so (Y.) S )))
Thus we can choose ey { 13 such that (Y.) S oz (- + +e. Since this is true for each coordinate E [d] we can select i E {-1, 13dd such that
1
Y. (Y.)
0: II
2'
1=1
claimed.
For an orientation 13,, let B, denote the Bg def
-2---, (0, which should be
interpreted as an open orthant of the foo e-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 e E C, there exists an orientation ő E (-1,, 13ah such that Y. B3 S [-] E, t]
12 For every T Y. we have (by definition of Y.) that (g)) = c and (by definition of 7) that ((ū) = x(f(i)) showing that xT)) and thus (by definition of X.) that f(7) Xe.
23

---

Proof of Claim. Let ö be an orientation given in A.16 for color c. We get the following chain of containments:
d
Ye + Bg =
11
Us (0,E)
DDef'n Bş)
d
II
(- 1
+e]
+ II - 1.::00.44 (0,E)
A. 16
21
0/ (- 1
+e]
+
II U/ (-e,0)
(Factor negative)
21
iil
d
0j (- - 5 +
(Minkowski sum rectangles)
i=1
C E, + tela
(u. E (-1,1))
This proves the claim.
We also claim that Y. + B3 has substantial measure.
Subelaim A.18. For each color e E C and any orientation & E (-1,1)), the set Y, + Bg is Borel measurable and m(Y + Bạ) 2 mout (Vc) (1+ 1te)
Proof of Claim. Let M + =)d which the measure of II ea (- + +e.. and because by A.16 Y. is a subset of this set, we have Mout (Ya) S M.
We have that Y. By Borel measurable and that m (Yo + Bz) Mona (Yo) 2 +5)
A.6 (see
details
Thus, we have the following chain of inequalities:
m(e + Bp) 2 Mout (Vo) (V.) + +0)
(Above)
Mout Moun(Y.) (Y.) 1/d
d
= M
(Factor out M)
Mi/d
M1/d
Mone (Ya)
(1
2 M
A.7
M
Mi/a
(1+
= Mont (Ye)
(Simplify and use (1 + E)4
1+
Now, consider the indexed family A (Yo+ BB(e) ) esc (where iT(c) is an orientation for in A.16 and A.17) noting that it has finite cardinality because C has finite cardinality. Considering the
Nott that the Loo norm, measure of the unit ball Ufj-lla 2d. Then note that Bş an open orthant of an e ball with respect to fas, so is in fact itself an 2 ball with respect to loc. This is why we get "e" instead of the "2s" An6 We could translate this open ball to the origin and translate the set Y. accordingly to get the same Minkowski without changing the measures, and after doing so could apply A.6 verbatim.
24

---

sum of measures of sets in A, we have the following:
Σ AEA
m(A) Σ
(Ye + Bi(c))
(Def'n of A; measurability was shown above)
oEC
Moat (Yc)
A.18 and linearity of summation)
1+e
eEC
U
Moutt
1
(Countable/finite subaddativity of outer measures)
1 1+e
Mout (1-2 2 +e]
(The Y.'s partition [- E, 2,2 + =
6
1 + 1 1te)
(1 + 25)
(Evaluate outer measure)
By A.17 each member of A is subset of [-2 6, + =] by 5.1
there exists point ç
[-2 E, 2 + e] that belongs to least
(1 + 28)d
- (11 I+
d'
It8
(1+ 21+2
(1 T+s
sets in A. That is, bebllog to Y. + Be(e) for at least
colors E C. For each such
color it follows that + (-e,e)d intersects Y. (see justification
14 Note that with respect to the foo
norm, 7 (-8,e)d = B% (e, p) showing that B (e. P) contains points of at least
(1 F
d'
I+f
colors (according to the coloring of y since we are discussing sets Ye).
What we really want, though, a point the unit cube that has this property rather than a point in the extended cube, and want it with respect to the original coloring x rather than the extended coloring 7. We will show that the point [()) suffices.
Subclaim A.19. Ifc C' is color for which B% (s,D) n., + 0, then also B% (e, ( n X +
Proof of Claim. Let 1j E B (E, Then because jī B (s,p), we have || pl < so for each coordinate E [d]. ly: Pal E. It easy to analyze the cases (or by symmetries) arising in the definition of ff to see that this implies [f(w) domain so that they are farther apart), thus [I[(w) f and thus (() E B& (e, [(1)..
f(p:) <
f(p))
well (i.e. maps pairs of values in its
Also, as justified in prior footnote
12 for any 7 Y. we have f(y) E Xx so that f(w)
B% f (p) n X. which shows that the intersection is non-empty.
Thus, because (E, intersects Y. for at least (1+ Its
choices of color C, by A.19
(1+ 1tt
(P) is a point in the unit cube which intersects X, for least
different colors c e C.
That is, this ball contains points from at least this many of the original color sets.
The final step the proof of the theorem is to clean up the expression with an inequality, Note that C must contain of at least 2d colors because each of the 2d corners of the unit cube must be assigned a
"If " E Ye + Bace) C Y, + (-s,e)", then by definition of Minkowski sum there exists T E Y. and
DE (- such that 5 = 5 + 5 Y. e 5 = p be p (- demonstrating that these two sets contain common point.
25

---

unique color since any pair of corners belong to an opposite pair of faces on the cube. For this reason is trivial that for > there a point p such that (E. p) intersects at least 2 colors: just let p be the midpoint the unit cube. Thus, the only interesting case is E (0, ž.. and for such we have
1 + e S 2 and thus c the theorem.
2 (1 Ge) This completes the proof of I+E fe showing that (1+ T+z
B Measure Theory
Throughout this section, we use the word "countable" mean finite or countably infinite.
Fact B.1 &L Diameter Ball), Let d E N and X C 12d be bounded set with diameter D (with respect to (oo). Then there exists 5 E I& such that X C BD)2(p). As a consequence, Mout (X) S Dd where Mout denotes outer Lebesgue measure.
Proof Sketch. each coordinate E [d], consider the set X; (T) (((G)::E E) S R of the coordinates of each point in X. The infimum and supremum distance most D apart. because
otherwise there would be points y. 8 e X such that (²) n, (v)) > D which means || V/ > D.
Thus taking 17
vd 1== we have X C II [inf(X;), sup(()) S
D1
B(D/2, 22 p)-
L
Fact B.2. If is measure and A is (possibly uncountable) famill of pairwise disjoint measurable sets, then
41
A)
Σ
((A).
AEA
AEA
Proof. By definition of the arbitrary summation (c.f. 200 p. 11]) we have
Σ
((A)
def sup
Σ
m(A) F S A, F finite
AEA
LAFF
and for any F C A we have
L AEA
A)
L
A)= Σ M(A).
AEJ
AEF
Thus "LLAAA A) is an upper bound for the set (AAFM(AA) than or equal to the supremum.
FF A, F finite} and thus greater
Fact B.3 (Interchange of Countable Sums with Non-negative Terms). I, are countable sets, and aig 2 ffror all (i,j) E Exx. J, then
ΣΣ D.j = ΣΣ an iE JEJ
JEJ IET
Proof. 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 integral over countable measure space, this can be viewed
corollary to Tonelli's theorem. D
Lemma B.4 (Upper Bound Measure of Multiplicity). Let n E N. Let X be measurable set in some
measure space (the measure being denoted by μ1) and let A be a countable family of measurable subsets of X such that for each E X, x belongs to at most members of A. Then
Σ AEA
u(A) < P(X).
Proof. For ease of indexing, assume A {A Let IA, denote the indicator function for A, and note that by hypothesis, for any N, the function Σ IA, is bounded above by the constant
We thank an anonymous researcher who pointed out that our original proof was overcomplicating things and pointing to this elementary proof.
26

---

function n. Thus, recalling that (((A)) = Jx LA, du (because A, S X) we have the following for any k N:
k Σ (MA))
du / ndu n m(X).
Σ
AAi
1=1
1=1
Li=1
Since this holds for all k, it also holds in the limit:
Σ
M(A)
((A,)
lim
Σ ((Ai)
In In-M(X).
AEA
Corollary B.5 (Lower Bound Cover Number). Let X be a measurable set in some measure space (the measure being denoted by ()) such that (xX) op. Let be countable family measurable subsets of X such that AAEA ((A) < cc. Then there exists E X such that x belongs to at least
AAA p(A) -many members of A.
a(X)
EAEA ((A) finite. Suppose for contradiction that each M(X)
Proof. First observe that by hypothesis,
Easa ((A)
A m((A) 1
X belongs to strictly less than
-many members of A. Let
M[X)
p(X)
(noting that EACa (ACA)(A) p.(A). Then each X belongs at most n-many members of A, have
H(X)
Σ m(A) Sn E.nnMi M(X)
(Lemma B.4
AEA
ExEAM(A)
(0 < ((X) < 3o and n << Exeam(a) ((()
m(X) m(X)
Σ m(A)
AEA
which is a contradiction.
Remark B.6. In Corollary B.5 above, it important that required E A H((A) be finite. we allowed to be infinite, Then the claim would have been that there was some x. E X belonging to infinitely many members of A, but this is in general not true (see B.7 B.7below). Nonetheless, is true (and a straightforward corollary of the above) that if E'AA (A(A) oc, then for any E No. there exists a point In X that is contained in 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 E N). Then Σ ((A) Σien co. For any
or Lebesgue measure μ.. Let A (0, 4) : n E N, we can consider the point Fn n which is contained in (0, 7) for E [n] and not for any other i, so 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 (0,1). Then for sufficiently large Ni, & (0, }) so x belongs only finitely many members of A.
The prior results have been stated in typical measure theory notation, but in the body of the paper we present B.5 as follows for RRd specifically with notation matching what is used elsewhere in the paper.
Proof of Proposition
A. This follows trivially from B.5 and B.6
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Rigorous proofs of all results stated in the abstract and introduction are provided in the main body/appendix.
Guidelines:
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 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA].
Justification:
This is theoretical paper. The open problems and future research directions are discussed.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 the scope of the claims made, e.g., if the approach was only tested on few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: Complete proof' of all the theorems are provided in the appendix. The main body discusses proof ideas. No assumptions in the theorem statements are made.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /utee//ggudddeeeedSuuuummbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 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 emrr 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes],
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there a special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "DmHNTDtOTe", "reviewer": "Reviewer_Srve", "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$\nTheir 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$.\nLastly, the authors use the techniques they have developed to prove a \"neighborhood\" version of the cubical Sperner's/KKM lemma.", "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?\n\n-Can you explain a bit more about the adaptation of Theorem 5.1 you talk about in Line 231?", "limitations": "Adequately addressed.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "-The constructions that the authors present are mathematically elegant. \n\n-The paper is written clearly and is easy to follow.\n\n-Their applications to list-replicable learning, which has gained some attention recently, are spelled out in the paper. \n\n-Some of the results, like the extension of Sperner's lemma, can have further applications.", "weaknesses": "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.\n\nSome minor points/typos:\n-Line 53: double full-stop.\n-Line 56: \"the replicable algorithm\" -> replicable algorithms.\n-Theorem 2.4: it would be better for a broader audience to define face/closure.\n-Line 109: the degree parameter -> it.\n-Line 339: know -> known.\n-In many places: lowerbound -> lower bound\n-Line 156: global stability.\n-Line 172: extend -> extended.\n-Line 112: a ) is missing.\n-Line 114: drop result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to the Weaknesses Comment:\n \nWe agree with the reviewer that the connection between secluded partitions and list-replicability was already observed. Indeed, that is our  main motivation to further investigate the possibility of constructing secluded partitions better than those previously known. However, our result is negative and shows that the known constructions cannot be improved by much. We believe negative results are  a significant contribution in the sense that they guide the research directions. Moreover, the techniques used to establish the negative result led to the discovery of the neighborhood-Sperner/KKM lemma. We disagree with the reviewer that the results are incremental because our results provide a comprehensive picture of a secluded partition (both constructions and impossibility results), and for establishing the lower bounds we need quite different techniques (from measure theory and geometry) than those used in the literature. \n\nThank you for pointing out the typos. We will fix them in the final version. \n\nResponse to Questions: \n\nAnswer to Question: \n\nQ1. We conjecture that any $(d+1)$-list replicable algorithms for the d-bias coin problem requires $\\Omega(d^2/\\nu^2)$ samples per coin. \n\nQ2. Adaptation of Theorem 5.1: This is only a slight technicality: Our lower bound theorem works for partitions whose members have bounded outer measure (need not be measurable). However, for Theorem 5.1 to be applied, we need sets $A, B$, and $A+B$ to be measurable. So an adaptation of 5.1 is needed and is given as Lemma A.6, which allows us to work with outer measures.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KhVqCDrDna", "reviewer": "Reviewer_W1GL", "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.", "questions": "What direct implications do these results have for list-replicable learning?\n\nHow do these implications compare to what is known for $\\rho$-replicable learning for similar problems?", "limitations": "Yes, the authors have addressed all limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This work provides novel results with potentially broad applications in geometry and computer science. Sperner's lemma is widely useful across disciplines, and this neighborhood variant may prove similarly broadly useful.", "weaknesses": "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. \n\nIf 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]. \n\n[1] “Stability is Stable” Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, Sorrell\n[2] “Replicability in Reinforcement Learning” Karbasi, Velegkas, Yang, Zhou ’23\n[3] “Replicability in High Dimensional Statistics” Hopkins, Impagliazzo, Kane, Liu, Ye ‘24\n\nTypos/suggested edits:\n\nAbstract\n\n“We show that for each d” -> “we show for each d”\n\nSection 1 pg 2\nBrower -> Brouwer\nshould be seen as a fundamental endeavor. . \n\nSection 2 page 2\n“belongs to a list L consisting of almost k good hypotheses”\n\n“over which a family of distribution” -> “over which a family of distributions”\n\npage 3\n\n“the partitions considered in this work have a non-zero” -> “the partitions considered in this work have non-zero\n\nTheorem 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\n\nSection 3\n\n“in general a $(k, \\varepsilon)$-secluded partitions” \n\n“Can we improve this and construct a (d+1, \\omega(1/d)-secluded partition?”\n\n“is the following result upper bound result”\n\n“Till this work we know”\n\n“There exist a k-list replicable algorithm”\n\n“Spener/KKM Lemma”\n\nSection 4\n“A learning algorithm A to be $(n, \\eta)$-globally stable”\n\nSection 5.1\n\nNeed a period before Thus/ what we do is to “replace”\n\nI 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?)\n\nNeed a period before “Now that we have dealt with both issues” on page 6.\n\n“So because there is a ceiling involved” could be made more precise, as could “by our change of perspective.”\n\nSection 5.2\n\nThere’s a $d_n$ that should be $d_i$ in Definition 5.2\n\nSection 6\n\n“We also constructed secluded partitions for a wide all $k$”\n\nThe second paragraph of Section 6 is very vague, and doesn’t mention that the similar upper bounds are for general lp norms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to Weaknesses Comment:\n\nThis weakness regarding the scope is addressed in the general response, and we reiterate it here. Our work is motivated by the connection of geometric/topological tools to list replicability (secluded partitions and Sperner/KKM Lemmas). Driven by this connection, the current work undertakes an in-depth investigation of secluded partitions, a tool used to establish list replicability results. We believe that understanding the power and limitations of tools employed in replicability research is a significant contribution to the field and falls within the scope of NeurIPS.\n\nOur investigation into secluded partitions not only led us to a comprehensive understanding of secluded partitions but also to a new neighborhood version of Sperner/KKM lemma. Sperner/KKM lemma and its variants (such as Poincare-Miranda) have proven to be critical tools in replicable learning and have applications in broader areas of computer science. We believe that this new version neighborhood version of Sperner/KKM lemma will have significant applications in learning. Other reviewers (D2ky, 1env) have expressed similar sentiments.\n\nRegarding related works, thank you for suggested references. We will make the related work section more comprehensive in the final version taking into consideration all the references, including the ones that appeared after NeurIPS deadline.\n\nThank you for carefully reading and pointing out the typos and suggestions for improvements. We will fix the typos and will incorporate your suggestions in the final version. \n\nResponse to Questions:\n\nQ1: Our secluded partition construction (Theorem 3.2) leads to corollary 3.3 which gives a tradeoff between list size and sample complexities. For example, if we allow the list size to be $2^{\\sqrt{d}}$ then we can get sample complexity of $\\tilde O(d/\\nu^2)$ per coin, which is a new result. Theorem 3.1 shows the limitations of secluded partitions as a tool. \n\nQ2: It is possible to go from list-replicable algorithms to $\\rho$-replicable algorithms (using ideas from Goldreich [25]).  In $\\rho$-replicability,  one is allowed to choose a random string. Once a random string is fixed, the rest of the computation is perfectly replicable (i.e.,  with list size 1). Goldreich’s construction implies that a $\\ell$-list replicable algorithm leads to a $\\rho$-replicable algorithm where the length of the random string is of the order of  $O(\\log l)$ (with additional dependency on  $\\rho^2$). However, such a transformation leads to a sample complexity blow-up. This is already observed in [16].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GfFqjV1dSC", "reviewer": "Reviewer_D2Ky", "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$. \n\nThe 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.", "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?\n\n2) There is a series of works that establish connections between replicability and approximate DP. Is there some similar connection to list-replicability?\n\n3) Returning to the geometric connections to list replicability, is there some similar geometric intuition for DP?", "limitations": "No limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Since there is a $(k, \\epsilon) = (d+1, 1/(2d))$-secluded partition of the $d$-dimensional Euclidean space, one natural question is whether one can improve on $k$ or $\\epsilon$. For $k$, we knew that this is tight. The main result of the paper states that essentially the dependence on $\\epsilon$ is also tight: for any $k \\leq 2^d$, it must be the case that $\\epsilon \\in \\tilde{O}(1/d)$. Hence, even by relaxing the number of intersections to be $k = \\mathrm{poly}(d),$ one cannot get $\\epsilon = \\omega(1/d)$. I find this result interesting since it raises new questions on how to design improved list-replicable learners.\n\nThe second result of the paper is a construction of a $(k, \\epsilon)$-secluded partition for (roughly) any $k \\in [2^d]$. Each choice of $k$ gives a related value for $\\epsilon$. \n\nI find the connections raised in this paper quite nice. I feel that the geometric insight is very useful and could inspire future work in the area of replicable algorithms. The results of the paper are clear and I enjoyed reading the paper. Finally, I think that the paper is technically interesting and the arguments are nice.", "weaknesses": "Some suggestions in terms of presentation:\n\n1) Between line 91-95, I would add some more discussion about Sperner's lemma and the terminology used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to Suggestion:\n\nThank you for the suggestion. We will add the discussion along the lines you propose. \n\nResponse to Questions: \n\nQ1: Unit ball in $\\ell_p$ norm is a subset of a unit ball in $\\ell_\\infty$ norm. Thus secluded partitions with respect to $\\ell_\\infty$ norm are also secluded with respect to $\\ell_p$ norm. Based on this, we can get a $d+1$-list replicable algorithm for the d-biased coin problem (where the approximation is in $\\ell_p$ norm), using the known relation between the secluded partition and list replicable algorithms. In the present work, we also establish a generic version of Theorem 3.1 that applies to other norms. This result appears in the appendix as Theorem A.8. From this theorem, for example for $\\ell_2$ norm, we obtain that $k > (1+\\varepsilon\\sqrt(2\\pi e/d))^d$. \n\nQ2 and Q3: We know from the work reported in [11], the global stability parameter is inverse to the list size. Prior work established the relationship between DP and stability [9]. In particular, from these works it follows that  for a concept class $\\cal C$ a learning algorithm with a polynomial list size with polynomially many samples implies that the concept class is DP learnable with polynomial sample complexity.  Admittedly, we are not experts on DP, and our intuition there is limited. \n\nWe thank the reviewer for very encouraging remarks about the usefulness of our work in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y4DjONf2KI", "reviewer": "Reviewer_1env", "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.\n\nThe 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.\n\nPrior 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’.\n\nThe 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.\n\nPrior 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.\n\nThe 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.", "questions": "N/A", "limitations": "The authors have appropriately discussed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Algorithmic stability is a natural and recently fruitful topic in learning theory, closely related to core notions including differential privacy. Understanding the `cost’ trade-off between samples and strength of stability (in this case, list size) is a very natural problem. \n\nThe coin problem is a fundamental learning problem that has also shown up as a subroutine in analysis of replicable tasks, e.g. reinforcement learning in (\"Replicability in Reinforcement Learning\") and hypothesis testing in (\"Replicability in High Dimensional Statistics\"). The authors prove a new upper bound for this problem that interpolates between (essentially) no overhead at the `trivial’ list size of $2^d$, to $d^2$ overhead at the optimal list size $d+1$. The authors show this is tight assuming the use of secluded partitions.\n\nThe problem of secluded partitions itself, while formally a purely geometric result, is a natural problem and does have a similar flavor to recent techniques used for lower bounds in algorithmic stability. I would not be surprised if the author’s new neighborhood lemma sees future use in learning.\n\nFinally, the paper (or at least the introduction) is very well-written, with good proof intuition clearly laid out in the introduction and a good overview of prior literature.", "weaknesses": "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.\n\nIn 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.\n\nThus 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to Weaknesses Comment:\n\nThe concern regarding the scope to NeurIPS is addressed in the General Response as well as the response to Reviewer W1GL. We agree the main novelty and technicality is in establishing the lower bound. However, the upper bound is critical to complete the picture. Thank you for the optimistic remark that these notions have the potential to be useful in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
General Response:

We sincerely thank all the reviewers for their careful reading and thoughtful comments and suggestions. 

A common concern raised by the reviewers is the scope and fit of the present work for NeurIPS, which we address here. Our work is motivated by the fundamental connections between geometry/topology and the fast-emerging topic of replicable learning. This connection continues to be revealed. For instance, the works reported in [29, 16] use geometric partitions to design replicable algorithms, while those in [16,12,11] utilize Sperner-KKM-like fixed point theorems from geometry/topology to establish lower bounds (references as appear in the submission). Therefore, it is natural and fundamental to further investigate geometric partitions and Sperner/KKM-type theorems in relation to replicability. We believe that undertaking such investigations is a significant endeavor and should be of interest to the NeurIPS community.

Our work is a comprehensive study of geometric partitions, specifically secluded partitions, which have direct applications to list replicability [16]. Additionally, the work establishes a neighborhood variant of the Sperner/KKM lemma. As  majority of reviewers have pointed out, this neighborhood version is a fundamental contribution with strong potential for applications in replicability research.

Thus, while our motivation to investigate the partition problem is inspired by replicability, our study focuses on geometric partitions and Sperner/KKM-type results. We believe such a study is within the scope of the conference.

Meta-review: 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.
Decision: Accept (poster)