Optimization Can Learn Johnson Lindenstrauss Embeddings
Nikos Tsikouras, Constantine Caramanis, Christos Tzamos · 2024
Read Optimization Can Learn Johnson Lindenstrauss Embeddings by Nikos Tsikouras, Constantine Caramanis, Christos Tzamos (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07242.txt.
Introduction
Nikos Tsikouras, Constantine Caramanis, and Christos Tzamos ask in 2024 whether optimization can learn the embeddings that random methods now provide. Embeddings squeeze complex data into compact forms while keeping distances between points close to true.
The classic random method carries strong worst case guarantees, but it ignores any structure in the data. Direct optimization of the distance keeping goal turns out to be a trap: the landscape is non convex and full of bad stopping points. Inspired by diffusion models, the authors optimize over samplers of solutions instead, slowly shrinking their spread. The path ends at a single firm solution and dodges the bad points.
Catalog record
| CREATOR | Nikos Tsikouras, Constantine Caramanis, Christos Tzamos |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-07242
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimization Can Learn Johnson Lindenstrauss Embeddings Nikos Tsikouras, Constantine Caramanis, Christos Tzamos Abstract Embeddings play a pivotal role across various disciplines, offering compact representations of complex data structures. Randomized methods like Johnson-Lindenstrauss (JL) provide state-of-the-art and essentially unimprovable theoretical guarantees for achieving such representations. These guarantees are worst-case and in particular, neither the analysis, nor the algorithm , takes into account any potential structural information of the data. The natural question is: must we randomize? Could we instead use an optimization-based approach, working directly with the data? A first answer is no: as we show, the distance-preserving objective of JL has a non-convex landscape over the space of projection matrices, with many bad stationary points. But this is not the final answer. We present a novel method motivated by diffusion models, that circumvents this fundamental challenge: rather than performing optimization directly over the space of projection matrices, we use optimization over the larger space of random solution samplers , gradually reducing the variance of the sampler. We show that by moving through this larger space, our objective converges to a deterministic (zero variance) solution, avoiding bad stationary points. This method can also be seen as an optimization-based derandomization approach and is an idea and method that we believe can be applied to many other problems. 1 Introduction Embeddings are foundational across diverse disciplines, offering compact representations of complex data structures. Algorithms across different domains leverage embeddings to capture nuanced relationships between data points, improving efficiency and effectiveness in processing. Within this field, there are distinct lines of work. Embeddings have been used as dimensionality-reducing tools, while preserving important structures in data. They have been a major research focus for years, and have been a key ingredient in several algorithmic applications such as graph sparsification ( Spielman and Srivastava, 2008 ) , nearest-neighbor search ( Indyk and Motwani, 1998 ) , hashing ( Dietzfelbinger et al., 1997 ) and digital research ( Schmidt, 2018 ) . A celebrated result in this area has been the Johnson-Lindenstrauss (JL) lemma Johnson (1984) which shows that a random linear mapping can reduce the dimension of the dataset while approximately preserving the L_{2} norm of all points, with high probability. JL embeddings give bounds on the maximum distortion over all the points. Many variants have been developed and studied, as we discuss below in Section 2 . For this paper, the salient point is that the algorithms that enjoy theoretical guarantees are for random projections drawn from a distribution over projection matrices. To the best of our knowledge, even among derandomization of JL-type techniques (e.g., Clarkson and Woodruff (2009) , and see Section 2 for further discussion), there are no guarantees for optimization-based algorithms that directly attempt to minimize a distortion objective. On the other hand, in the last decade, embeddings have risen to prominence across various tasks in deep learning. In encoder-decoder architectures, embeddings act as intermediary representations to solve a broad range of challenges in natural language processing and speech processing, ( Bengio and Heigold, 2014 ; Cho et al., 2014a ; Cho et al., 2014b ; Qi et al., 2018 ; Rush et al., 2015 ; Xiong et al., 2016 ) . In the domain of face recognition, embeddings encode facial features into concise vectors, enabling precise identification and matching ( Liu et al., 2015 ; Liu et al., 2017 ; Schroff et al., 2015 ) . Furthermore, contrastive learning techniques utilize embeddings to emphasize disparities between similar and dissimilar instances, thereby augmenting the discriminative capabilities of models ( Gao et al., 2021 ; Khosla et al., 2020 ; Radford et al., 2021 ) . In contrast to the JL-type results, in the above applications these embeddings are learned using optimization as part of the (pre)training process ( Caron et al., 2021 ; Oquab et al., 2023 ; Press and Wolf, 2016 ; Vaswani et al., 2017 ) . Though their empirical success is remarkable, the non-convex landscape of the optimization process makes obtaining theoretical guarantees a key challenge. Another important related area is the extensive body of literature dedicated to employing optimization techniques for Principal Component Analysis (PCA). PCA aims to find linear embeddings that capture the optimal average distortion in the data, thereby reducing its dimensionality while preserving as much information as possible. The last decade saw significant success of direct matrix optimization in various PCA-like settings ( Garber and Hazan, 2015 ; Shamir, 2016 ; Xu and Li, 2021 ; Yi et al., 2016 ) . Though clearly there are similarities to the JL objective, the difference between guarantees on the maximum perturbation (JL) vs the average perturbation (PCA) are significant, and one reason why the techniques pioneered for PCA have yet to be applied successfully to JL. Nevertheless, the empirical success of optimization in neural networks, and its theoretical success for PCA-type objectives, motivate us to revisit the JL low-distortion embedding task (see Section 3 for the exact definition of the JL guarantee ), and ask the question that to the best of our knowledge, has yet to find an answer: Can optimization-based approaches be used to obtain a matrix that satisfies the Johnson-Lindenstrauss guarantee? Answering this question is the main goal of this paper. Our Contributions and a Conceptual Road Map. The main contribution of this paper is in developing a framework that allows a direct (and deterministic) optimization approach to obtain the same JL guarantees as random projection. After all, it is well-known that the JL guarantees given by random projection are not improvable ( Larsen and Nelson, 2014 ; Larsen and Nelson, 2017 ; Alon and Klartag, 2017 ) . Moreover, established derandomization techniques based on conditional expectation and other methods have long been available ( Raghavan, 1988 ; Engebretsen et al., 2002 ; Bhargava and Kosaraju, 2005 ) . The key conceptual steps on the way to our main result are as follows: Step 1: We first show that the optimization landscape in the ambient space of projection matrices is not favorable, and in particular, any attempt to directly minimize distortion over this space using first or second-order methods, is destined to fail. Theorem (Informal version of Theorem 1 ) . The maximum distortion objective considered as a function in the space of matrices has many suboptimal local minima. Step 2: Given the above negative result, a different approach is required. We draw inspiration from diffusion models and solution samplers ( Bello et al., 2016 ; Ho et al., 2020 ) . Rather than optimize in the space of matrices, we optimize in the larger space of (mean, variance) parameters of Gaussian distributions over embedding matrices. Thanks to the original JL theorem, we know an initial choice of parameters that define a solution sampler whose expected distortion is small: zero mean and unit variance. Akin to diffusion, we then seek to sequentially decrease the magnitude of the variance, without increasing the expected distortion of the sampler. Note that the space of matrices is properly contained in this space of samplers, as we can identify a specific (deterministic) projection matrix with a Gaussian distribution with that mean, and zero variance. The challenge is to find a path from our initial JL sampler, to a deterministic