Learning versus Refutation in Noninteractive Local Differential Privacy

2022/10/26 by Edmonds, Alexander, Nikolov, Aleksandar, Pitassi, Toniann
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2210.15439

Abstract

We study two basic statistical tasks in non-interactive local differential privacy (LDP): learning and refutation. Learning requires finding a concept that best fits an unknown target function (from labelled samples drawn from a distribution), whereas refutation requires distinguishing between data distributions that are well-correlated with some concept in the class, versus distributions where the labels are random. Our main result is a complete characterization of the sample complexity of agnostic PAC learning for non-interactive LDP protocols. We show that the optimal sample complexity for any concept class is captured by the approximate γ₂~norm of a natural matrix associated with the class. Combined with previous work [Edmonds, Nikolov and Ullman, 2019] this gives an equivalence between learning and refutation in the agnostic setting.

Related

• Locally Private Learning without Interaction Requires Separation
• On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data
• Interaction is necessary for distributed learning with privacy or\n communication constraints
• Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
• Distributed Learning, Communication Complexity and Privacy