{"id":"fa55d4dc-9d94-42c5-af86-64870be39e0b","arxiv_id":"2504.20194","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"CO2 reduces coreset selection for any smooth divergence to MMD minimization and proves that Sinkhorn divergence coresets of size m=ω(log^d n) match the error of the full empirical measure.","lead":"This paper introduces CO2, an algorithm that compresses large datasets into a small weighted subset while preserving a chosen statistical divergence, and shows that for the Sinkhorn divergence only polylogarithmically many points are needed. The result connects coreset selection to kernel quadrature and could make optimal-transport-based data compression practical.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's O(n^2m + m^3) construction time rests on Lemma 12, whose Nyström transfer proof is explicitly deferred; without it only the exact-SVD variant is supported, and its cost is unanalyzed.","rationale":"I read the paper in good faith. The main quantitative claim — that Sinkhorn divergence coresets of size m = ω(log^d n) can be asymptotically lossless at the 1/n scale — is supported by a long and mostly careful chain: Lemma 1 reduces smooth divergence compression to MMD; Lemma 2 gives fast MMD compression from spectral tail bounds; Lemmas 60–61 give exponential Gaussian tail decay; and Theorems 8, 40, 43, 48, and 9 establish the needed second-order Hadamard differentiability relative to the Gaussian RKHS. I did not find a concrete mathematical error in Theorem 48's derivation; the local approximation from Gonzalez-Sanz et al. is cited and the algebra in the g1/g2 expansion checks out after accounting for the separable structure of the potentials. The reader's weakest_assumption (Theorem 48) is indeed load-bearing, but it is not where I found an actual gap. The concrete gap is the self-acknowledged incompleteness of Lemma 12. That lemma is needed to justify the O(n^2m + m^3) construction time in Theorem 7 when using the Sinkhorn kernel rather than a generic Gaussian kernel. Since the proof explicitly defers the Nyström manipulations, the stated computational guarantee is not yet established. This does not require rejection: the statistical coreset result may stand, and the gap could be closed by a complete Nyström transfer analysis or by explicitly limiting Theorem 7 to the exact-SVD variant with a corrected complexity. Because the reader already issued a CONDITIONAL verdict and my concern reinforces that condition rather than overturning it, I recommend UNCHANGED. Minor issues I noticed but do not treat as load-bearing: Lemma 25's claim that every continuous-kernel RKHS unit ball is Donsker is too strong in general (though true for the Gaussian kernel used here), and the Hadamard operator in Theorem 9 appears to absorb a factor of 1/2 from Theorem 48 without comment. Neither changes the rates or the main conclusion.","tokens_in":42412,"tokens_out":44074,"duration_ms":447872,"concrete_test":"Complete the deferred Nyström argument: let π be the n×n entropic plan and let π̃ be its rank-r Nyström approximation from Algorithm 4 with r = θm. Define G̃ from the same sketch by applying the spectral map λ ↦ εnλ/(1 - λ^2) to the approximate eigenvalues of π. Prove or disprove a bound of the form ||G_n - G̃||_1 ≤ C||π - π̃||_1 (or a bound in terms of the same tail T(m)), and then verify that recombination against G̃ yields Q_{G̃}(P_n - P_m) = o_p(n^{-1}). If the transfer fails, restate Theorem 7 for the exact-SVD construction and revise the time complexity to include the O(n^3) eigendecomposition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim bundles a statistical guarantee with a fast-construction claim: Theorem 7 asserts that a polylog-size Sinkhorn coreset can be built in O(n^2m + m^3) time. The statistical half of the argument (Theorems 3, 9, and 48) is coherent and I did not find a concrete flaw in the second-order Hadamard differentiability proof. The weak point is the computational half. Algorithm 3 requires a rank-m Nyström approximation of the Sinkhorn kernel G_n = εn(I - π/2)^{-1}π, where π = π^ε_{P_n,P_n}. Because G_n is a spectral function of π, the natural fast route is to Nyström-approximate π and transfer the eigenpairs to G_n. This is exactly what Lemma 12 asserts, but its proof only treats the exact rank-r SVD and then stops: 'We leave a complete argument to future research, as the necessary Nyström manipulations are outside the scope of this paper.' Without that transfer, the only proven construction uses an exact eigendecomposition of G_n (or solves linear systems with (I - π/2)^{-1}), which costs O(n^3) rather than O(n^2m + m^3). Thus the theorem's stated time complexity is not fully supported. The existence of asymptotically lossless polylog coresets may survive if one pays O(n^3), but the theorem as written — with its O(n^2m + m^3) construction — is conditional on closing the Lemma 12 gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces CO2, a two-stage framework for convexly weighted coreset selection with respect to generic smooth divergences. The first stage identifies the second-order Hadamard derivative of the divergence and the associated Hadamard operator, and the second stage performs MMD compression with respect to that operator using a Nyström-based recombination algorithm. The authors apply this framework to the Sinkhorn divergence, deriving new Hadamard differentiability results for entropic optimal transport potentials and showing that the Sinkhorn divergence is second-order Hadamard differentiable relative to a Gaussian RKHS. Their main theorem claims that, for m = ω(log^d n), a coreset of size m can be constructed in O(n^2 m + m^3) time such that S(P, P_m) = S(P, P_n) + o_p(1/n). Numerical experiments on Gaussian mixtures and MNIST illustrate the method's practical performance.","tokens_in":42728,"tokens_out":11582,"duration_ms":118190,"significance":"If the main result holds, this is a significant contribution: it gives the first polylogarithmic-size coreset guarantee for the Sinkhorn divergence, connects coreset selection to kernel quadrature through a functional Taylor expansion, and contains new regularity results for entropic optimal transport potentials that are of independent interest. The theoretical derivation is largely self-contained: the Sinkhorn kernel is derived from the divergence rather than fitted to data, the polylog bound follows from known geometric spectral decay of Gaussian kernels, and the proof of second-order Hadamard differentiability is detailed. The code is publicly available, and the experiments are clearly described. The principal weakness is that the advertised fast construction time is not fully supported, because the key Nyström transfer argument in Lemma 12 is explicitly deferred rather than proved.","major_comments":[{"comment":"Theorem 7's O(n^2 m + m^3) construction time is not fully supported, because the proof of Lemma 12 only treats the exact rank-r SVD variant and explicitly defers the Nyström transfer: 'We leave a complete argument to future research, as the necessary Nyström manipulations are outside the scope of this paper.' The proof assumes that the residual vector w satisfies a_1 = ... = a_m = 0 in the eigenbasis of π_{P_n,P_n}, which is a property of exact diagonalization and subsequent exact recombination, not of the Nyström approximation used in Algorithm 3. Since Algorithm 3 and Section 5 operate with the Nyström approximation of G or of ξ_n, the stated polylogarithmic guarantee at O(n^2 m + m^3) time remains conditional. A complete proof of the Nyström transfer, or a revised Theorem 7 that states the O(n^3) exact-SVD construction, is needed.","section":"§4.3, Lemma 12; Theorem 7"},{"comment":"There is an ambiguity about which quadratic form the implemented algorithm minimizes: Section 5 says 'CO2 is performed with respect to π_{P_n,P_n} for improved computational efficiency as detailed in Section 4.3,' while Algorithm 3 calls Nyström(G) on the Hadamard operator G. Lemma 12 only relates Q_{G_n} to εQ_{ξ_n} in the exact-SVD case. The paper does not provide a theorem showing that the Nyström-approximated directions of π_{P_n,P_n} yield the same or sufficiently close guarantee as exact SVD, so the empirical procedure and the mathematical claim in Theorem 7 are not yet matched.","section":"§4.3, Lemma 12; §5"}],"minor_comments":[{"comment":"The word 'ambguity' should be 'ambiguity'.","section":"§3.1"},{"comment":"Theorem 7 states O(n^2 m + m^3), but Lemma 2 and Theorem 3 include θ^3 m^3 and m^3 log(n/m) factors; the theorem should either state the assumptions on the oversampling parameter θ or present the complexity consistently with the lemmas it relies on.","section":"Theorem 7"},{"comment":"Algorithm 2 defines V as the orthogonal complement of U⊕1, whereas Algorithm 5 uses U⊕1⊕kdiag; the two algorithms should use the same complement, or the difference should be justified in the text.","section":"Algorithm 2 and Algorithm 5"},{"comment":"The claim that the eigenvalues λ_i of π_{P_n,P_n} are geometrically decaying by 'Lemmas 22 and 61' is not self-evident; the argument should explicitly explain how uniform smoothness of the Sinkhorn scalings and the Gaussian RKHS spectral decay combine to yield this geometric decay for the empirical Sinkhorn plan.","section":"Proof of Lemma 12"}],"recommendation":"major_revision","confidential_remarks":"The statistical core of the paper appears sound and the derivation of the Sinkhorn kernel is a genuine contribution. The advertised efficient algorithm, however, is conditional on closing the Lemma 12 gap. I would ask the authors either to provide the missing Nyström transfer proof or to restate Theorem 7 as an existence result with an exact eigendecomposition and O(n^3) cost, while clearly separating the heuristic efficient implementation in the experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it delivers a real first: polylogarithmically many points suffice for asymptotically lossless Sinkhorn coresets, and the reduction from smooth divergence compression to MMD compression is a clean idea that will likely be reused. Second, the paper's headline theorem bundles a statistical guarantee with a fast-construction claim, and the fast half is not fully proven. The gap is explicit and load-bearing, so the theorem as stated is conditional.\n\nWhat is actually new and good: the CO2 framework connects second-order Hadamard differentiability to MMD compression, and the new regularity results for entropic OT potentials in Gaussian RKHS are nontrivial and of independent interest. The Sinkhorn kernel is derived from the divergence, not fitted, and the polylog bound follows from known spectral decay of Gaussian kernels. I read through the statistical chain—Theorem 3, Theorem 9, Theorem 48—and it holds together. The proof of second-order Hadamard differentiability is detailed and I did not find a concrete flaw there. The paper is also honest in its discussion and does not oversell comparison to prior work.\n\nThe soft spot is exactly where the stress-test lands: Lemma 12. To get the fast implementation, the paper needs a Nyström approximation of the Sinkhorn kernel to transfer eigenpairs from the entropic plan to G_n. But the proof of Lemma 12 only treats the exact rank-r SVD and then stops. The authors write, \"We leave a complete argument to future research, as the necessary Nyström manipulations are outside the scope of this paper.\" That is an explicit omitted proof, and it is not minor. Without that transfer, the only proven construction uses an exact eigendecomposition or solves n×n linear systems, costing O(n^3) rather than O(n^2m + m^3). The statistical guarantee—polylog points suffice—likely survives even at O(n^3), but Theorem 7 as written bundles an unproven computational claim. The experiments show the Nyström approximation works in practice, but numerical evidence does not close the gap.\n\nWho should read this: anyone working on coresets, kernel quadrature, or entropic optimal transport. It deserves a serious referee, and I would send it out. The fix is clear: either close the Nyström transfer argument or restate Theorem 7 with the exact-SVD variant and analyze its cost. I would recommend conditional acceptance, with the Lemma 12 gap resolved or explicitly scoped out of the main theorem.","headline":"A genuinely new polylog Sinkhorn coreset result with a coherent statistical core, but the advertised O(n^2m + m^3) construction time rests on an explicitly deferred Nyström proof that needs to be fixed before publication.","tokens_in":43237,"tokens_out":2538,"would_cite":true,"duration_ms":27594,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For the Sinkhorn divergence, a convexly weighted coreset of $m = \\omega(\\log^d n)$ observed points reproduces the full-sample divergence up to an asymptotically negligible $o_p(1/n)$ error.","keywords":["coresets","Sinkhorn divergence","maximum mean discrepancy","Hadamard differentiability","entropic optimal transport","kernel quadrature","recombination","Nyström approximation"],"falsifier":"Fix a compactly supported distribution in dimension $d$ and a regularization level $\\varepsilon$; draw $n$ samples, build a CO2 coreset with $m=C\\log^d n$ for several growing $n$, and compute $n|S(P,P_m)-S(P,P_n)|$ over repeated trials. Theorem 7 predicts this quantity converges to zero; observing bounded-away-from-zero values, or confidence intervals that do not shrink like $1/\\sqrt{n}$, would refute the central guarantee.","tokens_in":42218,"feed_emoji":"🎯","tokens_out":8191,"duration_ms":76863,"temperature":0.7,"pith_summary":"This paper introduces CO2 (Coresets of Order 2), a two-step recipe for compressing a dataset with respect to any smooth divergence: expand the divergence to second order around the empirical distribution, which turns the task into a maximum mean discrepancy minimization, then compress against the kernel that appears in that expansion. The flagship application is the Sinkhorn divergence, the debiased entropically regularized optimal transport loss often used as a fast, smooth stand-in for Wasserstein distance. The paper claims that a convexly weighted coreset of $m = \\omega(\\log^d n)$ of the $n$ observed points reproduces the full-sample Sinkhorn divergence up to $S(P,P_m)=S(P,P_n)+o_p(1/n)$, matching random sampling at the $1/n$ scale with far fewer than $n$ points. If this is right, Sinkhorn coresets are the first provably asymptotically lossless $o(n)$-sized coresets for an optimal-transport-style loss, and coreset selection becomes a direct instance of kernel quadrature with a data-dependent kernel.","feed_headline":"Polylog points match full-sample Sinkhorn accuracy","feed_subtitle":"CO2 compresses smooth divergences by Taylor-expanding them into MMD problems, needing only log^d n points.","key_machinery":"The load-bearing object is the Hadamard operator $G$, the kernel of the divergence's second-order Taylor term at the population distribution: Lemma 1 shows that once $D$ is second-order Hadamard differentiable, $D(P_m)=D(P_n)+o_p(1/n)$ follows from $\\mathrm{MMD}_G(P_n,P_m)=o_p(n^{-1/2})$, so compression reduces to MMD against $G$. For the Sinkhorn divergence the paper computes $G=\\varepsilon(I-A^2)^{-1}\\xi$, where $A$ is the entropic optimal transport operator $Af(x)=\\int \\xi(x,y)f(y)\\,dP(y)$ and $\\xi$ is the density of the entropic self-coupling, and proves this kernel is equivalent to the Gaussian kernel $\\exp(-\\|x-y\\|^2/\\varepsilon)$. The algorithm then builds the coreset by recombination on Nyström eigenvectors of the empirical $G_n$, and the geometric spectral decay of Gaussian Gram matrices supplies the $m=\\omega(\\log^d n)$ rate through Lemma 61.","core_discovery":"The central discovery is that second-order Hadamard differentiability turns divergence compression into MMD compression: Lemma 1 shows that if $D$ is second-order Hadamard differentiable at $P$, then any $P_m$ with $\\mathrm{MMD}_G(P_n,P_m)=o_p(n^{-1/2})$ satisfies $D(P_m)=D(P_n)+o_p(1/n)$, where $G$ is the kernel of the quadratic term. For the Sinkhorn divergence the paper verifies the previously unknown regularity needed to apply this: $S$ is second-order Hadamard differentiable relative to the Gaussian kernel RKHS, with Hadamard operator $G=\\varepsilon(I-A^2)^{-1}\\xi$ equivalent to the Gaussian kernel, and entropic optimal transport potentials are Hadamard differentiable in that refined topology. Because Gaussian Gram matrices have geometric spectral decay, the recombination-plus-Nyström MMD compressor needs only $m=\\omega(\\log^d n)$ points and $O(n^2m+m^3)$ time to reach the $o_p(1/n)$ target. The proof passes through new differentiability results for the exponentiated entropic potentials $(u_{\\mu,\\nu},v_{\\mu,\\nu})=(e^{-\\phi_{\\mu,\\nu}/\\varepsilon},e^{-\\psi_{\\mu,\\nu}/\\varepsilon})$.","pith_inferences":["The condition the paper actually needs is spectral equivalence between the divergence's second-order operator and a kernel with fast decay; entropically regularized Wasserstein losses with other ground costs are the natural testbed for whether the polylog result is specific to the Gaussian kernel or generic across smooth divergences.","The paper's reduction suggests a black-box implementation: estimate the second-order Hadamard operator by automatic differentiation of the divergence and compress against the resulting data-dependent kernel, avoiding the analytic derivation that currently limits CO2 to specially studied functionals.","The MNIST label-proportion result hints that Sinkhorn-optimal coresets are good for downstream aggregate statistics, not just for the divergence itself; a direct test would compare CO2 coresets against pure MMD coresets on classification and moment-estimation tasks.","The paper leaves the replacement of $Q_{G_n}$ by the cheaper $\\varepsilon Q_{\\xi_n}$ as a conjecture supported by Lemma 12; if that exponential-rate claim is correct, computing Sinkhorn coresets requires only one entropic plan and its spectrum."],"forward_implications":["With $m=\\omega(\\log^d n)$, Sinkhorn coresets achieve $S(P,P_m)=S(P,P_n)+o_p(1/n)$ in $O(n^2m+m^3)$ time, so asymptotic losslessness does not require a constant fraction of the data.","Since the reduction to MMD is generic, any improvement in convex MMD compression can be substituted into CO2 and immediately improves Sinkhorn coresets.","The new Hadamard differentiability results for entropic optimal transport potentials extend to other functionals built from entropic plans, such as the regularized OT cost itself or entropic barycenters, potentially giving them the same coreset guarantees.","In Sobolev-type RKHSs of order $\\alpha$, the same framework gives $m=\\omega(n^{1/(1-\\beta)})$ points, so the required coreset size tracks the spectral decay of the kernel exactly."],"supporting_citations":[{"why":"Defines the Sinkhorn divergence as the debiased entropically regularized OT functional that CO2 compresses.","marker":"Ramdas et al. (2015)"},{"why":"Introduces entropic regularization of optimal transport, the object behind $OT_\\varepsilon$ used throughout.","marker":"Cuturi (2013)"},{"why":"Supplies the local quadratic approximation of $OT_\\varepsilon$ and the analytic form of potential derivatives that Theorem 48 builds on.","marker":"Gonzalez-Sanz et al. (2022)"},{"why":"Establishes Hadamard differentiability of entropic potentials and the functional delta method used in Lemma 1's proof.","marker":"Goldfeld et al. (2022)"},{"why":"Provides the sampling-based kernel quadrature and recombination scheme adapted in Lemma 2 for fast MMD compression.","marker":"Hayakawa et al. (2023)"},{"why":"Provides the random-projection Nyström approximation used in the CO2 algorithm to make recombination efficient.","marker":"Tropp et al. (2017)"},{"why":"Verifies uniform boundedness of eigenfunctions and the Gaussian and Sobolev spectral decay rates used in Lemma 61 to obtain $m=\\omega(\\log^d n)$.","marker":"Yang et al. (2020)"},{"why":"Introduces high-order recombination, the core of the convex-weighting step in CO2's second stage.","marker":"Litterer and Lyons (2012)"}],"fun_headline_variants":["CO2: quadratic Taylor coresets for smooth divergences","Taylor expansion reduces coreset selection to MMD","Sinkhorn coreset needs only log^d n points","Hadamard regularity powers poly-log Sinkhorn coresets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the Sinkhorn divergence's error as a function of the data distribution has a valid quadratic Taylor approximation in the very smooth function space induced by a Gaussian kernel, which the proof obtains from a technical local approximation and compact-support assumptions; if that Taylor approximation fails, the polylogarithmic guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["CO2: quadratic Taylor coresets for smooth divergences","Taylor expansion reduces coreset selection to MMD","Sinkhorn coreset needs only log^d n points","Hadamard regularity powers poly-log Sinkhorn coresets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000666,"raw_usage":{"total_tokens":3049,"prompt_tokens":961,"completion_tokens":2088,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":2021}},"tokens_in":577,"tokens_out":2088,"duration_ms":16818,"temperature":1.0,"reasoning_tokens":2021,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:34:41.630169+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a compactly supported distribution in dimension $d$ and a regularization level $\\varepsilon$; draw $n$ samples, build a CO2 coreset with $m=C\\log^d n$ for several growing $n$, and compute $n|S(P,P_m)-S(P,P_n)|$ over repeated trials. Theorem 7 predicts this quantity converges to zero; observing bounded-away-from-zero values, or confidence intervals that do not shrink like $1/\\sqrt{n}$, would refute the central guarantee.","supporting_citations":[{"cited_title":"On wasserstein two sample testing and related families of nonparametric tests, 2015","cited_arxiv_id":null,"evidence_quote":"Defines the Sinkhorn divergence as the debiased entropically regularized OT functional that CO2 compresses."},{"cited_title":"Weak limits of entropy regularized optimal transport; potentials, plans and divergences","cited_arxiv_id":null,"evidence_quote":"Supplies the local quadratic approximation of $OT_\\varepsilon$ and the analytic form of potential derivatives that Theorem 48 builds on."},{"cited_title":"Sampling-based nystr\\\"om approximation and kernel quadrature, 2023","cited_arxiv_id":null,"evidence_quote":"Provides the sampling-based kernel quadrature and recombination scheme adapted in Lemma 2 for fast MMD compression."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Verifies uniform boundedness of eigenfunctions and the Gaussian and Sobolev spectral decay rates used in Lemma 61 to obtain $m=\\omega(\\log^d n)$."}],"review_version":1}