Search

The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly‐time universal: any function distribution that can be learned from samples in polytime can also be learned by a poly‐size neural net trained by SGD with polynomial parameters. In particular, this can be achieved despite polynomial noise on the gradients, implying a separation result between SGD‐based deep learning and statistical query algorithms, as the latter are not comparably universal due to cases like parities. This also shows that deep learning does not suffer from the limitations of shallow networks. (2) The paper further gives a lower‐bound on the generalization error of descent algorithms, which relies on two quantities: the cross‐predictability, an average‐case quantity related to the statistical dimension, and the null‐flow, a quantity specific to descent algorithms. The lower‐bound implies in particular that for functions of low enough cross‐predictability, the above robust universality breaks down once the gradients are averaged over too many samples (as in perfect GD) rather than fewer (as in SGD). (3) Finally, it is shown that if larger amounts of noise are added on the initialization and on the gradients, then SGD is no longer comparably universal due again to distributions having low enough cross‐predictability. [ABSTRACT FROM AUTHOR]

This paper considers “ $\delta $ -almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a $\delta $ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon >0$ , there exists a family of $\delta $ -almost Reed–Muller codes of constant rate that correct $1/2- \varepsilon $ fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

We study the problem of community detection on Euclidean random geometric graphs where each vertex has two latent variables: a binary community label and a |$\mathbb{R}^d$| valued location label which forms the support of a Poisson point process of intensity |$\lambda $|⁠. A random graph is then drawn with edge probabilities dependent on both the community and location labels. In contrast to the stochastic block model (SBM) that has no location labels, the resulting random graph contains many more short loops due to the geometric embedding. We consider the recovery of the community labels, partial and exact, using the random graph and the location labels. We establish phase transitions for both sparse and logarithmic degree regimes and provide bounds on the location of the thresholds, conjectured to be tight in the case of exact recovery. We also show that the threshold of the distinguishability problem, i.e. the testing between our model and the null model without community labels exhibits no phase transition and in particular, does not match the weak recovery threshold (in contrast to the SBM). [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon’s capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix $\begin{aligned} G_{m}= \left[{\begin{smallmatrix}1 & 0 \\ 1 & 1 \\ \end{smallmatrix}}\right]^{\otimes m} \end{aligned}$ but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in $G_{m}$ ; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arıkan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this article, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in $G_{m}$ , the conditional mutual information again polarizes. Here “polarization” means that almost all the conditional mutual information becomes either very close to 0 or very close to 1. Polarization itself is a necessary condition for RM codes to achieve capacity on symmetric channels while polarization together with a strong order on the conditional mutual information gives a sufficient condition, where strong order means that rows with larger weight always correspond to larger conditional mutual information. Although we are not able to prove the strong order, we establish a partial order on the conditional mutual information, which is a subset of the strong order. While the main results of this article–polarization together with the partial order–provide some advances on the capacity-achieving conjecture of RM codes, we emphasize that our results do not allow us to prove the conjecture. [ABSTRACT FROM AUTHOR]

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations. [ABSTRACT FROM AUTHOR]

We derive generalization and excess risk bounds for neural networks using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural networks and by using the technique of chaining mutual information introduced by Asadi et al. '18. The resulting bounds are algorithm-dependent and multiscale: they exploit the multilevel structure of neural networks. This, in turn, leads to an empirical risk minimization problem with a multilevel entropic regularization. The minimization problem is resolved by introducing a multiscale extension of the celebrated Gibbs posterior distribution, proving that the derived distribution achieves the unique minimum. This leads to a new training procedure for neural networks with performance guarantees, which exploits the chain rule of relative entropy rather than the chain rule of derivatives (as in backpropagation), and which takes into account the interactions between different scales of the hypothesis sets of neural networks corresponding to different depths of the hidden layers. To obtain an efficient implementation of the latter, we further develop a multilevel Metropolis algorithm simulating the multiscale Gibbs distribution, with an experiment for a two-layer neural network on the MNIST data set. [ABSTRACT FROM AUTHOR]

This paper develops deterministic upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exploit r-nonbacktracking walks and Fortuin|Kasteleyn|Ginibre (FKG) type inequalities, and are computed by message passing algorithms. Further, we provide parameterized versions of the bounds that control the trade-off between efficiency and accuracy. Finally, the tightness of the bounds is illustrated on various network models. [ABSTRACT FROM AUTHOR]

In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal’s orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as $\omega (1/ \mathrm {SNR}^{3})$. In this paper, using a generalization of the Chapman–Robbins bound for orbits and expansions of the $\chi ^{2}$ divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as $\omega (1/ \mathrm {SNR}^{2})$. This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation–maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model. [ABSTRACT FROM AUTHOR]

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences. This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds. The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed. [ABSTRACT FROM AUTHOR]

In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborová, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten‐Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulié, Mossel et al., and Bordenave, Lelarge, and Massoulié proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi‐linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message‐passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information‐theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information‐computation gaps. © 2017 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Rényi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the RID of an i.i.d. sequence of mixture random variables polarizes to the extremal values of 0 and 1 (corresponding to discrete and continuous distributions) when transformed by a Hadamard matrix. Furthermore, we prove that the polarization pattern of the RID admits a closed form expression and follows exactly the Binary Erasure Channel (BEC) polarization pattern in the discrete setting. We discuss the applications of the RID polarization to Compressed Sensing of i.i.d. sources. In particular, we use the RID polarization to construct a family of deterministic ±1-valued sensing matrices for Compressed Sensing. We run numerical simulations to compare the performance of the resulting matrices with that of the random Gaussian and the random Hadamard matrices. The results indicate that the proposed matrices afford competitive performances, while being explicitly constructed. [ABSTRACT FROM PUBLISHER]

In this note, the following basic question is explored: in a cyclic group, how are the Shannon entropies of the sum and difference of i.i.d. random variables related to each other? For the integer group, we show that they can differ by any real number additively, but not too much multiplicatively; on the other hand, for Z/3Z, the entropy of the difference is always at least as large as that of the sum. These results are closely related to the study of more-sums-than-differences (i.e., MSTD) sets in additive combinatorics. We also investigate polar codes for q-ary input channels using non-canonical kernels to construct the generator matrix and present applications of our results to constructing polar codes with significantly improved error probability compared to the canonical construction. [ABSTRACT FROM AUTHOR]

We develop an information-theoretic viewof the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph G from such a model is generated by first assigning vertex labels at random from a finite alphabet, and then connecting vertices with edge probabilities depending on the labels of the endpoints. In the case of the symmetric two-group model, we establish an explicit ‘single-letter’ characterization of the per-vertex mutual information between the vertex labels and the graph, when the mean vertex degree diverges. The explicit expression of the mutual information is intimately related to estimation-theoretic quantities, and —in particular—reveals a phase transition at the critical point for community detection. Below the critical point the per-vertex mutual information is asymptotically the same as if edges were independent. Correspondingly, no algorithm can estimate the partition better than random guessing. Conversely, above the threshold, the per-vertex mutual information is strictly smaller than the independent-edges upper bound. In this regime, there exists a procedure that estimates the vertex labels better than random guessing. [ABSTRACT FROM AUTHOR]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [ABSTRACT FROM AUTHOR]

The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability $p$ within clusters and q$ across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of |p-q|$ to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if \alpha =pn/\log (n)$ and \beta =qn/\log (n)$ are constant (with and is impossible if ({\alpha +\beta }/{2}) - \sqrt {\alpha \beta }<1 . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. [ABSTRACT FROM PUBLISHER]

This paper studies the parameters for which binary Reed–Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate $GF(2)$ polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about $E(m,r)$ , the matrix whose rows are the truth tables of all the monomials of degree $\leq r$ in $m$ variables. What is the most (resp. least) number of random columns in $E(m,r)$ that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees $r$ , which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code $C$ of sufficiently high rate, we construct a new code $C'$ obtained by tensorizing $C$ , such that for every subset $S$ of coordinates, if $C$ can recover from erasures in $S$ , then $C'$ can recover from errors in $S$ . Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials. [ABSTRACT FROM PUBLISHER]

The polarization phenomenon for a single source is extended to a framework with multiple correlated sources. It is shown in addition to extracting the randomness of the source, the polar transforms take the original arbitrary dependencies to extremal dependencies. Polar coding schemes for the Slepian–Wolf (SW) coding problem and for secret key generations are then proposed based on this phenomenon. In particular, secret keys achieving the secrecy capacity and compression schemes achieving the SW capacity region are obtained with a complexity of $O(n \log (n))$ . [ABSTRACT FROM AUTHOR]

Polar codes are introduced for discrete memoryless broadcast channels. For m -user deterministic broadcast channels, polarization is applied to map uniformly random message bits from m -independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: 1) Cover’s superposition codes and 2) Marton’s codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multiuser setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is O(n \log n) , where n of the average block error probability where 0 < \beta < {1}/{2} . Reproducible experiments for finite block lengths n = 512, 1024, 2048$ corroborate the theory. [ABSTRACT FROM AUTHOR]

The entropy power inequality (EPI) yields lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X+X^\prime)-H(X)\geq1\over2-o(1) when X , X^{\prime} are independent identically distributed (i.i.d.) with high entropy. This paper provides the inequality H(X+X^{\prime})-H(X)\geq g(H(X)) , where X , X^{\prime} are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on \BBR+ satisfying g(0)=0 . Extensions to nonidentically distributed random variables and to conditional entropies are also obtained. [ABSTRACT FROM AUTHOR]

It is conjectured that the covariance matrices minimizing the outage probability under a power constraint for multiple-input multiple-output channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the multiple-input single-output (MISO) setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting. [ABSTRACT FROM PUBLISHER]

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into successive uses of extremal MACs. This transformation has a number of desirable properties: 1) the “uniform sum-rate” of the original MAC is preserved, 2) the extremal MACs have uniform rate regions that are not only polymatroids but matroids, and thus, 3) their uniform sum-rate can be reached by each user transmitting either uncoded or fixed bits; in this sense, they are easy to communicate over. A polar code can then be constructed with an encoding and decoding complexity of O(n \log n) (where n is the block length), a block error probability of o(\exp (- n^1/2 - \varepsilon)), and capable of achieving the uniform sum-rate of any binary input MAC with arbitrary many users. Applications of this polar code construction to channels with a finite field input alphabet and to the additive white Gaussian noise channel are also discussed. [ABSTRACT FROM PUBLISHER]

This paper investigates network information theory problems where the external noise is Gaussian distributed. In particular, the Gaussian broadcast channel with coherent fading and the Gaussian interference channel are considered. It is shown that in these problems, non-Gaussian code ensembles can achieve higher rates than the Gaussian ones. It is also shown that the strong Shamai–Laroia conjecture on the Gaussian ISI channel does not hold. In order to analyze non-Gaussian code ensembles over Gaussian networks, a geometrical tool using the Hermite polynomials is proposed. This tool provides a coordinate system to analyze a class of non-Gaussian input distributions that are invariant over Gaussian networks. [ABSTRACT FROM AUTHOR]

Over discrete memoryless channels (DMC), linear decoders (maximizing additive metrics) afford several nice properties. In particular, if suitable encoders are employed, the use of decoding algorithms with manageable complexities is permitted. For a compound DMC, decoders that perform well without the channel's knowledge are required in order to achieve capacity. Several such decoders have been studied in the literature, however, there is no such known decoder which is linear. Hence, the problem of finding linear decoders achieving capacity for compound DMC is addressed, and it is shown that under minor concessions, such decoders exist and can be constructed. A geometric method based on the very noisy transformation is developed and used to solve this problem. [ABSTRACT FROM PUBLISHER]

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw connections between such entropic matroids and secret-sharing matroids and show that entropic matroids are linear matroids when p = 2 , 3 but not when p = 9 . Our results leave open the possibility for p-entropic matroids to be linear whenever p is prime, with particular cases proved here. Applications of entropic matroids to coding theory and cryptography are also discussed. [ABSTRACT FROM AUTHOR]

Practical implementations of secret-key generation are often based on sequential strategies, which handle reliability and secrecy in two successive steps, called reconciliation and privacy amplification. In this paper, we propose an alternative approach based on polar codes that jointly deals with reliability and secrecy. Specifically, we propose secret-key capacity-achieving polar coding schemes for the following models: (i) the degraded binary memoryless source (DBMS) model with rate-unlimited public communication, (ii) the DBMS model with one-way rate-limited public communication, (iii) the 1-to-m broadcast model and (iv) the Markov tree model with uniform marginals. For models (i) and (ii) our coding schemes remain valid for non-degraded sources, although they may not achieve the secret-key capacity. For models (i), (ii) and (iii), our schemes rely on pre-shared secret seed of negligible rate; however, we provide special cases of these models for which no seed is required. Finally, we show an application of our results to secrecy and privacy for biometric systems. We thus provide the first examples of low-complexity secret-key capacity-achieving schemes that are able to handle vector quantization for model (ii), or multiterminal communication for models (iii) and (iv). [ABSTRACT FROM PUBLISHER]