acceptodds
Under review as a conference paper at ICLR 2027

Sketch-Aware Generalized Linear Bandits: Efficient One-Pass Updates via Frequent Directions

Abstract

The nonlinear link function in generalized linear bandits (GLBs) makes it challenging to achieve statistical and computational efficiency simultaneously. Recent online mirror descent methods enable statistically efficient one-pass learning, but their guarantees rely on dense curvature geometry, incurring memory and computation per round in the feature dimension . We propose a sketch-aware GLBs algorithm based on Frequent Directions, a deterministic sketch that incrementally compresses the adaptively revealed curvature geometry. A single sketch supports both estimator updates and optimistic action selection, reducing memory to and, for small candidate action sets, amortized per-round computation to for sketch size . We establish a rigorous regret guarantee that quantifies the efficiency–utility trade-off: the approximation penalty is controlled by the discarded spectral tail, while the regret retains the statistical efficiency of its full-matrix counterpart under favorable spectral structure. Across synthetic and real-world benchmarks, our approach closely matches the regret of full-matrix methods while substantially reducing runtime and peak memory.

Primary area:
reinforcement learning
Keywords:
Generalized Linear Bandits, Matrix Sketching, Online Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_FvzFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes SGLB, a sketch-based extension of GLB-OMD for generalized linear bandits. It uses Frequent Directions to compress the accumulated curvature matrix and constructs an OMD update and confidence set that account for sketching error. The theoretical analysis gives a regret bound depending on the sketch size and discarded spectral tail, retaining the optimal-action curvature dependence of GLB-OMD. The paper claims O(md)O(md) memory and amortized per-round computation for small action sets, with better statistical guarantees when the spectral tail is small. Experiments on synthetic logistic and Poisson bandits and real-world dataset evaluate regret, runtime, and memory, illustrating computational savings and the regret cost of the sketch-based GLB algorithm.

Critical strengths
  1. The paper addresses a computational bottleneck. Section 3 integrates Frequent Directions into the curvature matrix and constructs a sketch-based OMD update, and optimism bonus. This method reduces the dimension-dependent costs that remain in GLB-OMD despite its one-pass updates.

  2. The experiments demonstrate a trade-off between performance and computational efficiency. This paper evaluates synthetic logistic and Poisson bandits and read world datasets, reporting regret alongside runtime and memory. The results show compute and memory savings relative to GLB-OMD while also exposing the regret degradation from compression by sketching. This provides empirical support for the method’s intended computational benefit.

Critical weaknesses
  1. The contribution appears overstated relative to the conditions needed for favorable regret. The improvement in Section 4.1 depends critically on a small spectral-tail quantity ϵm\epsilon_m, but the paper provides neither an advance guarantee that this quantity remains small nor an adaptive procedure for selecting mm. Under the stated assumptions, ϵm\epsilon_m can grow as T/(λm)T/(\lambda m), making Theorem 2 vacuous in the worst case. This sensitivity is visible in the Poisson experiments: Appendix F.2 imposes latent rank r=100r=100, and sketches of size m=120m=120 or 140140 track GLB-OMD reasonably well, whereas m=60m=60 or 8080 incur substantially larger regret. These results support exploiting favorable low-rank structure, but provide limited evidence for preserving statistical efficiency when the sketch is genuinely undersized. Moreover, the “equivalent” simplified bound in Section 4.1 understates the dependence on large ϵm\epsilon_m. These limitations substantially narrow the claimed statistical contribution.

  2. The central theoretical and computational guarantees require corrections. Appendix B.2, Lemma 3, and Appendix C.2, Lemma 6, incorrectly treat FD compression as subtracting ρsId\rho_s I_d. These identities enter the regret proof and require replacement by valid PSD inequalities. Separately, Appendix E.1 incorrectly recovers singular-vector coordinates using pre-shrink singular values and asserts an O(m)O(m) cost for the reduced projection solve without establishing the necessary structured computation. Some issues may be repairable, but the manuscript does not currently establish that a valid implementation simultaneously achieves the stated regret and O(md)O(md) amortized computation. Since this combination is the main contribution, the gaps materially weaken the case for acceptance.

Questions for authors
  1. Clarification of the claimed computational complexity. The O(md)O(md) amortized per-round complexity is central to the paper’s contribution, but Appendix E.1 does not sufficiently justify the projection cost. Could you specify the structured computation that achieves this cost, its dependence on numerical accuracy, and whether the same procedure applies to the buffered implementation in Appendix E.2? This would clarify whether the stated computational guarantee holds for the complete implemented algorithm.

  2. Conditions for statistical improvement. Could you state explicitly when the full bound in Theorem 2 improves upon GLB-OMD, accounting for all factors involving ϵm\epsilon_m? The simplified expression in Section 4.1 appears to understate this dependence when ϵm\epsilon_m is large. Since ϵm\epsilon_m can grow with the horizon, what information or diagnostic supports choosing an appropriate mm before running the algorithm? This is consequential to assessing how broadly the claimed statistical improvement applies.

  3. Empirical support for the small-error regime. How large is ϵm\epsilon_m in the reported experiments? Could you plot its prefix version ϵm(t)\epsilon_m(t) across rounds for each tested sketch size, alongside the corresponding regret curves? Appendix F.2 fixes latent rank r=100r=100, and the Poisson configurations closest to GLB-OMD use m=120m=120 or 140140, while m=60m=60 or 8080 perform substantially worse. These plots would help distinguish the benefit of representing the imposed low-rank structure exactly from the ability to tolerate a nonzero spectral tail.

  4. Novelty relative to the existing framework. Which specific algorithmic or theoretical advances go beyond combining GLB-OMD with standard Frequent Directions guarantees? Much of the proof follows the existing OMD analysis, so identifying the essential new arguments would help establish the depth of the contribution. In particular, is the favorable low-rank regret dependence specific to the proposed method, or could a comparable dependence be obtained for full-matrix GLB-OMD by retaining its log-determinant terms rather than bounding them by dlog⁡Td\log T? Clarifying this would help separate the statistical contribution from the computational savings.

1 comment
Reviewer_FvzFOpenReview ↗

Follow-up on the authors' response

Thank you for the responses and revisions. I appreciate the technical corrections and additional diagnostics. My main concerns remain the depth of the contribution and the computational guarantee.

Q4: The stated novelty still appears incremental.

1. Nonlinearity. GLB-OMD already uses the weighted Hessian

\qquad w_s=\frac{\mu'(x_s^\top\theta_{s+1})}{g(\tau)}.$$ SGLB forms the rows $a_s^\top=\sqrt{w_s}x_s^\top$, feeds them into standard FD, and uses $\widetilde H_t=\lambda I+B_t^\top B_t$. Thus, the nonlinear curvature comes from GLB-OMD, while the compression applies FD to rescaled inputs. Since FD's deterministic guarantee holds for arbitrary row sequences, the dependence of these weights on the evolving estimator does not by itself establish a new sketching argument. What additional argument is required to handle this dependence? The response has not made that distinction clear. **2. Mix loss.** The main framework for constructing an OMD confidence set through inverse regret and mix loss was already developed in GLB-OMD. The manuscript acknowledges this: Appendix D identifies Lemma 12 as Lemma 5 of Zhang et al. (2025), and Lemma 13 attributes the general-$Q$ identity used in the mix-loss decomposition to that work. The Gaussian Bregman and KL calculations in Appendix B also closely follow its analysis. The additional contribution is the discarded-curvature accounting in Lemmas 3–4, using $0\preceq D_s\preceq\rho_s I$ to introduce the sketching penalty. This is useful, but the response has not explained why this error accounting within the existing framework constitutes a substantial technical advance. **3. Approximate monotonicity.** Lemma 6 follows directly from the FD spectral comparison and full-Hessian monotonicity: $$\widetilde H_{t+1}^{-1} \preceq(1+\varepsilon_m)H_{t+1}^{-1} \preceq(1+\varepsilon_m)H_t^{-1} \preceq(1+\varepsilon_m)\widetilde H_t^{-1}.$$ This supplies a needed step, but appears to be a direct application of existing matrix bounds. Also, the idea of applying sketching to the bandit scenario can be traced back to the 2019 "Efficient Linear Bandits through Matrix Sketching" paper. Taken together, these points have not convinced me that the theoretical contribution goes substantially beyond adapting GLB-OMD with standard FD guarantees. **W2 & Q1: The $O(md)$ claim for the stated buffered implementation remains insufficiently justified.** Appendix E.1 explicitly gives $O(md+m^3+Lm)$, including $O(m^3)$ for recovering the spectral factors. Even with fixed $L$, $m\ll d$ does not suffice to absorb $m^3$ into $md$; a condition such as $m^2=O(d)$ or an additional amortization procedure is needed. For example, $m=\lfloor d^{3/4}\rfloor$ satisfies $m/d\to0$ but $m^3/(md)\to\infty$. The experimental choices also make this omission relevant. The synthetic experiments use $d\in\{150,200,500\}$ and $m\in\{60,80,120,140\}$. In the Poisson experiments, the larger sketches $m=120,140$ are the ones that remain close to GLB-OMD. At $d=150$, their ratios $m^3/(md)=m^2/d$ are 96 and approximately 131, respectively. These compare the stated complexity terms, not measured runtimes, and do not constitute an asymptotic counterexample. They make it important to clarify how spectral recovery is handled in the reported settings. Appendix E.2 explains the amortization of FD compression and the block-inverse maintenance of $G$. This does not explain how the spectral factors needed by E.1 are updated between compressions, or how their recovery cost is avoided or amortized. Figure 4(c) fixes $m=16$ and supplies orthogonal sketch rows, so it does not test this general buffered case. For the implementation described in E.1–E.2, please account for this cost and clarify whether the runtime experiments include the complete buffered weighted projection. If an additional procedure or parameter restriction is needed for $O(md)$, please state it explicitly.
Reviewer_kkHpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Frequent Directions sketching into one-pass OMD learning for generalized linear bandits. It compresses the history weighted by local curvature and uses the same low-rank geometry for parameter updates and optimistic action selection. Experiments compare regret, runtime, and memory on synthetic logistic/Poisson tasks and bandit tasks constructed from classification datasets.

Critical strengths
  1. The synthetic logistic/Poisson experiments and MNIST, Covertype, MFeat, and W8A results examine regret alongside runtime and memory while varying sketch size. This is well aligned with the motivation for high-dimensional one-pass learning.

  2. Theorem 1 incorporates cumulative shrinkage into the confidence radius, and Theorem 2 makes the spectral-tail penalty explicit in regret. This provides a principled account of compression in both update and exploration geometry, beyond simply substituting a low-rank matrix for the dense one.

Critical weaknesses
  1. The central O(md)O(md) projection and fast-implementation argument has identifiable gaps. Appendix E.1, p. 31, lines 1641–1650 writes B=Σ2−ρIV⊤B=\sqrt{\Sigma^2-\rho I}V^\top and then uses V⊤x=Σ−1BxV^\top x=\Sigma^{-1}Bx, which does not follow from the displayed definition when shrinkage is nonzero. More importantly, Algorithm 3 appends non-orthogonal rows between compressions, so the diagonal SVD representation used in E.1 does not automatically remain available. The projection cost linking the per-round-SVD algorithm to the amortized fast algorithm is therefore not fully established. This affects the core computational contribution.

  2. The spectral conditions and experimental calibration leave long-horizon statistical efficiency unclear. In addition, the experiments use empirical regularization and bonus scaling on real datasets rather than directly validating the theorem’s prescribed configuration.

Questions for authors
  1. Could you explain treatment of zero post-shrink singular values? Is this only an exposition issue, or does it affect the experimental implementation?

  2. How does Algorithm 3 perform constrained projection between FD compressions?

  3. Could you report cumulative shrinkage and regret across sketch sizes and horizons, including a setting without a rapidly decaying spectral tail?

Reviewer_LysuOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers a new method for generalized linear bandits based on using sketches for streaming data. Past work on generalized linear bandits was able to achieve O(d\sqrt{T}) regret in d dimensions over T rounds, but required O(d^2) memory and O(d^3) compute time per round, which does not scale well to high dimensions. The paper proposes a sketch-based method based on "frequent directions" sketching, shows that it can have much lower computation and memory costs and nearly the O(d\sqrt{T}) regret under some conditions.

Critical strengths

This paper is quite well written. It is clear, all terms are well defined, the logical flow is easy to follow, and the proposed method is presented clearly with clean algorithm blocks. It was a pleasure to read. Using such a simple idea to realize such a big improvement is very satisfying.

The theoretical results are where this method really shines, but the empirical results are also compelling.

Critical weaknesses

I want to make sure I'm reading the main result correctly. It looks like the regret is O((1+ε)d \tilde m \sqrt{T}) where \tilde m = m + ε d. So if ε = 0 (when the data are in an m-dimensional subspace), the regret is O(dm\sqrt{T}) -- that is, worse by a factor of m than the original method. Did I get this right? If our data is in a low-dimensional subspace, then we can get lower memory and compute requirements, but worse regret? It would be helpful to see this discussed.

I think the paper would benefit from a discussion about what was challenging about proving this result and if any key new insights were needed beyond a relatively straightforward blending of methods used in past work on sketching streaming data and generalized linear bandits.

Questions for authors

see under weaknesses

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.