广义自共轭函数:牛顿类型方法的配方
我们引入自协调平滑的概念,用于最小化两个凸函数的和:第一个是光滑的函数,第二个可以是不光滑的函数。我们的方法自然地从称为部分平滑的平滑近似技术中得出。我们的方法的重点在于所得问题结构的自然特性,它为我们提供了一个变量度量选择方法和一条特别适合于近端牛顿类型算法的步长选择规则。另外,我们有效地处理不光滑函数推动的特定结构,例如 L1 正则化和组套索惩罚。我们证明了两种算法的局部二次收敛速度:Prox-N-SCORE,即近端牛顿算法和 Prox-GGN-SCORE,即近端广义高斯牛顿(GGN)算法。Prox-GGN-SCORE 算法突出了一种较为重要的近似过程,有助于显著降低与逆 Hessian 相关的大部分计算开销。此近似过程对于超参数机器学习模型和小批量设置非常有用。对合成数据集和真实数据集的数值实验证明了我们方法的效率和优越性。
Sep, 2023
研究了带有准自共轭平滑成分的复合凸优化问题,通过使用基本的牛顿法结合梯度正则化,提出了一种简单而高效的算法,并应用于多个实际问题,包括逻辑回归、软最大和矩阵缩放,无需对目标函数进行额外的假设,并且获得了快速全局线性收敛率。
Aug, 2023
本文提出了基于可变度量的框架,针对自共轭(self-concordant)函数和可能非平滑凸函数之和的问题,提出了一种易于计算的近端算子。通过利用问题的结构,本文建立了分析式的步长选择和校正过程,并在几个有趣的应用上展示了这一框架的具体算法实例和其在合成数据和真实数据上的数值结果。
Aug, 2013
该研究提出了一种随机化的二阶优化方法 ——Newton Sketch,使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数,该算法证明具有超线性收敛和指数高概率,与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化,即使在没有自共轭的情况下,也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序,带有凸约束的二次程序,逻辑回归和其他广义线性模型以及半定规划的扩展问题。
May, 2015
该研究广义化了牛顿型方法以处理光滑函数的最小化,特别是一个包含简单近端映射的凸函数和一个非光滑函数的总和,在此基础上提出了近端牛顿型方法。研究表明,该方法即使在计算搜索方向不精确时,也能继承用于最小化光滑函数的牛顿型方法的理想收敛性质。该方法是许多针对生物信息学、信号处理和统计学习等问题量身定制的流行方法的特例,并且分析结果为其中一些方法提供了新的收敛结果。
Jun, 2012
证明了牛顿法对于具有稳定 Hessians 的目标函数具有全局收敛的线性速度,在这一类问题中包括了许多不是强凸的函数,如逻辑回归,相比于仅在类似条件下实现次线性 $O(1/t^2)$ 收敛率的一阶方法,我们的线性收敛结果是(i)仿射不变的,即使使用(ii)近似海森和(iii)仅近似解决子问题。
Jun, 2018
通过研究不具有假局部最小值 (即不是全局最小值的局部最小值) 的连续函数集,即全局函数,以分析非凸、非光滑优化问题,并证明了一些张量分解问题可以被视为全局函数,并提供了广泛使用的 $l_1$ 范数用于避免非凸优化点的理论保证。
May, 2018
该研究论文探讨了如何使用凸优化方法和自协调函数对正方形误差和逻辑损失进行理论分析,并将这些方法应用于逻辑回归中,通过结果表明二元分类的新结果可以从最小二乘回归中轻松衍生。
Oct, 2009
本文提出了增量 Newton 方法和梯度增长条件,通过实例研究,发现增量 Newton 方法需要满足梯度增长条件才能达到线性收敛率,进而得到了分布式优化方法的线性收敛率结果。
Oct, 2014