Compressed Learning with Regular Concept

摘要

We revisit compressed learning in the PAC learning framework. Specifically, we derive error bounds for learning halfspace concepts with compressed data. We propose the regularity assumption over a pair of concept and data distribution to greatly generalize former assumptions. For a regular concept we define a robust factor to characterize the margin distribution and show that such a factor tightly controls the generalization error of a learned classifier. Moreover, we extend our analysis to the more general linearly non-separable case. Empirical results on both toy and real world data validate our analysis.