L2

The standard rounding procedure in floating-point computations is round to nearest (RN). In this talk we consider an alternative rounding strategy called stochastic rounding (SR) which has the appealing property of being exact (actually exact!) in expectation. In the first part of the talk we discuss recent developments in probabilistic rounding error analysis and we show how rounding errors grow at an O(\sqrt{n}) rate rather than O(n) when SR is employed. This shows that Wilkinson's rule of thumb provably holds for this type of rounding. In the second part of the talk we consider the application of SR to parabolic PDEs admitting a steady state solution. We show that when the heat equation is solved in half precision RN fails to compute an accurate solution, while SR successfully solves the problem to decent accuracy.
 

We consider the problem of dynamically pricing multiple products on a network of resources, such as that faced by an airline selling tickets on its route network. For computational reasons this inherently stochastic problem is often approximated deterministically, however even the deterministic dynamic pricing problem can be impractical to solve. For this reason we have derived a novel iterative Quadratic Programming approximation to the deterministic dynamic pricing problem that is not only very fast to solve in practice but also exhibits a provably linear rate of convergence. This is joint work with Saksham Jain and Raphael Hauser.
 

Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson (who is speaking twice this week), and Tropp (SIREV 2011) contains extensive analysis, and made it a very popular method. 
The complexity for $m\times n$ matrices is $O(Nr+(m+n)r^2)$ where $N$ is the cost of a (fast) matrix-vector multiplication; which becomes $O(mn\log n+(m+n)r^2)$ for dense matrices. This work uses classical results in numerical linear algebra to reduce the computational cost to $O(Nr)$ without sacrificing numerical stability. The cost is essentially optimal for many classes of matrices, including $O(mn\log n)$ for dense matrices. The method can also be adapted for updating, downdating and perturbing the matrix, and is especially efficient relative to previous algorithms for such purposes.  

Robust principal component analysis and low-rank matrix completion are extensions of PCA that allow for outliers and missing entries, respectively. Solving these problems requires a low coherence between the low-rank matrix and the canonical basis. However, in both problems the well-posedness issue is even more fundamental; in some cases, both Robust PCA and matrix completion can fail to have any solutions due to the fact that the set of low-rank plus sparse matrices is not closed. Another consequence of this fact is that the lower restricted isometry property (RIP) bound cannot be satisfied for some low-rank plus sparse matrices unless further restrictions are imposed on the constituents. By restricting the energy of one of the components, we close the set and are able to derive the RIP over the set of low rank plus sparse matrices and operators satisfying concentration of measure inequalities. We show that the RIP of an operator implies exact recovery of a low-rank plus sparse matrix is possible with computationally tractable algorithms such as convex relaxations or line-search methods. We propose two efficient iterative methods called Normalized Iterative Hard Thresholding (NIHT) and Normalized Alternative Hard Thresholding (NAHT) that provably recover a low-rank plus sparse matrix from subsampled measurements taken by an operator satisfying the RIP.
 

Tensors are higher dimensional analogues of matrices, used to record data with multiple changing variables. Interpreting tensor data requires finding multi-linear stucture that depends on the application or context. I will describe a tensor-based clustering method for multi-dimensional data. The multi-linear structure is encoded as algebraic constraints in a linear program. I apply the method to a collection of experiments measuring the response of genetically diverse breast cancer cell lines to an array of ligands. In the second part of the talk, I will discuss low-rank decompositions of tensors that arise in statistics, focusing on two graphical models with hidden variables. I describe how the implicit semi-algebraic description of the statistical models can be used to obtain a closed form expression for the maximum likelihood estimate.

We present some regularity estimates for viscosity solutions to a class of possible degenerate and singular integro-differential equations whose leading operator switches between two different types of fractional elliptic phases, according to the zero set of a modulating coefficient a = a(·, ·). The model case is driven by the following nonlocal double phase operator,

$$\int \frac{|u(x) − u(y)|^{p−2} (u(x) − u(y))} {|x − y|^{n+sp}} dy+ \int a(x, y) \frac{|u(x) − u(y)|^{ q−2} (u(x) − u(y))} {|x − y|^{n+tq}} dy$$

where $q ≥ p$ and $a(·, ·) = 0$. Our results do also apply for inhomogeneous equations, for very general classes of measurable kernels. By simply assuming the boundedness of the modulating coefficient, we are able to prove that the solutions are Hölder continuous, whereas similar sharp results for the classical local case do require a to be Hölder continuous. To our knowledge, this is the first (regularity) result for nonlocal double phase problems.

Numerous researchers recently applied empirical spectral analysis to the study of modern deep learning classifiers. We identify and discuss an important formal class/cross-class structure and show how it lies at the origin of the many visually striking features observed in deepnet spectra, some of which were reported in recent articles and others unveiled here for the first time. These include spectral outliers and small but distinct bumps often seen beyond the edge of a "main bulk". The structure we identify organizes the coordinates of deepnet features and back-propagated errors, indexing them as an NxC or NxCxC array. Such arrays can be indexed by a two-tuple (i,c) or a three-tuple (i,c,c'), where i runs across the indices of the train set; c runs across the class indices and c' runs across the cross-class indices. This indexing naturally induces C class means, each obtained by averaging over the indices i and c' for a fixed class c. The same indexing also naturally defines C^2 cross-class means, each obtained by averaging over the index i for a fixed class c and a cross-class c'. We develop a formal process of spectral attribution, which is used to show the outliers are attributable to the C class means; the small bump next to the "main bulk" is attributable to between-cross-class covariance; and the "main bulk" is attributable to within-cross-class covariance. Formal theoretical results validate our attribution methodology.
We show how the effects of the class/cross-class structure permeate not only the spectra of deepnet features and backpropagated errors, but also the gradients, Fisher Information matrix and Hessian, whether these are considered in the context of an individual layer or the concatenation of them all. The Kronecker or Khatri-Rao product of the class means in the features and the class/cross-class means in the backpropagated errors approximates the class/cross-class means in the gradients. These means of gradients then create C and C^2 outliers in the spectrum of the Fisher Information matrix, which is the second moment of these gradients. The outliers in the Fisher Information matrix spectrum then create outliers in the Hessian spectrum. We explain the significance of this insight by proposing a correction to KFAC, a well known second-order optimization algorithm for training deepnets.

We study nearly singular PDEs that arise in the solution of linear elasticity and incompressible flow. We will demonstrate, that due to the nearly singular nature, standard methods for the solution of the linear systems arising in a finite element discretisation for these problems fail. We motivate two key ingredients required for a robust multigrid scheme for these equations and construct robust relaxation and prolongation operators for a particular choice of discretisation.
 

We consider CFTs with large gap in the spectrum of operators and a large number of degrees of freedom (large central charge). We analytically study a Heavy-Heavy-Light-Light correlation function, where Heavy, refers to an operator with conformal dimension which scales like the central charge and Light, refers to an operator whose dimension is of order unity in the large central charge limit. In certain regimes, the correlation function can be examined analytically leading to very simple and suggestive expressions.