Efficient Private Algorithms for Learning Large-Margin Halfspaces
This addresses privacy-preserving machine learning for high-dimensional data, offering a more efficient approach compared to prior methods.
The paper tackled the problem of learning large-margin halfspaces with differential privacy, developing algorithms whose sample complexity depends only on the margin and not on the dimension, and proved that this margin dependence is optimal.
We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of the data, and not on the dimension. We complement our results with a lower bound, showing that the dependence of our upper bounds on the margin is optimal.