Location: Google Meet (link)

Time: 10:30 - 12:00, 2021.05.05

Abstract: We establish a family of Bayesian Cramér-Rao bounds indexed by probability measures that satisfy a logarithmic Sobolev inequality. This family includes as special cases the Bayesian Cramér-Rao bound (also known as the van Trees inequality) and an entropic improvement due to Efroimovich. We provide an upper bound on the mutual information between observations generated from a parametric model and parameters of the model, given a log-concave prior. We conclude by showing how we may apply our results to establish tight non-asymptotic lower bounds for minimax risk under the generalized linear model.

Short bio: Kuan-Yun Lee is a Ph.D. candidate in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Prior to Berkeley, he received a B.S. degree in Electrical Engineering from the National Taiwan University in 2016. His research interest is in questions within the intersection of information theory, statistics, and machine learning.

Location: Google Meet (Link: https://meet.google.com/mrn-vubr-skw)

Time: 10:30 - 12:00, 2021.02.24

Abstract: Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable last-iterate convergence. They are also no-regret algorithms with important applications in online learning, especially when playing against adversarial opponents. However, their behaviors for simple bilinear games over the probability simplex are still not fully understood. In this work, we significantly expand the understanding of last-iterate convergence for OGDA and OMWU in the constrained setting. Specifically, for OMWU in bilinear games over the simplex, we show that when the equilibrium is unique, linear last-iterate convergence is achievable with a constant learning rate, which improves the result of (Daskalakis & Panageas, 2019) under the same assumption. We then significantly extend the results to more general objectives and feasible sets for the projected OGDA algorithm by introducing a sufficient condition under which OGDA exhibits concrete last-iterate convergence rates with a constant learning rate. We show that bilinear games over any polytope satisfy this condition, and OGDA converges exponentially fast even without the unique equilibrium assumption. Our condition also holds for strongly-convex-strongly-concave functions, recovering the result of (Hsieh et al., 2019).

Short bio: Chung-Wei Lee is a third-year Ph.D. student in computer science at USC. Before that, he received his B.S. degree in Electrical Engineering and Mathematics in 2018. He currently works on theoretical machine learning and its connections to optimization, game theory, and social science. His works got accepted in COLT, NeurIPS, CVPR, and ICLR.

Location: BL-214, NTU

Time: 15:30 - 17:00, 2021.01.13

Abstract: We study a model of online news dissemination on a Twitter-like social network. Given a noisy observation of the state of the world henceforth called the news, agents with heterogeneous priors decide whether to share with their followers based on whether receiving the news can persuade their followers to move their beliefs closer to theirs in aggregate. We demonstrate how surprise and affirmation motives naturally emerge from the utility-maximizing behavior of agents. We fully characterize the dynamics of the news spread and uncover the mechanisms that lead to a sharing cascade. We further investigate the impact of the network structure, heterogeneity of priors, and precision levels of news on the ex-ante probability of the news going viral. In particular, we show that as individual perspectives become more diverse, a wider range of news precision levels cause a cascade. Finally, we elucidate an association between the news precision levels that maximize the probability of a cascade and the prior wisdom of the crowd. Our results complement the empirical findings that support wider spread of inaccurate/false news compared to accurate information on social networks, providing a theoretical micro-foundation for utility-based news-sharing decisions.

Short bio: Chin-Chia Hsu is currently a Ph.D. candidate at Institute for Data, Systems and Society (IDSS) at MIT, working with Prof. Ali Jadbabaie. He is also affiliated with LIDS (Laboratory for Information and Decision Systems). Prior to MIT, he obtained his B.S. in Electrical Engineering from National Taiwan University (NTU). His primary research focus is on developing micro-foundations of information processing and decision making of individuals interacting on social media platforms, and investigate how these individual behaviors can evolve to large-scale social phenomena such as information cascades or subscription choices on news outlets. He establishes and analyzes models using tools and techniques from game theory, optimization, microeconomics, and probability theory to gain insights into economic decision making, based on which moderation principles can be made.

Location: EE2-105, NTU

Time: 15:30 - 17:00, 2020.12.30

Abstract: In many important graph data processing applications the acquired information includes both node features and observations of the graph topology. Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility and integrate them in a manner that is also universal. Here, universality refers to independence on homophily or heterophily graph assumptions. We address these issues by introducing a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction, regardless of the extent to which the node labels are homophilic or heterophilic. Learned GPR weights automatically adjust to the node label pattern and thereby guarantee excellent learning performance for label patterns that are usually hard to handle. Furthermore, they allow one to avoid feature over-smoothing, a process which renders feature information nondiscriminative, without requiring the network to be shallow. In this talk, we will dive into the crucial method GPR in detail. Then we explain how GPR inspired our design of GPR-GNN and why it can theoretically resolve two fundamental weaknesses in existing GNN architectures such as universality and over-smoothing.

Short bio: Eli Chien is currently a Ph.D. candidate in the department of Electrical and Computer Engineering at the University of Illinois Urbana-Champaign. He works on a broad range of problems related to algorithms to process the non-Euclidean data, including (hyper)graph and hyperbolic space. His researches mainly focus on connecting theory and practice by developing and analyzing principled algorithms. Specifically, his recent research results include Generalized PageRank algorithm, theory for graph neural networks, active learning on (hyper)graphs and hypergraph analysis for biology applications. Previously, he also works on semi-supervised k-means problem, support estimation problem and statistical modeling for hypergraphs. His works got published in TIT, NeurIPS, AISTATS, AAAI, ISIT and ICASSP.

Location: BL-214, NTU

Time: 15:30 - 17:00, 2020.12.23

Abstract: Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. Moreover, existing results mainly focus on global minimax estimation error and fail to leverage the sparse property that real-world data usually possesses.

In the first part of this talk, I will introduce novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone. In the second part of the talk, I will present our recent results on estimating sparse discrete distributions under both constraints. We characterize the local minimax estimation error and show how the underlying sparse structure can improve the estimation performance.

Short bio: Wei-Ning Chen received a B.Sc. degree in Electrical Engineering and Mathematics in 2016, and an M.S. degree in Communication Engineering in 2019, both from National Taiwan University. He is currently working towards the Ph.D. degree in the Department of Electrical Engineering at Stanford University. He is a recipient of the Stanford Graduate Fellowship (SGF). His research interests include information theory, statistics and theoretical machine learning.