2020/02/17 by Deyi Liu, Volkan Cevher, Liu, Deyi +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2002.07003
openalex publication_date 2020/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(ε-ν) 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.