acceptodds
Under review as a conference paper at ICLR 2027

Estimating Traces from Noisy Matrix–Vector Products

Abstract

Trace estimation for curvature, sensitivity, and second-order statistics can involve stochastic products, making the low-rank approximation used for variance reduction noisy. We determine both the optimal query cost and when spending queries on such an approximation improves accuracy. For a -dimensional positive semidefinite matrix with trace in , we allow adaptive unit-vector queries with fresh centered noise of total second moment at most and query-direction variance at most , where . At constant confidence, the minimax cost for relative error is . Complete correction adds the trace of the realized noisy approximation and subtracts that same approximation in every residual observation. This correction and sufficiently averaged projected estimation attain the rate, with coordinate queries in small dimensions. An exact equal-budget variance identity determines when correction improves on independent sphere sampling. Fixed noise covariance reduces the worst-case noise term to . Experiments on an 81,290-parameter CNN reveal a minibatch-quality crossover. Paid decisions and a fresh-product XTrace comparison expose the cost of noisy pilots; model-score comparisons identify settings where direct model access is computationally preferable.

Primary area:
learning theory
Keywords:
trace estimation, randomized numerical linear algebra, stochastic matrix-vector products, variance reduction, minimax query complexity, Hutch++

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_LetFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies trace estimation for positive semidefinite matrices when matrix-vector products are corrupted by fresh, centered noise. The authors propose a low-rank estimator with complete correction, which reuses the same noisy low-rank approximation in both the estimated trace and residual estimation to maintain unbiasedness. They establish a matching minimax query complexity of Θ(min⁡(d,ϵ−1)+d2ρσ2ϵ−2)\Theta(\min(d,\epsilon^{-1})+d^2\rho\sigma^2\epsilon^{-2}), including lower bounds for adaptive algorithms.

The paper further derives an exact finite budget criterion characterizing when the proposed correction method outperforms standard sphere-based Monte Carlo estimation. It also analyzes how different noise structures affect query complexity. The theoretical findings are supported by synthetic experiments and evaluations on covariance estimation and neural-network curvature estimation, with comparisons against several existing estimators.

Critical strengths
  • Tight minimax query complexity: the paper establishes matching upper and lower bounds for trace estimation under noisy matrix-vector products, providing an optimal query complexity characterization across different noise regimes. The lower bounds also account for adaptive query algorithms, making the result comprehensive.

  • Analysis of different noise regimes and structures: the paper considers various noise levels, directional dependencies, and covariance structures, and characterizes how these properties affect estimation complexity and the benefit of low-rank correction. The synthetic experiments systematically illustrate these effects, including the regimes where correction is beneficial and where its overhead outweighs the variance reduction.

Critical weaknesses
  • Limited practical advantage and unclear application relevance: although the proposed method achieves optimal query complexity under the specified noisy matrix-vector oracle model, the experimental results do not demonstrate a consistent advantage over existing methods across different settings. More importantly, the evaluated applications admit alternative approaches that exploit additional structural properties and can achieve better results. For instance, direct sample-norm estimation performs substantially better in the covariance experiments, while the score-norm estimator achieves better accuracy and computational efficiency in several neural-network settings. This raises the question of whether the restricted noisy matrix-vector oracle model is the most appropriate formulation for the motivating applications. I think the theoretical optimality is valuable, but the practical significance is less convincing if the underlying application problems can be addressed more effectively.

  • Limited practical utility of the benefit criterion: the paper derives an exact criterion for determining when low-rank correction outperforms standard sphere sampling. However, evaluating this criterion requires quantities that are generally unknown to the estimator, including the original probe variance and oracle noise variance. As a result, the criterion does not directly provide an actionable strategy for deciding whether to construct a pilot in the first place. Although the authors investigate a paid diagnostic policy, this policy makes its decision only after the pilot cost has already been incurred. Consequently, the practically important problem of adaptively deciding whether to use correction or direct sampling remains largely unresolved.

Questions for authors
  1. Novelty relative to Hutch++: the proposed method builds upon the existing low-rank trace estimation and control-variate framework of Hutch++. Could the authors clarify the main technical novelty beyond extending this framework to noisy matrix-vector products? Specifically, what are the fundamental challenges introduced by fresh oracle noise, and which parts of the proposed analysis or algorithm require genuinely new techniques rather than relatively direct adaptations of existing results?

  2. Relevance of the motivating applications: see above; in the evaluated applications, alternative estimators exploiting additional structural information can outperform the proposed method. Could the authors identify practical applications where noisy matrix-vector products are the natural or only feasible access model, and where such structure-exploiting alternatives are unavailable or computationally less attractive? Demonstrating the method's effectiveness in such settings would help establish the significance of the proposed problem formulation.

  3. Choice of baselines: Sphere-based Monte Carlo is a relatively simple randomized trace estimator, and improvements over this baseline in low-noise regimes seem largely consistent with existing low-rank variance-reduction intuition. What additional algorithmic insights does the proposed method provide beyond this expected behavior?

  4. Adaptive estimator selection: Is it possible to develop a practical policy that decides whether to invest in a low-rank pilot before incurring its construction cost, without prior knowledge of the relevant variance quantities? Are there additional theoretical results or potential approaches for adaptive budget allocation under reasonable assumptions on the oracle noise? I think such a result would substantially improve the practical usefulness.

  5. Significance of the synthetic experiments: several synthetic experiments appear primarily to verify phenomena that follow directly from the theoretical analysis. For example, the benefit-criterion experiment compares empirical MSE against predictions from an exact variance identity, while the qualitative noise-dependent crossover is already suggested by the theoretical framework. Could the authors clarify what additional insights these experiments provide beyond validating the derived expressions and the implementation?

Reviewer_EnNcOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper discusses estimating the trace of a PSD matrix AA which is assumed unknown. One can only access noisy matrix vector products Av+noiseAv + noise, and the authors propose analyzing the number of queries vv necessary to achieve an (ε,δ)(\varepsilon, \delta)-PAC guarantee. Lower bounds are proposed and a Gaussian-based sketched trace estimator, which uses a control-variate correction, is analyzed.

Critical strengths

The paper analyzes both lower bounds and upper bounds jointly.

Critical weaknesses

The writing quality and the narrative of this paper are in my view completely insufficient as I had a very difficult time reading this paper (I precise that I did not rely on AI hence my understanding of this paper is mainly restricted by my reading of it).

Several parts of this paper feel robotically written, left to the reader to decipher, and not motivated, which is a major weakness for a learning theory paper. Some unclear examples are: "The model permits exact local arithmetic", the paragraph starting from "Independent median amplification multiplies the upper bound by O(log⁡(1/δ))O(\log(1/\delta))" at Line 150. The minimax bounds are never properly defined, nor the "oracle class" and notation Θ\Theta does not say what constant it hides especially as it takes a fixed value of δ=0.1\delta=0.1. The estimator τ^\hat \tau does not say what it observes and uses, hence Theorem 1 (and similarly Theorem 6) is currently not meaningful from my perspective. The proof of Lemma 2 is just a collection of short sentences with no connection nor justification. The cost cc is not defined, qq neither making Corollary 3 and this benefit of correction hard for me to read. The upper bounds are proposed in expectation while the lower bound in probaiblity.

Furthermore, the theoretical impact seems quite limited to me, especially as the Related section is very short and the paper proposes little interpretation of the results. Algorithm 1 is essentially the randomized SVD of Halko, Tropp, Martinsson whose theory has been already extensively studied with additional power iteration scheme.

Questions for authors

My main questions are about the assumptions.

Q1: Did you measure ρ\rho ?

Q2: It is assumed that Tr(A)∈[1,2]\mathrm{Tr}(A)\in [1,2]. Can you discuss it ?

Reviewer_ypi1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of approximation of traces using noisy matrix-vector products (MVP). Specifically, the authors ask: a) how many noisy MVPs produce an accurate trace estimate, and b) when does a noisy low-rank initial MVP probe improve accuracy at a fixed budget. The authors show that when the trace of a matrix is in [1,2][1,2], using O~(1/ϵ2)\tilde{O}(1/\epsilon^2) queries one can approximate the trace of a PSD matrix even with a noisy matvec oracle. The authors also provide experimental evidence on real world matrices.

Critical strengths
  1. The idea of studying trace approximations in a noisy matvec oracle is novel and worth further investigation. This paper introduces this idea.
  2. Experiments on real world matrices are generally convincing.
Critical weaknesses
  1. The first paragraph talks about how a random sample produces different outputs when compute random matvecs. It is somewhat confusing why we are talking about this, when it is trivially known that random matvecs or any randomized procedure will produce different results at any run. I feel like this was not a wise use of space.
  2. The symbols are not explained before being used, e.g., HH and ZZ in Equation 1. There are also weird phrases like “paid pilot decisions” which seems pretty confusing.
  3. The theta bound in Theorem 1 seems incorrect as stated? The upper bound gives O(log⁡(1/δ)/ϵ2+log⁡(1/δ)min⁡(d,1/ϵ))O(\log(1/\delta)/ \epsilon^2 + \log(1/\delta)\min(d, 1/\epsilon)) and the adaptive lower bound is O(log⁡(1/δ)/ϵ2)O(\log(1/\delta)/\epsilon^2), so the theta bound should be Θ(log⁡(1/δ)/ϵ2)\Theta(\log(1/\delta)/\epsilon^2) (I did not necessarily check all the proof steps).
  4. It is unclear until page 4 as to what a pilot matrix is. Perhaps this needs to be stated earlier in the paper. There is some statement about it in line 79, but it is not clear at all. So in section 3.1, when the authors talk about matrix BB, we don’t know what this matrix is. In line 215, equation 15 it becomes clear that BB is nothing but a one step lanczos approximation.
  5. Perhaps the biggest weakness of this work is, given the assumptions around the noise in the oracle, the results in this work seem pretty straightforward adaptation of other works on trace approximation. Furthermore, the experiment regimes are on real world matrices, where corruption however little is extremely rare, leading to an almost always a reliably noiseless oracle. As such the applications domains are not really convincing.
Questions for authors

Please check the weaknesses section. Also:

  1. What do the authors mean by “a known uniform second-moment bound supplies the noise envelope for our accuracy guarantees”? Bernstein and similar bounds don't assume uniform distribution.
  2. I am confused about Lemma 4. Aren’t these results already known in matvec communities, especially when considering literature around Krylov or other subspace approximation methods?
  3. In section 3.3, the authors state an alternative representation of τ\tau. This looks to a Chebyshev polynomial and perhaps an analysis in this direction could have been useful.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.