Data dependent preferred region for noise generation

1 . A system comprising one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

computing a preferred region for true query answers for a kernel differentially private mechanism using a noise value for a query for the kernel differentially private mechanism, a true query answer for a query for the kernel differentially private mechanism, and a relative error ratio for the preferred region;

computing, for the kernel differentially private mechanism, a privacy parameter and a boosting rate that increases variance in outputs for the kernel differentially private mechanism using the preferred region for true query answers for the kernel differentially private mechanism;

maintaining a plurality of output data received from one or more client devices;

receiving, from a downstream system, a query for data from a dataset;

generating a response to the query that includes noise data using the kernel differentially private mechanism that includes the privacy parameter; and

transmitting, to the downstream system, the response to the query.

2 . The system of claim 1 , the operations comprising:

computing a probability that output from the kernel differentially private mechanism falls in the preferred region using, as input to a cumulative density function, an offset that increases a first likelihood that the preferred region remains valid given the dataset for query answers for the kernel differentially private mechanism; and

computing the boosting rate using the probability and a confidence level indicating a second likelihood that the output from the kernel differentially private mechanism falls within the preferred region.

3 . The system of claim 2 , wherein computing the probability comprises computing the probability using a combination of a first output of the cumulative density function with a first sign of the offset as input and a second output of the cumulative density function with a second, different sign of the offset as input.

4 . The system of claim 2 , wherein computing the privacy parameter comprises:

computing at least one loss using the boosting rate and, as input to a cumulative density function, the offset, and a sensitivity of the query;

computing at least one weight using, as input to a cumulative density function, the offset, a sensitivity of the query; and

computing the privacy parameter using the at least one loss and the at least one weight.

5 . The system of claim 1 , the operations comprising:

computing a probability that output from the kernel differentially private mechanism falls in the preferred region using the true query answer, the relative error ratio, and an offset that increases a first likelihood that the preferred region remains valid given a dataset for query answers for the kernel differentially private mechanism; and

computing the boosting rate using the probability and a confidence level indicating a second likelihood that the output from the kernel differentially private mechanism falls within the preferred region.

6 . The system of claim 5 , wherein computing the probability comprises computing the probability using, as input to a cumulative density function, the true query answer, the relative error ratio, and the offset that increases the first likelihood that the preferred region remains valid given the dataset for query answers for the kernel differentially private mechanism.

7 . The system of claim 1 , wherein computing the preferred region uses the true query answer for a query for the kernel differentially private mechanism, the relative error ratio for the preferred region, and an offset that increases a likelihood that the preferred region remains valid given a dataset for query answers for the kernel differentially private mechanism.

8 . The system of claim 7 , comprising computing the offset using a dataset that includes the preferred region and the true query answer to increase a likelihood that the preferred region remains valid for true query answers to queries.

9 . One or more computer storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

computing a preferred region for true query answers for a kernel differentially private mechanism using a noise value for a query for the kernel differentially private mechanism, a true query answer for a query for the kernel differentially private mechanism, and a relative error ratio for the preferred region;

computing, for the kernel differentially private mechanism, a privacy parameter and a boosting rate that increases variance in outputs for the kernel differentially private mechanism using the preferred region for true query answers for the kernel differentially private mechanism;

maintaining a plurality of output data received from one or more client devices;

receiving, from a downstream system, a query for data from a dataset;

generating a response to the query that includes noise data using the kernel differentially private mechanism that includes the privacy parameter; and

transmitting, to the downstream system, the response to the query.

10 . The computer storage media of claim 9 , the operations comprising:

computing a probability that output from the kernel differentially private mechanism falls in the preferred region using, as input to a cumulative density function, an offset that increases a first likelihood that the preferred region remains valid given the dataset for query answers for the kernel differentially private mechanism; and

computing the boosting rate using the probability and a confidence level indicating a second likelihood that the output from the kernel differentially private mechanism falls within the preferred region.

11 . The computer storage media of claim 10 , wherein computing the probability comprises computing the probability using a combination of a first output of the cumulative density function with a first sign of the offset as input and a second output of the cumulative density function with a second, different sign of the offset as input.

12 . The computer storage media of claim 10 , wherein computing the privacy parameter comprises:

computing at least one loss using the boosting rate and, as input to a cumulative density function, the offset, and a sensitivity of the query;

computing at least one weight using, as input to a cumulative density function, the offset, a sensitivity of the query; and

computing the privacy parameter using the at least one loss and the at least one weight.

13 . The computer storage media of claim 9 , the operations comprising:

computing a probability that output from the kernel differentially private mechanism falls in the preferred region using the true query answer, the relative error ratio, and an offset that increases a first likelihood that the preferred region remains valid given a dataset for query answers for the kernel differentially private mechanism; and

computing the boosting rate using the probability and a confidence level indicating a second likelihood that the output from the kernel differentially private mechanism falls within the preferred region.

14 . The computer storage media of claim 13 , wherein computing the probability comprises computing the probability using, as input to a cumulative density function, the true query answer, the relative error ratio, and the offset that increases the first likelihood that the preferred region remains valid given the dataset for query answers for the kernel differentially private mechanism.

15 . The computer storage media of claim 9 , wherein computing the preferred region uses the true query answer for a query for the kernel differentially private mechanism, the relative error ratio for the preferred region, and an offset that increases a likelihood that the preferred region remains valid given a dataset for query answers for the kernel differentially private mechanism.

16 . The computer storage media of claim 15 , comprising computing the offset using a dataset that includes the preferred region and the true query answer to increase a likelihood that the preferred region remains valid for true query answers to queries.

17 . A computer-implemented method comprising:

computing a preferred region for true query answers for a kernel differentially private mechanism using a noise value for a query for the kernel differentially private mechanism, a true query answer for a query for the kernel differentially private mechanism, and a relative error ratio for the preferred region;

computing, for the kernel differentially private mechanism, a privacy parameter and a boosting rate that increases variance in outputs for the kernel differentially private mechanism using the preferred region for true query answers for the kernel differentially private mechanism;

maintaining a plurality of output data received from one or more client devices;

receiving, from a downstream system, a query for data from a dataset;

generating a response to the query that includes noise data using the kernel differentially private mechanism that includes the privacy parameter; and

transmitting, to the downstream system, the response to the query.

18 . The method of claim 17 , comprising:

computing a probability that output from the kernel differentially private mechanism falls in the preferred region using, as input to a cumulative density function, an offset that increases a first likelihood that the preferred region remains valid given the dataset for query answers for the kernel differentially private mechanism; and

computing the boosting rate using the probability and a confidence level indicating a second likelihood that the output from the kernel differentially private mechanism falls within the preferred region.

19 . The method of claim 18 , wherein computing the probability comprises computing the probability using a combination of a first output of the cumulative density function with a first sign of the offset as input and a second output of the cumulative density function with a second, different sign of the offset as input.

20 . The method of claim 18 , wherein computing the privacy parameter comprises:

computing at least one loss using the boosting rate and, as input to a cumulative density function, the offset, and a sensitivity of the query;

computing at least one weight using, as input to a cumulative density function, the offset, a sensitivity of the query; and

computing the privacy parameter using the at least one loss and the at least one weight.