Skip to content
conftrace_
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
📈 Trend Setter - Differential Privacy

Authors

Amit Daniely, Vitaly Feldman

Topics

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

Keywords

differential privacy pac learning distributed learning boolean function local differential privacy margin complexity
Download PDF

More from COLT 2019

All COLT 2019 papers →
Estimation of smooth densities in Wasserstein distance
Estimating the Mixing Time of Ergodic Markov Chains
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
Open Problem: How fast can a multiclass test set be overfit?
Open Problem: Do Good Algorithms Necessarily Query Bad Points?
Open Problem: Risk of Ruin in Multiarmed Bandits