acceptodds
Under review as a conference paper at ICLR 2027

Dynamic estimation of slowly varying sequences

Abstract

We consider the problem of sequentially approximating a target function of each element in a slowly-varying sequence, i.e. one where the magnitude of the difference between the elements at positions and , measured in an appropriate norm, is small. Recent work on implicit trace estimation shows that when is small in Frobenius norm, reusing queries to past sequence elements can reduce the overall cost (Dharangutte and Musco, 2021; Woodruff et al., 2022). We introduce a framework that generalizes this approach to linear and nonlinear functions on normed vector spaces, obtaining sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and certain boundary value problems from partial differential equations (PDEs). Furthermore, we develop an algorithm that locally scales the estimation budget with , obtaining sharper path-length-style variation bounds of form on the cost of estimating a sequence of length to accuracy . This improves upon the earlier implicit trace estimation dependence on (Dharangutte and Musco, 2021), which results from fixing the query budget using the worst-case step size and is thus inefficient for stable sequences with rare bursts. Furthermore, while prior theoretical guarantees assume a known bound on the step sizes, we show in certain cases how to estimate them on the fly with (nearly) no added cost. Lastly, we complement our theoretical results with experiments demonstrating improved accuracy–cost trade-offs over prior baselines on trace estimation and Hessian tracking. In summary, our framework makes sequential approximation general-purpose and adaptive while sharpening state-of-the-art guarantees for dynamic trace estimation.

Primary area:
learning theory
Keywords:
Dynamic estimation, randomized numerical linear algebra, adaptive, trace estimation, hessian, spectral density estimation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_DE2jOpenReview ↗
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
  1. 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.

  2. 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
  1. 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?

  2. 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

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)\|A\|_F^2 = \operatorname{tr}(A^\top 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.

AuthorsOpenReview ↗

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

Reviewer_Nw7JOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the problem of estimating properties of systems consisting of mm elements of a vector space where the distance between consecutive elements i−1i-1 and ii is αi\alpha_i. To achieve this, this paper assumes access to a linear estimator that has sub-exponential concentration around its target property for every element of the vector space, with concentration parameters that scale with each element’s norm. To do this, the authors first introduce a randomized estimator that is norm concentrated with power p>0p>0, i.e., a randomized variable which grows sub-exponentially for all vectors in the associated vector space (which also has bounded parameters, a generalization of a similar property from DM21). This estimator allows the authors to write AdaDeltaShift, a meta-algorithm that can approximate target properties of the sequence of vectors. It also adjusts budget dynamically based on αi\alpha_i, leading to a tighter cost estimation (trace norm of α\alpha) leading to improved query complexity as compared to DM21. Furthermore, using auto-concentrated property, with unknown step sizes in AdaDeltaShift, Theorem 2 provides for guarantees on its dynamic sample complexity. The authors then apply AdaDeltaShift to several problems including dynamic traces of matrix powers, SDE, and dynamic dirichlet estimation.

Critical strengths

This paper studies the problem of estimating several properties of a set of vectors which are varying with time. It extends prior work by identifying properties like norm-concentrated estimator properties and auto-concentrated property of estimators, that help us design the AdaDeltaShift algorithm that can approximate various properties dynamically using improved sample complexity as compared to DM21.

Critical weaknesses
  1. The paper states “we complement our theoretical results with experiments”. However, much of the experiments are pushed to the appendices. I believe that to claim that theoretical guarantees are backed by experiments, a little bit more exposition in the main text would be warranted.
  2. WZZ22 succeeds the work of DM21, however most of the discussions in this paper seems geared towards the bounds in DM21. I understand the premise that AdaDeltaShift is meant to succeed DeltaShift, but the comparisons should be to the state-of-the-art.
  3. I fail to understand the premise of having a meta-algorithm that in principle will have worse bounds as compared to the state-of-the-art algorithms. If such a meta-algorithm can give useful insights that can help in improving the best known bounds, they may perhaps be useful. But unfortunately, I didn't observe such a direction in almost all of the applications noted.
Questions for authors

Please see weaknesses. Also:

  1. For SDE, the work of CTU21 has been succeeded by several works including KPM, and Lanczos Quadrature (SLQ specifically) method. Does AdaDelta shift give any non-trivial bounds for those methods?
  2. What is the baseline for Figures 2-4?
4 comments

We thank the reviewer for their review and suggestions for improving our work. Below, we hope to address the concerns and questions raised.

W1: Our original submission summarized the experimental findings in Section 5, with detailed results deferred to the appendix due to space constraints. Using the extra page available now, we have expanded Section 5 with a new SGD experiment alongside the existing SGDR comparison, and a new ablation isolating adaptive damping and query allocation, together with a discussion of their results. We have also added an experiment estimating the trace of the squared Hessian in the appendix, providing further evidence for the matrix-power extension.

W2: DM21 and WZZ22 have asymptotically equivalent guarantees in the setting we target, and thus our comparison is already to the state-of-the-art. In particular, while WZZ22 also studies the dynamic trace problem with matrix-vector access, its main improvement over DM21 is for the nuclear-norm case, whereas our paper is focused on the Frobenius norm. For the Frobenius norm, WZZ22 gives the same exact bounds as in DM21, and in particular, WZZ22 also has a m⋅max⁡iαi/ϵ2m \cdot \max_i \alpha_i / \epsilon^2, where max⁡iαi\max_i \alpha_i is the largest step size, exactly as in DM21 (see Theorem B.2 in the arxiv version of WZZ22 https://arxiv.org/abs/2209.15219). Thus, they are both state-of-the-art for the Frobenius norm. We have updated the related work to clarify the relationship between our work, DM21, and WZZ22.

W3: We respectfully but strongly disagree with this negative view of meta-algorithms, which have been a core component of theory-building in CS; examples such as multiplicative weights [AHK12] and sum-of-squares [BS14] are widely cited and have led to a significant amount of subsequent research. The point of meta-algorithms is not necessarily to get the best bound for a specific problem but to identify the crucial components and assumptions underlying an approach; this (1) drives greater understanding of the original problem and (2) enables new connections to seemingly unrelated problems. As frontier LLMs become more and more capable of generating state-of-the-art theoretical guarantees, research that increases understanding and connections will become more valuable.

Our submission achieves both of these meta-algorithmic goals: we identify a crucial assumption (norm-concentration) underlying dynamic estimation, which (1) drives greater understanding (as evidenced by our introduction of the auto-concentration property for adapting to unknown local changes, which we would not have discovered otherwise) and (2) enables new connections (as evidenced by our new algorithms for dynamic spectral density estimation and function integral approximation).

Furthermore, in the only application for which there is prior work to improve upon (dynamic trace estimation), our meta-algorithm does “give useful insights that can help in improving the best known bounds”: our dynamic trace estimation result (Corollary 3) improves directly upon DM21, both by replacing their mmax⁡iαim\max_i\alpha_i by the sharper ∑iαi\sum_i\alpha_i and by removing their assumption that the step-sizes αi\alpha_i are known. These improvements are driven entirely by the norm-concentration and auto-concentration assumptions underlying our meta-algorithm. As for the other applications, since they did not have prior dynamic estimation work, it is unreasonable to expect an improvement over existing art.

Q1: Thank you for the question. Yes, our framework also easily extends to the more recent Chebyshev polynomial based approach of Braverman, Krishnan, and Musco (STOC ‘22) for SDE. At a high level, this is because for symmetric matrices with spectra in [−1,1][-1,1], the degree-kk Chebyshev polynomial TkT_k satisfies ∥Tk(A)−Tk(B)∥F≤k2∥A−B∥F\|T_k(A)-T_k(B)\|_F\le k^2\|A-B\|_F. Thus, if a sequence of matrices AiA_i is slowly varying, then so is the sequence Tk(Ai)T_k(A_i), up to a k2k^2 factor. We have added appendix Section B.1 with the details; please see Corollary 10 there for the formal result. Extending AdaDeltaShift to SLQ may be less straightforward but is an interesting direction for future work.

Q2: As mentioned in Section 5 of the main body, the baseline is the DeltaShift algorithm of DM21. We have updated the text to make this more clear.

References:

[AHK12] Arora, Hazan, Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing 8, 2012.

[BS14] Barak, Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. Proceedings of the ICM, 2014.

AuthorsOpenReview ↗

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

Reviewer_Nw7JOpenReview ↗

response to rebuttal

We thank you for you detailed response and apologize for the delay in responding to your rebuttal.

W1 is resolved. I also apologize for missing the equivalence of WZZ22 and DM21, and that indeed the authors are correct here.

Regarding W3 -- I did not mean to portray meta-algorithms in negative light. What I really wanted to understand here is how this helps when compared to the state of the art methods the algorithm applies to. Specifically, the authors are correct in stating that one goal of meta-algorithms is to find avenues of cross pollination of ideas across multiple areas of areas. However, if the algorithm indeed performs worse when compared to other algorithms, it kind of defeats the purpose of the work. On this, the trace-estimation result addresses that concern in part, and Appendix B.2 on SDE of the updated draft helps strengthen this claim! In fact, it is shown that if matrices change slowly, the bound here can be better than Braverman et al., 2022.

In the light of these discussions and updates to the paper, I am willing to increase my score.

Thank you for engaging with our rebuttal and increasing your score. We appreciate your thoughtful feedback, which helped improve the paper.

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

This paper presents a framework for dynamically estimating linear functionals over slowly varying sequences. Its algorithm adjusts the damping factor and query budget according to local changes and provides estimation guarantees when step sizes are known. For problems with a suitable squared-norm estimator, it also handles unknown step sizes with simultaneous high-probability guarantees. The paper develops theoretical applications to matrix powers, spectral density estimation, and Monte Carlo integration. The problem is clearly defined, and the main analysis is well presented. Overall, the reviewer views the work positively.

Critical strengths
  • The adaptive query budget yields a stronger path-length-dependent bound than the worst-case step-size bound used for the baseline, through a relatively simple modification.
  • The framework applies to several estimation problems, suggesting value beyond dynamic trace estimation.
Critical weaknesses
  • The experiments do not make the end-to-end cost of the unknown-step algorithm clear. Please state whether step sizes are supplied or estimated, and include the cost of norm estimation in the reported query totals.
  • The comparison with DeltaShift does not isolate the contribution of each adaptive component. Since the earlier parameter-free method already adapts damping, an ablation comparing fixed and adaptive damping with fixed and adaptive query budgets would clarify the source of the gains.
  • Publicly accessible experiment code and configurations would improve reproducibility and help others apply the framework.
Questions for authors

See Weaknesses

3 comments

We thank the reviewer for their careful reading and positive assessment of our work. We are glad that they find the exposition clear and highlight the improved bounds achieved by our adaptive query budget. In particular, we are pleased that they appreciate the simplicity and general applicability of our framework, which we hoped to convey as one of the main messages of the paper. We now address the weaknesses raised.

W1: All step sizes in our experiments were unknown. We estimated them using the auto-concentration technique described in Section 2.2 of the paper. The cost of norm estimation is already included in the query totals shown in the plots. We have updated the paper to be more clear about this point.

W2: We agree that this ablation will help isolate the contribution of each adaptive component (thanks for pointing this out!). Towards this, we have added an ablation comparing all four combinations of fixed and adaptive damping and query budgets on a bursty synthetic matrix sequence (Figure 2). At the same total query budget, using both adaptive components yields substantially lower error than using either alone.

W3: We note that the submission already includes the experimental code in the supplementary material, which is publicly available.

Thank you for the response and the revised manuscript. The changes largely address my concerns, so I will keep my positive score.

AuthorsOpenReview ↗

Follow up to reviewer

Thank you!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.