An Away-Step Frank-Wolfe Method for Minimizing Logarithmically-Homogeneous Barriers

We present and analyze a new away-step Frank-Wolfe method for the convex optimization problem ${\min}_{x\in\mathcal{X}} \; f(\mathsf{A} x) + \langle{c},{x}\rangle$, where $f$ is a $\theta$-logarithmically-homogeneous self-concordant barrier, $\mathsf{A}$ is a linear operator, $\langle{c},{\cdot}\rangle$ is a linear function and $\mathcal{X}$ is a nonempty polytope. We establish affine-invariant and norm-independent global linear convergence rate of our method, in terms of both the objective gap and the Frank-Wolfe gap. When specialized to the D-optimal design problem, our results settle a question left open since Ahipasaoglu, Sun and Todd (2008). We also show that the iterates generated by our method will land on a face of $\mathcal{X}$ in a finite number of iterations, and this may lead to improved local linear convergence rates. We conduct numerical experiments on the problems of D-optimal design and inference of multivariate Hawkes processes, and the results not only showcase the efficiency and effectiveness of our method compared to other first-order methods, but also corroborate our theoretical results fairly well