Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation

• URL: http://arxiv.org/abs/2204.11168v3
• Date: Wed, 06 Nov 2024 01:50:26 GMT
• Title: Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation
• Authors: Jinbao Zhu, Hengxuan Tang, Songze Li, Yijia Chang,
• Abstract summary: 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.
• Score: 11.951700263976777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset containing multiple inputs, on a distributed computing system with a master node and multiple worker nodes. Generalized Lagrange Coded Computing (GLCC) codes are proposed to simultaneously provide resiliency against stragglers who do not return computation results in time, security against adversarial workers who deliberately modify results for their benefit, and information-theoretic privacy of the dataset amidst possible collusion of workers. GLCC codes are constructed by first partitioning the dataset into multiple groups, then encoding the dataset using carefully designed interpolating polynomials, and sharing multiple encoded data points to each worker, such that interference computation results across groups can be eliminated at the master. Particularly, GLCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case, and exhibit a more flexible tradeoff between communication and computation overheads in optimizing system efficiency. Furthermore, we apply GLCC to distributed training of machine learning models, and demonstrate that GLCC codes achieve a speedup of up to $2.5\text{--}3.9\times$ over LCC codes in training time, across experiments for training image classifiers on different datasets, model architectures, and straggler patterns.

Related papers

• Robust Categorical Data Clustering Guided by Multi-Granular Competitive Learning [47.32771052588132]
  The nested granular cluster effect is prevalent in the implicit discrete distance space of categorical data.<n>We propose a Multi-Granular Competitiveization Learning algorithm to allow potential clusters to interactively tune themselves.<n>It is shown that the proposed MGCPL-guided Categorical Data Clustering approach is competent in exploring the nested distribution of multi-granular clusters.
  arXiv  Detail & Related papers  (2026-01-23T06:33:08Z)
• TFHE-Coder: Evaluating LLM-agentic Fully Homomorphic Encryption Code Generation [10.597643264309415]
  Homomorphic Encryption over the torus (TFHE) enables encrypted computation on data without decryption. Despite its potential in privacy preserving machine learning, secure multi party computation, private blockchain transactions, and secure medical diagnostics, its adoption remains limited due to cryptographic complexity and usability challenges. This work establishes the first benchmark for TFHE code generation, demonstrating how LLMs, when augmented with domain-specific feedback, can bridge the expertise gap in FHE code generation.
  arXiv  Detail & Related papers  (2025-03-15T17:57:44Z)
• Autoencoded UMAP-Enhanced Clustering for Unsupervised Learning [49.1574468325115]
  We propose a novel approach to unsupervised learning by constructing a non-linear embedding of the data into a low-dimensional space followed by any conventional clustering algorithm.<n>The embedding promotes clusterability of the data and is comprised of two mappings: the encoder of an autoencoder neural network and the output of UMAP algorithm.<n>When applied to MNIST data, AUEC significantly outperforms the state-of-the-art techniques in terms of clustering accuracy.
  arXiv  Detail & Related papers  (2025-01-13T22:30:38Z)
• OpenCoder: The Open Cookbook for Top-Tier Code Large Language Models [70.72097493954067]
  Large language models (LLMs) for code have become indispensable in various domains, including code generation, reasoning tasks and agent systems. While open-access code LLMs are increasingly approaching the performance levels of proprietary models, high-quality code LLMs remain limited. We introduce OpenCoder, a top-tier code LLM that not only achieves performance comparable to leading models but also serves as an "open cookbook" for the research community.
  arXiv  Detail & Related papers  (2024-11-07T17:47:25Z)
• AlchemistCoder: Harmonizing and Eliciting Code Capability by Hindsight Tuning on Multi-source Data [64.69872638349922]
  We present AlchemistCoder, a series of Code LLMs with enhanced code generation and generalization capabilities fine-tuned on multi-source data. We propose incorporating the data construction process into the fine-tuning data as code comprehension tasks, including instruction evolution, data filtering, and code review.
  arXiv  Detail & Related papers  (2024-05-29T16:57:33Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• PEOPL: Characterizing Privately Encoded Open Datasets with Public Labels [59.66777287810985]
  We introduce information-theoretic scores for privacy and utility, which quantify the average performance of an unfaithful user. We then theoretically characterize primitives in building families of encoding schemes that motivate the use of random deep neural networks.
  arXiv  Detail & Related papers  (2023-03-31T18:03:53Z)
• Graph-Collaborated Auto-Encoder Hashing for Multi-view Binary Clustering [11.082316688429641]
  We propose a hashing algorithm based on auto-encoders for multi-view binary clustering. Specifically, we propose a multi-view affinity graphs learning model with low-rank constraint, which can mine the underlying geometric information from multi-view data. We also design an encoder-decoder paradigm to collaborate the multiple affinity graphs, which can learn a unified binary code effectively.
  arXiv  Detail & Related papers  (2023-01-06T12:43:13Z)
• 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)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is $straggling$ workers. Coded distributed techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. We propose a novel dynamic GC scheme, which assigns redundant data to workers to acquire the flexibility to choose from among a set of possible codes depending on the past straggling behavior.
  arXiv  Detail & Related papers  (2021-03-01T18:51:29Z)
• 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)
• Analog Lagrange Coded Computing [23.67685616088422]
  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)
  arXiv  Detail & Related papers  (2020-08-19T17:47:37Z)
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off [56.08535873173518]
  Straggling workers can be tolerated by assigning redundant computations and coding across data and computations. In most existing schemes, each non-straggling worker transmits one message per iteration to the parameter server (PS) after completing all its computations. Imposing such a limitation results in two main drawbacks; over-computation due to inaccurate prediction of the straggling behaviour, and under-utilization due to treating workers as straggler/non-straggler.
  arXiv  Detail & Related papers  (2020-04-10T08:39:36Z)

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.