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

32nd Conference on Learning Theory (COLT) part of the ACM Federated Computing Research Conference

作者： Diakonikolas, Jelena Guzman, Cristobal Univ Calif Berkeley Berkeley CA 94720 USA Pontificia Univ Catolica Chile Millennium Nucleus Ctr Discovery Struct Complex D Santiago Chile

We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and nonsmooth, weakly-smooth, or smooth objective functions. In particular, we show that it is not possible to obtain a polylogarithmic (in the sequential complexity of the problem) number of parallel rounds with a polynomial (in the dimension) number of queries per round. In the majority of these settings and when the dimension of the space is polynomial in the inverse target accuracy, our lower bounds match the oracle complexity of sequential convex optimization, up to at most a logarithmic factor in the dimension, which makes them (nearly) tight. Prior to our work, lower bounds for parallel convex optimization algorithms were only known in a small fraction of the settings considered in this paper, mainly applying to Euclidean (l(2)) and l(infinity) spaces. Our work provides a more general and streamlined approach for proving lower bounds in the setting of parallel convex optimization.

关键词： Lower bounds convex optimization parallel algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized Constraints Consensus for Distributed Robust Linear Programming

引用

IFAC-PapersOnLine 2017年第1期50卷 4973-4978页

作者： Chamanbaz M. Notarstefano G. Bouffanais R. Arak University of Technology Arak Iran Singapore University of Technology and Design Singapore Department of Engineering Università del Salento Lecce Italy

In this paper we consider a network of processors aiming at cooperatively solving linear programming problems subject to uncertainty. Each node only knows a common cost function and its local uncertain constraint set. We propose a randomized, distributed algorithm working under time-varying, asynchronous and directed communication topology. The algorithm is based on a local computation and communication paradigm. At each communication round, nodes perform two updates: (i) a verification in which they check—in a randomized setup—the robust feasibility (and hence optimality) of the candidate optimal point, and (ii) an optimization step in which they exchange their candidate bases (minimal sets of active constraints) with neighbors and locally solve an optimization problem whose constraint set includes: a sampled constraint violating the candidate optimal point (if it exists), agent's current basis and the collection of neighbor's basis. As main result, we show that if a processor successfully performs the verification step for a sufficient number of communication rounds, it can stop the algorithm since a consensus has been reached. The common solution is—with high confidence—feasible (and hence optimal) for the entire set of uncertainty except a subset having arbitrary small probability measure. We show the effectiveness of the proposed distributed algorithm on a multi-core platform in which the nodes communicate asynchronously. © 2017

关键词： control of large-scale network systems Distributed Optimization Large scale optimization problems Optimization randomized algorithms Robust Linear Programming

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for randomized Load Balancing on Arbitrary Network Topologies

Tight Bounds for Randomized Load Balancing on Arbitrary Netw...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Sauerwald, Thomas Sun, He Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781467343831

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case. We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no difference between the discrete and continuous case. For instance, for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs.

关键词： randomized algorithms parallel and distributed algorithms graph expansion Markov chains load balancing

来源：评论

学校读者我要写书评

暂无评论

Non-independent randomized rounding and coloring

Non-independent randomized rounding and coloring

引用

Workshop on Efficient algorithms (WEA)

作者： Doerr, B Univ Kiel Math Seminar D-24098 Kiel Germany

We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well. We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2(d/2) decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to O(root n) (from n). The latter also speeds up the corresponding derandomization by a factor of root n. (c) 2005 Elsevier B.V. All rights reserved.

关键词： randomized algorithms hypergraph coloring discrepancy randomized rounding integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Mixed Precision randomized Low-Rank Approximation with GPU Tensor Cores 30th

Mixed Precision Randomized Low-Rank Approximation with GPU T...

引用

30th European Conference on Parallel and Distributed Processing (Euro-Par)

作者： Baboulin, Marc Donfack, Simplice Kaya, Oguz Mary, Theo Robeyns, Matthieu Univ Paris Saclay CNRS ENS Paris Saclay LMF Gif Sur Yvette France Univ Paris Saclay UVSQ INRIA CNRSCEAMaison Simulat Gif Sur Yvette France Univ Paris Saclay CNRS LISN Orsay France Sorbonne Univ CNRS LIP6 Paris France Inst Dev & Ressources Informat Sci Rue John von Neumann F-91403 Orsay France

ISBN: (纸本)9783031695827;9783031695834

randomized projection methods have been shown to be very efficient at computing low-rank approximations (LRA) of large matrices. In this work, we investigate the design and development of such methods capable of exploiting recent mixed precision accelerators like GPUs equipped with tensor core units. We combine three new ideas to exploit mixed precision arithmetic in randomized LRA. The first is to perform the matrix multiplication with mixed precision fp16/fp32 tensor cores. The second is to use CholeskyQR orthonormalization, which is much faster on GPUs, while mitigating its numerical instability by using fp64 arithmetic. The third is to use a recently proposed iterative refinement method for LRA to improve the accuracy of the LRA by calling it twice. We implement the proposed approach on various GPU architectures and analyze its performance and accuracy. We compare with a standard randomized LRA entirely in fp32 arithmetic, which achieves an average accuracy of order 10(-4). Our results show that our approach without refinement is up to 8x faster, with an average accuracy of order 10(-2), which may be acceptable for some applications. Otherwise, we show that using refinement significantly improves the accuracy to an average of order 10(-5), while remaining up to 2.2x faster than the standard fp32 randomized LRA. This work illustrates the convergence of approximate computing techniques by combining low-rank approximations, randomization, mixed precision arithmetic, and GPU acceleration.

关键词： mixed precision algorithms randomized algorithms low-rank approximations GPU computing tensor cores

来源：评论

学校读者我要写书评

暂无评论

randomized Constraints Consensus for Distributed Robust Linear Programming

Randomized Constraints Consensus for Distributed Robust Line...

引用

20th World Congress of the International-Federation-of-Automatic-Control (IFAC)

作者： Chamanbaz, Mohammadreza Notarstefano, Giuseppe Bouffanais, Roland Arak Univ Technol Arak Iran Univ Salento Dept Engn Lecce Italy Singapore Univ Technol & Design Singapore Singapore

In this paper we consider a network of processors aiming at cooperatively solving linear programming problems subject to uncertainty. Each node only knows a common cost function and its local uncertain constraint set. We propose a randomized, distributed algorithm working under time-varying, asynchronous and directed communication topology. The algorithm is based on a local computation and communication paradigm. At each communication round, nodes perform two updates: (i) a verification in which they check in a randomized setup the robust feasibility (and hence optimality) of the candidate optimal point, and (ii) an optimization step in which they exchange their candidate bases (minimal sets of active constraints) with neighbors and locally solve an optimization problem whose constraint set includes: a sampled constraint violating the candidate optimal point (if it exists), agent's current basis and the collection of neighbor's basis. As main result, we show that if a processor successfully performs the verification step for a sufficient number of communication rounds, it can stop the algorithm since a consensus has been reached. The common solution is with high confidence feasible (and hence optimal) for the entire set of uncertainty except a subset having arbitrary small probability measure. We show the effectiveness of the proposed distributed algorithm on a multi-core platform in which the nodes communicate asynchronously. (C) 2017, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

关键词： Distributed Optimization randomized algorithms Robust Linear Programming Optimization and control of large-scale network systems Large scale optimization problems

来源：评论

学校读者我要写书评

暂无评论

randomized Consensus in Expected O(n log n) Individual Work

Randomized Consensus in Expected O(n log n) Individual Work

引用

27th Annual ACM Symposium on Principles of Distributed Computing

作者： Aspnes, James Attiya, Hagit Censor, Keren Yale Univ Dept Comp Sci POB 2158 New Haven CT 06520 USA Dept Comp Sci Techn Haifa Israel

ISBN: (纸本)9781595939890

This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary. The fastest previously known algorithm requires a process to perform an expected O(n log(2) n) read and write operations in the worst case. In our algorithm, each process executes at most an expected O(n log n) read and write operations. It, is shown that shared-coin algorithms can be combined together to yield an algorithm with O(n log n) individual work and O(n(2)) total work.

关键词： distributed computing shared memory randomized algorithms consensus

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for robust stabilization via static-output-feedbacks

A randomized algorithm for robust stabilization via static-o...

引用

IEEE International Conference on the Science of Electrical Engineering in Israel (ICSEE)

作者： Peretz, Yossi Merzbach, Oria Moyal, Simon Jerusalem Coll Technol Lev Acad Ctr Comp Sci Dept Jerusalem Israel

ISBN: (纸本)9781538663783

A new theorem regarding the robust stability hypercube-tolerance with respect to the specific system defined by the middle-point of a hypercube and a given stabilizing static-output-feedback for it, is proved. Based on the theorem and using the Ray-Shooting Method, a randomized algorithm for the problem of robust stabilization via static-output feedback is suggested. The suggested algorithm has several advantages over existing LMI based algorithms and can easily incorporate structural and other constraints on the controller.

关键词： Continuous-Time Linear Systems State-Space Representation Feedback Stability Robust Stability Simultaneous Stabilization Static Output Feedbacks randomized algorithms Approximation algorithms Convergence In Probability

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for randomized Consensus under a Weak Adversary

Lower Bounds for Randomized Consensus under a Weak Adversary

引用

27th Annual ACM Symposium on Principles of Distributed Computing

作者： Attiya, Hagit Censor, Keren Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781595939890

This paper studies the inherent trade-off between termination probability and total step complexity of randomized Consensus algorithms. It shows that for every integer k the probability that an f-resilient randomized consensus algorithm of n processes does not terminate with agreement within k(n - f) steps is at least 1/c(k), for settle constant c. The lower bound holds for asynchronous systems, where processes communicate either by message passing or through shared memory, under a very weak adversary that determines the schedule in advance, without observing the algorithm's act ions. This complement's algorithms of Kapron et al. [22], for message-passing systems, and of Aumann et al. [6,7], for shared-memory systems.

关键词： distributed computing shared memory message passing lower bound randomized algorithms consensus

来源：评论

学校读者我要写书评

暂无评论

OnlineMin: A Fast Strongly Competitive randomized Paging Algorithm

OnlineMin: A Fast Strongly Competitive Randomized Paging Alg...

引用

9th International Workshop on Approximation and Online algorithms (WAOA 2011)

作者： Brodal, Gerth Stolting Moruz, Gabriel Negoescu, Andrei Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8200 Aarhus N Denmark Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

ISBN: (纸本)9783642291159

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

关键词： On-line algorithms Competitive analysis Paging randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：