---
author:
- 'Mark Bun [^1]'
- 'Roi Livni [^2]'
- 'Shay Moran [^3]'
bibliography:
- 'biblio.bib'
title: |
    An Equivalence Between Private Classification\
    and Online Prediction
---

Introduction
============

This paper continues the study of the close relationship between differentially-private learning and online learning.

#### Differentially-Private Learning.

Statistical analyses and computer algorithms play significant roles in the decisions which shape modern society. The collection and analysis of individuals’ data drives computer programs which determine many critical outcomes, including the allocation of community resources, decisions to give loans, and school admissions.

While data-driven and automated approaches have obvious benefits in terms of efficiency, they also raise the possibility of unintended negative impacts, especially against marginalized groups. This possibility highlights the need for [*responsible*]{} algorithms that obey relevant ethical requirements (see e.g. [@Oneil2016weapons]).

[*Differential Privacy*]{} (DP) [@DworkMNS06] plays a key role in this context. Its initial (and primary) purpose was to provide a formal framework for ensuring individuals’ privacy in the statistical analysis of large datasets. But it has also found use in addressing other ethical issues such as [*algorithmic fairness*]{} (see, e.g. [@DworkHPRZ12; @cummings19fairness]).

Many tasks which involve sensitive data arise in machine learning (e.g. in medical applications and in 