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

Distributed Matrix Completion and Robust Factorization

JOURNAL OF MACHINE LEARNING RESEARCH 2015年第1期16卷 913-960页

作者： Mackey, Lester Talwalkar, Ameet Jordan, Michael I. Stanford Univ Dept Stat 390 Serra Mall Stanford CA 94305 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.

关键词： collaborative filtering divide-and-conquer matrix completion matrix factorization parallel and distributed algorithms randomized algorithms robust matrix factorization video surveillance

来源：评论

学校读者我要写书评

暂无评论

An Improved Distributed Algorithm for Maximal Independent Set 16

An Improved Distributed Algorithm for Maximal Independent Se...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Mohsen Ghaffari MIT

ISBN: (纸本)9781510819672

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity. Classical MIS algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after O(log n) rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node v terminates after O(log deg(v) + log 1/ε) rounds, with probability at least 1 - ε. The degree-dependency in this bound is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12; arXiv: 1202.1983v3], we get an MIS algorithm with a high probability global complexity of O(logΔ) + 2~(O({the square root of}(log log n))), where Δ denotes the maximum degree. This improves over the O(log~2 Δ) + 2_(O({the square root of}(log log n))) result of Barenboim et al., and gets close to the Ω(min{log Δ, {the square root of}(log n)}) lower bound of Kuhn et al. Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation algorithms (LCA) model, and a faster distributed algorithm for the Lovasz Local Lemma.

关键词： Management Information Systems distributed algorithms randomized algorithms Graph algorithms Square root algorithms Probability Complexity

来源：评论

学校读者我要写书评

暂无评论

Online Degree-Bounded Steiner Network Design 16

Online Degree-Bounded Steiner Network Design

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Sina Dehghani Soheil Ehsani MohammadTaghi Hajiaghayi Vahid Liaghat University of Maryland Stanford University

ISBN: (纸本)9781510819672

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem - which asks for a subgraph with minimum degree that connects a given set of vertices - is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance. The standard techniques for solving degree bounded problems often fall in the category of iterative and dependent rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree bounded problems has remained widely open. In this paper, we design an intuitive greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems. Furer and Raghavachari resolved the offline variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the family of degree-bounded network design problems has been extensively studied in the litera

关键词： network design problem Steiner trees Steiner network rounding on-line model OFF LINE randomized algorithms vertex head paper family

来源：评论

学校读者我要写书评

暂无评论

Node sampling using Random Centrifugal Walks

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2015年第Nov.期11卷 34-45页

作者： Sevilla, Andres Mozo, Alberto Fernandez Anta, Antonio Univ Politecn Madrid Dept Sistemas Informat Madrid Spain Inst IMDEA Networks Madrid Spain

A distributed algorithm is proposed for sampling networks, so that nodes are selected by a special node (source), with a given probability distribution. We define a new class of random walks, that we call Random Centrifugal Walks (ROW). A RCW starts at the source and always moves away from it. The algorithm assumes that each node has a weight, so the nodes are selected with a probability proportional to its weight. It requires a preprocessing phase before the sampling of nodes. This preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. The length of RCW walks are bounded by the network diameter. The RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Node sampling Random walks randomized algorithms Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Pricing with Impatient Bidders 16

Online Pricing with Impatient Bidders

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Marek Cygan Marcin Mucha Piotr Sankowski Qiang Zhang Institute of Informatics University of Warsaw

ISBN: (纸本)9781510819672

In this paper we consider the following online pricing problem. An auctioneer is selling identical items in unlimited supply, whereas each bidder from a given set is interested in purchasing a single copy of the item. Each bidder is characterized by a budget and a time interval, in which he is considering to buy the item. Bidders are willing to buy the item at the earliest time provided it is within their time intervals and the price at that time is within their budgets. We call such bidders impatient bidders. The problem is considered in the online setting, i.e., each bidder arrives at the start of his time interval, and only then an algorithm learns of his existence and his budget. The goal of the seller is to set the price of the item over time so that the total revenue is maximized. We study two versions of the impatient bidders problem: the one introduced by Bansal et al. [TALG'10], and a more restricted setting in which the deadline of each bidder remains unknown until it is hit. We give tight bounds for both settings. Rather surprisingly, in both cases the optimum competitive ratios are the same. In particular we prove that the competitive ratio of an optimum deterministic algorithm is Θ(log h/log log h), whereas for randomized algorithms it is Θ(log log h).

关键词： Time intervals Budgets Pricing randomized algorithms solidification Histidine Auctioneers deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic computability and choice

引用

INFORMATION AND COMPUTATION 2015年 242卷 249-286页

作者： Brattka, Vasco Gherardi, Guido Hoelzl, Rupert Univ Bundeswehr Munchen Fac Comp Sci Munich Germany Univ Cape Town Dept Math & Appl Math ZA-7700 Rondebosch South Africa Natl Univ Singapore Fac Sci Dept Math Singapore 117548 Singapore

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak Konig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak Konig's Lemma, but not to Weak Weak Konig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space. Besides Cantor space, we study the natural numbers, the Euclidean space and Baire space. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Computable analysis Weihrauch lattice Computability theory Reverse mathematics randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

On the de-randomization of space-bounded approximate counting problems

引用

INFORMATION PROCESSING LETTERS 2015年第10期115卷 750-753页

作者： Doron, Dean Ta-Shma, Amnon Tel Aviv Univ Blavatnik Sch Comp Sci IL-6997801 Tel Aviv Israel

It was recently shown that SVD and matrix inversion can be approximated in quantum log-space [1] for well formed matrices. This can be interpreted as a fully logarithmic quantum approximation scheme for both problems. We show that if prBQL = prBPL then every fully logarithmic quantum approximation scheme can be replaced by a probabilistic one. Hence, if classical algorithms cannot approximate the above functions in logarithmic space, then there is a gap already for languages, namely, prBQL not equal prBPL. On the way we simplify a proof of Goldreich for a similar statement for time bounded probabilistic algorithms. We show that our simplified algorithm works also in the space bounded setting (for a large set of functions) whereas Goldreich's approach does not seem to apply in the space bounded setting. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Computational complexity Approximation algorithms randomized algorithms Space bounded computation Space bounded quantum computation Space bounded approximation schemes

来源：评论

学校读者我要写书评

暂无评论

DETECTING AND COUNTING SMALL PATTERN GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第3期29卷 1322-1339页

作者： Floderus, Peter Kowaluk, Miroslaw Lingas, Andrzej Lundell, Eva-Marta Lund Univ Ctr Math Sci S-22100 Lund Sweden Warsaw Univ Inst Informat Warsaw Poland Lund Univ Dept Comp Sci S-22100 Lund Sweden

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.

关键词： subgraph and induced subgraph isomorphism counting and detection of subgraphs polynomial testing exact algorithms randomized algorithms rectangular matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds on Sample Size for Implicit Matrix Trace Estimators

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2015年第5期15卷 1187-1212页

作者： Roosta-Khorasani, Farbod Ascher, Uri Univ British Columbia Dept Comp Sci Vancouver BC V6T 1W5 Canada

This article is concerned with Monte Carlo methods for the estimation of the trace of an implicitly given matrix whose information is only available through matrix-vector products. Such a method approximates the trace by an average of expressions of the form , with random vectors drawn from an appropriate distribution. We prove, discuss and experiment with bounds on the number of realizations required to guarantee a probabilistic bound on the relative error of the trace estimation upon employing Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. In total, one necessary bound and six sufficient bounds are proved, improving upon and extending similar estimates obtained in the seminal work of Avron and Toledo (JACM 58(2). Article 8, 2011) in several dimensions. We first improve their bound on for the Hutchinson method, dropping a term that relates to and making the bound comparable with that for the Gaussian estimator. We further prove new sufficient bounds for the Hutchinson, Gaussian and unit vector estimators, as well as a necessary bound for the Gaussian estimator, which depend more specifically on properties of matrix . As such, they may suggest the type of matrix for which one distribution or another provides a particularly effective or relatively ineffective stochastic estimation method.

关键词： randomized algorithms Trace estimation Monte Carlo methods Implicit linear operators

来源：评论

学校读者我要写书评

暂无评论

SUBSPACE ITERATION RANDOMIZATION AND SINGULAR VALUE PROBLEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2015年第3期37卷 A1139-A1173页

作者： Gu, M. Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

A classical problem in matrix computations is the efficient and reliable approximation of a given matrix by a matrix of lower rank. The truncated singular value decomposition (SVD) is known to provide the best such approximation for any given fixed rank. However, the SVD is also known to be very costly to compute. Among the different approaches in the literature for computing low-rank approximations, randomized algorithms have attracted researchers' attention recently due to their surprising reliability and computational efficiency in different application areas. Typically, such algorithms are shown to compute with very high probability low-rank approximations that are within a constant factor from optimal, and are known to perform even better in many practical situations. In this paper, we present a novel error analysis that considers randomized algorithms within the subspace iteration framework and show with very high probability that highly accurate low-rank approximations as well as singular values can indeed be computed quickly for matrices with rapidly decaying singular values. Such matrices appear frequently in diverse application areas such as data analysis, fast structured matrix computations, and fast direct methods for large sparse linear systems of equations and are the driving motivation for randomized methods. Furthermore, we show that the low-rank approximations computed by these randomized algorithms are actually rank-revealing approximations, and the special case of a rank-1 approximation can also be used to correctly estimate matrix 2-norms with very high probability. Our numerical experiments are in full support of our conclusions.

关键词： low-rank approximation randomized algorithms singular values standard Gaussian matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：