Research map / Learning theory and algorithms / Sample complexity
Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies (k, ε)-secluded partitions of R^d for replicable learning, proving an upper bound ε ≤ log4(k)/d, constructing near-matching unit-cube partitions, and proving a neighborhood variant of the Sperner/KKM lemma.
Problem
Determining the optimal tradeoff between degree k and tolerance ε of secluded partitions of R^d, which governs list complexity and sample complexity of replicable learning algorithms, and extending Sperner/KKM lemma to neighborhoods.
Approach
Shows via a generalized Brunn-Minkowski inequality and a continuous multi-pigeonhole principle that any partition with unit-measure members must have k ≥ (1+2ε)^d, and builds product of known unit-cube partitions to achieve near-matching tolerance for every k in [2d]; also proves a neighborhood version of cubical KKM lemma.
Key results
- Any (k, ε)-secluded partition with unit-measure members satisfies k ≥ (1+2ε)^d, hence ε ≤ log4(k)/d for k ≤ 2d.
- For every d and k in [2d] \ [d], a (k, ε)-secluded unit-cube partition exists with ε ≥ log4(k)/(8d log4(d+1)), optimal up to log factors.
- Neighborhood Sperner/KKM: for any Sperner coloring of [0,1]^d and ε in (0, 1/2], some point's open ε-ball meets at least (1+2ε/3)^d colors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the product partition construction for degrees k ∈ [2^d] \ [d] instead of the previously known constructions | Unit cube partitions of R^d · Secluded partitions | tolerance: ε ≥ log4(k)/(8d log4(d+1)) | Helped |
| Increase the degree allowance to k ∈ [2^d] | Secluded partitions of R^d · Secluded partitions | tolerance: ε ≤ log4(k)/d; ε ≥ log4(k)/(8d log4(d+1)) | Mixed |
| Apply the neighborhood version to a Sperner/KKM coloring | Cubical Sperner/KKM coloring of [0, 1]^d · Cubical Sperner/KKM coloring | colors in an open ε-radius ℓ∞-ball: (1 + 2/3ε)^d | Helped |
Limitations
- Results are near-optimal only for the ℓ∞ norm; other norms lack matching constructions.
- Neighborhood Sperner bound (1+2ε/3)^d is not tight for small ε, failing to recover d+1 colors from standard Sperner.
- Bounds are optimal only up to logarithmic factors.
Experimental setup
Baselines: (d+1, 1/(2d))-secluded partition
Builds on: secluded partitions (Su, Zhang and others, cited as [44]) Sperner/KKM lemma Blichfeldt's theorem list replicability (Dixon et al.)
Closest papers by meaning
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.86)
- Learning Partitions from Context (NeurIPS 2024 · similarity 0.85)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.85)
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.85)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.85)
- ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.