Research map / Learning theory and algorithms / Combinatorial and search optimization

Optimization Can Learn Johnson Lindenstrauss Embeddings

NeurIPS 2024 · Learning theory and algorithms › Combinatorial and search optimization · approach: Constrained neural network optimization · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that direct optimization of JL projection matrices has bad local minima, then optimizes over Gaussian solution samplers (mean, variance) with second-order descent so variance shrinks to zero, yielding a deterministic matrix satisfying the JL guarantee.

Problem

Johnson-Lindenstrauss embeddings are usually built by random projection; the question is whether a deterministic optimization-based method can directly find a matrix satisfying the JL distortion guarantee, given that the distortion landscape over matrices is non-convex.

Approach

Optimize over the larger space of Gaussian solution samplers (mean matrix and variance) with a regularized failure-probability objective, using a deterministic second-order (Hessian descent) method; the variance is pushed to zero along the way, so the final mean matrix is a deterministic JL embedding, inspired by diffusion-style variance reduction and derandomization.

Key results

• On synthetic data (n=100, d=500, k=30), the optimized mean matrix gives ||Mx||^2 approximately 1 (near-zero distortion), versus average ~2 and minimum ~1.6 for 1000 random Gaussian matrices (as stated in the appendix; main text reports ~1 and ~0.6).
• Theory: any rho-second-order stationary point reachable from the origin has variance sigma^2 < poly(n,k,d)*rho^O(1), and for small rho the mean matrix satisfies the JL guarantee with distortion O(epsilon).
• Theorem: running the deterministic Hessian descent for poly(n,k,d) steps returns a JL matrix with distortion O(epsilon).

Measured effects reported in the paper

Surprising findings

• The distortion objective over the space of projection matrices has many strict bad local minima, so first- and second-order methods applied directly to matrices are expected to fail.

Limitations

• Experiments are limited to a single small synthetic dataset with n=100, d=500, k=30.
• Theoretical guarantees hold for the simple Gaussian JL construction; extension to more complex randomized constructions is left open.
• Results of the main text and appendix differ in reported numeric distortion values (e.g., ~0.6 vs 1.6 for minimum random distortion).

Experimental setup

Datasets: synthetic unit-norm dataset (n=100, d=500)

Benchmarks: synthetic unit-norm dataset (n=100, d=500, k=30)

Metrics: maximum distortion variance over iterations expected maximum distortion

Baselines: Gaussian random projection (JL construction)

Builds on: Johnson-Lindenstrauss lemma perturbed gradient descent Adam

Closest papers by meaning

• Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.89)
• Optimal Randomized First-Order Methods for Least-Squares Problems (ICML 2020 · similarity 0.88)
• Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems (NeurIPS 2026 · similarity 0.86)
• Node Similarities under Random Projections: Limits and Pathological Cases (ICLR 2025 · similarity 0.86)
• Near-Optimality of Contrastive Divergence Algorithms (NeurIPS 2024 · similarity 0.85)
• Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.85)