Current state-of-the-art Neural Architecture Search (NAS) methods neither efficiently scale to multiple hardware platforms, nor handle diverse architectural search-spaces. To remedy this, we present DONNA (Distilling Optimal Neural Network Architectures), a novel pipeline for rapid, scalable and diverse NAS, that scales to many user scenarios. DONNA consists of three phases. First, an accuracy predictor is built using blockwise knowledge distillation from a reference model. This predictor enables searching across diverse networks with varying macro-architectural parameters such as layer types and attention mechanisms, as well as across micro-architectural parameters such as block repeats and expansion rates. Second, a rapid evolutionary search finds a set of pareto-optimal architectures for any scenario using the accuracy predictor and on-device measurements. Third, optimal models are quickly fine-tuned to training-from-scratch accuracy. DONNA is up to 100× faster than MNasNet in finding state-of-the-art architectures on-device. Classifying ImageNet, DONNA architectures are 20% faster than EfficientNet-B0 and Mo-bileNetV2 on a Nvidia V100 GPU and 10% faster with 0.5% higher accuracy than MobileNetV2-1.4x on a Samsung S20 smartphone. In addition to NAS, DONNA is used for search-space extension and exploration, as well as hardware-aware model compression.

In communication networks, cooperative strategies are coding schemes where network nodes work together to improve performance metrics such as the total rate delivered across the network. This work studies encoder cooperation in the setting of a discrete multiple access channel (MAC) with two encoders and a single decoder. A network node, here called the cooperation facilitator (CF), that is connected to both encoders via rate-limited links, enables the cooperation strategy. Previous work by the authors presents two classes of MACs: (i) one class where the average-error sum-capacity has an infinite derivative in the limit where CF output link capacities approach zero, and (ii) a second class of MACs where the maximal-error sum-capacity is not continuous at the point where the output link capacities of the CF equal zero. This work contrasts the power of the CF in the maximal- and average-error cases, showing that a constant number of bits communicated over the CF output link can yield a positive gain in the maximal-error sum-capacity, while a far greater number of bits, even a number that grows sublinearly in the blocklength, can never yield a non-negligible gain in the average-error sum-capacity.

In communication networks, cooperative strategies are coding schemes where network nodes work together to improve network performance metrics such as sum-rate. This work studies encoder cooperation in the setting of a discrete multiple access channel with two encoders and a single decoder. A node in the network that is connected to both encoders via rate-limited links, referred to as the cooperation facilitator (CF), enables the cooperation strategy. Previously, the authors presented a class of multiple access channels where the average-error sum-capacity has an infinite derivative in the limit where CF output link capacities approach zero. The authors also demonstrated that for some channels, the maximal-error sum-capacity is not continuous at the point where the output link capacities of the CF equal zero. This work shows that the average-error sum-capacity is continuous when CF output link capacities converge to zero; that is, the infinite derivative of the average-error sum-capacity is not a result of its discontinuity as in the maximal-error case.

Cooperation strategies allow communication devices to work together to improve network capacity. Consider a network consisting of k encoders, a multiple access channel (MAC), a decoder, and a node, referred to as a “cooperation facilitator” (CF), that is connected to each encoder via a pair of rate-limited links, with one link going from the encoder to the CF and the other link going back. Let the “cooperation rate” be the total outgoing rate of the CF. This paper demonstrates the existence of a class of MACs where the ratio of the sum-capacity gain to cooperation rate tends to infinity as the cooperation rate tends to zero. For any k ≥ 2, examples of channels in this class include the k-user binary adder MAC and the k-user Gaussian MAC.

In network cooperation strategies, nodes work together with the aim of increasing transmission rates or reliability. This paper demonstrates that enabling cooperation between the transmitters of a two-user multiple access channel via a cooperation facilitator that has access to both messages results in a network whose maximal- and average-error capacity regions are the same; this benefit ensues even when the information received by each transmitter is negligible. From this result, it follows that if a multiple access channel with no transmitter cooperation has different maximal- and average-error sum-capacities, then the maximal-error sum-capacity of the network consisting of this channel and a cooperation facilitator is not continuous with respect to the output edge capacities of the facilitator. Thus, there exist networks where adding negligible rate yields a non-negligible benefit.

In many communication networks, the availability of channel state information at various nodes provides an opportunity for network nodes to work together, or “cooperate.” This work studies the benefit of cooperation in the multiple access channel with a cooperation facilitator, distributed state information at the encoders, and full state information available at the decoder. Under various causality constraints, sufficient conditions are obtained such that encoder cooperation through the facilitator results in a gain in sum-capacity that has infinite slope in the information rate shared with the encoders. This result extends the prior work of the authors on cooperation in networks where none of the nodes have access to state information.

A key result of classical information theory states that if the rate of a randomly generated codebook is less than the mutual information between the channel's input and output, then the probability that that codebook has negligible error goes to one as the blocklength goes to infinity. In an attempt to bridge the gap between the probabilistic world of classical information theory and the combinatorial world of zero-error information theory, this work derives necessary and sufficient conditions on the rate so that the probability that a randomly generated codebook operated under list decoding (for any fixed list size) has zero error probability goes to one as the blocklength goes to infinity. Furthermore, this work extends the classical birthday problem to an information-theoretic setting, which results in the definition of a “noisy” counterpart of Rényi entropy, analogous to how mutual information can be considered a noisy counterpart of Shannon entropy.

Cooperation strategies that allow communication devices to work together can improve network capacity. This paper generalizes the “cooperation facilitator” (CF) model from the 2-user to the k-user multiple access channel (MAC), extending capacity bounds, characterizing all k-user MACs for which the sum-capacity gain of encoder cooperation exceeds the capacity cost that enables it, and demonstrating an infinite benefit-cost ratio in the limit of small cost.

In network cooperation strategies, nodes work together with the aim of increasing transmission rates or reliability. This paper demonstrates that enabling cooperation between the transmitters of a two-user multiple access channel via a cooperation facilitator that has access to both messages, always results in a network whose maximal- and average-error sum-capacities are the same-even when the information shared with the encoders is negligible. Thus, for a multiple access channel whose maximal- and average-error sum-capacities differ, the maximal-error sum-capacity is not continuous with respect to the output edge capacities of the facilitator. This shows that for some networks, sharing even a negligible number of bits per channel use with the encoders can yield a non-negligible benefit.

In cooperative communication, network nodes that would otherwise act independently instead coordinate their efforts with the aim of improving communication performance. To better understand cooperation, we consider communication over a multiple access channel using a “cooperation facilitator”, a node that receives rate-limited message descriptions from the transmitters and sends rate-limited message descriptions back. This model includes the conferencing encoders model and a prior model from the current authors as special cases. We characterize a class of multiple access channels for which there is no gain in sum-capacity under current or prior cooperation models. We then show that for all other multiple access channels, the gain in sum-capacity can be far greater than the capacity of the cooperation facilitator's output links. These channels violate the edge removal property. The Gaussian multiple access channel is an important special case for which we explicitly characterize the sum-rate cooperation gain.

In this paper, we propose a new cooperation model for discrete memoryless multiple access channels. Unlike in prior cooperation models (e.g., conferencing encoders), where the transmitters cooperate directly, in this model the transmitters cooperate through a larger network. We show that under this indirect cooperation model, there exist channels for which the increase in sum-capacity resulting from cooperation is significantly larger than the rate shared by the transmitters to establish the cooperation. This result contrasts both with results on the benefit of cooperation under prior models and results in the network coding literature, where attempts to find examples in which similar small network modifications yield large capacity benefits have to date been unsuccessful.