End-to-End Efficient Representation Learning via Cascading Combinatorial Optimization
This addresses the computational bottleneck in similarity-based search for applications like image retrieval, though it appears incremental as it builds on quantization methods.
The paper tackles efficient similarity search by developing hierarchically quantized embedding representations, achieving state-of-the-art search accuracy on Cifar100 and ImageNet datasets while providing several orders of magnitude speedup over exhaustive linear search.
We develop hierarchically quantized efficient embedding representations for similarity-based search and show that this representation provides not only the state of the art performance on the search accuracy but also provides several orders of speed up during inference. The idea is to hierarchically quantize the representation so that the quantization granularity is greatly increased while maintaining the accuracy and keeping the computational complexity low. We also show that the problem of finding the optimal sparse compound hash code respecting the hierarchical structure can be optimized in polynomial time via minimum cost flow in an equivalent flow network. This allows us to train the method end-to-end in a mini-batch stochastic gradient descent setting. Our experiments on Cifar100 and ImageNet datasets show the state of the art search accuracy while providing several orders of magnitude search speedup respectively over exhaustive linear search over the dataset.