检索结果-内蒙古大学图书馆

Access-Redundancy Tradeoffs in Quantized Linear computations

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第11期70卷 7723-7739页

作者： Ramkumar, Vinayak Raviv, Netanel Tamo, Itzhak Washington Univ St Louis Dept Comp Sci & Engn St Louis MO 63130 USA Tel Aviv Univ Dept Elect Engn Syst IL-6139001 Tel Aviv Israel

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations that are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as +/- 1), have gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where a smaller access parameter requires more redundancy in the system, and vice versa. In this paper, we study this tradeoff and provide several explicit low-access schemes for $\{\pm 1\}$ quantized linear computations based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art for two-valued linear computations. We further show that the same storage scheme can be used to retrieve any linear combination with two distinct coefficients-regardless of what those coefficients are-with the same access parameter. This universality result is then extended to all possible quantizations with any number of values;while the storage remains identical, the access parameter increases according to a new additive-combinatorics property we call coefficient complexity. We then turn to study the coefficient complexity-we characterize the complexity of small sets of coefficients, provide bounds, and identify coefficient sets having the highest and lowest complexity. Interestingly, arithmetic progressions have the lowest possible complexity, and some geometric progressions have the highest possible complexity, the former being particularly attracti

关键词： Servers Error correction codes Complexity theory Vectors Protocols Encoding Quantization (signal) Access-redundancy distributed systems coded computation covering codes additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

The Capacity of 3 User Linear computation Broadcast

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第6期70卷 4414-4438页

作者： Yao, Yuhang Jafar, Syed A. Univ Calif Irvine Ctr Pervas Commun & Comp CPCC Dept Elect Engn & Comp Sci Irvine CA 92697 USA

The K User Linear computation Broadcast (LCBC) problem is comprised of d dimensional data (from F-q ), that is fully available to a central server, and K users, who require various linear computations of the data, and have prior knowledge of various linear functions of the data as side-information. The optimal broadcast cost is the minimum number of q-ary symbols to be broadcast by the server per computation instance, for every user to retrieve its desired computation. The reciprocal of the optimal broadcast cost is called the capacity. The main contribution of this paper is the exact capacity characterization for the K = 3 user LCBC for all cases, i.e., for arbitrary finite fields F-q , arbitrary data dimension d, and arbitrary linear side-informations and demands at each user. A remarkable aspect of the converse (impossibility result) is that unlike the 2 user LCBC whose capacity was determined previously, the entropic formulation (where the entropies of demands and side-informations are specified, but not their functional forms) is insufficient to obtain a tight converse for the 3 user LCBC. Instead, the converse exploits functional submodularity. Notable aspects of achievability include sufficiency of vector linear coding schemes, subspace decompositions that parallel those found previously by Yao Wang in degrees of freedom (DoF) studies of wireless broadcast networks, and efficiency tradeoffs that lead to a constrained waterfilling solution. Random coding arguments are invoked to resolve compatibility issues that arise as each user has a different view of the subspace decomposition, conditioned on its own side-information.

关键词： Channel coding Indexes Costs Vectors Servers Distributed databases Symbols Capacity broadcast index coding coded computation

来源：评论

学校读者我要写书评

暂无评论

Numerically Stable coded Matrix computations via Circulant and Rotation Matrix Embeddings

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第4期68卷 2684-2703页

作者： Ramamoorthy, Aditya Tang, Li Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Iowa State Univ Ames IA 50011 USA Pinterest Inc San Francisco CA 94107 USA

Polynomial based methods have recently been used in several works for mitigating the effect of stragglers (slow or failed nodes) in distributed matrix computations. For a system with n worker nodes where s can be stragglers, these approaches allow for an optimal recovery threshold, whereby the intended result can be decoded as long as any (n - s) worker nodes complete their tasks. However, they suffer from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices;this condition number grows exponentially in n. We present a novel approach that leverages the properties of circulant permutation matrices and rotation matrices for coded matrix computation. In addition to having an optimal recovery threshold, we demonstrate an upper bound on the worst-case condition number of our recovery matrices which grows as approximate to O(n(s+5.5));in the practical scenario where s is a constant, this grows polynomially in n. Our schemes leverage the well-behaved conditioning of complex Vandermonde matrices with parameters on the complex unit circle, while still working with computation over the reals. Exhaustive experimental results demonstrate that our proposed method has condition numbers that are orders of magnitude lower than prior work.

关键词： coded computation Vandermonde matrix condition number numerical stability

来源：评论

学校读者我要写书评

暂无评论

Straggler-Exploiting Fully Private Distributed Matrix Multiplication With Chebyshev Polynomials

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2023年第3期71卷 1579-1594页

作者： Hong, Sangwoo Yang, Heecheol Yoon, Youngseok Lee, Jungwoo Seoul Natl Univ Dept Elect & Comp Engn Commun & Machine Learning Lab Seoul 08826 South Korea Chungnam Natl Univ Div Comp Convergence Distributed Networks & Comp Lab Daejeon 34134 South Korea

In this paper, we consider coded computation for matrix multiplication tasks in distributed computing to mitigate straggler effects. We assume that the stragglers' computation results can be leveraged at the master by assigning multiple sub- tasks to the workers. We propose a new coded computation scheme, namely Chebyshev coded fully private matrix multiplication (CFP), to preserve the privacy of a master in a scenario where a master wants to obtain a matrix multiplication result from the libraries which are shared by the workers, while concealing both of the two indices of the desired matrices from each worker. The key idea of CFP is to introduce Chebyshev polynomials, which have commutative property, in queries sent to workers to allocate sub-tasks. We also extend CFP to keep the privacy of a master from colluding workers. In conclusion, we show that CFP can preserve the privacy of a master from each worker and efficiently mitigate straggler effects compared to existing schemes.

关键词： Distributed computing the privacy of a master coded computation private information retrieval Chebyshev polynomials

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Group Testing for Byzantine Attack Identification in Distributed Matrix Multiplication

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2022年第3期40卷 1013-1029页

作者： Hong, Sangwoo Yang, Heecheol Lee, Jungwoo Seoul Natl Univ Dept Elect & Comp Engn Commun & Machine Learning Lab Seoul 08826 South Korea Chunguam Natl Univ Div Comp Convergence Distributed Networks & Comp Lab Daejeon 34134 South Korea

coded computing has proved its efficiency in handling a straggler issue in distributed computing framework. It uses error correcting codes to mitigate the effect of the stragglers. However, in a coded distributed computing framework, there may exist Byzantine workers who send the wrong computation results to a master in order to contaminate the overall computation output. Therefore, it is essential to identify Byzantine workers from their computation results in coded computing. In this paper, we consider Byzantine attack identification problem in coded computing for distributed matrix multiplication tasks. We propose a new coding scheme which facilitates the efficient Byzantine attack identification, namely locally testable codes. We also suggest a hierarchical group testing method for Byzantine attack identification. We claim the required number of tests for group testing in our scheme, and show that it requires smaller number of tests than the conventional group testing method for the existing coded computing schemes.

关键词： Testing Codes Distributed computing Task analysis Encoding Decoding Reed-Solomon codes Distributed computing Byzantine attack coded computation matrix multiplication group testing

来源：评论

学校读者我要写书评

暂无评论

Private coded Matrix Multiplication

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2020年 15卷 1434-1443页

作者： Kim, Minchul Yang, Heecheol Lee, Jungwoo Seoul Natl Univ Dept Elect & Comp Engn Commun & Machine Learning Lab Seoul 08826 South Korea Kumoh Natl Inst Technol Sch Elect Engn Gumi 39177 South Korea

In distributed computing system for the master-worker framework, an erasure code is able to mitigate the effects of slow workers, also called stragglers. The distributed computing system combined with coding is referred to as coded computation. For a matrix multiplication, we consider a variation of coded computation that ensures the master's privacy from the workers, which is referred to as private coded matrix multiplication. In the private coded matrix multiplication, the master needs to compute a matrix multiplication on its own matrix and one of the matrices in a library exclusively shared by the external workers. After the master recovers the matrix multiplication through coded matrix multiplication, the workers should not know which matrix in the library was desired by the master, which implies that the master's privacy is ensured. Our problem is a special case of linear private computation, where a linear combination of matrices in the library should be concealed. We propose a private coded matrix multiplication scheme, based on the conventional coded matrix multiplication scheme. In terms of computation time and communication load, we compare our proposed scheme with a conventional robust private information retrieval scheme and private computation schemes.

关键词： Libraries Privacy Encoding Distributed computing Data privacy Artificial intelligence Databases Distributed computing coded computation private information retrieval erasure codes information theory privacy

来源：评论

学校读者我要写书评

暂无评论

Managing Distributed Machine Learning Lifecycle for Healthcare Data in the Cloud

引用

IEEE ACCESS 2024年 12卷 115750-115774页

作者： Zeydan, Engin Arslan, Suayb S. Liyanage, Madhusanka Ctr Tecnol Telecomunicac Catalunya Castelldefels 08860 Barcelona Spain Bogazici Univ Dept Comp Engn TR-34342 Istanbul Turkiye MIT Dept Brain & Cognit Sci Cambridge MA 02139 USA Univ Coll Dublin Sch Comp Sci Dublin D04 V1W8 Ireland

The main objective of this paper is to highlight the research directions and explain the main roles of current Artificial Intelligence (AI)/Machine Learning (ML) frameworks and available cloud infrastructures in building end-to-end ML lifecycle management for healthcare systems and sensitive biomedical data. We identify and explore the versatility of many genuine techniques from distributed computing and current state-of-the-art ML research, such as building cognition-inspired learning pipelines and federated learning (FL) ecosystem. Additionally, we outline the advantages and highlight the main obstacles of our methodology utilizing contemporary distributed secure ML techniques, such as FL, and tools designed for managing data throughout its lifecycle. For a robust system design, we present key architectural decisions essential for optimal healthcare data management, focusing on security, privacy and interoperability. Finally, we discuss ongoing efforts and future research directions to overcome existing challenges and improve the effectiveness of AI/ML applications in the healthcare domain.

关键词： Medical services Data engineering Surveys Deep learning Big Data Artificial intelligence Machine learning Federated learning Cloud computing healthcare biomedicine data management federated learning cloud coded computation distributed systems

来源：评论

学校读者我要写书评

暂无评论

Optimal Incentive and Load Design for Distributed coded Machine Learning

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2021年第7期39卷 2090-2104页

作者： Ding, Ningning Fang, Zhixuan Duan, Lingjie Huang, Jianwei Chinese Univ Hong Kong Dept Informat Engn Hong Kong Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Shanghai Qi Zhi Inst Shanghai 200030 Peoples R China Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore 487372 Singapore Shenzhen Inst Artificial Intelligence & Robot Soc Shenzhen 518129 Peoples R China Chinese Univ Hong Kong Sch Sci & Engn Shenzhen 518172 Peoples R China

A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the multi-dimensional incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Although the exact overall runtime is intractable, we characterize the platform's (asymptotically) optimal load assignment to heterogeneous workers in coded machine learning. When the platform has incomplete information about workers' costs, it is optimal to assign loads only based on workers' computation performances;when the platform further lacks workers' computation performance information, it is optimal to design the loads to be cost-dependent and performance-dependent.

关键词： Distributed machine learning coded computation loads and incentives multi-dimensional incomplete information

来源：评论

学校读者我要写书评

暂无评论

Hierarchical coded Matrix Multiplication in Heterogeneous Multihop Networks

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2022年第6期70卷 3597-3612页

作者： Zhu, Hongtao Chen, Li Zhao, Nan Chen, Yunfei Wang, Weidong Yu, F. Richard Univ Sci & Technol China Dept Elect Engn & Informat Sci Hefei 230027 Peoples R China Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL W Midlands England Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

The performance of distributed computing is restricted by the slowest worker nodes, known as stragglers, in the system. coded computation has emerged as an efficient technique to mitigate the straggler effects in distributed computing. Most existing works only considered the computation straggler for single-hop networks. However, in multi-hop networks, the straggler effects will occur not only on worker nodes but also on relay nodes. In this paper, we consider a heterogeneous multi-hop network. The nodes in the network are heterogeneous, i.e., their computation capacities and transmission capacities are different. We propose a hierarchical coding scheme for such a network. Firstly, we reorganize it into a hierarchical network containing multiple layers. Each layer in the network consists of several groups. Then, a new hierarchical coding scheme is proposed, where coding is applied to each group to mitigate the stragglers. By taking both the computation time and transmission time into consideration, the overall task completion time is derived. To improve the performance of the network, heterogeneous hierarchical coded computation (HHCC) algorithm is proposed to provide an asymptotically optimal task allocation strategy. Compared with existing uniform uncoded, load balanced uncoded, and heterogeneous coded matrix multiplication schemes, HHCC has significant improvement.

关键词： Task analysis Encoding Codes Spread spectrum communication Resource management Distributed computing Runtime coded computation distributed computing hierarchical networks straggler mitigation

来源：评论

学校读者我要写书评

暂无评论

Embedded Index Coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第3期67卷 1461-1477页

作者： Porter, Alexandra Wootters, Mary Stanford Univ Dept Comp Sci Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

Motivated by applications in distributed storage and distributed computation, we introduce embedded index coding (EIC). EIC is a type of distributed index coding in which nodes in a distributed system act as both broadcast senders and receivers of information. We show how linear embedded index coding is related to linear index coding in general, and give characterizations and bounds on the communication costs of optimal embedded index codes. We also define task-based EIC, in which there is only one sender node responsible for transmitting a block to a particular receiving node. Task-based EIC is more computationally tractable and has advantages in applications such as distributed storage, in which senders may complete their broadcasts at different times. Finally, we give heuristic algorithms for approximating optimal linear embedded index codes, and demonstrate empirically that these algorithms perform well.

关键词： Indexes Encoding Task analysis Receivers computational modeling Peer-to-peer computing Approximation algorithms Index coding distributed storage coded computation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：