Learning the Positions in CountSketch Article Swipe

MAKE IMPACT

Simin Liu , Tianrui Liu , Ali Vakilian , Yulin Wan , David P. Woodruff · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2306.06611

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~\cite{indyk2019learning}, 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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2306.06611

PDF

https://arxiv.org/pdf/2306.06611

OA Status

green

References

13

Related Works

10

OpenAlex ID

https://openalex.org/W3167284867

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3167284867

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2306.06611

Digital Object Identifier

Title

Learning the Positions in CountSketch

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-06-11

Full publication date if available

Authors

Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff

List of authors in order

Landing page

https://arxiv.org/abs/2306.06611

Publisher landing page

PDF URL

https://arxiv.org/pdf/2306.06611

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2306.06611

Direct OA link when available

Concepts

Sketch, Hessian matrix, Computer science, Greedy algorithm, Algorithm, Matrix (chemical analysis), Matrix norm, Gradient descent, Constraint (computer-aided design), Mathematical optimization, Optimization problem, Norm (philosophy), Artificial intelligence, Mathematics, Applied mathematics, Physics, Geometry, Composite material, Artificial neural network, Eigenvalues and eigenvectors, Political science, Quantum mechanics, Law, Materials science

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

13

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload