A Bandit Approach to Maximum Inner Product Search
Authors: Rui Liu, Tianyi Wu, Barzan Mozafari4376-4383
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments Our experiments aim to (1) empirically validate the theoretical guarantees of Theorem 1 and (2) compare our method against the state-of-the-art. Datasets. Since Theorem 1 is a worst-case guarantee, we use an adversarily-generated synthetic dataset to verify its correctness. Then, we use both synthetic and real-world datasets to compare our algorithm with several state-of-the-art techniques. For each dataset, we used 104 vectors with 105 dimensions. Baselines. We compared our method against the following state-of-the-art methods: LSH-MIPS (Shrivastava and Li 2014; Neyshabur and Srebro 2015), which is a popular method for MIPS. We used the nearest neighbor transformation proposed in (Bachrach et al. 2014) and the LSH function, as suggested in (Neyshabur and Srebro 2015). We used the standard amplification procedure, i.e., the final result is an ORconstruction of b hyper LSH hash functions and each hyper LSH function is an AND-construction of a random projections. GREEDY-MIPS (Yu et al. 2017), which is a recently proposed method that uses a budget B to control the time complexity of the query time. PCA-MIPS (Bachrach et al. 2014), which uses the depth of the PCA tree to control the time-precision tradeoff. Comparison Metrics. We compare different algorithms by varying their parameters in order to explore their tradeoffs between precision and online speedup. Precision is defined as the fraction of true top K solutions in the returned top K solutions. Online speedup of an algorithm is defined as the query time required by the na ıve (i.e., exhaustive) search divided by the query time of that algorithm. |
| Researcher Affiliation | Academia | Rui Liu Computer Science and Engineering University of Michigan, Ann Arbor ruixliu@umich.edu Tianyi Wu Computer Science and Engineering University of Michigan, Ann Arbor tianyiwu@umich.edu Barzan Mozafari Computer Science and Engineering University of Michigan, Ann Arbor mozafari@umich.edu |
| Pseudocode | Yes | Algorithm 1 BOUNDEDME Algorithm (for top-K) 1: input: K 1, ϵ > 0, δ > 0, and a set of arms A 2: output: a set of K arms that is ϵ-optimal with probability 1 δ 3: 4: set S1 = A, ϵ1 = ϵ 2, l = 1 5: set t0 = 0 6: while |Sl| > K do 7: set tl = m 2 ϵ2 l log 2(|Sl| K) δl j |Sl| K 8: Pull every arm a Sl for tl tl 1 times, and let ˆpl a denote its empirical mean since the begining of the algorithm 9: Find the l |Sl| K 2 m -th value of ˆpl a in ascending order, and denote it as pl 10: Sl+1 = Sl \ {a Sl : ˆpl a pl} (more precisely, re- move l |Sl| K 2 m arms with the least empirical means thus far) 11: ϵl+1 = 3 4ϵl, δl+1 = δl 2 , l = l + 1 12: end while 13: return Sl |
| Open Source Code | No | No explicit statement or link to open-source code for the described methodology was found. |
| Open Datasets | Yes | We also compare BOUNDEDME against others on two real-world datasets, Netflix and Yahoo-Music used in (Yu et al. 2017). |
| Dataset Splits | No | No specific training, validation, or test dataset splits were explicitly mentioned in percentages or sample counts. The paper describes varying experimental parameters like ϵ and δ for different datasets, but not specific data partitioning strategies for train/validation/test. |
| Hardware Specification | No | No specific hardware (e.g., GPU/CPU models, memory specifications) used for running the experiments was mentioned. |
| Software Dependencies | No | No specific software dependencies with version numbers (e.g., libraries, frameworks, or solvers) were mentioned. |
| Experiment Setup | Yes | For BOUNDEDME, we varied ϵ, δ [0, 1]. For LSH-MIPS, we varied a [1, 20] and b [1, 50]. For GREEDY-MIPS, we varied B from 10% to 100% of the dataset size. For PCA-MIPS, we varied the tree depth in [0, 20]. We run experiments for both the cases of returning the top 5 and 10 solutions. ... In this experiment, we vary ϵ between 0 and 0.6. For each value of ϵ, we try all values of δ from the set {0.01, 0.05, 0.1, 0.2, 0.3}. For each pair of ϵ and δ, we run BOUNDEDME 20 times, each time on a different randomly generated adversarial dataset (as described above). |