REVIEW 4 major objections 6 minor 39 references
Maximal entropy in the moment body
T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Moment-body membership reduces to globally minimizing one smooth strictly convex function, and after Gram-matrix preconditioning a standard quasi-Newton method solves dense $n=m=1000$ instances to $10^{-8}$ in a few seconds.
desk verdict The practical max-entropy recipe and preconditioning are worth knowing, but the strong-convexity lemma that supports the complexity theorem is false, so the paper needs real revision before I would rely on its theoretical claims. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the log-partition function $f(y)=\log\mathrm{tr}\,\exp A(y)-b^T y$, whose gradient is the residual $A(\exp_1 A(y))-b$ and whose Hessian is a covariance-like positive semidefinite form. The argument turns on the diffeomorphism property of the gradient map and on curvature bounds expressed through the Gram matrix $G=[\mathrm{tr}(A_iA_j)]_{i,j}$: the function is $\tfrac12\lambda_{\max}(G)$-smooth and $\lambda_{\min}(G)/(n^2\exp f(y_0))$-strongly convex on sublevel sets. A centering-and-whitening preconditioner forces $G=I_m$, making the dual $\tfrac12$-smooth and $1/n^3$-strongly convex; these constants feed the L-BFGS iteration bound, and the boundary distance $\beta=1-\|b\|_2$ enters the norm bound on the minimizer.
What would settle it
For a random normalized dense instance with $n=m=1000$, run L-BFGS from $y_0=0$ with exact line search and record the iterations needed to reach $\|A(\exp_1 A(y_k))-b\|_2\le 10^{-8}$; the theorem predicts at most about $n^3\log(1/(\epsilon\sqrt{\log n-\log\beta}))$ iterations, so a count orders of magnitude larger, or failure to converge, would falsify the complexity claim.
Extended reading notes
Core claim
The central claim is that the maximum-entropy dual is not just a reformulation but an efficient oracle: the gradient map $y\mapsto A(\exp_1 A(y))$ is a diffeomorphism from $\mathbb{R}^m$ onto the interior of the moment body, so every interior point has a unique entropy-maximizing representing density matrix, and minimizing $f$ finds it. With an exact line search, L-BFGS applied to the preconditioned dual reaches gradient norm $\epsilon$ in at most about $n^3\log(1/(\epsilon\sqrt{\log n-\log\beta}))$ iterations, and each iteration costs $O(n^3+mn^2)$. Consequently dense instances with $n=m=1000$ are solved to $10^{-8}$ in under five seconds, sparse matrix-completion-like instances scale to several thousand in minutes, and the same dual detects weak feasibility and certifies infeasibility from a single iterate.
Load-bearing premise
The paper's promised time bound rests on assuming that L-BFGS with exact line search inherits the linear convergence rate $(1-\alpha/\lambda)^k$ of gradient descent; that step is asserted without proof in Section 7, and if it fails the claimed cubic iteration bound loses its theoretical support.
Editorial extensions
If this is right
- Dense moment-body membership with $n=m=1000$ becomes a routine few-second computation on a laptop at accuracy $10^{-8}$, provided the $m\times n^2$ data can be stored.
- For sparse instances such as matrix completion, the same oracle scales to matrices of size several thousand in minutes, with the main effort shifted to gradient storage and manipulation.
- Weakly feasible boundary points are recognized qualitatively: the gradient never vanishes, iterates drift along a supporting direction, and a norm threshold $\|y_k\|>\sqrt{n}\log(1/\beta)$ certifies that $b$ is not interior.
- If at some iteration $f(y_k)<0$, the normalized vector $y_k/\|y_k\|$ is an explicit separating hyperplane certifying $b\notin M$, so infeasibility is detected without solving a separate problem.
- Because the trace-one structure is what keeps the dual smooth, the same log-partition framework extends to block-separable problems, giving an unconstrained dual with a sum of block traces under the logarithm.
Reading between the lines
- Beyond the paper: the iteration bound is stated for exact line search, but the numerics use practical L-BFGS line searches; a testable extension is to verify whether the same $n^3$-type count holds with inexact Wolfe line search on random instances.
- Beyond the paper: the boundary certificate suggests an adaptive refinement strategy for near-boundary points: once $\|y_k\|$ crosses the threshold, one could project $b$ inward and warm-start, a procedure the paper does not explore.
- Beyond the paper: the observed few-iteration performance on random instances suggests typical curvature is far better than the worst-case $1/n^3$ bound; quantifying that typical-case concentration is an open extension.
- Beyond the paper: the entropic central path sketched in the conclusion, for minimizing a linear function over the moment body, could be tested on small sum-of-squares problems to see whether log-partition smoothness cures the unreliable behavior reported for partition-function regularizations; the paper leaves that test to future work.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses the moment body membership oracle: deciding whether b lies in M = {A(X) : X⪰0, tr X=1}. It proposes to solve the unconstrained minimization of the log-partition function f(y)=log tr exp A(y)-b^T y, whose unique minimizer y* gives X*=exp1 A(y*) with A(X*)=b. Under Assumptions 1-2 the authors prove duality (Theorem 1), smoothness and coercivity (Lemmas 1-2), strict convexity (Lemma 3), and a diffeomorphism between R^m and int M (Lemma 4). A Gram-based preconditioning step (Algorithm 1) orthonormalizes the matrices Ai; the authors then claim f is 1/2-smooth and 1/n^3-strongly convex on sublevel sets (Theorems 3-4), yielding an L-BFGS iteration bound (Theorem 5) and a per-iteration cost analysis (Theorem 6). Numerical experiments report that a rudimentary Matlab implementation solves dense random instances with n=m=1000 to 1e-8 in a few seconds and compares favorably with MOSEK and SDPNAL+.
Significance. The paper's core insight—using the maximum-entropy dual with a log-partition objective and Gram-based preconditioning for moment body membership—is attractive and relevant for quantum state estimation and polynomial optimization. The duality framework is clean, the geometric interpretation is helpful, and the numerical experiments, if reproducible, suggest a practical first-order alternative. The paper also provides a code URL and compares against established solvers, which is commendable. However, the theoretical complexity claims currently rest on a false curvature lemma (Lemma 6) and on an unproved L-BFGS linear-rate assertion (Theorem 5); as a result the advertised 'cubic dependence' is not established. The practical value of the method may survive a corrected analysis, but the manuscript's central theory needs substantial revision.
major comments (4)
- [Section 4, Lemma 6] The claimed strong convexity on sublevel sets is false. The proof asserts the inequality δ≤f(y0)-f(y*) for the spectral gap δ(y)=λmax(A(y))-λmin(A(y)); this does not follow from 'f increases with the spectral gap' and is in fact false. Counterexample: take n=2, m=1, A1=diag(1,-1)/√2, b=0. Then f(y)=log(2cosh(y/√2)), the sublevel set S={f≤f(y0)} is [-y0,y0], and min_S f''=f''(y0)=(1/2)sech^2(y0/√2) ~ 2 exp(-√2 y0). Lemma 6 predicts α=λmin(G)/(n^2 exp f(y0)) ~ (1/8)exp(-y0/√2). At y0=10 the predicted α is about 1e-4 while the actual Hessian lower bound is about 1.4e-6. Thus Theorem 4's 1/n^3 strong-convexity modulus and the α substituted into Theorem 5 do not follow.
- [Section 7, Theorem 5] The theorem assumes that L-BFGS iterates with exact line search inherit the gradient-descent linear rate (1-α/λ)^k. No proof is given, and this is not a standard property of limited-memory BFGS with bounded memory. The citation to Nocedal and Wright, Chapter 8, supports local superlinear convergence and global convergence under convexity, not a global linear rate with explicit constant 1-c/(κ m_hist) as stated in Section 4. The proof of Theorem 5 is exactly the gradient-descent proof with α taken from Theorem 4, so the iteration bound is unsupported even if Lemma 6 were repaired. The theorem must either be replaced by a rigorous L-BFGS complexity analysis or the complexity claims must be downgraded to heuristics.
- [Abstract and Theorems 5-6] The advertised cubic dependence is not supported by the stated bounds. Theorem 5 gives k=O(n^3) iterations for y0=0, and Theorem 6 gives O(n^3+mn^2) per iteration, so the worst-case total is O(n^6+m n^5), i.e. O(n^6) when n=m, not O(n^3). If the intended claim is that each iteration costs O(n^3) and that the observed iteration count is constant, that is an empirical observation, not a 'detailed complexity analysis'. This internal inconsistency should be resolved in the revision.
- [Sections 5 and 10] Algorithm 1 transforms only the matrices Ai; the paper never states the corresponding affine transformation of the query point b that preserves membership in the original moment body. Replacing Ai by the orthonormalized matrices changes M, so for arbitrary input (A,b) the algorithm as stated does not test b∈M unless b is also transformed, e.g. b ↦ C(b - A(I/n)) in the centered coordinates. The numerical experiments avoid this issue by generating b after preconditioning, but Section 3's oracle claim applies to a given b. This needs to be stated explicitly and, ideally, implemented in the code.
minor comments (6)
- [Throughout] The manuscript contains several typos, including 'versatily' in Section 1, 'againt' in Section 10, and 'semdefinite' in the conclusion; these should be corrected.
- [Section 3, Lemma 3] The notation 'f* = arg min_{y∈R^m} f(y)' is misleading: f* should denote the value and y* the minimizer. The proof text 'unique global minimizer f*' should be adjusted.
- [Section 8, Corollary 2] The argument uses Lemma 9, which bounds the minimizer y*, to conclude that the sublevel set lies in a ball; Lemma 9 as stated does not bound all sublevel iterates. Either prove the sublevel bound or label the test as heuristic.
- [Section 10] The experimental section should report hardware details, the number of random instances, the variance of timings, and the exact solver tolerances used for MOSEK and SDPNAL+; a single run on one 'standard laptop' is not sufficient to support the timing claims.
- [Abstract and Section 10] The abstract mentions sparse matrix completion problems scaling to several thousand and dense projections to several hundred, but Section 10 contains only dense random instances with n=m=1000. Either add the sparse experiments or align the abstract with the actual content.
- [Section 4, Lemma 10] The displayed derivation '0 = ∑λ_i =≥ λmax + (n−1)λmin' contains a typographical artifact; the inequality should be written cleanly.
Circularity Check
No circular reduction found: the membership/minimization duality and preconditioning chain are self-contained, with only non-load-bearing self-citations.
full rationale
The central derivation is self-contained. Membership in the moment body is linked to the convex problem min_y f(y) through Lemmas 1-3 and Theorem 1, which use only matrix calculus, Cauchy-Schwarz, strict convexity, coercivity, and Lagrangian duality; nothing is fitted to the target vector b. The membership certificate X(y*) = exp1(A(y*)) follows from the first-order condition grad f(y*) = A(X(y*)) - b = 0, so the output is not equal to the input by construction. Preconditioning (Algorithm 1, Theorem 2) uses only the Gram matrix G' of the centered input matrices and is not calibrated to b or to the feasibility answer. The curvature bounds (Lemmas 5-6, Theorems 3-4) are expressed in terms of the spectrum of G and of f(y0), i.e. input data and the initial point, not fitted to the answer. Numerical experiments generate b = A(X) from a random feasible X, which is a benchmark with a known feasible point rather than a fitted prediction, and the solver is compared against the external solvers MOSEK and SDPNAL+. The self-citations to [11, 12, 18, 19] are historical remarks about projection/BFGS ideas, not load-bearing justifications of the paper's main claims, and the diffeomorphism result of Lemma 4 is attributed to the external references [14, 34]. The reviewer-identified weaknesses of this paper are mathematical-correctness risks, not circularity: the proof of Theorem 5 asserts that L-BFGS with exact line search inherits the gradient-descent linear rate ('a standard result (e.g. for gradient descent with step 1/lambda)'), and the strong-convexity modulus in Lemma 6 has been questioned on a 2x2 example. These would affect the validity of the complexity estimate, but they do not make the claimed result equivalent to its inputs or rename a fitted parameter as a prediction. Accordingly, no circular step meets the evidentiary bar, so the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption I_n, A_1, ..., A_m are linearly independent (Assumption 1).
- domain assumption b belongs to the interior of M (Assumption 2) for the main convergence analysis.
- ad hoc to paper The Hessian of log tr exp X is bounded below by p_min(X) I_n (Lemma 6).
- ad hoc to paper L-BFGS iterates with exact line search inherit the linear rate (1-alpha/lambda)^k of gradient descent (Theorem 5).
- standard math Known quantum-information duality and diffeomorphism results (Wichmann 1963; Jarov and Van Raamsdonk 2023).
Cite this review
Pith. "Pith review of Maximal entropy in the moment body." pith.science (2026). https://pith.science/paper/UODKYRTI
@misc{pith2026250702461,
author = {Pith},
title = {Pith review of: Maximal entropy in the moment body},
year = {2026},
howpublished = {\url{https://pith.science/paper/UODKYRTI}},
note = {Machine review of arXiv:2507.02461}
}
read the original abstract
A moment body is a linear projection of the spectraplex, the convex set of trace-one positive semidefinite matrices. Determining whether a given point lies within a given moment body is a problem with numerous applications in quantum state estimation and polynomial optimization. This moment body membership oracle can be addressed with semidefinite programming, for which several off-the-shelf interior-point solvers are available. In this paper, inspired by techniques from quantum information theory, we argue analytically and geometrically that a much more efficient approach consists of minimizing globally a smooth strictly convex log-partition function, dual to a maximum entropy problem. We analyze the curvature properties of this function, showing that conditioning is governed by the distance of the point to the boundary of the moment body, and we describe a neat geometric preconditioning algorithm that exploits this analysis. Basic numerical experiments, comparing against interior-point and first-order semidefinite solvers, reveal a cubic dependence on the matrix size, similar to a few eigenstructure computations. They also illustrate the two regimes of the oracle: dense projections are handled efficiently up to sizes of several hundred, while sparse instances such as matrix completion scale to matrices of size several thousand in minutes on a standard laptop. In both cases the main bottleneck in this approach to large-scale semidefinite programming is moved almost entirely to efficient gradient storage and manipulation.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
- [1]
-
[2]
I. Bengtsson, K. ˙Zyczkowski. Geometry of quantum states. Cambridge University Press, 2nd edition, 2017
work page 2017
-
[3]
A. Ben-Tal, A. Nemirovski. Lectures on modern convex optimization: analysis, algo- rithms, and engineering applications. SIAM, 2001
work page 2001
- [4]
-
[5]
S. Boyd and L. Vandenberghe. Convex optimization. Cambridge Univ. Press, 2004
work page 2004
-
[6]
S. P. Chhatoi, J. B. Lasserre. Shannon- and von Neumann-entropy regularizations of linear and semidefinite programs. arXiv:2503.23815, 2025
work page Pith review arXiv 2025
-
[7]
M. M. Davis, D. Papp. Dual certificates and efficient rational sum-of-squares decompo- sitions for polynomial optimization over compact sets. SIAM J. Optim. 32(4):2461-2492, 2022
work page 2022
-
[8]
C. Helmberg, F. Rendl. A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696, 2000
work page 2000
Show all 39 references
-
[9]
D. Henrion. Semidefinite geometry of the numerical range. Elec. J. Lin. Alg. 20:322-332, 2010
2010
-
[10]
Henrion, M
D. Henrion, M. Korda, J. B. Lasserre. The moment-SOS hierarchy. World Scientific, 2020
2020
-
[11]
Henrion, J
D. Henrion, J. Malick. Projection methods for conic feasibility problems, applications to polynomial sum-of-squares decompositions, Optim. Methods and Software, Vol. 26, No. 1, pp. 23-46, 2011
2011
-
[12]
Henrion, J
D. Henrion, J. Malick. Projection methods in convex optimization. In M. Anjos and J. B. Lasserre (Editors). Handbook of semidefinite, cone and polynomial optimization. Springer, 2012
2012
-
[13]
S.-Y. Hou, Z. Wu, J. Zeng, N. Cao, C. Cao, Y. Li, B. Zeng. Maximum entropy methods for quantum state compatibility problems. Adv. Quantum Technol. 2400172, 2024
2024
-
[14]
Jarov, M
S. Jarov, M. Van Raamsbonk. Mapping the space of quantum expectation values. arXiv:2310.13111, 2023
2023 arXiv
-
[15]
M. Lindsey. Fast randomized entropically regularized semidefinite programming. arXiv:2303.12133, 2023
2023 arXiv
-
[16]
N. H. A. Mai, J. B. Lasserre, V. Magron. A hierarchy of spectral relaxations for poly- nomial optimization. Math. Prog. Comp. 15:651–701, 2023
2023
-
[17]
N. H. A. Mai, J. B. Lasserre, V. Magron, J. Wang. Exploiting constant trace property in large-scale polynomial optimization. ACM Trans. Math. Software 48(4):1-39, 2022
2022
-
[18]
J. Malick. A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. Vol. 26, No. 1, pp. 272-284, 2004. 29
2004
-
[19]
Malick, J
J. Malick, J. Povh, F. Rendl, and A. Wiegele. Regularization methods for semidefinite programming. SIAM J. Optim 20(1):336–356, 2009
2009
-
[20]
R. D. C. Monteiro, A. Sujanani, D. Cifuentes. A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. arXiv:2401.12490, 2024
2024 arXiv
-
[21]
J. Nie. Moment and polynomial optimization, SIAM, 2023
2023
-
[22]
Ni˜ no-Cortes, C
J. Ni˜ no-Cortes, C. Vinzant. The convex algebraic geometry of higher-rank numerical ranges. arXiv:2410.21625, 2024
2024 arXiv
-
[23]
Nesterov
Y. Nesterov. Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, 2004
2004
-
[24]
Nesterov, A
Y. Nesterov, A. Nemirovskii. Interior-point polynomial algorithms in convex program- ming. SIAM, 1994
1994
-
[25]
Nocedal and S
J. Nocedal and S. J. Wright. Numerical optimization, 2nd edition. Springer, 2006
2006
-
[26]
M. L. Overton. HANSO: Hybrid Algorithm for Non-Smooth Optimization (Version 3.0) [Software], 2021
2021
-
[27]
G. Pataki. Characterizing bad semidefinite programs: normal forms and short proofs. SIAM Review 61(4):839-859, 2019
2019
-
[28]
Pavlov, B
D. Pavlov, B. Sturmfels, S. Telen. Gibbs manifolds. Information Geometry 7:691–71, 2024
2024
-
[29]
Plaumann, R
D. Plaumann, R. Sinn, S. Weis. Kippenhahn’s theorem for joint numerical ranges and quantum states. SIAM J. Appl. Alg. Geom. 5(1):86-113, 2021
2021
-
[30]
J. Renegar. Linear programming, complexity theory and elementary functional analysis. Math. Prog. 70:279-351, 1995
1995
-
[31]
D. F. Sun, K. C. Toh, Y. C. Yuan, X. Y. Zhao, SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0), Optim. Methods and Software, 35:87–115, 2020
2020
-
[32]
Theobald
T. Theobald. Real algebraic geometry and optimization. AMS, 2024
2024
-
[33]
S. Weis. Information topologies on non-commutative state spaces. J. Convex Anal. 21(2):339–399, 2014
2014
-
[34]
E. H. Wichmann. Density matrices arising from incomplete measurements. J. Math. Phys. 4:884–896, 1963
1963
-
[35]
S. J. Wright. Primal–Dual Interior-Point Methods. SIAM, 1997
1997
-
[36]
L. Q. Yang, D. F. Sun, K. C. Toh. SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative con- straints, Math. Prog. Comp. 7:331-366, 2015. 30
2015
-
[37]
Yurtsever, J
A. Yurtsever, J. A. Tropp, O. Fercoq, M. Udell, V. Cevher. Scalable semidefinite pro- gramming. SIAM J. Math. Data Sci. 3(1), 2021
2021
-
[38]
R. M. Wilcox. Exponential operators and parameter differentiation in quantum physics. J. Math. Phys. 8(4):962-982, 1967. 31
1967
-
[2000]
Translated from the Japanese original of 1993. 28
1993
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.