Workshop Details

Suppose we are given a distance or similarity matrix for a data set that is corrupted in some fashion, find a sparse correction or repair to the distance matrix so as to ensure the corrected distances come from a metric; i.e., repair as few entries as possible in the matrix so that we have a metric. I will discuss generalizations to graph metrics, applications to (and from) metric embeddings, and algorithms for variations of this problem. I will also touch upon applications in machine learning and bio-informatics.

We study the query complexity of estimating the covariance matrix T of a distribution D over d-dimensional vectors, under the assumption that T is Toeplitz. This assumption is standard in a wide variety of signal processing problems, where the covariance between any two measurements only depends on the time or distance between those measurements. In many of these applications, we are interested in estimation strategies that may choose to view only a subset of entries in each d-dimensional sample from D. We care about minimizing both 1) the number of samples taken and 2) the number of entries accessed in each sample, which often equates to minimizing equipment requirements in applications ranging from wireless transmission to advanced imaging.
We give some of the first nontrivial non-asymptotic bounds on these sample complexity measures. We analyze classical and widely used estimation algorithms, in particular methods based on selecting entries from each sample according to a \`sparse ruler'. We explain how sparse ruler based estimation can significantly outperform naive methods when T is close to low-rank, as is often the case in practice. We also develop a novel sampling and estimation strategy that improves on known algorithms in the low-rank case. Our method utilizes tools from random matrix sketching, leverage score based sampling techniques for continuous time signals, and sparse Fourier transform algorithms. 
This work is part of a broader agenda to address fundamental problems in signal processing using tools from theoretical computer science and randomized numerical linear algebra.

Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average reconstruction error. We study the multi-criteria dimensionality reduction problem, where we are given multiple objectives that need to be optimized simultaneously. As an application, our model captures several fairness criteria for dimensionality reduction such as the Fair PCA problem and the Nash Social Welfare (NSW) problem. In the Fair PCA problem, input data is divided into k groups, and the goal is to find a single d-dimensional representation for all groups for which the maximum reconstruction error of any one group is minimized. In NSW, the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensional space. 

Our main result is an exact polynomial-time algorithm for the two-criteria dimensionality reduction problem when the two criteria are increasing concave functions. As an application of this result, we obtain polynomial-time algorithms for Fair PCA and NSW for k=2 groups. We also give approximation algorithms for k>2 (and show the problem is NP-hard for general k, even for d=1). These results are based on new low-rank properties of extreme point solutions to semi-definite programs, and a generalization of iterative rounding for semidefinite programs, which appear to be of independent interest. 

This is joint work with Samira Samadi, Uthaipon Tantipongpipat, Jamie Morgenstern and Mohit Singh.

We consider the application of sketching to low CP-rank approximation of tensors. Prior works have introduced novel forms of sketching that are well-suited to this setting from the computational perspective, but have left open the question of whether the resulting heuristics converge. In this work, we provide generic conditions under which sketched, regularized alternating least squares algorithms guarantee convergence to a stationary point. Our results imply that the sketching rate must vary during the optimization procedure to ensure convergence. Based on this insight, we introduce CPD-MWU, an algorithm that predicts and tracks the best choice of sketching rate over the course of the optimization, and show empirically that CPD-MWU performs as well as other sketched ALS algorithms while also being much more robust to the selection of the sketching rate hyperparameter.

Computing and maintaining large graphs are increasingly important problems in data mining, machine learning, and security. This talk will use progress on two well-studied problems in static and dynamic graph algorithms, net-work flows and dynamic matchings, to discuss a methodology for designing faster algorithm for large graphs motivated by long-standing open problems in data structures.

I will start by describing how studies of network flows led to a focus on residual networks, which in turn motivated faster algorithms as well as more general notions of preconditioning. I will then discuss a similar phenomenon in dynamic graphs, where the current best algorithms for maintaining large matchings utilize kernels built from dual vertex covers.

Over the past few years, various randomized gradient compression (e.g., quantization, sparsification, sketching) techniques have been proposed for reducing communication in distributed training of very large machine learning models. However, despite high level of research activity in this area, surprisingly little is known about how such compression techniques should properly interact with first order optimization algorithms. For instance, randomized compression increases the variance of the stochastic gradient estimator, and this has an adverse effect on convergence speed. While a number of variance-reduction techniques exists for taming the variance of stochastic gradients arising from sub-sampling in finite-sum optimization problems, no variance reduction techniques exist for taming the variance introduced by gradient compression. Further, gradient compression techniques are invariably applied to unconstrained problems, and it is not known whether and how they could be applied to solve constrained or proximal problems. In this talk I will give positive resolutions to both of these problems. In particular, I will show how one can design fast variance-reduced proximal stochastic gradient descent methods in settings where stochasticity comes from gradient compression. 

This talk is based on:

[1] Filip Hanzely, Konstantin Mishchenko and Peter Richtárik SEGA: Variance reduction via gradient sketching NeurIPS 2018

[2] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč and Peter Richtárik Distributed learning with compressed gradient differences arXiv: 1901.09269

[3] Konstantin Mishchenko, Filip Hanzely and Peter Richtárik 99% of distributed optimization is a waste of time: the issue and how to fix it arXiv:1901.09437

[4] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik and Sebastian Stich Stochastic distributed learning with gradient quantization and variance reduction arXiv:1904.05115

To compute a small subset of the eigenvalues of a matrix, contour integral algorithms evaluate the action of the resolvent on low-dimensional right and left subspaces, sampled at points on the contour.  These algorithms have grown in popularity over the past 15 years, and hold particular promise as potential black-box solvers for nonlinear eigenvalue problems.  We will describe this general class of methods, and show how they relate to system realization algorithms from control theory.  This observation motivates a new method for nonlinear eigenvalue problems based on rational interpolation in random tangential directions.  This talk describes joint work with Michael Brennan (MIT) and Serkan Gugercin (Virginia Tech).

For full-rank least squares regression problems under a Gaussian linear model,  we analyze the uncertainties when the minimum-norm solution is computed by random row-sketching and, in particular random row sampling. Our expressions for the total expectation and variance of the solution - with regard to both model- and algorithm-induced uncertainties - are exact; hold for general sketching matrices; and make no assumptions on the rank of the sketched matrix. They show that expectation and variance are governed by the rank-deficiency and spatial geometry induced by the sketching process, rather than by structural properties of specific sketching or sampling methods.
From a deterministic perspective, our structural perturbation bounds imply that least squares solutions are less sensitive to multiplicative perturbations than to additive perturbations.  From a probabilistic perspective, we show that the differences between the total bias and variance on the one hand, and the model bias and variance on the other hand, are governed by two factors: (i) the expected rank deficiency of the sketched matrix, and (ii) the expected difference between projectors onto the spaces of the  original and the sketched problems.
This is joint work with Jocelyn Chi.

Performing statistical analysis of Randomized Numerical Linear Algebra (RandNLA) algorithms is challenging since there are two sources of randomness---one coming from noise in the data, and one coming from coin flips inside the algorithm itself---and since the randomness enters the estimators in a non-linear manner. In this talk, I will present techniques from asymptotic statistics to analyze RandNLA sampling estimators for the least squares.

Establishing global convergence of the classical Newton’s method has long been limited to making restrictive assumptions on (strong) convexity as well as Lipschitz continuity of the gradient/Hessian. We show  that two simple modifications of the classical Newton’s method result in an algorithm, called Newton-MR, which is almost indistinguishable from its classical counterpart but it can readily be applied to invex problems. By introducing a weaker notion of joint regularity of Hessian and gradient, we show that Newton-MR converges even in the absence of the traditional smoothness assumptions. We then turn to theoretically study the stability of Newton-MR under Hessian perturbations, which allows one to design efficient variants for large-scale problems where the curvature information is suitably approximated.

Leverage scores have arisen as a central and powerful tool in randomized numerical linear algebra. These scores measure the "importance" of rows or columns in a matrix and can be used to design fast randomized algorithms for regression, low-rank approximation, kernel learning, and many other matrix problems. In this talk, I will illustrate the potential of leverage scores to bring the power of randomization to an even broader class of problems in computational mathematics and signal processing. In particular, I will introduce a simple generalization of leverage scores to continuous linear operators and survey applications to polynomial curve fitting, bandlimited function interpolation, off-grid sparse Fourier transforms, and signal covariance estimation. Such applications present an exciting opportunity to apply ideas from RandNLA to new domains. I will devote a large portion of the talk to illustrating connections between randomized methods and classical tools in approximation theory. I will also discuss several open questions.

The representation and benefits of learning methods based on graph Laplacians, such as Laplacian smoothing or harmonic function solution for semi-supervised learning, are empirically and theoretically well supported. There is an increasing number of very large real-world graphs with a number of edges which is sufficiently large for sparsification algorithms to become practically applicable. Motivated by learning algorithms that employ regularization, we discuss the design and properties of a distributed algorithm for ridge spectral sparsification with demonstrable practical gains. The talk represents joint work with Daniele Calandriello, Alesandro Lazaric, and Michal Valko.

We formulate a geometric problem called Latent Simplex Learning (LSL) which includes as special cases the core problem in several Unsupervised Learning settings such as Topic Modeling and Mixed Community Block Membership models. LSL is simply stated:find a latent k-simplex K in Rd given n data points, each obtained by perturbing a latent point in K. The perturbations are large and most data points lie (far) outside K.
Under natural assumptions, which we show hold in the applications, we devise a algorithm to solve LSL which runs in time O*(k nnz) matching the best running time of algorithms in special cases. We use a new technique we call "subset smoothing" which optimizes k carefully chosen linear functions over the convex hull of (n  δn) points, obtained by averaging all δn subsets of the data points. We prove that each optimization yields an approximation to a new vertex of K. The proof is non-trivial and uses existing and new tools from Numerical Analysis, especially angles between singular spaces of close-by matrices.
Joint work with C. Bhattacharyya.

Ridge regression is frequently used to regularize ill-posed linear least-squares problems.  While ridge regression provides shrinkage for the regression coefficients, many of the coefficients remain small but non-zero.  We provide a deterministic algorithm using ridge leverage scores that effectively forces coefficients to zero.  This algorithm has a provable $(1+epsilon)$ bound on the statistical risk.  As such, it is an interesting alternative to elastic net regularization.  Our ridge regression bound follows from the properties of ridge leverage scores, which balance low-rank approximation and regularization.  We also give provable guarantees for deterministic column sampling using ridge leverage scores. Like the randomized counterparts, the deterministic algorithm provides $(1+epsilon)$  error column subset selection, $(1+epsilon)$ error projection-cost preservation, and an additive-multiplicative spectral bound.  We also show that under the assumption of power-law decay of ridge leverage scores, this deterministic algorithm is provably as accurate as randomized algorithms. 

Given a positive semi-definite n x n matrix L, we study the complexity of sampling from a distribution over all index subsets of the set 1,...,n where the probability of a subset S is proportional to the determinant of the submatrix of L with rows and columns indexed by S. Known as a determinantal point process, this distribution is widely used in machine learning and stochastic optimization to induce diversity in subset selection. It also provides optimal low-rank reconstruction guarantees for row/column subset selection and is used in combinatorial approximation algorithms for experimental design. In practice, we often wish to sample multiple subsets S with small expected size k = E[

In recent years, many randomized algorithms have been proposed for computing approximate solutions to large-scale problems in numerical linear algebra. However, the user rarely knows the actual error of a randomized solution. For this reason, it is common to rely on theoretical worst-case error bounds as a source of guidance. As a more practical alternative, we propose bootstrap methods to obtain direct error estimates for randomized solutions. Specifically, in the contexts of matrix multiplication and least-squares, we show that bootstrap error estimates are theoretically justified, and incur modest computational cost.

Joint work with Benjamin Erichson, Michael Mahoney, and Shusen Wang.

Oblivious subspace embeddings have proven to be an essential ingredient for approximately solving numerical linear algebra problems, such as regression and low-rank approximation.

While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of p = 1, much less was known. In this talk I will present our results on l1 oblivious subspace embeddings, including (i) nearly optimal lower bounds and (ii) new constructions for sparse l1 oblivious subspace embeddings.

Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise lp low rank approximation. Our results give improved algorithms for these applications.

Based on joint work with Ruosong Wang.

Random Matrix Theory (RMT) is applied to analyze the weight matrices of Deep Neural Networks (DNNs), including both production quality, pre-trained models and smaller models trained from scratch.  Empirical and theoretical results clearly indicate that the DNN training process itself implicitly implements a form of self-regularization, implicitly sculpting a more regularized energy or penalty landscape.  In particular, the empirical spectral density (ESD) of DNN layer matrices displays signatures of traditionally-regularized statistical models, even in the absence of exogenously specifying traditional forms of explicit regularization.  Building on relatively recent results in RMT, most notably its extension to Universality classes of Heavy-Tailed matrices, and applying them to these empirical results, we develop a theory to identify 5+1 Phases of Training, corresponding to increasing amounts of implicit self-regularization.  For smaller and/or older DNNs, this implicit self-regularization is like traditional Tikhonov regularization, in that there appears to be a \`\`size scale'' separating signal from noise.  For state-of-the-art DNNs, however, we identify a novel form of heavy-tailed self-regularization, similar to the self-organization seen in the statistical physics of disordered systems.  This implicit self-regularization can depend strongly on the many knobs of the training process.  In particular, by exploiting the generalization gap phenomena, we demonstrate that we can cause a small model to exhibit all 5+1 phases of training simply by changing the batch size.  This demonstrates that---all else being equal---DNN optimization with larger batch sizes leads to less-well implicitly-regularized models, and it provides an explanation for the generalization gap phenomena.  Joint work with Charles Martin of Calculation Consulting, Inc.

Federated learning (FL), also known as collaborative learning, allows multiple parties to jointly learn a model without data sharing. In this way, users' data privacy is seemingly protected. Unfortunately, although a participant's data never leave his machine, his data can be disclosed from his gradients and the global model parameters. Prior work demonstrated that one participant, not to mention the central server, can easily infer the other participants' data. The work showed that simple defenses like dropout, differential privacy, and federated averaging do not work. Since FL has been applied in the industry, its vulnerability to data leakage attacks may cause serious consequences.

We propose Double-Blind Federated Learning (DBFL) for defending against the data leakage attacks. The reason why FL is unsafe is that first, the server sees the participants' gradients and second, the participants see the true model parameters. Our key insight is to make FL double-blind: the server does not see the gradients, and the participants do not see the model parameters. DBFL is based on matrix sketching: the gradients are evaluated on sketched inputs, and the server sends only sketched parameters to the participants. DBFL is a generalization of dropout training (from uniform sampling to general sketching), and thus it is easy to tune and does not hurt test accuracy. While dropout fails, DBFL succeeds in defending some of the attacks. 

For solving large-scale non-convex problems, we propose inexact variants of trust region and adaptive cubic regularization methods, which, to increase efficiency, incorporate various approximations. In particular, in addition to approximate subproblem solves, both the Hessian and the gradient are suitably approximated. Using rather mild conditions on such approximations, we show that our proposed inexact methods achieve similar optimal worst-case iteration complexities as the exact counterparts. Our proposed algorithms, and their respective theoretical analysis, do not require knowledge of any unknowable problem-related quantities, and hence are easily implementable in practice. Furthermore, using the approximation of Hessian information, we propose a novel large batch training method on which combines recent results in adversarial training (to regularize against “sharp minima”) and second-order optimization (to use curvature information to change batch size adaptively during training). Without any additional hyper-parameter tuning, our method can reduce the number of SGD iterations of ResNet18 on Cifar-10/ImageNet to 44.8x and 28.8x, respectively.

Modern neural networks are commonly trained with gradient-based methods. The understanding of the dynamics of gradient descent algorithm is one of the key issues for the theoretical comprehension of why deep neural nets work so well today. In this work, we introduce a random matrix-based framework to analyze the dynamics of a simple toy network model trained by gradient descent. This preliminary result opens the door for future studies of more elaborate structures and models appearing in today’s neural networks.

Low-rank matrix approximations have become a technique of central importance in large scale data science. In this talk we discuss a set of novel low-rank matrix approximation algorithms that are taylored for all levels of accuracy requirements for maximum computational efficiency. These algorithms include spectrum-revealing matrix factorizations that are optimal up to dimension-dependent constants, and an efficient truncated SVD (singular value decomposition) that is accurate up to a given tolerance. We provide theoretical error bounds for both singular values and singular subspaces and numerical evidence that demonstrate the supriority of our algorithms over existing ones, and show their usefulness in a number of data science applications.

Sampling is one of the fundamental hammers in machine learning (ML) for reducing the size and scale of the problem at hand. Many ML applications demand adaptive sampling for faster convergence. However, the cost of adaptive sampling itself is prohibitive when the sampling weights are changing. This creates a fundamental barrier. 

In this talk, I will discuss some of my recent and surprising findings on the use of hashing algorithms for large-scale estimations. Locality Sensitive Hashing (LSH) is a hugely popular algorithm for sub-linear near neighbor search. However, it turns out that fundamentally LSH is a constant time (amortized) adaptive sampler from which efficient near-neighbor search is one of the many possibilities. LSH offers a unique capability to do smart sampling and statistical estimations at the cost of few hash lookups. Our observation bridges data structures (probabilistic hash tables) with efficient unbiased statistical estimations. I will demonstrate how this dynamic and efficient sampling beak the computational barriers in adaptive estimations, where it is possible that we pay roughly the cost of uniform sampling but get the benefits of adaptive sampling. I will demonstrate the power of a straightforward idea for a variety of problems 1) Adaptive Gradient Estimations for efficient SGD, 2) Efficient Deep Learning, 3) Anomaly Detection, and 4) The first possibility of sub-linear sketches for near-neighbor queries.