Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma

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. , an ε-radius ball (with respect to the ℓ ∞ norm) centered at ⃗ p intersects at most k members of P. In relation to replicable learning, the parameter k is 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 k and large ε) 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 ε.