PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Independence Testing for Latent Position Random Graphs

Xiaoyi Wen, Zoltan Szabo

arXiv:2610.34544v1stat.MLcs.LGcs.SI

TL;DR

Joint independence testing for multiple latent position random graphs is difficult because the latent Gram matrices are not directly observed and only a single graph realization is available. The paper defines GHSIC for M≥2 LPRGs and estimates it through adjacency-matrix spectral methods. It demonstrates the approach on synthetic and brain-network examples, while leaving open whether its convergence rate can be improved.

  • Problem

    Joint independence testing is challenging because each graph is observed through a single random realization and the latent Gram matrices required by classical HSIC are unavailable.

    Source: §1 · p. 4, §2 · p. 10

  • Method

    The paper defines GHSIC for M≥2 LPRGs and estimates it from adjacency matrices using spectral decomposition.

    Source: §5 · p. 26

  • Results

    The approach is demonstrated on synthetic examples and brain functional-connectivity subnetworks, with the latter yielding conclusions compatible with recent neuroscience results.

    Source: §5 · p. 26

  • Takeaways & Limitations

    The work extends graph-independence measurement to joint testing of M≥2 LPRGs.

    Source: §5 · p. 26

    Whether the obtained convergence rate can be improved remains open.

    Source: §5 · p. 26

Abstract

from arXiv · show

Kernel techniques are among the most powerful methods in data science and statistics. One of the key properties of kernels contributing to their numerous successful applications is that the associated reproducing kernel Hilbert space is expressive enough to encode probability distributions without loss of information or to capture the joint independence of $M\ge 2$ random variables, under mild conditions. Computationally, these measures (i) rely on the so-called Gram matrix which contains the pairwise similarity of sample points, and (ii) converge at a rate $O \left(n^{-\frac{1}{2}}\right)$, where $n$ denotes the sample size. We focus on measuring the independence of latent position random graphs (LPRGs), a model widely-applied for instance in neuroscience, sociology, and epidemiology. In LPRGs a latent representation is associated to each node. The similarity of these representations (meant via a kernel) determines whether two nodes are connected, making the Gram matrices only implicitly observable and the estimation challenging. Despite the fundamental importance of quantifying the independence of $M$ LPRGs, very little is known about the solution of this problem; existing techniques are restricted to $M=2$ components and only guarantee consistency without rates. In this work, (i) we define an independence measure called graph Hilbert-Schmidt independence criterion (GHSIC) for $M\ge 2$ LPRGs, (ii) we prove that it can be estimated at a rate $\tilde{O}\left(n^{-\frac{1}{3}}\right)$ relying on spectral decomposition of adjacency matrices, (iii) without the need to choose kernels and their hyperparameters. Numerical experiments demonstrate the effectiveness of the proposed GHSIC estimator both on synthetic examples and in the analysis of brain functional connectivity subnetworks in natural language perception.

1 Introduction

The introduction frames joint independence testing for multiple LPRGs as an open problem because standard graph-valued testing assumes repeated graph tuples, unlike the single graph tuple and implicit Gram matrices in this setting. It introduces an HSIC-based measure and spectral estimator, derives embedding-dimension guidance, and demonstrates the approach on synthetic and brain-network examples.

1 Introduction

  • Characteristic and universal kernels can make RKHS representations expressive enough to encode distributions or capture independence under stated conditions.For joint independence with M≥2 components, the cited background identifies c0-universality as sufficient.Source: §1 · pp. 2–3
  • Joint independence testing for M≥2 random graphs remains open; existing graph-dependence measures focus on layer similarity or specific associations rather than mutual independence.Prior work introduced a graph HSIC measure for M=2 LPRGs but did not address M≥2 or estimator rates.Source: §1 · pp. 4, 6
  • Standard graph-valued testing uses repeated graph tuples, whereas this setting provides one graph tuple on common nodes and one realization of each graph's random edges.Consequently, the latent-position Gram matrices cannot be formed from repeated graph-level observations.Source: §1 · p. 4
  • The paper defines an HSIC-based dependence measure for M≥2 LPRGs and estimates it using adjacency-matrix spectral decomposition.The introduction states that the estimator has proved error bounds.Source: §1 · p. 6
  • The authors derive an optimal embedding dimension for polynomial and exponential spectral decay of the associated integral operators.These are the two spectral-decay regimes specified in the contribution statement.Source: §1 · p. 6
  • The approach is demonstrated on simulated examples and functional brain networks, where the analysis yields conclusions compatible with recent neuroscience results.The introduction identifies multiplex graphs as the application setting.Source: §1 · p. 6

2 Problem Formulation

The section formulates joint independence testing for multiple LPRGs when latent positions and their Gram matrices are not observed directly. It specifies a latent-position graph model and motivates estimating the HSIC-based target from adjacency matrices.

2 Problem Formulation

  • The Gram matrices needed by the classical HSIC estimator are unobservable in LPRGs, so the goal is to estimate the target from indirect information in the adjacency matrices.The latent kernels determine connection probabilities, but the graphs provide the observable data.Source: §2 · pp. 10–11
  • The target is joint independence across M LPRGs defined on a common set of n nodes, with latent positions and kernels determining connection probabilities.The formulation assumes a joint latent random variable and n i.i.d. latent-position samples.Source: §2 · p. 10
  • Conditional on the latent positions, upper-triangular adjacency entries are independent Bernoulli variables; the adjacency matrices are symmetric and have zero diagonals.This specifies how the random graph realizations arise from the latent-position model.Source: §2 · p. 10
  • The squared GHSIC definition in the M=2 case reduces to the definition given by Wen et al. (2026).The section positions the measure as a multi-graph extension of that earlier two-graph definition.Source: §2 · p. 11

3 Proposed Estimator

The estimator replaces unavailable kernel matrices with estimates derived from adjacency-matrix spectral decompositions and does not require prior kernel or latent-position knowledge. The section establishes an error-bound analysis and discusses embedding-dimension choices under polynomial and exponential spectral decay.

3 Proposed Estimator

  • The proposed estimator replaces kernel matrices with estimates computed from each graph’s adjacency matrix using truncated spectral decompositions.The spectral decomposition is of the positive semidefinite matrix (A_m)^T A_m.Source: §3 · pp. 11–12
  • The estimator is nonnegative and therefore well-defined after taking the square root of its equivalent expression.The passages identify non-negativity and the resulting square-root form.Source: §3 · p. 12
  • The estimator requires no prior knowledge of the kernel or latent positions, avoiding the usual kernel-choice bottleneck.Source: §3 · p. 12

3.1 Main Result

  • The main result bounds estimator error, with embedding-dimension choices analyzed for polynomial and exponential spectral decay.The section considers embedding dimensions that may depend on node size and discusses both spectral-decay regimes.Source: §3.1 · pp. 14, 16

4 Numerical Experiments

The experiments assess GHSIC estimator accuracy and runtime, independence-test power, and functional connectivity in brain subnetworks. Results cover synthetic settings and fMRI data, with both spectral-decay patterns considered.

4 Numerical Experiments

  • Synthetic experiments used Gaussian latent positions and kernels under exponential spectral decay, while the fMRI analysis considered subnetworks with polynomial spectral decay.The fMRI analysis used d0-truncated SVD to estimate the polynomial decay rate.Source: §4 · p. 18, §4.3 · p. 26

4.1 Experiment-1

  • With fixed q and d0, d0-truncated SVD achieved O(n^2) runtime, matching the oracle estimator’s complexity; d0 = 10 was practical in this example.For calculating the estimated kernel matrix, d0 = 10 and 20 were significantly faster than d0 = 2.Source: §4.1 · pp. 20–21
  • All estimators approached oracle HSIC_k^2(P_n) accuracy as n grew, but larger M raised estimation error and slowed convergence; error differed little across d0 choices.The d0-truncated SVD strategy was effective for estimating the spectral decay rate.Source: §4.1 · p. 20, Figure 3 · p. 21, Figure 4 · p. 22
  • Increasing ρ raised estimation error; larger γ raised error at small n through a larger embedding dimension, while adding c could reduce error.The experiments varied ρ, γ, and c while retaining challenging settings from one experiment to the next.Source: §4.1 · p. 21, Figure 5 · p. 23

4.2 Experiment-2

  • The d0-truncated SVD significantly sped up permutation-test quantile calculation, while test statistics based on estimated decay rates were nearly identical across two strategies.The compared testing settings included ρ = 0.3 and ρ = 0.4; smaller ρ made testing more challenging.Source: §4.2 · p. 23

4.3 Experiment-3

  • Across subnetworks, accepting H1 was more feasible with larger node counts, while the authors identify SomMot and Vis as most active during natural-language perception.The smallest subnetwork, Limbic, had the lowest acceptance of H1; the authors note exceptions to the node-count trend.Source: §4.3 · p. 26

5 Conclusions

The paper develops joint independence testing for M ≥ 2 latent position random graphs (LPRGs) and reports applications to synthetic data and brain functional connectivity subnetworks. It also identifies open questions about the estimator’s rate and the scope of the framework.

5 Conclusions

  • The proposed independence measure targets joint testing for M ≥ 2 LPRGs, with an estimator based on adjacency spectral embeddings and error bounds using derived optimal embedding dimensions.The embedding dimensions are derived under polynomial or exponential decay of the corresponding integral-operator spectrum.Source: §5 · p. 26
  • The approach is demonstrated on synthetic examples and brain functional connectivity subnetworks, with the latter yielding conclusions compatible with recent neuroscience results.The conclusion does not specify individual numerical outcomes.Source: §5 · p. 26
  • Open questions include whether the obtained rate reflects the problem’s implicit Gram matrices or the current analysis, and whether faster rates or minimax lower bounds are possible.The conclusion also asks whether the framework and analysis extend to other random graph classes.Source: §5 · pp. 26, 28

Supplement

The supplement organizes external lemmas, the paper’s own results and proofs, and the permutation approach used in the independence-testing experiments. It also provides supporting notation and visual summaries.

Supplement

  • The supplement contains external lemmas, the paper’s own results and proofs, a brief account of the experiment’s permutation approach, and a derivation of optimal embedding dimensions.These materials are grouped into Sections A–D.Source: Supplement · p. 28
  • Supplemental notation includes permutation matrices, principal angles between column spaces, and notation for common matrix and probability concepts.The supplement defines principal angles using singular values of UᵀV.Source: Supplement · pp. 28–29
  • Figure 11 maps dependencies among external results, the paper’s own results, and assumptions; Table 2 summarizes the external and own results.Arrows indicate when a result is used in a proof or an assumption is first imposed.Source: Supplement · pp. 28–29, Table 2 · p. 30

Appendix A. External Results

Appendix A collects external results used in the paper’s proofs. These include matrix perturbation and concentration tools, kernel-spectrum results, and matrix characterizations.

Appendix A. External Results

  • The sin (Θ) theorem bounds the angle between eigenspaces of two symmetric matrices using an eigengap, while a corollary and variant support its use in the proofs.The appendix also invokes Weyl’s perturbation theorem in deriving the variant.Source: Appendix A · pp. 31–32
  • Adjacency-matrix concentration provides a high-probability approximation to an LPRG’s hidden Gram matrix.The appendix presents this as a lemma based on Oliveira (2009).Source: Appendix A · p. 32
  • Other concentration results cover bounded, zero-mean random symmetric matrices, Gram-matrix eigenvalues, Hilbert-space averages, and empirical covariance operators.The appendix also states McDiarmid’s inequality for functions with bounded differences.Source: Appendix A · pp. 33–35
  • The appendix gives effective-dimension orders under polynomial or exponential spectral decay and characterizes spectra of Gaussian-kernel operators and certain positive matrices.The matrix results cover Green’s matrices, oscillation matrices, and positivity and simplicity of oscillation-matrix eigenvalues.Source: Appendix A · pp. 35–36

Appendix B. Own Results

Appendix B.1 presents the paper’s own auxiliary results and discusses how they are used in the proofs in Section B.2.

Appendix B. Own Results

  • Section B.1 collects the paper’s auxiliary results and their discussion for use in the proofs in Section B.2.This passage states the section’s role but does not identify individual results.Source: Appendix B · p. 36

B.1 Lemmas to the Proof of Theorem 2

This section develops auxiliary results for the proof of Theorem 2, establishing high-probability bounds for truncation errors and adjacency-based spectral-feature approximations in latent position random graphs. It combines these bounds with concentration, matrix and norm inequalities, and tensor-product Hilbert-space results to control the theorem’s error terms.

B.1 Lemmas to the Proof of Theorem 2

  • Lemmas 20–25 supply further proof components, including the multiple-component extension, tensor-product norm bounds, truncated-feature isometry, and Lipschitz-constant bounds.The discussion of Theorem 2 relies on Lemma 22; Lemma 25 supports the proof of Lemma 19.Source: §B.1 · p. 37
  • Lemma 17 bounds the error of the d_m-truncated approximation to a single kernel’s empirical mean embedding under stated kernel, support, and assumption conditions.The subsequent proof extends this result to the tensor-product kernel in Lemma 18.Source: §B.1 · pp. 39, 42
  • Lemma 18 extends the truncation-error bound from individual kernels to the joint empirical mean embedding, with probability at least 1−Mη when t_km(n,η)≤∥C_km∥ for every component.The lemma assumes Assumptions 3–4 and continuous kernels on compact spaces.Source: §B.1 · pp. 42, 45
  • Lemma 19 establishes a high-probability Frobenius-norm approximation of the spectral features of K_m using the adjacency matrix, under Assumptions 1–4.The estimated features are computable from observations.Source: §B.1 · p. 45
  • The Lemma 19 bound controls the d_m-truncated approximation error, enabling later lemmas to use concentration between |A_m| and K_m to bound the target quantity.The bound is useful because its right-hand side can be bounded using that concentration.Source: §B.1 · p. 47
  • Figure 13 organizes the J_m events used in the probabilistic bound, showing how events imply or combine by union bounds and tracking large-n constraints.The proof summarizes constraints arising from assumptions and earlier lemmas alongside the event implications.Source: §B.1 · pp. 47–48, Figure 13 · p. 48
  • The proof uses an SVD-based decomposition to bound R_1 and R_2, then controls the resulting A_1, A_2, and A_3 terms.It further bounds D_1 through D_0 and treats D_2 and D_3 separately.Source: §B.1 · pp. 53, 57
  • The proof bounds D1, D2, and D3 using matrix-norm inequalities and positive-semidefinite ordering, then combines their bounds with a union bound.The argument also invokes spectral perturbation results and the assumed eigenvalue bounds.Source: §B.1 · pp. 61–64
  • The proof establishes a high-probability lower bound on the smallest eigenvalue of |Am|, enabling control of expressions that divide by it.It uses positive semidefiniteness, eigenvalue bounds, Weyl’s perturbation theorem, and a split into events E ∩ F and E ∩ ¯F.Source: §B.1 · pp. 66, 67, 70
  • The proof controls E2 by decomposing it into terms including R4, F1, and F2, bounding them with norm inequalities and combining the bounds.It uses a sufficient dominance condition from Assumption 2(ii), a rank bound, and union bounds.Source: §B.1 · pp. 72, 75, 76
  • The extension treats both adjacency-matrix entries and latent positions as random, a setting described as key to understanding the proposed GHSICk estimator’s performance from random samples.Source: §B.1 · p. 82
  • Lemma 20 continues Lemma 19 by bounding the approximation error for Gram-matrix spectral features obtained from adjacency matrices, with probability at least 1−η under its assumptions.The lemma considers M LPRGs and their latent-position samples.Source: §B.1 · pp. 82–83
  • Lemma 21 establishes a high-probability error bound for approximating joint spectral features from adjacency matrices.It extends an error bound for truncated matrix approximations to their feature maps.Source: §B.1 · pp. 90, 92
  • Lemma 22 proves that the function f in (202) is strictly increasing.The proof establishes positivity of its derivative over the stated domain.Source: §B.1 · pp. 94–95
  • Lemma 23 gives tensor-product Hilbert-space properties, including a norm bound for differences of tensor products.The proof obtains the bound by induction, using bounds on the component-vector norms.Source: §B.1 · pp. 95–96
  • Lemma 24 establishes an isometric property for the truncated feature maps and their tensor-product representation.The proof shows the associated map is an isometric isomorphism onto the corresponding tensor space.Source: §B.1 · pp. 97–99
  • Lemma 25 gives upper and lower bounds for the Lipschitz constant in Lemma 7 under stated assumptions.The supplied passages specify conditions for the bounds but do not include their values.Source: §B.1 · pp. 100–101
  • With fixed latent positions, inequality (150) holds with Qm-probability at least 1 − η for η ∈ (0, 2) and n ≥ 8η.The proof then extends the bound to the joint distribution of latent positions and adjacency-matrix entries under Assumption 1(ii), for η ∈ (0, 1) and a stated sample-size threshold.Source: §B.1 · pp. 102–103
  • The proof derives the remaining norm bound using the spectral-to-Frobenius norm inequality and ∥Km∥ ≤ n, then applies monotonicity of the logarithm.The spectral-to-Frobenius inequality is attributed to Golub and Van Loan (2013).Source: §B.1 · p. 103

B.2 Proofs

Lemma 26 establishes measurability for two groups of events and combines probability bounds for them. The section also outlines verification of assumptions for the Laplacian kernel and uniform distribution.

B.2 Proofs

  • The section roadmap verifies kernel universality and assumptions 1–7 for the Laplacian kernel and uniform distribution.Assumptions 5–7 are treated in Lemma 28; assumptions 1–4 in Lemma 30, using Lemma 29.Source: §B.2 · p. 103
  • Lemma 26 states that A, B, and C are measurable in both event groups.The proof establishes measurability using inverse images of Borel sets and intersections of measurable sets.Source: §B.2 · pp. 104–105
  • If P_X(B) ≥ 1 − δ1 and P(C|X = x) ≥ 1 − δ2 for all x, then P_XY(A) ≥ 1 − (δ1 + δ2).The proof uses C ⊆ A and probability monotonicity.Source: §B.2 · pp. 104–105

B.2.1 Proof of Lemma 1

The proof uses inner-product properties in deriving its expressions and separately treats terms A2 and A3.

B.2.1 Proof of Lemma 1

  • The proof derives an expression using linearity and the tensor-product inner-product property.A further step uses the stated property of ˆK_m.Source: §B.2.1 · p. 106
  • The proof treats term A2 separately.The supplied passage identifies A2 but gives no further detail about its derivation.Source: §B.2.1 · p. 106
  • The proof also treats term A3 separately.The supplied passage identifies A3 but gives no further detail about its derivation.Source: §B.2.1 · p. 106

B.2.2 Proof of Theorem 2

The proof bounds the error between GHSIC_k(P) and its estimator by controlling separate terms. The argument invokes concentration results under stated kernel and model assumptions.

B.2.2 Proof of Theorem 2

  • The proof bounds the error between GHSIC_k(P) and its estimator by controlling terms A1 and A2.It invokes the definitions of GHSIC_k(P) and its estimator and applies triangle inequalities in the decomposition.Source: §B.2.2 · p. 107
  • The C1 and C2 bounds invoke Lemmas 21, 23, and 9 under assumptions including bounded kernels and compact domains.The cited proof steps also require Assumptions 3–4 and, for the kernel bounds, full support of P_m.Source: §B.2.2 · pp. 109, 111
  • The final bound is combined under Assumptions 1–4 and additional kernel and term-specific conditions.These include kernel continuity on compact metric spaces, full support, and the stated t_km condition.Source: §B.2.2 · p. 112

B.2.3 Validating universality of the Laplacian kernel

The proof establishes universality of the Laplacian kernel on [0, 1] by restricting its known universality on R^d.

B.2.3 Validating universality of the Laplacian kernel

  • The even Laplacian kernel on R^d is cc-universal, as established by cited prior work.The passage cites Micchelli et al. (2006) and Sriperumbudur et al. (2011).Source: §B.2.3 · p. 113
  • cc-universality is equivalent to c-universality on every compact subset.The passage attributes this equivalence to Carmeli et al. (2010).Source: §B.2.3 · p. 113
  • Because X_m = [0, 1] is compact, the restricted Laplacian kernel is c-universal on X_m.The kernel is defined as k_m(x, y) := e^−|x−y|.Source: §B.2.3 · pp. 112–113

B.2.4 Validation of Assumptions 5-7 for the Laplacian kernel and the uniform distribution

For the uniform distribution on [0,1] and the Laplacian kernel, the proof establishes polynomial eigenvalue decay and verifies Assumptions 5–7.

B.2.4 Validation of Assumptions 5-7 for the Laplacian kernel and the uniform distribution

  • The sequence c_m(i) converges to a limit strictly greater than c_m^l, verifying Assumption 6.The proof identifies the limit as greater than the lower bound c_m^l.Source: §B.2.4 · pp. 113, 116
  • The proof establishes that the consecutive differences of c_m(i) satisfy the bound required by Assumption 7 for some K_m < α_m c_m^l.The proof concludes that Assumption 7 holds.Source: §B.2.4 · pp. 113, 116, 118
  • The Laplacian-kernel eigenvalues have polynomial decay with exponent α_m = 2, establishing the decay requirement in Assumption 5.The proof considers X_m distributed uniformly on [0,1] with k_m(x,y) = e^−|x−y|.Source: §B.2.4 · p. 113

B.2.5 Validation of Assumption 1-4 for the Laplacian kernel and the uniform distribution

This section verifies Assumptions 1–4 for the Laplacian kernel under the uniform distribution on [0,1], using triangular-distribution moment calculations and spectral properties. It establishes Gram-matrix invertibility for distinct samples and positive, simple eigenvalues through oscillation-matrix and permutation arguments.

B.2.5 Validation of Assumption 1-4 for the Laplacian kernel and the uniform distribution

  • The proof checks Assumptions 1–4 for X_m ∼ U[0,1] with k_m(x,y) = e^−|x−y|, using expectations of off-diagonal Gram-matrix entries.Differences of independent uniform samples have a triangular distribution on [−1,1], whose expectations and second moments are computed in Lemma 29.Source: §B.2.5 · pp. 118–120
  • The Laplacian-kernel integral operator has positive, simple eigenvalues, and the sampled Gram matrix has positive, simple eigenvalues almost surely.The operator eigenvalues are pairwise distinct by their explicit decreasing form; for the Gram matrix, uniform samples are pairwise distinct almost surely, enabling an oscillation-matrix argument.Source: §B.2.5 · pp. 119, 127
  • Assumptions 1 and 2 are verified through concentration bounds and kernel-complexity conditions for the uniform distribution and Laplacian kernel.The argument uses bounded differences with McDiarmid’s inequality for Assumption 1 and establishes the required bounds for Assumption 2.Source: §B.2.5 · pp. 120, 121, 122, 124, 125, 126
  • cc-universality of the Laplacian kernel implies a positive-definite Gram matrix for pairwise distinct samples, hence the matrix is invertible.The cited discussion identifies the kernel as cc-universal and applies Corollary 4.3 of Carmeli et al. (2010).Source: §B.2.5 · p. 127
  • Positive off-diagonal entries make the sorted Gram matrix an oscillation matrix, which has positive and simple eigenvalues.The entries are positive by positivity of the exponential function; Lemmas 15 and 16 yield the matrix and eigenvalue properties.Source: §B.2.5 · p. 128
  • The original and sorted Gram matrices differ by a simultaneous row-and-column permutation, so they share eigenvalues and the original matrix also has positive, simple eigenvalues.The permutation matrix may depend on the realization.Source: §B.2.5 · p. 128

Appendix C. Independence Testing with the Permutation Approach

The permutation approach constructs a reference distribution by independently permuting the estimated latent-feature columns for each graph. It uses that distribution to test whether the LPRGs are independent.

Appendix C. Independence Testing with the Permutation Approach

  • For each graph, the procedure permutes the columns of the estimated feature matrix and forms a permuted Gram-matrix estimate.The estimated Gram matrix is formed from the feature matrix as its transpose times itself.Source: Appendix C · p. 128
  • The permuted estimates produce an empirical distribution used as the reference distribution for the test.The procedure forms an empirical cumulative distribution estimate from the permutation results.Source: Appendix C · p. 128
  • At level α, reject the null hypothesis of independence when the observed squared GHSIC estimate exceeds the permutation distribution's (1−α) quantile.Source: Appendix C · p. 128

Appendix D. Optimal Embedding Dimensions

Appendix D examines how embedding-dimension choices affect the GHSIC estimator’s error under polynomial and exponential eigenvalue decay, using Theorem 2’s bound to characterize attainable rates and admissible dimension ranges. For polynomial decay, the rate depends on the stated A_m and B_m terms and can approach O(n^-1/3), while the proposed A_m + B_m,1 regime is ruled out; the excerpt links θ_m=1/3 to the error without giving the resulting bound.

Appendix D. Optimal Embedding Dimensions

  • At θ_m = 1/(2α_m), A_m yields slower convergence than when θ_m > 1/(2α_m).Thus the analysis focuses on the strict inequality case.Source: Appendix D · p. 130
  • For non-equal exponents in n, B_m,1 converges faster than B_m,2 iff θ_m > α_m/(3α_m + 2), and slower iff θ_m < α_m/(3α_m + 2).Source: Appendix D · p. 134
  • B_m,3, B_m,4, and B_m,5 converge faster than B_m,1 or B_m,2, so the rate is determined by A_m combined with B_m,1 or B_m,2.The appendix treats these two dominant-term cases separately.Source: Appendix D · p. 135
  • The candidate A_m + B_m,1 regime requires α_m > 2 and 1/(2α_m) < θ_m < α_m/(3α_m + 2), but its balancing choice violates the interval, so this case is discarded.The appendix therefore turns to the A_m + B_m,2 case.Source: Appendix D · pp. 135–137

Polynomial eigenvalue decay

  • The polynomial-decay rate exponent is β = min{f(α₁), …, f(α_M)}: f is positive and strictly increasing, tends to 1/3 as α increases, and tends to zero at the hardest boundary.Thus, increasing the α_m values improves the estimator’s rate, which can approach O(n^-1/3); near the hardest boundary, the rate can become arbitrarily slow.Source: Appendix D · p. 139
  • Under the current error bound, an embedding dimension that grows only poly-logarithmically with node size is insufficient to guarantee consistency.The appendix considers dimensions d_m = Θ((log n)^s) and answers negatively whether this choice can drive the error to zero.Source: Appendix D · p. 140

Exponential eigenvalue decay

  • Under the assumed exponential eigenvalue decay, the passage states that the lower branch of A_m is activated for θ_m < 1.Source: Appendix D · pp. 140, 143
  • For exponential decay, terms B_m,3, B_m,4, and B_m,5 converge faster than B_m,1 or B_m,2, so the U_3,m rate is determined by A_m paired with one of the latter terms.In one case, matching the polynomial orders gives θ_m = 1/3; the appendix then derives an embedding-dimension choice and an upper bound for U_3,m.Source: Appendix D · pp. 143–144

Appendix D. Optimal Embedding Dimensions

  • The appendix identifies θ_m=1/3 as the setting used to characterize the GHSIC estimation error.The supplied passage ends before stating the bound.Source: Appendix D · p. 145

Related papers

Loading 2610.34544v1…