Escaping The Curse Of Dimensionality In Similarity Learning: Efficient Frank-wolfe Algorithm And Generalization Bounds

Abstract

Similarity and metric learning provides a principled approach to construct a task-specific similarity from weakly supervised data. However, these methods are subject to the curse of dimensionality: as the number of features grows large, poor generalization is to be expected and training becomes intractable due to high computational and memory costs. In this paper, we propose a similarity learning method that can efficiently deal with high-dimensional sparse data. This is achieved through a parameterization of similarity functions by convex combinations of sparse rank-one matrices, together with the use of a greedy approximate Frank-Wolfe algorithm which provides an efficient way to control the number of active features. We show that the convergence rate of the algorithm, as well as its time and memory complexity, are independent of the data dimension. We further provide a theoretical justification of our modeling choices through an analysis of the generalization error, which depends lo

Stats

• citations17
• S2 citations—
• github stars0
• HF likes0
• heat score9.41
• arxiv keyliu2018escaping

Related papers

• Deep Metric Learning Using Similarities From Nonlinear Rank Approximations (2019)2.26
• Efficient Optimization Methods For Extreme Similarity Learning With Nonlinear Embeddings (2020)3.58
• Super-sparse Learning In Similarity Spaces (2017)5.24
• Generalization Bound For Kernel Similarity Learning (2016)0.00
• Discriminative Learning Of Similarity And Group Equivariant Representations (2018)0.00
• Sparse Online Relative Similarity Learning (2021)2.26
• Generalization Analysis With Deep Relu Networks For Metric And Similarity Learning (2024)0.00
• Sharing Matters For Generalization In Deep Metric Learning (2020)8.35