Prateek Jain, Purushottam Kar《Non-convex Optimization for Machine Learning》的总结整理(2)

第二章非凸优化的基本算法
三（2）（接上一排序）、PGD求解非凸问题
对于非凸问题的求解前面已经提到是NP难的，但对于有特殊结构的非凸问题可以很好的求解。主要求解三个方面的问题：1、约束集是非凸的，投影本身是NP难的（因为投影本身是一个非凸优化，见前面投影的定义）但有特殊结构，投影可以很好的处理。例如（稀疏恢复的例子）投影到稀疏向量集， 可以求解（相当于截断），其中
。（推荐系统的例子）投影到低秩矩阵集，可以利用SVD。2、目标函数非凸，但有特殊结构。
第一章中，给出了目标函数是凸的且梯度有界函数的收敛性，以及更进一步地，强凸强光滑函数的收敛性（约束集也是凸的，即凸投影，证明也利用了凸投影的性质）。
当目标函数非凸，但在约束集（凸或非凸都可）上是凸的，或强凸强光滑时，PGD的收敛性。因为约束优化中只考虑约束集上函数的属性即可。

下面给出几个概念：限制凸函数，限制强凸强光滑性，

同样的对于不可微函数用次梯度代替梯度。

RSS，RSC和前面SS，SC的定义一样，只不过限制在约束集上而不是整个定义域。RSS，RSC的定义更general. 而事实证明，实际情况中非凸优化问题的一些目标函数以某种形式满足RSS，RSC，后边的应用中会介绍。
下图很直观的给出了RSS，RSC的例子

gPGD ( generalized projected gradient descent )

算法2和算法1只在约束集上是不一样的，算法1中约束集C是凸的，而2中是非凸的。
给出gPGD求解非凸优化的收敛性分析之前对问题做相应的标记和一定的假设：
1、最优函数值 （与前面的记法一样），最优解 ，（这里相当于真实值）。
2、为了简化证明，假设 （在凸的情况下没有这个假设，因为凸的情况可以利用带约束凸优化的一阶最优性条件），只要目标函数可微，并且最优点x位于约束集内部，该假设就成立。当然，去掉这个假设也是成立的，不过证明会变得复杂。

1、 Th3.3中取固定步长 ，事实上只要 就可以，和Th2.6中的设置一样。
2、 关于Th3.3的证明，定义势函数 （与2.5中一致，2.6中势函数是迭代点和最优点的差 ）
3、 最后得到 ，还是一样先放缩（利用不等式x<exp(x-1)，对任意的x∈R，或者1 - x ≤ exp(-x)）再递推.
4、 Th3.3中对条件数做了假设： 这也是为了简化证明（凸的情况没有该假设）
四、交替极小化（AM）（针对无约束优化问题）
很老的一个算法，但激发了非凸优化的一些新的算法。
AM求解一类有特殊结构的函数优化（前面给出PGD求解两类特殊结构函数），先给出几个相关的概念。
1联合凸(Joint Convexity)，2边缘凸(Marginal Convexity)（类似于边缘概率分布）3边缘强凸强光滑函数就，4边缘最优坐标，5双稳定点

联合凸类似于凸多元函数。

固定一个变量，对另一个变量是凸的（一元凸函数）
对每个变量是边缘凸的，不能推出函数是联合凸的，反之是成立的，例： 非凸函数，但关于单个变量是凸的，在最前面推荐系统的例子中也有类似的例子
这个定义比较好理解


边缘最优相对于单个变量是最优的，但对另外的变量不一定是最优的。


中间的两个优化问题可以根据函数结构采取相应的算法。还可以直接利用梯度下降求解AM中两个优化问题，
AM最终收敛的双稳定点取决于初值的选取。
下面给出AM用在凸优化和特定结构的非凸优化中的收敛性分析。

f是凸的连续可微函数，且边缘强光滑，AM的收敛阶 ，对于凸可微函数，所有的双稳定点都是全局最优。
而对于非凸的情况双稳定点不能保证都是全局最优（甚至不能保证是局部极小点）.

连续可微且边缘凸函数的双稳定点等价于稳定点（一阶最优点），而对于非凸函数，稳定点可以是局部极值点，鞍点。
对函数的性质加一些假设（在后边的应用中有些问题是满足该假设的）.

针对这种特殊性质的函数给出AM求解非凸优化的收敛性分析。

尽管目标函数不具有凸性，但在特殊情况下，AM提供了快速收敛。证明用到了下面C鲁棒双稳定性的结论。

与AM类似的算法是CM（Coordinate Minimization），CM是求解大规模凸优化问题有效的算法.
五、EM 算法（没读/(ㄒoㄒ)/~~，只是很久之前在别的地方读过）

六、随机优化
１、为什么要讨论随机优化？
在更一般的情况讨论非凸问题，对于二次函数 ，当A有负特征值时，求全局最优也是NP难的，退而求其次，求其局部最优也是可以的，随着深度学习的发展，当有足够的数据，即便局部最优解performs quite well. 在这种背景下前面介绍的一些非凸技术如，凸松弛，EM，AM，PGD不能直接应用，（不满足这些technique的条件，或维度特别高，这些technique求解效率不高，或者比如AM中的两个子问题不好求解，PGD中的投影算子不能很好的表示。。。总之前面介绍的算法都太过特殊！！！）所以需要寻求非凸问题的直接求解。求解非凸问题容易陷入鞍点，如何更好的逃离鞍点是比较大的challenge。
类似于前面的算法一样，要求目标函数具有比较好的结构（例如前面讨论过的RSC，RSS，MSC，MSS，LSC，LSS）才可以对非凸问题进行求解。
机器学习信号处理中，很多都是非凸优化问题，例如正交张量分解，这个问题在GMM，HMM，ICA，RL中都会出现。（文中有对正交张量分解的简单介绍）
２、鞍点带来的问题
利用梯度下降求解非凸问题时， ，当梯度消失时，迭代停滞在一阶稳定点（ ）一阶稳定点包括局部最优和鞍点。若函数二次可微，可通过hessian区分鞍点和局部极值点
１） hessian只有正特征值，该点为局部极小
２） hessian只有负特征值，该点位局部极大
３） 既有正的也有负的，该点为鞍点
４） 若有０特征值，为更复杂的鞍点
（与多元函数求极值类似）
而随着问题维数的增加，鞍点数量呈指数增长（一不下心就踩雷），也就是说一阶稳定点大部分都是鞍点。
３、鞍点分类
对于结构比较特别的鞍点，可以很好的解决，因此研究鞍点的结构对其进行分类（捡软柿子捏）

Def６.１假设目标函数二次可微，且在局部极小点是强凸的，则任意一点要么是非稳定点（梯度比较大），要么hessian有一个负特征值，即在该点存在下降方向，要么离局部极小点很近，即局部极小点的近似点。第二类称为严格按点。下图比较直观的描述了严格按点的形状：

下面介绍逃离严格鞍点的算法
４、NGD（Noisy　Gradient　Descent）算法
思想：严格鞍点如上图，不是很稳定，如果把一个球放在上边，给一个扰动就会掉下来，所以在鞍点处给梯度一个扰动来逃离鞍点。

１关于步长的选取，和前面算法１一样，这里取 是为了下面证明的方便，算法实现中可取 。
２加的扰动要保持梯度是无偏的。（书中有简单介绍）
３这里是在GD的基础上进行的改进。
下面给出NGD的收敛性。
假设目标函数１）满足严格按点性（定义６.１）２）β强光滑，３）有界，４）hessian　　　　　　ρ－Lｉｐｓｃｈｉｔｚ连续 （对目标函数的假设有点多。。。这么多有意义吗？其实并没有那么多，╮(╯▽╰)╭，也是有意义的）
５、NGD的收敛性证明
证明比较复杂，前面给了３个lemma，分别对严格鞍点性中出现的三类点进行了分析分别表面：１对于既不是鞍点也不是极小点的临界点，NGD是有效的，可以使函数值下降。
２当迭代点离最优点比较近时，NGD在很多不迭代也不会离最优点太远
３可以逃离严格鞍点
每一种情况中的式子都不是一两下可以推出来的。。。。准备好足够的草稿纸。。。╮(╯▽╰)╭

书中下面又介绍了带约束的，自己看吧。。。
整理了对应的参考文献，这里主要都是基于GD的算法，在另一本书中介绍了随机算法，过段时间更。。。
非凸问题：
早期集中在二阶方法或者拟牛顿法：因为hessian可以区分鞍点和极值点。
【1】Yurii Nesterov and B.T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.
【2】Yann N. Dauphin, Razvan Pascanu, Çaglar Gülçehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS), pages 2933–2941, 2014.
【3】Ruoyu Sun and Zhi-Quan Lu. Guaranteed Matrix Completion via Non-convex Factorization. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2015.
【4】Ya-Xiang Yuan. Recent advances in trust region algorithms. Mathematical Programming, 151(1):249–281, 2015.

一阶方法：
比较高效，但不一定收敛到局部最优。（假设目标函数具有强光滑或限制强光滑）
【5】Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient Descent Only Converges to Minimizers. In Proceedings of the 29th Conference on Learning Theory (COLT), pages 1246–1257, 2016.
表明随机初始化，梯度下降可以避免鞍点。(指数收敛)
对鞍点的结构进行分类，假设非凸函数具有严格鞍点性，
【6】Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition. In Proceedings of The 28th Conference on Learning Theory (COLT), pages 797–842, 2015
【7】Ruoyu Sun and Zhi-Quan Lu. Guaranteed Matrix Completion via Non-convex Factorization. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2015
【8】Efficient approaches for escaping higher order saddle points in non-convex optimization. In Proceedings of the 29th Conference on Learning Theory (COLT), pages 81–102, 2016.
【7】考虑的是二阶方法，【6】表面只要梯度加噪声，一阶方法就可以逃离鞍点，收敛到局部最优
【9】Yuchen Zhang, Percy Liang, and Moses Charikar. A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. In Proceedings of the 30th Conference on Learning Theory, 2017
【9】随机扰动的梯度逃离鞍点用在了更一般的框架，Langevin Dynamics
【8】逃离高阶鞍点
非光滑方法：
前面的算法都会假设目标函数至少是可微的。当假设目标函数是限制光滑的。
【10】Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alexander J. Smola. Fast Stochastic Methods for Nonsmooth Nonconvex Optimization. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
【10】假设目标函数（有限和的形式）是非凸非光滑的，将方差缩减技术用来求解一阶稳定点。
加速优化算法：
【11】Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. “Convex Until Proven Guilty”: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017
【11】利用了nesterov动量加速。
【12】Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding Approximate Local Minima Faster than Gradient Descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2017. 【12】利用的二阶方法
【11】【12】对于一般的非凸函数（不一定是有限和的形式），给出了更快的收敛到鞍点的算法，其中假设目标函数是光滑的。

高维优化：
高维优化很难获得运行时间关于维数是超线性的。PNGD是 ，在中等维数的问题都不能适用。
【13】Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to Escape Saddle Points Efficiently. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1724– 1732, 2017
【13】提出了扰动梯度，（PGD）收敛到二阶稳定点（局部极小）的运行时间关于维数是拟线性的
【11】【12】收敛到鞍点（一阶稳定点）的运行时间关于维数是线性的。

逃离高阶鞍点：（退化鞍点：hessian只有非负特征值）
【8】Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Proceedings of the 29th Conference on Learning Theory (COLT), pages 81–102, 2016
基于【1】的方法提出了逃离更复杂的鞍点。

训练深层网络：
训练深层网络对应非凸优化问题。
训练多层感知器：
【14】Surbhi Goel and Adam Klivans. Learning Depth-Three Neural Networks in Polynomial Time. arXiv:1709.06010v1 [cs.DS], 2017
【15】Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery Guarantees for One-hidden-layer Neural Networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
【16】Yuanzhi Li and Yang Yuan. Convergence Analysis of Two-layer Neural Networks with ReLU Activation. In Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS), 2017

不重叠的卷积神经网络：
【17】Alon Brutzkus and Amir Globerson. Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
【15~17】基于梯度下降的算法，【14】利用保序回归（isotonic regression）和核技术
【16】表明包含恒等映射的网络把训练问题变得well-posed，从而更好求解。