Abstract
A continuing mystery in understanding the empirical success of deep neural networks has been in their ability to achieve zero training error and yet generalize well, even when the training data is noisy and there are many more parameters than data points. Following the information-theoretic tradition of seeking understanding, this talk will share our three-part approach to shedding light on this phenomenon. First, following the tradition of such distilled toy models like the BSC and AWGN channels, the Gaussian source, or scalar linear control systems, we zoom in on the classical linear regression problem in the underdetermined setting with more parameters than training data. Here, the solutions that minimize training error interpolate the data, including noise. Second, following the tradition of converse bounds, we give a genie-aided bound on how well such interpolative solutions can generalize to fresh test data, and show that this bound generically decays to zero with the number of extra features, thus characterizing an explicit benefit of overparameterization. Third, we talk about what it takes to achieve such harmless interpolation in appropriately overparameterized limits. For appropriately sparse linear models, we provide a hybrid interpolating scheme (combining classical sparse recovery schemes with harmless noise-fitting) to achieve generalization error close to the bound on interpolative solutions. Along the way, we call out certain key concepts that we call "signal bleed" and "crab-pot regularization" that help us understand what is required to achieve harmless interpolation in general.
Biography
Anant Sahai did his undergraduate work in EECS at UC Berkeley, and then went to MIT as a graduate student studying Electrical Engineering and Computer Science (Course 6 in MIT-speak). After graduating with his PhD, and before joining the Berkeley faculty, he was on the theoretical/algorithmic side of a team at the startup Enuvis, Inc. developing new adaptive software radio techniques for GPS in very low SNR environments (such as those encountered indoors in urban areas). He currently serves also as faculty adviser to UC Berkeley's chapter of Eta Kappa Nu. He has previously served as the Treasurer for the IEEE Information Theory Society.
His research interests span information theory, decentralized control, machine learning, and wireless communication --- with a particular interest at the intersections of these fields. Within wireless communication, he is particularly interested in Spectrum Sharing and Cognitive Radio as well as very-low-latency ultra-reliable wireless communication protocols for the Internet Of Things. Recently, he is very interested in machine learning for cooperation, control, and wireless communication.
Abstract
We first describe successive cancellation (SC) decoding on a binary-input symmetric memoryless channel using the Plotkin (u,u+v) construction. Here we also briefly address the complexity and performance characteristics of SC decoding and turn to its polarization properties. Any synthetic channel is then represented as some ensemble {qi,pi} of the binary symmetric channels BSC(pi) that occur in the decoding process with different probabilities qi and have different crossover probabilities pi. We then map each BSC(pi) onto a planar unit vector (sin ai,cos ai), where sin ai=(1-pi)/2. Polarization process then becomes a pairwise angle-modifying transformation in the ensemble {qi,ai} of unit vectors that occur with different probabilities qi and have different angles ai. In the upgrading process, two ordered vectors that have angles a and b produce a unit vector that has a smaller angle arcsin(sin a sin b). Similarly, a pairwise degrading of two BSC channels yields a unit vector with a larger angle arccos(cos a cos b). We study the properties of the angles ai and estimate how they change in the upgrading-degrading process. In particular, any two input angles produce two output angles that have a larger mutual separation. We also study some other quantities associated with pairwise angle transformations. As a result, different angles polarize and tend to 0 or π/2 with probability 1. This also proves the polarizing behavior of synthetic channels.
Biography
Ilya Dumer received his Ph.D. degree from the Institute for Information Transmission Problems of the Russian Academy of Sciences in 1981 and was with this Institute from 1983 to 1995. During 1992-1993, he was a Royal Society Guest Research Fellow at Manchester University, Manchester, U.K., and during 1993-1994, an Alexander von Humboldt Fellow at the Institute for Experimental Mathematics in Essen, Germany. Since 1995, he has been a Professor of Electrical Engineering at the University of California, Riverside. Dr. Dumer's interests are in coding theory, discrete geometry, and their applications, with an emphasis on the low-complexity decoding algorithms, non-binary and quantum codes, and covering problems in the Euclidean spaces. In 2006-2009, he served as Associate Editor for the IEEE Transactions on Information Theory. He is a Fellow of the IEEE (2007).
Abstract
An all-wireless vision connecting billions of devices is finally in sight with the Internet-of-Everything paradigm. This vision entails large networks with dynamic connectivity, ad hoc formation and heterogeneous nodes. Central to be able to integrate all our lives to this massive virtual domain is security and privacy of the information that flows through it. Current wireless systems have security of information as an add-on to current design, and rely on application layer protocols, which have worked well for the scale and the resources of the systems to date. Going forward however, with massive scale formation of networks of asymmetric resources, these protocols involving key exchanges and shared randomness for security may prove to be less than practical.
Securing information at the foundation of system design can alleviate these issues by replacing or strengthening the present cryptographic solutions. This foundational design approach brings us to information theoretic security for the all-connected world. In this talk, we will provide an overview of this approach that relies on local randomness and produces information theoretic security guarantees, e.g., for confidentiality and authentication, utilizing the properties of the transmission medium. We will review the insights that have emerged when information security is included as a design primitive and provide the state of the art directions towards realizing the potential of this approach. We will also introduce models where this approach can be integrated with encryption for nodes with local memory storage.
Biography
Aylin Yener is a Distinguished Professor of Electrical Engineering and a Dean's Fellow at Penn State. She joined Penn State in 2002 as an assistant professor, and has been a professor since 2010. In 2008-2009, she was a visiting associate professor in the Electrical Engineering Department at Stanford, and in 2016-2017 she was a visiting professor in the same department. She also held a visiting position in Telecom Paris Tech in 2016.
Yener's research interests are in foundations of networked systems, with core expertise areas in wireless communication theory, information theory, optimization, and network science. Her current focus areas are information theoretic security, energy sustainable wireless communication networks, coded content delivery and retrieval, and learning for communications.
Yener received the IEEE Communications Society best Tutorial Paper award in 2019, the IEEE Women in Communications Engineering (WICE) Outstanding Achievement Award in 2018, the IEEE Marconi Prize Paper Award in 2014, the IEEE ICC best paper award in 2010, and the NSF CAREER award in 2003. In 2017, she was a Clariviate Analytics highly cited researcher. She is presently Distinguished Lecturer for IEEE Information Theory Society (2019-2020), IEEE Communication Society (2018-2019), and IEEE Vehicular Technology Society (2017-2019). She is a fellow of the IEEE.
Yener's previous service to IEEE includes having served as a technical program chair of various symposia for the IEEE Communication Society, an associate editor for the IEEE Transactions on Communications, and IEEE Transactions on Mobile Computing, a guest editor for IEEE Journal on Selected Areas in Communications and IEEE Transactions on Information Forensics and Security, an associate editor and an editorial advisory board member for the IEEE Transactions on Wireless Communications. She currently serves as a senior editor for the IEEE Journal on Selected Areas in Communications, and is on the inaugural senior editor team for the IEEE Journal on Selected Areas in Information Theory. She has served in various roles in the IEEE Information Theory Society including Student Committee Chair (2007-2011), Treasurer (2012-2014), Member of the Board of Governors (2015-present), and Second Vice President (2018). She is the current Vice President of the IEEE Information Theory Society.
Abstract
We will overview the distributed optimization algorithms starting with the basic underlying idea illustrated on a prototype problem in machine learning. In particular, we will focus on convex minimization problem where the objective function is given as the sum of convex functions, each of which is known by an agent in a network. The agents communicate over the network with a task to jointly determine a minimum of the sum of their objective functions. The communication network can vary over time, which is modeled through a sequence of graphs over a static set of nodes (representing the agents in a system). In this setting, the distributed first-order methods will be discussed that make use of an agreement protocol, which is a mechanism replacing the role of a coordinator. We will discuss some refinements of the basic method and conclude with more recent developments of fast methods that can match the performance of centralized methods (up to a logarithmic factor).
Biography
Angelia Nedich holds a Ph.D. from Moscow State University, Moscow, Russia, in Computational Mathematics and Mathematical Physics (1994), and a Ph.D. from Massachusetts Institute of Technology, Cambridge, USA in Electrical and Computer Science Engineering (2002). She has worked as a senior engineer in BAE Systems North America, Advanced Information Technology Division at Burlington, MA. She is the recipient of an NSF CAREER Award 2007 in Operations Research for her work in distributed multi-agent optimization. She is a recipient (jointly with her co-authors) of the Best Paper Award at the Winter Simulation Conference 2013 and the Best Paper Award at the International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) 2015. Also, she is a coauthor of the book Convex Analysis and Optimization. Her current interest is in large-scale optimization, games, control and information processing in networks.
Abstract
Hypergraph partitioning is an important problem in machine learning, computer vision, VLSI design and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of placing hyperedges across clusters. Algorithmic solutions for this approach assume that different partitions of a hyperedge incur the same cost. However, this assumption fails to address settings in which different subsets of vertices in the same hyperedge provide different contributions to the underlying higher order relations. To accommodate nonuniform partitioning costs, we introduce the notions of inhomogeneous spectral hypergraph partitioning and submodular hypergraphs. Inhomogeneous spectral partitioning produces a quadratic approximation to the optimal solution if the costs satisfy submodularity constraints. We illustrate the advantages of inhomogenous over classical hypergraph partitioning on applications as diverse as structure learning of rankings, subspace segmentation and motif clustering.
Biography
Olgica Milenkovic is a professor of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign (UIUC), and Research Professor at the Coordinated Science Laboratory. She obtained her Masters Degree in Mathematics in 2001 and PhD in Electrical Engineering in 2002, both from the University of Michigan, Ann Arbor. Prof. Milenkovic heads a group focused on addressing unique interdisciplinary research challenges spanning the areas of algorithm design and computing, bioinformatics, coding theory, machine learning and signal processing. Her scholarly contributions have been recognized by multiple awards, including the NSF Faculty Early Career Development (CAREER) Award, the DARPA Young Faculty Award, the Dean's Excellence in Research Award, and several best paper awards. In 2013, she was elected a UIUC Center for Advanced Study Associate and Willett Scholar while in 2015 she was elected a Distinguished Lecturer of the Information Theory Society. In 2018 she became an IEEE Fellow. She has served as Associate Editor of the IEEE Transactions of Communications, the IEEE Transactions on Signal Processing, the IEEE Transactions on Information Theory and the IEEE Transactions on Molecular, Biological and Multi-Scale Communications. In 2009, she was the Guest Editor in Chief of a special issue of the IEEE Transactions on Information Theory on Molecular Biology and Neuroscience.
Abstract
The modern era of big data increasingly requires outsourcing of large data sets to remote servers (the cloud). Remote storage gives rise to new challenges such as user privacy and information security in addition to the concerns about data integrity, communication efficiency and computation complexity. The goal of Private Information Retrieval (PIR) is to allow users to efficiently access desired records from remotely stored datasets without revealing to the servers which records are desired. Recent information theoretic advances have led to capacity characterizations of PIR as well as several of its variants, and generated excitement for the future prospects of this rich research avenue. This is especially significant because PIR is a point of convergence of complementary perspectives. Indeed, PIR is the lens through which information theoretic analysis may be applied to a number of interconnected issues -- ranging from practical concerns such as privacy, security, integrity and computation complexity of distributed storage to broader theoretical ideas such as the structure of information and interference alignment. It is well known that PIR shares intimate connections to prominent problems in theoretical computer science and cryptography, communication and information theory, and coding and signal processing. As such, discoveries in PIR have the potential for a ripple effect in their impact on a number of related problems. The talk will highlight such connections, with special focus on privacy, security, locality, cross-subspace alignment and secure distributed matrix multiplication.
Biography
Syed Ali Jafar received his B. Tech. from IIT Delhi, India, in 1997, M.S. from Caltech, USA, in 1999, and Ph.D. from Stanford, USA, in 2003, all in Electrical Engineering. His industry experience includes positions at Lucent Bell Labs and Qualcomm. He is a Professor in the Department of Electrical Engineering and Computer Science at the University of California Irvine, Irvine, CA USA. His research interests include multiuser information theory, wireless communications and network coding.
Dr. Jafar is a recipient of the New York Academy of Sciences Blavatnik National Laureate in Physical Sciences and Engineering, the NSF CAREER Award, the ONR Young Investigator Award, the UCI Academic Senate Distinguished Mid-Career Faculty Award for Research, the School of Engineering Mid-Career Excellence in Research Award and the School of Engineering Maseeh Outstanding Research Award. His co-authored papers have received the IEEE Information Theory Society Best Paper Award, IEEE Communications Society Best Tutorial Paper Award, IEEE Communications Society Heinrich Hertz Award, IEEE Signal Processing Society Young Author Best Paper Award, IEEE Information Theory Society Jack Wolf ISIT Best Student Paper Award, and three IEEE GLOBECOM Best Paper Awards. Dr. Jafar received the UC Irvine EECS Professor of the Year award six times, in 2006, 2009, 2011, 2012, 2014 and 2017 from the Engineering Students Council, a School of Engineering Teaching Excellence Award in 2012, and a Senior Career Innovation in Teaching Award in 2018. He was a University of Canterbury Erskine Fellow in 2010 and an IEEE Communications Society Distinguished Lecturer for 2013-2014. Dr. Jafar was recognized as a Thomson Reuters/Clarivate Analytics Highly Cited Researcher and included by Sciencewatch among The World's Most Influential Scientific Minds in 2014, 2015, 2016 and 2017. He served as Associate Editor for IEEE Transactions on Communications 2004-2009, for IEEE Communications Letters 2008-2009 and for IEEE Transactions on Information Theory 2009-2012. He is a Fellow of the IEEE.
