arXiv research

Paper proposes an online covariance estimator for sketched Newton methods.

FROSH and DFROSH speed up online sketching hashing for big data.

We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the model. This enables memory-limited execution of several statistical analyses over streams, including online featu…

Density sketches summarize data distributions for accurate sampling and estimation.

We present the first sublinear memory sketch that can be queried to find the nearest neighbors in a dataset. Our online sketching algorithm compresses an N element dataset to a sketch of size $O(N^b \log^3 N)$ in $O(N^{(b+1)} \log^3 N)$ time, where $b < 1$. This sketch can correctly report the nearest neighbors of any …

New method for online inference of constrained optimization problems.

Paper proposes an efficient online Newton method with Nesterov's acceleration for streaming data.

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 …

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

We prove that two popular linear contextual bandit algorithms, OFUL and Thompson Sampling, can be made efficient using Frequent Directions, a deterministic online sketching technique. More precisely, we show that a sketch of size $m$ allows a $\mathcal{O}(md)$ update time for both algorithms, as opposed to $Ω(d^2)$ req…

New method solves constrained stochastic optimization problems efficiently.

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 algorithm reduces the time and space complexity for multinomial logistic bandits.

Kernel online convex optimization (KOCO) is a framework combining the expressiveness of non-parametric kernel models with the regret guarantees of online learning. First-order KOCO methods such as functional gradient descent require only $\mathcal{O}(t)$ time and space per iteration, and, when the only information on t…

SketchOGD improves memory efficiency for continual learning.

STORM enables edge computing for empirical risk minimization.

Sketch-BERT learns vector sketches using BERT-like self-supervised learning.

Cost-Sensitive Online Classification has drawn extensive attention in recent years, where the main approach is to directly online optimize two well-known cost-sensitive metrics: (i) weighted sum of sensitivity and specificity; (ii) weighted misclassification cost. However, previous existing methods only considered firs…

A new method improves convergence in low-rank approximation.

This appendix proves CORN's universal consistency. One of Bin's PhD thesis examiner (Special thanks to Vladimir Vovk from Royal Holloway, University of London) suggested that CORN is universal and provided sketch proof of Lemma 1.6, which is the key of this proof. Based on the proof in Gyprfi et al. [2006], we thus pro…

Sketchy reduces memory and compute requirements for adaptive regularization in deep learning.

We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical …

We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inputs and outputs of the network and can be used to quickly identify key components and summary statistics of the inputs. Furthermore, the sket…

Localized sketching improves matrix multiplication and ridge regression complexity.

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

New guarantees for asymmetric sketching in compressive learning.

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

With the scale of data growing every day, reducing the dimensionality (a.k.a. sketching) of high-dimensional data has emerged as a task of paramount importance. Relevant issues to address in this context include the sheer volume of data that may consist of categorical samples, the typically streaming format of acquisit…

A fast sketching algorithm solves regularized least squares problems efficiently.

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

Private sketches protect linear regression data privacy.

Sketching is a randomized dimensionality-reduction method that aims to preserve relevant information in large-scale datasets. Count sketch is a simple popular sketch which uses a randomized hash function to achieve compression. In this paper, we propose a novel extension known as Higher-order Count Sketch (HCS). While …

DiPS learns to optimize sketching policies for better recommendation quality.

Paper proposes Nyström sketches for better adaptive compressive learning.

Sketching is more fundamental to human cognition than speech. Deep Neural Networks (DNNs) have achieved the state-of-the-art in speech-related tasks but have not made significant development in generating stroke-based sketches a.k.a sketches in vector format. Though there are Variational Auto Encoders (VAEs) for genera…

Improved sketching for logistic and $\ell_1$ regression with near-linear dimensions.

Unified bounds for sketched bilinear forms in machine learning and statistics.

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

MetaGrad adapts multiple learning rates for faster online optimization.

Sketching accelerates structured prediction methods for large datasets.

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…

Paper develops a bootstrap method for estimating sketched SVD errors.

Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessia…

We present sketch-rnn, a recurrent neural network (RNN) able to construct stroke-based drawings of common objects. The model is trained on thousands of crude human-drawn images representing hundreds of classes. We outline a framework for conditional and unconditional sketch generation, and describe new robust training …

Sketching reduces data size for accurate spectral estimation.

Downsampling can improve generalization in ridgeless linear regression, especially with optimal sketching size.

A new data-oblivious sketch for logistic regression reduces data size while maintaining approximation accuracy.

Sketch-GNN reduces GNN training time and memory usage to sublinear scales.