We characterize the minimum noise amplitude and power for noise-adding mechanisms in (epsilon, delta)-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by analyzing a special class of (epsilon, delta)-differentially private mechanisms, the truncated Laplacian mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.

Quantization based techniques are the current state-of-the-art for scaling maximum inner product search to massive databases. Traditional approaches to quantization aim to minimize the reconstruction error of the database points. Based on the observation that for a given query, the database points that have the largest inner products are more relevant, we develop a family of anisotropic quantization loss functions. Under natural statistical assumptions, we show that quantization with these loss functions leads to a new variant of vector quantization that more greatly penalizes the parallel component of a datapoint’s residual relative to its orthogonal component. The proposed approach, whose implementation is open-source, achieves state-of-the-art results on the public benchmarks available at ann-benchmarks.com.

We derive the optimal $(0, \delta)$-differentially private query-output independent noise-adding mechanism for single real-valued query function under a general cost-minimization framework. Under a mild technical condition, we show that the optimal noise probability distribution is a uniform distribution with a probability mass at the origin. We explicitly derive the optimal noise distribution for general $\ell^p$ cost functions, including $\ell^1$ (for noise magnitude) and $\ell^2$ (for noise power) cost functions, and show that the probability concentration on the origin occurs when $\delta > \frac{p}{p+1}$. Our result demonstrates an improvement over the existing Gaussian mechanisms by a factor of two and three for $(0,\delta)$-differential privacy in the high privacy regime in the context of minimizing the noise magnitude and noise power, and the gain is more pronounced in the low privacy regime. Our result is consistent with the existing result for $(0,\delta)$-differential privacy in the discrete setting, and identifies a probability concentration phenomenon in the continuous setting.

We derive a new outer bound on the capacity region of broadcast traffic in multiple input broadcast packet erasure channels with feedback, and extend this outer bound to packet erasure relay networks with feedback. We show the tightness of the outer bound for various classes of networks. An important engineering implication of this work is that for network coding schemes for parallel broadcast channels, the “xor” packets should be sent over correlated broadcast subchannels.

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queriesqueries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ϵ-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1and ℓ2cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (ϵ is small), the Laplacian mechanism is asymptotically optimal as ϵ → 0; in the low privacy regime (ϵ is large), the minimum magnitude and second moment of noise are Θ(Δe(-ϵ/2)) and Θ(Δ2e(-2ϵ/3)) as ϵ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/ϵ and 2Δ2/ϵ2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

We study the (nearly) optimal mechanisms in (ϵ, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ϵ and δ in utility and privacy analysis for histogram-like query functions, and show that the (ϵ, δ)-differential privacy is a framework not much more general than the (ϵ, 0)-differential privacy and (ϵ, δ)-differential privacy in the context of ℓ1and ℓ2cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1and ℓ2cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (ϵ, δ) → (0, 0)). We conclude that in (ϵ, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/ϵ), (1/δ))) and Θ(min((1/ϵ2), (1/δ2))), respectively, in the high privacy regime.

We consider symmetric two-user Gaussian interference channel with common messages. We derive an upper bound on the sum capacity, and show that the upper bound is tight in the very low interference regime, where the optimal transmission scheme is to send no common messages and each receiver treats interference as noise. Our result shows that although the availability of common messages provides a cooperation opportunity for transmitters, in the low interference regime the presence of common messages does not help increase the sum capacity.

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this work we study the fundamental tradeoff between privacy and utility in differential privacy. We derive the optimal ε-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions, which can be viewed as a geometric mixture of uniform probability distributions. In the context of ℓ1and ℓ2utility functions, we show that the standard Laplacian mechanism, which has been widely used in the literature, is asymptotically optimal in the high privacy regime, while in the low privacy regime, the staircase mechanism performs exponentially better than the Laplacian mechanism. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While there is a body of empirical evidence suggesting this approach does learn very effective representations, there is little theoretical guarantee. In this paper, we show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the ℓ1norm. Namely, if A ∈ ℝm×nis an incoherent (and possibly overcomplete) dictionary, and the coefficients X ∈ ℝn×pfollow a random sparse model, then with high probability (A, X) is a local minimum of the ℓ1norm over the manifold of factorizations (A', X') satisfying A'X' = Y, provided the number of samples p = Ω(n3k). For overcomplete A, this is the first result showing that the dictionary learning problem is even locally solvable using ℓ1-minimization.

We study interference channels (IFCs) where the interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other using full-duplex radios. The interaction can come in two ways. First is through in-band interaction where sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. Second is through out-of-band interaction where destinations talk back to the sources on an out-of-band channel, which is possible from white-space channels. The flexibility afforded by the interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties,” i.e., insensitivity to the rationality or irrationality of channel parameters, small block lengths, and finite SNR operations. We show that, for several classes of IFCs, the interactive IA scheme can achieve the optimal degrees of freedom. In particular, we show a simple scheme (having a finite block length for channels having no diversity) for three-user and four-user IFCs with full-duplex radios to achieve the optimal degrees of freedom even after accounting for the cost of interaction. On the technical side, we show using a Gröbner basis argument that, in a general network potentially utilizing cooperation and feedback, the optimal degrees of freedom under linear schemes of a fixed block length is the same for channel coefficients with a probability of 1. Furthermore, a numerical method to estimate this value is also presented. These tools have potentially wider utility in studying other wireless networks as well.

We study interference channels (IFC) where interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other. The interaction can come in two ways: 1) for half-duplex radios, destinations can talk back to sources using either simultaneous out-of-band (white spaces) transmission or in-band half-duplex transmission; 2) for full-duplex radios, both sources and destinations can transmit and listen in the same channel simultaneously. The flexibility afforded by interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties”: insensitivity to the rationality or irrationality of channel parameters, small block lengths and finite SNR operations. We show that for several classes of interference channels the interactive interference alignment scheme can achieve the optimal degrees of freedom.