analiza aiqbench
This research addresses computational bottlenecks in high-dimensional linear bandits by introducing a cluster-aware sketching mechanism to reduce update costs from $O(d^2)$ to $O(l^2d)$. The proposed CS-LB algorithm mitigates the risk of vacuous regret associated with heavy spectral tails while preserving full covariance information within clusters. Experiments confirm that this approach effectively balances efficiency gains with robust sublinear regret performance.
Efficient Linear Bandits via Cluster-Aware Sketching
arXiv:2609.27594v1 Announce Type: new Abstract: We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension $d$ of the feature vectors leads to growing computational costs of $O(d^2)$ at each round of update. Traditional sketching-based methods such as SOFUL reduce computation via fixed-size matrix sketching, yet run the risk of incurring vacuous linear regret when the spectral tail of the data is heavy and the sketch size is inadequately selected. To guarantee regret convergence and effectively reduce computational costs, we introduce a clustering mechanism and propose the Cluster Sketch Linear Bandit (CS-LB) algorithm. Our method preserves the full covariance information in each cluster to guarantee robust sublinear regret without spectral-tail vulnerabilities, performs cluster switching by assigning a sentinel for each cluster, and reduces per-round update computation to $O(l^2d)$ via a tunable sketch size $l<d$. Experiments on synthetic datasets demonstrate that our method consistently maintains a favorable trade-off between efficiency and regret.
Abstract:We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension $d$ of the feature vectors leads to growing computational costs of $O(d^2)$ at each round of update. Traditional sketching-based methods such as SOFUL reduce computation via fixed-size matrix sketching, yet run the risk of incurring vacuous linear regret when the spectral tail of the data is heavy and the sketch size is inadequately selected. To guarantee regret convergence and effectively reduce computational costs, we introduce a clustering mechanism and propose the Cluster Sketch Linear Bandit (CS-LB) algorithm. Our method preserves the full covariance information in each cluster to guarantee robust sublinear regret without spectral-tail vulnerabilities, performs cluster switching by assigning a sentinel for each cluster, and reduces per-round update computation to $O(l^2d)$ via a tunable sketch size $l<d$. Experiments on synthetic datasets demonstrate that our method consistently maintains a favorable trade-off between efficiency and regret.
Machine Learning (cs.LG)
arXiv:2609.27594 [cs.LG]
(or arXiv:2609.27594v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.27594 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 255 cuvinte
Subiecte conexe
PIRAMID: Progress and Plans
LessWrong · 27 iul. 2026
J++ Lens: Jacobian Filtering Enables More Faithful Workspace Lenses
LessWrong · 8 oct. 2026
News
Quantum Computing Report · 25 iul. 2026
Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
arXiv · 22 iul. 2026