Nikita Zhivotovskiy (Technion Haifa):
Uniform concentration results for random graphs and random quadratic forms

The talk will be devoted to several applications of the entropy method and empirical processes techniques for concentration inequalities. At first, we discuss uniform concentration inequalities for the Erdős–Rényi graph process. We show that up to absolute constant factors the uniform concentration inequality for spectral norms of adjacency matrices around their means coincides with the non-uniform result of Alon, Krivelevich, and Vu that holds for one adjacency matrix. The second application is devoted to uniform over the classes of matrices Hanson-Wright-type inequalities. We extend concentration results of Talagrand (that hold for the order two Rademacher chaos) and more recent uniform results of Adamczak to more general classes of distributions. We also discuss simplified versions of original proofs. The talk is based on joint projects with Shahar Mendelson, Gabor Lugosi and Yegor Klochkov.

(Show/Hide Abstract)

Nadav Cohen (Princeton Institute of Advances Studies):
On Optimization in Deep Learning: Implicit Acceleration by Overparameterization

Deep learning refers to a class of statistical learning models that is enjoying unprecedented success in recent years, powering state of the art technologies in numerous application domains. However, despite the vast scientific and industrial interest it is drawing, our theoretical understanding of deep learning is partial at best. In this talk I will outline my perspective on the fundamental questions in deep learning theory, highlighting the difference from classical machine learning. I will then focus on the question of optimization, where depth (non-convexity) is believed to be an impediment. In stark contrast with conventional wisdom, I will show that, sometimes, increasing depth can speed up optimization. This result was recently derived with Sanjeev Arora and Elad Hazan (to appear in the proceedings of ICML 2018; arXiv preprint: https://arxiv.org/pdf/1802.06509.pdf).

(Show/Hide Abstract)

Christian Kümmerle (TU München):
The Quotient Property: Benefits of heavy tails in noise-blind compressed sensing

We review the problem of noise-blind compressed sensing and corresponding existing results. The key tool of the analysis is a geometric mapping condition on the measurement matrix A called $\ell_1$-quotient property, which corresponds to a lower bound on the size of the largest Euclidean ball contained in the centrally symmetric polytope spanned by the columns of A. We obtain the first results on the $\ell_1$-quotient property for matrices A whose entrywise distributions do not fulfill concentration properties, while providing a unified proof that recovers previous results for sub-Gaussian, Gaussian and Weibull distributions. They imply robustness of noise-blind $\ell_1$-decoders under the weakest possible assumptions on the entrywise distributions that allow for recovery with optimal sample complexity even in the noiseless case. We also shed light on noise-blind decoders based on matrices with artificially added columns, following ideas of Wojtaszczyk.

(Show/Hide Abstract)

Zhiyong Zhou (University of Umea):
Sparsity measures and sparse signal recovery

Sparse signal recovery, particularly compressive sensing, aims to reconstruct a sparse or compressible signal from noisy underdetermined linear measurements. If the measurement matrix satisfies the null space property (NSP) or restricted isometry property (RIP), stable and robust recovery can be guaranteed. Although probabilistic results conclude that the NSP and RIP are fulfilled for some specific random matrices with high probability, it's computationally hard to verify NSP and compute restricted isometry constant (RIC) for a given measurement matrix. In this talk, I’d like to introduce a new kind of stable sparsity measure, and present verifiable sufficient conditions and computable performance bounds for sparse recovery algorithms such as the Basis Pursuit, the Dantzig selector and the LASSO estimator, in terms of a newly defined family of quality measures for the measurement matrices. ​

(Show/Hide Abstract)

Moritz Helias (Forschungszentrum Jülich):
Optimal sequence memory in driven random networks

Autonomous randomly coupled neural networks display a transition to chaos at a critical coupling strength. We here investigate the effect of a time-varying input on the onset of chaos and the resulting consequences for information processing. Dynamic mean-field theory yields the statistics of the activity, the maximum Lyapunov exponent, and the memory capacity of the network. We find an exact condition that determines the transition from stable to chaotic dynamics and the sequential memory capacity in closed form. The input suppresses chaos by a dynamic mechanism, shifting the transition to significantly larger coupling strengths than predicted by local stability analysis. Beyond linear stability, a regime of coexistent locally expansive, but non-chaotic dynamics emerges that optimizes the capacity of the network to store sequential input.

(Show/Hide Abstract)

Maryia Kabanava (RWTH Aachen University):
Masked covariance estimation

Oliver Schaudt (RWTH Aachen University):
Fast algorithms for delta-separated sparsity projection

Hans-Christian Jung (RWTH Aachen University):
Convexity properties of the gaussian measure and deviation inequalities for convex functions

Florian Drechsler (TU München):
Discrete Gabor systems using special functions and their innate translations

We present various new discrete Gabor frames based on families of special functions, using certain translations that arise from these special functions. Our two main cases of interest are spherical Bessel functions and prolate spheroidal wave functions, also known as Slepian functions. In each case, we examine the reconstruction properties of these frames, and interpret the meaning of the Gabor frame coefficients.

(Show/Hide Abstract)

Ulrich Terstiege (RWTH Aachen University):
On the expressive power of deep learning: A tensor analysis.

This talk reports on results by N. Cohen, O. Sharir, and A. Shashua presented in their paper On the expressive power of deep learning: A tensor analysis.

(Show/Hide Abstract)

Jean-Luc Bouchot (RWTH Aachen University):
CUR decomposition and data analysis

Jonathan Fell (RWTH Aachen University):
Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class

Shahar Mendelson (Technion Haifa and ANU Canberra):
An optimal unrestricted learning procedure

A learning problem consists of a triplet (F,X,Y), where F is a known function class on (\Omega,\mu); X is distributed according to the unknown probability measure \mu; and Y is the unknown target random variable one wishes to approximate. Given a sample D=(X_i,Y_i)_{i=1}^N of cardinality N, the goal is to produce some \hat{f} \in L_2(\mu) for which the squared risk E((\hat{f}(X)-Y)^2 |D) is almost as good as the best possible risk of a class member: \inf_{f \in F} E(f(X)-Y)^2. Moreover, this has to be achieved with high probability relative to the given sample (i.e., with respect to the N-product measure endowed by (X,Y) ). The question of identifying the best possible tradeoff between the accuracy r^2=E((\hat{f}(X)-Y)^2 |D) - \inf_{f \in F} E(f(X)-Y)^2 and the confidence with which that accuracy can be attained has been of central importance in statistical learning theory. And naturally, a satisfactory solution must include the identity of a procedure \hat{f} for which the optimal tradeoff is attained. In this talk I will present some of the ideas used in the solution of the problem - a procedure that attains the optimal accuracy/confidence tradeoff for an arbitrary triplet (F,X,Y) - including classes that need not be convex and "heavy tailed" situations.

(Show/Hide Abstract)

Alexander Stollenwerk (RWTH Aachen University):
tba

Holger Rauhut (RWTH Aachen University):
One-bit compressive sensing with partial Gaussian matrices

Harald Günzel (RWTH Aachen University):
Die Menge der stationären Punkte in der parametrischen Optimierung

Alexander Jung (Aalto University):
Compressed Sensing for Learning from Big Data over Networks

In this talk I present some of our most recent work on applying tools from compressed sensing to (semi-supervised) learning from massive network-structured datasets, i.e., big data over networks. We expect the use of compressed sensing ideas game changing as it was for digital signal processing. In particular, i will present a sparse label propagation algorithm which efficiently learns the labels for datapoints based on the availability of a few labeled training datapoints. This algorithm is inspired by compressed sensing recovery methods and allows for a simple sufficient condition on the network structure which guarantees accurate learning.

(Show/Hide Abstract)

Shahar Mendelson (Technion Haifa):
Median of means tournaments

I will present a new learning procedure that is based on the idea of median-of-means. The procedure attains the best possible accuracy/confidence trade-off in (almost) any learning problem involving a convex class F and with respect to the squared loss. In particular, the optimal estimates hold for "heavy-tailed" problems. As a simple outcome I will present the optimal solution for the classical problem of mean estimation: let $X$ be a random vector with mean $x_0$ and covariance matrix $\Sigma$ - that are both not known. If $X_1,...,X_N$ are independent copies of $X$, then a "winner" $\hat{\mu}$ of an appropriate median of means tournament satisfies that with probability at least $1-\delta$, $$ \|\hat{\mu}-x_0\|_2 \leq C\max\left\{\sqrt{\frac{{\rm Tr}(\Sigma)}{N}}, \sqrt{\frac{\lambda_1 \log(2/\delta)}{N}}\right\}; $$ ${\rm Tr}(\Sigma)$ and $\lambda_1$ are the trace of the covariance matrix $\Sigma$ and its largest eigenvalue, respectively. This optimal estimate was known previously only under strong assumptions on the tail decay of $X$. Joint work with G. Lugosi.

(Show/Hide Abstract)

Samuel Vaiter (Université de Bourgogne):
Recovery Guarantees for Low Complexity Models

Inverse problems and regularization theory is a central theme in contemporary signal processing, where the goal is to reconstruct an unknown signal from partial indirect, and possibly noisy, measurements of it. A now standard method for recovering the unknown signal is to solve a convex optimization problem that enforces some prior knowledge about its structure. This has proved efficient in many problems routinely encountered in imaging sciences, statistics and machine learning. I will deliver a review of recent advances in the field where the regularization prior promotes solutions conforming to some notion of simplicity/low-complexity. These priors encompass as popular examples sparsity and group sparsity (to capture the compressibility of natural signals and images), total variation and analysis sparsity (to promote piecewise regularity), and low-rank (as natural extension of sparsity to matrix-valued data). Our aim is to provide a unified treatment of all these regularizations under a single umbrella, namely the theory of partial smoothness. This framework is very general and accommodates all low-complexity regularizers just mentioned, as well as others. Partial smoothness turns out to be the canonical way to encode low-dimensional models that can be linear spaces or more general smooth manifolds. We will cover several topics: (i) recovery guarantees and stability to noise, both in terms of l2-stability and model (manifold) identification; (ii) sensitivity analysis to perturbations of the parameters involved (in particular the observations), with applications to unbiased risk estimation ; (iii) convergence properties of the forward-backward proximal splitting scheme, that is particularly well suited to solve the corresponding large-scale regularized optimization problem.

(Show/Hide Abstract)

Ivan Yaroslavtsev (Delft University of Technology):
tba

Martin Genzel (TU Berlin):
Feature selection from real-world Data with nonlinear observations

A fundamental challenge in machine learning is the selection of discriminative features from a relatively small collection of sample pairs (x_i, y_i), i=1,...,m. Here, the observations y_i are often supposed to follow a noisy single-index model, depending on a certain set of target variables. The major difficulty is now that these variables cannot be observed directly, but rather arise as \emph{hidden} factors in the actual data vector x_i in R^d (feature variables). A typical example would be mass spectrometry data of the human proteome, where the desired molecular concentrations of proteins are intrinsically encoded by means of Gaussian-shaped peaks. In this talk, we will see that a successful feature selection is still possible when the applied estimator does not have any knowledge of the underlying data representation and only takes the ``raw'' samples (x_i, y_i) as input. Guarantees of such type are especially appealing for practical purposes, since in many applications even standard methods, e.g., the Lasso or logistic regression, yield surprisingly good outcomes. The mathematical basis of our results forms a recent framework for structured signal recovery from highly underdetermined (non-)linear equation systems. This allows us to treat the problem of feature selection in a unified way, particularly including non-linear observations, arbitrary convex signal structures as well as strictly convex loss functions. This is joint work with Gitta Kutyniok.

(Show/Hide Abstract)

Alexander Stollenwerk (RWTH Aachen University):
Learning without concentration for general loss functions

One important goal of empirical risk minimization is to control the L2-distance between the optimal approximation of some target function (within a certain class of functions and with respect to some convex loss) and the minimal solution of the corresponding empirical risk minimization problem. Using his small ball method, Mendelson is able to control this distance in a very general setup, where the target function as well as the function class can be unbounded and heavy-tailed. Further, this analysis can be applied to a wide range of loss functions, making it possible to decrease the negative effect of having to deal with heavy-tailed noise and a rapidly increasing loss function (like the squared loss) at the same time.

(Show/Hide Abstract)

Reinhard Heckel (University of California at Berkeley):
Exact Localization of Point Sources via Convex Optimization

Line spectral estimation is the problem of recovering the frequencies and amplitudes of a mixture of a few sinusoids from equispaced samples. However, in a variety of applications in signal processing arising in imaging, radar, and localization, we do not have access directly to such equispaced samples. Rather we only observe a severely undersampled version of these observations through linear measurements. We reformulate these problems as sparse signal recovery problems over a continuously indexed dictionary which can be solved via a convex program. We prove that the frequencies and amplitudes of the components of the mixture can be recovered perfectly from a near-minimal number of observations via this convex program. These results holds provided the frequencies are sufficiently separated, and the linear measurements obey natural conditions that are satisfied in a variety of applications. As a concrete application, we explain how this problem arrises in Radar, and how the aforementioned results allow to super-resolve the delay-Doppler shifts, which in turn allows very accurate localization of the targets.

(Show/Hide Abstract)