Rademacher Observations, Private Data, and Boosting

By Richard Nock, Giorgio Patrini, Arik Friedman. 2015

13 citations recorded by the source corpus.

The minimization of the logistic loss is a popular approach to batch supervised learning. Our paper starts from the surprising observation that, when fitting linear classifiers, the minimization of the logistic loss is equivalent to the minimization of an exponential rado-loss computed (i) over transformed data that we call Rademacher observations (rados), and (ii) over the same classifier as the one of the logistic loss. Thus, a classifier learnt from rados can be directly used to classify observations. We provide a learning algorithm over rados with boosting-compliant convergence rates on the logistic loss (computed over examples). Experiments on domains with up to millions of examples, backed up by theoretical arguments, display that learning over a small set of random rados can challenge the state of the art that learns over the complete set of examples. We show that rados comply with various privacy requirements that make them good candidates for machine learning in a privacy framework. We give several algebraic, geometric and computational hardness results on reconstructing examples from rados. We also show how it is possible to craft, and efficiently learn from, rados in a differential privacy framework. Tests reveal that learning from differentially private rados brings non-trivial privacy vs accuracy tradeoffs.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, methodology): “ that entity resolution is not necessary for good approximations of the optimal model. Related methods exploit the fact that one can learn from sufﬁcient statistics for the class instead of examples [Nock et al., 2015, Nock, 2016, Patrini, 2016], many of which do not require entity resolution to be ”
Fast Learning from Distributed Datasets without Entity Matching (2016, methodology): “Theorem 3 expresses a form of su ficiencyof the whole set of rados with regard to the square loss; a similar property is proposed for logistic los s in [21].”
A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial Examples (2016, background): “Recent studies have proposed various strategies (Xie et al., 2014; Bojarski et al., 2014; Stoddard et al., 2014; Li & Zhou, 2015; Rajkumar & Agarwal, 2012; Dwork, 2011; Nock et al., 2015) to preserve the privacy of data such as differential privacy.”
On Regularizing Rademacher Observation Losses (2016, methodology): “= {yi · xi, i = 1, 2, ...,m} since zi = θ >(yi ·xi), and the rado loss can be described using rademacher observations [Nock et al., 2015], since ∑ i∈I zi = θ >πσ for σi = yi iff i ∈ I (and −yi otherwise) and πσ .”
Learning Games and Rademacher Observations Losses (2015, methodology): “opular logistic loss over examples in supervised learning is equivalent to the minimisation of the exponential loss over sufﬁcient statistics about the class known as Rademacher observations (rados, (Nock et al., 2015)), for the same classiﬁer. In short, we ﬁt a classiﬁer over data that is different”