Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908821696282624 |
|---|---|
| author | Shustova, Evgenia Sheshukova, Marina Samsonov, Sergey Frolov, Evgeny |
| author_facet | Shustova, Evgenia Sheshukova, Marina Samsonov, Sergey Frolov, Evgeny |
| contents | In this paper, we introduce PSI-LinUCB, a scalable variant of LinUCB that enables efficient training, inference, and memory usage by representing the inverse regularized design matrix as a sum of a diagonal matrix and low-rank correction. We derive numerically stable rank-1 and batched updates that maintain the inverse without explicitly forming the matrix. To control memory growth, we employ a projector-splitting integrator for dynamical low-rank approximation, yielding an average per-step update cost and memory usage of $O(dr)$ for approximation rank $r$. The inference complexity of the proposed algorithm is $O(dr)$ per action evaluation. Experiments on recommender system datasets demonstrate the effectiveness of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19349 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces Shustova, Evgenia Sheshukova, Marina Samsonov, Sergey Frolov, Evgeny Machine Learning 68T05, 65F30 In this paper, we introduce PSI-LinUCB, a scalable variant of LinUCB that enables efficient training, inference, and memory usage by representing the inverse regularized design matrix as a sum of a diagonal matrix and low-rank correction. We derive numerically stable rank-1 and batched updates that maintain the inverse without explicitly forming the matrix. To control memory growth, we employ a projector-splitting integrator for dynamical low-rank approximation, yielding an average per-step update cost and memory usage of $O(dr)$ for approximation rank $r$. The inference complexity of the proposed algorithm is $O(dr)$ per action evaluation. Experiments on recommender system datasets demonstrate the effectiveness of our algorithm. |
| title | Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces |
| topic | Machine Learning 68T05, 65F30 |
| url | https://arxiv.org/abs/2510.19349 |