Two Applications of Compression in Group Testing and Multi-Armed Bandits

Add to your list(s) Download to your calendar using vCal

• Christina Fragouli, UCLA
• Monday 03 July 2023, 11:00-12:00
• Room 909B, EEE Building.

If you have a question about this talk, please contact Cong Ling.

In this talk, we will present two applications where a form of compression is used: community aware group testing, and compression for multi-armed bandit systems.

Group testing pools together diagnostic samples to reduce the number of tests needed to identify infected members in a population. It is closely related to sparse estimation methods akin to compressive sensing, but is distinct as it only has access to a binary output of the tests (or sensed values). The traditional work in group testing assumes “independent” infections. However, infections can be correlated according to a community structure; consider for instance families that practice social distancing, or schools that operate with student pods, there can be a strong correlation on whether members of the same community are infected or not. We will show that taking into account community structure, can significantly reduce the number of tests needed to identify infected individuals; and we will discuss how these results extend to the case of dynamic infections.

The multi-armed bandit (MAB) problem is an active learning framework that aims to select the best among a set of actions by sequentially observing rewards. Recently, it has become popular for a number of applications over wireless networks, where communication constraints can form a bottleneck. By providing nearly matching upper and lower bounds, we will tightly characterize the number of bits needed per reward for the learner to accurately learn without suffering additional regret.

Short Bio ========= Christina Fragouli is a Professor in the Electrical and Computer Engineering Department at UCLA . She received the B.S. degree in Electrical Engineering from the National Technical University of Athens, Athens, Greece, and the M.Sc. and Ph.D. degrees in Electrical Engineering from the University of California, Los Angeles. She has worked at the Information Sciences Center, AT\&T Labs, Florham Park New Jersey, and the National University of Athens. She also visited Bell Laboratories, Murray Hill, NJ, and DIMACS , Rutgers University. Between 2006—2015 she was an Assistant and Associate Professor in the School of Computer and Communication Sciences, EPFL , Switzerland. She is an IEEE fellow, and has served in several IEEE Committees as member or Chair, including serving as the 2022 President of the IEEE Information Theory Society. She has also served as an Information Theory Society Distinguished Lecturer, and as an Associate Editor for IEEE Communications Letters, for Elsevier Journal on Computer Communication, for IEEE Transactions on Communications, for IEEE Transactions on Information Theory, and for IEEE Transactions on Mobile Communications. Her current research interests are in the intersection of network algorithms, coding techniques, and machine learning.

This talk is part of the COMMSP Seminar series.

This talk is included in these lists:

• COMMSP & CP list
• COMMSP Seminar
• Room 909B, EEE Building
• SAP Talks

Note that ex-directory lists are not shown.