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.

该论文介绍了投影法优化的一些缺陷，提出了一种基于 Frank-Wolfe 方法的更好优化算法，支持大规模优化，并适用于非凸函数。

Frank-Wolfe 算法的广义自共轭分析

Generalized Self-Concordant Analysis of Frank-Wolfe algorithms

We propose a variable decomposition algorithm -greedy block coordinate
descent (GBCD)- in order to make dense Gaussian process regression practical
for large scale problems. GBCD breaks a large scale optimization into a series
of small sub-problems. The challenge in variable decomposition algorithms is
the identification of a subproblem (the active set of variables) that yields
the largest improvement. We analyze the limitations of existing methods and
cast the active set selection into a zero-norm constrained optimization problem
that we solve using greedy methods. By directly estimating the decrease in the
objective function, we obtain not only efficient approximate solutions for
GBCD, but we are also able to demonstrate that the method is globally
convergent. Empirical comparisons against competing dense methods like
Conjugate Gradient or SMO show that GBCD is an order of magnitude faster.
Comparisons against sparse GP methods show that GBCD is both accurate and
capable of handling datasets of 100,000 samples or more.

通过提出变量分解算法 - greedy block coordinate descent（GBCD）-，我们将密集高斯过程回归变得实用，解决了现有方法的局限性，并将主动集选择转化为零规范约束优化问题，使用贪心方法求解，进而在实证比较中证明了 GBCD 具有全局收敛的能力并且比竞争算法更快、更准确。