NIPSAug, 2018

在线主成分估计和全局收敛的扩散近似

PDF
TL;DR本文提出采用扩散近似工具研究 Oja 迭代的动态特性，它是一种用于数据流中的在线随机梯度下降方法。我们使用扩散近似和弱收敛工具将 Oja 迭代特征为三个阶段，进而为其提供有限样本误差界限。
diffusion approximationoja's iterationstochastic gradient descentmarkov chainprincipal component analysis
发现论文，激发创造
  • 在线主成分估计的近最优随机逼近

    本文将在线 PCA 转化为随机非凸优化问题，并将在线 PCA 算法分析为随机逼近迭代。在亚高斯假设下，我们证明了在线 PCA 算法的近乎最优有限样本误差界限，并且表明有限样本误差界限与极小信息下界紧密匹配。

    Mar, 2016

  • 随机梯度下降半群与在线主成分分析：性质和扩散近似

    该文研究了机器学习中两个重要算法的 Markov 半群：随机梯度下降和在线主成分分析，通过讨论其性质，证明了这些 semigroups 可以逼近 SGD（在线 PCA）。

    Dec, 2017

  • 流式 k-PCA 的第一个高效收敛：全局无间隙，近乎最优速率

    本研究研究了流式主成分分析，并提出了 Oja 算法的全局收敛，同时提供了一个修改后的变体 Oja++，可以比 Oja 更快地运行。

    Jul, 2016

  • 用于高速流式主成分分析的分布式随机算法

    本文探讨了在流式数据下，从独立同分布的数据采样中估算协方差矩阵的主特征向量的问题，并提出和分析了一种分布式变体方案 D-Krasulina，该方案可以在多个处理节点上分布计算负载以跟上高数据流率。通过对该方案的分析表明，在适当的条件下，D-Krasulina 以次序优化的方式收敛于主特征向量，即在接收到所有节点的 M 个采样后，其估算误差可以是 O (1/M)。最后，通过对合成和真实世界数据的实验验证了 D-Krasulina 和 DM-Krasulina 在高速数据流场景中的收敛行为。

    Jan, 2020

  • 随机梯度下降法在 PCA 中的收敛性

    本文针对主成分分析问题在流式随机场景中进行探讨和研究，给出了针对性的随机梯度下降算法，提供了最新的无需基于非平凡特征值间隙假设的收敛保证，并改进了在该假设下的优化算法保证效果。

    Sep, 2015

  • 高维稀疏 PCA 的在线学习：精确动态和相变

    研究基于在线 PCA 和逐元素非线性的算法对于稀疏主特征向量的学习，证明其在高维极限下收敛于确定性的，尺度测度过程，同时证明在稀疏支持恢复中有良好的表现，并通过非线性 PDE 的稳态分析揭示了有趣的相变现象。

    Sep, 2016

  • 通过扩散逼近对随机梯度下降算法进行时间均匀性弱误差分析

    本文介绍一种新的方法来扩展了扩散逼近的有效性，使得可以利用此方法对强凸目标函数的常步长随机梯度下降算法进行渐进行为的表征，从而使得扩散逼近的适用范围更广、更深入涵盖了数据科学中随机优化算法的应用。

    Feb, 2019

  • 用于马尔可夫数据的流式主成分分析

    研究了数据点从无法分解的 Markov 链中采样的流式主成分分析（PCA）问题，提出了一个新的算法并证明了其收敛速率，解决了使用 MCMC 算法从链的稳态分布中采样的问题。

    May, 2023

  • 分布式随机主成分分析的通信效率算法

    在统计分布设置中，研究了 PCA 的基本问题，介绍了一种在计算效率和估计误差方面都优于局部 ERM 解决方案的算法，通过进行简单的校正步骤来消除误差并提供一种估计器，还介绍了一种使用分布式矩阵向量乘法的迭代分布式算法，提供在广泛的参数范围内通信轮次的显着加速。

    Feb, 2017

  • 流式 PCA：匹配矩阵伯恩斯坦和 Oja 算法的几乎最优有限样本保证

    该研究提出了一个对流式主成分分析（PCA）有改进保证的线性时间算法，该算法可以在常数精度下估计协方差矩阵的前几个特征向量。该算法通过一种新颖的 Oja 算法分析方法实现。

    Feb, 2016