Systems and methods for locally private non-interactive communications
A computer-implemented method for encoding data for communications with improved privacy includes obtaining, by a computing system comprising one or more computing devices, input data including one or more input data points. The method can include constructing, by the computing system, a net tree including potential representatives of the one or more input data points, the potential representatives arranged in a plurality of levels, the net tree including a hierarchical data structure including a plurality of hierarchically organized nodes. The method can include determining, by the computing system, a representative of each of the one or more input data points from the potential representatives of the net tree, the representative including one of the plurality of hierarchically organized nodes. The method can include encoding, by the computing system, the representative of each of the one or more input data points for communication.
1 . A computer-implemented method for encoding data for communications with improved privacy, the method comprising:
obtaining, by a computing system comprising one or more computing devices, input data comprising one or more input data points;
constructing, by the computing system, a net tree comprising potential representatives of the one or more input data points, the potential representatives arranged in a plurality of levels, the net tree comprising a hierarchical data structure comprising a plurality of hierarchically organized nodes, wherein constructing, by the computing system, the net tree comprising potential representatives of the one or more input data points comprises:
determining, by the computing system, the expansion threshold;
identifying, by the computing system, a number of one or more highest-ranking nodes in the net tree at a first level in the net tree, the number being equal to the expansion threshold; and
expanding, by the computing system, the one or more highest-ranking nodes at a second level in the net tree;
wherein the expansion threshold is based at least in part on an optimal transport cost between the one or more input data points and the potential representatives or on a lower bound on a minimum cost between the one or more input data points and the potential representatives;
determining, by the computing system, a representative of each of the one or more input data points from the potential representatives of the net tree, the representative comprising one of the plurality of hierarchically organized nodes; and
encoding, by the computing system, the representative of each of the one or more input data points for communication.
2 . The computer-implemented method of claim 1 , further comprising:
prior to determining a representative of each of the one or more input data points from the potential representatives of the net tree, projecting the one or more input data points to a random subspace; and
subsequent to projecting the one or more input data points to the random subspace, scaling the projected input data points to a subspace having reduced dimensionality.
3 . The computer-implemented method of claim 1 , wherein the communication comprises a local model of differential privacy.
4 . The computer-implemented method of claim 1 , wherein the communication comprises a shuffled model of differential privacy.
5 . The computer-implemented method of claim 1 wherein the net tree comprises a plurality of efficiently decodable nets.
6 . The computer-implemented method of claim 1 , wherein encoding, by the computing system, the representative of each of the one or more input data points for communication comprises encoding, by the computing system, the representative by a generalized bucketized vector summation encoder model.
7 . The computer-implemented method of claim 6 , wherein the generalized bucketized vector summation encoder model comprises a vector encoding of a dot product of a shared uniform random component and a potential representative.
8 . The computer-implemented method of claim 1 , wherein encoding, by the computing system, the representative of each of the one or more input data points for communication comprises encoding, by the computing system, the representative by a generalized histogram encoder model.
9 . The computer-implemented method of claim 8 , wherein the generalized histogram encoder model produces an output based on a shared uniform random component, wherein the output is positive with probability e{circumflex over ( )}ε/(e{circumflex over ( )}ε+1) and negative with probability 1/(e{circumflex over ( )}ε+1), where ε is a hyperparameter of differential privacy.
10 . The computer-implemented method of claim 1 , wherein the representative of an input data point of the one or more input data points comprises a closest potential representative to the input data point.
11 . The computer-implemented method of claim 10 , wherein the closest potential representative to the input data point comprises a potential representative having a smallest Euclidean distance to the input data point relative to each of the other potential representatives in the net tree.
12 . A computer-implemented method for clustering input data points with differential privacy guarantees and reduced approximation ratio, the computer-implemented method comprising:
obtaining, by a computing system comprising one or more computing devices, input data comprising one or more input data points;
constructing, by the computing system, a net tree comprising potential representatives of the one or more input data points, the potential representatives arranged in a plurality of levels, the net tree comprising a hierarchical data structure comprising a plurality of hierarchically organized nodes and a plurality of mappings between the plurality of hierarchically organized nodes, wherein constructing, by the computing system, the net tree comprising potential representatives of the one or more input data points comprises:
determining, by the computing system, the expansion threshold;
identifying, by the computing system, a number of one or more highest-ranking nodes in the net tree at a first level in the net tree, the number being equal to the expansion threshold; and
expanding, by the computing system, the one or more highest-ranking nodes at a second level in the net tree;
wherein the expansion threshold is based at least in part on an optimal transport cost between the one or more input data points and the potential representatives or on a lower bound on a minimum cost between the one or more input data points and the potential representatives; and
determining, by the computing system, a representative of each of the one or more input data points from the potential representatives of the net tree, the representative comprising one of the plurality of hierarchically organized nodes.
13 . The computer-implemented method of claim 12 , further comprising:
prior to determining a representative of each of the one or more input data points from the potential representatives of the net tree, projecting the one or more input data points to a random subspace; and
subsequent to projecting the one or more input data points to the random subspace, scaling the projected input data points to a subspace having reduced dimensionality.