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

Statistical properties of a class of randomized binary search algorithms

PERFORMANCE EVALUATION 2025年 168卷

作者： Xia, Ye Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

In this paper, we analyze the statistical properties of a randomized binary search algorithm and its variants. These algorithms have applications in caching and load balancing in distributed environments such as peer-to-peer networks, cloud storage, data centers, and content distribution networks. The basic discrete version of the problem is as follows. Suppose there are m servers, numbered 1, 2, ... , m, out of which the first k servers are marked as special, where k is unknown. These k servers may contain a particular file or service that clients want. The objective is to select one of the marked servers uniformly at random. Considering the intended applications, we impose the constraint that there is no central controller to facilitate the selection process. We start with a basic algorithm: In each step, the client requesting the service chooses a number y uniformly at random from 1, 2, ... , x, where x is the number chosen in the previous step, initially set to m in the first step. A query is then sent to server y asking whether y is marked. If the answer is yes, the algorithm returns y;otherwise, the process is repeated with x <- y. In this paper, we primarily consider two batch versions of this algorithm in which multiple numbers are chosen in each step and multiple queries are made in parallel. We derive the mean and variance (exact and/or asymptotic) for the number of search steps in each version of the algorithm, and when possible, we give its distribution. Additionally, we analyze the access pattern of queries across the entire search space.

关键词： Analysis of algorithms parallel and distributed algorithms Randomized binary search algorithm distributed search Load balancing

来源：评论

学校读者我要写书评

暂无评论

Training efficiency optimization algorithm of wireless federated learning based on processor performance and network condition awareness

引用

EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING 2024年第1期2024卷 98页

作者： Pang, Guohao Zhu, Xiaorong Nanjing Univ Posts & Telecommun Coll Portland Nanjing 210003 Peoples R China Nanjing Univ Posts & Telecommun Coll Telecommun & Informat Engn Nanjing 210003 Peoples R China

With the explosive growth of smart mobile devices in wireless networks, the increasing computational power of mobile chips and the growing concern for personal privacy, a decentralized deep learning framework at the mobile terminal layer has emerged called federated learning (FL) to enhance user experience. This paper studies the training efficiency optimization problem of wireless FL that jointly considers processor performance, channel conditions and terminals' power in a non-independent identically distribution (non-IID) scenario. And, the training efficiency optimization problem is mathematically modeled and then decomposed into several sub-problems based on the independence and decoupling of the variables involved. To enhance the training efficiency of wireless FL, a comprehensive scheduling strategy encompassing computational and communication aspects is proposed. Simulation results show that the proposed scheduling strategy for wireless FL achieves superior learning performance with reduced training latency.

关键词： Federated learning Wireless communication Scheduling policies parallel and distributed algorithms Resource allocation

来源：评论

学校读者我要写书评

暂无评论

Robust Federated Learning With Noisy Labeled Data Through Loss Function Correction

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2023年第3期10卷 1501-1511页

作者： Chen, Li Ang, Fan Chen, Yunfei Wang, Weidong Univ Sci & Technol China Dept Elect Engn & Informat Sci Hefei 230027 Anhui Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL England

Federated learning (FL) is a communication efficient machine learning paradigm to leverage distributed data at the network edge. Nevertheless, FL usually fails to train a high-quality model from the networks, where the edge nodes collect noisy labeled data. To tackle this challenge, this paper focuses on developing an innovative robust FL. We consider two kinds of networks with different data distribution. Firstly, we design a reweighted FL under a full-data network, where all edge nodes are equipped with both numerous noisy labeled dataset and small clean dataset. The key idea is that edge devices learn to assign the local weights of loss functions in noisy labeled dataset, and cooperate with central server to update global weights. Secondly, we consider a part-data network where some edge nodes exclude clean dataset, and can not compute the weights locally. The broadcasting of the global weights is added to help those edge nodes without clean dataset to reweight their noisy loss functions. Both designs have a convergence rate of O(1=T-2). Simulation results illustrate that the both proposed training processes improve the prediction accuracy due to the proper weights assignments of noisy loss function.

关键词： Noise measurement Training Servers Data models Federated learning Loss measurement Convergence distributed networks federated learning label noise machine learning non-convex optimization parallel and distributed algorithms robust design

来源：评论

学校读者我要写书评

暂无评论

Efficiency Optimization Method of Wireless Federated Learning Considering Computational Capability and Channel State 23

Efficiency Optimization Method of Wireless Federated Learnin...

引用

23rd IEEE International Conference on Communication Technology, ICCT 2023

作者： Pang, Guohao Li, Fengguo Zhu, Xiaorong College of Portland Nanjing University of Posts and Telecommunications Nanjing China China Mobile Company Shandong China College of Telecommunication and Information Engineering Nanjing University of Posts and Telecommunications Nanjing China

ISBN: (纸本)9798350325959

Due to the explosive growth in the variety of smart mobile terminals in wireless networks, the increasing computing capability of mobile chips, and the public's growing concern for personal privacy, it is a better solution to decentralize the deep learning framework for mobile services that can enhance user experience to the mobile terminal layer. In this paper, we study the joint optimization problem of processor performance and channel state in a non-independent distribution scenario (non-IID), while considering the user's device experience problem to improve the battery efficiency of the terminal device (TD) as much as possible and maximize the efficiency of the federated learning (FL) system while ensuring low local upload latency. To improve the efficiency of wireless federated learning (WFL), we propose a specific and complete scheduling strategy involving both computational and communication aspects. First, we model the total problem and decouple it into several sub-problems to solve according to the nature of the variables. Then, we propose a Reduced Load algorithm (RL) to solve the task allocation problem and a dynamic bandwidth allocation strategy to solve the bandwidth allocation problem. Simulation results show that the proposed scheduling strategy can achieve higher learning performance with lower training latency and is capable of adaptively adjusting the bandwidth allocation to decrease upload latency. © 2023 IEEE.

关键词： Federated learning parallel and distributed algorithms resource allocation scheduling policies wireless communication

来源：评论

学校读者我要写书评

暂无评论

Iterated Vector Fields and Conservatism, with Applications to Federated Learning 33

Iterated Vector Fields and Conservatism, with Applications t...

引用

33rd International Conference on Algorithmic Learning Theory (ALT)

作者： Charles, Zachary Rush, Keith Google Res Mountain View CA 94043 USA

We study whether iterated vector fields (vector fields composed with themselves) are conservative. We give explicit examples of vector fields for which this self-composition preserves conservatism. Notably, this includes gradient vector fields of loss functions associated to some generalized linear models. In the context of federated learning, we show that when clients have loss functions whose gradient satisfies this condition, federated averaging is equivalent to gradient descent on a surrogate loss function. We leverage this to derive novel convergence results for federated learning. By contrast, we demonstrate that when the client losses violate this property, federated averaging can yield behavior which is fundamentally distinct from centralized optimization. Finally, we discuss theoretical and practical questions our analytical framework raises for federated learning.

关键词： Optimization federated learning dynamical systems parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A data structure perspective to the RDD-based Apriori algorithm on Spark

引用

International Journal of Information Technology (Singapore) 2022年第3期14卷 1585-1594页

作者： Singh, Pankaj Singh, Sudhakar Mishra, P.K. Garg, Rakhi Department of Computer Science Banaras Hindu University Varanasi India Department of Electronics and Communication University of Allahabad Prayagraj India Mahila Maha Vidyalaya Banaras Hindu University Varanasi India

During the recent years, a number of efficient and scalable frequent itemset mining algorithms for big data analytics have been proposed by many researchers. Initially, MapReduce-based frequent itemset mining algorithms on Hadoop cluster were proposed. Although, Hadoop has been developed as a cluster computing system for handling and processing big data, but the performance of Hadoop does not meet the expectation for the iterative algorithms of data mining, due to its high I/O, and writing and then reading intermediate results in the disk. Consequently, Spark has been developed as another cluster computing infrastructure which is much faster than Hadoop due to its in-memory computation. It is highly suitable for iterative algorithms and supports batch, interactive, iterative, and stream processing of data. Many frequent itemset mining algorithms have been re-designed on the Spark, and most of them are Apriori-based. All these Spark-based Apriori algorithms use Hash Tree as the underlying data structure. This paper investigates the efficiency of various data structures for the Spark-based Apriori. Although, the data structure perspective has been investigated previously, but for the MapReduce-based Apriori, and it must be re-investigated in the distributed computing environment of Spark. The considered underlying data structures are Hash Tree, Trie, and Hash Table Trie. The experimental results on the benchmark datasets show that the performance of Spark-based Apriori with Trie and Hash Table Trie are almost similar but both perform many times better than Hash Tree in the distributed computing environment of Spark. © 2019, Bharati Vidyapeeth's Institute of Computer Applications and Management.

关键词： Apriori Big data analytics Frequent itemset mining parallel and distributed algorithms RDD Spark

来源：评论

学校读者我要写书评

暂无评论

Practice and Experience in using parallel and Scalable Machine Learning with Heterogenous Modular Supercomputing Architectures

Practice and Experience in using Parallel and Scalable Machi...

引用

35th IEEE International parallel and distributed Processing Symposium (IPDPS)

作者： Riedel, Morris Sedona, Rocco Barakat, Chadi Einarsson, Petur Hassanian, Reza Cavallaro, Gabriele Book, Matthias Neukirchen, Helmut Lintermann, Andreas Univ Iceland Dept Comp Sci Reykjavik Iceland Forschungszentrum Julich Julich Supercomp Ctr Julich Germany

ISBN: (纸本)9781665435772

We observe a continuously increased use of Deep Learning (DL) as a specific type of Machine Learning (ML) for data-intensive problems (i.e., 'big data') that requires powerful computing resources with equally increasing performance. Consequently, innovative heterogeneous High-Performance Computing (HPC) systems based on multi-core CPUs and many-core GPUs require an architectural design that addresses end user communities' requirements that take advantage of ML and DL. Still the workloads of end user communities of the simulation sciences (e.g., using numerical methods based on known physical laws) needs to be equally supported in those architectures. This paper offers insights into the Modular Supercomputer Architecture (MSA) developed in the Dynamic Exascale Entry Platform (DEEP) series of projects to address the requirements of both simulation sciences and data-intensive sciences such as High Performance Data Analytics (HPDA). It shares insights into implementing the MSA in the Julich Supercomputing Centre (JSC) hosting Europe No. 1 Supercomputer Julich Wizard for European Leadership Science (JUWELS). We augment the technical findings with experience and lessons learned from two application communities case studies (i.e., remote sensing and health sciences) using the MSA with JUWELS and the DEEP systems in practice. Thus, the paper provides details into specific MSA design elements that enable significant performance improvements of ML and DL algorithms. While this paper focuses on MSA-based HPC systems and application experience, we are not losing sight of advances in Cloud Computing (CC) and Quantum Computing (QC) relevant for ML and DL.

关键词： High performance computing cloud computing quantum computing machine learning deep learning parallel and distributed algorithms remote sensing health sciences modular supercomputer architecture

来源：评论

学校读者我要写书评

暂无评论

PRACTICE AND EXPERIENCE IN USING parallel AND SCALABLE MACHINE LEARNING IN REMOTE SENSING FROM HPC OVER CLOUD TO QUANTUM COMPUTING

PRACTICE AND EXPERIENCE IN USING PARALLEL AND SCALABLE MACHI...

引用

IEEE International Geoscience and Remote Sensing Symposium (IGARSS)

作者： Rieder, Morris Cavallaro, Gabriele Benediktsson, Jon Atli Univ Iceland Sch Engn & Nat Sci Reykjavik Iceland Forschungszentrum Julich Julich Supercomp Ctr Julich Germany

ISBN: (纸本)9781665403696

Using computationally efficient techniques for transforming the massive amount of Remote Sensing (RS) data into scientific understanding is critical for Earth science. The utilization of efficient techniques through innovative computing systems in RS applications has become more widespread in recent years. The continuously increased use of Deep Learning (DL) as a specific type of Machine Learning (ML) for data-intensive problems (i.e., 'big data') requires powerful computing resources with equally increasing performance. This paper reviews recent advances in High-Performance Computing (HPC), Cloud Computing (CC), and Quantum Computing (QC) applied to RS problems. It thus represents a snapshot of the state-of-the-art in ML in the context of the most recent developments in those computing areas, including our lessons learned over the last years. Our paper also includes some recent challenges and good experiences by using Europeans fastest supercomputer for hyper-spectral and multi-spectral image analysis with state-of-the-art data analysis tools. It offers a thoughtful perspective of the potential and emerging challenges of applying innovative computing paradigms to RS problems.

关键词： High performance computing cloud computing quantum computing machine learning deep learning parallel and distributed algorithms remote sensing

来源：评论

学校读者我要写书评

暂无评论

Novel Control Approaches for Demand Response With Real-Time Pricing Using parallel and distributed Consensus-Based ADMM

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2019年第10期66卷 7935-7945页

作者： Dinh Hoa Nguyen Azuma, Shun-Ichi Sugie, Toshiharu Kyushu Univ Int Inst Carbon Neutral Energy Res Fukuoka Fukuoka 8190395 Japan Kyushu Univ Inst Math Ind Fukuoka Fukuoka 8190395 Japan Nagoya Univ Grad Sch Engn Dept Mech Syst Engn Nagoya Aichi 4648603 Japan Kyoto Univ Grad Sch Informat Dept Syst Sci Kyoto 6068501 Japan

This paper studies the automated demand response (DR) problem in smart grids equipped with information and communication technology networks, where power generating and consuming units can exchange information as a multiagent system (MAS), and a real-time pricing (RTP) scheme is proposed. When the communication graph among agents is connected, a novel parallel and distributed consensus-based algorithm is proposed to derive an RTP scheme to facilitate DR, and when communication uncertainties exist, a robust consensus algorithm is proposed to cease the effect of uncertainties. Next, this paper proposes a novel control mechanism to tackle the problem of disconnected communication among agents, e.g., under cyber-attacks, by employing the so-called mixed communication-broadcast control architecture where the underlying ideas are twofold. First, each area in the grid associated with a connected subgraph is controlled by a MAS to guarantee the power balance and to reach consensus on the local electric price for that area. Second, a supervisory unit observes those local electric prices to calculate the global electric price for the whole grid and then broadcasts to all units so that they can properly adjust their output powers. Simulations are carried out on the IEEE 39-bus system to validate the proposed control mechanisms.

关键词： Alternating direction method of multipliers (ADMM) communication failure demand response (DR) mixed communication-broadcast multiagent system (MAS) parallel and distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling Policies for Federated Learning in Wireless Networks

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2020年第1期68卷 317-333页

作者： Yang, Howard H. Liu, Zuozhu Quek, Tony Q. S. Poor, H. Vincent Singapore Univ Technol & Design Informat Syst Technol & Design Pillar Singapore 487372 Singapore Natl Univ Singapore Dept Stat & Appl Probabil Singapore 119077 Singapore Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

Motivated by the increasing computational capacity of wireless user equipments (UEs), e.g., smart phones, tablets, or vehicles, as well as the increasing concerns about sharing private data, a new machine learning model has emerged, namely federated learning (FL), that allows a decoupling of data acquisition and computation at the central unit. Unlike centralized learning taking place in a data center, FL usually operates in a wireless edge network where the communication medium is resource-constrained and unreliable. Due to limited bandwidth, only a portion of UEs can be scheduled for updates at each iteration. Due to the shared nature of the wireless medium, transmissions are subjected to interference and are not guaranteed. The performance of FL system in such a setting is not well understood. In this paper, an analytical model is developed to characterize the performance of FL in wireless networks. Particularly, tractable expressions are derived for the convergence rate of FL in a wireless setting, accounting for effects from both scheduling schemes and inter-cell interference. Using the developed analysis, the effectiveness of three different scheduling policies, i.e., random scheduling (RS), round robin (RR), and proportional fair (PF), are compared in terms of FL convergence rate. It is shown that running FL with PF outperforms RS and RR if the network is operating under a high signal-to-interference-plus-noise ratio (SINR) threshold, while RR is more preferable when the SINR threshold is low. Moreover, the FL convergence rate decreases rapidly as the SINR threshold increases, thus confirming the importance of compression and quantization of the update parameters. The analysis also reveals a trade-off between the number of scheduled UEs and subchannel bandwidth under a fixed amount of available spectrum.

关键词： Convergence Data models Signal to noise ratio Interference Computational modeling Training Wireless networks Federated learning scheduling policies parallel and distributed algorithms stochastic geometry convergence analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：