Hands-On Differential Privacy

Chapter 6. Fearless Combinators

In the context of DP, the term combinators encompasses algorithms that build new stable transformations and private mechanisms from other functions. Many algorithms in differential privacy can be expressed this way, making it a useful qualifier to describe a class of DP algorithms. While the name combinator may seem complex at first, the concept is completely approachable. You are already familiar with chaining and composition, which are two examples of combinators. The main topics discussed in this chapter are:

• Chaining

• Privacy measure conversion

• Generalized composition

• Privacy amplification

• Sample and aggregate

• Private selection from private candidates

Along the way, you’ll learn about some new mechanisms that can be built up from previous mechanisms, through the use of these combinators:

• Bounds estimation (chaining/postprocessing)

• B-Trees (chaining/postprocessing)

• Sparse vector technique (adaptive composition)

• Multi-quantiles (parallel composition)

• Shuffle-DP (amplification)

• k-means (private selection from private candidates)

Chaining

Chaining is another word for functional composition, where a new function is constructed that iteratively applies two functions to an input:¹

$$f_c(x)=f_2(f_1(x))$$

The combinator representation doesn’t fix the initial argument $x$, instead opting to delay application:

def make_chain_mt(f_2, f_1):
    """Construct a new measurement representing f_c(x) = f_2(f_1(x))"""
    # check that f_1 is a transformation ...