N&O seminar: Sebastian Pokutta (Zuse Institute & TU Berlin)

Everyone is welcome to attend the N&O seminar by Sebastian Pokutta with the title 'Locally Accelerated Conditional Gradients'.
  • What Networks & Optimization English Seminars
  • When 09-10-2019 from 11:00 to 12:00 (Europe/Amsterdam / UTC200)
  • Where Room L016 at CWI, Science Park 123 in Amsterdam
  • Contact Name Daniel Dadush
  • Add event to calendar iCal

Everyone is welcome to attend the N&O seminar by Sebastian Pokutta with the title 'Locally Accelerated Conditional Gradients'.

Abstract: 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.