In the sequential setting, a decades-old fundamental result in online algorithms states that if there is a c-competitive randomized online algorithm against an adaptive, offline adversary, then there is a c-competitiv...
详细信息
In the sequential setting, a decades-old fundamental result in online algorithms states that if there is a c-competitive randomized online algorithm against an adaptive, offline adversary, then there is a c-competitive deterministic algorithm. The adaptive, offline adversary is the strongest adversary among the ones usually considered, so the result states that if one has to be competitive against such a strong adversary, then randomization does not help. This implies that researchers do not consider randomization against an adaptive, offline adversary. We prove that in a distributed setting, this result does not necessarily hold, so randomization against an adaptive, offline adversary becomes interesting again. (C) 2020 Elsevier B.V. All rights reserved.
In this paper, we introduce a method for multivariate function approximation using function evaluations, Chebyshev polynomials, and tensor-based compression techniques via the Tucker format. We develop novel randomize...
详细信息
In this paper, we introduce a method for multivariate function approximation using function evaluations, Chebyshev polynomials, and tensor-based compression techniques via the Tucker format. We develop novel randomized techniques to accomplish the tensor compression, provide a detailed analysis of the computational costs, provide insight into the error of the resulting approximations, and discuss the benefits of the proposed approaches. We also apply the tensor-based function approximation to develop low-rank matrix approximations to kernel matrices that describe pairwise interactions between two sets of points;the resulting low-rank approximations are efficient to compute and store (the complexity is linear in the number of points). We present an adaptive version of the function and kernel approximation that determines an approximation that satisfies a user-specified relative error over a set of random points. We extend our approach to the case where the kernel requires repeated evaluations for many values of (hyper)parameters that govern the kernel. We give detailed numerical experiments on example problems involving multivariate function approximation, low-rank matrix approximations of kernel matrices involving well-separated clusters of sources and target points, and a global low-rank approximation of kernel matrices with an application to Gaussian processes. We observe speedups up to 18X over standard matrix-based approaches.
Distributed peer-to-peer systems rely on voluntary participation of peers to effectively manage a storage pool. In such systems, data is generally replicated for performance and availability. If the storage associated...
详细信息
Distributed peer-to-peer systems rely on voluntary participation of peers to effectively manage a storage pool. In such systems, data is generally replicated for performance and availability. If the storage associated with replication is not monitored and provisioned, the underlying benefits may not be realized. Resource constraints, performance scalability, and availability present diverse considerations. Availability and performance scalability, in terms of response time, are improved by aggressive replication, whereas resource constraints limit total storage in the network. Identification and elimination of redundant data pose fundamental problems for such systems. In this paper, we present a novel and efficient solution that addresses availability and scalability with respect to management of redundant data. Specifically, we address the problem of duplicate elimination in the context of systems connected over an unstructured peer-to-peer network in which there is no a priori binding between an object and its location. We propose two randomized protocols to solve this problem in a scalable and decentralized fashion that does not compromise the availability requirements of the application. Performance results using both large-scale simulations and a prototype built on PlanetLab demonstrate that our protocols provide high probabilistic guarantees while incurring minimal administrative overheads.
Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizi...
详细信息
Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor. (C) 2002 Elsevier Science B.V. All rights reserved.
The CANDECOMP/ PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdeter...
详细信息
The CANDECOMP/ PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show that the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri-Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization.
We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic oper...
详细信息
We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum l(2)-norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
The mechanisms used to improve the reliability of distributed systems often limit performance and scalability. Focusing on one widely-used definition of reliability, we explore the origins of this phenomenon and concl...
详细信息
The mechanisms used to improve the reliability of distributed systems often limit performance and scalability. Focusing on one widely-used definition of reliability, we explore the origins of this phenomenon and conclude that it reflects a tradeoff arising deep within the typical protocol stack. Specifically, we suggest that protocol designs often disregard the high cost of infrequent events. When a distributed system is scaled, both the frequency and the overall cost of such events often grow with the size of the system. This triggers an O(n(2)) phenomenon, which becomes visible above some threshold sizes. Our findings suggest that it would be more effective to construct large-scale reliable systems where, unlike traditional protocol stacks, lower layers use randomized mechanisms, with probabilistic guarantees, to overcome low-probability events. Reliability and other end-to-end properties are introduced closer to the application. We employ a back-of-the-envelope analysis to quantify this phenomenon for a class of strongly reliable multicast problems. We construct a non-traditional stack, as described above, that implements virtually synchronous multicast. Experimental results reveal that virtual synchrony over a non-traditional, probabilistic stack helps break through the scalability barrier faced by traditional implementations of the protocol. Copyright (C) 2002 John Wiley Sons, Ltd.
We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions wi...
详细信息
We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions with the exponent rho. We study the epsilon-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic epsilon-complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized epsilon-complexity is of order epsilon(-d/(r+rho)). In the quantum setting, the epsilon-complexity is shown to be of order epsilon(-d/(2(r+rho))). This means that a quadratic speed-up is achieved on a quantum computer. (C) 2013 Elsevier Inc. All rights reserved.
We present an O(n(3))-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where it is the number of vertices in the input (u...
详细信息
We present an O(n(3))-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where it is the number of vertices in the input (undirected) graph. This improves the previous best.
The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. in this paper we present efficient algorith...
详细信息
The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. in this paper we present efficient algorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N-2-processor OTIS-Mesh is 4 root N - 3. We present an algorithm for routing any partial permutation in 4 root N + o(root N) time. Our selection algorithm runs in time 6 root N + o(root N) and our sorting algorithm runs in 8 root N + o(root N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.
暂无评论