Private Multiple Linear Computation: A Flexible Communication-Computation Tradeoff

• URL: http://arxiv.org/abs/2404.09165v1
• Date: Sun, 14 Apr 2024 07:07:08 GMT
• Title: Private Multiple Linear Computation: A Flexible Communication-Computation Tradeoff
• Authors: Jinbao Zhu, Lanping Li, Xiaohu Tang, Ping Deng,
• Abstract summary: We consider the problem of private multiple linear computation (PMLC) over a replicated storage system with colluding and unresponsive constraints. We propose a novel PMLC scheme to establish a flexible tradeoff between communication costs and computational complexities.
• Score: 27.511481199887978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of private multiple linear computation (PMLC) over a replicated storage system with colluding and unresponsive constraints. In this scenario, the user wishes to privately compute $P$ linear combinations of $M$ files from a set of $N$ replicated servers without revealing any information about the coefficients of these linear combinations to any $T$ colluding servers, in the presence of $S$ unresponsive servers that do not provide any information in response to user queries. Our focus is on more general performance metrics where the communication and computational overheads incurred by the user are not neglected. Additionally, the communication and computational overheads for servers are also taken into consideration. Unlike most previous literature that primarily focused on download cost from servers as a performance metric, we propose a novel PMLC scheme to establish a flexible tradeoff between communication costs and computational complexities.

Related papers

• Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
  We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where $N$ agents interact through a communication graph. In each round, each agent $i$ receives a strongly convex hitting cost function $fi_t$ in an online fashion. Our results hold even when the communication graph changes arbitrarily and adaptively over time.
  arXiv  Detail & Related papers  (2024-11-13T05:59:04Z)
• CORAG: A Cost-Constrained Retrieval Optimization System for Retrieval-Augmented Generation [22.918861762038116]
  Large Language Models (LLMs) have demonstrated remarkable generation capabilities but often struggle to access up-to-date information. Retrieval-Augmented Generation (RAG) addresses this issue by incorporating knowledge from external databases.
  arXiv  Detail & Related papers  (2024-11-01T17:11:16Z)
• On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
  We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to $o(K)$, where $K$ is the number of candidate hypothesis spaces.
  arXiv  Detail & Related papers  (2024-04-15T06:32:28Z)
• FSD-Inference: Fully Serverless Distributed Inference with Scalable Cloud Communication [2.1301190271783317]
  We present FSD-Inference, the first fully serverless and highly scalable system for distributed ML inference. We introduce novel fully serverless communication schemes for ML inference workloads, leveraging both cloud-based publish-subscribe/queueing and object storage offerings.
  arXiv  Detail & Related papers  (2024-03-22T13:31:24Z)
• Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach [67.27031215756121]
  Federated learning (FL) is a machine learning paradigm that targets model training without gathering the local data over various data sources. Standard FL, which employs a single server, can only support a limited number of users, leading to degraded learning capability. In this work, we consider a multi-server FL framework, referred to as emphConfederated Learning (CFL) in order to accommodate a larger number of users.
  arXiv  Detail & Related papers  (2024-02-28T03:27:10Z)
• Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users [95.77678166036561]
  We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
  arXiv  Detail & Related papers  (2024-02-26T05:31:14Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Computationally Budgeted Continual Learning: What Does Matter? [128.0827987414154]
  Continual Learning (CL) aims to sequentially train models on streams of incoming data that vary in distribution by preserving previous knowledge while adapting to new data. Current CL literature focuses on restricted access to previously seen data, while imposing no constraints on the computational budget for training. We revisit this problem with a large-scale benchmark and analyze the performance of traditional CL approaches in a compute-constrained setting.
  arXiv  Detail & Related papers  (2023-03-20T14:50:27Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• Single-Server Private Linear Transformation: The Joint Privacy Case [10.072633952908456]
  This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation. The problem includes one or more remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ independent linear combinations of a $D$-subset of messages.
  arXiv  Detail & Related papers  (2021-06-09T17:09:22Z)
• Corella: A Private Multi Server Learning Approach based on Correlated Queries [30.3330177204504]
  We propose $textitCorella$ as an alternative approach to protect the privacy of data. The proposed scheme relies on a cluster of servers, where at most $T in mathbbN$ of them may collude, each running a learning model. The variance of the noise is set to be large enough to make the information leakage to any subset of up to $T$ servers information-theoretically negligible.
  arXiv  Detail & Related papers  (2020-03-26T17:44:00Z)

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.