Blog
About

10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle

      Preprint

      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          While machine learning has proven to be a powerful data-driven solution to many real-life problems, its use in sensitive domains has been limited due to privacy concerns. A popular approach known as **differential privacy** offers provable privacy guarantees, but it is often observed in practice that it could substantially hamper learning accuracy. In this paper we study the learnability (whether a problem can be learned by any algorithm) under Vapnik's general learning setting with differential privacy constraint, and reveal some intricate relationships between privacy, stability and learnability. In particular, we show that a problem is privately learnable **if an only if** there is a private algorithm that asymptotically minimizes the empirical risk (AERM). In contrast, for non-private learning AERM alone is not sufficient for learnability. This result suggests that when searching for private learning algorithms, we can restrict the search to algorithms that are AERM. In light of this, we propose a conceptual procedure that always finds a universally consistent algorithm whenever the problem is learnable under privacy constraint. We also propose a generic and practical algorithm and show that under very general conditions it privately learns a wide class of learning problems. Lastly, we extend some of the results to the more practical \((\epsilon,\delta)\)-differential privacy and establish the existence of a phase-transition on the class of problems that are approximately privately learnable with respect to how small \(\delta\) needs to be.

          Related collections

          Most cited references 6

          • Record: found
          • Abstract: not found
          • Article: not found

          What Can We Learn Privately?

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Mechanism Design via Differential Privacy

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A Statistical Framework for Differential Privacy

                Bookmark

                Author and article information

                Journal
                2015-02-22
                2016-04-27
                Article
                1502.06309

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                to appear, Journal of Machine Learning Research, 2016
                stat.ML cs.CR cs.LG

                Security & Cryptology, Machine learning, Artificial intelligence

                Comments

                Comment on this article