Communication, Control and Signal Processing Seminar
Abstracts of talks
Fall 2018
08/29 Rajesh Sundaresan (Indian Institute of Science), Learning to detect an oddball target
ABSTRACT: What policy should you employ if you were to locate an oddball target among many (two or more) distracters? You do not know the statistics of the observations that a 'view' of the oddball produces. Nor do you know the statistics of the observations arising from a view of a distractor. The objective is to minimize the search time, subject to keeping the probability of false detection low. Clearly, the common statistics of the distracter-generated observations should be compared, recognized as similar, and further recognized as different from those generated by the oddball target. But where should you look next, when should you stop, and when you stop, what should you decide as the oddball location?
When the observations are points of a Poisson process (as in firings of neurons), and when the probability of false detection is driven down to zero, we will discuss the best growth rate of the expected search time. We will also identify an asymptotically optimal search policy that achieves the best growth rate. Finally, we will apply our results to a particular visual search experiment studied recently by neuroscientists and will highlight how prior information affects search performance.
09/06 Karim Banawan (UMD), The Capacity of Private Information Retrieval from Byzantine and Colluding Databases
ABSTRACT: We consider the problem of single-round private information retrieval (PIR) from $N$ replicated databases. We consider the case when $B$ databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of $M$ messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the $T$-privacy constraint in this paper, where any $T$ databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of \emph{correct symbols} that can be retrieved privately (under the $T$-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be $C=\frac{N-2B}{N}\cdot\frac{1-\frac{T}{N-2B}}{1-(\frac{T}{N-2B})^M}$, if $2B+T < N$. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing $2B$ databases from the system, with a penalty factor of $\frac{N-2B}{N}$, which signifies that even though the number of databases needed for PIR is effectively $N-2B$, the user still needs to access the entire $N$ databases. The result shows that for the unsynchronized PIR problem if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the \emph{errors} introduced by the Byzantine databases as opposed to \emph{erasures} in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.
09/20 Aneesh Raghavan (UMD), Cooperative Binary Hypothesis Testing by Two Observers
ABSTRACT: We consider the binary hypothesis testing problem with two observers. There are two possible states of nature (or hypotheses). Observations are collected by two observers. The observations are statistically related to the true state of nature. Given the observations, the objective of the observers is to find the true state of nature. We present two different approaches to address the problem. In the first (centralized) approach, the observations collected by both the observers are sent to a central coordinator where hypothesis testing is performed. In the second approach, each observer performs hypothesis testing based on locally collected observations. Then they exchange binary information to arrive at a consensus. First, we discuss the probability space construction for the two approaches. Then we formulate and solve the hypothesis testing problems. We prove the convergence of the consensus algorithm in the second approach. We compare the rate of decay of the probability of error of the two approaches and prove that if the observations collected by the observers are independent conditioned on the hypothesis, the rate of decay achieved in the second approach is greater than or equal to the rate of decay in the first approach.
This is joint work with Prof. John Baras.
09/27 Min Ye (Princeton University), Practical coding schemes for distributed learning, storage and communication
ABSTRACT: Communication constraints form significant obstacles for improving the performance of distributed learning and storage systems. In recent years system design in both these applications has been shown to benefit from data encoding. We address coding theory problems that arise in distributed learning and storage, and present several efficient coding schemes that attain the minimum possible communication cost. The coding schemes have been implemented and evaluated on Amazon EC2 clusters, and they were shown to improve upon the state-of-the-art solutions.
In the second part of the talk, I will address a classical coding-theoretic problem that concerns Reed-Muller codes. Several years ago this class of codes was shown to attain the capacity of the Binary Erasure Channel. It has been conjectured that this result holds more broadly, and Reed-Muller codes attain the capacity of any binary-input memoryless symmetric channel. We present partial results toward this conjecture relying on the ideas from polar codes. We also give a new efficient decoding algorithm for low-rate RM codes that outperforms all known decoding algorithms for RM codes as well as polar codes with the same parameters.
10/04 Itzhak Tamo (Tel-Aviv University), From Index coding to hat guessing games
ABSTRACT: There are several well-known hat guessing puzzles in recreational mathematics. In this talk I will focus on a relatively new variation of these problems and show its connection to the basic problem of Index coding. Then I will show that the puzzle exhibits a relatively familiar phenomena: the use of nonlinear guessing functions outperforms the use of linear functions. We conclude the talk with some open problems.
11/15 Varun Jog (University of Wisconsin - Madison), Information Theoretic Perspectives on Learning Algorithms
ABSTRACT: In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. We overview some recent work [Xu and Raginsky (2017)] that bounds generalization error of empirical risk minimization based on the mutual information I(S;W) between the algorithm input S and the algorithm output W. We leverage these results to derive generalization error bounds for a broad class of iterative algorithms that are characterized by bounded, noisy updates with Markovian structure, such as stochastic gradient Langevin dynamics (SGLD). We describe certain shortcomings of mutual information-based bounds and propose alternate bounds that employ the Wasserstein metric from optimal transport theory. We compare the Wasserstein metric-based bounds with the mutual information-based bounds and show that for a class of data generating distributions, the former leads to stronger bounds on the generalization error.
11/29 Ohad Elishco (UMD), Semiconstrained Systems
ABSTRACT: When transmitting information over a noisy channel, two approaches are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code, or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this talk, we analyze a middle road, which we call a semiconstrained system. In such a system we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We will address several key issues such as bounds on the capacity, encoders and approximation of capacity in high dimensions.
12/06 Ke Wu (Johns Hopkins University), Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
ABSTRACT: Synchronization strings were recently introduced by Haeupler and Shahrasbi in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm, it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added. Haeupler and Shahrasbi showed that for any parameter $\epsilon > 0$, synchronization strings of arbitrary length exist over an alphabet whose size depends only on $\epsilon$. Specifically, Haeupler and Shahrasbi obtained an alphabet size of $O(\epsilon^{-4})$, which left an open question on where the minimal size of such alphabets lies between $O(\epsilon^{-1})$ and $O(\epsilon^{-4})$. In this work, we partially bridge this gap by providing an improved lower bound of $O(\epsilon^{-3/2})$, and an improved upper bound of $O(\epsilon^{-2})$. We also provide fast explicit constructions of synchronization strings over small alphabets.
Further along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant $\epsilon < 1$. We show that one can construct $\epsilon$-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.