arXiv research

Matrix sketching balances class sizes for better supervised classification performance.

The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.

Newton-LESS sparsifies Gaussian sketching for faster optimization.

We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlike MMW, where every step requires full matrix exponentiation, our steps require only a single product of the form $e^A b$, which the Lanczos …

Algorithm learns a better sketch matrix for low-rank approximations.

Develops accelerated methods for optimization using low-dimensional projected-gradient information.

DBCL defends collaborative learning by sketching parameters to prevent gradient-based privacy inference attacks.

A new method improves convergence in low-rank approximation.

We improve prediction risk estimation for large datasets using sketching and ridge regression.

Detecting emergence of a low-rank signal from high-dimensional data is an important problem arising from many applications such as camera surveillance and swarm monitoring using sensors. We consider a procedure based on the largest eigenvalue of the sample covariance matrix over a sliding window to detect the change. T…

A new method uses matrix sketches for efficient graph clustering in dynamic environments.

A new method reduces the bias in estimating inverse covariance matrices from sketches.

This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a re…

New algorithm optimizes positions of CountSketch non-zero entries for better data compression.

Paper develops a bootstrap method for estimating sketched SVD errors.

Randomized SVD shows phase transitions in noisy data.

Paper proposes an online covariance estimator for sketched Newton methods.

Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given $n$ samples, the time and space complexity of computing the KRR estimate scale as $\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$ respectively, and so is prohibitive in many cases. We prop…

We consider the problem of finding anomalies in high-dimensional data using popular PCA based anomaly scores. The naive algorithms for computing these scores explicitly compute the PCA of the covariance matrix which uses space quadratic in the dimensionality of the data. We give the first streaming algorithms that use …

Develops precise expressions for random projections for better machine learning tasks.

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-speci…

Localized sketching improves matrix multiplication and ridge regression complexity.

Improved ridge regression with Frequent Directions for large-scale tasks.

We consider statistical as well as algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. For a LS problem with input data $(X, Y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n$, sketching algorithms use a sketching matrix, $S\in\mathbb{R}^{r \times n}$ with $r \…

Linear regression is a classic method of data analysis. In recent years, sketching -- a method of dimension reduction using random sampling, random projections, or both -- has gained popularity as an effective computational approximation when the number of observations greatly exceeds the number of variables. In this p…

Bundle method solves low rank SDP problems without full matrix construction.

Improved estimator for least squares using random projections achieves smaller error.

The immense amount of daily generated and communicated data presents unique challenges in their processing. Clustering, the grouping of data without the presence of ground-truth labels, is an important tool for drawing inferences from data. Subspace clustering (SC) is a relatively recent method that is able to successf…

We accelerate the power method for strong low-rank approximation using fast sketching.

New algorithm converts data into sub-gaussian designs efficiently.

A parallel optimization method for convex functions using Hessian sketching and debiasing.

A fast sketching algorithm solves regularized least squares problems efficiently.

The paper develops concentration inequalities for structured random data, extending beyond independent terms.

Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-$k$ projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These condit…

The main contribution of the paper is to show that Gaussian sketching of a kernel-Gram matrix $\boldsymbol K$ yields an operator whose counterpart in an RKHS $\mathcal H$, is a \emph{random projection} operator---in the spirit of Johnson-Lindenstrauss (J-L) lemma. To be precise, given a random matrix $Z$ with i.i.d. Ga…

New method reduces linear regret in high-dimensional bandit problems.

This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modi…

Paper develops a method for estimating PFLM with minimized rates in high dimensions.

New analysis proves sketching operators' RIP guarantees for mixture models without importance sampling.

We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance meas…

Paper studies randomized spectral clustering for large-scale networks.

New method for online inference of constrained optimization problems.

A new method for estimating large-scale linear models with improved precision.

New algorithm reduces sketching dimension to effective problem size.

In recent years, randomized methods for numerical linear algebra have received growing interest as a general approach to large-scale problems. Typically, the essential ingredient of these methods is some form of randomized dimension reduction, which accelerates computations, but also creates random approximation error.…

New methods for sketching non-PSD matrices improve regression and optimization tasks.

Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner …

Given a matrix $A\in \mathbb{R}^{n\times d}$ and a vector $b\in \mathbb{R}^n$, we consider the regression problem with $\ell_\infty$ guarantees: finding a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty \leq \fracε{\sqrt{d}}\cdot \|Ax^*-b\|_2\cdot \|A^\dagger\|$ where $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|…