We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude αi of the difference between the elements at positions i and i−1 is small. Recent work on implicit trace estimation shows that when αt is small, reusing queries to past sequence elements can reduce the overall cost [Dharangutte & Musco, NeurIPS2021; Woodruff et al., NeurIPS2022]. We introduce a framework generalizing this to a variety of linear and nonlinear functions on diverse vector spaces, obtaining novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and a boundary value problem from partial differential equations~(PDEs). Furthermore, we develop a novel algorithm for use with this framework that locally scales the estimation budget with αt, obtaining sharper path-length-style variation bounds of form O(∑i=1mαi) on the cost of estimating a sequence of length m. This improves upon the previous implicit trace estimation bound of O(m⋅maxiαi) [Dharangutte & Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case αi and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on αi, we show in certain cases how the changes can be estimated on-the-fly with (nearly) no added cost. In summary, our framework makes the sequential approximation toolkit general-purpose and adaptive while improving upon state-of-the-art-guarantees for dynamic 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
Sequence prediction methods for linear dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows linearly with the hidden dimension of the underlying generative model. While many methods have been developed to address this regime with varying success, we show that simply using the second-order Vovk-Azoury-Warmuth (VAW) algorithm to learn a short autoregressive-with-inputs (ARX) model achieves astoundingly strong results: for bounded sequential data from a marginally-stable linear dynamical system with spectra in the complex disk except for angular wedge of width δ around the negative real axis, this algorithm achieves dimension-free regret O(δ−4log2T). These bounds are state-of-the-art to our knowledge. The key components for our result come from 1) using the theory of ``Universal Sequence Preconditioning'' (USP) \cite{marsdenuniversal} to prove the existence of an optimal setting of autoregressive coefficients, 2) the application of VAW which takes better advantage of the memory compression provided by USP, and 3) the analysis of Faber polynomials on circular sectors to extend these results to systems with complex spectra.
In this work, we revisit the problem of active sequential prediction-powered mean estimation, where at each round one must decide the query probability of the ground-truth label upon observing the covariates of a sample. Furthermore, if the label is not queried, the prediction from a machine learning model is used instead. Prior work proposed an elegant scheme that determines the query probability by combining an uncertainty-based suggestion with a constant probability that encodes a soft constraint on the query probability. We explored different values of the mixing parameter and observed an intriguing empirical pattern: the smallest confidence width tends to occur when the weight on the constant probability is close to one, thereby reducing the influence of the uncertainty-based component. Motivated by this observation, we develop a non-asymptotic analysis of the estimator and establish a data-dependent bound on its confidence interval. Our analysis further suggests that when a no-regret learning approach is used to determine the query probability and control this bound, the query probability converges to the constraint of the max value of the query probability when it is chosen obliviously to the current covariates. We also conduct simulations that corroborate these theoretical findings.