- 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 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
-
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.
-
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
-
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 , but the paper provides neither an advance guarantee that this quantity remains small nor an adaptive procedure for selecting . Under the stated assumptions, can grow as , making Theorem 2 vacuous in the worst case. This sensitivity is visible in the Poisson experiments: Appendix F.2 imposes latent rank , and sketches of size or track GLB-OMD reasonably well, whereas or 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 . These limitations substantially narrow the claimed statistical contribution.
-
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 . 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 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 amortized computation. Since this combination is the main contribution, the gaps materially weaken the case for acceptance.
Questions for authors
-
Clarification of the claimed computational complexity. The 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.
-
Conditions for statistical improvement. Could you state explicitly when the full bound in Theorem 2 improves upon GLB-OMD, accounting for all factors involving ? The simplified expression in Section 4.1 appears to understate this dependence when is large. Since can grow with the horizon, what information or diagnostic supports choosing an appropriate before running the algorithm? This is consequential to assessing how broadly the claimed statistical improvement applies.
-
Empirical support for the small-error regime. How large is in the reported experiments? Could you plot its prefix version across rounds for each tested sketch size, alongside the corresponding regret curves? Appendix F.2 fixes latent rank , and the Poisson configurations closest to GLB-OMD use or , while or 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.
-
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 ? Clarifying this would help separate the statistical contribution from the computational savings.
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.