Skip to yearly menu bar Skip to main content


Poster

Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma

Jason Vander Woude · Peter Dixon · A. Pavan · Jamie Radcliffe · N. V. Vinodchandran

West Ballroom A-D #5501
[ ]
[ Paper [ Poster [ OpenReview
Wed 11 Dec 11 a.m. PST — 2 p.m. PST

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 P of Rd is called a (k,ϵ)-secluded partition if for every pRd, 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 ε. 1. We show that for any (k,ϵ)-secluded partition where each member has at most unit measure, it must be that k(1+2ε)d, and consequently, for the interesting regime k[2d] it must be that ϵlog4(k)d. 2. To complement this upper bound on ϵ, we show that for each dN and each viable k[2d], a construction of a (k,ϵ)-secluded (unit cube) partition with ϵlog4(k)d18log4(d+1). This establishes the optimality of ϵ within a logarithmic factor.3. Finally, we adapt our proof techniques to obtain a new neighborhood'' variant of the cubical KKM lemma (or cubical Sperner's lemma): For any coloring of [0,1]d in which no color is used on opposing faces, it holds for each ϵ(0,12] that there is a point where the open ϵ-radius -ball intersects at least (1+23ϵ)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.

Chat is not available.