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

41st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Lafond, Jean Wai, Hoi-To Moulines, Eric Telecom ParisTech CNRS LTCI Inst Mines Telecom Paris France Arizona State Univ Sch ECEE Tempe AZ 85287 USA Ecole Polytech CMAP Palaiseau France

ISBN: (纸本)9781479999880

We propose distributed algorithms for high-dimensional sparse optimization. In many applications, the parameter is sparse but high-dimensional. This is pathological for existing distributed algorithms as the latter require an information exchange stage involving transmission of the full parameter, which may not be sparse during the intermediate steps of optimization. The novelty of this work is to develop communication efficient algorithms using the stochastic Frank-Wolfe (sFW) algorithm, where the gradient computation is inexact but controllable. For star network topology, we propose an algorithm with low communication cost and establishes its convergence. The proposed algorithm is then extended to perform decentralized optimization on general network topology. Numerical experiments are conducted to verify our findings.

关键词： decentralized algorithm sparse optimization large-scale optimization communication efficient algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel Weighted Random Sampling

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第3期48卷 1-40页

作者： Huebschle-Schneider, Lorenz Sanders, Peter Karlsruhe Inst Technol Kaiserstr 12 D-76131 Karlsruhe Germany

Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps. We give efficient, fast, and practicable parallel and distributed algorithms for building data structures that support sampling single items (alias tables, compressed data structures). This also yields a simplified and more space-efficient sequential algorithm for alias table construction. Our approaches to sampling k out of n items with/without replacement and to subset (Poisson) sampling are output-sensitive, i.e., the sampling algorithms use work linear in the number of different samples. This is also interesting in the sequential case. Weighted random permutation can be done by sorting appropriate random deviates. We show that this is possible with linear work. Finally, we give a communication-efficient, highly scalable approach to (weighted and unweighted) reservoir sampling. This algorithm is based on a fully distributed model of streaming algorithms that might be of independent interest. Experiments for alias tables and sampling with replacement show near linear speedups using up to 158 threads of shared-memory machines. An experimental evaluation of distributed weighted reservoir sampling on up to 5,120 cores also shows good speedups.

关键词： Categorical distribution multinoulli distribution parallel algorithm alias method PRAM communication efficient algorithm Poisson sampling reservoir sampling

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms Reconsidered 32

Parallel Algorithms Reconsidered

引用

32nd International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Sanders, Peter Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9783939897781

Parallel algorithms have been a subject of intensive algorithmic research in the 1980s. This research almost died out in the mid 1990s. In this paper we argue that it is high time to reconsider this subject since a lot of things have changed. First and foremost, parallel processing has moved from a niche application to something mandatory for any performance critical computer applications. We will also point out that even very fundamental results can still be obtained. We give examples and also formulate some open problems.

关键词： parallel algorithm algorithm engineering communication efficient algorithm polylogarithmic time algorithm parallel machine model

来源：评论

学校读者我要写书评

暂无评论

Parallel Weighted Random Sampling 27

Parallel Weighted Random Sampling

引用

27th Annual European Symposium on algorithms (ESA)

作者： Huebschle-Schneider, Lorenz Sanders, Peter Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9783959771245

Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps both for shared-memory and distributed-memory machines. We give efficient, fast, and practicable algorithms for sampling single items, k items with/without replacement, permutations, subsets, and reservoirs. We also give improved sequential algorithms for alias table construction and for sampling with replacement. Experiments on shared-memory parallel machines with up to 158 threads show near linear speedups both for construction and queries.

关键词： categorical distribution multinoulli distribution parallel algorithm alias method PRAM communication efficient algorithm subset sampling reservoir sampling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：