A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits

• URL: http://arxiv.org/abs/2501.10722v2
• Date: Thu, 23 Jan 2025 12:14:51 GMT
• Title: A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits
• Authors: Jiannan Li, Yiyang Yang, Yao Wang, Shaojie Tang,
• Abstract summary: 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.
• Score: 16.06016915165857
• License:
• Abstract: Modern decision-making scenarios often involve data that is both high-dimensional and rich in higher-order contextual information, where existing bandits algorithms fail to generate effective policies. In response, we propose in this paper a generalized linear tensor bandits algorithm designed to tackle these challenges by incorporating low-dimensional tensor structures, and further derive a unified analytical framework of the proposed algorithm. Specifically, our framework introduces a convex optimization approach with the weakly decomposable regularizers, enabling it to not only achieve better results based on the tensor low-rankness structure assumption but also extend to cases involving other low-dimensional structures such as slice sparsity and low-rankness. The theoretical analysis shows that, compared to existing low-rankness tensor result, our framework not only provides better bounds but also has a broader applicability. Notably, in the special case of degenerating to low-rank matrices, our bounds still offer advantages in certain scenarios.

Related papers

• Unraveling Zeroth-Order Optimization through the Lens of Low-Dimensional Structured Perturbations [33.38543010618118]
  Zeroth-order (ZO) optimization has emerged as a promising alternative to gradient-based backpropagation methods. We show that high dimensionality is the primary bottleneck and introduce the notions of textit and textiteffective perturbations to explain how structured perturbations reduce gradient noise and accelerate convergence.
  arXiv  Detail & Related papers  (2025-01-31T12:46:04Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Efficient Generalized Low-Rank Tensor Contextual Bandits [14.016197224603433]
  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.
  arXiv  Detail & Related papers  (2023-11-03T08:12:05Z)
• Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption [9.620832983703863]
  We introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin. We show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches.
  arXiv  Detail & Related papers  (2023-10-20T11:46:12Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits. We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
  arXiv  Detail & Related papers  (2021-07-12T21:30:41Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
  In this work, we bridge the gap by introducing the Threshold Learned Iterative Shrinkage Algorithming (NLISTA) Experiments on synthetic data corroborate our theoretical results and show our method outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-10-26T11:31:08Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)
• Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework [21.037720934987483]
  We propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. We provide a novel argument for the uniqueness of the optimum even in the absence of strong convexity. Our experiments show that the new regularizer not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry.
  arXiv  Detail & Related papers  (2019-03-09T18:54:21Z)

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.