Title: A User Guide to Low-Pass Graph Signal Processing and its Applications
Abstract: The notion of graph filters can be used to define generative models for graph data. In fact, the data obtained from many examples of network dynamics may be viewed as the output of a graph filter. With this interpretation, classical signal processing tools such as frequency analysis have been successfully applied with analogous interpretation to graph data, generating new insights for data science. What follows is a user guide on a specific class of graph data, where the generating graph filters are low-pass, i.e., the filter attenuates contents in the higher graph frequencies while retaining contents in the lower frequencies. Our choice is motivated by the prevalence of low-pass models in application domains such as social networks, financial markets, and power systems. We illustrate how to leverage properties of low-pass graph filters to learn the graph topology or identify its community structure, efficiently represent graph data through sampling, recover missing measurements, and de-noise graph data.
Biography: Anna Scaglione (M.Sc.’95, Ph.D. ’99) is currently a professor in electrical and computer at Cornell Tech, the New York City campus of Cornell University, Prior to that she held faculty positions at Arizona State University, the University of California at Davis, Cornell University (the first time) and the University of New Mexico.
She is IEEE fellow since 2011 and received the 2013, IEEE Donald G. Fink Prize Paper Award, the 2000 IEEE Signal Processing Transactions Best Paper Award the NSF CAREER grant (2002). She is co-recipient with her students of several best student papers awards at conferences and received the 2013 IEEE Signal Processing Society Young Author Best Paper Award with one of the PhD students. She was Distinguished Lecturer of the Signal Processing Society in 2019 and 2020, when most of her travel was cut short by the pandemic.
Dr. Scaglione’s expertise and research considers theoretical and applied problems is in statistical signal processing, communications theory and cyber-physical systems. Her talk includes research she has done on data that originate from networked systems.
Abstract: The problems of heterogeneity pose major challenges in extracting meaningful information from data as well as in the subsequent decision making or prediction tasks. Heterogeneity brings forward some very fundamental theoretical questions of machine learning. For unsupervised learning, Mixture models are standard tools for probabilistic modeling of heterogeneous data, and have been studied theoretically for more than a century. However for supervised learning, labels can be generated via a mixture of functional relationships, which is a relatively new model. We will provide a survey of results on parameter learning in these mixture models, some unexpected connections with other problems, and some interesting future directions.
This presentation is based on joint works with Soumyabrata Pal.
Biography: Arya Mazumdar is an Associate Professor of Data Science in UC San Diego. Arya obtained his Ph.D. degree from University of Maryland, College Park specializing in information theory. Subsequently Arya was a postdoctoral scholar at Massachusetts Institute of Technology, an assistant professor in University of Minnesota, and an assistant followed by associate professor in University of Massachusetts Amherst. Arya is a recipient of multiple awards, including a Distinguished Dissertation Award for his Ph.D. thesis, the NSF CAREER award, an EURASIP JASP Best Paper Award, and the ISIT Jack K. Wolf Student Paper Award. He is currently serving as an Associate Editor for the IEEE Transactions on Information Theory and as an Area editor for Now Publishers Foundation and Trends in Communication and Information Theory. Arya’s research interests include coding theory (error-correcting codes and related combinatorics), information theory, statistical learning and distributed optimization.
Abstract: In this talk, we study function-correcting codes, a new class of codes designed to protect the function evaluation of a message against errors. We show that function-correcting codes are equivalent to irregular-distance codes, i.e., codes that obey some given distance requirement between each pair of codewords. Using these connections, we study irregular-distance codes and derive general upper and lower bounds on their optimal redundancy. Since these bounds heavily depend on the specific function, we provide simplified, suboptimal bounds that are easier to evaluate. We further employ our general results to specific functions of interest and compare our results to standard error-correcting codes which protect the whole message.
(Joint work with Andreas Lenz, Rawad Bitar and Eitan Yaakobi)
Biography: Antonia Wachter-Zeh is an Associate Professor at the Technical University of Munich (TUM), Munich, Germany in the Department of Electrical and Computer Engineering. She received the M.Sc. degree in communications technology in 2009 from Ulm University, Germany. She obtained her Ph.D. degree in 2013 from Ulm University and from Universite de Rennes 1, Rennes, France. From 2013 to 2016, she was a postdoctoral researcher at the Technion—Israel Institute of Technology, Haifa, Israel, and from 2016 to 2020 a Tenure Track Assistant Professor at TUM. She is a recipient of the DFG Heinz Maier-Leibnitz-Preis and of an ERC Starting Grant. She is currently an Associate Editor for the IEEE Transactions on Information Theory. Her research interests are coding theory, cryptography and information theory and their application to storage, communications, privacy, and security.
Title: Robust learning: Worst-case, average-case, or in-between?
Abstract: Many of the successes of machine learning are based on minimizing an averaged loss function. However, it is well-known that this paradigm suffers from robustness issues that hinder its applicability in safety-critical domains. These issues are often addressed by training against worst-case perturbations of data, a technique known as adversarial training. Although empirically effective, adversarial training can be overly conservative, leading to unfavorable trade-offs between nominal performance and robustness. To this end, in this paper we propose a framework called probabilistic robustness that bridges the gap between the accurate, yet brittle average case and the robust, yet conservative worst case by enforcing robustness to most rather than to all perturbations. From a theoretical point of view, this framework overcomes the trade-offs between the performance and the sample-complexity of worst-case and average-case learning. From a practical point of view, we propose a novel algorithm based on risk-aware optimization that effectively balances average- and worst-case performance at a considerably lower computational cost relative to adversarial training. Our results on MNIST, CIFAR-10, and SVHN illustrate the advantages of this framework on the spectrum from average- to worst-case robustness.
Biography: Hamed Hassani is currently an assistant professor of Electrical and Systems Engineering department as well as the Computer and Information Systems department, and the Statistics department at the University of Pennsylvania. Prior to that, he was a research fellow at Simons Institute for the Theory of Computing (UC Berkeley) affiliated with the program of Foundations of Machine Learning, and a post-doctoral researcher in the Institute of Machine Learning at ETH Zurich. He received a Ph.D. degree in Computer and Communication Sciences from EPFL, Lausanne. He is the recipient of the 2014 IEEE Information Theory Society Thomas M. Cover Dissertation Award, 2015 IEEE International Symposium on Information Theory Student Paper Award, 2017 Simons-Berkeley Fellowship, 2018 NSF-CRII Research Initiative Award, 2020 Air Force Office of Scientific Research (AFOSR) Young Investigator Award, 2020 National Science Foundation (NSF) CAREER Award, and 2020 Intel Rising Star award. He has recently been selected as the distinguished lecturer of the IEEE Information Theory Society in 2022-2023.
Title: Real-time sampling and estimation: from IoT Markov processes to disease spread processes
Abstract: The Internet of Things (IoT) and social networks have provided unprecedented information platforms. The information is often governed by processes that evolve over time and/or space (e.g. on an underlying graph) and they may not be stationary or stable. We seek to devise efficient strategies to collect real-time information for timely estimation and inference. This is critical for learning and control.
In the first part of the talk, we focus on the problem of real-time sampling and estimation of autoregressive Markov processes over random access channels. For the class of policies in which decision making has to be independent of the source realizations, we make a bridge with the recent notion of Age of Information (AoI) to devise novel distributed policies that utilize local AoI for decision making. We also provide strong guarantees for the performance of the proposed policies. More generally, allowing decision making to be dependent on the source realizations, we propose distributed policies that improve upon the state of the art by a factor of approximately 6. Furthermore, we numerically show the surprising result that despite being decentralized, our proposed policy has a performance very close to that of centralized scheduling.
In the second part of the talk, we go beyond time-evolving processes by looking at spread processes that are defined over time as well as an underlying network. We consider the spread of an infectious disease such as COVID-19 in a network of people and design sequential testing (and isolation) strategies to contain the spread and minimize the cumulative infections under a given test budget. We prove that the objective can be optimized, with performance guarantees, by greedily selecting the nodes to test. We further design reward-based methodologies that minimize an upper bound on the cumulative infections and are computationally more tractable in large networks. These policies, however, need knowledge about the nodes’ infection probabilities which are unknown and have to be learned by sequential testing. We develop a message-passing framework for this purpose and, building on that, show novel tradeoffs between exploitation of knowledge through reward-based heuristics and exploration of the unknown through a carefully designed probabilistic testing. We provably show the necessity of exploration in a stylized network and show through simulations that exploration can outperform exploitation in various synthetic and real-data networks depending on the parameters of the network and the spread.
Biography: Shirin Saeedi Bidokhti is an assistant professor in the Department of Electrical and Systems Engineering at the University of Pennsylvania (UPenn). She received her M.Sc. and Ph.D. degrees in Computer and Communication Sciences from the Swiss Federal Institute of Technology (EPFL). Prior to joining UPenn, she was a postdoctoral scholar at Stanford University and the Technical University of Munich. She has also held short-term visiting positions at ETH Zurich, University of California at Los Angeles, and the Pennsylvania State University. Her research interests broadly include the design and analysis of network strategies that are scalable, practical, and efficient for use in Internet of Things (IoT) applications, information transfer on networks, as well as data compression techniques for big data. She is a recipient of the 2022 IT society Goldsmith lecturer award, 2021 NSF-CAREER award, 2019 NSF-CRII Research Initiative award and the prospective researcher and advanced postdoctoral fellowships from the Swiss National Science Foundation.