Optimal Query Complexities for Dynamic Trace Estimation
Authors: David Woodruff
Fred Zhang
Qiuyi Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: trace estimation
numerical linear algebra
query complexity lower bound

Abstract: We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly, such as during an optimization process. Specifically, for any $m$ matrices $\mathbf{A}_1,...,\mathbf{A}_m$ with consecutive differences bounded in Schatten-$1$ norm by $\alpha$, we provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $\epsilon$ error with $\delta$ failure probability with an optimal query complexity of $\widetilde{O}(m \alpha\sqrt{\log(1/\delta)}/\epsilon + m\log(1/\delta))$, improving the dependence on both $\alpha$ and $\delta$ from Dharangutte and Musco (NeurIPS, 2021). Our procedure works without additional norm bounds on $\mathbf{A}_i$ and can be generalized to a bound for the $p$-th Schatten norm for $p \in [1,2]$, giving a complexity of $\widetilde{O}(m \alpha(\sqrt{\log(1/\delta)}/\epsilon)^p +m \log(1/\delta))$. By using novel reductions to communication complexity and information-theoretic analyses of Gaussian matrices, we provide matching lower bounds for static and dynamic trace estimation in all relevant parameters, including the failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error {\it even in the static setting}, and (2) are the first unconditional lower bounds for dynamic trace estimation, resolving open questions of prior work.

Optimal Query Complexities for Dynamic Trace Estimation
David Woodruff Carnegie Mellon University dwoodruf@cs, cmu, edu
Fred Zhang UC Berkeley z0@berkeley.co edu
Qiuyi (Richard) Zhang Google Brain qiuyiz@goglle.co com
Abstract
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underly- ing matrix is changing slowly, such during optimization process. Specif- ically, for any m matrices A1, Am with consecutive differences bounded Schatten-1 norm by a, provide novel binary tree summation procedure that simultaneously estimates all m traces up to e error with failure probability with + m log(1/6)), improving
an optimal query complexity of (loga//oo((//)))) the dependence on both a and from Dharangutte and Musco (NeurIPS, 2021). Our procedure works without additional norm bounds on A; and can be gener- alized to a bound for the p-th Schatten norm for p E [1, 2]. giving complexity Omma( (Too/oo//////o (1//(//))//))) + m log(1 (gg(1//0) 16)).. By using novel reductions to commu- analyses of Gaussian matrices, we
nication complexity and information-theoree provide matching lower bounds for static and dynamic trace estimation in all rel- evant parameters, including the failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's 's estimator in the matrix-vector product model with Frobenius norm even in the static setting, and (2) are the first uncon- ditional lower bounds for dynamic trace estimation, resolving open questions of prior work.
Introduction
Implicit matrix trace estimation is ubiquitous in numerical linear algebra and arises naturally in wide range of applications, see, e.g., [25]. In this problem, we are given an oracle which gives us matrix-vector products A.r,, Ar2,, .... Arm for unknown
n square matrix A and queries 21, F'm of our choice, that may be chosen adaptively. In typical applications, one cannot afford compute the diagonal entries of A explicitly, due to being implicitly represented and compu- tational constraints. The goal is to efficiently estimate Tr A using only matrix-vector products.
In machine learning and data science, applications of trace estimation include training Gaussian Processes [8, 11], triangle counting [1]. computing the Estrada Index [10, 9], and studying opti- mization landscapes of deep neural networks from Hessian matrices [12, 26]. In these applications, is common that A is represented implicitly due to its large memory footprint. For example, while it is possible compute Hessian-vector products via Pearlmutter's trick [20], is prohibitive to compute or store the Hessian matrix H, see, e.g.. [12].
Moreover, A may be matrix function f of another matrix B in some applications. Since computing f(B) expensive, is desirable to apply implicit trace estimation. For example, during the training of Gaussian Processes, the marginal log- ligeiiil contains a heavy-computation term, i.c., the log of the determinant of the covariance matrix, log(det(K)), where E Rax= and n is the number of data points. The canonical way of computing log(det: (og(de((K)) is via Cholesky factorization K, which takes (nn3) time. Instead, implicit trace estimation methods provide fast algorithms for
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

approximating (og(det(K)) = E log(A,) = tr(log(K) on large-scale data. Therefore, it is important to understand the fundamental limits of implicit trace estimation as the query complexity, i.e. the minimum number of matrix-vector multiplications required to achieve a desired accuracy and success rate.
Static trace estimation and Hutchinson's method. On the algorithmic side, Hutchinson's method [14] is a simple and widely used method for trace estimation. Let Q [qI,..., be vectors with i.i.d. standard Gaussian or Rademacher random variables. Given matrix-vector multiplication access to A, Hutchinson's 's method estimates tr(A) by
., qe] E Ruxe
1 -i=1 9. Aq; =
q tr(Q" AQ). It is known [2] that the estimator satisfies that for any E, 5 E (0,
Tr S s A|EF, Fr with probability at least 6, provided the number E of queries satisfies 2 C' log(1/6)/e² for some fixed constant C.
For Hutchinson's 's method, there is also previous work which showed for queries of the form x T Ar, ((1//=)) queries are required [21]: however, this does not imply even lower bound for non-adaptive algorithms that use matrix-vector queries. Though stronger algorithmic results and matching lower bounds are known for the important case of PSD matrices in the non-adaptive setting [18, 16], the optimality of Hutchinson's 's estimator as an trace estimator for general square matrices in the matrix- vector product model still remains an open problem. Notably, Hutchinson's method chooses the query vectors non-adaptively and it is furthermore unclear whether adaptivity could help.
More generally, there has been a flurry of recent work that gives trace estimators with o(1/e²) query complexity but with different error guarantee. Specifically, let us consider a Schatten-p norm error guarantee, where the goal is to provide an estimate t such that
Tr A| S =| Alp: with probability at least 8,
where ||
p denotes the Schatten-p norm.
For p 1, a previous work [18] proposes variance-reduced version of Hutchinson's 's method that uses only ((1/E) matrix-vector product queries to achieve a nuclear norm error of e||A|] in con- trast the (11/=²) queries used when the error is in the Frobenius norm. When the matrix is positive semidefinite (PSD), the nuclear norm error is equivalent to a (1 + E) multiplicative approx- imation the trace. Their work, along with subsequent work [16], shows that ((1/s) queries are therefore sufficient and necessary to achieve a (1 + 8) multiplicative trace approximation in this set- ting. While this line of work mainly focuses on PSD matrices and nuclear norm error, we consider trace estimation on general square matrices with Schatten-p norm error for any E [1.2].
Furthermore, note that the variance-reduced Hutchinson's 's method splits the queries between approximating the top O(1/E) eigenvalues, i.c., by computing a rank-O(1/E) approximation to A, and performing Hutchinsons's method the remainder. Due the low rank approxima- tion subroutine, the query complexity's s dependence on the failure probability is more concretely O( ((oTo + log(1/o)) for additive el| A|| error. The additive log(1/8) rate is shown to be necessary when non-adaptive queries are used, but it is an open problem whether adaptive queries can remove the additive log(1/)) term for trace estimation with Schatten-p norm error [16].
This motivates the natural question:
Question I: Is Hutchinson's 's method optimal in terms of & and 8 for static trace estimation of general square matrices, even when adaptivity is allowed? How do we generalize Hutchinson's 's method for error in general Schatten-p p norms?
Dynamic trace estimation. In various applications the input matrix is not fixed. For example, during model training, we need to estimate the trace of dynamically changing Hessian matrix with respect to some loss function. One may assume that the change at each step is not very large. Motivated by such a scenario, a recent work by Dharangutte and Musco [6] studies dynamic trace estimation.
Formally, letp E [1,2] and A,, A.,..., Am be n x matrices in stream such that (1) ||A S for all i > 1, where Ip denotes the Schatten-p norm, and (2) A - A:llp S a < for all
i S 1. The goal is output sequence of estimates ",. Imm such that for each E [m].
|t: T--Th Tr A,l S with probability at least 1 6,
(3)

---

Upper Bounds
Prior Work
Query Complexity
Matrix Type
Failure Rate
Algorithm Type
12 22
O Ollg((166//"
general square
6
non-adaptive,
Ooy /
log(1/8))
PSD
adaptive. p
(1/0)/e)
PSD
non-udaptive, p
[16]
Ol (lyoog(1/8)) + log( (188)
PSD
non-adaptive, p =
This work
Olly (og(1/))//)) (og(1/
PSD
non-adaptive, general
Lower Bounds (Adaptive)
[18]
10(1/(6 llg((//)))
general square. bit
constant general square, bit
adaptive. p
This work?
6
adaptive, general
(0+ (og(1/8)
This work
? [(Voog(L/5)///
general square, ram
8 adaptive, general
Lower Bounds (Non-Adaptive)
[18]
12(1/e)
constant PSD, ram
non-adaptive, p
[16]
O(y log(1/6]/==
log
1/51
PSD, ram
5
non-adaptive, p
This work"
Ω log"/ 22 (1/6)/(=*(b + log (1/=)))
general square,
non-udaptive, gen-auaativeegnncaal general p
This work
f2 (VVoog(1//0 [V/log(1/0)//}> log(1/6)
178) general square, ram 6
non-udaptive, general
Table I: Upper and lower bounds on the query complexity for static trace estimation. the bit complexity model, each entry of the query vector is specified by bits, and the dependence on b is necessary.
A static upper bound generalizing Hutch++ [18] to Schatten-p norm error (Theorem C.I). 2, An adaptive lower bound via communication complexity of the Gap Equality and Approximate Orthogonality problem (Theorem 4.1,, which combines Theorem D.2 and Theorem D.3, resolving an open problem that (18) queries are required the adaptive setting.
3; An adaptive lower bound via iifformation-thhoreee
analysis of Gaussian Wigner matrices (Theo-
rem 4.2), showing optimal dependence on log(1/6), (1/5).
4, A non-adaptive lower bound via communication complexity of Augmented Indexing (Theo-
rem F.1), optimal in all parameters up to the bit complexity term.
5: A non-adaptive lower bound combining our Theorem 4.2 and the prior result from [16].
via matrix-vector multiplication query access to the first i matrices (A1) Naïvely, one could estimate each Tr A; independently using Hutchinson's 's method. This, however, does not exploit that the changes are bounded at each step. Alternatively, one can rewrite Tr A, as Tr Ai Tr ()) where A, A, A,-1, by lincarity of the trace, and apply Hutchinson's 'ss method on each term. Unfortunately, this scheme suffers from an accumulation of errors over the steps.
The prior work [6] is focused on {1,2} and improves upon the naïve ideas above. For 1, the authors give a method that uses O [m a///e + VT56/e queries. For p 2, they provide an 2 + log llo((1/)) /E") and conditional lower bound
algorithm with query complexity (ma log(1 (1/ showing that this is tight. This leaves open the question:
Can design improved algorithms for dynamic trace estimation under general Schatten norm assumption? Can we prove an unconditionally optimal lower bound?
Question 2:
1.1 Our Results
Our work resolves the proposed questions (nearly) optimally, and we next discuss our main results.
Static trace estimation: For Question we prove query complexity lower bounds for implicit trace estimation in both bit complexity and real RAM models of computation, resolving the open problem of establishing unconditional lower bounds for the optimality of Hutchinson's method even in the adaptive setting.
To so, we provide new reductions from classic communication complexity problems, includ- ing GAP-EQUALITY and APPROXIMATE- ORTHoGONALLtY APPROXIMATE:ORTTIOOOOLLLI lower bounds demonstrate that log(1/)) queries are always needed even with adaptivity and for gen- eral p. there is additional 1/s" dependence. A key idea is communication protocol simulation
to matrix trace estimation. Our main
3

---

using the product of two matrices rather than the sum, as was used in prior work on PSD lower bounds [18].
Theorem 1.1 (Informal; see Theorem 4.1). In the bit complexity model, where each entry of each query vector is specified using b bils,
log(1/6)
Ω
OP log(1/e) + b+ log (1(()/))
number of adaptive queries is necessary to achieve ell All error with probability at least - 8.
When adaptivity is not allowed, we give a stronger lower bound (Theorem F.1) of (110)/221//)/=2) This matches the guarantee of Hutchinson's 's non-adaptive estimator up to a constant factor, for which random sign vectors suffice and one can take b O(1..
We also provide query complexity lower bound in the real RAM model for general Schatten p- norms with p [1,2] by using Gaussian ensembles and controlling the remaining entropy of the distribution conditioned on prior queries. In the special case of p guarantee), our bound again matches the classic Hutchinson's 's method
(i.e., Frobenius norm error
to constant factor for p 2, and an additive log(1/6) factor for p < 2. Note that in the non-adaptive setting, our lower bound in the RAM model can also be improved for p < 2 to include log(1/0)/ log log(1/)) factor. Therefore, this lower bound emphasizes that our dependence on (og(1/6) the e-dependent term tight, even in the adaptive setting.
Theorem 1.2 (Informal; see Theorem 4.2). In the real RAM model, where the queries are real- valued, for sufficiently small and any E [1, 2). & ((V[oog(1/)) p) necessary to achieve a|| Alpp error with probability least 6.
number of adaptive queries
On the algorithmic front, give matching upper bound for static trace estimation for general Schatten-p norm error for E [1,2]. The argument requires a careful balancing of the e and parameters in the low rank approximation of the Hutch++ procedure from [18]. See Theorem C.I for a full statement.
Dynamic trace estimation:
To answer Question 2, we first give an improved algorithm for dy- namic trace estimation that uses a binary tree-based decomposition to estimate all matrix traces with only small logarithmic overhead. The algorithm improves upon the previous work [6] and gets an optimal dependence on 0 < a, < 1, up to logarithmic factors. Specifically, for p 1, the prior work gives method that uses O (mva//5
queries for small e, while our algorithm gives an
improved Omma / log(1/5)/e bound with linear dependence a and square root dependence on log(1/8). For p 2, our algorithm matches the query complexity of O(ma by previous work. Furthermore, our algorithm works under general Schatten p-norm assumption for any p E 2]:
given
Theorem 1.3 (Informal; see Theorem 3.1 and Theorem C.2). For any p E [1,2]. there is a dynamic trace estimation algorithm that achieves error and failure 8 at each step. The algoritim uses a total of
ō + 11
(( (vlog(1/(ad))/})
P + +m log(L1((())))
(4)
matrix-vector product queries. Furthermore, for 1, can be improved to
(ma 1) (Vlog(1/(a0))/) (V)(())((())((0)))
+ mommi,,,,// (og(1)(0))((
(5)
Furthermore, since our algorithm avoids the variance reduction technique from [6], we may relax the assumptions of dynamic trace estimation and require only the first matrix to have norm [A1]] S 1, instead of asking the entire sequence A, to be bounded such way. While the norm bound on all A, is crucial for the algorithm in [6] (rerunning the analysis naïvely would give worse query complexity of ( a3 /E)). our tree-based algorithm achieves a nearly optimal query complexity even when the norm of A; grows, and we suffer only a log overhead in that case. Moreover, in our experiments, we find that our algorithm significantly outperforms previous algorithms on real and synthetic datasets. See Section 6 for our experimental results.

---

To complement our algorithms, we give unconditional lower bounds showing that our algorithm is nearly optimal. Our lower bounds rely on a reduction from dynamic trace estimation static matrix trace estimation from [6] and make use of our new lower bounds in the static setting. In particular, the reduction shows that if for a fixed set of parameters E, p. a static trace estimation scheme requires (2()) queries, then ((mor) queries are necessary for any dynamic algorithm. Combining this observation with our static trace estimation lower bounds, we get:
Theorem 1.4 (Informal; see Theorem 5.2 and Theorem 5.3). For any p = (1, our algorithm attains the optimal query complexity, up to bit complexity and logarithmic terms.
More specifically, we prove lower bounds that match the first term our upper bound (4) for all p E [1. 2J. For 1, we give lower bound (Theorem 5.4) matching the the second term in (5) as well, showing that the m (log((1) (1))) additive dependence is necessary.
For p 2, the prior work [6] gives upper bound of ( log(1/6)/e² log(1/8)/e2). Our lower bounds are unconditional and show that the first term tight. Moreover, the second term necessary due to the static lower bound when
1. This result is not contradicted by the claim of Theorem 5.4, In particular, when a 2 E², Theorem 5.4 is weaker than the {ma log(1 (18)/ /e) ee)) lower bound; and when < e², the construction by itself requires e/a update steps to change the trace by E, which leads to a lower bound (mma log(1/))/e) again weaker than 52 log (l))
2 Preliminaries
matrix A E RR is symmetric positive semi-defnite (PSD) if is real, symmetric and has non- negative eigenvalues. Hence, x' Ar 2 O for all x E IR" Let tr = > 2i-1 A;; denote the trace of
A. Let ||A|]]=
(E= E 1/2 denote the Frobenius norm and ||Allop / ||Av||2
denote the operator norm of A. We let || ( of) be the Schatten-p norm, where a; the singular values of A. Two special cases are the Frobenius norm, which equals the Schatten-2 norm A F ||) and the nuclear norm, equals the Schatten-1 norm (|A|] ||Al]]).
3 Algorithm for Dynamic Trace Estimation
We give algorithm for dynamic trace estimation under general Schatten-p assumption, for p E [1, 2]. For p = 1, our algorithm provides an improved guarantee upon the DeltaShift++ procedure from [6]. In later section we complement the result by showing that is indeed near- optimal. Specifically, we give an algorithm that achieves the following guarantees:
Theorem 3.1 (Improved dynamic trace estimation). Let A2, , Am be n x n matrices such that (1) ||A.l+ < 1 for all i, and (2) ||A - Asll+ for all S m 1. Given matrix-vector multiplication access to the matrices, a failure rate > O and ervor bound E, there is an algorithm that outputs sequence of esstmaate I1," Im such that for each i [m].
It: Tr A, S e, with probability at least 1 8.
(6)
The algorithm uses total of
o (1ma+ 1) (1/a) looooo/o(((((/))))/ min(L,a//)log((/((())
matrix-vector multiplication queries A1, A2, Am.
Compared with DeltaShift++ in [6], this guarantee provides an exponential improvement in 8 and polynomial improvement in a for p of while maintaining the optimal dependence on and
3.1 Algorithm
We now describe our algorithm. The first idea is to partition the m updates into groups of size s [1/(2o]]. Each group will be treated independently, and we will use
(108 (10g(11/a) (oog[\\a))
log(L/(a0)).
(8)
5

---

queries on each group. This leads to our claimed query complexity, as there are ((ma) groups. Note that if a < E, since [Tr -A - | Ai- a, the trace can change by at most an additive a, so we can simply ignore every subsequence of length e/a. Therefore, we only need to apply our estimators to ma/e matrices.
Without loss of generality, consider a group of matrices AI.... A1/2a- As the first step, we estimate Tr(A, A)-1) for each j 2 by using the Hutch++ static trace estimator [18] as a black box. Then, for each even integer j 2k (for an integer 2 S S s/2), also estimate Tr(A2x A2(k-1) in the same way. More generally, for each integer k, for 0 S & < log2 use Hutch++ to approximate Tr (Age; (k-))) We view this scheme as a binary tree: the bottom level consists of leaves corresponding to the trace difference of neighboring matrices, and nodes at level correspond the trace difference of matrices that are 2 apart in their indices.
To output an estimate of Tr A,, we will write i in its binary representation and approximate it by (r(A)) plus sequence of (log(1/a)) differences, at most for each level in the binary tree. By setting the success rates and errors bounds at each level carefully, we can achieve the desired emror guarantee of Equation (6).
To formalize the construction, we first eite the following guarantee of the Hutch++ algorithm:
Lemma 3.2 (Hutch++, nuclear norm, Theorem 5 of [18]). The Hutch+ estimator uses
N = (V)) + log(1/8"))
matrix-vector multiplication queries such that given any square matrix A and parameters e',8', with probability at least 1 - 8", the algorithm's 's output satisfies
- TT S VE A - A1/1/e S |
Let flutch+((AEe (A, 8') denote the output of Hutch++ on matrix A with parameters c', It will be invoked with different parameters different levels of the binary tree construction. A description of the algorithm is given by the pseudocode Algorithm 1, with helper function Algorithm 2.
For simplicity of analysis, note that since we add dummy matrices (say, extra copies of A assume that each group has size exactly 8 = [1/(2a)] and a power of two. This blows up the total number of matrices by at most a constant factor.
Algorithm 1:
Improved Dynamic Trace Estimation
Input: : sequence square matrices (A.) E RRann failure rate 8, error bound g
Ouput: Trace estimate 4 for each matrix
Partition the matrices into groups of size [1/(2a)].
For every 2 O and i {0, 10. g-th group.
1}. let A = Age-it1 denote the i-th matrix in the
3 for each group (0)
A 8-1 independently do Let to (A e222,
for each level f.rrom 0 to log, do
gap=2 = 2
for k from to (s 1)/ gap do
Compute t4, = Hutch++ (Ak-gap gs. ='(),,"). with e'( (2 log, 8) and 8' ad.
Output fgsti+1 to + SUMTREE log2 1, for each i E [0, 1).
3.2 Analysis
The analysis of the algorithm rather lengthy and is delayed to Appendix C.I. addition, we give a general analysis of the algorithm under Schatten-p norm assumption and the specific im- proved bounds for p = in Appendix C.2 and show how relax the bounded norm assumption in Appendix C.3.

---

Algorithm 2: SUMTREE: Helper Function for Tracing the Binary Tree
Input: Indices J, level f, binary tree node values \
gap 2
if, j S then
[ return O.
if gap then return tz
j - gap then
return /g/(0_1)//aap + SUMTREE(i gap,j. 1,t).
else
return SUMTREE(i, gap).
4
Lower Bounds for Adaptive Trace Estimation
In this section, we provide (nearly) optimal lower bounds for trace estimation with adaptive matrix- vector multiplication queries, under general square matrices and Schatten-p norm error.
4.1 Adaptive Lower Bound, Bit Complexity
First, we show two separate lower bounds under bit complexity model, both proven via reductions from communication complexity problems. One shows an 2(1/E") lower bound (Theorem D.2) and the other ((log(1/0)) (Theorem D.3), up bit complexity terms. Combined together, they yield:
Theorem 4.1 (Adaptive query lower bound, bit complexity). Any algorithm that accesses a square matrix A via matrix-vector multiplication queries requires at least
Ω ( (<<((=Log((/)) + k log (og((11))
(og(1/8)
le log(L/E))
queries to output an estimate such that with probability at least 1 5, - any [1, 2), where the query vectors may be adaptively chosen with entries specified by k bits.
Tr
E El|Alpp lp. for
The proofs of the theorems can be found in Appendix D.I.
4.2 Adaptive Lower Bound, RAM
Next, we prove a tight lower bound under the real RAM model (Theorem 4.2). The bounds hold for any Schatten-p norm eπrrr. Our proof is via information -eetrmttion-thcoretic analysis of random Gaussian matrices and is delayed to Appendix D.2.
Theorem 4.2 (Lower Bound for Any Schatten Norm). For all [1,2]. 8 0 and (o0))) any algorithm that takes in any input matrix A and succeeds with probability at least - in outputting an estimate t such that It [A) S =|[A|>> requires
(18(118)
m = Ω
matrix-vector multiplication queries.
5 Lower Bounds for Dynamic Trace Estimation
Using the query complexity lower bounds for adaptive trace estimation, we can now prove tight lower bounds for dynamic trace estimation. The recent work of Dharangutte and Musco [6] only provides conditional lower bound, assuming that Hutchinson's scheme optimal. We remove this assumption and make the lower bound unconditional. We additionally prove lower bound by constructing an explicit hard instance in the dynamic setting. Our lower bounds hold under general Shatten norm assumption and nearly matches the guarantec of our algorithm.

---

5.1 Lower Bounds via Static-to-Dynamic Reduction
We first show lower bound for dynamic trace estimation under Frobenius norm assumption. This immediately implies that the DeltShift algorithm due to [6] is optimal for = 2.
First, we cite a static-to-dynamic reduction from [6] and its implication. The reduction shows how to solve a static instance using a dynamic trace estimation scheme, and therefore any hardness on the static problem translates to the dynamic setting well. It holds generally for error bound in any Schatten norm For completeness, we give a proof in Appendix E.I.
Lemma 5.1 (Conditional lower bound for dynamic trace estimation [6]). Suppose that any algo- rithm that achieves Equation (2) for static trace estimation must use 12(r) matrix-vector product queries. Then any dynamic trace estimation algorithm requires (romm) matrix-vector product queries under a general Schatten-p norm assumption, when a 1/(m 1).
It follows immediately from this lemma and our adaptive query lower bound (Theorem 4.1):
Theorem 5.2 (Unconditional lower bound for dynamic trace estimation, bit). For all E [1, 2] and e, E (0, 1), any algorithm for dynamic trace estimation under Schatten-p norm assumption must use at least
S2 cmm ( ( log(1/))) + &PP (EP +
log(1/8)
k log log (1)(
malrix-vector multiplication queries, where each entry of the query vectors is specified by k bits.
Combining the same reduction (Theorem D.6) with our previous real RAM lower bound (Theo- rem 4.2) in the static setting gives:
Theorem 5.3 (Unconditional lower bound for dynamic trace estimation, RAM). For all E 21. 5 > 0 and 0 < (log(1/6))1/2-1// any algorithm for dynamic trace estimation under
Schatten-p norm assumption must use at least Q (am (vIog(1/6)/=)) matrix-vector multiplica- tion queries.
5.2 Lower Bound via Explicit Hard Instance
Using the hard instance based on GAP-EQUALITY in the static setting (from the proof of Theo- rem D.3), we give an explicit hardness construction against any dynamic trace estimation scheme. This yields the following lower bound, and its proof is in Appendix E.2.
Theorem 5.4. For all [1,2] and e, 8 E (0. 1/4). any algorithm for dynamic trace estimation under Schatten-p norm assumption must use least
a ( min (1.
log( (1/0)
log log(1/5)
matrix-vector multipiiiionn queries, where each entry of the query vectors is specified by bits.
Experiments
We experimentally validate our algorithmic results. We compare Algorithm 1, with the following procedures on both synthetic and real datasets. More experimental details are in Appendix G.
Hutchinson's: Apply the classic Hutchinson's scheme for each Tr(A,) independently.
DiffSum: Approximate 1 Tr(A,) and each neighboring difference d, Tr(A,)
Tr(A,-1) using Hutchinson's 's independently. Then output t; = t1 + 24
DeltaShift: The main algorithm of [6]. The experiments from [6] demonstrate that
DeltaShift outperforms DiffSum and other Hutchinson- based schemes on various datasets.
Synthetic data. We simulate dynamic trace estimation instance by first generating (symmetric) random matrix A nne and then adding random perturbations over 100 time steps. The details and results are found in Appendix G.I.

---

Average Relative Elror over 100 THAMs
Averago Reluaivee Error over 100 Triass
0.30
0.045
Tree
I J MAMO
0.04
0.025
M (M
M
0.30
W MM
M
Enge
Reletve Erer
0.04
0.52
6.055
10
Stop
Timo Blop
(a) SNAP/NN- GrQC
(b) SNePica-HepTh
Figure 1: ArXiv datasets. Query budget 8, 000. this experiment, the trace values are large, so we measure the performance of the algorithms by their relative error i; Tr A max; Tr A
Average Absolute Enor over 100 trals
Average Absolite Emrr over trats
0.25
110
1000
Detsuur
UV Bux
Klocc 1.
500
Stop
(a) Error over last 900 time steps
(b) Error over entire 1, 0000 time steps
Figure 2: MNIST. Query budget is 50, 000.
Counting triangles. Our first experiment real-world dataset is counting triangles in dy- namic undirected (simple) graphs. Note that the number of triangles in a graph equals 6 Tr A where A is the adjacency matrix of the graph. Thus, triangle counting reduces to trace estimation.
We use two arXiv collaboration networks with 5, 242 and 9, 877 nodes [17].' The nodes represent authors, and edges indicate co-authorships. To simulate real-world scenario, we add a random clique size most 6 to the graph in each step, indicating group researchers jointly publishing paper. We note that our algorithm significantly outperforms other methods (Figure 1).
Neural network weight matrix. We evaluate the performance of the algorithms on sequence of weight matrices of neural network, generated during the training process. In particular, we choose a three-layer neural network with a hidden layer of 100 x 100. We train the network on the MNIST dataset via mini-batch SGD and consider the first 1, 000 steps, when the weights are changing most rapidly. Our algorithm achieves much smaller error than DiffSum and DeltaShift (Figure 2).
'The first is the collaboration network of arXiv General Relativity (ca-Gr GrQe) and the second High Energy Physics Theory (ca-HepTh). Both available at https htttps://sparaee //wpa//epeeeeee/eeeeee tamu, cdu/SNAP.

---

Acknowledgement
Work done while David P. Woodruff and Fred Zhang were Google Research in Pittsburgh.
Fred Zhang is supported by ONR grant
References
[1] Haim Avron. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications, volume 10, page 9, 2010.
[2] Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. ACM, 58(2), 2011.
[3] Kai Bergermann and Martin Stoll. Fast computation of matrix function- centrality mea- sures for layer-coupled multiplex networks. Physical Review E, 105(3);034305, 2022.
[4] Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), 1998.
[5] Amit Chakrabarti, Ranganath Kondapally, and Zhenghui Wang. Information complexity versus corruption and applications to orthogonality and gap-hamming. In Approximation, Random- izution, and Combinatorial Optimization (APPROX-RANDOM), 2012.
[6] Prathamesh Dharangutte and Christopher Musco. Dynamic trace estimation. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[7] Edoardo Di Napoli, Eric Polizzi, and Yousef Saad. Efficient estimation of eigenvalue counts an interval. Numerical Linear Algebra with Applications, 23(4):674 2016.
[8] Kun Dong, David Eriksson, Hannes Nickisch, David Bindel, and Andrew G Wilson. Scalable log determinants for gaussian process kernel learning. In Advances Neural Information Processing Systems (NeurIPS), 2017.
[9] Ernesto Estrada. Characterization of 3d molecular structure. Chemical Physics Letters, 319(5- 6):713-718, 2000.
[10] Ernesto Estrada and Naomichi Hatano. Communicability complex networks. Phyy. Rev. E, 77:036111, 2008.
[11] Jack K. Fitzsimons, Diego Granziol, Kurt Cutajar, Michael A. Osborne, Maurizio Filippone, and Stephen J. Roberts. Entropic trace estimates for log determinants. In ECMI/PKDD, 2017.
[12] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net opti- mization via hessian eigenvalue density. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[13] Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin. Approximating the spectral sums of large-scale matrices using chebyshev approximations. SIAM Journal on Scientific Computing, 39, 06 2016.
[14] Michael Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in 1076, 1989.
and Computation, 18(3): 1059-
[15] Thathachar S Jayram and David P Woodruff. Optimal bounds for jonjoooonn-inddessraaas trans- forms and streaming problems with subconstant error. ACM Transactions on Algorithms (TALG), 9(3):1117, 2013.
[16] Shuli Jiang, Hai Pham, David Woodruff, and Richard Zhang. Optimal sketching for trace estimation. Advances in Neural Information Processing Systems (NeurIPS), 2021.
10

---

[17] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(I), 2007.
[18] Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity Algorithms (SOSA), 2021.
[19] Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David Woodruff. Spectrum approximation beyond fast matrix multiplication: Algorithms and hard- ness. In 9th Innovations in Theoretical Computer Science Conference (ITCS)), 2018.
[20] Barak Pearlmutter. Fast exact multiplication by the hessian, Neural Computation, 6:147- 160, 1994.
[21] Farbod Koosta-Khorassan and Uri Ascher. Improved bounds on sample size for implicit matrix trace estimators. Foundations of Computational Mathematicx, 15(5):1187-12) 2015.
[22] Farbod trace estimators. Found. Comput. Math., 15(5):1187-121,, October 2015.
and Uri Ascher. Improved bounds on sample size for implicit matrix
[23] Mark Rudelson and Roman Vershynin. Non-asympiotic theory of random matrices: extreme singular values. Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pages 1576-1602. World Scientific, 2010.
[24] Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. Tight query complexity lower bounds for pca via finite sample deformed wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
[25] Shashanka Ubaru and Yousef Saad. Applications of trace estimation techniques. In High Performance Computing in Science and Engineering, 2018.
[26] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE International Conference on Big Data (BigData), 2020.
[27] Yuchen Zhang, Martin Wainwright, and Michael Jordan. Distributed estimation of generalized matrix rank: Efficient algorithms and lower bounds. In International Conference on Machine Learning (ICML), 2015. 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
11

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're re using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "iFAR-RsSA3w", "reviewer": "Reviewer_dsKZ", "summary": "The paper provides query complexity results for $\\epsilon$-trace estimation, with error being multiplicative in some specified matrix norm, under the matrix-vector product oracle in a variety of settings: static/dynamic, adaptive/non-adaptive (the former uses samples that depend on previous ones and therefore, by definition, is sequential; the latter doesn't, and is therefore amenable to parallelization.), error measured in $p$-norm for various $p$, PSD/general square matrices, and combinations of all these. Some specific contributions include \n\n1. improved bounds of the classical Hutch++ algorithm for PSD matrices in general $p$-norm error (previously known only for $p\\in \\\\{1, 2\\\\}$), \n\n2. lower bounds for adaptive and non-adaptive trace estimation in general $p$-norm error (previously known only for $p\\in \\\\{1, 2\\\\}$) and, along the way, settling the question of optimality of Hutch++ for $p=2$, \n\n3. (most importantly) a dynamic trace estimation algorithm that improves upon the query complexity for $1$-norm error by Dharangutte-Musco, matches their result for $2$-norm error, and provides a bound (previously unknown) in the range $p \\in [1, 2]$. \n\nThe lower bounds are proven by reduction to problems in communication complexity, while the dynamic trace estimation improvement is obtained by a binary tree based partition technique combined with the idea of applying Hutch++ to the changes in the input matrices in a specific partition. ", "questions": "N/A ", "limitations": "The authors are very clear on what models of computation they use and what regimes their results hold in. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\nThis is a very strong paper. All the main technical contributions (listed in the previous field) are strong in their own right: one, giving an improved analysis of an existing algorithm, second, showing that this is the best possible query complexity for certain settings of this problem, and third, providing results for previously unknown regimes. Trace estimation --- moreso dynamic trace estimation --- is a task that shows up as a subroutine in several fundamental machine learning algorithms. Therefore, this paper scores highly on significance and originality.\n\nThe paper scores highly on clarity: I particularly liked the contextualization of the results in Section 1. I think the algorithm in Section 3.1 could be explained a bit better: in the main body, this currently reads quite terse. (The results on lower bounds could be moved to the Appendix entirely, to fit the page limit, since merely restating the previously mentioned lower bounds formally, but without proofs, doesn't add much value for the reader.)  I also appreciated the clear specification of the computation model (matrix-vector product) along with its justification, the detailed motivation behind the need to study fast trace estimation (through the example of gaussian processes), and the table on related work: to me, this feels like a paper that could easily welcome a new reader into this topic of research. \n\nTo summarize, I appreciate the technical contributions and think that the problem is well-motivated. I currently rate this paper 7/10 (GOOD PAPER, ACCEPT). \n\n**Weaknesses** \n\nI think Section 3.1's algorithm could be explained better. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gXoE5wIgIgW", "reviewer": "Reviewer_5gFw", "summary": "Estimating the trace of matrices is an important problem in numerical linear algebra. This paper studies the trace estimation problem in a dynamic setting, i.e., we are given m matrices A_1, …, A_m in an online manner, with consecutive differences bounded by alpha in Schatten norms. For bounds under Schatten 1-norm, the authors can improve the dependence on both alpha and delta (failure probability) compared to the previous best-known result in NeurIPS 2021. For the Schattern 2-norm case, the result matches the previous best-known result. As a complementary, the paper also proves matching lower bounds for static and dynamic trace estimation by reductions to communication complexity and information-theoretic analyses of Gaussian matrices.", "questions": "It would be helpful if the authors can address my comments above.", "limitations": "In the checklist, the authors mark the potential negative societal impact as “not applied”. I in general agree, but at least a brief discussion with 1-2 sentences can be helpful.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "From my perspective, the trace estimation problem is of general interest both in theory and in practice. It’s nice to see that the authors can prove tight bounds for the dynamic version of the trace estimation problem. In particular, I think the improvement in the Schatten 1-norm case is a significant contribution – the prior art on this, a NeurIPS paper last year, can only achieve sqrt{alpha} and sqrt{1/delta} complexities, whereas the current paper improves the parameter dependences to alpha and log(1/delta), respectively. This is significant to me. It’s also nice to see that the result can be extended to general Schatten p-norm with p \\in [1,2], and also new techniques can be brought to proving matching lower bounds. Moreover, it’s very nice to see very detailed numerical experiments both for synthetic data and real data – many theory papers did not make enough efforts on this to me, but the authors of the current paper made the numerics of their algorithms very persuasive. In all, the technical contributions made by this submission are notable and decent.\n\nIn terms of weaknesses, I have the following suggestions: \n\n- It would be helpful to articulate more about the motivation of studying the dynamic trace estimation problem. On the one hand, a main technical contribution of the paper is to study the slow change under Schatten p-norm for p \\in [1,2], but why is p \\in (1,2) of general interest? Does such general norm appear in real applications? On the other hand, it would also be helpful to describe the real scenarios where we need to estimate the traces of slow-changing matrices.\n\n- In general, I think the authors did a decent job in reviewing prior works, but maybe there’s still space to improve. I have two specific papers to suggest. One is the paper by Sun, Woodruff, Yang, and Zhang in ICALP 2019: https://arxiv.org/pdf/1906.05736.pdf This is an early paper which studies algorithms with matrix-vector products. In particular, Section 3.2 of that paper studied query lower bounds on trace estimation, and it would be clearer if a detailed comparison can be made between that and Section 4 of the current paper (Section 3.1 of this ICALP 2019 paper also talked about adaptivity of matrix-vector queries, which is also relevant). \n\n- The other one is the paper by Braverman, Hazan, Simchowitz, and Woodworth in COLT 2020: http://proceedings.mlr.press/v125/braverman20a/braverman20a.pdf This is also a paper studies matrix-vector queries, and they proved a tight lower bound for linear regression using information-theoretic analyses of Gaussian matrices (see its Section 3). It will be very helpful if the authors can make a comparison between that paper and the idea in the current paper when proving lower bounds. \n\n- Typo: In many places of the paper, the abbreviation dots \\cdots should be \\ldots. For instance, this is correct in Line 23, but the dots in Line 22 should be \\ldots. Such changes can be applied throughout the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YEAlLRZEG0E", "reviewer": "Reviewer_2eEg", "summary": "The paper looks at query complexity bounds for trace estimation and dynamic trace estimation, in the matrix-vector query model, under Schatten $p$-norm error for $p \\in [1, 2]$. In particular, the goal is to obtain an estimate $T$ such that $|T - \\text{tr}(A)| \\leq \\epsilon ||A||_p$. There are four main contributions: \n\n1. Tight lower bounds (in terms of $\\epsilon$ and $\\delta$) for static trace estimation under Schatten $p$-norm error in two settings: 1. (bounded bit complexity) queries have entries described using $b$ bits and 2. (RAM) query vectors can have real-valued entries. Most notably, the lower bound proves that $\\Omega(\\log(1/\\delta)/\\epsilon^2)$ queries are required for general square matrices under Frobenius norm error, even when the queries are adaptively chosen. This proves the tightness of the query complexity of Hutchinson's estimator in terms of both $\\epsilon$ and $\\delta$. Secondly, in the nuclear norm case (i.e. p = 1), the bound improves on [1] by a $\\sqrt{\\log(1/\\delta)}$ factor.\n\n2. Upper bounds, along with a new algorithm, for dynamic trace estimation under Schatten $p$-norm error. I.e., one is given a sequence of $m$ matrices $A_1, \\dots, A_m$ such that $ \\text{Schatten p-norm}(A_{i+1} - A_i) \\leq \\alpha$. The bound is an exponential improvement in the failure probability $\\delta$ over [2] in the $p=1$ setting, improving from $\\sqrt{1/\\delta}$ to $\\sqrt{\\log 1/\\delta}$. Although, there is an additional $\\log(m)$ factor. The improvement comes from a new estimator they propose -- by building a binary tree, where the $l$-th level contains estimates of the trace $\\text{tr}(A_{2^l(k)} - A_{2^l(k-1)})$.\n\n3. Lower bounds for dynamic trace estimation nearly matching the upper bound are given via a reduction to the static setting.\n\n4. The authors perform experiments on a sparse collaboration network dataset to estimate triangles and on the weight matrix of a NN being trained on MNIST with SGD. \n\n[1] Meyer, R. A., Musco, C., Musco, C., & Woodruff, D. P. (2021). Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA) (pp. 142-155). Society for Industrial and Applied Mathematics.\n\n[2] Dharangutte, P., & Musco, C. (2021). Dynamic Trace Estimation. Advances in Neural Information Processing Systems, 34, 30088-30099.\n", "questions": "- The lower bound in the dynamic setting is claimed to be 'unconditional'. What is it unconditional on? It seems like there are some conditions on the value of $m$ and $\\alpha$, i.e., one is fixed in terms of the other.\n- In the dynamic setting, does the algorithm require knowledge of $\\alpha$? It seems like it does. Is there a simple way to remove this assumption -- a doubling trick maybe? If so, does the algorithm have to re-query vectors in the $i$-th time step with matrices that appeared in previous timesteps?\n- It seems like the $log(m)$ factor in the upper bound for the dynamic setting is missing from Theorem 3.1\n- What is alpha for the SNAP/MNIST experiments? Can you show some information about how the spectrum of the matrices changes? \n- What about how the trace itself changes? How small is the change compared to its value?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS\nThe main significance of the results, in my opinion, is a tight lower bound for the query complexity under Frobenius norm error, even allowing for adaptive queries. This proves the optimality of Hutchinson's estimator under Frobenius norm error in the matrix-vector query model. \n\nSince trace estimation is an important primitive in numerical linear algebra/ML and the lower bound (under Frobenius norm error) for general square matrices has remained open, this contribution is a significant result.\n\nOn the algorithmic front, in the dynamic setting, the exponential improvement over [2] in the dependence on $\\delta$ under nuclear norm error is also an important contribution as it matches the nature of the dependence on $\\epsilon$ and $\\delta$ in the static setting. The idea required to do this is -- estimating different levels of differences -- is a novel idea over prior work [2].\n\nWEAKNESSES\n1. A small weakness of the algorithmic result in the dynamic setting -- it seems like there is an additional $log(m)$ factor in the number of queries, due to the binary tree. This makes the result a little weaker than that of [2] in the Frobenius norm error setting.\n\n2. The author(s) refer to the lower bound in the dynamic setting as 'unconditional' -- although the construction seems like it fixes $\\alpha$ in terms of $m$ or vice versa. Please see questions section... \n\n3. Concerns about the writing/clarity: Since there are many results in different regimes -- adaptive vs non-adaptive, bounded bit complexity vs unbounded, static vs dynamic, different values of $p$ -- it is hard to follow each result and how it compares to previous work. Especially since the improvements are in some regimes and not others. I would suggest triaging which results are important in the intro -- Frobenius norm error lower bound in the static setting, dynamic setting upper bound for nuclear norm -- and punting the general theorems to to the appendix. And then clearly state how these are improvements over [1] and [2].\n\nTypos etc. \n- footnote 4 in Table 1: 'coplexity' --> complexity\n- Algorithm 1 : Line 4, should be two separate lines (?)\n- Algorithm 1, 2 : remove the variable 'gap' and just use $2^l$.\n- It isn't clear what Algorithm 1 is outputting. Maybe state this at the top?\n- Algorithm 1, Input: What is 'i'?\n- Theorem 4.1: You started with 'b' for bits and switched to 'k'.\n- \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept