Sublinear Algorithms for Approximating Probability Distributions

用于近似概率分布的次线性算法

• 批准号: EP/L021749/1
• 负责人: Ilias Diakonikolas
• 金额: $ 12.59万
• 依托单位: University of Edinburgh
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2014
• 资助国家: 英国
• 起止时间: 2014 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FL021749%2F1
• 关键词: Sublinear; Algorithms; Approximating; Probability; Distributions

The goal of this proposal is to advance a research program of developing sublinear-time algorithms for estimating a wide range of natural and important classes of probability distributions.We live in an era of "big data," where the amount of data that can be brought to bearon questions of biology, climate, economics, etc, is vast and expanding rapidly.Much of this raw data frequently consists of example points without corresponding labels.The challenge of how to make sense of this unlabeled data has immediate relevanceand has rapidly become a bottleneck in scientific understanding across many disciplines.An important class of big data is most naturally modeled as samples from a probability distribution over a very large domain. The challenge of big data is that the sizes of the domains of the distributions are immense, typically resulting in unacceptably slow algorithms. Scaling up a computational framework to comfortably deal with ever-larger data presents a series of challenges in algorithms. This prompts the basic question: Given samples from some unknown distribution, what can we infer?While this question has been studied for several decades by various different communities of researchers,both the number of samples and running time required for such estimation tasksare not yet well understood, even for some surprisingly simple types of discrete distributions.The proposed research focuses on sublinear-time algorithms, that is,algorithms that run in time that is significantly less than the domain of the underlying distributions.In this project we will develop sublinear-time algorithms for estimating various classes of discrete distributions over very large domains. Specific problems we will address include:(1) Developing sublinear algorithms to estimate probability distributions that satisfy variousnatural types of "shape restrictions" on the underlying probability density function.(2) Developing sublinear algorithms for estimating complex distributions that result from the aggregation of many independent simple sources of randomness.We believe that highly efficient algorithms for these estimation tasks may play an important role for the next generation of large-scale machine learning applications.

该提案的目标是推进开发亚线性时间算法的研究计划，以估计各种自然且重要的概率分布类别。我们生活在“大数据”时代，可以计算的数据量涉及生物学、气候、经济学等问题的数据量巨大且正在迅速扩展。这些原始数据中的大部分通常由没有相应标签的示例点组成。如何理解这些未标记数据的挑战具有直接相关性，并且已迅速成为许多人科学理解的瓶颈一类重要的大数据最自然地被建模为来自非常大的域的概率分布的样本。大数据的挑战在于分布域的大小巨大，通常会导致算法速度慢得令人无法接受。扩展计算框架以轻松处理越来越大的数据给算法带来了一系列挑战。这就提出了一个基本问题：给定来自某个未知分布的样本，我们可以推断出什么？虽然这个问题已经被各个不同领域的研究人员研究了几十年，但此类估计任务所需的样本数量和运行时间尚不清楚可以理解，即使对于一些令人惊讶的简单类型的离散分布。所提出的研究重点是次线性时间算法，即运行时间明显小于基础分布域的算法。在这个项目中，我们将开发次线性时间算法时间算法估计非常大的域上的各种类别的离散分布。我们将解决的具体问题包括：(1) 开发次线性算法来估计概率分布，以满足底层概率密度函数的各种自然类型的“形状限制”。(2) 开发次线性算法来估计由许多集合产生的复杂分布。独立的简单随机源。我们相信，用于这些估计任务的高效算法可能会在下一代大规模机器学习应用中发挥重要作用。

项目成果

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer

关于单位需求购买者的最优彩票定价和随机机制的复杂性

• DOI: http://dx.10.1137/17m1136481
• 发表时间: 2022
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Chen X

Fast Algorithms for Segmented Regression

分段回归的快速算法

• DOI: 10.1109/wacv.2016.7477651
• 发表时间: 2016-06-19
• 期刊: ArXiv
• 作者: Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
• 通讯作者: Ludwig Schmidt

Testing Shape Restrictions of Discrete Distributions

测试离散分布的形状限制

• DOI: http://dx.10.48550/arxiv.1507.03558
• 发表时间: 2015
• 作者: Canonne C

Sample-Optimal Density Estimation in Nearly-Linear Time

近线性时间内的样本最优密度估计

• DOI: http://dx.10.48550/arxiv.1506.00671
• 发表时间: 2015
• 作者: Acharya J

Fourier-Based Testing for Families of Distributions

基于傅立叶的分布族测试

• DOI: http://dx.10.48550/arxiv.1706.05738
• 发表时间: 2017
• 作者: Canonne C