Neural compression methods are gaining popularity due to their superior rate-distortion performance over traditional methods, even at extremely low bitrates below 0.1 bpp. As deep learning models, they are prone to bias during the training, potentially leading to unfair outcomes for individuals in different groups. In this paper, we present a scalable framework for evaluating bias in 9 neural image compression models. We first demonstrate that traditional distortion metrics are ineffective in capturing bias in these models. Next, we highlight that racial bias is present in all neural compression models and can be captured by examining facial phenotype degradation in image reconstructions. Finally, we show that utilizing a racially balanced training set can reduce bias but is not a sufficient bias mitigation strategy, since the bias can be attributed to both compression model bias and classification model bias. We believe that this work is a first step towards evaluating and eliminating bias in neural image compression models.

In differentially private distributed mean estimation (DP-DME), a central server computes the mean of vectors distributed across$n$users while preserving differential privacy (DP). DP-DME has been studied under various DP models, with distributed DP with secure aggregation and local DP (LDP) being the main models that do not rely on a trusted third party. Distributed DP-based schemes leverage correlated noise among users to achieve higher accuracy than LDP-based schemes, where users operate independently. However, the accuracy of distributed DP comes at the cost of higher communication overhead for generating correlated noise and complex multiround protocols to handle dropouts. In this work, we analyze the communication-accuracy trade-off in distributed DP-DME under arbitrary communication constraints, and propose a method to generate correlated noise strategically within these constraints to enable single-round dropout handling. Our results show that the communication costs of existing distributed DP-DME approaches can be substantially reduced with minimal impact on accuracy.

Parallel tensor network contraction algorithms have emerged as the pivotal benchmarks for assessing the classical limits of computation, exemplified by Google's demonstration of quantum supremacy through random circuit sampling. However, the massive parallelization of the algorithm makes it vulnerable to computer node failures. In this work, we apply coded computing to a practical parallel tensor network contraction algorithm. To the best of our knowledge, this is the first attempt to code tensor network contractions. Inspired by matrix multiplication codes, we provide two coding schemes: 2-node code for practicality in quantum simulation and hyperedge code for generality. Our 2-node code successfully achieves significant gain for f-resilient number compared to naive replication, proportional to both the number of node failures and the dimension product of sliced indices. Our hyperedge code can cover tensor networks out of the scope of quantum, with degraded gain in the exchange of its generality.

We consider the problem of private distributed multiparty computation. It is well-established that coding strategies can enable perfect information-theoretic privacy in distributed computation (e.g., the BGW protocol). However, perfect privacy comes at a high computational overhead cost, requiring 2t + 1 compute nodes to ensure privacy against any t colluding nodes. By allowing for approximate computation and operations over the real numbers, we demonstrate that noise can be added to data shared with computing nodes in order to ensure differential privacy instead of perfect privacy. Specifically, the signal-to-noise ratio of the data received by colluding nodes can be mapped to differential privacy guarantees. We precisely characterize the trade-off between differential privacy and accuracy in this setting, and prove that a degree of differential privacy against t colluding nodes can always be ensured whenever there are more than t+1 computing node—a reduction of t nodes compared to perfect privacy. A particularly novel technical aspect is an achievable scheme that carefully encodes the data and noise at different magnitude levels. This coding scheme ensures that the adversary’s input appears to be layers of noise, whereas the legitimate decoder is able to uncover the desired computation by "peeling" off the noise layers.

We investigate the fairness concerns of training a machine learning model using data with missing values. Even though there are a number of fairness intervention methods in the literature, most of them require a complete training set as input. In practice, data can have missing values, and data missing patterns can depend on group attributes (e.g. gender or race). Simply applying off-the-shelf fair learning algorithms to an imputed dataset may lead to an unfair model. In this paper, we first theoretically analyze different sources of discrimination risks when training with an imputed dataset. Then, we propose an integrated approach based on decision trees that does not require a separate process of imputation and learning. Instead, we train a tree with missing incorporated as attribute (MIA), which does not require explicit imputation, and we optimize a fairness-regularized objective function. We demonstrate that our approach outperforms existing fairness intervention methods applied to an imputed dataset, through several experiments on real-world datasets.

The classic BGW algorithm of Ben Or, Goldwasser and Wigderson for secure multiparty computing demonstrates that secure distributed matrix multiplication over finite fields is possible over 2t+1 computation nodes, while keeping the input matrices private from every t colluding computation nodes. In this paper, we develop and study a novel coding formulation to explore the trade-offs between computation accuracy and privacy in secure multiparty computing for real-valued data, even with fewer than 2t+1 nodes, through a differential privacy perspective. For the case of t = 1, we develop achievable schemes and converse arguments that bound ϵ — the differential privacy parameter that measures the privacy loss — for a given accuracy level. Our achievable coding schemes are specializations of Shamir secret sharing applied to real-valued data, coupled with appropriate choice of evaluation points. We develop converse arguments that apply for general additive noise based schemes.

We consider the problem of producing fair probabilistic classifiers for multi-class classification tasks. We formulate this problem in terms of ``projecting'' a pre-trained (and potentially unfair) classifier onto the set of models that satisfy target group-fairness requirements. The new, projected model is given by post-processing the outputs of the pre-trained classifier by a multiplicative factor. We provide a parallelizable, iterative algorithm for computing the projected classifier and derive both sample complexity and convergence guarantees. Comprehensive numerical comparisons with state-of-the-art benchmarks demonstrate that our approach maintains competitive performance in terms of accuracy-fairness trade-off curves, while achieving favorable runtime on large datasets. We also evaluate our method at scale on an open dataset with multiple classes, multiple intersectional groups, and over 1M samples.

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of$P$computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with ∊ relative error from any$m$of the$P$nodes for any ∊ >0. We obtain this result through a careful specialization of MatDot codes-a class of matrix multiplication code previously developed in the context of exact recovery (∊ = 0). Since previous results showed that the MatDot code is tight for a class of linear coding schemes for exact recovery, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. Moreover, we develop an optimization framework based on alternating minimization that enables the discovery of new codes for approximate matrix multiplication.

QR decomposition of a matrix is one of the essential operations that is used for solving linear equations and finding least-squares solutions. We propose a coded computing strategy for parallel QR decomposition with applications to solving a full-rank square system of linear equations in a high-performance computing system. Our strategy is applied to the parallel Gram-Schmidt algorithm, which is one of the three commonly used algorithms for QR decomposition. Conventional coding strategies cannot preserve the orthogonality of Q. We prove a condition for a checksum-generator matrix to restore the degraded orthogonality of the decoded Q through low-cost post-processing, and construct a checksum-generator matrix for single-node failures. We obtain the minimal number of checksums required for singlenode failures under the "in-node checksum storage setting", where checksums are stored in original nodes, and further adapt the coded QR decomposition to this setting.

Computing systems are evolving rapidly. At the device level, emerging devices are beginning to compete with traditional CMOS systems. At the architecture level, novel architectures are successfully avoiding the communication bottleneck that is a central feature, and a central limitation, of the von Neumann architecture. Furthermore, such systems are increasingly plagued by unreliability. This unreliability arises at device or gate-level in emerging devices, and can percolate up to processor or system-level if left unchecked. The goal of this article is to survey recent advances in reliable computing using unreliable elements, with an eye on nonsilicon and non-von Neumann architectures. We first observe that instead of aiming for generic computing problems, the community could use “dwarfs of modern computing,” first noted in the high-performance computing (HPC) community, as a starting point. These computing problems are the basic building blocks of almost all scientific computing, machine learning, and data analytics today. Next, we survey the state of the art in “coded computing,” which is an emerging area that advances on classical algorithm-based fault-tolerance (ABFT) and brings a fundamental information-theoretic perspective. By weaving error-correcting codes into a computing algorithm, coded computing provides dramatic improvements on solutions, as well as obtains novel fundamental limits, for problems that have been open for more than 30 years. We introduce existing and novel coded computing techniques in the context of “coded dwarfs,” where a specific dwarf's computation is made resilient by applying coding. We discuss how, for the same redundancy, “coded dwarfs” are significantly more resilient compared to classical techniques such as replication. Furthermore, by examining a widely popular computation task-training large neural networks-we demonstrate how coded dwarfs can be applied to address this fundamentally nonlinear problem. Finally, we discuss practical challenges and future directions in implementing coded computing techniques on emerging and existing nonsilicon and/or non-von Neumann architectures.

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent “Polynomial code” constructions in recovery threshold, i.e., the required number of successful workers. When a fixed 1/m fraction of each matrix can be stored at each worker node, Polynomial codes require m2 successful workers, while our MatDot codes only require 2m - 1 successful workers. However, MatDot codes have higher computation cost per worker and higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Furthermore, we propose “PolyDot” coding that interpolates between Polynomial codes and MatDot codes to trade off computation/communication costs and recovery thresholds. Finally, we demonstrate a novel coding technique for multiplying n matrices (n ≥ 3) using ideas from MatDot and PolyDot codes.

As error/failure rates in supercomputers are projected to grow, computationally intensive scientific applications that lever-age large-scale parallelization will suffer from the increased error rate. In this work, we apply "coded computing" to protein folding simulations in an error-prone environment. We implemented the fast Fourier Poisson method for solving electrostatic equations at each time step of the simulation, and we utilize coded FFT algorithm to protect the compute-intensive FFT algorithm from soft errors. Through experiments on Amazon AWS, we showed that coded protein folding can be implemented with less than 10% overhead in total simulation time, and also showed that coded computing approach is faster than classical checkpointing method when the error rate is high.

The problem of computing distributed matrix multiplication reliably has been of immense interest for several decades. Recently, it was shown that Polynomial codes achieve the theoretically minimum recovery bandwidth. However, existing constructions for Polynomial codes are nonsystematic, which can impose substantial overhead in distributed computing. In this paper, we propose two different systematic code constructions that achieve the same recovery bandwidth as Polynomial codes. First uses a random coding argument, and the second is polynomial-based, but uses bivariate instead of originally used univariate polynomials. We show that the proposed constructions are communication optimal with high probability.

In an era of ever-increasing dynamicity and heterogeneity of wireless networks, energy is fast becoming the most constrained resource. First, we review recent studies that suggest that using one single error-correcting code (ECC) designed to meet the worst case requirement is inefficient in terms of energy consumption when there are many heterogeneous nodes in the network. These works extend the classical Shannon theory and incorporate circuit energy and signal transmit energy to optimize total energy/power consumption of today's communication systems. Then, we survey recent work on designing adaptive ECCs to operate energy efficiently even in the presence of extremely large heterogeneity in requirements and conditions. Two constructions of energy-adaptive codes are summarized: energy-adaptive low-density parity-check (LDPC) codes and energy-adaptive polar codes. These constructions have shown theoretically and empirically that having adaptivity in code design can save substantial energy, especially when the network has very diverse communication scenarios. Finally, we suggest a few possible applications where energy-adaptive codes can be employed and outline interesting future directions and challenges.

We propose a novel application of coded computing to the problem of the nearest neighbor estimation using MatDot Codes (Fahim et al., Allerton'17) that are known to be optimal for matrix multiplication in terms of recovery threshold under storage constraints. In approximate nearest neighbor algorithms, it is common to construct efficient in-memory indexes to improve query response time. One such strategy is Multiple Random Projection Trees (MRPT), which reduces the set of candidate points over which Euclidean distance calculations are performed. However, this may result in a high memory footprint and possibly paging penalties for large or high-dimensional data. Here we propose two techniques to parallelize MRPT that exploit data and model parallelism respectively by dividing both the data storage and the computation efforts among different nodes in a distributed computing cluster. This is especially critical when a single compute node cannot hold the complete dataset in memory. We also propose a novel coded computation strategy based on MatDot codes for the model-parallel architecture that, in a straggler-prone environment, achieves the storage-optimal recovery threshold, i.e., the number of nodes that are required to serve a query. We experimentally demonstrate that, in the absence of straggling, our distributed approaches require less query time than execution on a single processing node, providing near-linear speedups with respect to the number of worker nodes. Our experiments on real systems with simulated straggling, we also show that in a straggler-prone environment, our strategy achieves a faster query execution than the uncoded strategy.

This paper has two main contributions. First, we propose a novel coding technique - Generalized PolyDot - for matrix-vector products that advances on existing techniques for coded matrix operations under storage and communication constraints. Next, we use Generalized PolyDot for the problem of training large Deep Neural Networks (DNNs) using unreliable nodes that are prone to soft-errors, e.g., bit flips during computation that produce erroneous outputs. An additional difficulty imposed by the problem of DNN training is that the parameter values (weight matrices) are updated at every iteration, and thus require a prohibitively large encoding cost at every iteration if we naively extend existing coded computing techniques. Thus, we propose a “unified” coded DNN training strategy where we weave coding into the operations of DNN training itself, so that the weight matrices, once initially encoded, remain encoded during updates with negligible encoding/decoding overhead per iteration. Moreover, our strategy can also allow for errors even in the nonlinear step of training. Finally, our coded DNN training strategy is completely decentralized: no assumptions on the presence of a master node are made, which avoids any single point of failure under soft-errors. Our strategy can provide unboundedly better error tolerance than the competing replication strategy and an MDS-code-based strategy [1].

It is now well known that using a long and complicated error correcting code (ECC) designed for the worst-case error probability requirement wastes excessive total system energy (transmit + circuit energy) when the error probability requirement is much higher than the worst case. We propose a novel adaptive polar coding strategy that adjusts the decoder circuit to consume minimal decoding circuit energy at each given target error requirement. By combining Thompson's VLSI theory and scaling analysis of polar codes, we provide upper bounds on energy, area, and time complexity of polar decoding circuits in terms of target block error probability. The upper bounds are derived from an explicit construction of decoder circuit based on mesh-network structure. Our comparison shows that the proposed energy-adaptive coding strategy has a scaling-sense gain in decoding energy with little circuit area overhead when there is a large gap between the worst-case and typical target error rate requirements.

In this paper, message dissemination with node mobility is studied where each node in the network having mobility wants to send its message to all the other nodes. The channel capacity between two nodes is assumed to be large enough for exchanging all the messages they have when they get close enough. We show that what type of network graph enables each node to accumulate all messages in the network, and investigate the dissemination time T for all nodes to get all messages. For a general directed graph model, the upper and lower bounds on T are given as Θ(n2) and Θ(1), respectively. For some special cases, we present tighter bounds. For general undirected graph, T is upper bounded by Θ(n). For grid graph, T is an order of Θ(√n).