Distributing Frank-Wolfe via Map-Reduce

Distributing Frank-Wolfe via Map-Reduce

Armin Moharrer, Stratis Ioannidis

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 5334-5338. https://doi.org/10.24963/ijcai.2018/748

We identify structural properties under which a convex optimization over the simplex can be massively parallelized via map-reduce operations using the Frank-Wolfe (FW) algorithm. A broad class of problems, e.g., Convex Approximation, Experimental Designs, and Adaboost, can be tackled this way. We implement FW over Apache Spark, and solve problems with 20 million variables using 350 cores in 79 minutes; the same operation takes 165 hours when executed serially.
Keywords:
Machine Learning: Data Mining
Machine Learning: Machine Learning
Computer Vision: Big Data and Large Scale Methods
Machine Learning Applications: Big data ; Scalability