信息理论措施已广泛采用学习和决策问题的特征。受到这一点的启发,我们介绍了Shannon Sense的信息损失的弱形式,ii)在考虑一系列有损的连续表示(特征)时,错误(MPE)意义上的最小概率的操作损失连续观察。我们展示了几个结果揭示了这种相互作用的结果。我们的第一个结果在采用离散的损耗表示(量化)而不是原始原始观察时,在其各自的操作损失的函数中提供弱的信息损失形式的下限。从这后,我们的主要结果表明,在考虑一般的持续陈述时,特定形式的消失信息丧失(渐近信息充足的弱势概念)意味着消失的MPE损失(或渐近运营充足机会)。我们的理论调查结果支持观察到选择要捕捉信息充足性的特征表示是适当的学习,但如果预期目标在分类中实现MPE,这种选择是一种相当保守的设计原则。支持这一表明,在某些结构条件下,我们表明,可以采取信息充足的替代概念(严格弱于互信息意义上的纯粹足够的充足),以实现运动充足。
translated by 谷歌翻译
我们介绍了统计实验的两种新的信息度量,它们概括和包含$ \ phi $ -diverences,积分概率指标,$ \ mathfrak {n} $ - distances(mmd)和$(f,\ gamma)$ divergences $ divergences在两个或多个分布之间。这使我们能够在信息的度量与统计决策问题的贝叶斯风险之间得出简单的几何关系,从而将变异的$ \ phi $ -divergence代表扩展到多个分布,以完全对称的方式。在马尔可夫运营商的行动下,新的分歧家庭被关闭,该家族产生了信息处理平等,这是经典数据处理不平等的完善和概括。这种平等使人深入了解假设类别在经典风险最小化中的重要性。
translated by 谷歌翻译
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.
translated by 谷歌翻译
近似消息传递(AMP)是解决高维统计问题的有效迭代范式。但是,当迭代次数超过$ o \ big(\ frac {\ log n} {\ log log \ log \ log n} \时big)$(带有$ n $问题维度)。为了解决这一不足,本文开发了一个非吸附框架,用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项,我们布置了一个分析配方,以表征在存在独立初始化的情况下AMP的有限样本行为,该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果:(i)求解$ \ mathbb {z} _2 $同步时,我们预测了频谱初始化AMP的行为,最高为$ o \ big(\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big)$迭代,表明该算法成功而无需随后的细化阶段(如最近由\ citet {celentano2021local}推测); (ii)我们表征了稀疏PCA中AMP的非反应性行为(在尖刺的Wigner模型中),以广泛的信噪比。
translated by 谷歌翻译
鉴于$ n $ i.i.d.从未知的分发$ P $绘制的样本,何时可以生成更大的$ n + m $ samples,这些标题不能与$ n + m $ i.i.d区别区别。从$ p $绘制的样品?(AXELROD等人2019)将该问题正式化为样本放大问题,并为离散分布和高斯位置模型提供了最佳放大程序。然而,这些程序和相关的下限定制到特定分布类,对样本扩增的一般统计理解仍然很大程度上。在这项工作中,我们通过推出通常适用的放大程序,下限技术和与现有统计概念的联系来放置对公司统计基础的样本放大问题。我们的技术适用于一大类分布,包括指数家庭,并在样本放大和分配学习之间建立严格的联系。
translated by 谷歌翻译
在本文中,我们介绍了超模块化$ \ mf $ -Diverences,并为它们提供了三个应用程序:(i)我们在基于超模型$ \ MF $ - 基于独立随机变量的尾部引入了Sanov的上限。分歧并表明我们的广义萨诺夫(Sanov)严格改善了普通的界限,(ii)我们考虑了有损耗的压缩问题,该问题研究了给定失真和代码长度的一组可实现的速率。我们使用互助$ \ mf $ - 信息扩展了利率 - 延伸函数,并使用超模块化$ \ mf $ -Diverences在有限的区块长度方面提供了新的,严格的更好的界限,并且(iii)我们提供了连接具有有限输入/输出共同$ \ mf $的算法的概括误差和广义率延伸问题。该连接使我们能够使用速率函数的下限来限制学习算法的概括误差。我们的界限是基于对利率延伸函数的新下限,该函数(对于某些示例)严格改善了以前最著名的界限。此外,使用超模块化$ \ mf $ -Divergences来减少问题的尺寸并获得单字母界限。
translated by 谷歌翻译
我们研究了广义熵的连续性属性作为潜在的概率分布的函数,用动作空间和损失函数定义,并使用此属性来回答统计学习理论中的基本问题:各种学习方法的过度风险分析。我们首先在几种常用的F分歧,Wassersein距离的熵差异导出了两个分布的熵差,这取决于动作空间的距离和损失函数,以及由熵产生的Bregman发散,这也诱导了两个分布之间的欧几里德距离方面的界限。对于每个一般结果的讨论给出了示例,使用现有的熵差界进行比较,并且基于新结果导出新的相互信息上限。然后,我们将熵差异界限应用于统计学习理论。结果表明,两种流行的学习范式,频繁学习和贝叶斯学习中的过度风险都可以用不同形式的广义熵的连续性研究。然后将分析扩展到广义条件熵的连续性。扩展为贝叶斯决策提供了不匹配的分布来提供性能范围。它也会导致第三个划分的学习范式的过度风险范围,其中决策规则是在经验分布的预定分布家族的预测下进行最佳设计。因此,我们通过广义熵的连续性建立了统计学习三大范式的过度风险分析的统一方法。
translated by 谷歌翻译
Testing the significance of a variable or group of variables $X$ for predicting a response $Y$, given additional covariates $Z$, is a ubiquitous task in statistics. A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. However, when the model is misspecified, the test may have poor power, for example when $X$ is involved in complex interactions, or lead to many false rejections. In this work we study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests, to yield both robust error control and high power. The procedure involves using these methods to perform regressions, first to estimate a form of projection of $Y$ on $X$ and $Z$ using one half of the data, and then to estimate the expected conditional covariance between this projection and $Y$ on the remaining half of the data. While the approach is general, we show that a version of our procedure using spline regression achieves what we show is the minimax optimal rate in this nonparametric testing problem. Numerical experiments demonstrate the effectiveness of our approach both in terms of maintaining Type I error control, and power, compared to several existing approaches.
translated by 谷歌翻译
随机块模型(SBM)是一个随机图模型,其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型,并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展,无论是在信息理论和计算方案方面,以及各种恢复要求,例如精确,部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换,Kesten-Stigum阈值弱恢复的相变,最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导,特别是通过绘制绘制,半定义编程,(线性化)信念传播,经典/非背带频谱和图形供电。还讨论了其他块模型的扩展,例如几何模型和一些开放问题。
translated by 谷歌翻译
我们考虑使用随机球形代码的高维信号$ x $的有损压缩表示之间的分布连接,并在添加白色高斯噪声(AWGN)下的$ X $观察$ x $。我们展示了比特率 - $ R $压缩版的Wassersein距离$ x $及其在AWGN-噪声比率下的AWGN噪声比率下的观察2 ^ {2R} -1 $ 2 ^ {2r} -1 $中的下线性。我们利用此事实基于AWGN损坏的$ x $的AWGN损坏版本的估算者的风险连接到与其比特率 - $ r $量化版本相同的估算器所获得的风险。我们通过在压缩约束下导出推导问题的各种新结果来展示这种联系的有用性,包括Minimax估计,稀疏回归,压缩感和远程源编码中的线性估计的普遍性。
translated by 谷歌翻译
经典的错误发现率(FDR)控制程序提供了强大而可解释的保证,而它们通常缺乏灵活性。另一方面,最近的机器学习分类算法是基于随机森林(RF)或神经网络(NN)的算法,具有出色的实践表现,但缺乏解释和理论保证。在本文中,我们通过引入新的自适应新颖性检测程序(称为Adadetect)来使这两个相遇。它将多个测试文献的最新作品范围扩展到高维度的范围,尤其是Yang等人的范围。 (2021)。显示AD​​ADETECT既可以强烈控制FDR,又具有在特定意义上模仿甲骨文之一的力量。理论结果,几个基准数据集上的数值实验以及对天体物理数据的应用,我们的方法的兴趣和有效性得到了证明。特别是,虽然可以将AdadEtect与任何分类器结合使用,但它在带有RF的现实世界数据集以及带有NN的图像上特别有效。
translated by 谷歌翻译
我们研究了有限空间中值的静止随机过程的最佳运输。为了反映潜在流程的实向性,我们限制了对固定联轴器的关注,也称为联系。由此产生的最佳连接问题捕获感兴趣过程的长期平均行为的差异。我们介绍了最优联接的估算和最佳的加入成本,我们建立了温和条件下估算器的一致性。此外,在更强的混合假设下,我们为估计的最佳连接成本建立有限样本误差速率,其延伸了IID案件中的最佳已知结果。最后,我们将一致性和速率分析扩展到最佳加入问题的熵惩罚版本。
translated by 谷歌翻译
我们正式化并研究通过嵌入设计凸替代损失函数的自然方法,例如分类,排名或结构化预测等问题。在这种方法中,一个人将每一个有限的预测(例如排名)嵌入$ r^d $中的一个点,将原始损失值分配给这些要点,并以某种方式“凸出”损失以获得替代物。我们在这种方法和多面体(分段线性凸)的替代损失之间建立了牢固的联系:每个离散损失都被一些多面体损失嵌入,并且每个多面体损失都嵌入了一些离散的损失。此外,嵌入会产生一致的链接功能以及线性替代遗憾界限。正如我们用几个示例所说明的那样,我们的结果具有建设性。特别是,我们的框架为文献中各种多面体替代物以及不一致的替代物提供了简洁的证据或不一致的证据,它进一步揭示了这些代理人一致的离散损失。我们继续展示嵌入的其他结构,例如嵌入和匹配贝叶斯风险的等效性以及各种非算术概念的等效性。使用这些结果,我们确定与多面体替代物一起工作时,间接启发是一致性的必要条件也足够了。
translated by 谷歌翻译
在这项工作中,我们研究了数据驱动的决策,并偏离了经典的相同和独立分布(I.I.D.)假设。我们提出了一个新的框架,其中我们将历史样本从未知和不同的分布中产生,我们将其配置为异质环境。假定这些分布位于具有已知半径的异质球中,并围绕(也是)未知的未来(样本外)分布,将评估决策的表现。我们量化了中央数据驱动的策略(例如样本平均近似值,也可以通过速率优势)来量化的渐近性最坏案例遗憾,这是异质性球半径的函数。我们的工作表明,在问题类别和异质性概念的不同组合中,可实现的性能类型的变化很大。我们通过比较广泛研究的数据驱动问题(例如定价,滑雪租赁和新闻顾问)的异质版本来证明框架的多功能性。在途中,我们在数据驱动的决策和分配强大的优化之间建立了新的联系。
translated by 谷歌翻译
在这项工作中,我们调查了Steinke和Zakynthinou(2020)的“条件互信息”(CMI)框架的表现力,以及使用它来提供统一框架,用于在可实现的环境中证明泛化界限。我们首先证明可以使用该框架来表达任何用于从一类界限VC维度输出假设的任何学习算法的非琐碎(但是次优)界限。我们证明了CMI框架在用于学习半个空间的预期风险上产生最佳限制。该结果是我们的一般结果的应用,显示稳定的压缩方案Bousquet al。 (2020)尺寸$ k $有统一有限的命令$ o(k)$。我们进一步表明,适当学习VC类的固有限制与恒定的CMI存在适当的学习者的存在,并且它意味着对Steinke和Zakynthinou(2020)的开放问题的负面分辨率。我们进一步研究了价值最低限度(ERMS)的CMI的级别$ H $,并表明,如果才能使用有界CMI输出所有一致的分类器(版本空间),只有在$ H $具有有界的星号(Hanneke和杨(2015)))。此外,我们证明了一般性的减少,表明“休假”分析通过CMI框架表示。作为推论,我们研究了Haussler等人提出的一包图算法的CMI。 (1994)。更一般地说,我们表明CMI框架是通用的,因为对于每一项一致的算法和数据分布,当且仅当其评估的CMI具有样品的载位增长时,预期的风险就会消失。
translated by 谷歌翻译
我们研究只有历史数据时设计最佳学习和决策制定公式的问题。先前的工作通常承诺要进行特定的数据驱动配方,并随后尝试建立样本外的性能保证。我们以相反的方式采取了相反的方法。我们首先定义一个明智的院子棒,以测量任何数据驱动的公式的质量,然后寻求找到最佳的这种配方。在非正式的情况下,可以看到任何数据驱动的公式可以平衡估计成本与实际成本的接近度的量度,同时保证了样本外的性能水平。考虑到可接受的样本外部性能水平,我们明确地构建了一个数据驱动的配方,该配方比任何其他享有相同样本外部性能的其他配方都更接近真实成本。我们展示了三种不同的样本外绩效制度(超大型制度,指数状态和次指数制度)之间存在,最佳数据驱动配方的性质会经历相变的性质。最佳数据驱动的公式可以解释为超级稳定的公式,在指数方面是一种熵分布在熵上稳健的公式,最后是次指数制度中的方差惩罚公式。这个最终的观察揭示了这三个观察之间的令人惊讶的联系,乍一看似乎是无关的,数据驱动的配方,直到现在仍然隐藏了。
translated by 谷歌翻译
我们研究了使用动力学系统的流量图相对于输入指数的某些置换的函数的近似值。这种不变的功能包括涉及图像任务的经过研究的翻译不变性功能,但还包含许多在科学和工程中找到新兴应用程序的置换不变函数。我们证明了通过受控的模棱两可的动态系统的通用近似的足够条件,可以将其视为具有对称约束的深度残留网络的一般抽象。这些结果不仅意味着用于对称函数近似的各种常用神经网络体系结构的通用近似,而且还指导设计具有近似值保证的架构的设计,以保证涉及新对称要求的应用。
translated by 谷歌翻译
We study a family of adversarial multiclass classification problems and provide equivalent reformulations in terms of: 1) a family of generalized barycenter problems introduced in the paper and 2) a family of multimarginal optimal transport problems where the number of marginals is equal to the number of classes in the original classification problem. These new theoretical results reveal a rich geometric structure of adversarial learning problems in multiclass classification and extend recent results restricted to the binary classification setting. A direct computational implication of our results is that by solving either the barycenter problem and its dual, or the MOT problem and its dual, we can recover the optimal robust classification rule and the optimal adversarial strategy for the original adversarial problem. Examples with synthetic and real data illustrate our results.
translated by 谷歌翻译
We consider the problem of estimating a multivariate function $f_0$ of bounded variation (BV), from noisy observations $y_i = f_0(x_i) + z_i$ made at random design points $x_i \in \mathbb{R}^d$, $i=1,\ldots,n$. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters $\theta_i,\theta_j$ (which estimate the function values $f_0(x_i),f_0(x_j)$) at all neighboring cells $i,j$ in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.
translated by 谷歌翻译
在因果推理和强盗文献中,基于观察数据的线性功能估算线性功能的问题是规范的。我们分析了首先估计治疗效果函数的广泛的两阶段程序,然后使用该数量来估计线性功能。我们证明了此类过程的均方误差上的非反应性上限:这些边界表明,为了获得非反应性最佳程序,应在特定加权$ l^2 $中最大程度地估算治疗效果的误差。 -规范。我们根据该加权规范的约束回归分析了两阶段的程序,并通过匹配非轴突局部局部最小值下限,在有限样品中建立了实例依赖性最优性。这些结果表明,除了取决于渐近效率方差之外,最佳的非质子风险除了取决于样本量支持的最富有函数类别的真实结果函数与其近似类别之间的加权规范距离。
translated by 谷歌翻译