Maria Florina Balcan
Associate Professor, School of Computer Science (MLD and CSD)
Carnegie Mellon University

Data Driven Algorithm Design

Abstract

Data driven algorithm design for combinatorial problems is an important aspect of modern data science and algorithm design. Rather than using off the shelf algorithms that only have worst case performance guarantees, practitioners typically optimize over large families of parametrized algorithms and tune the parameters of these algorithms using a training set of problem instances from their domain to determine a configuration with high expected performance over future instances. However, most of this work comes with no performance guarantees. The challenge is that for many combinatorial problems, including partitioning and subset selection problems, a small tweak to the parameters can cause a cascade of changes in the algorithm's behavior, so the algorithm's performance is a discontinuous function of its parameters.
In this talk, I will present new work that helps put data driven combinatorial algorithm selection on firm foundations. We provide strong computational and statistical performance guarantees for several subset selection and combinatorial partitioning problems (including various forms of clustering), both for the batch and online scenarios where a collection of typical problem instances from the given application are presented either all at once or in an online fashion, respectively.

Biography

Maria Florina Balcan is an Associate Professor in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, computational aspects in economics and game theory, and algorithms. Her honors include the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards. She was a program committee co-chair for the Conference on Learning Theory in 2014 and for the International Conference on Machine Learning in 2016. She is currently board member of the International Machine Learning Society (since 2011), a Tutorial Chair for ICML 2019, and a Workshop Chair for FOCS 2019.

Calin Belta
Professor and Tegan Family Distinguished Faculty Fellow
Department of Mechanical Engineering, Systems Engineering and Bioinformatics
Boston University

Formal Synthesis of Control Strategies for Dynamical Systems

Abstract

In control theory, complex models of physical processes, such as systems of differential equations, are analyzed or controlled from simple specifications, such as stability and set invariance. In formal methods, rich specifications, such as formulae of temporal logics, are checked against simple models of software programs and digital circuits, such as finite transition systems. With the development and integration of cyber physical and safety critical systems, there is an increasing need for computational tools for verification and control of complex systems from rich, temporal logic specifications. In this talk, I will discuss a set of approaches to formal synthesis of control strategies for dynamical systems from temporal logic specifications. I will first show how automata games for finite systems can be extended to obtain conservative control strategies for low dimensional linear and multilinear dynamical systems. I will then present several methods to reduce conservativeness and improve the scalability of the control synthesis algorithms for more general classes of dynamics. I will illustrate the usefulness of these approaches with examples from robotics and traffic control.

Biography

Calin Belta is a Professor in the Department of Mechanical Engineering at Boston University, where he holds the Tegan Family Distinguished Faculty Fellowship. He is the Director of the BU Robotics Lab and of the Center for Autonomous and Robotic Systems (CARS), and is also affiliated with the Department of Electrical and Computer Engineering and the Division of Systems Engineering at Boston University. His research focuses on dynamics and control theory, with particular emphasis on hybrid and cyber-physical systems, formal synthesis and verification, and robotics. He received the Air Force Office of Scientific Research Young Investigator Award and the National Science Foundation CAREER Award. He is a IEEE Fellow.

Andrea Montanari
Professor, Department of Electrical Engineering, Department of Statistics
Stanford University

Optimization of the Sherrington-Kirkpatrick Hamiltonian

Abstract

Let \(A\) be an \(n \times n\) symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing \(x^TAx\) over binary vectors \(x\) with \(\pm 1\) entries. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any \(\epsilon > 0\), outputs a feasible solution that is at least \((1 − \epsilon)\) of the optimum value, with probability converging to one as \(n\) goes to infinity. The algorithm’s time complexity is \(\mathcal{O}(n^2)\). It is a message-passing algorithm, but the specific structure of its update rules is new.
As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the celebrated Thouless-Anderson-Palmer equations.

Biography

Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Théorique de l'Ecole Normale Supérieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Chargé de Recherche (with Centre National de la Recherche Scientifique, CNRS) at LPTENS. In September 2006 he joined Stanford University as a faculty, and since 2015 he is Full Professor in the Departments of Electrical Engineering and Statistics.
He was co-awarded the ACM SIGMETRICS best paper award in 2008. He received the CNRS bronze medal for theoretical physics in 2006, the National Science Foundation CAREER award in 2008, the Okawa Foundation Research Grant in 2013, and the Applied Probability Society Best Publication Award in 2015. He is an Information Theory Society distinguished lecturer for 2015-2016. In 2016 he received the James L. Massey Research & Teaching Award of the Information Theory Society for young scholars. In 2018 he was an invited sectional speaker at the International Congress of Mathematicians.

Abhay Parekh
Adjunct Professor, Department of Electrical Engineering and Computer Science
University of California, Berkeley

Sharing Human Resources

Abstract

During the early years of the internet, when I was a student at LIDS, the network was the scarce resource and the primary goal was to figure out efficient and fair ways to share this complicated resource with users. Today, it is the users who are more complicated as we seek to get them to click on ads and to solve problems on crowdsourcing platforms. I will focus on two of these "complications" that arise naturally in crowdsourcing platforms. The first is the issue of bias and inconsistencies of judgment among the various workers, and second is the need to design incentive schemes which ensure that some workers do not lie or perform significantly less than their best.

Biography

Abhay Parekh received a B.E.S. in Mathematical Sciences from Johns Hopkins University in 1983, an S.M. in Operations Research from the Sloan School of Management at MIT in 1985, and the Ph.D. in Electrical Engineering and Computer Science from MIT in 1992, where he was affiliated with the Laboratory for Information and Decision Systems. After obtaining his doctorate, he was a postdoc at the MIT Laboratory for Computer Sciences. Dr. Parekh has spent a number of years in industry (AT&T; Bell Laboratories, T. J. Watson Research Center IBM, Sun Microsystems, Inktomi), as an entrepreneur (FastForward Networks, Flowgram, and most recently Lytmus), as an investor (Accel Partners). Concurrently with his startup activities, he has been an Adjunct Professor in the EECS department at the University of California, Berkeley since 2003.