On the Sample Complexity of Privately Learning Axis-Aligned Rectangles

2021/07/24 by Sadigurschi, Menachem, Stemmer, Uri
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2107.11526

Abstract

We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid X^d⊆ℝ^d with differential privacy. Existing results show that the sample complexity of this problem is at most min\ d⋅log|X| , d^1.5⋅(log^*|X| )^1.5\. That is, existing constructions either require sample complexity that grows linearly with log|X|, or else it grows super linearly with the dimension d. We present a novel algorithm that reduces the sample complexity to only O\d⋅(log^*|X|)^1.5\, attaining a dimensionality optimal dependency without requiring the sample complexity to grow with log|X|.The technique used in order to attain this improvement involves the deletion of "exposed" data-points on the go, in a fashion designed to avoid the cost of the adaptive composition theorems. The core of this technique may be of individual interest, introducing a new method for constructing statistically-efficient private algorithms.

Related

• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• Private Center Points and Learning of Halfspaces
• Differentially Private Learning of Geometric Concepts
• Private Learning and Sanitization: Pure vs. Approximate Differential\n Privacy
• Privately Learning Thresholds: Closing the Exponential Gap