BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Composable Core-sets for Distributed Optimization: From Submodular
 ity to Feature Selection
DTSTART:20170614T103000
DTEND:20170614T111500
DTSTAMP:20260407T034523Z
UID:ad3484cba40328dc151231ad2d3467f8fe40e8d08b0fc3ee2ef36eb2
CATEGORIES:Conferences - Seminars
DESCRIPTION:Vahab Mirrokni\, Google Research\nAn effective technique for s
 olving optimization problems over massive data sets is to partition the da
 ta into smaller pieces\, solve the problem on each piece and compute a rep
 resentative solution from it\, and finally obtain a solution inside the un
 ion of the representative solutions for all pieces. Such an algorithm can 
 be implemented easily in 2 rounds of MapReduces or be applied in a streami
 ng model. This technique can be captured via the concept of composable cor
 e-sets\, and has been recently applied to solve various problems. We will 
 see that diversity maximization and clustering problems\, a deterministic 
 variant of this technique applies\, and for submodular maximization and co
 lumn subset selection problems\, a randomized variant of composable core-s
 et problem can be applied\, e.g.\, a 0.3 and a 0.58-approximation for non-
 monotone and monotone submodualr maximization problems. Finally\, I show h
 ow to improve the above results to achieve a 1-1/e-\\eps-approximation for
  coverage function using a new sketching technique. I will discuss how to 
 design almost optimal streaming and distributed algorithms for coverage pr
 oblems\, and how to use these algorithms in feature selection problems. Th
 e main part of the talk summarizes results from a STOC 2015 (with M. ZadiM
 oghaddam) and a new paper (with H. Bateni and H. Esfandiari). The survey p
 art of the talk is from three recent papers that appeared in PODS'14\, NIP
 S'14\, and ICML'16.
LOCATION:BcC 420 https://plan.epfl.ch/theme/generalite_thm_plan_public?dim
 _floor=4&lang=en&dim_lang=en&tree_groups=centres_nevralgiques%2Cacces%2Cmo
 bilite_reduite%2Censeignement%2Ccommerces_et_services%2Cvehicules%2Cd
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR