TILOS Seminar: How to use Machine Learning for Combinatorial Optimization
Sherief Reda, Professor, Brown University and Principal Research Scientist at Amazon
Combinatorial optimization methods are routinely used in many scientific fields to identify optimal solutions among a large but finite set of possible solutions for problems of interests. Given the recent success of machine learning techniques in classification of natural signals (e.g., voice, image, text), it is natural to ask how machine learning methods can be used to improve the quality of solution or the runtime of combinatorial optimization algorithms? In this talk I will provide a general taxonomy and research directions for the use of machine learning techniques in combinatorial optimization. I will illustrate these directions using a number of case studies from my group's research, which include (1) improving the quality of results of integer linear programming (ILP) solver using deep metric learning, and (2) using reinforcement learning techniques to optimize the size of graphs arising in digital circuit design.
Sherief Reda is a Full Professor at the School of Engineering and Computer Science Department at Brown University and a Principal Research Scientist at Amazon. He joined Brown University in 2006 after receiving his Ph.D. in computer science and engineering from University of California, San Diego. He has over 135 research articles in the areas of energy-efficient computing, electronic design automation and combinatorial optimization, as well as several patents. Professor Reda received a number of research acknowledgments and awards, including eight best paper nominations, three best paper awards, and a National Science Foundation CAREER award. He has been a PI or co-PI on more than $21.1M of funded projects from federal agencies and industry corporations. He is a senior member of IEEE.
TILOS Seminar: Reasoning Numerically
Sicun Gao, Assistant Professor, UC San Diego
Highly-nonlinear continuous functions have become a pervasive model of computation. Despite newsworthy progress, the practical success of “intelligent” computing is still restricted by our ability to answer questions regarding their quality and dependability: How do we rigorously know that a system will do exactly what we want it to do and nothing else? For traditional software and hardware systems that primarily use digital and rule-based designs, automated reasoning has provided the fundamental principles and widely-used tools for ensuring their quality in all stages of design and engineering. However, the rigid symbolic formulations of typical automated reasoning methods often make them unsuitable for dealing with computation units that are driven by numerical and data-driven approaches. I will overview some of our attempts in bridging this gap. I will highlight how the core challenge of NP-hardness is shared across discrete and continuous domains, and how it motivates us to seek the unification of symbolic, numerical, and statistical perspectives towards better understanding and handling of the curse of dimensionality.
Sicun Gao is an Assistant Professor in Computer Science and Engineering at the University of California, San Diego. He works on search and optimization algorithms for improving the quality of automation and autonomous systems. He is a recipient of the Air Force Young Investigator Award, Amazon Research Award, NSF Career Award, and Silver Medal for the Kurt Godel Research Prize. He received his PhD from Carnegie Mellon University and was a postdoctoral researcher at CMU and MIT.
TILOS Seminar: Deep Generative Models and Inverse Problems
Alexandros G. Dimakis, Professor, The University of Texas at Austin
Sparsity has given us MP3, JPEG, MPEG, Faster MRI and many fun mathematical problems. Deep generative models like GANs, VAEs, invertible flows and Score-based models are modern data-driven generalizations of sparse structure. We will start by presenting the CSGM framework by Bora et al. to solve inverse problems like denoising, filling missing data, and recovery from linear projections using an unsupervised method that relies on a pre-trained generator. We generalize compressed sensing theory beyond sparsity, extending Restricted Isometries to sets created by deep generative models. Our recent results include establishing theoretical results for Langevin sampling from full-dimensional generative models, generative models for MRI reconstruction and fairness guarantees for inverse problems.
Alexandros G. Dimakis is a Professor at the ECE department at UT Austin and the co-director of the National AI Institute on the Foundations of Machine Learning (IFML). He received his Ph.D. from UC Berkeley and the Diploma degree from the National Technical University of Athens. He received several awards including the James Massey Award, NSF Career, a Google research award, the UC Berkeley Eli Jury dissertation award and several best paper awards. He served as an Associate editor for IEEE Transactions on Information Theory and as an Area Chair for major Machine Learning conferences (NeurIPS, ICML, AAAI) and as the chair of the Technical Committee for MLSys 2021. He was selected as an IEEE Fellow for contributions to distributed coding and learning. His research interests include information theory, coding theory and machine learning.
TILOS Seminar: Learning in the Presence of Distribution Shifts: How does the Geometry of Perturbations Play a Role?
Hamed Hassani, Assistant Professor, University of Pennsylvania
In this talk, we will focus on the emerging field of (adversarially) robust machine learning. The talk will be self-contained and no particular background on robust learning will be needed. Recent progress in this field has been accelerated by the observation that despite unprecedented performance on clean data, modern learning models remain fragile to seemingly innocuous changes such as small, norm-bounded additive perturbations. Moreover, recent work in this field has looked beyond norm-bounded perturbations and has revealed that various other types of distributional shifts in the data can significantly degrade performance. However, in general our understanding of such shifts is in its infancy and several key questions remain unaddressed.
The goal of this talk is to explain why robust learning paradigms have to be designed—and sometimes rethought—based on the geometry of the input perturbations. We will cover a wide range of perturbation geometries from simple norm-bounded perturbations, to sparse, natural, and more general distribution shifts. As we will show, the geometry of the perturbations necessitates fundamental modifications to the learning procedure as well as the architecture in order to ensure robustness. In the first part of the talk, we will discuss our recent theoretical results on robust learning with respect to various geometries, along with fundamental tradeoffs between robustness and accuracy, phase transitions, etc. The remaining portion of the talk will be about developing practical robust training algorithms and evaluating the resulting (robust) deep networks against state-of-the-art methods on naturally-varying, real-world datasets.
TILOS Seminar: The Connections Between Discrete Geometric Mechanics, Information Geometry, Accelerated Optimization and Machine Learning
Melvin Leok, Professor of Mathematics, UC San Diego
Geometric mechanics describes Lagrangian and Hamiltonian mechanics geometrically, and information geometry formulates statistical estimation, inference, and machine learning in terms of geometry. A divergence function is an asymmetric distance between two probability densities that induces differential geometric structures and yields efficient machine learning algorithms that minimize the duality gap. The connection between information geometry and geometric mechanics will yield a unified treatment of machine learning and structure-preserving discretizations. In particular, the divergence function of information geometry can be viewed as a discrete Lagrangian, which is a generating function of a symplectic map, that arise in discrete variational mechanics. This identification allows the methods of backward error analysis to be applied, and the symplectic map generated by a divergence function can be associated with the exact time-h flow map of a Hamiltonian system on the space of probability distributions. We will also discuss how time-adaptive Hamiltonian variational integrators can be used to discretize the Bregman Hamiltonian, whose flow generalizes the differential equation that describes the dynamics of the Nesterov accelerated gradient descent method.
Melvin Leok is professor of mathematics and co-director of the CSME graduate program at the UC San Diego. His research interests are in computational geometric mechanics, computational geometric control theory, discrete geometry, and structure-preserving numerical schemes, and particularly how these subjects relate to systems with symmetry. He received his Ph.D. in 2004 from the California Institute of Technology in Control and Dynamical Systems under the direction of Jerrold Marsden. He is a three-time NAS Kavli Frontiers of Science Fellow, a Simons Fellow in Mathematics, and has received the DoD Newton Award for Transformative Ideas, the NSF Faculty Early Career Development (CAREER) award, the SciCADE New Talent Prize, the SIAM Student Paper Prize, and the Leslie Fox Prize (second prize) in Numerical Analysis. He has given plenary talks at Foundations of Computational Mathematics, NUMDIFF, and the IFAC Workshop on Lagrangian and Hamiltonian Methods for Nonlinear Control. He serves on the editorial boards of the Journal of Nonlinear Science, the Journal of Geometric Mechanics, and the Journal of Computational Dynamics, and has served on the editorial boards of the SIAM Journal on Control and Optimization, and the LMS Journal of Computation and Mathematics.
TILOS Seminar: MCMC vs. Variational Inference for Credible Learning and Decision Making at Scale
Yian Ma, Assistant Professor, UC San Diego
Professor Ma will introduce some recent progress towards understanding the scalability of Markov chain Monte Carlo (MCMC) methods and their comparative advantage with respect to variational inference. Further, he will discuss an optimization perspective on the infinite dimensional probability space, where MCMC leverages stochastic sample paths while variational inference projects the probabilities onto a finite dimensional parameter space. Three ingredients will be the focus of this discussion: non-convexity, acceleration, and stochasticity. This line of work is motivated by epidemic prediction, where we need uncertainty quantification for credible predictions and informed decision making with complex models and evolving data.
Yian Ma is an assistant professor at the Halıcıoğlu Data Science Institute and an affiliated faculty member at the Computer Science and Engineering Department of University of California San Diego. Prior to UC San Diego, he spent a year as a visiting faculty at Google Research. Before that, he was a post-doctoral fellow at EECS, UC Berkeley. Professor Ma completed his Ph.D. at University of Washington and obtained my bachelor's degree at Shanghai Jiao Tong University.
His current research primarily revolves around scalable inference methods for credible machine learning. This involves designing Bayesian inference methods to quantify uncertainty in the predictions of complex models; understanding computational and statistical guarantees of inference algorithms; and leveraging these scalable algorithms to learn from time series data and perform sequential decision making tasks.
TILOS Seminar: A Mixture of Past, Present, and Future
Arya Mazumdar, Associate Professor, UC San Diego
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, a standard technique is the use of mixture models for statistical inference. However for supervised learning, labels can be generated via a mixture of functional relationships. We will provide a survey of results on parameter learning in mixture models, some unexpected connections with other problems, and some interesting future directions.