Minive散列（Minhash）是一种经典方法，用于有效地估计大规模二进制（0/1）数据中的Jaccrad相似性。为了为每个数据向量产生$ k $哈希值，Minhash的标准理论需要k $独立的排列。有趣的是，最近的“循环Minhash”（C-MINASH）的工作表明，仅需要两个排列。第一排列破坏了数据的结构，并且第二个置换以循环方式重新使用$ K $时间。令人惊讶的是，证明C-MINHASH的估计准确性被严格小于原始MINAHASH的精度。最近的工作进一步证明，实际上只需要一个排列。请注意，C-MINHASH与在NIPS'12中发布的“一个权限散列（oph）”的众所周知的工作不同。使用不同“致密化”方案的OPH及其变体是标准Minhash的流行替代品。致密化步骤是必要的，以便处理存在于一个处于一个置换散列中的空箱。在本文中，我们建议纳入C-MINHASH的基本思想，以提高一个置换散列的准确性。基本上，我们为OPH开发了一种新的致密化方法，而与OPH的所有现有的致密化方案相比，实现了最小的估计方差。我们所提出的方法名为C-OPH（循环oph）。在初始排列（缩小数据的现有结构）之后，C-OPH只需要长度$ D / k $（而不是$ d $）的“较短”排列，其中$ d $是原始数据维度和$ k $是oph中的垃圾箱总数。这种短排列以循环移位方式重新使用以美元的价格。可以表明，Jaccard相似性的估计方差严格小于现有（致密化）OPH方法的方差。

我们开发“广义一致加权采样”（GCWS），用于散列“Powered-Gmm”（PGMM）内核（具有调谐参数$ P $）。事实证明，GCWS提供了一种用于在原始数据上应用功率变换的数字稳定方案，无论$ P $和数据的大小如何。功率变换通常有效地提高性能，在许多情况下大大。我们在各种公共分类数据集中将哈希数据送到神经网络上，并命名我们的方法``gcwsnet''。我们广泛的实验表明，GCWSNet经常提高分类准确性。此外，从GCWSNet收敛得更快的实验中，很明显。事实上，GCW通常仅达到合理的准确性（小于）培训过程的一个时代。此属性很需要，因为许多应用程序，例如广告点击率（CTR）预测模型或数据流（即，只有一次的数据），通常只培训一个时代。另一个有益的副作用是，由于输入数据变为二进制（并且高稀疏），第一层的神经网络的计算变得添加而不是乘法。提供了与（标准化）随机傅里叶特征（NRFF）的经验比较。我们还建议通过Count-Shark减少GCWSNet的模型大小，并开发了分析使用计数素描对GCW的准确性的影响的理论。我们的分析表明，“8位”的策略应该很好地运行，因为我们可以始终在GCWS散列的输出上应用一个8位计数迹象，而不会损害精度。在培训深度神经网络时，还有许多其他方法可以利用GCW。例如，可以在最后一层的输出上应用GCW，以提高受过训练的深神经网络的准确性。

A flexible method is developed to construct a confidence interval for the frequency of a queried object in a very large data set, based on a much smaller sketch of the data. The approach requires no knowledge of the data distribution or of the details of the sketching algorithm; instead, it constructs provably valid frequentist confidence intervals for random queries using a conformal inference approach. After achieving marginal coverage for random queries under the assumption of data exchangeability, the proposed method is extended to provide stronger inferences accounting for possibly heterogeneous frequencies of different random queries, redundant queries, and distribution shifts. While the presented methods are broadly applicable, this paper focuses on use cases involving the count-min sketch algorithm and a non-linear variation thereof, to facilitate comparison to prior work. In particular, the developed methods are compared empirically to frequentist and Bayesian alternatives, through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature.

分类属性是那些可以采用离散值集的那些，例如颜色。这项工作是关于将vects压缩到基于小维度离散矢量的分类属性。基于目前的哈希的方法将传感器压缩到低维离散矢量的分类属性不提供压缩表示之间的汉明距离的任何保证。在这里，我们呈现fsketch以创建稀疏分类数据的草图和估算器，以估计仅从其草图中的未压缩数据之间的成对汉明距离。我们声称这些草图可以在通常的数据挖掘任务中使用代替原始数据而不会影响任务的质量。为此，我们确保草图也是分类，稀疏，汉明距离估计是合理的精确性。素描结构和汉明距离估计算法都只需要一条单通;此外，对数据点的改变可以以有效的方式结合到其草图中。压缩性取决于数据的稀疏程度如何且与原始维度无关 - 使我们的算法对许多现实生活场景具有吸引力。我们的索赔通过对FSKetch性质的严格理论分析来支持，并通过对某些现实世界数据集的相关算法进行广泛的比较评估。我们表明FSKetch明显更快，并且通过使用其草图获得的准确性是RMSE，聚类和相似性搜索的标准无监督任务的顶部。

最小化器和卷积神经网络（CNNS）是两种完全不同的流行技术，其都被用于分析生物序列。在面值，方法看起来完全不同。最小机构在滚动窗口上使用min-wise散列，以提取每个窗口的单个重要的K-MET功能。 CNNS从多个随机初始化的卷积滤波器开始，配对池操作，然后多个附加​​的神经层，以学习滤波器本身以及这些过滤器如何用于对序列进行分类。在本手稿中，我通过仔细的数学分析来证明了散列函数的特性，最小化器和卷积滤波器之间存在深刻的理论连接 - 对于在分类字母表上的序列，具有最大池的卷积滤波器的随机高斯初始化是等效的从随机哈希函数选择最小化器偏向更独特的K-MERS。这提供了CNN在分类序列分析中的不合理效果的局部解释。

高维计算（HDC）是用于数据表示和学习的范式，起源于计算神经科学。HDC将数据表示为高维，低精度向量，可用于学习或召回等各种信息处理任务。高维空间的映射是HDC中的一个基本问题，现有方法在输入数据本身是高维时会遇到可伸缩性问题。在这项工作中，我们探索了一个基于哈希的流媒体编码技术。我们正式表明，这些方法在学习应用程序的性能方面具有可比的保证，同时比现有替代方案更有效。我们在一个流行的高维分类问题上对这些结果进行了实验验证，并表明我们的方法很容易扩展到非常大的数据集。

开发了一种使用多个辅助变量的非静止空间建模算法。它将Geodatistics与Simitile随机林结合起来，以提供一种新的插值和随机仿真算法。本文介绍了该方法，并表明它具有与施加地统计学建模和定量随机森林的那些相似的一致性结果。该方法允许嵌入更简单的插值技术，例如Kriging，以进一步调节模型。该算法通过估计每个目标位置处的目标变量的条件分布来工作。这种分布的家庭称为目标变量的包络。由此，可以获得空间估计，定量和不确定性。还开发了一种从包络产生条件模拟的算法。随着它们从信封中的样本，因此通过相对变化的次要变量，趋势和可变性的相对变化局部地影响。

在本文中，我们提出了一种称为\ Textit {自适应提升直方图变换}（\ TeatiT {ABHT}）的渐变升压算法，以便回归以说明直方图变换集合学习中梯度升压算法的本地适应性。从理论上的角度来看，当目标函数位于本地H \“较旧的连续空间时，我们表明我们的ABHT可以用不同的平滑度过滤出区域。因此，我们能够证明收敛的上限ABHT的速率严格小于\ Texit {并行集合直方图变换}（\ Textit {PEHT}）的下限。在实验中，合成和现实世界数据实验都经验验证了理论结果，这证明了有利的性能和我们的ABHT的局部适应性。

在这项工作中，我们提出了一种维度减少算法，即AKA。素描，用于分类数据集。我们提出的草图算法舱从高维分类向量构造低维二进制草图，我们的距离估计算法CHAM仅计算任何两个原始向量之间的汉明距离的近似近似。 Cham以确保良好估计的速度要求的最小尺寸理论上只取决于数据点的稀疏性 - 使其对涉及稀疏数据集的许多现实生活场景有用。我们对我们的方法提供了严格的理论分析，并在几个高维现实世界数据集上进行了广泛的实验，包括一个超过一百万维度的实验。我们表明，与使用完整数据集和其他维数减少技术相比，机舱和Cham Duo是一种明显的快速准确的任务和群集，如RMSE，全对相似性和聚类。

A flexible conformal inference method is developed to construct confidence intervals for the frequencies of queried objects in very large data sets, based on a much smaller sketch of those data. The approach is data-adaptive and requires no knowledge of the data distribution or of the details of the sketching algorithm; instead, it constructs provably valid frequentist confidence intervals under the sole assumption of data exchangeability. Although our solution is broadly applicable, this paper focuses on applications involving the count-min sketch algorithm and a non-linear variation thereof. The performance is compared to that of frequentist and Bayesian alternatives through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature.

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets.This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed-either explicitly or implicitly-to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m × n matrix. (i) For a dense input matrix, randomized algorithms require O(mn log(k)) floating-point operations (flops) in contrast with O(mnk) for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multi-processor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.

本文为信号去噪提供了一般交叉验证框架。然后将一般框架应用于非参数回归方法，例如趋势过滤和二元推车。然后显示所得到的交叉验证版本以获得最佳调谐的类似物所熟知的几乎相同的收敛速度。没有任何先前的趋势过滤或二元推车的理论分析。为了说明框架的一般性，我们还提出并研究了两个基本估算器的交叉验证版本;套索用于高维线性回归和矩阵估计的奇异值阈值阈值。我们的一般框架是由Chatterjee和Jafarov（2015）的想法的启发，并且可能适用于使用调整参数的广泛估算方法。

G-Enum histograms are a new fast and fully automated method for irregular histogram construction. By framing histogram construction as a density estimation problem and its automation as a model selection task, these histograms leverage the Minimum Description Length principle (MDL) to derive two different model selection criteria. Several proven theoretical results about these criteria give insights about their asymptotic behavior and are used to speed up their optimisation. These insights, combined to a greedy search heuristic, are used to construct histograms in linearithmic time rather than the polynomial time incurred by previous works. The capabilities of the proposed MDL density estimation method are illustrated with reference to other fully automated methods in the literature, both on synthetic and large real-world data sets.

加权最近的邻居（WNN）估计量通常用作平均回归估计的灵活且易于实现的非参数工具。袋装技术是一种优雅的方式，可以自动生成最近邻居的重量的WNN估计器；我们将最终的估计量命名为分布最近的邻居（DNN），以便于参考。然而，这种估计器缺乏分布结果，从而将其应用于统计推断。此外，当平均回归函数具有高阶平滑度时，DNN无法达到最佳的非参数收敛率，这主要是由于偏差问题。在这项工作中，我们对DNN提供了深入的技术分析，我们建议通过线性将两个DNN估计量与不同的子采样量表进行线性相结合，从而提出了DNN估计量的偏差方法，从而导致新型的两尺度DNN（TDNN（TDNN） ）估计器。两尺度的DNN估计量具有等效的WNN表示，重量承认明确形式，有些则是负面的。我们证明，由于使用负权重，两尺度DNN估计器在四阶平滑度条件下估算回归函数时享有最佳的非参数收敛速率。我们进一步超出了估计，并确定DNN和两个规模的DNN均无渐进地正常，因为亚次采样量表和样本量差异到无穷大。对于实际实施，我们还使用二尺度DNN的Jacknife和Bootstrap技术提供方差估计器和分配估计器。可以利用这些估计器来构建有效的置信区间，以用于回归函数的非参数推断。建议的两尺度DNN方法的理论结果和吸引人的有限样本性能用几个数值示例说明了。

Classical asymptotic theory for statistical inference usually involves calibrating a statistic by fixing the dimension $d$ while letting the sample size $n$ increase to infinity. Recently, much effort has been dedicated towards understanding how these methods behave in high-dimensional settings, where $d$ and $n$ both increase to infinity together. This often leads to different inference procedures, depending on the assumptions about the dimensionality, leaving the practitioner in a bind: given a dataset with 100 samples in 20 dimensions, should they calibrate by assuming $n \gg d$, or $d/n \approx 0.2$? This paper considers the goal of dimension-agnostic inference; developing methods whose validity does not depend on any assumption on $d$ versus $n$. We introduce an approach that uses variational representations of existing test statistics along with sample splitting and self-normalization to produce a new test statistic with a Gaussian limiting distribution, regardless of how $d$ scales with $n$. The resulting statistic can be viewed as a careful modification of degenerate U-statistics, dropping diagonal blocks and retaining off-diagonal blocks. We exemplify our technique for some classical problems including one-sample mean and covariance testing, and show that our tests have minimax rate-optimal power against appropriate local alternatives. In most settings, our cross U-statistic matches the high-dimensional power of the corresponding (degenerate) U-statistic up to a $\sqrt{2}$ factor.

交叉验证是在许多非参数回归问题中调整参数选择的标准方法。然而，它在变化点回归中的使用不太常见，也许由于其预测误差的标准可能似乎允许小的虚假变化，因此不太适合估计变化点的数量和位置。我们表明，实际上，具有平方误差损失的交叉验证问题更严重，可以导致系统的减少或过度估计变化点的数量，以及在更改的简单设置中的平均功能的高度次优估计很容易检测到。我们提出了两种简单的方法来解决这些问题，第一个涉及使用绝对误差而不是平方误差损失，以及第二个涉及修改所用的熔断集。对于后者，我们提供了允许一致估计一般变更点估计程序的变化点数的条件。我们显示这些条件对于使用新结果的最佳分区满足其在提供错误数量的更改点时的性能。数值实验表明，特别是当错误分布良好的调整参数选择时，特别是使用经典调谐参数选择的绝对误差方法竞争，但可以在错过的模型中显着优于这些。 CRAN上的R包CrossValidationCP中提供了我们的方法。

在线性回归中，我们希望根据少量样本估算超过$ d $维的输入点和实价响应的最佳最小二乘预测。根据标准随机设计分析，其中绘制样品i.i.d。从输入分布中，该样品的最小二乘解决方案可以看作是最佳的自然估计器。不幸的是，该估计器几乎总是产生来自输入点的随机性的不良偏置，这在模型平均中是一个重要的瓶颈。在本文中，我们表明可以绘制非i.i.d。输入点的样本，无论响应模型如何，最小二乘解决方案都是最佳的无偏估计器。此外，可以通过增强先前绘制的I.I.D。可以有效地生产该样本。带有额外的$ d $点的样品，根据点由点跨越的平方量重新缩放的输入分布构建的一定确定点过程，共同绘制。在此激励的基础上，我们开发了一个理论框架来研究体积响应的采样，并在此过程中证明了许多新的矩阵期望身份。我们使用它们来表明，对于任何输入分布和$ \ epsilon> 0 $，有一个随机设计由$ o（d \ log d+ d+ d+ d/\ epsilon）$点，从中可以从中构造出无偏见的估计器，其预期的是正方形损耗在整个发行版中，$ 1+\ epsilon $ times最佳损失。我们提供有效的算法来在许多实际设置中生成这种无偏估计量，并在实验中支持我们的主张。

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the 'combine' function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with \emph{exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only a polylogarithmic number of parameters in $n$, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

我们考虑在未知排列存在下存在的结构化张量的问题。这些数据问题通常在推荐系统，神经影像学，社区检测和多道比较应用中出现。在这里，我们开发了一般的平滑张量模型，直到任意指数排列;该模型包括流行的张量块模型和Lipschitz超图模型作为特殊情况。我们表明，块明智多项式家族中的约束最小二乘估计值实现了最小的误差。相对于最佳恢复所需的平滑度阈值，揭示了相变现象。特别是，我们发现高达$（m-2）（m + 1）/ 2 $的多项式，足以准确地恢复订单 - $ M $张力，而更高的程度则没有进一步的益处。这种现象揭示了具有和没有未知排列的平滑张量估计问题的内在区别。此外，我们提供了一种有效的多项式BORDA计数算法，可在单调性假设下可被证明可以实现最佳率。通过模拟和芝加哥犯罪数据分析证明了我们的程序的功效。

我们考虑了顺序评估的问题，在该问题中，评估者以序列观察候选人，并以在线，不可撤销的方式为这些候选人分配分数。受到在这种环境中研究顺序偏见的心理学文献的激励 - 即，评估结果与候选人出现的顺序之间的依赖性 - 我们为评估者的评级过程提出了一个自然模型，该模型捕获了缺乏固有的校准固有的校准这样的任务。我们进行众包实验，以展示模型的各个方面。然后，我们开始研究如何通过将其作为统计推断问题来纠正模型下的顺序偏差。我们提出了一个接近线性的时间，在线算法，以确保两个规范的排名指标可以保证。我们还通过在两个指标中建立匹配的下限来证明我们的算法在理论上是最佳信息。最后，我们表明我们的算法优于使用报告得分引起的排名的事实上的方法。