Wireless networks are characterized by variation in the network states. In practice the variations are combated by allocating resources for learning the network states. In networks with high mobility users, the variations are fast enough so that allocating separate resources may significantly deplete the resources and quality of communication. In this thesis we study the optimal schemes for nonchoherent networks, where the network channel states are unknown and are changing within given time periods. We address the question on how to optimally allocate the resources for training and communication.

In the first part of the thesis, we consider single flow noncoherent wireless networks, where there is a single information source and a single destination. A simple nontrivial version of this is the noncoherent multiple input multiple output (MIMO) network. We consider the noncoherent MIMO with asymmetric link strengths, which would arise when the antennas are well separated. Examples of this are in the 5G architecture where the basestations can cooperate through a backhaul and when there is device-to-device cooperation through a sidechannel. The study of noncoherent MIMO is also fundamental in understanding the nature of noncoherent networks in the sense that the cut-sets in noncoherent networks form a MIMO. We prove that for single input multiple output (SIMO) and multiple input single input (MISO) networks, it is optimal to use the statistically best antenna. For 2x2 MIMO with symmetric statistics i.e., the direct links have identical statistics and so do the cross links, we derive the generalized degrees of freedom (gDoF) and prove that training-based schemes are not optimal. For larger MxM MIMO we prove that in general, a training scheme that learns all the channel parameters is not optimal in gDoF measure. We then proceed to study the noncoherent diamond network (2-relay channel). We prove that in certain regimes it is optimal to perform a relay selection and operate the network. In other regimes where we need to operate both the relays, it is not optimal to learn all the channel states through training. We propose a novel scheme that partially trains the network and combine it with scaling at the relays and quantize-map-forward operation and prove that our scheme is gDoF optimal.

In the second part of the thesis, we consider multiple flow noncoherent wireless networks. We specifically consider the noncoherent 2-user interference channel, where both the transmitters and the receivers do not know the channels strengths, but the statistics are known. For studying this, we first consider the fast fading interference channel (FF-IC) where the transmitters do not know the channel, but the receivers do know the channel. We extend the existing rate-splitting schemes when the channels are known at the receivers, to the fast fading case by performing rate-splitting based on the statistics of the channel. We prove that this scheme achieves the capacity approximately for a wide range of fading models. With this result for the FF-IC, we proceed to the noncoherent IC. We propose a noncoherent scheme with rate-splitting based on the statistics of the channel. We prove that this schemes achieves higher gDoF than a training-based scheme. The results extend to the case of noncoherent IC with feedback, where the outputs at the receivers are fed back to the corresponding transmitter.

The increase in mobile Internet usage has created a need to optimize content delivery in cellular networks.

In emerging technologies such as 5G, heterogeneous networks are proposed, which consist of sparsely deployed cellular base stations (BS) with wide coverage but low data rate, combined with a dense network of wireless access points (AP) of small coverage but relatively high data rate.

We envisage equipping the APs with a local cache.

When a group of users request some files, their demands are served by a (common) broadcast from one or more BSs, which is aided by side information placed a priori in the APs.

Therefore, there is a tradeoff between the size of the cache and the size of the broadcast.

Our goal is to design schemes that optimize this tradeoff.

Traditional caching techniques, which have proved efficient in the wired Internet, are insufficient to handle the explosion in multimedia demand in wireless networks.

The seminal work by Maddah-Ali and Niesen [``Fundamental limits of caching,'' IEEE Transactions on Information Theory, May 2014] introduced an information-theoretic framework to study this problem and proposed the so-called ``coded caching'' technique that takes advantage of the broadcast nature of wireless to send coded multicast messages to many users at once, thus greatly improving the transmission rate.

This original work assumed a caching system with an error-free broadcast link between the content library and the users, focused on equally popular files, and assumed that each user has one exclusive local cache.

Inspired by this work, this thesis studies more general coded caching problems within this information-theoretic framework.

Broadly speaking, we focus on non-uniform content popularity as well as more general network topologies.

First, we consider a system where the files desired by the users are not all equally popular.

We adopt a ``multi-level'' popularity model where files are partitioned into multiple popularity classes.

Under this model, we study the behavior of the system as the total number of users, as compared to the number of caches, varies.

Furthermore, we allow a more complex topology by requiring some users to connect to multiple caches at once.

We find approximately optimal strategies for the two extreme cases: when the number of users per cache is very large, and when each cache has exactly one user.

An interesting dichotomy is observed where the approximately optimal strategies required for these two extremes are very different.

Finally, we provide a heuristic for ``discretizing'' common popularity distributions such as Zipf into multiple levels, and numerically evaluate its performance.

Second, we study the caching problem when we are allowed to assign users to caches after their demands are known, under some restrictions.

Specifically, we divide the caches into several clusters, and we assume that each user can be assigned to one cache from a specific cluster and that each cache can serve no more than one user.

Focusing on a stochastic Zipf popularity model, we find that there are regimes in which coded caching is no longer efficient.

Instead, a strategy that consists in replicating files across clusters and performs an uncoded delivery dominates certain regimes.

We compare these two schemes and find the regimes in which each is more efficient, as a function of cache memory, cluster size, and skewness of popularity.

Finally, we show that each scheme is approximately optimal in some of these regimes.

Third, we return to the uniform popularity model in order to study more complicated networks than the error-free broadcast network.

Our main focus is on Gaussian interference networks, where caches are placed at both the transmitters (BSs) and the receivers (APs).

We propose a separation-based approach that creates separate network and physical layers, with a multiple-multicast message set to act as an interface between them.

At the physical layer, we focus on transmitting this message set across the interference channel; at the network layer, we solve the caching problem using the message set as a set of error-free links replacing the channel.

We show that this architecture is approximately optimal under high SNR.

Among the implications of this result is that placing common information between the transmitters cannot give more than a constant-factor benefit.

Moreover, we show that, when the receiver memory is large, a small number of transmitters is enough to obtain most of the benefits.

Large scale distributed optimization has become increasingly important with the emergence of edge computation architectures such as in the federated learning setup, where large amounts of data, possibly of a secure nature and generated in an online manner can be massively distributed across personal devices. A key bottleneck for many such large-scale problems is in the communication overhead of exchanging information between devices over bandwidth limited networks as well as in the unreliability of communication for distributed optimization. The existing approaches propose to mitigate these bottlenecks either by using different forms of compression or by computing local models and mixing them iteratively. In this thesis we first propose a novel class of highly communication efficient operators that employ stochastic and deterministic quantization with aggressive sparsification such as Top-k in the form of a composed operator. Furthermore, in federated learning one can use local computations to reduce communication. Using such a framework, we incorporate local iterations into our algorithm which allows the communication to be infrequent and possibly asynchronous thereby enabling significantly reduced communication.

Putting them together we have distributed Qsparse-local-SGD for federated learning for which our analysis demonstrates convergence rates matching vanilla distributed SGD where we observe that quantization and sparsification are almost for free for smooth functions, both non-convex and convex. We characterize the asymptotic allowable limits of local iterations for synchronous and asynchronous implementations of Qsparse-local-SGD, so as to harness both the distributed processing gains as well as the benefits of quantization, sparsification and local computations. Our numerics demonstrate that Qsparse-local-SGD combines the bit savings of our composed operators, as well as local computations, thereby outperforming the cases where these techniques are individually used. We use it to train ResNet-50 on ImageNet, as well as a softmax multi-class classifier on MNIST, resulting in significant savings over the state-of-the-art, in the number of bits transmitted to reach target accuracy.

Many types of communication and computation networks arising in modern systems have fundamentally dynamic, time-varying, and ultimately unreliably available resources. Specifically, in wireless communication networks, such unreliability may manifest itself as variability in channel conditions, intermittent availability of undedicated resources (such as unlicensed spectrum), or collisions due to multiple-access. In distributed computing, and specifically in large-scale distributed optimization and machine learning, this phenomenon manifests itself in the form of communication bottlenecks, straggling or failed nodes, or running background processes which hamper or slow down the computational task. In this thesis, we develop information-theoretically-motivated approaches that make progress towards building robust and reliable communication and computation networks built upon unreliable resources. In the first part of the thesis, we focus on three problems in wireless networks which involve opportunistically harnessing time-varying resources while providing theoretical performance guarantees. First, we show that in full-duplex uplink-downlink cellular networks, a simple, low-overhead user scheduling scheme that exploits the variations in channel conditions can be used to optimally mitigate inter-user interference in the many-user regime. Next, we consider the use of intermittently available links over unlicensed spectral bands to enhance communication over the licensed cellular band. We show that channel output feedback over such links, combined with quantize-map-forward relaying, provides generalized-degrees-of-freedom gain in interference networks. We characterize the information-theoretic capacity region of this model to within a constant gap. We finally consider the use of such intermittent links in device-to-device cooperation to aid cellular downlink. We develop an optimal dynamic resource allocation algorithm for such networks using stochastic approximation and graph theory techniques, and show that the resulting scheme results in up to 5-6x throughput gain for cell-edge users. In the second part, we consider the problem of distributed optimization and machine learning over large-scale, yet unreliable clusters. Focusing on a master-worker architecture, where large-scale datasets are distributed across worker nodes which communicate with a central parameter server to optimize a global objective, we develop a framework for embedding redundancy in the dataset to combat node failures and delays. This framework consists of an efficient linear transformation (coding) of the dataset that results in an overcomplete representation, combined with a coding-oblivious application of a distributed optimization algorithm. We show that if the linear transformation is designed to satisfy certain spectral properties resembling the restricted isometry property, nodes that fail or delay their computation can be dynamically left out of the computational process, while still converging to a reasonable solution with fast convergence rates, obviating the need for explicit fault-tolerance mechanisms and significantly speeding up overall computation. We implement the techniques on Amazon EC2 clusters to demonstrate the applicability of the proposed technique to various machine learning problems, such as logistic regression, support vector machine, ridge regression, and collaborative filtering; as well as several popular optimization algorithms including gradient descent, L-BFGS, coordinate descent and proximal gradient methods.