一种适应性二阶方法用于非凸非光滑复合优化问题
内容提要
本文提出了多种优化算法，解决非凸和非光滑的机器学习问题，包括近似正则化路径追踪、BFGS方法的扩展和随机拟牛顿方法。这些算法展示了全局收敛性和高效性，能够有效利用曲率信息，优化样本复杂度，适用于深度学习等领域。
延伸解读
非凸非光滑优化的算法全景
文章汇总了多种针对非凸非光滑问题的优化算法，包括近似正则化路径追踪、subBFGS、随机拟牛顿、迭代重加权l1、条件梯度与ADMM、显式L1最小二乘算法、立方正则化牛顿法以及分布式二阶方法。这些算法分别从路径追踪、拟牛顿、随机优化、正则化、分布式计算等角度切入，共同展示了该领域在全局收敛性、迭代复杂度和样本复杂度方面的研究进展。
曲率信息的利用与逃离鞍点
多篇工作强调利用曲率信息提升优化效率。例如，基于牛顿方法的算法能更好地逃离平坦区域和鞍点，并在泛化性能上媲美或优于手动调参的随机梯度下降；立方正则化牛顿法在一致凸目标上具有线性收敛率，且全局迭代复杂度优于梯度法。这表明二阶信息在处理非凸机器学习问题时具有独特优势。
随机与分布式优化的效率突破
针对大规模问题，文章介绍了随机拟牛顿方法和分布式二阶算法。随机拟牛顿通过梯度剪切和方差减小达到O(ε^(-3))样本复杂度，并可通过超参数调节加速收敛；分布式算法使用逐步二次逼近，在非强凸问题上具有全局线性收敛性和低通信复杂度，初步实验显示在凸问题上显著优于现有方法。这些进展有助于推动深度学习等应用。
稀疏正则化与鞍点性质
文章探讨了l_p正则化的严格鞍点性质，并提出迭代重加权的l1算法求解l_p正则化问题。该算法只能收敛到局部极小值点，但严格鞍点性质在稀疏优化中普遍存在，且分析可扩展到一般非凸正则化。此外，显式算法处理不可分离L1项时具有1/N收敛速率，并可推广到其他凸非分离度量。
Q&A
什么是近似正则化路径追踪方法？
近似正则化路径追踪方法用于求解非凸学习问题，具有与全正则化路径相同的迭代复杂度，并能实现全局几何收敛。
subBFGS算法的主要特点是什么？
subBFGS算法是BFGS拟牛顿方法的扩展，适用于非平滑凸目标的优化，具有全局收敛性。
随机拟牛顿方法如何优化样本复杂度？
随机拟牛顿方法通过梯度剪切和方差减小，实现了O(ε^(-3))的样本复杂度，并通过超参数调节加速收敛。
如何处理带有不可分离L1项的优化问题？
提出了一种显式算法，通过四个矩阵向量乘法和简单投影来最小化带有不可分离L1项的L1正则化最小二乘函数。
立方正则化牛顿法的收敛性如何？
立方正则化牛顿法在一致凸性目标的复合最小化问题中具有线性收敛率，证明了其迭代复杂度优于梯度法。
分布式优化算法的优势是什么？
分布式优化算法在解决具有非平滑正则化项的ERM问题时，具有全局线性收敛性和低通信复杂度，适用于广泛的非强凸问题。
