Fall 2018 SIP Seminars
Dr. David Karpuk
Title: Private Computation
Abstract: Private Information Retrieval (PIR) is the problem of downloading a file from a database without revealing to the database which file is being downloaded. This problem has been studied extensively from an information-theoretic perspective over the past few years, and schemes which achieve the optimal download rate are known for a variety of generalizations of the PIR problem. Private Computation (PC) is a generalization of the PIR problem in which a user wishes to compute an arbitrary function of the database, without revealing the identity of the function. Much less is known about this problem, especially when the function one wishes to compute is not linear. In this talk we will give a survey of the current state-of-the-art in PIR and construct some explicit PC schemes for computing polynomial functions. We will conclude by discussing some very recent progress on the problem of Private Search, in which a user wishes to search a database for a file close to their own file, while hiding the contents of their file.
Biography: David Karpuk received his Ph.D. in Mathematics from the University of Maryland, College Park in 2012. As a Postdoctoral Researcher at Aalto University, Finland from 2012-2017, his research focused on applying algebraic and number-theoretic tools to problems in coding theory and wireless communications. Since Fall 2017 he has been an Assistant Professor at Universidad de los Andes, Bogotá, Colombia, and his current research interests involve privacy and security in distributed computation.
Dr. Alex Dytso
Title: Generalized Gaussian Distributions in Estimation and Information Theory
Abstract: This talk will focus on the family of distributions termed Generalized Gaussian (GG). The family of GG distributions has received considerable attention from the engineering community, due to the flexible parametric form of its probability density function, and used for modeling many physical phenomena. Roughly the talk will consist of four parts. In the first part of the talk, we will consider problems of estimation of GG random variables in the presence of Gaussian noise. Due to the fact that the pdf of GG distributions is not always analytic, the Bayesian Cramer-Rao lower bound in this setting is either too lose or does not exist. We will show a new class of lower bounds that are based on the study of non-Gaussianity and are tight in this setting. The GG data sources are ubiquitous, thus it is important to understand the fundamental limits of lossy compression of GG sources. In the second part of the talk, we will discuss the lossy compression of GG sources. Closed-form expressions for the rate-distortion curves will be given. Along the way, we will show previously unknown properties of the GG distribution. For example, a complete characterization of conditions under which GG random variables are infinitely divisible and self-decomposable will be given. The third part of the talk will focus on communication over channels with additive GG noise. The GG distributions can model impulsive noise environments such as acoustic under-water noise and interference in ultrawideband systems with time-hopping. The final part is an outlook focusing on the open problems and future directions.
Biography: Alex Dytso is currently a Postdoctoral Researcher in the Department of Electrical Engineering at Princeton University working under the supervision of Professor H. Vincent Poor. He received a Ph.D. degree from the Department of Electrical and Computer Engineering at the University of Illinois at Chicago (UIC) under the supervision of Daniela Tuninetti and Natasha Devroye. He received his B. S. degree in 2011 from the University of Illinois at Chicago where he received International Engineering Consortium’s William L. Everitt Student Award of Excellence for outstanding seniors, who have demonstrated an interest in the communications field. His current research topic focuses on multi-user information and estimation theories and their applications to wireless networks.
Zhixiong Yang
Title: Distributed Learning Under Byzantine Failures
Abstract: Distributed machine learning algorithms enable learning of models from datasets that are distributed over a network without gathering the data at a centralized location. While efficient distributed algorithms have been developed under the assumption of faultless networks, failures that can render these algorithms nonfunctional occur frequently in the real world. This talk focuses on the problem of Byzantine failures, which are the hardest to safeguard against in distributed algorithms. While Byzantine fault tolerance has a rich history, existing work does not translate into efficient and practical algorithms for high-dimensional distributed learning. In this talk, two variants of an algorithm termed Byzantine-resilient distributed coordinate descent (ByRDiE) are introduced that enable distributed learning in the presence of Byzantine failures. Theoretical analysis and numerical experiments presented highlight the usefulness of ByRDiE for high-dimensional distributed learning in the presence of Byzantine failures.
Biography: Zhixiong Yang received the B.E. degree (with Honors) in electrical engineering from Beijing Jiaotong University, Beijing, China, in 2011. He is currently a Ph.D. student with the Department of Electrical and Computer Engineering, Rutgers University-New Brunswick, NJ, USA. His research interests include distributed optimization methods, robust learning algorithms, and learning under adversarial settings.
Dr. Shirin Jalali
Title: Compression Codes for Efficient Data Acquisition
Abstract: With more than a century of research and development, data compression is a relatively mature field with impressive practical results on one hand, and a solid information-theoretic background on the other. Commercial image and video compression codes are carefully-designed algorithms that take advantage of intricate structures that exist in natural images or video files to encode them as efficiently as possible. On the other hand, exploiting a signal’s structure to design more efficient data acquisition systems, as done in compressed sensing or phase retrieval, is a relatively new research endeavor with its actual impact starting to emerge in few industries. However, comparing signal structures used by typical data compression codes with those used by modern data acquisition systems readily reveals the big gap between the two. This motivates us to ask the following question: can we design a data acquisition algorithm that employs an existing compression code as a mechanism to define and impose structure? An affirmative answer to this question potentially leads to much more efficient data acquisition systems that exploit complex structures, much beyond those already used in such systems. In this talk, we focus on addressing this question and show that not only the answer to this question is theoretically affirmative, but also there are efficient compression-based recovery algorithms that can achieve state-of-the-art performance, for instance, in imaging systems.
Biography: Shirin Jalali is a research scientist in the Mathematics and Algorithms Group at Nokia Bell Labs in Murray Hills, NJ. Prior to that she held positions as a research scholar at the department of Electrical Engineering at Princeton University and as a faculty fellow at NYU Tandon School of Engineering. She received her B.Sc. and M.Sc. degrees in Electrical Engineering from Sharif University of Technology. She obtained her M.Sc. in Statistics and Ph.D. in Electrical Engineering from Stanford University. Her research interests are in the areas of information theory, high-dimensional statistics and machine learning.
Prof. Mert Gurbuzbalaban
Title: Momentum Acceleration Under Random Gradient Noise: From Convex to Non-convex Optimization
Abstract: For many large-scale optimization and machine learning problems, first-order methods and their accelerated variants based on momentum have been a leading approach for computing low-to-medium accuracy solutions because of their cheap iterations and mild dependence on the problem dimension and data size. Even though momentum-based accelerated gradient (AG) methods proposed by Nesterov for convex optimization converges provably faster than gradient descent (GD) in the absence of noise, the comparison is no longer clear in the presence of gradient noise.
In the first part of the talk, we focus on GD and AG methods for minimizing strongly convex functions when the gradient has random errors in the form of additive i.i.d. noise. We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. Our results show that AG can achieve acceleration while being more robust to random gradient errors. Our framework also leads to practical algorithms that can perform better than other state-of-the-art methods in the presence of random gradient noise. This is joint work with Serhat Aybat, Alireza Fallah and Asu Ozdaglar.
In the second part of the talk, we focus on non-convex optimization and study the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm, which is a popular variant of the stochastic gradient with momentum where a controlled and properly scaled Gaussian noise is added to the unbiased gradient estimates to steer them towards a global minimum. We obtain first-time non-asymptotic global convergence guarantees for SGHMC for both empirical risk and population risk optimization problems. Our results demonstrate that momentum-based Monte Carlo algorithms can lead to better iteration complexity as well as generalization performance compared to known guarantees for the (reversible) standard stochastic gradient Langevin Monte Carlo methods, justifying the use of momentum in the context of non-convex optimization and non-convex learning further. This is joint work with Xuefeng Gao and Lingjiong Zhu.
Biography: Mert Gürbüzbalaban is an assistant professor at Rutgers University. Previously, he was apostdoctoral associate at the Laboratory for Information and Decision Systems (LIDS) at MIT. He is broadly interested in optimization and computational science driven by applications in large-scale information and decision systems. He received his B.Sc. degrees in Electrical Engineering and Mathematics as a valedictorian from Boğaziçi University, Istanbul, Turkey, the “Diplôme d’ingénieur” degree from École Polytechnique, France, and the M.S. and Ph.D. degrees in (Applied) Mathematics from the Courant Institute of Mathematical Sciences, New York University. Dr. Gürbüzbalaban received the Kurt Friedrichs Prize (given by the Courant Institute of New York University for an outstanding thesis) in 2013, Bronze Medal in the École Polytechnique Scientific Project Competition in 2006, the Nadir Orhan Bengisu Award (given by the electrical-electronics engineering department of Boğaziçi University to the best graduating undergraduate student) in 2005 and the Bülent Kerim Altay Award from the Electrical-Electronics Engineering Department of Middle East Technical University in 2001. He received funding from a variety of sources including multiple programs at the U.S. National Science Foundation.