Research map / Learning theory and algorithms / Sample complexity
Faster Maximum Inner Product Search in High Dimensions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BanditMIPS, a randomized maximum inner product search algorithm that uses multi-armed bandit adaptive coordinate sampling to get sample complexity independent of dimension d, plus a non-uniform variant BanditMIPS-α.
Problem
Maximum inner product search (MIPS) costs at least O(sqrt(d)) per atom in high dimensions, which becomes prohibitive as d grows.
Approach
Treat each atom as a bandit arm whose mean is its normalized inner product; estimate inner products by subsampling coordinates and adaptively allocate more coordinate samples to promising atoms via confidence-interval elimination, yielding complexity independent of d under gap assumptions, with no preprocessing and no nonnegativity requirement.
Key results
- On MovieLens (n=4,000, d=6,000), BanditMIPS is about 20x faster than the closest baseline (NEQ-MIPS) and BanditMIPS-α about 27x faster while returning the same answer.
- BanditMIPS sample complexity does not scale with d on the four main datasets and is roughly O(1) on Sift-1M and CryptoPairs up to one million dimensions.
- BanditMIPS returns the correct MIPS answer in all scaling trials; BanditMIPS-α outperformed BanditMIPS on 3 of 4 datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BanditMIPS instead of the closest baseline, NEQ-MIPS | MIPS · Movie Lens | speedup: 20$\times$ faster | Helped |
| use BanditMIPS-α instead of NEQ-MIPS | MIPS · Movie Lens | speedup: 27$\times$ faster | Helped |
| add non-uniform coordinate sampling (ablation) | BanditMIPS · three of four datasets | sample complexity | Helped |
| add non-uniform coordinate sampling (ablation) | BanditMIPS · Netflix | sample complexity | Hurt |
| use BanditMIPS rather than prior MIPS algorithms | MIPS · four experimental datasets | sample complexity | Helped |
| add norm-binning preprocessing (Bucket_AE) (ablation) | BanditMIPS · CORRELATED_NORMAL_CUSTOM and Netflix | scaling with n | Helped |
| apply BanditMIPS to the highly symmetric setting where the gap scales with dimension | BanditMIPS · SymmetricNormal | sample complexity scaling with d | Hurt |
Surprising findings
- On the SymmetricNormal dataset with i.i.d. atoms, the sample complexity scales linearly with d because gaps shrink as 1/sqrt(d), showing the d-independence assumption can fail.
Limitations
- Requires sub-Gaussian bounded-coordinate assumption and gaps Δ independent of d; complexity degrades to O(d) per atom when many atoms are nearly tied.
- When many arm gaps are small, the algorithm falls back to near-naive computation for relevant atoms.
- BanditMIPS-α requires an O(d log d) sort of the query, which can be costly relative to n.
Experimental setup
Datasets: NORMAL_CUSTOM CORRELATED_NORMAL_CUSTOM Netflix Prize MovieLens-1M Sift-1M CryptoPairs SimpleSong SymmetricNormal
Benchmarks: NORMAL_CUSTOM CORRELATED_NORMAL_CUSTOM Netflix Prize MovieLens-1M Sift-1M CryptoPairs
Metrics: sample complexity (coordinate-wise multiplications) speedup over naive precision@1 precision@k
Baselines: LSH-MIPS H2-ALSH-MIPS NEQ-MIPS PCA-MIPS BoundedME Greedy-MIPS HNSW-MIPS NAPG-MIPS
Builds on: successive elimination UCB BoundedME Hoeffding's inequality
Closest papers by meaning
- A Bandit Approach to Maximum Inner Product Search (AAAI 2019 · similarity 0.92)
- A Greedy Approach for Budgeted Maximum Inner Product Search (NeurIPS 2017 · similarity 0.92)
- Differentially Private High-dimensional Variable Selection via Integer Programming (NeurIPS 2025 · similarity 0.84)
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.83)
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.83)
- FraPPE: Fast and Efficient Preference-Based Pure Exploration (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.