Optimization Can Learn Johnson Lindenstrauss Embeddings
Authors: Nikos Tsikouras
Constantine Caramanis
Christos Tzamos
Venue: NeurIPS 2024 poster (2024)
Keywords: Optimization
Non-Convex Optimization
Embeddings
Projections
Derandomization
Gradient Descent
Dimensionality Reduction
Primary area: optimization
TL;DR: We give a novel derandomization of JL via optimization, that avoids all bad local minima in the non-convex landscape by a diffusion-like process where we move through the space of randomized solution samplers, sequentially reducing the variance.

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, ${\textit{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 $\textit{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.

Optimization Can Learn Johnson Lindenstrauss Embeddings
Nikos Tsikouras
Constantine Caramanis UT Austin & Archimedes / Athena RC constantinelutexas edu
UOA & Archimedes / Athena RC n. tsikkouras@atheearr..g
Christos Tzamos
UOA & Archimedes / Athena RC
christos@tzzams.comm com
Abstract
Embeddings play pivotal role across various disciplines, offering compact rep- resentations of complex data structures. Randomized methods like Johnson- Lindenstrauss (JL) provide state-of-the-an 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: domize? Could we instead use an optimization- based approach, working directly with the data? A first answer is no: as we show, the destance-preservee objective of JL has a non-convex landscape over the space of projection matrices, with many bad stationary points. But this not the final answer.
ran-
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 deterministic (zero variance) solution, avoiding bad stationary points.
This method can also seen as an optimization- based derandomization approach and is an idea and method that we believe can be applied to many other problems.
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.
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 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 Joonson-LLinenstrann Johnson [1984] which shows that a random linear mapping can reduce the dimension the dataset while approximately preserving the L2 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, discuss below in Section 2. For this paper, the salient point is that the algorithms that
Embeddings have been used as dimensionalliy-reduuee
(JL.) lemma
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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-bann 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., 20, 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, 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 optimizatiin--aseee approaches be used to obtain a matrix that satisfies the Johnson--Lndensttrnn Lindenstrauss guarantee?
Answering this question the main goal of this paper.
Our Contributions and a Conceptual Road Map.
The main contribution of this paper is in developing framework that allows direct (and determin- istic) optimization approach to obtain the same JL guarantees as random projection. After all, is well-known that the JL guarantees given by random projection are not improvable [Larsen and Nelson, 2014, 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 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 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 specific (deterministic) projection matrix with a Gaussian distribution with that mean, and zero variance. The challenge to find path from our initial JI. sampler, to deterministic sampler (a projection matrix) whose maximum distortion is approximately as good as the expected guarantee of the original JI. sampler.
We turn this into an optimization problem by creating an objective function in the space of samplers. Our first result demonstrates that if we find second-order stationary point for this objective function, then we have solved our original problem. Specifically:
Theorem (Informal Version of Theorem 2). For data 21....,āa In E Rd and target dimension k all second-order stationary points reuchable from the origin for the objective function defined in Equation 4 have zero variance and hence correspond to fixed matrices; moreover, these matrices satisfy the JL guarantee.
Step 3: The final step requires proving the tractability of finding a second-order stationary point, i..., of solving this optimization problem. We do so using generic deterministic second-order opti- mization algorithm (see Alg. 1). Thus our result shows that our second-orde ooderr optimization algorithm successively performs reverse-diffusion-lie steps, decreasing the variance without deteriorating the quality of the solution sampler, until it has finally arrived at a deterministic solution.
Theorem (Informal Version of Theorem 3). For data Zt.... In E R and target dimension k rumning Algorithm I using Equation 4 for poly(n, k; d) steps returns a matrix that satisfies the JL guarantee.
Step 4: Finally, we show through simulations that the qualitative and quantitative results of our theory are borne out.
2 Related Work and Alternative Approaches
The JL lemma is a well-studied result studied the literature, with several simplifications and extensions of the original proof [Dasgupta and Gupta, 2003, Frankl and Maehara, 1988, Kane and Nelson, 2010, Matoušck, 2008]. It has also been shown that the JL lemma is optimal in terms of the target dimension. The authors in [Larsen and Nelson, 2017, Alon and Klartag, 2017] provide a tight lower bound on the target dimension required by the JL lemma, given a specific distortion, for any random linear mapping. In addition to these theoretical insights, there have been various approaches aimed at efficiently constructing random matrices that satisfy the JL guarantee with high probability.
One approach samples each matrix entry independently from a Gaussian distribution [Indyk and Motwani, 1998], while others utilize Rademacher and sparse Rademacher distributions [Arriaga and Vempala, 2006, Achlioptas, 2001]. Moreover, generalized sampling methods have shown that any distribution with zero mean, unit variance, and a subgaussian tail can be used [Matoušek, 2008). The Fast Johnssn--Lnddenstraue Transform employs sparse matrices and randomised transforms for efficiency [Ailon and Chazelle, 2009]. Additionally, the subsampled randomised Hadamard transform, achieves efficient embeddings by combining subsampling with randomised Hadamard transforms, maintaining a high probability of preserving the distances between points [Ailon and Liberty, 2013].
Derandomizing Jwhnson- Lindenstrauss. Derandomization is technique for developing determin- istic algorithms or algorithms that require fewer random bits, and it has proven to be a powerful theoretical tool [Kabanets, 2002]. There have been numerous efforts to derandomize the JI. lemma, with a significant focus on using pseudorandom generators (PRGs) capable of fooling statistical tests [Nisan, 1990]. These constructions aim to achieve reduced seed lengths while satisfying the JL lemma's ss norm- preesevvnn properties with te distortion and probability of failure 6. For example, the fz-streaming algorithm achieves JL family with seed length Olog d)) and with A = (E)((=))) [Alon et al., 1996]. The authors in [Clarkson and Woodruff, 2009] leveraged the use of scaled random Bernoulli matrices with (logg (1 -wise independent entries, resulting in a seed length of (log(1/8) ( log d). Additionally. PRGs that 5-fool 2 polynomial threshold functions generate JL families with seed lengths of poly (1/8) log d [Meka and Zuckerman, 2010].
Other approaches have utilized conditional probabilities and pessimistic estimators, introduced in (Raghavan, 1988], to derive deterministic algorithms for embeddings [Figebretsen et al., 2002, Bhargava and Kosaraju, 2005].
3

---

These works differ from ours in several ways. The Nisan pseudorandom generator uses a few random bits. Additionally, the authors in [Bhargava and Kosaraju, 2005] fully derandomize the Rademacher construction by [Achlioptas, 2001] using combinatorial algorithm that greedily selects the best matrix entries. Even in such a coordinate wise fashion, using gradient-descent (continuous- optimization) approach is challenging, as even then the optimization landscape is bimodal.
Overall, the key difference in philosophy, setting and ultimately results, comes from our focus on optimization: our method is a study in the power of local (first and second-order) optimization methods.
Preliminaries and Notation
In this section, we introduce essential definitions and notation for our work. We consider without loss of generality unit norm data points #....... Tn Rd which aim to project into k dimensions while preserving their norms with distortion at most O(ylog l/k). Specifically, we seek matrices that satisfy the Jolnsson-Lindenstrauss guarantee:
Definition 1 (Johnson- Grohnson-Lindenstraaee Lindenstrauss guarantee). The Nohnson-Lindenstren guarantee (JL, guar- antee) states that for given dataset II, E Rdd and target dimension the distortion for all points does not exceed O( ((Vlog n/k).
To achieve this we define linear mapping f(x) = Ax, where A E R The JL Lemma guarantees that there exists a random linear mapping that achieves this projection with high probability:
Lemma 1 (Distributional Johnson-Lindenstrnn (log(116))e{ there exists a probability distribution D over linear functions f Rd + R such that for every x E Rdd:
Lemma). For 5, E (0, 1) and k
(1If()) e [[1 - = (1 +))l=11)) 2 8 FND
Pr
There has been significant research aimed improving the construction of these random mappings. In contrast to traditional algorithms, our approach proposes learning the linear mapping directly from the data, leveraging the inherent structure to surpass worst-case performance.
Next, we give essential definitions for our optimization framework.
Definition 2. A function f Rd + R is defined to be L-smooth, for all x, E Rd it satisfies:
-MV))-f((lll < L||= vl12.
A function called Hessian Lipsehitz for all x, y Rd:
~V S K| 2112-
Below, we give the definition for approximate stationarity.
Definition 3. (Approximate stationarity). For a K - -Hessian fincctiot, f(-), we say that a point x² is pesecond-orrer stationary point (p-SOSP) if:
[Vf(2")12 SP and Amin( (V2((=")
Notation. For vectors u, V (u, v) to denote their inner product and ||ul|2 to denote the L norm. For matrix M kx we denote the element of the 7th row and 8th column by pi, and we use || F to denote the Frobenius norm. For matrix M [g and o² E to denote
N ((M, o²) d random Gaussian matrix where each element ai N N(us, We use f and 2 f to denote the gradient and Hessian operators, respectively.

---

control any deterioration of the JL guarantee of The Main Results
This section contains the full statement of our main theorems, and proof outlines. We organize the flow of this section according our conceptual outline given in the introduction. In most cases, we defer the full proofs to the appendix.
Our goal is to find matrix that satisfies the Johnsson-Lindensttrusss guarantee given in Lemma 1. Consider the natural objective function of maximum distortion:
h(A)= = max
||
ar's Fe
Step 1: The first step tells us what will not work. In particular, direct optimization over the space of matrices cannot work. Our first result shows that minimizing this maximum distortion objective via first or second-ored ooder method, is a doomed approach. In particular, we show that there exist instances which are bad local minima.
Theorem 1. For all k > 1, there exists a family of matrices A which are strict local minima for the objective function of Equation I reachable from the origin. The achieved distortion is (2(1) over a set of (k²) points, while there exist matrices yielding distortion O O(ylog k:/k) 0.
The proof of this is constructive. We construct a dataset and then show that set of matrices reachable from the origin have large constant distortion, yet these points are locally unimprovable. The full proof can be found in Appendix A.
D
Step 2: The key idea towards our final result is to perform an optimization over an extended space: the space of parameters of random Gaussian solution samplers. We first define an optimization objective over this space, and then prove properties about the resulting landscape over the space of samplers.
Gaussian solution sampler defined by its mean and variance. We only consider the case where all entries have the same variance. Thus, our new parameter space consists of pairs (M, o²), where M a projection matrix, here interpreted as the mean a Gaussian distribution, and a² is the variance parameter. Given [M, o²),, the solution sampler defined is simply: A ~ N(M, o²).
We note that new parameter space has just one additional parameter than the ambient setting.
Step 2A: We next must extend the maximum distortion objective above, to the space of random solution samplers we have defined. Consider the objective f*, defined as follows:
(' = PrA Th (A) > c].
Thus, (MM o²) is the probability that a matrix sampled according to the corresponding Gaussian distribution will have maximum distortion at least E. When we take ş = O( (0(Vl1ll))) Vlog n/k), our objective function f gives us the probability that a Gaussian solution sampler fails produce matrix that meets the JL guarantee. Hence, good sampler is one that makes f small.
We note that in the proof of the JL lemma in [Indyk and Motwani. 1998], the authors show that matrix with Gaussian entries satisfies the JL guarantee with high probability. Thus, in particular, we know that taking M 0, where 0 le zero matrix, and x² 1, gives low objective value for f*
In the context of these definitions, therefore. our goal is to find matrix M such that f f'M 0) has low objective value. To do this, we now define a related objective value, which thanks to regularization term, will allow the optimization algorithm to push us towards lower variance solutions. The technical challenge is then show that these lower variance solutions.
We define our final objective function starting from I defined above. First, we simplify the objective by applying a standard union bound and write a relaxed objective that sums for every point the probability that the point will have norm outside the required bounds after the linear transformation.
5

---

J(M = Σ (M)
& & -1 (1
For appropriately chosen value of 0 O(y n/k). we have that constraint is violated with probability greater than 1/(3n) and f(0, 1/3. The function f serves as an upper bound on the probability of generating matrix that does have the JL. guarantee, effectively acting proxy for "bad" events. Next, we add an appropriate regularization term that penalizes high variance points. Our overall objective is thus:
(M, 0 ((M, + 0²/2.
(4)
At our initialization point M = and o² = 1, the value of the regularization is 1/2, thus: g(0, < 1/3 + 1/2 < <5/6. This is crucial, as implies that following any decreasing path in leads to points with likelihood of a bad event being less than 1. Consequently, this convergence toward solution sampler maintains a positive (and (())) probability of achieving a projection matrix that satisfies the JL guarantee. The next step provides our algorithm. After that, we characterize its fixed points.
Step 2B: Algorithm is second-orde descent algorithm consisting of two simple steps: At a given point = (M, dz), if the gradient is sufficiently large, we take gradient step. If the gradient is small, we consider the Hessian; the smallest eigenvalue is sufficiently negative, we take step in that direction of negative curvature; otherwise the algorithm terminates by reporting the mean parameter M, (see Lemma for discussion on this final point). To prove correctness of the algorithm, we must show that any --SOSP will have sufficiently small variance. The proof of correctness is given Step 2C, and a bound on its running time in Step 3. We can call this algorithm recursively, to find the best distortion, using simple routine given in Algorithm 2.
We note that in principle, many first-order methods can also be used, for example, Perturbed Gradient Descent (PGD) which has been shown to converge to second-order stationary points fast [Jin et al., 2017]. We use deterministic algorithm in our analysis to enable straightforward derandomization of the JL. lemma through the optimization of Equation 4.
Algorithm 1 Hessian Descent.
3/6 Require: Vg. V'g.v= 1 K
L. K, p, Muit 0, of
0
2: + (Minit, fiit)
3: while true do
4: if V > then
5: 2++1 f- J4- - v. Vg(xt)
6: else if Vgg la S p and Amin( gzx)) < <VVKp then
7:
01 + the eigenvector corresponding to ( (zx))
8:
T++1 f- x, hug
9:
else
10:
return 00 M,
11:
end
12: +- 1 +1
13:
end while
Step 2C: Since we initialize at good solution sampler and we descent algorithm objective, we know that we can never move to a bad sampler. But that is not enough for us. For we recall that goal is not to find good randomized algorithm, but rather to find good (deterministic) JL matrix, via optimization. Thus we must show that we do not get trapped in any points that have non-zero variance.
We accomplish this in several lemmas. First Lemma we show that stationary points must have zero variance. We then refine this in Lemma 3 and show that being in p-second-ordes stationary point requires the variance to very small. We need this in order to show we can escape from any point with sufficiently large variance. Finally, in Theorem 2 show that our second-order algorithm

---

Algorithm 2 An algorithm to find optimal distortion.
Require: Vg, V2g, I., K,P; Vinitial, Egrid
1: ming +- 00
2: minlaalue <- OC
3: for each E in grid do
4: M2 < HESSIAN DESCENT(V L,
5: value -- max distortio of Mg
6: if value < mitllaaue then
7: minialue value
8: ming 6-
9: end if
10:
end for
return ming, minvalue
will not get stuck at any point with large variance, and that once we are at solution sampler with small enough variance, the mean parameter itself will enjoy (deterministically) the JL. guarantee.
In the following lemma, we show that points with non-zero variance cannot be local minima. Specifically, we show that for any given mean matrix and variance, there exists nearby mean matrix with reduced variance that improves the objective value.
Lemma 2. Let M E Rexd, and o > 0. Then for any Y E [0, there exists M E Bkxd such that:
- JMMMM'J S <2r kdlog 3v/kd
g(M, -
Proof Sketch: The proof of the lemma essentially is a small derandomization step, where we show that by taking sufficiently small variance-reducing step, even if we deteriorate the JL guarantee (i.e., the function increases), the decrease the regularizer outweighs this increase, thereby decreasing the overall value of the objective, thus showing we could not have been at local minimum.
More specifically, the proof proceeds follows. We begin with Gaussian matrix A N(M, o²) and use the additivity property to partition it: A A + A', where A >²) and A' ~ [ 02 )²). representing small additive noise and the remainder of A, respectively.
The core idea to derandomize A to achieve a decreased objective value. We extend the definition of bad event by constraining A to take values only within specific range R. Within R, there must exist a realization of A", denoted as a², which at worst, only slightly increases the probability of failure due to the truncation of the Gaussian distribution tails. By choosing this specific value a effectively derandomize AT, . As we show in the appendix, this can result in an only slightly increased probability of bad event.
We then define M' = a + M and show that the regularization term ensures an overall decrease in the objective function. The full proof can be found in Appendix A.2.
In Lemma 2, we established that any point with non-zero variance cannot be a local minimum, as there always exists nearby point with lower objective value. The next lemma addresses whether descent direction can be found at each step. We prove that this is indeed the case, specifically demonstrating that the p-second-order stationary points of the objective function in Equation 4 correspond to points with approximately zero variance.
Lemma 3. Consider F1...., Tn Rdd. Given target dimension k choose ε 0 /og The p-second-order stationary points of the objective function in Eq. 4 implies o² poly(n, k d) p 00)
We establish the lemma by examining the behavior of the variance o² at points approaching prsecond-order stationarity under the objective function defined in Equation 4. While ? large we employ series incremental reductions, and we show we can continue in this manner until 2² is reduced least to the claimed level.
Proof Sketch:
7

---

Using Taylor's theorem and the Lipschitzness of V2g. we prove that at any point oM, either the gradient will be large and thus progress will be made using first-order methods, or that the minimum eigenvalue of the Hessian will be negative and thus we can follow that direction to make progress. We then show that convergence to p-second-order stationary points gives us the desired result. Controlling the effect of the Lipschitz constant is main challenge. The full proof can be found in Appendix A.3.
Since our Algorithm I finds an approximate p-SOSP, we need an additional result that gives us a stopping criterion once the variance is small enough, and simply use the mean with controlled deterioration of the JL guarantee. That is, instead of sampling from A ~ N (M, (M,.)), d²), we can directly use M instead. This is why in line 10 of Algorithm 1, we simply return the parameter M..
Step 2D:
Lemma 4. Given n unit vectors in Rd and a target dimension choose = = O /log n such that distribution A ~ N (M, o²) satisfies the JL guarantee with distortion with probability 1/6. Then using matrix M instead of sampling from A retains the JL guarantee with a threshold increased by at most poly(o, 1/k).
Proof Sketch: By assumption, A ~ .NM, o²) satisfies A/ E11-,,1+0) with probability at least 1/6. Next, we decompose A as A = M + Z with Z (O), and invoking the JL lemma, we choose En such that Z/ E [o²(1 ED), o1 + Eo)] with probability at least 6/7. This choice ensures that there exists region in the space such that the JL guarantee holds simultaneously for both A and Z. Our goal is to establish a bound on the distortion when using M instead of sampling from A. We show that |Ma can be bounded with terms involving only ||Ar]] and ||xx| and derive an upper and lower bound on the distortion that must hold deterministically, The full proof can be found in Appendix A.4.
O
Putting the above results together, we have our first main result that shows the correctness of Algorithm 1: it will not get trapped any point with large variance, and once it does finally arrive at a point of small enough variance, the mean parameter satisfies the JL. property.
Theorem 2. Given n unit vectors in Red and target dimension k, consider the corresponding function g of Equation 4 for any E 2 C /logn/f where C is sufficiently large constant. Any P-SOSP, that a pair of parameters (M, o²)) ), of g reachable from the origin satisfies a² poly(n, k. d) pol) and goes to 0 as p + 0. Moreover, when p < 1/poly(n, k, d). M satisfies the JL guarantee having distortion at most (()).
Proof. We choose the parameter C such that g 1) < 5/6. Using Lemmas 2 and we find that a p- SOSP of g is a pair of parameters (M, o²), with d² < poly(n, k d) (() and g(M, o²) < g(0, 1). This implies that drawing sample from A ~ N o²) satisfies the JL guarantee with distortion at most & with probability 1/6.
Then, from Lemma 4, using the matrix M satisfies the JL guarantee with distortion O(e).
The above result proves correctness of Algorithm but is qualitative: we have not proved how many steps are required. Below we give a quantitative result proving that we can minimize our objective function efficiently and learn a deterministic JL embedding in polynomial time, while incurring a minor increase in the distortion. Though as mentioned, we see the main contribution of our work as centering on the optimization formulation, we note that this theorem constitutes a novel approach to derandomizing the Gaussian JL transformation.
Step 3:
Theorem 3. Given n unit vectors in T and target dimension is consider any 2 C Vooog n/ where C a sufficiently large constant. Then, running Algorithm I deterministically optimize the objective function of Equation 4 for poly(n, k. d) steps returns a matrix M that satisfies the JL guarantee with distortion at most O(e).
Proof. The first part of this theorem relies on two auxiliary results:
Lemma 5 (Sufficient Descent for Gradient Descent). If Vf p and I. the smoothness ofg. g. then for v= 1 and I++1 = It - V Vg(zz)), we have g(x++1) S g(xx) "g" Lemma 6 (Sufficient Descent for Negative Curvature Descent). If (VVg(=))12 S p and
Amin (29((z))) < -VKp, and K the Hessian Lipschitz parameter, then for h = 3 and
K
It-1 = It hu,, where in corresponds to the eigenvector of the minimum eigenvalue, we have g(2(41)= < g(xz) 3.
AVK'
8

---

The proofs of both lemmas are in Appendices A.5, A.6, respectively. Given these two results, now standard optimization techniques show that Algorithm 1 finds p-SOSP in O(1/p" -5) steps.
According to Theorem 2, choosing < (no k, d), implies that a p~SOSP for g is a pair of parameters (M, o²) with M satisfying the JI. guarantee with distortion at most O Therefore, running Algorithm for poly(n, k, d) steps returns matrix M which satisfies the JL guarantee with distortion most (s).
5 Simulations
We empirically validate theoretical results, demonstrating that first and second-order information suffices to learn high-quality embeddings. Our goal to identify an optimal matrix M that produces embeddings satisfying the JI. guarantee (see Definition 1) while minimizing distortion. We show that our method generates embeddings with significantly lower distortion compared to those obtained using the Gaussian construction of the JL lemma.
We generate unit norm dataset with n = 100 data points sion k 30 dimensions. We aim minimize the expected maximum distortion (A~N((M, () a.) [A]] (see Equation 1). We employ the first-order optimization algorithm Adam [Kingma and Ba, 2014] over 5000 iterations and compare
500 dimensions, and target dimen-
method against the average and minimum distortions over 1000
trials using the baseline matrix 7 ~ N NO, 1) (left plot of Figure 1). To calculate the distortions of method, sample from the updated mean matrix and variance each iteration.
As predicted by our theoretical analysis, we demonstrate that while the Gaussian randomized con- struction achieves satisfactory distortion levels, our method converges to a high-quality deterministic solution that nearly eliminates distortion (both plots Figure 1). At the conclusion the procedure, we calculate the distortion using the resultant mean matrix M. Interestingly, the results demonstrate that M| 12 x (i.e. almost 0 distortion), compared to approximately and 0.6 for the average and minimum distortions of the random construction, respectively. We plot the progression of the distortions and variance over the iterations in the plots of Figure 1.
This evidence highlights the effectiveness of our methodology in practice, showcasing the advantage of integrating data structure into dimensionality reduction for more accurate embeddings with provable guarantees.
Further details can be found in Appendix B.
1.4
Distortion (Optimization)
1.0
Variance
Average Distortion (Random)
1.2
Minimum Distortion (Random)
0.8
Distortion
1.0
Variance o²
0.6
0.8
0.6
0.4
MW
0.2
0.2
0.0
0.0
0
1000
2000
3000
4000
5000
0
1000
2000 Iterations
3000
4000
5000
Iterations
Figure 1: Plot of the distortion obtained through optimization over 5000 iterations vs the average distortion using random Gaussian matrix (left plot), and the progression of variance over the same number of iterations (right plot). To calculate the distortions' progression with our method, we sample from the updated mean matrix and variance at each iteration and compute the distortion. We remark that distortion plotted is a proxy for our objective in Equation 4. We observe that our optimization-basee approach converges to deterministic solution sampler. By using the mean matrix M, we achieve nearly optimal distortion, where Ma R3 |z]-

---

Conclusion
In this work, we have demonstrated that optimization used directly in the sampler space can find a deterministic JL-quality embedding. While our initial focus has been on the relatively simple random construction of the Johnson-Lindenssraass Lemma, there exist more complex randomized constructions that may offer greater flexibility. We believe that the methods we have introduced could find applicability far outside the JL setting.
Acknowledgements
This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NexiGenerationEU Program.
Constantine Caramanis was partially supported by the NSF IFML Institute (NSF 2019844), and the NSF AI-EDGE Institute (NSF 21 2112471).
References
D. Achlioptas. Database-friendly random projections. In Proceedings the twentieth ACM SIGMOD- SIGACT-SIGART sympossum on Principles of databuse systems, pages 274-281, 2001.
N. Ailon and B. Chazelle. The fast johnson-lindennsrruss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):302-322, 2009.
N. Ailon and E. Liberty. An almost optimal unrestricted fast johnson-lindensttrass transform. ACM Transactions on Algorithms (TALG), 933) 2013.
N. Alon and B. Klartag. Optimal compression of approximate inner products and dimension reduction. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 639- 650. IEEE, 2017.
N. Alon, Matias, and M. Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20-29, 1996.
R. Arriaga and S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine learning, 63:161-182, 2006.
I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.0994) 2016.
S. Bengio and G. Heigold. Word embeddings for speech recognition. Interspeech, pages 1053- 1057, 2014.
A. Bhargava and S. R. Kosaraju. Derandomization of dimensionality reduction and sdp based algorithms, In Workshop on Algorithms and Data Structures, pages 396-408. Springer, 2005.
M. Caron, H. Touvron, Misra, H. Jégou, Mairal, Bojanowski, and A. Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEF/CVF international conference on computer vision, pages 9650-9660, 2021.
K. Cho, B. Van Merriënboer, Bahdanau, and Y. Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv: /259, 2014a.
K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: |406. 1078, 2014b.
K. L. Clarkson and D. P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 205-214, 2009.
Dasgupta and Gupta. elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60-66 65, 2003.
10

---

M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19-51, 1997.
L. Engebretsen, P. Indyk, and R. O'Donnell. Derandomized dimensionality reduction with applica- tions. 2002.
P. Frankl and H. Machara. The johnson-linddenstraus lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Series B, 44(3):3355-30 1988.
T. Gao, X. Yao, and D. Chen. Simcse: Simple contrastive learning of sentence embeddings. arXiv preprint ar (04.0882), 2021.
D. Garber and B. Hazan. Fast and simple pea via convex optimization. arXiv preprini arXiv:1509.05647, 2015.
J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-660 68511, 2020.
Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse dimen- sionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-613, 1998.
C. Jin, R. Ge. P. Netrapalli, S. M. Kakade, and M. I. Jordan. How to escape saddle points efficiently. In International conference on machine learning, pages 1724-1732. PMLR, 2017.
W. B. Johnson. Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984, pages 189-206, 1984.
V. Kabanets. Derandomization: A brief overview. Current Trends in Theoretical Computer Science: The Challenge of the New Century, 1:165-187, 2002.
D. M. Kane and Nelson. A derandomized sparse johnson-lindenstraus transform. arXiv preprint 1006v 2010.
P. Khosla, P. Teterwak, C. Wang, A. Samaa, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan. Supervised contrastive learning. Advances in neural information processing systems, 33:18661- 18673, 2020.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: arXiv:1422.6990 1412.6980. 2014.
K. G. Larsen and J. Nelson. The johnson-lindenstraane lemma is optimal for linear dimensionality reduction. arXiv preprint arXiv:1411.. .4044, 2014.
K. G. Larsen and J. Nelson. Optimality of the Johnson-lindenstraul lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638. IEEE, 2017.
J. Liu, Y. Deng, T. Bai, Z. Wei, and C. Huang. Targeting ultimate accuracy: Face recognition via deep embedding. arXiv preprint arXiv: X06.:/5000.03/... 2015.
W. Liu, Y. Wen, Z. Yu, M. B. Raj, and L. Song. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 212-220, 2017.
J. Matoušek. On variants of the johnson-lindeestraus lemma. Random Structures & Algorithms, 33 (2):142-156, 2008.
R. Meka and Zuckerman. Pseudorandom generators for polynomial threshold functions. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, pages 427-436, 2010.
Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
N. Nisan. Pseudorandom generators for space-bounded computations. Proceedings of the twenty- second annual ACM symposium Theory of computing, pages 204-212, 1990.

---

M. Oquab, T. Darcet, T. Moutakanni, H. Vo, M. Szafraniec, V. Khalidov, P. Fernandez, D. Haziza, F. Massa, A. El-Nouby, al. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07199, 2023.
O. Press and L. Wolf. Using the output embedding to improve language models. arXiv preprint I50.:06608.88, 2016.
Y. Qi, D. S. Sachan, M. Felix, J. Padmanabhan, and G. Neubig. When and why are pre-trained word embeddings useful for neural machine translation? arXiv preprint (ati::/800006322 2018.
A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763. PMLR, 2021.
Raghavan. Probabilistic construction deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, 1988.
A. M. Rush, S. Chopra, and J. Weston. A neural attention model for abstractive sentence summariza- tion. arXiv preprint arXiv: www.15590000000 509000085, 2015.
B. Schmidt. Stable random projection: Lightweight, general- purpose dimensionality reduction for digitized libraries. Journal of Cultural Analytics, 3(1), 2018.
Schroff, D. Kalenichenko, and Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815 123, 2015.
O. Shamir. Convergence of stochastic gradient descent for pea. International Conference on Machine Learning, pages 257-265. PMLR, 2016.
D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 563-568, 2008.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, t. Kaiser, and I. Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
C. Xiong, V. Zhong, and R. Socher. Dynamic coattention networks for question answering. arXiv preprint w:Xiv:661..01600 2016.
Z. Xu and P. Li. A comprehensively tight analysis of gradient descent for pea. Advances in Neural Information Processing Systems, 34:21935 21946,, 2021.
X. Yi, D. Park, Y. Chen, and C. Caramanis. Fast algorithms for robust pea via gradient descent. Advances in neural information processing systems, 29, 2016.
12

---

Appendix
A Proofs of Section 4
A.1 Proof of Theorem
Theorem. For all 1, there exists a family of matrices A which are strict local minima for the objective function of Equation reachable from the origin. The achieved distortion is (1(1) over set of (K2)) points. while there exist matrices yielding distortion O( (oy k/k) + O.
Proof. We show that trying to minimize the maximum distortion of points directly can lead to getting stuck bad local minima. Specifically, there exists a set of points such that the family of matrices block and a zero
F (k+1), which consist of unitary matrices scaled by the first vector in the last column, is local minimum, and any matrix A' with || All < 1/poly (k) for some matrix F results worse maximum distortion.
Consider any matrix A' and its closest matrix A E F. A' can be written as [A A] |u] where A A/ represents the first lo x & block of A' and its last column. If we compute the polar decomposition of | = U., where is a unitary matrix and is a positive semidefinite symmetric matrix, the closest matrix A A' can be written [2U]0]. By rotating the space with U-1, assume, without loss of generality, that U = and thus [ax is a positive definite symmetric matrix.
Dataset Construction:
Define vectors e, R for i 1....,k: k. The first & components of our vectors will be either e; or e + Ey with + j. For each such vector we have 4 different versions for the last coordinate, denoted by last(ar), is given by:
las)( E (+v/5||<=]le - /15||=/|a + v7/3| -V7/3||=1|2]
Thus, the data points are constructed as è (ar, last(x))) Essentially, last(2:) the completion the depending on whether we want tight large distortion tight small distortion.
Distortion Analysis:
analyze || - | Using the Taylor expansion:
|| | ((AF) A + O(I - -Al?))
A' = ? We consider two cases based on the Since ||A -- |P- 2 + ||0112. let ||A magnitude of ||0||3
Case 1: ||01i 2 /2
In this case, there exists at least one such that o² 2 22//(2k)) We consider:
2(A A x" ' - 21) r + x² last(z)
Choosing I = ej we encounter two sub-cases, depending on the sign of xT 21)x. In both sub-cases, the term 2(Az)* -A')ē dominates the higher-order term. This holds because:
(PP221)a x + vlaat(())] (PTP-21)e + vT/3n/ > 72 11- 11--A110 A'
Then, we have:
II TF 21)x 0, select the negative value of the tight large distortion case for last(x:) -V7/3]le,,| to ensure || < || resulting in worse distortion. That is, expected norm
4/3, but instead using matrix A, we got norm 2, and any A' nearby will only increase gap.
If (P 2 2 0, select the positive value of the tight small distortion case for last(x) = v15ll 22 to ensure | > | again resulting in worse distortion. resulting in worse distortion. In this case, we expected norm 4, but instead we got norm and any A' nearby will only increase gap.
13

---

Case 2:
||0122 < <2
This implies that [P 2/ 2 72/22. Again, we encounter sub-cases. Either entry the diagonal of P case, the first-order term dominates.
- 2/ has mass 2 7/2k² or an off-diagonal entry does. We shall prove that in each
n/2k², -Diagonal Entry: [ - 2f) -f))a 2
choose a = E4. Then:
|P' 21) + x² vlast(x)) 17/2k22 x" elast(>)] > 72 -IA-A
We note here that we always match the sign of last(z) to that of x² x 27) jæ: to increase the error Now, we follow the same logic in Case to show that there always exists point with worse distortion.
LOff-Diagone Entry: [ 21)xal 7/2k² for some i ب j. choose E; Ej. Since P is symmetric, we are adding the contribution two elements, and even the diagonal elements have the opposite sign, by definition of this sub-case, their magnitude does not suffice to make the norm of the first-order term negligible:
x (P- + IJ vlast(x)) 17/2k² = ellas(()) > 72 A.
We can follow the same logic as Case to show that there always exists a point with worse distortion.
Conclusion:
In summary, in all cases, the first-order term (P (P-2f)x + + Te=TTelstte clast(r) dominates over higher-order terms O(I Alll ), and thus the sign is always determined by the first term. We have shown that there always exists a point æ causing increased distortion, thus confirming that any perturbation ||A' A| < 1 1/poly(A) results in worse maximum distortion. Thus, this family of matrices is local minimum with constant distortion.
A.2 Proof of Lemma
Lemma. Let M Rexdd, and 0 and consider random matrix A ((M,o?) Then for any 7 (0, there exists M' E poxd such that:
|M - -0 22r kdlog
3vkd
9(M', 0² -2) s g(,, (M, 02) 72/6
Proof. Consider random matrix A ~ NNM, o²). Let E (0, then using the additivity property of Gaussian distributions, we decompose into A (02 and A' ~ N(M 02 y²), ). such that A = A + A'. We note that the case for 722 o² follows from the same analysis but taking A' M deterministically.
We extend the definition of "bad event", and consider a failure when | falls outside the range
R1 = / h:1 - z), h(1 +E) for any x, or when any entry generated from A falls beyond
the range R2 := -2 log
Vied 7/3
2% log
Vkd
This extension results in an increased
probability of bad event by 72 2//3. Denote by as the 7th element of the ith row of matrix A", then:
14

---

vkd
v kd
Pr
| 2 2
log
Vi = 1 k, = .
|a 2 27,
log
7/3
7/3
1=1 j=1
47 log
V 7/33
2 exx
272
/2/99
2 exx
log
kd
22/9 kd
2 /9 /3.
We note that the inequality holds due to standard Gaussian properties.
We prove that there exists realization for A (0, within the range R2, which leads to an improvement in the objective function. To see this, we express Equation 3 as follows:
f(M, = Σ Pr PrA Axşl12 & R1)
j=1
PEAt, I| + A'æz112 $ Ri)
(5)
Let 8 denote the current value of J(M, o²) and consider the following expression of the extended definition of a bad event:
Pr [1AA + A'as R1 V A $ Rd)
PrAn, [1|A' + A'xz112 & R1] + P [A & R2]
E Σ PR 11|A4 + A'z,lla $ R1 A 1 & R2]
(6)
We lower bound Equation 6 by the minimum of the function inside the expectation to show that there must exist a realization of A7 that lies the range Rz, and increases the original objective function from 8 to 8 _
min Σ AreRa j=1
Pr 11 + A'x,112 & Rí A"] EAT Σ
PE [|A',, + A'assl2 $ R1 |A7 + +1[A7 & Rol
< 8 + 72 2/3.
Denote a² == min AVE Σx === Pr [||''r, + A'I, $ R1 AA7, then A = a + A'
N(M', 0² ?)), where M' R M. Consequently, this means that:
f(M' 02 - Σ
Pra ||Ax, Ri] 6 2/33
15

---

However, since we are working with the regularized objective in Equation 4, reducing x² to o² -r2 means that we have an overall decrease of the objective.
g(M 0² (,
A.3 Proof of Lemma
Lemma. Consider ..,..., , RR. Given target dimension k choose OlVlog n/k). The second-order stationary points of the objective function in Equation imply x² < poly(n, k d).p (o()
Assume that we have reached point = (M, Our analysis proceeds in two distinct cases based on the magnitude of a². If the variance exceeds specified threshold, we employ series of incremental reductions. This procedure continues until the variance reaches sufficiently low threshold, facilitating a transition to a scenario wherein the variance can be reduced to zero single step.
Proof.
Case 1: d² 2- (Kd &/ Choose 2-==2- )og(kd According to Lemma there exists neighboring point M' and we define v' (M', o² 72) which reduces the objective function. Then, the distance between v' and v is given by:
kdd
|| 0|12
do
74.
7/3
Denote K the Hessian Lipschitz constant, then, from Lemma and Taylor's theorem on the Lips- chitzness of V2g [Nesterov, 2013] we get:
g(v') g(0) Vg(v) (v' - v) 1 (0' -0) v2g(o) (o' u)
K 11
S
m12
K ||' 011 < g(6') g
Vg(c). (0' v) + 7( v). V29(1) (V' -v) v)
K
Vg(v) (o' v) + 2 (o' v) (2g(1) (0' () lle
21
6
This implies that either
Vg(u)= (v'-v) x- VVg(u)11
?
12
12
4d
skd 3/3
+ 72
or
K
722
w) v (V' v)
1l1
r11
<
6
12"
The last incquality implics that
K
Vkd
Amin (V V2g(v))
+
472d log
+ 74
Vkd 12 (d
6
\
7/3
7/3
1
21 4d
Vkd 7/3
+ 72
16

---

The last inequality follows from the choice of 72 we made at the beginning.
This guarantees that in each step either the gradient will be large and thus progress will be made using first-order methods or that the minimum eigenvalue of the Hessian will be negative and thus there exists direction which
follow by second-order method.
Case 2: x² s 2 2 2 (/ )
Assume that after several iterations, have reached point (M,o?), Given that the inequality in holds for all 7² v o², we select the maximum allowable reduction. This allows us to reduce the variance zero in single step. Based Lemma 2, there exists neighboring point o' (M', 0) which reduces the objective function and by following the steps as in the previous case, we get:
(o(())22 >
12 log
Vkd 0/3
+ o²
or
Amin (V2g(v)
24 [d
Lkd r/3
+ o²
This means that, convergence to a p-second-order stationary point for implies:
P.
12
4d log
Vkd 0/3
+ +
1
VVp.p.
24
4d
vkd 0/3
+ +
We will use the second inequality. First, observe that:
24
12 Ved
+ +02)
24
[4d [d
Vkd 0/3
+ a2
Therefore, we have:
1
kk + 24g
288
VKp
Because of our analysis we have that at all times during the optimization o² < 1 (refer to the regularized objective function Equation In addition to that, we assume that > k: 2 which are both natural assumptions. This in turn implies that:
< 576 kd
VKp
3vkd
576d Kp
1
576d / pkd
< 5762 K pkd
Finally, substituting in for the Lipschitz constant K, we get: x² < (nly k. d) 0(1)
This implies that a² can become arbitrarily small for an appropriate choice of
17

---

A.4 Proof of Lemma
Lemma. Given u unit vectors TR and a target dimension k, choose = O( (ol/ooog/// n//k) such that
distribution NMM, o²²) satisfies the guarantee with distortion with probability 1 1/6. Then using matrix M instead of sampling from A retains the JL guarantee with threshold increased by at most poly(o, 1/k).
Proof. We start with the assumption that -11-2112 E (1 (1-E E, + with probability at least / Expressing A as = M + Z where Z N(0, o²), and from the JL lemma, we can select Eo such that
| 7 E [o - Eo), o2 t0)]
with probability at least 6. hold simultaneously.
7- This ensures there exists an overlap where both inequalities for and Z
Our goal determine how much worse the distortion becomes when using M instead of sampling from the distribution A.
Using the triangle inequality we have:
1 k Mr + Zr - Zall S k
M
| + Zxrl2 + k. k 11A2112 + +1
Zx
which by squaring both sides and using the JL guarantee for A and Z, we obtain:
2
M
Aa
+
||r||a/|
Zx + 7: 2
k
2a
+1
+
VI+ev1 + +o +
k
2/20 +
<1+et
k
For the lower bound, using the Schwarz incquality and the JL guarantee for A and Z, we have:
1
1 Mr + Zx
Mx
2
k
2k
k
1
2k: Amxl1 |
> 1/2(1 - -5) 0² EO)
2 1/2(1 -5) - 02
Combining these results, we observe that replacing A with M maintains the JL. guarantee with an increased distortion threshold, bounded by at most poly(a, 1/k).
A.5 Proof of Lemma
Proof. We use Taylor's theorem on the smoothness of g and get:
Lemma. If [[ p. then for and ae+1 It Vg(zt), have g(x441) S rg² 2
g(ø,)
18

---

g(a(+1) S g(x,) + (Vg(z)), I2+1 xz) + 2
21+1
- 22112
Lu²
=((z)) (x)
2 [V
= -g(,) -1- - Lu up?.
We 1 to get the following:
g(x141) S g 2 u
A.6 Proof of Lemma
Lemma. ([()ll and Amin ((=g( <-VKp, then for h 3/2 and F++1 It + hui
K
where corresponds to the eigenvector of the minimum eigenvalue, we have g(Fi41) S g(xz) 3p"
4vK"
Proof. We use Taylor's theorem on the Lipschitzness of 2 [Nesterov, 2013] and get:
K
g(x++1) S g(x)) + (g(())) Fe+1 -xt) + V2 (2)(())( - x2), (Fe+1 xx)) + 6
| - x2
1/211 +
K
= -(x)) + h(Vg(zt) un) +
2
6
S g(xz) + hp h² Kpp
We can use
3/F VK
get the following:
3p/p
g(x++1) S g(x))
2vK
B Details of the Experimental Evaluation
We explore the behavior of a distortion optimization process using by minimizing the expected maximum distortion given dataset through a series of optimization descent steps. We show that while the Gaussian randomized construction can achieve good enough distortion, our method goes beyond that and achieves almost zero distortion, by taking into account the structure of the data.
B.1 Proxy for the Objective Function.
To do this, we use the maximum distortion (Equation 1) with a proxy of our objective function (Equation 4) and aim to minimize:
S(M [A(A)) + 0²/2.
(8)
To do this the gradient of Equation 8 with respect the parameters of interest (M,o²)
V V(M EANN(M.2)) + 0²/2.
(9)
19

---

We can approximate the expectation by taking yi....., .N samples drawn from N(M, o²) and using Monte Carlo sampling we get the approximate gradient:
N
1 02) = h(v:).
V (M
Σ
N 2=1
B.2 Methodology of the Simulation.
We generate a unit norn synthetic dataset of = 100 data points in d' = 500 dimensions and our goal to project these into k = 30 dimensions while minimizing f. We our optimization for 5000 iterations, using the Adam optimizer [Kingma and Ba, 2014] with a learning rate of 0.01 and batch size N 20. At every iteration, calculate the maximum distortion and store it. We demonstrate that, through this procedure, the model consistently reduces the distortion and the variance, thus converging deterministic solution sampler.
We compare our method with the Gaussian random construction, that is we draw Z ((, 1) and calculate Z To have fair evaluation draw 1000 such matrices and calculate the mean and the minimum distortion obtained.
Our results show that we consistently learn matrix with close to optimal distortion, that is | & 1, while the randomized construction achieves an average value of Zuvg 13 and minimum value mm ~ 1.6.
C Proving Smoothness and Hessian Lipschitzness
Denote by fl...., Pk. the rows of matrix M and Ai...., As the rows of the Gaussian random matrix A. Then we can write the objective function:
n Σ = Pr
g(M.o
-
2A1 +.... 2,), & [k(1 E), k(1 +(1++))] +
2
j=1
n
21) + t... x²
(px, (en, 23)2 O
0²
Pr Xi
81.3 =
$ R
+
o²
o2
2
σ²
Σ
Pr (x)) & [k(1 - =)/0², //////,K11111 k(1 + +]]]]
+
2
n
k(1-))
f Aaya
0o
0²
Σ
fk.o, (2)d2
f (z)dz
+
2
J=1
(6(1-e)
(k(1-8) 02
(b(1+))
0²
Σ
+ Fk.o,
-Fris,
+
(10)
02
2
where fu.8,, Fk,6, are the pdf and edf of x2, the non-central chi-squared distribution with & degrees of freedom and 6, (pr, +... 21,) as the non centrality parameter, respectively.
o²
Note that, instead of considering the i mean variables directly, it is simpler to reframe the problem. Specifically, we can view the function in terms of the inner product variables ui...., U/. and o², where v; (14, at) and μ4 is the i-th row of the matrix M.
Therefore, our problem reduces to proving the Lipschitz continuity of the Gradient and Hessian continuity with respect these new variables. This approach simplifies the calculations significantly.
20

---

To establish that the Gradient and Hessian is Lipschitz continuous, we examine the case for j = 1.
The extension to j = n. can be handled through summation. Let = o². Then, we have ||:1
1 +
Our function from Equation 10 becomes
k(1 -
k(1 [((++)) T/2
g Uk:
Fk,5
where (x) = 5/2
Σ
(6/2)'
Qr 2ÿ), with Q(2;k)
7(kk/2a/2) F(k/2)
and 7(V, () is the lower
==
incomplete gamma function.
Notice that taking the derivative gives extra part with increased degrees of freedom (F)
-1/2Fg, + 1122
C.1 Gradient Lipschitzness.
Denote by the elements of Vg. and note that in this section to simplify notation we use to represent 1|.. Then the derivatives are:
k(1
-8)
1i
k(1 - -e)
(U1,...,,
FR,5
+
Fk+2,
T
7
+ Vi FE.8
k(1+
U1 Fk+2.6
k(1++)
||u112
k(1 =E)
|1011
k(1 4(1--)
k(1 -
h(1 -
(V( T)
Fk.0
Fk42,6
f4.5
27
2r
72
||011
k(1 + $)
|
k(1+E)
k(1 + 5)
k(1 + E)
Fu.
+
FK42.8
+ 72
fK.
27
27
To prove Gradient Lipschitzness of we can bound the Frobenius norm of the Hessian Vag. by 2 the elements of V2g. Below calculate and bound all the derivatives:
Denote
1
k(1 -6) 5)
2uf
k(1-
D2 g(L,,..,
+
F
+
Fx+2,5
7
7
72
7
k(1 -11-E) k(1-E) E)
A(1+
+
Fk44.8
+
FR.
72
72
2v
k:1 k(1+E)
2
k(1 +
+
F
Fk+
72
72
Here we used the triangle inequality and the fact that the edf is bounded by Notice how there is no dependency on ||v| since the range are integrating over with the cumulative distribution functions
independent of ||u|| Consequently, ||o|| large, the probability becomes exponentially small.
Thus, we can bound this by:
4 D2 00 ((1,, Ul..... Uh, T) <
8 72
1 72
50
T
Next, we have:
D2 De,,,glui,,.. T)
024y FR.5
k(1 =)
20,0/ FR
k(1 -
02U 7
F F
k(1 -s)
72
T
U;Ui FR.s 22
h(l +
2000y FR42.6 72
k(1 [|1+E]
0:4y ?2
k(1
F
21

---

Thus, we can bound this by:
DD2 ee gui,,.., Uky r)
80zug
<0
1 72
x²
Next, we have:
D2 - ....,........................... T)
Vi
we||o|12
FE.
h:1 6(1-8)
+
22//|uu|1
Fk+2,8
k(1-
72
73
72
T
vallu112
k(1 k()-=))
1ak(1 vak(1-E) =e)
k(1-5)
FR444.8 73
r3
T
u1Ai(1 -)
k-11 -8)
vi|lo|12
k(1 + E)
SK+28
+
FR.
73
72
73
7
20;
20:11e113
2v1
k(1+
1:/11112 FR448 73
k-1 +
FK42,6
+
73
-2
01A(1
+
+))+
k<(1
21h(1 + E)
h(1 +E)
fu.6
+
fit2,6
3
x2
Thus, we can bound this by:
4u
Sui1le11
20,k(1 - E)
20,k(1+ +
k 0
- Uk T) S
+
73
73
73
73
Next, we have:
|1/12
|101|2
A:(1 [))
+ (--
||0||
||0|13
k(1 - 8)
D2 ((u,,..... 7k)
Fk.
Fk+26
x3
47
7
2
73
|0||
k(1 E)
+
Fk+
4
||u||2 1
- E))
2k((1 -t)
(k(1 - =))
k(1 (((1-)
+
+
fk.6
274
73
27
1o|12ki(1
- E)
(k(1-)
fk42.8
2
k(1
E)
(8/2))
k(1 -E)
55/
5/2
(1++2))/2 1)5x+25
73
j!
1=0
|
||0||
k(1+s)
|
|01122
k((++) +
k(1
F
+
Fx
47
2-4
33
T
|0|1
k(1+ +E)
Fk444.6
4
T
[|u1|2k(11 55
2k(1+e)
(1:(1 + E))²
k(1 ((1+8)
Sh.
274
73
274
T
101121(11 +
k(1+e)
fK42,8
2T
T
k(1 + E)
(8/2))
k(1 (e)
1
6/2
((1 22)/2j/22222 1)fk+2j
+
33
j!
2
1=
Thus, can bound this by:
22

---

4/10112
2||0|1
||01|8k(1 -)
3k(1 - 8)
(k(1 - z))²
73
7
73
27
|| |1 (11
+ E)
3k(1+
+ (k(1 + E))
+
7
73
274
hE
s 0
74
Overall, for D2 U,,0 we have:
Ser max
| ( (k. 7) "1
S min(1177))
Similarly, for D2 De 9. obtain Eu,,, I min, (1/72) for D De. we obtain Sour min, (k:/73) and for D we obtain fr,r I min, 2
Substituting M and o² back, and assuming that minimum value for o² we allow og we have that the Frobenius norm of the Hessian is bounded from:
1 S Σ Su,o, + E3 +
Σ
2
+2
2
Seni
ifj
1=1
$ ke2
+ Eg,,0² + 2(h
2h
1)<2.
+ 2k.52
Therefore we get:
h +0
1222
dk T
k 06
+
+
S poly (k, e, d, 1/00).
Finally, since we are summing over n data points the smoothness Lipschitz constant is poly(n,k,e,d 1/on)
C.2 Hessian Lipschitzness.
To prove Hessian Lipschitzness of g will use the definition and the third-order derivatives. Denote by 3 the elements of Vag. Below we calculate and bound all the third-order derivatives:
30%
k(1
-6)
6y;
3ud
k(1 -))
D Do
g(11 gel.....,
F
+
Fk+2,5
72
3
7
3v,
3u
k(1 ((1-E)
21
k(1-E)
Fx+4,5
Fk+6,5
72
3
T
T
30,
k(1 {((+E))
6o
30
(((++)
Fk.6
+
Fx42,8
72
3
72
33
3t
3u?
(((++))
3
k(1+
+
Fk+4.8
F
2
3
Thus, we can bound this:
240
16
D
(0r ..., ,k, r)
+
<
72
3
73
23

---

Here we used the triangle inequality and the fact that the cdf is bounded by 1. Notice how there is no dependency on ||v| since the range we are integrating over with the cumulative distribution functions is independent of ||o|| Consequently, if ||0|| is large, the probability becomes exponentially small.
Next, we have:
D 9(11),,))(1............. T)
Vi
k(1 -E)
20
+
Fk+26
k(1
72
73
72
73
5
30;
k(1 Ee)
k(1 EE)
Fk+4.8
Fk+6,8
T
7
U/
k(1 +e)
30;0
k(1 6(1+))
PR,
FK42,8
3
72
73
T
30;0} 2
k(1 +
k(1 +6)
FK-4.8
F 73
73
T
Thus, we can bound this by:
Svy
16
D3 (
rk, o) 5
+
72
73
73
Next, we have:
D3 De
7),
UzUgUR
FR.b
k:(1 -8)
30;uyuk
F 33
73
7
7
30euee Uk 73
k(1
k(1-E) E)
Fx44.6
FR+0.6
7
7
ULUjUK
k(1 +2)
30sUgUk FE42,6 7
k(1+e)
FE.8 73
7
30,23 Uk 73
k(1 ((1+E)
122yUk
(k(++))
+
F FR44.6
FR40.6
7
7
Thus, we can bound this by:
160;0,
D3
o u6, (.,
T)
< 73
7
Next, we have:
24

---

|u]
30,
of
1111112
Fi.5 k(1-8)
D Uk. 7)
72
73
73
71
6v
30
||
2|10112
1
(k(1-E) - E)
+
Fi
F2+208
74
7
72
3uf
3u;
|
k(1 =E)
23 1
[((--)
F844.8
FRIGS
7
73
33
7
k(1
E)
o2 - 5)
k(1 k(1-o)
fI.
73
74
T
k(1 E)
20f -E)
k(1 -()--)
fu42.
73
7
k 8)
k(1 -6)
SK+4.8
||012
3u?
1/1121112
EE)
F2.8
72
73
73
Guz
30
2||0|12
1:1 +8)
+ 72
FK42,8
3
7
73
30 1ull
3u?
||u||2]
1(1 (((++))
1z 11112
k(1 +
+
Fk+4.6
+
F FR66,6
71
73
73
k(1 +
+5)
k(1 (E)
SK.8
73
71
A(1+
2nfk(1 +0)
1:(1 +
fk+2,6
73
74
T
u +))
k(1 +()+
1K44.8
74
T
Thus, we can bound this by:
8|108|
24v²
16 111
(M1...., 5
+
+
72
7
7
74
2k(1 - 5)
40² -)
+
33
74
2k + e)
1o
$)
<
73
74
7d
Next, we have:
25

---

3
11121
h(1 E)
D3
bi (01.-.. uk, r)
F
73
74
30/091/u112
h(1 E)
Fx426
73
7
30su B0tty//o|12 30e
k(1 =)
Fx+18
74
73
kk(1 -)
Fk+6,6
TO
T
20;0zk(1 - =)
k(1 - 8)
40;0zk(1 66)
k(1 ((1-=) T
Sk.88
fx+2.8
T
74
20;
E)
k(1 -6)
fk+4.6
T
30;0
0203110112
k(1 +E)
F
3
T4
60,0y
30/25/10112
k(1 +
Fk+2,8
73
74
T
30;oy ||011
30zuz
(k(1+E)
+
Fu+1.8
74
73
0 1112
k(1++)
FR+G.
71
7
20,0sk(1 +
k(1++)
40:0sk(1 +
[k1
SN.8
+
fu42.8
74
71
20;0zk(1
+E)
(k(1+E)
f1+1,88
74
T
Thus, we can bound this by:
240,0, 33
16 |0|2
160,0,k(1- - 8) +
161,e,k(1 +
k
DD ((1,,,, U6, 7),
+
74 +
- (1z))
74
74
Next, we have:
26

---

2v
2110||/er
2//1011
2/
k(1-E) -E)
D3 gl ,..,,, Uk, 7)
FR.s
73
T1
47
7
61/0|1203 0z
30s11u11*
2v:
k(1 =()
Fk+2,6
74
47
73
11|lo|1
20al|u112
21|1o11
h(1 -1)-))
275
47
7
0/
||0||
k(1-
FR+0,6
4
T
30,k(1 - E)
B/||u|1 12(((1 - E)
vi(k(1 (16(1--))) -E))
(((--)
+
+
f6.5
71
2-
75
7
0s|lu||<k(1 -6)
30,k(1 -s)
vi(A((1 - =s))²
k(1 - 8)
+
SK+2,8
76
74
27
a²
Us |||u||2A(1 -
k(1-E)
fx-118
275
1,k(1 - 5) e 6/2
00
(6/2))
k(1 =))
Σ
((I -1)]//1))/22//
74
j!
1=
02k(1 - 5)
(8/2)²
k(1 -
e
6/2
((1 + 2j + 2)/2 1) 1)fk+2j22
74
j!
T
1=0
22
2|10|
1
U1
1||lul|
A(1 +2)
Fk.6
74
4
7
6||u||30,
30.1|u/14
20;
k(1 + k(1++)
F142,8
74
475
73
7
20/||u112
2z
47
k(1+E)
+
Fk+1.8
275
74
47
7
k(1
FR40,6
4T
30ck(1 +E)
Uillu||2B(1
+
U, (1(11 + +))
k(1 +
fr.8
74
275
75
uallu|12 +s)
3ock(1 +E)
U. (x(k11 + =))
[k[+
fK+2.8
75
71
27
u=|lv||<k(1 e)
k(1+s)
fM44.8
275
T
0, + +
(5/2)²
k(1 + +
71
e
8/2
j!
((1 22)/2 - 1)fk+2j
1=0
1,k(1 + 5)
(8/2)'
+(]+
-//2
j! ((1 + 2j + 22/2 1)fx42442
74
1=0
Thus, can bound this by:
27

---

Sv;
20 20/l0|/25
vil|all
14u/||o||
(0.,..9901,...... r) v
73 +
+
7t
27
47
80;k(1 -9)
2vz
w1 || 2x(11 =) 30r(k(1 ())
+
74
75
27
S0,ki1 + +E)
20l/|u1|2 + E)
3e,(k(1 + E))²
74
7
27
75
Next, we have:
3/
31/211
|1:116
k(l-E)
D3 (VI,,.
T)
+
PR.
71
2,5
876
4||w||1
3||0||1
31/u01121
k(1 -)
FK+2,8
75
876
44
7
3/10/16
3||0||
k:1
E)
||0||66
k(1
FR444,8
Fk40.8
876
2,5
876
T
2k{(1 6)
||0||*k(11
8)
6k(1 8)
2(k(1
=e)
||0|| - E))2
k(1 ((1--)
+
Sk.b
7
276
74
75
47
[1 -6)
A|lu||2a(1 - 6)
||0|| (x(12( - =))2
1(1
+
Su42.6
76
5
476
||01|<>(11 - 8)
k(1 ((1-6)
fx+4.8
47
7
||01122(11
31(11 =))
(k(1 E))
8
(6/2g²
k(1 - E)
+
-8/2
Σ
(I: + 2j 22
275
74
275
j!
1=0
[1012 E)
(6/2)²
hrl 1)(-E)
-8/2
8/2
Σ
(1/2 + j)fx42221
27
j!
i=0
k(1
8
(8/2)/
(k(1-e)
8/2
Σ
((1 (1++2)/22 - fxt2
74
j!
T
==
28

---

||
3|10||
|0||
k(1 +
+
Fu.s
x¹
2,
8-
7
|||w|||
3/10/11
3/1u/1 27
k(1 +
Fk+2,8
75
87
3|1u|1*]
k(1 +1
|1
+(]+s)
+
FR44.6
+
6R
8
275
7
8r
+
||0||| [kll
((1 +
6k:(1 + +8)
2(k(1
+ +o))²
||0112
(A:(1 + +2))2]
[k(1 [k(1+
+
+
7
27
74
75
47
4||2|12k( +
|ool2(((1
+ +
()(++E)
fu+2.8
76
75
47
T
|0l1
+
k(1 6))
Sk+4.8
47
T
||011P((11 - E)
3k(1
+ E)
(As(1 + +))
(6/2)²
k[1 + (((++)
+
+
6/2
Σ
(k: 2j 2)fx+25
275
74
275
j!
f=0
|0112k(1 + E)
(8/2)²
h(1 + E)
6/2
Σ
(1/2 + j){k+2+2j
27
j=0
k(1 + 5)
(8/2)
[k(1+e)
5/2
22)/2 1)2fxt2
j!
T
Thus, we can bound this by:
1/|
7|/0///
||a||6
DD
uk, T) 5
+
74
7
75
8/1 2k(11 e)
[|| 6)
10k(1 -e)
5(k(1 E))² =))2
[101|(k((1 =))2
75
476
275
276
7 [|10| =))
476
|| + E)
7||0||*b(1+ +
10A(1 +
5(k(1 +c))
||0]| +)))
+
476
74
27
27
[11 + +E)
476
62
6
Overall, for D2 u, we have:
VVD g( " UR,
Pur.
max U UE.T
< max
1 0 u r),
DD g(U ok, 7) DDJ bl 7)
< mmjn(k/7²).
Similarly, for D2 Do,,y9 we obtain Poway S (ke/(k) for D2 D2 we obtain Peur S (N2=2/7)))) and for D2 we obtain Pr,- 6k2 /75).
Substituting M and o² back, and assuming that the minimum value for o² we allow is of we have:
29

---

[M (M2,, 02)1== Σ Igu..e (MI, - Iri. (M2, (M - 9 (M2, (M2, o
+ Σ 2 [9m., (MI. - Ivc,e (M2, oā)]² +2 - *
[ (M,, - -u (M,, ož)] 1
i=1
$ (kpt +82.00 + 2(k d 2/ 1) 1)
2kpp
[[M] - (M)) (o og)²].
Therefore, we get:
122
1222
k3 0
HH - - 03)1 $
+
+
+
[I - (MM, o3)1l
= poly k,,, d. 0o 2
[|M (M2, oB)1l-
Finally, since po,y,n,k,,, d, 1/00).
summing over data points, the Hessian Lipschitz constant, is
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract summarizes the findings presented in the paper, while the in- troduction summarizes the motivations behind our work and reviews prior research in the field.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [No]
Justification: The paper focuses primarily on presenting a theoretical result. As such, it does not delve into empirical validations or practical implementations where limitations would typically be more relevant. The nature of the result is more abstract and formal, and thus, potential limitations about practical application, empirical robustness, or computational scalability are not directly addressed within the scope of this work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
31

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All lemmas and theorem statements provide the full set of assumptions. We provide proof sketches in the main body and complete and correct proofs for all our results in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We present simulation in the main body to demonstrate our method, along with a detailed explanation of the simulation process.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
32

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
We have provided the code for our simulations in the supplementary material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
guides/CodeSuumise
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the relevant information about the simulation in the main body and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide all the relevant information about the simulation error in the main body and appendix.
Guidelines:
33

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Given that this is a theoretical result, the experiments did not require substantial computational resources, and conducted all experiments on local machines.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: https://neuu //tp::///neuuueeeeeeee wwwparips.ccppuuueeeee httppppllie.ccccccuueeeeeeeeeeee
Answer: [Yes]
Justification: The research conducted in the paper fully adheres to the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
34

---

Justification:
Since this is theoretical result, we do not foresee any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Since this is theoretical result, we do not think it has any risk of misuse
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
35

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. . com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "vf2tLWSKRq", "reviewer": "Reviewer_pTrj", "summary": "This paper investigates the problem of using optimization-based approaches to learn Johnson Lindenstrauss(JL) embedding. The authors proposed a new framework to achieve the JL guarantee via optimization, instead of the traditional randomized methods. Similar with diffusion models, the authors proposed a novel method that uses optimization in an extended space of random Gaussian solution samplers, which circumvents direct optimization in non-convex landscape. Their approach uses second-order descent, gradually reduces the variance without increasing the expected distortion of the sampler, then can identify a specific projection matrix with the Gaussian distribution. Overall, theoretical guarantees and empirical results demonstrate that this method efficiently achieves a deterministic solution that satisfies the JL guarantee.", "questions": "1. Could you explain the statement in lines 215-216? Are the values of 1/(3n) and 1/3 derived based on the chosen value of $\\epsilon$?\n\n2. Line 336, there is a typo  “appplicability”. \n\n3. Regarding the notation $\\rho$-second-order stationary points($\\rho$-SOSP), the paper uses $\\rho$-second-order stationary points in some sections and uses $\\rho$-SOSP in others.", "limitations": "No potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is well-written. The state of the art is well discussed by an extensive literature review. The proposed method combining optimized-based approaches and Johnson Lindenstrauss embeddings is an innovative contribution to the field. \n\nThe paper is technically sound, provides rigorous theoretical analysis and proofs.", "weaknesses": "It would be helpful to understand the main results if section 4 could be more organized, such as using subsections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and for recognizing the innovation in our work.\n\n**Q: Could you explain the statement in lines 215-216? Are the values of 1/(3n) and 1/3 derived based on the chosen value of** $\\epsilon$**?**\n\nA: Yes, that's exactly correct: you can choose $\\epsilon$ appropriately to get a $1/(3n)$ probability for any data point to violate the threshold constraint. Thus, if you sum these $n$ probabilities you get $1/3$.\n\nThank you for your keen observations on the paper's typo and notation inconsistencies, we fixed it and made it consistent throughout.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8JIVTvYSea", "reviewer": "Reviewer_y6Yv", "summary": "The paper considers using the optimization method to \"learn\" the Johnson Lindenstrauss transform. The paper first shows that the naive objective may not be good enough -- there are stationary points that are sub-optimal. Instead, they consider the way that optimize the random Gaussian space rather than the concrete matrix. Then the authors give an optimization method and show that using this way, every stationary point is a good point and claim that this gives way to deterministic learns the JL matrix. Finally, the paper gives an experiment that shows the advantages of the proposed method.", "questions": "1. I am still a little confused about the main conclusion of the results of this paper. That is -- it gives a deterministic construction of the JL lemma, or it gives a better optimization way and it works well empirically? (as the author mentioned, the bound of the JL lemma can not be improved)\n \n2. The equation (4) is about probability, and B.1 says they use Monte Carlo sampling, however, would it means that the proposed method still contains some randomness part? \n\n3. In the experiment section, the paper compares the proposed method with the JL lemma. It will make this stronger if the comparison with equation (1) is also given.", "limitations": "See above questions.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis of this paper is very interesting. To my knowledge, there are very few results about analyzing the landscape of the learned sketching matrix and this paper gives a strong analysis. The experiments also show the advantages of the proposed method. The presentation of the paper is also good.", "weaknesses": "I am still confused about some parts of the paper. I can raise the score if the authors can adjust this. (see the below question)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and for appreciating our analysis. We agree with you that there are not many results analyzing the landscape of the learned sketching matrix. We address your questions below.\n\n**Q: [...] it gives a deterministic construction of the JL lemma, or it gives a better optimization way and it works well empirically? [...].**\n\nA: The answer is both. Our main contribution is that one can use direct optimization to efficiently find \"good\" embeddings. We propose a novel optimization objective and analyze its performance from two distinct angles:\n\n- First, we take a worst-case perspective where we theoretically show that optimization can obtain matrices that are always at least as good as the guarantees of the Johnson Lindenstrauss (JL) lemma. This establishes that our method is worst-case optimal, given that the JL lemma guarantees cannot be improved. \n- Secondly, we demonstrate that for practical instances that have non-worst-case structure our method significantly outperforms the randomized JL construction. This is intuitively right as the randomized construction is data agnostic. \n\nAlong the way, we establish that naive methods do not have these guarantees as the space of projection matrices is non-convex and has bad local minima. Instead, we need to work in a slightly larger space of samplers, and there, our optimization method will find a deterministic solution.\n\nIn summary, our theoretical guarantees state that we can achieve the JL guarantee in the worst case, but we showcase that in practice we can go beyond that, if the data allows it.\n\n\n**Q: The equation (4) is about probability, and B.1 says they use Monte Carlo sampling, however, would it means that the proposed method still contains some randomness part?**\n\nA: As mentioned above our main contribution is the analysis of this novel objective. While this objective (Equation 4) involves probabilities, they have a closed form expression and can be calculated exactly without any sampling or randomness. Our main result is that second-order stationary points of this objective function satisfy the JL guarantee. Using a deterministic second-order method, we achieve a **truly derandomized construction** of a JL matrix. \n\nHaving established these theoretical guarantees, in our empirical evaluations, we do not insist on deterministic computation as our focus is now different (as explained in the previous question). Instead, for simplicity, we use Monte Carlo sampling and randomized first-order methods which are known to converge to second-order stationary points with high probability [Gao et al. 2017]. In practice, second-order methods can be prohibitively expensive but are not necessary for convergence to second-order stationary points if randomness is allowed.\n\n\n\n**Q: In the experiment section, the paper compares the proposed method with the JL lemma. It will make this stronger if the comparison with equation (1) is also given.**\n\nA: Thank you for the suggestion. However, as we show in Theorem 1, optimizing Equation 1 directly in the matrix space can lead to bad solutions with high distortion, whereas our method is guaranteed to succeed. Since we showed that taking the approach of Equation 1 can (provably) fail, we decided that it would not provide a fair comparison and would distract from the comparison with the randomized JL construction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hSRlBtrfZY", "reviewer": "Reviewer_XscG", "summary": "The paper proposes to calculate the embedding matrices used in the statement of the Johnson-Lindenstrauss lemma using optimization instead of randomization. The proposed algorithm is a Hessian descent. Authors prove that the algorithm finds the matrix of minimum distortion. Numerical results display the findings", "questions": "The paper's main claim is that mean distortion embeddings are computationally well studied: spectral methods (SVD / eigenvalue) methods calculate those. Authors claim that the min (instead of mean) distortion method is what they want to find. Can authors explain why the relaxation of f* to f using the probability bound in Eq (2) and invoking union bound to obtain (3) does not reduce the max to a sum. The entire promise of the method is to work with the max directly to minimize distortion. It appears that relaxation of max to a sum using the union bound drops the nice property which was the primary motivation of the work. Can you explain what I am missing of misinterpreting?", "limitations": "scaling the method up and a clear argument why relaxation of Eq (3) is not making the problem trivial would impove the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "JL is a well celebrated result used for proving existence of optimal (low distortion) embeddings. It is stated in the formal result of JL that such embeddings can be found in polynomial time. But we often rely on randomization to exhibit them. It is useful to have an algorithm to calculate the embeddings. The paper tackles a well motivated problem and their presentation is clear and clean.", "weaknesses": "The paper lacks complexity analysis of the algorithm. The algorithm proposed requires a full eigenvalue decomposition at every step. It is prohibitive to use this method in any practical scenario. A discussion on the complexity and how to scale the method up (using randomized methods??) would be nice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and valuable comments. We appreciate your recognition of the strengths of our work and have addressed your concerns below.\n\nYou raise a valid point about the computational expense of second-order methods. We should clarify here that our primary result is that second-order stationary points of the objective function in Equation 4 satisfy the Johnson Lindenstrauss (JL) guarantee. We opted to use a deterministic second-order method in order to achieve an end-to-end derandomized construction of a JL matrix.\n\nHaving established these theoretical guarantees, in our empirical evaluations, we do not insist on deterministic computation as our focus is now different, namely to demonstrate that for practical instances that have non-worst-case structure our method significantly outperforms the randomized JL construction. Instead, for simplicity, we use Monte Carlo sampling and randomized first-order methods which are known to converge to second-order stationary points with high probability [Gao et al. 2017]. In practice, second-order methods can be prohibitively expensive but are not necessary for convergence to second-order stationary points if randomness is allowed.\n\n**Q: [...] Can authors explain why the relaxation of f\\* to f using the probability bound in Eq (2) and invoking union bound to obtain (3) does not reduce the max to a sum.**\n\nA: The primary objective of our paper is to use optimization-based methods to find matrices that satisfy the JL guarantee, ensuring that the maximum distortion over all points does not exceed a specified threshold $\\epsilon$. As we mention, this is a different (and more challenging) objective than what spectral methods like PCA control. Our goal is to show that this can be accomplished deterministically, directly using optimization. We show, however, that if one tries to do this naively, e.g., by directly working in the space of projection matrices, then significant challenges arise (to put it simply, such an approach will not work) because the landscape of the optimization in this space is non-convex, with bad local minima. \n\n\nTherefore, another approach is needed. We do not change the objective -- as you correctly point out, working with the maximum is important in getting the guarantees we wish to give. Instead, we change the optimization approach, and the **space** in which we optimize. To do this, we work in the space of **solution samplers** rather than in the space of projection matrices. So at any current step in the optimization, the current \"solution\" of the optimizer is not a deterministic projection matrix, but rather a distribution from which one samples such a matrix. For our framework, therefore, we define a new objective $f^*$ (Equation 2) which represents the **probability** of generating a matrix $A$ with maximum distortion exceeding $\\epsilon$.  This is the probability that a given solution sampler generates a projection matrix that does not match the JL guarantee. We clarify that *we do not use the union bound to reduce the maximum distortion to the sum of all distortions*. Instead, we reduce $f^*$ to $f$  (Equation 3), i.e. to the sum of probabilities of each point having distortion larger than $\\epsilon$ using a randomly generated matrix $A$. To make it more clear, we note that when no randomness is involved, i.e. $\\sigma^2=0$, we have that $f^*(M,0) = 0$ means that no projected data point has distortion larger than $\\epsilon$ and $f(M,0) = 0$ measures how many projected data points have distortion larger than $\\epsilon$. Additionally, it is important to see that, $f^*(M,0) = 0$ if and only if $f(M,0) = 0$. \n\nUltimately, we show that our process converges to a distribution with no variance, hence, a specific projection matrix that satisfies the JL guarantee.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5E87bXBiG0", "reviewer": "Reviewer_WAK9", "summary": "This work shows that a deterministic optimization procedure can find a matrix $A$ that satisfies the Johnson Lindenstrauss guarantee. That is, a matrix $A$ maps a set of $n$ vectors to a lower dimensional space while preserving all pairwise distances up to some chosen multiplicative distortion. Typically, $A$ is constructed by sampling it from a random matrix distribution with i.i.d. entries. The authors prove that attempting to directly optimize the entries of $A$ through an optimization procedure by minimizing the maximum distortion is prone to being stuck at local minima. However, the authors show that by optimizing the mean of each entry and the entry-wise variance of the distribution $A$ is sampled from, one can maintain a fixed probability of $A$ being a JL-embedding while at the same time guaranteeing the entry-wise variance ‘sigma’ goes to zero. They then show that, when ‘sigma’ is sufficiently small, one may use the optimized expectation of $A$ as the embedding matrix while only slight increasing the maximum distortion, thereby deterministically finding the desired JL embedding matrix $A$. They show that $\\rho$-SOSPs (second order stationary points) have sufficiently low variance when $\\rho$ is small, and finally show that a method for finding $\\rho$-SOSPs suffices to solve the designed optimization problem.", "questions": "In the conclusion, you mention the potential for this approach in applications beyond the Johnson Lindenstrauss setting. In your approach for the JL setting, you upper bound the failure probability of the distortion guarantee via the union bound in eqn. (3). This formulation of the objective function seems difficult to translate to other sketching guarantees on $A$ (e.g., projection cost preservation, L2-subspace embedding, affine embedding). Is there any intuitive reason why it may be possible to formulate a relaxed differentiable objective function when the embedding guarantee must hold over an uncountable number of points?\n\nHow does learning a JL embedding relate to learning embeddings for application areas discussed in the introduction? In particular, how do you see the results of this paper affecting that line of work? As mentioned above, I think it would be helpful to expand on the link between your result and the motivation of deep learning embeddings given in the intro.", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall, the paper is clearly written and well-motivated. The intuition of the approach and analysis is easy to follow.\n\nThe key idea of optimizing the parameters of a random matrix distribution to preserve the JL-embedding property while reducing the entry-wise variance seems like an innovative approach. The authors point out the original space of matrices is contained in this larger probabilistic space, since a deterministic matrix $A$ is equivalent to having mean $A$ and zero variance. Hence, this can be seen as a probabilistic relaxation of the original matrix optimization problem. I have not seen this type of relaxation used in the field of matrix sketching or more generally randomized numerical linear algebra before, and I believe it may be useful for other problems in the area. I am not very familiar with diffusion models, so I cannot speak on the novelty of the approach regarding that area.\n\nThe empirical results are also strong in the sense that they show this procedure for constructing a JL embedding tends to achieve a much lower distortion factor than randomized constructions for a fixed dimension.", "weaknesses": "The iterative method to find the matrix $A$ takes $\\operatorname{poly}(n, k, d)$ steps, i.e., the complexity is proven to be polynomial but not explicitly determined. Since the paper is primarily theoretical with only limited experiments, it is unclear how efficient this method is in practice.\n\nWhile the results seem very interesting theoretically, the paper could be strengthened by pointing out some practical applications where this improved deterministic JL embedding would be useful. In the applications I am familiar with, oblivious JL embeddings are needed due to the large number of points in the high-dimensional space (e.g., preserving k-means loss). The authors point to embeddings in deep learning as motivation. It is unclear to me as to how the authors expect progress in understanding deterministic JL embeddings to relate to these embeddings in deep learning. Additional clarification of this point would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review of our paper. We appreciate your recognition of the strengths and innovation of our work. We understand your concerns regarding the practical efficiency of our method and the explicit determination of its complexity. While our paper primarily focuses on the theoretical foundations, we acknowledge the importance of practical applicability. This is why we included an experiment to showcase the superior performance of our method, even with access to only first-order information, demonstrating its computational efficiency. \n\nWe understand your questions but first, we want to clarify what we mean by \"our approach\". Our approach includes lifting the domain to the distributional space, then optimizing the distributions’ parameters and finally obtaining a deterministic solution using variance reduction. We view this as the main contribution of this paper as we provide a different optimization paradigm and show that optimizing indirectly using our framework can be provably better than direct optimization. We expand on this further below.\n\n**Q: [...] Is there any intuitive reason why it may be possible to formulate a relaxed differentiable objective function when the embedding guarantee must hold over an uncountable number of points?**\n\nA: There are many applications of our approach in theoretical results. Often times specialized randomized constructions are used for several tasks (distance preserving in $L_2$ or other norms, $L_0$ sampling, linear-sketching or other tasks as you mentioned). Our hope is to be able to recover these results directly via optimization methods and potentially derandomizing them via variance reduction. While in the case of JL the initial distribution (Gaussian) was very simple, in other applications much more clever constructions are required. Can optimization recover these embeddings in a principled way? While the specific formulation may vary, the underlying principle of optimizing distribution parameters to achieve low variance and deterministic solutions could be adapted to other contexts.\n\n\n**Q: How does learning a JL embedding relate to learning embeddings for application areas discussed in the introduction? In particular, how do you see the results of this paper affecting that line of work? [...].**\n\nA: This is an interesting question. As a first point, we are optimistic that since our contributions include effectively, a new perspective and analysis, it opens the door to studying embeddings of points that have some specific structure. Secondly, in broader terms, deep learning is a general framework applicable to many domains. Frequently in deep learning, we utilize encoder architectures to generate embeddings from data, for which we want certain properties to hold. In this sense, learning a JL embedding can be viewed as a special case of an encoder, where our focus is on preserving the $L_2$ distance. Our work contributes to the deep learning field by informing the design of algorithms of this general principle. Specifically, we show that optimizing directly can lead to “bad” solutions and to overcome this one can choose to optimize in the “richer” space of distributions. \n\nIn addition, we believe our results provide a crucial link between deep learning practitioners and theorists who offer theoretical guarantees through classical/randomized algorithms. Embeddings are central to the success of neural networks, driving much of their empirical achievements. However, the lack of provable guarantees for these embeddings remains a significant challenge. By introducing provable guarantees for embeddings via optimization, alongside an algorithmic approach that is still essentially as tractable as a direct optimization approach, our work bridges these two perspectives. It allows us to harness the power of optimization while ensuring that the embeddings maintain desired properties. \n\nThis combination not only enhances the reliability of embeddings used in deep learning but also provides insights into the underlying dynamics contributing to the empirical success of deep learning models. This approach can potentially illuminate why certain embeddings work well in practice and how they can be systematically improved with theoretical backing.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful and constructive feedback on our submission. We appreciate the time and effort they have dedicated to reviewing our work. We are encouraged by their positive reception, noting that they found our contribution innovative (pTrj, WAK9), our analysis strong (y6Yv), and the problem well-motivated (XscG).

Furthermore, reviewer WAK9 noted that our probabilistic relaxation can be useful for other problems in matrix sketching and randomized numerical linear algebra. Reviewers y6Yv and WAK9 also found our experiments valuable, highlighting that they effectively demonstrate the advantages of our method.

We address the reviewers' comments below and will incorporate all feedback.

Meta-review: This paper proposes a data-driven optimization approach for embedding that is in stark contrast to randomized methods such as the Johnson-Lindenstraus (JL). While solving the distance-preserving objective is intractable over the projection matrices, this paper considers an optimization program that searches a solution on a larger space and shows that the algorithm converges in polynomial steps.

The idea that optimizing over an expanded and carefully constructed space is novel. The results are sound, in the sense that the solution returned by the optimization program satisfies the JL guarantee; this is the first result of its kind which does not rely on random projection matrix. Empirically, it appears that the optimization-based approach enjoys lower distortion. That said, there are also weaknesses regarding the computational cost and empirical viability of the method as it relies on second order optimization.

Overall, the techniques presented in this paper may inspire a new line of research and represent a nice addition to NeurIPS program.
Decision: Accept (poster)