Large scale DNN training tasks are exceedingly compute-intensive and time-consuming, which are usually executed on highly-parallel platforms. Data and model parallelization is a common way to speed up the training progress across devices. However, they tend to achieve sub-optimal performance due to the communication overheads and unbalanced load among servers. Recent emerging pipelining solutions mitigate the above issues, incorporating the advantages of data and model parallelism. In this paper, we make a step further towards optimizing the execution of pipelining. We introduce PipePar, a pipeline-parallel DNN training method that provides optimized execution strategies of layer-stacked DNNs. PipePar considers the entire tensor partition space of pipelining and explores potential hybrid parallel configurations of each stage in the pipeline. Additionally, we notice the network heterogeneity between different GPU servers and it is inevitable to transfer tensors with different bandwidths and latency. So, taking into account both computation and communication capacity of different GPU servers, PipePar is intended to find a elastic load distribution strategy at different levels. We evaluate PipePar with a set of real-world DNNs on 4 GPU servers. Our experimental results show that PipePar is able to find an efficient strategy that are up to 2.16× faster than state-of-the-art hybrid parallelization approaches.

Let$T_{\epsilon }$be the noise operator acting on Boolean functions$f:\{0, 1\}^{n}\to \{0, 1\}$, where$\epsilon \in [{0, 1/2}]$is the noise parameter. Given$\alpha >1$and fixed mean$\mathbb {E} f$, which Boolean function$f$has the largest$\alpha $-th moment$\mathbb {E}(T_\epsilon f)^\alpha $? This question has close connections with noise stability of Boolean functions, the problem of non-interactive correlation distillation, and Courtade-Kumar’s conjecture on the most informative Boolean function. In this paper, we characterize maximizers in some extremal settings, such as low noise ($\epsilon =\epsilon (n)$close to 0), high noise ($\epsilon =\epsilon (n)$close to 1/2), as well as when$\alpha =\alpha (n)$is large. Analogous results are also established in more general contexts, such as Boolean functions defined on discrete torus$(\mathbb {Z}/p \mathbb {Z})^{n}$and the problem of noise stability in a tree model.

Usable upper and lower deviation bounds are given for the information content of random vectors from a s-concave probability density function. Some information-theoretic interpretation, related to non-asymptotic equipartition properties, is also developed.

Summary Exorbitant resources (computing and memory) are required to train a deep neural network (DNN). Often researchers deploy an approach that uses distributed parallel training to acquire larger models faster on GPUs. This approach has its detriments, though; on one hand, a GPU's expanded capacity to compute also produces bigger bottlenecks in inter‐GPU's communications during model training, and multi‐GPU systems lead to complex connectivity. Workload schedulers then end up having to consider hardware topology and requirements for workload communication, in hopes of allocating GPU resources to optimize execution time and improve usage in a heterogeneous environment. On the other hand, the high memory requirements to train a DNN model make running the training processes on GPUs onerous. To contend with this, we introduce two execution optimization methods based on pipeline‐hybrid parallelism (using both data and model parallelism) in a GPU cluster with heterogeneous networking. First, we propose a model partition algorithm that accelerates pipeline‐hybrid parallelism training between heterogeneously network‐connected GPUs. Second, we introduce a cost‐balanced recomputing algorithm to reduce memory usage in the pipeline mode. Experiments show that our solution (Pipe‐Torch) averages a speedup of 1.4× compared with data parallelism, and reduces the memory footprint while maintaining pipelined load‐balanced training.

We establish a central limit theorem for Rényi entropies when the Rényi parameters belong to (0, 1) for a large class of random vectors. This complements a celebrated result of Barron (1986). As an application, we show that a general Rényi entropy power inequality fails when the Rényi parameter is in (0, 1).

In this paper, we investigate the role of convexity in entropy power inequalities. We establish Rényi entropy power inequalities of order r ∈ (0, 1) for a large class of densities, the so-called s-concave densities. This extends recent works on Rényi entropy power inequalities.

We introduce a new algorithm for realizing maximum likelihood (ML) decoding for arbitrary codebooks in discrete channels with or without memory, in which the receiver rank-orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the codebook is the ML decoding. We name this algorithm GRAND for Guessing Random Additive Noise Decoding. We establish that GRAND is capacity-achieving when used with random codebooks. For rates below capacity, we identify error exponents, and for rates beyond capacity, we identify success exponents. We determine the scheme's complexity in terms of the number of computations that the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which, if a member of the codebook is identified, that it is likely to be the transmitted code word. We introduce an approximate ML decoding scheme where the receiver abandons the search after a fixed number of queries, an approach we dub GRANDAB, for GRAND with ABandonment. While not an ML decoder, we establish that the algorithm GRANDAB is also capacity-achieving for an appropriate choice of abandonment threshold, and characterize its complexity, error, and success exponents. Worked examples are presented for Markovian noise that indicate these decoding schemes substantially outperform the brute force decoding approach.

We introduce a new algorithm for Maximum Likelihood (ML) decoding for channels with memory. The algorithm is based on the principle that the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in an element of the code-book is the ML decoding. In contrast to traditional approaches, this novel scheme has the desirable property that it becomes more efficient as the code-book rate increases. We establish that the algorithm is capacity achieving for randomly selected code-books. When the code-book rate is less than capacity, we identify asymptotic error exponents as the block length becomes large. When the code-book rate is beyond capacity, we identify asymptotic success exponents. We determine properties of the complexity of the scheme in terms of the number of computations the receiver must perform per block symbol. Worked examples are presented for binary memoryless and Markovian noise. These demonstrate that block-lengths that offer a good complexity-rate tradeoff are typically smaller than the reciprocal of the bit error rate.

Let Tε be the noise operator acting on Boolean functions f:{0,1}n→{0,1}, where ε ∈ [0,1/2] is the noise parameter. Given and the mean \mathbbEf, which Boolean function f maximizes the p-th moment \mathbbE(Tεf)p?Our findings are: in the low noise scenario, i.e., ε is small, the maximum is achieved by the lexicographical function; in the high noise scenario, i.e., ε is close to 1/2, the maximum is achieved by Boolean functions with the maximal degree-1 Fourier weight; and when p is an integer, the maximum is achieved by some monotone function, and in particular, among balanced Boolean functions, the maximum is achieved by any function which is 0 on all strings with fewer than n/2 1,s when p is large enough. Our results recover Mossel and O'Donnell's results about the problem of non-interactive correlation distillation, and confirm a conjecture of Courtade and Kumar on the most informative Boolean function in the low noise and high noise regimes. We also observe that Courtade and Kumar's conjecture is equivalent to that the dictator function maximizes \mathbbE(Tεf)pfor p close to 1.

Cover and Zhang proved a certain reversal of the Entropy Power Inequality for the sum of (possibly dependent) random variables possessing the same log-concave density, and what is more that log-concave densities were the only densities that satisfied such an inequality. In this work the authors consider the analogous reversal of recent Renyi Entropy Power Inequalities for random vectors and again show that not only do they hold for s-concave densities, but that s-concave densities are characterized by satisfying said inequalities.

Sharp exponential deviation estimates for the information content as well as a sharp bound on the varentropy are obtained for convex probability measures on Euclidean spaces. These provide, in a sense, a nonasymptotic equipartition property for convex measures even in the absence of stationarity-type assumptions.