On the Optimization Landscape of Tensor Decompositions
Rong Ge Duke University, Computer Science Department, email: Tengyu Ma Princeton University, Computer Science Department, email:
Abstract
Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape of many objective functions in learning has been conjectured to have the geometric property that “all local optima are (approximately) global optima”, and thus they can be solved efficiently by local search algorithms. However, establishing such property can be very difficult.
中文速览
随机过完备张量（over-complete tensor）的分解在无监督学习中极为重要，但理论上属于NP难问题，人们一直不清楚为什么梯度上升等局部搜索方法在实践中能奏效。这篇论文通过分析该问题的优化地形（optimization landscape），证明了一个关键结论：在函数值略高于随机初始化期望值的"超水平集"区域内，所有局部极大值都近似等于真实分量，不存在会让算法"卡住"的虚假局部极大值。技术上，作者首次将Kac-Rice公式（一种对流形上特殊点计数的工具）成功应用于具有复杂依赖结构的高次随机多项式，并结合随机矩阵理论对不同区域分别估计局部极大值的数量。这一结果意味着，哪怕初始点只比随机猜测稍好一点点，梯度上升算法就能在多项式时间内可靠地恢复张量的真实成分，从理论上为过完备张量分解的实际有效性提供了迄今最强的保障。
原文 arXiv:1706.05598;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1706.05598v1