- 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 , 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
-
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?
-
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.
-
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?
-
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.
-
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?