- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the Multnomial Logistics Bandits, aiming to address the computational and storage bottlenecks faced by existing algorithms due to the maintenance and operation of high-dimensional Hessian matrices. The author proposes EOFD-MLogB to maintain the low-rank spectrum representation of cumulative Hessian, and transform the high-dimensional spectrum norm calculation in optimistic reward into an eigenvalue problem of . Theoretically, this method reduces the main calculation complexity and spatial complexity of each round to and respectively, and gives the regret bound of sketching error controlled by Hessian truncated spectral tail. Experimental results show that EOFD-MLogB can significantly reduce running time and memory overhead on synthetic data and multiple real data sets, while maintaining a regret performance close to OFUL-MLogB.
Critical strengths
- The research problem is well motivated and has practical significance.
- The paper provides theoretical analysis and relatively thorough experimental evaluation.
Critical weaknesses
Theorem 1 requires a relatively large regularization parameter , which scales at least linearly with . For instance, under the multinomial synthetic setting , this condition requires , whereas Appendix C.1 reports using . More importantly, under the theoretical choice of , the accumulated Hessian 's norm is relative small compared to such large , suggesting that the full Hessian matrix is already close to an isotropic matrix and that its directional curvature information may have limited influence.
This raises a concern about the connection between the theoretical guarantees and the empirical benefits of Hessian sketching. In the theory, this work requires in a extremly large regularization parameter where preserving the principal Hessian directions may be less important. Moreover, the experiments use a much smaller regularization parameter outside the stated theoretical conditions. It would be valuable to clarify this gap and examine whether the proposed method maintains its empirical advantages under theoretically admissible regularization parameters.
Questions for authors
see weakness part
We thank the reviewer for their appreciation of our work and raising this concern. We will take the opportunity to clarify the typo and gap between theorems and experiments.
[1] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Advances in Neural Information Processing Systems, volume 36, pages 29741–29782, 2023.