Analog Lagrange Coded Computing

• URL: http://arxiv.org/abs/2008.08565v2
• Date: Fri, 29 Jan 2021 23:42:14 GMT
• Title: Analog Lagrange Coded Computing
• Authors: Mahdi Soleymani, Hessam Mahdavifar, A. Salman Avestimehr
• Abstract summary: A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. LCC, proposed by Yu et al., leverages the well-known Lagrange operations on coded computing. We propose a novel extension of LCC to the analog domain, referred to as analog (ALCC)
• Score: 23.67685616088422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. Lagrange coded computing (LCC), proposed by Yu et al., leverages the well-known Lagrange polynomial to perform polynomial evaluation of the dataset in such a scenario in an efficient parallel fashion while keeping the privacy of data amidst possible collusion of workers. This solution relies on quantizing the data into a finite field, so that Shamir's secret sharing, as one of its main building blocks, can be employed. Such a solution, however, is not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of LCC to the analog domain, referred to as analog LCC (ALCC). All the operations in the proposed ALCC protocol are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in ALCC, against any subset of colluding workers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, a fundamental trade-off between the accuracy of the outcome of ALCC and its privacy level is observed and is numerically evaluated. Moreover, we implement the proposed scheme to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to the state-of-the-art LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

Related papers

• Determinant Estimation under Memory Constraints and Neural Scaling Laws [48.68885778257016]
  We derive a novel hierarchical algorithm for large-scale log-determinant calculation in memory-constrained settings.<n>We show that the ratio of pseudo-determinants satisfies a power-law relationship, allowing us to derive corresponding scaling laws.<n>This enables accurate estimation of NTK log-determinants from a tiny fraction of the full dataset.
  arXiv  Detail & Related papers  (2025-03-06T13:32:13Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem. These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem. We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• Secure numerical simulations using fully homomorphic encryption [0.8739101659113153]
  This work explores the viability of FHE-based, privacy-preserving numerical simulations of partial differential equations.<n>Two Julia packages are introduced, OpenFHE$.$jl and SecureArithmetic$.$jl, which wrap the OpenFHE C++ library.<n>Results show that cryptographically secure numerical simulations are possible, but that careful consideration must be given to the computational overhead and the numerical errors introduced by using FHE.
  arXiv  Detail & Related papers  (2024-10-29T07:47:10Z)
• ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment [90.60126724503662]
  ByzSecAgg is an efficient secure aggregation scheme for federated learning. ByzSecAgg is protected against Byzantine attacks and privacy leakages.
  arXiv  Detail & Related papers  (2023-02-20T11:15:18Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Task-Oriented Sensing, Computation, and Communication Integration for Multi-Device Edge AI [108.08079323459822]
  This paper studies a new multi-intelligent edge artificial-latency (AI) system, which jointly exploits the AI model split inference and integrated sensing and communication (ISAC) We measure the inference accuracy by adopting an approximate but tractable metric, namely discriminant gain.
  arXiv  Detail & Related papers  (2022-07-03T06:57:07Z)
• A Learning-Based Approach to Approximate Coded Computation [22.886991943938703]
  We propose AICC, an AI-aided learning approach that is inspired by LCC but also uses deep neural networks (DNNs) It is appropriate for coded computation of more general functions.
  arXiv  Detail & Related papers  (2022-05-19T19:43:53Z)
• Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation [11.951700263976777]
  Generalized Lagrange Coded Computing (GLCC) codes are proposed to provide resiliency against stragglers who do not return results in time. LCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case.
  arXiv  Detail & Related papers  (2022-04-24T02:48:07Z)
• Meta Learning Low Rank Covariance Factors for Energy-Based Deterministic Uncertainty [58.144520501201995]
  Bi-Lipschitz regularization of neural network layers preserve relative distances between data instances in the feature spaces of each layer. With the use of an attentive set encoder, we propose to meta learn either diagonal or diagonal plus low-rank factors to efficiently construct task specific covariance matrices. We also propose an inference procedure which utilizes scaled energy to achieve a final predictive distribution.
  arXiv  Detail & Related papers  (2021-10-12T22:04:19Z)
• List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier [24.75623641870649]
  We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. We show how the master node can perform certain carefully designed extra computations in order to obtain the side information. We further propose folded Lagrange coded computing, referred to as folded LCC or FLCC, to incorporate the developed techniques into a specific coded computing setting.
  arXiv  Detail & Related papers  (2021-01-27T19:17:33Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  We propose Berrut Approximated Coded Computing (BACC) as an alternative approach to deal with stragglers effect. BACC is proven to be numerically stable with low computational complexity. In particular, BACC is used to train a deep neural network on a cluster of servers.
  arXiv  Detail & Related papers  (2020-09-17T14:23:38Z)
• Privacy-Preserving Distributed Learning in the Analog Domain [23.67685616088422]
  We consider the problem of distributed learning over data while keeping it private from the computational servers. We propose a novel algorithm to solve the problem when data is in the analog domain. We show how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers.
  arXiv  Detail & Related papers  (2020-07-17T07:56:39Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  We introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR) CCPR reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery.
  arXiv  Detail & Related papers  (2020-07-04T21:34:49Z)
• Learnable Subspace Clustering [76.2352740039615]
  We develop a learnable subspace clustering paradigm to efficiently solve the large-scale subspace clustering problem. The key idea is to learn a parametric function to partition the high-dimensional subspaces into their underlying low-dimensional subspaces. To the best of our knowledge, this paper is the first work to efficiently cluster millions of data points among the subspace clustering methods.
  arXiv  Detail & Related papers  (2020-04-09T12:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.