- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the problem of sequentially estimating properties of slowly varying sequences. The authors propose AdaDeltaShift, which adjusts the estimation budget according to local changes in the sequence, improving the query complexity from a dependence on the maximum step size to the cumulative local variation. The framework is also extended to unknown step sizes through an additional norm estimator. Theoretical results are provided for several applications, including matrix trace estimation, spectral density estimation, function integration, and certain PDE problems. Experiments on synthetic matrix sequences and neural network Hessians demonstrate improved estimation efficiency.
Critical strengths
The paper makes a clear theoretical contribution. Replacing the dependence on the maximum step size with cumulative local variation provides a meaningful improvement over the fixed-budget approach, particularly for sequences with occasional large changes. The extension to unknown step sizes is also valuable, as these quantities are often unavailable in practice. I find the general framework based on norm-concentrated estimators interesting, and the applications to different estimation problems further illustrate its potential usefulness. The theoretical analysis is generally convincing, and the experiments provide encouraging evidence of reduced query costs without a substantial loss in accuracy.
Critical weaknesses
-
Theorem 2 provides a way to estimate local changes online, which is an important contribution. However, it is not sufficiently clear whether the experiments actually use this mechanism or rely on known step sizes. In particular, for Hessian trace estimation, the cost of obtaining or estimating the local Frobenius differences should be included when assessing the overall efficiency. A more direct evaluation of the unknown-step-size setting would strengthen the practical significance of the results.
-
The experimental validation is somewhat limited compared with the scope of the theoretical framework. Although the paper develops results for matrix powers, spectral densities, function integration, and PDE-related problems, the experiments mainly focus on trace estimation. Moreover, the tested sequences contain occasional large changes, where the proposed adaptive allocation is expected to be particularly effective. Results under more general variation patterns would be useful.
Questions for authors
-
Could the authors clarify whether the experiments use the online step-size estimation mechanism developed in Theorem 2? If so, are the additional queries for estimating the local changes included in the reported computational costs? If not, how would these costs affect the observed efficiency gains?
-
Could the authors provide additional evidence for the effectiveness of the framework beyond dynamic trace estimation, or under different sequence variation patterns? This would help assess how broadly the theoretical improvements translate into practical gains.
2 comments
Follow up to reviewer
Dear Reviewer,
As the public discussion period is coming to a close tomorrow, we wanted to follow up as to whether you had any remaining concerns that we could address.
Many thanks, The authors
We thank the reviewer for their careful reading and positive assessment of our work. We are glad that they recognize the improved bounds achieved by our adaptive query budget. In particular, we are pleased that they appreciate the extension to unknown step sizes and the general applicability of our framework, which we hoped to convey as one of the main messages of the paper. We now address the weaknesses and questions raised.
W1/Q1: All step sizes in our experiments, including those for Hessian trace estimation, were unknown. We estimated them using the auto-concentration technique described in the paper; for trace estimation, this uses the identity ∥A∥F2=tr(A⊤A). The cost of norm estimation, including estimating the local Frobenius differences in the Hessian experiments, is already included in the query totals shown in the plots. Thus, the reported efficiency gains account for this additional cost. We have updated the paper to be more clear about this point.
W2/Q2: We have added experiments on SGD trajectories and on estimating the trace of the squared Hessian, testing a different variation pattern and our matrix-power extension, respectively. Both show comparable errors with substantially fewer queries. The SGD/SGDR comparison and a new damping/query-budget ablation appear in Section 5, while the squared-Hessian experiment appears in the appendix.