以下の通り，第3回研究会を開催いたしました．
日時: 2019年7月9日 (火) 15:00～17:00
場所: 京都大学 数理解析研究所 (RIMS) 2階 204室
参加者: 18名
講演者: Sebastian Pokutta (Georgia Institute of Technology)
題目: Locally Accelerated Conditional Gradients
概要: Conditional gradient methods form a class of projection-free first-order algorithms for solving smooth convex optimization problems. Apart from eschewing projections, these methods are attractive because of their simplicity, numerical performance, and the sparsity of the solutions outputted. However, they do not achieve optimal convergence rates.
We present the Locally Accelerated Conditional Gradients algorithm that relaxes the projection-freeness requirement to only require projection onto (typically low-dimensional) simplices and mixes accelerated steps with conditional gradient steps to achieve local acceleration. We derive asymptotically optimal convergence rates for this algorithm. Our experimental results demonstrate the practicality of our approach; in particular, the speedup is achieved both in wall-clock time and per-iteration progress compared to standard conditional gradient methods and a Catalyst-accelerated Away-Step Frank-Wolfe algorithm.