Workshop on Modern Information Theory
时间: 2021年12月31日 9:00-12:00
Online link: https://meeting.tencent.com/dw/EWY596mlxD8Y 腾讯会议
1. Speaker: Prof. Guangyue Han, Hong Kong University
9:00-10:00, Dec. 31, 2021
On Sampling Continuous-Time AWGN Channels
For a continuous-time additive white Gaussian noise (AWGN) channel with possible feedback, it has been shown that as sampling gets infinitesimally fine, the mutual information of the associative discrete-time channels converges to that of the original continuous-time channel. We give in this paper more quantitative strengthenings of this result, which, among other implications, characterize how over-sampling approaches the true mutual information of a continuous-time Gaussian channel with bandwidth limit. The assumptions in our results are relatively mild. In particular, for the non-feedback case, compared to the Shannon-Nyquist sampling theorem, a widely used tool to connect continuous-time Gaussian channels to their discrete-time counterparts that requires the band-limitedness of the channel input, our results only require some integrability conditions on the power spectral density function of the input.
Guangyue Han received the B.S. and M.S. degrees in mathematics from Peking University, China, in 1997 and 2000, respectively, and the Ph.D. degree in mathematics from the University of Notre Dame, USA, in 2004. After three years with the Department of Mathematics, the University of British Columbia, Canada, he joined the Department of Mathematics, the University of Hong Kong, China, in 2007. His main research areas are coding and information theory.
2. Speaker: Prof. Vincent Tan, National University of Singapore
10:00-11:00, Dec. 31, 2021
Towards Minimax Optimal Best Arm Identification in Linear Bandits (https://arxiv.org/abs/2105.13017)
We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We provide a theoretical analysis of the failure probability of OD-LinBAI. Instead of all the optimality gaps, the performance of ODLinBAI depends on the gaps of the top d arms, where d is the effective dimension of the linear bandit instance. Furthermore, we present a minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to multiplicative factors in the exponent, which is a significant improvement over existing methods (e.g., BayesGap, Peace, LinearExploration and GSE). Finally, numerical experiments corroborate our theoretical findings.
Vincent Y. F. Tan (S'07-M'11-SM'15) was born in Singapore in 1981. He received the B.A. and M.Eng. degrees in electrical and information science from Cambridge University in 2005, and the Ph.D. degree in electrical engineering and computer science (EECS) from the Massachusetts Institute of Technology (MIT) in 2011. He is currently a Dean’s Chair Associate Professor with the Department of Electrical and Computer Engineering and the Department of Mathematics, National University of Singapore (NUS). His research interests include information theory, machine learning, and statistical signal processing.
Dr. Tan is a member of the IEEE Information Theory Society Board of Governors. He was an IEEE Information Theory Society Distinguished Lecturer from 2018 to 2019. He received the MIT EECS Jin-Au Kong Outstanding Doctoral Thesis Prize in 2011, the NUS Young Investigator Award in 2014, the Singapore National Research Foundation (NRF) Fellowship (Class of 2018), and the NUS Young Researcher Award in 2019. A dedicated educator, he was also awarded the Engineering Educator Award in 2020. He is currently serving as an Associate Editor for the IEEE Transactions on Signal Processing and as an Associate Editor in Machine Learning and Statistics for the IEEE Transactions on Information Theory.
3. Speaker: Prof. Linqi Song, City University of Hong Kong
11:00-12:00, Dec. 31, 2021 0020
Privacy-Preserving Communication-Efficient Federated Multi-Armed Bandits
Communication bottleneck and data privacy are two critical concerns in federated multi-armed bandit (MAB) problems, such as situations in decision-making and recommendations of connected vehicles via wireless. In this paper, we design the privacy-preserving communication-efficient algorithm in such problems and study the interactions among privacy, communication and learning performance in terms of the regret. To be specific, we design privacy-preserving learning algorithms and communication protocols and derive the learning regret when networked private agents are performing online bandit learning in both a master-worker structure and a decentralized structure, where communication constraints are to be counted. Our bandit learning algorithms are based on epoch-wise sub-optimal arm eliminations at each agent and agents exchange learning knowledge with the server/each other at the end of each epoch. Furthermore, we adopt the differential privacy (DP) approach to protect the data privacy at each agent when exchanging information; and we curtail communication costs by making less frequent communications with fewer agents participation. By analyzing the regret of our proposed algorithmic framework in both master-worker and decentralized network structures, we theoretically show trade-offs between regret and communication costs/privacy, namely, less communication costs and higher privacy requirements lead to more regret in the federated MAB problem. Finally, we empirically show these trade-offs which are consistent with our theoretical analysis.
Linqi Song is currently an Assistant Professor with the Department of Computer Science, City University of Hong Kong and a Research Scientist with the City University of Hong Kong Shenzhen Research Institute. He received the Ph.D. degree in electrical engineering from the University of California, Los Angeles (UCLA), USA and the B.S. and M.S. degrees from Tsinghua University, China. He was a Postdoctoral Scholar with the Department of Electrical and Computer Engineering, UCLA. His research interests include information theory, machine learning, and big data. He has received the Hong Kong RGC Early Career Scheme in 2019and the Best Paper Award from IEEE MIPR 2020.