Sublinear Algorithms for Approximating Probability Distributions

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

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.