Learning-Augmented Frequent Directions
Authors: Anders Aamand
Justin Y. Chen
Siddharth Gollapudi
Sandeep Silwal
Hao WU
Venue: ICLR 2025 Spotlight (2025)
Keywords: learning-augmented algorithms
algorithms with predictions
data streams
streaming algorithms
frequency estimation
heavy hitters
frequent directions
low-rank approximation
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We simplify and generalize existing work on frequency estimation with learned predictions.

Abstract: An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the streaming literature, the goal of frequency estimation is to approximate the number of occurrences of items appearing in a long stream of data using only a small amount of memory. Hsu et al. develop a natural framework to combine the worst-case guarantees of popular solutions such as CountMin and CountSketch with learned predictions of high frequency elements. They demonstrate that learning the underlying structure of data can be used to yield better streaming algorithms, both in theory and practice.

We simplify and generalize past work on learning-augmented frequency estimation. Our first contribution is a learning-augmented variant of the Misra-Gries algorithm which improves upon the error of learned CountMin and learned CountSketch and achieves the state-of-the-art performance of randomized algorithms (Aamand et al., NeurIPS'23) with a simpler, deterministic algorithm. Our second contribution is to adapt learning-augmentation to a high-dimensional generalization of frequency estimation corresponding to finding important directions (top singular vectors) of a matrix given its rows one-by-one in a stream. We analyze a learning-augmented variant of the Frequent Directions algorithm, extending the theoretical and empirical understanding of learned predictions to matrix streaming.

Published as a conference paper at ICLR 2025
LEARNING-AUGMENTER FREQUENT DIRECTIONS
Anders Aamand
Justin Y. Chen
Siddharth Gollapudi
University of Copenhagen
MIT justc@mit.edu
Independent
andersaamanda com
sgollapu@brrkeleycco edu
Sandeep Silwal
Hao WU
UW-Madison
University of Waterloo hao wul @wwaterloo...... ca
silwalecs wisc.
ABSTRACT
An influential paper of Hsu al. (ICLR" 19) introduced the study of Searning-augmente stream- ing algorithms in the context of frequency estimation. A fundamental problem in the streaming literature, the goal of frequency estimation is to approximate the number of occurrences of items appearing in a long stream of data using only small amount of memory. Hsu et al. develop a natural framework to combine the worst-case guarantees of popular solutions such as CountMin and CountSketch with learned predictions of high frequency elements. They demonstrate that learning the underlying structure of data can be used to yield better streaming algorithms, both theory and practice.
We simplify and generalize past work on leaming-augmented frequency estimation. Our first Searning-augmennn variant of the Misra-Gries algorithm which improves upon the error of learned CountMin and learned CountSketch and achieves the state-of- state-of-the-ar ti-the-art perfor- mance of randomized algorithms (Aamand al., NeurlPS'P 23) with a simpler, deterministic al- gorithm. Our second contribution is to adapt leamnng-augmentatin augmentation to a high-dimensional gen- eralization of frequency estimation corresponding to finding important directions (top singular vectors) of matrix given its rows one-by-one in a stream. We analyze bearning-augmentt variant of the Frequent Directions algorithm, extending the theoretical and empirical under- standing of learned predictions to matrix streaming.
contribution
INTRODUCTION
I Learning-augmented algorithms combine the worst-case analysis of traditional algorithm design with machine learning to exploit structure in the specific inputs on which the algorithm is deployed. burgeoning line of work this context has studied algorithms furnished with predictions given by domain experts or learned from past data. This general methodology has been applied to create input-optimized data structures (Kraska et al. [2018] Mitzenmacher) 2018)) graph algorithms (Dinitz
et al.) 2021: Chen et al. 2022c), online algorithms (Lykouris & Vassilvitskii 2021; Gollapudi & Panigrahi 2019), streaming algorithms (Hsu et al. 2019 Jiang et al.) 2020 Chen et al. 2022a) among many other applications] Within the context of streaming algorithms, where the imput arrives in an online fashion and the algorithm has too little memory to store everything, predictors can highlight data which are worth remembering. This intuition was formalized in influential work of Hsu et al. (2019) in the context of frequency estimation, a fundamental streaming problem where the goal to provide an estimate of how many times any element appeared in the stream.
Given access to a heavy-hitter oracle identifying the highest frequency elements, Hsu et al. (2019) give natural framework where the heavy-hitters are counted exactly while the rest of the frequen- cies are approximated using standard algorithms such as CountMin (Cormode & Muthukrishnan 2005) or CountSketch (Charikar et al. 2002). They study the setting where the frequencies follow power law distribution, commonly seen in practice and therefore well-studied for frequency estima- tion (Cormode & Muthukrishnan 2005 Metwally al. 2005 Minton & Price 2012). Given access
'There are hundreds of papers written on this topics. See the survey of Mitzenmacher & Vassilvitskil 2022 2022 the website https:://aala /ttp::://///gorihhsss.m. th pit-ppeeiio ct ons thu.. 1

---

Published as a conference paper at ICLR 2025
to an oracle which can recover the heaviest elements, they give improved error bounds where error is taken in expectation over the empirical distribution of frequencies. A sequence of follow-up works investigate how to learn good predictors (Du et al., 2021 Chen et al. 2022b), apply the results to
other streaming models (Shahout et al. 2024), and give improved algorithms (Aamand et al.
2023
Algorithms
Weighted Error
Predictions?
Analysis
d Jn
[ (In d)²
Frequent Direction
-
No
Theorem 3.3
m
Learned Frequent Direction
A
Yes
Theorem 3.4
(lud)
T
Error bounds for Frequent Directions with input vectors from the domain Rd using m X dl words of memory, assuming that the matrix consisting of input vectors has singular value of x 1/i. The weighted error is defined by Equation (2).
Table 1:
In this work, we define and analyze the corresponding problem in the setting where each data point is a vector rather than an integer, and the goal is to find frequent directions rather than elements (cap- turing low-rank structure in the space spanned by the vectors). This setting of "matrix streaming" is an important tool in big data applications including image analysis, text processing, and numer- ical linear algebra. Low-rank approximations via SVD/PCA are ubiquitous in these applications, and streaming algorithms for this problem allow for memory-efficient estimation of these approxi- mations. In the matrix context, we define a corresponding notion of expected error and power-law distributed data. We develop a learning-augmented streaming algorithm for the problem based on the Frequent Directions (FD) algorithm (Ghashami et al. (016) and give a detailed theoretical anal- ysis on the space/error tradeoffs of our algorithm given predictions of the important directions of the input matrix. Our framework captures and significantly generalizes that of frequency estimation in one dimension. When the input vectors are basis vectors, our algorithm corresponds to a learning- augmented version of the popular Misra-Gries (Misra & Gries 1982) heavy hitters algorithm. In this special case our model, our algorithm achieves state-of the-art bounds for frequency estimation, matching that of Aamand et al. (002)). In contrast to prior work, we achieve this performance without specializing our algorithm for power-law distributed data.
We experimentally verify the performance of our learning- augmented algorithms lowing prior work, we consider datasets containing numerous problem instances in a temporal order (each instance being either sequence of items for frequency estimation sequence of matrices for matrix streaming). Using predictions trained on past data, we demonstrate the power of incorpo- rating learned structure in our algorithms, achieving state-of-the-ard performance in both settings.
real data. Fol-
Our Contributions
We generalize the germing-augmenten frequency estimation model to the matrix streaming setting: each stream element a row vector of matrix A. We define corresponding notions of expected error and power-law distributed data with respect to the singular vectors and values of A.
In this setting, we develop and analyze a algorithm of Ghashami al. (2016). Given predictions of the important directions (correspond- ing to the top right singular vectors of A), we demonstrate an asymptotically better space/error tradeoff than the base algorithm without learning. See Table
version of the Frequent Directions
As a special case of our setting and a corollary of our analysis. we bound the performance of crrming-augmentee Misra-Gries for frequency estimation. In the aauning-augmented setting, past work has analyzed randomized algorithms CountMin and CountSketch as well as specialized variants (Hsu et al., 2019 Aamand et al. 2023). To our knowledge, no analysis has been done prior to our work for the popular, deterministic Misra-Gries algorithm. Our analysis shows that frequency estimation bounds, without randomness or specializing the algorithm for Zipfian data. See Table
learned Misra-Gries achieves state-of-the-arr carning-augment
We empirically validate our theoretical results via experiments on real data. For matrix streaming, our Baaming-augmentt Frequent Directions algorithm outperforms the non-leamndd version by 1- 2 orders magnitude on all datasets. For frequency estimation, our learned Misra-Griae Gries algorithm achieves superior competitive performance against the baselines.
2

---

Published as a conference paper at ICLR 2025
Algorithm
Weighted Error
Rand?
Pred?
Reference
CountMin
θ
Yes
No
Aamand al.
2023
(In
d
Learned CountMin
+
Yes
Yes
(Hsu et al.
2019
(1u d)a
CountSketch
(
Yes
No
Aamand al.
2023
In
d
Learned CountSketch
0
Yes
Yes
Aamand al.
2023
CountSketch++
O In vn pallyyll In
Yes
No
Aamand al.
2023
Learned CountSketch ++
Yes
Yes
Aamand al.
2023
dya
Misra-Grit
+
In la
In 2x
No
No
Theorem 3.1
dIn
Learned Misra-Gries
No
Theorem 3.2
[In di
Error bounds for frequency estimation with input elements from the domain [d] using m words of memory, assuming that the frequency element i [d] follows f(i) x 1/1. The weighted error indicates that element i is queried with a probability proportional 1/i.
Table 2:
Related Work The learning-uut auggeeted frequency estimation problem was introduced Hsu et al. (2019). They suggest the model of predicted frequencies and give the first analysis of learning- augmented CountMin and CountSketch with weighted error and Zipfian frequencies. Du et al. (02II) evaluate several choices for the loss functions to use to learn the frequency predictor and Chen et al. (2022b) develop procedure to Iearn good predictor itself with a streaming algorithm. Shahout et al. (2024) extend the model to sliding window streams where frequency estimation is re-
stricted to recently appearing items. [Shahout & Mitzenmacher (2024) analyze learning-un eeaning--uumented version of the SpaceSaving algorithm (Metwally et al.) 2005) which a deterministic algorithm for frequency estimation, but, unlike our work, they do not give space/error tradeoff's comparable to Hsu et al. 2019). Aamand et al. (2023) give tight analysis for CountMin and CountSketch both with and without learned predictions they develop new algorithm based on the CountSketch, which we refer to as -ugrineed CountSketch++,, which has better asymptotic and empirical performance.
the setting of weighted error with Zipfian data. Furthermore,
Matrix sketching and low-rank approximations are ubiquitous in machine learning. The line of work most pertinent to our work is that on matrix streaming where rows arrive one-by-one, and in small space, the goal is maintain low-rank approximation of the full matrix. The Frequent Directions algorithm for the matrix streaming problem was introduced by Liberty (2013). Subsequent work of Ghashami & Phillips 2014a) and Woodruff (2014) refined the analysis and gave matching lower bound. These works were joined and developed in Ghashami et al. 2016 with an even simpler analysis given by Liberty (2022).
A related line of work is on learning sketching matrices for low-rank approximation, studied in Indyk al. (2019: 2021). Their goal is to learn sketching matrix S with few rows so that the low-rank approximation of can be recovered from SA. The main guarantee is that the classical low-rank approximation algorithm Clarkoon & Woodruff (2013), which uses random S, can be augmented so that only half of its rows are random, while retaining worst-case error. The learned half of S can be optimized empirically, leading to small sketch SA in practice. The difference between these works and us is that their overall procedure cannot be implemented in single pass over the stream. We discuss other related works in Appendix
Organization Section delves into the necessary preliminaries for our algorithm. We define the problems frequency estimation, and its natural higher dimensional version, introduce our notion of estimation error for these problems, and discuss the two related algorithms Misra-Gries and Frequent Directions for these problems. In Section we introduce our -aggeenee versions of Misra- Gries and Frequent Directions. We also analyse the performance of learned Misra-Griie algorithms, postponing the the analysis of learned Frequent Directions to Appendix D Section presents our experiment results with extensive figures given in Appendix F
3

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
Frequency Estimation. Let n. d E N and consider a sequence 01, d2,...,. On E [d] arriving one by one. We are interested in the number of times each element in [d] appears in the stream. Specifically, the frequency f(i) of element E [d] is defined as f(i) = H[t E [n] = i)}. Thus,
Eie[q f(i) = n. Given estimates f(i) for each , E [d]. we focus on the following weighted
estimation error (Hsu et al. 2019 Aamand et al. 2023): Err = f())
((1) - f(0) (1)
The weighted error assigns weight to each element's estimation error proportional to its frequency, reflecting the intuition that frequent elements are queried more often than less frequent ones.
Direction Frequency. The frequency estimation problem has natural high high-dimensional exten- sion. The input now consists of a stream of vectors A1, A An E Rdd For each unit vector i Rd, we define its "frequency." f(T)), as the sum of the squares of the projected lengths of each input vector onto ह. Specifically, let E RRad denote the matrix whose rows are A AT Then f(i) = |
To see the definition is a natural extension of the element frequency in the frequency estimation problem, suppose each input vector A, is one of the standard basis vectors .i.-.., Ea in Rd. Further, we restrict the frequency query vector i to be one of these standard basis vectors, i.e., === é, for some E [d]. Then f(e) = ||A 22 = ΣiEm) (A., Eie(n [AA.=)) which is simply the number of times E, appears A.
Estimation Error. Consider an algorithm that can provide an estimate f(i)) of f(Ø) for any unit vector Rdd The estimation error of a single vector given by [(() - [(0) = || ア(
Since the set of all unit vectors in Rd is uncountably infinite, we propose to study the following weighted error:
Err Σ
of
| -
f(t)
(2)
||
*E[d
where O,...., Od denote the singular values of A, ,,...., Te are the corresponding right singular vectors, and |||| r is its Frobenius norm.
......,,,
To see how this generalizes Equation ( assume again that the rows of A consist of standard basis vectors and that (() ((2) 2
f(Za). In this case, it is straightforward verify that of = f(ē) and गū é for all E [d]. Consequently, o = f()), and || = =sejj of n. Therefore, Equation (2) reduces to Equation (T) in this case. Moreover, for a specific class of algorithms, we can offer an alternative and intuitive interpretation of the weighted error.
Lemma 2.1. For algorithms that estimate f(T) by first constructing matrix B and then applying the formula f(T) = [BB7 such that 0 S fū) S f(T), the weighted error defined in Equation (2)
satisfies Err (B-N((,ATA) || f(0) (3)
The conditions stated in the lemma apply to the Frequent Directions algorithm (Ghashami et al. 2016), discussed later in the section. The lemma asserts that the weighted error is proportional to
the expected difference between || | and f(J), where i is sampled from a multivariate normal distribution with mean 0 and covariance matrix A A. The proof is included in the Appendix
We follows the assumption that in the frequency estimation problem, the element frequencies follow Zipfian distribution (Hsu et al. 2019 Aamand et al. 2023) i.c., f(i) x 1/i Vi E (d). Naturally, for the high dimensional counterpart, we assume that of x T/i.
Zipfian Distribution.
and Frequent Directions Algorithms. The Misra-Gries algorithm (Misra & Gries)
1982) is a well-known algorithm developed for frequency estimation in the streaming setting with limited memory. Its nigh-dimensional counterpart is the Frequent Directions algorithm (Ghashami jtt al., 2016)). We focus on presenting the Frequent Directions algorithm here along with brief explanation of how Misra-Gries be derived from it.
4

---

Published as a conference paper at ICLR 2025
The algorithm is described in Algorithm 1 The matrix B created during the initialization phase be viewed as an array of m buckets, where each bucket can store vector in R As each input vector A; arrives, the algorithm updates B using "update" procedure, inserting A into the first avail-
able bucket in B.
full, additional operations are triggered (Lines T0p: essentially, the algo-
rithm performs singular value decomposition (SVD) of B, such that B = Ej
(1) (3)
(t) where uj and ( of are the columns of matrices U and V respectively, and of are the diagonal
entries of ( The algorithm then retains only the first right singular vectors, o1 ..... 7-1
(8)
scaled by the factors ((ol))2 (a. )2) 1/2
((or_)) (2) respectively.
Algorithm Frequent Direction App
1: Procedure INITIALIZATION
2: Input: sketch parameters m, r, N+, s.t., S m S
3: Reserve m x d space for an empty matrix B
4: Procedure UPDATE
5: Input: an input vector A, E Rd
6: B +
[B; A matrix obtained by appending A? after the last row B
7:
B has m rows then
8:
UO 1 V SVD(B)
max -ot (o.f))21.0)) where (i) is the 7(th) largest singular value
9:
B
11: Procedure RETURN return
To reduce the algorithm to Misra-Gries, we make the following modifications: each input vector A; is an element in [d], and B is replaced by dynamic array with capacity of m. The SVD operation replaced by an aggregation step, where identical elements in B are grouped together, retaining only one copy of each along with its frequency in B. Consequently, lines 7-10 now correspond to selecting the top-(r
elements and reducing their frequencies by f(T)
Based on recent work by Liberty (2022), Algorithm possesses the following properties. For com- pleteness, we provide a brief proof in the Appendix.
Proposition 2.2 ((Liberty
2022 ). Algorithm uses O(md) space, operates in
ama d m+11-
time,
and ensures that A
B B = O. Moreover, it guarantees the following error bound:
AA - AA
| B
min ke
(4)
k
where Il. the spectral norm of matrix, and [A] is the best rank-k approximation of A.
Note that the error in this context is defined by the maximum distortion rather than weighted one. If = (1 (11)m, the rumning time reduces to O(nmd)). Furthermore, for = 0, the error bound simplifies to the original bound established by Liberty (2013). These bounds can be adapted for the Misra-Gries algorithm, where ATA B z 0 implies that the algorithm never overestimates element frequencies. Additionally, when implemented with hash table, the running time for Misra-Gries can be further optimized to On)).
3 LEARNING-AUGGENTTR FREQUENT DIRECTION
We aim to augment the Frequent Directions algorithm with learned predictions. The framework is presented in Algorithm 2
Given space for storing m vectors in Rd the algorithm reserves my S m
A common implementation of Misra-Gries sets and the aggregation step can be optimized using hash tables.

---

Published as a conference paper at ICLR 2025
slots for the predicted "frequent directions" ........ maz which orthonormal vectors returned by a learned oracle. The algorithm then initializes two seperate instances of Algorithm denoted by ApD and AED with space usage mL and m - 2 m., respectively.
After initialization, when an input vector A; arrives, the algorithm decomposes it into com- ponents, A; = t + I where Ait is the projection of A; onto the subspace spanned by wi,....; Wmzz and T is the component orthogonal to this subspace. The vector A, passed to T
AbD. while 1 is passed to App Intuitively, AED is responsible to compute a sketch matrix for the subspace predicted by the learned oracle, whereas App is responsible to compute a sketch matrix for the orthogonal subspace. When the algorithm terminates, the output matrix is obtained by stacking the matrices returned by ArD and Arp To adapt this framework for the learning-augmentie Misra- Gries algorithm, App corresponds to an array to record the exact counts of the predicted elements and An corresponds to a Misra-Gries algorithm over all other elements.
Algorithm 2 Learning-Augmentle Frequent Direction ALPD
1: Procedure INITIALIZATION
2: Input: sketch parameters m, N+; learned oracle parameter my S.t., my S
3: Let PH [w]] ... wmzl E Rddxms be the matrix consisting of the my orthonormal columns, which are the frequent directions predicted by the learned oracle
4: Initialize an instance of Algorithm
A Atppániitializzttommmn 0.5 mz, d)
5: Initialize an instance of Algorithm
A App App.nnttialization (m 2-m
z. 0.5 (m m2)m
6: Procedure UPDATE
7: Input: an input vector A;
8:
A, < P PH P A,
9:
A + A A..
10:
A up.puedeeeA..
11:
#DD-updatel 1
12: Procedure RETURN
13:
B- + returnn)))
14:
B + A repuur)))))
15:
B [B:B11'
16:
return
3.1 THEORETICAL ANALYSIS
We present the theoretical analysis for the (learned) Misra-Grie and (learned) Frequent Directions algorithms under a Zipfian distribution. The error bounds for the (learned) Misra-Gries algorithms detailed in Theorems 3.1 and 3.2 The corresponding results for the (learned) Frequent Direc- tions algorithm are provided in Theorems
3.3 and 3.4 The complete proofs for are provided in
Appendix C and Appendix D respectively.
Due to space constraints, we provide sketch proofs for the (learned) Misra-Gries algorithm only. The proof's for the (learned) Frequent Directions algorithm follow similar techniques. Since the structure of Misra-Grice is simpler, analyzing its bounds first offers clearer insights into the problems.
Theorem 3.1 (Expected Error of the Misra-Gris Gries Algorithm). Given stream of n elements from domain [d], where each element has a frequency f(i) x 1/i E [d], the Misru- algorithm using m words of memory achieves expected error of Err E 6
@((1n In
m In (In d)= m (5)
Proof Sketch. At a high level, we first derive an upper bound on the maximum estimation error using Fact 2.2 under the Zipfian distribution assumption. We then partition the elements into two groups: those with frequencies exceeding this error and those that do not. For the first group, the estimation error for each element is bounded by the maximum error. For the second group, since Misra-Gries never overestimates their frequencies, the error limited to the actual frequency of each element. For each group, can show that the weighted error is bounded above by the RHS

---

Published as a conference paper at ICLR 2025
of (5). For the lower bound, construct adversarial input sequence such that the weighted error of elements in the first group indeed matches the upper bound, proving that the bound is tight. O
Theorem 3.2 (Expected Error of the Learned Misra- Peises Algorithm). Given stream of elements from a domain [d], where each element i has a frequency f(i) & for i E [d], and assuming Misra-Gret algorithm using m words of memory achieves
perfect oracle, the
expected enror of Err E ①
Here, a perfect oracle is defined as one that makes no mistakes in predicting the top frequent ele- ments. The scenario where the learning oracle is not perfect will be discussed later in this section.
Proof Sketch. Under the assumption of access to a perfect oracle, the algorithm does not make estimation error on the top-m, elements. For the remaining elements, the Misra-Gries algorithm never overestimates its frequency: f(()= E [()] Hence the weighted error at most
Err Σ
1(0) JW) n2 150 --000 i=
Σ
a
EO
n
(6)
Inn ind m
(In
11
The lower bound is obtained using a similar technique as in Theorem 3.1 by constructing an input sequence such that the error incurred by the non-predicted elements matches the upper bound. D
Comparison with Previous Work. This guarantee matches that of the learning-augmenti quency estimation algorithm Aamand et al. (2023) but with significant simplifications. Aamand et al. (2023) also reserve separate buckets for the predicted heavy hitters, but to get a robust algo- rithm in case of faulty predictions, they maintain (log logn) n) additional CountSketch tables for determining if an arriving element (which is not predicted to be heavy) is in fact a heavy hitter with reasonably high probability. If these tables deem the element light, they output zero as the estimate, and otherwise, they use the estimate of separate CountSketch table. In contrast, our algorithm uses just a single implementation of the simple and classic Misra-Grn Ceire- algorithm. This approach has the additional advantage of being deterministic in contrast CountSketch, which is randomized.
fre-
Robustness and Resilience to Prediction Errors. We note that the learned Misra-Gries algorithm is robust in the sense that it essentially retains the error bounds of its classic counterpart regardless of predictor quality. Indeed, the learned version allocates m/2 space to maintain exact counts of elements predicted be heavy, and uses a classic Misra-Gries sketch size m for the remaining elements. Thus, it incurs no eтror on the elements predicted to be heavy and on the elements pre- dicted be light, we get the error guarantees of classic Misra-Gries (using space m/2 instead of m). It is further worth noting that the error bound of Theorem 3.2 holds even for non-perfect learn- ing oracles or predictions as long as their accuracy is high enough. Specifically, assume that the algorithm allocates some my 2(m) buckets for the learned oracle. Further, assume that only the top c- my elements with the highest frequencies are included among the m heavy hitters predicted by the oracle, for some < 1 (c.g., 0.1). In this case. Inequality (6) still holds: the summation now starts from c. m + instead m + 1, which does not affect the asymptotic error.
The corresponding theorems for (learned) Frequent Directions below with proofs in Appendix D Theorem 3.3 (Expected Error of the FREQUENT DIRECTIONS Algorithm). Assume that the singu- 1 satisfies of x for all E [d], achieves an |
lar values of the input matrix A to the Algorithm expected error of Err(ArD) E e @(1n
m
In (lu
In 24
Theorem 3.4 (Expected Error of the Learned FREQUENT DIRECTIONS Algorithm). Assume that
the singular values of the input matrix A to Algorithm 2 satisfies of for all [d]. and that
learning oracle is perfect, achieves an expected error of Err(AFD) E θ (Ind)²
|A
m
Robustness of Learned Frequent Directions. It turns out that Algorithm 2 does not come with a robustness guarantee similar to that of Learned Misra-Gries discussed above. fact, we can construct adversarial inputs for which the expected error is much worse than in the classic setting. Fortunately, there is a way to modify the algorithm slightly using the fact that the residual error | ||] can be computed within constant factor using algorithm from Li et al. 2024)..

---

Published as a conference paper at ICLR 2025
Since the error of the algorithm scales with the residual error, this essentially allows us determine we should output the result of a learned or standard Frequent Directions algorithm. The result is Theorem[E.
robustness. Combined with Theorem E.22, which explicitly bounds the error of Al-
gorithm 2 in terms of the true and predicted frequent directions, we obtain consistency/robustnes tradeoff's for the modified algorithm. Details provided in Appendix [
EXPERIMENTS
We complement our theoretical results with experiments on real data both in the frequency estima- tion (I-dimensional stream elements) and frequent directions (row vector stream elements) settings. We highlight the main experimental results here and include extensive figures in Appendix F
4.1 FREQUENT DIRECTIONS EXPERIMENTS
Datasets and Predictions We use datasets from Indyk et al. (2019) and Indyk et al. (2021), prior works on learning- low rank approximation not in the streaming setting. The Hyper dataset (Imamoglu et al. 2018) contains a sequence of hyperspectral images of natural scenes. We consider 80 images each of dimension 1024 768. The Logo, Friends, and Eagle datasets come from high- resolution Youtube video We consider 20 frames from each video each with dimension 3240 x 1920. We plot the distribution singular values for each dataset in Appendix F For each dataset, we use the top singular vectors of the first matrix in the sequence to form the prediction via low-rank projection matrix (see Algorithm
Baselines We compare two streaming algorithms and one incomparable baseline. In the streaming setting, we compare the Frequent Directions algorithm of Ghashami et al. (2016) with our learning- augmented variant. Both implementations are based on an existing implementation of Frequent Di- rection="] We additionally plot the performance of the low-rank approximation given by the largest right singular vectors (weighted by singular values). This matrix is not compuluble in a stream as it involves taking the SVD of the entire matrix but we evaluate for comparison purposes. Results are displayed based on the rank of the matrix output by the algorithm, which we vary from 20 to 200. For both Frequent Directions and our learned variant, the space used by the streaming algorithm is twice the rank: this is a choice made in the Frequent Directions implementation to avoid running SVD on every insertion and thus improve the update time. We use half of the space for the learned projection component and half for the orthogonal component in our algorithm.
Results For each of the four datasets, we plot tradeoff's between median error (across the sequence of matrices) and rank as well as error across the sequence for a fixed rank of 100 (see Figure []. Frequent
We include the latter plots for choices of rank in Appendix F Our Barriing-augmene Directions algorithm improves upon the base Frequent Directions by 1-2 orders of magnitude on all datasets. In most cases, it performs within an order of magnitude of the (full-memory, non- streaming) SVD approximation. In all cases, increasing rank, or equivalently, space, yields signifi- cant improvement the error. These results indicate that learned hints taken from the SVD solution on the first matrix in the sequence can be extremely powerful in improving matrix approximations in streams. As the sequences of matrices retain self-similarity (e.g.. due being a sequence of frames in video), the predicted projection allows our streaming algorithm to achieve eтror closer to that of the memory-intensive SVD solution than that of the base streaming algorithm.
4.2 FREQUENCY ESTIMATION EXPERIMENTS
Datasets and Predictions We test our algorithm and baselines on the CAIDA (CAIAA 2016 and AOL (Pass et al.) (006) datasets used in prior work (Hsu et al. 2019 Aamand et al. 2023
The CAIDA dataset contains 50 minutes of internet traffic data, with a stream corresponding to the IP addressed associated with packets passing through an ISP over minute of data. Each minute of data contains approximately 30 million packets with 1 million unique IPs. The AOL dataset
'Originally downloaded from
be/
xm xml./s.. and http: httt:::///otuuuu wtw.ttuuueeeeuffee hff and appcaring in Indyk et al. (2019)
https:: thub. htt.ar//attto..oooooooooorrrrrea
8

---

Published as a conference paper at ICLR 2025
Error/Rank Tradeoff
100
SVD
10
SVD
FD
Learned
Learned
10-4
Eno:
Ereor
10-1
10-3
10th
120
200
20
(a) Hyper
Error/Rank Tradeoff
10a
SVD
SVD
FD
10a
10*
Eree
10a
10a
10*
(b) Logo
Error/Rank Tradeoff
10a
SVD
10a
10r
101
Ener
10-2
10a
10'
Learned FD (ours)
(c) Eagle
Tradeoff
10a
SVD
SVD
FD
(ours)
10F
Ereer
10c
300
102
(d) Friends
Figure 1: Comparison of matrix approximations. The Frequent Directions and Seaminn--ugmant Frequent Directions algorithms are streaming algorithms while the exact SVD stores the entire ma- trix compute low-rank approximation (so cannot be implemented in stream). For each dataset, the left plot shows median error (error formula from Equation (2) as the rank of the approx- imation varies while the right plot shows 100. The sudden drop in error in Eagle corresponds to several frames of a black screen in the video.
the sequence of matrices with fixed rank of
contains 80 days of internet search query data with each stream (corresponding to a day) having around 300k total queries and 100k unique queries. We plot the frequency distribution for both

---

Published as a conference paper at ICLR 2025
datasets in Appendix F We use recurrent neural networks trained in past work of Hsu et al. (2019) as the predictor for both datasets.
Algorithms We compare our Garning-augmant
Misra-Griee algorithm with learning-augmenter 2019) and learning-augmenter augmented CountSketch++ (Aamand et al. 2023). As
CountSketch (Hsu et al.
in Aamand al. (2023) we forego comparisons against CountMin as it has worse performance both
learned CS++ the implemented algorithm does not exactly correspond to the one which achieves the best theoretical bounds as only single CountSketch table is used (as opposed to two) and the number of rows of the sketch 3 (as opposed to (log log n)). There is tunable hyperparameter where elements with estimated frequency less than Cn/u have their estimates truncated to zero (where is the stream length and w is the sketch width). The space stored by the sketch corresponds to 3w as there are 3 rows. For Misra-Gries, the space corresponds to double the number of stored counters as each counter requires storing a key as well as a count. As in prior work, for all algorithms, their learned variants use half of the space for the normal algorithm and half of the space to store exact counts for the elements with top predicted frequencies.
in theory (Aamand et al.
2023) and practice (Hsu et al. 2019). For the prior tfate-of-the-eee
1o12
Error/Space Tradeoff
2013
Space: 750
1.4
CS
CS
1.2
CS++ (C-2)
CS++ (C-2)
3.0-
CS+4 (C+5)
Weighted Eiror in
CS++ (C-5)
MG
0.8-
0.6
0.4
500
1000
1500
2000
2500
3000
10
20
30
40
50
Space
Streams
Error/Space Tradeoff
Space: 750
3.0
CS++ [C-1]
CS++ (C=1)
Weignted Error
CS+1
Weightte Ereer
C5++ (C=5)
(C-5)
MG lours)
MG (ours)
1.5
1.0
1000
1500
20000
2500
3000
20
30
50
80
Streams
Figure 2: Comparison of sauming--ugmeent frequency estimation algorithms. Top: CAIDA, Bot- tom: AOL. For both datasets, the left plot show the median error of each method (across all 50 streams) with varying space budgets. The right plot shows the performance of each algorithm across streams with fixed space of 750 words. Randomized algorithms are averaged across 10 trials and one standard deviation is shaded.
Results For both datasets, we compare the learning-augmenti algorithms by plotting the tradeoff between median error and space as well as error across the sequence of streams for a fixed space of 750 (see Figure 22. In Appendix P. we include the latter plots for all choices of space, as well as all corresponding plots both without predictions (to compare the base CS, CS++, and MG algorithms) and under unweighted error (taken as the unweighted sum of absolute errors over all stream items re- gardless of frequency) which was also evaluated in prior work. The searning-augmeet algorithm improves significantly over seemming-augmentee. CountSketch, as implied by our theoret- ical bounds. Furthermore, it is competitive with the state-of-the-an learning- eeaming-augmented, augmented CS++ al- gorithm. Sometimes our algorithm outperforms the best hyperparameter choice CS++ and often outperforms several of the hyperparameter choices of CS++. Furthermore, reaming--uugmente MG has no equivalent tunable parameter and is simpler to deploy (especially as CS++ is already a sim- plification of the theoretical algorithm of Aamand et al. (2023)). As Baaming--uumeent only deterministic algorithm with provable guarantees in the setting of Hsu et al. (2019), our results indicate that there is essentially cost to derandomization.
Misra-Gries
MG is the
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Justin Y. Chen is supported by an NSF Graduate Research Fellowship under Grant No. 17453. Hao WU was a Postdoctoral Fellow at the University of Copenhagen, supported by Providentia, a Data Science Distinguished Investigator grant from Novo Nordisk Fonden. Siddharth Gollapudi is supported in part by the NSF (CSGrad4US award no. 2313998).
REFERENCES
Anders Aamand, Justin Y. Chen, Huy Le Nguyen, Sandeep Silwal, and Ali Vakilian. Im- proved frequency estimation algorithms with and without predictions. In Alice Oh, Tris- tan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Ad- vances in Neural Information Processing Systems 36: Annual Conference on Neural Infor- mation Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL httpp///apprr..nsss.cc//ggg http://ppee.fiillepsapper/////// (t139934cccccba6oo
html
CAIDA. Caida internet traces, chicago.
http://www..ccaaaooo////ooooooos
chicago.xml, 2016.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David Woodruff. and Michael Zhang. Triangle and four cycle count- ing with predictions in graph streams. In International Conference on Learning Representations, 2022a.
Justin Y. Chen, Piotr Indyk, and Tal Wagner. Streaming algorithms for support-aware histograms. In Proceedings of the 39th International Conference on Machine Learning, 2022b.
Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algo- rithms via learned predictions. In International Conference on Machine Learning, pp. 3583-3602.
PMLR, 2022c.
Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input spar- sity time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (eds.), Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pp. 81-90. ACM, URL https:/ /ttp:///oi..oo /ttp::///ooi.or/11.... 11011114544888
2013. doi: 00.1145/248860824886222 2488620
Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithmss 55(1):58-75, 2005.
Michael Dinitz, Sungjin Im. Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.
Faster matchings via learned duals. ArXiv, abs/2107.09770, 2021. URL https://app.
semant wachhoar.............mm..
ID: 2231158922
Elbert Du Franklyn Wang. and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 2869. PMLR, 18-24 Jul 2021. URL https: //proceedings... mlr wwwpsppsspee.ee.e
html
Mina Ghashami and Jeff M. Phillips. Relative errors for deterministic low-rank matrix approxima- tions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '14, pp. 707-717, USA, 201 Society for Industrial and Applied Mathematics. ISBN 9781611973389.
Mina Ghashami and Jeff M Phillips. Relative errors for deterministic low-rank matrix approxima- tions. In Proceedings of the twenty-fifth annual pp. 707-717. STAM, 2014b.
symposium on Discrete algorithms,
11

---

Published as a conference paper at ICLR 2025
Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5):1762-177 1792, 2016. doi: 10.1137/15M10009711
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert
advice. In International Conference Machine Learning, 2019. URL https://api.
remanticscholesn wwt.:/aa..rrrooooooooooooooo//o Swgg/oorpusiii : :10::::48800000 74800680
Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL Eorum? farammid=rllin @g=rllohoCqy?.
Nevrez Imamoglu, Yu Oishi, Xiaoqiang Zhang, Guanqun Ding, Yuming Fang, Toru Kouyama, and Ryosuke Nakamura. Hyperspectral image dataset for benchmarking on salient object detection. In 2018 Tenth international conference on quality of multimedia experience (qoMEX), pp. 1-3. IEEE, 2018.
Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning- based low-rank approximations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https::/prooeeeding..eeee www.iips.n.g................ cc/ppper files//aper/2019/ File/162550 /ttp:///022222277777766022232220
Piotr Indyk, Tal Wagner, and David Woodruff. Few-shot data-driven algorithms for low rank ap- proximation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 10678-10690. Cur- ran Associates, Inc., 2021. htt.:////.....ee/oooope.ee...ee.
files/ Papperppppr....
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P Woodruff. Leaming-augmented data stream algorithms. ICLR, 2020.
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD '18 pp. 489-504, New York, NY, USA, 2018. Association for Computing Machin- ery. ISBN 9781450347037. doi: 10.1145/318371333199990 URL https:///doi.ozg/1...
1145/3183713. 319690999999
Yi Li, Honghao Lin, and David P. Woodruff. Optimal sketching for residual error estimation for matrix and vector norms. The Twelfth International Conference on Learning Representa- tions, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https:
7/ /openzeview. fere/fformm22 wawermmmddd-ssmmmmee RsJwnWVE60
Edo Liberty. Simple and deterministic matrix sketching. In Inderjit S. Dhillon, Yehuda Koren, Rayid Ghani, Ted E. Senator, Paul Bradley, Rajesh Parekh, Jingrui He, Robert L. Grossman, and Ramasamy Uthurusamy (eds.), The 19th ACM SIGKDD International Conference Knowl- edge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11-14, 2013, pp. 581- doi: 10.1145/2485555.24888 2487766....
588. ACM, 2013.
URL https:://ci.orgee
2487575. 2487 2487
Edo Liberty. Even simpler deterministic matrix sketching. CoRR, abs/2202.01780,, 2022. URL
ht https: :tstts:/aaraae //tpxv/vvvvv///////////aa//aavvv org/ abs/ 2202.222.20 01780
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4), July 2021. ISSN 0004-5411. doi: 10. 10.1145/3447579, httphtttt///...... org/
10.1145/344757
Ahmed Metwally, Divyakant Agrawal, and A. Abbadi. Efficient computation of frequent and top- elements in data streams. In International Conference on Database Theory, pp. 398-412, 2005. ISBN 2488---40-24288-8 doi: 10.0007797783354400057773 27.
12

---

Published as a conference paper at ICLR 2025
Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA), pp. 142-155. SIAM, 2021.
Gregory T. Minton and Eric Price. Improved concentration bounds for count-skerch. In ACM-STAM Symposium on Discrete Algorithms, 2012. URL httas//.....mmmtttccccccoo......
CorpusID:11724333
Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program., 2(2):143- 152, 1982. doi: 10. (0.101660166-662336))))000000000
URL https:///ci.orr/11....
0167-6423 (82) 90012-0
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Advances in Neural Information Processing Systems, 31, 2018.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun ACM, 65 (7):33-35, June 2022. ISSN 0001-0782. doi: 10.1145/3528087. URL 10. 10.1145/3528087
org/
Greg Pass, Abdur Chowdhury, and Cayley Torgeson. A picture of search. Proceedings of the Ist international conference Scalable information systems, pp. 1-cs, 2006.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS 06), pp. 143-152.
IEEE, 2006.
Rana Shahout and Michael Mitzemmacher. Learning Learning-based based heavy hitters and flow frequency esti- mation in streams. In arXiv preprint, 06 2024. doi: 10.48550/arXiv.2406. 16270.
Rana Shahout, Ibrahim Sabek, and Michael Mitzenmacher. Learning-augmented frequency estima- tion in sliding windows. In arXiv preprint, 09 2024. doi: 10.48550/r2xi..4009..55 1511.
Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketching algorithms for low-rank matrix approximation. SIAM Journal Matrix Analysis and Applications, 38(4): 1454-1485, 2017.
David Woodruff. Low rank approximation lower bounds in row-update streams. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL http:////procceeins...eeee inwpeeeeeeddnng...e........... wttps//c.pppppppeeeeeeeeee File/ #i1e=//eed4455000777e2222222b2bd Paper .pff
David P Woodruff et al. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Other Related Works
15
B Missing Proofs for Preliminaries
15
Analysis of Misra-Gries
D Analysis of Frequent Directions
21
D.i Frequent Directions Under Ziphan
21
D.2 Learned Frequent Directions Under Ziphan
22
E
Consiseeney/Robustnee trade offs
25
E.1
The Error of Non-Perfect Oracles
26
F
Additional Experiments
28
Dataset Statistics.
................................
28
F2
Noise Analysis Frequent Directions
28
F3
Additional Frequent Directions Experiments
29
F4
Additional Frequency Estimation Experiments
30
Table of Notations
Symbol
Definition
Number of Inputs in the Stream
Domain Size (Frequency Estimation)
d
Dimension (Frequent Directions)
J(-)
Frequency
ag
The 1 input element in the stream (Frequency Estimation)
A
The 2h input vector in the stream (Frequent Directions)
A
Stream Input Matrix
Standard Basis Vector
0
Singular Value of a Matrix
N(..)
Normal Distribution
U
Σ V
The SVD decomposition matrices at the 1h iteration of Algorithm 1
Table 3: Definitions of Main Notation.
14

---

Published as a conference paper at ICLR 2025
A OTHER RELATED WORKS
There is also a vast literature on sketching based algorithms for low-rank approximation without any learned aanneed-aggmetttionn (Sarlos) 2006; Ghashami & Phillips 20144b Liberty 2013 Tropp al. 2017 Meyer et al. 2021). We refer to the monograph WWoodrfff et al. (0114) for more details.
B
MISSING PROOFS FOR PRELIMINARIES
We refer the reader to Section 2 for the full statements.
Proof of Lemma 2.1
E
|| - [(0)
-E T A Ao
E O
B" B"Bo]
(.
E [Ir(T" TT A A
[r(T" B Bo)
= E [tr(AA T Arz
E (t((B T Brx ]
=trAAAA A E xx
-rtBB" E [x.1
=tr((AAA) A)
BAAAAAA
Let ú; be the right singular vectors of A:
(ATA)²) = tr tr
of
17544
(7)
(E|d]
tr
Σ
o
=
Σ +
(8)
iE|d
iE|d
tr (B A) =
BTB
Σ
(9)
iE [d]
Σ iE|4
of tr B B
Σ
of tr
(of B Be))
(10)
(E(d]
Therefore,
E (-N(OAATA)
JJ (ATA - - Σ Σ
of
of tr
1 B
(11)
vEld]
EE|d]
Further, since ((T) |Bë 2 and 0 f(ū) ((0). Equation 22 can be written
of
Σ
-B'B)B
(12)
A
KE/4
The first term is given by
of
Σ
7=
Σ
74
Σ o.
(13)
[E(d]
jEGd
KE(d]
EE|4
Further note that
||01|]]
I=TAA -TTATT 2] = E
[tr (tr(:TAA) (=TAAA=))
(14)
A
N~N((
z~N(0.1)
E
(rr (AAT 222 tr tr (AA7) = |A
(15)
*~N((011
15

---

Published as a conference paper at ICLR 2025
Therefore,
of -
BEONTOATA) [TT BBB ET-N(OATA)) |
(16)
|
Proof of Fact 2.2
For consistence, at each iteration, if B has less than m rows after insertion, we
still define
U 0 v + SVD(B); and Σ (
To analyze the error, let ( denote the value of B after the j(th) iteration, and define
(i) A A,
( 1) B
(i-1)
B
BO
vūrD U U ( (
v E
- "000" (() (1) E(1
V(i)T
Then
ATA ((m)
B (())
Σ
A?" + B B ((0) B(a)
Σ
A
(0
(17)
iE(n)
sc/n
Since each
(6) > 0, we prove that
A - ((m) B(n)) 2 0.
(18)
Let Ui...., Us IR* be the right singular vectors of A. For each ....., 1, define the projection matrix PA 0 0 ūx+1 I... Tdl Rdxd consisting of columns vectors O....,0, Ö, uk+1..... Tz. The null space thus spanned by the top-k right singular vectors of A. We
claim the following holds:
Ph
Ps.
= 0,.......
(19)
T-
Before proving it, we complete the proof of the error:
ATA- B(n)
((n)
Σ
Ph
A Ps
(20)
2
/E(M]
(E(n]
iE(n)
tr
P
Σ
A
(
Ps
(21)
k
[E(A]
1
tr P T
A
APP
1|A -A]I
(22)
k
k
Proof of Inequality 19):
First,
(6)
V(0) 101 T
(1)) 1
V
E0 T
16) D(I)
m ())
(o.0) 2
1
(1)
16

---

Published as a conference paper at ICLR 2025
where of is the 7(th) largest singular value of Next,
E(t)
A (3)
= tr
V
Σ
(3)
E
V(07)
(23)
Σ
T
Σ
E
Σ SEId
(00))²²
(
2 r. (o!))²
(24)
Next, let Ps 01 .... 06 10 ... [0] E dxd be the projection matrix to the space spanned by
the top-k right singular vectors A. Then Ps- + Ps I, and
tr = tr (PPx PR
Pk P..) = tr P A PA)
+ +
Pk
(1) Ps
(25)
Expanding (P. A (1) Pk) get
P A (9
Ps.
Σ
o
A
By
S k. (0!0)
(26)
jE(k]
which implies that
5 Ph S (T (T- k)) (0.0) 2 = -T- A
(27)
Running Time: For each A,, inserting it into takes ((d) time. When reaches its capacity of rows, the operations in Lines 10 are triggered, and performing the SVD requires (m d) time.
After completing this step. has at least m - r + empty rows. Thus, the algorithm can ac- additional insertions before Lines
commodate least m Consequently, the total running time is:
10 need to be executed again.
0
11
m 2 d
(28)
m T
17

---

Published as a conference paper at ICLR 2025
C ANALYSIS OF MISRA-GRIES
Proof of Theorem 3.1 We need to prove both upper bounds and lower bounds for the thcorem.
Upper Bound for Theorem 3.1 W.L.O.G., assume that f(1) > f(2)
f(d). Since f(i) x
for each E [d]. and the input stream consists of n elements, it follows that f(i) ~ m
ilnd
Assume that we have a Misra-Gries sketch size m E N+ Then by translating the error guarantee from Fact 2.2 for Misra-Gries, we have
72 Σj ((i)
Eje(m/2 f(i)
2. In 2d
max ((0 - [(i) x min ic|d]
S
(29)
(0 m-
T
m/2 /2
m In d
Further,
n
2 In
1 2 In 2d
f(1) i. Ind
(30)
m
In
Since also know that 0 f()) S f()., it follows that
zz
Σ iE(d
f(i)
[8() - 5(1)
f(i)
[(1) -(()
+
Σ
f(i)
F(1) - f(1)
n
2:1a 28
2:hm
f(i) 2 12
2d
f(i)
Σ
[(i
In d
2-1n 2d
+1
21
1
2 In
2d
Σ
d
m In
i In
Il
+1
2.1n 2d
In
2.1n
In m
72
0
In
In d
m
+ 1
(In d)2
2-1a 23
2-In
m
2I
n
d
In
0
1
m
(In d)²
m
(In d)²
d
m
n2 (In d)3
0
In
2d
To prove the lower bound, we assume there is an adversary which controls the order that the input elements arrive, under the constraints that Σie(a f(i) and f(i) x 1/i, to maximize the error of the Misra-Gries algorithm.
Lower Bound for Theorem 3.7
Denote B the array maintained by the Misra-Gries algorithm, containing buckets. Initially, all buckets are empty.
First, the adversary inserts elements 1,..., to the Misra-Gries algorithm, with multiplicities (())...,,(()) where In 22 After this, contains t non-empty buckets (for simplicity, here we assume that Eie(e) f(i) is multiple of m). which stores elements 1, I,..., associated with their recorded frequencies "))),.,,()),,, which we call their counters.
Next, let be the multi-set consisting of elements t+ 1+.,..., d, such that each element E [t 1..d has multiplicity f(i) in C. Consider the following game:
Adversary: pick element from C that is not in B. If such element exists, remove one copy from C, and send it to the Misra-Gries algorithm as the next input. If there is no such element, stop the game.
18

---

Published as a conference paper at ICLR 2025
Misra-Gries Algorithm: process the input i.
During this game, B are filled up and contains no empty bucket after at most every input, and the counters elements .,....t decrease by (if they are still above zero) when B is updated make empty buckets.
Further, when the game stops, there can be most m distinct elements in C, with frequency sum at most m f(i). It follows that the counters of elements 1, .....,f in decrease least by
1
Σ f(i)
Iu d m Ind
since m S 2m.
m
i=++++1
Therefore, the weighted error introduced by these counters is at least
Σ iE|O
i. Ind m In Ind m In = -2 52 (0((1)
n In m = int In
In
n (In
In
In
2d
d)² m
Proof of Theorem 3.2 We need to prove both upper bounds and lower bounds for the theorem.
It suffices to show that, there exists parameter setting of my which enables the algorithm to achieve the desired error bound.
Upper Bound for Theorem
Assume that the algorithm reserves my mm/3 words for the learned oracle. Then for each element
i E [mz], its frequency estimate f(i) f())) And for each i & [mr.], the Misra-Gries algorithm
never overestimate its frequency: f(i) [0, (()] Hence
Err Σ
f(i)
[(1) (())
S Σ 1= ind i ind E E (In d)
n
n
(31)
1=mL+1
To establish the lower bound, we consider an adversarial sce- nario where an adversary controls the order in which elements arrive, subject to the constraints Eieta f(i) n and f(i) 1/i. The adversary's goal is to maximize the error of the learned
Lower Bound for Theorem
Misra-Gries algorithm.
According to the framework presented Algorithm 2 for the learned Frequent Directions, the learned Misra-Gries algorithm initializes separate Misra-Gries instances: one for the my el- ements predicted to be frequent and one for elements predicted to be non-frequent.
Since my memory words already reserved for storing the frequencies of the predicted frequent elements, we do not need to run a full Misra-Gries algorithm on the these elements. Instead, we only record their observed frequencies.
By overloading the notation littl, let us denote B as the array used by the Misra-Gries instance managing the predicted non-frequent elements, which has capacity of m my buckets. Initially, all buckets in B are empty.
Since the learned Misra-Gries algorithm incurs no estimation error for the predicted frequent ele- ments, our analysis focuses on the non-frequent elements and the potential error introduced by the Misra-Gries instance that processes them.
Let C denote the multi-ser set of elements my -1, -1... d, where each element [m_ + 1.. appears with multiplicity f(i) in C. Consider the following adversarial game:
Adversary's 's Role: At each step, the adversary selects an element i from that is not cur- rently stored in the array B. If such element exists, the adversary removes occur- rence of i from and sends it to the Misra-Grrs Gries algorithm as the next input. If there is no such element left, the adversary halts the game.
19

---

Published as a conference paper at ICLR 2025
Misra-Griie Algorithm's Role: The Misra-Gries algorithm processes the incoming element as it would normally, using the array B capacity m m..
After the game, the remaining elements in C' fed the Misra-Gries algorithm in arbitrary order by the adversary.
Now, consider the estimation error made by the Misra-Gries algorithm on the elements my + 1,..., my + 2(m m.). Since the array B can only store up to m my elements, the algo- rithm must estimate the frequency of at least m mz elements from this range as zero. Therefore, the error is at least
m. 11mm2mmmmpp
mL m2
f(i) f(i)
Σ
n i In d i. Ind
El n )
mn?
m+)
8= +1
which finishes the proof.
20

---

Published as a conference paper at ICLR 2025
D ANALYSIS OF FREQUENT DIRECTIONS
D.1 FREQUENT DIRECTIONS UNDER ZIPFIAN
Proof of Theorem 3.3
We need to prove both upper bounds and lower bounds for the theorem.
Upper Bound for Theorem
3.3
First, based on the assumption that of 4, and Fact 2.2 we have
|A
[ 1|
A A
B S
min kejo..
(32)
m-]
k
Σ d 2imk+1 of
min
(33)
ke(o..mm- m-1
k
(Ha Hx) |
min kelu..m- m-
(34)
(r - k) In
2- (H, - H -2mm2) ||
(35)
mn In
||A|| In 2d m In
0
(36)
where Hm =E Ezmml j. vm E N+ are the harmonic numbers. Further,
|
| 2 In m m Ind
p
m
(37)
2d
Ind
Since B 2 0, and A B B = 0 by Fact 2.2 it follows that for each right singular vector 8 of A
0 < (A - B'B of A
S sof
(38)
where is the singular value associated with T7 Therefore, the expected error is given by
Err(Ard) Σ
(A
T A
B'BU
(39)
|
2
AIT
o²
d
of
A E +
Σ
A (40)
||A|
2
| 2
F
+1
In
|| In 2d m In d
of | F
E
of
(41)
||||
2
P
in
|| P
In m In
2d m
||| 8 Ind
(42)
i In d
i- In d
Y12
|| In 2d
|| 1| (In d)
In
(43)
In d
m In d
1
In
In
In 20
| F
In 2d
In 2d
||||
2
F
(44)
1
m (In d
m
(In d)2
In d
|| 2 (In dy²
In
(45)
2d In
m
21

---

Published as a conference paper at ICLR 2025
Lower Bound for Theorem 3.3 The proof of the lower bound follows the same approach as the one for Theorem 3.1 in Appendix
Assume that A consists of standard basis vectors é Eg E R. Let f(e.) denote the number of occurrences of ē; in A. Without loss of generality, assume that f(ā)) 2 ... 2 f(ex). In this case, we have f(E;) = of and Σie(a f(e,) Eie of || = Further, we can then view the B maintained by the Frequent Directions algorithm as an array of m buckets.
Now the setting is exactly the same the Misra-Gries algorithm. Consequently, the constructive lower bound proof from Theorem 3.1 directly applies to Frequent Directions.
D.2 LEARNED FREQUENT DIRECTIONS UNDER ZIPFIAN
We need an additional result to prove Theorem 3.4 Recall that H in Algorithm 2 consists of or- thonormal column vectors 1...... Wms. E RR Extending this set of vectors to form orthonormal basis of Rd: Wi..... Umz+ +m Wd. Write PH = [wmz+1 ... Wi the projection ma- trix to the orthogonal subspace. Let A, AP f P be the matrix of projecting the rows of to the predicted subspace, and A A A = A(I P.).)).
The following lemma holds.
Lemma D.1. For vector I E Rd have
ATAF= of d'A
Σ of (P P sE|d]
(P H
PT.
(46)
The proof the lemma is included at the end of the section.
Proof of Theorem 3.4 We need prove both upper bounds and lower bounds for the theorem.
It suffices to show that, there exists parameter setting of m. which enables the algorithm to achieve the desired error bound. We assume that the algorithm mL m/3 predicted directions from the learned oracle.
Upper Bound for Theorem 4
Recall that Algorithm maintains two instances of Algorithm App and A The former pro- cesses vectors projected onto the subspace defined by P H. while the latter handles the vectors projected onto the orthogonal subspace. Therefore, the input to A is A₁ = AP, PTP and the input to ApD is A₁ A A, A(I PHPP) = APHPT H Ultimately, the resulting matrix is a combination of the matrices returned by A%d and ApD specifically denoted as B and B respectively.
Combined with Lemma D.I for each right singular vector iz A, we have
/ A
of A o/ (B,) B
(B (B.)
(47)
of - 7 (B.)
(48)
of AT [B BL
(49)
2 Σ of 1- P P P. T.)
(50)
(E
First, observe that since A is allocated my x d space for the matrix A with rank at most my, by the error guarantee of Frequent Direction algorithm (Fact 2.2). it guaranteed that iy A ATA,0 of (B TBU 0.
Second, note that (P Uz is the inner product, between the projected vectors ūn and dj to the subspace H specified by the predicted frequent directions, and that "P is the inner product, between the projected vectors in and di to the orthogonal complement of H.
22

---

Published as a conference paper at ICLR 2025
In particular, when the machine learning oracle makes perfect predictions of 01 ,,,..., ,in.,,, i.e,, W1 ......, Wmz = Umg, then for each i, either U or "
U will be zero.
Therefore, holds that B'
of (L1)
(51)
Further, by the property of Frequent Direction algorithm App- ATAL- _ the projection of A to the subspace spanned by the right singular vectors tm Ud still has right singular vectors Um tl........ Ud. associated with singular values mmttl It follows that
= 0. And since
0 of (ATA BBB
(52)
A A1 (B.)
(53)
of A
(54)
d3 > mL
(55)
0 js mL
Therefore, the weighted error is given by
Err(ArD)
(A
BBB
(56)
<Eid
o.
(A A - BBB +
Σ
A - BBB) (57)
A
F
d
-ATA-B'BI
(58)
||A||
2
i
+1
Σ
o
of
(59)
|
2
d
| 2 F I-lnd
1
(60)
i. In d
1 iimp+1
||||
0
(61)
my +
dIn
Noting that my (m) finishes the proof of upper bound.
Lower Bound for Theorem 3.4 The proof of the lower bound follows the same approach as the one
for Theorem 3.2 in Appendix
Assume that A consists of standard basis vectors é Es E Rd. Let f(ē,) denote the number of occurrences of in A. Without loss of generality, assume that f(e)) 2 ... 2 f(ea). In this case, we have ((,) = of and Eie(a f(() = Eneea of = ||A|| = n. Further, we can then view the B maintained by the Frequent Directions algorithm as an array of m buckets.
Now the setting is exactly the same the Misra- Griee algorithm. Consequently, the constructive lower bound proof from Theorem 3.2 directly applies to learned Frequent Directions.
We next prove Lemma D.1
Proof of Lemma D.1
First, observe that
AT A A F (A + (A + +AJE
(62)
=f + O AT A L AAAAAAAFFFAA
(63)
23

---

Published as a conference paper at ICLR 2025
It suffices to show that
Σ of P *EId
(64)
Note that
A'A T= o' (PPP)))) ( (A(T- -S(T-PAI -
(65)
- -AAAIPPA PHPPT (I- H A" AP = ALE
(66)
(67)
Hence, it remains to study x" A 1 Af AAA E. Keeping expanding one of them
A'A E (I PHP P
(68)
[I Σ
PHPTET
(69)
iE|d
= =Σ of (ū, (I - PHPT)E (L. E
(70)
iE(4
Since PHP7 P H
if AAALE Σ of (6. PTPP
(H.P
(71)
iE(d
Σ of P P D (P PT
Eot
(72)
<E(d
24

---

Published as a conference paper at ICLR 2025
E CONSISTENCY/ROBUSSINSS TRADE OFFS
If the predictions are perfect, the sketch B output by Algorithm satisties that B 3 A A. This property in particular gives the quantity F' B"Br B B = O, we get that the error B Bug प. A A i I of for any of the singular vectors ūj A
< if A Ar for any vector H and as further
(and with perfect predictions the errors on the predicted singular vectors are zero). Unfortunately, with imperfect predictions, the guarantee that B z A A is not retained. To take a simple example, suppose that d 2 and that the input matrix A (1,1) has just one row. Suppose we create two frequent direction sketches by projecting onto the standard basis vectors and eg and stack the resulting sketches B₁ and B2 get sketch matrix B. It is then easy to check that B is in fact the identify matrix. In particular, if i = 62, then |B 1 = 2 whereas | showing that A A B is not positive semidefinit. The absence of this property poses issues in proving consistencyyrrobuttees trade off's for the algorithm. Indeed, our analysis of the classic frequent directions algorithm under Zipfian distributions, crucially uses that the error incurred in the light directions हū for i 2 is at most of.
0
In this section, we address this issue by presenting a variant of Algorithm@jhat does indeed provide consistency/robustnes trade-off's with only constant factor blow up in space. To do so, we will maintain three different sketches of the matrix A. The first sketch is the standard frequent directions sketch produced
sketch Liberty (2013) in Algorithm [] the second one is the eaaming-auggenttn by Algorithm 2 and the final sketch computes an approximation to the residual eπror ||AA [A]x 2 within a constant factor using an algorithm from et al. (2024). Let B, be the output of Algorithm on input A and B2 be the output of Algorithm 2 on input A. Suppose for simplicity that we knew [A] I| exactly. Then, the idea is that when queried with a unit vector Hf we compute ||Br=l|
||A
and |B these are within 2 llA [A of each other, we output ||Ba as the final estimate of of A A. otherwise, we output || The idea behind this approach is that in the latter case, we know that the learning-based algorithm must have performed poorly with error of
m
least |A and by outputting the estimate from the classic algorithm, we retain its theoretical
guarantee. On the other hand, in the former case, know that the error is most 3 ||A-(A) but could be much better if the learning augmented algorithm performed well.
m k
To state our the exact result, we recall that the algorithm from Li et al. (2024) using space (A22/=*) maintains sketch of A such that from the sketch we can compute estimate a such that |
[A < a < (1 + +) A [1]. We denote this algorithm Ares (k, e), Our final algorithm is Algorithm for which we prove the following result.
Theorem E.I. /Worst-Case guarantees] For any unit vector T, the estimate I of || returned
by Algorithm satisfies
AF - r min (I|AT] [|| |A - [A]& m k
In other words, the Error of Algorithm 3 is asymptotically bounded by the minimum of Algorithm and the classic Frequent Direction algorithm.
Proof.
Suppose first that || 3 Moreover, by the approximation guarantees of Ares and ARD.
B B < 2a. Then || - r = ||| - |
S Sa + 2a S 6 IA - [
|| 2 - B2 < | - | | + B
|
k
as desired.
Suppose on the other hand that ||| |B | > 2o. Since by Fact 2.2 we always have that || - || <
||-|AA) < a, it follows that ||| - || a
WA m
m-k
But since in this case, we output [BFil the estimate of the standard frequent direction, we again have by Fact 2.2 that |
|2r < |A as desired.
We note that the constant in the theorem can be replaced by any constant > 3 by increasing the space used for Ares-
25

---

Published as a conference paper at ICLR 2025
Algorithm 3 Robust Learning-based Frequent Direction ARLED
1: Procedure INITIALIZATION
2: Input: sketch parameters m, E : learned oracle parameter m, s.t., my, I m. predicted
frequent directions P [
Um RRxmm, query vector J.
3: Initialize an instance Algorithm Arp.inallializaatimmmn 0.5 m, d)
4: Initialize instance of Algorithm ALap.initialization (m, 0.5 m, d)
5:
Initialize the residual error estimation algorithm Li ct al. (2024) Ares (m 2, 2,
6: Procedure UPDATE
7:
ArD. update(A A;)
8:
ALED ALFD.uddate update( (A;)
9:
Ares updatee As)
10:
Procedure RETURN
11:
B1 Arp-relurn()
12:
B2 + AFD.return()
ag Area.
14:
15:
return (B,, B2
Procedure QUERY(E)
17:
if' B2
B B
<
2a then
return |2
19:
else
return
|
E.1
THE ERROR OF NON- PON-PERFECT ORACLES.
We will now obtain more fine-grained understanding of the consistency/rooustnees trade off of Al- gorithm 3 Consider the SVD) Eie(d प.ūū Let A AP, P be the matrix of projecting the of A to the predicted subspace. and A = A A A(I PHP7) Recall that P consists of orthonormal column vectors WI...., Wms Rd. Extending this set of vectors to form an orthonormal basis of [R:; WI...., Um2 Wm Wmm+l1...... Wh. Write P = [+ projection matrix to the orthogonal subspace.
We] the
Based on Lemma D.I for each vector, we can write
# AATAR= &'AA 2 Σ of (PT PT (P P
(73)
xE[d]
To understand the significance of Lemma D.I note that our algorithm attempts to approximate the first two terms (through either exact or approximate Frequent Direction sketches), but ignores the final one. Therefore, regardless of how successful it is in approximating x² "''AAA AfAAT + Af I we will have EvEra of (PT TTT) ( 5) occurring as an additional added error.
Note that (PT JT) is the inner product, between the projected vectors it and iī, to the sub- space H specified by the predicted frequent directions, and that (P' pf 17 is the inner product, between the projected vectors U, and T to the orthogonal complement of H. In particular, if P consists of a set of correctly predicted singular vectors of A, then for any i, either PT or pT Jj will be zero and in particular the additional added error will be zero. In order to obtain an algo- rithm performing as well if had perfect predictions, it therefore suffices that the predictions are accurate enough that
A [A]&1
Σ of (P P REld
(PT PT EO
(74)
m
26

---

Published as a conference paper at ICLR 2025
To obtain general smoothnesssrrbusttesss trade off, plug into Theorem E.1 Doing so the setting of Theorem 3.4 where the singular values follow a Zipfian distribution, we obtain the following immediate corollary.
Corollary E.2. Consider the setting of Theorem 3.4 but where we run Algorithm 3 instead of Algorithm and where we make no assumptions on the quality of the oracle. Then the error Err(ARLFE is most
0 AA
+2 iE|d
ΣoJ jEId
(In (In
7n
|
but also always bounded by
In m of
(
In m
| 2
in
dIn))²
We finish by showing an example demonstrating that even with very accurate predictions, the extra added error be prohibitive. Assume that the input space is R and the input vectors are either 0) or (0, 1). Assume that of = 10", o3 = 1., 01 = (1, and 2 = (0,1).
In this case, assume that my 1. A perfect Pи should be Pи (1,0), but will assume that the actual prediction we get is a little perturbed, say we change it to PH = (cos Too sin r Therefore, P (sin 100
0o8 )
Σ of (P U. P (T kE(2
(PT H
1T = 10 (cos
100'
COS
100'
(sin
100"
sin
100
(75)
1 100'
1
+ 1 (sin
(- cos
sin
(76)
100"
100"
100'
2 10 cos
2
sin
2
(77)
100
100
23 107
10
(78)
1002
In general, assume that Pи = (cos 0, sin 0) for small 0. The
Σ of P UT)) (P P úi) = of cos² sin2 o70²
(79)
EE
So we need 0 As 1/ym, m, order that this bound is comparable with the normal FD bound.
27

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTS
In this section, we include figures which did not fit in the main text.
F.1 DATASET STATISTICS
CAIDA Log-Log Frequencies
AOL Log-Log Frequencies
10a
10a
Frequency
Frequency
10
10a
10a
10a
100
10a
10'
102
10
10P
10
10"
10a
102
10
10
10
Sorted Elements
Sorted Elements
Figure Log-log plot of frequencies for the CAIDA and AOL datasets.
Hyper Log-Log Singular Values
Logo Log-Log Singular Values
10a
10a
Singdar Value
10'
Sinuuar
80*
202
10a
10P
10'
10a
10a
16
10
102
10a
Sorted Index
Sorted Index
Figure 4: Log-log plot of singular values for the first Hyper and Logo matrices.
Eagle Log: Log Singular Values
102
Singulor Value
10-1
10-7
10
16a
10'
10'
10*
Sorted Index
Figure 5: Log-log plot singular values for the first Eagle and Friends matrices.
F.2 NOISE ANALYSIS IN FREQUENT DIRECTIONS
We present the following figure for the
28

---

Published as a conference paper at ICLR 2025
Noise Analysis (Rank: 100)
10*
FD
Leamed (ours)
10a
10
Nolse 10-2
Figure 6: Analysis of prediction noise in matrix streaming on the first matrix of the Logo dataset. The rank of the algorithms is 100. The baselines of Frequent Directions and the true SVD are shown as dashed lines. Our learned Frequent Directions algorithm uses perfect predictions corrupted by matrix of Gaussian noise with standard deviation a /vd where a is displayed as the amount noise the horizontal axis. The linear relationship the log-log plot indicates that the performance of our algorithm decays polynomially with the amount noise.
F.3 ADDITIONAL FREQUENT DIRECTIONS EXPERIMENTS
We present plots error/rank tradeoffs and error across sequences of matrices with fixed rank for all four datasets Hyper, Logo, Eagle, and Friends.
F.3.1 HYPER DATASET
Rank: 20
Rank: 200
FD
Learned
10-4
Learned
Ereer
10
10-4
10
30
80
50
70
Matrices
Matricos
Figure Frequent directions results on the Hyper dataset.
F.3.2 LOGO DATASET
Rank: 20
Rank: 200
10a
SVD
10a
FD
Learned FD lours)
Learned FD (ours)
10'
10*
10c
10:
165
4
10
12
14
16
18
2
10
12
14
16
18
Matrices
Matrices
Figure 8: Frequent directions results the Logo dataset.
29

---

Published as a conference paper at ICLR 2025
F.3.3
EAGLE DATASET
Rank:
Rank: 200
10
10
Ener
10
10
10-4
10
10-9
FD
Learned (ours)
Learneed FD (ours)
8
12
36
18
0
10
14
18
Mutrices
Matrices
Figure 9: Frequent directions results on the Eagle dataset.
F.3.4 FRIENDS DATASET
SVD
10a
SVD
10*
(ours)
10
Enerr
10a
Figure 10: Frequent directions results on the Friends dataset.
F.4 ADDITIONAL FREQUENCY ESTIMATION EXPERIMENTS
Here, we present all frequency estimation results comparing our Learned Misra-Gries algorithm with Learned CountSketch of Hsu al. (2019) and Learned CountSketch++ of of[Aamand al. (2023). We present results both with and without learned predictions. Additionally, we present results both with standard weighted error discussed in this paper as well as unweighted error also evaluated in the experiments of prior work. The unweighted error corresponds taking the sum of absolute errors across all items appearing in the stream (not weighted by their frequencies).
F.4.1 No PREDICTIONS, WEIGHTED ERROR
Error/Space Tradeoff
1e11
Space: 300
C5++ (C=1)
tS+ (Ce1)
CS++ (C-2)
CS+e (C
Weighted Error
CSea (C=5)
Weighted
MG louns)
(ours)
0.4
0.2
500
1000
1500
2000
2500
3000
10
20
30
40
50
Space
Streams
Figure 11: Frequency estimation the CAIDA dataset with weighted error and predictions.
30

---

Published as a conference paper at ICLR 2025
107
ErronSpacc Tradeoff
107
300
C5++ [C+1]
CS++ (C=1)
Valgeaa Error
C5++ (C+5)
CS+e (C-5) NG (ours)
Weighted
MG lours)
2500
Sitr
Figure 12: Frequency estimation on the AOL dataset with weighted error and no predictions.
F.4.2
WITH PREDICTIONS, WEIGHTED ERROR
Error/Space Tradeoff
Space: 300
1.4
CS++ [C=1]
C (C-1)
CS+4 (C=2)
ES++ (C=2)
1.0
Weighted Error
(C-3)
MG lours)
MG (ours)
0.6
0.6
0.4
0.2
500
1000
2500
3000
30
50
Stre
Figure 13: Frequency estimation on the CAIDA dataset with weighted error and learned predictions.
Error/Space Tradeoff
Space: 300
C5+4 [C-1)
1S+ (C-1)
C5+4 (C-2)
US++ (C=
CS++ (C+5)
WWiggttee Ererr
(C=5)
Weighted
MS lours)
MG (ours)
1000
1500
2000
2500
3000
10
20
30
70
Streams
Figure 14: Frequency estimation on the AOL dataset with weighted error and learned predictions.
F.4.3
No PREDICTIONS, UNWEIGHTED ERROR
1e10
Error/Space Tradeoff
Space: 300
C5++ (C=1)
US+e (Cm CS+e (C=2)
C5++ (C-2)
Unavighted Enerr
Unwoighted
MG lours)
(ours)
500
1000
1500
2000
2500
3000
10
20
30
40
50
Seace
Streams
Figure 15: Frequency estimation the CAIDA dataset with unweighted error and no predictions.
31

---

Published as a conference paper at ICLR 2025
167
Error/Space Tradeoff
107
Space:
3.0
ts
C5++ [C+1]
C5++ (C=1)
Unweented Enor
2.5
Unwegitted Errer
0S+ (C-2)
C5++ (C+5)
2.0
CS+ (C-5) MGJouus)
MG lours)
1.5
1.0
0.5
0.0
Figure Frequency estimation on the AOL dataset with unweighted error and no predictions.
F.4.4
WITH PREDICTIONS, UNWEIGHTED ERROR
2e10
Erron/ppace Tradeoff
1=10
Space: 300
c5
CS
2
CS++ (C=2)
Unweighttd Error
CSee (C-
C5++
(C-5) (ours)
Unaeionted
MG lours)
500
1000
1500
2000
2500
3000
10
20
30
40
50
Space
Streams
Figure 17: Frequency estimation on the CAIDA dataset with unweighted error and learned predic- tions.
Error/Space Tradeoff
Space: 300
3.0
2.5
CS++ (C=1)
CS+e (C=1)
CS+4 (C=2)
Inwwighted Erear
cS+a (C=2)
2.0
CS++ (C=5)
(C=5(
Unwderted
MG lours)
MG (burs)
1.0
0.5
0.5
0.0
0.0
1000
1500
2500
3000
20
50
70
80
Streams
Figure 18: Frequency estimation the AOL dataset with unweighted error and learned predictions.
32


Reviews:
[{"review_id": "dufgQGT8Ea", "reviewer": "Reviewer_rWSV", "summary": "The paper discusses the problem of online learning of frequent directions given a stream of vectors. In particular, they also consider the learning-augmented problem, where one has access to a predictor that provides estimate of which directions are frequent. They also address the problem of frequent items, since this a special case of the frequent direction problem, where item i is associated to the standard vector e_i.\n\nThe contribution of the author is two-fold. They first study the problem of frequent directions using power-law distributed data (i.e., in this case the singular values of the input matrix A, that is given online row by row, follow a power law or Zipfian distribution). To this goal, they analyze the Frequent Direction Algorithms (Ghashami et al., 2016) in this setting (Theorem 3.3). Additionally, they also shows that if one has access to a perfect learning oracle, the expected error of the algorithm can decrease. As a special case, they also shows that a variation of this algorithm (based on the Misra-Gries algorithm, that is the 1-dimensional variant of the frequent direction algorithm), allows to solve the (learning-augmented) frequent item problem with Zipfian distribution law of the frequency. In particular, they retrieve the results of the previous work with a simple deterministic algorithm, compared to previous work that is based on CountMin sketch and is randomized.", "questions": "See weakness.\n\nThe lower bound of Thm.1  and Thm.3 seems specific to the algorithm that is used. Is there any lower bound that applies for any algorithm, given an input sequence that satisfies the Zipfian law assumption?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is within the algorithms with prediction framework, that was subject to a considerable amount of research in the last years. The paper studies a new problem in the algorithms with prediction framework: learning-augmented frequent directions. \n\nOne of the main strength of the algorithm is that they are also able to recover, with a simple algorithm, results of the previous work for the special case of frequent items.\n\nAnother strength of the paper is that it is extremely well-written. The technical section is easy to follow. The results look correct.\n\nDue to the simplicity of the algorithm, clarity of exposition, and the relevance of the results, I believe this paper provides a good contribution.", "weaknesses": "The paragraph on robustness 361-366 is not clear. It seems that they constraint the oracle to provide still a lot of valuable information. I believe it would be better to provide instead sufficient conditions required on the oracle to still obtain the approximation guarantees of Thm 3.4 (or resp., Thm 3.2). It seems to me that appendix E shows that one can accomodate an arbitrary bad oracle (Theorem E.1) using a modification of the algorithm. Unless I am missing something, I believe this is more important than the robustness paragraph 361-366, and should be maybe included in the main paper.\n\nPages 15-28 contains a sequence of plots with virtually almost no-text (Figure 53 seems a very high number of figures). I think it would be better to select some plots that are then discussed with text to express a message, or summarize the information in a different and more concise manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "vXYPvXRmnk", "reviewer": "Reviewer_TCrD", "summary": "This paper presents a theoretical and empirical study of learning-augmented streaming algorithms, focusing on frequency estimation and its extension to matrix streaming. The authors introduce a learning-augmented variant of the Frequent Directions algorithm and demonstrate both theoretical improvements and practical benefits when combining learned predictions with traditional streaming algorithms.", "questions": "1. Is there a fundamental trade-off between space usage and prediction accuracy?\n2. How does the performance vary with different stream lengths?\n3. How does the approach scale to very high-dimensional data?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a clear theoretical analysis of both learning-augmented Misra-Gries and Frequent Directions algorithms. Achieves state-of-the-art bounds for learning-augmented frequency estimation with a simpler, deterministic algorithm\n\n2.  Successfully extends learning-augmented techniques from frequency estimation to matrix streaming\n\n3. Comprehensive experimental evaluation on real-world datasets. Shows 1-2 orders of magnitude improvement over baseline algorithms and very close to SVD algorithm which is memory intensive.", "weaknesses": "1. Limited diversity in the prediction models used. More comparison with other learning-augmented streaming algorithms would strengthen the evaluation\n\n\n2. Could benefit from ablation studies on prediction quality vs. performance", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "ZRFhoKF0UA", "reviewer": "Reviewer_CHdX", "summary": "This paper studied the learning-augmented frequent directions, which is a natural generalization of the frequency estimation problem in a stream of elements. The frequency estimation problem asks the following question: we are given a stream of $n$ items that below to at most $d$ distinct elements, what is the additive error we could get for the estimation with a limited memory $m\\ll \\min(n,d)$. Learning-augmented frequency estimation, which additionally assumes a (potentially erroneous) oracle that returns a predicted frequency of each element *and* the Zipfian distribution of the elements, has been extensively studied in recent years. The state-of-the-art error bound was given by ACNSV [NeurIPS’23] for frequency estimation.\n\nThis paper asked if we want to generalize the frequency estimation in high-dimensional applications. Here, a natural setup is to have multiple $d$-dimensional vectors $A_1$, $\\cdots$, $A_n$. Furthermore, the following aspects are defined for the generalization.\n- To generalize the notion of frequency estimation error, the paper used a notion of the error of vector projection to the singular vectors of the matrix formed by $A=[A^T_1, A^T_2, \\cdots, A^T_n]^T$. \n- To generalize the distribution assumption of Zipfian distributions, the paper used the notion of the square of the $i$-th largest singular values of the matrix $A$ being inversely proportional to $i$.\n- To generalize the frequency prediction, the paper introduced an oracle that directly predicts orthogonal frequency directions, which are the ``right rows’’ an optimal algorithm should have used.\n\nThe paper showed that (learning-augmented) frequency estimation can be reduced to the (learning-augmented) frequent direction problem defined above. This justifies the claim that this problem is a *natural* extension of the frequency estimation counterpart.\n\nThe paper obtained a frequent direction algorithm with $O(\\log{m}\\cdot \\frac{\\log{d/m}}{\\log^{2}{d}}\\cdot \\frac{\\||A\\||^2_{F}}{m})$ additive error for $m$-memory algorithms even without predictions (by taking advantage of the ‘Zipfian’ distribution of the matrix).  For algorithms with predictions, the error bound becomes $O( \\frac{1}{\\log^{2}{d}}\\cdot \\frac{\\||A\\||^2_{F}}{m})$, assuming the prediction is at least accurate on a constant fraction of the predicted frequency directions. The paper further generalized their results to the frequency estimation problem, showing that it is possible to recover the best bound for the frequency estimation problems using the new algorithm.", "questions": "In the experiment, you used SVD as a benchmark. Can you give the error bound for storing all vectors in $A$ and run SVD? In particular, does the error also scale with $\\||A\\||^2_{F}$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "My overall opinion of this paper is quite positive: it is well-motivated and well-written, and it contains quite some results that could be interesting to a wide range of audiences both in machine learning and algorithms in general. Barring some lower-order exposition issues, the paper is generally easy to follow, and the technical idea, while simple, is quite neat. As such, the paper is a clear acceptance from my perspective.", "weaknesses": "I do not see any major weakness in the paper. Some comments for expositions:\n- The column indexing of the SVD in algorithm 1 is not as clear as it could be. I suggest having a notation section that lists all the notations you use in the paper.\n- Calling the lemma statement of Liberty [Arxiv’22] a ‘fact’ is perhaps overly trivializing the significance of the lemma. I would say to call it a ‘proposition’ (I know it’s a one-line proof, but still :)).\n- The discussion about the robustness in the main paper is perhaps too sketchy. I understand that you have a more detailed discussion in the appendix; however, I think it’d be helpful if you could expand the discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "LKOXUMsoyY", "reviewer": "Reviewer_uku3", "summary": "This work revisits the problem of learning-augmented frequency estimation and provides simplified, improved, and generalized results. In the classic frequency estimation problem, we wish to estimate the number of occurrences of an item in a stream up to some small error. In the “learning-augmented” setting, we assume that some oracle tells us the most frequent items, which allows for better algorithms. Furthermore, the stream is also assumed to follow a Zipfian distribution, that is, there is a clear choice of “most frequent items” so this assumption is actually useful. Prior work on this subject, such as the work of Hsu et al. (2019), uses randomized algorithms based on CountMin, CountSketch, and related constructions. The current work shows that the Misra-Gries algorithm, a classic deterministic algorithm for frequency estimation, actually obtains sharp guarantees for this problem. Furthermore, this work also generalizes this to the vector setting, where the stream items are vectors and the desired output is estimates to the singular vectors of the stream viewed as a matrix. In this setting, Misra-Gries corresponds to the frequent directions algorithm, and the authors obtain similar guarantees.", "questions": "None at this time.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is remarkably well written. Every time I wanted to ask a question to the authors, I felt like it was almost immediately answered in the following text. The contribution is also solid, and gives a clean improvement to prior work on this subject. The experiments were also insightful, and showed how an initial estimate of the top singular values can be used as the “learned frequent directions” for use in the learned frequent directions algorithm. In hindsight, this seems pretty similar to related ideas in numerical linear algebra about using a coarse estimate of the top singular components when designing algorithms for matrix estimation tasks, such as https://arxiv.org/abs/2010.09649 and https://arxiv.org/abs/1511.07263. Connections to such works might be interesting to include.", "weaknesses": "The only complaint is that the paper is pretty much a combination of existing and known ideas. However, it is a high quality implementation of such a study and adds valuable information to this literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)