Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching

This paper addresses the issue of linear regret in high-dimensional linear bandits caused by heavy spectral tails in matrix sketching by proposing Dyadic Block Sketching, a novel multi-scale approach that dynamically adjusts sketch size to achieve sublinear regret without prior knowledge of matrix properties.

The Gist

Imagine you are a tour guide leading a group of tourists (the "arms") through a massive, unfamiliar city (the "decision space"). Your goal is to find the best restaurant (the "highest reward") for the group every single day for a long time.

In the world of Linear Bandits, you don't know the city map. You have to guess which street leads to the best food, try it out, and learn from the result. The more streets you explore, the better your map becomes.

The Problem: The "Too Big to Carry" Map

The city is huge. It has thousands of dimensions (streets, alleys, parks).

• The Old Way (OFUL): To make a perfect decision, you try to draw a complete, high-definition map of the entire city in your head every day. This is incredibly accurate, but it takes forever to update. If the city is huge, your brain (the computer) crashes from the effort.
• The "Sketch" Way (SOFUL/CBSCFD): To save time, you decide to carry a mini-map (a "sketch"). Instead of drawing every single street, you just draw the main highways. This is fast! You can update your mini-map in seconds.

But here's the catch:
If the city has a few "hidden gems" (important details) that are tucked away in the side streets, and your mini-map is too small to capture them, you might miss the best restaurant entirely.

• If you pick a mini-map size that is too small, you might end up wandering in circles for years, never finding the best food. In math terms, this is called "Linear Regret" (you keep making bad choices at a steady, terrible rate).
• If you pick a mini-map size that is too big, you are back to the slow, heavy brain-crash problem.

The dilemma? You don't know how big the city is or where the hidden gems are until you've walked through it. So, how do you choose the right mini-map size before you even start?

The Solution: The "Dyadic Block Sketching" (The Growing Backpack)

The authors of this paper propose a clever new strategy called Dyadic Block Sketching.

Imagine instead of carrying one fixed-size map, you have a magical, expanding backpack.

1. Start Small: You begin your journey with a tiny, pocket-sized map. It's super fast to update.
2. Watch and Learn: As you walk, you keep an eye on your backpack.
   • If the pocket map is getting too crowded and you're starting to lose important details (the "spectral error" gets too high), you don't panic.
   • Instead, you double the size of your backpack and get a bigger map for the next section of the city.
3. The "Dyadic" Magic: You don't just have one map. You keep the old, smaller maps for the parts of the city you've already visited, and you use the new, bigger map for the new territory.
   • Analogy: It's like building a house. You start with a small shed. As you need more room, you add a new room that is twice as big as the last one. You keep the old rooms (they are still useful for the past) and use the new big room for the present.

Why This is a Game-Changer

This method solves the "Goldilocks" problem (not too big, not too small) automatically:

• If the city is simple (low complexity): Your backpack stays small. You stay super fast and efficient, just like the old "Sketch" methods.
• If the city is complex (full of hidden gems): Your backpack keeps growing. Eventually, it becomes so big that it's almost like carrying the full map again. This ensures you never get stuck in a loop of bad decisions (no "Linear Regret").
• No Crystal Ball Needed: You don't need to know the city's size beforehand. The backpack grows only as much as it needs to, based on what you actually see.

The Result

The paper shows that this new "Growing Backpack" approach:

1. Saves Time: It's much faster than drawing the full map every day.
2. Saves Memory: It doesn't take up as much space as the full map.
3. Never Fails: Even if the city is a nightmare of complexity, the backpack grows enough to find the best restaurant, guaranteeing that your mistakes (regret) stay low over time.

In short: They replaced the rigid, one-size-fits-all mini-map with a smart, self-adjusting backpack that grows exactly as big as it needs to be, ensuring you never get lost, no matter how weird the city turns out to be.

Technical Summary

1. Problem Statement

The paper addresses a critical limitation in Stochastic Linear Bandits (SLB) when applied to high-dimensional settings.

• Context: Standard algorithms like OFUL (Optimism in the Face of Uncertainty Linear) achieve a regret bound of $\tilde{O}(d\sqrt{T})$ but suffer from a per-round computational complexity of $\Omega(d^2)$, which is prohibitive for large dimensions $d$.
• Existing Solution: Matrix sketching techniques (e.g., Frequent Directions, Random Projections) are used to reduce complexity to $O(dl)$, where $l < d$ is the sketch size.
• The Pitfall: Existing sketch-based methods (like SOFUL) rely on a fixed sketch size $l$. The paper demonstrates that if the streaming data matrix exhibits heavy spectral tails (i.e., the eigenvalues decay slowly) and the fixed $l$ is insufficient to capture the spectral structure, the spectral approximation error ($\Delta_T$) grows rapidly.
• Consequence: This leads to a vacuous linear regret bound ($O(T)$), effectively causing the algorithm to fail. The core challenge is that the optimal sketch size depends on unknown spectral properties of the data stream, creating a dilemma: a small $l$ risks linear regret, while a large $l$ sacrifices the computational efficiency gained by sketching.

2. Methodology: Dyadic Block Sketching (DBS)

The authors propose Dyadic Block Sketching, a novel multi-scale matrix sketching framework designed to dynamically adjust the sketch size based on the observed data, ensuring a bounded global error without prior knowledge of the matrix properties.

Core Mechanism

• Block Partitioning: The data stream is partitioned into contiguous blocks.
• Dyadic Growth: The sketch size for each block doubles relative to the previous one ($l_0, 2l_0, 4l_0, \dots$).
• Active vs. Inactive Blocks:
  • Active Block: The current block receiving new data rows. It is updated using a base sketching algorithm (e.g., Frequent Directions or Robust Frequent Directions).
  • Inactive Blocks: Completed blocks that are frozen. Their sketches are combined to form the global approximation.
• Error Management Invariants:
  1. Block Size Threshold: A block is closed (becomes inactive) if its accumulated squared norm exceeds a threshold ($\epsilon l_0$) or if the rank of the data within the block exceeds the current sketch size.
  2. Global Error Bound: By concatenating sketches from multiple scales, the method guarantees that the total spectral error $\|X^\top X - S^\top S\|_2$ is bounded by a pre-specified parameter $\epsilon$, regardless of the data distribution.
• Integration with Bandits: The framework is integrated into the DBSLinUCB algorithm. It maintains the sketched covariance matrix and its inverse (via Woodbury identity) to compute the Upper Confidence Bound (UCB) for arm selection.

3. Key Contributions

1. Theoretical Analysis of Linear Regret: The authors formally prove that fixed-size sketching methods (like SOFUL) incur linear regret when the sketch size $l$ is insufficient relative to the spectral decay of the data (specifically when $l < d - T^{1/3-q}$ for locally convex arm spaces).
2. Dyadic Block Sketching Framework: They introduce a multi-scale sketching paradigm that adaptively increases sketch capacity. They prove that this method bounds the global covariance error by a user-defined $\epsilon$, effectively decoupling the regret guarantee from the unknown spectral properties of the stream.
3. Sublinear Regret Guarantee:
   • DBSLinUCB-FD: Achieves a regret bound of $\tilde{O}((1 + \epsilon/\lambda)^{3/2} (d + l_{BT})\sqrt{T})$.
   • DBSLinUCB-RFD: By using Robust Frequent Directions, they improve the bound to $\tilde{O}(\sqrt{(1+\epsilon)l_{BT}T} + \sqrt{d l_{BT}T})$.
   • Crucially, these bounds remain sublinear even in worst-case heavy-tailed scenarios, unlike fixed-size methods.
4. Adaptive Complexity: The algorithm automatically scales its computational cost. In low-rank or light-tailed scenarios, it behaves like efficient sketching ($O(dk)$). In heavy-tailed scenarios, it gracefully degrades to full-rank complexity ($O(d^2)$) only when necessary to maintain accuracy, avoiding the "linear regret" trap.

4. Experimental Results

The paper evaluates DBSLinUCB on synthetic data and real-world datasets (MNIST, cnae-9, MFeat, Spam).

• Synthetic Data:
  • When the sketch size is small ($l=50$) for heavy-tailed data, baseline methods (SOFUL, CBSCFD) exhibit near-linear regret.
  • DBSLinUCB maintains sublinear regret comparable to the non-sketched OFUL, demonstrating its ability to adapt to the spectral structure.
  • Spectral error analysis confirms that DBS keeps the error term $\log(\Delta_T)/\log(t)$ below the critical threshold ($1/3$) that triggers linear regret.
• Real-World Data (MNIST):
  • DBSLinUCB achieves a Pareto frontier superior to baselines.
  • It reduces regret by up to 40% compared to SOFUL at similar resource usage.
  • It achieves 60% time reduction and 80% space reduction compared to OFUL while maintaining regret close to the optimal non-sketched baseline.
• Robustness: The method is robust to parameter choices ($\epsilon$ and initial $l_0$) and performs consistently across different underlying sketching algorithms (FD vs. RFD).

5. Significance

• Solving the "Linear Regret" Pitfall: This is the first work to systematically address and solve the catastrophic failure mode of sketch-based linear bandits in high-dimensional, heavy-tailed settings.
• Bridging Theory and Practice: It provides a practical framework that offers the computational efficiency of sketching without sacrificing the theoretical regret guarantees of full-rank methods.
• Generalizability: The Dyadic Block Sketching framework is modular and can be applied to other online learning problems (e.g., heavy-tailed noise, generalized linear bandits) where controlling approximation error is critical.
• Resource Allocation: It introduces a principled approach to computational resource allocation in online learning, dynamically balancing accuracy and efficiency based on data arrival rather than static hyperparameters.

In summary, the paper establishes that adaptive multi-scale sketching is essential for robust linear bandits, providing a general solution that guarantees sublinear regret regardless of the unknown spectral properties of the streaming data.