ε-coresets for attention exist of size O(√d e^{ρ+o(ρ)}/ε) for unit-norm keys/values and queries of norm ≤ρ, nearly matching the Ω(√d e^ρ/ε) lower bound.
Spectral norm of random tensors, 2014.https://arxiv.org/abs/ 1407.1870
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We show that the spectral norm of a random $n_1\times n_2\times \cdots \times n_K$ tensor (or higher-order array) scales as $O\left(\sqrt{(\sum_{k=1}^{K}n_k)\log(K)}\right)$ under some sub-Gaussian assumption on the entries. The proof is based on a covering number argument. Since the spectral norm is dual to the tensor nuclear norm (the tightest convex relaxation of the set of rank one tensors), the bound implies that the convex relaxation yields sample complexity that is linear in (the sum of) the number of dimensions, which is much smaller than other recently proposed convex relaxations of tensor rank that use unfolding.
years
2026 2verdicts
UNVERDICTED 2representative citing papers
Finite-iteration local theory and generic warm-start conditions for alternating power iteration on asymmetric rank-one spiked tensors, reducing to high-signal regime under multilinear noise events.
citing papers explorer
-
Nearly Optimal Attention Coresets
ε-coresets for attention exist of size O(√d e^{ρ+o(ρ)}/ε) for unit-norm keys/values and queries of norm ≤ρ, nearly matching the Ω(√d e^ρ/ε) lower bound.
-
Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA
Finite-iteration local theory and generic warm-start conditions for alternating power iteration on asymmetric rank-one spiked tensors, reducing to high-signal regime under multilinear noise events.