INFORMATICA

Seminari

2020

Landscape and Training Dynamics of DNNs: lessons from physics-inspired methods
13/02/2020
Despite their formidable success in recent years, a fundamental understanding of deep neural networks (DNNs) is still lacking. Open questions include the origin of the slowness of the training dynamics, and the relationship between the dimensionality of parameter space and number of training examples, since DNNs empirically generalize very well even when over-parametrized. A popular way to address these issues is to study the topology of the cost function (the loss landscape) and the properties of the algorithm used for training (usually stochastic gradient descent, SGD). Here, we use methods and results coming from the physics of disordered systems, in particular glasses and sphere packings. On one hand, we are able to understand to what extent DNNs resemble widely studied physical systems. On the other hand, we use this knowledge to identify properties of the learning dynamics and of the landscape. In particular, through the study of time correlation functions in weight space, we argue that the slow dynamics is not due to barrier crossing, but rather to an increasingly large number of null-gradient directions, and we show that, at the end of learning, the system is diffusing at the bottom of the landscape. We also find that DNNs exhibit a phase transition between over- and under-parametrized regimes, where perfect fitting can or cannot be achieved. We show that in this overparametrized phase there cannot be spurious local minima. In the vicinity of this transition, properties of the curvature of the loss function minima are critical. This kind of knowledge can be used both as a basis for a more grounded understanding of DNNs and for hands-on requirements such as hyperparameter optimization and model selection.

Fences and RMRs Required for Synchronization
24/02/2020
Compiler optimizations that execute memory accesses out of (program) order often lead to incorrect execution of concurrent programs. These re-orderings are prohibited by inserting costly fence (memory barrier) instructions. The inherent Fence Complexity is a good estimate of an algorithm's time complexity, as is its RMR complexity: the number of Remote Memory References the algorithm must issue. When write instructions are executed in order, as in the Total Store Order (TSO) model, it is possible to implement a lock (and other objects) using only one RAW fence and an optimal O(n log n) RMR complexity. However, when store instructions may be re-ordered, as in the Partial Store Order (PSO) model, we prove that there is an inherent tradeoff between fence and RMR complexities. The proof relies on an interesting encoding argument.

Network archeology: on revealing the past of random trees
10/02/2020
Networks are often naturally modeled by random processes in which nodes of the network are added one-by-one, according to some random rule. Uniform and preferential attachment trees are among the simplest examples of such dynamically growing networks. The statistical problems we address in this talk regard discovering the past of the network when a present-day snapshot is observed. Such problems are sometimes termed "network archeology". We present a few results that show that, even in gigantic networks, a lot of information is preserved from the very early days. Gabor Lugosi is an ICREA research professor at the Department of Economics, Pompeu Fabra University, Barcelona. He graduated in electrical engineering at the Technical University of Budapest in 1987, and received his Ph.D. from the Hungarian Academy of Sciences in 1991. His research main interests include the theory of machine learning, combinatorial statistics, inequalities in probability, random graphs and random structures, and information theory.

Model Based Design of Safety and Mission Critical Systems
19/02/2020
Many software based control systems are indeed safety or mission critical systems. Examples are: aerospace, transportation, medical devices, financial systems. In this talk I will outline my research activity as for model based synthesis and verification of software based control systems and show how the general purpose algorithms and tools developed have been used in specific application domains.

Safe and Efficient Exploration in Reinforcement Learning
05/02/2020
At the heart of Reinforcement Learning lies the challenge of trading exploration -- collecting data for identifying better models -- and exploitation -- using the estimate to make decisions. In simulated environments (e.g., games), exploration is primarily a computational concern. In real-world settings, exploration is costly, and a potentially dangerous proposition, as it requires experimenting with actions that have unknown consequences. In this talk, I will present our work towards rigorously reasoning about safety of exploration in reinforcement learning. I will discuss a model-free approach, where we seek to optimize an unknown reward function subject to unknown constraints. Both reward and constraints are revealed through noisy experiments, and safety requires that no infeasible action is chosen at any point. I will also discuss model-based approaches, where we learn about system dynamics through exploration, yet need to verify safety of the estimated policy. Our approaches use Bayesian inference over the objective, constraints and dynamics, and -- under some regularity conditions -- are guaranteed to be both safe and complete, i.e., converge to a natural notion of reachable optimum. I will also present recent results harnessing the model uncertainty for improving efficiency of exploration, and show experiments on safely and efficiently tuning cyber-physical systems in a data-driven manner. Andreas Krause is a Professor of Computer Science at ETH Zurich, where he leads the Learning & Adaptive Systems Group. He also serves as Academic Co-Director of the Swiss Data Science Center. Before that he was an Assistant Professor of Computer Science at Caltech. He received his Ph.D. in Computer Science from Carnegie Mellon University (2008) and his Diplom in Computer Science and Mathematics from the Technical University of Munich, Germany (2004). He is a Microsoft Research Faculty Fellow and a Kavli Frontiers Fellow of the US National Academy of Sciences. He received ERC Starting Investigator and ERC Consolidator grants, the Deutscher Mustererkennungspreis, an NSF CAREER award, the Okawa Foundation Research Grant recognizing top young researchers in telecommunications as well as the ETH Golden Owl teaching award. His research on machine learning and adaptive systems has received awards at several premier conferences and journals, including the ACM SIGKDD Test of Time award 2019. Andreas Krause served as Program Co-Chair for ICML 2018, and is regularly serving as Area Chair or Senior Program Committee member for ICML, NeurIPS, AAAI and IJCAI, and as Action Editor for the Journal of Machine Learning Research.

Automatic Synthesis of Controllers for Cyber-Physical Systems
28/01/2020
A Cyber-Physical System (sometimes also called hybrid system) is composed of physical subsystems and software subsystems. Many Cyber-Physical Systems are indeed control systems: the software part is designed to control the physical part, so that some desired behavior is achieved. Applications of such Cyber-Physical Control Systems are ubiquitous: smart grids, electrical engineering, aerospace, automotive, biology, and so on. Recently, many methodologies have been presented on automatically synthesizing controllers for Cyber-Physical Systems. Such methodologies take as input a description of the physical part (plant) of a Cyber-Physical Control System, a set of requirements for the software part (controller), a set of desired behaviors for the closed-loop system (controller + plant), and output the actual software for the controller, which is guaranteed to meet all given specifications. In this talk, I will present a selection of such methodologies, mainly focusing on my own contributions.

Adaptive Communication for Battery-Free IoT devices
28/01/2020
With the ever-growing usage of batteries in the IoT era, the need for more eco-friendly technologies is clear. RF-powered computing enables the redesign of personal computing devices in a battery-less manner. While there has been substantial work on the underlying methods for RF-powered computing, practical applications of this technology has largely been limited to scenarios that involve simple tasks. This talk discusses how RFID technology, typically used to implement object identification and counting, can be exploited to realize a battery-free smart home. In particular, this talk considers the coexistence of several battery-free devices, with different transmission requirements - periodic, event-based, and real-time - and proposes a new approach to dynamically collect information from devices without requiring any a priori knowledge of the environment.

Learning to rank results optimally in search and recommendation engines
17/01/2020
Consider the scenario where an algorithm is given a context, and then it must select a slate of relevant results to display. As four special cases, the context may be a search query, a slot for an advertisement, a social media user, or an opportunity to show recommendations. We want to compare many alternative ranking functions that select results in different ways. However, A/B testing with traffic from real users is expensive. This research provides a method to use traffic that was exposed to a past ranking function to obtain an unbiased estimate of the utility of a hypothetical new ranking function. The method is a purely offline computation, and relies on assumptions that are quite reasonable. We show further how to design a ranking function that is the best possible, given the same assumptions. Learning optimal rankings for search results given queries is a special case. Experimental findings on data logged by a real-world e-commerce web site are positive.

Corso di 24 ore di "Scrittura tecnico-scientifica" (corso in lingua italiana)
28/01/2020

2019

Harnessing the Power of (Knowledge) Graphs
09/01/2019
The Web, traditionally viewed as a vast repository of documents, is being transformed into a huge database by the massive presence of structured data. New research challenges arise in this information space due to the intrinsic decentralized data creation and management, the lack of superimposed schema, and the availability of huge volumes of data covering diverse domains. In this talk, I will give an overview of my research activities in the areas of graph querying and explanation languages, knowledge discovery from graphs, and social networks. I will also outline some ongoing research activities centered around the marriage between machine learning and knowledge representation and reasoning.

Limits and Structure of Learnability and Provability
01/02/2019
I will describe my two main areas of research: Learning in the Limit and Reverse Mathematics. Learning in the limit is one of the main computational models of learnability. A learner is modeled by a computational device which inductively generates hypotheses about an input language and stabilizes in the limit on a correct guess. Contrary to other models of learning, this model allows to decide questions of the following type: Is it the case that some learning constraint or learning strategy is necessary for learning some language class? I will discuss the case of so-called "U-shaped learning", a prominent and as-of-yet not well-understood feature of human learning in many contexts. The study of the effective (or computable) content and relative strength of theorems is one of the main areas of recent research in Computable Mathematics and Reverse Mathematics. I will outline a framework in which the following questions can be addressed: Given two theorems, is one stronger than the other or are they equivalent? Is it the case that one theorem is reducible to the other by a computable reduction? Given a problem, what is the complexity of its solutions to computable instances? I will discuss the case of Hindman's Finite Sums Theorem, which is the subject of a number of long-standing open problems in the area.

Power Efficient Machine Learning in Silicon
20/02/2019
Power efficiency is a key aspect in computer systems both in high-end servers and in portable devices. The focus of this talk is to discuss how the numerical formats of data impacts the energy efficiency of the computation, and how to trade-off accuracy with power savings. Machine Learning and Deep Learning are used as case studies to present the key ideas and the benefits derived by a flexible format to represent numerical data.

Round Compression for Parallel Matching Algorithms
20/02/2019
For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the fundamental graph problem of finding maximum matching. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. showed that if each machine has n^{1+Ω(1)} memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. In this talk, we finally show how to refute that perplexing possibility. That is, we break the above O(log n) round complexity bound even in the case of slightly sublinear memory per machine. This is a joint work with Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski, which appeared at STOC'2018.

HOW BLOCKCHAINS WORK AND THEIR IMPLICATIONS ON CYBERSECURITY
04/03/2019
This talk will be divided in two parts. The first part will explain the main properties of blockchain applications. During the second part, we will show how blockchain properties can have an impact on security and show some examples of past vulnerabilities suffered by blockchain-based systems.

Dynamic graph algorithms and complexity (a survey)
08/03/2019
In this talk I will attempt to answer the following questions I have been asked quite often: What are the current challenges in dynamic graph algorithms? What are good starting points for people who want to try working in this field? The talk will focus on challenges for basic graph problems (e.g. connectivity, shortest paths, maximum matching), and will survey some existing upper and lower bound results and techniques.

THE PROTECTION OF SPACE MISSIONS: THREATS THAT ARE SPECIFIC TO CYBER SECURITY
18/03/2019
Space-based systems play an important role in our daily life and business. The trend is likely to rely on the use of space based systems in a growing number of services or applications that can be either safety-of-life critical or business and mission-critical. The security measures implemented in space-based systems may turn out to be insufficient to guarantee the information assurance properties, in particular confidentiality (if required by the data policy), availability and integrity of these services/applications. The various and possible cyber-attacks on space segments, ground stations and its control segments are meanwhile well known and experienced in many cases. We address the Cybersecurity specific aspects of space missions, the specific threats to space mission from cyberspace, and analyze the set of all the possible countermeasures.

Strong coresets for k-median and subspace clustering: Goodbye dimension
10/04/2019
I will start my talk with an introduction to the area of coresets for clustering problems, give basic definitions and explain how coresets can be used to obtain distributed and streaming algorithms. During my talk, I will mostly focus on a commonly used coreset definition that has been introduced by Har-Peled and Mazumdar: A coreset is a weighted set S of points such that for all sets C of k centers we have (1-eps) cost(P,C) <= cost(S,C) <= (1+eps) cost(P,C), where cost(P,C) is the sum of distances of the points in P to their closest center in C. Then I will present a new algorithm to compute coresets that have a similar for-all guarantee as in the above definition and that consist of a number of points that is independent of the size of the input point set P and the dimension of the input space d. Joint work with David Woodruff.

Stochastic Incremental Algorithms for Optimal Transport with SON Regularizer
18/04/2019
Optimal Transport (OT) is a classic area in probability and statistics for transferring mass from one probability distribution to another. Recently OT has been very successfully used for domain adaptation in many applications in computer vision, texture analysis, tomographic reconstruction and clustering. We introduce a new regularizer OT which is tailored to better preserve the class structure. We give the first theoretical guarantees for an OT scheme that respects class structure. We give an accelerated proximal--projection scheme for this formulation with the proximal operator in closed form to give a highly scalable algorithm for computing optimal transport plans. Our experiments show that the new regularizer preserves class structure better and is more robust compared to previous regularizers.

Distributed algorithms for hybrid networks
09/05/2019
I will introduce a new communication model, called hybrid network, in which the nodes have the choice between two communication modes: a local mode that allows them to exchange messages with nearby nodes, and a global mode where communication between any pair of nodes is possible, but the amount of communication is limited. This can be motivated, for instance, by wireless networks in which we combine direct device-to-device communication with communication via the cellular infrastructure. I will show how to quickly build up a low-diameter, low-degree network of global edges (i.e., connections established via the global communication mode) on top of any network of local edges (i.e., connections given by the local communication mode) so that various problems such as computing minimum spanning trees and shortest paths can be solved much more efficiently than by just using the local edges. This is joint work with various colleagues including John Augustine, Fabian Kuhn, and Mohsen Ghaffari.

2018

Manuel Mazo Espinosa Jr. - Symbolic abstractions of control systems' timing behaviour
09/10/2018
With the advent of the Internet-of-things and Cyber-Physical Systems everywhere, there has arisen a renewed interest on the study of networked control systems (NCS). NCS are systems in which measurements from sensors are sent through a communications network to a control unit to compute corrective actions for the system being monitored, actions which are again relayed through a network to actuators. In the past decade a shift of perspective in the design and analysis of NCS has emerged in order to make the use of communications bandwidth as efficient as possible. The idea is to move away from the traditional approach employing pre-determined (usually periodic) update times, to designs in which the time instants at which the control loop is closed is determined by the sensors themselves. This has resulted in what has been named “event-based control” (EBC). Despite of the many promising results of EBC designs I will argue that the unpredictability of the communications traffic they generate is a critical bottleneck to exploit EBC’s potential benefits. To solve this critical problem, I will describe our recent results on the construction of abstractions (in the form of timed automata) capturing the communications traffic of EBC. I will then describe how such abstractions can help in the design of more efficient EBC systems and schedulers for them.