Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Abstract

We ask whether every class of Boolean functions that has polynomial margin complexity can be PAC learned efficiently by a non-interactive locally differentially private algorithm.