{"id":"8510ac6a-cab0-48dc-ade8-8fc10953aed5","arxiv_id":"2412.07242","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Optimizing a regularized failure-probability objective over Gaussian sampler parameters (mean and variance) yields a deterministic Johnson-Lindenstrauss embedding in polynomial time.","lead":"This paper shows that a deterministic matrix satisfying the Johnson-Lindenstrauss embedding guarantee can be found by optimizing an objective in the space of Gaussian samplers, rather than directly in the space of matrices. It also proves that direct optimization over matrices is doomed by bad local minima, and connects the fix to diffusion-style variance annealing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4, the bridge from a low-variance sampler to a deterministic JL matrix, is algebraically wrong: its lower bound is vacuous (factor 1/2) and its cross term is off by a factor 1/k. Without a repaired Lemma 4, Theorem 3 is unsupported.","rationale":"I read the paper in good faith. The strongest claim is Theorem 3: deterministic optimization of g (Eq. 4) returns a JL matrix in poly(n,k,d) steps. This requires (i) second-order stationarity forces sigma small (Lemma 3), (ii) small sigma means the mean is JL (Lemma 4), and (iii) L and K, the smoothness and Hessian-Lipschitz constants, are controlled on the region visited (Appendix C). The most load-bearing link is (ii): without it, even a perfectly optimized low-variance sampler gives no deterministic matrix. I found Lemma 4's proof incorrect in two independent places. The upper bound's cross term is off by a factor k; the lower bound's use of (1/2)||Ax||^2 yields a vacuous bound of about (1-epsilon)/2. Thus as written, Lemma 4 does not prove that M inherits JL. This is not an issue of disagreement with consensus; it is an internal algebraic inconsistency. It is likely repairable with the reverse triangle inequality, which is why I would not move from the reader's CONDITIONAL to REJECT. I also note the reader's chosen weakest assumption: Appendix C's L and K bounds require sigma^2 >= sigma_0^2, while Theorem 3 needs the algorithm's behavior as sigma^2 tends to 0. That is a real secondary gap: the fixed step sizes nu = 1/L and h = 3 sqrt(rho)/K are only valid where those constants are finite, and the constants blow up near sigma^2 = 0. The simulations (Section 5) use Adam on a Monte-Carlo proxy (Eq. 8), not Algorithm 1 on Eq. 4, so they do not directly validate the theoretical claim. Overall, the framework is plausible and the derandomization intuition in Lemma 2 is interesting; the issue is that a key lemma is not proven as stated.","tokens_in":30898,"tokens_out":9023,"duration_ms":88081,"concrete_test":"Re-derive Lemma 4 from the identity M = A - Z, using the reverse triangle inequality for the lower bound and the correct squared triangle inequality for the upper bound, under the two good events for A and Z. Then check whether the resulting distortion interval for M is (1 - epsilon', 1 + epsilon') with epsilon' = O(epsilon + sigma); if the 1/2 factor persists or the cross term is 2 sigma sqrt((1+epsilon)(1+epsilon_0)) rather than 2 sigma/k sqrt(...), the lemma is false as written and Theorem 3 needs a new argument. As a side verification, rerun Algorithm 1 with sigma_0-dependent L and K from Appendix C to see whether the descent lemmas remain valid on the actual visited region.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 inherits its deterministic-output step from Theorem 2, which in turn relies on Lemma 4 (Appendix A.4): once A ~ N(M, sigma^2) is epsilon-JL with probability 1/6, M itself should be JL with distortion increased by poly(sigma, 1/k). The proof of Lemma 4 does not establish this. From A = M + Z, the correct squared triangle bound is (1/k)||Mx||^2 <= (1/k)||Ax||^2 + (2/k)||Ax|| ||Zx|| + (1/k)||Zx||^2. The text instead has 2/k^2 in the cross term, understating it by a factor k. With ||Ax|| ~ sqrt(k) and ||Zx|| ~ sigma sqrt(k), the true additive excess is Theta(sigma), not Theta(sigma/k). More serious: the lower bound is (1/k)||Mx||^2 >= 1/(2k)||Ax||^2 - (1/k)||Zx||^2 >= (1-epsilon)/2 - sigma^2(1+epsilon_0). Even at sigma = 0 this gives only (1-epsilon)/2, so it cannot certify the lower side of a JL guarantee with O(epsilon) distortion. The natural repair is the reverse triangle inequality, ||Mx|| >= ||Ax|| - ||Zx||, yielding (sqrt(1-epsilon) - sigma sqrt(1+epsilon_0))^2, but that is not what is proved. A secondary gap remains: Appendix C bounds L and K only on sigma^2 >= sigma_0^2, while Theorem 3 needs the dynamics for arbitrarily small sigma^2; the stated polynomial iteration bound therefore also lacks a valid constant regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an optimization-based method to construct deterministic Johnson-Lindenstrauss (JL) embeddings. It defines an objective g(M,σ²) over the mean and variance of a Gaussian sampler, adds a variance-reducing regularizer, and claims that a deterministic second-order descent algorithm (Algorithm 1) reaches a second-order stationary point whose variance is small and whose mean matrix M satisfies the JL guarantee. The paper also presents a negative result for direct optimization over matrices (Theorem 1) and supports the theory with simulations on synthetic data.","tokens_in":31263,"tokens_out":12483,"duration_ms":115330,"significance":"If the main result were correct, it would constitute a novel derandomization of JL via continuous optimization, with the appealing conceptual step of optimizing in the space of random samplers and annealing the variance. The paper explicitly frames the method as an optimization-based derandomization with potential applicability beyond JL. However, the main theorem chain currently has several load-bearing gaps, so the significance is conditional on a substantial repair of the proofs.","major_comments":[{"comment":"The proof of Lemma 4 contains an algebraically incorrect inequality. Squaring the triangle inequality for normalized norms gives (1/k)||Mx||² ≤ (1/k)||Ax||² + (2/k)||Ax||·||Zx|| + (1/k)||Zx||², but the manuscript writes the cross term as 2/k², understating it by a factor of k. More decisively, the lower bound (1/k)||Mx||² ≥ (1/(2k))||Ax||² − (1/k)||Zx||², combined with the assumed JL-style bounds, yields at best (1/2)(1−ε) − σ²(1+ε₀), which is only (1−ε)/2 even when σ=0. This cannot certify the lower side of a JL guarantee with distortion O(ε). The reverse triangle inequality would give (√(1−ε) − σ√(1+ε₀))², but that is not what is proved, and it would require σ=O(ε). Consequently, the bridge from a good sampler to a deterministic mean matrix, used in Theorems 2 and 3, is not established.","section":"§4, Lemma 4 and Appendix A.4"},{"comment":"The smoothness and Hessian-Lipschitz constants are established only under an explicit lower bound σ² ≥ σ₀², with bounds of the form poly(n,k,ε,d,1/σ₀). Theorems 2 and 3, however, need conclusions as σ² tends to 0 (they require ρ < 1/poly(n,k,d) and then σ² < poly(n,k,d)·ρ^{O(1)}). The derivative expressions in Appendix C show terms that blow up as inverse powers of σ², so no finite global L and K exist on the entire trajectory. The paper does not explain how the second-order descent analysis (Lemmas 5–6 and the O(1/ρ^{1.5}) iteration bound) applies when the trajectory approaches the singular boundary σ²=0, nor does it provide uniform bounds as σ₀→0. The polynomial-step claim of Theorem 3 therefore lacks a proof in the regime where it is stated.","section":"Appendix C vs. Theorems 2 and 3"},{"comment":"The proof of Lemma 2 asserts the existence of a realization αγ inside the truncation set R₂ with conditional failure probability at most δ + γ²/3, but this does not follow from the displayed expectation identity. The identity says E_{Aγ}[X + 1_{Aγ∉R₂}] = δ + γ²/3, where X is the sum of conditional failure probabilities; the minimum of X over R₂ is not necessarily bounded by this expectation. A valid argument would need to condition on Aγ ∈ R₂ and use a bound on X outside R₂ (e.g., via X ≤ n or a separate concentration estimate). As written, the inequality and the resulting γ²/6 decrease are unjustified. Since Lemma 2 is used to prove Lemma 3, this gap propagates into the stationarity analysis.","section":"Appendix A.2, Lemma 2"}],"minor_comments":[{"comment":"The statement and proof sketch of Lemma 3 do not specify the domain on which the Hessian-Lipschitz constant K is finite; the proof should explicitly reference the σ₀² restriction of Appendix C and discuss how the conclusion handles the limit σ²→0.","section":"§4, Lemma 3 and Appendix C"},{"comment":"The notation h(A) is introduced in Equation (1) but used again in Equation (2) without a cross-reference; please restate or point back to the definition.","section":"Equation (1) and Equation (2)"},{"comment":"The simulation text reports inconsistent numbers: one paragraph states the random construction achieves average and minimum distortions of approximately 1 and 0.6, while Appendix B states ||Z_{avg}x|| ≈ 2 and ||Z_{min}x|| ≈ 1.6; please reconcile the values and clarify the units.","section":"Section 5 and Appendix B"},{"comment":"The checklist answers 'No' to the Limitations question, but the paper itself contains a significant domain restriction in Appendix C (σ² ≥ σ₀²); a limitations section discussing the absence of global smoothness and the singular behavior at σ²=0 would be appropriate.","section":"NeurIPS Checklist, Limitations"},{"comment":"The proof of Lemma 4 sometimes writes 1/k ||Mx|| without the square while other lines use 1/k ||Mx||²; please standardize the notation to avoid confusion.","section":"Notation in Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The paper presents an appealing idea and a plausible conceptual framework, but the proof of the main theorem contains a concrete algebraic error in Lemma 4 (the cross term and, more seriously, the vacuous lower bound) and a domain mismatch between the smoothness analysis of Appendix C and the σ²→0 regime required by Theorems 2 and 3. The third major comment on Lemma 2 indicates a further gap in the derandomization step. I recommend major_revision rather than reject because the underlying approach may be repairable with a strengthened variance condition and a more careful domain decomposition, but the current manuscript does not provide a valid proof of its advertised claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The central theorem is currently unsupported, but the conceptual framework is genuinely new and worth engaging with. The idea of optimizing over Gaussian sampler parameters and annealing the variance is a fresh angle on derandomizing JL, and the negative landscape result for direct matrix optimization (Theorem 1) is a nice concrete observation, even if its reachability claim is asserted rather than proved.\n\nThe soft spots are load-bearing. Lemma 4, the bridge from a low-variance sampler to a deterministic matrix, has two serious problems. First, the norm inequality as written is dimensionally inconsistent: from (1/k)||Mx|| ≤ (1/k)||Ax|| + (1/k)||Zx||, squaring gives a cross term of 2/k, not 2/k^2. The paper understates that term by a factor of k. Second, the lower bound via Cauchy-Schwarz gives (1/2)(1-ε) - σ^2(1+ε0), which even at σ=0 only certifies distortion 1/2, not (1-ε). The natural repair is to work with norms and use the reverse triangle inequality, yielding (sqrt(1-ε) - σ sqrt(1+ε0))^2, but that is not what is proved. Without a repaired Lemma 4, Theorems 2 and 3 do not go through.\n\nThere is also a gap in the smoothness analysis. Appendix C bounds the smoothness and Hessian-Lipschitz constants on a domain with σ^2 ≥ σ0^2, and the constants depend polynomially on 1/σ0. The theorems need the dynamics to reach arbitrarily small σ^2, so the claimed polynomial iteration bound in Theorem 3 has no valid constant regime. This is a gap, though potentially fixable with a more careful treatment near σ=0.\n\nA minor point: the simulations use Adam on an expected-distortion objective, not the deterministic Hessian descent of Algorithm 1, so they do not directly validate the theory. That is fine as a proof-of-concept, but it should not be presented as confirming the specific algorithm.\n\nThe paper is well-written and positions itself correctly against prior PRG and conditional-expectation derandomizations. The flaws are specific and possibly repairable. I would send this to a serious referee rather than desk-reject, because the idea is novel and the technical issues are identifiable. The authors should be asked to fix Lemma 4, restate the smoothness assumptions, and either prove or soften the reachability claim in Theorem 1.","headline":"Novel sampler-space optimization idea, but the main theorem rests on an algebraically wrong Lemma 4 and on Lipschitz bounds that only hold away from zero variance.","tokens_in":31777,"tokens_out":3262,"would_cite":false,"duration_ms":30646,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","90C26","62H25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deterministic second-order optimization can produce Johnson-Lindenstrauss embeddings, matching the guarantees of random projection.","keywords":["Johnson-Lindenstrauss lemma","dimensionality reduction","derandomization","second-order optimization","Gaussian solution samplers","variance annealing","non-convex landscape","Hessian Lipschitz"],"falsifier":"Take a dataset with two unit vectors at a distance very close to the distortion boundary, run the Hessian-descent algorithm to a tolerance $\\rho$, record the actual variance reached, and check whether the mean matrix satisfies the claimed $O(\\epsilon)$ distortion. If the algorithm exits at a variance bounded away from zero on some instance, or if the empirical Hessian-Lipschitz constant along the trajectory grows without bound as $\\rho \\to 0$, the total steps would need to grow beyond $\\mathrm{poly}(n,k,d)$.","tokens_in":30648,"feed_emoji":"🎯","tokens_out":5040,"duration_ms":53088,"temperature":0.7,"pith_summary":"This paper asks whether a deterministic optimization algorithm can produce a matrix that satisfies the Johnson-Lindenstrauss (JL) guarantee, sidestepping random projection entirely. It first shows that directly minimizing the maximum-distortion objective over projection matrices is doomed: that landscape contains many strict bad local minima reachable from the origin. The paper's solution is to optimize over a larger space of Gaussian samplers, parameterized by a mean matrix $M$ and variance $\\sigma^2$, starting from the known-good sampler $\\mathcal{N}(0,1)$ and annealing the variance down to zero while a regularized objective decreases. Any second-order stationary point reachable from the origin has variance tending to zero as the stationarity tolerance does, and the mean matrix then satisfies the JL guarantee with distortion $O(\\epsilon)$ for $\\epsilon = \\Omega(\\sqrt{\\log n/k})$. Running a deterministic Hessian-descent algorithm for $\\mathrm{poly}(n,k,d)$ steps returns such a matrix, giving an optimization-based derandomization of the Gaussian JL construction.","feed_headline":"Deterministic descent constructs JL embeddings in polynomial time","feed_subtitle":"By annealing the variance of a Gaussian sampler, descent reaches a matrix that preserves distances as well as random projections.","key_machinery":"The carrying object is the Gaussian solution sampler $A\\sim\\mathcal{N}(M,\\sigma^2)$ with a regularized failure objective $g(M,\\sigma^2)=\\sum_j \\Pr\\left[\\frac{1}{k}\\|Ax_j\\|_2^2 \\notin (1-\\epsilon,1+\\epsilon)\\right]+\\frac{\\sigma^2}{2}$. The key mechanism is the Gaussian decomposition $A=A_\\gamma+A'$ used in Lemma 2: for any positive variance one can find a nearby mean with variance reduced by $\\gamma^2$ that lowers $g$ by at least $\\gamma^2/6$, so no reachable point with nonzero variance can be a local minimum. That derandomization step, together with the smoothness and Hessian-Lipschitz bounds on $g$, lets a deterministic gradient-plus-negative-curvature algorithm drive $\\sigma^2$ to zero while preserving the JL guarantee of the mean.","core_discovery":"The central claim is that random projection is not necessary for the JL guarantee: a deterministic, data-dependent optimization over samplers can obtain it. The proof proceeds in four steps: direct matrix optimization is hopeless; the sampler-space objective has no bad stationary points with nonzero variance; approximate second-order stationary points correspond to nearly deterministic samplers whose mean is a JL matrix; and a standard second-order descent algorithm finds such a point in polynomial time. The empirical section shows the learned matrix attaining near-zero distortion on a synthetic dataset, while random Gaussian matrices achieve only an average distortion of about 0.6. The paper therefore presents a derandomized JL construction that is also data-adaptive.","pith_inferences":["The variance-annealing scheme is essentially reverse diffusion on a Gaussian sampler; the same objective-with-regularizer could be applied to sparse or Hadamard JL constructions, where the sampler distribution is not isotropic Gaussian and the derandomization step would differ.","The guarantee is worst-case polynomial but does not state an explicit constant in the $O(\\epsilon)$ distortion; sharpening that constant might matter for practical deployment.","A natural testable extension is replacing the $\\sigma^2/2$ penalty with $\\sigma^p$ for other values of $p$, which may give different variance-annealing trajectories and possibly faster empirical convergence; this paper's analysis does not cover that family."],"forward_implications":["For any $n$ unit vectors and target dimension $k$, a deterministic algorithm now matches the Gaussian JL guarantee with distortion $O(\\epsilon)$ in $\\mathrm{poly}(n,k,d)$ steps, so randomness is not required for the JL property.","Direct first- or second-order minimization of the maximum-distortion objective over projection matrices cannot work in general, because that landscape has many strict bad local minima.","The resulting embedding can exploit data structure: the method converges to a deterministic matrix whose distortion on the given data is much smaller than the worst-case random construction.","The sampler-space optimization view gives a purely optimization-based derandomization of JL, distinct from pseudorandom-generator or conditional-expectation approaches."],"supporting_citations":[{"why":"Establishes the JL lemma: random linear maps preserve distances with high probability, the target the paper matches deterministically.","marker":"[Johnson, 1984]"},{"why":"Provides the Gaussian construction and proof that $\\mathcal{N}(0,1)$ matrices satisfy JL, used as the initialization sampler and as the baseline in simulations.","marker":"[Indyk and Motwani, 1998]"},{"why":"Tight lower bound showing the JL distortion-dimension trade-off is optimal, setting the target the algorithm attains.","marker":"[Larsen and Nelson, 2017]"},{"why":"Another optimality result for JL-type dimension reduction, reinforcing the worst-case target the paper's guarantee is compared against.","marker":"[Alon and Klartag, 2017]"},{"why":"Standard Taylor-type descent analysis used to prove sufficient descent for gradient and negative-curvature steps.","marker":"[Nesterov, 2013]"},{"why":"Method to escape saddle points efficiently; the paper notes a first-order perturbed gradient descent can replace the deterministic second-order algorithm.","marker":"[Jin et al., 2017]"},{"why":"Adam optimizer used in the empirical section to minimize the Monte Carlo proxy of the objective.","marker":"[Kingma and Ba, 2014]"}],"fun_headline_variants":["No need for randomness: optimization learns JL embeddings","Optimization over samplers anneals randomness for JL","Deterministic JL via annealed Gaussian samplers","Polynomial-time derandomized JL from variance annealing","Data-adaptive JL embeddings without random projection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the objective function's gradient and Hessian are Lipschitz on the entire region the algorithm visits, but the appendix establishes those bounds only when the variance stays above a small floor $\\sigma_0^2$; the theorems need conclusions as $\\sigma^2 \\to 0$, where the objective's derivatives become singular near the norm-distortion boundaries. If those regularity bounds fail in the limit, the polynomial-time guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["No need for randomness: optimization learns JL embeddings","Optimization over samplers anneals randomness for JL","Deterministic JL via annealed Gaussian samplers","Polynomial-time derandomized JL from variance annealing","Data-adaptive JL embeddings without random projection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000782,"raw_usage":{"total_tokens":3430,"prompt_tokens":898,"completion_tokens":2532,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":514,"completion_tokens_details":{"reasoning_tokens":2457}},"tokens_in":514,"tokens_out":2532,"duration_ms":19846,"temperature":1.0,"reasoning_tokens":2457,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:56:53.843838+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a dataset with two unit vectors at a distance very close to the distortion boundary, run the Hessian-descent algorithm to a tolerance $\\rho$, record the actual variance reached, and check whether the mean matrix satisfies the claimed $O(\\epsilon)$ distortion. If the algorithm exits at a variance bounded away from zero on some instance, or if the empirical Hessian-Lipschitz constant along the trajectory grows without bound as $\\rho \\to 0$, the total steps would need to grow beyond $\\mathrm{poly}(n,k,d)$.","supporting_citations":[],"review_version":1}