A bounded algorithm is any algorithm that requires lower and upper input bounds as parameters. There is no BoundedAlgorithm interface as a subclass of Algorithm, but Algorithms that need bounds do share a common builder interface. Bounded algorithms are constructed using a BoundedAlgorithmBuilder, which is a subclass of AlgorithmBuilder.
Bounded algorithms can be constructed in two ways. The first way is to set lower and upper input bounds directly. The second is to omit setting the bounds. If bounds are omitted, some algorithms will spend a portion of their privacy budget (epsilon and delta) to automatically infer and set the bounds. How exactly the bounded algorithm infers the bounds can be configured using the ApproxBounds algorithm; see its page for more information. If you have knowledge about the range of your input data you can use it to set bounds explicitly. This will leave more budget for adding noise. Otherwise, it is often better to infer the bounds than to guess and overstimate them.
BoundedAlgorithmBuilder builder =
BoundedAlgorithmBuilder().SetEpsilon(double epsilon)
// Option 1: Set bounds directly.
base::StatusOr<std::unique_ptr<Algorithm<T>>> bounded_algorithm =
builder.SetLower(T lower)
.SetUpper(T upper)
.Build();
// Option 2: Automatically infer bounds.
base::StatusOr<std::unique_ptr<Algorithm<T>>> bounded_algorithm =
builder.Build();
T is the template parameter type (usually int64 or double).T lower: The lower bound of input to the algorithm. If an input is less than lower, it will be clamped to lower.T upper: The upper bound of input to the algorithm. If an input is greater than upper, it will be clamped to upper.The following algorithms are bounded, and automatically infer bounds using the ApproxBounds algorithm if they are not set manually.
The following algorithms are bounded, but use numeric limits as bounds if they are not set manually.
How do the bounds affect the algorithm? As we have mentioned, values less than the lower bound or greater than the upper bound are clamped to be equal to the lower or upper bound, respectively. If the interval between bounds is too narrow, many input values will be clamped, degrading accuracy.
However, bounds are also used to determine the amount of noise we add to the algorithm results to provide privacy. The relationship between the bounds used and the amount of noise added varies between algorithms. However, as a general rule, larger bound intervals map to more noise added. So a loose bound interval around an input set also degrades accuracy. We must set our bounds to balance between these two sources of inaccuracy.