Lecture Resources


Topic: Estimation and hypothesis testing under information constraints

Abstract: In this tutorial, we will provide an overview of techniques and recipes for distributed learning (estimation) and testing under information constraints such as communication, local privacy, and memory constraints. Motivated by applications in machine learning and distributed computing, these questions lie at the intersection of information theory, statistics, theoretical computer science, and machine learning. We will mainly focus on minimax lower bound techniques, and cover a set of general methods to establish information-theoretic lower bounds, for both estimation and hypothesis testing questions, in both noninteractive and interactive settings.


Clément Canonne joined the School of Computer Science of the University of Sydney as a Lecturer in January 2021. Prior to that, he was a postdoc first in the Stanford Theory Group, then at IBM Research Almaden. He obtained his Ph.D. from the Computer Science department of Columbia University, where he was advised by Prof. Rocco Servedio, and received an M.Sc. in Computer Science from the Parisian Master of Research in Computer Science, and an engineering degree from one of France's "Grand Schools," the Ecole Centrale Paris.

Homepage: https://ccanonne.github.io/

Topic: Mutual information in machine learning

Abstract: Mutual information is a fundamental quantity in information theory. It is widely used in machine learning to measure statistical dependency among different features in data. Applications are numerous, ranging from classification, clustering, representation learning, and other tasks that require the selection/extraction of lower-dimensional features of the data without losing valuable information. Although mutual information has a precise formula defined in terms of a probability model, it must be estimated for real-world data with an unknown probability model. In this lecture series, we will dive into some of the applications and estimations of mutual information in machine learning. Registered participants will have hands-on coding experience using the virtual teaching and learning environment DIVE offered by CityU CS Department.

Biography: Chung Chan received the B.Sc., M.Eng. and Ph.D. from the EECS Department at MIT in 2004, 2005 and 2010 respectively. He was a Research Assistant Professor at the Institute of Network Coding, the Chinese University of Hong Kong from 2013 to 2017. He is currently an Assistant Professor at the Department of Computer Science, City University of Hong Kong. His research interest is to develop general information measures and flow models from network information theory that are applicable to practical problems. His research topics include the development of network link models using matroids, the derivation of theoretical limits and optimal strategies for the problems of multiterminal source coding, data exchange, and secret generation. His most significant work is the extension of Shannon’s mutual information to the multivariate case, and the discovery of its connections to various problems in information theory and machine learning. During the COVID-19 pandemic in 2020/21, he received the outstanding teaching award from CityU College of Engineering for the DIVE virtual learning and teaching environment.

Homepage: https://scholars.cityu.edu.hk/person/ccha23

Topic: Random walk on high dimensional expanders

Abstract: High dimensional expanders are certain generalizations of expander graphs to hypergraphs. They recently appeared in many randomized algorithms and combinatorial constructions in theoretical computer science. A few random sampling algorithms can be seen as random walks on high dimensional expanders, such as nearly uniformly sampling of spanning trees by exchanging edges. High dimensional expanders also appear in locally testable codes and probabilistically checkable proofs. In this talk, I will give a gentle introduction to high dimensional expanders and survey their recent results.

Biography: Siu On Chan is an Assistant Professor in the CSE Department at the Chinese University of Hong Kong (CUHK). Before joining CUHK, he was a postdoc researcher at Microsoft Research New England. Before that, he obtained his Ph.D. in theoretical computer science at UC Berkeley. His advisors were Luca Trevisan and Elchanan Mossel. Earlier, he obtained his masters at the University of Toronto, under Michael Molloy, and his undergraduate degree at CUHK, working with Leizhen Cai. He is interested in understanding the limitations of approximation algorithms, especially convex optimization algorithms. He is also interested in random graphs, testing and learning.

Homepage: https://www.cse.cuhk.edu.hk/~siuon/

Topic: Finite-blocklength schemes in information theory

Abstract: While asymptotic coding theorems in information theory have the benefit of simplicity, they are not suitable for practical delay-constrained communication settings. We will discuss finite-blocklength schemes that take delay constraints into account. Settings such as channel coding, compression, joint source-channel coding and channels with state will be investigated.

Biography: Cheuk Ting Li received the B.Sc. degree in mathematics and B.Eng. degree in information engineering from The Chinese University of Hong Kong in 2012, and the M.S. and Ph.D. degree in electrical engineering from Stanford University in 2014 and 2018 respectively. He was a postdoctoral scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley. He was awarded the 2016 IEEE Jack Keil Wolf ISIT Student Paper Award. He joined the Department of Information Engineering, the Chinese University of Hong Kong in January 2020. He is interested in developing new information-theoretic techniques to address problems in delay-constrained communications, information security, distributed computing and machine learning.

Homepage: https://staff.ie.cuhk.edu.hk/~ctli/

Topic: Locally-testable and locally-decodable codes

Abstract: Locally-testable and locally-decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. These codes have arisen from a variety of motivations within the theory of computation, and the study of these codes had a significant effect on coding theory as well. In this talk we will survey the motivations for the study of locally-testable and locally-decodable codes within the theory of computation and some of the state-of-the-art results. We will also highlight some of the most interesting challenges that remain.

Biography: Noga Ron-Zewi is a Senior Lecturer at the Department of Computer Science at the University of Haifa in Israel. Her research interests are in the theory of computation, with a focus on research topics at the interface of communication and computation. She received a Ph.D. degree in Computer Science from the Technion – Israel Institute of Technology in 2014. Prior to joining the University of Haifa, she was the IAS-DIMACS postdoctoral fellow with a joint position at the Institute for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers, and a faculty member at Ben-Gurion University in Israel. She is a recipient of the Rothschild postdoctoral fellowship, the Alon Fellowship, and the Krill Prize.

Homepage: https://sites.google.com/view/nogazewi

Topic: Fundamental trade-offs between privacy and utility in data sharing

Abstract: A main barrier in sharing data between people and organizations is legitimate concerns about privacy. To address this concern, an active research area has focused on designing data perturbation mechanisms that can maintain usefulness of shared data for a given analytical task, while minimizing the capability of the data analyst in inferring sensitive information. However, there is often a fundamental and nontrivial trade-off between data privacy and utility. This lecture aims to provide a thorough understanding of this trade-off and optimal ways to deal with it. The primary focus will be on information theoretic aspects of this problem. We will explore questions such as how to meaningfully and operationally measure privacy leakage using mutual information and its various generalizations in the literature, such as Sibson mutual information and maximal leakage. We will formulate the problem of privacy-utility trade-off and explore theoretical bounds on optimal solutions, as well as novel privacy-preserving algorithms to achieve them. We will also present new connections between information-theoretic privacy and other privacy-preserving frameworks, most notably differential privacy, identifiability, and low-influence. The lecture aims to provide many illustrative and interactive examples to establish key concepts and discuss practical applications of data perturbation for discrete-valued queries on datasets (such as counting or voting) and statistical queries on datasets (such as mean or quantiles).

Biography: Parastoo Sadeghi received the bachelor and master degrees in electrical engineering from Sharif University of Technology, Tehran, Iran, in 1995 and 1997, respectively, and the Ph.D. degree in electrical engineering from the University of New South Wales (UNSW) Sydney, in 2006. She is currently a Professor at the School of Engineering and Information Technology, UNSW Canberra. Her research interests include information theory, data privacy, index coding, and network coding. She has co-authored the book Hilbert Space Methods in Signal Processing (Cambridge University Press, 2013) and around 170 refereed journal articles and conference papers. In 2019, she was awarded a Future Fellowship from the Australian Research Council. From 2016 to 2019, she served as an Associate Editor for the IEEE Transactions on Information Theory. She has also served on the Board of Governors of the IEEE Information Theory Society.

Homepage: https://cecs.anu.edu.au/people/parastoo-sadeghi

Topic: Fair machine learning via information theory

Abstract: We explore an interesting topic in the field of Artificial Intelligence (AI) via the lens of information theory: fair machine learning. Fairness is one of the crucial aspects required for enabling trustworthy AI. In this series of lectures, we study how tools of information theory serve to develop fair classifiers that aim to achieve the irrelevancy of a prediction to sensitive attributes such as race, sex, age and religion. We also investigate an intimate connection to one prominent unsupervised learning framework: generative adversarial networks.

Biography: Changho Suh is an Associate Professor and a Vice-Chair of Electrical Engineering at KAIST. He received the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in EECS from UC Berkeley in 2011. From 2011 to 2012, he was a postdoctoral associate in MIT. From 2002 to 2006, he had been with Samsung. Prof. Suh is a recipient of numerous awards: the AFOSR Grant, the Google Education Grant, the Young IT Engineer Award, the IEIE Haedong Young Engineer Award, the IEEE Communications Society Stephen O. Rice Prize, the David J. Sakrison Memorial Prize (the best dissertation award in UC Berkeley EECS), the IEEE ISIT Best Student Paper Award, and the Department Teaching Awards. Dr. Suh is an IEEE Information Theory Society Distinguished Lecturer, the General Co-Chair of East Asian School of Information Theory, and a Member of Young Korean Academy of Science and Technology. He is also the Editor for the IEEE Information Theory Newsletter, an Associate Editor for Statistical Learning for the IEEE Transactions on Information Theory, and a Senior Program Committee member of IJCAI 2019–2021.

Homepage: http://csuh.kaist.ac.kr/


  • The lectures are held in Room 201 of the Cheng Yu Tung Building on the campus of CUHK.
  • The poster sessions are held in Room 202 of the Cheng Yu Tung Building on the campus of CUHK.
  • Hotel check-in can be made in the afternoon of Sunday, 22 August 2021. We will have some ice-breaking activities in the evening.
  • Hotel check-out shall be made by the morning of Friday, 27 August 2021.
  • See this page for more accommodation details.