[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3357713.3384302acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article
Open access

On the computability of continuous maximum entropy distributions with applications

Published: 22 June 2020 Publication History

Abstract

We initiate a study of the following problem: Given a continuous domain Ω along with its convex hull K, a point AK and a prior measure µ on Ω, find the probability density over Ω whose marginal is A and that minimizes the KL-divergence to µ. This framework gives rise to several extremal distributions that arise in mathematics, quantum mechanics, statistics, and theoretical computer science. Our technical contributions include a polynomial bound on the norm of the optimizer of the dual problem that holds in a very general setting and relies on a “balance” property of the measure µ on Ω, and exact algorithms for evaluating the dual and its gradient for several interesting settings of Ω and µ. Together, along with the ellipsoid method, these results imply polynomial-time algorithms to compute such KL-divergence minimizing distributions in several cases. Applications of our results include: 1) an optimization characterization of the Goemans-Williamson measure that is used to round a positive semidefinite matrix to a vector, 2) the computability of the entropic barrier for polytopes studied by Bubeck and Eldan, and 3) a polynomial-time algorithm to compute the barycentric quantum entropy of a density matrix that was proposed as an alternative to von Neumann entropy by Band and Park in the 1970s: this corresponds to the case when Ω is the set of rank one projection matrices and µ corresponds to the Haar measure on the unit sphere. Our techniques generalize to the setting of rank k projections using the Harish-Chandra-Itzykson-Zuber formula, and are applicable even beyond, to adjoint orbits of compact Lie groups.

References

[1]
Zeyuan Allen Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In FOCS’17: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, 2017.
[2]
Arash Asadpour, Michel X Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi. An O (log n / log log n)-approximation algorithm for the asymmetric traveling salesman problem. Operations Research, 65(4):1043–1061, 2017.
[3]
William Band and James L. Park. New information-theoretic foundations for quantum statistics. Foundations of Physics, 6(3):249–262, Jun 1976.
[4]
Alexander Barvinok and Isabella Novik. A centrally symmetric version of the cyclic polytope. Discrete & Computational Geometry, 39(1-3):76–99, 2008.
[5]
Aharon Ben-Tal and Arkadi Nemirovski. Optimization III: Convex analysis, nonlinear programming theory, nonlinear programming algorithms. Lecture Notes, 2012.
[6]
Christopher Bingham. An antipodally symmetric distribution on the sphere. Ann. Statist., 2(6):1201–1225, 11 1974.
[7]
Sébastien Bubeck and Ronen Eldan. The entropic barrier: a simple and optimal universal self-concordant barrier. In Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 279–279, Paris, France, 03–06 Jul 2015. PMLR.
[8]
Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 883–897, 2018.
[9]
Joseph T Chang and David Pollard. Conditioning as disintegration. Statistica Neerlandica, 51(3):287–317, 1997.
[10]
Matthias Christandl, Brent Doran, Stavros Kousidis, and Michael Walter. Eigenvalue distributions of reduced density matrices. Communications in mathematical physics, 332(1):1–52, 2014.
[11]
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained Newton’s method and interior point methods. In FOCS’17: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, 2017.
[12]
J. J. Duistermaat and G. J. Heckman. On the variation in the cohomology of the symplectic form of the reduced phase space. Inventiones mathematicae, 69(2):259–268, Jun 1982.
[13]
Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Operator scaling: theory and applications. Foundations of Computational Mathematics, pages 1–68, 2015.
[14]
Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, November 1995.
[15]
M. Gromov. Convex sets and Kahler manifolds, pages 1–38. 1990.
[16]
Osman Güler. Barrier functions in interior point methods. Mathematics of Operations Research, 21(4):860–885, 1996.
[17]
Osman. Güler. On the self-concordance of the universal barrier function. SIAM Journal on Optimization, 7(2):295–303, 1997.
[18]
Osman Güler and Levent Tunçel. Characterization of the barrier parameter of homogeneous convex cones. Mathematical Programming, 81(1):55–76, Mar 1998.
[19]
Leonid Gurvits and Alex Samorodnitsky. A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume, and a combinatorial corollary. Discrete & Computational Geometry, 27:531–550, 2002.
[20]
Harish-Chandra. Differential operators on a semisimple lie algebra. American Journal of Mathematics, 79(1):87–120, 1957.
[21]
Peter D. Hoff. Simulation of the matrix bingham-von mises-fisher distribution, with applications to multivariate and relational data. Journal of Computational and Graphical Statistics, 18(2):438–456, 2009.
[22]
Alfred Horn. Doubly stochastic matrices and the diagonal of a rotation matrix. American Journal of Mathematics, 76(3):620–630, 1954.
[23]
C. Itzykson and J. Zuber. The planar approximation. ii. Journal of Mathematical Physics, 21(3):411–421, 1980.
[24]
Edwin T. Jaynes. Information theory and statistical mechanics. Physical Review, 106:620–630, May 1957.
[25]
Edwin T. Jaynes. Information theory and statistical mechanics. II. Physical Review, 108:171–190, October 1957.
[26]
C. G. Khatri and K. V. Mardia. The von mises-fisher matrix distribution in orientation statistics. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):95–106, 1977.
[27]
B. Klartag. On convex perturbations with a bounded isotropic constant. Geometric & Functional Analysis GAFA, 16(6):1274–1290, Dec 2006.
[28]
Anthony W Knapp. Lie groups beyond an introduction, volume 140. Springer Science & Business Media, 2013.
[29]
Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming, volume 13. Siam, 1994.
[30]
James L. Park and William Band. Rigorous information-theoretic derivation of quantum-statistical thermodynamics. i. Foundations of Physics, 7(3):233–244, Apr 1977.
[31]
Damián Pinasco. Lower bounds for norms of products of polynomials via bombieri inequality. Transactions of the American Mathematical Society, 364(8):3993–4010, 2012.
[32]
Raman Sanyal, Frank Sottile, and Bernd Sturmfels. Orbitopes. Mathematika, 57(2):275–314, 2011.
[33]
Issai Schur. Uber eine klasse von mittelbildungen mit anwendungen auf die determinantentheorie. Sitzungsberichte der Berliner Mathematischen Gesellschaft, 22(9-20):51, 1923.
[34]
Mohit Singh and Nisheeth K Vishnoi. Entropy, optimization and counting. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 50–59. ACM, 2014.
[35]
Paul B. Slater. Relations between the barycentric and von neumann entropies of a density matrix. Physics Letters A, 159(8):411 – 414, 1991.
[36]
Damian Straszak and Nisheeth K. Vishnoi. Maximum entropy distributions: Bit complexity and stability. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2861–2891, Phoenix, USA, 25–28 Jun 2019. PMLR.
[37]
Michèle Vergne. Convex polytopes and quantization of symplectic manifolds. Proceedings of the National Academy of Sciences, 93(25):14238–14242, 1996.
[38]
J. von Neumann and R.T. Beyer. Mathematical Foundations of Quantum Mechanics. Goldstine Printed Materials. Princeton University Press, 1955.

Cited By

View all
  • (2023)Projections of orbital measures and quantum marginal problemsTransactions of the American Mathematical Society10.1090/tran/8931376:8(5601-5640)Online publication date: 23-May-2023
  • (2022)Re-analyze gaussProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3603066(38585-38599)Online publication date: 28-Nov-2022
  • (2021)Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacyProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451094(1384-1397)Online publication date: 15-Jun-2021
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
June 2020
1429 pages
ISBN:9781450369794
DOI:10.1145/3357713
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Entropy
  2. Optimization
  3. Quantum entropy

Qualifiers

  • Research-article

Funding Sources

  • NSF
  • Vetenskapsrådet

Conference

STOC '20
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)115
  • Downloads (Last 6 weeks)19
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Projections of orbital measures and quantum marginal problemsTransactions of the American Mathematical Society10.1090/tran/8931376:8(5601-5640)Online publication date: 23-May-2023
  • (2022)Re-analyze gaussProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3603066(38585-38599)Online publication date: 28-Nov-2022
  • (2021)Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacyProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451094(1384-1397)Online publication date: 15-Jun-2021
  • (2021)Algorithms for Convex Optimization10.1017/9781108699211Online publication date: 24-Sep-2021

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media