Lune

KDD2021Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Convolutional Embedding for Edit DistanceXinyan Dai, Xiao Yan, Kaiwen Zhou, Yuxuan Wang et al.SIGIR 2020 · 27 citations
  2. Embeddings into Similarity Measures for Nearest Neighbor SearchAlexandr Andoni, Negev Shekel NosatzkiFOCS 2025 · 3 citations
  3. Kernel similarity matching with Hebbian networksKyle Luther, H. Sebastian SeungNeurIPS 2022 · 3 citations
  4. Siamese Networks: The Tale of Two ManifoldsSoumava Kumar Roy, Mehrtash Harandi, Richard Nock, Richard I. HartleyICCV 2019 · 53 citations
  5. Trajectory Similarity Measurement: An Efficiency PerspectiveYanchuan Chang, Egemen Tanin, Gao Cong, Christian S. Jensen et al.VLDB 2024 · 28 citations
Dusk over the sea between two cliffs drawn in fine vertical lines