Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products. However, in tensor-structured settings, unstructured Gaussian or Rademacher test vectors may be prohibitively expensive to store and compute with, while cheaper rank-one tensor-product vectors can require sample complexities that grow exponentially with the tensor order. This work studies Gaussian random tensor train vectors as a structured alternative for stochastic trace estimation. We show that, with a suitable choice of the tensor train rank, random tensor train vectors recover dimension-independent guarantees for the Girard--Hutchinson estimator. In particular, a median-of-means variant with tensor train rank r≥d−1 achieves the same dependence on the accuracy ε and failure probability δ as the classical estimator based on unstructured Gaussian vectors. We further prove an oblivious subspace injection result for sketches formed from independent Gaussian random tensor train vectors: tensor train rank r≥d−1 and O(ε−2(k+log(1/δ))) samples suffice for a k-dimensional target subspace. Finally, we investigate the use of such sketches within the Nyström++ framework. We show that the resulting estimator can achieve the desired O(ε−1) sample complexity under an additional spectral-tail condition. These results provide clarififcation on both the potential and the limitations of random tensor train vectors in stochastic trace estimation.
We consider the problem of estimating the trace of an implicit matrix A∈Rdp×dp that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% \cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, Hm(A)=m1∑i=1mz(i)TAz(i),where z(i)∈Rdp, and zj(i)∈N(0,1),j∈[dp], satisfies the following guarantees: (i) E[Hm(A)]=tr(A), and (ii) Var[Hm(A)]=m2∣∣A∣∣F2. Generating one query vector z(i) requires O(dp) random bits; thus, m queries require O(mdp) random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in Rdp is constructed as the Kronecker product of p random vectors in Rd, requiring O(mpd) random bits for m query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with p. In this work, we address this limitation by proposing a sketching-based estimator that requires O(p(d+m)logm) random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with p.
Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma
\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels x⊗p∈Rdp. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), where D denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time O(p(\nnzx+DlogD)). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3p/D. Recent work by\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to 2p/D for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}\citep{pham2013fast} that achieves the same variance bound as\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.
Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1
Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have been highly successful, their analyses are largely estimator-specific and expectation-based, obscuring the structural tradeoffs that determine reliability. In this paper, we develop a unified framework for stochastic variance-reduced estimation based on a recursion with three components: memory retention, reset probability, and a correction term for iterate movement. This framework recovers several classical estimators, motivates new second-order variants, and yields a bias-variance decomposition of estimation error. Our main result is a unified high-probability bound proved using a new dimension-free vector-valued Freedman inequality, valid for smooth normed spaces involving random sums of vector martingales. The result applies in both Euclidean and non-Euclidean settings, including the analysis of mirror-descent-based methods in Banach spaces. As applications, we obtain high-probability oracle complexities for unconstrained optimization with mirror descent, establishing the logarithmic dependence on the confidence level. We also derive the first O~(ε−3) oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing O~(ε−4) complexity by leveraging variance-reduced estimation for the first time in this setting.