Efficient Optimization Methods for Extreme Similarity Learning with Nonlinear Embeddings
Bo-Wen Yuan, Yu-Sheng Li, Pengrui Quan, Chih-Jen Lin
Abstract
We study the problem of learning similarity by using nonlinear embedding models (e.g., neural networks) from all possible pairs. This problem is well-known for its difficulty of training with the extreme number of pairs. For the special case of using linear embeddings, many studies have addressed this issue of handling all pairs by considering certain loss functions and developing efficient optimization algorithms. This paper aims to extend results for general nonlinear embeddings. First, we finish detailed derivations and provide clean formulations for efficiently calculating some building blocks of optimization algorithms such as function, gradient evaluation, and Hessian-vector product. The result enables the use of many optimization methods for extreme similarity learning with nonlinear embeddings. Second, we study some optimization methods in detail. Due to the use of nonlinear embeddings, implementation issues different from linear cases are addressed. In the end, some methods are shown to be highly efficient for extreme similarity learning with nonlinear embeddings.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Convolutional Embedding for Edit DistanceXinyan Dai, Xiao Yan, Kaiwen Zhou, Yuxuan Wang et al.SIGIR 2020 · 27 citations
- Embeddings into Similarity Measures for Nearest Neighbor SearchAlexandr Andoni, Negev Shekel NosatzkiFOCS 2025 · 3 citations
- Kernel similarity matching with Hebbian networksKyle Luther, H. Sebastian SeungNeurIPS 2022 · 3 citations
- Siamese Networks: The Tale of Two ManifoldsSoumava Kumar Roy, Mehrtash Harandi, Richard Nock, Richard I. HartleyICCV 2019 · 53 citations
- Trajectory Similarity Measurement: An Efficiency PerspectiveYanchuan Chang, Egemen Tanin, Gao Cong, Christian S. Jensen et al.VLDB 2024 · 28 citations
