Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces

2025/10/22 by Evgenia Shustova, Shustova, Evgenia, Marina Sheshukova +5
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Recommender Systems and Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2510.19349

Abstract

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.

Citations

• Efficient Implementation of LinearUCB through Algorithmic Improvements and Vector Computing Acceleration for Embedded Learning Systems
• Comparative Performance of Collaborative Bandit Algorithms: Effect of Sparsity and Exploration Intensity
• Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching
• Online Matching: A Real-time Bandit System for Large-scale Recommendations
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward
• Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics
• Offline Reinforcement Learning as Anti-Exploration
• Bandit Algorithms
• Efficient Linear Bandits through Matrix Sketching
• Fast symmetric factorization of hierarchical matrices with applications
• Finite-Time Analysis of Kernelised Contextual Bandits
• A projector-splitting integrator for dynamical low-rank approximation
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Gradient-based learning applied to document recognition

Related

• Initialization using Update Approximation is a Silver Bullet for Extremely Efficient Low-Rank Fine-Tuning
• BlockLLM: Memory-Efficient Adaptation of LLMs by Selecting and Optimizing the Right Coordinate Blocks
• PMSS: Pretrained Matrices Skeleton Selection for LLM Fine-tuning
• EDoRA: Efficient Weight-Decomposed Low-Rank Adaptation via Singular Value Decomposition
• ScaLoRA: Optimally Scaled Low-Rank Adaptation for Efficient High-Rank Fine-Tuning