Matrix Sketching in Bandits: Current Pitfalls and New Framework

Response to Reviewer MFSi:

Thanks for your detailed review of our work! We sincerely appreciate the time and effort you have invested in reviewing our paper. Your suggestions regarding the presentation and experimental setup have been incredibly valuable to us. However, we have observed that some of your claims, specifically in W4 and Q2, appear to be based on misunderstandings or incorrect assumptions. We hope the clarifications provided below will help facilitate a more balanced assessment of our work.

W1, Q1: About the lower bound

• Kuzborskij et al. (2019) did not impose assumptions on the environment in their regret analysis. In contrast, we assume that the environment determines the chosen arm $x_t$, which follows a distribution over $r$ orthonormal vectors. This assumption is reasonable, as the environment can influence $x_t$ regardless of the policy used by the algorithm. The sketching step introduced by Kuzborskij et al. (2019) remains applicable, as it represents an efficient policy for selecting the arm, independent of the environmental factors.

• We appreciate the reviewer pointing out the typo $\Omega(T^2)$. As the reviewer noted, we would like to clarify that the 'upper bound' of the expected regret using FD may be linear. Previous work provides a regret upper bound of $(1+\Delta_T)^{\frac{3}{2}} \sqrt{T}$, treating the spectral error term $\Delta_T$ as a constant. However, we have found that $\Delta_T$ is strongly influenced by the environment and may scale linearly with $T$. This means that using the sketching method can be risky, as the 'upper bound' of regret may fail to guarantee sublinear growth. This risk is even more pronounced than in the $K$-armed bandit example, because while $K$ is known before learning, we have no prior knowledge of $\Delta_T$ prior to the learning process.

Thank you for your sincere rebuttal, but I still feel suspicious.

Q1, W1) If I understood your sentence correctly, in your setting, the environment is acting 'adversarially' that makes your algorithm choose a certain arm' $x_t$ which is a distribution over $r$ orthonormal distribution. Could the authors present one example environment such that the algorithm is forced to sample $x_t$ over $r$ vectors and induce extreme regret? According to Appendix A, I cannot find your specific adversarial environment which forces the learner to choose $x_t$ as $r$ orthonormal distribution.

I also believe addressing these points will take a lot of work, which is not a level of a minor revision, but a clear rewriting, already with this point.

Response to Reviewer u3gg:

Thanks for your detailed review of our work! We appreciate your insights and have addressed your concerns below.

Q1: Additional experiments

The MNIST dataset is a widely used real-world benchmark in related works. Its high dimensionality and uneven spectral distribution make it particularly well-suited for studying sketching problems. Thus, we believe that our current real-world experiments provide sufficient evidence to support our conclusions. However, we are open to incorporating additional, more diverse real-world datasets in future work as needed.

Q2: Complexity

In real-world applications, relying on single-scale sketching is risky, as the properties of the matrix are often unknown. Although the complexity of our method may increase during the learning process, it has the ability to adapt to potential low-rank structures (as outlined in Section 3.3). This means that when the spectral tail of the matrix is small, our method automatically adjusts to the optimal sketch size, whereas single-scale sketching requires prior knowledge of the matrix properties before learning .

Q3: Improved regret bound

In most online learning literature, hyperparameters must be carefully tuned to ensure a low regret upper bound. However, single-scale sketching introduces an uncontrollable term $\Delta_T$ into the regret bound. Our method aligns with traditional online learning approaches by relying only on a preset constant $\epsilon$ in the regret. As discussed previously, under favorable conditions (e.g., a low spectral tail, which is common in many high-dimensional datasets), our method ensures a sublinear regret bound while maintaining computational efficiency.

Thank you again for your valuable feedback. If you have any other questions, we are looking forward to more conversations.

Response to Reviewer 3oww:

Thanks for your detailed review of our work! We have addressed your concerns and provided clarifications below.

W1: Comparison with previous work

The review comments focus on the differences between our method and previous work. We invite the reviewers to refer to the following sections of our paper, where we separately discuss the limitations of previous work, as well as the complexity and regret:

• In Section 2.2, we discuss the limitations of previous work. They use a fixed sketch size $l$ to control the complexity of the algorithm, but this can lead to linear regret due to the uncontrollable term $\Delta_T$. While $l$ represents a trade-off between time complexity and regret, it remains risky because the spectral error $\Delta_T$ is not constant and increases rapidly over time.

• In Section 3.3, we discuss the space and amortized time complexity of our method. The per-step complexity is addressed in line 405. The previous method performs ideally when the matrix has favorable properties, such as low rank. In Corollary 1, we show that under these conditions, the complexity of our method aligns with the optimal single-scale sketch complexity. Unlike the previous method, which requires prior knowledge of the matrix (e.g., rank $k$) to achieve optimal complexity, our method does not rely on any prior knowledge.

• In Theorems 3 and 4, we discuss the corresponding regret bounds and compare our method with previous work. The main advantage of our approach is that it fixes the order of the regret bound while adjusting the complexity. In contrast to previous methods that fix the complexity but lead to an uncontrollable regret bound, our method provides a more practical and reasonable solution for real-world applications.

W2: Worst-case scenario

In Theorem 1, we demonstrate that when the sketch size $l$ is smaller than $r$, the result is linear regret due to excessive loss of spectral information during sketching. Previous algorithms cannot adapt to this worst-case scenario because the sketch size $l$ is fixed prior to learning, while $r$ is unknown. In contrast, our method dynamically adjusts the sketch size during learning. As shown in Corollary 1, our method maintains an active block with a sketch size $l_{B_t} > r$ after some rounds, thereby achieving sublinear regret even in the worst-case scenario.

W3: Scaling the parameters

The core parameter of our method, $\epsilon$, represents the upper bound of the matrix approximation error. We believe that conducting scaling experiments on this parameter will enhance the insights provided in our article. We have uploaded a revised version of the paper and invite the reviewer to review our experiment on the error parameter in Appendix I.

W4: Theorem 1

We sincerely thank the reviewer for pointing out this typo. Previous work treats the spectral error $\Delta_T$ as a constant term in the regret upper bound $O\left((1 + \Delta_T)^{\frac{3}{2}} \sqrt{T}\right)$. However, we found that $\Delta_T$ is likely not constant but increases with $T$, making the previous method risky. The motivation behind Theorem 1 is to show that when the environment produces a matrix with a heavy spectral tail, the spectral error $\Delta_T$ becomes dependent on $T$, leading to a linear regret upper bound. We will revise the expression of Theorem 1 in the updated version for clarity.

Thank you again for your valuable feedback. If you have any other questions, we are looking forward to more conversations.

Thanks for your detailed review of our work! We have addressed your concerns and provided clarifications below.

W1: Prior work

• The decomposability of matrix sketches is a well-known property in streaming algorithms and has been widely used in the literature (including the “Dyadic Interval framework” mentioned by the reviewer). While our method shares this property, there is a fundamental difference compared to traditional streaming methods. We invite the reviewer to refer to the following sections of our paper for clarification.

  In Remark 2 (line 358), we demonstrate that our method reverts to a non-sketched version in the worst-case scenario, which means it does not rely on space-bounded assumptions. In contrast, traditional streaming methods require a fixed space usage (e.g., the “Dyadic Interval framework” stores at most $l$ rows to maintain a sliding window sketch). Additionally, the Sigmod paper considers a matrix sketching algorithm over the sliding window model, which is unrelated to our work, and we did not cite it.

• The citations regarding matrix sketching techniques are older because these methods have been well-studied for over a decade. For example, the Frequent Directions method was proven to be optimal by Liberty (2013).

W2: Error parameter $\epsilon$

We appreciate the reviewer's insights on the error parameter $\epsilon$, and we glad to provide some discussions and experiments to help readers better choose $\epsilon$. We have uploaded a revised version of the paper and invite the reviewer to review our experiment on the error parameter $\epsilon$ in Appendix I.

From the theoratical perspective, we should assume $\epsilon$ as a much smaller constant than $T$ to achieve the sublinear regret bound. However, during the actual experimental process, we found that it is most effective to set $\epsilon$ slightly larger than the theoretical value for two main reasons:

• In some cases, the upper bounds for both components are not tight. For matrix approximation, as shown in Figure 3, the error upper bound of our method can be much larger than the actual error. Similarly, for the arm selection strategy, a certain level of matrix approximation may not significantly impact the choice of a specific arm, meaning that the regret upper bound can be much larger than the actual performance.
• When $\epsilon$ is set too small, the algorithm's robustness to row norm size deteriorates. For example, when rows with larger norms (such as outliers) arrive, a smaller $\epsilon$ causes the threshold for creating new blocks to decrease, resulting in the algorithm unnecessarily expanding the new blocks. Moreover, we found that reducing $\epsilon$ does not significantly improve algorithm performance, but rather increases time complexity. This is because, at the optimal sketch size, the algorithm’s performance is nearly identical to the non-sketch version. A very small $\epsilon$ only leads the algorithm to quickly revert to the non-sketch version, which limits the potential to optimize time complexity using sketches.

In summary, we have adopted a simple yet effective criterion for selecting $\epsilon$, which is based on the total number of rounds, $T$. We recommend choosing a value for $\epsilon$ that is smaller than $T$, which is straightforward since $T$ is typically known in advance. If prior knowledge suggests that the row norms of certain matrices are relatively large, we can even set $\epsilon$ equal to $T$ (as we did in the synthetic experiments).

W3, W4: Matrix approximation experiment

• In the first experiment, we address the problem of matrix approximation. Note that the upper bound of the error caused by an FD sketch with sketch size $l$ is $\frac{||A||_F^2}{l}$. Since the per-round complexity of our method is dominated by the sketch size of the active block, the computational complexity can be inferred from the slope of the curve. For example, the slope of DBS-FD is initially steeper than that of FD, as the sketch size in the first block of DBS-FD is 16, while the fixed sketch size of FD is 50.

• As mentioned previously, FD performs better than DBS-FD for a small number of rows because, in the initial stages, DBS-FD uses a smaller sketch size (smaller than FD) to approximate the matrix.

W5: Theorem 1

We appreciate the reviewer pointing out this typo. Previous work treats the spectral error $\Delta_T$ as a constant term in the regret upper bound $O\left((1 + \Delta_T)^{\frac{3}{2}} \sqrt{T}\right)$. The motivation behind Theorem 1 is to demonstrate that when the environment produces a matrix with a heavy spectral tail, the spectral error $\Delta_T$ becomes dependent on $T$, leading to a linear regret upper bound. For clarity, we will revise the expression of Theorem 1 in the updated version.

Thank you again for your valuable feedback. If you have any other questions, we are looking forward to more conversations.