ETH-FDS seminar series

More information about ETH Foundations of Data Science can be found here

×

Modal title

Modal content

Please subscribe here if you would you like to be notified about these events via e-mail. Moreover you can also subscribe to the iCal/ics Calender.

Spring Semester 2021

Date / Time Speaker Title Location
4 May 2021
17:00-18:00
Manfred K. Warmuth
University of California, Santa Cruz / Google Research
Details

ETH-FDS seminar

Title A case where a spindly two-layer linear network whips any neural network with a fully connected input layer
Speaker, Affiliation Manfred K. Warmuth, University of California, Santa Cruz / Google Research
Date, Time 4 May 2021, 17:00-18:00
Location
Abstract It was conjectured that any neural network of any structure and arbitrary differentiable transfer functions at the nodes cannot learn the following problem sample efficiently when trained with gradient descent: The instances are the rows of a \(d\)-dimensional Hadamard matrix and the target is one of the features, i.e. very sparse. We essentially prove this conjecture: We show that after receiving a random training set of size \(k < d\), the expected square loss is still \(1 - k/(d - 1)\). The only requirement needed is that the input layer is fully connected and the initial weight vectors of the input nodes are chosen from a rotation invariant distribution. Surprisingly the same type of problem can be solved drastically more efficient by a simple 2-layer linear neural network in which the \(d\) inputs are connected to the output node by chains of length 2 (Now the input layer has only one edge per input). When such a network is trained by gradient descent, then it has been shown that its expected square loss is \(\frac{\log d}{k}\). Our lower bounds essentially show that a sparse input layer is needed to sample efficiently learn sparse targets with gradient descent when the number of examples is less than the number of input features.
Documents Video Manfred K. Warmuth - ETH-FDS talk on 4 May 2021file_download
A case where a spindly two-layer linear network whips any neural network with a fully connected input layerread_more
20 May 2021
16:15-17:15
Gitta Kutyniok
Ludwig-Maximilians-Universität München
Details

ETH-FDS seminar

Title Graph Convolutional Neural Networks: The Mystery of Generalization
Speaker, Affiliation Gitta Kutyniok, Ludwig-Maximilians-Universität München
Date, Time 20 May 2021, 16:15-17:15
Location
Abstract The tremendous importance of graph structured data due to recommender systems or social networks led to the introduction of graph convolutional neural networks (GCN). Those split into spatial and spectral GCNs, where in the later case filters are defined as elementwise multiplication in the frequency domain of a graph. Since often the dataset consists of signals defined on many different graphs, the trained network should generalize to signals on graphs unseen in the training set. One instance of this problem is the transferability of a GCN, which refers to the condition that a single filter or the entire network have similar repercussions on both graphs, if two graphs describe the same phenomenon. However, for a long time it was believed that spectral filters are not transferable. In this talk by modelling graphs mimicking the same phenomenon in a very general sense, also taking the novel graphon approach into account, we will debunk this misconception. In general, we will show that spectral GCNs are transferable, both theoretically and numerically. This is joint work with R. Levie, S. Maskey, W. Huang, L. Bucci, and M. Bronstein.
Documents Video Gitta Kutyniok - ETH-FDS talk on 20 May 2021file_download
Graph Convolutional Neural Networks: The Mystery of Generalizationread_more
27 May 2021
16:00-17:00
Rina Foygel Barber
The University of Chicago
Details

ETH-FDS seminar

Title Distribution-free inference for regression: discrete, continuous, and in between
Speaker, Affiliation Rina Foygel Barber, The University of Chicago
Date, Time 27 May 2021, 16:00-17:00
Location
Abstract In data analysis problems where we are not able to rely on distributional assumptions, what types of inference guarantees can still be obtained? Many popular methods, such as holdout methods, cross-validation methods, and conformal prediction, are able to provide distribution-free guarantees for predictive inference, but the problem of providing inference for the underlying regression function (for example, inference on the conditional meanE[Y|X]) is more challenging. If X takes only a small number of possible values, then inference on E[Y|X] is trivial to achieve. At the other extreme, if the features X are continuously distributed, we show that any confidence interval for E[Y|X] must have non-vanishing width, even as sample size tends to infinity - this is true regardless of smoothness properties or other desirable features of the underlying distribution. In between these two extremes, we find several distinct regimes - in particular, it is possible for distribution-free confidence intervals to have vanishing width if and only if the effective support size of the distribution ofXis smaller than the square of the sample size. This work is joint with Yonghoon Lee. Bio: Rina Foygel Barber is a Louis Block Professor in the Department of Statistics at the University of Chicago. She was a NSF postdoctoral fellow during 2012-13 in the Department of Statistics at Stanford University, supervised by Emmanuel Candès. She received her PhD in Statistics at the University of Chicago in 2012, advised by Mathias Drton and Nati Srebro, and a MS in Mathematics at the University of Chicago in 2009. Prior to graduate school, she was a mathematics teacher at the Park School of Baltimore from 2005 to 2007.
Documents Video Rina Foygel Barber - ETH-FDS talk on 27 May 2021file_download
Distribution-free inference for regression: discrete, continuous, and in betweenread_more
3 June 2021
17:00-18:00
Sewoong Oh
Allen School of Computer Science & Engineering University of Washington
Details

ETH-FDS seminar

Title Robust and Differentially Private Estimation
Speaker, Affiliation Sewoong Oh, Allen School of Computer Science & Engineering University of Washington
Date, Time 3 June 2021, 17:00-18:00
Location
Abstract Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices, initiating an extensive line of research in accurately and privately releasing statistics of a database. An increasing number of such databases consist of data from multiple sources, not all of which can be trusted. This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data. We are in a dire need for algorithms that guarantee privacy and robustness (to a fraction of data being corrupted) simultaneously. However, even the simplest questions remain open. For the canonical problem of estimating the mean (and the covariance) from i.i.d. samples under both privacy and robustness, I will present a minimax optimal algorithm, but requires an exponential run-time. This is followed by an efficient algorithm that requires a factor of $d^{1/2}$ more samples when the samples are in $d$-dimensions. It remains an open question if this computational gap can be closed, either with a more sample efficient algorithm or a tighter lower bound.
Documents Video Sewoong Oh - ETH-FDS talk on 3 June 2021 file_download
Robust and Differentially Private Estimation read_more
JavaScript has been disabled in your browser