Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel

• URL: http://arxiv.org/abs/2202.02031v4
• Date: Sun, 30 Apr 2023 22:10:33 GMT
• Title: Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel
• Authors: Jonas Wacker, Ruben Ohana, Maurizio Filippone
• Abstract summary: Randomized sketches of a product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
• Score: 15.535749953841274
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $\mathcal{O}(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $\mathcal{O}(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.

Related papers

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• SketchINR: A First Look into Sketches as Implicit Neural Representations [120.4152701687737]
  We propose SketchINR, to advance the representation of vector sketches with implicit neural models. A variable length vector sketch is compressed into a latent space of fixed dimension that implicitly encodes the underlying shape as a function of time and strokes. For the first time, SketchINR emulates the human ability to reproduce a sketch with varying abstraction in terms of number and complexity of strokes.
  arXiv  Detail & Related papers  (2024-03-14T12:49:29Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  We provide an algorithmic framework for gaussianizing data distributions via averaging. We show that it is possible to efficiently construct data sketches that are nearly indistinguishable from sub-gaussian random designs.
  arXiv  Detail & Related papers  (2022-06-21T12:16:45Z)
• Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs [2.737640280995564]
  We use network embeddings to perform dimensionality reduction of tensor network structured inputs $x$. We provide an algorithm to efficiently sketch input data using such embeddings. We show optimality of an existing algorithm for train rounding.
  arXiv  Detail & Related papers  (2022-05-26T05:27:31Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Hashing embeddings of optimal dimension, with applications to linear least squares [1.2891210250935143]
  We present subspace embedding properties for $s$-hashing sketching matrices, with $sgeq 1$, that are optimal in the projection dimension $m$ of the sketch. We apply these results to the special case of Linear Least Squares (LLS), and develop Ski-LLS, a generic software package for these problems.
  arXiv  Detail & Related papers  (2021-05-25T10:35:13Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
  We propose a fast, distance-preserving, binary embedding algorithm to transform a dataset $mathcalTsubseteqmathbbRn$ into binary sequences in the cube $pm 1m$. Our method is both fast and memory efficient, with time complexity $O(m)$ and space complexity $O(m)$.
  arXiv  Detail & Related papers  (2020-10-01T22:41:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.