# Learning the Positions in CountSketch

arXiv: https://arxiv.org/abs/2306.06611 · HTML: https://mlsanity.com/paper/2306.06611/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 11 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [Hyperspectral Image Dataset for Benchmarking on Salient Object Detection](https://mlsanity.com/paper/1806.11314/) (2018)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [(Learned) Frequency Estimation Algorithms under Zipfian Distribution](https://mlsanity.com/paper/1908.05198/) (2019)
- [Composable Sketches for Functions of Frequencies: Beyond the Worst Case](https://mlsanity.com/paper/2004.04772/) (2020)
- [Learning Space Partitions for Nearest Neighbor Search](https://mlsanity.com/paper/1901.08544/) (2019)
- [Iterative Hessian Sketch in Input Sparsity Time](https://mlsanity.com/paper/1910.14166/) (2019)

## Abstract (arXiv)

We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low-rank approximation and regression. In the learning-based sketching paradigm proposed by~citeindyk2019learning, the sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch, and then the values of its non-zero entries are updated by running gradient descent on a training data set. Despite the growing body of work on this paradigm, a noticeable omission is that the locations of the non-zero entries of previous algorithms were fixed, and only their values were learned. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries. Our first proposed algorithm is based on a greedy algorithm. However, one drawback of the greedy algorithm is its slower training time. We fix this issue and propose approaches for learning a sketching matrix for both low-rank approximation and Hessian approximation for second order optimization. The latter is helpful for a range of constrained optimization problems, such as LASSO and matrix estimation with a nuclear norm constraint. Both approaches achieve good accuracy with a fast running time. Moreover, our experiments suggest that our algorithm can still reduce the error significantly even if we only have a very limited number of training matrices.