Strawman: Target functionality for MVP

[benjaminsavage]

Target ads measurement use-cases for the MVP

Reporting use-cases for Ad Buyers

Counts, for all 3 types of source events

1. Count of "Click-through" attributed conversions
2. Count of "View-through" attributed conversions
3. "Conversion-lift", that is the count of conversions in "test" and "control" (source event = "Ad Opportunity")

Sums, for all 3 types of source events

1. Sum of conversion value across "Click-through" attributed conversions
2. Sum of conversion value across "View-through" attributed conversions
3. "Conversion-lift", that is the sum of conversion value in "test" and "control" (source event = "Ad Opportunity")

Multiple Breakdowns

Assuming source events are associated with multiple arbitrary breakdown keys

1. For a given set of source and trigger events, ability to generate multiple different breakdowns (e.g. campaign_id, age x gender, region)

Cross-environment

For all of the above, support for cases where source events and trigger events originate from different environments:

	App	In App Webview	Web
App	Yes	Yes	Yes
In App Webview	Yes	Yes	Yes
Web	Yes	Yes	Yes

Cross-device

For all of the above, support for cases where source events and trigger events originate from different devices. For example:

• App => Laptop
• CTV => Laptop
• CTV => App

Cross-publisher

For all of the above, support for cases where the source events originate from multiple different apps / websites operated by different ad-sellers

Multi-touch attribution

For all of the above, support for multi-touch attribution. For MVP just support for "equal credit" on the "last N touches" where "N" is a query parameter.

Aggregate use-cases for ad-sellers

• Support for aggregates spanning many different ad buyers, broken down by cross-buyer arbitrary breakdown keys (e.g. count of all purchases across all ad buyers, broken down by country)
• Ad-buyer partitioned attribution (e.g. A purchase of a phone case on website A should NOT be attributed to an ad for car insurance paid for by website B)

NOT in the MVP

The following use-cases are not a part of the MVP, but should ideally our solution should be architecturally compatible such them.

1. ML Model training
2. Offline conversions

Human language version

Inputs:

• A set of “source events”
  • Each originating from a person
  • Each with a timestamp
  • And having a sequence of Q “breakdown keys”
• A set of “trigger events”
  • Each originating from a person
  • Each with a timestamp
  • And having some “trigger value”

Outputs:

A sequence of Q histograms. Each histogram is a map from “breakdown keys” to noisy aggregate sums.

The "breakdown keys" appearing in the qth histogram (q = 0 to q = Q-1) are the unique values of "breakdown key" appearing in the qth place in the sequence of "breakdown keys" in the "source events".

Ideal functionality:

• For each trigger event, see if there are any source events from the same person which happened before that trigger event.
• If there are, split the trigger value equally across the last K, adding these fractions of the trigger value to the running sums for the corresponding breakdown keys.
• Cap each user’s total contribution (across all breakdown keys) to at most M.
• Finally, add a small amount of random noise to the running sums to provide a differential privacy guarantee.
• Finally, return the list of breakdown keys with their corresponding noisy sums.

Pseudocode

function(source_events, trigger_events, last_n_touches, max_contribution, budget_query_to_consume) {
    let breakdown_running_sums = {};
    let unique_breakdown_keys = source_events.map(|s| s.breakdown_key).unique()
    for each b in unique_breakdown_keys
        breakdown_running_sums[b] = 0;
    end
    
    let user_total_contributions = {};
    let unique_people = source_events.concat(trigger_events).map(|x| x.match_key).unique()
    for each p in unique_people
        user_total_contributions[p] = 0;
    end
    
    for each t in trigger_events
        let attribution_candidates = {}
        for each s in source_events
            if s.match_key == t.match_key AND s.timestamp < t.timestamp
                attribution_candidates.add(s)
            end
        end
		        
        let attributed_source_events = attribution_candidates
            .sort_descending(|x, y| x.timestamp ⇔ y.timestamp)
            .slice(1, last_n_touches)
        
        if attributed_source_events.empty()
            continue;
        end
        
        if user_total_contributions[t.match_key] + t.trigger_value <= max_contribution
            user_total_contributions[t.match_key] += t.trigger_value
            let num_touches = attributed_source_events.cardinality()
            for each a in attributed_source_events
                breakdown_running_sums[a.breakdown_key] += (t.trigger_value / num_touches)
            end
        end
    end
    
    let noise_distribution = get_noise_distribution(TARGET_EPSILON, max_contribution, budget_query_to_consume)
    for each b in unique_breakdown_keys
        breakdown_running_sums[b] += noise_distribution.sample()
    end
    
    return breakdown_running_sums;
end

Mathy Version

Givens

Given n source events, i = 0 through i = n - 1, each comprised of three unsigned integer values:

• match key: m^s_i
• timestamp: t^s_i
• breakdown key: b_i

Given m trigger events, j = 0 through j = m - 1, each comprised of three unsigned integer values:

• match key: m^t_j
• timestamp: t^t_j
• trigger value: v_j (values validated to all lie between 1 and value_max)

Given an integer K, value between 1 and 5 (inclusive), indicating the maximum number of source events to which a particular trigger event should be attributed.

Given an integer M, indicating the maximum total value any particular user should be able to contribute to the output across all breakdown keys. (This value should be at least as large as the maximum trigger value)

Given an integer P, value between 1 and 100 (inclusive), indicating the amount of privacy budget the query should consume.

Ideal Functionality

Let the set of unique breakdown keys be known as B

Let the set of attribution candidates C_j be equal to the set of source events for which: m^t_j == m^s_i and t^s_i < t^t_j
Let the set of attributed source events A^s_j be the MIN( |C_j|, K ) elements from C_j with the largest values of t^s_i
Let the list of attributed breakdown keys B^j be the values of the breakdown keys from A^s_j
Let the set of attributed trigger events A^t be equal to the subset of tuples (m^t_j, v_j, B^j) where A^s_j is non-empty
Let U be the set of unique match keys m in A^t
Let the set of capped events Q be a subset of elements selected from attributed trigger events such each match key's total contribution is at most M. Put another way:
Given a match key m_k in U
Let the total contribution t_k of match key m_k be equal to the sum Σv_j where m_j == m_k, across all the tuples (m_j, v_j, B^j) in Q
Then for all match keys m_k in U, it is true that t_k <= M
Let count^j_b be the number of times that breakdown key b appears in the list B^j
Let the no noise total total_b of breakdown key b be equal to the sum: Σ(v_j/|B^j|) * count^j_b across all the tuples (m_j, v_j, B^j) in Q
Let the noised total noised_total_b for each breakdown key b in B, be equal to the sum of total_b + random_noise(M, P)
Return the set of tuples (b, noised_total_b) for each breakdown key b in B

[eriktaubeneck]

Thanks for this write up @benjaminsavage. I hope it will help clarify the conversation tomorrow.

The only thing I'd add is that along with counts and sums, we often also want variance (of the value.) This is particularly acute in the "conversion-lift" case, where we want to establish a statistically significant difference between the test and control group (but more generally, all these are often used for comparisons, which are more meaningful with a measure of variance.)

One small wrinkle here is that we may actually prefer a differential private confidence interval, rather than a differentially private mean (eg sum) and variance, as it may be more efficient (in terms of the privacy budget.) This latter point is probably beyond scope for an MVP, but something else we may want to be able to support in the future.

[martinthomson]

When you define "breakdown keys" you don't mention the site on which source event occurred. Did you mean to make that one of the factors that might be used to determine a breakdown key?

I've a few quibbles with your Mathy bit, but mostly presentation-wise. Let's concentrate on what I think your intent is.

In my slides for tomorrow, I had something like:

1. For each conversion on site X, find all ad events that:
   • are from the same browser person,
   • precede the conversion, and
   • meet some additional conditions
2. For those events, calculate a function over associated values
3. Aggregate the results of each calculation against the site in the ad event using a second function

You have described concrete versions of both the per-conversion and aggregation functions that I think could (with appropriate values for $\varepsilon$) meet our goals. I hope that we will be in a position to swap those functions out as we learn more, but as a first attempt, these seem plausible to me. Though I have to point out that my interests are in making this work while maintaining privacy. I don't have to live with the utility this produces, so my opinion here means very little.

[csharrison]

Thanks @benjaminsavage for the strawman. I want to poke at one aspect which is multiple breakdown keys per source event. This is listed as ideal functionality but isn't described in the detailed code / math. I would vote to add this. My goal is to try to achieve some level of sensitivity management that I discussed in the last meeting in the MVP. This will improve the utility of the system as a whole and unlock new use-cases. With multiple breakdown keys per source this is achievable with some changes to the underlying algorithm:

• Multiple queries to the system are configured by appending multiple breakdown keys to each source (for simplicity, assume every source has exactly q >= 1 breakdown keys)
• Amend the pseudocode function to take an index q_i, and edit the algorithm to just consider the q_ith breakdown key
• Run the main algorithm q times, with some custom noise distribution function based on q

Obviously, the above can be optimized to avoid q joins, but that's the overall idea. What this unlocks is the ability for us to take advantage of advanced DP composition, so multi-query settings can receive much smaller effective noise. How this works is by enforcing additional sensitivity constraints on the system, by varying q and the max_contribution parameter. The Linf sensitivity of the entire (multi-)query is equal to max_contribution and the L1 sensitivity is equal to q * max_contribution, so the L2 sensitivity is equal to max_contribution * sqrt(q)

Note: there are other ways of achieving this goal, but I think this serves as a flexible basis, and is probably the simplest without making the core algorithm more complicated in how it does contribution capping. We can do more advanced things by varying max_contribution per sub-query, and the noise scale per query without impacting the core algorithm too. We could also constrain individual subqueries more by defining a max_contribution_per_breakdown_key param to the core algorithm, which would improve utility if the ad-tech expects user contributions across many keys in one subquery. That seems less generally useful to me although I'm sure there are some use-cases where it works well.

I also want to make sure that privacy unit / grain discussions happen on the other issue and not here, despite it being embedded in the algorithm here.

[benjaminsavage]

@csharrison - this is an excellent suggestion. I completely agree with you. I think there is a very nice win here for API callers who would like to make N queries, on the same set of input data, and want to do N different breakdowns. I'd love to get that sweet, sweet advanced DP composition win =).

I'll try to update the algorithm, if I can, to do what you've said.

[martinthomson]

Do you want a different values for each different breakdown? That is, if you are going for breakdown 1, you might be counting (low sensitivity), but breakdown 2 might be a sum over a different breakdown.

[csharrison]

@martinthomson my suggestion was assuming a fixed trigger_value per trigger. I think you could easily extend the proposal to do something like choose what statistic to be aggregating (count, sum) across each of the q queries. You could also do more advanced epsilon budgeting within a batch of queries if you know for sure that some queries can tolerate more noise (this last one is a more sophisticated technique but should totally be possible).

[AramZS]

Would we like to present these in an upcoming meeting?

[benjaminsavage]

I think in an upcoming meeting we should discuss the "multiple-breakdown" use-case.

As @csharrison mentions in his comment above, "sensitivity management" is really important here to ensure good DP composition.

But I'd like to file a separate issue about this topic. I'm happy to close this issue.