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

memory complexity of Estimating Entropy and Mutual Information

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第5期71卷 3334-3349页

作者： Berg, Tomer Ordentlich, Or Shayevitz, Ofer Tel Aviv Univ Dept Elect Engn Syst IL-69978 Tel Aviv Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn IL-91904 Jerusalem Israel

We observe an infinite sequence of independent identically distributed random variables X-1, X-2,& mldr;drawn from an unknown distribution p over [n] , and our goal is to estimate the entropy H(p) = -E[logp(X)] within an epsilon -additive error. To that end, at each time point we are allowed to update a finite-state machine with S states, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity S & lowast;of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least 1 - delta asymptotically, uniformly in p. Specifically, we show that there exist universal constants C-1 and C-2 such that S* <= C-1 & sdot;n(log n)(4)/epsilon(2)delta for epsilon not too small, and S* >= C-2 & sdot;max{n, log n/epsilon} for epsilon not too large. The upper bound is proved using approximate counting to estimate the logarithm of p, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.

关键词： Entropy Estimation complexity theory memory management Mutual information Lower bound Additives Upper bound Testing Automata memory complexity sample complexity entropy estimation mutual information estimation finite memory algorithms

来源：评论

学校读者我要写书评

暂无评论

On The memory complexity of Uniformity Testing 35

On The Memory Complexity of Uniformity Testing

引用

35th Conference on Learning Theory (COLT)

作者： Berg, Tomer Ordentlich, Or Shayevitz, Ofer Tel Aviv Univ Sch Elect Engn Tel Aviv Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn Jerusalem Israel

In this paper we consider the problem of uniformity testing with limited memory. We observe a sequence of independent identically distributed random variables drawn from a distribution p over [n], which is either uniform or is epsilon-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with S states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most 0 < delta < 1/2 uniformly under both hypotheses. The main contribution of this paper is deriving upper and lower bounds on the number of states S needed in order to achieve a constant error probability d, as a function of n and e, where our upper bound is O(n log n/epsilon) and our lower bound is Omega(n + 1/epsilon). Prior works in the field have almost exclusively used collision counting for upper bounds, and the Paninski mixture for lower bounds. Somewhat surprisingly, in the limited memory with unlimited samples setup, the optimal solution does not involve counting collisions, and the Paninski prior is not hard. Thus, different proof techniques are needed in order to attain our bounds.

关键词： memory complexity uniformity testing

来源：评论

学校读者我要写书评

暂无评论

Statistical Inference With Limited memory: A Survey

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2024年 5卷 623-644页

作者： Berg, Tomer Ordentlich, Or Shayevitz, Ofer Tel Aviv Univ Dept Elect Engn Syst IL-6997801 Tel Aviv Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn IL-91904 Jerusalem Israel

The problem of statistical inference in its various forms has been the subject of decades-long extensive research. Most of the effort has been focused on characterizing the behavior as a function of the number of available samples, with far less attention given to the effect of memory limitations on performance. Recently, this latter topic has drawn much interest in the engineering and computer science literature. In this survey paper, we attempt to review the state-of-the-art of statistical inference under memory constraints in several canonical problems, including hypothesis testing, parameter estimation, and distribution property testing/estimation. We discuss the main results in this developing field, and by identifying recurrent themes, we extract some fundamental building blocks for algorithmic construction, as well as useful techniques for lower bound derivations.

关键词： memory complexity sample complexity com- munication complexity com- munication complexity inference under memory constraints finite memory algorithms finite memory algorithms simple hypothesis testing simple hypothesis testing parameter estimation parameter estimation uniformity testing uniformity testing entropy estimation entropy estimation entropy estimation

来源：评论

学校读者我要写书评

暂无评论

Showcasing straight-line programs with memory via matrix Bruhat decomposition

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2024年第7期34卷 1059-1090页

作者： Niemeyer, Alice C. Popiel, Tomasz Praeger, Cheryl E. Rademacher, Daniel Rhein Westfal TH Aachen Chair Algebra & Representat Theory Pontdriesch 10-16 D-52062 Aachen Germany Monash Univ Sch Math 9 Rainforest Walk Clayton Vic 3800 Australia Univ Western Australia Ctr Math Symmetry & Computat 35 Stirling Highway Crawley WA 6009 Australia

We suggest that straight-line programs designed for algebraic computations should be accompanied by a comprehensive complexity analysis that takes into account both the number of fundamental algebraic operations needed, as well as memory requirements arising during evaluation. We introduce an approach for formalizing this idea and, as illustration, construct and analyze straight-line programs for the Bruhat decomposition of d x d matrices with determinant 1 over a finite field of order q that have length O(d2log(q)) and require storing only O(log(q)) matrices during evaluation.

关键词： Straight-Line program complexity of algorithms Bruhat decomposition memory complexity

来源：评论

学校读者我要写书评

暂无评论

Agent-Driven BFS Tree in Anonymous Graphs with Applications 1

引用

12th International Conference on Networked Systems (NETYS)

作者： Chand, Prabhat Kumar Kumar, Manish Molla, Anisur Rahaman Indian Stat Inst Kolkata Baranagar India Indian Inst Technol Chennai India

ISBN: (数字)9783031673214

ISBN: (纸本)9783031673207;9783031673214

Breadth-First-Search (BFS) trees serve a pivotal role in designing efficient graph algorithms due to their efficacy in traversing and exploring graph structures with a systematic layer-by-layer approach. This paper introduces an agent-based novel approach for constructing a BFS tree on an arbitrary anonymous graph G with n nodes and m edges using k >= n autonomous mobile agents. In this paper, we provide algorithms for BFS tree construction for different starting configurations and demonstrate their applications. Our main result considers the dispersed starting configuration (i.e., each node is occupied by a single agent at the start) and takes O(D Delta) rounds to execute, where D is the diameter and Delta is the highest degree of G. The algorithm assumes the knowledge of a root node for the BFS tree. We further continue our investigation for BFS tree construction with two other classical configurations, namely, rooted configuration and arbitrary configuration (with and without the knowledge of root) of the agents with some other follow-up configurations for k > n. In addition, the paper demonstrates the application of the BFS tree construction methodology in tasks like - checking a graph for bipartiteness and gathering agents into a single node, a fundamental task in distributed robotics.

关键词： Breadth First Search Tree Mobile Agents Distributed Network Algorithms Time complexity memory complexity Bipartite Graph Gathering Distributed Graph Algorithms

来源：评论

学校读者我要写书评

暂无评论

Run for Cover: Dominating Set via Mobile Agents 1

引用

19th International Symposium on Algorithmics of Wireless Networks (ALGOWIN) as part of ALGO Conference

作者： Chand, Prabhat Kumar Molla, Anisur Rahaman Sivasubramaniam, Sumathi Indian Stat Inst Kolkata India

ISBN: (数字)9783031488825

ISBN: (纸本)9783031488818;9783031488825

Research involving computing with mobile agents is a fast-growing field, given the advancement of technology in automated systems, e.g., robots, drones, self-driving cars, etc. Therefore, it is pressing to focus on solving classical network problems using mobile agents. In this paper, we study one such problem-finding small dominating sets of a graph G using mobile agents. Dominating set is interesting in the field of mobile agents as it opens up a way for solving various robotic problems, e.g., guarding, covering, facility location, transport routing, etc. In this paper, we first present two algorithms for computing a minimal dominating set: (i) an O(m) time algorithm if the robots start from a single node (i.e., gathered initially), (ii) an O(l Delta log(lambda) + nl + m) time algorithm, if the robots start from multiple nodes (i.e., positioned arbitrarily), where m is the number of edges and. is the maximum degree of G, l is the number of clusters of the robots initially and lambda is the maximum ID-length of the robots. Then we present a ln(Delta) approximation algorithm for the minimum dominating set which takes O(n Delta log(lambda)) rounds.

关键词： Dominating Set Mobile Agents Distributed Network Algorithms Approximation Algorithms Time complexity memory complexity Maximal Independent Set

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Dispersion of Mobile Robots 9th

Fault-Tolerant Dispersion of Mobile Robots

引用

9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM)

作者： Chand, Prabhat Kumar Kumar, Manish Molla, Anisur Rahaman Sivasubramaniam, Sumathi Indian Stat Inst Kolkata India

ISBN: (纸本)9783031252105;9783031252112

We consider the mobile robot dispersion problem in the presence of faulty robots (crash-fault). Mobile robot dispersion consists of k <= n robots in an n-node anonymous graph. The goal is to ensure that regardless of the initial placement of the robots over the nodes, the final configuration consists of having at most one robot at each node. In a crash-fault setting, up to f <= k robots may fail by crashing arbitrarily and subsequently lose all the information stored at the robots, rendering them unable to communicate. In this paper, we solve the dispersion problem in a crash-fault setting by considering two different initial configurations: i) the rooted configuration, and ii) the arbitrary configuration. In the rooted case, all robots are placed together at a single node at the start. The arbitrary configuration is a general configuration (a.k.a. arbitrary configuration in the literature) where the robots are placed in some l < k clusters arbitrarily across the graph. For the first case, we develop an algorithm solving dispersion in the presence of faulty robots in O(k(2)) rounds, which improves over the previous O(f center dot min(m, k Delta))-round result by [23]. For the arbitrary configuration, we present an algorithm solving dispersion in O((f + l) center dot min(m, k Delta, k(2))) rounds, when the number of edges m and the maximum degree. of the graph is known to the robots.

关键词： Distributed algorithm Mobile robot Dispersion Fault-tolerant algorithm Crash-fault Round complexity memory complexity

来源：评论

学校读者我要写书评

暂无评论

Clustered Network Adaptation Methodology for the Resource Constrained Platform 20

Clustered Network Adaptation Methodology for the Resource Co...

引用

20th IEEE Interregional NEWCAS Conference (IEEE NEWCAS)

作者： Verma, Pratibha Sasmal, Pradip Pal, Chandrajit Channappayya, Sumohana Acharyya, Amit Indian Inst Technol Dept Elect Engn Hyderabad India

ISBN: (数字)9781665401050

ISBN: (纸本)9781665401050

Recently, deep neural networks (DNNs) are widely used for many artificial intelligence (AI) applications, including robotics, self driving vehicles etc. Although DNNs deliver state-of-the-art accuracy on many AI tasks, but are both computationally and memory intensive. This hinders the deployment of DNNs on mobile and IoT edge devices with limited hardware resources and power budgets. Traditional DNN compression is applicable during training to obtain an efficient inference engine. When the inference engine runs on the hardware platform, constrained by battery backup it brings additional challenge in terms of reducing the complexity (like memory requirement, area on hardware etc.). To reduce the memory complexity, we are proposing a new low complex methodology named as "Clustering Algorithm" to eliminate the redundancies present within the filter coefficients (i.e. weights). This algorithm is a three stage pipeline: quantization, coefficient clustering and code-assignment, that work together to reduce the memory storage of neural networks on the cost of low run-time memory requirement. To show the efficacy of the proposed "Clustering Algorithm", we executed it on the network obtained after applying NetAdapt Algorithm, a popular inference engine on pre-trained AlexNet for CIFAR-10 dataset. We observe that our "Clustering Algorithm" reduces the storage required by five layers of already pruned pre-trained AlexNet by 3x (approximately 65%) on FPGA, and 2x (approximately 51%) on CPU. This allows the model to fit into on-chip SRAM cache rather than off-chip DRAM memory.

关键词： Deep Learning Model Compression memory complexity Convolutional Neural Network Clustering

来源：评论

学校读者我要写书评

暂无评论

memory-Constrained No-Regret Learning in Adversarial Multi-Armed Bandits

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 2371-2382页

作者： Xu, Xiao Zhao, Qing Cornell Univ Sch Elect & Comp Engn Ithaca NY 14850 USA

An adversarial multi-armed bandit problem with memory constraints is studied where the memory for storing arm statistics is only in a sublinear order of the number of arms. A hierarchical learning framework that offers a sequence of operating points on the tradeoff curve between the regret order and memory complexity is developed. Its sublinear regret orders are established under both weak regret and shifting regret notions. This work appears to be the first on memory-constrained bandit problems in the adversarial setting.

关键词： memory management complexity theory Benchmark testing Stochastic processes Deep learning Games History Adversarial multi-armed bandits no-regret learning memory complexity

来源：评论

学校读者我要写书评

暂无评论

An empirical estimation for time and memory algorithm complexities: newly developed R package

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2021年第2期80卷 2997-3015页

作者： Agenis-Nevers, Marc Bokde, Neeraj Dhanraj Yaseen, Zaher Mundher Shende, Mayur Kishor Epictr Factory Clermont Ferrand France Aarhus Univ Dept Engn Renewable Energy & Thermodynam Aarhus Denmark Ton Duc Thang Univ Sustainable Dev Civil Engn Res Grp Fac Civil Engn Ho Chi Minh City Vietnam Govt Coll Engn Nagpur Maharashtra India

When an algorithm or a program runs on a computer, it requires some resources. The complexity of an algorithm is the measure of the resources, for some input. These complexities are usually space and time. The subject of the empirical computational complexity has been studied in the research. This article introduces GuessCompx which is an R package that performs an empirical estimation on the time and memory complexities of an algorithm or a function, and provides a reliable, convenient and simple procedure for estimation process. It tests multiple increasing-sizes samples of the user's data and attempts to fit one of seven complexity functions:O(N), O(N2), O(log(N)), etc. In addition, based on the best fit procedure using leave one out-mean squared error (LOO-MSE), it predicts the full computation time and memory usage on the whole dataset. Together with this results, a plot and a significance test are returned. complexity is assessed with regard to the user's actual dataset through its size (and no other parameter). This article provides several examples demonstrating several cases (e.g., distance function, time series and custom function) and optimal parameters tuning.

关键词： Time complexity memory complexity Empirical approach R package Algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：