找到模型概率密度的好方法是概率推断的关键。理想的模型应该能够简单地近似于概率,同时也与两个主要操作兼容:两个模型(产品规则)的乘法和相对于随机变量的子集(SUM规则)的边缘化。在这项工作中,我们表明最近提出的非负函数的正半明确(PSD)模型特别适用于此。特别是,我们表征了PSD模型的近似和泛化能力,显示它们享有强烈的理论保证。此外,我们表明我们可以通过矩阵操作以封闭形式的封闭形式有效地执行和产品规则,享受混合模型的相同多功能性。我们的结果为PSD模型应用于密度估计,决策理论和推理的方式开辟了途径。
translated by 谷歌翻译
对于函数的矩阵或凸起的正半明确度(PSD)的形状约束在机器学习和科学的许多应用中起着核心作用,包括公制学习,最佳运输和经济学。然而,存在很少的功能模型,以良好的经验性能和理论担保来强制执行PSD-NESS或凸起。在本文中,我们介绍了用于在PSD锥中的值的函数的内核平方模型,其扩展了最近建议编码非负标量函数的内核平方型号。我们为这类PSD函数提供了一个代表性定理,表明它构成了PSD函数的普遍近似器,并在限定的平等约束的情况下导出特征值界限。然后,我们将结果应用于建模凸起函数,通过执行其Hessian的核心量子表示,并表明可以因此表示任何平滑且强凸的功能。最后,我们说明了我们在PSD矩阵值回归任务中的方法以及标准值凸起回归。
translated by 谷歌翻译
在本文中,我们考虑了基于系数的正则分布回归,该回归旨在从概率措施中回归到复制的内核希尔伯特空间(RKHS)的实现响应(RKHS),该响应将正则化放在系数上,而内核被假定为无限期的。 。该算法涉及两个采样阶段,第一阶段样本由分布组成,第二阶段样品是从这些分布中获得的。全面研究了回归函数的不同规律性范围内算法的渐近行为,并通过整体操作员技术得出学习率。我们在某些温和条件下获得最佳速率,这与单级采样的最小最佳速率相匹配。与文献中分布回归的内核方法相比,所考虑的算法不需要内核是对称的和阳性的半明确仪,因此为设计不确定的内核方法提供了一个简单的范式,从而丰富了分布回归的主题。据我们所知,这是使用不确定核进行分配回归的第一个结果,我们的算法可以改善饱和效果。
translated by 谷歌翻译
We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nystrom approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to extend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector machines. This unified analysis requires developing new proofs, that use different technical tools, such as sub-gaussian inputs, to achieve fast rates. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance.
translated by 谷歌翻译
我们考虑通过复制内核希尔伯特空间的相关协方差操作员对概率分布进行分析。我们表明,冯·诺伊曼(Von Neumann)的熵和这些操作员的相对熵与香农熵和相对熵的通常概念密切相关,并具有许多特性。它们与来自概率分布的各种口径的有效估计算法结合在一起。我们还考虑了产品空间,并表明对于张量产品内核,我们可以定义互信息和联合熵的概念,然后可以完美地表征独立性,但只能部分条件独立。我们最终展示了这些新的相对熵概念如何导致对数分区函数的新上限,这些函数可以与变异推理方法中的凸优化一起使用,从而提供了新的概率推理方法家族。
translated by 谷歌翻译
我们研究基于度量传输的非参数密度估计器的收敛性和相关距离。这些估计量代表了利息的度量,作为传输图下选择的参考分布的推动力,其中地图是通过最大似然目标选择(等效地,将经验性的kullback-leibler损失)或其受惩罚版本选择。我们通过将M估计的技术与基于运输的密度表示的分析性能相结合,为一般惩罚措施估计量的一般类别的措施运输估计器建立了浓度不平等。然后,我们证明了我们的理论对三角形knothe-rosenblatt(kr)在$ d $维单元方面的运输的含义,并表明该估计器的惩罚和未化的版本都达到了Minimax最佳收敛速率,超过了H \ \ \'“较旧的密度类别。具体来说,我们建立了在有限的h \“较旧型球上,未确定的非参数最大似然估计,然后在某些sobolev-penalate的估计器和筛分的小波估计器中建立了最佳速率。
translated by 谷歌翻译
我们研究了非参数脊的最小二乘的学习属性。特别是,我们考虑常见的估计人的估计案例,由比例依赖性内核定义,并专注于规模的作用。这些估计器内插数据,可以显示规模来通过条件号控制其稳定性。我们的分析表明,这是不同的制度,具体取决于样本大小,其尺寸与问题的平滑度之间的相互作用。实际上,当样本大小小于数据维度中的指数时,可以选择比例,以便学习错误减少。随着样本尺寸变大,总体错误停止减小但有趣地可以选择规模,使得噪声引起的差异仍然存在界线。我们的分析结合了概率,具有来自插值理论的许多分析技术。
translated by 谷歌翻译
最大平均差异(MMD)(例如内核Stein差异(KSD))已成为广泛应用的中心,包括假设测试,采样器选择,分布近似和变异推断。在每种情况下,这些基于内核的差异度量都需要(i)(i)将目标p与其他概率度量分开,甚至(ii)控制弱收敛到P。在本文中,我们得出了新的足够和必要的条件,以确保(i) (ii)。对于可分开的度量空间上的MMD,我们表征了那些将BOCHNER嵌入量度分开的内核,并引入了简单条件,以将所有措施用无限的内核分开,并控制与有界内核的收敛。我们在$ \ mathbb {r}^d $上使用这些结果来实质性地扩大了KSD分离和收敛控制的已知条件,并开发了已知的第一个KSD,以恰好将弱收敛到P。我们的假设检验,测量和改善样本质量以及用Stein变异梯度下降进行抽样的结果。
translated by 谷歌翻译
比较概率分布是许多机器学习算法的关键。最大平均差异(MMD)和最佳运输距离(OT)是在过去几年吸引丰富的关注的概率措施之间的两类距离。本文建立了一些条件,可以通过MMD规范控制Wassersein距离。我们的作品受到压缩统计学习(CSL)理论的推动,资源有效的大规模学习的一般框架,其中训练数据总结在单个向量(称为草图)中,该训练数据捕获与所考虑的学习任务相关的信息。在CSL中的现有结果启发,我们介绍了H \“较旧的较低限制的等距属性(H \”较旧的LRIP)并表明这家属性具有有趣的保证对压缩统计学习。基于MMD与Wassersein距离之间的关系,我们通过引入和研究学习任务的Wassersein可读性的概念来提供压缩统计学习的保证,即概率分布之间的某些特定于特定的特定度量,可以由Wassersein界定距离。
translated by 谷歌翻译
三角形流量,也称为kn \“{o}的Rosenblatt测量耦合,包括用于生成建模和密度估计的归一化流模型的重要构建块,包括诸如实值的非体积保存变换模型的流行自回归流模型(真实的NVP)。我们提出了三角形流量统计模型的统计保证和样本复杂性界限。特别是,我们建立了KN的统计一致性和kullback-leibler估算器的rospblatt的kullback-leibler估计的有限样本会聚率使用实证过程理论的工具测量耦合。我们的结果突出了三角形流动下播放功能类的各向异性几何形状,优化坐标排序,并导致雅各比比流动的统计保证。我们对合成数据进行数值实验,以说明我们理论发现的实际意义。
translated by 谷歌翻译
We consider the problem of estimating the optimal transport map between a (fixed) source distribution $P$ and an unknown target distribution $Q$, based on samples from $Q$. The estimation of such optimal transport maps has become increasingly relevant in modern statistical applications, such as generative modeling. At present, estimation rates are only known in a few settings (e.g. when $P$ and $Q$ have densities bounded above and below and when the transport map lies in a H\"older class), which are often not reflected in practice. We present a unified methodology for obtaining rates of estimation of optimal transport maps in general function spaces. Our assumptions are significantly weaker than those appearing in the literature: we require only that the source measure $P$ satisfies a Poincar\'e inequality and that the optimal map be the gradient of a smooth convex function that lies in a space whose metric entropy can be controlled. As a special case, we recover known estimation rates for bounded densities and H\"older transport maps, but also obtain nearly sharp results in many settings not covered by prior work. For example, we provide the first statistical rates of estimation when $P$ is the normal distribution and the transport map is given by an infinite-width shallow neural network.
translated by 谷歌翻译
Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency.
translated by 谷歌翻译
对于高维和非参数统计模型,速率最优估计器平衡平方偏差和方差是一种常见的现象。虽然这种平衡被广泛观察到,但很少知道是否存在可以避免偏差和方差之间的权衡的方法。我们提出了一般的策略,以获得对任何估计方差的下限,偏差小于预先限定的界限。这表明偏差差异折衷的程度是不可避免的,并且允许量化不服从其的方法的性能损失。该方法基于许多抽象的下限,用于涉及关于不同概率措施的预期变化以及诸如Kullback-Leibler或Chi-Sque-diversence的信息措施的变化。其中一些不平等依赖于信息矩阵的新概念。在该物品的第二部分中,将抽象的下限应用于几种统计模型,包括高斯白噪声模型,边界估计问题,高斯序列模型和高维线性回归模型。对于这些特定的统计应用,发生不同类型的偏差差异发生,其实力变化很大。对于高斯白噪声模型中集成平方偏置和集成方差之间的权衡,我们将较低界限的一般策略与减少技术相结合。这允许我们将原始问题与估计的估计器中的偏差折衷联动,以更简单的统计模型中具有额外的对称性属性。在高斯序列模型中,发生偏差差异的不同相位转换。虽然偏差和方差之间存在非平凡的相互作用,但是平方偏差的速率和方差不必平衡以实现最小估计速率。
translated by 谷歌翻译
在机器学习或统计中,通常希望减少高维空间$ \ mathbb {r} ^ d $的数据点样本的维度。本文介绍了一种维度还原方法,其中嵌入坐标是作为半定程序无限尺寸模拟的溶液获得的正半定核的特征向量。这种嵌入是自适应和非线性的。我们对学习内核的弱者和强烈的平滑假设讨论了这个问题。我们的方法的主要特点是在两种情况下存在嵌入坐标的样本延伸公式。该外推公式产生内核矩阵的延伸到数据相关的Mercer内核功能。我们的经验结果表明,与光谱嵌入方法相比,该嵌入方法对异常值的影响更加稳健。
translated by 谷歌翻译
我们提出和研究内核偶联梯度方法(KCGM),并在可分离的希尔伯特空间上进行最小二乘回归的随机投影。考虑两种类型的随机草图和nyStr \“ {o} m子采样产生的随机投影,我们在适当的停止规则下证明了有关算法的规范变体的最佳统计结果。尤其是我们的结果表明,如果投影维度显示了投影维度与问题的有效维度成正比,带有随机草图的KCGM可以最佳地概括,同时获得计算优势。作为推论,我们在良好条件方面的经典KCGM得出了最佳的经典KCGM,因为目标函数可能不会不会在假设空间中。
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 谷歌翻译
内核平均值嵌入是一种强大的工具,可以代表任意空间上的概率分布作为希尔伯特空间中的单个点。然而,计算和存储此类嵌入的成本禁止其在大规模设置中的直接使用。我们提出了一个基于NyStr \“ Om方法的有效近似过程,该过程利用了数据集的一个小随机子集。我们的主要结果是该过程的近似误差的上限。它在子样本大小上产生足够的条件以获得足够的条件。降低计算成本的同时,标准的$ n^{ - 1/2} $。我们讨论了此结果的应用,以近似的最大平均差异和正交规则,并通过数值实验说明了我们的理论发现。
translated by 谷歌翻译
我们在具有Martingale差异噪声的可实现的时间序列框架中学习正方形损失。我们的主要结果是一个快速率的多余风险结合,这表明每当轨迹超收缩条件成立时,依赖数据的最小二乘估计器的风险与燃烧时间后的IID速率订单匹配。相比之下,从依赖数据中学习的许多现有结果都具有有效的样本量,即使在燃烧时间之后,有效的样本量也被基础过程的混合时间降低。此外,我们的结果允许协变量过程表现出远距离相关性,这些相关性大大弱于几何牙齿。我们将这种现象学习称为几乎没有混合的方式,并为其示出了几个示例:$ l^2 $和$ l^{2+\ epsilon} $ norms的有界函数类是等效的,有限的有限态Markov链,各种参数模型,以及一个无限尺寸$ \ ell^2(\ mathbb {n})$椭圆形的广阔家族。通过将我们的主要结果实例化,以使用广义线性模型过渡对非线性动力学的系统识别,我们仅在多项式燃烧时间后获得了几乎最小的最佳超量风险。
translated by 谷歌翻译
我们介绍内核变薄,更有效地压缩了一个新的程序,而不是i.i.d. \采样或标准变薄。给定合适的再现内核$ \ mathbf {k} $和$ \ mathcal {o}(n ^ 2)$ time,内核变薄将$ n $ thepoint近似压缩为$ \ mathbb {p} $ to to $ \ sqrt {n} $ - 点近似与相关的再现内核希尔伯特空间相比的可比最坏情况集成错误。具有高概率,集成错误中的最大差异是$ \ mathcal {o} _d(n ^ { - 1/2} \ sqrt {\ log n})$,用于紧凑地支持$ \ mathbb {p} $和$ \ mathcal {o} _d(n ^ { - \ frac {1} {2}}(\ log n)^ {(d + 1)/ 2} \ sqrt {\ log \ log n})$ for子指数$ \ $ \ mathbb {r} ^ d $上的mathbb {p} $。相反,来自$ \ mathbb {p} $ \ oomega(n ^ { - 1/4})$ Integration错误的平等大小。我们的子指数保证类似于统一$ \ mathbb {p} $ on $ [0,1] ^ d $的典型准蒙特卡洛错误速率,但适用于$ \ mathbb {r} ^ d $和a的常规发行版广泛的常见内核。我们使用我们的结果推导出Gaussian,Mat \'ern和B样曲线内部的显式非渐近最大平均差异界限,并提出了两个渐晕,说明了内核变薄的实际益处,而\采样和标准马尔可夫链蒙特卡罗稀疏,尺寸$ d = 2美元到100美元。
translated by 谷歌翻译
确定点过程(DPP)是排斥点模式的统计模型。取样和推理都是DPPS的易用,这是具有负依赖性的模型中的罕见特征,解释了他们在机器学习和空间统计中的普及。已经在有限情况下提出了参数和非参数推断方法,即当点模式生活在有限的地面集中时。在连续的情况下,只有研究参数方法,而DPPS的非参数最大可能性 - 追踪课程运算符的优化问题 - 仍然是一个打开的问题。在本文中,我们表明,这种最大可能性(MLE)问题的受限制版本落入了RKHS中的非负面函数的最新代表定理的范围内。这导致有限的尺寸问题,具有强大的统计关系到原始MLE。此外,我们提出,分析,并展示了解决这个有限尺寸问题的定点算法。最后,我们还提供了对DPP的相关核的受控估计,从而提供更多的解释性。
translated by 谷歌翻译