Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Variational inference and density estimation with non-negative tensor train

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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.

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

arxiv 2507.21519 v1 pith:D5CLGPVH submitted 2025-07-29 math.NA cs.NA

Xun Tang , Rajat Dwaraknath , Lexing Ying This is my paper · ORCID
classification math.NAcs.NA MSC 65C2015A6990C51
keywords non-negativetensortrainvariationalinferencedensityestimationcrosssketchinglogbarrieralternatingminimizationmultiplicativeupdate
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [§3, Theorem 3.4; §2.2, Algorithm 2.2] 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.
  2. [§4, Figures 1-2] 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.
  3. [§2.2, §2.3] 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.
  4. [§4.2] 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.
minor comments (5)
  1. [Eq. (2.17)] 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.
  2. [§3, proof of Theorem 3.4, Step 1] 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+λ).
  3. [References] References [3] and [8] contain spurious spaces in author names ('V andenberghe' and 'V anden-Eijnden'); these should be corrected.
  4. [Reproducibility] The manuscript does not mention code or data availability. A reproducibility statement or a link to an implementation would substantially strengthen the empirical contribution.
  5. [§2.3] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the two-stage pipeline is validated against independently defined ground truth and an external baseline.

full rationale

The derivation chain is self-contained. Stage one obtains a TT approximation tilde-P from P via TT-cross (variational inference) or TT-sketch (density estimation), with convergence guarantees cited from external works [24] as well as the authors' own [30]; stage two fits a non-negative TT PG by minimizing ||PG - tilde-P||_F^2 plus log barriers (Eq. 2.15). All reported successes are checked against the original P via relative Frobenius error and negative log-likelihood, not against the fitted objective alone, so no fitted parameter defines the comparison target. Theorem 3.4 is a standard self-concordance Newton convergence proof for the fixed-component subproblem; the observation that Algorithm 2.2 takes only one Newton step per component is a gap between the proven statement and the deployed algorithm, not a definitional equivalence. Self-citations [30]-[32] supply background sketching and error-analysis results and are not used to define the NTT output or the benchmark; the speed-up claim is compared with an external multiplicative update from [27]. Thus no equation is identical to its input by construction and no circularity score above 1 is warranted.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central algorithm depends on standard convex analysis, on the domain assumption that the target distribution is well-approximated by a TT and then by an NTT with inflated rank, and on two heuristic components: the absolute-value adaptive barrier update and the warm initialization via an unspecified number of multiplicative updates. No invented entities are introduced. The main free parameters are the barrier centering parameter sigma, the initial barrier coefficient and schedule, the chosen NTT ranks, the CG iteration cap, and the warm-start length.

free parameters (5)
  • Adaptive barrier centering parameter sigma = 0.2 (Examples 1,2,4), 0.01 (Example 3), 0.005 (Example 5)
    Per-example tuned value in the adaptive barrier update formula (2.17); the paper calls it fixed but varies it across experiments.
  • Initial barrier coefficient mu and decay schedule = mu=1e-3, halved to 1e-12 (fixed schedule)
    Chosen by hand; the adaptive schedule replaces this in density estimation, and the fixed schedule is reported as significantly slower there.
  • NTT internal ranks rho = 20, 25, 20, 10, 20 across the five examples
    Chosen per example to exceed the TT rank r; directly controls achievable approximation accuracy.
  • CG iteration cap Niter and PCG switch threshold = Niter=100, threshold mu=1e-8
    Algorithmic settings chosen by hand to balance accuracy and speed in solving the Newton system (2.16).
  • Number of warm-up multiplicative update iterations = A few (unspecified)
    Section 2.3 says 'a few iterations' of Algorithm 2.3 are used for initialization; the exact count is not given.
assumptions (5)
  • standard math Self-concordance of the log barrier and standard Newton analysis for convex composite objectives.
    Invoked in Section 3.1 and Theorem 3.4, relying on standard results from Boyd and Vandenberghe and Nesterov and Nemirovskii.
  • domain assumption The ground-truth distribution P is well-approximated by a tensor train, and the stage-one outputs (TT-cross or TT-sketch) are close to P.
    Section 2.1 relies on recovery guarantees from [24] and [30]; when this fails, the two-stage pipeline inherits the stage-one error.
  • domain assumption The NTT ansatz with inflated rank rho >= r can accurately represent the stage-one TT approximation.
    Section 2.2 states 'we typically choose rho_k >= r_k to account for the fact that NTT has less representational power than TT'; no a priori guarantee is provided.
  • ad hoc to paper The adaptive barrier update rule with absolute value in Equation (2.17) is a valid heuristic for choosing mu_k.
    Section 2.3 modifies the heuristic from [20] by adding absolute values; no convergence guarantee is given for this modified rule.
  • ad hoc to paper Warm initialization via a few multiplicative updates plus rescaling produces a suitable starting point for the Newton sweeps.
    Section 2.3 describes this heuristic without analysis; the success of the full algorithm depends on it empirically.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Variational inference and density estimation with non-negative tensor train." pith.science (2026). https://pith.science/paper/D5CLGPVH

@misc{pith2026250721519,
  author       = {Pith},
  title        = {Pith review of: Variational inference and density estimation with non-negative tensor train},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D5CLGPVH}},
  note         = {Machine review of arXiv:2507.21519}
}
read the original abstract

This work proposes an efficient numerical approach for compressing a high-dimensional discrete distribution function into a non-negative tensor train (NTT) format. The two settings we consider are variational inference and density estimation, whereby one has access to either the unnormalized analytic formula of the distribution or the samples generated from the distribution. In particular, the compression is done through a two-stage approach. In the first stage, we use existing subroutines to encode the distribution function in a tensor train format. In the second stage, we use an NTT ansatz to fit the obtained tensor train. For the NTT fitting procedure, we use a log barrier term to ensure the positivity of each tensor component, and then utilize a second-order alternating minimization scheme to accelerate convergence. In practice, we observe that the proposed NTT fitting procedure exhibits drastically faster convergence than an alternative multiplicative update method that has been previously proposed. Through challenging numerical experiments, we show that our approach can accurately compress target distribution functions.

Figures

Figures reproduced from arXiv: 2507.21519 by the authors.

Figure 1
Figure 1. Numerical results for NTT fitting in the variational inference setting. The plot compares [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Numerical results for NTT fitting in the density estimation setting. The details can be [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Nonnegative Low-Rank Matrix Correction under an Orthogonality Constraint in Conservative Vlasov Simulations

    math.NA 2026-07 conditional novelty 6.0 of 10

    A constrained nuclear-norm correction with an implicit singular-value threshold restores nonnegativity in low-rank Vlasov solutions without changing conserved moments.

Reference graph

Works this paper leans on

36 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [1]

    M. W. Berry, M. Browne, A. N. Langville, V. P. Pauca, and R. J. Plemmons, Algorithms and appli- cations for approximate nonnegative matrix factorization , Computational statistics & data analysis, 52 (2007), pp. 155–173

    work page 2007

  2. [2]

    D. M. Blei, A. Kucukelbir, and J. D. McAuliffe, Variational inference: A review for statisticians, Journal of the American statistical Association, 112 (2017), pp. 859–877

    work page 2017

  3. [3]

    S. P. Boyd and L. V andenberghe, Convex optimization , Cambridge university press, 2004

    work page 2004

  4. [4]

    Chen and Y

    Y. Chen and Y. Khoo, Combining particle and tensor-network methods for partial differential equations via sketching, arXiv preprint arXiv:2305.17884, (2023)

    work page arXiv 2023

  5. [5]

    Cichocki, S

    A. Cichocki, S. Cruces, and S.-i. Amari, Generalized alpha-beta divergences and their application to robust nonnegative matrix factorization , Entropy, 13 (2011), pp. 134–170

    work page 2011

  6. [6]

    Cichocki, H

    A. Cichocki, H. Lee, Y.-D. Kim, and S. Choi, Non-negative matrix factorization with α-divergence, Pattern Recognition Letters, 29 (2008), pp. 1433–1440

    work page 2008

  7. [7]

    Donoho and V

    D. Donoho and V. Stodden, When does non-negative matrix factorization give a correct decomposition into parts?, Advances in neural information processing systems, 16 (2003)

    work page 2003

  8. [8]

    W. E, W. Ren, and E. V anden-Eijnden, Minimum action method for the study of rare events , Communi- cations on pure and applied mathematics, 57 (2004), pp. 637–656

    work page 2004

Show all 36 references
  1. [9]

    Forsgren, P

    A. Forsgren, P. E. Gill, and M. H. Wright, Interior methods for nonlinear optimization , SIAM review, 44 (2002), pp. 525–597

    2002

  2. [10]

    V. L. Ginzburg, V. L. Ginzburg, and L. Landau, On the theory of superconductivity , Springer, 2009

    2009

  3. [11]

    G. H. Golub and C. F. V an Loan, Matrix computations, JHU press, 2013

    2013

  4. [12]

    Y. Hur, J. G. Hoskins, M. Lindsey, E. M. Stoudenmire, and Y. Khoo, Generative modeling via tensor train sketching, Applied and Computational Harmonic Analysis, 67 (2023), p. 101575

    2023

  5. [13]

    M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, An introduction to variational methods for graphical models, Machine learning, 37 (1999), pp. 183–233

    1999

  6. [14]

    D. Kim, S. Sra, and I. S. Dhillon, Fast newton-type methods for the least squares nonnegative matrix approximation problem, in Proceedings of the 2007 SIAM international conference on data mining, SIAM, 2007, pp. 343–354

    2007

  7. [15]

    Lee and H

    D. Lee and H. S. Seung, Algorithms for non-negative matrix factorization , Advances in neural information processing systems, 13 (2000)

    2000

  8. [16]

    D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization , nature, 401 (1999), pp. 788–791

    1999

  9. [17]

    Liu, Monte Carlo strategies in scientific computing , vol

    J. Liu, Monte Carlo strategies in scientific computing , vol. 75, Springer, 2001

    2001

  10. [18]

    S. D. Marino and A. Gerolin, An optimal transport approach for the schr¨ odinger bridge problem and convergence of sinkhorn algorithm , Journal of Scientific Computing, 85 (2020), p. 27

    2020

  11. [19]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming , SIAM, 1994

    1994

  12. [20]

    Nocedal, A

    J. Nocedal, A. W¨achter, and R. A. W altz, Adaptive barrier update strategies for nonlinear interior methods, SIAM Journal on Optimization, 19 (2009), pp. 1674–1693

    2009

  13. [21]

    Nocedal and S

    J. Nocedal and S. J. Wright, Numerical optimization, Springer, 1999

    1999

  14. [22]

    Oseledets and E

    I. Oseledets and E. Tyrtyshnikov, Tt-cross approximation for multidimensional arrays , Linear Algebra and its Applications, 432 (2010), pp. 70–88

    2010

  15. [23]

    I. V. Oseledets, Tensor-train decomposition, SIAM Journal on Scientific Computing, 33 (2011), pp. 2295– 2317

    2011

  16. [24]

    Z. Qin, A. Lidiak, Z. Gong, G. Tang, M. B. W akin, and Z. Zhu, Error analysis of tensor-train cross approximation, Advances in Neural Information Processing Systems, 35 (2022), pp. 14236–14249

    2022

  17. [25]

    Savostyanov and I

    D. Savostyanov and I. Oseledets, Fast adaptive interpolation of multi-dimensional arrays in tensor train format, in The 2011 International Workshop on Multidimensional (nD) Systems, IEEE, 2011, pp. 1–8

    2011

  18. [26]

    Schneider and A

    R. Schneider and A. Uschmajew, Approximation rates for the hierarchical tensor format in periodic sobolev spaces, Journal of Complexity, 30 (2014), pp. 56–71

    2014

  19. [27]

    Shcherbakova, Nonnegative tensor train factorization with dmrg technique, Lobachevskii Journal of Math- ematics, 40 (2019), pp

    E. Shcherbakova, Nonnegative tensor train factorization with dmrg technique, Lobachevskii Journal of Math- ematics, 40 (2019), pp. 1863–1872

    2019

  20. [28]

    B. W. Silverman, Density estimation for statistics and data analysis , Routledge, 2018

    2018

  21. [29]

    Tang, Tensor network methods for scientific computing , phd thesis, Stanford University, Stanford, CA, March 2025

    X. Tang, Tensor network methods for scientific computing , phd thesis, Stanford University, Stanford, CA, March 2025. Available at https://purl.stanford.edu/np304kb7547. 22 X. TANG, R. DW ARAKNATH, L. YING

    2025

  22. [30]

    X. Tang, Y. Hur, Y. Khoo, and L. Ying, Generative modeling via tree tensor network states , Research in the Mathematical Sciences, 10 (2023), p. 19

    2023

  23. [31]

    X. Tang, Y. Khoo, and L. Ying, Initialization and training of matrix product state probabilistic models , arXiv preprint arXiv:2505.06419, (2025)

    2025 arXiv

  24. [32]

    Tang and L

    X. Tang and L. Ying, Wavelet-based density sketching with functional hierarchical tensor , arXiv preprint arXiv:2502.20655, (2025)

    2025 arXiv

  25. [33]

    S. A. V avasis, On the complexity of nonnegative matrix factorization , SIAM journal on optimization, 20 (2010), pp. 1364–1377

    2010

  26. [34]

    W ang and Y.-J

    Y.-X. W ang and Y.-J. Zhang, Nonnegative matrix factorization: A comprehensive review , IEEE Transac- tions on knowledge and data engineering, 25 (2012), pp. 1336–1353

    2012

  27. [35]

    S. R. White, Density matrix formulation for quantum renormalization groups , Physical review letters, 69 (1992), p. 2863

    1992

  28. [36]

    Zdunek and A

    R. Zdunek and A. Cichocki, Nonnegative matrix factorization with constrained second-order optimization , Signal Processing, 87 (2007), pp. 1904–1916

    2007

Pith tools

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