Learning-Augmented Frequent Directions

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.

Thank you for pointing out the relevant works. We have updated our references.

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||_F^2?

The SVD benchmark of storing all the vectors in A and then outputting the optimal rank m approximation can be shown to have error $\Theta\left( \frac{ ||A||_F^2}{m (\log d)^2} \right)$ for our weighted error metric, which is asymptotically what our learned algorithm (with a perfect oracle) obtains. The SVD benchmark does not use predictions but requires $\Omega(nd)$ space, so it is not a sensible streaming algorithm.

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.

We agree. Please see the discussion with reviewer rWSV who made a similar point. We will expand upon this in the main text of the final version.

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 :)).

Thanks for the suggestion, we agree and have changed it.

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.

Thanks for the suggestion. We have added a table of notation to the beginning of the appendix.

Thanks for the feedback, and in particular confirming the error bound for running SVD with all vectors. I have no further questions.

I also went across my colleagues' reviews. I am not as concerned about having multiple types of predictions, but it might be an interesting point to discuss.

Finally, a small note on style: please have a unified format of references, i.e, either name et al. (conf year) or (name et al. conf year). Right now, both formats are used in the abstract. Please make sure the format is consistent (and without using \cite{} in the abstract, of course).

Is there a fundamental trade-off between space usage and prediction accuracy?

We are not sure exactly what you mean by prediction accuracy. Here are a few comments on tradeoffs: please let us know if you are asking about something else.

• Regarding tradeoffs between space usage and the error of our algorithms, our main theorems and experiments directly address this tradeoff.

• Our theoretical and experimental results demonstrate that learned predictions yield algorithms with improved tradeoffs between space usage and error. In this sense, for a fixed utility, accurate predictions allow for less space.

• Another tradeoff is the space required to store the prediction model. Though an interesting question, this is not a focus of our work. Rather, our goal is to optimize the space/error tradeoff of streaming algorithms given a black box predictor.

Could benefit from ablation studies on prediction quality vs. performance

Thanks for this comment, this is an important consideration which we did not emphasize enough in the draft. Our existing experiments indirectly show the performance of our algorithm as the prediction quality varies, for both frequency estimation and frequent directions. Our datasets consist of streams which vary with time. We used the earliest data stream to construct our predictor and evaluated the performance of our algorithms across all the later data streams. For example in Figures 2 (a) and 2(b) (the right plots), we use predictions based on the first day’s stream for all the subsequent days. In these plots, as the x-coordinate increases, the prediction becomes increasingly stale since it is obtained from a stream further and further in the past. Nevertheless, the performance of our algorithms remains the best among all the baselines, even as the quality of the predictions degrades.

We took up your helpful suggestion of doing a more direct analysis of how noise affects our algorithm. Please see Figure 6 in the appendix of the revised draft. We artificially added iid Gaussian noise of varying scales to the projection matrix which constitutes our prediction. The figure demonstrates that the performance of our algorithm degrades as some power of the scale of the error.

More comparison with other learning-augmented streaming algorithms would strengthen the evaluation

We compare against the best performing algorithms from prior learning-augmented frequency estimation papers: learning-augmented CS from Hsu et al. and learning-augmented CS++ from Aamand et al. For frequent directions, we propose the first learning augmented algorithm and there are therefore no natural alternatives to compare to, although such alternatives would be very interesting.

Limited diversity in the prediction models used.

We are using the most popular predictions used in prior learning augmented frequency estimation works.

How does the approach scale to very high-dimensional data?

The space of our algorithm has no dependence on $n$, the number of vectors that are arriving in the stream. It only depends on $m$, a user specified number of rows that we want to keep track of. Since the stream consists of $d$ dimensional vectors, we also maintain $m$ vectors in $d$ dimensions. Overall, our algorithm only has a linear dependence on the dimension $d$, in both time and space. This is the best one can hope for, because even reading one vector in the stream takes $\Omega(d)$ time and storing even one singular direction takes $\Omega(d)$ space. Our experiments also demonstrate that our algorithm can scale to large dimensions since we test on datasets with dimensionality up to 1920.

Dear Reviewer TCrD,

Thank you again for your review.

We believe we have thoroughly addressed your main concerns about diversity of prediction models and clearly outlined how our approach scales with different stream lengths and to high dimensional data. If any of your concerns have not been addressed, could you please let us know before the end of the discussion phase?

Many thanks, The authors

The paragraph on robustness 361-366 is not clear ...... I believe this is more important than the robustness paragraph 361-366, and should be maybe included in the main paper.

Thanks for pointing this out. ‘Robustness’ was not a good choice of word for this paragraph since it usually relates to retaining the worst case guarantees from the unlearned setting. Instead, the paragraph illustrates one possible relaxation of the assumption that the oracle is perfect where we still retain the approximation guarantees in Theorem 3.4. The reviewer is correct that Appendix E uses a modification of the Learned Frequent Directions algorithm to accommodate arbitrarily bad oracles (robustness) and we agree that this is important to discuss in the main body. We will update the paper accordingly.

The 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?

This is an interesting open problem. In fact, general lower bounds are currently not known even for the simpler case of learned frequency estimation with the Zipfian law assumption under weighted estimation error.

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

Thanks for the comment, we have made the appendix experiments more concise (and moved them to the end of the appendix) in the updated draft.