Robust and Private Learning of Halfspaces

2020/11/30 by Badih Ghazi, Ravi Kumar, Ghazi, Badih +5 · 2 citations
Computer Science · #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2011.14580

openalex publication_date 2020/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work, we study the trade-off between differential privacy and adversarial robustness under L2-perturbations in the context of learning halfspaces. We prove nearly tight bounds on the sample complexity of robust private learning of halfspaces for a large regime of parameters. A highlight of our results is that robust and private learning is harder than robust or private learning alone. We complement our theoretical analysis with experimental results on the MNIST and USPS datasets, for a learning algorithm that is both differentially private and adversarially robust.

Citations

• The perceptron: A probabilistic model for information storage and organization in the brain.
• Gradient-based learning applied to document recognition
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Adversarial Training Can Hurt Generalization
• Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• On Robustness to Adversarial Examples and Polynomial Optimization
• An Alternative Surrogate Loss for PGD-based Adversarial Testing
• Efficient Private Algorithms for Learning Large-Margin Halfspaces

Cited by

• Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
• On robustness and local differential privacy

Related

• Efficiently Learning Adversarially Robust Halfspaces with Noise
• Learning to be adversarially robust and differentially private
• Efficient Private Algorithms for Learning Large-Margin Halfspaces
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise