Generalized self-concordant analysis of Frank-Wolfe algorithms

• 成果类型: Article
• 署名作者: Dvurechensky, Pavel; Safin, Kamil; Shtern, Shimrit; Staudigl, Mathias
• 署名单位: Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Moscow Institute of Physics & Technology; Technion Israel Institute of Technology; Maastricht University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01771-1
• 发表日期: 2023
• 页码: 255-323
• 关键词: gradient-method; convex; CONVERGENCE; complexity

摘要

Projection-free optimization via different variants of the Frank-Wolfe method has become one of the cornerstones of 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 functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex, making them a challenging class of functions for first-order methods. Indeed, in a number of applications, such as inverse covariance estimation or distance-weighted discrimination problems in binary classification, the loss is given by a generalized self-concordant function having potentially unbounded curvature. For such problems projection-free minimization methods have no theoretical convergence guarantee. This paper closes this apparent gap in the literature by developing provably convergent Frank-Wolfe algorithms with standard O(1/k) convergence rate guarantees. Based on these new insights, we show how these sublinearly convergent methods can be accelerated to yield linearly convergent projection-free methods, by either relying on the availability of a local liner minimization oracle, or a suitable modification of the away-step Frank-Wolfe method.