Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces

We prove that the list replicability number of d-dimensional γ-margin half-spaces satisfies d/2+1 ≤ LR(Hγd) ≤ d. In particular, it grows with the dimension. Our lower bound uses a topological argument based on a local Borsuk–Ulam theorem. Our upper bound is proved by constructing a list-replicable learning rule from the generalization properties of SVMs. These bounds yield several consequences in learning theory and communication complexity.