Reproducibility in Learning

[RaphelWei]

paper

[RaphelWei]

This paper formally defines $\rho$-reproducibility.

[RaphelWei]

It mainly discusses several aspects:

1. learning half spaces
2. how to turn an algorithm into reproducible one

[RaphelWei]

These definitions revolve around the "Heavy Hitter" problem, which deals with identifying elements in a distribution that appear frequently (above a certain threshold).

Definition 3.1: Heavy-Hitter

• Concept: This definition explains what it means for an element $$x \in \mathcal{X}$$ to be a $$v$$-heavy-hitter of a distribution $$D$$.
• Formal Description: If an element $$x$$ appears with probability at least $$v$$ when drawing from distribution $$D$$, then it is a $$v$$-heavy-hitter.
• Explanation: Suppose you have a distribution $$D$$ over a set $$\mathcal{X}$$ (think of $$\mathcal{X}$$ as possible outcomes or elements). An element $$x$$ from $$\mathcal{X}$$ is called a heavy-hitter if the probability of selecting $$x$$ (denoted as $$\Pr_{x' \sim D}[x' = x]$$) is greater than or equal to some threshold $$v$$. This means $$x$$ occurs frequently enough in the distribution to be considered a "heavy" element.

Definition 3.2: Approximate Heavy-Hitter Problem

• Concept: This defines the problem of identifying approximately the heavy hitters of a distribution $$D$$, given a set of samples from $$D$$.

• Formal Description: Given sample access to the distribution $$D$$, the goal is to find a set $$L$$ that approximates the set of heavy hitters ($$L_v$$) within some error margin $$\epsilon$$.

  • $$L_v$$ is the set of all $$v$$-heavy-hitters, meaning the elements whose probability is at least $$v$$.
  • The output set $$L$$ should satisfy:
    1. $$L_{v+\epsilon} \subseteq L$$: the set $$L$$ includes all elements that are $$v + \epsilon$$-heavy-hitters.
    2. $$L \subseteq L_{v-\epsilon}$$: the set $$L$$ excludes any elements that are not $$v - \epsilon$$-heavy-hitters.

• Explanation: In practice, you don't have access to the entire distribution $$D$$, only samples from it. The problem is to approximate the set of $$v$$-heavy-hitters. Due to the approximation, there's a margin of error $$\epsilon$$. You want the output set $$L$$ to include all elements that are heavy hitters with some leeway $$v + \epsilon$$, but you also want to exclude elements that aren't heavy hitters up to $$v - \epsilon$$. This ensures that the approximation is both conservative and inclusive within that error range.