Timezone: »

 
Poster
Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
Geoffrey Negiar · Gideon Dresdner · Alicia Yi-Ting Tsai · Laurent El Ghaoui · Francesco Locatello · Robert Freund · Fabian Pedregosa

Tue Jul 14 12:00 PM -- 12:45 PM & Wed Jul 15 01:00 AM -- 01:45 AM (PDT) @ Virtual
in Poster Session 6 »

We propose a novel Stochastic Frank-Wolfe (a. k. a. conditional gradient) algorithm for constrained smooth finite-sum minimization with a generalized linear prediction/structure. This class of problems includes empirical risk minimization with sparse, low-rank, or other structured constraints. The proposed method is simple to implement, does not require step-size tuning, and has a constant per-iteration cost that is independent of the dataset size. Furthermore, as a byproduct of the method we obtain a stochastic estimator of the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the setting, the proposed method matches or improves on the best computational guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several datasets highlight different regimes in which the proposed method exhibits a faster empirical convergence than related methods. Finally, we provide an implementation of all considered methods in an open-source package.

Keywords: Convex Optimization · Large Scale Learning and Big Data · Sparsity and Compressed Sensing · Optimization - Convex
[ Slides] 

Author Information

Geoffrey Negiar (UC Berkeley)
Gideon Dresdner (ETH Zürich)
Alicia Yi-Ting Tsai (University of California, Berkeley)
Laurent El Ghaoui (UC Berkeley)
Francesco Locatello (ETH Zurich - Max Planck Institute)
Robert Freund (MIT)
Fabian Pedregosa (Google)

More from the Same Authors