Optimization Can Learn Johnson Lindenstrauss Embeddings

Christos Tzamos; Constantine Caramanis; Nikos Tsikouras

REVIEW 3 major objections 5 minor 27 references

Optimization Can Learn Johnson Lindenstrauss Embeddings

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Deterministic second-order optimization can produce Johnson-Lindenstrauss embeddings, matching the guarantees of random projection.

desk verdict 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. read the letter →

arxiv 2412.07242 v1 pith:UV4GB2WS submitted 2024-12-10 stat.ML cs.LG

Nikos Tsikouras , Constantine Caramanis , Christos Tzamos This is my paper · ORCID

classification stat.MLcs.LG MSC 68W2090C2662H25

keywords Johnson-Lindenstrausslemmadimensionalityreductionderandomizationsecond-orderoptimizationGaussiansolutionsamplersvarianceannealingnon-convexlandscapeHessianLipschitz

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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)$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

There 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.

A 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.

The 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[§4, Lemma 4 and Appendix A.4] 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.
[Appendix C vs. Theorems 2 and 3] 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.
[Appendix A.2, Lemma 2] 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.

minor comments (5)

[§4, Lemma 3 and Appendix C] 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.
[Equation (1) and Equation (2)] 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 5 and Appendix B] 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.
[NeurIPS Checklist, Limitations] 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.
[Notation in Lemma 4] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the JL guarantee is imported from the external distributional JL lemma and propagated to the mean by a substantive concentration claim; the flagged proof gaps are correctness issues, not circular reductions.

full rationale

The central derivation is not circular. Lemma 1 (distributional JL) is used only to certify the initialization f(0,1)<1/3; the objective g in Eq. 4 is a union-bound proxy plus a variance regularizer, and Theorems 2 and 3 analyze descent on that proxy with standard smoothness/Hessian-Lipschitz machinery. The sampler-to-mean transfer in Lemma 4 is a substantive concentration argument, not an assumption of its conclusion, so the JL guarantee is not hidden in the definition of the optimization target. I flag, but do not count as circular, three non-circular weaknesses: (i) the proof of Lemma 4 in Appendix A.4 appears algebraically flawed: the lower-bound step (1/2k)||Ax||^2 - (1/k)||Zx||^2 >= (1-epsilon)/2 - sigma^2(1+epsilon_0) is vacuous at sigma=0, and the displayed cross term 2/k^2 understates the triangle-inequality cross term, leaving the deterministic transfer unsupported as written; (ii) Appendix C bounds L and K only under sigma^2 >= sigma_0^2, while Theorems 2 and 3 need conclusions as sigma^2 tends to 0, so the polynomial iteration bound lacks a valid constant regime; (iii) the NeurIPS checklist states limitations are not discussed. These are proof-gap and scope issues, not circularity. The only self-citation (Yi et al. 2016, cited as related work on PCA) is not load-bearing; no fitted parameter is renamed as a prediction, and no equation is defined in terms of its own conclusion.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central derivation rests on the standard JL lemma, Gaussian tail bounds, and a smoothness assumption that is only proved on a restricted domain. The regularization weight 1/2 is a hand-chosen but non-essential constant.

free parameters (1)

Regularization weight 1/2 = 1/2
Chosen so that g(0,1) < 5/6; any weight in (1/3, 2/3) would preserve the argument, so this is a hand-selected design choice, not fitted to data.

assumptions (4)

standard math The standard distributional Johnson-Lindenstrauss lemma holds for Gaussian matrices.
Used to initialize the sampler at (0,1) and to control the residual Gaussian Z in Lemma 4.
ad hoc to paper The objective g is L-smooth and K-Hessian Lipschitz with finite L and K throughout the trajectory of Algorithm 1.
Needed for Lemmas 5 and 6; Appendix C only proves such bounds on a domain with a lower bound on variance, which is not stated in the theorems.
domain assumption Data points are unit norm; general data can be normalized.
WLOG normalization of input data, stated in Section 3.
standard math Gaussian tail bounds and the union bound control the extended bad event probability.
Used in the proof of Lemma 2 to bound Pr(A_gamma outside R2).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimization Can Learn Johnson Lindenstrauss Embeddings." pith.science (2026). https://pith.science/paper/UV4GB2WS

@misc{pith2026241207242,
  author       = {Pith},
  title        = {Pith review of: Optimization Can Learn Johnson Lindenstrauss Embeddings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UV4GB2WS}},
  note         = {Machine review of arXiv:2412.07242}
}

read the original abstract

Embeddings play a pivotal role across various disciplines, offering compact representations of complex data structures. Randomized methods like Johnson-Lindenstrauss (JL) provide state-of-the-art and essentially unimprovable theoretical guarantees for achieving such representations. These guarantees are worst-case and in particular, neither the analysis, nor the algorithm, takes into account any potential structural information of the data. The natural question is: must we randomize? Could we instead use an optimization-based approach, working directly with the data? A first answer is no: as we show, the distance-preserving objective of JL has a non-convex landscape over the space of projection matrices, with many bad stationary points. But this is not the final answer. We present a novel method motivated by diffusion models, that circumvents this fundamental challenge: rather than performing optimization directly over the space of projection matrices, we use optimization over the larger space of random solution samplers, gradually reducing the variance of the sampler. We show that by moving through this larger space, our objective converges to a deterministic (zero variance) solution, avoiding bad stationary points. This method can also be seen as an optimization-based derandomization approach and is an idea and method that we believe can be applied to many other problems.

Figures

Figures reproduced from arXiv: 2412.07242 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

[1]

− H(M2, σ2 2)∥2 = kX i=1 gvi,vi (M1, σ2

work page
[2]

bad event

Using the Taylor expansion: ∥A˜x∥2 2 − ∥A′ ˜x∥2 2 = 2(A˜x)T (A − A′)˜x + O(∥A′ − A∥2 F ) Since ∥A − A′∥2 F = ∥P − 2I∥2 F + ∥v∥2 2, let ∥A − A′∥2 F = γ2. We consider two cases based on the magnitude of ∥v∥2 2. Case 1: ∥v∥2 2 ≥ γ2/2 In this case, there exists at least one i such that v2 i ≥ γ2/(2k). We consider: 2(A˜x)T (A − A′)˜x = xT (P − 2I)x + xT v last...

work page 2013
[3]

We provide proof sketches in the main body and complete and correct proofs for all our results in the appendix

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...

work page
[4]

vi τ 2 − viv2 j τ 3 # Fk,δ k(1 − ε) τ +

To have a fair evaluation we draw 1000 such matrices and calculate the mean and the minimum distortion obtained. Our results show that we consistently learn a matrix with close to optimal distortion, that is∥M x∥2 2 ≈ 1, while the randomized construction achieves an average value of∥Zavgx∥2 2 ≈ 2 and minimum value ∥Zminx∥2 ≈ 1.6. C Proving Smoothness and ...

work page
[5]

Guidelines: • The answer NA means that paper does not include experiments requiring code

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] Justification: We have provided the code we ran for our simulations in the supplementary material. Guidelines: • The answe...

work page
[6]

− gvi,vi (M2, σ2 2) 2 + gσ2,σ2 (M1, σ2

work page
[7]

Our goal is to determine how much worse the distortion becomes when using M instead of sampling from the distribution A

This ensures there exists an overlap where both inequalities for A and Z hold simultaneously. Our goal is to 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 ∥M x∥2 = 1 k ∥M x + Zx − Zx∥2 ≤ 1 k ∥M x + Zx∥2 + 1 k ∥Zx∥2 = 1 k ∥Ax∥2 + 1 k ∥Zx∥2, which by squar...

work page 2013
[8]

− gσ2,σ2 (M2, σ2 2) 2 + X i̸=j 2 gvi,vj (M1, σ2

work page

Show all 27 references

[9]

− gvi,vj (M2, σ2 2) 2 + 2 kX i=1 gvi,σ2 (M1, σ2
[10]

Therefore, we get: ∥H(M1, σ2

− gvi,σ2 (M2, σ2 2) |2 ≤ kρ2 v1,v1 + ρ2 σ2,σ2 + 2(k × d − 2k − 1)ρ2 v1,v2 + 2kρ2 v1,σ2 (M1 − M2)2 + (σ2 1 − σ2 2)2 . Therefore, we get: ∥H(M1, σ2
[11]

− H(M2, σ2 2)∥ ≤ O k2 σ8 0 + O k2ε2 σ12 0 + O dk2ε σ8 0 + O k3ε2 σ10 0 ∥(M1, σ2
[12]

− (M2, σ2 2)∥ ≡ poly k, ε, d,1 σ0 ∥(M1, σ2
[13]

Finally, since we are summing over n data points, the Hessian Lipschitz constant, is poly(n, k, ε, d,1/σ0)

− (M2, σ2 2)∥. Finally, since we are summing over n data points, the Hessian Lipschitz constant, is poly(n, k, ε, d,1/σ0). 30 NeurIPS Paper Checklist
[14]

Guidelines: • The answer NA means that the abstract and introduction do not include the claims made in the paper

Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract summarizes the findings presented in the paper, while the in- troduction summarizes the motivations behin...
[15]

Limitations

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 whe...
[16]

Guidelines: • The answer NA means that the paper does not include experiments

Experimental Result Reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and da...
[18]

Guidelines: • The answer NA means that the paper does not include experiments

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 i...
[19]

Guidelines: 33 • The answer NA means that the paper does not include experiments

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 ...
[20]

Guidelines: • The answer NA means that the paper does not include experiments

Experiments Compute Resources Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [No] Justification: Given that this is a the...
[21]

Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics

Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The research conducted in the paper fully adheres to the NeurIPS Code of Ethics...
[22]

Guidelines: • The answer NA means that there is no societal impact of the work performed

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 a theoretical result, we do not foresee any societal impact. Guidelines: • The answer NA ...
[23]

Safeguards Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Since this is a...
[24]

• The authors should cite the original paper that produced the code package or dataset

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...
[25]

• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates

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 de...
[26]

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)? A...
[27]

36 • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research

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...
[650]

IEEE, 2017. N. Alon, Y . 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. I. Arriaga and S. Vempala. An algorithmic theory of learning: Ro...

2017 arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

− H(M2, σ2 2)∥2 = kX i=1 gvi,vi (M1, σ2

work page

[2] [2]

bad event

Using the Taylor expansion: ∥A˜x∥2 2 − ∥A′ ˜x∥2 2 = 2(A˜x)T (A − A′)˜x + O(∥A′ − A∥2 F ) Since ∥A − A′∥2 F = ∥P − 2I∥2 F + ∥v∥2 2, let ∥A − A′∥2 F = γ2. We consider two cases based on the magnitude of ∥v∥2 2. Case 1: ∥v∥2 2 ≥ γ2/2 In this case, there exists at least one i such that v2 i ≥ γ2/(2k). We consider: 2(A˜x)T (A − A′)˜x = xT (P − 2I)x + xT v last...

work page 2013

[3] [3]

We provide proof sketches in the main body and complete and correct proofs for all our results in the appendix

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...

work page

[4] [4]

vi τ 2 − viv2 j τ 3 # Fk,δ k(1 − ε) τ +

To have a fair evaluation we draw 1000 such matrices and calculate the mean and the minimum distortion obtained. Our results show that we consistently learn a matrix with close to optimal distortion, that is∥M x∥2 2 ≈ 1, while the randomized construction achieves an average value of∥Zavgx∥2 2 ≈ 2 and minimum value ∥Zminx∥2 ≈ 1.6. C Proving Smoothness and ...

work page

[5] [5]

Guidelines: • The answer NA means that paper does not include experiments requiring code

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] Justification: We have provided the code we ran for our simulations in the supplementary material. Guidelines: • The answe...

work page

[6] [6]

− gvi,vi (M2, σ2 2) 2 + gσ2,σ2 (M1, σ2

work page

[7] [7]

Our goal is to determine how much worse the distortion becomes when using M instead of sampling from the distribution A

This ensures there exists an overlap where both inequalities for A and Z hold simultaneously. Our goal is to 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 ∥M x∥2 = 1 k ∥M x + Zx − Zx∥2 ≤ 1 k ∥M x + Zx∥2 + 1 k ∥Zx∥2 = 1 k ∥Ax∥2 + 1 k ∥Zx∥2, which by squar...

work page 2013

[8] [8]

− gσ2,σ2 (M2, σ2 2) 2 + X i̸=j 2 gvi,vj (M1, σ2

work page