Timezone: »

Non-convex Conditional Gradient Sliding
chao qu · Yan Li · Huan Xu

Wed Jul 11 06:20 AM -- 06:30 AM (PDT) @ A9

We investigate a projection free optimization method, namely non-convex conditional gradient sliding (NCGS) for non-convex optimization problems on the batch, stochastic and finite-sum settings. Conditional gradient sliding (CGS) method, by integrating Nesterov's accelerated gradient method with Frank-Wolfe (FW) method in a smart way, outperforms FW for convex optimization, by reducing the amount of gradient computations. However, the study of CGS in the non-convex setting is limited. In this paper, we propose the non-convex conditional gradient sliding (NCGS) methods and analyze their convergence properties. We also leverage the idea of variance reduction from the recent progress in convex optimization to obtain a new algorithm termed {\em variance reduced NCGS} (NCGS-VR), and obtain faster convergence rate than the batch NCGS in the finite-sum setting. We show that NCGS algorithms outperform their Frank-Wolfe counterparts both in theory and in practice, for all three settings, namely the batch, stochastic and finite-sum setting. This significantly improves our understanding of optimizing non-convex functions with complicated feasible sets (where projection is prohibitively expensive).

Author Information

chao qu (technion)
Yan Li (Georgia Institute of Technology)
Huan Xu (Georgia Tech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors