Jannis Kurtz (RWTH Aachen University):
Robust Optimization in Machine Learning

In this talk we study the concept of Robust Optimization and its applications in Machine Learning. We present results for robust linear regression problems and for robust classification problems based on the concept of Regularized Support Vector Machines. Both concepts apply the paradigm of Robust Optimization to learning problems where the training samples are not precisely known or disturbed. In both approaches it turns out that the concept of Robustness can be used to find an appropriate regularizer based on the information about the pertubation of the data.

(Show/Hide Abstract)

Holger Rauhut (RWTH Aachen University):
Nonlinear compressive sensing with partial random circulant matrices

The talk presents results on compressive sensing where the measurements are given as subsampled random convolutions followed by a nonlinearity applied to each component. We provide near-optimal bounds on the minimal number of measurements required for accurate reconstruction using convex programming in a non-uniform scenario. For the special case of one-bit compressive sensing where the nonlinearity is the sign function, we also present a uniform recovery result which is based on an improved bound for an l1 version of the restricted isometry property. Joint with Shahar Mendelson.

(Show/Hide Abstract)

Vicky Kouni (Kapodistrian University of Athens):
Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class

In compressed sensing, it is often desirable to consider signals possessing additional structure beyond sparsity. One such structured signal model – which forms the focus of this paper – is the local sparsity in levels class. This class has recently found applications in problems such as compressive imaging, multi-sensor acquisition systems and sparse regularization in inverse problems. In this paper uniform recovery guarantees are presented for this class, when the measurement matrix corresponds to a subsampled isometry. This is done by establishing a variant of the standard restricted isometry property for sparse in levels vectors, known as the restricted isometry property in levels. Interestingly, besides the usual log factors, these uniform recovery guarantees are simpler and less stringent than existing nonuniform recovery guarantees. For the particular case of discrete Fourier sampling with Haar wavelet sparsity, a corollary of the main theorem yields a new recovery guarantee which improves over the current state-of-the-art.

(Show/Hide Abstract)

Alexander Stollenwerk (RWTH Aachen University):
A quantized Johnson-Lindenstrauss transform

Ulrich Terstiege (RWTH Aachen University):
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

This talk reports on the paper "A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks" by Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. In this paper, conditions for convergence to a global optimum of gradient decent for deep linear neural networks are investigated and the speed of the convergence is estimated.

(Show/Hide Abstract)

Hans-Christian Jung (RWTH Aachen University):
Sparse Recovery in Bounded Riesz Systems

Oliver Schaudt (RWTH Aachen University):
Algorithms for Group Model Projection

We discuss our recent work with J. Kurtz and B. Bah on algorithms surrounding the group model projection problem in compressed sensing. Group models are used to generalize concepts like block sparsity and typically suffer from a computationally hard model projection problem. I'll sketch our approach to circumvent this hardness using methods from discrete optimization.

(Show/Hide Abstract)

Sjoerd Dirksen (RWTH Aachen University):
Robust one-bit compressed sensing with non-Gaussian measurements

In the traditional compressed sensing literature, it is implicitly assumed that one has direct access to noisy analog linear measurements of an (unknown) signal. In reality, these analog measurements need to be quantized to a finite number of bits before they can be transmitted, stored, and processed. In the emerging theory of quantized compressed sensing it is studied how to jointly design a quantizer, measurement procedure, and reconstruction algorithm in order to accurately recover low-complexity signals. In the popular one-bit compressed sensing model, each linear analog measurement is quantized to a single bit in a memoryless fashion. This quantization operation can be implemented with energy-efficient hardware. There is by now a rich theory available for one-bit compressed sensing with standard Gaussian measurements. Outside of this purely Gaussian setting, very little is known about one-bit compressed sensing. In fact, recovery can in general easily fail for non-Gaussian measurement matrices, even if they are known to perform optimally in `unquantized’ compressed sensing. In my talk, I will show that this picture completely changes if we use dithering, i.e., deliberately add noise to the measurements before quantizing them. By using well-designed dithering, it becomes possible to accurately reconstruct low-complexity signals from a small number of one-bit quantized measurements, even if the measurement vectors are drawn from a heavy-tailed distribution. The reconstruction results that I will present are very robust to noise on the analog measurements as well as to adversarial bit corruptions occurring in the quantization process. If the measurement matrix is subgaussian, then accurate recovery can be achieved via a convex program. The proofs of these reconstruction theorems are based on novel random hyperplane tessellation results. Based on joint work with Shahar Mendelson (ANU Canberra)

(Show/Hide Abstract)

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