# A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization

arXiv: https://arxiv.org/abs/2002.07003 · HTML: https://mlsanity.com/paper/2002.07003/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 4 of 4)

- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems](https://mlsanity.com/paper/2407.03294/) (2024)

## Abstract (arXiv)

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 O(ε-nu) LMO's, where ε 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.