Projection-free optimization via different variants of the Frank-Wolfe (FW),
a.k.a. Conditional Gradient method has become one of the cornerstones in
optimization for machine learning since in many cases the linear minimization
oracle is much cheaper to implement than projections and some sparsity needs to
be preserved. In a number of applications, e.g. Poisson inverse problems or
quantum state tomography, the loss is given by a self-concordant (SC) function
having unbounded curvature, implying absence of theoretical guarantees for the
existing FW methods. We use the theory of SC functions to provide a new
adaptive step size for FW methods and prove global convergence rate O(1/k)
after k iterations. If the problem admits a stronger local linear minimization
oracle, we construct a novel FW method with linear convergence rate for SC
functions.

通过理论建立不同变体的 Frank-Wolfe（FW）算法的自适应步长，对一些机器学习及物理学问题，能够得到无需映射和保留稀疏性的优化，且对于具有无限曲率的自共轭函数，也可以获得全局收敛速率为 O (1/k) 或线性收敛速率的新的 FW 方法。

Frank-Wolfe 算法的自共轭分析

Self-Concordant Analysis of Frank-Wolfe Algorithms

We propose a variable metric framework for minimizing the sum of a
self-concordant function and a possibly non-smooth convex function, endowed
with an easily computable proximal operator. We theoretically establish the
convergence of our framework without relying on the usual Lipschitz gradient
assumption on the smooth part. An important highlight of our work is a new set
of analytic step-size selection and correction procedures based on the
structure of the problem. We describe concrete algorithmic instances of our
framework for several interesting applications and demonstrate them numerically
on both synthetic and real data.

本文提出了基于可变度量的框架，针对自共轭（self-concordant）函数和可能非平滑凸函数之和的问题，提出了一种易于计算的近端算子。通过利用问题的结构，本文建立了分析式的步长选择和校正过程，并在几个有趣的应用上展示了这一框架的具体算法实例和其在合成数据和真实数据上的数值结果。