Τίτλος: Equilibrium Computation and the Foundations of Deep Learning

Περίληψη: Deep Learning has recently yielded important advances in single‐agent learning challenges, much of that progress being fueled by the empirical success of gradient descent and its variants in computing local optima of non‐convex optimization problems. In multi‐agent learning applications, the role of single‐objective optimization is played by equilibrium computation, yet our understanding of its complexity in settings that are relevant for Deep Learning remains sparse. In this talk we focus on min‐max optimization of nonconvex‐nonconcave objectives, which has found applications in GANs, and other adversarial learning problems. Here, not only are there no known gradient‐descent based methods converging to even local and approximate min‐max equilibria, but the computational complexity of identifying them remains poorly understood. We show that finding approximate local min‐max equilibria of Lipschitz and smooth objectives requires a number of queries to the function and its gradient that is exponential in the relevant parameters, in sharp contrast to the polynomial number of queries required to find approximate local minima of non‐ convex objectives. Our oracle lower bound is a byproduct of a complexity‐theoretic result showing that finding approximate local min‐max equilibria is computationally equivalent to finding Brouwer fixed points, and Nash equilibria in non zero‐sum games, and thus PPAD‐complete.Minimal complexity theory knowledge will be assumed in the talk. Joint work with Stratis Skoulakis and Manolis Zampetakis.

Bio: Constantinos (a.k.a. “Costis”) Daskalakis (http://people.csail.mit.edu/costis) is a Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long‐ standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi‐item auctions. His current work focuses on high‐dimensional statistics and learning from biased, dependent, or strategic data. He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, and the Bodossaki Foundation Distinguished Young Scientists Award.

Τίτλος: Designing and Deploying Secure and Efficient Distributed Ledgers at a Global Scale

Περίληψη: Τhe advent of blockchain protocols brought to light a number of applications that could be facilitated by large scale consensus systems. At the same time a number of significant challenges were put forth in terms of incentives, scalability, energy efficiency, privacy, and the relevant threat model that such protocols may be proven secure for. In this talk I will give an overview of recent and ongoing research in the area of designing distributed ledgers at a global scale including the Ouroboros proof of stake blockchain protocol as well as other related constructions aiming to improve the interoperability, privacy and the incentive structure of distributed ledgers.

Bio: Aggelos Kiayias (https://www.kiayias.com) is chair in Cyber Security and Privacy and director of the Blockchain Technology Laboratory at the University of Edinburgh. He is also the Chief Scientist at blockchain technology company IOHK and an associate professor at the National and Kapodistrian University of Athens. His research interests are in computer security, information security, applied cryptography and foundations of cryptography with a particular emphasis in blockchain technologies and distributed systems, e‐voting and secure multiparty protocols as well as privacy and identity management. He has been the recipient of an ERC fellowship, a Marie Curie fellowship, an NSF Career Award, and a Fulbright Fellowship. He holds a Ph.D. from the City University of New York, he was a graduate student in ECE at NTUA and has an undergraduate degree in Mathematics from the University of Athens. He has over 150 publications in journals and conference proceedings in the area. He has served as the program chair of the Cryptographers’ Track of the RSA conference in 2011 and the Financial Cryptography and Data Security conference in 2017, as well as the general chair of Eurocrypt 2013. He also served as the program chair of Real World Crypto Symposium 2020 and the Public‐Key Cryptography Conference 2020.

Τίτλος: A Simple but Non‐Convex Objective for Learning Linear Classifiers with Noise

Περίληψη: We study the problem of learning linear classifiers with noise in the distribution‐specific PAC model. We give the first computationally efficient algorithm for learning under Massart noise with respect to a broad family of distributions, including log‐concave distributions. Moreover, we show that our algorithm works even under adversarial label noise, matching the best‐possiblemisclassification error guarantees of O(OPT)+ε in polynomial time. Our approach is simple and practical: We identify a smooth non‐convex surrogate loss whose approximate stationary points give near optimal solutions. Interestingly, non‐convexity is inherently necessary. We show that any convex surrogate, like the commonly used logistic loss, results in suboptimal error guarantees.

Bio: Christos Tzamos (https://tzamos.com) is an Assistant Professor in the Department of Computer Sciences at University of Wisconsin‐Madison and a member of the Theory of Computing group. His research interests lie in the interface of Theory of Computation with Economics and Game Theory, Machine Learning, Statistics and Probability Theory. He completed his PhD in the Theory of Computation group of MIT advised by Costis Daskalakis. He studied Electrical and Computer Engineering at NTUA before his PhD, and afterwards he was a postdoctoral researcher at Microsoft Research (New England) working on Mechanism Design, Algorithms and Machine Learning. He is the recipient of a Simons Foundation award, the George M. Sprowls award, the best paper and the best student paper award in EC 2013 and of an outstanding paper award in NeurIPS 2019.

Τίτλος: Tracking and Curing Epidemics with Uncertainty

Περίληψη: Epidemic processes can model anything that spreads. As such, they are a useful tool for studying not only human diseases, but also network attacks, the propagation of real or fake news, the spread of viral tweets, neural spikes in the brain, and other processes. In this talk, we're interested in epidemics spreading on an underlying graph. The study of epidemics is the study of high dimensional probability on combinatorial structures. Important tools include random graph processes, and concentration inequalities for these, as well as important combinatorial properties of graphs. The first part of this talk will be a tutorial introduction to some of these models, as well as some of the tools that are used. In the second part of the talk, we'll move to some recent results from my group that have centered on what we can do in the face of uncertainty. Currently, most theoretical research in this field assumes some form of perfect observation of the epidemic process. This is an unrealistic assumption for many real‐life applications, as the recent COVID‐19 pandemic tragically demonstrated: data are scarce, delayed, and/or imprecise for human epidemics, and symptoms may appear in a non‐deterministic fashion and order of infection ‐ if they appear at all. We discuss positive and negative results that arise as a consequence of uncertainty, and point to several open questions.

Bio: Constantine Caramanis (http://users.ece.utexas.edu/~cmcaram) is a Professor in the ECE department of The University of Texas at Austin. He received a PhD in EECS from The Massachusetts Institute of Technology, and an AB in Mathematics from Harvard University. He received the NSF CAREER award in 2011. His current research interests focus optimization and machine learning, high dimensional statistics, robustness, and stochastic networks.

Τίτλος: Rethinking Operating System and Hardware Abstractions for Good and Evil

Περίληψη: Current hardware and operating system abstractions were conceived at a time when we had minimal security threats, scarce compute and memory resources, and limited numbers of users. These assumptions are not true today. On one hand, attacks such as Spectre and Meltdown have shown that current hardware is plagued by vulnerabilities. On the other hand, new emerging cloud paradigms like microservices and serverless computing have led to the sharing of computing resources among hundreds of users at a time. In this new era of computing, we can no longer afford to build each layer separately. Instead, we have to rethink the synergy between the operating system and hardware from the ground up. In this talk, I will focus on rethinking the virtual memory abstraction. First, I will introduce Microarchitectural Replay Attacks, a novel family of side-channel attacks that exploit existing virtual memory mechanisms. These attacks leverage the fact that, in modern out-of-order processors, a single dynamic instruction can be forced to execute many times. Then, I will describe Elastic Cuckoo Page Tables, my proposal to rebuild the virtual memory abstraction for parallelism. Finally, I will conclude by describing ongoing and future directions towards redesigning the hardware and the operating system layers.

Bio: Dimitrios Skarlatos (http://www.cs.cmu.edu/~dskarlat) is currently with Facebook Ressearch and will start as an Assistant Professor in the Computer Science Department and Electrical and Computer Engineering (by courtesy) at Carnegie Mellon University in Fall 2021. He earned a PhD in Computer Science at the University of Illinois at Urbana‐Champaign, advised by Prof. Josep Torrellas.His alma mater is the Technical University of Crete in Greece. His research bridges computer architecture and operating systems focusing on performance, security, and scalability. His current work follows two central themes: (a) uncovering security vulnerabilities and building defenses at the boundary between hardware and OS, and (b) re‐designing abstractions and interfaces between the two layers to improve performance and scalability.