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

universal algorithms for Clustering Problems

ACM TRANSACTIONS ON algorithms 2023年第2期19卷 15-15页

作者： Ganesh, Arun Maggs, Bruce M. Panigrahi, Debmalya Univ Calif Berkeley Soda Hall Berkeley CA 94709 USA Duke Univ 308 Res Dr Durham NC 27710 USA Emerald Innovat 308 Res Dr Durham NC 27710 USA

This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm's solution and that of an optimal solution. A universal algorithm's solution sol for a clustering problem is said to be an (alpha, beta)-approximation if for all subsets of clients C', it satisfies sol(C') <= alpha center dot opt(C') + beta center dot mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other l(p) objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (alpha, beta)-approximation is NP-hard if alpha or beta is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O( 1))-approximation is the strongest type of guarantee obtainable for universal clustering.

关键词： universal algorithms clustering

来源：评论

学校读者我要写书评

暂无评论

universal algorithms for multinomial logistic regression under Kullback-Leibler game

引用

NEUROCOMPUTING 2020年 397卷 369-380页

作者： Dzhamtyrova, Raisa Kalnishkan, Yuri Royal Holloway Univ London Dept Comp Sci Egham Surrey England Moscow Inst Phys & Technol Lab Adv Combinator & Network Applicat Moscow Russia

We consider the framework of competitive prediction, where one provides guarantees compared to other predictive models that are called experts. We propose a universal algorithm predicting finite-dimensional distributions, i.e. points from a simplex, under Kullback-Leibler game. In the standard framework for prediction with expert advice, the performance of the learner is measured by means of the cumulative loss. In this paper we consider a generalisation of this setting and discount losses with time. A natural choice of predictors for the probability games is a class of multinomial logistic regression functions as they output a distribution that lies inside a probability simplex. We consider the class of multinomial logistic regressions to be our experts. We provide a strategy that allows us to 'track the best expert' of this type and derive the theoretical bound on the discounted loss of the strategy. We provide the kernelized version of our algorithm, which competes with a wider set of experts from Reproducing Kernel Hilbert Space (RKHS) and prove a theoretical guarantee for the kernelized strategy. We carry out experiments on three data sets and compare the cumulative losses of our algorithm and multinomial logistic regression. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Online learning Sequential prediction Competitive prediction universal algorithms Loss bounds Kullback-Leibler game

来源：评论

学校读者我要写书评

暂无评论

One Tree to Rule Them All: Poly-Logarithmic universal Steiner Tree 64

One Tree to Rule Them All: Poly-Logarithmic Universal Steine...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Busch, Costas Chen, Da Qi Filtser, Arnold Hathcock, Daniel Hershkowitz, D. Ellis Rajaraman, Rajmohan Augusta Univ Sch Comp & Cyber Sci Augusta GA 30912 USA Univ Virginia Biocomplex Inst & Initiat Charlottesville VA USA Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Carnegie Mellon Univ Dept Math Sci Pittsburgh PA USA Brown Univ Dept Comp Sci Providence RI USA Swiss Fed Inst Technol Dept Math Zurich Switzerland Northeastern Univ Khoury Coll Comp Sci Boston MA USA

ISBN: (纸本)9798350318944

A spanning tree T of graph G is a rho-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a rho factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits 2(O(root log n))-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions. We settle these open questions by giving polynomial-time algorithms for computing both O(log(7) n)-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving O(log n)-approximate USTs and O(1) strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

关键词： approximation algorithms metric embeddings Steiner trees universal algorithms

来源：评论

学校读者我要写书评

暂无评论

Recovery From Linear Measurements With Complexity-Matching universal Signal Estimation

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2015年第6期63卷 1512-1527页

作者： Zhu, Junan Baron, Dror Duarte, Marco F. N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA Univ Massachusetts Dept Elect & Comp Engn Amherst MA 01003 USA

We study the compressed sensing (CS) signal estimation problem where an input signal is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the input signal during recovery, the signal structure that can be leveraged is often not known a priori. In this paper, we consider universal CS recovery, where the statistics of a stationary ergodic signal source are estimated simultaneously with the signal itself. Inspired by Kolmogorov complexity and minimum description length, we focus on a maximum a posteriori (MAP) estimation framework that leverages universal priors to match the complexity of the source. Our framework can also be applied to general linear inverse problems where more measurements than in CS might be needed. We provide theoretical results that support the algorithmic feasibility of universal MAP estimation using a Markov chain Monte Carlo implementation, which is computationally challenging. We incorporate some techniques to accelerate the algorithm while providing comparable and in many cases better reconstruction quality than existing algorithms. Experimental results show the promise of universality in CS, particularly for low-complexity sources that do not exhibit standard sparsity or compressibility.

关键词： Compressed sensing MAP estimation Markov chain Monte Carlo universal algorithms

来源：评论

学校读者我要写书评

暂无评论

Low-Delay Distributed Source Coding for Time-Varying Sources with Unknown Statistics 34

Low-Delay Distributed Source Coding for Time-Varying Sources...

引用

34th IEEE Conference on Computer Communications (INFOCOM)

作者： Chen, Fangzhou Li, Bin Koksal, Can Emre Ohio State Univ Dept ECE Columbus OH 43210 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

ISBN: (纸本)9781479983810

We consider a system in which two nodes take correlated measurements of a random source with time-varying and unknown statistics. The observations of the source at the first node are to be losslessly replicated with a given probability of outage at the second node, which receives data from the first node over a constant-rate channel. We develop a system and associated strategies for joint distributed source coding (encoding and decoding) and transmission control in order to achieve low end-to-end delay. Slepian-Wolf coding in its traditional form cannot be applied in our scenario, since the encoder requires the joint statistics of the observations and the associated decoding delay is very high. We analytically evaluate the performance of our strategies and show that the delay achieved by them are order optimal, as the conditional entropy of the source approaches to the channel rate. We also evaluate the performance of our algorithms based on real-world experiments using two cameras recording videos of a scene at different angles. Having realized our schemes, we demonstrated that, even with a very low-complexity quantizer, a compression ratio of approximately 50% is achievable for lossless replication at the decoder, at an average delay of a few seconds.

关键词： Lossless distributed source coding universal algorithms delay optimal control heavy-traffic analysis

来源：评论

学校读者我要写书评

暂无评论

COMPLEXITY-ADAPTIVE universal SIGNAL ESTIMATION FOR COMPRESSED SENSING

COMPLEXITY-ADAPTIVE UNIVERSAL SIGNAL ESTIMATION FOR COMPRESS...

引用

IEEE Workshop on Statistical Signal Processing (SSP)

作者： Zhu, Junan Baron, Dror Duarte, Marco F. N Carolina State Univ ECE Dept Raleigh NC 27695 USA Univ Massachusetts ECE Dept Amherst MA 01003 USA

ISBN: (纸本)9781479949755

We study the compressed sensing (CS) signal estimation problem where a signal is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the signal during estimation, additional signal structure that can be leveraged is often not known a priori. For signals with independent and identically distributed (i.i.d.) entries, existing CS algorithms achieve optimal or near optimal estimation error without knowing the statistics of the signal. This paper addresses estimating stationary ergodic non-i.i.d. signals with unknown statistics. We have previously proposed a universal CS approach to simultaneously estimate the statistics of a stationary ergodic signal as well as the signal itself. This paper significantly improves on our previous work, especially for continuous-valued signals, by offering a four-stage algorithm called Complexity-Adaptive universal Signal Estimation (CAUSE), where the alphabet size of the estimate adaptively matches the coding complexity of the signal. Numerical results show that the new approach offers comparable and in some cases, especially for non-i.i.d. signals, lower mean square error than the prior art, despite not knowing the signal statistics.

关键词： MAP estimation Markov chain Monte Carlo non-i.i.d. signals signal estimation universal algorithms

来源：评论

学校读者我要写书评

暂无评论

SET COVERING WITH OUR EYES CLOSED

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 808-830页

作者： Grandoni, Fabrizio Gupta, Anupam Leonardi, Stefano Miettinen, Pauli Sankowski, Piotr Singh, Mohit Univ Lugano IDSIA CH-6928 Manno Lugano Switzerland Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Roma La Sapienza I-00185 Rome Italy Univ Helsinki Helsinki Inst Informat Technol FIN-00014 Helsinki Finland Univ Warsaw Inst Informat PL-02097 Warsaw Poland McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada Carnegie Mellon Univ Pittsburgh PA 15213 USA

Given a universe U of n elements and a weighted collection S of m subsets of U, the universal set cover problem is to a priori map each element u is an element of U to a set S(u) is an element of S containing u such that any set X subset of U is covered by S(X) - boolean OR S-u is an element of X(u). The aim is to find a mapping such that the cost of S(X) is as close as possible to the optimal set cover cost for X. (Such problems are also called oblivious or a priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be O(root n) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(log mn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (nonmetric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

关键词： approximation algorithms universal algorithms online algorithms set cover facility location

来源：评论

学校读者我要写书评

暂无评论

universal algorithms for channel decoding of uncompressed sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第5期54卷 2243-2262页

作者： Ordentlich, Erik Seroussi, Gadiel Verdu, Sergio Viswanathan, Krishnamurthy Hewlett Packard Labs Palo Alto CA 94304 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.

关键词： belief propagation channel decoding denoising discrete memoryless channels joint source-channel decoding loss-less compression soft decoding universal algorithms

来源：评论

学校读者我要写书评

暂无评论

universal Estimation of Erasure Entropy

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第1期55卷 350-357页

作者： Yu, Jiming Verdu, Sergio Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

Erasure entropy rate differs from Shannon's entropy rate in that the conditioning occurs with respect to both the past and the future, as opposed to only the past (or the future). In this paper, consistent universal algorithms for estimating erasure entropy rate are proposed based on the basic and extended context-tree weighting (CTW) algorithms. Simulation results for those algorithms applied to Markov sources, tree sources, and English texts are compared to those obtained by fixed-order plug-in estimators with different orders.

关键词： Bidirectional context tree context-tree weighting data compression entropy rate universal algorithms universal modeling

来源：评论

学校读者我要写书评

暂无评论

Discrete Denoising With Shifts

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第11期55卷 5284-5301页

作者： Moon, Taesup Weissman, Tsachy Stanford Univ Dept Elect Engn Stanford CA 94305 USA Technion Israel Inst Technol Dept Elect Engn IL-32000 Technion Haifa Israel

We introduce S-DUDE, a new algorithm for denoising discrete memoryless channel (DMC)-corrupted data. The algorithm, which generalizes the recently introduced DUDE (Discrete universal DEnoiser), aims to compete with a genie that has access, in addition to the noisy data, also to the underlying clean data, and that can choose to switch, up to times, between sliding-window denoisers in a way that minimizes the overall loss. When the underlying data form an individual sequence, we show that the S-DUDE performs essentially as well as this genie, provided that is sublinear in the size of the data. When the clean data are emitted by a piecewise stationary process, we show that the S-DUDE achieves the optimum distribution-dependent performance, provided that the same sublinearity condition is imposed on the number of switches. To further substantiate the universal optimality of the S-DUDE, we show that when the number of switches is allowed to grow linearly with the size of the data, any (sequence of) scheme(s) fails to compete in the above sense. Using dynamic programming, we derive an efficient implementation of the S-DUDE, which has complexity (time and memory) growing linearly with the data size and the number of switches Preliminary experimental results are presented, suggesting that S-DUDE has the capacity to improve on the performance attained by the original DUDE in applications where the nature of the data abruptly changes in time (or space), as is often the case in practice.

关键词： Competitive analysis discrete denoising discrete memoryless channel (DMC) dynamic programming forward-backward recursions individual sequence piecewise stationary processes switching experts universal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：