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

arXiv: https://arxiv.org/abs/2410.10258 · HTML: https://mlsanity.com/paper/2410.10258/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 14 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tiny Machine Learning: Progress and Futures](https://mlsanity.com/paper/2403.19076/) (2024)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions](https://mlsanity.com/paper/2302.03764/) (2023)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Dual-Mandate Patrols: Multi-Armed Bandits for Green Security](https://mlsanity.com/paper/2009.06560/) (2020)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Heavy hitters via cluster-preserving clustering](https://mlsanity.com/paper/1604.01357/) (2016)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Learnability with Time-Sharing Computational Resource Concerns](https://mlsanity.com/paper/2305.02217/) (2023)
- [Reward Imputation with Sketching for Contextual Batched Bandits](https://mlsanity.com/paper/2210.06719/) (2022)
- [Optimal Matrix Sketching over Sliding Windows](https://mlsanity.com/paper/2405.07792/) (2024)

## Built on by (most cited first, 4 of 4)

- [Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces](https://mlsanity.com/paper/2510.19349/) (2025)
- [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](https://mlsanity.com/paper/2606.27917/) (2026)
- [Efficient Linear Bandits via Cluster-Aware Sketching](https://mlsanity.com/paper/2609.27594/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

Linear bandits have become a cornerstone of online learning and sequential decision-making, providing solid theoretical foundations for balancing exploration and exploitation. Within this domain, matrix sketching serves as a critical component for achieving computational efficiency, especially when confronting high-dimensional problem instances. The sketch-based approaches reduce per-round complexity from Omega(d2) to O(dl), where d is the dimension and l<d is the sketch size. However, this computational efficiency comes with a fundamental pitfall: when the streaming matrix exhibits heavy spectral tails, such algorithms can incur vacuous textitlinear regret. In this paper, we revisit the regret bounds and algorithmic design for sketch-based linear bandits. Our analysis reveals that inappropriate sketch sizes can lead to substantial spectral error, severely undermining regret guarantees. To overcome this issue, we propose Dyadic Block Sketching, a novel multi-scale matrix sketching approach that dynamically adjusts the sketch size during the learning process. We apply this technique to linear bandits and demonstrate that the new algorithm achieves textitsublinear regret bounds without requiring prior knowledge of the streaming matrix properties. It establishes a general framework for efficient sketch-based linear bandits, which can be integrated with any matrix sketching method that provides covariance guarantees. Comprehensive experimental evaluation demonstrates the superior utility-efficiency trade-off achieved by our approach.