  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}(\epsilon^{-\nu})$ LMO's, where
$\epsilon$ is the desired accuracy and $\nu:= 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.
