论文标题
牛顿弗兰克·沃尔夫（Newton Frank-Wolfe）方法，用于限制自信的最小化
A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
论文作者
论文摘要
我们演示了如何使用线性最小化的甲环（LMO）在约束集上稳定地解决一类约束的自我符合最小化问题。我们证明，我们方法的LMO调用数量几乎与L-Smooth Case中Frank-Wolfe方法相同。具体来说，我们的牛顿弗兰克 - 沃尔夫方法使用$ \ mathcal {o}（ε^{ - ν}）$ lmo's，其中$ε$是所需的准确性，$ν：= 1 + o（1）$。此外，我们演示了我们的算法如何利用基于LMO的方案的改进变体，包括客场，以达到线性收敛速率。我们还提供具有竞争比率，D-最佳实验设计和逻辑回归的投资组合设计的数值证据，其中牛顿弗兰克·沃尔夫（Newton Frank-Wolfe）的表现优于最先进的弹性网。
We demonstrate how to scalably solve a class of constrained self-concordant minimization problems using linear minimization oracles (LMO) over the constraint set. We prove that the number of LMO calls of our method is nearly the same as that of the Frank-Wolfe method in the L-smooth case. Specifically, our Newton Frank-Wolfe method uses $\mathcal{O}(ε^{-ν})$ LMO's, where $ε$ is the desired accuracy and $ν:= 1 + o(1)$. In addition, we demonstrate how our algorithm can exploit the improved variants of the LMO-based schemes, including away-steps, to attain linear convergence rates. We also provide numerical evidence with portfolio design with the competitive ratio, D-optimal experimental design, and logistic regression with the elastic net where Newton Frank-Wolfe outperforms the state-of-the-art.
