TILOS-OPTML++ Seminar: Optimization, Robustness and Privacy in Deep Neural Networks: Insights from the Neural Tangent Kernel
2023-11-08 11:00 - 12:00 (America/Los_Angeles) | Virtual
Marco Mondelli, Institute of Science and Technology Austria
Abstract: A recent line of work has analyzed the properties of deep over-parameterized neural networks through the lens of the Neural Tangent Kernel (NTK). In this talk, I will show how concentration bounds on the NTK (and, specifically, on its smallest eigenvalue) provide insights on (i) the optimization of the network via gradient descent, (ii) its adversarial robustness, and (iii) its privacy guarantees. I will start by proving tight bounds on the smallest eigenvalue of the NTK for deep neural networks with minimum over-parameterization. This implies that the network optimized by gradient descent interpolates the training dataset (i.e., reaches 0 training loss), as soon as the number of parameters is information-theoretically optimal. Next, I will focus on two properties of the interpolating solution: robustness and privacy. A thought-provoking paper by Bubeck and Sellke has proposed a “universal law of robustness”: interpolating smoothly the data necessarily requires many more parameters than simple memorization. By providing sharp bounds on random features (RF) and NTK models, I will show that, while the RF model is never robust (regardless of the over-parameterization), the NTK model saturates the universal law of robustness, addressing a conjecture by Bubeck, Li and Nagaraj. Finally, I will study the safety of RF and NTK models against a family of powerful black-box information retrieval attacks: the proposed analysis shows that safety provably strengthens with an increase in the generalization capability, unveiling the role of the model and of its activation function.

Marco Mondelli received the B.S. and M.S. degree in Telecommunications Engineering from the University of Pisa, Italy, in 2010 and 2012, respectively. In 2016, he obtained his Ph.D. degree in Computer and Communication Sciences at the École Polytechnique Fédérale de Lausanne (EPFL), Switzerland. He is currently an Assistant Professor at the Institute of Science and Technology Austria (ISTA). Prior to that, he was a Postdoctoral Scholar in the Department of Electrical Engineering at Stanford University, USA, from February 2017 to August 2019. He was also a Research Fellow with the Simons Institute for the Theory of Computing, UC Berkeley, USA, for the program on Foundations of Data Science from August to December 2018. His research interests include data science, machine learning, information theory, and modern coding theory. He was the recipient of a number of fellowships and awards, including the Jack K. Wolf ISIT Student Paper Award in 2015, the STOC Best Paper Award in 2016, the EPFL Doctorate Award in 2018, the Simons-Berkeley Research Fellowship in 2018, the Lopez-Loreta Prize in 2019, and Information Theory Society Best Paper Award in 2021.

Boston Symmetry Day 2023
2023-11-03 | MIT
TILOS is a sponsor of Boston Symmetry Day, a meeting of symmetry-minded folks in the Boston area. It is the largest event on symmetry and machine learning in the United States. Registration is free for all who would like to attend, subject to space constraints.

TILOS Seminar: Building Personalized Decision Models with Federated Human Preferences
2023-11-02 11:00 - 12:00 | HDSI 123 and Virtual, 3234 Matthews Ln, La Jolla, CA, 92093, United States
Aadirupa Saha, Research Scientist, Apple
Abstract: Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: “Do you prefer Item A over B?”, rather than their absolute counterparts: “How much do you score items A and B on a scale of [0-10]?”. Drawing inspirations, in the search for a more effective feedback collection mechanism, led to the famous formulation of Dueling Bandits (DB), which is a widely studied online learning framework for efficient information aggregation from relative/comparative feedback. However despite the novel objective, unfortunately, most of the existing DB techniques were limited only to simpler settings of finite decision spaces, and stochastic environments, which are unrealistic in practice. In this talk, we will start with the basic problem formulations for DB and familiarize ourselves with some of the breakthrough results. Following this, will dive deeper into a more practical framework of contextual dueling bandits (C-DB) where the goal of the learner is to make personalized predictions based on the user contexts. We will see a new algorithmic approach that can efficiently achieve the optimal O(sqrt T) regret performance for this problem, resolving an open problem from Dudík et al. [COLT, 2015]. In the last part of the talk, we will extend the aforementioned models to a federated framework, which entails developing preference-driven prediction models for distributed environments for creating large-scale personalized systems, including recommender systems and chatbot interactions. Apart from exploiting the limited preference feedback model, the challenge lies in ensuring user privacy and reducing communication complexity in the federated setting. We will conclude the talk with some interesting open problems.

Aadirupa is currently a research scientist at Apple ML research, broadly working in the area of Machine Learning theory. She did a short-term research visit at Toyota Technological Institute, Chicago (TTIC), after finishing her postdoc at Microsoft Research New York City. She obtained her Ph.D. from IISc Bangalore with Aditya Gopalan and Chiranjib Bhattacharyya. Website: https://aadirupa.github.io

TILOS Seminar: Towards Foundation Models for Graph Reasoning and AI 4 Science
2023-10-11 10:00 - 11:00 | HDSI 123 and Virtual, 3234 Matthews Ln, La Jolla, CA, 92093, United States
Michael Galkin, Research Scientist, Intel AI Lab
Abstract: Foundation models in graph learning are hard to design due to the lack of common invariances that transfer across different structures and domains. In this talk, I will give an overview of the two main tracks of my research at Intel AI: creating foundation models for knowledge graph reasoning that can run zero-shot inference on any multi-relational graphs, and foundation models for materials discovery in the AI4Science domain that capture physical properties of crystal structures and transfer to a variety of predictive and generative tasks. We will also talk about theoretical and practical challenges like scaling behavior, data scarcity, and diverse evaluation of foundation graph models.

Michael Galkin is a Research Scientist at Intel AI Lab in San Diego working on Graph Machine Learning and Geometric Deep Learning. Previously, he was a postdoc at Mila–Quebec AI Institute with Will Hamilton, Reihaneh Rabbany, and Jian Tang, focusing on many graph representation learning problems. Sometimes, Mike writes long blog posts on Medium about graph learning.

TILOS Fireside Chat on Theory in the Age of Modern AI
2023-10-04 09:30 - 10:30 | Virtual
The first TILOS Fireside Chat of Fall 2023 will be a conversation about theory in the age of modern AI led by TILOS members Nisheeth Vishnoi, Tara Javidi, Misha Belkin, and Arya Mazumdar (moderator). This will be a great opportunity to discuss implications of AI and roles of theory (especially with the recent development in LLMs), and an exciting way to start the third year of TILOS!

TILOS Seminar: Machine Learning from Weak, Noisy, and Biased Supervision
2023-09-18 10:00 - 11:00 | Virtual
Masashi Sugiyama, University of Tokyo and RIKEN
Abstract: In statistical inference and machine learning, we face a variety of uncertainties such as training data with insufficient information, label noise, and bias. In this talk, I will give an overview of our research on reliable machine learning, including weakly supervised classification (positive unlabeled classification, positive confidence classification, complementary label classification, etc.), noisy label classification (noise transition estimation, instance-dependent noise, clean sample selection, etc.), and transfer learning (joint importance-predictor estimation for covariate shift adaptation, dynamic importance estimation for full distribution shift, continuous distribution shift, etc.).

AI Ethics Roundtable
2023-06-02 09:00 - 10:00 | Virtual
The TILOS Ethics and Early Career Committee invites you to an upcoming round table discussion on AI Ethics. This will take place virtually through Zoom on Friday, June 2, 2023 at 9am Pacific / 11am Central / Noon Eastern.
Please join Dr. Nisheeth Vishnoi from Yale, Dr. David Danks from UC San Diego, and Dr. Hoda Heidari from Carnegie Mellon University as we discuss a variety of aspects of AI Ethics with our moderators Dr. Stefanie Jegelka from MIT and Dr. Jodi Reeves from National University. This event is a great opportunity for TILOS students to learn about the constantly evolving issues of AI Ethics in research and the societal impact of AI. It will also provide a platform for students to gain insights and valuable advice that can help them in their future career pursuits.

Nisheeth Vishnoi is the A. Bartlett Giamatti Professor of Computer Science and a co-founder of the Computation and Society Initiative at Yale University. He studies the foundations of computation, and his research spans several areas of theoretical computer science, optimization, and machine learning. He is also interested in understanding nature and society from a computational viewpoint. Here, his current focus includes understanding the emergence of intelligence and developing methods to address ethical issues at the interface of artificial intelligence and humanity.

David Danks is Professor of Data Science & Philosophy and affiliate faculty in Computer Science & Engineering at University of California, San Diego. His research interests range widely across philosophy, cognitive science, and machine learning, including their intersection. Danks has examined the ethical, psychological, and policy issues around AI and robotics across multiple sectors, including transportation, healthcare, privacy, and security. He has also done significant research in computational cognitive science and developed multiple novel causal discovery algorithms for complex types of observational and experimental data. Danks is the recipient of a James S. McDonnell Foundation Scholar Award, as well as an Andrew Carnegie Fellowship. He currently serves on multiple advisory boards, including the National AI Advisory Committee.

Hoda Heidari is an Assistant Professor in Machine Learning and Societal Computing at the School of Computer Science, Carnegie Mellon University. Her research is broadly concerned with the social, ethical, and economic implications of Artificial Intelligence. In particular, her research addresses issues of unfairness and accountability through Machine Learning. Her work in this area has won a best-paper award at the ACM Conference on Fairness, Accountability, and Transparency (FAccT) and an exemplary track award at the ACM Conference on Economics and Computation (EC). She has organized several scholarly events on topics related to Responsible and Trustworthy AI, including a tutorial at the Web Conference (WWW) and several workshops at the Neural and Information Processing Systems (NeurIPS) conference. Dr. Heidari completed her doctoral studies in Computer and Information Science at the University of Pennsylvania. She holds an M.Sc. degree in Statistics from the Wharton School of Business. Before joining Carnegie Mellon as a faculty member, she was a postdoctoral scholar at the Machine Learning Institute of ETH Zurich, followed by a year at the Artificial Intelligence, Policy, and Practice (AIPP) initiative at Cornell University.

TILOS Seminar: Learning from Diverse and Small Data
2023-05-19 10:00 - 11:00 | Virtual
Ramya Korlakai Vinayak, Assistant Professor, University of Wisconsin–Madison
Abstract: Machine learning (ML) algorithms are becoming ubiquitous in various application domains such as public health, genomics, psychology, and social sciences. In these domains, data is often obtained from populations that are diverse, e.g., varying demographics, phenotypes, preferences etc. Many ML algorithms focus on learning model parameters that work well on average over the population but do not capture the diversity. On the other hand, such datasets usually have few observations per individual that limits our ability to learn about each individual separately. Question of interest in these scenarios is, how can we reliably capture the diversity in the data in small data settings?
In this talk, we will address this question in the following settings:
(i) In many applications, we observe count data which can be modeled as Binomial (e.g., polling, surveys, epidemiology) or Poisson (e.g., single cell RNA data) data. As a single or finite parameters do not capture the diversity of the population in such datasets, they are often modeled as nonparametric mixtures. In this setting, we will address the following question, “how well can we learn the distribution of parameters over the population without learning the individual parameters?” and show that nonparametric maximum likelihood estimators are in fact minimax optimal.
(ii) Learning preferences from human judgements using comparison queries plays a crucial role in cognitive and behavioral psychology, crowdsourcing democracy, surveys in social science applications, and recommendation systems. Models in the literature often focus on learning average preference over the population due to the limitations on the amount of data available per individual. We will discuss some recent results on how we can reliably capture diversity in preferences while pooling together data from individuals.

Ramya Korlakai Vinayak is an assistant professor in the Dept. of ECE and affiliated faculty in the Dept. of Computer Science and the Dept. of Statistics at the University of Wisconsin–Madison. Her research interests span the areas of machine learning, statistical inference, and crowdsourcing. Her work focuses on addressing theoretical and practical challenges that arise when learning from societal data. Prior to joining UW Madison, Ramya was a postdoctoral researcher in the Paul G. Allen School of Computer Science and Engineering at the University of Washington. She received her Ph.D. in Electrical Engineering from Caltech. She obtained her Masters from Caltech and Bachelors from IIT Madras. She is a recipient of the Schlumberger Foundation Faculty of the Future fellowship from 2013-15, and an invited participant at the Rising Stars in EECS workshop in 2019. She is the recipient of NSF CAREER Award 2023-2028.

TILOS Seminar: The Hidden Convex Optimization Landscape of Deep Neural Networks
2023-05-15 14:30 - 15:30 | Virtual
Mert Pilanci, Stanford University
Abstract: Since deep neural network training problems are inherently non-convex, their recent dramatic success largely relies on non-convex optimization heuristics and experimental findings. Despite significant advancements, the non-convex nature of neural network training poses two central challenges: first, understanding the underlying mechanisms that contribute to model performance, and second, achieving efficient training with low computational cost and energy consumption. The performance of non-convex models is notably influenced by the selection of optimization methods and hyperparameters, including initialization, mini-batching, and step sizes. Conversely, convex optimization problems are characterized by their robustness to these choices, allowing for the efficient and consistent achievement of globally optimal solutions, irrespective of optimization parameters. In this talk, we explore a novel perspective by examining multilayer neural networks equipped with ReLU activation functions through the framework of convex optimization. We introduce exact convex optimization formulations of ReLU network training problems. We show that two-layer ReLU networks can be globally trained via convex programs with the number of variables polynomial in the number of training samples, feature dimension, and the number of hidden neurons. We show that our analysis extends to deeper networks and that these convex programs possess an intuitive geometric interpretation. Our results provide an equivalent characterization of neural networks as convex models where a mixture of locally linear models are fitted to the data with sparsity inducing convex regularization. Moreover, we show that standard convolutional neural networks can be globally optimized in fully polynomial time. We discuss extensions to batch normalization, generative adversarial networks and transformers. Finally, we present numerical simulations verifying our claims and illustrating that the proposed convex approach is faster and more reliable than standard local search heuristics such as SGD and variants.

Mert Pilanci is an assistant professor of Electrical Engineering at Stanford University. He received his Ph.D. in Electrical Engineering and Computer Science from UC Berkeley in 2016. Prior to joining Stanford, he was an assistant professor of Electrical Engineering and Computer Science at the University of Michigan. In 2017, he was a Math+X postdoctoral fellow working with Emmanuel Candès at Stanford University. Mert’s research interests are in neural networks, machine learning, optimization, and signal processing. His group develops theory and algorithms for solving large scale optimization problems in machine learning. His research also seeks to develop safe and interpretable artificial intelligence and information theoretic foundations of distributed computing.

TILOS-OPTML++ Seminar: Sums of Squares: from Algebra to Analysis
2023-04-26 09:00 - 10:00 | Virtual
Francis Bach, NRIA, ENS, and PSL Paris
Abstract: The representation of non-negative functions as sums of squares has become an important tool in many modeling and optimization tasks. Traditionally applied to polynomial functions, it requires rich tools from algebraic geometry that led to many developments in the last twenty years. In this talk, I will look at this problem from a functional analysis point of view, leading to new applications and new results on the performance of sum-of-squares optimization.

Francis Bach is a researcher at Inria, leading since 2011 the machine learning team which is part of the Computer Science department at Ecole Normale Supérieure. He graduated from Ecole Polytechnique in 1997 and completed his Ph.D. in Computer Science at U.C. Berkeley in 2005, working with Professor Michael Jordan. He spent two years in the Mathematical Morphology group at Ecole des Mines de Paris, then he joined the computer vision project-team at Inria/Ecole Normale Supérieure from 2007 to 2010. Francis Bach is primarily interested in machine learning, and especially in sparse methods, kernel-based learning, large-scale optimization, computer vision and signal processing. He obtained in 2009 a Starting Grant and in 2016 a Consolidator Grant from the European Research Council, and received the Inria young researcher prize in 2012, the ICML test-of-time award in 2014 and 2019, as well as the Lagrange prize in continuous optimization in 2018, and the Jean-Jacques Moreau prize in 2019. He was elected in 2020 at the French Academy of Sciences. In 2015, he was program co-chair of the International Conference in Machine learning (ICML), and general chair in 2018; he is now co-editor-in-chief of the Journal of Machine Learning Research.

TILOS Seminar: ML Training Strategies Inspired by Humans’ Learning Skills
2023-04-19 10:00 - 11:00 | Virtual
Pengtao Xie, Assistant Professor, UC San Diego
Abstract: Humans, as the most powerful learners on the planet, have accumulated a lot of learning skills, such as learning through tests, interleaving learning, self-explanation, active recalling, to name a few. These learning skills and methodologies enable humans to learn new topics more effectively and efficiently. We are interested in investigating whether humans’ learning skills can be borrowed to help machines to learn better. Specifically, we aim to formalize these skills and leverage them to train better machine learning (ML) models. To achieve this goal, we develop a general framework, Skillearn, which provides a principled way to represent humans’ learning skills mathematically and use the formally-represented skills to improve the training of ML models. In two case studies, we apply Skillearn to formalize two learning skills of humans: learning by passing tests and interleaving learning, and use the formalized skills to improve neural architecture search.

Pengtao Xie is an assistant professor at UC San Diego. He received his PhD from the Machine Learning Department at Carnegie Mellon University in 2018. His research interests lie in machine learning inspired by human learning and its applications in healthcare. His research outcomes have been adopted by medical device companies, medical imaging centers, hospitals, etc. and have been published at top-tier artificial intelligence conferences and journals including ICML, NeurIPS, ACL, ICCV, TACL, etc. He is the recipient of the Tencent AI-Lab Faculty Award, Tencent WeChat Faculty Award, the Innovator Award presented by the Pittsburgh Business Times, the Siebel Scholars award, and the Goldman Sachs Global Leader Scholarship.

TILOS Seminar: Engineering the Future of Software with AI
2023-02-15 10:00 - 11:00 | Virtual
Dr. Ruchir Puri, Chief Scientist, IBM Research, IBM Fellow, Vice-President IBM Corporate Technology
Abstract: Software has become woven into every aspect of our society, and it will be fair to say that “Software has eaten the world.” More recently, advances in AI are starting to transform every aspect of our society as well. These two tectonic forces of transformation, software and AI, are colliding together resulting in a seismic shift—a future where software itself will be built, maintained, and operated by AI—pushing us towards a future where “Computers can program themselves!” In this talk, we will discuss these forces of “AI for Code” and how the future of software engineering is being redefined by AI.

TILOS Seminar: Causal Discovery for Root Cause Analysis
2023-01-18 10:00 - 11:00 | Virtual
Murat Kocaoglu, Assistant Professor, Purdue University
Abstract: Cause-effect relations are crucial for several fields, from medicine to policy design as they inform us of the outcomes of our actions a priori. However, causal knowledge is hard to curate for complex systems that might be changing frequently. Causal discovery algorithms allow us to extract causal knowledge from the available data. In this talk, first, we provide a short introduction to algorithmic causal discovery. Next, we propose a novel causal discovery algorithm from a collection of observational and interventional datasets in the presence of unobserved confounders, with unknown intervention targets. Finally, we demonstrate the effectiveness of our algorithm for root-cause analysis in microservice architectures.

TILOS Seminar: Rare Gems: Finding Lottery Tickets at Initialization
2022-11-16 10:00 - 11:00 | Virtual
Dimitris Papailiopoulos, Associate Professor, University of Wisconsin–Madison
Abstract: Large neural networks can be pruned to a small fraction of their original size, with little loss in accuracy, by following a time-consuming “train, prune, re-train” approach. Frankle & Carbin in 2019 conjectured that we can avoid this by training lottery tickets, i.e., special sparse subnetworks found at initialization, that can be trained to high accuracy. However, a subsequent line of work presents concrete evidence that current algorithms for finding trainable networks at initialization, fail simple baseline comparisons, e.g., against training random sparse subnetworks. Finding lottery tickets that train to better accuracy compared to simple baselines remains an open problem. In this work, we resolve this open problem by discovering Rare Gems: sparse, trainable networks at initialization, that achieve high accuracy even before training. When Rare Gems are trained with SGD, they achieve accuracy competitive or better than Iterative Magnitude Pruning (IMP) with warmup.

TILOS Seminar: Robust and Equitable Uncertainty Estimation
2022-10-12 10:00 - 11:00 | Virtual
Aaron Roth, Professor, University of Pennsylvania
Abstract: Machine learning provides us with an amazing set of tools to make predictions, but how much should we trust particular predictions? To answer this, we need a way of estimating the confidence we should have in particular predictions of black-box models. Standard tools for doing this give guarantees that are averages over predictions. For instance, in a medical application, such tools might paper over poor performance on one medically relevant demographic group if it is made up for by higher performance on another group. Standard methods also depend on the data distribution being static—in other words, the future should be like the past.
In this lecture, I will describe new techniques to address both these problems: a way to produce prediction sets for arbitrary black-box prediction methods that have correct empirical coverage even when the data distribution might change in arbitrary, unanticipated ways and such that we have correct coverage even when we zoom in to focus on demographic groups that can be arbitrary and intersecting. When we just want correct group-wise coverage and are willing to assume that the future will look like the past, our algorithms are especially simple.
This talk is based on two papers, that are joint work with Osbert Bastani, Varun Gupta, Chris Jung, Georgy Noarov, and Ramya Ramalingam.

TILOS Seminar: On Policy Optimization Methods for Control
2022-09-28 10:00 - 11:00 | Virtual
Maryam Fazel, Professor, University of Washington
Abstract: Policy Optimization methods enjoy wide practical use in reinforcement learning (RL) for applications ranging from robotic manipulation to game-playing, partly because they are easy to implement and allow for richly parameterized policies. Yet their theoretical properties, from optimality to statistical complexity, are still not fully understood. To help develop a theoretical basis for these methods, and to bridge the gap between RL and control theoretic approaches, recent work has studied whether gradient-based policy optimization can succeed in designing feedback control policies. In this talk, we start by showing the convergence and optimality of these methods for linear dynamical systems with quadratic costs, where despite nonconvexity, convergence to the optimal policy occurs under mild assumptions. Next, we make a connection between convex parameterizations in control theory on one hand, and the Polyak-Lojasiewicz property of the nonconvex cost function, on the other. Such a connection between the nonconvex and convex landscapes provides a unified view towards extending the results to more complex control problems.

TILOS Seminar: Non-convex Optimization for Linear Quadratic Gaussian (LQG) Control
2022-09-21 10:00 - 11:00 | Virtual
Yang Zheng, Assistant Professor, UC San Diego
Abstract: Recent studies have started to apply machine learning techniques to the control of unknown dynamical systems. They have achieved impressive empirical results. However, the convergence behavior, statistical properties, and robustness performance of these approaches are often poorly understood due to the non-convex nature of the underlying control problems. In this talk, we revisit the Linear Quadratic Gaussian (LQG) control and present recent progress towards its landscape analysis from a non-convex optimization perspective. We view the LQG cost as a function of the controller parameters and study its analytical and geometrical properties. Due to the inherent symmetry induced by similarity transformations, the LQG landscape is very rich yet complicated. We show that 1) the set of stabilizing controllers has at most two path-connected components, and 2) despite the nonconvexity, all minimal stationary points (controllable and observable controllers) are globally optimal. Based on the special non-convex optimization landscape, we further introduce a novel perturbed policy gradient (PGD) method to escape a large class of suboptimal stationary points (including high-order saddles). These results shed some light on the performance analysis of direct policy gradient methods for solving the LQG problem. The talk is based on our recent papers: https://arxiv.org/abs/2102.04393 and https://arxiv.org/abs/2204.00912.

TILOS Seminar: Machine Learning for Design Methodology and EDA Optimization
2022-08-17 10:00 - 11:00 | Virtual
Haoxing Ren, NVIDIA
Abstract: In this talk, I will first illustrate how ML helps improve design quality as well as design productivity from design methodology perspective with examples in digital and analog designs. Then I will discuss the potential of applying ML to solve challenging EDA optimization problems, focusing on three promising ML techniques: reinforcement learning (RL), physics-based modeling and self-supervised learning (SSL). RL learns to optimize the problem by converting the EDA problem objectives into environment rewards. It can be applied to both directly solve the EDA problem or be part of a conventional EDA algorithm. Physics-based modeling enables more accurate and transferable learning for EDA problems. SSL learns the optimized EDA solution data manifold. Conditioned on the problem input, it can directly produce the solution. I will illustrate the applications of these techniques in standard cell layout, computational lithography, and gate sizing problems. Finally, I will outline three main approaches to integrate ML and conventional EDA algorithms together and the importance of adopting GPU computing to EDA.

TILOS Seminar: How to use Machine Learning for Combinatorial Optimization? Research Directions and Case Studies
2022-07-20 10:00 - 11:00 | Virtual
Sherief Reda, Professor, Brown University and Principal Research Scientist at Amazon
Abstract: 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.

TILOS Seminar: The FPGA Physical Design Flow Through the Eyes of ML
2022-06-29 10:00 - 11:00 | Virtual
Dr. Ismail Bustany, Fellow at AMD
Abstract: The FPGA physical design (PD) flow has innate features that differentiate it from its sibling, the ASIC PD flow. FPGA device families service a wide range of applications, have much longer lifespans in production use, and bring templatized logic layout and routing interconnect fabrics whose characteristics are captured by detailed device models and simpler timing and routing models (e.g. buffered interconnect and abstracted routing resources). Furthermore, the FPGA PD flow is a “one-stop shop” from synthesis to bitstream generation. This avails complete access to annotate, instrument, and harvest netlist and design features. These key differences provide rich opportunities to exploit both device data and design application specific contexts in optimizing various components of the PD flow. In this talk, I will present examples for the application of ML in device modeling and parameter optimization, draw attention to exciting research opportunities for applying the “learning to optimize” paradigm to solving the placement and routing problems, and share some practical learnings.

TILOS Seminar: Reasoning Numerically
2022-06-15 10:00 - 11:00 | Virtual
Sicun Gao, Assistant Professor, UC San Diego
Abstract: 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.

TILOS Seminar: Deep Generative Models and Inverse Problems
2022-05-18 10:00 - 11:00 | Virtual
Alexandros G. Dimakis, Professor, The University of Texas at Austin
Abstract: 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.

TILOS-OPTML++ Seminar: Constant Regret in Online Decision-Making
2022-05-11 14:30 - 15:30 | Virtual
Siddhartha Banerjee, Cornell University
Abstract: I will present a class of finite-horizon control problems, where we see a random stream of arrivals, need to select actions in each step, and where the final objective depends only on the aggregate type-action counts; this includes many widely-studied control problems including online resource-allocation, dynamic pricing, generalized assignment, online bin packing, and bandits with knapsacks. For such settings, I will introduce a unified algorithmic paradigm, and provide a simple yet general condition under which these algorithms achieve constant regret, i.e., additive loss compared to the hindsight optimal solution which is independent of the horizon and state-space. These results stem from an elementary coupling argument, which may prove useful for many other questions in online decision-making. Time permitting, I will illustrate this by showing how we can use this technique to incorporate side information and historical data in these settings, and achieve constant regret with as little as a single data trace.

TILOS-OPTML++ Seminar: Equilibrium Computation, Deep Multi-Agent Learning, and Multi-Agent Reinforcement Learning
2022-04-27 14:30 - 15:30 | Virtual
Constantinos Daskalakis, MIT

TILOS Seminar: Learning in the Presence of Distribution Shifts: How does the Geometry of Perturbations Play a Role?
2022-04-20 10:00 - 11:00 | Virtual
Hamed Hassani, Assistant Professor, University of Pennsylvania
Abstract: 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
2022-03-16 10:00 - 11:00 | Virtual
Melvin Leok, Department of Mathematics, UC San Diego
Abstract: 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 University of California, 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
2022-02-16 10:00 - 11:00 | Virtual
Yian Ma, Assistant Professor, UC San Diego
Abstract: 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.

TILOS Seminar: Real-time Sampling and Estimation: From IoT Markov Processes to Disease Spread Processes
2022-01-19 10:00 - 11:00 | Virtual
Shirin Saeedi Bidokhti, Assistant Professor, University of Pennsylvania
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 six. 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. To this end, we develop a probabilistic framework to sequentially learn nodes’ probabilities of infection (using test observations) by an efficient backward-forward update algorithm that first infers about the state of the relevant nodes in the past before propagating that forward into future. We further argue that if nodes’ probabilities of infection were accurately known at each time, exploitation-based policies that test the most likely nodes are myopically optimal in a relevant class of policies. However, when our belief about the probabilities is wrong, exploitation can be arbitrarily bad, as we provably show, while a policy that combines exploitation with random testing can contain the spread faster. Accordingly, we propose exploration policies in which nodes are tested probabilistically based on our estimated probabilities of infection Using simulations, we show in several interesting settings how exploration helps contain the spread by detecting more infected nodes, in a timely manner, and by providing a more accurate estimate of the nodes’ probabilities of infection.

TILOS Seminar: Closing the Virtuous Cycle of AI for IC and IC for AI
2021-12-15 10:00 - 11:00 | Virtual
David Pan, Professor, The University of Texas at Austin
Abstract: The recent artificial intelligence (AI) boom has been primarily driven by three confluence forces: algorithms, big-data, and computing power enabled by modern integrated circuits (ICs), including specialized AI accelerators. This talk will present a closed-loop perspective for synergistic AI and agile IC design with two main themes, AI for IC and IC for AI. As semiconductor technology enters the era of extreme scaling and heterogeneous integration, IC design and manufacturing complexities become extremely high. More intelligent and agile IC design technologies are needed than ever to optimize performance, power, manufacturability, design cost, etc., and deliver equivalent scaling to Moore’s Law. This talk will present some recent results leveraging modern AI and machine learning advancement with domain-specific customizations for agile IC design and manufacturing, including open-sourced DREAMPlace (DAC’19 and TCAD’21 Best Paper Awards), DARPA-funded MAGICAL project for analog IC design automation, and LithoGAN for design-technology co-optimization. Meanwhile on the IC for AI frontier, customized ICs, including those with beyond-CMOS technologies, can drastically improve AI performance and energy efficiency by orders of magnitude. I will present our recent results on hardware and software co-design for optical neural networks and photonic ICs (which won the 2021 ACM Student Research Competition Grand Finals 1st Place). Closing the virtuous cycle between AI and IC holds great potential to significantly advance the state-of-the-art of each other.

TILOS Seminar: A Mixture of Past, Present, and Future
2021-11-17 10:00 - 11:00 | Virtual
Arya Mazumdar, Associate Professor, UC San Diego
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, 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.
