When: March 9, 2016, 12:30 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4401, email@example.com
Kwang-Sung Jun, Post-doc Optimization UW-Madison
Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls
We introduce a new multi-armed bandit (MAB) problem in which arms must be sampled in batches, rather than one at a time. This is motivated by applications in social media monitoring and biological experimentation where such batch constraints naturally arise. We develop and analyze algorithms for batch MABs and top arm identification, for both fixed confidence and fixed budget settings. The main theoretical results show that the batch constraint does not significantly affect the sample complexity of top arm identification compared to unconstrained MAB algorithms. Alternatively, if one views a batch as the fundamental sampling unit, then the results can be interpreted as showing that the sample complexity of batch MABs can be significantly less than traditional MABs. We demonstrate the new batch MAB algorithms with simulations and in two interesting real-world applications: (i) microwell array experiments for identifying genes that are important in virus replication and (ii) finding the most active users in Twitter on a specific topic.
Cong Han Lim, Graduate Student, Optimization,UW-Madison
Efficient Bregman Projections onto the Permutahedron and Related Polytopes
Computing the projection onto a permutahedron PH(c) — the convex hull of all permutations of a fixed vector c — is an important step for some algorithms in machine learning. This includes algorithms for online learning over rankings and algorithms for OWL-regularized problems. The projection problem (under any uniformly separable Bregman divergence) can be reduced to the Isotonic Optimization problem, which allows one to employ known fast algorithms to improve on several recent results on Bregman projections onto permutahedra. We develop two new algorithms that have better complexity when the number of distinct entries d in
the vector c is small, the simplex being one such example with c = (1,0,0,…,0) and d = 2. One algorithm runs in O(n log d) for certain popular Bregman divergence measures, while the other requires O(n log (dU/epsilon)) to find epsilon-close solutions for general uniformly separable Bregman divergences, where U is a bound on the width of the interval containing the dual solution components. These match or improve best known bounds for all Bregman projection problems onto various permutahedra, including recent results for Bregman projection onto the simplex.
Joint work with Stephen Wright.
The weekly SILO seminar series is made possible through the generous support of the 3M Company and its Advanced Technology Group
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.