Pith. sign in

REVIEW 3 major objections 7 minor 47 references

Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming

T0 review · 3 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Entropic regularization plus a problem-adapted norm lets dual gradient ascent converge at a dimension-independent rate, with concrete guarantees for Max-Cut, optimal transport, and permutation synchronization.

desk verdict The deterministic core and OT analysis are genuinely valuable, but the stochastic SDP claims ride on an unpublished companion and one apparent mismatch in the strong Perm-Synch update, so treat the advertised O~(ε^{-3}) complexities as conditional. read the letter →

arxiv 2506.09711 v2 pith:YA2RGAPY submitted 2025-06-11 math.OC cs.NAmath.NA

Yuhang Cai , Michael Lindsey This is my paper · ORCID
classification math.OCcs.NAmath.NA MSC 90C2290C2590C0665K05
keywords semidefiniteprogrammingentropicregularizationvonNeumannentropydualgradientascentrandomizedtraceestimationoptimaltransportMax-CutSDPpermutationsynchronization
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

Entropic regularization is a known workhorse, but this paper shows it can power a general solver: add the von Neumann entropy to a primal SDP, dualize the affine constraints, and run gradient ascent in a norm chosen from the constraint structure. The main theorem bounds the dual gradient norm after $T$ steps by roughly $3\gamma + 2\sqrt{\beta\Delta_e(C)/T} + 2\sqrt{\log n/T}$, independent of the matrix dimension except for the logarithmic term. Combined with rounding lemmas, this yields $\tilde{O}(\varepsilon^{-3})$ iterations for the Max-Cut and strong permutation-synchronization SDPs, with $\tilde{O}(\varepsilon^{-2})$ randomized samples per iteration, and for optimal transport it recovers Sinkhorn-level complexity $O((M/\varepsilon)^2 m n \log(mn))$. The paper also proves a stochastic-gradient objective bound that decays exponentially up to a bias set by the gradient error. A reader should care because these are dimension-independent, near-optimal scaling guarantees for several SDPs that do not assume low-rank solutions.

What carries the argument

The load-bearing object is the von Neumann entropy $S(X)=\mathrm{Tr}[X\log X]$ used as a regularizer, together with the problem-adapted dual norm $\|\cdot\|$ satisfying Assumption 6, namely $\|\lambda\cdot A\|_2 \le \|\lambda\|$. Entropy's $1$-strong convexity in nuclear norm (Theorem 4) makes the convex conjugate $S^*$ $1$-strongly smooth in spectral norm, which makes the dual free energy $\beta^{-1}\log\mathrm{Tr}\,e^{-\beta(C-\lambda\cdot A)}$ $\beta$-smooth in $\|\cdot\|$; this smoothness is what the convergence theorems use. The gradient is the primal feasibility gap $\mathrm{Tr}[A X_{\beta,\lambda}]-b$, estimated stochastically by randomized trace estimation. The non-Euclidean update is the prox of the chosen norm, and the rounding lemmas (Lemma 28 for Max-Cut, Lemma 31 for strong Perm-Synch) are what convert gradient convergence into primal-feasible objective bounds.

What would settle it

Check the three imported concentration lemmas directly: run the randomized trace estimator with $S=C\log(n/\delta)/\varepsilon^2$ on a matrix exponential whose eigenvalues are spread across many scales, and see whether the claimed entrywise multiplicative bounds (Lemmas 10, 12, 14) hold. If a matrix with large condition number breaks the bound, the sample complexity $S=\tilde{O}(\gamma^{-2})$ collapses and the stochastic dimension-independent convergence for the Max-Cut and Perm-Synch SDPs does not follow; alternatively, fix a target $\varepsilon$ and verify empirically that the number of iterations and samples needed to reach it stays independent of $n$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the convex-conjugate relationship between entropy and free energy makes a whole class of entropically regularized SDPs amenable to one algorithm: gradient ascent on the dual, measured in a norm that satisfies $\|\lambda\cdot A\|_2 \le \|\lambda\|$. The primal candidate is always the Gibbs state $X_{\beta,\lambda}\propto e^{-\beta(C-\lambda\cdot A)}$, whose feasibility gap equals the dual gradient. Because $S(X)=\mathrm{Tr}[X\log X]$ is $1$-strongly convex in nuclear norm, the dual objective is $\beta$-smooth in the chosen norm, so the prox update has a closed form that is cheap to compute. Randomized trace estimation supplies gradients without forming matrix exponentials, and rounding arguments, one lemma for Max-Cut and one for the strong Perm-Synch SDP, turn an approximately feasible Gibbs state into a truly feasible point with controlled objective loss. The consequence is that the dual gradient norm converges to zero independently of $n$, and the primal objective approximates the unregularized optimum with additive error $\varepsilon$ using $\tilde{O}(\varepsilon^{-3})$ iterations for the two SDP families and Sinkhorn-comparable complexity for optimal transport.

Load-bearing premise

The dimension-independent stochastic convergence for the SDP cases rests on the assumption that the randomized trace estimator has error at most $\gamma$, justified by concentration lemmas imported from an unpublished companion manuscript; the objective-convergence theorems additionally require an a priori bound $D$ on the distance to a dual optimizer, which is proved only in the optimal transport case.

Editorial extensions

If this is right

  • The Max-Cut Goemans-Williamson SDP can be approximated to additive $\varepsilon$ in $\tilde{O}(\varepsilon^{-3})$ iterations with $\tilde{O}(\varepsilon^{-2})$ samples per iteration, with only logarithmic dependence on the number of vertices and no low-rank assumption.
  • The entropically regularized optimal transport problem is solved in $O((M/\varepsilon)^2 m n \log(mn))$ operations, matching Sinkhorn scaling, while the method remains open to extra linear constraints.
  • The strong Perm-Synch SDP gets the first near-optimal-scaling algorithm: $\tilde{O}(\varepsilon^{-3})$ iterations and $\tilde{O}(\varepsilon^{-2})$ samples per iteration when the block degree and block size are constant.
  • For any SDP within the framework, Theorem 16 guarantees that after $T$ iterations some iterate has dual-gradient norm $O(\gamma+\sqrt{\beta\Delta_e(C)/T}+\sqrt{\log n/T})$, so near-feasibility is achieved without ever forming the full $n\times n$ primal matrix.
  • For stochastic gradient ascent on a smooth objective with respect to a general norm, the objective error decays exponentially down to a bias proportional to the gradient error $\gamma$, with rate depending on $\gamma$ and $D$.

Reading between the lines

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

  • The norm-selection recipe could be lifted to other SDPs: whenever constraints admit an operator-norm bound of Assumption 6, the same prox update and gradient-convergence proof apply, so the framework is likely to work for other combinatorial SDP relaxations such as Lovász theta or graph coloring.
  • Because the OT objective bound holds for every inverse temperature $\beta$, the algorithm can be run as a continuation schedule with $\beta$ increasing over time to approach the unregularized optimum; the paper does not explore this, but the general-$\beta$ theorem suggests it.
  • The SDP sample complexities stand on the three concentration lemmas imported from the companion manuscript. A reader should treat those lemmas as the checkable bottleneck: if a counterexample to Lemmas 10 or 12 exists, the sample counts would need revision, while the deterministic convergence theorem might still hold with exact gradients.
  • Numerically, the experiments in the paper fix $\beta$ while growing $n$; an easy extension is to fix the target $\varepsilon$ and record the observed iteration and sample counts, which would directly test whether the $\tilde{O}(\varepsilon^{-3})$ and $\tilde{O}(\varepsilon^{-2})$ scalings hold in practice.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 7 minor

Summary. The paper develops a non-Euclidean dual gradient ascent framework for entropically regularized semidefinite and linear programs. The authors dualize the affine constraints, leave the trace constraint in the primal domain, and show that the dual objective is strongly smooth with respect to a problem-adapted norm. They provide deterministic convergence bounds for the dual gradient norm (Theorem 16), objective convergence bounds under an a priori diameter bound D (Theorems 18 and 20), and a refined objective analysis for optimal transport (Theorems 22 and 24). For the Max-Cut SDP and the strong Perm-Synch SDP they give rounding arguments that convert approximate primal feasibility into objective error bounds (Theorems 29 and 32). For stochastic gradients, the paper claims near-linear dimension-independent sample complexity via randomized trace estimators, with the stochastic error controlled by Assumption 9 and validated by Lemmas 10, 12, and 14 reproduced from the unpublished companion manuscript [29]. The paper concludes with numerical experiments on Max-Cut, optimal transport, and permutation synchronization.

Significance. If the results are correct, this is a substantial contribution: it gives explicit, parameter-free convergence rates for entropically regularized SDPs that depend on dimension only logarithmically, without rank assumptions, and it matches the best-known Sinkhorn complexity for optimal transport while allowing additional linear constraints. The deterministic analysis is a genuine strength: the proofs are self-contained, the constants are explicit, and the OT potential bounds (Lemma 44) appear new for general beta. The availability of code and the numerical validation are also positive. However, the advertised stochastic SDP guarantees are not self-contained: the key concentration lemmas are quoted from an unpublished companion paper, and the strong Perm-Synch section contains normalization inconsistencies that affect both the algorithm and the rounding lemma. These issues are load-bearing for the central claims about dimension-independent stochastic SDP solving.

major comments (3)
  1. [Section 4.2.3] The strong Perm-Synch update is inconsistent with the primal problem (2.6). The algorithm defines G_t^(i) = \hat X_t^(i,i) - I_K, but the constraint in (2.6) is X^(i,i) = I_K/n, so the exact dual gradient is X^(i,i) - I_K/n, as used in Theorem 16 and Section 8. With the printed update, the fixed point would have \hat X^(i,i) = I_K, which is not feasible for a density matrix with Tr[X] = 1 and does not match the convergence analysis. This is not a cosmetic typo: it introduces a constant bias of (1 - 1/n)I_K in every iteration. Please correct the update (or, if the problem normalization is intentionally different, restate (2.6) and all subsequent theorems consistently).
  2. [Sections 4.2.1-4.2.4, Lemmas 10/12/14] The stochastic convergence guarantees for Max-Cut and both Perm-Synch SDPs rest entirely on Assumption 9, which is verified only through Lemmas 10, 12, and 14. These are stated as 'reproduced with suitable notation from [29]', an unpublished in-preparation manuscript co-authored by one of the authors, and no proofs are given in this paper. The resulting sample complexities S = O~(gamma^{-2}) and S = O~(gamma^{-2}K), and hence the O~(epsilon^{-3}) iteration complexity claims in Remarks 17, 30, and 33, are conditional on those lemmas. In particular, Lemma 12 requires simultaneous blockwise spectral concentration uniformly over all N blocks and all iterates lambda_t, and this is not an immediate consequence of the cited subspace-embedding fact as presented. If any of these lemmas requires additional hypotheses (for instance, a bound on ||lambda_t|| or on the spectrum of Y_{beta,lambda_t}), the advertised near-linear dimension-independent scaling for the SDP applications does not follow. Please either include complete proofs of these lemmas in this paper or clearly state the theorems as conditional on unpublished results.
  3. [Lemma 31 vs. Theorem 32] There is a normalization mismatch in the strong Perm-Synch rounding argument. Lemma 31 assumes sum_i ||X^(i,i) - I_K||_Tr <= delta and produces X' with [X']^(i,i) = I_K, whereas Theorem 32 and the primal problem (2.6) require the constraint X^(i,i) = I_K/n. The proof thresholds singular values at 1, which is tailored to the target I_K, not I_K/n. A naive rescaling by n would multiply delta by n and destroy the dimension-independence of the result. A corrected lemma with the I_K/n normalization, or an explicit rescaling argument that preserves the delta scaling, is needed before Theorem 32 can be considered proved.
minor comments (7)
  1. [Section 3.3.2] The text identifies the OT dual variable as lambda = (phi, nu); this should presumably be (phi, psi), matching all subsequent formulas.
  2. [Section 4.2.4] The first sentence says 'For the strong Perm-Synch SDP' but the section concerns the weak Perm-Synch SDP; please correct the heading or first sentence.
  3. [Section 8, Remark 33] Remark 33 refers to 'Theorem 29' when the relevant statement is Theorem 32, and it says 'Lemma 13' where Corollary 13 is meant. Also, the remark states S = O~(epsilon^{-2}) for the strong Perm-Synch SDP, while Corollary 13 gives S = O~(gamma^{-2} K log K); the K factor should be acknowledged unless K is explicitly assumed constant.
  4. [Section 6, proof of Theorem 26] The proof ends with 'beta^{-1} log n', but the theorem statement uses 'beta^{-1} log(mn)'. Please make the two consistent.
  5. [Section 9.3, Figure 9.4] The experiment text fixes K=10 and varies N=20,40,60,80,100, but the Figure 9.4 caption lists K = 10,20,30,40,50. Please align the caption with the stated experiment, or clarify which parameter is varied.
  6. [Section 9.4] The final paragraph refers to 'our solver for the strong Perm-Synch SDP' within a discussion of the weak Perm-Synch SDP; this should be 'weak Perm-Synch SDP'.
  7. [Theorems 18 and 20] The definition D := sup_t ||lambda_t - lambda_star||^2 does not explicitly state which norm is used. In the OT application the proof uses the problem-adapted norm, so please specify this in the theorem statements.

Circularity Check

1 steps flagged · score 4.0 of 10

Stochastic SDP guarantees rest on unproved concentration lemmas lifted from an unpublished co-authored manuscript; deterministic and OT derivations are self-contained.

  1. self citation load bearing [Assumption 9; Section 4.2.1 Lemma 10; Section 4.2.3 Lemma 12; Section 4.2.4 Lemma 14; Corollaries 11, 13, 15]
    "To this end, the following lemma, reproduced with suitable notation from [29], is simple consequence of the fact that the Johnson-Lindenstrauss random projection is a subspace embedding [30]: ... In fact we will see that we can take S=~O(gamma^{-2}). To see this, we reproduce the following lemma (with suitable notation) from [29], which is once again a simple consequence of the fact that the Johnson-Lindenstrauss random projection is a subspace embedding [30]:"

    The stochastic dimension-independent SDP claims depend on Assumption 9, which bounds the gradient estimation error. The only validation of Assumption 9 for the Max-Cut and Perm-Synch SDPs is Lemmas 10, 12, and 14, explicitly quoted as 'reproduced with suitable notation from [29]' — an unpublished in-preparation manuscript co-authored by M. Lindsey, an author of this paper. No proof, hypotheses, or external verification appears here; the corollaries only convert the lemmas into sample sizes. Thus the advertised S=~O(gamma^{-2}) and S=~O(gamma^{-2}K) complexities, and the consequent O~(epsilon^{-3}) SDP guarantees, rest on a self-citation chain rather than on a self-contained derivation or an independent checkable result.

full rationale

The deterministic core is not circular: Theorem 16 is proved from the β-smoothness of the dual objective (Corollary 8), Lemma 41, and Lemma 42, with explicit constants; the OT objective and gradient bounds (Theorems 22, 24, 26) are proved self-containedly in Appendix F, including a D bound via Lemma 44; the Max-Cut and strong Perm-Synch rounding lemmas (Lemmas 28, 31) are proved in Appendices G-H. No fitted parameter is renamed as a prediction, and no equation is used as its own conclusion. The circularity-adjacent defect is the stochastic SDP portion: the concentration lemmas that validate Assumption 9 are not proved or even stated with full hypotheses here; they are 'reproduced' from [29], an unpublished co-authored manuscript, and the corollaries that yield sample complexity are applications of those lemmas. This is load-bearing self-citation, so the advertised near-linear stochastic SDP guarantees are not self-contained. I also note, as a non-circular correctness concern, that Section 4.2.3 defines G_t^{(i)} = \hat X_t^{(i,i)} - I_K while problem (2.6) and Theorem 32 use I_K/n, a constant-bias mismatch; this does not affect the circularity score but further weakens the strong Perm-Synch stochastic claim.

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

The central claim relies on standard convex analysis (entropy strong convexity, minimax duality), a norm assumption adapted to the constraints, a bounded-error assumption on stochastic gradients, and unproved concentration lemmas borrowed from an unpublished self-cited manuscript. No parameters are fitted to data, and no new physical entities are introduced.

assumptions (6)
  • standard math The von Neumann entropy S(X)=Tr[X log X] is 1-strongly convex on P1 with respect to the nuclear norm (Theorem 4, cited to [11]).
    Used via convex conjugate duality to establish strong smoothness of the dual objective in Corollary 5 and Corollary 8.
  • standard math Strong duality and existence of a dual optimizer for the entropically regularized problem (Sion's minimax theorem, Slater's condition for the case studies).
    The paper uses strong duality in the proof of Theorem 16 (via -f(λ_T) ≤ p*_{β}) and assumes feasibility of the primal; Slater's condition is stated to hold for all case studies.
  • domain assumption Assumption 6: there exists a norm ||·|| on R^m such that ||λ·A||_2 ≤ ||λ||.
    This norm is the basis of the non-Euclidean descent and bounds the smoothness constant of the dual objective. For the case studies the paper constructs explicit norms in Section 3.3.
  • domain assumption Assumption 9: for each iteration, the gradient estimate satisfies ||g_t - ∇f(λ_t)||_* ≤ γ.
    All convergence theorems are stated under this assumption. For LP it holds with γ=0 by exact computation; for SDPs it is validated with high probability by Lemmas 10, 12, 14, which are quoted from the unpublished reference [29].
  • ad hoc to paper The trace-estimator concentration inequalities in Lemmas 10, 12, and 14 (reproduced from [29]) are valid.
    No proof is provided in this paper; these lemmas guarantee that S = O~(γ^{-2}) or O~(γ^{-2}K) samples suffice for Assumption 9. Their correctness is load-bearing for the stochastic complexity claims.
  • domain assumption The iterates remain within a bounded set, i.e., D = sup_t ||λ_t - λ*|| < ∞, in Theorems 18 and 20.
    The general objective convergence rates contain the constant D, and the paper only proves D is bounded for the OT case (Theorem 22). For general SDPs this is an unverified assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming." pith.science (2026). https://pith.science/paper/YA2RGAPY

@misc{pith2026250609711,
  author       = {Pith},
  title        = {Pith review of: Non-Euclidean dual gradient ascent for entropically regularized linear and semidefinite programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YA2RGAPY}},
  note         = {Machine review of arXiv:2506.09711}
}
read the original abstract

We present an optimization framework that exhibits dimension-independent convergence on a broad class of semidefinite programs (SDPs). Our approach first regularizes the primal problem with the von Neumann entropy, then solve the regularized problem using dual gradient ascent with respect to a problem-adapted norm. In particular, we show that the dual gradient norm converges to zero at a rate independent of the ambient dimension and, via rounding arguments, construct primal-feasible solutions in certain special cases. We also derive explicit convergence rates for the objective. In order to achieve optimal computational scaling, we must accommodate the use of stochastic gradients constructed via randomized trace estimators. Throughout we illustrate the generality of our framework via three important special cases -- the Goemans-Williamson SDP relaxation of the Max-Cut problem, the optimal transport linear program, and several SDP relaxations of the permutation synchronization problem. Numerical experiments confirm that our methods achieve dimension-independent convergence in practice.

Figures

Figures reproduced from arXiv: 2506.09711 by the authors.

Figure 9.1
Figure 9.1. Convergence profile of the primal feasibility error (9.1) for the Max-Cut SDP. Experi [PITH_FULL_IMAGE:figures/full_fig_p025_9_1.png] view at source ↗
Figure 9.2
Figure 9.2. Convergence profile of the dual objective error (9.2) and the primal feasibility error (9.3) [PITH_FULL_IMAGE:figures/full_fig_p027_9_2.png] view at source ↗
Figure 9.3
Figure 9.3. Convergence profile of the dual objective error (9.2) and the primal feasibility error (9.3) [PITH_FULL_IMAGE:figures/full_fig_p028_9_3.png] view at source ↗
Figures from the paper (2 more)
Figure 9.4
Figure 9.4. Figure 9.4: Convergence profile of the primal feasibility error (9.4) for the strong Perm-Synch SDP. [PITH_FULL_IMAGE:figures/full_fig_p029_9_4.png]
Figure 9.5
Figure 9.5. Figure 9.5: Convergence profile of the primal feasibility error (9.5) for the weak Perm-Synch SDP. [PITH_FULL_IMAGE:figures/full_fig_p030_9_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 33 canonical work pages

  1. [29]

    Fast entropy-regularized SDP relaxations for permutation synchronization.In preparation, 2025

    Michael Lindsey and Yunpeng Shi. Fast entropy-regularized SDP relaxations for permutation synchronization.In preparation, 2025

    work page 2025

  2. [1]

    Al-Mohy and Nicholas J

    Awad H. Al-Mohy and Nicholas J. Higham. Computing the action of the matrix exponen- tial, with an application to exponential integrators.SIAM Journal on Scientific Computing, 33(2):488–511, 2011

    work page 2011

  3. [2]

    Linear coupling: An ultimate unification of gradient and mirror descent.arXiv preprint arXiv:1407.1537, 2014

    Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent.arXiv preprint arXiv:1407.1537, 2014

    arXiv 2014

  4. [3]

    Near-linear time approximation al- gorithms for optimal transport via sinkhorn iteration

    Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation al- gorithms for optimal transport via sinkhorn iteration. InAdvances in Neural Information Processing Systems (NeurIPS), volume 30, 2017

    work page 2017

  5. [4]

    The multiplicative weights update method: a meta-algorithm and applications.Theory of computing, 8(1):121–164, 2012

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications.Theory of computing, 8(1):121–164, 2012

    work page 2012

  6. [5]

    SIAM, 2017

    Amir Beck.First-order methods in optimization. SIAM, 2017

    2017

  7. [6]

    Mirror descent and nonlinear projected subgradient methods for convex optimization.Operations Research Letters, 31(3):167–175, 2003

    Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization.Operations Research Letters, 31(3):167–175, 2003

    2003

  8. [7]

    Boumal, B

    N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, a Matlab toolbox for optimiza- tion on manifolds.Journal of Machine Learning Research, 15(42):1455–1459, 2014

    work page 2014

Show all 47 references
  1. [8]

    Boyd and L

    S.P. Boyd and L. Vandenberghe.Convex Optimization. Number pt. 1 in Berichte über verteilte messysteme. Cambridge University Press, 2004. 30

    2004

  2. [9]

    SIAM Studies in Applied Mathematics

    Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan.Linear Matrix Inequalities in System and Control Theory. SIAM Studies in Applied Mathematics. SIAM, 1994

    1994

  3. [10]

    Samuel Burer and Renato D. C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization.Mathematical Programming, 95(2):329–357, 2003

    2003

  4. [11]

    Remainder terms for some quantum entropy inequalities

    Eric A Carlen and Elliott H Lieb. Remainder terms for some quantum entropy inequalities. Journal of Mathematical Physics, 55(4), 2014

    2014

  5. [12]

    Sinkhorn distances: Lightspeed computation of optimal transport.Advances in neural information processing systems, 26, 2013

    Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport.Advances in neural information processing systems, 26, 2013

    2013

  6. [13]

    Distinguishing separable and entangled states.Physical Review Letters, 88(18):187904, 2002

    Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Distinguishing separable and entangled states.Physical Review Letters, 88(18):187904, 2002

    2002

  7. [14]

    Driscoll, Nicholas Hale, and Lloyd N

    Tobin A. Driscoll, Nicholas Hale, and Lloyd N. Trefethen. Chebfun: A new kind of numerical computing.SIAM Review, 56(4):561–588, 2014

    2014

  8. [15]

    Computational optimal trans- port: Complexity by accelerated gradient descent is better than by sinkhorn algorithm

    Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal trans- port: Complexity by accelerated gradient descent is better than by sinkhorn algorithm. In International conference on machine learning, pages 1367–1376. PMLR, 2018

    2018

  9. [16]

    Handbook of convergence theorems for (stochastic) gradient methods.arXiv preprint arXiv:2301.11235, 2023

    Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods.arXiv preprint arXiv:2301.11235, 2023

    2023 arXiv

  10. [17]

    De Gruyter, 2nd edition, 2011

    Hans-Otto Georgii.Gibbs Measures and Phase Transitions. De Gruyter, 2nd edition, 2011

    2011

  11. [18]

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    1995

  12. [19]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan.Matrix Computations. Johns Hopkins University Press, 4th edition, 2013

    2013

  13. [20]

    A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines.Communications in Statistics-Simulation and Computation, 18(3):1059– 1076, 1989

    Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines.Communications in Statistics-Simulation and Computation, 18(3):1059– 1076, 1989

    1989

  14. [21]

    Onthedualityofstrongconvexityand strong smoothness: Learning applications and matrix regularization.Unpublished Manuscript, http://ttic

    ShamKakade, ShaiShalev-Shwartz, AmbujTewari, etal. Onthedualityofstrongconvexityand strong smoothness: Learning applications and matrix regularization.Unpublished Manuscript, http://ttic. uchicago. edu/shai/papers/KakadeShalevTewari09. pdf, 2(1):35, 2009

    2009

  15. [22]

    H. Komiya. Elementary proof for Sion’s minimax theorem.Kodai Math. J., 11(1):5–7, 1988

    1988

  16. [23]

    Entropy penalized semidefinite programming.arXiv preprint arXiv:1802.04332, 2018

    Mikhail Krechetov, Jakub Marecek, Yury Maximov, and Martin Takac. Entropy penalized semidefinite programming.arXiv preprint arXiv:1802.04332, 2018

    2018 arXiv

  17. [24]

    Learning the kernel matrix with semidefinite programming.Journal of Machine Learning Research, 5:27–72, 2004

    Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I Jor- dan. Learning the kernel matrix with semidefinite programming.Journal of Machine Learning Research, 5:27–72, 2004. 31

    2004

  18. [25]

    Fastcomputation of optimal transport via entropy-regularized extragradient methods, 2024

    GenLi, YanxiChen, YuHuang, YuejieChi, H.VincentPoor, andYuxinChen. Fastcomputation of optimal transport via entropy-regularized extragradient methods, 2024

    2024

  19. [26]

    Variational embedding for quantum many-body problems.Com- munications on Pure and Applied Mathematics, 75(9):2033–2068, 2022

    Lin Lin and Michael Lindsey. Variational embedding for quantum many-body problems.Com- munications on Pure and Applied Mathematics, 75(9):2033–2068, 2022

    2022

  20. [27]

    On the efficiency of entropic regularized algorithms for optimal transport.Journal of Machine Learning Research, 23(137):1–42, 2022

    Tianyi Lin, Nhat Ho, and Michael I Jordan. On the efficiency of entropic regularized algorithms for optimal transport.Journal of Machine Learning Research, 23(137):1–42, 2022

    2022

  21. [28]

    Fast randomized entropically regularized semidefinite programming.arXiv preprint arXiv:2303.12133, 2023

    Michael Lindsey. Fast randomized entropically regularized semidefinite programming.arXiv preprint arXiv:2303.12133, 2023

    2023 arXiv

  22. [30]

    Per-Gunnar Martinsson and Joel A. Tropp. Randomized numerical linear algebra: Foundations and algorithms.Acta Numerica, 29:403–572, 2020

    2020

  23. [31]

    Hutch++: Optimal stochastic trace estimation

    Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff. Hutch++: Optimal stochastic trace estimation. InSymposium on Simplicity in Algorithms (SOSA), pages 142–155. SIAM, 2021

    2021

  24. [32]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  25. [33]

    Nielsen and I

    M. Nielsen and I. Chuang.Quantum computation and quantum information. Cambridge Uni- versity Press, 2001

    2001

  26. [34]

    Solving the multi-way matching problem by permutation synchronization.Advances in neural information processing systems, 26, 2013

    Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by permutation synchronization.Advances in neural information processing systems, 26, 2013

    2013

  27. [35]

    PhD thesis, California Institute of Technology, 2000

    Pablo A Parrilo.Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000

    2000

  28. [36]

    Logarithmically sparse symmetric matrices.Beiträge zur Algebra und Geome- trie/Contributions to Algebra and Geometry, pages 1–16, 2024

    Dmitrii Pavlov. Logarithmically sparse symmetric matrices.Beiträge zur Algebra und Geome- trie/Contributions to Algebra and Geometry, pages 1–16, 2024

    2024

  29. [37]

    Gibbs manifolds.Information Geometry, 7(Suppl 2):691–717, 2024

    Dmitrii Pavlov, Bernd Sturmfels, and Simon Telen. Gibbs manifolds.Information Geometry, 7(Suppl 2):691–717, 2024

    2024

  30. [38]

    Computational optimal transport: With applications to data science.Foundations and Trends®in Machine Learning, 11(5-6):355–607, 2019

    Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science.Foundations and Trends®in Machine Learning, 11(5-6):355–607, 2019

    2019

  31. [39]

    Entropic estimation of optimal transport maps, 2024

    Aram-Alexandre Pooladian and Jonathan Niles-Weed. Entropic estimation of optimal transport maps, 2024

    2024

  32. [40]

    Coordinate methods for acceleratingℓ∞ regression and faster approximate maximum flow

    Aaron Sidford and Kevin Tian. Coordinate methods for acceleratingℓ∞ regression and faster approximate maximum flow. In2018 IEEE 59th Annual Symposium on Foundations of Com- puter Science (FOCS), pages 922–933. IEEE, 2018

    2018

  33. [41]

    SIAM, 2019

    Lloyd N Trefethen.Approximation theory and approximation practice, extended edition. SIAM, 2019. 32

    2019

  34. [42]

    Mathematische grundlagen der quantenmechanik

    John von Neumann. Mathematische grundlagen der quantenmechanik. 1932. Translated as *Mathematical Foundations of Quantum Mechanics*

    1932

  35. [43]

    An explicit analysis of the entropic penalty in linear programming

    Jonathan Weed. An explicit analysis of the entropic penalty in linear programming. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors,Proceedings of the 31st Conference On Learning Theory, volume 75 ofProceedings of Machine Learning Research, pages 1841–1855....

    2018

  36. [44]

    Distance metric learning for large margin nearest neighbor classification.Journal of Machine Learning Research, 10:207–244, 2009

    Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification.Journal of Machine Learning Research, 10:207–244, 2009

    2009

  37. [45]

    Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher

    Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Scalable semidefinite programming.SIAM Journal on Mathematics of Data Science, 3(1):171–200, 2021. 33 Appendices A Proofs for norms In this section, we offer proofs deferred from Section 3.3. A.1...

    2021

  38. [46]

    In Step 1, we show that if[ϕt]i −[ϕ t]k ≥2M+ log(1/s) β , then[ϕ t+1]i −[ϕ t+1]k ≤[ϕ t]i −[ϕ t]k

  39. [47]

    Step 1.Consider the marginalµ t =π β,λt 1n appearing in (4.8) via the differenceµt −µ(which is the dual gradient with respect toϕ)

    In Step 2, we show that the desired result follows (using the fact thatϕ0 = 0andψ 0 = 0). Step 1.Consider the marginalµ t =π β,λt 1n appearing in (4.8) via the differenceµt −µ(which is the dual gradient with respect toϕ). We can compute elementwise: [µt −µ] k = Pn j=1 exp h β ...

Pith tools

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