{"id":"fe1eb54a-753d-442e-8bc9-7fb8122db759","arxiv_id":"2501.10617","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Mutual Regression Distance is a new pseudometric between sample sets based on mutual linear regression, with simplified variants and empirical gains in clustering, GANs, and domain adaptation.","lead":"This paper defines a new distance between two sets of data points, called Mutual Regression Distance, built from how well each set can linearly reconstruct the other. The authors show it is a pseudometric and test it in clustering, image generation, and domain adaptation, where it often beats Wasserstein distance and MMD.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The simplified MRD computation rests on Lemma 3.9, which is false when the unregularized least-squares coefficient already has spectral norm below 1; Algorithm 1 cannot terminate in that case, so the empirical claims built on it are not supported as written.","rationale":"The central theoretical claim, Theorem 3.5, appears sound: the pseudometric proof in Appendix D uses feasible compositions S13 = S23 S12 and S31 = S21 S32, and the norm inequalities correctly bound the cross terms. I did not find a defect there. The weakest load-bearing point is the computational shortcut: the simplified MRD, kernel simplified MRD, and Algorithm 1 all depend on Lemma 3.9. That lemma is false exactly when the unregularized least-squares map already has spectral norm below 1, a case the proof silently omits. The concrete 2x2 example above shows the binary search cannot converge, so the empirical results in Tables 1-3, which use this heuristic, are not backed by a correct algorithm. The reader's weakest_assumption identified the same lemma, and both the Definition 3.8 typo and the Algorithm 1 failure are addressable in revision. These issues do not disprove the existence or metric properties of MRD, but they do mean the practical recipe is currently broken for a nonempty set of inputs. A conditional acceptance requiring a corrected lemma, an explicit handling of the ||S12(0)||<=1 case (e.g., setting lambda = 0), and a fixed Definition 3.8 remains the appropriate verdict.","tokens_in":29329,"tokens_out":7287,"duration_ms":69409,"concrete_test":"Run Algorithm 1 on X1 = [1; 0.2236] and X2 = diag(10, 0.4472) in R^{2x2}, so that X2^T X2 = diag(100, 0.2), X2^T X1 = [10; 0.1], r = 9.8, and ||S12(0)||_2 = 0.5099. Observe that for every c > 0, ||(X2^T X2 + cI)^-1 X2^T X1||_2 < 1, so the loop never exits. Alternatively, verify analytically that ||S12(lambda)||_2 is nonincreasing for lambda >= 0 and starts below 1, so the equation ||S12(lambda)||_2 = 1 has no solution in [0, r], directly contradicting Lemma 3.9.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.9 asserts that for any X1, X2 there is a unique lambda12 in [0, r] with ||S12(lambda12)||_2 = 1, where r = ||X2^T X1||_2 - sigma_min(X2^T X2). The proof in Appendix F considers only the cases ||S12(0)||_2 = 1 and ||S12(0)||_2 > 1, and omits the case ||S12(0)||_2 < 1. Since ||S12(lambda)||_2 is nonincreasing in lambda for lambda >= 0, no nonnegative lambda can increase the spectral norm to 1. Algorithm 1 initializes l = 0 and r = ||X2^T X1||_2 - sigma_min(X2^T X2); if ||S12(0)||_2 < 1, every c > 0 also gives ||S12(c)||_2 < 1, so the binary search never satisfies the stopping condition and loops forever. This is not a rare edge case: with X2^T X2 = diag(100, 0.2) and X2^T X1 = [10, 0.1]^T, we have r = 9.8 > 0 but ||S12(0)||_2 = sqrt(100/10000 + 0.01/0.04) = sqrt(0.01 + 0.25) = 0.5099 < 1. Because the simplified MRD, the kernel simplified MRD, and all experiments in Section 6 use this heuristic, the practical claims are load-bearing on a false lemma. The main pseudometric theorem (Theorem 3.5) is not affected, but the paper's computational contribution and empirical evaluations are not valid as stated. In addition, Definition 3.8 has an inconsistency: the objective defining S12* regularizes by ||S21||_F instead of ||S12||_F, making the simplified MRD ill-defined even before the algorithmic issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Mutual Regression Distance (MRD) between two data matrices X1 and X2, defined as the minimum of a weighted sum of two least-squares residuals subject to spectral-norm constraints on the coefficient matrices S12 and S21. It proves that MRD is a pseudometric (Theorem 3.5), proposes a tightened variant, a simplified variant with closed-form ridge solutions, and kernel extensions, and gives Gaussian perturbation bounds (Theorems 4.1 and 4.3). The authors also present a heuristic algorithm (Algorithm 1) to select regularization parameters so that the coefficient matrices have unit spectral norm, and they report experiments on distribution transformation, discrete-distribution clustering, GAN training, and Office-31 domain adaptation.","tokens_in":29817,"tokens_out":6589,"duration_ms":65118,"significance":"If the central pseudometric result holds, MRD is an interesting finite-sample dissimilarity that departs from pairwise-distance-based measures such as MMD and Wasserstein distance and may exploit regression structure in the data. The paper contains a genuine proof of the pseudometric axioms using a gluing lemma, and the perturbation bound for the original MRD (Theorem 4.1) is a clean Lipschitz-style result. However, the computational contribution rests on Lemma 3.9, which is false as stated, and Definition 3.8 is internally inconsistent; the kernel robustness proof in Theorem 4.3 also contains an unjustified algebraic step. The paper is promising but requires substantive correction before its practical and robustness claims can be accepted.","major_comments":[{"comment":"Lemma 3.9 is false when the unregularized least-squares coefficient already has spectral norm below 1. For example, with X2^T X2 = diag(100, 0.2) and X2^T X1 = [10, 0.1]^T, one has r = 9.8 > 0 but ||S12(0)||_2 = sqrt(100/10000 + 0.01/0.04) = 0.5099 < 1; since ||S12(lambda)||_2 is nonincreasing in lambda for lambda >= 0, no lambda in [0, r] gives unit spectral norm. The proof in Appendix F treats only the cases ||S12(0)||_2 = 1 and ||S12(0)||_2 > 1, so the asserted existence and uniqueness are not established. Consequently, Algorithm 1's binary search never terminates in the omitted case, because every c > 0 also yields ||S12(c)||_2 < 1. Since the simplified MRD, simplified kernel MRD, and all experiments in Section 6 rely on this search, the empirical claims are not supported as written.","section":"§3.2, Lemma 3.9 and Algorithm 1"},{"comment":"Definition 3.8 is internally inconsistent: the objective defining S*_12 is written with a regularizer (lambda12/2)||S21||_F^2 rather than (lambda12/2)||S12||_F^2, while the displayed closed form S*_12 = (X2^T X2 + lambda12 I_n2)^{-1} X2^T X1 is the solution to the ridge problem with ||S12||_F^2. The same issue appears in Definition 3.12 for the kernel variant. This makes the simplified MRD ill-defined and must be corrected before Algorithm 1 can be interpreted as computing it.","section":"Definition 3.8"},{"comment":"The proof of Theorem 4.3 contains an unjustified algebraic step: the trace expression on the left of Eq. (75), which includes a term epsilon11 n1 plus terms involving |S12| and |S12|^T |S12|, is bounded by epsilon || |S12|^T I_n2 + I_n1 ||_2^2 without a supporting inequality relating a sum of traces to a squared spectral norm. The subsequent bound in Eq. (79) also needs a correct derivation, as it appears to mix Frobenius-norm and spectral-norm estimates. Since Theorem 4.3 is the advertised robustness guarantee for kernel MRD, this gap must be repaired.","section":"Theorem 4.3, proof around Eq. (75)"},{"comment":"No population limit or consistency result is provided. MRD is defined for finite matrices X1 in R^{m x n1} and X2 in R^{m x n2}, but the abstract and introduction describe it as a distance between distributions. There is no theorem showing that MRD(X1, X2) converges, as n1 and n2 grow, to a quantity depending only on the underlying distributions, nor that the empirical estimator is consistent. Given that the numerical comparisons are used to claim superiority over MMD and Wasserstein distance as distribution distances, a population-level definition or a consistency theorem is needed.","section":"Sections 1 and 6"}],"minor_comments":[{"comment":"The initialization in Algorithm 1 sets r = ||X2^T X1||_2 - ||X2^T X2||_2, but Lemma 3.9 uses sigma_min(X2^T X2); if sigma_min(X2^T X2) is small or r is negative, the search interval is inconsistent with the lemma and the algorithm is undefined.","section":"Algorithm 1"},{"comment":"The symbol X is used both for a data matrix and for a distribution (e.g., 'X1 ∈ R^{m x n1}' versus 'X1, X2, X3 ∈ R^{m x n}'), which is occasionally confusing; calligraphic letters for distributions would improve clarity.","section":"Notation throughout"},{"comment":"The feasible set S_F^{≤1} is defined generically with dimensions m and n, but the matrices S12 and S21 have different dimensions; the notation should use generic p and q to avoid ambiguity.","section":"Definition 3.7"},{"comment":"The FID and Inception Score results in Table 2 report standard deviations but no number of random seeds or a statistical test; adding this information would make the claimed improvements more verifiable.","section":"Section 6.3"}],"recommendation":"major_revision","confidential_remarks":"The central pseudometric proof appears sound, and the issues are concentrated in the computational and robustness machinery. The false Lemma 3.9, the inconsistent Definition 3.8, and the gap in Theorem 4.3 are identifiable and plausibly fixable, but they affect the paper's main practical claims. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core idea is new and the pseudometric proof holds up, but the simplified computation used in all experiments is built on a false lemma and an inconsistent definition. The paper deserves a serious referee but needs substantial revision before the empirical claims can be trusted.\n\nWhat's new: MRD—mutual regression with spectral-norm-ball constraints—is a real departure from MMD/OT. The triangle inequality proof via the gluing lemma is clever and appears correct for the constrained problem. The tightened Frobenius-norm variant is also fine. The robustness bound for the linear case (Theorem 4.1) is routine but clean. These are genuine contributions.\n\nSoft spots, in order:\n\n1. Lemma 3.9 is false. The proof only treats ||S12(0)|| >= 1 and asserts monotonicity in the wrong direction. Since ||S12(lambda)|| is nonincreasing, if the unregularized solution already has spectral norm below 1, no lambda in [0,r] achieves norm 1. Algorithm 1 then cannot terminate. This is not exotic—a simple two-column example gives r > 0 but ||S12(0)|| = 0.51. The experiments use this algorithm (via simplified MRD), so the empirical sections are not supported as written. The fix is easy (if norm <1 at 0, take lambda=0), but it needs to be said.\n\n2. Definition 3.8 is internally inconsistent: the S12 subproblem penalizes ||S21||_F instead of ||S12||_F, and the closed form doesn't match the stated objective. That's a presentation bug, but it makes the simplified MRD ill-defined.\n\n3. Theorem 4.3's proof has algebraic and dimensional errors (mixing identity with all-ones, dropping signs in the positive/negative decomposition). The bound as written doesn't hold. I would not rely on the kernel perturbation result without a rewrite.\n\n4. No population limit or consistency for MRD as a distribution distance. For a paper that motivates MRD as a distance between distributions, the lack of any sample-size analysis is a real gap, though not fatal.\n\nThe clustering table has no error bars, but the GAN numbers do, so that's a minor quibble.\n\nWho this is for: anyone working on distribution distances, OT/MMD alternatives, or manifold-aware losses. The idea is worth engaging with, but I would not accept the paper in its current form. The pseudometric theorem is likely correct, but the computational and empirical backbone needs to be rebuilt or restricted to the cases where Lemma 3.9 actually holds. Recommend major revision with the theoretical gaps addressed.","headline":"A genuinely new distance with a correct pseudometric theorem, but the simplified algorithm behind every experiment rests on a false lemma and a miswritten definition.","tokens_in":30254,"tokens_out":5096,"would_cite":true,"duration_ms":48420,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"MRD turns mutual linear regression into a pseudometric between data sets.","keywords":["mutual regression distance","pseudometric","distribution comparison","kernel methods","spectral norm constraint","maximum mean discrepancy","Wasserstein distance","domain adaptation"],"falsifier":"Take any full-rank $X_2$ and set $X_1=0.1\\,X_2$. Then the unregularized coefficient is $0.1\\,I$ with spectral norm $0.1<1$, so Lemma 3.9's assertion that a unique $\\lambda\\in[0,r]$ with $\\|S_{12}(\\lambda)\\|_2=1$ exists is false, and Algorithm 1's binary search will keep halving the interval without ever reaching the tolerance. Running the algorithm on this pair is a direct test of the assumption behind the simplified MRD.","tokens_in":29130,"feed_emoji":"📐","tokens_out":9475,"duration_ms":85664,"temperature":0.7,"pith_summary":"The paper introduces the Mutual Regression Distance (MRD), a way to measure how dissimilar two collections of data points are. Instead of averaging pairwise point distances as Wasserstein distance and MMD do, MRD asks how accurately each set can linearly reconstruct the other, with both reconstruction matrices constrained to have spectral norm—their largest singular value—at most 1; the distance is the combined reconstruction error. The paper proves that this quantity is a pseudometric, meaning it is nonnegative, symmetric, and obeys the triangle inequality, so it can serve as a loss or affinity in distribution-comparison tasks. Because the constrained problem is costly, the paper proposes a tightened version, a simplified closed-form ridge version, and kernel variants, and it reports lower computational cost than Wasserstein distance. The motivation is that regression-based reconstruction respects the smoothness of data lying on manifolds, which pairwise distances ignore.","feed_headline":"Mutual regression yields a proven pseudometric for comparing data sets","feed_subtitle":"Unlike MMD and Wasserstein costs, MRD exploits manifold structure and has a fast closed-form variant.","key_machinery":"The central object is the mutual regression problem: minimize the symmetric reconstruction error $\\sqrt{\\tfrac12\\|X_1-X_2S_{12}\\|_F^2+\\tfrac12\\|X_2-X_1S_{21}\\|_F^2}$ subject to $\\|S_{12}\\|_2\\le1$ and $\\|S_{21}\\|_2\\le1$. The spectral-norm ball is the load-bearing constraint: it makes the feasible set convex, keeps the problem meaningful when the two point sets have different cardinalities, and—through submultiplicativity $\\|S_{23}S_{12}\\|_2\\le\\|S_{23}\\|_2\\|S_{12}\\|_2$—it is exactly what allows the gluing lemma that proves the triangle inequality. The simplified variant replaces the constraint by ridge regularization and searches for the regularization coefficient that puts the ridge estimate on the boundary of the spectral-norm ball.","core_discovery":"On its own terms, the paper's central claim is Theorem 3.5: for $X_1, X_2 \\in \\mathbb{R}^{m\\times n}$, the value\n$$\\mathrm{MRD}(X_1,X_2)=\\min_{\\{S_{12},S_{21}\\}\\subseteq \\mathcal{S}^{\\le 1}_2}\\sqrt{\\tfrac12\\|X_1-X_2S_{12}\\|$_F^{2}$+\\tfrac12\\|X_2-X_1S_{21}\\|$_F^{2}$}$$\nis a pseudometric, where $\\mathcal{S}^{\\le1}_2$ is the set of matrices with spectral norm at most 1. The proof is carried by a gluing construction: composing the two optimal maps through an intermediate sample set produces admissible maps $S_{13}=S_{23}S_{12}$ and $S_{31}=S_{21}S_{32}$ because the spectral norm is submultiplicative, which yields the triangle inequality. The paper also shows that zero distance does not imply equality; the same-subspace example of Example 3.6 gives $X_1=X_2S_{12}$ with $\\|S_{12}\\|_2\\le1$ for different columns, so MRD intentionally fails separation and is permutation-invariant. For computation, the simplified MRD uses ridge-regularized least squares $S_{12}(\\lambda)=(X_2^\\top X_2+\\lambda I_{n_2})^{-1}X_2^\\top X_1$, with $\\lambda$ chosen by binary search so that $\\|S_{12}(\\lambda)\\|_2=1$; Lemma 3.9 asserts such a $\\lambda$ is unique in $[0,r]$ with $r=\\|X_2^\\top X_1\\|_2-\\sigma_{\\min}(X_2^\\top X_2)$.","pith_inferences":["Because MRD can be zero for different data sets that lie on the same subspace, the distance is better interpreted as a dissimilarity between manifolds or representational capacities than as a statistical divergence; this suggests testing MRD on pairs of distributions with identical support but different densities, where MMD would separate them but MRD may not.","The heuristic link between the constrained MRD and the ridge-based simplified MRD is only via the spectral-norm boundary condition; one could quantify the gap by comparing Algorithm 1's output to the exact constrained optimum on random matrices where the unregularized norm is far from 1.","The proof mechanism suggests an extension: verify whether the tightened Frobenius-norm variant preserves the triangle inequality, since the gluing argument no longer applies directly when composition can leave the Frobenius ball."],"forward_implications":["MRD is a valid objective for distribution matching: because it satisfies the triangle inequality and symmetry, using it as a loss in generative models or as an affinity in clustering inherits metric-like guarantees.","The simplified MRD reduces computation to ridge regressions and a one-dimensional search, so it offers a cheaper alternative to Wasserstein distance in high-dimensional comparisons.","Kernel MRD remains a pseudometric and lets the same regression construction act on nonlinear manifolds through the kernel trick.","Under Gaussian noise, MRD changes by at most $2\\sigma\\xi_{m,n_1,n_2}\\sqrt{w_1+w_2}$ with high probability, so the distance is robust to perturbation."],"supporting_citations":[{"why":"Defines MMD, the main distribution-distance baseline whose pairwise-point limitation MRD is designed to overcome.","marker":"[Gretton et al., 2012]"},{"why":"Supplies the optimal-transport and Wasserstein framework compared throughout, and the computational-cost contrast.","marker":"[Villani et al., 2009]"},{"why":"Introduces Sinkhorn distance, the entropic-OT baseline and computational-efficiency comparison point.","marker":"[Cuturi, 2013]"},{"why":"WGAN baseline that positions MRD as an alternative loss in generative modeling.","marker":"[Arjovsky et al., 2017]"},{"why":"Provides the gradient regularizers for kernel IPM GANs used in the SMRDGAN objective.","marker":"[Arbel et al., 2018]"},{"why":"Supplies the DDSC spectral-clustering framework and baseline distance affinities used in text clustering.","marker":"[Wang et al., 2024]"},{"why":"Gives the chi-square tail bounds used in the robustness theorems.","marker":"[Laurent and Massart, 2000]"},{"why":"Supplies the domain-adaptation framework and multi-kernel strategy used in the Office-31 experiments.","marker":"[Long et al., 2015]"}],"fun_headline_variants":["Mutual regression gives a fast manifold-aware distance","MRD: a proven pseudometric for manifold data","Proven fast distance for manifold data","Fast closed-form distance via mutual regression","Manifold-aware distance from mutual regression"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The practical algorithm assumes that the unregularized least-squares map from $X_2$ to $X_1$, namely $(X_2^\\top X_2)^{-1}X_2^\\top X_1$, already has spectral norm at least 1, so that increasing the ridge penalty can bring that norm down to exactly 1; when the norm is already below 1, no such penalty exists and the binary-search subroutine has no solution to find.","fun_headline_variants_meta":{"raw":{"variants":["Mutual regression gives a fast manifold-aware distance","MRD: a proven pseudometric for manifold data","Proven fast distance for manifold data","Fast closed-form distance via mutual regression","Manifold-aware distance from mutual regression"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00147,"raw_usage":{"total_tokens":6016,"prompt_tokens":1159,"completion_tokens":4857,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":775,"completion_tokens_details":{"reasoning_tokens":4790}},"tokens_in":775,"tokens_out":4857,"duration_ms":30182,"temperature":1.0,"reasoning_tokens":4790,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:02:29.384353+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any full-rank $X_2$ and set $X_1=0.1\\,X_2$. Then the unregularized coefficient is $0.1\\,I$ with spectral norm $0.1<1$, so Lemma 3.9's assertion that a unique $\\lambda\\in[0,r]$ with $\\|S_{12}(\\lambda)\\|_2=1$ exists is false, and Algorithm 1's binary search will keep halving the interval without ever reaching the tolerance. Running the algorithm on this pair is a direct test of the assumption behind the simplified MRD.","supporting_citations":[{"cited_title":"Spectral Clustering for Discrete Distributions","cited_arxiv_id":"2401.13913","evidence_quote":"Supplies the DDSC spectral-clustering framework and baseline distance affinities used in text clustering."},{"cited_title":"Adaptive estimation of a quadratic functional by model selection","cited_arxiv_id":null,"evidence_quote":"Gives the chi-square tail bounds used in the robustness theorems."},{"cited_title":"Learning transferable features with deep adaptation networks","cited_arxiv_id":null,"evidence_quote":"Supplies the domain-adaptation framework and multi-kernel strategy used in the Office-31 experiments."}],"review_version":1}