Coded computing is an effective technique to mitigate “stragglers” in large-scale and distributed matrix multiplication. In particular, univariate polynomial codes have been shown to be effective in straggler mitigation by making the computation time depend only on the fastest workers. However, these schemes completely ignore the work done by the straggling workers resulting in a waste of computational resources.
We consider machine learning applications that train a model by leveraging data distributed over a trusted network, where communication constraints can create a performance bottleneck. A number of recent approaches propose to overcome this bottleneck through compression of gradient updates. However, as models become larger, so does the size of the gradient updates.
Computing is the next frontier for information theory. Intellectually, the goal of coded computing has been of interest from the days of von Neumann and Shannon. von Neumann examined this issue in his 1956 paper “Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components,” which was in turn motivated intellectually by Shannon’s 1948 paper, and by the application of understanding reliability of seemingly noisy biological systems.
An error in the proof of the data-dependent tail bounds on the generalization error presented in Hellström and Durisi (2020) is identified, and a correction is proposed. Furthermore, we note that the absolute continuity requirements in Hellström and Durisi (2020) need to be strengthened to avoid measurability issues.
We study the problem of content delivery in two-user interference channels with altering topology, random available cache at the receivers, and delayed channel knowledge at the transmitters. We establish a new set of outer-bounds on the achievable rates when each receiver has access to a random fraction of the message intended for the other receiver, and when each transmitter is aware of which part of its own message is known to the unintended receiver.
We consider a distributed storage system with $n$ nodes, where a user can recover the stored file from any $k$ nodes, and study the problem of repairing $r$ partially failed nodes. We consider broadcast repair, that is, $d$ surviving nodes transmit broadcast messages on an error-free wireless channel to the $r$ nodes being repaired, which are then used, together with the surviving data in the local memories of the failed nodes, to recover the lost content.