Efficient Generalized Low-Rank Tensor Contextual Bandits

• URL: http://arxiv.org/abs/2311.01771v3
• Date: Wed, 17 Jan 2024 08:33:22 GMT
• Title: Efficient Generalized Low-Rank Tensor Contextual Bandits
• Authors: Qianxin Yi, Yiyang Yang, Shaojie Tang, Jiapeng Liu, Yao Wang
• Abstract summary: We introduce a low-rank contextual bandits model in which an action is formed from three feature vectors, and thus can be represented by a tensor. To effectively achieve the trade-off between exploration and exploitation, we introduce a novel algorithm called "Generalized Low-Rank Subspace then Refine" (G-LowTESTR) Rigorous theoretical analysis shows that the regret bound of G-LowTESTR is superior to those in vectorization and matricization cases.
• Score: 14.016197224603433
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we aim to build a novel bandits algorithm that is capable of fully harnessing the power of multi-dimensional data and the inherent non-linearity of reward functions to provide high-usable and accountable decision-making services. To this end, we introduce a generalized low-rank tensor contextual bandits model in which an action is formed from three feature vectors, and thus can be represented by a tensor. In this formulation, the reward is determined through a generalized linear function applied to the inner product of the action's feature tensor and a fixed but unknown parameter tensor with a low tubal rank. To effectively achieve the trade-off between exploration and exploitation, we introduce a novel algorithm called "Generalized Low-Rank Tensor Exploration Subspace then Refine" (G-LowTESTR). This algorithm first collects raw data to explore the intrinsic low-rank tensor subspace information embedded in the decision-making scenario, and then converts the original problem into an almost lower-dimensional generalized linear contextual bandits problem. Rigorous theoretical analysis shows that the regret bound of G-LowTESTR is superior to those in vectorization and matricization cases. We conduct a series of simulations and real data experiments to further highlight the effectiveness of G-LowTESTR, leveraging its ability to capitalize on the low-rank tensor structure for enhanced learning.

Related papers

• A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits [16.06016915165857]
  Decision-making scenarios often involve data that is both high-dimensional and rich in contextual information. We propose a generalized linear tensor bandits algorithm designed to tackle these challenges. Our framework not only provides better bounds but also has a broader applicability.
  arXiv  Detail & Related papers  (2025-01-18T10:46:12Z)
• Irregular Tensor Low-Rank Representation for Hyperspectral Image Representation [71.69331824668954]
  Spectral variations pose a common challenge in analyzing hyperspectral images (HSI) Low-rank tensor representation has emerged as a robust strategy, leveraging inherent correlations within HSI data. We propose a novel model for irregular tensor lowrank representation tailored to efficiently model irregular 3D cubes.
  arXiv  Detail & Related papers  (2024-10-24T02:56:22Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizers [30.920908325825668]
  To alleviate l1-norm in the low-rank tensor completion problem, non-rank surrogates/regularizers have been suggested. These regularizers are applied to nuclear-rank restoration, and efficient algorithms based on the method of multipliers are proposed.
  arXiv  Detail & Related papers  (2023-10-10T01:00:13Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  We show that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification. Our results indicate that interpolating with smoother functions leads to better generalization.
  arXiv  Detail & Related papers  (2023-05-30T19:37:44Z)
• On High-dimensional and Low-rank Tensor Bandits [53.0829344775769]
  This work studies a general tensor bandits model, where actions and system parameters are represented by tensors as opposed to vectors. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face of Uncertainty), is developed. Theoretical analyses show that TOFU improves the best-known regret upper bound by a multiplicative factor that grows exponentially in the system order.
  arXiv  Detail & Related papers  (2023-05-06T00:43:36Z)
• Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent [30.299284742925852]
  This paper tackles tensor robust principal component analysis (RPCA) It aims to recover a low-rank tensor from its observations contaminated by sparse corruptions. We show that the proposed algorithm achieves better and more scalable performance than state-of-the-art matrix and tensor RPCA algorithms.
  arXiv  Detail & Related papers  (2022-06-18T04:01:32Z)
• Truncated tensor Schatten p-norm based approach for spatiotemporal traffic data imputation with complicated missing patterns [77.34726150561087]
  We introduce four complicated missing patterns, including missing and three fiber-like missing cases according to the mode-drivenn fibers. Despite nonity of the objective function in our model, we derive the optimal solutions by integrating alternating data-mputation method of multipliers.
  arXiv  Detail & Related papers  (2022-05-19T08:37:56Z)
• Robust lEarned Shrinkage-Thresholding (REST): Robust unrolling for sparse recover [87.28082715343896]
  We consider deep neural networks for solving inverse problems that are robust to forward model mis-specifications. We design a new robust deep neural network architecture by applying algorithm unfolding techniques to a robust version of the underlying recovery problem. The proposed REST network is shown to outperform state-of-the-art model-based and data-driven algorithms in both compressive sensing and radar imaging problems.
  arXiv  Detail & Related papers  (2021-10-20T06:15:45Z)
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements [30.395874385570007]
  A fundamental task is to faithfully recover tensors from highly incomplete measurements. We develop an algorithm to directly recover the tensor factors in the Tucker decomposition. We show that it provably converges at a linear independent rate of the ground truth tensor for two canonical problems.
  arXiv  Detail & Related papers  (2021-04-29T17:44:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.