论文标题
Frank-Wolfe算法的广义自我符合分析
Generalized Self-Concordant Analysis of Frank-Wolfe algorithms
论文作者
论文摘要
通过Frank-Wolfe（FW）方法的不同变体的无投影优化已成为机器学习和计算统计的大规模优化基石之一。这些字段中的大量应用涉及具有自我符合属性的函数的最小化。这种广义的自我符合（GSC）函数不一定具有Lipschitz连续梯度，也不强烈凸出。确实，在许多应用中，例如逆协方差估计或支持向量机器中的距离加权歧视问题，损失是由具有无限曲率的GSC函数给出的，这意味着现有FW方法缺乏理论保证。本文通过开发具有标准O（1/K）收敛速率保证的可证明收敛的FW算法来缩小文献中的明显差距。如果问题公式允许有效地构建局部线性最小化的甲骨文，我们将开发具有线性收敛速率的FW方法。
Projection-free optimization via different variants of the Frank-Wolfe (FW) method has become one of the cornerstones in large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant (GSC) functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex. Indeed, in a number of applications, e.g. inverse covariance estimation or distance-weighted discrimination problems in support vector machines, the loss is given by a GSC function having unbounded curvature, implying absence of theoretical guarantees for the existing FW methods. This paper closes this apparent gap in the literature by developing provably convergent FW algorithms with standard O(1/k) convergence rate guarantees. If the problem formulation allows the efficient construction of a local linear minimization oracle, we develop a FW method with linear convergence rate.
