Fix FleetwideMeans minDenominatorEstimate usage.
FleetwideMeans now returns the maximum for all denominator values >
minDenominatorEstimate. For speed, this value is estimated by doing a
linear search for the highest error through a geometric series of
denominators using r = 1.5.
Unit tests have beeen updated.
BEFORE: https://screenshot.googleplex.com/8nQFhgWtpHawjEd
AFTER: https://screenshot.googleplex.com/CnA2puxWo2nks7y
Change-Id: Iaace7ca4fb6f048716375b8ada056a07ace444cc
Reviewed-on: https://fuchsia-review.googlesource.com/c/cobalt/+/511286
Reviewed-by: Pasin Manurangsi <pasin@google.com>
Commit-Queue: Jared Weinstein <jaredweinstein@google.com>
diff --git a/src/bin/config_parser/src/privacy/error_calculator.go b/src/bin/config_parser/src/privacy/error_calculator.go
index 5d66ffe..31113d8 100644
--- a/src/bin/config_parser/src/privacy/error_calculator.go
+++ b/src/bin/config_parser/src/privacy/error_calculator.go
@@ -68,14 +68,14 @@
case config.ReportDefinition_FLEETWIDE_OCCURRENCE_COUNTS:
contributionRange := uint64(report.MaxValue - report.MinValue)
if contributionRange <= 0 {
- return -1, fmt.Errorf("contribution range must be positive to estimate error.")
+ return -1, fmt.Errorf("contribution range must be positive to estimate error")
}
population *= 24 // Hourly contribution interval: 24*population pseudo-users.
errorEstimate = multipleContributionRapporRMSE(population, probBitFlip, contributionRange, discretization)
case config.ReportDefinition_FLEETWIDE_HISTOGRAMS:
contributionRange := report.MaxCount
if contributionRange <= 0 {
- return -1, fmt.Errorf("contribution range must be posititve to estimate error.")
+ return -1, fmt.Errorf("contribution range must be positive to estimate error")
}
population *= 24 // Hourly contribution interval: 24*population pseudo-users.
errorEstimate = multipleContributionRapporRMSE(population, probBitFlip, contributionRange, discretization)
@@ -95,7 +95,10 @@
return -1, err
}
population *= 24 // Hourly contribution interval: 24*population pseudo-users.
- errorEstimate = fleetwideMeansRapporRMSE(population, probBitFlip, minDenominatorEstimate, discretization, report)
+ errorEstimate, err = fleetwideMeansRapporRMSE(population, probBitFlip, minDenominatorEstimate, discretization, report)
+ if err != nil {
+ return -1, err
+ }
default:
reportType := config.ReportDefinition_ReportType_name[int32(report.GetReportType())]
return -1, fmt.Errorf("error estimation is not supported for reports of type %s", reportType)
@@ -147,7 +150,7 @@
}
// Compute 2D-RAPPOR RMSE for the FleetwideMeans report.
-func fleetwideMeansRapporRMSE(population uint64, probBitFlip float64, minDenominatorEstimate uint64, discretization uint64, report *config.ReportDefinition) float64 {
+func fleetwideMeansRapporRMSE(population uint64, probBitFlip float64, minDenominatorEstimate uint64, discretization uint64, report *config.ReportDefinition) (float64, error) {
t := report.MaxCount
a := probBitFlip * float64(t) / (1 - 2*probBitFlip)
T := float64(math.Max(float64(-report.MinValue), float64(report.MaxValue)))
@@ -160,7 +163,22 @@
// Denominator RMSE aggregated like FleetwideHistograms.
sigma := multipleContributionRapporRMSE(population, probBitFlip, t, discretization)
- return meanRapporRMSE(mseNumerator, sigma, a, T, float64(minDenominatorEstimate))
+ // Find the max over a geometric sequence of minDenominator > minDenominatorEstimate.
+ ratio := 1.5
+ maxSequence := 20
+ previousError := 0.0
+ for n := 0; n < maxSequence; n++ {
+ minDenominator := float64(minDenominatorEstimate) * math.Pow(ratio, float64(n))
+ currentError := meanRapporRMSE(mseNumerator, sigma, a, T, minDenominator)
+ // Assume meanRapporRMSE is concave. This is not proven but is observed for
+ // significant values of minDenominatorEstimate (roughly estimate > 500)
+ if currentError <= previousError {
+ return previousError, nil
+ }
+ previousError = currentError
+ }
+ // No maximum found
+ return -1, fmt.Errorf("maximum not found after %v iterations", maxSequence)
}
func meanRapporRMSE(mseNum float64, sigma float64, a float64, T float64, B float64) float64 {
diff --git a/src/bin/config_parser/src/privacy/error_calculator_test.go b/src/bin/config_parser/src/privacy/error_calculator_test.go
index 49174a9..3de38cb 100644
--- a/src/bin/config_parser/src/privacy/error_calculator_test.go
+++ b/src/bin/config_parser/src/privacy/error_calculator_test.go
@@ -166,9 +166,9 @@
{args{&testMetric, &fleetwideMeans, 10, 10000, 500}, true, 28.078743913512465},
{args{&testMetric, &fleetwideMeans, 1, 20000, 500}, true, 551.1417346736127},
{args{&testMetric, &fleetwideMeans, 1, 10000, 2000}, true, 0.9722845785198999},
- {args{&testMetric, &fleetwideMeansHighMaxCount, 1, 10000, 500}, true, 2370.2707572142904},
- {args{&testMetric, &fleetwideMeansHighMaxCount, 10, 10000, 500}, true, 2238.0931858912145},
- {args{&testMetric, &fleetwideMeansHighMaxCount, 1, 20000, 500}, true, 2404.5027616065695},
+ {args{&testMetric, &fleetwideMeansHighMaxCount, 1, 10000, 500}, true, 4471.951966988096},
+ {args{&testMetric, &fleetwideMeansHighMaxCount, 10, 10000, 500}, true, 3203.1776450207326},
+ {args{&testMetric, &fleetwideMeansHighMaxCount, 1, 20000, 500}, true, 5217.923499327469},
{args{&testMetric, &fleetwideMeansHighMaxCount, 1, 10000, 2000}, true, 4098.32133059633},
{args{&testMetric, &uniqueDeviceCount, 0, 100000, 0}, true, 0},
@@ -177,7 +177,7 @@
{args{&testMetricWithBufferMax, &uniqueDeviceCount, 1, 10000, 0}, true, 4.935511431266572},
{args{&testMetricWithBufferMax, &fleetwideOccurrenceCount, 1, 10000, 0}, true, 386.4795472694349},
{args{&testMetricWithBufferMax, &uniqueDeviceNumericStats, 1, 10000, 500}, true, 0.03372677729859206},
- {args{&testMetricWithBufferMax, &fleetwideMeans, 1, 10000, 500}, true, 2117.7764297912554},
+ {args{&testMetricWithBufferMax, &fleetwideMeans, 1, 10000, 500}, true, 2470.4301734178152},
// Invalid input
{args{&testMetric, &uniqueDeviceNumericStats, 1, 10000, 0}, false, 0},
