Bandit-based Maximum Inner Product Search with Data-Dependent Confidence Intervals

Yoichi Sasaki, Yuzuru Okajima
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:604-612, 2026.

Abstract

Maximum inner product search is a fundamental problem in recommender systems, information retrieval, and machine learning. Recently proposed bandit-based approaches have achieved high scalability with respect to dimensionality and offer favorable precision-speedup trade-offs. However, the lengths of their confidence intervals are determined independently of the actual reward distributions, which can lead to search inefficiency in practice. In this paper, we propose a data-dependent bandit-based algorithm in which the lengths of the confidence intervals are adaptively adjusted based on observed samples. Theoretical analysis demonstrates that our algorithm guarantees $\delta$-correctness for a broad class of distributions, including all log-concave continuous distributions, and that the sample complexity can be reduced adaptively according to individual reward distributions. In experiments, our approach outperformed existing algorithms on both synthetic and real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-sasaki26a, title = { Bandit-based Maximum Inner Product Search with Data-Dependent Confidence Intervals }, author = {Sasaki, Yoichi and Okajima, Yuzuru}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {604--612}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/sasaki26a/sasaki26a.pdf}, url = {https://proceedings.mlr.press/v300/sasaki26a.html}, abstract = { Maximum inner product search is a fundamental problem in recommender systems, information retrieval, and machine learning. Recently proposed bandit-based approaches have achieved high scalability with respect to dimensionality and offer favorable precision-speedup trade-offs. However, the lengths of their confidence intervals are determined independently of the actual reward distributions, which can lead to search inefficiency in practice. In this paper, we propose a data-dependent bandit-based algorithm in which the lengths of the confidence intervals are adaptively adjusted based on observed samples. Theoretical analysis demonstrates that our algorithm guarantees $\delta$-correctness for a broad class of distributions, including all log-concave continuous distributions, and that the sample complexity can be reduced adaptively according to individual reward distributions. In experiments, our approach outperformed existing algorithms on both synthetic and real-world datasets. } }
Endnote
%0 Conference Paper %T Bandit-based Maximum Inner Product Search with Data-Dependent Confidence Intervals %A Yoichi Sasaki %A Yuzuru Okajima %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-sasaki26a %I PMLR %P 604--612 %U https://proceedings.mlr.press/v300/sasaki26a.html %V 300 %X Maximum inner product search is a fundamental problem in recommender systems, information retrieval, and machine learning. Recently proposed bandit-based approaches have achieved high scalability with respect to dimensionality and offer favorable precision-speedup trade-offs. However, the lengths of their confidence intervals are determined independently of the actual reward distributions, which can lead to search inefficiency in practice. In this paper, we propose a data-dependent bandit-based algorithm in which the lengths of the confidence intervals are adaptively adjusted based on observed samples. Theoretical analysis demonstrates that our algorithm guarantees $\delta$-correctness for a broad class of distributions, including all log-concave continuous distributions, and that the sample complexity can be reduced adaptively according to individual reward distributions. In experiments, our approach outperformed existing algorithms on both synthetic and real-world datasets.
APA
Sasaki, Y. & Okajima, Y.. (2026). Bandit-based Maximum Inner Product Search with Data-Dependent Confidence Intervals . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:604-612 Available from https://proceedings.mlr.press/v300/sasaki26a.html.

Related Material