Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.
27 September 2016 in IEEE Transactions on Information Theory
In a group testing scheme, a series of tests are designed to identify a small number t of defective items that are present among a large number N of items. Each test takes a group of items as input and produces a binary output indicating whether any defective item is present in the group. In a nonadaptive scheme, the tests have to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a disjunct matrix, an M × N binary matrix where the union of supports of any t columns does not contain the support of any other column. In principle, one wants to have such a matrix with a minimum possible number M of rows. In this paper, we consider the scenario where defective items are random and follow simple probability distributions. In particular, we consider the cases where: 1) each item can be defective independently with probability t/N and 2) each t-set of items can be defective with uniform probability. In both the cases, our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before, and it is known that Θ(t log N) tests are necessary as well as sufficient (via random coding) in both the cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with O(t 2 log N) rows that identify any t defectives. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. Indeed, we show how distance, a pairwise property of the columns of the matrix, translates to a (t + 1)-wise property of the columns. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to O(t(log 2 N/log t)) for both the first and second cases. While only away by a factor of (log N/log t) from the optimal number of tests, this is the best set of parameters that one can obtain from a deterministic construction, and our main contribution lies in relating the group testing properties to the average and minimum distances of constant-weight codes.
23 March 2022 in IEEE Transactions on Information Theory
In this work, we present a family of vector quantization schemes vqSGD (Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic reduction in the communication cost with convergence guarantees in first-order distributed optimization. In the process we derive the following fundamental information theoretic fact: $\Theta \left({\frac {d}{R^{2}}}\right)$ bits are necessary and sufficient (up to an additive $O(\log d)$ term) to describe an unbiased estimator $\hat{\boldsymbol {g}}(\boldsymbol {g})$ for any $\boldsymbol {g}$ in the $d$ -dimensional unit sphere, under the constraint that $\| \hat{\boldsymbol {g}}(\boldsymbol {g})\|_{2}\le R$ almost surely, $R > 1$ . In particular, we consider a randomized scheme based on the convex hull of a point set, that returns an unbiased estimator of a $d$ -dimensional gradient vector with almost surely bounded norm. We provide multiple efficient instances of our scheme, that are near optimal, and require $o(d)$ bits of communication at the expense of tolerable increase in error. The instances of our quantization scheme are obtained using well-known families of binary error-correcting codes and provide a smooth tradeoff between the communication and the estimation error of quantization. Furthermore, we show that vqSGD also offers automatic privacy guarantees.
Federated Learning (FL) has gained increasing interest in recent years as a distributed on-device learning paradigm. However, multiple challenges remain to be addressed for deploying FL in real-world Internet-of-Things (IoT) networks with hierarchies. Although existing works have proposed various approaches to account data heterogeneity, system heterogeneity, unexpected stragglers and scalibility, none of them provides a systematic solution to address all of the challenges in a hierarchical and unreliable IoT network. In this paper, we propose an asynchronous and hierarchical framework (Async-HFL) for performing FL in a common three-tier IoT network architecture. In response to the largely varied networking and system processing delays, Async-HFL employs asynchronous aggregations at both the gateway and cloud levels thus avoids long waiting time. To fully unleash the potential of Async-HFL in converging speed under system heterogeneities and stragglers, we design device selection at the gateway level and device-gateway association at the cloud level. Device selection module chooses diverse and fast edge devices to trigger local training in real-time while device-gateway association module determines the efficient network topology periodically after several cloud epochs, with both modules satisfying bandwidth limitations. We evaluate Async-HFL’s convergence speedup using large-scale simulations based on ns-3 and a network topology from NYCMesh. Our results show that Async-HFL converges 1.08-1.31x faster in wall-clock time and saves up to 21.6% total communication cost compared to state-of-the-art asynchronous FL algorithms (with client selection). We further validate Async-HFL on a physical deployment and observe its robust convergence under unexpected stragglers.
17 March 2021 in IEEE Transactions on Information Theory
In the beautifully simple-to-state problem of trace reconstruction, the goal is to reconstruct an unknown binary string x given random “traces” of x where each trace is generated by deleting each coordinate of x independently with probability p <; 1. The problem is well studied both when the unknown string is arbitrary and when it is chosen uniformly at random. For both settings, there is still an exponential gap between upper and lower sample complexity bounds and our understanding of the problem is still surprisingly limited. In this paper, we consider natural parameterizations and generalizations of this problem in an effort to attain a deeper and more comprehensive understanding. Perhaps our most surprising results are: 1) We prove that exp(O(n 1/4 √{logn})) traces suffice for reconstructing arbitrary matrices. In the matrix version of the problem, each row and column of an unknown √n×√n matrix is deleted independently with probability p. Our results contrasts with the best known results for sequence reconstruction where the best known upper bound is exp(O(n 1/3 )). 2) An optimal result for random matrix reconstruction: we show that Θ(logn) traces are necessary and sufficient. This is in contrast to the problem for random sequences where there is a super-logarithmic lower bound and the best known upper bound is exp(O(log 1/3 n)). 3) We show that exp(O(k 1/3 log 2/3 n)) traces suffice to reconstruct k-sparse strings, providing an improvement over the best known sequence reconstruction results when k = o(n/log 2 n). 4) We show that poly(n) traces suffice if x is k-sparse and we additionally have a “separation” promise, specifically that the indices of 1's in x all differ by Ω(k logn).
16 August 2021 in IEEE Journal on Selected Areas in Information Theory
We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our algorithm matches that of Yin et al. (2018), which uses more complicated schemes (coordinate-wise median, trimmed mean). Furthermore, for communication efficiency, we consider a generic class of $\delta $ -approximate compressors from Karimireddi et al. (2019) that encompasses sign-based compressors and top- $k$ sparsification. Our algorithm uses compressed gradients and gradient norms for aggregation and Byzantine removal respectively. We establish the statistical error rate for non-convex smooth loss functions. We show that, in certain range of the compression factor $\delta $ , the (order-wise) rate of convergence is not affected by the compression operation. Moreover, we analyze the compressed gradient descent algorithm with error feedback (proposed in Karimireddi et al. 2019) in a distributed setting and in the presence of Byzantine worker machines. We show that exploiting error feedback improves the statistical error rate. Finally, we experimentally validate our results and show good performance in convergence for convex (least-square regression) and non-convex (neural network training) problems.