The cumulative distribution function (CDF) is fundamental due to its ability to reveal information about random variables, making it essential in studies that require privacy-preserving methods to protect sensitive data. This paper introduces a novel privacy-preserving CDF method inspired by the functional analysis and functional mechanism. Our approach projects the empirical CDF into a predefined space, approximating it using specific functions, and protects the coefficients to achieve a differentially private empirical CDF. Compared to existing methods like histogram queries and adaptive quantiles, our method is preferable in decentralized settings and scenarios where CDFs must be updated with newly collected data.

Deploying complex machine learning models on resource-constrained devices is challenging due to limited computational power, memory, and model retrainability. To address these limitations, a hybrid system can be established by augmenting the local model with a server-side model, where samples are selectively deferred by a *rejector* and then sent to the server for processing. The hybrid system enables efficient use of computational resources while minimizing the overhead associated with server usage. The recently proposed Learning to Help (L2H) model proposed training a server model given a fixed local (client) model. This differs from the Learning to Defer (L2D) framework which trains the client for a fixed (expert) server. In both L2D and L2H, the training includes learning a rejector at the client to determine when to query the server. In this work, we extend the L2H model from binary to multi-class classification problems and demonstrate its applicability in a number of different scenarios of practical interest in which access to the server may be limited by cost, availability, or policy. We derive a stage-switching surrogate loss function that is differentiable, convex, and consistent with the Bayes rule corresponding to the 0-1 loss for the L2H model. Experiments show that our proposed methods offer an efficient and practical solution for multi-class classification in resource-constrained environments.

In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the “power” constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity.

Federated analysis can help perform large-scale analyses using neuroimaging datasets across various research groups overcoming the limitations of institutional data-sharing policies, privacy or regulatory concerns as it requires no data sharing. In this work, we employ a federated neuromark algorithm to generate independent component analysis (ICA) time courses data from functional magnetic resonance imaging (fMRI) data and feed it to a federated deep neural network (DNN) model to perform classification of schizophrenia patients versus controls.

Federated learning (FL) for distributed data has gained significant attention by enabling model training on local data without transferring it to a central system. While this approach protects sensitive information, risks of data leakage still persist, necessitating the integration of privacy-preserving techniques such as differential privacy. In many FL applications, tasks like exploratory data analysis or tracking and monitoring data that change over time are essential. For these purposes, analysts rely on data visualizations to make decisions or draw conclusions. This vision paper emphasizes the importance of federated privacy-preserving visualization and outlines a general pipeline for its implementation. We discuss the challenges of integrating federated visualizations with differential privacy and demonstrate the feasibility of this approach through examples, such as federated privacy-preserving boxplots, scatterplots, and correlation visualizations in neuroimaging. This highlights the need for further research in this promising field.

Biomedical imaging systems often produce multidimensional signals (tensors). The high expense of image acquisition limits sample sizes and privacy regulations can prevent centralizing data from multiple sites. Federated learning can allow researchers to form research consortia to perform joint analyses without centralizing data. Standard analysis approaches for tensors often vectorize the data, resulting in high dimensional models for which the total sample size across a consortium may be insufficient. We propose a federated algorithm for tensor regression using generalized linear models (GLMs) based on a recently proposed centralized method using low separation rank (LSR) tensor decompositions. Our results show that by balancing the ratio of local update steps to rounds of communication, we can achieve results similar to those of a centralized algorithm using the entire data.

A recent trend in explainable AI research has focused on surrogate modeling, where neural networks are approximated as simpler ML algorithms such as kernel machines. A second trend has been to utilize kernel functions in various explain-by-example or data attribution tasks. In this work, we combine these two trends to analyze approximate empirical neural tangent kernels (eNTK) for data attribution. Approximation is critical for eNTK analysis due to the high computational cost to compute the eNTK. We define new approximate eNTK and perform novel analysis on how well the resulting kernel machine surrogate models correlate with the underlying neural network. We introduce two new random projection variants of approximate eNTK which allow users to tune the time and memory complexity of their calculation. We conclude that kernel machines using approximate neural tangent kernel as the kernel function are effective surrogate models, with the introduced trace NTK the most consistent performer.

We propose a concatenated code construction for a class of discrete-alphabet oblivious arbitrarily varying channels (AVCs) with cost constraints. The code has time and space complexity polynomial in the blocklength$n$. It uses a Reed-Solomon outer code, logarithmic blocklength random inner codes, and stochastic encoding by permuting the codeword before transmission. When the channel satisfies a condition called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability originally due to Dobrushin and Stambler), we show that the code achieves a rate that for a variety of oblivious AVCs (such as classically studied error/erasure channels) match the known capacities.

Future real-time applications like smart cities will use complex Machine Learning (ML) models for a variety of tasks. Timely status information is required for these applications to be reliable. Offloading computation to a mobile edge cloud (MEC) can reduce the completion time of these tasks. However, using the MEC may come at a cost such as related to use of a cloud service or privacy. In this paper, we consider a source that generates time-stamped status updates for delivery to a monitor after processing by the mobile device or MEC. We study how a scheduler must forward these updates to achieve timely updates at the monitor but also limit MEC usage. We measure timeliness at the monitor using the age of information (AoI) metric. We formulate this problem as an infinite horizon Markov decision process (MDP) with an average cost criterion. We prove that an optimal scheduling policy has an age-threshold structure that depends on how long an update has been in service.

We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and "sufficiently myopic" models. For the "insufficiently myopic" adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates.

We investigate the spectral properties of linear-width feed-forward neural networks, where the sample size is asymptotically proportional to network width. Empirically, we show that the spectra of weight in this high dimensional regime are invariant when trained by gradient descent for small constant learning rates; we provide a theoretical justification for this observation and prove the invariance of the bulk spectra for both conjugate and neural tangent kernels. We demonstrate similar characteristics when training with stochastic gradient descent with small learning rates. When the learning rate is large, we exhibit the emergence of an outlier whose corresponding eigenvector is aligned with the training data structure. We also show that after adaptive gradient training, where a lower test error and feature learning emerge, both weight and kernel matrices exhibit heavy tail behavior. Simple examples are provided to explain when heavy tails can have better generalizations. We exhibit different spectral properties such as invariant bulk, spike, and heavy-tailed distribution from a two-layer neural network using different training strategies, and then correlate them to the feature learning. Analogous phenomena also appear when we train conventional neural networks with real-world data. We conclude that monitoring the evolution of the spectra during training is an essential step toward understanding the training dynamics and feature learning.

We study the low-rank phase retrieval problem, where the objective is to recover a sequence of signals (typically images) given the magnitude of linear measurements of those signals. Existing solutions involve recovering a matrix constructed by vectorizing and stacking each image. These solutions model this matrix to be low-rank and leverage the low-rank property to decrease the sample complexity required for accurate recovery. However, when the number of available measurements is more limited, these low-rank matrix models can often fail. We propose an algorithm called Tucker-Structured Phase Retrieval (TSPR) that models the sequence of images as a tensor rather than a matrix that we factorize using the Tucker decomposition. This factorization reduces the number of parameters that need to be estimated, allowing for a more accurate reconstruction. We demonstrate the effectiveness of our approach on real video datasets under several different measurement models.

A source generates time-stamped update packets that are sent to a server and then forwarded to a monitor. This occurs in the presence of an adversary that can infer information about the source by observing the output process of the server. The server wishes to release updates in a timely way to the monitor but also wishes to minimize the information leaked to the adversary. We analyze the trade-off between the age of information (AoI) and the maximal leakage for systems in which the source generates updates as a Bernoulli process. For a time slotted system in which sending an update requires one slot, we consider three server policies: (1) Memoryless with Bernoulli Thinning (MBT): arriving updates are queued with some probability and head-of-line update is released after a geometric holding time; (2) Deterministic Accumulate-and-Dump (DAD): the most recently generated update (if any) is released after a fixed time; (3) Random Accumulate-and-Dump (RAD): the most recently generated update (if any) is released after a geometric waiting time. We show that for the same maximal leakage rate, the DAD policy achieves lower age compared to the other two policies but is restricted to discrete age-leakage operating points.

We characterize the capacity for the discrete-time arbitrarily varying channel with discrete inputs, outputs, and states when (a) the encoder and decoder do not share common randomness, (b) the input and state are subject to cost constraints, (c) the transition matrix of the channel is deterministic given the state, and (d) at each time step the adversary can only observe the current and past channel inputs when choosing the state at that time. The achievable strategy involves stochastic encoding together with list decoding and a disambiguation step. The converse uses a two-phase "babble-and-push" strategy where the adversary chooses the state randomly in the first phase, list decodes the output, and then chooses state inputs to symmetrize the channel in the second phase. These results generalize prior work on specific channels models (additive, erasure) to general discrete alphabets and models.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most$2\log (n)$bits in one sub-regime, and at most$\Omega ({n})$bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.

Motivated by traffic analysis attacks based on the packet sizes and timing information in the Internet of Things (IoT) networks, we establish a rigorous event-level differential privacy (DP) model on infinite packet streams. We propose a traffic shaper satisfying a first-come-first-served queuing discipline that outputs traffic dependent on the input using a DP mechanism. We show that in special cases the proposed mechanism recovers existing shapers which standardize the output independently from the input. To find the optimal shapers for given levels of privacy and transmission efficiency, we formulate the constrained problem of minimizing the expected delay per packet and propose using the expected queue size across time as a proxy. We further show that the constrained minimization is a convex program. We demonstrate the effect of shapers on both synthetic data and packet traces from actual IoT devices. The experimental results reveal inherent privacy-overhead tradeoffs: more shaping overhead provides better privacy protection. Under the same privacy level, there is a tradeoff between dummy traffic and delay. When shaping heavier or less bursty traffic, all shapers become more overhead-efficient. We also show that increased traffic from more IoT devices makes guaranteeing event-level privacy easier. The DP shaper offers tunable privacy that is invariant with the change in the input traffic distribution and has an advantage in handling burstiness over traffic-independent shapers. This approach accommodates heterogeneous network conditions and user demands in privacy and overhead.

The presence of correlation is known to make privacy protection more difficult. We investigate the privacy of socially contagious attributes on a network of individuals, where each individual possessing that attribute may influence a number of others into adopting it. We show that for contagions following the Independent Cascade model there exists a giant connected component of infected nodes, containing a constant fraction of all the nodes who all receive the contagion from the same set of sources. We further show that it is extremely hard to hide the existence of this giant connected component if we want to obtain an estimate of the activated users at an acceptable level. Moreover, an adversary possessing this knowledge can predict the real status (“active” or “inactive”) with decent probability for many of the individuals regardless of the privacy (perturbation) mechanism used. As a case study, we show that the Wasserstein mechanism, a state-of-the-art privacy mechanism designed specifically for correlated data, introduces a noise with magnitude of order Ω(n) in the count estimation in our setting. We provide theoretical guarantees for two classes of random networks: Erdős-Rényi graphs and Chung-Lu power-law graphs under the Independent Cascade model. Experiments demonstrate that a giant connected component of infected nodes can indeed appear in real-world networks and a simple inference attack can reveal the status of a good fraction of nodes.

We provide high-probability sample complexity guarantees for exact structure recovery and accurate predictive learning using noise-corrupted samples from an acyclic (tree-shaped) graphical model. The hidden variables follow a tree-structured Ising model distribution, whereas the observable variables are generated by a binary symmetric channel taking the hidden variables as its input (flipping each bit independently with some constant probability $q\in [0,1/2)$). In the absence of noise, predictive learning on Ising models was recently studied by Bresler and Karzand (2020); this paper quantifies how noise in the hidden model impacts the tasks of structure recovery and marginal distribution estimation by proving upper and lower bounds on the sample complexity. Our results generalize state-of-the-art bounds reported in prior work, and they exactly recover the noiseless case ($q=0$). In fact, for any tree with $p$ vertices and probability of incorrect recovery $\delta>0$, the sufficient number of samples remains logarithmic as in the noiseless case, i.e., $\mathcal{O}(\log(p/\delta))$, while the dependence on $q$ is $\mathcal{O}\big( 1/(1-2q)^{4} \big)$, for both aforementioned tasks. We also present a new equivalent of Isserlis' Theorem for sign-valued tree-structured distributions, yielding a new low-complexity algorithm for higher-order moment estimation.

We study a distributed sampling problem where a set of processors want to output (approximately) independent and identically distributed samples from a given joint distribution with the help of a common message from a coordinator. Each processor has access to a subset of sources from a set of independent sources of “shared” randomness. We consider two cases - in the “omniscient coordinator setting”, the coordinator has access to all these sources of shared randomness, while in the “oblivious coordinator setting,” it has access to none. In addition, all processors and the coordinator may privately randomize. In the omniscient coordinator setting, when the subsets at the processors are disjoint (individually shared randomness model), we characterize the rate of communication required from the coordinator to the processors over a multicast link. For the two-processor case, the optimal rate matches a special case of relaxed Wyner's common information proposed by Gastpar and Sula (2019), thereby providing an operational meaning to the latter. We also give an upper bound on the communication rate for the “randomness-on-the-forehead” model where each processor observes all but one source of randomness and present an achievable strategy for the general case where the processors have access to arbitrary subsets of sources of randomness. Also, we consider a more general model where the processors observe components of correlated sources (with the coordinator observing all the components), where we characterize the communication rate when all the processors wish to output the same random sequence. In the oblivious coordinator setting, we completely characterize the trade-off region between the communication and shared randomness rates for the general case where the processors have access to arbitrary subsets of sources of randomness.

Myopic arbitrarily varying channels (AVCs) are point-to-point communication models in which a channel state is controlled by a malicious adversary (a jammer) who receives side-information about the transmitted codeword via a side-channel (wiretapping) and wishes to maximize the probability of error. Compared to standard "oblivious" AVCs, myopic AVCs can potentially use the side information to launch a more effective attack, lowering the capacity of the channel. In this paper, we define a novel property, myopic symmetrizability, and prove it is a sufficient condition for the capacity of any myopic AVC to be zero. We also study the sufficiently myopic setting, in which, roughly speaking, the jammer's side information reveals less information on the codeword transmitted than eventually available at the receiver. In this scenario we show that myopic symmetrizability is also a necessary condition for the capacity to equal zero, by providing a novel code construction using non-i.i.d. codebooks. A key technical lemma, interesting in its own right, is an argument showing that for any positive-rate code (whether for myopic AVCs or not) one can identify a corresponding distribution PX,X'that is a convex combination of product distributions, and such that a constant fraction of pairs of codewords have an empirical distribution approximately equaling PX,X'.

We provide high-probability sample complexity guarantees for exact structure recovery of tree-structured graphical models, when only noisy observations of the respective vertex emissions are available. We assume that the hidden variables follow either an Ising model or a Gaussian graphical model, and the observables are noise-corrupted versions of the hidden variables: We consider multiplicative $\pm 1$ binary noise for Ising models, and additive Gaussian noise for Gaussian models. Such hidden models arise naturally in a variety of applications such as physics, biology, computer science, and finance. We study the impact of measurement noise on the task of learning the underlying tree structure via the well-known \textit{Chow-Liu algorithm} and provide formal sample complexity guarantees for exact recovery. In particular, for a tree with $p$ vertices and probability of failure $\delta>0$, we show that the number of necessary samples for exact structure recovery is of the order of $\mc{O}(\log(p/\delta))$ for Ising models (which remains the \textit{same as in the noiseless case}), and $\mc{O}(\mathrm{polylog}{(p/\delta)})$ for Gaussian models.

We propose a distributed differentially-private canonical correlation analysis (CCA) algorithm to use on multi-view data. CCA finds a subspace for each view such that projecting the views onto these subspaces simultaneously reduces the dimension and maximizes correlation. In applications involving privacy-sensitive data, such as medical imaging, distributed privacy-preserving algorithms can let data holders maintain local control of their data while participating in joint computations with other data holders. Differential privacy is a framework for quantifying the privacy risk in such settings. However, conventional distributed differentially-private algorithms introduce more noise to guarantee a given level of privacy compared to their centralized counterparts. Our differentially-private CCA employs a noise-reduction strategy to achieve the same utility level as CCA on centralized data. Experiments on synthetic and real data show the benefit of our approach over conventional methods.

The difference in capacity formulae between worst-case and average-case channel noise models has been part of information theory since the early days of the field. This paper continues a line of work studying intermediate models in which the channel behavior can depend partially on the transmitted codeword. In particular, we consider a model in which a binary erasure channel (with maximum fraction of erasures p) is controlled by an adversary who can observe the transmitted codeword through an independent and memoryless erasure channel (with erasure probability q). Upper and lower bounds on the capacity are given for two models: a noncausal model, in which the adversary can choose their erasures based on the entire (partially observed) codeword, and a causal model, in which at each time the adversary must choose its erasures based on the current and previously observed codeword bits. The achievable rate for the noncausal case is larger than the Gilbert-Varshamov bound and for some parameter ranges exceeds the linear programming (LP) bound; we also provide a non-trivial outer bound on the capacity. For the causal case, we show the capacity is 1-2p+q for p ≥ q (prior work shows the capacity to equal 1-p when p<;q). Our code construction in both scenarios are novel, requiring the encoder to carefully add “low-weight correlated noise” to its transmission.

This work addresses the problem of structured dictionary learning for computing sparse representations of tensor-structured data. It introduces a low-separation-rank dictionary learning (LSR-DL) model that better captures the structure of tensor data by generalizing the separable dictionary learning model. A dictionary with p columns that is generated from the LSR-DL model is shown to be locally identifiable from noisy observations with recovery error at most ρ given that the number of training samples scales with (# of degrees of freedom in the dictionary)×p2ρ-2.

This paper presents a new approach, called perturb-max, for high-dimensional statistical inference in graphical models that is based on applying random perturbations followed by optimization. This framework injects randomness into maximum a-posteriori (MAP) predictors by randomly perturbing the potential function for the input. A classic result from extreme value statistics asserts that perturb-max operations generate unbiased samples from the Gibbs distribution using high-dimensional perturbations. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. However, when the perturbations are of low dimension, sampling the perturb-max prediction is as efficient as MAP optimization. This paper shows that the expected value of perturb-max inference with low dimensional perturbations can be used sequentially to generate unbiased samples from the Gibbs distribution. Furthermore the expected value of the maximal perturbations is a natural bound on the entropy of such perturb-max models. A measure concentration result for perturb-max values shows that the deviation of their sampled average from its expectation decays exponentially in the number of samples, allowing effective approximation of the expectation.

Inductive matrix completion (IMC) is a model for incorporating side information in form of “features” of the row and column entities of an unknown matrix in the matrix completion problem. As side information, features can substantially reduce the number of observed entries required for reconstructing an unknown matrix from its given entries. The IMC problem can be formulated as a low-rank matrix recovery problem where the observed entries are seen as measurements of a smaller matrix that models the interaction between the column and row features. We take advantage of this property to study the optimization landscape of the factorized IMC problem. In particular, we show that the critical points of the objective function of this problem are either global minima that correspond to the true solution or are “escapable” saddle points. This result implies that any minimization algorithm with guaranteed convergence to a local minimum can be used for solving the factorized IMC problem.

Tensor decompositions have applications in many areas including signal processing, machine learning, computer vision and neuroscience. In this paper, we propose two new differentially private algorithms for orthogonal decomposition of symmetric tensors from private or sensitive data; these arise in applications such as latent variable models. Differential privacy is a formal privacy framework that guarantees protections against adversarial inference. We investigate the performance of these algorithms with varying privacy and database parameters and compare against another recently proposed privacy-preserving algorithm. Our experiments show that the proposed algorithms provide very good utility even while preserving strict privacy guarantees.

Differential privacy is a cryptographically-motivated formal privacy definition that is robust against strong adversaries. The principal component analysis (PCA) algorithm is frequently used in signal processing, machine learning, and statistics pipelines. In many scenarios, private or sensitive data is distributed across different sites: in this paper we propose a differentially private distributed PCA scheme to enable collaborative dimensionality reduction. We investigate the performance of the proposed algorithm on synthetic and real datasets and show empirically that our algorithm can reach the same level of utility as the non-private PCA for some parameter choices, which indicates that it is possible to have meaningful utility while preserving privacy.

Motivated by privacy issues in the Internet of Things (IoT), we generalize a previously proposed privacy-preserving packet obfuscation scheme to guarantee differential privacy. We propose a locally differentially private packet obfuscation mechanism as a defense against packet-size side-channel attacks in IoT networks. We formulate the problem as an optimization over a conditional probability distribution (channel) between the original and obfuscated packet sizes and show that the optimal set of obfuscated packet sizes is a strict subset of the set of original packet sizes. We study the optimal mechanisms for minimizing the (average or min-max) bandwidth overhead subject to a privacy constraint by solving the corresponding (linear or convex) program. We demonstrate our methods on synthetic and real data to illustrate privacy-bandwidth tradeoffs in different settings. Systems with many bandwidth-intensive devices can easily mask low-bandwidth devices. For data collected from actual smart home IoT devices, we show how the packet size distributions become increasingly indistinguishable as the level of privacy protection increases. The proposed mechanism highlights the possibility for bandwidth-constrained users to optimally tune their privacy preferences and trade off privacy with bandwidth.

Two processors output correlated sequences using the help of a coordinator with whom they individually share independent randomness. For the case of unlimited shared randomness, we characterize the rate of communication required from the coordinator to the processors over a broadcast link. We also give an achievable trade-off between the communication and shared randomness rates.

We consider the problem of communication over a channel with a causal jamming adversary subject to quadratic constraints. A sender Alice wishes to communicate a message to a receiver Bob by transmitting a real-valued length-n codeword x=(x1, ..., xn) through a communication channel. Alice and Bob do not share common randomness. Knowing Alice's encoding strategy, a jammer James chooses a real-valued length- n adversarial noise sequence s=(s1, ..., sn) in a causal manner: each st (1 ≤ t ≤ n) can only depend on (x1, ..., xt). Bob receives y, the sum (over \mathbbR) of Alice's transmission x and James' jamming vector s, and is required to reliably estimate Alice's message from this sum. In addition, Alice and James's transmission powers are restricted by quadratic constraints P > 0 and N > 0 such that Σt=1nxt2≤ nP and Σt=1nst2≤ nN. In this work, we characterize the channel capacity for such a channel as the limit superior of the optimal values Cn([P/N]) of a series of optimizations. Upper and lower bounds on Cn([P/N]) are provided both analytically and numerically. Interestingly, unlike many communication problems, in this causal setting Alice's optimal codebook may not have a uniform power allocation - for certain SNR a codebook with a two-level uniform power allocation results in a strictly higher rate than a codebook with a uniform power allocation would.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most O(log(n)) bits in one sub-regime, and at most O(n) bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques include a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest.

A privacy-utility tradeoff is developed for an arbitrary set of finite-alphabet source distributions. Privacy is quantified using differential privacy (DP), and utility is quantified using expected Hamming distortion maximized over the set of distributions. The family of source distribution sets (source sets) is categorized into three classes, based on different levels of prior knowledge they capture. For source sets whose convex hull includes the uniform distribution, symmetric DP mechanisms are optimal. For source sets whose probability values have a fixed monotonic ordering, asymmetric DP mechanisms are optimal. For all other source sets, general upper and lower bounds on the optimal privacy leakage are developed and necessary and sufficient conditions for tightness are established. Differentially private leakage is an upper bound on mutual information leakage: the two criteria are compared analytically and numerically to illustrate the effect of adopting a stronger privacy criterion.

This paper provides fundamental limits on the sample complexity of estimating dictionaries for tensor data. The specific focus of this work is on Kth-order tensor data and the case where the underlying dictionary can be expressed in terms of K smaller dictionaries. It is assumed the data are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. This work first provides a general lower bound on the minimax risk of dictionary learning for such tensor data and then adapts the proof techniques for specialized results in the case of sparse and sparse-Gaussian linear combinations. The results suggest the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data: for unstructured data it scales linearly with the product of the dictionary dimensions, whereas for tensor-structured data the bound scales linearly with the sum of the product of the dimensions of the (smaller) component dictionaries. A partial converse is provided for the case of 2nd-order tensor data to show that the bounds in this paper can be tight. This involves developing an algorithm for learning highly-structured dictionaries from noisy tensor data. Finally, numerical experiments highlight the advantages associated with explicitly accounting for tensor data structure during dictionary learning.

Sparse tensors appear in many large-scale applications with multidimensional and sparse data. While multidimensional sparse data often need to be processed on manycore processors, attempts to develop highly-optimized GPU-based implementations of sparse tensor operations are rare. The irregular computation patterns and sparsity structures as well as the large memory footprints of sparse tensor operations make such implementations challenging. We leverage the fact that sparse tensor operations share similar computation patterns to propose a unified tensor representation called F-COO. Combined with GPU-specific optimizations, F-COO provides highly-optimized implementations of sparse tensor computations on GPUs. The performance of the proposed unified approach is demonstrated for tensor-based kernels such as the Sparse Matricized Tensor-Times-Khatri-Rao Product (SpMTTKRP) and the Sparse Tensor-Times-Matrix Multiply (SpTTM) and is used in tensor decomposition algorithms. Compared to state-of-the-art work we improve the performance of SpTTM and SpMTTKRP up to 3.7 and 30.6 times respectively on NVIDIA Titan-X GPUs. We implement a CANDECOMP/PARAFAC (CP) decomposition and achieve up to 14.9 times speedup using the unified method over state-of-the-art libraries on NVIDIA Titan-X GPUs.

This paper provides bounds on the sample complexity of estimating Kronecker-structured dictionaries for Kth-order tensor data. The training samples are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. The lower bound follows from a lower bound on the minimax risk for general coefficient distributions and can be further specialized to sparse-Gaussian coefficients. This bound scales linearly with the sum of the product of the dimensions of the (smaller) coordinate dictionaries for tensor data. An explicit dictionary estimation algorithm for 2nd-order tensor data is also provided whose sample complexity matches the lower bound in the scaling sense. Numerical experiments highlight the advantages associated with explicitly accounting for tensor structure of data during dictionary learning.

Independent vector analysis (IVA) is an approach for joint blind source separation of several data sets that learns simultaneous unmixing transforms for each set. It assumes corresponding sources from different data sets to be statistically dependent. One of the main advantages is IVA's ability to retain subject-specific differences while simplifying comparison across subjects as the resulting components have the same order. The latter is an instrumental property for enabling collaboration between remote sites without sharing their data, which may be required because of ethical, privacy or efficiency concerns. This paper proposes a new decentralized algorithm for IVA that exploits the structure of the objective function. A centralized aggregator coordinates IVA algorithms at multiple sites using message passing, parallelizing the computation and limiting the amount of communication. Thus, the algorithm enables a plausibly private collaboration across multiple sites. Besides enabling analysis of decentralized data, our approach improves the running time of IVA when used locally.

Differential privacy is a strong, cryptographically-motivated definition of privacy that has recently received a significant amount of research attention for its robustness to known attacks. The principal component analysis (PCA) algorithm is frequently used in signal processing, machine learning and statistics pipelines. In this paper, we propose a new algorithm for differentially-private computation of PCA and compare the performance empirically with some recent state-of-the-art algorithms on different data sets. We intend to investigate the performance of these algorithms with varying privacy parameters and database parameters. We show that our proposed algorithm, despite guaranteeing stricter privacy, provides very good utility for different data sets.

In collaborative medical research settings, a moderate number of groups (sites) may wish to merge local analyses of private subject data. Differential privacy offers one way to guarantee privacy for these local analyses. We describe a novel ensemble learning method that we call the "feature method" for aggregating binary classifiers or regressors trained on local data. Our method leverages a public data set available at the aggregator to optimize a linear combination of local predictors. We provide some analysis of the method and show how it is effective when the local sites are required to learn classifiers that are differentially private. We prove that this method has near-optimal performance when local data sets are large enough under certain requirements on the parameters. Experimentally, we give a comparison of the feature method and the standard approach of averaging the local classifiers.

In this paper we study how individual sensors can compress their observations in a privacy-preserving manner. We propose a randomized requantization scheme that guarantees local differential privacy, a strong model for privacy in which individual data holders must mask their information before sending it to an untrusted third party. For our approach, the problem becomes an optimization over discrete mem-oryless channels between the sensor observations and their compressed version. We show that for a fixed compression ratio, finding privacy-optimal channel subject to a distortion constraint is a quasiconvex optimization problem that can be solved by the bisection method. Our results indicate interesting tradeoffs between the privacy risk, compression ratio, and utility, or distortion. For example, in the low distortion regime, we can halve the bit rate at little cost in distortion while maintaining the same privacy level. We illustrate our approach for a simple example of privatizing and recompressing lowpass signals and show that it yields better tradeoffs than existing approaches based on noise addition. Our approach may be useful in several privacy-sensitive monitoring applications envisioned for the Internet of Things (IoT).

We consider the problem of communicating a message m in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to pn bits, out of n transmitted bits X = (x1, ..., xn). The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit xidepends on his observations (x1, ..., xi) was recently characterized [1], [2] to be 1 - 2p. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit xidepends only on (x1, ..., xi-1) (and is independent of the “current bit” xi) then the capacity increases to 1 - p when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword X is a deterministic function of the message m) then no rate asymptotically larger than 1 - 2p is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of 1- p against a one-bit-delayed Calvin.

We examine a tradeoff between privacy and utility in terms of local differential privacy (L-DP) and Hamming distortion for certain classes of finite-alphabet sources under Hamming distortion. We define two classes: permutation-invariant, and ordered statistics (whose probability mass functions are monotonic). We obtain the optimal L-DP mechanism for permutation-invariant sources and derive upper and lower bounds on the achievable local differential privacy for ordered statistics for a range of target distortion values.

Dictionary learning is the problem of estimating the collection of atomic elements that provide a sparse representation of measured/collected signals or data. This paper finds fundamental limits on the sample complexity of estimating dictionaries for tensor data by proving a lower bound on the minimax risk. This lower bound depends on the dimensions of the tensor and parameters of the generative model. The focus of this paper is on second-order tensor data, with the underlying dictionaries constructed by taking the Kronecker product of two smaller dictionaries and the observed data generated by sparse linear combinations of dictionary atoms observed through white Gaussian noise. In this regard, the paper provides a general lower bound on the minimax risk and also adapts the proof techniques for equivalent results using sparse and Gaussian coefficient models. The reported results suggest that the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data.

We consider learning from data of variable quality that may be obtained from different heterogeneous sources. Addressing learning from heterogeneous data in its full generality is a challenging problem. In this paper, we adopt instead a model in which data is observed through heterogeneous noise, where the noise level reflects the quality of the data source. We study how to use stochastic gradient algorithms to learn in this model. Our study is motivated by two concrete examples where this problem arises naturally: learning with local differential privacy based on data from multiple sources with different privacy requirements, and learning from data with labels of variable quality. The main contribution of this paper is to identify how heterogeneous noise impacts performance. We show that given two datasets with heterogeneous noise, the order in which to use them in standard SGD depends on the learning rate. We propose a method for changing the learning rate as a function of the heterogeneity, and prove new regret bounds for our method in two cases of interest. Finally, we evaluate the performance of our algorithm on real data.

The maximum a-posteriori (MAP) perturbation framework has emerged as a useful approach for inference and learning in high dimensional complex models. By maximizing a randomly perturbed potential function, MAP perturbations generate unbiased samples from the Gibbs distribution. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This paper develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values. Applying the general result to MAP perturbations can yield a more efficient algorithm to approximate sampling from the Gibbs distribution. The measure concentration result is of general interest and may be applicable to other areas involving Monte Carlo estimation of expectations.

This paper considers a problem of distributed hypothesis testing and social learning. Individual nodes in a network receive noisy (private) observations whose distribution is parameterized by a discrete parameter (hypotheses). The distributions are known locally at the nodes, but the true parameter/hypothesis is not known. An update rule is analyzed in which agents first perform a Bayesian update of their belief (distribution estimate) of the parameter based on their local observation, communicate these updates to their neighbors, and then perform a “non-Bayesian” linear consensus using the log-beliefs of their neighbors. The main result of this paper is that under mild assumptions, the belief of any agent in any incorrect parameter converges to zero exponentially fast, and the exponential rate of learning is a characterized by the network structure and the divergences between the observations' distributions.

We study a distributed sampling scenario in which two agents observing components of a correlated source must each generate components of a second correlated source. The agents are aided by an “omniscient” third terminal which observes the two input sources and transmits rate-limited messages to assist the terminals in generating the required correlation in their outputs. We identify two sub-cases of this problem based on how the generated sources must depend on the input sources.

We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. We study binary classification in an extreme case, where the algorithm only pays for negative labels. Our motivation are applications such as fraud detection, in which investigating an honest transaction should be avoided if possible. We term the setting auditing, and consider the auditing complexity of an algorithm: The number of negative points it labels to learn a hypothesis with low relative error. We design auditing algorithms for thresholds on the line and axis-aligned rectangles, and show that with these algorithms, the auditing complexity can be significantly lower than the active label complexity. We discuss a general approach for auditing for a general hypothesis class, and describe several interesting directions for future work.

In this paper, we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codewordx=(x1, ...,xn) bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bitsxione at a time and can change up to ap-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bitxi, the jammer's decision on whether to corrupt it or not must depend only onxjforj≤i. This is in contrast to the “classical” adversarial jamming situations in which the jammer has no knowledge ofx, or knowsxcompletely. In this study, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, ..., xn) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits xione at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit xithe jammer's decision on whether to corrupt it or not must depend only on xjfor j ≤ i. This is in contrast to the “classical” adversarial jammer which may base its decisions on its complete knowledge of x. Binary channels with causal adversarial jammers have seen recent studies in which both lower bounds and upper bounds on their capacity is derived. In this work, we present improved upper bounds on the capacity which hold for both deterministic and stochastic encoding schemes.

Principal components analysis (PCA) is a standard tool for identifying good low-dimensional approximations to data sets in high dimension. Many current data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We demonstrate that on real data, there this a large performance gap between the existing methods and our method. We show that the sample complexity for the two procedures differs in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling.

OBJECTIVE: Today's clinical research institutions provide tools for researchers to query their data warehouses for counts of patients. To protect patient privacy, counts are perturbed before reporting; this compromises their utility for increased privacy. The goal of this study is to extend current query answer systems to guarantee a quantifiable level of privacy and allow users to tailor perturbations to maximize the usefulness according to their needs. METHODS: A perturbation mechanism was designed in which users are given options with respect to scale and direction of the perturbation. The mechanism translates the true count, user preferences, and a privacy level within administrator-specified bounds into a probability distribution from which the perturbed count is drawn. RESULTS: Users can significantly impact the scale and direction of the count perturbation and can receive more accurate final cohort estimates. Strong and semantically meaningful differential privacy is guaranteed, providing for a unified privacy accounting system that can support role-based trust levels. This study provides an open source web-enabled tool to investigate visually and numerically the interaction between system parameters, including required privacy level and user preference settings. CONCLUSIONS: Quantifying privacy allows system administrators to provide users with a privacy budget and to monitor its expenditure, enabling users to control the inevitable loss of utility. While current measures of privacy are conservative, this system can take advantage of future advances in privacy measurement. The system provides new ways of trading off privacy and utility that are not provided in current study design systems.

The influence of node mobility on the convergence time of averaging gossip algorithms in networks is studied. It is shown that a small number of fully mobile nodes can yield a significant decrease in convergence time. A method is developed for deriving lower bounds on the convergence time by merging nodes according to their mobility pattern. This method is used to show that if the agents have 1-D mobility in the same direction, the convergence time is improved by at most a constant. Upper bounds on the convergence time are obtained using techniques from the theory of Markov chains and show that simple models of mobility can dramatically accelerate gossip as long as the mobility paths overlap significantly. Simulations verify that different mobility patterns can have significantly different effects on the convergence of distributed algorithms.

List-decoding for arbitrarily varying channels (AVCs) under state constraints is investigated. It is shown that rates within ϵ of the randomized coding capacity of AVCs with input-dependent state can be achieved under maximal error with list-decoding using lists of size O(1/ϵ). Under the average error criterion, an achievable rate and converse bound are given for lists of size L . These bounds are based on two different notions of symmetrizability and do not coincide in general. An example is given which shows that for list size L , the capacity may be positive but strictly smaller than the randomized coding capacity, in contrast to the situation without constraints.

In this work we consider the communication of information in the presence of a delayed adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, ..., xn) over a communication channel. The adversarial jammer can view the transmitted symbols xi one at a time, but must base its action (when changing xi) on xjfor j ≤ i - Δn, where Δ ∈ [0, 1] is a delay parameter. In this work, we study codes for a class of delayed adversaries, and for any delay Δ > 0 present a single letter characterization of the achievable communication rate in the presence of such adversaries.

A variant on the arbitrarily varying channel (AVC) is proposed in which the jammer is allowed to base its actions on a noisy version of the transmitted codeword. It is shown via a random coding argument that the capacity is the minimum over all discrete memoryless channels (DMCs) that can be induced by memoryless strategies of the adversary. This generalizes two existing models in the AVC literature: the standard AVC in which the jammer does not know the channel input, and the AVC in which the jammer knows the channel input exactly.

Shannon's discovery of digital communication has shaped the architecture of virtually all communication systems in use today. The digital communication paradigm is built around the notion of bits and uses careful coding to deliver bits reliably end-to-end. It has been shown that this architectural principle can lead to a very significant performance penalty in wireless sensor networks. For a limited class of network scenarios, it was shown that optimal architectures are analog in nature, simple and scalable. In this paper, we show that more generally, simple analog architectures crucially depend on feedback to the sensors. Interesting questions then concern the amount of feedback needed and the resulting trade-off with performance. This paper provides rules-of-thumb for the selection of the number of feedback bits.

The utility of limited feedback for coding over an individual sequence of discrete memoryless channels is investigated. This study complements recent results showing how limited or noisy feedback can boost the reliability of communication. A strategy with fixed input distributionPis given that asymptotically achieves rates arbitrarily close to the mutual information induced byPand the state-averaged channel. When the capacity-achieving input distribution is the same over all channel states, this achieves rates at least as large as the capacity of the state-averaged channel, sometimes called the empirical capacity.

The arbitrarily varying channel (AVC) is a channel model whose state is selected maliciously by an adversary. Fixed-blocklength coding assumes a worst-case bound on the adversary's capabilities, which leads to pessimistic results. This paper defines a variable-length perspective on this problem, for which achievable rates are shown that depend on the realized actions of the adversary. Specifically, rateless codes are constructed which require a limited amount of common randomness. These codes are constructed for two kinds of AVC models. In the first the channel state cannot depend on the channel input, and in the second it can. As a by-product, the randomized coding capacity of the AVC with state depending on the transmitted codeword is found and shown to be achievable with a small amount of common randomness. The results for this model are proved using a randomized strategy based on list decoding.

We analyze how node mobility can influence the convergence time of averaging gossip algorithms on networks. Our main result is that even a small number of fully mobile nodes can yield a significant decrease in convergence time. We develop a method for deriving lower bounds on the convergence time by merging nodes according to their mobility pattern. We use this method to show that if the agents have one-dimensional mobility in the same direction the convergence time is improved by at most a constant. We also obtain upper bounds on the convergence time using techniques from the theory of Markov chains and show that simple models of mobility can dramatically accelerate gossip as long as the mobility paths significantly overlap. We use simulations to show that our bounds are still valid for more general mobility models that seem analytically intractable, and further illustrate that different mobility patterns can have significantly different effects on the convergence of distributed algorithms.

Most information-theoretic analyses of communication systems with feedback assume perfect output feedback. For multiaccess channels, this feedback can enable cooperation between users. However, as shown by a simple example, the rate required by the feedback link may exceed the capacity gains in the forward link. It is therefore of interest to look at systems where the feedback is rate-limited. For the compound multiaccess channel zero-rate feedback can tune the communication system to the realized channel, but for discrete memoryless channel the capacity region under zero-rate feedback is the same as that without feedback.

A deterministic dirty-paper coding strategy for communication over an arbitrarily varying channel with an interference signal known to the transmitter is investigated. The presence of a known interference signal at the transmitter is shown to provide some protection against jamming interference. For some values of the parameters the scheme is capacity- achieving. Applications to watermarking and spectrum-sharing channels are described.

Recently, Shayevitz and Feeler introduced an individual sequence formulation of channel coding under model uncertainty and an elegant coding strategy that adapts Horstein's scheme to this setting to achieve the empirical capacity of the channel. Their scheme requires both full-rate output feedback and common randomness. We present a strategy in the style of Hybrid ARQ that requires no output feedback by using common randomness and zero-rate active feedback. This strategy still asymptotically achieves the empirical capacity.

Coding over channels whose state can depend non- causally on the entire transmitted codeword and message are studied. The channel model is a variation on the arbitrarily varying channel (AVC) with state constraints. The randomized coding capacity of this channel is shown to be equal to the randomized coding capacity Crin the case where the jammer does not know the codeword, and common randomness of O (log n) bits is sufficient to achieve this capacity.

Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy 1/nausing O(n1.5√log n) radio transmissions, which reduces the energy consumption by a √nover log n factor over standard gossip algorithms.

The random coding capacity of the Gaussian arbitrarily varying channel (GAVC) under a maximal probability of error criterion is equal to that of an additive white Gaussian noise (AWGN) channel with the interference power as additional noise. The deterministic coding capacity under an average probability of error criterion is zero if the transmitter power does not exceed the interference power. We show that the random coding capacity for average probability error is the same as that for maximal probability of error and that the randomization need only be over a sub-exponential number of codebooks. The achievable error exponent is related to the amount of randomization. An application of these results to the degraded broadcast channel is discussed

In some remote sensing applications, the functional relationship between the source being observed and the sensor readings may not be known. Because of communication constraints, this uncertainty may result in poor end-to-end distortion. If the sensors have some knowledge of their joint statistics, they may be able to communicate collaboratively to combat the channel noise. A model is proposed for capturing some of the uncertainty in the observation process, called a fading observation model. An example with fading observations is analysed. For M sensors with no fading there exists a scheme for which the achievable distortion scales with M as M/sup -1/, but with fading the distortion does not scale with M. In this paper, a one-bit feedback scheme is presented that provides enough information about the joint statistics to achieve scaling rates like M/sup -1/3/. Additional feedback improves the achievable scaling rate. For comparison, a scheme based on separate source and channel coding at best gives a distortion scaling behaviour of (log M)/sup -1/. Some extensions to multiple sources and observation models with unknown delay are discussed.