{"id":"d5482452-0b92-4edb-b975-149315d73c7f","arxiv_id":"2507.21519","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A two-stage algorithm that fits non-negative tensor trains to high-dimensional discrete distributions using Newton-based alternating minimization with a log barrier converges much faster than the previous multiplicative update method.","lead":"This paper introduces a faster way to compress high-dimensional probability distributions into a non-negative tensor train, a structured representation used in variational inference and density estimation. The method first approximates the distribution as a tensor train, then fits a non-negative version using Newton steps with a log barrier, reporting order-of-magnitude speedups over the prior multiplicative update baseline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The convergence theory in §3 covers exact repeated Newton steps on a fixed subproblem, but Algorithm 2.2 uses one approximate Newton step per component with a changing barrier; the claimed speed-up therefore rests on tuned empirical examples rather than on the proven result.","rationale":"The strongest claim is specifically that the second-order fitting procedure converges drastically faster than the multiplicative update; this is used to justify the whole paper and the 'accurate compression' claims. The paper's only formal support is Theorem 3.4, which applies to repeated exact Newton steps for a fixed component with a fixed barrier. The actual loop changes the objective every sweep, visits each component once, and solves the Newton system approximately; hence Theorem 3.4 cannot by itself explain the observed speed. This is not a flaw in the numerics if the experiments cleanly demonstrate the improvement, but the numerical evidence is limited to five examples, no code or error bars are provided, and key hyperparameters σ are tuned per example. Therefore the most load-bearing concern is not internal inconsistency but an unproven generalization from a local result to the deployed heuristic. A controlled variant test would settle whether the speed-up is intrinsic to the proposed schedule or an artifact of hyperparameter tuning and approximate solves. This agrees with, and sharpens, the reader's weakest assumption; it does not move the verdict, since the reader already returned CONDITIONAL.","tokens_in":22198,"tokens_out":5325,"duration_ms":66796,"concrete_test":"Run Algorithm 2.2 on Examples 1–5 under three controlled variants: (i) fixed barrier schedule μ=10^-3 halved to 10^-12, (ii) adaptive schedule with σ ∈ {0.2, 0.05, 0.01, 0.005, 0.001}, and (iii) exact direct Newton solves instead of CG/PCG, each with the same one-step-per-component sweep. Report relative Frobenius error versus wall-clock time and, for the density examples, NLL. The concern lands if the speed advantage over Algorithm 2.3 is lost for any σ, if σ must be re-tuned per example to reach 10^-5, or if exact Newton solves change the ranking; otherwise the empirical claim is robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that Algorithm 2.2 fits NTTs drastically faster than the Lee–Seung-type multiplicative update—is supported only empirically, and the theory in §3 does not cover the algorithm actually run. Theorem 3.4 is stated for the single-component subproblem (3.1) at fixed Gk and fixed μ: it proves quadratic convergence only if exact Newton steps are repeated inside that subproblem. Algorithm 2.2 instead visits each component once per sweep, takes one Newton step (with backtracking), solves the Newton system approximately via CG/PCG with Niter=100 (§2.3), and halves μk every outer sweep. There is no lemma showing this one-step-per-visit schedule converges, reaches a stationary point, or preserves the quadratic regime; the authors explicitly characterize the goal as empirical. The density-estimation experiments further depend on the adaptive barrier schedule with per-example centering σ (0.2 for Example 4, 0.005 for Example 5), and the fixed schedule is omitted because it is slower. Thus the headline speed-up could be a property of the tuned adaptive schedule and approximate Newton solves rather than of the proposed alternating-minimization framework. This is a gap between the proven statement and the deployed algorithm, not an internal contradiction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a two-stage algorithm to compress a high-dimensional non-negative tensor P into a non-negative tensor train (NTT) PG. Stage one obtains a TT approximation \\tilde{P} from P either by TT-cross (variational inference) or TT-sketch (density estimation). Stage two fits an NTT by minimizing the squared Frobenius distance to \\tilde{P} with a log-barrier, using alternating minimization with one Newton step per component, accelerated by a block-diagonal Hessian structure, CG/PCG solves, an adaptive barrier update, and a warm start from a few multiplicative updates. The authors prove quadratic convergence for repeated Newton steps on a fixed single-component subproblem via self-concordance, and compare the method against the multiplicative update of Shcherbakova on five examples, reporting faster convergence and accurate density models.","tokens_in":22497,"tokens_out":10113,"duration_ms":119993,"significance":"If the practical claims hold, the paper offers a useful tool for non-negative compression of discrete distributions with linear scaling in dimension, addressing a real limitation of TT-cross/TT-sketch outputs that may contain negative entries. The self-concordance analysis in Section 3 is standard and appears correct for the inner subproblem. Strengths include the use of an external baseline, NLL evaluation in density estimation, and a clear two-stage pipeline that reuses existing TT-cross and TT-sketch subroutines. However, the theoretical guarantee does not cover the one-step-per-visit algorithm actually run, and the empirical evidence is based on single runs with per-example tuned schedule parameters. These issues are fixable but currently leave the central speed/accuracy claim less strongly supported than the presentation suggests.","major_comments":[{"comment":"Theorem 3.4 proves quadratic convergence only for repeated exact Newton steps on the fixed subproblem (3.1) for fixed Gk and fixed μ. Algorithm 2.2 instead takes a single approximate Newton step per component visit and changes μ each outer sweep, and no lemma or theorem shows that this schedule converges to a stationary point or preserves the quadratic regime. The text in §3 acknowledges this implicitly, but the abstract and introduction frame the method as second-order alternating minimization without this caveat. Please add a sweep-level convergence result, or state clearly in the abstract and introduction that convergence guarantees apply only to the inner subproblem and that the global claims are empirical.","section":"§3, Theorem 3.4; §2.2, Algorithm 2.2"},{"comment":"The empirical claims are supported by single runs only: each curve in Figures 1 and 2 corresponds to one trajectory, with no error bars, multiple seeds, or varied initializations. Since the optimization is nonconvex and the adaptive barrier depends on a per-example centering parameter σ (0.2 for Examples 1, 2, and 4; 0.01 for Example 3; 0.005 for Example 5), the reported speed advantage could be specific to the chosen runs and tunings. Please report multiple trials with variability, and include a sensitivity study for σ, or at least state explicitly that the reported behavior is based on single illustrative runs.","section":"§4, Figures 1-2"},{"comment":"The complexity statements that running Algorithm 2.2 has only a time complexity of O(dL) and that the algorithm is O(d) omit the cost of the Newton solves. Equation (2.16) shows that each component update requires solving n independent linear systems of size ρ_{k-1}ρ_k, costing O(n N_iter ρ^3) with CG/PCG; hence a full sweep costs O(d n N_iter ρ^3) up to contraction overhead, not simply O(d). Please restate the complexity in a way that makes the dependence on n, ranks, and N_iter explicit, or define a convention that these parameters are treated as fixed constants.","section":"§2.2, §2.3"},{"comment":"In the density estimation experiments the fixed barrier schedule is omitted because it converges significantly slower than the adaptive schedule, so the comparison in that setting is only between adaptive-schedule variants and the multiplicative baseline. The claimed advantage of Algorithm 2.2 in density estimation is therefore tied to the adaptive heuristic and the tuned σ. The paper should either report fixed-schedule results to quantify this dependence or weaken the corresponding claims so that they are not stated as a property of the proposed framework as a whole.","section":"§4.2"}],"minor_comments":[{"comment":"There is a stray closing parenthesis in the definition of \\tilde{\\mu}_k^i: the expression reads |∇_{G_k}ℓ_0(β_{k−1}, i_k, β_k))| with an extra parenthesis before the absolute value closes.","section":"Eq. (2.17)"},{"comment":"The proof says the backtracking loop multiplies t by β until tλ < 1, but Algorithm 3.1 as stated only tests the Armijo condition. Please justify that an accepted step always satisfies tλ < 1, for example by citing the standard self-concordance fact that the Armijo condition holds for t ≤ 1/(1+λ).","section":"§3, proof of Theorem 3.4, Step 1"},{"comment":"References [3] and [8] contain spurious spaces in author names ('V andenberghe' and 'V anden-Eijnden'); these should be corrected.","section":"References"},{"comment":"The manuscript does not mention code or data availability. A reproducibility statement or a link to an implementation would substantially strengthen the empirical contribution.","section":"Reproducibility"},{"comment":"The sentence 'each iteration over k ∈ [d] has a cost of O(d)' is imprecise: a forward-backward sweep has d component updates, but each update has a nontrivial cost as analyzed in §2.3. Rewording to 'each sweep has O(d) component updates, each costing ...' would avoid confusion.","section":"§2.3"}],"recommendation":"major_revision","confidential_remarks":"This is a promising algorithmic paper, but it is stronger as an empirical study than as a convergence-theory paper. The main risk is that readers of the abstract will attribute a global convergence guarantee to Algorithm 2.2 that is not proved. I recommend requesting a clear reframing of the theorem's scope and a modest strengthening of the experiments. The citation pattern is appropriate: self-citations appear only for background TT-cross/TT-sketch results and do not create circularity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a well-executed engineering paper with a clean local convergence theorem, and the empirical speed-up over the Lee-Seung-style multiplicative baseline looks real. The main soft spot is that the proven theory does not cover the algorithm actually run; the headline claim is empirical. It still deserves a serious referee.\n\nWhat is genuinely new: the two-stage compress-then-fit pipeline already appears in Shcherbakova (2019), but that work used first-order multiplicative updates. Here the NTT fitting is replaced by a log-barrier Newton alternating minimization, with block-diagonal Hessian structure exploited for parallel slice updates, CG/PCG for approximate Newton systems, and an adaptive barrier schedule. The per-sweep O(d) complexity argument is coherent. The self-concordance proof for the single-component subproblem is standard and appears correct; Theorem 3.4 gives quadratic convergence for repeated exact Newton steps at fixed barrier. The numerical comparison against the multiplicative update is consistent across five examples, and the negative-log-likelihood checks in Examples 4 and 5 are a nice honest touch. The citation pattern looks clean; self-citations are used only for background results like TT-cross and TT-sketch.\n\nThe soft spots are proportionate. The main one is exactly what the stress-test note says: Algorithm 2.2 performs one approximate Newton step per component per sweep with a shrinking barrier, but Section 3 proves quadratic convergence only for repeated exact Newton steps on a fixed subproblem. There is no lemma covering the actual schedule. The authors are candid that the goal is empirical, and the abstract says \"in practice we observe,\" but a reader should not come away thinking the theorem justifies the full algorithm. Second, the adaptive barrier schedule uses per-example centering parameters (sigma = 0.2, 0.01, 0.005), and in the density-estimation section the fixed schedule is omitted because it is significantly slower. That makes part of the speed-up a property of the tuned schedule. Third, experiments are single runs with no error bars and no code, so independent reimplementation is needed before relying on the exact numbers. There are also minor label/notation discrepancies, but nothing that changes the conclusions.\n\nWho is this for? People working on non-negative tensor networks, variational inference with tensor trains, and multi-marginal Sinkhorn methods. I would bring it to a reading group and would cite it if I worked in that area. My recommendation: send it to peer review. A good referee should ask for code and multiple runs, and should push the authors to state clearly what is proved versus what is observed.","headline":"Useful engineering paper with real speed-ups, but the proven theory covers only the single-component subproblem and not the alternating schedule actually run; still deserves peer review.","tokens_in":22996,"tokens_out":2076,"would_cite":true,"duration_ms":27430,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C20","15A69","90C51"],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-stage algorithm compresses high-dimensional distributions into non-negative tensor trains, with a Newton-based fitting stage that converges much faster than the previous multiplicative update method.","keywords":["non-negative tensor train","variational inference","density estimation","tensor train cross","tensor train sketching","log barrier","alternating minimization","multiplicative update"],"falsifier":"Take a target that is exactly representable as a non-negative tensor train, such as the $d=30$ Ising distribution, run stage one to near machine accuracy, and run Algorithm 2.2 as stated with one Newton step per component visit. If its relative squared Frobenius error $\\|P_G-P\\|_F^2/\\|P\\|_F^2$ stalls above ten times the stage-one error within 100 sweeps while a variant that repeats Newton steps per component reaches machine accuracy, then the claimed speed of the one-step outer schedule would not be explained by the self-concordance analysis.","tokens_in":1861,"feed_emoji":"🧮","tokens_out":2711,"duration_ms":126578,"temperature":0.7,"pith_summary":"The paper aims to compress a high-dimensional discrete probability tensor into a non-negative tensor train, a product of small non-negative tensors, so that the compressed object can be sampled, scored, and marginalized efficiently. The proposed pipeline works in two stages: first an existing tensor-train routine approximates the target, and then a new fitting routine matches that approximation with a non-negative tensor train by alternating Newton steps with log-barrier regularization. The authors report that this second-order fitting converges much faster and to lower error than the previously proposed multiplicative update method, reaching near-machine accuracy on variational inference examples and matching ground-truth likelihoods in density estimation examples. If the speed holds, non-negative tensor train compression becomes practical enough to use in place of full distribution tensors.","feed_headline":"Newton fitting beats multiplicative updates for non-negative tensor trains","feed_subtitle":"Non-negative tensor train fits reach near machine error on hard distributions and match ground-truth likelihoods.","key_machinery":"The central object is the non-negative tensor train ansatz, a chain of non-negative component tensors $G_1,\\dots,G_d$ whose contraction defines $P_G$. The workhorse is the loss $\\ell(G)=\\|P_G-\\tilde P\\|_F^2 - \\sum_k \\mu_k \\sum \\log G_k$, where the log barrier enforces positivity and the squared Frobenius term is quadratic in each single $G_k$. Updating $G_k$ by one Newton step is cheap because the Hessian block-diagonalizes across the physical index $i_k$, so each slice can be updated in parallel, and the inner linear system is solved by CG or by PCG with the barrier diagonal as preconditioner. An adaptive barrier rule lowers $\\mu_k$ as fast as approximate stationarity allows, and the algorithm is warm-started by a few multiplicative-update sweeps. Theorem 3.4 gives self-concordance-based quadratic convergence for repeated Newton steps inside one fixed-component subproblem, which the paper takes as evidence that inner steps are not the bottleneck.","core_discovery":"The central claim is that the two-stage NTT compression pipeline produces accurate non-negative approximations of high-dimensional discrete distributions, and that the bottleneck stage, fitting an NTT to a TT reference, is solved efficiently by Algorithm 2.2: alternating minimization with a log barrier for positivity and one Newton step per component visit, accelerated by a block-diagonal Hessian, conjugate-gradient or preconditioned-CG inner solves, and an adaptive barrier schedule. On the Ginzburg-Landau, Gibbs kernel, and heavy-tail variational-inference tests, the fit reaches relative squared Frobenius errors around $10^{-7}$ to $10^{-14}$; on the Ising and Heisenberg density-estimation tests, the fitted NTT attains negative log-likelihoods essentially equal to the ground truth, 17.467 versus 17.468 and 12.55 versus 12.53. The same experiments show the multiplicative update benchmark stalling at substantially higher error over the same wall-clock time.","pith_inferences":["The paper proves quadratic convergence for repeated Newton steps inside one fixed-component subproblem, but Algorithm 2.2 runs one Newton step per component visit; transferring the guarantee to the full sweep is an inference, not an established theorem.","The adaptive barrier schedule uses per-example centering parameters ($\\sigma=0.2$, $0.01$, $0.005$), and Section 4.2 notes that the fixed schedule converges significantly slower in density estimation, so applying the method to a new distribution likely requires similar tuning.","Because the second stage can at best recover the stage-one TT, improvements in positivity-aware or otherwise better tensor-train sketching would directly improve final NTT accuracy in the noisy density-estimation regime.","The paper suggests using NTT as the coefficient tensor in a functional tensor train for continuous densities; a direct test would be to replace the dense coefficient tensor with an NTT fit on the same examples."],"forward_implications":["Each full sweep over the $d$ components costs $O(d)$ tensor contractions, so the method compresses distributions in high dimension without ever forming the exponential tensor.","The NTT fitting can introduce essentially no extra error beyond stage one: on the Gibbs kernel example the final entry-wise error matches the stage-one TT error, and on the Ginzburg-Landau example the NTT reaches machine precision.","The resulting NTT model supports efficient sampling, moment estimation, marginal and conditional distributions, and potentially Sinkhorn scaling on the compressed tensor.","In density estimation, the fitted NTT matches the ground-truth negative log-likelihood, meaning the compressed model scores held-out samples as well as the true distribution in the tested cases.","The adaptive-barrier-plus-PCG combination is the most efficient overall, but full Newton can win for small internal ranks, giving practitioners a rank-dependent choice of solver."],"supporting_citations":[{"why":"Supplies the Lee-Seung multiplicative update step that Algorithm 2.3 generalizes to tensor trains and that serves as the benchmark.","marker":"[15]"},{"why":"Provides the previously proposed non-negative tensor train multiplicative-update fitting algorithm used both as benchmark and as warm start.","marker":"[27]"},{"why":"Provides the TT-cross subroutine used in stage one for the variational inference setting.","marker":"[22]"},{"why":"Provides the TT-sketch subroutine used in stage one for the density estimation setting.","marker":"[12]"},{"why":"Gives the asymptotic convergence guarantee for TT-sketch that justifies treating stage one as solved when P has a TT ansatz.","marker":"[30]"},{"why":"Gives the Frobenius-norm error analysis for TT-cross cited for the stage-one guarantee.","marker":"[24]"},{"why":"Provides the adaptive barrier update heuristic that Section 2.3 adapts for choosing $\\mu_k$.","marker":"[20]"},{"why":"Supplies the backtracking line search and self-concordance calculus used in Theorem 3.4.","marker":"[3]"}],"fun_headline_variants":["Newton NTT fits reach 1e-14 error on hard distributions","Two-stage NTT compression: Newton beats multiplicative","Log-barrier Newton accelerates tensor train fitting","NTT fits match truth at 1e-14 with Newton steps","Fast NTT fitting: Newton vs multiplicative update"],"cache_read_input_tokens":25088,"weakest_assumption_plain":"The reported speed and accuracy rest on the empirical convergence of the outer alternating-minimization loop: the paper proves fast convergence only when repeated Newton steps are taken inside one component's update, while the algorithm itself takes one Newton step per component each sweep.","fun_headline_variants_meta":{"raw":{"variants":["Newton NTT fits reach 1e-14 error on hard distributions","Two-stage NTT compression: Newton beats multiplicative","Log-barrier Newton accelerates tensor train fitting","NTT fits match truth at 1e-14 with Newton steps","Fast NTT fitting: Newton vs multiplicative update"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000617,"raw_usage":{"total_tokens":2843,"prompt_tokens":905,"completion_tokens":1938,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":1858}},"tokens_in":521,"tokens_out":1938,"duration_ms":15553,"temperature":1.0,"reasoning_tokens":1858,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T12:39:53.717545+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a target that is exactly representable as a non-negative tensor train, such as the $d=30$ Ising distribution, run stage one to near machine accuracy, and run Algorithm 2.2 as stated with one Newton step per component visit. If its relative squared Frobenius error $\\|P_G-P\\|_F^2/\\|P\\|_F^2$ stalls above ten times the stage-one error within 100 sweeps while a variant that repeats Newton steps per component reaches machine accuracy, then the claimed speed of the one-step outer schedule would not be explained by the self-concordance analysis.","supporting_citations":[{"cited_title":"Lee and H","cited_arxiv_id":null,"evidence_quote":"Supplies the Lee-Seung multiplicative update step that Algorithm 2.3 generalizes to tensor trains and that serves as the benchmark."},{"cited_title":"Shcherbakova, Nonnegative tensor train factorization with dmrg technique, Lobachevskii Journal of Math- ematics, 40 (2019), pp","cited_arxiv_id":null,"evidence_quote":"Provides the previously proposed non-negative tensor train multiplicative-update fitting algorithm used both as benchmark and as warm start."},{"cited_title":"Oseledets and E","cited_arxiv_id":null,"evidence_quote":"Provides the TT-cross subroutine used in stage one for the variational inference setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the TT-sketch subroutine used in stage one for the density estimation setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the asymptotic convergence guarantee for TT-sketch that justifies treating stage one as solved when P has a TT ansatz."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Frobenius-norm error analysis for TT-cross cited for the stage-one guarantee."},{"cited_title":"Nocedal, A","cited_arxiv_id":null,"evidence_quote":"Provides the adaptive barrier update heuristic that Section 2.3 adapts for choosing $\\mu_k$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the backtracking line search and self-concordance calculus used in Theorem 3.4."}],"review_version":1}