← Back to papers
2019 COLT COLT 2019

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Abstract

We ask whether every class of Boolean functions that has polynomial margin complexity can be PAC learned efficiently by a non-interactive locally differentially private algorithm.

❓ The Questioner
🌉 Interdisciplinary Bridge — Artificial Intelligence and Machine Learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Amit Daniely , Vitaly Feldman

Topics

Artificial Intelligence > Learning Paradigms > Transfer Learning Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Application Areas > Privacy

Keywords

differential privacy pac learning distributed learning margin complexity
Download PDF

Related papers

Inference under Information Constraints: Lower Bounds from Chi-Square Contraction 2019
Learning in Non-convex Games with an Optimization Oracle 2019
Learning to Prune: Speeding up Repeated Computations 2019
A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise 2019
Learning Two Layer Rectified Neural Networks in Polynomial Time 2019