The Second Order Linear Model
The Second Order Linear Model
复制标题
二阶线性模型
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Jieping Ye
中科院分区：
文献类型：
--
作者：
Ming Lin;Shuang Qiu;Bin Hong;Jieping Ye
我们研究了一类基本的回归模型，称为二阶线性模型(SLM)。SLM将线性模型推广到高阶函数空间，近年来引起了广泛的研究兴趣。然而，由于传统的梯度下降学习框架的一些基本局限性，如何在完全通用的情况下使用非凸求解器有效地学习SLM仍然是一个悬而未决的问题。在这项研究中，我们试图从一种无梯度的方法来解决这个问题，我们称之为矩估计序列(MES)方法。我们表明，传统的梯度下降启发式算法受到分布的偏斜性的影响，因此不再是学习SLM的最佳实践。基于MES框架，我们设计了一个非凸交替迭代过程，在$O(Kd)$内存和数据集的一次通过内训练$d$维排序-$k$SLM。在检索$O[k^{2}dcdotmathm{PolyLog}(kd/epsilon)]$样本后，该方法具有全局收敛和线性收敛的特点，并实现了$epsilon$恢复误差。此外，我们的理论分析表明，并不是所有的SLM都可以在每个亚高斯分布上学习。当样本来自所谓的$au$-MIP分布时，SLM可以通过$O(p/au^{2})$样本学习，其中$p$和$au$是取决于分布的偏度和峰度的正常数。对于非MIP分布，附加对角线自由预言是保证SLM可学习的必要条件和充分条件。数值模拟验证了我们的算法在采样复杂度和线性收敛速度方面的界的敏锐性。
We study a fundamental class of regression models called the second order linear model (SLM). The SLM extends the linear model to high order functional space and has attracted considerable research interest recently. Yet how to efficiently learn the SLM under full generality using nonconvex solver still remains an open question due to several fundamental limitations of the conventional gradient descent learning framework. In this study, we try to attack this problem from a gradient-free approach which we call the moment-estimation-sequence (MES) method. We show that the conventional gradient descent heuristic is biased by the skewness of the distribution therefore is no longer the best practice of learning the SLM. Based on the MES framework, we design a nonconvex alternating iteration process to train a $d$-dimension rank-$k$ SLM within $O(kd)$ memory and one-pass of the dataset. The proposed method converges globally and linearly, achieves $epsilon$ recovery error after retrieving $O[k^{2}dcdotmathrm{polylog}(kd/epsilon)]$ samples. Furthermore, our theoretical analysis reveals that not all SLMs can be learned on every sub-gaussian distribution. When the instances are sampled from a so-called $ au$-MIP distribution, the SLM can be learned by $O(p/ au^{2})$ samples where $p$ and $ au$ are positive constants depending on the skewness and kurtosis of the distribution. For non-MIP distribution, an addition diagonal-free oracle is necessary and sufficient to guarantee the learnability of the SLM. Numerical simulations verify the sharpness of our bounds on the sampling complexity and the linear convergence rate of our algorithm.
影响因子：
4.300
作者：
Hagar Ibrahim Labouta;Labiba K. El-Khordagui
通讯作者：
Labiba K. El-Khordagui