提出隐式高阶矩计算方法,实现多项式时间学习混合线性回归等模型。
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
- 设计隐式矩张量计算框架,突破高阶矩不可行的瓶颈
- 首次实现多项式时间学习混合线性回归与球形高斯混合模型
- 适用于带正则化激活函数的组合模型,对误差敏感度可控
我们研究潜变量模型的学习问题。常用方法是矩法,但非常数阶矩张量无法在多项式时间内写出。为解决此问题,我们提出一种通用高效的隐式矩张量计算算法。该框架推广了~\cite{LL21-opt} 的工作,后者针对球形高斯混合聚类中的特定矩张量提出了高效算法。利用我们的隐式矩估计算法,首次获得了以下模型的多项式时间学习算法:* 混合线性回归:在误差 $ε$ 下,时间为 $\mathrm{poly}(d, k, 1/ε)$;* 球形高斯混合:密度估计下,当均值位于半径 $O(\sqrt{\log k})$ 的球内时,时间为 $\mathrm{poly}(d, k, 1/ε)$(总变差误差);参数估计在最优均值分离 $Ω(\log^{1/2}(k/ε))$ 下,时间为 $\mathrm{poly}(d, k, 1/ε)$;* 正线性组合非线性激活函数:算法复杂度为 $\mathrm{poly}(d, k) g(ε)$,其中 $g$ 依赖于目标函数类的 Hermite 浓度;对 ReLU 组合,复杂度为 $\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/ε)}$。
原文摘要 · Abstract (English)
We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by the fact that the moment tensors of super-constant degree cannot even be written down in polynomial time. Motivated by such learning applications, we develop a general efficient algorithm for {\em implicit moment tensor computation}. Our framework generalizes the work of~\cite{LL21-opt} which developed an efficient algorithm for the specific moment tensors that arise in clustering mixtures of spherical Gaussians. By leveraging our implicit moment estimation algorithm, we obtain the first $\mathrm{poly}(d, k)$-time learning algorithms for the following models. * {\bf Mixtures of Linear Regressions} We give a $\mathrm{poly}(d, k, 1/ε)$-time algorithm for this task, where $ε$ is the desired error. * {\bf Mixtures of Spherical Gaussians} For density estimation, we give a $\mathrm{poly}(d, k, 1/ε)$-time learning algorithm, where $ε$ is the desired total variation error, under the condition that the means lie in a ball of radius $O(\sqrt{\log k})$. For parameter estimation, we give a $\mathrm{poly}(d, k, 1/ε)$-time algorithm under the {\em optimal} mean separation of $Ω(\log^{1/2}(k/ε))$. * {\bf Positive Linear Combinations of Non-Linear Activations} We give a general algorithm for this task with complexity $\mathrm{poly}(d, k) g(ε)$, where $ε$ is the desired error and the function $g$ depends on the Hermite concentration of the target class of functions. Specifically, for positive linear combinations of ReLU activations, our algorithm has complexity $\mathrm{poly}(d, k) 2^{\mathrm{poly}(1/ε)}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。