Pseudocode of an OpenDP combinator for privatizing a certain class of vector-valued transformations

make_stable_constructor.py

# Pseudocode of an OpenDP combinator for privatizing a certain class of vector-valued transformations

def make_some_transformation_stable(trans_query: Transformation, scale, threshold):
    assert trans_query.input_metric == SymmetricDistance
    assert trans_query.output_metric == L1Distance
    # must be equivalent to representation 2 in https://arxiv.org/pdf/1709.05396.pdf, Section 2.2.1
    assert trans_query.output_domain == HashMapDomain[AllDomain[KeyType], AllDomain[FloatCountType]]

    def function(data):
        noised = {k: v + sample_laplace(scale) for k, v in trans_query.invoke(data)}
        thresholded = {k: v for k, v in noised if v >= threshold}
        return shuffle(thresholded)

    def privacy_relation(d_in, d_out) -> bool:
        eps, delta = d_out
        l1_sens = binary_search(lambda o: trans_query.check(d_in, o), bounds=(0., 1e10))
        # This also works in opendp:
        # l1_sens = trans_query.stability_relation.forward_map(d_in)
        ideal_scale = l1_sens / eps
        # We don't have a way to get scalar_sens. 
        # For counting queries, scalar_sens is just d_in.
        ideal_threshold = scalar_sens + ideal_scale * ln(d_in/(2*delta))
        return scale >= ideal_scale and threshold >= ideal_threshold

    return Measurement(
        input_domain=trans_query.input_domain,
        output_domain=trans_query.output_domain,
        function=function,
        input_metric=trans_query.input_metric,
        output_measure=SmoothedMaxDivergence,
        privacy_relation=privacy_relation)