Revisiting Matrix Sketching in Linear  Bandits: Achieving Sublinear Regret via Dyadic Block Sketching
Authors: Dongxie Wen
Hanyan Yin
Xiao Zhang
Peng Zhao
Lijun Zhang
Zhewei Wei
Venue: ICLR 2026 Poster (2026)
Keywords: Linear Bandits
Matrix Sketching
Multi-scale Sketching
Primary area: reinforcement learning
TL;DR: We propose a framework for efficient sketch-based linear bandits to address the issue of linear regret that may arise with matrix sketching.

Abstract: 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(d^2)$ 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 *linear 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 *sublinear 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.

Published as a conference paper at ICLR 2026
REVISITING MATRIX SKETCHING IN LINEAR BAN- DITS: ACHIEVING SUBLINEAR REGRET VIA DYADIC BLOCK SKETCHING
Dongxie Wen'
Hanyan Yin-
Xiao Zhang!
Peng Zhao"
Lijun Zhang²
Zhewei Wei
"Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
Natiooaa Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China
dongxie, yinhanyan, zhangx89, zhewei @ruc. eeliiceddu.com (zhaop, zhanglj) j @ladda. nju. edu.cn
ABSTRACT
Linear bandits have become a cornerstone of online learning and sequential decision-making providing solid thcoretical foundations for balancing explo- ration 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 ((d?) to Odd)), where is the dimension and / 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 linear regret. In this paper, we revisit the regret bounds and algorithmic design for sketch-bases linear bandits. Our analysis reveals that inap- propriate 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 sublinear regref bounds without re- quiring prior knowledge of the streaming matrix properties. It establishes a gen- eral framework for efficient sketch-based linear bandits, which can be integrated with any matrix sketching method that provides covariance guarantees. Compre- hensive experimental evaluation demonstrates the superior urility-effiiiecc trade- off achieved by our approach.
INTRODUCTION
Multi-Armed Bandits (MAB) is general framework for modeling sequential decision bocision-making un- der partial information (Herbert, 1952), which has been widely adopted in various applications, including recommendation systems (Zhang et al., 2022). public health surveillance (Bastani et al.) 2021], and green security (Xu et al. 2021). We consider the Stochastic Linear Bandit (SLB), variant of the MAB under the linear assumption (Auer, 2002; Dani et al.) 2007 Abbasi-Yadkoni et al. 2011] Chu et al. 201T). In SLB, at round L, the player selects an arm R. from decision set x 0., where 0, represents unknown coefficients. Utilizing the regularized least squares estimator and upper confi- dence bounds, the seminal work Abbasi-Yadkort al, (201T) propose OFUL algorithm and achieve Ö(dTT) regret bound, where d is the dimension and T' denotes the number of rounds, and the Ō()) n-otntot hides logarithmic factors. Notably, OFUL exhibits a complexity of ((d?) per step.
X C R.. and then observes the reward ra R. The expected reward E[r,
In real-world decision-makee making problems, d can be very large such that traditional linear bandits be- come computationally prohibitive. Consequently, various studies apply matrix sketching techniques to eliminate the quadratic dependence on d and enhance efficiency. Yu et al. (201)) use random projection to map high-dimensional arms to a low m-dimensional subspace, reducing the update
"Zhewei Wei is the corresponding author.

---

Published as a conference paper at ICLR 2026
300
400
SOYUL (1- 50)
ORUT
CASCED & 50)
OPTE
0.50
Regret
300
DISII C3-F3
Regret
200
D&SI CI-CRE
200
100
-0.25
050
-0.50
1500
1000 Namber of Rounds
2000
Number of Rounds
(a) FD-based methods
(b) RFD-hased methods
(c) Spectral error
Figure I: (a), (b): Cumulative regret of the compared algorithms, the proposed methods on synthetic
dataset; (c): Scaling of spectral error with rounds on synthetic dataset w.r.t. sketch size
time from (2dd) to O(md + m²)) Another line of these works is based on a well-known deter- ministic sketching method Frequent Directions (FD), which has been proved to offer better the-
oretical guarantees than random projection under the streaming setting (Lieeryy 2013 Woodruff] 2014 Ghashami et al. 2016). Kuzborskij et al. (2019) are the first to employ FD to sketch the covariance matrix in linear bandits, reducing time complexity to O + (2) while achieving an Ō((1 + (/223 dllog1 + Ar))VT) regret, where
is the sketch size and ÂT represents the spectral error introduced by matrix sketching. Subsequently, [hen et al.] (2020) extended this work by substituting FD with a robust variant, which reduces the order the spectral error Ar and
decouples it from d. yielding a regret bound of Õ((v d loog(1 + + + VIT)
However, sketching baseed methods suffer from the linear regret catasllopocc regret when matrices exhibit heavy spectral tails. Figure Ia [b illustrate this phenomenon through the regret of SOFUL and CBSCFD across different sketch size I. When I 450, both sketch- based methods achieve regret comparable to that of the non-sketched OFUL. In stark contrast, when 1= 50, they exhibit near-linear regret growth, demonstrating severe performance degradation. This discrepancy arises because insufficient size fails to preserve essential spectral information, resulting in substantial spectral error. The possibility of linear regret contradicts the objective of online learn- ing, emphasizing the critical need to manage worst-case regret when employing matrix sketching.
Motivation.
Intuitively, avoiding the linear regret pitfall requires calibrating sketch size to the spectral properties of the matrix. However, existing methods employ single-scale sketching with fixed sketch size throughout learning. This rigid design creates a dilemma: optimal sketch size depends on spectral properties that remain unknown until data arrives, yet must be specified before learning begins. Too small risks catastrophic regret; too large sacrifices computational efficiency-the very motivation for sketching. This inherent tension raises critical question: Can we adaptively adjust sketch size during learning to guarantee sublinear regret without prior knowledge of the streaming matrix?
Contributions. We answer the question affirmatively by developing novel framework for sketch- based linear bandits. Our main contributions are summarized as follows.
Uncovering the impact of spectral error on regret. We revisit the regret bound of sketch-based lin- ear bandits, focusing on the spectral error induced by matrix sketching. Our analysis reveals that existing methods are susceptible to linear regret, primarily caused by an insufficient sketch size.
Controlling approximation error via multi-scale sketching. We propose Dyadic Block Sketching, a novel matrix sketching method that adaptively adjusts sketch sizes across multiple scales to control error. We prove that the global error is bounded by predetermined error Additionally, our method provably tracks the optimal rank-k approximation in the streaming setting, ensuring efficiency in scenarios with low-rank matrices or light-tailes spectra.
Achieving sublinear regret. By applying the proposed sketching framework to linear bandits, we elfectively address the issue of linear regret observed in prior works. Our method ensures a sub- linear regret, even when the streaming matrix is heavy-tailed. Furthermore, robust, scalable, and flexible, achieving diverse regret bounds through various matrix sketching approaches.
The rest is structured as follows. Section 2 revisits sketching in bandits and high- lights current pitfalls. Section 3 and Section present novel multi-scale sketching method and its application to linear bandits. Section 3 reports the experiments. Finally, Section paper. Due page limits, the notations and all proofs provided in the appendices.
Organization.
66 concludes the
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
Notations. Let [n] 21, n), upper-case bold letters (e.g.. A) represent matrix and lower- case bold letters (e.g., a) represent vectors. We denote by || and || || the spectral and Frobe- nius norms of A. We define |A| and Tr(A) as the determinant and trace of matrix A. For positive semi-definite matrix A, the matrix norm of vector æ is defined by ||=||A = Væ Aa. For two positive semi-definite matrices A and B, we use A : B to represent that A B is positive semi- definite. We use A = UEVT to represent the SVD of A, where U, V denote the left and right matrices of singular vectors and Σ d xx) ) is the diagonal matrix of singular values in the descending order. We define A [k] = U₁ Ev V for S rank ()) as the best rank-k approximation
to A, where Us E Ra*k and V Rd are the first & columns of U and V.
2.1 FREQUENT DIRECTIONS
Frequent Directions (FD) (Liberty 2013 Ghashami et al. 2016) is a deterministic matrix sketching x ..... E Rtxd, . [T], FD maintains
technique. Given streaming matrix X (
smaller sketch matrix ((1) E R to approximate ((),, where denotes the sketch size. To process
row It, we first replace the last row of ((t) with æt. Then, we perform SVD on ( i.e., S
U ( (()) Let (t)) diag(O1,..... Oa) and a of. where di is the 1-th largest singular value. Subsequently, we set ((+1)) diag( Vo? ....., Voi σ)) and ( = (())
We provide the pseudo-code of FD in Appendix B.1 FD uses ((d)) space and has an amortized update time of (dl). The fundamental property FD to bound the covariance error terms of the tail eigenvalues of X This property is formally expressed in the following lemma:
Lemma 1 (Claim of Liberty (0013) ). Let (T) be the streaming matrix at round T and X (T)
denote the matrix consisting of the first k singular vectors of (T), Then, it holds that
x (3)
(X(0 x (S(T)) ( |1, S Ar, where AT == min oskel
[k]
(1)
f- k
2.2 LINEAR BANDITS
We first introduce the basic assumptions for the linear bandits setting. At any round t, the decision set X, d is finite and for all Xr, we have ||æ||| S L. The reward for choosing
æ; is
defined as = x; 0, + T/,, where 0, is a fixed, unknown vector of real coefficients, and T/2 denotes the conditionally R-subgaussian noise variable. Moreover, the norm ||0, || is upper bounded by H.
OFUL Abbasi- Yadkori et al. 2011) utilizes regularized least squares (RLS) to estimate 0, as
A AIa + (x!0)² (1) 0, = (A((0)
rsW.:
x, I is the matrix containing all the arms selected up to round and is the regularization. After computing the confidence ellipsoid (8)) the arm selection is based on the upper confidence bound as # arg max fxr T 0, + (x(5) || (A :).
where (0) = [..,,...,
The objective of the learner is to minimize the cumulative (pseudo) regret (Lattimore Szepesvári 2020 over the total rounds, defined as Regrety- = Σi= maX x 0. -1 2, 0..
2.3
SKETCH-BASED LINEAR BANDITS
Note that both the RLS estimator and arm selection require maintaining the inverse of (t which necessitates an update time of ((d2). To address this issue, Kuzborskij et al. (2019) proposes sketch-based method, SOFUL, which reduces the time-consuming step via matrix sketching.
SOFUL produces a FD sketch s(t) E gild of the streaming matrix X By applying Wood- bury's identity, the inverse of the sketched covariance matrix can be written (Ā(1))-
3

---

Published as a conference paper at ICLR 2026
(Ta - (S M ((O). where M (SU)) + ATI) IRix is diagonal matrix that can be stored efficiently. Notably, (A can be updated implicitly using the sketch matrix s(t) and (t),, Since matrix-vector multiplications with ( require O(dl) time and matrix-matre multiplications with M take O(12) time, the update cost is reduced from (id to O(dl + 12).
Current Pitfalls. Despite its improved efficiency, the sketch-based methods introduce errors in matrix approximation, which may lead to a vacuous linear regret bound. We begin by presenting the regret bound of SOFUL, which is characterized in terms of spectral emror.
Lemma 2 (Theorem 3 of Kuzborskij et al. (2019).. Les Regrett denote the regret of SOFUL, where the sketch size is and Dr is defined in equation 7
With high probability, the regret satisfies
SOFUL SOFUL = Ō min { AT) (1 dllo(1 + AT))VT,TT)
Regret
The regret bound of SOFUL is tightly linked to spectral error År, which depends on both the spectral tail of (2) and the fixed sketch size (. This bound is meaningful only when AT = o(T However, as shown in Figure Ic if the sketch size is insufficient (e.g.. .. the blue and orange lines), Ar grows rapidly with the number of rounds, violating this condition and leading to linear regret.
The underlying reason for this phenomenon is that low-regret algorithms must ensure sufficient exploration by estimating all relevant directions in the parameter space, a concept extensively studied by |Banerjee et al. (2023). Specifically, they showed that when the space has locally convex surface, the minimum eigenvalue of the covariance matrix satisfies of = 22(7)) in expectation, where q (0, 1/2] depends the geometry of the arm space. For the convenience of readers, we restate this result in Theorem 5 in Appendix C.I Based on this result, we obtain the following observation:
Observation 1. Assume the decision set is drawn from locally convex arm space X. If the sketch size of SOFUL satisfies < d T3-9, then SOFUL incury vacuous linear regret. Consequently, when the geometry constant q 2 1/3, SOFUL suffers linear regret for any sketch size < d.
Observation indicates that it is difficult to constrain the spectral error by presetting fixed sketch size, since the spectral properties of the streaming matrix are unknown in advance. In some cases, even allocating SOFUL the maximum sketch size fails to prevent linear regret. Similarly, other sketch-based methods, such as CBSCFD (Chen et al. 2020). suffer from the same limitation, as discussed in Appendix [C2] This underscores the necessity of dynamically adjusting the sketch size guarantee worst-case sublinear regret.
The proof is provided in Appendix C.1
DYADIC BLOCK SKETCHING FOR CONSTRAINED GLOBAL ERROR BOUND
In this section, we propose Dyadic Block Sketching, a novel multi-scale sketching paradigm that fundamentally departs from single-scale sketching. Inspired by dyadic frameworks in streaming al- gorithms (Wang et al. [2013; Wei et al.) (0166, our method maintains multiple sketches with varying sizes. A key property is that the global error is governed by which is fixed before sketching.
3.1 ALGORITHM DESCRIPTIONS
High-Level Ideas. As illustrated in Figure partition the streaming data into blocks, with each block approximated by a matrix sketch. For the initial block, we use a relatively small sketch, and for each subsequent block, the sketch size is doubled compared the previous one. The following lemma shows that any sketch satisfying covariance error guarantee is decomposable, allowing us to concatenate the individual sketches to construct an approximation of the entire streaming matrix:
Lemma (Decomposability). Let X [XT ...., IJ with X; Br.xdd and Σ. n14 = If Ifeach X; admits a sketch S, satisfying |X] X, - S. S.lla S (,,,,, then with S = [ST ,..., S. we have || x - T S112 < Ei_ & ||?
Data Structure. The matrix rows are partitioned into blocks, with each block represented as the struct variable B. Each block is associated with a matrix sketching instance, denoted as B.sketch,
4

---

sketch matrices from L, denoted as S and M, which are updated Published as a conference paper at ICLR 2026
Error Management
Matrix Sketching
Inuctive Block
e/2
e/4
f/28
Active Block
Updat
Sketch Row
Block
Block
Block
Block B
New
Approximate
Muti-Scale Sketching
Rows
Data Row
22 13
2--1
Illustration for Dyadic Block Sketching. For each inactive block i [B - 1], the sketch covers the data from fi-1 to 4. For active block B, sketching updates are performed on the new rows. In Algorithm I I* represents the active block B, and L denotes the list of inactive blocks.
Figure 2:
which covers a segment of consecutive, non-overlapping rows. Each block characterized by two properties: block size and sketch size. The block size is defined as the sum of the squared norms of the rows contained within the block, i.e., B. BlockSizz Exes || The sketch size, B. B.SketchSize, represents the constant sketch size of the sketch matrix associated with the block.
We categorize the blocks into two states: active and inactive. An active block is updated with new rows, while an inactive block remains unchanged. As shown in Figure 2 there is exactly active block at any time. The active block is represented as B', and the list inactive blocks is denoted by L. Moreover, maintain two invariants during the update process for error management:
Invariant 1 (Inactive-Bloce Condition). Each inactive block either has sketch size no smaller than its rank, or block size less than elg, where ly is the initial sketch size and the error parameter.
Invariant 2 (Maximum Number of Blocks). The number of blocks is at most [log(d/l + 1)].
Algorithm presents the pseudo-code of Dyadic Block Sketching. Upon receiving new row we first verify that Invariant | holds. If the number of blocks reaches its upper limit, any error introduced by matrix sketch becomes intolerable, requiring the full preservation of the information. Concretely, we employ complete rank-I modifications to update the sketch.
we update the active block and, when necessary, create a new block. The sketch 8 .ssechh is updated using a chosen matrix sketching method (c.g.. FD or RFD; see Appendix B.1 We introduce Boolean flag willExcessSket. set to True if inserting the incoming row would cause the block rank to exceed the current sketch size, and False otherwise. This flag is easily computed by testing the update of the sketch B' .sketch; for FD, we tentatively add the new row and inspect the shrinking value a: if 0 (unchanged from before insertion) we willExcesss$ke
In Lines
to check the rank condition in Invariant !
temporary copy
False, otherwise to True. Line updates the information of the active block when either the block size remains below the threshold elo or willExcessSket as inactive, append it to L. initialize a new active block with twice the previous sketch size, and then insert the incoming row into this new block.
False. Otherwise, we mark the current active block
In Lines 14 15 we return a matrix approximation for the current streaming matrix. We query the sketch matrices S and M from the active block B*. Since the inactive blocks remain fixed, we can query the combined results
(similar to equation 3) once when block is marked as inactive. Leveraging the decomposability property (Lemma)
we combine the sketches from both the active and inactive blocks as follows:
s
S St
(1
M
S
+AI)
5t
M
5

---

Published as a conference paper at ICLR 2026
Algorithm Dyadic Block Sketching
Input: Data stream {a, J2 initial sketch size lo. error parameter regularization À Output: Sketch matrix ( MO
1: Initialize empty list L and B" "skkttch, set B" BlockSize 0 and B* .SketchSize to
2: for t = 1 to T given z; do
3: if (ength(() 2 [log(d/lo 1)] then
4: Update (5(++)) S(+1) (stO)* ((() + zi using rank- modifications
5: else
6:
Query willExcessSketcd from B .sketch and x;
7:
B' BlockSize || [ e or Ex11EEcesssketch is False then Update .sketch with and set B BlockSize += ||
8:
9:
else
10:
= SSkttchSize and mark B as inactive (appending to C) Initialize new empty B skktchh and set B BBlockSize 0, B .SSktcchSize =
11:
12:
Update B" .sketch with æ; and set B' BllockSize += ||
13:
end if
Query M* from B" .skelch and S, M from the list C of inactive blocks Compute (tt), ( by equation 3
15:
16:
end if
17:
end for
3.2 ANALYSIS
We now analyze the error guarantee and the space-time complexities of our approach. Let X denote the streaming matrix and X the subset rows approximated by inactive blocks. Consider matrix sketching algorithm ALG that achieves covariance error || X - S & || where S the sketch matrix and & constant. Assume ALG requires & rows and Me update time. The following theorem applies to any matrix sketching method satisfying this error guarantee.
Theorem 1 (Dyadic Block Sketching Guarantee). Given initial sketch size lo, error parameter and a single-scale matrix sketching algorithm ALG, our method produces a sketch satisfying
| X
S S11 2c.
(4)
The space complexity is O(d. EnO e and the per-round update complexity is 0 20100
)
2
where = min (log
& To cla
1| with h = rank(X).
The detailed proof is provided in Appendix D.2 Theorem I establishes that the global error is constrained by parameter c, while the complexity depends the choice of ALG and the number of blocks B. The value B grows adaptively during sketching and depends not only on the parameters lo and c, but also on the spectral properties of the streaming matrix (e.g., k and | To illustrate how different ALG yield different complexities, we present the following corollary for FD:
Dyadic Block Sketching for FD. We employ FD Liberty 2013 as ALG for each block in our method. With a given covariance error E, FD requires an amortized cost of μl = OddEE) The following corollary specializes Theorem to FD:
O(I/E) rows and processes updates at
Corollary 1. Dyadic Block Sketching with FD guarantees the error bound in equation 4 with both space complexity and amortized update cost O dlo min(k/lo. 2 21Ix(fz/(cdo)))
Our method provides framework for constraining the global error of matrix approximation by integrating sketches across multiple scales. This mechanism is particularly critical for learning and optimization algorithms that impose strict accuracy requirements, which the single-scale matrix sketching method cannot always satisfy. More precisely, as shown in Theorem T the error of Dyadic Block Sketching is governed by pre-specified parameter e, which can, in principle, be tuned to arbitrarily small values. When a stringent error tolerance is required, such as e < o where aa is the smallest singular value of X, even the largest FD with = d - 1 cannot meet this constraint.

---

Published as a conference paper at ICLR 2026
Furthermore, the active block's sketch size grows dyadically, method closely tracks the opti- mal rank-k approximation. Once it exceeds k, the spectral error the active block vanishes. Note that the full-rank case k d corresponds the edge that triggers rank-1 modifications. This behavior matches the first term in the complexity bound of Corollary and shows that, the low- rank regime, method attains the optimal FD complexity of ((dl).
Remark (Efficient Implementation). The update costs include calculating SVD to obtain ( and performing matrix multiplication to compute ( both of which cost (ddi)), where is the current sketch size. In implementation, the amortized cost can be reduced to O(dl) either by doubling space (detailed in Appendix B.2). or by employing the Su-Eiiensttt procedure (Gu Eisenstat 1993).
4 APPLICATION TO LINEAR BANDITS
In this section, we incorporate Dyadic Block Sketching into linear bandits and propose novel framework, termed DBSLinUCB. DBSLinUCB guarantees worst-case sublinear regret, independent of the streaming matrix, and readily extends to other sketch-based approaches.
4.1 ALGORITHM AND REGRET GUARANTEE
We use FD the base algorithm in Dyadic Block Sketching. First, present the estimator utilized in our approach, followed by the derivation of the confidence ellipsoid, which is essential for both the algorithm design and the regret analysis. Using the upper confidence bound, then propose selection criterion. Finally, we provide the theoretical guarantee on the regret of our method.
We adopt sketch-based RLS estimator, similar to previous work (Kuzborskij et al., Chen al. 2020), with the key difference that we use Algorithm to generate the sketch. Let L E Rexd denote the matrix containing all the arms selected up to round We utilize the sketch matrix ((t) Rie, and M1 approximate X where İB, the current sketch size. The sketched RLS estimator is given by
Estimator:
2019
X(O
x
0. (A")))
(1
Σ
-
(S (00))())))))))
Ds
Confidence Ellipsoid. For the estimator equation derive the corresponding confidence ellip- soid, which is a key component in achieving sublinear regret in the worst case.
Theorem (Multi-scale sketched confidence ellipsoid). Following the assumption of linear bandits in section 2.2 Let B, be the number of blocks round 1. For any 5 (0,1), the optimal weight O, belongs to the set O = (0 E Rd 110 - 0rllaw S 3,(5)} with probability at least where
(6) S R Ball (1 5) + 21
E X
H(X+e)
The proof is provided in Appendix E.1 Importantly, this result departs from the previous single- scale sketched one ((Kuzborskij et al. 2019), Theorem 2). Here, the ellipsoid is constructed by leveraging multiple sketches at different scales. We can then define the selection criterion as
F = arg max x To Br-1(6) -| æeA'
(Āu 11)11
(6)
Complexity. The overall algorithm is summarized in Algorithm 5 The computational cost arises from three components: updating the sketch via Algorithm 1 computing the sketched RLS estimator in equation [5. and performing arm selection in equation 6 Let LB, be the sketch size of the active block round I. Since both equation and equation require computing (Ā(())) we can employ the sketch-based acceleration discussed in Section 2.3 which costs (dd By + +12 Combined with the sketch maintenance cost from Corollary I we obtain a total space complexity of O(d) and
amortized update complexity of O Br 13,)) where In, min (k: 21l (e)o)))
7

---

Published as a conference paper at ICLR 2026
Regret Bound. We demonstrate that the regret bound of DBSLinUCB using FD is as follows:
Theorem 3 (Regret bound of DBSLinUCB-FD), Consider the basic assumptions of linear bandits outlined in Section 2.2 and assume that I. 2 Vx. Let the sketch size of the active block at round t be denoted by lB, S d. Given the error parameter e, the regret of DBSLinUCB- satisfies the following bound with probability at least 1/T:
Regrety =ō (11 (1++)) # (d) VT) )T).
where the constants and logarithmic terms are omitted for brevity. The detailed proof and a concrete upper bound are provided in Appendix E.2 We now provide a detailed comparison of our method with the single-scale sketch- based method SOFUL and the non-sketched method OFUL.
SOFUL utilizes FD with a fixed sketch size, achieving Ō(( + Ar)3/22T)) regret bound. As dis- cussed in Section 2.3 this dependence on the spectral error År introduces a fundamental vulnera- bility that can lead to linear regret. In contrast, DBSLinUCB achieves Ö(E3/2 regret bound, which reduces to Ö(VT) when setting
O(1), matching that of the slower, non-sketched coun- terpart. Crucially, DBSLinUCB dynamically adjusts its sketch size LB, based on the observed data, with the final size Br = min {k, 2 X 1 /cbo( determined by the streaming matrix's 's properties.
Given a target order of regret bound, such Ö(VT), our method can recover the complexity of SOFUL or OFUL. across different streaming data environments. For simplicity, we set lo = 1. When the streaming matrix exhibits favorable spectral properties (e.g., low rank k), the optimal complexity for SOFUL is (dk) since this yields AT O. In this case, by setting || / log k. DBSLinUCB achieves the same regret bound and O(dk) complexity as SOFUL, differing only by constant factors. Conversely, when the streaming matrix exhibits heavy spectral tail with full rank k = d, BBSL.inUB adaptively performs rank-1 1 modifications after certain number of rounds, effectively degenerating to the non-sketched method OFUL. with complexity (dd)) this scenario, our regret bound differs from OFUL's regret bound only by constant factor of 2/22
We therefore view our work as analyzing the trade-off between regret utility and sketching effi- ciency under streaming matrices with unknown spectral properties. SOFUL and OFUL represent the two extremes of this trade-off: SOFUL. is tailored for matrices with favorable characteristics, while OFUL is more effective in scenarios with unsatisfactory properties. DBSLinUCB, positioned between these extremes, provides flexible solution that can swing to both ends of the spectrum and generalizes to a wide range of scenarios. In practical applications, SOFUL is better suited for environments with strict cost constraints, such microcontrollers (Lin et al.) 2023), whereas DB- SLinUCB excels in settings where maximizing efficiency while maintaining accuracy is essential, such in large-scale online recommendation systems (Zhang et al., 2022).
Remark 2 (Practical Guidance of Parameters). The parameters of DBSLinUCB include the error parameter and the initial sketch size lg- The regret bound in Theorem 3 controlled by which allows us obtain regret bounds of different orders by adjusting its value. In particular, setting as a small constant yields the non-sketched Ö(VT) regret bound, as discussed above. More generally, by choosing = O ), one can achieve an arbitrary sublinear regret bound O(T") for any E [0.5, 1). For lo, we recommend selecting a value substantially smaller than d in the absence of prior knowledge about the streaming matrix, thereby ensuring sufficient exploration. In practice, if prior information about the effective dimensionality is available (e.g., an estimate 7), 4o can be chosen as a fraction 7 scaled by a constant. The parameter tuning results are provided in Section
4.2 EXPAND TO OTHER MATRIX SKETCHING METHODS
DBSLinUCB provides a scalable framework for efficient sketch-based linear bandits, capable of incorporating various matrix sketching methods. Robust Frequent Directions (RFD) is another ma- trix sketching technique developed to address the rank deficiency issue inherent in FD. It has been proven to be an ideal sketching method for sequential docision-makinn problems (Luo et al. 2019 Chen et al. 2020; Feinberg et al. 2023). We use the RFD (see Algorithm(3) as the sketching method in A Algorithm] 1 and derive the following regret bound. The proof is provided in Appendix E.3
8

---

Published as a conference paper at ICLR 2026
Theorem 4 (Regret Bound of DBSLinUCB- -FD)).FF...... Consider the basic assumptions of linear bandits outlined in Section 2.2 and assume that L Z Vx. Let the sketch size of the active block round t be denoted by LB. I d. Given the emorr parameter e, the regret of DESLinUCB-RFD satisfies the following bound with probability at least 1/T:
Regrety = (11+ VIB T v Bd
Compared to Theorem Theorem reduces the order of e from 3/2 to 1/2. Apart from logarith- mic terms, decoupling d and e further mitigates the impact of e. Since RFD and FD yield identical error bounds with the same sketch size, DBSLinUCB-FD and DBSLinUCB-RIET complexity expression, though their hidden constants may differ due algorithmic details. Replac- ing FD with RFD is straightforward, but its theoretical analysis is non-trivial. The improved regret bound stems from two key properties: positive definite monotonicity and well-conditioning. both of which are demonstrated under decomposability in Appendix [..4 This is, to our knowledge, the first result establish these properties within the context of multi-scale sketching.
share the same
EXPERIMENTS
In this section, we evaluate the performance of DBSLinUCB on the synthetic dataset and several real-world datasets. The baselines include the non-sketched method OFUL (Abbasi- Yadkori et al.)
2011) and the sketch-based methods SOFUL (Kuzborskij et al. 2019), CBSCFD (Chen al.
2020).
All sketch-based methods employed the efficient implementations described in Remark The ex- perimental setting, additional experiments, and configurations are available in Appendix
Online Regression in Synthetic Data. Inspired by the experimental settings in (Chen et al. 2020 build synthetic datasets using multivariate Gaussian distributions NO, Ia) with 100 arms and d = 500 features per context. The true parameter 9, is drawn from NN0. Iu) and is normalized. We set the sketch size {50, 450} for SOFUL and CBSCFD and the initial sketch size lo 50 for DBSLinUCB. We set the error parameter 8 for DBSLinUCB.
The experimental results presented Figures la and Tb (Section | demonstrate that DBSLinUCB, using both FD and RFD, consistently outperforms corresponding single-scale keetch-based methods. Notably, when = 50, both SOFUL and CBSCFD show significantly worse performance compared to DBSLinUCB, exhibiting nearly linear regret. In Figure Ic. report the trajectory of the spectral error term log( / logt over round We observe that for insufficient sketch sizes (1 = 50, 200), this term crosses the benchmark line of y 1/3, indicating that excessive spectral error leads to linear regret, which aligns with our theoretical analysis. We also evaluate the performance of our method in terms of matrix approximation in Appendix showing its ability to limit spectral error.
300
CIIEOD
275
15c
Thac
20-
2200
225
53
19
10
10000
Space
(a) cumulative regret
(b) running time
(c) Regret vs. Time
(d) Regret vs. Space
Figure 3: (a). (b): Cumulative regret and total running time of DBSLinUCB w.r.t. error parameter on MNIST; (c). (d): Pareto frontiers for regret vs. time and regret vs. space on MNIST, illustrating the uillity-efficiency trade-off between the proposed DBSLinUCB and the compared methods.
Online Classification in Real-worid Data. We perform online classification on the real-world dataset MNIST. The dataset contains 60, 000 samples, each with d = 784 features, and there are M 10 possible labels. We follow the setup in (Kuzborskij et al., 2019), details in Appendix F.I. We first investigate the impact of e and the initial sketch size lo on the performance of DBSLinUCE. Figures 3aland 3h present the cumulative regret and total running time after 2000 rounds. Our results

---

Published as a conference paper at ICLR 2026
indicate that larger values of lead to increased regret but improved computational efficiency. With respect to lo, we observe that larger values yield better regret at the cost of increased runtime. An interesting observation is that when is very small, the regret across different sketch sizes becomes nearly identical. This phenomenon can be attributed to Invariant [ which constrains the number of sketching blocks. Under a small e, the algorithm tends to sketch fewer rows and relies more heavily on non-sketched updates, thereby diminishing the influence of lo on overall performance. Furthermore, Figure 3a shows that for relatively small values of E (e.g., E 2, 4), the actual regret is not necessarily monotonically increasing. This is because constrains the upper bound of the matrix approximation error, while the tightness of this bound may vary with different parameter choices.
We then compare DBSLinUCB variants against OFUL, SOFUL, and CBSCFD. For baseline meth- ods, we vary sketch size E [10, 600) across 10 equally-spaced points; for DBSLinUCB, we eval- uate 10 configurations with E [2, 25] and lo E [50, 200). Figures 33 and 3d present the Pareto frontiers for regret-efficiency trade-offs. DBSLinUCB demonstrates superior performance across both dimensions: it consistently dominates SOFUL with up to 40% regret reduction at compara- ble resource usage, while DBSLinUCB-RED outperforms CBSCFD across nearly the entire Pareto frontier. Notably, method approaches OFUL's optimal regret ( 200) while achieving 60% time and 80% space reduction in certain configurations. A key advantage of DBSLinUCB is its regret- robustness, which consistently maintains regret below 300, whereas single-scale methods like SO- FUL exceed 500 under an insufficient sketch size. Additional experimental results on MNT ST and other real-world datasets are provided in Appendices F33 and F.4
CONCLUSION
This paper addresses the current pitfall of linear regret in sketch-based linear bandits for the first time. We propose Dyadic Block Sketching with a constrained global error bound and provide formal theoretical guarantees. By leveraging Dyadic Block Sketching, we present a framework for efficient sketch- baseeh linear bandits. Even in the worst-case scenario, our method can achieve sublinear regret without prior knowledge of the streaming matrix. The experimental evaluations conducted on both real and synthetic datasets underscore the superior performance of our method.
Our multi-scale sketching scheduling can also be applied to more challenging one-pass bandit set- tings, such as linear bandits with heavy-tailed noise (Shao et al. 2018 |Wang et al. 2025) and generalized linear bandits (Filippi et al.) 2010; Zhang et al. 2025). where the interplay between sketching error and model misspecification introduces additional technical challenges. Moreover, it would be promising to extend the Dyadic Block Sketching paradigm to broader online optimization problems (Luo et al. 2016 2 Zhang et al.) [023 Feinberg al., 2202)), to control worst-case regret un- der streaming constraints. There is one important open question left on how to leverage the adaptive spectral error bound of FD achieve a better allocation strategy for multi-scale sketches (Liberty) 2013). Our current analysis employs the Frobenius- based additive error bound, as the Frobenius norm can be tracked incrementally in the streaming setting. Exploiting the tighter, data-dependent spectral tail bound could enable more aggressive sketch size scheduling and improved complexity- regret trade-offs. Finally, it would be greatly important to further understand the minimal complexity required to achieve given regret guarantee without prior knowledge.
ACKNOWLEDGMENTS
The work was partially done at Gaoling School of Artificial Intelligence, Beijing Key Laboratory of Research on Large Models and Intelligent Governance, Engineering Research Center of Next- Generation Intelligent Search and Recommendation, MOF, and Pazhou Laboratory (Huangpu), Guangzhou, Guangdong 510555, China. This research was supported in part by National Science and Technology Major Project (2022ZD01 14802). by National Natural Science Foundation of China (No. U2241212, No. 92470128, No. 62376275). We also wish to acknowledge the support pro- vided by the fund for building world-class universities (diseiplines) of Renmin University of China, by Engineering Research Center of nexx--Geeraaion Intelligent Search and Recommendation, Min- istry of Education, by Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" Initiative, Public Policy and Decision-making Research Lab, and Public Computing Cloud, Renmin University of China.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work studies algorithmic methods for efficient linear bandits and evaluates them on synthetic data and the public MNIST dataset. It does not involve human subjects, personally identifiable information, or sensitive attributes; experiments use non-identifiable benchmarks and simulated data only. We therefore do not foresee direct risks to privacy or safety. Potential downstream (e.g.. recommendation or allocation) could amplify biases present in third-party data; to mitigate this, encourage practitioners pair our sketching framework with careful dataset curation, bias monitoring, and domain- -apropiapppoprriatee safeguards. Computational demands are modest (we report running times alongside regret to support resource transparency). limiting environmental impact. We affirm compliance with the ICLR Code of Ethics. Evidence of our experimental setup and datasets appears in the paper's experiments section (synthetic and MNIST) and running-time reporting.
REPRODUCIBILITY STATEMENT
We facilitate reproducibility through: (i) full algorithmic descriptions and pseudocode for Dyadic Block Sketching and the underlying FD/RFD sketches; (ii) precise statements assumptions and theorems with complete proof' placed in the appendices; and (iii) detailed experimental settings (data preprocessing, hyperparameters, and evaluation protocol) for both synthetic data and MNIST. Specifically, high-level algorithms and composition formulas are given in the main method section; FD/RED pseudocode is provided in Appendix [.I]] and the paper states that all proofs are included in the appendices, with experimental details collected in Appendix [F] In our submission,
include anonymized artifact implementing DBSLinUCB with FD/RED, configuration files, and seed con- trol reproduce all figures and tables. See method/algorithm details and composition, FD/RFD algorithms, statements regarding proofs in appendices, and experimental details.
USE OF LARGE LANGUAGE MODELS (LLMS)
LLMs were used only as writing assistants for minor language polishing. They were not used for research ideation, mathematical derivations, proof development, code generation. All technical contents were created and verified by the authors. The authors accept full responsibility for all content and have checked that generated text constitutes plagiarism or factual fabrication.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NeurIPS), pp. 2312-2320,
2011.
Dimitris Achlioptas. Datahase-friendly random projections. Proceedings of the 29th ACM VIGACT-SIGMOD-SIGAR Symposium Principles of Database Systems (PODS), pp. 274- 281, 2001.
Peter Auer. Using confidence bounds for exploitation-exxplrraion trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 8233-8262, 2023.
Hamsa Bastani, Kimon Drakopoulos, Vishal Gupta, Ioannis Vlachogiannis, Christos Had- jichristodoulou, Pagona Lagiou, Gkikas Magiorkinis, Dimitrios Paraskevis. and Sotirios Tsiodras. Efficient and targeted COVID-19 border testing via reinforcement learning. Nature, 599(7883): 108-113 2021.
Daniele Calandriello, Alessandro Lazarie, and Michal Valko. Efficient second-order online kernll learning with adaptive embedding. In Advances in Neural Information Processing Systems 30 (NeurIPS), pp. -1400-150.20 2017.
11

---

Published as a conference paper at ICLR 2026
Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust high- dimensional linear contextual bandits. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (ICAI). pp. 2259-4265 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). pp. 208 214. 2011.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. The price of bandit information for online optimization. In Advances in Neural Information Processing Systems 20 (NeurIPS), pp. 345-352, 2007.
Amit Deshpande and Luis Rademacher. Efficient volume sampling for row/column subset selec- tion. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 329-338, 2010.
Vladimir Feinberg, Xinyi Chen, Y. Jennifer Sun, Rohan Anil, and Elad Hazan. Sketchy: Memory- efficient adaptive regularization with frequent directions. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23 (NewrIPS), pp- 586-594, 2010.
Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. Journal of the ACM, 1125:1022-11 2004.
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-1792, 2016.
Alon Gonen, Francesco Orabona, and Shai Shalev-Shwartz. Solving ridge regression using sketched preconditioned SVRG. In Proceedings of the 33nd International Conference on Machine Learn- ing (ICML), pp. 1397-1405, 2016.
Ming Gu and Stanley C Eisenstat. A stable and fast algorithm for updating the singular value decomposition, 1993.
Robbins Herbert. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, pp. 527-535, 1952.
ПÍ Kuzborskij, Leonardo Cella, and Nicolò Cesa-Bianchi. Efficient linear bandits through matrix sketching. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS). pp. 177-185, 2019.
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, and Mikkel Thorup. Heavy hitters via cluster- preserving clustering. Communications of the ACM, 62(8):95-100, 2019.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Edo Liberty. Simple and deterministic matrix sketching. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 581-588, 2013.
Ji Lin, Ligeng Zhu, Wei-Ming Chen, Wei-Chen Wang, and Song Han. Tiny machine learning: Progress and futures. IEEE Circuits and Systems Magazine, 23(3):8-33) 34, 2023.
Haipeng Luo, Alekh Agarwal, Nicolò Cesa-Bianchi, and John Langford. Efficient second order on- line learning by sketching. In Advances in Neural Information Processing Systems 29 (NeurIPS), pp. 902-910, 2016.
Luo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li, and Tong Zhang. Robust frequent directions with application in online learning. Journal of Machine Learning Research, 20:45:1-45:41 2019.
Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming. (2):133-153 1982.
12

---

Published as a conference paper at ICLR 2026
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 152, 2006.
Han Shao, Xiaotian Yu, Irwin King, and Michael R. Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. In Advances in Neural Information Processing Sys- tems 31 (NeurIPS), pp. 8430-8439, 2018.
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luís Torgo. Openml: networked science in machine learning. SIGKDD Explor, 15(2):99600, 2013.
Jing Wang, Miao Yu, Peng Zhao, and Hui-Hua Zhou. Learning with adaptive resource allocation.
In Proceedings of the 41st International Conference on Machine Learning (ICML), pp. 52099- 52116, 2024.
Jing Wang, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou. Heavy-tailed linear bandits: Huber re- gression with one-pass update. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267, 2025.
Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: an experimental study. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 737-748, 2013.
Zhewei Wei, Ge Luo, Ke Yi, Xiaoyong Du, and Ji-Rong Wen. Persistent data sketching. In Pro- ceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). pp. 790-810, 2015.
Zhewei Wei, Xuancheng Liu, Feifei Li, Shuo Shang, Xiaoyong Du, and Ji-Rong Wen. Matrix sketching over sliding windows. In Proceedings of the ACM SIGMOD International Conference Management of Data (SIGMOD), pp. 1465-1488 2016.
David P. Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
Lily Xu, Elizabeth Bondi, Fei Fang, Andrew Perrault, Kai Wang, and Milind Tambe. Dual-mandate patrols: Multi-armed bandits for green security. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI), pp. 11974-14982. 2021.
Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Zengfeng Huang, and Feifei Li. Optimal matrix sketching over sliding windows. Proceedings the VLDB Endowment (VLDB), 1799)2149-2161, 2024.
Xiaotian Yu, Michael R. Lyu, and Irwin King. CBRAP: contextual bandits with random projection. In Proceedings of the 31th AAAI Conference on Artificial Intelligence (AAAI), pp. 2859-2866, 2017.
Tianjing Zeng, Zhewei Wei, Ge Luo, Ke Yi, Xiaoyong Du, and Ji-Rong Wen. Persistent summaries. ACM Transactions on Database Systems, 47:3):11:1-11: 2022.
Xiao Zhang, Sunhao Dai, Jun Xu, Zhenhua Dong. Quanyu Dai, and Ji-Rong Wen. Counteracting user attention bias in music streaming recommendation via reward modification. In Proceedings of the 28th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2022.
(KDD), pp.
Xiao Zhang, Ninglu Shao, Zihua Si, Jun Xu, Wenhan Wang, Hanjing Su, and Ji-Rong Wen. Reward imputation with sketching for contextual batched bandits. In Advances Neural Information Processing Systems 36 (NeurIPS), 2023.
Yu-Jie Zhang, Sheng-An Xu, Peng Zhao, and Masashi Sugiyama. Generalized linear bandits: Al- most optimal regret with one meepass update. In Advances in Neural Information Processing Systems 38 (NeurIPS), 2025.
Zhi-Hua Zhou. Learnability with time-sharing computational resource concerns. National Science Review, 11(10):204, 2024.
13

---

Published as a conference paper at ICLR 2026
Appendix: Contents
14
More Related Works
15
Omitted Algorithms
16
B.1 Pseudo-code of Deterministic Matrix Sketching
16
B.2 Fast Algorithm of Dyadic Block Sketching
17
B.3 Pscudo-code of DBSLinUCB
18
Omitted Details for Section 2
18
Proof of Observation
18
Linear Regret Pitfalls RFD-based Methods
19
D Omitted Proofs for Section
19
D.I Proof of Lemma
19
D.2 Proof of Theorem
20
Omitted Proofs for Section
21
Proof of Theorem
Proof of Theorem
24
Proof of Theorem
26
E,4
Properties of Dyadic Block Sketching for RFD
31
Omitted Details for Section
32
Experimental Sctups
32
F22
Experiments of Matri Approximation
33
More Experiments on MNIST
33
Experiments on Additional Real World Data
34
14

---

Published as a conference paper at ICLR 2026
A MORE RELATED WORKS
Sketch-baae baeechh-assed Online Learning, Sketch-based online learning leverages probabilistic (e.g., ran- dom projections or sampling) and deterministic (e.g., Frequent Directions) matrix sketches re- duce per-update time and memory while preserving essential learning information. In Table [ we summarize the theoretical results of state-of-the-art sketch based linear bandit methods and compare them with our approach. Beyond the linear bandit setting, sketching has been employed to accel- erate second-order online gradient methods (Luo et al. 2016 Feinberg et al. 2023), online kernel learning (Calandriello et al., 2017 Luo et al. 2019), stochastic optimization (Gonen et al. 2
and contextual batched bandits (Zhang et al. 2023). Another closely related direction is CoRE-
Learning (Zoo 2024| Wang al. 2024), which studies the interplay between resource allocation and learnability. In this sense, a sketch-size scheduling policy can be viewed as special case of computational resource allocation during learning. To the best of our knowledge, existing work has almost exclusively relied on single-scale matrix sketching schemes, while systematic investigations of multi-scale matrix sketching scheduling in online learning remain largely absent.
Table 1: Comparison of regret bounds, complexities, and sketching methods for sketch-based linear bandit algorithms. Here d denotes the dimension and I the horizon. For single-scale methods, the sketch size / fixed. For multi-scale methods, the sketch size IB, min 21l (fdo( [o} is dynamically adjusted, where lo is the initial sketch size and k rank(X)
Algorithms
Regret Bounds
Time
Space
Sketching Method
OFUL Abbusi-Yadkori Yadkori et al.
2011))
Ö(dvT) +T/V)
O(d))
((f))
CBRAP Yu et al. 2017)
Ofdi + P))
O(d)
Random Projection
SOFUL Kuzbonkij et
2019
Ø(11 + (1) - Ar))vT)
O(dl)
O(dl)
Single-scale FD
CBSCED Chen
ōl(v/I + dng(( AT) + Var)vir)
O(dl)
O(d))
Single-scale RED
DBSLinU (This
ō((1 + (014+)) Iy,
O(dla))
O(dia,)
Multi-scle FD
DBSLiMUCCBRRD (This work)
O(d
O(diez) Multi-scale RFD
Matrix Sketching. Matrix sketching algorithms are typically designed for the unbounded stream- ing model. In this framework, the algorithm receives rows of a matrix A E Rnxdd sequentially over time. The objective is to maintain matrix sketch structure that produces an approximation matrix B E Igldd with only / rows. The goal is to ensure that the covariance matrix approximation satisfies B A A, meaning that B approximates A well.
Streaming matrix sketching methods can be broadly categorized into three groups: The first ap- proach sampling a small subset of matrix rows or columns that approximates the entire ma- trix (Fricze et al. [2044) Deshpande & Rademacher 2010). The second approach is randomly com- bining matrix rows via random projection. Several results are available in the literature, including random projections and hashing (Achlioptas) 2001: [Sarlos] 2006). The third approach employs deterministic matrix sketching technique proposed by Liberty (2013), which adapts the well-known MG algorithm from Misra & Gries (1982) (originally used for approximating item frequencies) to sketch a streaming matrix by tracking its frequent directions. For further details, we refer readers to the survey (Woodruff 2014).
Multi-scale Sketching. Maintaining multiple streaming sketches at different scales is beneficial for a variety of streaming problems and has been well-studied in the literature. For instance, Waag al. (2013) employ dyadic aggregation structure, expressing a range as a sum of a bounded number of estimated counts. Additionally, multi-scale sketching has been applied to problems such as the heavy-hitter problem (Larsen et al., 2019), the sliding-window problem (Wei et al. 2016 Yin et al.) 2024), and persistent sketching (Wei et al. 2015) Zeng et al., 2022). We emphasize that Dyadic Block Sketching is fundamentally distinct from multi-scale sketching methods studied in streaming algorithms. Multi-scale sketches in classical streaming settings typically focus on capturing statistics over restricted portion of the stream (e.g., a sliding window), and therefore provide relative, data- dependent error guarantees, much like their single-scale counterparts. In contrast, our method must accommodate the entire sequence of actions generated by the linear bandit process and aims to
15

---

Published as a conference paper at ICLR 2026
guarantee worst-case regret. This yields data-independent, absolute error bound at the global level, rather than range-specitte guarantee.
B OMITTED ALGORITHMS
In this section, we present the pseudo-code for deterministic matrix sketching (Appendix B. an efficient implementation of Dyadic Block Sketching (Appendix [B2), and the multi-scale sketched linear bandit framework DBSLinUCB (Appendix B.3
B. PSEUDO-CODE OF DETERMINISTIC MATRIX SKETCHING
Frequent Directions (FD) a deterministic sketching method (Liberty 2013 Ghashami et al. 2016). FD uniquely maintains the invariant that the last row of the sketch matrix, S, is always zero. In each round, new row Dy is inserted into this last row of S, and the matrix undergoes singular value decomposition into UEVT. Subsequently, is updated to / oI V,",, where æ represents the square of the 1-th singular value. Given that the rows S are orthogonal, M = (SS + + remains diagonal matrix, facilitating efficient maintenance.
The Robust Frequent Directions (RFD) sketching technique is designed to tackle the problem of rank deficiency (Luo et al., 2019; Chen et al.) (020). RFD enhances the Frequent Directions (FD) method by maintaining a counter a, which captures the spectral erro.. More precisely, RFD approximates X X by S S aI. The error bound for RFD is equivalent to that of FD, as follows:
Lemma (Theorem of Chen et al. (2020)). Let (() be the streaming matrix at round and S(t) be the sketch matrix and ag be the counter produced by RFD. Define the spectral error
x
A
min k<l
1-
where (1) denotes the matrix consisting of the first k singular vectors of X (T), Then, it holds that [4]
(sS")] T 5(0) + + - (x(1) T
x(0)
S SAT.
Algorithm 2 FD sketch
Algorithm 3 RFD sketch
Input: Data X E RRxxd sketch size reg- ularization A
Input: Data X E <Rxxx sketch size reg- ularization X
Output: Sketch S, M Initialize S <- 0xxd M < 1
Output: Sketch S, .M and counter a Initialize S +- 0 M < 1 1 +-
fort 1 to T do
fort = to T do
Append to the last row of S
Append æ; to the last row of S
Compute [U, E, V] + svd(S)
Compute EU Vl + -vd(SS a
of Update S + V oI V,T
Set
Set of
Update S / al V,T
Update M diag
Set M + diag
x -o
āoox ota
ota
Xta
end for
end for
The pseudocode for FD and RFD is given in Algorithms and 3 a Boolean flag wills 1x11xxcsssket to test the rank condition in Invariant TT. is obtained by applying the update to temporary copy of the sketch. However, when the number of rows cur- rently stored in a block smaller than its sketch size (or dimension d), this test uninformative:
Within our algorithm, we use
In the linear bandit literature, this variant is typically referred to as SCFD (Algorithm 1 of Chen et al. 2020 ) which corresponds to Algorithm 3 in our paper. For consistency, we refer to it as RFD throughout the
paper.
16

---

Published as a conference paper at ICLR 2026
Algorithm 4 Fast Dyadic Block Sketching
Input: Data stream {a, J sketch size lo, error parameter regularization À
Output: Sketch matrix ( (O
1: Initialize empty list C and B .sketch
2: Initialize B -BlockSizc = 0, B .SketchSize = lu
3: for I 1 to 7 do
4: Receive 3;
5: if length((C) 2 [log (d/4- + 1)] then
6: Update ( with rank-1 modifications.
7: else
8:
Query wi wix.xeeskeettchh from Bs.sketch and æ if B" BlockSize + || < c- lo or www.wwceessseeeeeeeccceeeee is False then
9:
Update B" .llloockiize += ||a;,|2
11:
Append H, below B .sketh.
Query S, M from the inactive blocks C
13:
if 1 .sketch have 2 B .SketchSize rows then
Update B .sketch
15:
Query S* M* from B" sketth
16:
Compute ( and M()) by equation
else
Combine g(t)
S*
19:
Combine (1) by equation] end if
20:
21:
else
22:
Set 1 = 10''B".S. .SketchSize
23:
Mark B as inactive and append it to C
24:
Initialize new empty B sk.sefhch
25:
Set 8 BBlockSize = 0, 3 SketchSize = 21
Append H, below B .sketch and update B BlockSize += |
27:
Query S, MM from the inactive blocks C
Combine (*t)
29:
Combine (1) by equation
30:
end if
31:
end if
32:
end for
FD/RFD necessarily yields shrinkage value 0 but no compression would occur. In practice, we therefore skip the test in this regime and set w wrilExceessSketr to True as a sentinel, so bypass rank-check; the block is still updated via simple accumulation, and the block size threshold governs new block generation. Finally, these deterministic matrix sketching methods can be accelerated by doubling the sketch size. More details be found in Appendix B.2
B.2 FAST ALGORITHM DYADIC BLOCK SKETCHING
The computational cost both FD and RFD, as outlined in Algorithms 2 and is primarily de- termined by the singular value decomposition operations. Specifically, SVD must be performed every update, which results in an update complexity of O However, this amortized update cost be reduced to (dd)) by doubling the sketch size, discussed in several works (Liberty) 2013
Luo et al. 2016 Kuzborskij et al. 2019).
In Algorithm [ at round f, with B, blocks, let denote the sketch size of the i-th block. This results in an amortized time complexity of O(d(2, ), due to the standard SVD process in the active block. Additionally, the computation of (1)) via matrix multiplication and inversion requires
17

---

Published as a conference paper at ICLR 2026
Algorithm 5 DBSLinUCB
Input: Data stream (x:) sketch size lo, error parameter e, regularization parameter A, confi- dence parameter 5
1: Initialize a Dyadic Block Sketching instance Sketch(S ()) with parameters lo X,
2: for = 1 to 7 do
3: Get arm set X.
4: Compute the confidence ellipsoid (6)
5: Select H; = max x + (6) || (Ā 1)-1
æEA,
6: Receive the reward Ftt
7: Update Sketch(S(() (1) with 2t by Algorithm
8: Compute (A(0)) -1 = La (s(t)) g())
9: Compute 0: = (A(1) Σ a
end for
( Similarly, we can improve the efficiency of our 1. 1.,.BB.... d (E 1.)²
Dyadic Block Sketching method by doubling the sketch size, as detailed Algorithm
We perform the SVD step only after adding B "SSeetchSize rows. Note that within each epoch where no updates occur, the construction of M can be formulated as
M [M
where Φ ((-1)) and & T.
x (S + a + When the sketching method is FD, is set to O; conversely, when the sketching method is RFD, serves the counter maintained in the RFD sketch.
Given that the size of (t) is at most twice of the B SketchSize, the amortized computation time required for ( is limited to O p.) Additionally, we perform the SVD only after every addition of B SketchSize rows, reducing the amortized update time complexity to (dl..).
B.3 PSEUDO-CODE OF DBSLINUCE
DBSLinUCB introduces an inno- vative framework for sketch-based linear bandits, leveraging the multi-scale sketching technique to compute the sketched covariance matrix. As demonstrated in Theorems 3 and the regret bound of DBSLinUCB is parametrized by offering a regret guarantee that is both controllable and ad- justable.
We present the pseudo-code for DBSLinUCB in Algorithm 5
C OMITTED DETAILS FOR SECTION
we present the proof of Observation which demonstrates that an insufficient sketch size will lead to linear regret. In Section C.2 we discuss how RFD-based linear bandits are also susceptible to linear regret.
In this section, we provide the omitted details from Section In Section C.I
C.1 PROOF OF OBSERVATION
Observation T follows from Theorem 3.3 of Banerjee et al. (2023) which shows that in locally convex arm space (defined in Definition 3.1 of Banerjee et al. (2023) h) the design matrix generated by
any linear bandit algorithm with expected ((VT) (T) regret has a heavy spectral tail. For convenience, restate:
Theorem 5 (Theorem 3.3 of Banerjee et al. 2023 Let X be locally convex space and let GT E E [..a]]] denote the expected design matrix. For any bandit algorithm with expected
18

---

Published as a conference paper at ICLR 2026
regret at most O(yT), there exists (0. such that >a(Gr) = 92(T).
The exponent q depends on the geometry of X (c.g., how well the surface approximates a locally constant Hessian). Since SOFUL essentially sketches the OFUL design-matrix sequence, the spec- tral error term Ar in its regret bound inherits this growth.
Fix sketch size
By Lemma choosing k = 1 - 1 gives
AT
Σ of (x()) 2 (d - (d i=1
where (x(X(T)) are the singular values of ( and o x (T) = Amin Amin X()) (x)))
Taking E[Aa] 2 (d-1) Ad = (2( - 1) T
expectation and using >a(GT) Amio (EE (2)) x ()))) obtain
Lemma gives
Regret, R
SOFUL
Ō min (4 VT, T)).
Thus if dd-73-1 then E 2 T1/ and the bound collapses to the trivial O(T). In particular, when the unknown geometry constant 9 2 1/3, we have E[Ar] ス / for any I d, so SOFUL suffers linear regret even at the maximal sketch size 1 = d 1.
C.2 LINEAR REGRET PITFALLS IN RFD-BASED METHONS
Beyond FD-based approaches such as SOFUL, algorithms based on Robust Frequent Directions (RFD) are also vulnerable to linear regret when the sketch size is insufficient. Similar to the discus- sion in Section 2.3 we recall the regret bound of CBSCFD:
Lemma 5 (Theorem 2 of Chen et al. (2020)). Let R
CBSCFD denote the regret of CBSCFD with sketch size and spectral error Ag defined in equation
7
With high probability,
CBSCFD = - { {(V++ (Vi+dlog() dlog(1 + Ar) + VAT) T}}
Regret
Although CBSCED reduces the dependence on AT compared to FD-based methods, it still degen- erates to linear regret whenever Ar ST(T). In particular, if the sketch size is chosen without knowledge of the spectral properties of the streaming matrix, this risk cannot be avoided:
Observation 2. Let X be locally convex arm space. If the sketch size of CBSCFD satisfies I < 71-9, then CBSCFD incurs vacuous linear regret.
This highlights fundamental limitation of single-scale sketching: any fixed sketch size inevitably ties the spectral error AT to the horizon T, making linear regret unavoidable when the spectral structure of the data is unknown in advance.
D OMITTED PROOFS FOR SECTION
In this section. we provide the omitted proofs for Section In Appendix D.I we prove Lemma of decomposability, which abstracts the key idea of multi-scale matrix sketching. Later, the proof of Theorem is provided in Appendix D.2
D.1 PROOF OF LEMMA 3
Since have X X E1 X T, and T == ΣT_ S.T S.. Therefore
x -
Σ
x X; S S.112 Σ G 1
1=1
and the Lemma follows.
19

---

Published as a conference paper at ICLR 2026
D.2 PROOF OF THEOREM
We begin by analyzing the number of blocks of Dyadic Block Sketching. Let the stream of rows form matrix X E Ra Dyadic Block Sketching partitions the stream into contiguous blocks and maintains dyadically growing sketch size. Concretely, let
X
[x, X
R
where block contains n, rows (X; E Rm.xd) and stores sketch S, We call blocks 0, ....., B inactive and the last block B active. In the setting of matrix sketching, low oow-rank detection is only evaluated once block has accumulated least d rows; in particular, whenever detection is triggered, d. We analyze the following two cases:
the corresponding block satisfies
When the streaming matrix low-rank, i.e., rank(X) exceeds the rank, shrinkage vanishes and the block remains low-rank (i.e., the sketch SB tracks rank k). Equivalently, the last active level B is the unique integer such that
By Invariant |
once the sketch size
2B I < 28
which yields the tight bounds
k log
k
B log
+1
B log(k/|o)]]
When the streaming matrix is full-rank, the above derivation shows that the rank-1 modification triggered at block index B [log(d/lo]], which represents the maximum number of blocks possible in any case. However, when the row norms of the streaming matrix are small or the error parameter is relatively large, the actual number of blocks can be strictly smaller.
Assume that the maximum row norm is bounded by || 12 S L < elg. By Invariant
we have
elo S
X;
P S clo,
i = 0, 1, B-1.
Let X = [X X T
collect all rows summarized by inactive blocks. Summing the
above bounds yields
X elo
X
B (elo- - L)
X
<
B Belo
elo
and therefore we can approximate this case by || / full-rank scenarios, the number of blocks is therefore given by
(elo))
Combining the low-rank and
min log &
|| elo
B
For the error guarantee, we bound the global error by exploiting the decomposability of blockwise matrix sketches, shown in Lemma Without loss of generality, assume the streaming matrix has rank k. Partition the block indices into
{ i (O...., B 1) : |X S elo (inactive/approximaae blocks)
and
E { i (O...., B}
sketch size 2 rank(X.)] (exact-capture blocks).
In particular, by design of the dyadic growth, the sketch size last active block B alway larger than k. hence B &. For every i the sketch is exact in the sense that
X X, S, S O.
since once the sketch size exceeds the rank of block, the best rank-k (or local rank) approximation is captured exactly. For E I, Invariant guarantees || | & I clg, and the i-th block employs a streaming sketch with error parameter 1/(2))), implying the per-block spectral error bound
1 2%
1
X X; S.T S. -
|
-
2% (do) 2:
20

---

Published as a conference paper at ICLR 2026
Let
S = ST ....,,, Sp]
be the concatenated sketch used to approximate X. By Lemma 3
we have
B
x
Σ
X X; S S.112
Σ
x x; - S. +
Σ 3E
Σ iEI
6
S
26.
2
VEI
Hence, the global spectral error is bounded by 2e.
For space complexity, note that the i-th block employs streaming matrix sketch with error parame- ter 12(2%)), which requires sketch size of (1((2)))- Hence, the total number of rows stored across all sketches is
Σ 1=0
1/(2)))))
and the overall space requirement
0ld d (1
For update complexity, only the active block needs be updated each step. Consequently, the per-update cost is determined solely by the sketch size of the active block, leading to O (11)
OMITTED PROOFS FOR SECTION 4
In this section, we first provide a proof of Theorem 2 in Appendix E.11 which is the key theorem leading the regret bound of our method when using FD. The proofs for the regret bounds in Theorem 3 and Theorem 4 are provided in Appendix E.2 and Appendix E.3 respectively. Later, we
illustrate and prove the properties of Dyadic Block Sketching for RFD in Appendix R.4 which consistent with the properties of single-scale RFD.
Our key technical contribution is extending the theoretical framework (Kuzborskij et al. 2019 Chen et al. 2020) from single-scale to multi-scale matrix sketching. In particular, we show that the RLS estimator can effectively leverage multiple sketches at different scales, where the estimation error depends on their collective approximation quality. This analytical framework bridges the theoretical gap between multi-scale sketching and linear bandit algorithms, opening avenues for applying multi- scale techniques to other online learning problems.
E.1 PROOF OF THEOREM
Denote as the number of blocks round t, and o; as the sum of shrinking singular values in the sketch of block i. Let L,, be the sketch size in the active block at round t. According to Algorithm the approximate covariance matrix is
B.
0 XI
S
$050
where S(()) the sketch matrix block at round t. Define ni .... ni Rd the noise sequence conditionally R-subgaussian for a fixed constant and r = (ri, r2,..., rt) E Rd the reward vector. We begin by noticing that
0, (A')) X,Tr,
(A")) x. (X,0, + +m).
21

---

Published as a conference paper at ICLR 2026
Therefore, decompose ||0, 0.112r0
into two parts as follows
0 0
0 0.
(r)
0 0.)
0 0,
(
((A(0) -1
X, (X,0, + +m) - -0.
(8)
0
0,
(1)
(
-1
x, X,0, - 0.
+ 0 0.
x
Term Bias Error
Term Variance Error
Bounding the bias error.
We first focus bounding the first term. We have that
A (( (4())
0 0.)
X, X,0, - 0.
0 0.) (A (A()) -
(x, X,0, - -A
(9)
(A()) $ (A +
0, 0.)
(A A 0. -20
In accordance with the decomposability of matrix sketches, as detailed in Lemma 3
we have
Σ q
(10)
2
By Cauchy-Schwarte inequality and the triangle inequality, we have
0,
0.
(0)
(A²)² [(4-- A(1)
-
A 0.
10.
B.
0
0 - 0,
||0.1| (A(0)-1
(11)
A
1=1
H
A
1i=1
B1
0i
0 0, A
where the last inequality holds beacause ( > Al and 10.112 - H.
Bounding the variance error. Then, aim bound the second term. We the following self-normalized martingale concentration inequality by (Abbasi-
et al. 2011).
Proposition (Lemma 9 of Abbasi- Yadkori et al. (201I)). Assume that mh ne is a conditionally R-subgaussian real-valued stochastic process and X, [ such that æ; is measurable with respect to the o-algebra generated by m..... nt- Then, for any 8 > O, with probability at least 1 6. for all 2 0,
:.... :..,:?? xx]]
any stochastic process
X mill(coo= 2R
( A |A (
Notice that the variance error can be reformulated as
(0.-0.) x nh (0. 0.)
-0.
A
(A(0) $
x, n
0, 0,
(12)
x 0 - 0. 700
A0
|| mi (Aw))
0, 0.
where the last inequality Cauchy-Sehward inequality.
22

---

Published as a conference paper at ICLR 2026
For any vector a, have
||ala3 - ||a|| A109 = a T (A (
B.
B.
(13)
a T
X X x
((1)
aa
i=1
i=
Therefore, the ratios of norms on the right-hand side of equation 12 can be bounded
0
0,
00, 0
A
1
0,
0,
0
0,
111
A
0 0,
+ >>>
Br
03
0, 0,
(14)
0 0.
A(1)
B: --=
07
+
X
Substituting equation 14 and Proposition
into equation 12 gives
0, 0,
0:
0+
A
|X, m: (A(1))
A0
0, Q.
A
(15)
Bi
+ 0;
1
2R In
|A0| (
-
0. aw
A
Motivated by Ab/bbbssi- Yadkori et al.) based determinant-trace inequality. Compared to the non-sketched version, this inequality depends on the approximate covariance matrix A, reflecting the costs associated with the shrinkage due to multi-scale sketching.
2011 Kuzborskij al. 2019),, apply the multi-scale sketch-
Lemma 6 (Multi-scale sketch-based determinant-trace inequality). For any 1 2 1, define A
II + X, X,, and assume | S L. we have
AA0
E 0i Bl.. In (1+
11.2
(1+
In
< dln
1+
|
X
21
Proof. EB: (5(1) T (t) has rank at most 21 due to the Dyadic Block Sketching, Since Á B, B, (s(()) ((()) and (9 < ( + BB. σ; I, we have
Al + 1i=
B
A (1) <
7
0
t=1
Bi
d-2in
Σ
21g. 1=1
!1)
B, +
- Ti
21g:
+
21
1=1
2ln
B
d-2la,
B
Tr
B
(S(11)
S((()
X+
0i
A x
21 R.
1=1
1=1
d-
21
B.
B.
tL?
x
0.
A +
0
+
21
1=1
1=1
23

---

Published as a conference paper at ICLR 2026
where the last inequality holds because
Tr
5:00
TT Xi) Σ xg Dg 2t?
Therefore, have
(0)
A - Ti
d-21a.
x+ Σ i=
5. +
112
21
21m
In
S In
[AT]
X
A
ΣE 0j
Σ =1=1
0
tL?
(d - 1-21BB) 1l ln
1
+ 21 In
1
21 A
_i=1
T.
1+ tL?
s dln
1
+ 21g,
In
A
21 A
According to Lemma
we finally bound the variance error term as follows
0, 0.
0 0
A(t)
-|x, mmlll
0, 0,
< V
1 +
Σ 1=1
0;
2 In
|
[ -b ) 1|0, -00
|AI
-0.. 0.11200 A())
R
1 1+
Σ 1=1
0,
2ln
dln
1+
E T. A
+ 2l In 1+
tLa
0 0,
A
8
21 21 2
7(3)
Sum up the bias error and the variance error and divide both sides of equation 8 by 100, 0. g simultaneously. we have
-0.-0.120 300 SR. V
1
Limi o.
tL 21 >
2 2l
dln
1+
2l In
1+
X
\ +
B
0
VT
11
+ dln (1+ () 21 In
tL? 21
Xte
< R
1
2ln
1+
+ +H.
S R dln (1 + :)
2l
v 1 VA
(({++)
where the second inequality follows from the error bound of Dyadic Block Sketching as stated in Theorem |I
E.2 PROOF OF THEOREM
Having established the confidence ellipsoid, now focus on analyzing the regret. We begin with an analysis of the instantaneous regret. Recall that the optimal arm at round t is defined as x; = arg max(x²) T 0.). On the other hand, the principle of optimism in the face of uncertainty ensures mEX,
that (x,, θ.-1) arg max x 0. By denoting O the RLS estimator, we utilize these facts (x,0))x,x0,.-1
24

---

Published as a conference paper at ICLR 2026
to establish the bound on the instantaneous regret as follows
(Ø) xx) 0. S x 0i-1 0.
_ 00-1 01-1) +x (01-1-0) (0.11-0.)
| (A(c-)))-
(100-- - 0
Al +
+ -0.
Aa 12 .,) 0
0.
(16)
2 (3) || (At--)))-
Now, we are prepared to establish the upper bound of regret. Utilizing equation 16 and Cauchy- Schwartz inequality, derive the following bound
Regret, = Σ
max x. T 0. 2EX t=1
Σ a. 0. t=1
2
min
HL, 12-1 ||a0x (1000))))00(()))-10)
S 2
3 (6) min
<x
|| [|00e|((u-1))-
(17)
T
< 2 max
1, V1
(7(
Σ
min 1, 21
t=1
{1. 1,
L
< 2 max
3T(
T Σ min
|/21 (An-11)-1 (1
Vx
We further bound the terms in the above. In particular, we formulate (8) by Theorem as follows
(6) = (R/00R1/100 1+
Br
T.
2ln
dln
1+
Br Eee T.
2
TL2 11
A
A
21 A
(18)
Σ By -
HVV
Ti
1+
Besides, we adopt the Sketched leverage scores established by Kuzborskij et al. (2019) as follows
Proposition 2 (Lemma 6 of Kuzborskij et al. 2019)). The sketched leverage scores through sketch- ing at round T can be upper bounded as
Σ 1=1
min
1, 1|,10
12 (ACU)-1
Br
[A(T)
2
1
.nn
[
Σ
1 Σ > Ti
Br + 2l -hn (1+ 1+
TT2 2l
2
1+
dln
Combining equation
18
equation
17 and Proposition assuming
L VX, we have
25

---

Published as a conference paper at ICLR 2026
{1, L
Regrety 2. 2- max
(T)
min
1, 1,,1211
vX
(A
VT.
1
-==
Ti
dln
1
1 oi
+ 21
In (1+
TT2
x
x
Bl
(1+
1+
Li=1 o
2ln
1
dln
1+
T
+l -11
(1
TL2
X
Bl A
E oi ) + 1 A
HVV
According to Theorem we can bound the spectral error by emor c, i.e. E oi Given that L VÀ, the complete regret bound of DBSLinUCB using FD is as follows
Regret, s VT. (1+
L V
d 1 ( 21 In (1+ 21B,A\/ 1)
TI?
1 RVI+ c X
Ry RV/
2ln x
+ ddln (1+ 2) +l Inn (1
TL2
+ +HVA (1+ (1+2)
2)
21 A
L(R+HVA)
dn (1 4) 21 In (1+
TL? 2
(1 2) VT.
VA
Ignoring the constants R, and well the logarithmic terms, we simplify the regret bound to
Regret, σ (1+ 9)²² (d (d+ler)) VT.
E.3 PROOF OF THEOREM
We denote as the number of blocks round and o. the cumulative shrinking singular values in the sketch of block i. Let 1,, be the sketch size in the active block at round t. Similarly, our analysis establishes an intermediate result regarding the confidence ellipsoid.
Theorem (Sketched confidence ellipsoid by RFD). Let θ be the RLS estimate constructed by an arbitrary policy for linear bandits after rounds of play. For any ō E (0,1), the optimal unknown
weight O, belongs to the set O = {o Rdd 0, Am S B(())) with probability at least 1 - 6.
where
1
-i=l Ts 1
tLa
h
3,) R.
2ln
dln
21 In
1+
+
X
21 X
x
+ H
A
gi
1=1
and
B.
Bi
Ti
0:
21
Proof. Notice that RFD uses the adaptive regularization term to approximate the covariance matrix,
i... ( X E.t a I ( s(t), where s(t) is the sketch matrix block and
a the adaptive regularization term of RFD round I.
(0)
26

---

Published as a conference paper at ICLR 2026
Similarily, we decompose
|00 0- xte into two parts as follows
2
0,
0.
A
0,
0.
(t)
0, 0.)
0,
0.
(
((T10) -1
x (X,0, + n:) -0.)
0,
0.
A
(1(0)
-1
X, X,0, 0.
+ 0, (6--0.) x, m
x,
Torm 2: Variance Error
Term I: Bias Errer
Bounding the bias error. For the bias error term, we have
( 0.)
(1) (AT1)
X, X,0. -0. 0.)
(0. 0.)
(A(0) $
(A()
-
(x] X,0 -,
(19)
(0. 0.)
(0 & (AC)
-
x,T X, - -I Σ
Be
B,
((t)
T
S(t)
0,
iml
im
A 00 0.)
(0) $
(AO)
D..
Since D, = X, T X; AI-
Em= ai
(0)
I
Bl Li=l
(5!") T
!
for any unit vector a, we have
la T D:a
a
X, X,
Al
0
(2)
I
(1)
T
((1)
i=1
:=1
(20)
B.
a
X, X₁
Σ
(s(())
T
(1)
AI
a
According to Theroem
we can get
B a
0 a T
x, xr Σ
(2)
s(1)
<
1=1
Bring the above equation into equation 20 norm of D, as follows
since Σ
1 ai
(1)
> iml T; we can bound the spectral
| s A
(21)
1=1
By Souchy-Schwarzz inequality and the triangle inequality, we can bound equation 19 by
00 - 0.)
(xw)
(A D, 8.
<
00
0.
|DDrl2 1|0=1| ((s)) (2:))
T00)
(22)
B,
|0. 0. g00)
H
+
0
where the last inequality holds because
10.12
2
||e_
[()))
Amin
A
Σ B,
:=
27

---

Published as a conference paper at ICLR 2026
Bounding the variance error. For the variance error, we have
00 - 0.) x, n = 0 - 0.) ( A (t)
(A(1)
x, 17
0, 0,
0, 0. A
A
||x, noll
(ell(a00))
(23)
0 0,
0, 0,
|| 77
(A(O)-1
where the last inequality holds because for any vector a
||al| - ||all A(c)
T
x
x
B,
8(1)
T
5
Σ
B
0
1=1
i=1
Bi
T
B.
T
X
X
(((1)
a
a
2
(24)
t=1
B.
B.
5
aa
Σ
o
a
2
0
By Proposition]] I
we can bound the variance error term as follows
0 0.)
x, n
T
(A))) - (A(1) $ X, n.
0
0.)
(25)
0 0,
||x,, m: (A)0)--
Áw
2R In
1
|
$ |
||0, 0. 0.1/200
According to equation 24 most Bl we can bound the determinant of 10) as follows
we have |
>
A
| For any 1 E [T], since the rank of Ā is at
B.
d-212,
28g
1
II A (A()) f=1
<
+ A
1=1
2-21p
Σ ==
2lm
A (A(()
2n.
a
(1)
+
21 Bi
i=1
21
(26)
B
d-21B;
B.
Tr
Σ (5 S(())
Σ
+
Σ
J. +
21
d d-2l
21
B
B
>B Rr i==
4. oi
TT,2
+
Σ
0
+ X
-
21
21
where the last inequality satisfies due to
Tr
B,
s(S))
T
s(t0)
=
B. > Tr
(s! 5::))
1 Σ
Tr(x, x:))
Σ
B.
4 T
B,
$ T
1=1
28

---

Published as a conference paper at ICLR 2026
Therefore, the variance error term can be bounded
0, -.
X, m7
1 A $ | | }) |0. 0g
2R
$
2R In
A
|AI [X|]+ #)
10. 0,
A(0)
S R
2
+ (d 21
1 i=
Σ B,
Ti x
+ +21B. In
(+
21 x
tI²
+
h4
x
00, 0.
x(0)
S R.
2 ln
8
1
+ dln
1
Ei= oi
Bi
Bl -In
[1
1T2
+
x
14
| - 0.
x
21 X
A(te)
where
Ei=1 o
B,
B
4.
Sum up the bias error term and the variance error term and divide both sides by 100: -0.1 simultaneously, we have
0. 0. 10:-0.1a
Ato S
R
21n
1 σ
+ dln
1
E Ti x + Bl In (1+ 2l X
1L2
he
+
H
A +
B.
1=1
which concludes the proof.
Next, we start to prove the regret. Similar to the case using FD, since the algorithm uses the principle of optimism in the face of uncertainty to select the arm, we can bound instantaneous regret by equation 16 Utilizing equation 16 and Cauchy-Schwart Schwartz inequality, we derive the following bound
Regret, =
Σ
max x 0, xEX t=1
Σ a. aT 0. t=1
2
min
HL, (0) || 1l (1:--13)-1
L [
5 2
Σ
3,-1 (6)
min
|| (()-1))-
(27)
[=1
T
< max
1,
3r()
Σ
min { 1, 11eleelll (1l
VX
1=1
L Vx
< 2 max
1,
(T)
T Σ min
1, [ (A
(Au-11)-
We present lemma of RFD-sketched leverage scores to conclude the proof. Lemma (Sketch-based leverage scores by RFD).
Σ min 1, |||20001 11/001ll2 ||020|(2001)11 < 20 In (1+ t=1l
T
TL2
+ ht
)
21
2
Proof. Denote C, 111-1) + x① xt. Notice that the first 2(B eigenvalues of C, the same as ( while the other eigenvalues of C, are ΣB, a (1-1)
+ X. Thus we can obtain
Σ B
G= a (1) +
d-2in.
C1
Σ DB a;
(t-1) +
29

---

Published as a conference paper at ICLR 2026
For the determinant of (+), we have
Σ Br (1)
+1
d-21p,
1
C|
1)
+
Br +1
d-2In.
( I (A(--1)- -1
xi axe
11 1=1
+1
(28)
d-21n,
1=
+1
| (1+ || [1 (
B (1-1) +1
ii=
2-
2i=1 Tz +1
|T II
1+ | | (
Since min (1,z) & 21 (1 + x)) for all x 2 0, using equation 28 we can derive the following bound
T
min { 1, || (aaeel(vv-n (()-11)-2
$
Σ In
1
+
||ax 11 (()-))))
[=1
t=1
((
d-2ler
((r))
A
= 2n
D Br T. A
ai
TL2
ht
S Br In
| 11(
21 By X
where the last step holds by equation and hT
EB o.
By
BT 4. 24
We combine equation
27 Theorem 6 and Lemma 7
Assume L 2 VI, we have
Regrety
max x #EX
0.
Σ x O.
T
L
2 . max
1,
Br(())
7
min
1, 1,|| 11 (Ac-n)) 1
VX
1=1
Br
< L
TL2
hy
VT.
21 In
1 Br A
+
(
H
1 + Σ oit
VX
x
1=1
(1)
1
1+ Eei Ti
TL2
hT
R.
2ln
+ dln
+ +2 In
1+
+
X
According to Theorem
the accumulated spectral error
EBT T. is bounded by and we have
Br
BT 4:
T
Br
2i-1
br
T
21 Br
2BT
1=1
1=1
Br
2
1
< E
1
BT
2
1=1
< 6.
30

---

Published as a conference paper at ICLR 2026
Therefore, derive the complete regret bound as follows:
L
1+ 2 + 2) H H.. vx+
TL2
Regret, 1
VT.
2l In
V
{
1
+ dln [1+ - 5) + 21BB In
[+ Bl + E
TL2
)
R.
2ln
L
TI2
+ 2).
VlB, T
/2
(1 Bl x
H H.
VĀ
R-
V
d [
2)
BB In
1+ 20 A + 2)
TL2
Ignoring the constants L, R, and H, as well as the logarithmic terms, we simplify the regret bound
Regret, σ (1+ ++ VBITT + Dd T.
E.4 PROPERTIES OF DYADIC BLOCK SKETCHING FOR RFD
In this section, we highlight two significant properties of Dyadic Block Sketching for RFD that elucidate why the regret bound of DBSLinUCB using RFD improved. Although Robust Frequent Directions for ridge regression have been studied by [uo et al. (2019), their theory is limited to single-scale deterministic streaming sketches We demonstrate that the decomposability of multi- scale sketching does not alter the properties of RFD.
We begin with the positive definite monotonicity of Dyadic Block Sketching for RFD, which ensures that the sequence of approximation matrices is per-step optimal.
Theorem (Positive Definite Monotonicity). At round t, denote that the Dyadic Block Sketching for RFD provides sketch (tt), we have the following equation
(s()) 5(9) + 1 (s(t-1))
1(t-1) + +a (t-1)
Proof. Notice that (1) I+
S = E. 1 (S))) where s(1) is the sketch
(0) matrix in block and a;; is the adaptive regularization term of RFD round l.
is the shrinking singular values of active block at round t, the shrinking step of RFD provides
Let Q [
(s(t_")) T x. B,
B,
B.
B
Σ
( 5 + +
Σ
(5 T 5.00 QQQQZ
Σ ( (((-11)
5(1-1)
(29)
1=1
1=1
Therefore, for any unit vector a, we have
a T
((ttt)
5(1) + +a(1
(s(t-1)) g(t-1) + a((-1)) a
B
B
Bi-1
B
a
T
I
(((1)
(1))
Σ
(1-1)
Σ
( ((((-1))
5 s(1-1) a
i=1
1=1
t=1
t=1
= a T
Σ
B,
(((0)
T
+ 0 -
B
Σ (
T
s((-1)
a
0,
which concludes the proof.
31

---

Published as a conference paper at ICLR 2026
Next, prove that the sketch matrix produced by Dyadic Block Sketching for RFD is better ditioned than those produced by Dyadic Block Sketching for FD and the covariance matrix. this context, the selected by RFD is optimal, choosing smaller would result in worse condition number for the approximation matrices.
Theorem 8 (Well-Conditioned Property). Let cond(X)
Omaee (X) be the condition number of Ouinn! X)
matrix X. Ar round t, denote that the Dyadic Block Sketching for RFD provides a sketch S we have
((s(t) 5 + +
S <cond ((st:) T 5(0 + +
cond
(S())) 5(0)) + 1 S cond (X, X, +1).
cond
Proof.
Notice that ( I+ (5
B. i= T
where 5 is the sketch
(8) matrix in block and a; is the adaptive regularization term of RFD at round t. We have
T
cond ((st0)* g + a +1
maxx
Σ
(tt)
+ +
1
A
Σ
i=1 a
B, (1)
max
E
(s!!1
((1)
+
((s T
cond
5(()) + 11)
Similarly, we have
EE (s(t) S
+X+ Σ a (
cond ((s:)) 5(0 + a + AT)
O Imax
X +1=1
T max
(x, X,) + +
Σ B,
Di=1 a
X+
(xTX,) +
max
1 cond (x, X, + A1).
which concludes the proof.
F OMITTED DETAILS FOR SECTION 5
In this section, we provide the omitted details of experiments section 5 mental setups and configurations in Appendix F.1 and additional experiments in F.2 F3
We provide the experi-
and F.4
F.1 EXPERIMENTAL SETUPS
All experiments are performed on a machine with 24-core Intel(R) Xeon(R) Gold 6240R 2.40GHZ CPU and 256 GB memory. We compare our DBSLinUCH with the state-of-the-art linear bandit algorithms the synthetic dataset and several well-known classification benchmarks. The training and testing data are merged into a single dataset, followed by vector normalization based on the l2 norm. Each experiment is performed over 20 different random permutations of the datasets. The confidence ellipsoid B3 of all algorithms is searched in {10-4, 10-3 ,...., 1} and À is searched in {2 10-4,- 4,2 10 ..... 2 10*).
In the experiments of online classification in real-world data, we follow the experimental setup in Kuzborskij al, (2019). Specifically, construct the online classification problem within the
32

---

Published as a conference paper at ICLR 2026
contextual bandit setting follows: given dataset with data in M labels, first choose cluster as the target label. In each round, we randomly draw one sample from each label and compose an arm set of M samples in M contexts. The algorithms choose observe the reward based on whether the selected sample belongs to the target label. The reward is 1 if the selected sample comes from the target label and O otherwise.
sample from the set and
F.2 EXPERIMENTS OF MATRIX APPROXIMATION
We evaluate the performance the proposed Dyadic Block Sketching in terms matrix approxima- tion. We compare it with FD (Liberty 2013). We generated synthetic dataset with = 1250 rows and d 500 columns. Specifically, each row a, E 12000 is independently drawn from multivariate Gaussian distribution
.V (0, Ia), followed by vector normalization based on the ly norm. We set the sketch size lo = 50 for FD and initial sketch size lo = 16 for Dyadic Block Sketching. The spectral norm error is defined as || A! A. S Sell2, where A, is the streaming matrix at round t and Se is the sketch matrix at round
FD
17.5
FD (Upper bound)
2.5
Specral Norm Error
DBS-FD
2.0
12.5
(Upper bound)
Spectral
1.5
10.0
7.5
1.0
DBS-FDX = 5)
5.0
DBS-FD(E 10)
0.5
DBS-FDXE= 20)
0.9
0.0
200
400
600
800
1000
1200
200
400
600
800
1000
1200
Number of Rows
Number Rows
(a) Spectral error with varying
(b) Comparison among FD and DBS-FD
Figure 4: (a): The spectral norm error w.r.t the error parameter synthetic dataset; (b): Compar- ison among FD and our DBS-FD w.r.t. the error and its upper bound
We first vary the error parameter 6 E {5, 10, 20). As illustrated in Figures 4a we observe that in- creasing the error parameter leads to a larger spectral norm error. Then compare method with FD. We set the error parameter e = 10 for Dyadic Block Sketching. Figure 4b) presents the spectral norm error A A, S, S2112 along with its upper bound for matrix sketching. We ob- serve that Dyadic Block Sketching provides a constrained global error bound for matrix sketching. In comparison to FD. the rate of eтror growth in Dyadic Block Sketching decreases over time, effec- tively mitigating the linear growth of the spectral tail.
F.3 MORE EXPERIMENTS ON MN
In this section, we present additional experimental results the MNIST dataset, demonstrating our method's capability to adaptively adjust to optimal sketch sizes. The evaluation focuses primarily on FD-based methods for comparison. For the SOFUL algorithm, we evaluate performance across multiple sketch sizes with / { {20, 100, 1503. For our proposed DBSLinUCB algorithm, we initial- ize the sketch size lo 50 and configure the error parameter = 8. We also report that the streaming matrix used by all methods is full rank.
The cumulative regret results demonstrate that DBSLinUCH achieves com- petitive performance compared to the baseline algorithms. As shown in Figure 5a DBSLinUCB maintains regret levels comparable to OFUL, the gold standard algorithm, throughout the 2000 rounds of evaluation on the MNIST dataset. In contrast, SOFUL exhibits significant performance degradation when configured with insufficient sketch sizes, particularly evident with 20 and = 100, where the cumulative regret substantially exceeds that of both OFUL and DBSLinUCB. While SOFUL with 150 achieves regret performance similar OFUL and DBSLinUCB, this
Regret Performance.
33

---

Published as a conference paper at ICLR 2026
500
OFUL
SOPUL (1- 20)
SOFUL (1- 100)
20
400
SOFUL (1= 150)
Regret
300
Time(s)
200
10
100
5
0
500
1000
1500
2000
SOFUL
SOFUr.
SOFUL DBSLi OFUI.
Number Rounds
(a) Cumulative regret
(b) Running time
Figure 5:
Cumulative regret and total running time of the compared algorithms, the proposed DB- SLinUCB on MNIST
configuration requires careful tuning of the sketch size parameter, which presents practical chal- lenges in real-world applications where the optimal sketch size cannot be determined priori.
Running Time Efficiency. The computational efficiency analysis presented in Figure 5b reveals the significant advantage of DBSLinUCB in terms of runtime performance. DBSLinUCB achieves approximately seconds total running time, representing substantial improvement over OFUL's 23 seconds execution time. Even when compared to SOFUL variants, DBSLinUCB maintains com- petitive efficiency while avoiding the performance trade-offs associated with fixed sketch sizes. SO- FUL with smaller sketch sizes (1 = 20) achieves faster runtime at approximately 9 seconds, but this comes at the cost of severely degraded regret performance. The results indicate that DBSLin- UCB successfully addresses the fundamental challenge of balancing computational efficiency with learning performance, eliminating the need for manual sketch size tuning while maintaining both competitive regret bounds and superior runtime characteristics.
Space Complexity. Table reports the maximum memory footprint of each algorithm over 2000 rounds on MNIST. DBSLin CB achieves 40% reduction in space usage compared to OFUL while maintaining competitive regret performance. Unlike SOFUL, which requires pre-specifying fixed sketch size I, DBSL innUBB adaptively adjusts its sketch dimensions based on the observed data stream. This adaptive mechanism allows DBSLinUCB to match the space efficiency of SOFUL. with 150 while providing stronger robustness guarantees-notablee SOFUL with smaller sketch sizes (1 E {20, 100}) achieves lower memory usage but suffers from degraded regret performance shown in previous experiments. The results demonstrate that DBSLinUCB effectively navigates the space-regret trade-off without requiring prior knowledge of optimal hyperparameters.
Table 2: Comparison Space Usage on MNIST
Algorithm
Sketch Size (!)
Max Space (KB)
OFUL SOFUL
N/A
4802.0
20
682.9
SOFUL
100
1528.3
SOFUL
150
2529.3
DBSLinUCB
Adaptive
2842.0
F.4 EXPERIMENTS ON ADDITIONAL REAL-WORLD DATA
In this section, we evaluate DBSLinUCB on online classification tasks across multiple real-world benchmarks beyond MNIST, validating its generalizability and practical effectiveness. Similarly, the baselines include the non-sketched method OFUL (Abbasi- Abbasi-Yadkort Yadkori et al. 2011) and the sketch-
based methods SOFUL (Kuzborskij al. 2019), CBSCED (Chen al. 2020)
34

---

Published as a conference paper at ICLR 2026
Table 3: Dataset Information
Dataset
OpenML ID
Instances
Features
Classes
cnae-9
1468
1080
856
MFett
22
2000
48
10
Spam
44
4601
57
2
SOPUR
1000
OFTIL SOPCE
200
SOFUL DISLIAICE
DSSLLSUCE
DESLIDCE FD
Regret
Regret
DASI DISILnUCCH-RP
Regret
PASLUMUCH-RRO
150-
500
500
100
40
1000
2000
100
200
Time
Time (rus)
Time (ms)
(a) Regret vs. Time
(b) Regret vs. Time
(c) Regret vs. Time
SOFUR
1000
SOFUZ
200
SOFTL
CRASCIPP
DRISLBUCH
DUSLLOUG KD DISLISUCB-BR CFF--FD
DNSSUSUCC DISLLSTCC-BR
Regret
1ISSLSU/CB-RF
Regret
Regret
150
500
500
100
5000
10000
20 Space (KB)
Space (KB)
Space (KB)
(d) Regret vs. Space
(e) Regret vs. Space
(f) Regret vs. Space
Figure 6: (d): Pareto frontiers for regret vs. time and regret space cnae-9; (b). Pareto frontiers for regret vs. time and regret vs. space on MFeat; (f), Pareto frontiers for regret vs. time and regret space on Spam
Datasets. We conduct experiments on three publicly available multiclass classification datasets from the OpenML repository /Vanschoren et al. 2013), as detailed in the table The experimental setup is provided in Appendix F The datasets include cnae-9, 9, MFeat, and Spam, each with varying numbers of instances, features, and classes. These datasets utilized to evaluate the performance of our proposed method across multiclass classification tasks.
Pareto Frontier Analysis. The Pareto frontier evaluation across three datasets (cnae-9 9, MFeat, and Spam) reveals the superior trade-off characteristics of our proposed DBSLinUCB methods. As consistently establish better
illustrated in Figure 6 both DBSLinUCB-FD and DBSLinUCB-ReE positions on the Pareto frontiers for both regret vs. time and regret vs. space trade-offs. Notably, our methods form well-positioned curves that span a wide range of efficiency levels while maintaining competitive regret performance, demonstrating the flexibility and adaptability the dyadic block sketching approach across different resource constraints.
Adaptation to Low-Dimensional Data. On relatively low-dimensional datasets, particularly on Spam (Figures 6c and 6f), OFUL serves as strong baseline with an excellent trade-off between regret, time, and space. Notably, our DBSLinUCB-RED variants closely approach the OFUL curve across multiple configurations. While this demonstrates a clear advantage over single-scale sketch- ing methods, it also suggests that method may incur some cost when degenerating to OFUL, phenomenon more pronounced in certain now-dimensional settings.
Variants Consistency and Robustness Across multiple datasets (especially in enae-9, 9, Fig- ures 6a and 6d). our method achieves similar trade-offs in terms of regret, space, and time for both
35

---

Published as a conference paper at ICLR 2026
FD and RFD variants. In contrast, scale sketching methods, such as SOFUL (FD based) and CBSCED (RFD-based), exhibit significantly different trade-offs (e.g.. Figures 6a 6c 6d
and 6f).
This performance consistency arises because method effectively controls global error in matrix approximation through a unified parameter e, and replacing sketching methods does not result in substantial loss of accuracy. This stability highlights the robustness of dyadic block sketching framework, offering reliable performance regardless the selected underlying sketching technique. Unlike traditional single-scale methods, where the choice between FD and RFD can dramatically affect performance, our approach ensures consistent outcomes.
36


Reviews:
[{"review_id": "k9YOMWQZaP", "reviewer": "Reviewer_NX8x", "summary": "This paper revisits the computational and regret trade-offs in sketch-based linear bandits, where matrix sketching is employed to reduce the per-round computational cost from quadratic $O(d^2)$---with $d$ denoting the feature dimension---to subquadratic, while maintaining sublinear regret in $T$, the time horizon. Earlier work has shown that for linear bandits regret of order $O(d\\sqrt{T})$ can be achieved with per-round complexity proportional to $O(d^2)$. Subsequent research demonstrated how to reduce this computational burden using dimensionality reduction techniques, particularly matrix sketching, to achieve per-round complexity $O(dl + l^2)$, where $l$ is the sketch size. However, in these approaches, the regret depends on the *spectral error* introduced by dimensionality reduction and can become linear (i.e., vacuous) when the spectral error exceeds $T^{1/3}$.\n\nThis paper makes progress on this front by introducing an algorithm termed *Dyadic Block Sketching (DBS)*---a multi-scale sketching framework that adaptively doubles the sketch size as learning progresses. The key claim is that this adaptive structure bounds the global covariance error by a user-specified parameter $\\varepsilon$, thereby ensuring sublinear regret independent of the spectral error. Empirical results on synthetic and real-world datasets (e.g., MNIST) support the theoretical analysis, showing improved regret–efficiency trade-offs compared to prior methods.", "questions": "The problem you identified: getting sublinear regret algorithm for linear bandits with sub quadratic per-round complexity for is very interesting to me. So it will be very nice to the readers if you could make a table with what is known (including your work) and to what extend this is an open question. Making a separate section on related works and discussing this will also make the paper very nice to read.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The computational efficiency of linear bandits is an important and active area. Reducing per-round complexity while retaining sublinear regret is a significant theoretical question. The proposed framework makes a meaningful contribution toward that goal and the method is natural (adapting the sketch size). The paper is well written with detailed proof given in the appendix. The authors complement their theoretical work with experimental validation, which is an added bonus.", "weaknesses": "While the claimed regret bound is independent of the spectral error, it still depends on other parameters such as  the $\\ell_2$-norm of the feature vectors, and the sketch size of the active block $l_B$. This dependence implies that in certain regimes, the regret may still exhibit linear scaling. Providing a clearer exposition or characterization of when such linear growth arises would  strengthen the paper. In particular, the paper would benefit from explicitly stating conditions under which their algorithm reverts to linear regret. This will lead to open questions that can be stated explicitly. Regarding exposition, for semi/non-experts, the presentation is dense and occasionally confusing. Terms like “streaming matrix” and “spectral tail” are introduced early without clear explanations. It is not clear what is streaming matrix means in this context.", "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": "2xCJqRhWXc", "reviewer": "Reviewer_pFPs", "summary": "The authors first show that existing sketch-based linear bandit algorithms can suffer from linear regret. To address this issue, they propose a novel matrix sketching framework called Dyadic Block Sketching (DBS), which adaptively adjusts the sketch size in a multi-scale manner. By applying DBS to linear bandits, the authors achieve sublinear regret bounds. They further validate the effectiveness of the proposed method through experiments on both synthetic and real-world datasets.", "questions": "see Weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation of this paper is clearly presented.\n2. The proposed methods are novel and interesting.\n3. Although I did not examine the proofs in the appendices in detail, the theoretical results appear convincing and reasonable.\n4. The writing is generally clear, though some parts require further clarification (see Weaknesses).", "weaknesses": "1. In lines 372–379, the authors discuss choosing $\\epsilon$ based on the spectral properties of the data matrix. However, in linear bandit problems, it is usually unknown whether the data matrix is low-rank or has a heavy spectral tail. How should $\\epsilon$ be selected in practice? Moreover, in the experiments, how was the value of $\\epsilon$ determined?\n\n2. Some experimental results require further clarification:\n- In Figure 3(a), why does the regret of $\\epsilon=4$ outperform that with $\\epsilon=2$?\n- In Figure 3(d), when the sketch-based methods use the same amount of space as OFUL, their performance is still inferior to OFUL. The authors should provide a more detailed explanation for this result.\n\n3. Some statements in the paper are unclear or inaccurate:\n- In the abstract, the authors claim that “the sketch-based approaches reduce per-round complexity from Ω($d^2$) to O($d$),” which is not accurate. The computational complexity of matrix sketching depends on the sketch size. If the sketch size is $O(d)$, the overall complexity of sketch-based methods remains $O(d^2)$.\n- In line 66, the statement “thereby reducing the order of spectral error $\\Delta_T$ and decoupling it from $d$” is difficult to understand for readers unfamiliar with Chen et al. (2020). It is recommended that the authors present the regret bound from Chen et al. (2020) in the paper for clarity.\n- In the last line of page 3, the phrase “under certain conditions” is too vague. The authors should describe these conditions in more detail.\n- In the last line of page 5, the phrase “$\\tilde{X}$ the subset of rows approximated by inactive blocks” is confusing. Does it mean “$\\tilde{X}$ is the subset of rows consisting of inactive blocks”?\n- Algorithm 3 is commonly referred to as SCFD (Chen et al., 2020) rather than RFD (Luo et al., 2019). Note that the regularizer in SCFD sums the total mass of subtracted values during the FD procedure, whereas in RFD, it sums only half of the subtracted mass.", "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": "aMHRJElmGq", "reviewer": "Reviewer_v1kF", "summary": "This paper shows that existing sketch-based linear bandits can suffer linear regret when the data matrix has heavy spectral tails. The authors propose Dyadic Block Sketching (DBS), which adaptively adjusts sketch sizes to control global error. Applied to linear bandits, their DBSLinUCB algorithm achieves sublinear regret and better efficiency than prior methods.", "questions": "1. The discussion on the parameter choices in Remark 2 is insightful. I am wondering is there any approach on adaptively estimating l0 to make the selection of parameters adaptive to environments. \n\n2. I am not deeply familiar with the literature on matrix sketching for linear bandits, but I noticed that most baselines in this paper are from around five years ago (e.g., SOFUL [Kuzborskij et al., 2019], CBSCFD [Chen et al., 2020]). It would be helpful if the authors could comment on or compare with more recent works, such as Zhang et al. (2023) and Feinberg et al. (2023).\n\n3. In the related work section on multi-scale sketching, the authors explain that previous algorithms were developed for different purposes. I am curious whether there are shared ideas or overlapping design principles between those existing methods and the proposed Dyadic Block Sketching framework.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a clear motivation by highlighting the pitfalls of previous studies. And the introduced of multi-scale sketching approach is well-grounded. \n\n2. The algorithm and its analysis are presented clearly, with good intuition and easy-to-follow explanations. The numerical experiments use meaningful benchmarks, and the results, particularly in Figure 3(c), convincingly validate the claimed performance improvement.", "weaknesses": "I did not find any major technical weaknesses in this paper. However, as a reader who is not very familiar with matrix sketching applications in bandits or online learning, I have several questions about the positioning of this work and the choice of benchmarks, as mentioned in the question part.", "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": "3AlKkmZkgb", "reviewer": "Reviewer_1de1", "summary": "This paper revisits efficient linear bandits using matrix sketching. Matrix sketching approximates the streaming matrix X to reduce update costs. Previous methods such as SOFUL lower the per-round complexity from \\Omega(d^2) to O(dl + l^2) by maintaining low-rank sketches, but their regret can become linear when the sketch size is too small or the spectrum decays slowly. The authors propose Dyadic Block Sketching (DBS), a new framework that adaptively adjusts the sketch size at multiple scales without prior knowledge of the data. Applied to linear bandits, this leads to the DBSLinUCB algorithm, which achieves sublinear regret under general conditions. Both theoretical analysis and experiments on synthetic and real-world datasets support its effectiveness.", "questions": "Please address the concerns raised in Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Theoretical guarantees: When an appropriate value of \\epsilon is chosen in advance, DBSLinUCB achieves the O(\\sqrt{T}) regret of OFUL (Theorem 3), which SOFUL cannot do without knowing spectral information. Even in the worst case, the algorithm attains an O(dk) update complexity (Corollary 1) while maintaining robust regret guarantees.\n\n2. Balanced trade-off: Regret can be controlled via fixed parameters (\\epsilon, l_0), while the update cost depends adaptively on the matrix rank k or Frobenius norm \\|\\tilde{X}\\|^2_F, achieving a balance between theory and efficiency.\n\n3. Flexibility: The DBS framework is modular and compatible with methods such as FD and RFD, supporting wide applications in online and bandit learning.\n\n4. Empirical results: Experiments on synthetic and real datasets show consistent improvements in regret and efficiency, confirming robustness under different settings.", "weaknesses": "1. Incomplete theoretical coverage: The theoretical guarantees do not fully subsume SOFUL. When l < k and \\|\\tilde{X}\\|^2_F is unknown, the analysis cannot ensure an update cost of O(dl + l^2), and no choice of (\\epsilon, l_0) achieves SOFUL-level efficiency.\n\n2. Efficiency–regret trade-off: Achieving near-optimal O(d\\sqrt{T}) regret may lead to high update costs, especially when the data matrix has large rank or Frobenius norm. It would help to provide examples or evidence showing that in practice, k \\ll d or \\|\\tilde{X}\\|^2_F is small (e.g., constant or o(T^{1/3})).\n\n3. Lack of empirical context: In the MNIST experiments (Figure 5), the rank k of the dataset is not reported. Without this, the complexity comparison is hard to interpret—particularly when k is close to d, where DBSLinUCB may be much slower than SOFUL.", "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 (Poster)